纠正中本聪关于<比特币白皮书>中“赌徒破产问题“的描述

作者:王建伯

发布时间: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)《Gamblers Ruin Problem(赌徒破产问题)研究总结+修订2020.1.4http://btc.mom/?p=3696

(2)《比特币51%攻击是什么?比特币6次确认数是怎么得到的?》http://btc.mom/?p=1872

相关文章:

发表评论