硬核丨如何改進 BFT 共識演算法?

通訊複雜度問題

PBFT是基於三階段投票即可達成共識的協議。prepare和commit階段中,都需要每個節點廣播自己的prepare或commit訊息,因此通訊複雜度是。

view change過程中,需要所有的副本節點發現主節點time out,每個副本節點會廣播view change訊息,所有副本節點對view change達成共識後,新的主節點會把這個訊息廣播出去宣佈view change。由於view change訊息是P2P廣播,且每個view change訊息中都包含達到prepared狀態的請求,因此view change的驗證複雜度是。

高達的複雜度無疑給PBFT的共識效率帶來了嚴重的影響,極大地制約了PBFT的可擴充套件性。

BFT協議的最佳化

那麼如何把的通訊複雜度降到,提高共識效率,是BFT共識協議在區塊鏈場景中面臨的挑戰。針對BFT共識效率的最佳化方法,共有以下幾類:

1. 聚合簽名

E.Kokoris-Kogias等在其論文中提出了在共識機制中使用聚合簽名的方法。論文中提到的ByzCoin[4]以數字簽名方式替代原有PBFT使用的MAC將通訊延遲從降低至,使用聚合簽名方式將通訊複雜度進一步降低至。但ByzCoin在主節點作惡或33%容錯等方面仍有侷限。

之後一些公鏈專案基於這種思想,採用EC-Schnorr多籤演算法提高PBFT過程中prepare和commit階段的訊息傳遞效率。

2. 通訊機制最佳化

PBFT使用多對多(all-to-all)的訊息模式,因此需要的通訊複雜度。

SBFT(Scale optimized PBFT)[5]提出了一個使用收集器(collector)的線性通訊模式。這種模式下不再將訊息發給每一個副本節點,而是發給收集器,然後再由收集器廣播給所有副本節點,同時透過使用門限簽名(threshold signatures)可以將訊息長度從線性降低到常數,從而總的開銷降低到。

Tendermint[6]使用gossip通訊機制,樂觀情況下可以將通訊複雜度降低到。

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流程,因此通訊複雜度也就降為。

HotStuff參考Tendermint,也將檢視切換流程和正常流程進行合併,即不再有單獨的檢視切換流程。透過引入二階段投票鎖定區塊,並採用leader節點集合BLS聚合簽名的方式,將檢視切換的通訊複雜度降低到了。

4. 鏈式BFT

傳統BFT需要對每個區塊進行兩輪共識,的通訊複雜度可以讓區塊達到prepareQC,但是必須要的通訊複雜度才能讓區塊達到commitQC。

Hotstuff將傳統BFT的兩輪的同步BFT改為三輪的鏈式BFT,沒有明確的prepare,commit共識階段,每個區塊只需要進行一輪QC,後一個區塊的prepare階段為前一個區塊的pre-commit階段,後一個區塊的pre-commit階段為前一個區塊的commit階段。每次出塊的時候都只需要的通訊複雜度,透過兩輪的通訊複雜度,達到了之前的效果。

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.IOTechnical White Paper v2.” [Online]. Available:https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读