Scroll

Categories

Tags

Monthly Archives

Keyword

Back

2018.07.09

# 5. 证明

We now turn to prove that the order converges, and that an attacker (with less than 50%) is unable to cause reorgs. We restate the theorem from Section 3:

Theorem 5(PHANTOM scales). Given a block creation rate $\lambda > 0, \delta > 0$ , and $D_{max} > 0$ , if $D_{max}$ is equal to or greater than the network’s propagation delay diameter $D$ , then the security threshold of PHANTOM, parameterized with $k(D_{max} , \delta)$ , is at least $1/2 \cdot (1-\delta )$ .

Our proof relies on the following lemma, which states that if some block B has the property that its anticone contains no blue blocks, then all blue blocks in its past precede all blocks outside its past. We call this the Hourglass property:

Lemma 7. If for some $\hat{B} \in G$ , $BLUE_k(G) \cap anticone(\hat{B}) = \emptyset$ , then $\forall B \in past(\hat{B}) \cap BLUE_k(G)$ and $\forall C \notin past(\hat{B})$ , $B \prec_G C$ . We then write $\hat{B} \in Hourglass(G)$ .

Fig. 4: An example of a DAG with an Hourglass block $K$ . Here, the delay parameter is $k = 3$ . As in Figure 3, the small circle near each block represents its score. The colouring of the DAG was done according to Algorithm 1. The greedily selected chain of blocks of highest score is marked with light-blue filling (note that this chain is not the longest one). Block $K$ has the property that all blue blocks are either in $K$ ’s past or in its future (in addition to $K$ itself). It is thus an Hourglass block.

In Figure 4 we provide an example of an Hourglass block. The proof of this lemma is straightforward from the operation of Algorithm 2:

Proof of Lemma 7. First note that if $BLUE_k(G) \cap anticone(\hat{B}) = \emptyset$ , then $\hat{B} \in BLUE_k(G)$ . Indeed, Algorithm 1 defines a chain, $Chn(G)$ (see Subsection 2.2). This chain necessarily intersects some block in anticone $anticone(\hat{B}) \cup \{\hat{B}\}$ . And the intersection block must become blue itself, by lines (6-7). Thus, $BLUE_k(G) \cap anticone(\hat{B}) = \emptyset$ implies that $\hat{B} \in Chn(G)$ and in particular $\hat{B} \in BLUE_k(G)$ .

