具有監督機制的高效拜占庭容錯算法

王日宏，邢聰穎，徐泉清，袁杉杉

1.青島理工大學 信息與控制工程學院，山東 青島266520

2.螞蟻金服，杭州310012

隨著比特幣[1]的興起，區塊鏈技術也逐漸引起各界人士的興趣。區塊鏈綜合了密碼學、分布式等原理，具有去中心化、可追溯、不可篡改等特性[2]。共識機制作為區塊鏈技術不可或缺的環節，決定著區塊鏈系統的安全性。全節點的交互不需要提前信任其他節點，當某節點提出區塊數據后，各節點通過既定的共識機制共同認證和操作數據，通過認證的區塊將被加入到區塊鏈中。因此，共識機制在區塊鏈領域占據至關重要的位置。

根據應用場景及用戶需求不同，區塊鏈分為公有鏈、私有鏈以及聯盟鏈三種。私有鏈的網絡系統歸屬于特定的組織或機構，數據受限于這些弱中心化機構；公有鏈對中心化要求最高，允許節點參加鏈上數據的讀寫，并能夠自由進出網絡，其典型共識算法有工作量證明（Proof of Work，PoW）、權益證明（Proof of Stake，PoS）[3]以及授權股份證明（Delegated Proof of Stake，DPoS）[4]等。

聯盟鏈中的節點是事先確定的，并且節點數量較為固定，節點信用度更高。聯盟鏈共識算法分為非拜占庭容錯共識算法和拜占庭容錯算法。前者主要應用于系統存在故障，但是不存在惡意節點的場景，典型共識算法有Paxos[5]、Raft[6]等；后者應用于偽造信息、惡意響應的場景，在此種情境下，消息可能會被丟失、延遲、重放以及偽造等，典型共識算法有PBFT[7]、HotStuff BFT[8]等。即便是在信任度極高的聯盟鏈中，理論上并不能排除惡意節點或網絡環境導致的惡劣行為，況且現有的共識機制大都建立在特定理論假設情況下，例如PBFT共識算法適用于部分同步模式，其在異步模型下仍然面臨系統不協調情形[9]。雖然PBFT算法日趨成熟，但是算法仍然對網絡帶寬要求較高，帶寬隨節點數量的增加呈多項式級增長，本文就PBFT在算法效率和異步網絡環境中的實施問題做出研究，提出了一種高效監督拜占庭容錯算法ES-BFT。

本文主要做出了以下貢獻：

（1）ES-BFT算法將網絡中的節點劃分為節點簇，并設置信譽值機制，通過信譽值從節點簇中劃分出共識節點與監督節點；共識節點執行PBFT算法。節點的選取機制降低了網絡運行的成本，減小了網絡帶寬的開銷，提升了算法的效率。

（2）引入監督機制，算法在PBFT的確認階段向監督節點發送共識節點狀態，及時制止系統不協調情況的發生。當滿足系統不協調條件時，監督節點觸發共識節點的狀態調整。

（3）評估了ES-BFT算法，結果表明，它在效率（延遲和吞吐量）以及安全性上優于PBFT算法。

1 準備知識

1.1 區塊鏈基本架構

區塊鏈是實現了數據公開、透明以及可追溯的架構設計方法，其系統架構[10]分為以下五層：數據層、網絡層、共識層、合約層、應用層，如圖1所示。

圖1 區塊鏈的層級架構Fig.1 Hierarchical structure of blockchain

各層分別支持不同的核心功能，層級之間合作支撐，實現去中心化。數據層主要描述了區塊鏈的底層數據結構；網絡層通過P2P網絡實現節點間的信息傳播及驗證等；共識層包含各類共識算法及激勵機制，激勵機制負責制定相關獎勵措施，主要用于公有鏈，在聯盟鏈中作用并不明顯；合約層編程規定區塊鏈的交易方式、流程細節等；應用層涵蓋各類區塊鏈應用。本文主要對網絡層和共識層進行研究。

1.2 主流共識算法

區塊鏈共識算法不斷創新，經典的PBFT算法雖然帶來了多項式級的算法突破，但仍然受到網絡模型、算法復雜度、傳播成本等的限制，因此專業人士在算法復雜度、容錯能力以及網絡模型方面做出了改進：

