Loading...

Loading...

Scroll

Categories

Tags

Monthly Archives

Keyword

Back

SPECTRE:4. THE SPECTRE PROTOCOL

2018.04.04

Category

Tags

Source: https://eprint.iacr.org/2016/1159.pdf
TranStudy: https://github.com/DAGfans/TranStudy/new/master/Papers/SPECTRE

4. THE SPECTRE PROTOCOL

4. SPECTRE 协议

A. The generation of the block DAG

A. 区块 DAG 的产生

As in Bitcoin, participating nodes (called miners) create blocks of transactions by solving PoW puzzles. A block specifies its direct predecessors by referencing their ID in its header (a block’s ID is obtained by applying a collision resistant hash to its header); we will describe in the next subsection how these predecessors are chosen. This results in a structure of a direct acyclic graph (DAG) of blocks (as blocks can only reference blocks created before them), denoted typically $G = (C, E)$. Here, C represents blocks and E represents the hash references. We will frequently write z ∈ G instead of z ∈ C .

和比特币一样,参与节点(称为矿工)通过解决PoW难题来创建交易的区块。 一个块通过在其头部引用其前置节点的ID来引用它们(一个块的ID是通过对其头部执行抗碰撞散列函数来获得的); 我们将在下一小节描述如何选择这些前置节点。 这将生成一个区块的有向无环图(DAG)的结构(因为块只能引用在它们之前创建的块),通常表示为$G = (C, E)$。 这里,C表示块,E表示散列引用。 我们将经常写成$z∈G$而不是$z∈C$。

$past (z, G) ⊂ C$ denotes the subset of blocks reachable from z , and similarly $future (z, G) ⊂ C$ denotes the subset of blocks from which z is reachable; these are blocks that were provably created before and after z , correspondingly. Note that an edge in the DAG points back in time, from the new block to previously created blocks which it extends. A node does not consider a block as valid until it receives its entire past set. We denote by $cone (z, G)$ the set of blocks that the DAG directly orders with respect to $z : cone (z, G) := past (z, G)∪{z}∪future (z, G)$, and by $anticone (z)$ the complementary of $cone (z, G)$. The set $past (b, G)$ is fixed once and for all at the creation of b (in sharp contrast to $future (z, G)$ and $anticone (z, G)$ that may grow as blocks are added later to the DAG), hence we can simply write $past (b)$ without noting the context.

$past (z, G) ⊂ C$表示可从z到达的块的子集,类似地$future (z, G) ⊂ C$表示可到达z的块的子集; 这些相应地可以证明是在z之前和之后创建的块。 请注意,DAG中的一条边的方向跟时间是相反的,从新块指向它以前创建的块来延展。 一个节点在接收到某区块过去的整个集合之前不会将该区块视为有效。 我们用$cone (z, G)$表示z在DAG中可以确定顺序的集合,即$cone (z, G) := past (z, G)∪{z}∪future (z, G)$和用$anticone (z)$表示剩下的部分。 集合$past (b, G)$在b创建时生成后就会固定下来(而$future (z, G)$和$anticone (z, G)$则不一样,随着块被添加到DAG中,它们可以增长) 因此我们可以简单地写成$past (b)$而不用考虑上下文。 译注: 这里的上下文主要考虑的是时间,因为过去集合在创建时就固定下来了,所以无论在那个时间点讨论都是一样的,但是将来集合和反锥体会随时间增长而增大,所以在讨论时必须指定时间。

The unique block genesis is the block created at the inception of the system, and every valid block must have it in its past set. In addition, we relate to a hypothetical block, $virtual (G)$. This block satisfies $past (virtual (G))=G$. While its role is merely methodological, $virtual (G)$ can also be thought of as representing the next block that a node whose current observed DAG is G attempts to create.

唯一的创世区块是在系统开始时创建的,并且每个有效的区块必须在其过去集合中包含它。 另外,我们还涉及一个假设的区块,$virtual (G)$。 这个块满足$past (virtual (G))=G$。 虽然它的作用仅仅是便于讨论,但是$virtual (G)$也可以被认为是代表节点尝试创建的下一个块,该节点当前观察到的DAG是G。

