通訊複雜度問題PBFT是基於三階段投票即可達成共識的協議。prepare和commit階段中，都需要每個節點廣播自己的prepare或commit訊息，因此通訊複雜度是O(n²）。view change過程中，需要所有的副本節點發現主節點time out，每個副本節點會廣播view change訊息，所有副本節點對view change達成共識後，新的主節點會把這個訊息廣播出去宣佈view change。由於view change訊息是P2P廣播，且每個view change訊息中都包含達到prepared狀態的請求，因此view change的驗證複雜度是O(n³）。高達O(n³）的複雜度無疑給PBFT的共識效率帶來了嚴重的影響，極大地制約了PBFT的可擴充套件性。BFT協議的最佳化那麼如何把O(n³）的通訊複雜度降到O(n），提高共識效率，是BFT共識協議在區塊鏈場景中面臨的挑戰。針對BFT共識效率的最佳化方法，共有以下幾類：

1. 聚合簽名E.Kokoris-Kogias等在其論文中提出了在共識機制中使用聚合簽名的方法。論文中提到的ByzCoin[4]以數字簽名方式替代原有PBFT使用的MAC將通訊延遲從O(n²）降低至O(n），使用聚合簽名方式將通訊複雜度進一步降低至O(log n）。但ByzCoin在主節點作惡或33%容錯等方面仍有侷限。之後一些公鏈專案基於這種思想，採用EC-Schnorr多籤演算法提高PBFT過程中prepare和commit階段的訊息傳遞效率。2. 通訊機制最佳化PBFT使用多對多(all-to-all)的訊息模式，因此需要O(n）的通訊複雜度。SBFT(Scale optimized PBFT)[5]提出了一個使用收集器(collector)的線性通訊模式。這種模式下不再將訊息發給每一個副本節點，而是發給收集器，然後再由收集器廣播給所有副本節點，同時透過使用門限簽名(threshold signatures)可以將訊息長度從線性降低到常數，從而總的開銷降低到O(n）。

Tendermint[6]使用gossip通訊機制，樂觀情況下可以將通訊複雜度降低到O(n log n）。3. view-change流程最佳化所有的BFT協議都透過view-change來更換主節點。PBFT，SBFT等協議具有獨立的view-change流程，當主節點出問題後才觸發。而在Tendermint、HostStuff[7]等協議中沒有顯示的view-change流程，view-change流程合入正常流程中，因此提高了view-change的效率，將view-change的通訊複雜度降低。Tendermint將roundchange(和viewchange類似)合入正常流程中，因此roundchange和正常的區塊訊息commit流程一樣，不像PBFT一樣有單獨的viewchange流程，因此通訊複雜度也就降為O(n²）。HotStuff參考Tendermint，也將檢視切換流程和正常流程進行合併，即不再有單獨的檢視切換流程。透過引入二階段投票鎖定區塊，並採用leader節點集合BLS聚合簽名的方式，將檢視切換的通訊複雜度降低到了O(n）。4. 鏈式BFT

傳統BFT需要對每個區塊進行兩輪共識，O(n）的通訊複雜度可以讓區塊達到prepareQC，但是必須要O(n²）的通訊複雜度才能讓區塊達到commitQC。Hotstuff將傳統BFT的兩輪的同步BFT改為三輪的鏈式BFT，沒有明確的prepare，commit共識階段，每個區塊只需要進行一輪QC，後一個區塊的prepare階段為前一個區塊的pre-commit階段，後一個區塊的pre-commit階段為前一個區塊的commit階段。每次出塊的時候都只需要O(n）的通訊複雜度，透過兩輪的O(n）通訊複雜度，達到了之前O(n²）的效果。5. 流水線（Pipelining）和並行處理（Concurrency）PBFT、Tendermint等協議具有即時確定(Instant Finality)的特性，幾乎不可能出現分叉。在PBFT中，每個區塊被確認後才能出下一個區塊，Tendermint還提出區塊鎖定的概念，進一步確保了區塊的即時確定性，即在某個round階段，節點對區塊訊息投了pre-commit票，則在下一個round中，該節點也只能給該區塊訊息投pre-commit票，除非收到新proposer的針對某個區塊訊息的解鎖證明。這類BFT共識協議本質上是一個同步系統，將區塊的生產和確認緊密耦合，一個區塊確認後才能生產下一個區塊，需要在塊與塊間等待最大的可能網路延遲，共識效率受到很大的限制。HotStuff的Pipelining方法將區塊的生產和確認分離，每個區塊的最終確認需要後兩個區塊達到QC，也就意味著上一個區塊沒有完全確認（需要滿足Three-Chain）的情況下可以生產下一個區塊。這種方式實際上還是一個半同步系統，每個區塊的產生還是需要等上一個區塊達到QC。

EOS[8]的BFT-DPoS共識協議可認為是一種完全並行的Pipelining方案：每個區塊生產後立即全網廣播，區塊生產者一邊等待0.5秒生產下一個區塊，一邊接收其他見證人對於上一個區塊的確認結果，使用BFT協議達成共識，新區塊的生產和舊區塊確認的接收同時進行，這極大地最佳化了出塊效率。（未完待續）參考[4] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.[5] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu，“a Scalable and Decentralized Trust Infrastructure”，2018.[6] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.

[7] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019.[8] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.