双花问题硬核科普:“手撕”比特币白皮书第11章

TokenClub资讯 240 2019-01-30 08:47

白皮书第11章计算很难懂?

为纪念比特币十年,圈内最近掀起了一股重读比特币白皮书的热潮。然而,虽然很多文章都在感叹比特币的经济机制设计得如何精妙,但竟然少有能把白皮书第11章的双花攻击成功率的计算公式讲明白的。

image.png

作为一个刚入圈的新手,我实在无法理解,如果弄不懂比特币背后的数学机制,不能确信双花的概率,我们又何来的对比特币系统安全性的信心。当然,如果诸位只是想要找个附属物安一个政治口号,宣扬一下自由主义的观念,再炒作和信仰一番,那就另当别论了。

我也看到了很多比较模糊、甚至与中本聪原意出入很大的说法。例如“比特币交易需要6个确认”:有人认为比特币一定要经过6个确认后,才算是交易成功;也有人认为经过6个区块的确认后,交易就不存在风险了。还有大家常常挂在嘴边的51%攻击:很多人认为,攻击的算力必须达到51%,或者必须多于50%,才能够攻击成功。但其实不是这样的。实际情况是,如果你拥有40%的算力,在人们采取6个确认的情况下,无限攻击成功的概率仍有50%。

“6个确认”和“51%攻击”的说法由来以久,且传播深远。但如果你读完中本聪的原文,你会发现,比特币白皮书中压根就没有提到这两个词。他既没有说交易一定需要6个确认,也没有说必须拥有51%的算力才能成功发动攻击。甚至在中本聪给出的简化模型里,只需要50%的算力,不管人们采取多少个确认(1000个或者10000个),无限攻击成功的可能性为100%。严格意义来说,人们应该称“51%攻击”为“50%攻击”。

但50%攻击显然不符合人们的直觉,也不符合人们少数服从多数的政治期望。在日后布道者们的宣传中,为了让人们能够快速理解和接受这个概念,双花攻击最终被简化成了“51%攻击”。

本文作为一篇硬核科普,将从数学概率的角度澄清人们对“6个确认”和“51%攻击”的一些误解。内容主要分为双花攻击流程、双花成功概率分析、结论与不足。为了读懂本文,你最好掌握一些概率论的知识,主要是泊松分布(学过高数就行);你也需要了解一下白皮书中提到的“赌徒破产模型”,它是我们理解“50%攻击”的关键。当然,如果你没有学过这些内容也无关紧要,因为它们背后的思想都简单易懂。尤其是“赌徒破产模型”,它看上去非常违背直觉,但很有趣。

 

双花攻击流程

最近钢铁佩奇比较火。为了让讲解过程不那么枯燥,请让我以钢铁佩奇为例来讲一讲这无聊而又致命的双花攻击。

image.png

引用电子货币领域经典的Alice和Bob交易例子,来说明比特币作为电子现金的三大难点及其解决方案。Alice想以1299元购买Bob的钢铁佩奇,Alice付款有2种方式,一是物理现金,二是电子转账。第二种方式实际上传递的是一个转账消息,电子消息充当了货币,其成功关键在于有银行判定Alice是否有足够的余额支付,并进行划扣,最终记录交易双方账户余额。

设想如果系统中没有中心的银行如何进行支付呢?这就是比特币想要解决的事情。

同样,Alice向Bob发送了一个电子消息“Alice给Bob转1299元。”想要使Bob相信这笔付款,起码要解决3个问题,证明此消息确实是Alice发送的(不可伪造性)、判断Alice确实有1299元(所有权证明),知道Alice没有同时支付给另一个人(双花)。

利用不对称加密算法,Alice使用私钥签名能够提供其资产所有权证明和保证交易的不可伪造性,这是比特币之前就已经很成熟的技术。

但是双花难题依旧没有解决,此前的电子货币方案一直依赖于引入中心第三方来解决,这相当于重造了一个中央银行,现实意义并不大。中本聪创造性地利用区块链作为公共账本和引入矿工竞争记账解决了这个问题,这也是比特币的伟大之处。

双花是指,Alice给Bob转钱的同时又给Charlie转了相同数目的一笔钱买手机。这时候Bob和Charlie查看自己的账本进行验证,发现Alice确实有1299元。他们无法得知Alice是否给其他人也转账了。于是,Alice拿走佩奇和手机,剩下Bob和Charlie只有一个人能得到1299元,这就是简单情形下的双花问题。中本聪引入矿工之后,Bob收到这笔付款通过交易验证后,并不会立马独自记账然后发货,他会广播这笔交易,让网络上多数人帮忙验证Alice是否只给自己转了这笔钱。假设Charlie也广播了这笔交易,那么最后只能有一笔交易记在公共账本上。通过分析可以知道,这种简单双花基本上是不可能实现的。其他矿工没动机帮Alice记假账(放入Alice给Bob和Charlie的两笔冲突交易)即使Alice竞争到了记账机会,广播区块之后,也会被其他矿工验证出两笔冲突交易存在。

