Monthly Archives







Source: https://eprint.iacr.org/2018/104.pdf
TranStudy: https://github.com/DAGfans/TranStudy/edit/master/Papers/PHANTOM/2-THE%20PHANTOM%20PROTOCOLmd



In this section we describe the operation of the PHANTOM protocol. PHANTOM consists of the following three-step procedure:

在本节中,我们将介绍PHANTOM协议的操作。 PHANTOM包含以下三个步骤:

1) Using the structure of the DAG, we recognize in it a cluster of well-connected blocks; with high probability, blocks that were mined honestly belong to this cluster and vice versa. 2) We extend the DAG’s natural partial ordering to a full topological ordering in a way that favours blocks inside the selected cluster and penalizes those outside it. 3) The order over blocks induces an order over transactions;

transactions in the same block are ordered according to the order of their appearance in it. We iterate over all transactions in this order, and accept each one that is consistent (according to the underlying Consistency notion) with those approved so far. The Consistency notion used in the last step depends on the specific application under consideration. For instance, with regards to the Payments application, a transaction is consistent with the history only if all of its inputs have been approved and no double spending transaction has been approved before. Our work is agnostic to the definition of the Consistency rule. The contribution of PHANTOM is its implementation of the first two steps described above, which we now turn to describe.

1) 使用DAG的结构,我们在其中识别出连接良好的区块集群; 很有可能,被诚实挖出的块属于这个集群,反之亦然。 2) 我们用某种方式将DAG天然的偏序扩展为全序,该方式奖励集群内的块,并对集群外的块进行惩罚。 3) 块的顺序也会引发交易的顺序(译注:应该是指,如果块A的顺序大于块B,则块A内的所有交易的顺序都大于块B内的交易);

同一块的交易根据它们在内部出现的顺序排序. 我们按照此顺序遍历所有交易,并接受每一笔与迄今已确认的交易一致(根据基本的一致性概念)的交易。 最后一步中使用的一致性概念取决于所考虑的具体应用。 例如,关于“支付”应用程序,只有在所有输入都被确认并且之前没有确认过双花交易的情况下,交易才符合历史记录。 我们的工作对一致性规则的定义是不可知的。 PHANTOM的贡献在于实现了上述的前两个步骤,现在我们来描述它们。

A. Intuition

A. 思路

How can we distinguish between honest blocks (i.e., blocks mined by cooperating nodes) and dishonest ones?

Recall that the DAG mining protocol instructs a miner to acknowledge in its new block the entire DAG it observes locally, by referencing the “tips” of the DAG.

Thus, if block B was mined at time t by an honest miner, then any block published before time $t-D$ was received by the miner and is therefore in B’s past set (i.e., referenced by B directly or recursively via its predecessors; see illustration in Figure 1).

Similarly, if B’s miner is honest then it published B immediately, and so any honest block created after time $t+D$ belongs to B’s future set.



因此,如果块B在时间t由一个诚实的矿工挖出,那么在时间$t-D$之前发布的任何块都会被该矿工接收,因此会在B的过去集中(即,由B直接引用或通过其祖先递归地引用;参见 图1中的图解)。


As a result, the set of honest blocks in B’s anticone – which we denote $anticone_h(B)$– is typically small, and consists only of blocks created in the interval $\left [t-D,t+D \right ]$ .^2

In other words, the probability that an honest block B will suffer a large honest anticone is small:

$Pr(|anticone_h(B)|>k)\in O(e^{-C\cdot k})$ , for some constant $C > 0$ (this stems from a bound on the Poisson distribution’s tail).

We rely on this property and set PHANTOM’s parameter k such that the latter probability is smaller than δ , for some predefined $\delta > 0$;

see discussion in Section 4.

因此,B的反锥体中的诚实块集- 我们表示为$anticone_h(B)$ - 通常很小,并且只包含在时段$\left [t-D,t+D \right ]$中创建的块。^2


对于某个常数$C> 0$, $Pr(|anticone_h(B)|>k)\in O(e^{-C\cdot k})$(这源于泊松分布尾部的边界)。



Following this intuition, the set of honest blocks (save perhaps a fraction δ thereof) is guaranteed to form a k-cluster.


(^2) Note that, in contrast to anticone h(B), an attacker can easily increase the size of anticone(B), for any block B, by creating many blocks that do not reference B and that are kept secret so that B cannot reference them.