針對算法復雜度問題，MinBFT[11]通過可信執行環境，將PBFT的三階段通信降為兩階段通信；SBFT[12]使用收集器降低通信量，同時使用門限簽名降低收集器消息規模和驗證簽名總的開銷，將客戶端通信量由O(n)降到O(1)。

針對容錯能力問題，可信執行環境的實施將部分算法（例如MinBFT、A2M[13]）的容錯能力提升為2f+1。

針對網絡模型問題，（1）部分共識算法以優化節點的選取為突破口，例如，BBFT[14]、BFT-DPOS[15]及DBFT[16]，此類共識算法通過讓部分節點參與共識，提高共識效率；LgTTBFT[17]共識算法提出LgTree節點路由算法，實現了高效的查找效率；（2）部分共識以網絡模型為突破口，Paxos、Hot-Stuff以及SBFT算法假設部分同步模式；OBFT[18]算法通過超時時間切換同步和部分同步網絡中的拜占庭容錯；MinBFT、HoneyBadger[19]等算法屬于異步共識算法；Wang從GST（Global Stabilization Time）到來之前的視角分析了PBFT算法的缺陷，PBFT算法可能面臨系統不協調的問題，在部分同步網絡下并不適用于公鏈或聯盟鏈。本文主要在PBFT網絡節點選取和網絡模型問題上做出研究。

1.3 PBFT算法

PBFT算法建立在假設部分同步模式下的拜占庭容錯算法，即保證異步模式下的安全性（Safety）和同步模式下的活性（Liveness）。存在一個GST，在GST之后網絡變為同步網絡。

PBFT是一種狀態機副本復制算法，所有副本在視圖v的輪轉過程中運作，主節點由p=vmod ||R得出，其中v為視圖編號，R為副本節點數，p為主節點編號。同時通過超時機制檢測主節點狀態，當主節點出現問題，從節點觸發視圖切換機制。算法流程可以分為以下幾步：

（1）客戶端向主節點發送請求。

（2）主節點接收客戶端發來的請求，按順序對請求進行排序，并廣播給從節點。

（3）所有副本節點通過準備和確認階段兩兩進行交互。

（4）副本執行請求并將結果返回給客戶端。

（5）假設最大拜占庭節點數為f，因此客戶端需要等待f+1個不同節點返回的相同結果，才能達成共識。

算法設置View Change協議來解決主節點作惡或宕機的情況，主要通過以下兩種方式：（1）副本節點通過檢查主節點分配的序號合法性判斷主節點狀態，當序號不合法時，發起View Change協議；（2）客戶端設置超時機制檢測主節點掉線或作惡的問題，如果超時，向所有副本節點廣播請求消息，副本節點發起View Change協議。

2 ES-BFT算法設計

2.1 算法介紹

由于無法預知PBFT算法的GST到來時間，因此在GST之前，消息傳播不可靠，存在丟失（DoS攻擊）、被排序等風險。ES-BFT算法旨在解決PBFT算法的系統不協調問題。具體分析了ES-BFT算法的設計內容，一是節點的選取，二是共識與監督的過程。

2.1.1 節點的選取

（1）節點劃分

眾所周知，DPoS共識機制是一種基于投票選舉的共識機制，投票者根據其持有的代幣量進行投票，選出101個節點輪流執行區塊鏈的記賬和上鏈等。本文將網絡中的節點隨機劃分為多個節點簇，借鑒DPOS的算法思想，對節點簇中信譽值級別為A的節點進行選舉，選舉出的N個節點運行PBFT共識，剩余信譽值為A、B類的節點作為監督節點，監督共識過程。共識節點的選取如圖2所示。

圖2 共識節點的選取Fig.2 Selection of consensus nodes

（2）信譽值等級劃分

理想情況下所有節點都能及時完成共識過程中的任務，但是在實際的網絡傳輸中，部分節點可能會出現宕機、不發或錯發消息等問題，因此在共識過程引入節點計分制和懲罰制。共識過程根據節點行為產生信譽值計分，成功完成共識或監督的節點加1分，共識過程中存在惡意或不作為行為的節點減5分，同時扣除一定份額的賬戶資金。懲罰機制的介入使節點作惡時不得不考慮成本問題，這在一定程度上提升了網絡的安全性。

系統根據信譽值將節點等級劃分A、B、C三種，其中各級別的節點具有的權限如表1所示。

