GBFT：一種實用拜占庭容錯算法改進方案?

李 彬 張新有

（西南交通大學信息科學與技術學院 成都 611756）

1 引言

區塊鏈作為數字加密貨幣的重要底層技術，最早于2008 年由化名為中本聰［1］的學者提出。區塊鏈技術的去中心化、數據不可篡改、數據安全等特點，使得其在數字貨幣、物流溯源、數據取證和金融交易等領域都有很好的應用前景［2］。

當前，區塊鏈發展成為三種差異化類型：公有鏈，聯盟鏈，私有鏈［3］。其中，部分去中心化的聯盟鏈得益于參與節點數量較為固定、網絡規模較小、節點的信用度好等特點，具備了交易確認延遲低、吞吐量高、耗能小等優勢，因此在近年來得到迅速發展。共識算法作為區塊鏈中最為核心的技術，對區塊鏈的整體性能表現有著直接的影響。現有的許多適用于公有鏈場景的共識算法，因為有著巨大的共識成本和算力開銷，明顯不適用于聯盟鏈場景下的區塊鏈［3］。2014 年，隨著IBM 的聯盟鏈項目Hyperledger Fabric 的推出［4］，人們把目光聚焦到了實用拜占庭容錯算法（Practical Byzantine Fault Tolerance，PBFT）。

本文針對聯盟鏈的應用場景，分析了PBFT 共識機制存在的不足，并基于PBFT算法的思想，提出了一種分級的共識方案（Graded Byzantine Fault Tolerance，GBFT），以期在系統的長期運行中達到更高的共識效率和吞吐量及更低的資源消耗。

2 共識機制

一致性問題是分布式系統面臨的核心問題之一。分布式系統中如果僅存在非拜占庭錯誤，如網絡延遲、節點宕機，可以通過Paxos［5］和Raft［6］等算法解決一致性問題。但是區塊鏈網絡作為一個低信任的分布式系統，節點之間屬于互相不了解的參與者。受到利益的驅使，網絡中還可能產生拜占庭錯誤［7］。拜占庭錯誤是指存在節點主動向其他節點發送錯誤信息的可能，拜占庭節點指可以產生拜占庭錯誤的節點。在一個存在拜占庭節點的系統中，需要使用有拜占庭容錯能力的共識算法［8］。目前主流的區塊鏈共識機制主要有工作量證明、權益證明、股份授權證明以及實用拜占庭容錯算法等［9］。

2.1 工作量證明

工作量證明（PoW）的概念最早由Cynthia Dwork 和Moni Naor 在1993 年的論文中提出，主要用于解決當時日益嚴重的垃圾郵件問題［10］。幾年后，Markus Jakobsson 和Ari Juels 正式提出了術語“Proof of Work”，并給出了PoW 的形式化定義［11］。在一個區塊鏈網絡中，必須有負責記錄交易的節點存在，最簡單的方法是進行隨機選擇。然而，隨機選擇會使系統隨時暴露在可被攻擊的環境中。因此，如果一個節點想要發布一個交易區塊，就必須完成大量的工作來證明該節點幾乎沒有惡意攻擊網絡的可能性。一般來說，上述所謂的“工作”即計算機算力。工作量證明機制的優點在于算法簡單、去中心化程度高、網絡擴展性強、節點加入退出靈活。它的缺點是無用的工作量計算導致能源、算力等資源的嚴重浪費。此外，PoW 共識的效率較低，過長的出塊時間和交易確認時間難以滿足現實需求。

2.2 權益證明

權益證明（PoS）［12］試圖通過將采礦能力與節點持有的權益相聯系來解決PoW 中算力競爭的問題。PoS 的核心思想是持有較高權益的節點有更大的可能性來獲得區塊打包權。在使用PoS 機制的網絡中，依然需要節點求解PoW 中類似的數學難題。但是每個節點面對的數學難題的難度是不同的，這個難度與節點持有的代幣數量正相關。這意味著節點持有的代幣數量越多，它所需要求解的數學難題的難度越低，那么該節點解出這個難題并獲得區塊打包權的概率也就越大。PoS 的去中心化能力、網絡擴展性與PoW 相當，同時還有效降低了對資源的浪費。但是PoS 中存在的“無利害攻擊”，“長程攻擊”等問題也讓PoS 的安全性備受質疑。

