鄒傳偉:技術解析比特幣應對雙花攻擊的安全性問題


中本聰在比特幣白皮書技術部分(第 6-9 頁)討論了比特幣分散式賬本面對雙花攻擊的安全問題,核心是誠實節點和惡意節點在挖礦中的競爭。這部分內容非常重要,但中本聰的表述非常簡略,省去了關鍵論證過程。區塊鏈行業中有專家對這部分內容做了說明,但都存在一些疏漏之處。本文在前人工作的基礎上,試圖給出一個嚴謹解析。

比特幣挖礦的數學過程

比特幣挖礦的本質上通過不斷執行雜湊計算,以找出一個符合要求的 Nonce,使其前若干位等於 0。如果將 Nonce 視為一個十六進位制小數,那麼其可以視為一個在 0 和 1 之間均勻分佈的隨機變數,合格 Nonce 需小於α(如果要求 Nonce 前β位等於 0,那麼α=2-β)。α由比特幣演算法根據全網算力調整。

用Η表示全網算力,含義是每秒可執行雜湊計算的次數。用隨機變數τ表示找到合格 Nonce 的時點,τ是概率論上的停時概念。因為不同次雜湊計算的結果相互獨立,所以對任意 t>0,


因此,隨機變數τ的累積概率分佈函式等於


(1) 表示引數為-ln(1-α)Η的指數分佈。根據指數分佈的性質,找到一個合格區塊的平均時間為


用 T 表示平均出塊時間(即 10 分鐘)。那麼,存在如下關係


(2) 就是比特幣的難度係數調整機制。

誠實節點與惡意節點之間的挖礦競爭

假設全網算力 H 不變,誠實節點與惡意節點的算力分別為 Hg和 Hb,H=Hg+Hb。它們找到合格區塊的時間分別為τg和τb。根據前文的分析,和均服從指數分佈,引數分別是


誠實節點先找到合格區塊的概率是


同理,惡意節點先找到合規區塊的概率是

延伸閱讀  讀懂以太坊域間互操作性的不可能三角


(3) 和 (4) 說明,先找到合規區塊的概率與算力成正比。

惡意節點從落後追趕誠實節點的問題

假設全網算力 H、誠實節點的算力 Hg和惡意節點的算力 Hb均保持不變。假設惡意節點落後誠實節點個區塊,接下來考慮惡意節點趕上誠實節點的概率。站在惡意節點的角度,引入如下計數函式


其中,-z 表示初始時惡意節點落後誠實節點 z 個區塊。Ii(τb
(6) 的含義是,惡意節點從落後 z 個區塊出發,能超越誠實節點 1 個區塊的概率。

考慮第 1 個區塊的情況(i=1)。如果這個區塊由惡意節點生成,則惡意節點領先於誠實節點的區塊數量變為-z+1,此情形的概率為 Pr(τbτg)=p。因此,


另外,q-1=1。但僅憑 (7) 和這個邊界條件不足以求解,需要將這個問題轉換為「賭徒破產」問題(Gambler’s Ruin Problem)。

假設惡意節點在落後誠實節點 N 個區塊後放棄追趕(N 是一個很大的正整數),惡意節點在超越誠實節點 1 個區塊後贏得「最長鏈競爭」。這兩種情況都對應著「最長鏈競爭」停止,表示成「賭徒破產」問題是:


其中, τc也是概率論上的停時概念,L( τc)=-1 表示惡意節點贏得「最長鏈競爭」,L( τc)=-N 表示惡意節點退出「最長鏈競爭」。此時,(6) 等價於


(7) 仍然成立,但有兩個邊界條件:

延伸閱讀  五分鐘瞭解 Elk Finance 跨鏈兌換機制


(7) 可以等價表述為,


也就是


迭代可知,


將上述迭代結果累加起來可得,


(12)

考慮邊界條件 (10),存在兩種情況。


第一,q>p (也就是惡意節點佔優)。因為 q/p>1,所以


第二,q


(二) p=q=0.5


在上述求解過程中,N->∞的含義是惡意節點為了贏得「最長鏈競爭」可以容忍任何大的成本。這當然是一個過於理想化的假設,只考慮了惡意節點從落後追趕誠實節點在技術上的可行性。實際上,惡意節點會衡量追趕的成本和收益,在很多情況下成本超過收益,說明追趕即使在技術上可行,在經濟學上不可行。這會為比特幣分散式賬本帶來安全保障。

這就對應著比特幣白皮書第 6 頁給出的如下公式。需要說明的是,比特幣白皮書討論的是惡意節點從落後追平誠實節點的概率,而 (15) 給出的是惡意節點至少超過誠實節點 1 個區塊的概率。

分散式賬本面對雙花攻擊的安全性

這是比特幣白皮書重點討論的問題。此問題的關鍵是泊松過程與指數分佈之間的關係。如果從任意時點開始統計區塊生成數量,由此得到的計數過程就是泊松分佈:

任意兩個不重疊的時間段內區塊生成數量是互相獨立的隨機變數;在任意長度為的時間段內,區塊生成數量服從泊松分佈


換言之,在相鄰兩個區塊之間的時間間隔服從引數為-ln(1-α)H 的指數分佈時,與其對應的計數過程服從引數為-ln(1-α)H 的泊松過程。

在雙花攻擊中,假設交易發起者等待了 z 個區塊。這些區塊由誠實節點生成,對應的時間等於


假設惡意節點在這個時間段內在私下生成區塊,累計生成區塊生成數量 Z 服從泊松分佈,引數等於


這對應著比特幣白皮書第 7 頁的如下公式:


根據泊松分佈的定義,


在時 0=z+1 時,惡意節點已完成雙花攻擊。因此,惡意節點雙花成功的概率等於(只討論 q

延伸閱讀  後 Taproot 時代:探討比特幣新篇章的機遇、挑戰及演進方向


Scroll to Top