表1 信譽值等級Table 1 Reputation rating

A類節點均可擔任共識、監督以及選舉節點三個角色。B類節點信譽值適中，可用于選舉共識節點、監督共識過程。C類節點信譽值較低，只可參與投票給A類節點。

2.1.2 共識與監督過程

（1）系統不協調狀態

在GST之前，消息傳播不可靠，PBFT共識算法可能面臨系統不協調的風險。為方便理解，本文闡述了一種攻擊方法，假定系統存在1、2、3、4四個節點，其中作惡的主節點編號為1。攻擊過程如圖3所示。

圖3 攻擊過程Fig.3 Attack process

預準備階段：主節點1廣播PRE-PREPARE消息給節點1、2、3，但是不向4發送消息。

確認階段：主節點1向3發送COMMIT消息，但是不向節點2、4發送。

實施以上攻擊之后，節點3正常進行任務請求，并將結果返回給客戶端，但是節點2、4最多收到兩個COMMIT消息，因此節點1、2、4將不會執行此任務。客戶端接收不到足夠數量的回復，系統將啟動View Change過程，但是由于誠實節點2、3、4內部狀態不一致，系統將處于不協調狀態。

（2）算法流程

ES-BFT算法分兩個過程，即共識過程和監督過程，監督過程與共識過程同時進行。共識進行過程中，監督節點負責檢測系統不協調狀態，當系統出現不協調狀態導致共識無法完成時，監督節點發送清除狀態信息，系統進入準備階段重新共識。算法基本流程如圖4所示。

圖4 共識流程圖Fig.4 Consensus flow chart

（3）算法細節

首先，算法選取N≥3f+1個A級信譽值節點為共識節點，其中f為拜占庭節點數，選取除共識節點外的剩余A、B級節點為監督節點，這里將監督節點數量設置為M。其次，完成共識過程和監督過程的搭建。共識開始時，客戶端要向共識節點和監督節點發送請求消息。其中，監督節點接收客戶端消息是為了在清除狀態階段轉發客戶端消息，客戶端消息的轉發避免了節點與客戶端再次交互，提高消息傳播的效率。最后，在共識的回復階段，節點除了要向其他節點發送COMMIT消息以外，還要向監督節點發送其在本輪共識收到的PREPARE和COMMIT消息集合。監督節點對比各節點狀態，滿足系統不協調條件時，向共識節點廣播清除狀態信息，共識節點計數清除狀態信息的數量，如果超過2M/3，那么以當前視圖及請求序號開始重新共識。這里的2M/3是根據PBFT共識準備階段及確認階段消息數2f+1推論得出。共識過程各消息格式表示如下：

ES-BFT算法根據p=vmod ||R選取當前輪次主節點，其中v表示當前視圖編號，R為副本節點個數，p表示主節點編號。客戶端向共識主節點和監督節點廣播消息，其中o表示請求的操作，t表示時間戳，c表示客戶端，REQUEST包含消息內容m和消息摘要d。

預準備階段：主節點在收到客戶端的請求消息后，首先驗證客戶端請求消息簽名是否正確，如果驗證成功，主節點需要為請求消息分配序號，然后廣播一條<,m>消息給其他從節點，其中v表示視圖編號，n表示消息序號，d表示消息摘要，m為消息內容。主節點廣播預準備消息內容給從節點。

準備階段：從節點收到主節點的PRE-PR EPARE消息之后對消息內容進行校驗，校驗通過，從節點向包括主節點在內的其他節點廣播消息，其中i是當前節點編號。副本在相應的日志中記錄PR E-PREPARE和PREPARE消息，用于在View Change過程恢復未完成的請求。

小麥從開花到成熟，進入生育后期，一般從5月上旬到6月中旬，約30d。在這個時期主要工作是養根護葉，延長上部葉片的綠色時間，防止早衰或貪青，保花增粒、促進灌漿。

確認階段：主、從節點分別對接收到的PR EPARE消息進行校驗。當節點i收到2f+1條校驗通過的PR EPARE消息后，向包括主節點在內的其他節點發送消息。節點將COMMIT消息記錄到日志中，用于View Change過程恢復未完成的請求。

回復與監督階段：首先進行校驗，如果節點接收到2f+1條來自不同節點（包括自己）的COMMIT消息，則進入回復階段。回復階段主要進行以下兩部分內容：