以上情形是交易被Alice确认之前的简单双花问题,还有一种复杂的双花问题,Alice可以转给自己,同时制造分叉链最后代替主链完成双花,基本攻击流程是这样的。

(1)在图(a)最后一个区块,Alice向全网广播“Alice给Bob转1299元”

(2)Alice修改自己的客户端程序,记入一笔“Alice给Alice转1299元”,同时悄悄挖矿,不广播自己的进度,挖出图(b)的白色链。

(3)等到Bob看到全网主链(黑色链)有足够的确认区块个数(通常认为是6个,为什么?),发出钢铁佩奇之后,如果Alice的白链长于黑色主链,他会向全网公布自己的进度,从而被接受为新的主链。

image.png

主链只记录“Alice给Alice转1299元”,从而使得“Alice给Bob转1299元”无法记入账本。最终双花攻击成功,Alice拿到了钢铁佩奇,Bob一无所获。当然,Alice发起攻击是有成本的,他为了挖出白色链,需要投入矿机以及电力消耗,除非收益大于成本,否则理性攻击者是不会发起攻击的。余下全文,我们仅考虑在收款方等待z个确认之后,占全网算力q%的攻击者双花成功的概率。也就是说,不考虑攻击的经济可行性,仅仅分析攻击成功的概率大小。

 

双花成功概率分析

我们都学过如何求解应用题。第一部分交代了双花问题的背景,相当于告诉了我们“应用题”的条件,现在我们需要求解这道题。题目是:已知Alice占有全网算力比例为q,诚实节点占全网算力比例为p,p+q=1,Bob等待z个区块确认交易后,求解Alice使得自己偷偷挖的白链长度追上黑链(主链)的概率P(win)?

此问题还包含着以下假设:追赶时间内,系统难度值保持不变;攻击者Alice和诚实节点的算力相对比例不变。

image.png

求解追上概率可以拆解为两种情况来分析,第一情况是在等待z个区块确认的时间里,这段时间攻击者Alice挖出了k个区块,且k>z即攻击链更长。这种情况下,一旦公开网络上最长链追加了z个区块,Bob就会认为交易已经确认,可以向Alice发出钢铁佩奇。而Alice一旦看到货已经发出,他就可以公布自己的白色链,由于白色链长于黑色,那么Alice记录的“Alice给Alice转1299元”交易记录留在主链上,双花成功。

另一种情况是,k<=z,记n=z-k表示攻击链和诚实主链的差距。也就是说,在Bob确认交易的时候,Alice的白链短于主链,不足以发动攻击,他会继续偷偷挖,和主链竞争不断缩小差距,直到比主链长。

算出两种情况下概率再求和就是攻击成功概率了。

泊松分布—求Alice挖出k个区块的概率

以下按照中本聪的白皮书原文思路来推导,采用泊松分布假设,Meni Rosenfeld在“Analysis of hashrate-based double-spending”中采用更加精确的负二项分布,两个结果差异很小。

假设诚实节点按预期时间均匀出块,那么在诚实节点挖出Z个块的时间内,Alice挖出区块的平均值是λ=z q/p 。

泊松分布的概率函数为:

P(x=k)=(λ^k ⅇ^(-λ))/k!  ,   k=0,1,2,3·····

泊松分布用来描述单位时间内随机事件发生的次数。泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生次数。

通过泊松分布,就可以知道k=1,2,3····的概率分别是多少,比如,这段时间Alice只挖到k=1个块的概率是

image.png

那么第一种情况发生的概率就是

image.png

这个式子表示发生k=z+1,z+2,z+3····这些事件的概率之和。

 

赌徒破产问题

如果你看到了这里,恭喜。要么你就是一个脑子里还留了一点高等数学的人,对于读者来说这已经相当不易,欢迎在后台联系我;要么你对严谨枯燥内容的抗性已经超过了绝大多数人,这比前者还要难得。

我们现在需要对问题的另一半进行解答。但在讨论这一部分之前,你需要接受一个反直觉的例子:假使一个赌徒把自己的钱分成n份去赌场赌博,他输赢的概率为二分之一。如果这场赌博进行无限次,赌徒一定会输光自己身上所有的钱。

