按：本章内容较多，不再在全部原文之后才开始解读——直接将解读内容插到原文中，也不再按句解读，而是按段落解读。本章讲述的内容，直观理解还是比较容易，但要完全看懂计算并证明，并不容易。
We consider the scenario of an attacker trying to generate an alternate chain faster than the honest chain. Even if this is accomplished, it does not throw the system open to arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Nodes are not going to accept an invalid transaction as payment, and honest nodes will never accept a block containing them. An attacker can only try to change one of his own transactions to take back money he recently spent.
我们考虑一个攻击者试图比诚实链更快地生成另一条链的情况。即使攻击者达到了这个目标，它也不会打开系统进行任意更改，比如凭空创造价值或夺取从未属于攻击者的资金。一个攻击者只能尽可能改变他自己的交易去拿回他最近花出去的钱。
在区块链中，每个区块都包含着前一个区块的信息，形成了一个不可篡改的链条。攻击者如果想要更改区块链上的信息，需要比整个网络上的其他节点更快地生成一条新的链，使得其他节点都认为这是新的正确链。
The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The success event is the honest chain being extended by one block, increasing its lead by +1, and the failure event is the attacker’s chain being extended by one block, reducing the gap by −1.
这段话主要在讲区块链技术中的一个概念——“诚实链”和“攻击链”的竞争过程可以被描述为一个二项式随机漫步。其中，成功事件是指诚实链被扩展了一个区块，导致其领先优势增加了+1；失败事件则是指攻击链被扩展了一个区块，导致其与诚实链的差距减少了-1。
二项式随机漫步是一种随机过程，它可以用来描述某个事件在一系列独立的试验中的概率分布。在这里，诚实链和攻击链的竞争过程就可以被看作一系列独立的试验，每一次试验都可以是诚实链或攻击链被扩展一个区块的事件之一。
这个概念在区块链中非常重要，因为它可以帮助我们更好地理解区块链技术中的安全性和去中心化性质。通过了解区块链技术中的各种概念和原理，我们可以更好地应用这些知识去设计和实现更安全、更可靠的区块链系统。
【Binomial Random Walk】
Binomial Random Walk（二项式随机游走，二项随机漫步）是一种随机过程，描述了一系列随机步长对一个初始值进行的累加。在二项式随机游走中，每一步的步长可以是1或-1，每个步长都有相同的概率出现。步长的正负与概率相等的特性使得二项式随机游走具有对称性。
二项式随机游走可以用来模拟一些实际问题，例如股票价格的波动、随机漫步等。在金融领域，二项式随机游走被广泛应用于期权定价模型中，其中股票价格的变化被视为随机步长的累加。
参隨機漫步
The probability of an attacker catching up from a given deficit is analogous to a Gambler’s Ruin problem. Suppose a gambler with unlimited credit starts at a deficit and plays potentially an infinite number of trials to try to reach breakeven. We can calculate the probability he ever reaches breakeven, or that an attacker ever catches up with the honest chain, as follows [^8]:
这段话讲的是攻击者从一定的落后状态追赶上来的概率类似于一个赌徒破产的问题。假设一个赌徒有无限的信用，从一个亏损状态开始，可能进行无限次尝试以达到盈亏平衡。我们可以计算他达到盈亏平衡的概率，或者攻击者追赶上诚实链的概率，如下所述。
$\large p = \textit{ probability an honest node finds the next block}$ 诚实链找到下一个区块的概率
$\large q = \textit{ probability the attacker finds the next block}$ 攻击链找到下一个区块的概率
$\large q_z = \textit{ probability the attacker will ever catch up from z blocks behind}$ 攻击者从落后z块的位置追上诚实链的概率
\[\large q_z = \begin{Bmatrix} 1 \hspace{4 em} \textit{if}\; p \leq q\\ \left(\dfrac qp\right)^z \hspace{2 em} \textit{if}\; p \gt q \end{Bmatrix}\]从统计学上讲，如果 $p\lt q$，则攻击链比诚实链进展更快，能追上并超过； 如果 $p = q$，则攻击链和诚实链进展一样快，因为这里假设是尝试无限次的，“无限”和“无限+z”可以认为是相等的，在理论上也相当于追上了。 如果 $p \gt q$，则诚实链更容易建立，自然追不上。这个公式还可以只要第二行，如果结果大于1，再修正为1就行了，因为概率值最大只能是1，这里必须修正。
\[\large q_z = \left(\dfrac qp\right)^z = \begin{Bmatrix} 1 \hspace{4 em}\textit{if}\; q_z \geq 1\\ \left(\dfrac qp\right)^z \hspace{1.5 em} \textit{if}\; q_z \lt 1 \end{Bmatrix}\]这个公式从直觉上很好理解，成功打包发布下一个区块的概率，诚实链的概率是$p$，攻击链的概率是$q$，则攻击链相对于诚实链的成功概率是$\dfrac qp$。假若攻击链条落后$z$块要赶上，则它赶上的概率是$\left(\dfrac qp\right)^z$. 当$\dfrac qp < 1$时，如果$z$比较大，则$\left(\dfrac qp\right)^z$几乎没有可能赶上诚实块。比如
$\dfrac qp = \dfrac 13$，这说明攻击链条有诚实链$\dfrac{1}{3}$的可能成功发布下一个区块，而再成功发布一个区块的可能性减为$\left(\dfrac 13\right)^2$，一次类推，成功发布$z$个区块的概率的概率就是$\left(\dfrac 13\right)^z$，假定$z = 6$，$\left(\dfrac 13\right)^6 \approx 0.137\%$。因为算力的份额和发布区块的可能性是对应的，这里实际上相当于假设攻击节点拥有$\dfrac 13$拥有诚实结点的算力，也就是攻击节点的算力占全网的$\dfrac 14$，这是非常夸张的假设，实际上很难有某个势力能有这么大的算力。即便是这样，通过计算得知，要赶上6个快的可能性也只有$0.137\%$，按十分钟一个区块，对应的时间约一个小时。
所以当一个区块被全网接受后，很难被篡改。
Given our assumption that $p>q$, the probability drops exponentially as the number of blocks the attacker has to catch up with increases. With the odds against him, if he doesn’t make a lucky lunge forward early on, his chances become vanishingly small as he falls further behind.
我们假设$p>q$，则追上诚实链增长的可能性按需要追赶的区块数量呈指数下降。因为他面临不利情况（胜算不高），如果他不在早期进行幸运的向前冲，随着他落后的程度越来越大，他的机会就变得微乎其微了。
We now consider how long the recipient of a new transaction needs to wait before being sufficiently certain the sender can’t change the transaction. We assume the sender is an attacker who wants to make the recipient believe he paid him for a while, then switch it to pay back to himself after some time has passed. The receiver will be alerted when that happens, but the sender hopes it will be too late.
我们现在考虑一个交易的收款人要等多久才能确认付款人不能篡改交易。我们假设付款人是一个攻击者，他想让接收者相信他已经支付了，但旋即把钱发回给自己。如果那种情况发生，收款人将被警告，但是发送者希望警告很晚。
The receiver generates a new key pair and gives the public key to the sender shortly before signing. This prevents the sender from preparing a chain of blocks ahead of time by working on it continuously until he is lucky enough to get far enough ahead, then executing the transaction at that moment. Once the transaction is sent, the dishonest sender starts working in secret on a parallel chain containing an alternate version of his transaction.
收款人创建一个新的密钥对然后把公钥给付款人，这样付款人就无法提前对交易签名。这阻止了发送者试图准备一条链，他持续工作在这条链上，他足够幸运并大幅领先，然后在那时执行交易。
The recipient waits until the transaction has been added to a block and z blocks have been linked after it. He doesn’t know the exact amount of progress the attacker has made, but assuming the honest blocks took the average expected time per block, the attacker’s potential progress will be a Poisson distribution with expected value:
收款人等待交易被添加进某个区块中并且z个区块已经链接到前面这个区块后。他不知道攻击者具体怎么做的，但是假设诚实的区块用掉了每个区块预期的时间，这个攻击者可能的进度将是一个泊松分布，其期望值为
\[\large \lambda = z \frac qp\]To get the probability the attacker could still catch up now, we multiply the Poisson density for each amount of progress he could have made by the probability he could catch up from that point:
为计算攻击者现在仍能赶上的概率，我们给他可能到达的进度的泊松密度乘以他在那个进度能赶上诚实链的概率：
\[\large \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \begin{Bmatrix} (q/p)^{(z-k)} \hspace{1 em} \textit{if}\;k\leq z\\ 1 \hspace{4 em} \textit{if} \; k \gt z \end{Bmatrix}\]Rearranging to avoid summing the infinite tail of the distribution…
变换以避免对分布的无限尾部求和…
\[\large 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left ( 1-(q/p)^{(z-k)} \right )\]Converting to C code…
转成C代码…
#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}
Running some results, we can see the probability drop off exponentially with z.
运行得到一些结果，我们可以看到概率随z呈指数下降。
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
Solving for P less than 0.1%…
P小于0.1%的解…
P < 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340
参考资料