Now, Algorithm 2 pushes a block into the queue only after it has pushed already all blocks in its past (lines 11 and 12). Therefore, $topo\_queue$ pops out blocks according to a topological order. Now, there are no blue blocks in $anticone(\hat{B})$ , hence if $C$ is a blue block then it must belong to $future(\hat{B}) \cup \{\hat{B}\}$ , in which case it must have been pushed to the queue after $\hat{B}$ was popped (unless $C = \hat{B}$ ). Thus, if $C$ is blue, any block in $past(\hat{B})$ was popped out before $C$ , and added to the ordered list $L$ before it (line 8). In particular, $B \prec_G C$ . On the other hand, if $C$ is not blue, it was necessarily pushed into the queue only by belonging to the past set of some blue block $B'$ (lines 9-11). $B'$ was popped out after $\hat{B}$ (unless $B' = \hat{B}$ ), from the same argument as in the previous case. Thus, $C$ was pushed into the queue after $\hat{B}$ was popped out, which in turn must have occurred after $B$ was popped out. In particular, in this case as well, $B \prec_G C$ . $\hspace{5mm}\square$

Lemma 8. If $\hat{B}$ is an Hourglass block in a DAG $G$ , then $G$ inherits the order from $\hat{B}$ : $ord(G) \cap past(\hat{B}) = ord(past(\hat{B}))$ .

Proof. In the proof of the previous lemma we have shown that $\hat{B} \in Chn(G)$ . By the recursive operation of Algorithm 1 (lines 6-7), this implies that $G$ inherits the colouring of $\hat{B}$ on its past: $BLUE_k(G) \cap past(\hat{B}) = BLUE_k(past(\hat{B}))$ .

Now, no block in $anticone(\hat{B})$ is pushed into $topo\_queue$ before $\hat{B}$ is popped out, because blocks get pushed in only if they are blue (and no such block exists in $anticone(\hat{B})$ ) or if a blue block in their future was pushed in-—and this too only happens after $\hat{B}$ is popped out. Since the queue respects the topology, this means that all blocks in $past(\hat{B})$ (which must be visited before $\hat{B}$ ) are popped out before any block outside $past(\hat{B})$ .

The fact that blocks in $anticone(\hat{B})$ are not pushed into the queue before all of $past(\hat{B})$ is popped out, implies further that the order in which Algorithm 2 pushes blocks in $past(\hat{B})$ into and out of $topo\_queue$ depends only on $past(\hat{B})$ , and not on the DAG $G$ . Hence, $ord(G) \cap past(\hat{B}) = ord(past(\hat{B})$ . $\hspace{5mm}\square$

$past(\hat{B})$ 的所有区块被弹出之前， $anticone(\hat{B})$ 中的区块不会被压入队列。这进一步意味着算法2将 $past(\hat{B})$ 里的区块压入和弹出 $topo\_queue$ 的顺序仅取决于 $past(\hat{B})$ ，而不取决于 DAG $G$ 。因此， $ord(G) \cap past(\hat{B}) = ord(past(\hat{B})$$\hspace{5mm}\square$

The proof of Theorem 5 uses the occurrence of Hourglass blocks to secure all blocks in their past set.

Proof of Therom 5. Let $\delta > 0$ and assume that $% $ . We need to prove that $\forall t_0 > 0$ and $B \in G_{t_0}^{pub}$ : $\lim\limits_{t_1 \to \infty} Risk(B, t_1) = 0$ , where $Risk(B, t_1) := \Pr(\exists s > t_1, \exists C \in G_s^{pub}: B \prec_{G_{t_1}^{pub}} C \wedge C \prec_{G_s^{pub}} B)$ , and assuming a fraction of at most $1/2 - \delta$ can deviate arbitrarily from the mining pool.

Fix $t_0$ and $B$ , and let $\tau(t_0)$ be the first time after $t_0$ where an honest block $\hat{B}$ was published such that $\hat{B}$ is an Hourglass block and will forever remain so:

$t_0$$B$ 固定，并且假设 $t_0$ 之后符合下面条件的一个诚实区块 $\hat{B}$ 被发布——该区块是 $t_0$ 之后首个被发布的诚实的沙漏区块，并且之后也将一直保持为沙漏区块。我们将该区块的发布时间记为 $\tau(t_0)$

$\tau(t_0)$ is a random variable. By Lemma 9 it has finite expectation. In particular, $\lim\limits_{t_1 \to \infty} \Pr(\tau(t_0) > t_1) = 0$ (e.g., by Markov’s Inequality).

$\tau(t_0)$ 是一个随机变量。 根据引理9，它的期望值是有限的。 特别是， $\lim\limits_{t_1 \to \infty} \Pr(\tau(t_0) > t_1) = 0$ （比如，根据马尔可夫不等式）。

Assume that such a $\tau(t_0)$ arrives, i.e., that a block $\hat{B}$ is created and remains permanently an Hourglass block. Then, by Lemma 8, the order between all blocks in $past(\hat{B})$ never changes, and in particular the order between $B$ and any other block $C$ never changes. Thus, $Risk(B, \tau(t_0)) = 0$ . Therefore, $\lim\limits_{t_1 \to \infty} \Pr(\tau(t_0) > t_1) = 0$ implies $\lim\limits_{t_1 \to \infty} Risk(B, t_1) = 0$ . $\hspace{5mm}\square$

Lemma 9. Let $t_0 \geq 0$ . The expected waiting time for $\tau(t_0)$ (defined in (2)) is finite, and moreover is upper bounded by a constant that does not depend on $t_0$ .

Proof. Let $\varepsilon(t_0)$ denote the event defined by the following conditions:

1. Some block $\hat{B}$ was created at some time $u > t_0$ by an honest node (i.e., $\hat{B} \in G_u^{pub}$ ) and apart from $\hat{B}$ no other block was created in the time interval $[u - D, u + D]$ . 1
2. For some $T_1$ , the $k$ last blocks in $BLUE_k(past(\hat{B}))$ , denoted $LAST_k(past(\hat{B}))$ , was created in the time interval $[u - T_1, u]$ , and dishonest miners created no blocks in this time interval.
3. The score of $\hat{B}$ ‘s chain is forever higher than the score of any chain that does not pass through $\hat{B}$ : $\forall s \geq u, \forall C_1, C_2 \in tips(G_s^{pub}): score(C_1) \geq score(C_2) \Longrightarrow \hat{B} \in Chn(past(C_1))$ .
1. 某个区块 $\hat{B}$ 在某个时刻 $u > t_0$ 被一个诚实节点所创建（即 $\hat{B} \in G_u^{pub}$ ）并且除了 $\hat{B}$ 以外在时间区间 $[u - D, u + D]$ 以内没有其它区块被创建。 1
2. 对某个时间长度 $T_1$ 来说， $BLUE_k(past(\hat{B}))$ 的最后 $k$ 个区块，记为 $LAST_k(past(\hat{B}))$ ，是在时间区间 $[u - T_1], u]$ 内被创建的，并且在此时间区间内作弊矿工没有创建区块。
3. $\hat{B}$ 的链的得分永远比任意一条不穿过 $\hat{B}$ 的链的得分高： $\forall s \geq u, \forall C_1, C_2 \in tips(G_s^{pub}): score(C_1) \geq score(C_2) \Longrightarrow \hat{B} \in Chn(past(C_1))$ 。（译注：感觉这里的数学符号表达并不严谨，因为有可能 $Chn(past(C_1))$$Chn(past(C_2))$ 都不包含 $\hat{B}$ 。但我并不确定。可能需要详细理解下文断言3的证明。）

Claim 2 and 4 together imply the required result.

The following claim states that the first two conditions in the above definition guarantee that as long as $\hat{B}$ is blue no block in its anticone is blue:

Claim 1. Assume that for some block $\hat{B}$ the first two conditions in the definition of $\varepsilon(t_0)$ hold true. Then, as long as $\hat{B}$ is blue, all blue blocks have $\hat{B}$ in their past: $\forall s \geq u, \forall B \in anticone(\hat{B}) : B \notin BLUE_k(G_s^{pub}) \lor \hat{B} \notin BLUE_k(G_s^{pub})$ .

（译注：断言1换句话说，也就是All blocks created by the attacker before $u-T_1$ are either in $past(\hat{B})$ or in the anticone of all k+1 blocks in Last (including $\hat{B}$) itself）

Proof of Claim 1. Let $B \in anticone(\hat{B})$ . If $\hat{B} \notin BLUE_k(G_s^{pub})$ we’re done. Assume therefore that $\hat{B} \in BLUE_k(G_s^{pub})$ . Any block that was published before time $u - D$ belongs to $past(\hat{B})$ . Any block that was created after $u + D$ by an honest node belongs to $future(\hat{B})$ . As honest nodes did not create blocks in the interim, blocks in $anticone(\hat{B})$ can only belong to the attacker. Now, since the attacker did not create new blocks while blocks in $LAST_k(past(\hat{B}))$ were created, all attacker blocks that were created before the interval $[u - T_1, u]$ and that do not belong to $past(\hat{B})$ (hence belong to $anticone(\hat{B})$ ) have all blocks in $LAST_k(past(\hat{B}))$ in their anticone; formally: $\forall C \in anticone(\hat{B}, G_u^{oracle}) : LAST_k(past(\hat{B})) \subseteq anticone(C, G_u^{oracle})$ . Thus, if $\hat{B} \in BLUE_k(G_s^{pub})$ , any block in $anticone(\hat{B})$ suffers an anticone that is larger than $k$ (it contains $LAST_k(past(\hat{B})) \cup {\hat{B}}$ ) and is therefore not in $BLUE_k(G_s^{pub})$ . In particular, $B \notin BLUE_k(G_s^{pub})$ .

Claim 2. The waiting time for the event $\varepsilon (t_0)$ upper bounds $\tau(t_0)$ .

Proof of Claim 2. The previous claim implies that a block $\widehat{B}$ that satisfies the first two conditions is an Hourglass block in $G_s^{pub}$ . The third condition implies that $\widehat{B}$ forever remains in the chain, and in particular forever remains blue. It is thus an Hourglass block in all DAGs $G_s^{pub}(s \geq u)$ .

Claim 3. If the first two conditions in the definition of $\varepsilon (t_0)$ hold true then the third one holds true with a positive probability.

Proof of Claim 3. Part I: We begin by assuming that the attacker did not publish any block in the time interval $[0,u-D_{max})$ ; formally, we assume that $\forall C \in past(\widehat{B}):C\in honest$ .

Let us compare the score of the honest chain to that of any chain that excludes $\widehat B$ . This gap is captured by the following definition: For a time $r > 0$ , define

Let us focus first on the evolution of the process $X_r$ between time 0 and time $u-T_1$. We refer to the lead $X_{u-T_1}$ ，that the attacker obtained at the end of this stage as “the premining gap”; see [8].

Let $B^{r}_1$ be the argmax of $X^{1}_r$ , and let $C^{r}_1$ be the latest block in $G^{pub}_r \cap BLUE_k(past(B^{r}_1))$ , namely, the latest honest block which is blue in the attacker chain.

$B^{r}_1$ 作为 $X^{1}_r$ 取最大值时的参数 ，让 $C^{r}_1$ 成为 $G^{pub}_r \cap BLUE_k(past(B^{r}_1))$ 中最新的块，即，在攻击者链上的蓝色的最新的诚实块。

Recall that for now we are assuming that all attacker blocks that were premined were kept secret until after time $u-D_{max}$ . Observe that at most k blocks that were created by the attacker before $time(C^{r}_1)$ can be in $BLUE_k(past(B^{r}_1))$ and can contribute to the score of the attacker’s chain.

Thus, between $time(C^{r}_1)$ and time $u-T_1$ , - i.e. during the premining phase – the score of the attacker chain grows only via the contribution of attacker blocks, and therefore at a rate of $\alpha \cdot \beta$ at most.2

We only claim that the attacker’s highest scoring chain grows at a rate of $\alpha \cdot \beta$ at most, because every attacker block can increase the attacker’s highest scoring chain by 1 at most. Creating a single chain is indeed the optimal attack on the attacker side.

Now, by the choice of $K(D_{max},\delta )$ (defined in 1), the probability of an arbitrary honest block $B$ having too large of an honest anticone is small: 3

This is because block creation follows a Poisson process, and because honest blocks that were created $D_{max}$ seconds before (after) $B$ belong to its past (future), hence are not in its anticone. Since any block that is blue in the honest chain contributes to its score, at any time interval, the score of the public chain grows at a rate of $(1-\delta)\cdot (1-\alpha )\cdot \lambda$ at least. And at most k honest blocks created in the premining stage contributed to the score of the attack chain.

Part III: From Part I and Part II we conclude that the random process $X_r-k$ is upper bounded by the premining race analyzed in [8]. Therein it was shown that the probability distribution over $X_{u - T_1} - k$ (the process’s state at the end of the premining stage) is dominated by the stationary probability distribution $\pi$ of a reflecting random walk over the non-negative integers with a bias of $\frac{(1-\delta)\cdot (1-\alpha)}{1-\delta\cdot (1-\alpha )}$ towards negative infinity. The stationary distribution exists because $% $ .4

In particular, there is a positive probability that at time $u - T_1$ the premining gap, $X_{u-T_1}$ , was less than k, so that $% $ .5 Between times $u - T_1$ and $u$ the honest network contributed additional $k + 1$ to the score of the public chain, namely, blocks $LAST_k(past(\widehat{B}))\cup \{\widehat{B}\}$ . During the same time the score of any secret chain(s) did not increase at all, per the second condition in the definition of $\varepsilon (t_0)$ . Thus, $X_u=X_{u-T_1}-(k+1)$ . And by the first assumption, $X_u + D_{max} = X_u$ . All in all, with some positive probability, $% $ .

Part IV: Let us turn to look at the evolution of $(X_r)_{r \leq u+D_{max}}$ at the second stage.

Assume that $% $ .

In Claim 1 we saw that for any $r$ such that $\widehat{B} \in BLUE_k(G_r^{pub})$ , all blocks in $\widehat{B}$ ’s anticone are red in $G^{pub}_r$ . This implies that, as long as $\widehat{B}$ is blue in the public DAG, only attacker blocks contribute to the score of the attacker’s chain: $\widehat{B} \in BLUE_k(G^{pub}_r) \Rightarrow \forall B \in anticone(\widehat{B}): BLUE_k(past(B))\setminus future(\widehat{B}) = \emptyset$ (indeed, note that all honest blocks created after time $u + D_{max}$ belong to $future(\widehat{B})$ ). Consequently, the attacker’s best chain grows at a rate of $\alpha \cdot \beta$ at most, as this interval ( $[u+D_{max},\infty )$ ) as well, as long as $\widehat{B} \in BLUE_k(G^{pub}_r)$. We have already seen that at any time interval the honest chain’s score grows at a rate of $(1-\delta )·(1-\alpha )\cdot \lambda$ at least. Thus, starting at time $u+D_{max}$ , the race between the honest chain’s score and the attacker chain’s score can be modeled as a random walk over all integers with a bias of $\frac{(1-\delta )(1-\alpha )}{1-\delta\cdot (1-\alpha )}$ towards negative infinity.

Since the random walk begins at the negative location $X_{u+D_{max}}$ , this supposedly implies that with a positive probability the walk will never return to the origin: $% 0 %]]>$ . This in turn implies that $\widehat{B}$ will forever remain a blue block (and a chain block for that matter). However, to complete the analysis correctly, some careful attention is required:

Note on the other hand that blocks created by honest nodes too do not contribute to the attacker chain’s score, even if they are red in $G_{pub}^r$ . This is because we argued that at most $k$ blocks that were created by the attacker before time ( $C^r_1$ ) can be blue in $BLUE_k (past(B^r_1))$ , and this is regardless of $C^r_1$ ’s status within $G_{pub}^r$ (we merely used the fact that $C^r_1$ was created by an honest node, we didn’t use the assumption that $C^r_1$ is blue in the honest chain).

Part V: First, we must account for the fact that not all honest nodes observe all honest blocks immediately, i.e., that $G^v_r$ might be a proper subset of $G^{pub}_r$ . This might give the attacker an advantage, as he can create blocks, reveal them immediately to honest nodes, and these blocks do not compete with honest blocks unseen yet by these nodes. This advantage can be accounted for by assuming that the race begins only after the attacker was given $D_{max}$ additional seconds to create blocks while the honest network sat idle; see [8]. This fact does not change our general conclusion that $% 0 %]]>$ , e.g., because there is a positive probability that the attacker did not create any block during these $D_{max}$ additional seconds.

Secondly, observe that the honest chain grows according to a random process that is not necessarily Poisson. Fortunately, a result from [9] shows that nevertheless we can treat the block race as if the honest score grows according to a Poisson process, and that this assumption can only increase the value of $X_r$ ; it is thus a worst case analysis.