(^2) 注意,与 anticone h(B)相比,对于任何块B,攻击者可以通过创建许多不引用B并且保密的块来很容易地增加 anticone(B)的大小以至于B不能引用它们。

Definition 1. Given a DAG $G=(C,E)$ , a subset $S\subseteq C$ is called a k-cluster, if $\forall B\in S: |anticone(B)\cap S|\leq k$.

定义1 给定一个DAG $G =(C,E)$, 如果 $\forall B \in S: |anticone(B)\cap S|\leq k$, 则子集$S\subseteq C$被称为k-集群。

Note that the attacker can easily create k-clusters as well, e.g., by structuring his blocks in a single chain.

Fortunately, we can leverage the fact that the group of honest miners possesses a majority of the computational power, and look at the largest k-cluster.

We argue that the latter represents, in most likelihood, blocks that were mined properly by cooperating nodes.

Refer to Figure 2 for an illustration of the largest 3 -cluster in a given blockDAG.

Identifying this set in general DAGs turns out to be computationally infeasible, and so in practice our protocol uses a greedy algorithm which is good enough for our purposes.

We term this selection of a k-cluster a colouring of the DAG, and use the colours blue and red as a convention for blocks inside and outside the chosen cluster, respectively.







B. Step #1: recognizing honest blocks

B. 步骤 #1:识别诚实的块

Algorithm 1 below selects a k-cluster in a greedy fashion.

We denote by $BLUE_k(G)$ the set of blocks that it returns.

The algorithm operates as follows:




1) Given a DAG G, the algorithm recursively computes on the past set of each tip in G.^3 This outputs a k-cluster for each tip.^4 (lines 4-5)

2) Then, it makes a greedy choice and picks the largest one among the outputted clusters. (lines 6-7)

3) Finally, it tries to extend this set and add to it any block whose anticone is small enough with respect to the set. (lines 8-10)

1) 给定一个DAG G,该算法递归计算G 中每个末端的过去集合^3 这将为每个末端输出一个k-集群。^4(第4-5行)

2) 然后,它进行一个贪婪的选择,并从输出的集群中选出最大的一个。 (第6-7行)

3) 最后,它试图扩展这个集合,并添加任何相对于该集合来说其反锥体足够小的块。 (第8-10行)

(^3) A tip is a leaf-block, that is, a block not referenced by other blocks. See Figure 1.

(^4) Observe that, for any block B, the DAG $past(B)$ is fixed once and for all at B’s creation, and in particular the set $BLUE_k(past(B))$ cannot be later modified.

Thus, in an actual implementation of Algorithm 1, the sets $BLUE_k(B)$ will have been computed already (by previous calls) and stored, and there will be no need to recompute them.

(^3) 末端是一个叶块,也就是一个没有被其他块引用的块。 参见图1

(^4) 可见,对于任何块B,DAG的$past(B)$在B的创建时被永久地固定了,特别是集合$BLUE_k(past(B))$不能被过后修改。


Intuitively, we first let the DAG inherit the colouring of its highest scoring tip, $B_{max}$, where the score of a block is defined as the number of blue blocks in its past: $score(B) :=|BLUE_k(past(B))|$.

Then, we proceed to colour blocks in $anticone(B_{max})$ in a way that preserves the k-cluster property.

This inheritance implies that the greedy algorithm operates as a chain-selection rule—$B_{max}$ is the chain tip, the highest scoring tip in $past(B_{max})$ is its predecessor in the chain, and so on.

We denote this chain by $Chn(G) = (genesis = Chn_0(G),Chn_1(G),…,Chn_h(G))$.

The reasoning behind this procedure is very similar to that given in Section 1 in relation to the Maximum k-cluster SubDAG problem.

They only differ in that, instead of searching for the maximal k-cluster, we are hoping to maximize it via the tip with maximal cluster and then adding blocks from its anticone.

Thus, the reader should think of our algorithm (informally) as approximating the optimal solution to the Maximum k-cluster SubDAG problem.

直觉上,我们首先让DAG继承其得分最高的末端($B_{max}$)的着色, 其中一个块的得分被定义为过去的蓝色块的数量:$score(B) :=|BLUE_k(past(B))|$。



我们用$Chn(G) = (genesis = Chn_0(G),Chn_1(G),…,Chn_h(G))$表示这条链。





Fig. 3: An example of a blockDAG G and the operation of the greedy algorithm to construct its blue set $BLUE_k(B)$ set, under the parameter k= 3.