節點發送給客戶端，r為請求操作結果。當客戶端收到f+1個由不同節點發來的相同的REPLY消息，共識達成并記錄。當檢測到節點不能正常完成共識時，客戶端考慮是否重新發送消息。

節點在向客戶端回復的同時向監督節點發送消息，其中，Pi表示節點i收到的PREPARE消息集合，Ci為節點i收到的COMMIT消息集合。Pi、Ci集合決定了監督過程的進行與否。當集合中節點狀態呈現兩種相同狀態時，系統處于不協調狀態，監督節點轉發清除狀態信息。

當S TATE消息集合中節點呈現兩種相同狀態時，監督節點對節點進行計數，如果計數值為2f+1，則向共識節點轉發清除狀態信息，清除狀態信息格式為，其中m為消息內容，v為當前視圖，n為當前消息序列號。CLEARSTATE消息中包含的消息內容能有效降低節點與客戶端的交互次數。當共識節點接收到超過2M/3條CLEAR STATE消息，各節點進入準備階段重新共識。

總的來說，一般情況下，View Change協議完全有能力解決共識失敗的問題，但是無法在系統不協調情況下做出解決。監督機制的設立有效解決了GST到達之前的系統不協調問題。因此，對于一般狀態，共識節點觸發View Change協議正常處理，監督節點不做任何處理；而對于不協調狀態，需要監督節點輔助進行共識。

2.2 算法分析

在PBFT算法中，隨著網絡中共識節點數量的增加，網絡對于帶寬的需求將以多項式級別增長，同時，網絡節點的動態增刪將導致網絡的多次初始化。如果要求所有加入網絡的節點參與共識，不論是網絡帶寬的需求還是動態性都將受到限制。ES-BFT算法使用DPoS算法選舉部分A類節點為共識節點，減少了網絡中參與共識的節點數量，提升了共識網絡的穩定性，有效降低了網絡對于帶寬的需求。共識節點需要有一定的網絡投票以及信譽值，因此共識節點出現拜占庭錯誤的幾率會降低，從而在一定程度上保證了共識的安全性。

監督機制的設立能有效保證共識的安全性和活性，安全性要求所有誠實節點會提交一致的共識結果，活性要求節點在一定的時間范圍內達成共識。PBFT算法在安全性問題上已做出解決方案，這里不做分析。系統不協調狀態將導致共識和視圖更換階段難以進行，監督機制的設立恰巧避免了系統出現不協調的狀態，因此能夠保證算法的活性。

2.3 算法評估結果

本節中，選擇通過go語言實現PBFT算法，并在PBFT算法基礎上作了改進，得到ES-BFT算法；為控制變量，實驗建立在相同網絡環境中，不考慮節點會執行其他服務的情況下，在本地開啟多節點模擬了ES-BFT算法、PBFT算法的共識過程；實驗過程中記錄數據吞吐量、共識時延等數據，最后通過對實驗數據取平均值得出最終實驗結果。實驗表明，無論在吞吐量還是時延上，ESBFT都表現出優異的性能，同時在系統不協調情況下，ES-BFT表現出不錯的交易時延。測試環境配置如表2。

表2 環境配置Table 2 Environment configuration

2.3.1 數據吞吐量測試

數據吞吐量表現為單位時間內打包的交易數，是反映共識算法性能的關鍵指標。本次實驗首先認證在固定的網絡環境中，監督節點的數量對數據吞吐量的影響。測試過程中，在本地開啟17個端口，其中分別選取4、7、10、13個端口作為監督節點，其余節點為共識節點。另開啟一個新端口作為客戶端節點，客戶端節點向共識和監督節點發送請求消息。每組測試分別記錄20組數據，數據吞吐量測試結果取各組記錄平均值，測試結果如圖5。

圖5 監督節點數量對數據吞吐量的影響Fig.5 Impact of the number of monitoring nodes on data throughput

圖5表明，隨網絡中監督節點數量的增加，網絡中數據吞吐量有了迅速提升。因此可以得出，在同一網絡規模下，監督節點的設置大大提升了數據吞吐量，監督節點占比越高，數據吞吐量越高，監督節點在一定程度上提升了數據的傳輸效率。

