# 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 follows8:

$$\begin{eqnarray} \large p &=& \text{ 诚实节点找到下一个区块的概率}\ \\ \large q &=& \text{ 攻击者找到下一个区块的概率}\ \\ \large q_z &=& \text{ 攻击者落后 z 个区块却依然能够赶上的概率} \end{eqnarray}$$

$$\large q_z = \begin{Bmatrix} 1 & \textit{if } p \leq q\ \\ (q/p)^z & \textit{if } p > q \end{Bmatrix}$$

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.

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:

$$\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)} & \textit{if } k\leq z\ \\ 1 & \textit{if } k > 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...

#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.

   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.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


[8] An Introduction to Probability Theory and its Applications* William Feller John Wiley & Sons* (1957) https://archive.org/details/AnIntroductionToProbabilityTheoryAndItsApplicationsVolume1

## 赌徒破产问题

A.手气 B.谁先抛硬币 C.抛硬币次数 D.总游戏时长 E.以上皆是 F.以上皆不是

## 赌博破产问题 Python 模拟

• 把 round_num 改成 1000 试试

• 庄家来一点「抽水」

【Python 知识点】 点击链接跳转至《自学是门手艺》相应知识点

import random
'''

10位玩家，赌本10元，进行100轮。
'''

round_num = 10
person_num = 10
player_total_win_money = 0

for person in range(1,person_num + 1):

gambling_money = 10

for r in range(1,round_num + 1):
coin = random.randint(0, 1) # 0为正，1为反
if coin == 0 :
gambling_money = gambling_money + 1
elif coin == 1 :
gambling_money = gambling_money - 1

if gambling_money == 0 :
# 因破产而退出赌博
break
else:
pass
player_total_win_money += gambling_money - 10
print("第 {} 号玩家经过 {} 轮赌博，最后的资产为 {} 元".format(person,r,gambling_money))
print("=========")
if player_total_win_money > 0:
print("玩家赢！赢了：{} 元".format(player_total_win_money))
elif player_total_win_money <0:
print("庄家赢！赢了：{} 元".format(-player_total_win_money))
else:
print("庄家和玩家平手！")

第 1 号玩家经过 10 轮赌博，最后的资产为 4 元

=========



• 二项随机漫步

• 泊松分布

## 延伸阅读

https://zhuanlan.zhihu.com/p/56151888

## 攻击者追块概率计算 Python 版

【Python 知识点】

import math
def attacker_success_probability(q, z):
sum = 1.0
p = 1.0 - q
lamba = z * (q / p)
i = 0;
k = 0;
for k in range(z + 1):
poisson = math.exp(-lamba)
for i in range(1, k + 1):
poisson *= (lamba / i)
sum -= poisson * (1 - pow(q / p, z - k))
return sum

q= 0.1
print("q = {}".format(q))
for z in range(0,10):
prob = attacker_success_probability(q, z)
print(" z = {}, P = {:.10f}".format(z, prob))

q = 0.1
z = 0, P = 1.0000000000
z = 1, P = 0.2045872739
z = 2, P = 0.0509778928
z = 3, P = 0.0131722417
z = 4, P = 0.0034552435
z = 5, P = 0.0009136822
z = 6, P = 0.0002428027
z = 7, P = 0.0000647353
z = 8, P = 0.0000172998
z = 9, P = 0.0000046312

q= 0.3
print("q = {}".format(q))
for z in range(0,50,5):
prob = attacker_success_probability(q, z)
print(" z = {}, P = {:.10f}".format(z, prob))

q = 0.3
z = 0, P = 1.0000000000
z = 5, P = 0.1773523114
z = 10, P = 0.0416604800
z = 15, P = 0.0101007622
z = 20, P = 0.0024803982
z = 25, P = 0.0006132284
z = 30, P = 0.0001522339
z = 35, P = 0.0000378958
z = 40, P = 0.0000094517
z = 45, P = 0.0000023608