改進型實用拜占庭容錯

改進型實用拜占庭容錯的共識機制是少數服從多數，根據信息在分散式網路中節點間互相交換後各節點列出所有得到的信息，一個節點代表一票，選擇大多數的結果作為解決辦法。PBET將容錯量控制在全部節點數的1/3，即如只要有超過2/3的正常節點，整個系統便可正常運作。

基本介紹

• 中文名：改進型實用拜占庭容錯
• 外文名：Practical Byzantine Fault Tolerance
• 縮寫：PBFT

相關介紹

1 拜占庭將軍問題
Byzantine Generals Problem/BGP
拜占庭將軍問題是指“在存在訊息丟失的不可靠信道上試圖通過訊息傳遞的方式達到一致性是不可能的”。因此在系統中存在除了訊息延遲或不可送達的故障以外的錯誤，包括訊息被篡改、節點不按照協定進行處理等，將會潛在地會對系統造成針對性的破壞。
2 授權拜占庭容錯算法
Delegated Byzantine Fault Tolerance/dBFT
dBFT，是基於持有權益比例來選出專門的記賬人（記賬節點），然後記賬人之間通過拜占庭容錯算法（即少數服從多數的投票機制）來達成共識，決定動態參與節點。dBFT可以容忍任何類型的錯誤，且專門的多個記賬人使得每一個區塊都有最終性、不會分叉。
3 聯邦拜占庭協定
Federated Byzantine Agreement/FBA
聯邦拜占庭協定的主要特性是去中心化和任意行為容錯，通過分散式的方法，達到法定人數或者節點足夠的群體能達成共識，每一個節點不需要依賴相同的參與者就能決定信任的對象來完成共識。

簡介

1 拜占庭容錯背景

面對這些風險的時候，採用什麼樣的技術可以在成本與風險中取得平衡呢？入侵容忍體系就是這項技術中的核心。入侵容忍就是在這樣的假設空間中實現它的價值：個人的公開行為在一定的機率下是可預知的，系統在一定的機率下能夠正確完成基本的功能。一定的機率並不是指全部，所以，可以允許有錯誤，因此，入侵容忍還有對糾錯理論的聯想：即利用糾錯碼可以在一個錯誤百出、但有信道容量的信道中準確無誤地傳輸數據，網路系統就這樣在錯誤中“生存”下來的，這就是我們說的入侵容忍體系，它有兩種實現方式：一是攻擊回響的入侵容忍方法，它不需要重新設計系統，可通過高效的檢測系統發現異常，利用資源配置系統調整系統資源，並對對錯誤進行修補（修補系統）；二是攻擊遮蔽的入侵容忍方法，它需要重新設計整個系統，並通過冗餘、容錯技術，門檻密碼學技術及“拜占庭容錯問題”來實現拜占庭問題更為廣泛，討論的是允許存在少數節點作惡（訊息可能被偽造）場景下的一致性達成問題。拜占庭算法討論的是最壞情況下的保障。

拜占庭將軍問題之前，就已經存在中國將軍問題：兩個將軍要通過信使來達成進攻還是撤退的約定，但信使可能迷路或被敵軍阻攔（訊息丟失或偽造），如何達成一致。根據 FLP 不可能原理，這個問題無解。

2 拜占庭問題

又叫拜占庭將軍（Byzantine Generals Problem）問題，是 Leslie Lamport 1982 年提出用來解釋一致性問題的一個虛構模型。拜占庭是古代東羅馬帝國的首都，由於地域寬廣，守衛邊境的多個將軍（系統中的多個節點）需要通過信使來傳遞訊息，達成某些一致的決定。但由於將軍中可能存在叛徒（系統中節點出錯），這些叛徒將努力向不同的將軍傳送不同的訊息，試圖會干擾一致性的達成拜占庭問題即為在此情況下，如何讓忠誠的將軍們能達成行動的一致。

對於拜占庭問題來說，假如節點總數為 N，叛變將軍數為 F，則當時，問題才有解，即 Byzantine Fault Tolerant (BFT) 算法

例如，N=3，F=1 時

提案人不是叛變者，提案人傳送一個提案出來，叛變者可以宣稱收到的是相反的命令。則對於第三個人（忠誠者）收到兩個相反的訊息，無法判斷誰是叛變者，則系統無法達到一致。

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

更常見的，當提案人不是叛變者，提案人提出提案信息 1，則對於合作者來看，系統中會有 N-F 份確定的信息 1，和 F 份不確定的信息（假設叛變者會儘量干擾一致的達成），，即情況下才能達成一致。

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

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

Leslie Lamport 證明，當叛變者不超過 1/3時，存在有效的算法，不論叛變者如何折騰，忠誠的將軍們總能達成一致的結果。如果叛變者過多，則無法保證一定能達到一致性。

多於1/3的叛變者時有沒有可能有解決方案呢？構想 f 個叛變者和 g 個忠誠者，叛變者故意使壞，可以給出錯誤的結果，也可以不回響。某個時候 f 個叛變者都不回響，則 g 個忠誠者取多數既能得到正確結果。當 f 個叛變者都給出一個惡意的提案，並且 g 個忠誠者中有 f 個離線時，剩下的 g - f 個忠誠者此時無法分別是否混入了叛變者，仍然要確保取多數能得到正確結果，因此，，即，所以系統整體規模要大於 3f。

能確保達成一致的拜占庭系統節點數至少為 4，允許出現 1 個壞的節點。

3 Byzantine Fault Tolerant 算法

面向拜占庭問題的容錯算法，解決的是網路通信可靠，但節點可能故障情況下的一致性達成

最早由 Castro 和 Liskov 在 1999 年提出的 Practical Byzantine Fault Tolerant（PBFT）是第一個得到廣泛套用的 BFT 算法。只要系統中有 2/3的節點是正常工作的，則可以保證一致性。

PBFT 算法包括三個階段來達成共識：Pre-Prepare、Prepare 和 Commit。

4 新的解決思路

拜占庭問題之所以難解，在於任何時候系統中都可能存在多個提案（提案成本為 0），並且要完成最終的一致性確認過程十分困難，容易受干擾。但是一旦確認，即為最終確認。

比特幣的區塊鏈網路在設計時提出了創新的 PoW（Proof of Work） 算法思路。一個是限制一段時間內整個網路中出現提案的個數，另外一個是放寬對最終一致性確認的需求，約定好大家都確認並沿著已知最長的鏈進行拓寬。系統的最終確認是機率意義上的存在。這樣，即便有人試圖惡意破壞，也會付出很大的經濟代價（付出超過系統一半的算力）

後來的各種 PoX 系列算法，也都是沿著這個思路進行改進，採用經濟上的懲罰來制約破壞者。