比特币雙花攻擊成功機率與比特币白皮書的calculation部分解讀

第一部分： q z = ( q / p ) z q_z = (q/p)^z qz​=(q/p)z

已知

p p p = probability an honest node finds the next block

q q q = probability the attacker finds the next block

q − z q_{-z} q−z​ = probability the attacker will ever catch up from z blocks behind

注： p + q = 1 p + q = 1 p+q=1

求攻擊者在落後z個區塊的情況下被攻擊者追上的機率。

分析：

這個問題可以等價于賭徒問題，賭徒（攻擊者）本錢為 − z -z −z；相當于目前落後z個區塊

• 當資産為 − x -x −x塊時，賭徒會止損（ x > z x>z x>z），即賭徒不能忍受損失 x x x；相當于當攻擊者發現已經落後誠實結點x個區塊後，不再進行攻擊。
• 當資産為 0 0 0時，賭徒會收手；相當于攻擊者目前區塊高度與誠實結點一樣，攻擊成功。

賭徒賭赢的機率是 q q q，那麼賭徒的本錢為-z時，賭徒攻擊成功的機率為

q − z = q ∗ q − z + 1 + ( 1 − q ) ∗ q − z − 1 q_{-z}= q*q_{-z+1}+(1-q)*q_{-z-1} q−z​=q∗q−z+1​+(1−q)∗q−z−1​

目的是資産達到i，我們來看第一回合賭局，有兩種可能，以q的機率賭赢，以1-q的機率賭輸：

• 第一回合賭赢，第二回合賭徒的本錢為 − z + 1 -z+1 −z+1，後面基于本錢 − z + 1 -z+1 −z+1攻擊成功的機率為 q − z + 1 q_{-z+1} q−z+1​；這種情況的機率為 q ∗ q i − 1 q*q_{i-1} q∗qi−1​
• 第二回合賭輸，第二回合賭徒的本錢為 − z − 1 -z-1 −z−1，後面基于本錢 − z − 1 -z-1 −z−1攻擊成功的機率為 q − z − 1 q_{-z-1} q−z−1​；這種情況的機率為 ( 1 − q ) ∗ q i − 1 (1-q)*q_{i-1} (1−q)∗qi−1​

這是一個二階的數列，相當于解方程 x = q x 2 + ( 1 − q ) x=qx^2+(1-q) x=qx2+(1−q)，解得 x 1 = 1 x_1=1 x1​=1， x 2 = 1 − q q x_2=\frac{1-q}{q} x2​=q1−q​。

注意：

• q 0 = 1 q_0=1 q0​=1：如果攻擊者與誠實結點高度差異為0，那麼攻擊成功
• q − ∞ = 0 q_{-\infin}=0 q−∞​=0：如果攻擊者落後誠實結點 ∞ \infin ∞個區塊，攻擊者放棄攻擊，攻擊失敗。如何了解上面的表述？即攻擊者在追趕的過程中無論落後多少個區塊也不會放棄攻擊

當 x 1 = x 2 x_1=x_2 x1​=x2​時，即 q = 1 2 q=\frac{1}{2} q=21​，

q − z = ( A + B ( − z ) ) ( x 1 ) − z = A + B ( − z ) q_{-z}=(A+B(-z))(x_1)^{-z} = A+B(-z) q−z​=(A+B(−z))(x1​)−z=A+B(−z)

又因為 q 0 = 1 q_0=1 q0​=1且 q − ∞ = 0 q_{-\infin}=0 q−∞​=0，是以 q z = 1 q_z=1 qz​=1。

當 x 1 ≠ x 2 時 ， {x_1}\neq{x_2}時， x1​̸​=x2​時，

q − z = A ( x 1 ) − z + B ( x 2 ) − z = A + B ( 1 − q q ) − z q_{-z}=A(x_1)^{-z}+B(x_2)^{-z} = A+B(\frac{1-q}{q})^{-z} q−z​=A(x1​)−z+B(x2​)−z=A+B(q1−q​)−z

• 當 q &lt; 1 2 q&lt;\frac{1}{2} q<21​時， q − ∞ = 0 q_{-\infin}=0 q−∞​=0 且 q 0 = 1 q_0=1 q0​=1=> A = 0 ， B = 1 A=0，B=1 A=0，B=1 => q − z = ( 1 − q q ) − z q_{-z}=(\frac{1-q}{q})^{-z} q−z​=(q1−q​)−z
• 當 p &gt; 1 2 p&gt;\frac{1}{2} p>21​時， q − ∞ = 0 q_{-\infin}=0 q−∞​=0 且 q 0 = 1 q_0=1 q0​=1=> A = 1 ， B = 0 A=1，B=0 A=1，B=0 => q z = 1 q_z=1 qz​=1

綜上所述：

q − z = { ( 1 − q q ) − z = ( q 1 − q ) z , q &lt; 1 2 1 , q ≥ 1 2 q_{-z} = \begin{cases} (\frac{1-q}{q})^{-z}=(\frac{q}{1-q})^{z}, &amp; q&lt;\frac{1}{2} \\ 1, &amp; q \geq \frac{1}{2} \end{cases} q−z​={(q1−q​)−z=(1−qq​)z,1,​q<21​q≥21​​

進行變換：

q − z = { ( q p ) z , q &lt; p 1 , q ≥ p q_{-z} = \begin{cases} (\frac{q}{p})^{z}, &amp; q&lt;p \\ 1, &amp; q \geq p \end{cases} q−z​={(pq​)z,1,​q<pq≥p​

第二部分：泊松分布

當我們發起一筆交易tx在T1時被廣播，而攻擊者同時在T1做雙花攻擊。在T2時tx被主鍊上z個區塊支援。

那麼我們需要猜測攻擊者在從T1時刻到T2時刻，暗地裡挖了多少個塊？

假設是蔔瓦松過程，T為一段長時間，在間隔T内，誠實結點挖了p個，攻擊者挖了q個。

誠實結點挖z個區塊所花時間t滿足 z = ( p T ) t z = (\frac{p}{T})t z=(Tp​)t

攻擊結點挖x個區塊所花時間t滿足 x = ( q T ) t x = (\frac{q}{T})t x=(Tq​)t

是以，

x = q p z x = \frac{q}{p}z x=pq​z

是以，攻擊者暗地裡挖的區塊個數滿足 λ = q p z \lambda=\frac{q}{p}z λ=pq​z的泊松分布P(x)。是以攻擊者攻擊成功的機率為

P ( 攻 擊 成 功 ) = ∑ x = 0 + ∞ P ( x ) ∗ q − z ( z − x ) = ∑ x = 0 + ∞ λ x e x p ( − λ ) x ! ∗ { ( q p ) z − x , x ≤ z 1 , x &gt; z = 1 − ∑ x = 0 z λ x e x p ( − λ ) x ! ( 1 − ( q p ) z − x ) P(攻擊成功) = \sum_{x=0}^{+\infin} P(x)*q_{-z}(z-x) = \sum_{x=0}^{+\infin} \frac{{\lambda}^{x}{exp(-\lambda)}}{x!} * \begin{cases} (\frac{q}{p})^{z-x}, &amp; x\leq z \\ 1, &amp; x &gt; z \end{cases}=1-\sum_{x=0}^{z} \frac{{\lambda}^{x}{exp(-\lambda)}}{x!}(1-(\frac{q}{p})^{z-x}) P(攻擊成功)=x=0∑+∞​P(x)∗q−z​(z−x)=x=0∑+∞​x!λxexp(−λ)​∗{(pq​)z−x,1,​x≤zx>z​=1−x=0∑z​x!λxexp(−λ)​(1−(pq​)z−x)