Scroll

Categories

Tags

Monthly Archives

Keyword

Back

2018.04.05

# 2. PHANTOM 协议

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

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内的交易);

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

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 predeﬁned $\delta > 0$;

see discussion in Section 4.

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

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. 步骤 #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.

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.

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.

(^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.

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.

• 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. 步骤 #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).

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)$

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. 对交易安全的影响

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.

Top