Scroll

Categories

Tags

Monthly Archives

Keyword

Back

2018.07.12

# 5. 证明的高层次概述

We now provide some intuition as to why SPECTRE’s procedures indeed guarantee that transactions can be accepted safely, and that all transactions of honest users are quickly accepted. We aim at proving Property 4. As mentioned above, this property is easy to translate to the desired security properties of transactions (as we do formally in Appendix E). Concretely, we wish to prove the following statement (in the proposition, $G_r^{pub} := ∪_{u∈honest} G_r^u$ ):

### Proposition

Assume block x was published at time $t_{pub}(x ∈ G_{t_{pub}}^{pub} )$, and y not published before time $t_{acc}(y ∉ G_{t_{acc}}^{pub})$. 1 Let $T = t_{acc}-t_{pub}$ . Then the probability that x will not always precede y ($Pr (∃u ∈ honest, ∃s ≥ t_{acc} : vote_{x,y}(virtual (G_s^u )) ≥ 0)$) decreases exponentially in T .

### 命题

Proof overview. Assume that the event in which y comes to precede x in some future DAG occurs. Let s be the earliest moment in time that such an event occurred at some node. Notice that y cannot be in the past of x or in its future (otherwise their order is determined by the topology and cannot be reversed). We thus assume henceforth $y ∈ anticone (x)$.

The block race after x is published. We ﬁrst consider the votes of blocks created after the publication of block x:

• (Almost) all honest blocks created between $t_{pub}$ and $t_{acc}$ vote forever in favour of $x≺y$ , as they have x in their past but not y . Denote by $n_1$ the number of such blocks.

• All honest blocks created between $t_{acc}$ and s vote in favour of $x≺y$ , as well, by the choice of s. Denote by $n_2$ the number of such blocks.

• Denote by $m_1$ and $m_2$ the number of blocks created by the attacker in the time intervals corresponding to $n_1$ and $n_2$ . Honest nodes possess a fraction $1-α > α$ of the computational power. Consequently, for any positive constant C , the probability that the relation $m_1+m_2+C-(n_1 + n_2 ) ≥ 0$ will ever be satisﬁed decreases exponentially with $n_1$ . This is typically analyzed as the probability that a biased random walk on the integers, beginning at C , returns to the origin (see [13], [17], [18]).

x发布后的区块竞争. 我们首先考虑在区块x发布后创建的区块投票：

• （几乎）在$t_{pub}$ 和$t_{acc}$之间创建的所有诚实区块永远投票支持$x≺y$，因为他们在过去有x，但不是y。 用$n_1$表示这种块的数量。

• 在$t_{acc}$和s之间的创建的所有诚实区块也都投票支持$x≺y$，直到时间点s。 用$n_2$表示这种块的数量。

• 用$m_1$和$m_2$表示攻击者在对应于$n_1$和$n_2$的时间间隔中创建的块的数量。 诚实的节点具有计算能力的比例$1-α > α$。 因此，对于任何正常数C，满足关系$m_1+m_2+C-(n_1 + n_2 ) ≥ 0$的概率将会满足$n_1$指数级下降。 这通常被分析为从C开始的整数上的偏见随机游走返回原点的概率（参见[13]，[17]，[18]）。（译注： 随机游走就是指随机的分布，比如说设x, y在[-1，1]内随机抽取，形成一个坐标，点数足够多会近似一个圆，这里“偏见”体现在概率的分布是不一样的，比如说抽取到0的概率大于抽取到1的概率，这里也是这个意思，如果是以常数C为原点，则随机选择大于或等于C的点，但是越接近C被抽取的概率就越高，最终平均值趋近于C）

The term $m_1+m_2+C-(n_1 + n_2 )$ represents the aggregate vote between x and y , considering only blocks created after x’s publication. We now show that blocks that the attacker prepared in advance before x’s publication, in a preparatory “pre-mining” stage, do not give him more than some constant advantage (which will be counted into C above).

### The pre-mining stage

Honest blocks that were created before x was published are typically in its past (apart from a small set of blocks) and hence have their vote decided by the majority of votes in their future (as per Alg. 1). Their vote is thus possibly subject to change as the DAG grows, and as the attacker publishes blocks.

### 预挖矿阶段

For every block z in the past of x we must therefore consider the number of blocks above it that vote in favour of x and those that vote against it. Denote by $X_z$ the gap between the number of attacker blocks and honest blocks in the future of z , up to time $t_{pub}$ . In Lemma 24 we show that the worst case gap $X_z$ (over all blocks $z ∈ past (x)$) can be modeled as a reﬂecting random walk over the nonnegative integers, with bias towards the origin. Consequently, the best gap that the attacker can secretly gain over a block in $past (x)$ has an exponentially decaying tail, and, in particular, is bounded by a constant w.h.p.

All in all, as $t_{acc}-t_{pub}$ grows, the number $n_1$ of votes, or “conﬁrmations”, that x receives increases linearly, and the probability that the attacker will be able to reveal enough blocks so that some $z ∈ past (x)$ will have more $y≺x$ votes in its future than $x≺y$ votes, decreases exponentially in $n_1$ . Since this holds for all $z ∈ past (x)$ uniformly, it implies in particular that the genesis block has more $x≺y$ votes in its future than $y≺x$ votes (unless an exponentially unlikely event occurred). The vote of the virtual block is determined by that of the genesis block (this is easy to see, and is proven in Lemma 13), completing the argument.

The proposition above is the gist of Lemmas 14 and 15. In the above sketch, we abstracted out many additional subtleties and details. For instance, honest blocks that were created D seconds around $t_{pub}$ , $t_{acc}$ , or s may not have contributed votes in favour of x. In our formal analysis (Appendix E) we count these as attacker blocks, accounting for the worst case, and add them to the aforementioned constant C . We additionally show how the user can measure $n_1$ correctly, even if the attacker publishes his blocks in an attempt to delay acceptance.

1. Intuitively, $t_{acc}$ represents the time at which some node accepted a transaction which appears in block x.  2

Top