拜占庭問題與算法

拜占庭問題(Byzantine Problem)又叫拜占庭將軍(Byzantine Generals Problem)問題,討論的是允許存在少數節點作惡(消息可能被偽造)場景下的如何達成共識問題。拜占庭容錯(Byzantine Fault Tolerant,BFT)討論的是容忍拜占庭錯誤的共識算法。

兩將軍問題

拜占庭問題之前,學術界就已經存在兩將軍問題的討論(《Some constraints and tradeofis in the design of network communications》,1975 年):兩個將軍要通過信使來達成進攻還是撤退的約定,但信使可能迷路或被敵軍阻攔(消息丟失或偽造),如何達成一致?根據 FLP 不可能原理,這個問題無通用解。

拜占庭問題

拜占庭問題最早由 Leslie Lamport 等學者於 1982 年在論文《The Byzantine Generals Problem》中正式提出,是用來解釋異步系統中共識問題的一個虛構模型。拜占庭是古代東羅馬帝國的首都,由於地域寬廣,守衛邊境的多個將軍(系統中的多個節點)需要通過信使來傳遞消息,達成某些一致決定。但由於將軍中可能存在叛徒(系統中節點出錯),這些叛徒將向不同的將軍發送不同的消息,試圖干擾共識的達成。這種情況十分類似於分佈式系統中多個節點達成共識的問題。

拜占庭問題即討論在此情況下,如何讓忠誠的將軍們能達成行動的一致。

問題的解決

論文中指出,對於拜占庭問題來說,假如節點總數為 N,故障節點數為 F,則當 N >= 3F + 1 時,問題才能有解,由 BFT 算法進行保證。

例如,N = 3,F = 1 時。

若提案人不是叛變者,提案人發送一個提案出來,收到的叛變者可以宣稱收到的是相反的命令。則對於第三個人(忠誠者)會收到兩個相反的消息,無法判斷誰是叛變者,則系統無法達到一致。

若提案人是叛變者,發送兩個相反的提案分別給另外兩人,另外兩人都收到兩個相反的消息,無法判斷究竟誰是叛變者,則系統無法達到一致。

更一般的,當提案人不是叛變者,提案人提出提案信息 1,則對於合作者來看,系統中會有 N - F 份確定的信息 1,和 F 份不確定的信息(可能為 0 或 1,假設叛變者會盡量干擾一致的達成),N − F > F,即 N > 2F 情況下才能達成一致。

當提案人是叛變者,會盡量發送相反的提案給 N - F 個合作者,從收到 1 的合作者看來,系統中會存在 (N - F)/2 個信息 1,以及 (N - F)/2 個信息 0;從收到 0 的合作者看來,系統中會存在 (N - F)/2 個信息 0,以及 (N - F)/2 個信息 1;

另外存在 F − 1 個不確定的信息。合作者要想達成一致,必須進一步的對所獲得的消息進行判定,詢問其他人某個被懷疑對象的消息值,並通過取多數來作為被懷疑者的信息值。這個過程可以進一步遞歸下去。

Leslie Lamport 等人在論文《Reaching agreement in the presence of faults》中證明,當叛變者不超過 1/3 時,存在有效的拜占庭容錯算法(最壞需要 F+1 輪交互)。反之,如果叛變者過多,超過 1/3,則無法保證一定能達到一致結果。

那麼,當存在多於 1/3 的叛變者時,有沒有可能存在解決方案呢?

設想 F 個叛變者和 L 個忠誠者,叛變者故意使壞,可以給出錯誤的結果,也可以不響應。某個時候 F 個叛變者都不響應,則 L 個忠誠者取多數既能得到正確結果。當 F 個叛變者都給出一個惡意的提案,並且 L 個忠誠者中有 F 個離線時,剩下的 L - F 個忠誠者此時無法分別是否混入了叛變者,仍然要確保取多數能得到正確結果,因此,L - F > F,即 L > 2F 或 N - F > 2F,所以系統整體規模 N 要大於 3F。

能確保達成共識的拜占庭系統節點數至少為 4,此時最多允許出現 1 個壞的節點。

拜占庭容錯算法

拜占庭容錯算法(Byzantine Fault Tolerant)是面向拜占庭問題的容錯算法,解決的是在網絡通信可靠,但節點可能故障和作惡情況下如何達成共識。

拜占庭容錯算法最早的討論可以追溯到 Leslie Lamport 等人 1982 年 發表的論文《The Byzantine Generals Problem》,之後出現了大量的改進工作,代表性成果包括《Optimal Asynchronous Byzantine Agreement》(1992 年)、《Fully Polynomial Byzantine Agreement for n>3t Processors in t+1 Rounds》(1998 年)等。長期以來,拜占庭問題的解決方案都存在運行過慢,或複雜度過高的問題,直到“實用拜占庭容錯算法”(Practical Byzantine Fault Tolerance,PBFT) 算法的提出。

