作者|白魚
編輯|唐晗
白皮書第11章計算很難懂术陶？
為紀(jì)念比特幣十年，圈內(nèi)最近掀起了一股重讀比特幣白皮書的熱潮煤痕。然而梧宫，雖然很多文章都在感嘆比特幣的經(jīng)濟(jì)機(jī)制設(shè)計得如何精妙接谨，但竟然少有能把白皮書第11章的雙花攻擊成功率的計算公式講明白的。
作為一個剛?cè)肴Φ男率痔料唬覍?shí)在無法理解脓豪，如果弄不懂比特幣背后的數(shù)學(xué)機(jī)制，不能確信雙花的概率忌卤，我們又何來的對比特幣系統(tǒng)安全性的信心扫夜。當(dāng)然，如果諸位只是想要找個附屬物安一個政治口號驰徊，宣揚(yáng)一下自由主義的觀念历谍，再炒作和信仰一番，那就另當(dāng)別論了辣垒。
我也看到了很多比較模糊望侈、甚至與中本聰原意出入很大的說法。例如“比特幣交易需要6個確認(rèn)”：有人認(rèn)為比特幣一定要經(jīng)過6個確認(rèn)后勋桶，才算是交易成功脱衙；也有人認(rèn)為經(jīng)過6個區(qū)塊的確認(rèn)后，交易就不存在風(fēng)險了例驹。還有大家常常掛在嘴邊的51%攻擊：很多人認(rèn)為捐韩，攻擊的算力必須達(dá)到51%，或者必須多于50%鹃锈，才能夠攻擊成功荤胁。但其實(shí)不是這樣的。實(shí)際情況是屎债，如果你擁有40%的算力仅政，在人們采取6個確認(rèn)的情況下，無限攻擊成功的概率仍有50%盆驹。
“6個確認(rèn)”和“51%攻擊”的說法由來以久圆丹，且傳播深遠(yuǎn)。但如果你讀完中本聰?shù)脑那銜l(fā)現(xiàn)辫封，比特幣白皮書中壓根就沒有提到這兩個詞。他既沒有說交易一定需要6個確認(rèn)廉丽，也沒有說必須擁有51%的算力才能成功發(fā)動攻擊倦微。甚至在中本聰給出的簡化模型里，只需要50%的算力正压，不管人們采取多少個確認(rèn)（1000個或者10000個）欣福，無限攻擊成功的可能性為100%。嚴(yán)格意義來說蔑匣，人們應(yīng)該稱“51%攻擊”為“50%攻擊”劣欢。
但50%攻擊顯然不符合人們的直覺棕诵，也不符合人們少數(shù)服從多數(shù)的政治期望裁良。在日后布道者們的宣傳中凿将，為了讓人們能夠快速理解和接受這個概念，雙花攻擊最終被簡化成了“51%攻擊”价脾。
本文作為一篇硬核科普牧抵，將從數(shù)學(xué)概率的角度澄清人們對“6個確認(rèn)”和“51%攻擊”的一些誤解。內(nèi)容主要分為雙花攻擊流程侨把、雙花成功概率分析犀变、結(jié)論與不足。為了讀懂本文秋柄，你最好掌握一些概率論的知識获枝，主要是泊松分布（學(xué)過高數(shù)就行）；你也需要了解一下白皮書中提到的“賭徒破產(chǎn)模型”骇笔，它是我們理解“50%攻擊”的關(guān)鍵省店。當(dāng)然，如果你沒有學(xué)過這些內(nèi)容也無關(guān)緊要笨触，因為它們背后的思想都簡單易懂懦傍。尤其是“賭徒破產(chǎn)模型”，它看上去非常違背直覺芦劣，但很有趣粗俱。
雙花攻擊流程
最近鋼鐵佩奇比較火。為了讓講解過程不那么枯燥虚吟，請讓我以鋼鐵佩奇為例來講一講這無聊而又致命的雙花攻擊寸认。
引用電子貨幣領(lǐng)域經(jīng)典的Alice和Bob交易例子，來說明比特幣作為電子現(xiàn)金的三大難點(diǎn)及其解決方案串慰。Alice想以1299元購買Bob的鋼鐵佩奇废麻，Alice付款有2種方式，一是物理現(xiàn)金模庐，二是電子轉(zhuǎn)賬烛愧。第二種方式實(shí)際上傳遞的是一個轉(zhuǎn)賬消息，電子消息充當(dāng)了貨幣掂碱，其成功關(guān)鍵在于有銀行判定Alice是否有足夠的余額支付怜姿，并進(jìn)行劃扣，最終記錄交易雙方賬戶余額疼燥。
設(shè)想如果系統(tǒng)中沒有中心的銀行如何進(jìn)行支付呢沧卢？這就是比特幣想要解決的事情。
同樣醉者，Alice向Bob發(fā)送了一個電子消息“Alice給Bob轉(zhuǎn)1299元但狭∨”想要使Bob相信這筆付款，起碼要解決3個問題立磁，證明此消息確實(shí)是Alice發(fā)送的（不可偽造性）呈队、判斷Alice確實(shí)有1299元（所有權(quán)證明），知道Alice沒有同時支付給另一個人（雙花）唱歧。
利用不對稱加密算法宪摧，Alice使用私鑰簽名能夠提供其資產(chǎn)所有權(quán)證明和保證交易的不可偽造性，這是比特幣之前就已經(jīng)很成熟的技術(shù)颅崩。
但是雙花難題依舊沒有解決几于，此前的電子貨幣方案一直依賴于引入中心第三方來解決，這相當(dāng)于重造了一個中央銀行沿后，現(xiàn)實(shí)意義并不大沿彭。中本聰創(chuàng)造性地利用區(qū)塊鏈作為公共賬本和引入礦工競爭記賬解決了這個問題，這也是比特幣的偉大之處尖滚。
雙花是指喉刘，Alice給Bob轉(zhuǎn)錢的同時又給Charlie轉(zhuǎn)了相同數(shù)目的一筆錢買手機(jī)。這時候Bob和Charlie查看自己的賬本進(jìn)行驗證熔掺，發(fā)現(xiàn)Alice確實(shí)有1299元饱搏。他們無法得知Alice是否給其他人也轉(zhuǎn)賬了。于是置逻，Alice拿走佩奇和手機(jī)推沸，剩下Bob和Charlie只有一個人能得到1299元，這就是簡單情形下的雙花問題券坞。中本聰引入礦工之后鬓催，Bob收到這筆付款通過交易驗證后，并不會立馬獨(dú)自記賬然后發(fā)貨恨锚，他會廣播這筆交易宇驾，讓網(wǎng)絡(luò)上多數(shù)人幫忙驗證Alice是否只給自己轉(zhuǎn)了這筆錢。假設(shè)Charlie也廣播了這筆交易猴伶，那么最后只能有一筆交易記在公共賬本上课舍。通過分析可以知道，這種簡單雙花基本上是不可能實(shí)現(xiàn)的他挎。其他礦工沒動機(jī)幫Alice記假賬（放入Alice給Bob和Charlie的兩筆沖突交易）即使Alice競爭到了記賬機(jī)會筝尾，廣播區(qū)塊之后，也會被其他礦工驗證出兩筆沖突交易存在办桨。
以上情形是交易被Alice確認(rèn)之前的簡單雙花問題筹淫，還有一種復(fù)雜的雙花問題，Alice可以轉(zhuǎn)給自己呢撞，同時制造分叉鏈最后代替主鏈完成雙花损姜，基本攻擊流程是這樣的饰剥。
（1）在圖（a）最后一個區(qū)塊，Alice向全網(wǎng)廣播“Alice給Bob轉(zhuǎn)1299元”
（2）Alice修改自己的客戶端程序摧阅，記入一筆“Alice給Alice轉(zhuǎn)1299元”汰蓉，同時悄悄挖礦，不廣播自己的進(jìn)度逸尖，挖出圖（b）的白色鏈古沥。
（3）等到Bob看到全網(wǎng)主鏈（黑色鏈）有足夠的確認(rèn)區(qū)塊個數(shù)（通常認(rèn)為是6個瘸右，為什么娇跟？），發(fā)出鋼鐵佩奇之后太颤，如果Alice的白鏈長于黑色主鏈苞俘，他會向全網(wǎng)公布自己的進(jìn)度，從而被接受為新的主鏈龄章。
主鏈只記錄“Alice給Alice轉(zhuǎn)1299元”吃谣，從而使得“Alice給Bob轉(zhuǎn)1299元”無法記入賬本。最終雙花攻擊成功做裙，Alice拿到了鋼鐵佩奇岗憋，Bob一無所獲。當(dāng)然锚贱，Alice發(fā)起攻擊是有成本的仔戈，他為了挖出白色鏈，需要投入礦機(jī)以及電力消耗拧廊，除非收益大于成本监徘，否則理性攻擊者是不會發(fā)起攻擊的。余下全文吧碾，我們僅考慮在收款方等待z個確認(rèn)之后凰盔，占全網(wǎng)算力q%的攻擊者雙花成功的概率。也就是說倦春，不考慮攻擊的經(jīng)濟(jì)可行性户敬，僅僅分析攻擊成功的概率大小。
雙花成功概率分析
我們都學(xué)過如何求解應(yīng)用題睁本。第一部分交代了雙花問題的背景尿庐，相當(dāng)于告訴了我們“應(yīng)用題”的條件，現(xiàn)在我們需要求解這道題添履。題目是：已知Alice占有全網(wǎng)算力比例為q屁倔，誠實(shí)節(jié)點(diǎn)占全網(wǎng)算力比例為p，p+q=1暮胧，Bob等待z個區(qū)塊確認(rèn)交易后锐借，求解Alice使得自己偷偷挖的白鏈長度追上黑鏈（主鏈）的概率P（win）?
此問題還包含著以下假設(shè)：追趕時間內(nèi)问麸，系統(tǒng)難度值保持不變；攻擊者Alice和誠實(shí)節(jié)點(diǎn)的算力相對比例不變钞翔。
求解追上概率可以拆解為兩種情況來分析严卖，第一情況是在等待z個區(qū)塊確認(rèn)的時間里，這段時間攻擊者Alice挖出了k個區(qū)塊布轿，且k>z即攻擊鏈更長哮笆。這種情況下，一旦公開網(wǎng)絡(luò)上最長鏈追加了z個區(qū)塊汰扭，Bob就會認(rèn)為交易已經(jīng)確認(rèn)稠肘，可以向Alice發(fā)出鋼鐵佩奇。而Alice一旦看到貨已經(jīng)發(fā)出萝毛，他就可以公布自己的白色鏈项阴，由于白色鏈長于黑色，那么Alice記錄的“Alice給Alice轉(zhuǎn)1299元”交易記錄留在主鏈上笆包，雙花成功环揽。
另一種情況是，k<=z庵佣，記n=z-k表示攻擊鏈和誠實(shí)主鏈的差距歉胶。也就是說，在Bob確認(rèn)交易的時候巴粪，Alice的白鏈短于主鏈通今，不足以發(fā)動攻擊，他會繼續(xù)偷偷挖验毡，和主鏈競爭不斷縮小差距衡创，直到比主鏈長。
算出兩種情況下概率再求和就是攻擊成功概率了晶通。
泊松分布—求Alice挖出k個區(qū)塊的概率
以下按照中本聰?shù)陌灼乃悸穪硗茖?dǎo)璃氢，采用泊松分布假設(shè)，Meni Rosenfeld在“Analysis of hashrate-based double-spending”中采用更加精確的負(fù)二項分布狮辽，兩個結(jié)果差異很小一也。
假設(shè)誠實(shí)節(jié)點(diǎn)按預(yù)期時間均勻出塊，那么在誠實(shí)節(jié)點(diǎn)挖出Z個塊的時間內(nèi)喉脖，Alice挖出區(qū)塊的平均值是λ=z q/p?椰苟。
泊松分布的概率函數(shù)為：
P(x=k)=(λ^k ?^(-λ))/k!?，??k=0,1,2,3·····
泊松分布用來描述單位時間內(nèi)隨機(jī)事件發(fā)生的次數(shù)树叽。泊松分布的參數(shù)λ是單位時間(或單位面積)內(nèi)隨機(jī)事件的平均發(fā)生次數(shù)舆蝴。
通過泊松分布，就可以知道k=1,2,3····的概率分別是多少，比如,這段時間Alice只挖到k=1個塊的概率是
那么第一種情況發(fā)生的概率就是
這個式子表示發(fā)生k=z+1,z+2,z+3····這些事件的概率之和洁仗。
賭徒破產(chǎn)問題
如果你看到了這里层皱，恭喜。要么你就是一個腦子里還留了一點(diǎn)高等數(shù)學(xué)的人赠潦，對于讀者來說這已經(jīng)相當(dāng)不易叫胖，歡迎在后臺聯(lián)系我；要么你對嚴(yán)謹(jǐn)枯燥內(nèi)容的抗性已經(jīng)超過了絕大多數(shù)人她奥，這比前者還要難得瓮增。
我們現(xiàn)在需要對問題的另一半進(jìn)行解答。但在討論這一部分之前哩俭，你需要接受一個反直覺的例子：假使一個賭徒把自己的錢分成n份去賭場賭博绷跑，他輸贏的概率為二分之一。如果這場賭博進(jìn)行無限次携茂，賭徒一定會輸光自己身上所有的錢你踩。
這就是大名鼎鼎的“賭徒破產(chǎn)問題”诅岩。這個問題的關(guān)鍵在于假設(shè)賭場手里的錢遠(yuǎn)多于賭徒讳苦，因而不需要考慮籌碼歸零的問題；而賭徒手里的錢遠(yuǎn)少于賭場吩谦，一旦某一次賭輸鸳谜，使籌碼歸零，便必須退出游戲式廷。因此咐扭，雖然從單次賭博的概率上看上去，賭徒和賭場的游戲是平等的滑废，但由于籌碼的多少限制了賭徒和賭場游戲可以進(jìn)行的區(qū)間蝗肪，最終游戲的天平倒向了賭場。
這個問題規(guī)勸了那些賭博成癮的人們蠕趁。它說明了薛闪，就算游戲是公平的，但如果一個人執(zhí)迷賭場以此為家俺陋，最后也將賠得精光豁延。
這與攻擊者和誠實(shí)節(jié)點(diǎn)又何其之像！攻擊者只要區(qū)塊數(shù)追平后超過誠實(shí)節(jié)點(diǎn)所挖的鏈腊状，按照比特幣“最長鏈”的原則诱咏，其他算力便會轉(zhuǎn)移到節(jié)點(diǎn)數(shù)更高的新鏈上來，攻擊成功缴挖。假設(shè)誠實(shí)節(jié)點(diǎn)們挖得的鏈長度超過攻擊者z-k個袋狞，這就好比誠實(shí)節(jié)點(diǎn)作為賭徒手里有z-k個籌碼。此時，誠實(shí)節(jié)點(diǎn)與攻擊者同時進(jìn)行著一場賭博的競賽苟鸯，一旦誠實(shí)節(jié)點(diǎn)將手中的籌碼輸干凈法焰，攻擊者便能追上。（其實(shí)應(yīng)該是輸?shù)绞Ｏ?1個倔毙，但中本聰?shù)陌灼锏募僭O(shè)是輸?shù)?埃仪。其實(shí)，輸?shù)?僅僅是追平陕赃，但雙花攻擊需要超越卵蛉，因此這個假設(shè)不太嚴(yán)謹(jǐn)，讀者們見仁見智么库，可以做更深的討論傻丝。我們暫時按照白皮書里的思路走。）
理解了這個比喻诉儒，讓我們回到原來的話題∑乡郑現(xiàn)在我們要求第二種情況下追上的概率，這種情況下忱反，我們可以把問題進(jìn)行簡化泛释，近似抽象成賭徒破產(chǎn)問題。已經(jīng)知道温算，此時Alice挖出k個區(qū)塊怜校，比主鏈少n=z-k個。在既定的n個區(qū)塊差距下注竿，他們將競賽挖礦茄茁，攻擊者成功概率是q，誠實(shí)節(jié)點(diǎn)是p巩割。放在數(shù)軸上考慮裙顽，每一局競賽當(dāng)攻擊者贏，則向左一步宣谈，縮小差距為n-1愈犹，否則向右變?yōu)閚+1。問多局博弈之后蒲祈，Alice向左移到0的概率甘萧？
我們可以先考慮n=1的時候移到n=0的概率。記p(1)表示從1移到0的概率梆掸，p(2)表示從2移到0的概率扬卷，依次類推求p(n)。
顯然在1這個點(diǎn)酸钦，一局博弈之后怪得，只有兩種情況，向左到0，向右到2徒恋。然后從2移到0的概率為p(2).所以有以下方程:
p(1)=q+p?p（2）
P(1)表示從1到0的概率蚕断，也可以表示任何一點(diǎn)向左一步的概率。而從2到0入挣，一定會先到1再到0亿乳，故p(2)=p^2 (1).
代入p(2),就可以求出 p(1)=q/p?，則p(n)=(q/P)^n?
當(dāng)q>p 径筏，即?q/p>1?葛假，有p（n）>1，也就是n次博弈之后滋恬，一定會移到0. 結(jié)果說明聊训，當(dāng)Alice算力超過50%時，他一定可以追上主鏈恢氯，這是確定事件带斑。
當(dāng)q=p，即攻擊者算力占50%勋拟，那么p(1)=1勋磕，p(n)=1，攻擊一定會成功指黎。也就是說朋凉，50%的算力就一定可以攻擊成功，并不需要51%醋安。
當(dāng)q<p, 有 p(n)=(q/P)^n，此時q/P<1,說明如果Alice在n較小時沒有追上墓毒，越往后其追上的概率越小吓揪，n趨于無窮時，p(n)趨近于0所计，但是永遠(yuǎn)不可能為0柠辞。
所以第二種情況概率為：
結(jié)論
總結(jié)得到Alice追上概率為：
這也就是白皮書第11章最后給出的結(jié)論公式（見下圖）。一些人用過這個公式主胧，但我沒能找到完整的推導(dǎo)過程叭首。希望本文解答那些對此公式同樣感到費(fèi)解的朋友們的一些疑惑。
在得出這個公式后踪栋，讓我們回歸文章開頭的“6個確認(rèn)”和“51%攻擊”問題焙格。
簡單來說，這個公式可以總結(jié)為p(win)=f(q,z), 即雙花成功的概率是攻擊者算力比例q和收款者等待確認(rèn)區(qū)塊個數(shù)z的函數(shù)夷都。給定q和z,就可以算出成功概率眷唉，以下是Meni Rosenfeld論文中根據(jù)此函數(shù)，給出的數(shù)據(jù)和圖。
圖中橫軸表示q取不同值冬阳，不同曲線表示z不同蛤虐，縱軸表示成功概率。
由以上結(jié)果驳庭，可以得出一些結(jié)論：
1、一般情形下氯窍，成功概率對z值呈指數(shù)下降嚷掠，所以等待更多區(qū)塊以后確認(rèn)交易是保險的策略。
2荞驴、無論多大的確認(rèn)數(shù)z也無法把成功概率降到0不皆，做不到萬無一失。
3熊楼、當(dāng)攻擊算力大于等于50%霹娄，不管多大的區(qū)塊確認(rèn)數(shù)也無法阻止雙花成功。（關(guān)于50%攻擊鲫骗，請回想一下賭徒破產(chǎn)模型犬耻。其實(shí)，中本聰在白皮書中把情況二雙花的要求退化成了“追上”执泰。但就算我們把“追上”變成“超過”枕磁，即允許賭徒最后可以-1個，這依然改變不了什么术吝。掌握了50%后计济，只要能夠發(fā)動無限時長的攻擊，就一定能夠攻擊成功排苍。這就類似于沦寂，哪怕賭場愿意借一塊錢給賭徒賭博，最后賭徒也無法避免破產(chǎn)的命運(yùn)淘衙。）
至此传藏，我們可以清楚明白，所謂“6個確認(rèn)”是說彤守，攻擊算力在10%以下毯侦，等待6區(qū)塊確認(rèn)，雙花成功的概率在0.1%以下具垫。理論上講侈离，在任意小算力和任意大確認(rèn)數(shù)下，成功概率非常小做修，但仍可能攻擊成功霍狰。
不足
此模型有些地方并不精確抡草。求解第二階段概率時，把問題抽象成賭徒破產(chǎn)模型蔗坯。誠實(shí)節(jié)點(diǎn)和攻擊者是分別在兩條鏈上各自挖礦競爭康震，假設(shè)攻擊者先挖到了區(qū)塊，那么此局結(jié)束宾濒，雙方仍以p和q的概率開啟下一局腿短，誠實(shí)節(jié)點(diǎn)算新區(qū)塊，攻擊者繼續(xù)算上一個區(qū)塊绘梦。然而現(xiàn)實(shí)時攻擊者雖然此局失敗橘忱，但是他已經(jīng)累積了一定工作量，他繼續(xù)算出這個區(qū)塊的概率比上一局算出的概率大卸奉。由此會對最終計算結(jié)果造成一定誤差钝诚。
另外一點(diǎn)是本文沒有討論攻擊者的攻擊成本和收益的經(jīng)濟(jì)分析。
注：本文概率分析模型主要參考比特幣白皮書榄棵、Meni Rosenfeld的“Analysis of hashrate-based double-spending”以及果殼的“從酒鬼失足到賭徒破產(chǎn)凝颇，悲劇收場為何注定”。
參考文獻(xiàn)：
1.Satoshi Nakamoto , ”Bitcoin: A Peer-to-Peer Electronic Cash System”,2009
2.Meni Rosenfeld,“Analysis of hashrate-based double-spending”, 2012
3.pondering疹鳄，“從酒鬼失足到賭徒破產(chǎn)拧略，悲劇收場為何注定”,果殼,2011
4.Zhangzedtv,”通過源碼學(xué)習(xí)比特幣-難度目標(biāo)與難度調(diào)整” 2018
5.Michael Nielsen,”比特幣協(xié)議是怎樣工作的”,2014
6.W. Feller, "An introduction to probability theory and its applications,"1957
7.Tiny熊, ”比特幣如何達(dá)成共識-最長鏈的選擇”
