Scroll

Categories

Tags

Monthly Archives

Keyword

Back

2018.04.04

# 4. SPECTRE 协议

## A. 区块 DAG 的产生

As in Bitcoin, participating nodes (called miners) create blocks of transactions by solving PoW puzzles. A block speciﬁes 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 .

$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 ﬁxed 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 satisﬁes $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.

$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. 挖矿协议

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 conﬂicts in the contents of their blocks.

## C. TxO 协议

### Overview

As the block DAG may contain conﬂicting 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.

### 概述

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 conﬂicting 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.

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].

### 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-proﬁle 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 satisﬁes $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) ﬁnally, (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)$.

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)$之外的块之前。

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.

Intuitively, the ﬁrst 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 ampliﬁcation, 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$ .

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.

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.

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 conﬂicting 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.

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 conﬂicting 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 conﬂicting 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.

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

Top