1999 年,這一算法由 Castro 和 Liskov 於論文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。該算法基於前人工作(特別是 Paxos 相關算法,因此也被稱為 Byzantine Paxos)進行了優化,首次將拜占庭容錯算法複雜度從指數級降低到了多項式級,目前已得到廣泛應用。其可以在惡意節點不超過總數 1/3 的情況下同時保證 Safety 和 Liveness。

PBFT 算法採用密碼學相關技術(RSA 簽名算法、消息驗證編碼和摘要)確保消息傳遞過程無法被篡改和破壞。

算法整體的基本過程如下:

  • 首先,通過輪換或隨機算法選出某個節點為主節點,此後只要主節點不切換,則稱為一個視圖(View)。

  • 在某個視圖中,客戶端將請求 <REQUEST,operation,timestamp,client> 發送給主節點,主節點負責廣播請求到所有其它副本節點。

  • 所有節點處理完成請求,將處理結果 <REPLY,view,timestamp,client,id_node,response> 返回給客戶端。客戶端檢查是否收到了至少 f+1 個來自不同節點的相同結果,作為最終結果。

主節點廣播過程包括三個階段的處理:預準備(Pre-Prepare)、準備(Prepare)和提交(Commit)。預準備和準備階段確保在同一個視圖內請求發送的順序正確;準備和提交階段則確保在不同視圖之間的確認請求是保序的。

  • 預準備階段:主節點為從客戶端收到的請求分配提案編號,然後發出預準備消息 <<PRE-PREPARE,view,n,digest>,message> 給各副本節點,其中 message 是客戶端的請求消息,digest 是消息的摘要。

  • 準備階段:副本節點收到預準備消息後,檢查消息。如消息合法,則向其它節點發送準備消息 <PREPARE,view,n,digest,id>,帶上自己的 id 信息,同時接收來自其它節點的準備消息。收到準備消息的節點對消息同樣進行合法性檢查。驗證通過則把這個準備消息寫入消息日誌中。集齊至少 2f+1 個驗證過的消息才進入準備狀態。

  • 提交階段:廣播 commit 消息,告訴其它節點某個提案 n 在視圖 v 裡已經處於準備狀態。如果集齊至少 2f+1 個驗證過的 commit 消息,則說明提案通過。

具體實現上還包括視圖切換、checkpoint 等機制,讀者可自行參考論文內容,在此不再贅述。

拜占庭容錯類的算法因為要考慮最惡意的存在“搗亂”者的情況,在大規模場景下共識性能往往會受到影響。

新的解決思路

拜占庭問題之所以難解,在於任何時候系統中都可能存在多個提案(因為提案成本很低),並且在大規模場景下要完成最終確認的過程容易受干擾,難以達成共識。

2014 年,斯坦福的 Christopher Copeland 和 Hongxia Zhong 在論文《Tangaroa: a byzantine fault tolerant raft》中提出在 Raft 算法基礎上引入拜占庭容錯性,兼顧可實現性和魯棒性。該論文也啟發了 Kadena 等項目的出現,實現更好性能的拜占庭算法。

2017 年,MIT 計算機科學與人工智能實驗室(CSAIL)的 Yossi Gilad 和 Silvio Micali 等人在論文《Algorand: Scaling Byzantine Agreements for Cryptocurrencies》中針對 PBFT 算法在很多節點情況下性能不佳的問題,提出先選出少量記賬節點,然後再利用可驗證隨機函數(Verifiable Random Function,VRF)來隨機選取領導節點,避免全網直接做共識,將拜占庭算法擴展到了支持較大規模的應用場景,同時保持較好的性能(1000+ tps)。

此外,康奈爾大學的 Rafael Pass 和 Elaine Shi 在論文《The Sleepy Model of Consensus》中還探討了在動態場景(大量節點離線情況)下如何保障共識的安全性,所提出的 Sleepy Consensus 算法可以在活躍誠實節點達到一半以上時確保完成拜占庭共識。

2018 年,清華大學的 Chenxing Li 等在論文《Scaling Nakamoto Consensus to Thousands of Transactions per Second》中提出了 Conflux 共識協議。該協議在 GHOST 算法基礎上改善了安全性,面向公有區塊鏈場景下,理論上能達到 6000+ tps。

比特幣網絡在設計時使用了 PoW(Proof of Work)的概率型算法思路,從如下兩個角度解決大規模場景下的拜占庭容錯問題。

首先,限制一段時間內整個網絡中出現提案的個數(通過工作量證明來增加提案成本);其次是丟掉最終確認的約數,約定好始終沿著已知最長的鏈進行拓展。共識的最終確認是概率意義上的存在。這樣,即便有人試圖惡意破壞,也會付出相應的經濟代價(超過整體系統一半的工作量)。

後來的各種 PoX 系列算法,也都是沿著這個思路進行改進,採用經濟博弈來制約攻擊者。

Last updated