这就是大名鼎鼎的“赌徒破产问题”。这个问题的关键在于假设赌场手里的钱远多于赌徒,因而不需要考虑筹码归零的问题;而赌徒手里的钱远少于赌场,一旦某一次赌输,使筹码归零,便必须退出游戏。因此,虽然从单次赌博的概率上看上去,赌徒和赌场的游戏是平等的,但由于筹码的多少限制了赌徒和赌场游戏可以进行的区间,最终游戏的天平倒向了赌场。

这个问题规劝了那些赌博成瘾的人们。它说明了,就算游戏是公平的,但如果一个人执迷赌场以此为家,最后也将赔得精光。

这与攻击者和诚实节点又何其之像!攻击者只要区块数追平后超过诚实节点所挖的链,按照比特币“最长链”的原则,其他算力便会转移到节点数更高的新链上来,攻击成功。假设诚实节点们挖得的链长度超过攻击者z-k个,这就好比诚实节点作为赌徒手里有z-k个筹码。此时,诚实节点与攻击者同时进行着一场赌博的竞赛,一旦诚实节点将手中的筹码输干净,攻击者便能追上。(其实应该是输到剩下-1个,但中本聪的白皮书里的假设是输到0。其实,输到0仅仅是追平,但双花攻击需要超越,因此这个假设不太严谨,读者们见仁见智,可以做更深的讨论。我们暂时按照白皮书里的思路走。)

理解了这个比喻,让我们回到原来的话题。现在我们要求第二种情况下追上的概率,这种情况下,我们可以把问题进行简化,近似抽象成赌徒破产问题。已经知道,此时Alice挖出k个区块,比主链少n=z-k个。在既定的n个区块差距下,他们将竞赛挖矿,攻击者成功概率是q,诚实节点是p。放在数轴上考虑,每一局竞赛当攻击者赢,则向左一步,缩小差距为n-1,否则向右变为n+1。问多局博弈之后,Alice向左移到0的概率?

image.png

我们可以先考虑n=1的时候移到n=0的概率。记p(1)表示从1移到0的概率,p(2)表示从2移到0的概率,依次类推求p(n)。

显然在1这个点,一局博弈之后,只有两种情况,向左到0,向右到2。然后从2移到0的概率为p(2).所以有以下方程:

p(1)=q+p⋅p(2)

P(1)表示从1到0的概率,也可以表示任何一点向左一步的概率。而从2到0,一定会先到1再到0,故p(2)=p^2 (1).

代入p(2),就可以求出 p(1)=q/p  ,则p(n)=(q/P)^n

当q>p ,即  q/p>1  ,有p(n)>1,也就是n次博弈之后,一定会移到0. 结果说明,当Alice算力超过50%时,他一定可以追上主链,这是确定事件。

当q=p,即攻击者算力占50%,那么p(1)=1,p(n)=1,攻击一定会成功。也就是说,50%的算力就一定可以攻击成功,并不需要51%。

当q<p, 有 p(n)=(q/P)^n,此时q/P<1,说明如果Alice在n较小时没有追上,越往后其追上的概率越小,n趋于无穷时,p(n)趋近于0,但是永远不可能为0。

所以第二种情况概率为:

image.png

结论

总结得到Alice追上概率为:

image.png

这也就是白皮书第11章最后给出的结论公式(见下图)。一些人用过这个公式,但我没能找到完整的推导过程。希望本文解答那些对此公式同样感到费解的朋友们的一些疑惑。

image.png

中本聪白皮书原文

在得出这个公式后,让我们回归文章开头的“6个确认”和“51%攻击”问题。

简单来说,这个公式可以总结为p(win)=f(q,z), 即双花成功的概率是攻击者算力比例q和收款者等待确认区块个数z的函数。给定q和z,就可以算出成功概率,以下是Meni Rosenfeld论文中根据此函数,给出的数据和图。

图中横轴表示q取不同值,不同曲线表示z不同,纵轴表示成功概率。

image.png

如图所示:当攻击者算力占比大于等于50%时,无限时长的攻击总能成功

image.png

由以上结果,可以得出一些结论:

1、一般情形下,成功概率对z值呈指数下降,所以等待更多区块以后确认交易是保险的策略。

2、无论多大的确认数z也无法把成功概率降到0,做不到万无一失。