$G_t^v$ denotes the block DAG observed by node $v ∈ \mathcal{N}$ at time t. This DAG represents the history of all (valid) block-messages received by the node, instantiating the abstract data structure assumed in Section 2.

$G_t^v$表示在时间t由节点$v ∈ \mathcal{N}$观察到的块DAG。 这个DAG表示节点接收的所有(有效)块消息的历史,是第2节中假设的抽象数据结构的实现。

B. The mining protocol

B. 挖矿协议

SPECTRE’s instructions to miners are extremely simple:

1) When creating or receiving a block, transmit the block to all peers.

2) When creating a block, embed in its header a list containing the hash of all leaf-blocks (blocks with in-degree 0) in the locally-observed DAG.

SPECTRE中矿工的规则非常简单:

1) 创建或接收块时,将块发送给所有对等节点。

2) 创建块时,在其头中嵌入一个列表,其中包含本地观察到的DAG中所有叶块(入度为0的块)的散列。

Note that these instructions allow miners to operate concurrently irrespective of potential conflicts in the contents of their blocks.

请注意,这些说明允许矿工同时进行操作,而不管其区块内容是否存在潜在的冲突。

C. The TxO protocol

C. TxO 协议

Overview

As the block DAG may contain conflicting transactions, we must provide a method for nodes to interpret the DAG and extract from it the set of accepted transactions. Doing so in a way that will be agreed upon by all nodes (eventually) is the main challenge of SPECTRE. We now describe how this is done.

概述

由于块DAG可能包含冲突交易,因此我们必须提供一种方法让节点解释DAG并从中提取一组已接受的交易。 该方法必须保证所有节点(最终)达成一致,这是SPECTRE的主要挑战。 我们现在描述这是如何完成的。

The topology of a block DAG G induces a natural precedence-relation over blocks: if x is reachable from y (i.e., $x ∈ past (y)$) then x precedes y , as it was provably created before it. SPECTRE extends this relation into a complete relation over G’s blocks, denoted $≺$ . This order is immediately translatable into an order over transactions in G: tx 1 precedes tx 2 if the block containing the former precedes that containing the latter. This relation, in turn, induces a natural subset of accepted transactions: tx is accepted if it precedes all of its conflicting transactions in G. The relation  is generated by a pairwise vote procedure that occurs independently for every pair of blocks. The operation of this layer will be explained in the next subsections.

块DAG G的拓扑结构在块上产生自然的优先关系:如果x能从y到达(即$x ∈ past (y)$),那么x在y之前,因为x可以证明在y之前创建。 SPECTRE将这个关系扩展为G块中的完整关系,记为$≺$。 这个顺序可以直接解释成G中的交易顺序:如果包含$tx_1$的块在包含$tx_2$的块的前面,则$tx_1$在$tx_2$之前。 反过来,这种关系自然地引入了一个已接受的交易的子集:如果tx在G中的所有冲突交易之前,则tx被接受。 (译注: 这里的已接受的交易不确定有没有包括冲突的交易,感觉这里存在语言的模糊,因为存在两个accept,第一个似乎允许冲突存在,第二个则相反。这个问题很关键,因为这会涉及到账本中允不允许存放双花交易,似乎允许的可能性比较大,即第一个accept可能指的是存放账本,第二个accept可能指这笔交易是有效的而其他是非法的) 这个关系是通过对每对区块逐一独立地投票生成的。 这一层的操作将在下一小节中解释。

Although we may at times refer to $≺$  as though it orders blocks, we stress that $≺$ is not necessarily a transitive relation. It is possible to have a series of blocks that precede each other cyclically. 1 The lack of a total linear ordering over blocks is in fact the way SPECTRE utilizes the weaker consensus requirements of our framework, as a linear order is equivalent to solving the consensus problem [3].

