发布时间:2020年1月5日
微博:比特币布道者
《纠正中本聪关于<比特币白皮书>中“赌徒破产问题“的描述》
原文:
攻击者从给定的落后点追上的概率类似赌徒破产。假定一个赌徒输了钱,他有永远花不完的钱,并且一直赌下去,试图达到盈亏平衡,我们可以计算出他达到盈亏平衡点的概率,也就是攻击者追上诚实链的概率,如下所示:
p=诚实节点找到下一区块的概率
q=攻击者找到下一区块的概率
qz=攻击者在落后z个区块时追上诚实链的概率
当p≤q时,qz=1
当p>q时,qz=(q/p)^z
假设p>q,随着攻击者需要追上区块数量的增加,追上的概率呈指数下降。由于攻击者的成功概率低,如果他在早期没有幸运的追上,随着他进一步落后,追上的机会越来越渺茫。
纠正:
1.第二种赌徒破产问题的规则是:
一个赌徒初始时有n个筹码,每次有概率q赢得一个筹码,或者概率p(p=1-q)输掉一个筹码。赌徒赢得N个筹码后,或者输掉所有钱后,即终止游戏。
f(n)是赌徒赢得N个筹码的概率,n<N。
有以下两个临界点值:
f(0)=0,即,没有筹码,无法参与赌博,故概率为0。
f(N)=1,即,初始筹码等于目标筹码N,赌徒不需要参与赌博,就能赢得游戏,故概率为1。
2.错误点
中本聪描述攻击者输掉z个区块(也就是,诚实链领先z个区块),同时攻击者的筹码是无限的,计算攻击者追上诚实链的概率。
这种情况不符合“第二种赌徒破产问题”。因为,在第二种赌徒破产问题中,如果赌徒筹码是无限的(即,大于目标筹码N),赌徒就不需要参与赌博,就已经赢得游戏。
3.更正
攻击者落后诚实链z个区块,攻击者追上诚实链的概率,属于“第一种赌徒破产问题“。
即,诚实链初始时有z个筹码,每次有概率p赢得一个筹码,或者概率q(q=1-p)输掉一个筹码(攻击者追上1个区块,就相当于诚实链输掉一个筹码)。诚实链输掉所有筹码后,即终止游戏。
3.1 当p≤q时,即诚实节点只掌握了50%或更低的算力时,在筹码有限的情况下,经过无限次赌博(与攻击者竞争),诚实节点终归会输掉所有筹码,以破产宣告游戏结束,即,攻击者最终会追上了诚实链,所以qz=1。
注:即使诚实节点掌握了50%的算力,在筹码有限的情况下,经过无限次赌博,结局只有一个,输掉所有钱,赌徒破产,结束游戏。
3.2 当p>q时,通过赌徒破产问题公式,可以推导出,qz=(q/p)^z,在攻击者落后z个区块,同时算力不足的情况下,想追上诚实链的难度是呈指数级增加的,追上的概率基本为零。
参考:
(1)《Gambler’s Ruin Problem(赌徒破产问题)研究总结+修订2020.1.4》https://startbitcoin.org/?p=3696
(2)《比特币51%攻击是什么?比特币6次确认数是怎么得到的?》https://startbitcoin.org/?p=1872