2.3 股份授權證明

股份授權證明（DPoS）［13］，可以看做PoS的一個變種，由Bitshares 的首席開發者Dan Larimer 提出并應用。它通過實施去中心化的民主方式，每個節點可以將其持有的權益作為選票投給一名代表。系統將選出得票較高的前N 個節點組成見證人網絡。見證人網絡中的節點使用專業運行的網絡服務器，收集交易、打包區塊，引導促進區塊鏈項目的發展。在完成本職工作的同時，這些節點還可以領取區塊獎勵和交易手續費。DPoS 通過投票、選舉降低了參與共識的節點數目，因此與POS、POW 相比，它具有更低的交易處理時延和更高的吞吐量。但是DPoS中存在的“超級節點”也讓它的去中心化能力備受爭議。

2.4 實用拜占庭容錯

實用拜占庭容錯（PBFT），最早由Castro等［14］在1999 年提出，是解決存在拜占庭節點的分布式系統一致性問題的通用方案。PBFT算法基于狀態機復制原理（State Machine Replication）［15］，主要由三個協議組成：一致性協議、檢查點協議以及視圖更換協議。區塊生成過程中，一致性協議用來保證全網所有的節點保存數據的一致性，其通過三階段節點間的互相通信來實現；當運行一致性協議無法達成一致時產生超時事件，啟動視圖更換協議進行視圖轉換，以保證節點之間順利達成共識；檢查點協議主要有兩個用途：一是定期清除節點的過期數據，以減輕存儲壓力；二是檢查系統狀態，將系統中的節點同步到一個相同狀態。目前在區塊鏈領域中，PBFT 共識機制主要應用于聯盟鏈場景，例如hyperledger fabric（v0.6）、FISCO BCOS［16］等聯盟鏈平臺都在進行該共識機制的實際部署應用。

在PBFT 算法中，一個消息從發起到達成共識需要經過5 個階段。圖1 中，C 代表客戶端，0、1、2、3 表示4 個參與共識的節點，其中節點3 為拜占庭節點。具體步驟如下：

圖1 PBFT算法的一致性協議

1）request階段：客戶端發送請求到主節點；

2）pre-prepare階段：主節點收到客戶端請求后將其封裝為一個pre-prepare 消息，然后將pre-prepare消息廣播給從節點；

3）prepare 階段：從節點收到pre-prepare 證書后將其封裝為prepare 消息，并廣播給其他從節點，從節點進入pre-prepared狀態；

4）commit 階段：當系統中存在f 個拜占庭節點時，要求系統中總節點數量不能小于3f+1。若一個節點收到包括自己節點prepare消息在內的2f+1 個prepare 消息后，則該節點進入prepared 狀態，并向其他節點廣播commit消息；

5）reply 階段：節點收到包括自己節點的commit消息在內的2f+1個commit消息后進入commited狀態，并向客戶端返回reply響應消息。

傳統拜占庭容錯算法由于指數級別的時間復雜度而難以在實際系統中應用。PBFT算法則將時間復雜度降到了多項式級別，還能提供1/3 的容錯性。但PBFT算法的缺點也很明顯。一是算法在收到客戶端請求之后，需要經過5 個階段才能達成共識。其中prepare階段與commit階段是全節點參與的廣播過程，使得共識過程產生巨大的通信開銷；二是PBFT算法中的主節點由所有節點依次輪流擔當，這種主節點選擇策略過于隨意，使得主節點身份可以被輕易預測，增加了其被攻擊的風險；三是算法中的每個節點都維護了一個固定的節點列表，缺少節點的加入、退出機制，不能靈活應對網絡規模的動態變化。

不同的共識算法在不同的評判項目中，具有不同的表現。對上述4 種共識算法，從高往低分別用5分至1分對各項評測功能點做出評測，結果如表1所示［17］。

表1 四種共識算法性能比較

除以上四種經典共識算法外，近年來還涌現了多種新型共識算法，如Algorand［18］、Omniledger［19］、Rapidchain［20］、2-hop［21］。這些算法本質上都是多種經典共識算法融合的產物，它們不約而同地體現了同一個共識算法改進思路：基于實際應用場景對處理效率和規模的不同需求，將各具優勢的共識算法相融合，取長補短，從而在各項指標中取得最佳平衡。這也是本文提出的改進方案的基本思路。

