NO IMAGE

拜占庭將軍問題的經典解決方案

最好的描述資料

http://www.8btc.com/baizhantingjiangjun
注:論文中的拜占庭將軍問題的兩個方法只是解決拜占庭問題的手段之一,等價於PBFT也是解決拜占庭問題的手段之一。

PBFT是Practical Byzantine Fault Tolerance的縮寫,意為實用拜占庭容錯演算法。該演算法是Miguel Castro (卡斯特羅)和Barbara Liskov(利斯科夫)在1999年提出來的,解決了原始拜占庭容錯演算法效率不高的問題,將演算法複雜度由指數級降低到多項式級,使得拜占庭容錯演算法在實際系統應用中變得可行。

經典方案中的1/3的容錯率

區塊鏈的解決方案比如PoW為什麼可以突破1/3這個閾值而達到1/2,主要是因為經典的解決方案都利用了投票的方式。

下面簡單證明,為什麼投票方式的閾值是1/3:

從接收端的角度,n個節點裡面可能有f個惡意節點出不迴應。
這種情況下客戶端必須要在有迴應的 n-f 個訊息中進行判斷。
但由於系統是非同步的,即這f個不迴應的訊息可能都不是惡意的節點,只是因為延遲等問題。也即在n-f個迴應中,可能還有f個訊息是惡意節點發出的。
為了能在這n-f個迴應中通過多數決得出正確的結果,必須要求 n-2f>f,即n>3f。

經典解決方案的缺陷

  1. 節點之間要相互認識
  2. 因為節點之間要相互互動,頻寬佔用達到O(n2)” role=”presentation”>O(n2)O(n2)O(n^2)的規模,這就是Hyperledger基本達到百級的節點就不能用的主要原因。

區塊鏈的解決方案(PoW)

看了PoW真的有很深的觸動,真正的創新不是繁雜的推導和證明,大道至簡。

PoW採用的方法是專制的方式,不用投票,不用兩兩互動,誰贏了這個遊戲,誰說了算,使得系統達到了一致性。

如果誠實節點佔據多於50%的算力,從概率的角度看,誠實節點總會贏得遊戲。從社會學的角度看,設計了coinbase的獎勵,所以掌握了51%的人,為了經濟利益也會去維護這個系統。