降低複雜度是 BFT 共識算法的最直接的優化方向,除此之外,併發優化也是重要的優化方向。

撰文:李升林,矩陣元首席架構師

拜占庭容錯問題最早由 Leslie Lamport 等學者於 1982 年在論文《The Byzantine Generals Problem》中正式提出,主要描述分佈式網絡節點通信的容錯問題。

從 20 世紀 80 年代起,提出了很多解決該問題的算法,這類算法被統稱爲 BFT 算法。實用拜占庭容錯(Practical BFT,PBFT)算法是最經典的 BFT 算法,由 Miguel Castro 和 Barbara Liskov 於 1999 年提出。PBFT 算法解決了之前 BFT 算法容錯率較低的問題,且降低了算法複雜度,使 BFT 算法可以實際應用於分佈式系統。但 PBFT 的過高的通信複雜度無疑給共識效率帶來了嚴重的影響,極大地制約了 PBFT 的可擴展性。

分佈式系統故障模型

說起拜占庭容錯(Byzantine Fault Tolerance,簡稱 BFT)共識算法,就不可避免地提到分佈式系統的網絡模型和故障模型。對於網絡模型大家都比較熟悉,就不多做介紹了,這裏重點介紹一下故障模型,下面我們使用較爲廣泛的一種分類方法。

技術簡述 BFT 共識算法特性與優化方法圖 1 分佈式系統的故障模型

技術簡述 BFT 共識算法特性與優化方法

實際可分爲 byzantine failures 和 crash failures 兩大類,大數據或雲計算中常用的 Paxos/RAFT 共識算法只能解決 crash failure,BFT 共識算法能解決 byzantine failure。所有 BFT 協議都有一個基本假設:節點總數大於 3f 時,惡意節點最大爲 f ,誠實節點可以達成一致的正確結果。

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):不管網絡狀態如何,收到足夠的響應馬上進入下一步。

BFT 共識算法的優化

複雜度優化

一般來說,隨着硬件資源的增加,分佈式系統的處理能力能得到線性或接近線性的提升。但是區塊鏈系統運行在 P2P 的網絡條件下,所有的消息包括共識都是通過 P2P 方式廣播,其通信複雜度隨着節點數的增加呈線性或指數增加,處理能力也相應下降甚至停止。另外,簽名認證的複雜度也是重要的衡量因素,因爲產生或驗證數字簽名的密碼學操作通常是共識協議中計算量最大的操作。

因此,降低複雜度是 BFT 共識算法的最直接的優化方向。

典型的兩階段方案

技術簡述 BFT 共識算法特性與優化方法圖 2 典型的兩階段共識方案

上圖是典型的兩階段 BFT 共識方案,如 Tendermint[2] 和 Casper[3] 都是這種方案。在兩階段方案中,每個區塊經過兩輪投票後才能生產下一個區塊,可保證區塊的即時確認,但是在某些異常情況下存在 Liveness 問題,需要採取以下方案避免。

  • 增加鎖定解鎖機制,簡化 View Change 複雜度,但是 View Change 需要等待固定的時間 (Δ) 收集足夠的提交證明,因而損失 Responsiveness,Tendermint[2] 和 Casper[3] 是這種方案。
  • View Change 時帶上提交證明,具備 Responsiveness,但是提高了 View Change 的複雜度, PBFT[4] 是這種方案。

Pipeline 確認

技術簡述 BFT 共識算法特性與優化方法圖 3 三階段 Pipeline 共識方案

Pipeline 方案可進一步降低複雜度,一個區塊經過一輪投票達成後即可進入下一個區塊的共識, 但是一般需要經過後續多個區塊投票達成後才能保證不可逆,TTF (Time To Finality)相對稍長。

通信機制優化

通信機制上可採用 Leader 和聚合簽名進一步降低通信複雜度和通信量。下圖爲 Hotstuff[1] 的共識算法。

技術簡述 BFT 共識算法特性與優化方法圖 4 基於 Leader 和聚合簽名的 Hotstuff 共識算法

視圖切換(View Change)優化

視圖切換一般有兩種優化方法降低複雜度:

  • 將視圖切換流程整合到正常流程,無需獨立的視圖切換流程
  • 採用鎖定解鎖機制減少提交證明,上一個 View 的提交證明無需傳遞給下一個 View

並行 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 個驗證人的確認簽名進入下一階段。
  • Decide:最終提交區塊。

業界有些區塊鏈系統在 Pre-Prapare 階段根據交易的依賴性進行並行打包區塊,有些在其他階段進行並行處理,PlatONE 雲圖聯盟鏈的 CBFT 算法在 Prepare、Pre-Commit 和 Commit 階段進行並行處理。

PlatONE 雲圖聯盟鏈的 CBFT 共識算法

PlatONE 雲圖聯盟鏈的優化

技術簡述 BFT 共識算法特性與優化方法圖 5 PlatONE 雲圖聯盟鏈的 CBFT 共識算法

PlatONE 雲圖聯盟鏈的 CBFT 算法包含多個方面的優化,在降低複雜度的同時通過並行進一步提高吞吐量。

  • 三階段 Pipeline 驗證:一個區塊經過一輪投票達成後即可進入下一個區塊的共識,經過三個區塊投票達成可最終確認。
  • 並行出塊和驗證:將出塊與確認分離,在 Prepare、Pre-Commit 和 Commit 階段進行並行處理。
  • 通信優化:採用聚合簽名減少通信量,也提供基於 Leader 的優化版本,進一步降低通信複雜度。
  • 視圖切換優化:將視圖切換流程整合到正常流程,無需獨立的視圖切換流程。

複雜度分析

下表爲各類 BFT 共識算法的複雜度分析,PlatONE 雲圖聯盟鏈的 CBFT 有兩個版本,廣播版本具有 O(N2) 的復 雜度,Leader 版本具有 O(N) 的複雜度。

技術簡述 BFT 共識算法特性與優化方法

參考文檔

[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.