虽然我们有时可能会提到$≺$好像它可以给所有区块排序,但是我们要强调$≺$不一定是传递关系。 因为可能会存在一系列的区块是循环前置关系。1译注: 例如A<B, B<C, C<A) 实际上,SPECTRE利用我们框架中较弱的一致性要求造成了区块的线形全序的缺失,因为线性顺序相当于解决共识问题[3]。 (译注: 所以有了后来的PHANTOM)

Pairwise ordering of blocks.

The basic layer of SPECTRE involves deciding on a pairwise order over the block DAG. Fix two blocks $x, y ∈ G$. In order to decide if $x≺y$ or $y≺x$, we interpret the structure of the DAG as representing an abstract vote. Every block $z ∈ G$ is considered a voter with respect to the pair (x, y), and its vote is inferred from the structure of the DAG. We represent a vote by a number in {−1, 0, +1}, and we denote z ’s voting-profile on all pairs by $vote (z, G)$. $vote_{x,y} (z, G) = -1$ represents x preceding y $(x≺y)$, $vote_{x,y} (z, G) = +1$ represents y preceding x, and $vote_{x,y}(z, G) = 0$ represents a tie. Importantly, $vote (z, G)$ is an asymmetric relation: $vote_{y,x}(z, G) =-vote_{x,y}(z, G)$.

区块的成对排序

SPECTRE的基础层涉及确定块DAG上的成对块之间顺序。 指定两个块$x, y ∈ G$. 为了确定是$x≺y$还是$y≺x$,我们将DAG的结构理解为一个抽象的投票。 每个块$z ∈ G$被认为是对区块对 (x, y)进行投票的投票者,并且它的一票是从DAG的结构中推断出来的。 我们用{−1, 0, +1}中的一个数字来表示一票,并且我们用$vote (z, G)$表示z对所有区块对的投票信息。 $vote_{x,y} (z, G) = -1$代表x在y之前$(x≺y)$,$vote_{x,y} (z, G) = +1$代表y在x之前,$vote_{x,y}(z, G) = 0$代表是平票的。 译注: tie的定义在这里 重要的是,$vote (z, G)$是一个反对称关系:$vote_{y,x}(z, G) =-vote_{x,y}(z, G)$。

To simplify presentation, we associate a vote with $virtual (G)$ as well. Recall that the virtual block of G is a hypothetical block which satisfies $past (virtual (G)) = G$. The vote of $virtual (G)$ represents essentially the aggregated vote of the entire block DAG. The basic rules of z ’s vote, for any $z ∈ G ∪ {virtual (G)}$, are as follows:

1) if $z ∈ G$ is in $future (x)$ but not in $future (y)$ then it will vote in favour of x (i.e., for $x≺y$ ).

2) if $z ∈ G$ is in $future (x)∩future (y)$ then z ’s vote will be determined recursively according to the DAG that is reduced to its past, i.e., it has the same vote as $virtual (past (z))$. If the result of this vote is a tie, z breaks it arbitrarily. 2

3) if $z ∈ G$ is not in the future of either blocks then it will vote the same way as the vote of the majority of blocks in its own future.

4) if z is the virtual block of G then it will vote the same way as the vote of the majority of blocks in G.

5) finally, (for the case where z equals x or y ), z votes for itself to succeed any block in $past (z)$ and to precede any block outside $past (z)$.

为了简化演示,我们也让$virtual (G)$参与投票。 回想一下,G的虚拟块是一个满足$past (virtual (G)) = G$的假设块。 $virtual (G)$的投票本质上表示整个块DAG的聚合投票。 对于任何$z ∈ G ∪ {virtual (G)}$,z的投票基本规则如下:

1) 如果$z ∈ G$在$future (x)$但不在$future (y)$中,则它将投票给x(即,$x≺y$)。

2) 如果 $z ∈ G$在$future (x)∩future (y)$中,那么z的投票则简化为根据其过去集来递归确定,即它与 $virtual (past (z))$的投票相同。 (译注: 这句理解为如果z在x和y的未来集里,则把z 的过去集当成当前的DAG,而z本身当作下一个块,也就是虚拟块,虚拟块的排序参见规则3) 如果这次投票的结果是平票,z可以用任意规则打破。 2译注: 任意规则就是自定义的规则,比如说用区块的散列值,因为这个规则所有节点都是一样的,所以可能会造成误判,但是可以保证一致性)