3 改進方案GBFT

由圖1 知，PBFT 算法的一致性協議中有兩個階段（prepare 階段和commit 階段）的全節點廣播。隨著節點數量的增加，網絡中的通信開銷會增長迅速，影響算法的共識效率。針對此問題，結合聯盟鏈的特點，本文引入了非拜占庭容錯的共識協議，以降低節點之間的通信開銷；為了配合非拜占庭容錯的共識協議，同時提出了一種基于節點行為的選舉制度；在非拜占庭容錯協議、選舉機制、PBFT 容錯協議的基礎上構建了三級共識機制。

3.1 整體思想

根據模塊功能的不同，可以將一個使用PBFT共識機制的區塊鏈系統抽象為四個層次［22］（圖2）：應用層、執行引擎層、共識層、數據層。其中，應用層代表各種基于區塊鏈網絡的應用；執行引擎層提供了區塊鏈網絡的運行時環境；共識層定義了系統所使用的共識協議；數據層定義了區塊、交易等結構以及與這些結構相關的增刪改查操作。通過2.4節的分析可知，PBFT 共識機制的性能瓶頸主要在于準備階段和提交階段的兩次全節點廣播。隨著區塊鏈網絡中節點數目的增多，網絡通信量會急劇增長，從而增加帶寬的壓力，導致了交易確認時間長、吞吐量低、網絡擴展性差等問題。

圖2 使用PBFT共識機制的區塊鏈系統架構

針對PBFT 共識機制的性能瓶頸，本文提出以下三點舉措解決問題。

1）引入非拜占庭容錯的一致性協議。在聯盟鏈場景中，節點都是經過一定準入機制才能加入區塊鏈網絡，這使得聯盟鏈中的節點相比公有鏈中的節點有更高的可信度。據此可以認為聯盟鏈中大多數情況下是沒有拜占庭節點的，此時在網絡中運行拜占庭容錯的一致性協議并不是十分必要。因此，可以在在共識層引入一種非拜占庭容錯的一致性協議。系統根據網絡中節點狀態來選擇執行不同的一致性協議：當參與共識的節點中不存在拜占庭節點時，運行非拜占庭容錯協議；當使用非拜占庭容錯協議無法達到一致時，運行PBFT 的一致性協議。

2）設計基于節點行為的選舉機制。引入非拜占庭容錯協議的同時也引發了另外一個問題，即網絡中存在拜占庭節點時，使用非拜占庭容錯協議無法達到一致，那么就需要切換到PBFT 的一致性協議。如果在存在拜占庭節點的網絡中使全節點都參與非拜占庭容錯協議，實際上共識機制不僅會退化為普通的PBFT 算法，還會因為頻繁的協議切換帶了更大的共識成本。因此需要設計一種選舉機制，選出部分節點參與非拜占庭容錯協議，且選出的節點應當盡量避免包含拜占庭節點。

3）提出三級共識機制。在計算機結構的三級存儲體系中，計算機的存取速度接近于緩存的速度，而存儲容量由硬盤所決定。基于這種思想，提出三級共識機制。首先由選舉出的部分節點參與非拜占庭容錯協議作為第一級共識，第一級共識無法達成一致的情況下進入第二級共識。第二級共識是部分節點參與的PBFT 一致性協議，當第二級共識無法達成一致時進入第三級共識。第三級共識就是原始的全節點參與的PBFT共識。最終希望達到的效果就是整個網絡的共識效率由第一級共識決定，而系統的容錯性由第三級共識決定。

綜上，在共識層應用GBFT 算法的區塊鏈系統架構如圖3所示。

圖3 使用GBFT共識機制的區塊鏈系統架構

3.2 改進方案設計

3.2.1 非拜占庭容錯協議

引入非拜占庭容錯協議的目的在于簡化PBFT共識協議中prepare階段和commit階段中的全節點廣播通信，本文采用了參考文獻［23］中提出的簡化一致性協議，如圖4所示，具體內容為

圖4 非拜占庭容錯協議

