今天给别人分享比特币白皮书时才发现，第11小结Calculations部分当时并没有仔细理解消化，中间还有很多知识点值得仔细研究，虽然现在还是有几处没有吃透的地方，但先记录下来希望大家讨论解决。
首先先附上原文片段
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.
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]:
p = probability an honest node finds the next block
q = probability the attacker finds the next block
\(q_z\)= probability the attacker will ever catch up from z blocks behind
$$
q_z=
\begin{cases}
1 &\mbox{if $p\leq$q}\\
\left(\frac{q}{p}\right)^z &\mbox{if $p>$q }
\end{cases}
$$
上面这个公式的来由作者用两个模型做出了类比，一个是二项随机游走（Binomial Random Walk）另外一个是赌徒破产问题（Gambler’s Ruin Problem)。那么接下来我们从这两个模型入手分析公式的来由。
赌徒破产模型
二阶线性递归
首先我们先要有一个预备知识那就是二阶线性递归。
二阶线性递归是指数列的一项是由前两项的线性组合决定的，次数为一次。通常二阶线性递归的形式可以如下表示：
$$ a_n = pa_{n-1} + qa_{n-2} $$
设 \( \alpha, \beta. \)拼凑等比数列，使得，
$$
\begin {aligned}
a_n = pa_{n-1} + qa_{n-2} \\
a_n = (\alpha+\beta)a_{n-1}-\alpha\beta a_{n-2} \
\end {aligned}
$$
所以，
$$
\begin{cases}
\alpha+\beta=p \\
\alpha\beta=q
\end{cases}
$$
若 \( \alpha\not=\beta. \)则
$$ a_n - \alpha a_{n-1}=\beta^{n-2}(a_2-\alpha a_1) $$
又由于\(\alpha,\beta 具有对称性\)
$$
\begin{cases}
\beta a_n - \alpha\beta a_{n-1}=\beta^{n-1}(a_2-\alpha a_1) \\
\alpha a_n - \beta a_{n-1}=\alpha^{n-1}(a_2-\beta a_1)
\end{cases}
$$
解得，
$$ a_n=\frac{a_2-\alpha a_1}{\beta(\beta-\alpha)}\beta^n + \frac{a_2-\beta a_1}{\alpha(\alpha-\beta)}\alpha^n $$
从上面的式子可以发现特征根法的结果为：
$$ a_n=A\alpha^n + B\beta^n$$
其中A，B可以带入两个特殊值求解出，例如\(a_1,a_2。\alpha,\beta\)则为递推公式\(a_n=pa_{n-1}+qa_{n-2}\)对应特征方程\(x^2=px+q\)的两个根。
赌徒模型
此时我们引入赌徒破产问题，假设游戏中赌徒有\(\alpha \)的概率赢得一元，\(1-\alpha \)的概率输掉一元。现在赌徒拥有h元,他的目标是N元，当他成功赢到N元(即手里的前变为N)或者输光已有的h元（手头钱为0）则游戏结束。P(N|h)可以表示赌徒拥有h元赢到N的概率。明显有两个值我们可以求解得P(N|0)=0, P(N|N)=1.
当赌徒拥有h元时，那么下一轮的状态有\(\alpha \)的概率是h+1或者\(1-\alpha \)的概率是h-1。因此当前胜利的概率可以用下一状态的两种可能的和表示。
$$ P(N|h) = \alpha P(N|h+1)+(1-\alpha)P(N|h-1) $$
这边构成了一个二阶线性递归，根据上面的知识我们知道特征多项式为
$$ x^2 - \frac{1}{\alpha}x + \frac{1-\alpha}{\alpha}=0$$
很容易的出上面方程的两个根是1和\(r=\frac{1-\alpha}{\alpha}\).所以，
$$P(N|h)=A(1)^h+B(r)^h$$
带入P(N|0)=0, P(N|N)=1可解得
$$
\begin{cases}
A+B=0 \\
A+B(r)^N = 1
\end{cases}
$$
$$
\begin{cases}
A=\frac{1}{1-r^N} \\
B=\frac{-1}{1-r^N}
\end{cases}
$$
所以，当赌徒拥有h元最终获得N的概率为
$$
P(N|h) = \frac{1-r^h}{1-r^N}
$$
建模解决问题
论文中的问题如果用赌徒破产模型建模的话可以从两个方面着手，一个是诚实节点拥有z个块，目标是输完最终拥有0个块（也就是攻击节点追上z个）可以用P(0|z)表示这一概率。
参考上面的模型，此时\(\alpha\)=q(攻击者发现块的概率)
$$ P(0|z)=\alpha P(0|z-1)+(1-\alpha)p(0|z+1)$$
解得，
$$
\begin{cases}
x_1=1 \\
x_2=\frac{\alpha}{1-\alpha} = r
\end{cases}
$$
$$P(0|z)=A(1)^z+B(r)^z$$
此时我们需要带入两个点求得A,B。 P(0|0)和\(P(0|\infty)\)是两个容易发现的边界点。因为\(r^z\)的单调性不一致需要分类讨论。
当0<r<1, \(0<\alpha<\frac{1}{2}\)时，
$$
\begin{cases}
A+B=0 \\
A=0
\end{cases}
$$
所以，B=1,P(0|z)=\((\frac{\alpha}{1-\alpha})^z = (\frac{q}{p})^z\)
当 \(r\geq 1, \alpha \geq\frac{1}{2}\)时
$$
\begin{cases}
A+B=1 \\
A+\infty=0
\end{cases}
$$
所以 P(0|z)=1.当然，从攻击者的角度来求解也是可以的即求解P(z|0),过程与上述类似。