3) 如果$z ∈ G$不在任何一个块的未来集中,那么它将以与其未来集大多数块的投票相同。

4) 如果z是G的虚拟块,那么它将以与G中大多数块的投票相同。

5) 最后,(对于z等于x或y的情况),z投票自己在$past (z)$中的任何块之后,并且在任何$past (z)$之外的块之前。

这与社会选择中的Condorcet悖论有关[2]。

我们可以使用z头部中编码的信息,例如明确的打破平票的指令,或者使用平票块的(散列)的字典顺序等。

Fig. 1: An example of the voting procedure on a simple DAG.

Fig. 1: An example of the voting procedure on a simple DAG. Block x and blocks 6-8 vote $x≺y$ as they only see x in their past, and not y . Similarly, block y and blocks 9-11 vote $y≺x$. Block 12 votes according to a recursive call on the DAG that does not contain blocks 10,11,12. Any block from 1-5 votes $x≺y$ , because it sees more $x≺y$ voters in its future than $y≺x$ voters.

图1:一个简单的DAG上投票流程的例子。 块x和块6-8投票$x≺y$ 因为他们在他们的过去集中只看到x,而没有看到y。 同样,块y和块9-11投票$y≺x$ 。 (译注: 上面两条是规则1,等于6-8在x的将来集,9-11在y的将来集) 块12的投票根据在不包含块10,11,12的DAG上的递归调用得到。 (译注: 块12之所以只考虑不包含10,11,12是因为块12既属于x的将来集也属于y的将来集,满足规则2,那这个时候看块12的过去集,自然10,11,12就排除掉了。然后因为块12可以看作是 块12的过去集的虚拟块即 $virtual(past(block12))$), 满足规则4,则统计block12的过去集中各个节点的票数,发现投 $x≺y$的有x,6,7,8,投$y≺x$的有y,9,4比2所以$y≺x$ 1-5中的任何块投票$x≺y$,因为它看到投$x≺y$比$y≺x$更多的投票者。 (译注: 然后1-5均不在x或y的未来集里,满足规则3,则看他们的将来集中的投票情况,显然2会投x,因为其未来集x,6,7,8,12都是投x,没有投y;5也显然会投x,因为其未来集投x的有7,8,12,投y的有9,11,3比2;3会投x因为其未来集投x的有x,6,7,8,12,投y的有y,9,10,11,5比4;4的未来集投x的有x,5,6,7,8,12,投y的有y,9,10,11,6比4;1显然投x)

Intuitively, the first rule dictates that a block that was honestly published gain votes over blocks that are secretly withheld, as honest nodes keep adding new blocks to its future set. The second and fourth rules together guarantee majority amplification, as new blocks add votes that comply with and enhance previous decisions. The third rule is the most subtle; basically, it allows blocks in $past (x)$ (in addition to those in $future (x)$) to vote in its favour against y , in case y was withheld for a long time. This is needed to counter a pre-mining attack scheme, which will be described in future sections. Notice that all votes respect the DAG’s topology: If x is reachable from y then all blocks vote unanimously $x≺y$ .

直观的理解就是,第一条规则规定,一个诚实节点发布的区块的投票会获得高于对被暗中扣留的区块,因为诚实的节点不断为其未来集合添加新的区块。 第二和第四条规则共同保证了会放大大多数人的投票,因为新的区块投票给了符合先前决定的区块,从而增强了该区块。 第三条规则是最微妙的; 基本上,它允许$past (x)$ 的区块(加上$future (x)$的之外的区块)投票反对y,以防y被长时间扣留。 (译注: 比如说5就既不在$past (x)$也不在$future (x)$) 这是对付图谋预挖矿攻击所需要的,这将在以后的章节中介绍。 请注意,所有投票都遵守DAG的拓扑结构的规则:如果可从y到达x,那么所有块都一致投票$x≺y$。 (译注: 比如说上图中,5可以从9到达,则$5≺9$)