1）主節點廣播pre-prepare消息到從節點，從節點驗證消息內容后向主節點回復確認消息；

2）主節點收到所有從節點的確認消息后，廣播confirm 消息到從節點，從節點驗證消息內容后向主節點回復確認消息；

3）主節點收到所有節點的確認消息則代表達成共識，否則意味著共識失敗。

3.2.2 選舉機制

在引入非拜占庭容錯協議的系統中，系統優先選擇非拜占庭容錯協議作為共識協議，當非拜占庭容錯協議無法達成一致時再切換到PBFT的一致性協議。為了避免不同協議頻繁切換帶來的額外開銷，我們希望每次參與非拜占庭容錯協議的節點都是誠實節點，為此系統中設計了一個基于節點行為的選舉機制。

在區塊鏈網絡中，每個節點都由一個信用分屬性。所有節點被劃分為兩類：共識節點、非共識節點。共識節點與非共識節點的比例為1∶1。選舉模塊選取共識節點時遵循兩個原則：一是信用分高的節點優先；二是信用分相同時編號較小的節點優先。共識過程中，首先由共識節點參與一級共識，若達成一致，則每個參與節點可獲得2 信用分；若無法達成一致，參與節點扣3 信用分，然后進入二級共識。若系統執行二級共識達成一致，每個參與節點獲得1 信用分；若無法達成一致，每個參與節點扣2 信用分，然后進入三級共識。三級共識執行的是全節點參與的PBFT 一致性協議，三級共識中不再對節點信用分進行增減。如此往復，節點會因為自身行為而獲取、損失信用分，分值代表了節點的可信度。圖5 是一個節點的信用分的狀態轉換圖，其中X代表一個節點的信用分。

圖5 節點信用分狀態轉換圖

共識節點選舉機制將會在以下三種情況發生時被觸發：

1）區塊鏈系統啟動的初始時刻。此時所有節點信用分為0，根據信用分相同時編號較小的節點優先原則，選舉模塊將選擇編號較小的前50%節點作為共識節點。

2）發生了共識級別轉換。若某次請求的共識過程中發生了共識級別轉換，意味著共識節點集合中存在拜占庭節點。最壞情況下，該請求依然可以通過三級共識在各節點間達成一致，然而在下一個請求到來時共識節點集合中還是存在拜占庭節點，那么通過一級共識始終無法達成一致，總是要執行共識級別轉換，帶來額外的資源消耗。因此，每當發生了共識級別轉換，在當前請求完成后，都要重新進行共識節點選舉。

3）共識節點強制選舉計時器超時。共識節點長時間運行一級共識會使這些節點始終處于忙碌狀態，而非共識節點無法獲得信用分，沒有上升通道，也浪費了算力。為了避免這種情況的發生，在系統中設定一個共識節點強制選舉計時器。當該計時器超時，將所有節點信用分清零，強制進行共識節點選舉。共識節點編號ni由式（1）和式（2）計算得出。

其中：timestamp為共識節點強制選舉計時器超時時刻的時間戳，N為節點總數。

3.2.3 三級共識機制

為了進一步提高共識效率與網絡擴展性，結合非拜占庭容錯協議、PBFT 一致性協議以及選舉機制，提出的三級共識機制流程如圖6所示。

圖6 三級共識算法流程

具體內容為

1）選舉產生共識節點。

2）接收來自客戶端的交易請求。

3）共識節點執行一級共識。若達成一致，進入6）；否則，進入4）。

4）執行共識級別轉換，共識節點參與二級共識。若達成一致，進入6）；否則，進入5）。

5）執行視圖轉換，所有節點參與三級共識。若達成一致，進入6）；否則，繼續執行5）。

6）所有節點接受共識結果，執行客戶端請求。7）更新每個節點的信用分。

8）若發生了共識級別轉換，則選舉產生新的共識節點。

9）一次請求結束。

4 實驗場景及結果分析

本章從吞吐量、交易確認時延和容錯性能等三方面分別對原始PBFT 和GBFT 進行測試。通過對照，驗證了改進方案的有效性和可用性。

4.1 實驗場景