Part VI: Finally, we alleviate our assumption that the attacker published no block during the premining phase $[0,u−D_{max})$ . Instead, consider any attacker block $C$ that belongs to $past(\widehat{B})$ . If $C\in BLUE_k(past(BB))$ then $C$ contributed to the score of the honest chain which passes through $\widehat{B}$ and maybe to the attacker chain as well, so its existence does not change the above analysis. Similarly, if $C\notin BLUE_k(past(BB))$ , the fact that it was published has no consequence whatsoever on the score of the honest chain, and so we can ignore it and apply the same analysis as if it weren’t published.

Claim 4. The waiting time for the event $\varepsilon (t_0)$ is finite. Moreover, it is upper bounded by a constant that does not depend on $t_0$.

Proof of Claim 4. Let $B$ be an arbitrary honest block created in $time(B)$ . The probability that no other block was created in the interval $[time (B)-D_{max}, time (B)+D_{max}]$ is given by $e^{-2\cdot D_{max}\cdot \lambda }$ . An arbitrary block $B$ satisfies the first condition in the definition of $\varepsilon (t_0)$ with a positive probability.

Given an arbitrary block $B$ satisfying the above condition, let $T_1$ be the creation time of the earliest block in $LAST_k(past (B))$ . The probability that the attacker did not create any block in the interval $[u-T_1, u-D_{max}]$ is given by $((1-\alpha )\cdot (1-\delta ))^k$ . In particular, given the first condition, the second one is satisfied with a positive probability.