Figure 1 illustrates the voting procedure with regards to a single pair of blocks (x,y ). Additional examples along with intuition regarding this key algorithm are provided in Appendix A.

图1图解了关于区块对(x,y)的投票流程。 附录A提供了有关此关键算法的其他示例以及思路。 (译注: Intuition 翻译成思路,直译成直觉实在很难理解。)

The voting procedure is implemented in Algorithm 1 below. In the algorithm, $\widetilde{sgn}(n) =-1$ for $n < 0$, $\widetilde{sgn}(n) =+1$ for $n > 0$, and $\widetilde{sgn}(0) =0$. To see that the recursion calls from line 4 halt, observe that they take as inputs DAGs strictly smaller than G (because $past (z)⊈ ( G)$, and hence eventually all arrive at the base case $G=ϕ$ and return. The algorithm is written in its naive form, for the sake of readability, with a run time of $\mathcal{O}(|G|^3 )$. We have written a more sophisticated implementation of this procedure, which runs in expected time of $\mathcal{O}(d\cdotλ)$. We will make the code available online in the full version.

投票程序在下面的算法1中实施。 在算法中,当$n < 0$时,$\widetilde{sgn}(n) =-1$,$n > 0$时$\widetilde{sgn}(n) =+1$,$\widetilde{sgn}(0) =0$。 为了保证第4行的递归调用会停止,可以看到它们将输入的DAG严格小于G(因为$past (z)⊂( G)$),因此最终会全部到达基本情况$G=ϕ$并返回。 为了便于阅读,算法采用简单的形式编写,运行时间为$\mathcal{O}(|G|^3 )$. 我们已经编写了一个实现更复杂的程序,该程序预期时间为$\mathcal{O}(d\cdotλ)$,我们将会上线完整版可用代码。

The pairwise ordering of SPECTRE has the following highly valuable property:

SPECTRE的成对排序具有以下非常有价值的属性:

Property 4

Once a block is published, the set of blocks that precede it in the pairwise ordering closes fast— w.h.p. it consists only of blocks published before or right after its publication.

属性 4

区块发布后,经过成对排序,顺序在它之前的集合会很快地固定下来。 极有可能它仅包含在其它发布之前或紧挨着在它之后发布的块。

The implications of this guarantee to the security of transactions is immediate, at least at the intuitive level: A user whose transaction is embedded in some published block x can guarantee its safety by waiting some time after x’s publication before accepting it; he is then guaranteed that any block published later on – and that might contain a conflicting transaction – will be preceded by x hence will not threaten the acceptance of his transaction. In Section 5 we will explain how this guarantee is achieved.

这种保证对交易安全的影响是非常直接的,至少在直观的层面上是这样的: 一个用户的交易被嵌入到某个已发布的区块x中,可以通过在接受x之前等待一段时间来保证其安全性; 那么他可以保证,任何后来发布的区块 - 可能包含冲突交易 - 都将在x之后,因此不会威胁到他到交易的接受。 在第5节中,我们将解释如何实现这一保证。

Algorithm 1 $CalcVotes$

Input: G – a block DAG Output: $vote (virtual (G))$ – a pairwise ordering of blocks in G

  1. if $G = ϕ$ then
  2. return an empty ordering

  3. for all $z ∈ G$ do
  4. $vote (z, past (z)) ← CalcVotes (past (z))$ and break ties arbitrarily

  5. for all $z ∈ G$ in some topological order (from leaves to root) do
  6. for all $x, y ∈ G (x ≠ y)$ do 

  7. if $x ∈ (\overline{past} (z) ∧ y ∉ past (z))∨(x ∈ past (z) , y = z)$ then

  8. $vote_{x,y}(z, G) ←-1$

  9. else if $(y ∈ \overline{past} (z)∧ (x ∉ past (z)) ∨ (y ∈ past (z) , x = z))$ then

  10. $vote_{x,y}(z, G) ←+1$

  11. else if $x, y ∈ past (z)$ then

  12. $vote_{x,y}(z, G) ←vote_{x,y}(z, past (z))$

  13. else if $x, y ∉ past (z)$ then  

  14. $vote_{x,y}(z, G) ←\widetilde{sgn}(\sum_{z’∈future(z,G)}vote_{x,y}(z’, G))$

  15. $vote (virtual (G) , G) ← \widetilde{sgn}(\sum_{z∈G}vote (z, G))$
  16. return $vote (virtual (G) , G)$

Accepting transactions

Equipped with the pairwise relation over blocks, we now turn to construct the set of accepted transactions. To maintain consistency, we mark a transaction as accepted iff all three conditions below hold true:

1) all of its inputs have been accepted.