The small circle near each block X represents its score, namely, the number of blue blocks in the DAG $past(X)$.

The algorithm selects the chain greedily, starting from the highest scoring tip M, then selecting its predecessor K(the highest scoring tip in $past(M))$,

then H,D(breaking the C,D,E tie arbitrarily), and finally Genesis.

For methodological reasons, we add to this chain a hypothetical “virtual” block V – a block whose past equals the entire current DAG.

Blocks in the chain(genesis,D,H,K,M,V) are marked with a light-blue shade.

Using this chain, we construct the DAG’s set of blue blocks,$BLUE_k(G)$.

The set is constructed recursively, starting with an empty one, as follows: In step 1 we visit D and add genesis to the blue set (it is the only block in $past(D))$.

Next, in step 2, we visit H and add to $BLUE_k(G)$ blocks that are blue in $past(H)$, namely, C,D,E.

In step 3 we visit K and add H,I;

note that block B is in $past(K)$ but was not added to the blue set, since it has 4 blue blocks in its anticone.

In step 4 we visit M and add K to the blue set;

again, note that $F\in past(M)$ could not be added to the blue set due its large blue anticone.

Finally, in step 5, we visit the block $virtual(G) =V$, and add M and L to $BLUE_k(G)$, leaving J away due its large blue anticone.

图3: blockDAG G的一个例子,展示贪婪算法在参数k = 3下构造其蓝色集$BLUE_k(G)$的操作。






使用这个链,我们构建了DAG的蓝色块集合, $BLUE_k(G)$。






再一次请注意,$F\in past(M)$由于其大蓝色反锥体而无法添加到蓝色集合中。

最后,在步骤5中,我们访问$virtual(G) =V$,并将M和L添加到$BLUE_k(G)$中,J由于其大的蓝色反锥体而被抛弃。

We demonstrate the operation of this algorithm in Figure 3.

Another example appears in Figure 4.

Note that the recursion halts because for any block $B\in G:|past(B)|<|G|$.

Let us specify the order in which blocks in $anticone(B_{max})$ should be visited, in line 8 of the algorithm.

We suggest inserting all blocks in $anticone(B_{max})$ into a lexicographical topological priority queue, which we denote $topo_queue$.

The priority of a block is represented by the size of its past set;^5

in case of ties, the block with lowest hash ID is chosen.



请注意,递归会因为任何块$B\in G:|past(B)|<|G|$而停止。



块的优先级由其过去集的大小表示; ^5


(^5) This guarantees that a block cannot be popped out while a block in its past is still in the queue, since $C\in future(B) \Rightarrow |past(C)|>|past(B)|$.

(^5) 由于$C\in future(B) \Rightarrow |past(C)|>|past(B)|$,所以这确保了块在其过去的块仍然在队列中时不能弹出。

Remark. Our choice of ordering via $topo_queue$ is not inherently significant, and many alternative topological orderings can provide similar robustness properties.

That said, it might be the case that other rules provide faster convergence and confirmation times.

We revisit this issue in Section 7.

备注. 我们选择通过$topo_queue$进行排序的本质上并不重要,许多替代拓扑排序可以提供类似的鲁棒性性。



To summarize the function that the blue set satisfies, we state the following:


Proposition 2. Let $G=G_{pub}^\infty$ be the eventual DAG containing all blocks in history, and let B be an arbitrary block in G.

命题2. 假定 $G=G_{pub}^\infty$ 是包含历史中所有块的最终DAG,B为G中的任意块。

  • If B was created by an honest miner, the probability that B will not belong to $BLUE_k(G)$ decreases exponentially with k.
  • If B was created by a malicious miner, and was withheld for a time interval of length T, the probability that B will belong to $BLUE_k(G)$ decreases exponentially with T.
  • 如果B由诚实的矿工创建,则B不会属于$BLUE_k(G)$的概率随k的增大而指数式减小。
  • 如果B由恶意矿工创建,并且在长度为T的时间间隔内被扣留,那么B会属于$BLUE_k(G)$的概率将随着T的增大而指数式减小。

The proof of this proposition follows from the proof of Claim 3 in Section 5.


C. Step #2: ordering blocks
C. 步骤 #2: 区块排序

Recall that the DAG is ordered partially via its topology.

We now wish to extend this order to a full order (aka a topological order).

Our objective is to define a rule that gives precedence to blocks in the blue set, that penalizes blocks outside this set by deferring their location in the order, and that preserves the topological relations of blocks.