為體現實驗的一般性，選取典型的4個監督節點進行后續測試。在同樣的網絡環境下，設置8、12、16、20個端口，開啟一個客戶端節點，分別對PBFT算法、ESBFT算法進行吞吐量測試。每一輪進行20次測試，最后統計平均數據吞吐量。測試結果如圖6。

由圖6可以得出，網絡節點數為8、12、16、20時，ESBFT算法比PBFT算法在數據吞吐量上分別有125%、109.1%、69.7%、67.4%的提升。進而表明，由于網絡中參與共識的節點規模變小，在同等規模的網絡環境中ES-BFT算法的數據吞吐量更高，算法更優。

圖6 ES-BFT算法與PBFT算法數據吞吐量對比圖Fig.6 Comparison of data throughput between ES-BFT algorithm and PBFT algorithm

2.3.2 共識時延測試

共識時延表現為請求發起到請求被寫入的時間間隔，是反映共識算法性能的又一關鍵指標。在進行兩種算法時延對比之前，實驗測試了監督節點數量對網絡時延的影響，選取17個網絡節點，其中監督節點數量分別為4、7、10、13。實驗記錄從請求交易到交易提交的時間，每組節點進行20次測試，測試結果選取測試平均值，測試結果如圖7。

圖7 監督節點數量對共識時延的影響Fig.7 Impact of the number of supervisory nodes on consensus delay

圖7表明隨著監督節點數量的增加，共識時延明顯縮短。因此在實際應用中，可通過適當降低共識節點的比例來提高共識效率。

同數據吞吐量測試，本次測試首先開啟1個客戶端端口；其次，分別開啟了8、12、16和20個網絡節點端口，并從中選取具有代表性的4個監督節點；最后，測試了在相同網絡環境、各節點不進行任何服務情況下PBFT算法和ES-BFT算法的共識時延，同樣，每組測試各進行20次，測試結果選取20組數的平均值。測試結果如圖8。

由圖8的測試結果計算得出，實驗節點數量一定的情況下，ES-BFT算法的共識時延比PBFT算法時延下降69.8%、45.3%、32.9%、39.4%。由此表明，ES-BFT算法在共識時延上較PBFT算法有更大的優勢，隨著節點數的增多，PBFT算法時延上升明顯，而ES-BFT算法時延相對穩步上升。共識時延是算法性能的直接體現，因此在不考慮網絡環境影響、節點任務的情況下，單純就共識算法性能一項來講，ES-BFT算法性能優于PBFT算法。

圖8 ES-BFT算法與PBFT算法共識時延對比Fig.8 Consensus delay comparison between ES-BFT algorithm and PBFT algorithm

ES-BFT算法的監督機制避免了在GST到達之前的系統不協調情況的發生，在一定程度上提升了共識算法的安全性。本次實驗模擬主節點作惡，為方便理解，以4個節點為例，將節點分組并編號為1、2、3、4，主節點1在預準備階段向除4以外的其他節點發送消息，其他節點消息正常發送；在確認階段，主節點向2發送消息，但是不向3、4發送；本次的模擬方法將使四組節點兩兩進入相同狀態，系統產生不協調情況。實驗模擬了監督節點數為4，共識節點數分別為4、8、12、16的情形，每組節點記錄20組共識時延數據，測試結果取各組平均數，結果如圖9。

圖9 系統不協調下的ES-BFT算法共識時延Fig.9 ES-BFT algorithm consensus delay under system inco-ordination

圖9為系統不協調情境下ES-BFT算法在監督機制下從系統不協調到再次共識的總時延，圖9表明，監督機制的設計在有限時延內有效避免了系統不協調導致的長時間無法共識的情況。

3 結束語

ES-BFT算法提出了一種新的節點選取辦法和監督機制。節點的劃片選取和信譽值機制不僅有效地提高了共識節點的隨機性與可信性，還提升了網絡的靈活性；監督機制的設立成功避免了共識系統不協調的情況。實驗進一步認證，監督節點的使用提升了網絡的靈活性，在實際應用中，用戶可根據需求選取監督節點數量；節點選取和監督機制的實施有效地提升了PBFT算法的共識效率和安全性。本文算法是在不考慮復雜的網絡環境以及網絡節點不進行其他任務的條件下獲得的，以上限制條件值得在接下來的工作中進行探索研究。