bft演算法

㈠ 共識演算法4 (BFT)

拜占庭將軍問題（Byzantine Generals Problem），由Leslie Lamport、Robert Shostak和Marshall Pease，在其同名論文中提出（1982年）。拜占庭將軍問題現在主要指分布式對等網路節點間的通信容錯問題。在分布式網路中，不同的計節點通過交換信息達成共識。但有時候，系統中的成員節點可能出錯而發送錯誤的信息，用於傳遞信息的通訊網路也可能導致信息損壞，也可能存在惡意節點或被黑客攻破的節點故意發送錯誤的信息，從而導致系統無法達成共識或者達成錯誤的共識。（參考： BFT Wikipedia ）

拜占庭將軍問題提出後，有很多的演算法被提出用於解決這個問題。這類演算法統稱拜占庭容錯演算法（BFT: Byzantine Fault Tolerance）。BFT從上世紀80年代開始被研究，目前已經是一個被研究得比較透徹的理論，具體實現都已經有現成的演算法。

BFT演算法中最典型的是PBFT（Practical BFT）。PBFT是由Miguel Castro和Barbara Liskov於1999年提出。PBFT演算法解決了之前拜占庭容錯演算法效率不高的問題，將演算法復雜度由指數級降低到多項式級，使得拜占庭容錯演算法在實際系統應用中變得可行。PBFT在保證安全性和可用性的前提下，提供了 (n-1)/3 的容錯性。（細節請參考： PBFT ）

PBFT之後，很多進一步提升性能或魯棒性的BFT演算法先後被提出，例如Zyzzyva、ABsTRACTs、Aardvark、RBFT等等。近幾年，由於區塊鏈的熱度，無數針對區塊鏈應用場景優化過的BFT演算法也不斷涌現出來。雖然目前PBFT已經不能說是最好的，或最適合區塊鏈的BFT演算法。但是PBFT已經足夠好了，而且在實際應用中已經非常成熟。

在BFT共識機制中，網路中節點的數量和身份必須是提前確定好的。BFT共識機制無法做到PoW共識機制中實現的任何人都可以隨時加入挖礦。另外，BFT演算法無法應用到大量的節點，業內普遍認為100個節點是BFT演算法的上限。所以BFT演算法無法直接用於公有鏈，BFT演算法適合的場景是私有鏈和聯盟鏈。業內大名鼎鼎的聯盟鏈Hyperledger fabric v0.6採用的是PBFT，v1.0又推出PBFT的改進版本SBFT。這里再順便提一句，在可信環境下共識演算法一般使用傳統的分布式一致演算法PAXOS或者RAFT。

公有鏈使用BFT的一個例外是NEO，NEO使用了DBFT（delegated BFT）共識機制。DBFT共識機制下投票選出7個共識節點。這些代理節點是通過靜態選出的，並完全由項目方部署。這也是NEO被外界質疑過於中心化的原因。（參考： 早期公有鏈明星項目-NEO ）

BFT演算法和公有鏈合適的結合點在於基於BFT的PoS共識演算法（BFT based PoS）。基於BFT的PoS共識演算法要點有：一，網路節點通過鎖定虛擬資產申請成為區塊鏈系統的驗證者（或礦工）。系統驗證者的數量是動態變化的。二，系統從當前驗證者中隨機選擇一個人作為區塊提案人。三，系統驗證者對區塊提案進行投票表決，投票可能要進行多輪才能達成共識。每個人的投票比重與鎖定的虛擬資產成比例。

基於BFT的PoS的典型例子是tendermint（Cosmos採用了tendermint作為共識核心）。