共識機制 – BFT 拜占庭容錯 Byzantine Fault Tolerance

BFT 拜占庭容錯 Byzantine Fault Tolerance 的出現是為了解決節點故障時,可能造成對分布式帳本系統的危害。

區塊鏈是一個分布式的帳本系統,所有的網路參與者都以節點的方式連接,所有的訊息都透過廣播形式來做傳達。點對點網路中存在著兩種節點:進行轉帳交易的普通節點與負責管理全網路帳本的記帳節點。

我們假設在區塊鏈網路中,傳輸的訊息有可能會被丟失、重複發送、損壞、延遲與亂序,且此區塊鏈網路中的節點可以隨意的參與或退出網路、偽造與延遲訊息、停止工作,還可能發生各種突發不可抗力的故障等等。這些就是著名的拜占庭將軍問題。

 

拜占庭將軍問題 The Byzantine Generals Problem

 

The Byzantine Generals Problem

拜占庭將軍問題為 Leslie Lamport 於 1982 年所提出:

拜占庭帝國的 11 位將軍出兵去打仗,但這 11 位將軍散落在不同的位置,若要達成一起進攻或一起撤退的共識,唯一的方式就是透過傳令來投票:每位將軍都將自己的決策紀錄複製 11 份,傳令至其餘 10 位將軍,並給自己留 1 份。最後取多數票來決定要繼續出兵征戰還是回守。

但若這 11 位將軍都非誠實將軍呢?假使其中有 2 位間諜廣播的訊息為撤退,其餘 9 位忠誠的將軍有 5 位判斷進攻,而有 4 位判斷撤退,如此最後的共識結果就會是全軍撤退。此結果狀態是相對可以接受的,畢竟全部 11 位將軍的行動仍然保持全部撤退一至性。

若上述的 2 位間諜,對於 5 位投進攻的將軍也表示他們投進攻,卻對另外 4 位投撤退的將軍表示他們投撤退,這樣所有將軍會產生分歧的行動,結果就糟了。

這種狀態不一致,還感知不到的危險,即為廣義的拜占庭將軍問題。

 

實用拜占庭容錯 Practical Byzantine Fault Tolerance

為了解決拜占庭將軍問題,Miguel Castro 和 Barbara Liskov 在1999 年提出了 PBFT 實用拜占庭容錯演算法:「只要間諜節點不超過 1/3,其餘的誠實節點依然可以透過投票達成共識並執行出行動一致性的結果。」

PBFT 演算法的核心理論是 n >= 3f +1

n 為系統裡的總節點數量,f 為系統裡允許出現的非誠實節點數量。意思為若系統裡有 10 個惡意節點,只要系統裡總共有 31 個以上的節點即能繼續正常運作達成共識。也即是系統擁有不超過 (n-1) / 3 的容錯率。

 

拜占庭容錯現實應用

拜占庭容錯在現實生活中除了區塊鏈項目外的應用不少,只要一個大系統需要大量的感應偵測器做系統偵測回報,為了避免感應偵測器故障都需要拜占庭容錯,譬如說飛機起降控制系統,甚至是 SpaceX 的工程師 Robert Rose 在 2013 的 Embedded Linux Conference 也宣稱將採用容錯系統。