Importantly, for any two blocks $B_1$ and $B_2$ created after $t_0$ and that satisfy $|time(B_1)-time(B_2)| > 4\cdot D_{max}$ , the satisfaction of the first condition with respect to $B_1$ is independent from its satisfaction with respect to $B_2$ . Consequently, the expected waiting time for the occurrence of a block $\widehat{B}$ which satisfies the first two conditions in the definition of $\varepsilon (t_0)$ is finite (see, for instance, Chapter 10.11 in [10]). Moreover, while the precise expected time $\mathbb{E}[Hourglass(t_0)]$ may theoretically depend on $t_0$, the above argument shows that $% $ , where const does not depend on $t_0$ . This completes the proof of Claim 4 and of Lemma 9.

Theorem 5 guarantees that the probability of reorg with respect to a given block $B$ diminishes: $Risk(B, t_1)\rightarrow 0$ . However, it does not guarantee anything about the convergence rate, i.e., the waiting time for a $t_1$ that satisfies $% $ , for some $\varepsilon > 0$ .[^18] Following the analysis in the proof of Claim 4, the waiting time for an Hourglass block can be upper bounded by a constant in the order of magnitude of $O(e^{C\cdot D_{max}\cdot \lambda })$ , for some $C > 0$ ; and after such a block is created, the analysis implies that $Risk(B,t_1)$ converges to 0 at an exponential rate, due to the random walk dynamic.

However, the analysis used in the proof is not tight. It relies on rather infrequent events which guarantee convergence in a straightforward way, namely, on the occurrence of Hourglass blocks. In practice the network is likely to converge much faster. Moreover, it can be shown that when there is no active attack, the convergence time is faster by orders-of-magnitude.

1. 然而，我们不能假设在此区间内没有区块被发布，因为攻击者可能会决定在此区间内发布他早前创建的区块。  2

2. 注意我们的分析没有假设攻击者在单链上创建它的块。

3. 以下， $\overline{anticone_h}(B, G)$ 表示所有在 $anticone(B, G)$ 中的块由诚实结点创建的区块。  2

4. 注意我们已经把 $(1-\alpha)$$(1-\delta)$ 相乘来考虑一些罕见的事件，如有一些块创建事件突然发生，因此一些诚实块没有贡献公共链的得分。

5. 事实上，这个概率随着 $k$ 增加而以对数形式递减。  2

Top