2) all conflicting transactions from its anticone set (i.e., that are not related to it topologically) are contained in blocks that are preceded by the block containing the transaction.

3) all conflicting transactions from its past set (i.e., that precede it in the DAG, topologically) have been rejected.

接受交易

通过对区块进行配对,我们就可以开始构建一组已接受的交易。 为了保持一致性,如果以下所有三个条件都成立,我们将交易标记为已接受:

1) 所有的输入都已被接受。

2) 反锥体中所有与其冲突的交易(即无法确定拓扑顺序的交易)都在包含该交易的区块后面的区块中。

3) 过去集中所有冲突的交易(即在拓扑顺序上先于它DAG)都已被拒绝。 (译注: 这里的拓扑顺序就是指在存在一条路径经过两个参与比较的节点,如果不存在,则认为无法拓扑定序,所以区块是无法和其反锥体里面的任意区块定序)

Algorithm 2 implements these rules, and outputs a set of accepted transactions. It operates recursively, and should be initially called with $TxO(G, G)$ (we later denote this simply by $TxO(G)$). In the algorithm, the notation $Z_G (tx)$ stands for all blocks in G that contain tx. Some complexity arises due to possible multiple copies of the same transaction in the DAG; we denote by $[tx]$ the equivalence class containing all of tx’s copies.

算法2实现了这些规则,并输出一组已接受的交易。 它递归地运行,并且首先应该被$TxO(G, G)$调用(我们稍后通过 $TxO(G)$简单地表示)。 (译注: 这个TxO也是一个算法,在第五章介绍) 在算法中,符号 $Z_G (tx)$代表G中包含tx的所有块。 由于DAG中可能存在多个相同交易的副本,因此会出现一些复杂性; 我们用$[tx]$表示包含所有tx副本的等价类。 (译注: 这里明确说明了DAG中不同区块是允许存在重复的交易的)

Algorithm 2 TxO Input: G – a block DAG, subG – a subDAG of G which is the past of a (possibly virtual) block Output: $Tx$ – a hyper-set of valid transactions in G

  1. $vote (virtual (G)) ← CalcVotes(G)$
  2. $Tx ←ϕ$
  3. for all $z_1 ∈ subG$ do
  4. for all $tx ∈ z_1$ do

  5. for all $tx_2 ∈ G ∩ conflict (tx)$ do

  6. for all $z_2 ∈ Z_G (tx 2 ) ∩ anticone (z_1 , G)$ do

  7. if $vote_{z_1 ,z_2} (virtual (G)) ≥ 0$ then

  8. break (to line 4 and pick next $tx$)

  9. if $[tx_2 ] ∩ TxO(G, past (z_1 )) ≠ ϕ$ then

  10. break (to line 4 and pick next $tx$)

  11. for all $[tx_3 ] ∈ inputs (tx)$ do

  12. if $[tx_3 ] ∩ TxO (G, past (z_1 )) = ϕ$ then

  13. break (to line 4 and pick next $tx$)

  14. add $tx$ to $Tx$

  15. return $Tx$

The third part of the SPECTRE protocol, namely, the RobustTxO procedure, is rather involved. We defer its description to Appendix C.

SPECTRE协议的第三部分,即RobustTxO程序,是非常相关的。 我们将其描述推迟到附录C.

  1. This is related to the Condorcet paradox in social choice [2].  2

  2. We can use information encoded in z’s header, e.g., explicit instructions for tie-breaking, or use the lexicographical ordering of (hashes of) tied blocks, etc.  2

Related Posts

Top