We propose the following procedure: Traverse the blue set according to some topological order, and iteratively add blocks to the current last position in $ord^k$;

when visiting block B, first check if there are blocks in past(B) that haven’t been added yet, add such blocks to the order (again, according to some topological order), and then add B to the order.



For example, a possible output of $ord^3$ on the blockDAG illustrated in Figure 2 is: (A,D,C,G,B,F,I,E,J,H,K).

例如,图2中所示的blockDAG上的 $ord^3$的可能输出是:(A,D,C,G,B,F,I,E,J,H,K)。

This procedure is formalized in Algorithm 2 below.

The algorithm begins by initializing an empty priority queue and an empty ordered list.

Throughout, the list will represent the order in which blocks were popped out from the queue.

The algorithm favours blocks in the blue set by adding to the queue all of the blue children of the current block.

When a block is pushed into the queue, all blocks in its past (that weren’t already treated) are pushed as well.






In the algorithm,topo_queue is the same lexicographical topological priority queue defined in the preceding subsection.

In addition, the queue should avoid duplicating elements, and so $topo_queue.push(C)$ should do nothing in case C is already in $topo_queue$.



The intuition here is simple.

The algorithm is intended to guarantee that a block B can precede a blue block C only if B is blue, or B is referenced by a blue block.

In this way, blocks that were withheld by an attacker will not precede blocks that were mined properly and published on time (which are represented roughly by the set of blue blocks).




Algorithm 1 Selection of a blue set

Input: G – a block DAG, k – the propagation parameter

Output: $BLUE_k(G)$ – the dense-set of G

  1. function CALC-B L UE(G, k )

  2. if $B == genesis$ then

  3. return {$genesis$}

  4. for $B \in tips(G)$ do

  5. $BLUE_k(B) \leftarrow CALC-BLUE(past (B) , k)$

  6. $B_{max} \leftarrow \arg max {|BLUE_k(B)|:B\in tips(G)}$ (and break ties arbitrarily)

  7. $BLUE_k(G) \leftarrow BLUE_k(B_{max}) \cup {B_{max} }$

  8. for $B \in anticone (B_{max} )$ do in some topological ordering

  9. if $|anticone (B) \cap BLUE_k(G)| \leq k$ then

  10. add B to $BLUE_k(G)$

  11. return $BLUE_k(G)$

译者注:arg max即“argument of the maximum“的缩写,直译就是”最大值的自变量“,意思是使arg max后面所跟的公式达到最大值的自变量的取值。在上面算法中就是指拥有最多蓝色祖先区块的G的末端区块。

Algorithm 2 Ordering of the DAG

Input: G – a block DAG, k – the propagation parameter

Output: $ord(G)$ – an ordered list containing all of G’s blocks

  1. function ORDER(G, k )

  2. initialize empty queue topo_queue

  3. initialize empty ordered list L

  4. $BLUE_kG) \leftarrow CALC-BLUE(G, k)$

  5. $topo_queue.push (genesis)$

  6. while $topo_queue \neq \phi$ do

  7. $B \leftarrow topo_queue.pop()$

  8. $L.add(B)$ (B is added to the end of the list)

  9. for all $C \in childrenB \cap BLUE_k(G)$ do

  10. for all $D \in past (C) \cap anticone (b) \setminus L$ do

  11. $topo_queue.push(D)$

  12. $topo_queue.push(C)$

  13. $ord(G) \leftarrow L$

  14. return $ord(G)$

D. Implications to transaction security
D. 对交易安全的影响

We now demonstrate how the above procedures of PHANTOM enable safe acceptance of transactions.

Consider a transaction $tx\in B$, where B is a block in the blue set of G.

In order to render tx invalid, a conflicting transaction $\bar{tx}$ must precede it in the order, and must therefore be embedded in a block $C\in anticone(B)$ that precedes B.^6

The ordering procedure implies that, for C to precedes B, it must either be a blue block or in the past set of a blue block.

In both cases,C could not have been withheld for too long, by the second guarantee of Proposition 2.

Thus, the recipient of tx can wait for the blue set around B to become sufficiently robust to reorgs, and then approve tx.

In Section 5 we prove that robustness is indeed obtained, after some waiting time.


考虑一个交易$tx\in B$,其中B是G的蓝色集合中的一个块。

为了使tx无效,冲突交易$\bar{tx}$ 必须在它的顺序之前,因此必须嵌入在B之前的块$C\in anticone(B)$





Related Posts