租用了一臺云服務器作為實驗平臺，在服務器上安裝了Ubuntu 操作系統以及docker、docker-compose、Go 語言等基本環境。然后在Hyperledger Fabric 原生的PBFT 算法的基礎上實現了GBFT。最后在服務器上分別對應用原始PBFT 算法的Hyperledger Fabric 和應用GBFT 算法的Hyperledger Fabric 進行測試。實驗平臺的軟硬件配置如表2所示。

表2 實驗環境配置信息表

4.2 吞吐量測試

吞吐量是衡量系統運行效率的一個重要標準。在區塊鏈網絡中，一般用每秒交易數（tps）來表示，即：

其中：transactions 為出塊時間內系統處理交易數，t為出塊時間。設計兩種共識機制在4、5、6、7、8 個節點下的對照實驗，多次測試取平均值，實驗結果如圖7所示。

圖7 兩種算法的吞吐量比較

從圖7 的實驗結果可以看出，隨著網絡中節點數目的增加，兩種情況下吞吐量都下降明顯。這是因為節點數目的增加使得網絡中通信開銷增大，導致網絡運行效率下降。還可以看出，在節點數目相同的情況下，相比于原始PBFT 算法，GBFT 始終具有更高的吞吐量。

4.3 時延測試

交易確認時延指客戶端發送一個交易請求到客戶端確認交易完成的時間間隔，即：

其中：Tconfirm為交易得到確認的時間，Trequest為發送交易請求的開始時間。設計兩種共識機制在4、5、6、7、8 個節點下的對照實驗，多次測試取平均值，實驗結果如圖8所示。帶來的通信成本增加所導致的結果，但是原始PBFT算法的時延上升速率更大，而GBFT由于引入了非拜占庭容錯一致性協議與選舉機制，使得它的時延上升速率是隨節點數目的增加而下降的。此外，在節點數目相同的情況下，相比于PBFT，GBFT始終具有更低的交易確認時延。

圖8 兩種算法的交易確認時延比較

圖8 中，兩種方案的交易確認時延都隨節點數目的增加呈上升趨勢，這同樣是由節點數目的增加

4.4 容錯性分析

設區塊鏈網絡中共有N（N ≥4）個節點，其中有F 個拜占庭節點。改進方案中，系統會根據節點信用度的高低選出N/2 個節點納入共識節點組，設共識節點組中的拜占庭節點數目為f（f ≤F），則有：

1）第一級共識：共識節點組參與簡化協議。若共識節點組中沒有拜占庭節點，即f=0，則順利達成一致；若f ≥1，則通過非拜占庭容錯協議無法達成一致，進入第二級共識。

2）第二級共識：共識節點組參與PBFT 共識協議。若1 ≤f≤（N/2-1）/3，已知PBFT算法的容錯性為（N-1）/3，可知第二級共識順利達成一致；若f>（N/2-1）/3，則第二級共識無法達成一致，進入第三級共識。

3）第三級共識：全節點參與PBFT 共識。此時共識機制退化為原始的PBFT 算法，有f=F。當f≤（N-1）/3 時，節點之間順利達成一致；當f >（N-1）/3，整個網絡無法達成一致。

以上分析證明，GBFT 的容錯性是由第三級共識的容錯性決定的。即采用GBFT 作為共識機制的區塊鏈網絡中共N個節點時，整個網絡可以提供（N-1）/3的容錯性。

5 結語

基于PBFT 算法的思想，結合聯盟鏈應用場景中節點可信度相對更高的特點，提出一種改進的共識算法。首先在保留PBFT一致性協議的同時引入了非拜占庭容錯協議，以降共識過程中的通信開銷；為了避免兩種一致性協議的頻繁切換帶來的額外開銷，提出了基于節點行為的選舉機制；最后在非拜占庭容錯協議、選舉機制、PBFT一致性協議的基礎上構建了三級共識機制。實驗結果表明，相比于PBFT 算法，本文提出的GBFT 算法有效提高了區塊鏈網絡的吞吐量，降低了交易確認時延，同時還保持了PBFT 算法的容錯性。在GBFT 中，將信用分排名前50%的節點納入了共識節點集，這樣的設定可能無法適用于所有的應用場景。下一步的工作中可以考慮將共識節點集的容量設置為一個可配置的參數，以靈活調整網絡的去中心化程度。