說起拜占庭容錯（Byzantine Fault Tolerance，簡稱BFT）共識演算法，就不可避免地提到分散式系統的網路模型和故障模型。對於網路模型大家都比較熟悉，就不多做介紹了，這裡重點介紹一下故障模型，下面我們使用較為廣泛的一種分類方法。
實際可分為byzantine failures和crash failures兩大類，大資料或雲端計算中常用的Paxos/RAFT共識演算法只能解決crash failure，BFT共識演算法能解決byzantine failure。所有BFT協議都有一個基本假設：節點總數大於3f時，惡意節點最大為f ，誠實節點可以達成一致的正確結果。
2. BFT共識演算法的屬性
一般來說，共識演算法需要滿足以下屬性：
正確性(Validity)：誠實節點最終達成共識的值必須是來自誠實節點提議的值。
一致性(Agreement)：所有的誠實節點都必須就相同的值達成共識。
終止性(Termination)：誠實的節點必須最終就某個值達成共識。
換個說法，實際上就是我們常說的安全性(Safety)和活性(Liveness)，其中正確性(Validity)和一致性(Agreement)決定了安全性(Safety)，而終止性(Termination)就是活性（Liveness）。
安全性（Safety）：在故障發生時，共識系統不能產生錯誤的結果。在區塊鏈的語義下，指的是不會產生雙重花費和分叉。
活性（Liveness）：系統一直能持續產生提交，在區塊鏈的語義下，指的是共識會持續進行，不會卡住。假如一個區塊鏈系統的共識卡在了某個高度，那麼新的交易是沒有迴應的，也就是不滿足liveness。
BFT共識一般是基於檢視(View)的共識協議，View表示一個共識單元，共識過程是由一個接一個的View組成。在一個View中，存在一個確定Leader來主導共識協議，View切換時需要更換Leader。按照Hotstuff[1]，檢視切換流程需要滿足兩個屬性：
線性（Linearity）：複雜度與共識節點數呈線性關係。
響應性（Responsiveness）：不管網路狀態如何，收到足夠的響應馬上進入下一步。
3. BFT共識演算法的最佳化
3.1 複雜度最佳化
一般來說，隨著硬體資源的增加，分散式系統的處理能力能得到線性或接近線性的提升。但是區塊鏈系統執行在P2P的網路條件下，所有的訊息包括共識都是透過P2P方式廣播，其通訊複雜度隨著節點數的增加呈線性或指數增加，處理能力也相應下降甚至停止。另外，簽名認證的複雜度也是重要的衡量因素，因為產生或驗證數字簽名的密碼學操作通常是共識協議中計算量最大的操作。
因此，降低複雜度是BFT共識演算法的最直接的最佳化方向。
3.1.1 典型的兩階段方案
上圖是典型的兩階段BFT共識方案，如Tendermint[2]和Casper[3]都是這種方案。在兩階段方案中，每個區塊經過兩輪投票後才能生產下一個區塊，可保證區塊的即時確認，但是在某些異常情況下存在Liveness問題，需要採取以下方案避免。
· 增加鎖定解鎖機制，簡化View Change複雜度，但是View Change需要等待固定的時間(Δ)收集足夠的提交證明，因而損失Responsiveness，Tendermint[2]和Casper[3]是這種方案。
· View Change時帶上提交證明，具備Responsiveness，但是提高了View Change的複雜度，PBFT[4]是這種方案。
3.1.2 Pipeline確認
Pipeline方案可進一步降低複雜度，一個區塊經過一輪投票達成後即可進入下一個區塊的共識，但是一般需要經過後續多個區塊投票達成後才能保證不可逆，TTF（Time To Finality）相對稍長。
3.1.3 通訊機制最佳化
通訊機制上可採用Leader和聚合簽名進一步降低通訊複雜度和通訊量。下圖為Hotstuff[1]的共識演算法。
3.1.4 檢視切換（View Change）最佳化
檢視切換一般有兩種最佳化方法降低複雜度：
· 將檢視切換流程整合到正常流程，無需獨立的檢視切換流
· 採用鎖定解鎖機制減少提交證明，上一個View的提交證明無需傳遞給下一個View
3.2 並行BFT（Concurrent BFT，簡稱CBFT）
典型的BFT演算法要求交易按順序執行，即使經過複雜度最佳化，吞吐量仍然還會受到較大的限制。因此BFT共識演算法的併發最佳化也是非常重要的方向。
CBFT在學術上代表一類共識演算法，也一直是共識演算法的重點研究方向，之前也已經有很多的研究成果。Kotla和Dahlin[5]透過並行化執行獨立的交易來提高吞吐量，他們設計了一些規則用以確定一個交易是否依賴於其他交易。Distler and Kapitza[6] 進一步擴充套件了Kotla和Dahlin的工作，引入了一種只在選定的副本子集上執行交易的方案。這個方案假設每個交易訪問的狀態變數是已知的，狀態物件分佈和物件訪問是統一的。2012年，Honglei Zhang and Wenbing Zhao[7]提出一種CBFT演算法，使用軟體事務性記憶體動態地檢測併發操作的依賴性。
大部分BFT類共識都可算作PBFT的變種，因此都可抽象為四個階段：
· Prepare：提議人生產區塊並廣播到整個區塊鏈網路。
· Pre-Commit：進行第一輪投票，收到N-f個驗證人的確認簽名進入下一階段。
· Commit：進行第二輪投票，收到N-f個驗證人的確認簽名進入下一階段。
· 最終提交區塊
業界有些區塊鏈系統在Prepare階段根據交易的依賴性進行並行打包區塊。有些區塊鏈系統在Prepare、Pre-Commit、Commit等階段不需要等前面的區塊完成確認，並行生產或驗證後續區塊，PlatONE雲圖聯盟鏈的CBFT演算法就是如此。
4. PlatONE雲圖聯盟鏈的CBFT共識演算法
4.1 PlatONE雲圖聯盟鏈的最佳化
PlatONE雲圖聯盟鏈的CBFT演算法包含多個方面的最佳化，在降低複雜度的同時透過並行進一步提高吞吐量。
· 三階段Pipeline驗證：一個區塊經過一輪投票達成後即可進入下一個區塊的共識，經過三個區塊投票達成可最終確認。
· 並行出塊和驗證：將出塊與確認分離，在Prepare、Pre-Commit和Commit階段進行並行處理。
· 通訊最佳化：採用聚合簽名減少通訊量，也提供基於Leader的最佳化版本，進一步降低通訊複雜度。
· 檢視切換最佳化：將檢視切換流程整合到正常流程，無需獨立的檢視切換流程。
4.2 複雜度分析
下表為各類BFT共識演算法的複雜度分析，PlatONE雲圖聯盟鏈的CBFT有兩個版本，廣播版本具有的複雜度，Leader版本具有O(N)的複雜度。
參考文件
[1] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019. http://arxiv.org/abs/1803.05069v4
[2] Ethan Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains. PhD thesis, 2016.
[3] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. CoRR, abs/1710.09437, 2017.
[4] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999, pages 173–186, 1999.
[5] R. Kotlan and M. Dahlin, “High throughput byzantine fault tolerance,” Proceedings of International Conference on Dependable Systems and Networks, 2004.
[6] T. Distler and R. Kapitza, “Increasing performance in byzantine fault-tolerant systems with on- demand replica consistency,” Proceedings of the sixth Eurosys conference, 2011.
[7] Honglei Zhang and Wenbing Zhao, "Concurrent Byzantine Fault Tolerance for Software- Transactional-Memory Based Applications", International Journal of Future Computer and Communication, Vol. 1, No. 1, June 2012.
[8] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Consensus in the presence of partial synchrony. J.ACM, 35(2):288–323, 1988.
[9] Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: a scalable decentralized trust infrastructure for blockchains. CoRR, abs/1804.01626, 2018.
