作者|白魚
編輯|唐晗
白皮書第11章計算很難懂？
為紀念比特幣十年，圈內(nèi)最近掀起了一股重讀比特幣白皮書的熱潮。然而，雖然很多文章都在感嘆比特幣的經(jīng)濟機制設(shè)計得如何精妙，但竟然少有能把白皮書第11章的雙花攻擊成功率的計算公式講明白的。
作為一個剛?cè)肴Φ男率?，我實在無法理解，如果弄不懂比特幣背后的數(shù)學(xué)機制，不能確信雙花的概率，我們又何來的對比特幣系統(tǒng)安全性的信心。當然，如果諸位只是想要找個附屬物安一個政治口號，宣揚一下自由主義的觀念，再炒作和信仰一番，那就另當別論了。
我也看到了很多比較模糊、甚至與中本聰原意出入很大的說法。例如“比特幣交易需要6個確認”：有人認為比特幣一定要經(jīng)過6個確認后，才算是交易成功；也有人認為經(jīng)過6個區(qū)塊的確認后，交易就不存在風(fēng)險了。還有大家常常掛在嘴邊的51%攻擊：很多人認為，攻擊的算力必須達到51%，或者必須多于50%，才能夠攻擊成功。但其實不是這樣的。實際情況是，如果你擁有40%的算力，在人們采取6個確認的情況下，無限攻擊成功的概率仍有50%。
“6個確認”和“51%攻擊”的說法由來以久，且傳播深遠。但如果你讀完中本聰?shù)脑模銜l(fā)現(xiàn)，比特幣白皮書中壓根就沒有提到這兩個詞。他既沒有說交易一定需要6個確認，也沒有說必須擁有51%的算力才能成功發(fā)動攻擊。甚至在中本聰給出的簡化模型里，只需要50%的算力，不管人們采取多少個確認（1000個或者10000個），無限攻擊成功的可能性為100%。嚴格意義來說，人們應(yīng)該稱“51%攻擊”為“50%攻擊”。
但50%攻擊顯然不符合人們的直覺，也不符合人們少數(shù)服從多數(shù)的政治期望。在日后布道者們的宣傳中，為了讓人們能夠快速理解和接受這個概念，雙花攻擊最終被簡化成了“51%攻擊”。
本文作為一篇硬核科普，將從數(shù)學(xué)概率的角度澄清人們對“6個確認”和“51%攻擊”的一些誤解。內(nèi)容主要分為雙花攻擊流程、雙花成功概率分析、結(jié)論與不足。為了讀懂本文，你最好掌握一些概率論的知識，主要是泊松分布（學(xué)過高數(shù)就行）；你也需要了解一下白皮書中提到的“賭徒破產(chǎn)模型”，它是我們理解“50%攻擊”的關(guān)鍵。當然，如果你沒有學(xué)過這些內(nèi)容也無關(guān)緊要，因為它們背后的思想都簡單易懂。尤其是“賭徒破產(chǎn)模型”，它看上去非常違背直覺，但很有趣。
雙花攻擊流程
最近鋼鐵佩奇比較火。為了讓講解過程不那么枯燥，請讓我以鋼鐵佩奇為例來講一講這無聊而又致命的雙花攻擊。
引用電子貨幣領(lǐng)域經(jīng)典的Alice和Bob交易例子，來說明比特幣作為電子現(xiàn)金的三大難點及其解決方案。Alice想以1299元購買Bob的鋼鐵佩奇，Alice付款有2種方式，一是物理現(xiàn)金，二是電子轉(zhuǎn)賬。第二種方式實際上傳遞的是一個轉(zhuǎn)賬消息，電子消息充當了貨幣，其成功關(guān)鍵在于有銀行判定Alice是否有足夠的余額支付，并進行劃扣，最終記錄交易雙方賬戶余額。
設(shè)想如果系統(tǒng)中沒有中心的銀行如何進行支付呢？這就是比特幣想要解決的事情。
同樣，Alice向Bob發(fā)送了一個電子消息“Alice給Bob轉(zhuǎn)1299元。”想要使Bob相信這筆付款，起碼要解決3個問題，證明此消息確實是Alice發(fā)送的（不可偽造性）、判斷Alice確實有1299元（所有權(quán)證明），知道Alice沒有同時支付給另一個人（雙花）。
利用不對稱加密算法，Alice使用私鑰簽名能夠提供其資產(chǎn)所有權(quán)證明和保證交易的不可偽造性，這是比特幣之前就已經(jīng)很成熟的技術(shù)。
但是雙花難題依舊沒有解決，此前的電子貨幣方案一直依賴于引入中心第三方來解決，這相當于重造了一個中央銀行，現(xiàn)實意義并不大。中本聰創(chuàng)造性地利用區(qū)塊鏈作為公共賬本和引入礦工競爭記賬解決了這個問題，這也是比特幣的偉大之處。
雙花是指，Alice給Bob轉(zhuǎn)錢的同時又給Charlie轉(zhuǎn)了相同數(shù)目的一筆錢買手機。這時候Bob和Charlie查看自己的賬本進行驗證，發(fā)現(xiàn)Alice確實有1299元。他們無法得知Alice是否給其他人也轉(zhuǎn)賬了。于是，Alice拿走佩奇和手機，剩下Bob和Charlie只有一個人能得到1299元，這就是簡單情形下的雙花問題。中本聰引入礦工之后，Bob收到這筆付款通過交易驗證后，并不會立馬獨自記賬然后發(fā)貨，他會廣播這筆交易，讓網(wǎng)絡(luò)上多數(shù)人幫忙驗證Alice是否只給自己轉(zhuǎn)了這筆錢。假設(shè)Charlie也廣播了這筆交易，那么最后只能有一筆交易記在公共賬本上。通過分析可以知道，這種簡單雙花基本上是不可能實現(xiàn)的。其他礦工沒動機幫Alice記假賬（放入Alice給Bob和Charlie的兩筆沖突交易）即使Alice競爭到了記賬機會，廣播區(qū)塊之后，也會被其他礦工驗證出兩筆沖突交易存在。
以上情形是交易被Alice確認之前的簡單雙花問題，還有一種復(fù)雜的雙花問題，Alice可以轉(zhuǎn)給自己，同時制造分叉鏈最后代替主鏈完成雙花，基本攻擊流程是這樣的。
（1）在圖（a）最后一個區(qū)塊，Alice向全網(wǎng)廣播“Alice給Bob轉(zhuǎn)1299元”
（2）Alice修改自己的客戶端程序，記入一筆“Alice給Alice轉(zhuǎn)1299元”，同時悄悄挖礦，不廣播自己的進度，挖出圖（b）的白色鏈。
（3）等到Bob看到全網(wǎng)主鏈（黑色鏈）有足夠的確認區(qū)塊個數(shù)（通常認為是6個，為什么？），發(fā)出鋼鐵佩奇之后，如果Alice的白鏈長于黑色主鏈，他會向全網(wǎng)公布自己的進度，從而被接受為新的主鏈。
主鏈只記錄“Alice給Alice轉(zhuǎn)1299元”，從而使得“Alice給Bob轉(zhuǎn)1299元”無法記入賬本。最終雙花攻擊成功，Alice拿到了鋼鐵佩奇，Bob一無所獲。當然，Alice發(fā)起攻擊是有成本的，他為了挖出白色鏈，需要投入礦機以及電力消耗，除非收益大于成本，否則理性攻擊者是不會發(fā)起攻擊的。余下全文，我們僅考慮在收款方等待z個確認之后，占全網(wǎng)算力q%的攻擊者雙花成功的概率。也就是說，不考慮攻擊的經(jīng)濟可行性，僅僅分析攻擊成功的概率大小。
雙花成功概率分析
我們都學(xué)過如何求解應(yīng)用題。第一部分交代了雙花問題的背景，相當于告訴了我們“應(yīng)用題”的條件，現(xiàn)在我們需要求解這道題。題目是：已知Alice占有全網(wǎng)算力比例為q，誠實節(jié)點占全網(wǎng)算力比例為p，p+q=1，Bob等待z個區(qū)塊確認交易后，求解Alice使得自己偷偷挖的白鏈長度追上黑鏈（主鏈）的概率P（win）?
此問題還包含著以下假設(shè)：追趕時間內(nèi)，系統(tǒng)難度值保持不變；攻擊者Alice和誠實節(jié)點的算力相對比例不變。
求解追上概率可以拆解為兩種情況來分析，第一情況是在等待z個區(qū)塊確認的時間里，這段時間攻擊者Alice挖出了k個區(qū)塊，且k>z即攻擊鏈更長。這種情況下，一旦公開網(wǎng)絡(luò)上最長鏈追加了z個區(qū)塊，Bob就會認為交易已經(jīng)確認，可以向Alice發(fā)出鋼鐵佩奇。而Alice一旦看到貨已經(jīng)發(fā)出，他就可以公布自己的白色鏈，由于白色鏈長于黑色，那么Alice記錄的“Alice給Alice轉(zhuǎn)1299元”交易記錄留在主鏈上，雙花成功。
另一種情況是，k<=z，記n=z-k表示攻擊鏈和誠實主鏈的差距。也就是說，在Bob確認交易的時候，Alice的白鏈短于主鏈，不足以發(fā)動攻擊，他會繼續(xù)偷偷挖，和主鏈競爭不斷縮小差距，直到比主鏈長。
算出兩種情況下概率再求和就是攻擊成功概率了。
泊松分布—求Alice挖出k個區(qū)塊的概率
以下按照中本聰?shù)陌灼乃悸穪硗茖?dǎo)，采用泊松分布假設(shè)，Meni Rosenfeld在“Analysis of hashrate-based double-spending”中采用更加精確的負二項分布，兩個結(jié)果差異很小。
假設(shè)誠實節(jié)點按預(yù)期時間均勻出塊，那么在誠實節(jié)點挖出Z個塊的時間內(nèi)，Alice挖出區(qū)塊的平均值是λ=z q/p?。
泊松分布的概率函數(shù)為：
P(x=k)=(λ^k ?^(-λ))/k!?，??k=0,1,2,3·····
泊松分布用來描述單位時間內(nèi)隨機事件發(fā)生的次數(shù)。泊松分布的參數(shù)λ是單位時間(或單位面積)內(nèi)隨機事件的平均發(fā)生次數(shù)。
通過泊松分布，就可以知道k=1,2,3····的概率分別是多少，比如,這段時間Alice只挖到k=1個塊的概率是
那么第一種情況發(fā)生的概率就是
這個式子表示發(fā)生k=z+1,z+2,z+3····這些事件的概率之和。
賭徒破產(chǎn)問題
如果你看到了這里，恭喜。要么你就是一個腦子里還留了一點高等數(shù)學(xué)的人，對于讀者來說這已經(jīng)相當不易，歡迎在后臺聯(lián)系我；要么你對嚴謹枯燥內(nèi)容的抗性已經(jīng)超過了絕大多數(shù)人，這比前者還要難得。
我們現(xiàn)在需要對問題的另一半進行解答。但在討論這一部分之前，你需要接受一個反直覺的例子：假使一個賭徒把自己的錢分成n份去賭場賭博，他輸贏的概率為二分之一。如果這場賭博進行無限次，賭徒一定會輸光自己身上所有的錢。
這就是大名鼎鼎的“賭徒破產(chǎn)問題”。這個問題的關(guān)鍵在于假設(shè)賭場手里的錢遠多于賭徒，因而不需要考慮籌碼歸零的問題；而賭徒手里的錢遠少于賭場，一旦某一次賭輸，使籌碼歸零，便必須退出游戲。因此，雖然從單次賭博的概率上看上去，賭徒和賭場的游戲是平等的，但由于籌碼的多少限制了賭徒和賭場游戲可以進行的區(qū)間，最終游戲的天平倒向了賭場。
這個問題規(guī)勸了那些賭博成癮的人們。它說明了，就算游戲是公平的，但如果一個人執(zhí)迷賭場以此為家，最后也將賠得精光。
這與攻擊者和誠實節(jié)點又何其之像！攻擊者只要區(qū)塊數(shù)追平后超過誠實節(jié)點所挖的鏈，按照比特幣“最長鏈”的原則，其他算力便會轉(zhuǎn)移到節(jié)點數(shù)更高的新鏈上來，攻擊成功。假設(shè)誠實節(jié)點們挖得的鏈長度超過攻擊者z-k個，這就好比誠實節(jié)點作為賭徒手里有z-k個籌碼。此時，誠實節(jié)點與攻擊者同時進行著一場賭博的競賽，一旦誠實節(jié)點將手中的籌碼輸干凈，攻擊者便能追上。（其實應(yīng)該是輸?shù)绞Ｏ?1個，但中本聰?shù)陌灼锏募僭O(shè)是輸?shù)?。其實，輸?shù)?僅僅是追平，但雙花攻擊需要超越，因此這個假設(shè)不太嚴謹，讀者們見仁見智，可以做更深的討論。我們暫時按照白皮書里的思路走。）
理解了這個比喻，讓我們回到原來的話題?，F(xiàn)在我們要求第二種情況下追上的概率，這種情況下，我們可以把問題進行簡化，近似抽象成賭徒破產(chǎn)問題。已經(jīng)知道，此時Alice挖出k個區(qū)塊，比主鏈少n=z-k個。在既定的n個區(qū)塊差距下，他們將競賽挖礦，攻擊者成功概率是q，誠實節(jié)點是p。放在數(shù)軸上考慮，每一局競賽當攻擊者贏，則向左一步，縮小差距為n-1，否則向右變?yōu)閚+1。問多局博弈之后，Alice向左移到0的概率？
我們可以先考慮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. 結(jié)果說明，當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。
所以第二種情況概率為：
結(jié)論
總結(jié)得到Alice追上概率為：
這也就是白皮書第11章最后給出的結(jié)論公式（見下圖）。一些人用過這個公式，但我沒能找到完整的推導(dǎo)過程。希望本文解答那些對此公式同樣感到費解的朋友們的一些疑惑。
在得出這個公式后，讓我們回歸文章開頭的“6個確認”和“51%攻擊”問題。
簡單來說，這個公式可以總結(jié)為p(win)=f(q,z), 即雙花成功的概率是攻擊者算力比例q和收款者等待確認區(qū)塊個數(shù)z的函數(shù)。給定q和z,就可以算出成功概率，以下是Meni Rosenfeld論文中根據(jù)此函數(shù)，給出的數(shù)據(jù)和圖。
圖中橫軸表示q取不同值，不同曲線表示z不同，縱軸表示成功概率。
由以上結(jié)果，可以得出一些結(jié)論：
1、一般情形下，成功概率對z值呈指數(shù)下降，所以等待更多區(qū)塊以后確認交易是保險的策略。
2、無論多大的確認數(shù)z也無法把成功概率降到0，做不到萬無一失。
3、當攻擊算力大于等于50%，不管多大的區(qū)塊確認數(shù)也無法阻止雙花成功。（關(guān)于50%攻擊，請回想一下賭徒破產(chǎn)模型。其實，中本聰在白皮書中把情況二雙花的要求退化成了“追上”。但就算我們把“追上”變成“超過”，即允許賭徒最后可以-1個，這依然改變不了什么。掌握了50%后，只要能夠發(fā)動無限時長的攻擊，就一定能夠攻擊成功。這就類似于，哪怕賭場愿意借一塊錢給賭徒賭博，最后賭徒也無法避免破產(chǎn)的命運。）
至此，我們可以清楚明白，所謂“6個確認”是說，攻擊算力在10%以下，等待6區(qū)塊確認，雙花成功的概率在0.1%以下。理論上講，在任意小算力和任意大確認數(shù)下，成功概率非常小，但仍可能攻擊成功。
不足
此模型有些地方并不精確。求解第二階段概率時，把問題抽象成賭徒破產(chǎn)模型。誠實節(jié)點和攻擊者是分別在兩條鏈上各自挖礦競爭，假設(shè)攻擊者先挖到了區(qū)塊，那么此局結(jié)束，雙方仍以p和q的概率開啟下一局，誠實節(jié)點算新區(qū)塊，攻擊者繼續(xù)算上一個區(qū)塊。然而現(xiàn)實時攻擊者雖然此局失敗，但是他已經(jīng)累積了一定工作量，他繼續(xù)算出這個區(qū)塊的概率比上一局算出的概率大。由此會對最終計算結(jié)果造成一定誤差。
另外一點是本文沒有討論攻擊者的攻擊成本和收益的經(jīng)濟分析。
注：本文概率分析模型主要參考比特幣白皮書、Meni Rosenfeld的“Analysis of hashrate-based double-spending”以及果殼的“從酒鬼失足到賭徒破產(chǎ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í)比特幣-難度目標與難度調(diào)整” 2018
5.Michael Nielsen,”比特幣協(xié)議是怎樣工作的”,2014
6.W. Feller, "An introduction to probability theory and its applications,"1957
7.Tiny熊, ”比特幣如何達成共識-最長鏈的選擇”