3、当攻击算力大于等于50%,不管多大的区块确认数也无法阻止双花成功。(关于50%攻击,请回想一下赌徒破产模型。其实,中本聪在白皮书中把情况二双花的要求退化成了“追上”。但就算我们把“追上”变成“超过”,即允许赌徒最后可以-1个,这依然改变不了什么。掌握了50%后,只要能够发动无限时长的攻击,就一定能够攻击成功。这就类似于,哪怕赌场愿意借一块钱给赌徒赌博,最后赌徒也无法避免破产的命运。)

至此,我们可以清楚明白,所谓“6个确认”是说,攻击算力在10%以下,等待6区块确认,双花成功的概率在0.1%以下。理论上讲,在任意小算力和任意大确认数下,成功概率非常小,但仍可能攻击成功。

不足

此模型有些地方并不精确。求解第二阶段概率时,把问题抽象成赌徒破产模型。诚实节点和攻击者是分别在两条链上各自挖矿竞争,假设攻击者先挖到了区块,那么此局结束,双方仍以p和q的概率开启下一局,诚实节点算新区块,攻击者继续算上一个区块。然而现实时攻击者虽然此局失败,但是他已经累积了一定工作量,他继续算出这个区块的概率比上一局算出的概率大。由此会对最终计算结果造成一定误差。

另外一点是本文没有讨论攻击者的攻击成本和收益的经济分析。

注:本文概率分析模型主要参考比特币白皮书、Meni Rosenfeld的“Analysis of hashrate-based double-spending”以及果壳的“从酒鬼失足到赌徒破产,悲剧收场为何注定”。

参考文献:

1.Satoshi Nakamoto , ”Bitcoin: A Peer-to-Peer Electronic Cash System”,2009

2.Meni Rosenfeld,“Analysis of hashrate-based double-spending”, 2012

3.pondering,“从酒鬼失足到赌徒破产,悲剧收场为何注定”,果壳,2011

4.Zhangzedtv,”通过源码学习比特币-难度目标与难度调整” 2018

5.Michael Nielsen,”比特币协议是怎样工作的”,2014

6.W. Feller, “An introduction to probability theory and its applications,”1957

7.Tiny熊, ”比特币如何达成共识-最长链的选择”

 

本文来源:碳链价值

作者:白鱼 编辑:唐晗



<<免责声明:本文仅代表作者本人观点,并不代表小牛币读之观点,小牛币读对作者观点不承担任何担保责任。>> 行情,快讯,资讯,您只需一个公众号
小牛币读公众号
长按识别二微码关注公众号
文章评论
文章栏目
全部 八爪鱼区块链 黑鳯李 数链评级 锌链接 BA社区 OK区块链商学院 金猫kinmall 链得得 比特财经专栏 乌鸦区块链 金氪资本 陀螺财经 算多多 区块链投资社区 爱必投 吴庆英 xiaoxiaochuxia 币圈一老友 九叔说币 36氪鲸准研究院 Bplus新加坡 筱静观察 童刚 币必盈 拾荒的蜘蛛侠 如何拥抱未来 BB财经 区块佣兵 PANews 牛盾 31QU 陈天宇 蓝狐笔记 阿尔法套利 沉蜇 星鉴网 哈希游讯 大侠区块链研究院 BUGX 链闻ChainNews MinerHub TokenInsight 币圈老沈 环球链 TopDapp 链小小小白 百晓生说币 可盈可乐 图灵财经 比特币复利 币学 区块链酋长 听风说币 街头区块链 区块链记者圈 博链财经 巴比特资讯 胖子区块链 币叨叨 中原区块链 DAppTalk 小诸葛 鳄鱼看趋势 救赎说币pro 王衡数链评级 TokenClub资讯 火星财经 lbnd123 DappReview 奔跑财经 三非彼得 晨辉 黑钻君 区块链狂牛 旗是风的翅膀 伟大的渺小 兔子酱 OK区块链财经 区块链游戏投资者 佛系白露 李大狗 COINBIG sealchain AvalonMiner 烦立停 智能比特 DapDap区块链 币民日记 猎云财经 王团长区块链日记 哔哔News 数字货币趋势狂人 比特吴社区 盈链数字货币 枭枭 炼金石财经 币coin K线中有杀气 币圈邦德 MocDapp001 数字货币分析大侠 Odaily星球日报 算力智库 蒋司令说区块链 IMEOS 张大侠 深链财经 标准共识 BTCC 币全 链鱼鱼 DappDiscover 陀螺财经研究院 哈希派 ONETOP评级 TokenGazer 蜂巢财经NEWS 白话区块链 班里小明 合约江湖08 数字门徒 风火轮区块链 陨石财经 币姥爷 小牛看币 鳄鱼看币 小马