基于改進Raft共識算法和PBFT共識算法的雙層共識算法

袁昊天 李飛

摘 要：針對目前應用于聯盟鏈中的實用拜占庭（PBFT）共識算法可擴展性不足、通信開銷增長過大、難以適用于大規模網絡節點環境等問題，提出了一種基于改進Raft共識算法和PBFT共識算法的雙層共識算法（DL_RBFT）。首先將區塊鏈中的節點分成若干小組，組成下層共識網絡，然后小組的組長再構成上層共識網絡，形成一個雙層共識網絡結構；在下層共識網絡的小組內部引入監督機制和聲譽機制來改進Raft共識算法，在初始組長的選舉流程引入了蟻群算法，使選舉效率始終維持在較高水平；在上層共識網絡中，使用PBFT共識算法進行共識。改進后的Raft共識算法具備了抗拜占庭節點攻擊的能力，提升了算法的安全性。實驗結果分析表明，相較于傳統的PBFT共識算法，在100個節點的情況下，DL_RBFT將共識時延降低了兩個數量級，吞吐量也提升了一個數量級，與其余改進算法相比也有著明顯優勢。因此DL_RBFT共識算法擁有良好的可擴展性，可以廣泛應用于聯盟鏈的各種場景中。

關鍵詞：聯盟鏈； 共識算法； Raft； PBFT； 區塊鏈； 雙層共識網絡； 監督機制； 聲譽機制

中圖分類號：TP301 文獻標志碼：A?文章編號：1001-3695（2024）05-005-1314-07

doi：10.19734/j.issn.1001-3695.2023.08.0390

Double layer consensus algorithm based onimproved Raft consensus algorithm and PBFT

Abstract：This paper proposed a dual-layer consensus algorithm（DL_RBFT） based on the enhanced Raft and practical Byzantine fault tolerance（PBFT） consensus algorithms to address scalability issues， excessive communication overhead， and challenges in large-scale network node environments in use within consortium blockchains. Initially， it divided blockchain nodes into several groups to form a lower-layer consensus network. Then， leaders from these groups constituted an upper-layer consensus network， creating a dual-layer consensus structure. In the lower-layer consensus network， it improved Raft consensus algorithm by introducing supervision and reputation mechanisms， while the leader election process introduced ant colony optimization to maintain high efficiency. In the upper-layer consensus network， it utilized the PBFT consensus algorithm for consensus. The enhanced Raft consensus algorithm exhibited resistance to Byzantine node attacks， enhancing the algorithms security. Experimental results indicate that compared to traditional PBFT consensus algorithms， DL_RBFT reduces consensus latency by two orders of magnitude and improves throughput by one order of magnitude in a 100-node scenario. In comparison to other enhanced algorithms， DL_RBFT demonstrates significant advantages. Therefore， DL_RBFT consensus algorithm exhibits strong scalability and can be widely applied in various consortium blockchain scenarios.

Key words：consortium blockchains; consensus algorithm; Raft; PBFT; blockchain; dual-layer consensus network; supervision mechanism; reputation mechanism

0 引言

自2008年中本聰發布比特幣白皮書［1］，區塊鏈［2］作為一種分布式、去中心化的技術，憑借其不可竄改、透明、安全性高等優勢，受到各領域的關注。作為區塊鏈核心技術之一的共識機制，其保證了節點集群的安全性、穩定性和一致性。隨著區塊鏈技術的快速發展，越來越多的人加入到區塊鏈網絡中，因而對區塊鏈節點體量的要求越來越大，對共識機制的要求也越來越高，因此，共識機制的可擴展性、安全性和穩定性就成為了區塊鏈領域的重點研究問題［3］。

現有的共識機制有工作量證明（proof of work，PoW）［4］、權益證明（proof of stake，PoS）［5］、權益證明+權益投票（delegated proof of stake，DPoS）［6］ 、工作量證明+權益證明（proof of work with proof of stake，PoW/PoS）［7］、優先委托權益證明（preferential delegated proof of stake，PDPoS）［8］、Raft［9］、拜占庭容錯共識（Byzantine fault tolerant consensus，BFT consensus）［10］、實用拜占庭容錯共識（practical Byzantine fault tolerance，PBFT）［11］等。

根據節點準入類型的不同，可以將區塊鏈劃分為公有鏈（public blockchain）、聯盟鏈（consortium blockchain）以及私有鏈（private blockchain）［12］三類。公有鏈是一種完全開放的區塊鏈網絡；在公有鏈中，任何人都可以參與該網絡的節點，并且可以進行交易、添加新的區塊以及參與共識機制。在聯盟鏈中，參與的節點需要獲得邀請或滿足特定的準入條件才能加入網絡；一般情況下，聯盟鏈的節點由多個組織或實體共同管理；聯盟鏈的共識機制可能不同于完全去中心化的公有鏈，聯盟鏈通常更注重隱私性和可擴展性，因為參與者之間可能需要一定程度的信任；聯盟鏈在特定行業或組織之間分享數據和交換價值的場景中被廣泛使用。AntChain、Zhi Xin Chain、XuperChain、Ti Chain、星火鏈、長安鏈等，都是有名的聯盟鏈。私有鏈是一種完全私有化的區塊鏈網絡，參與節點由單個實體或組織控制。私有鏈的訪問權限通常受到嚴格限制，只有授權的節點才能參與網絡的管理和交易活動。

聯盟鏈相比于公鏈和私有鏈，更適合一些特定的企業和組織間合作的場景，因為其可以提供更高的隱私性、可控性和可擴展性。聯盟鏈在物聯網（IoT）［13］、供應鏈管理［14］、電子健康記錄［15］、版權保護［16］、跨部門數據共享［17］、產品溯源［18］等領域有著廣闊的應用前景。盡管聯盟鏈在這些應用場景中表現出許多優勢，但它們仍然面臨一些挑戰，比如擴展性差、安全性低、吞吐量小等問題。

目前在聯盟鏈的許多應用中，使用最多的是PBFT共識算法，PBFT共識算法雖然不像PoW需要消耗大量的算力，但其時間復雜度為O（n2）［19］，隨著鏈上節點數的增加，PBFT的通信開銷呈現平方級的增長，共識效率急劇降低，故只適用于節點數量在一定范圍的場景。在供應鏈管理、物聯網、跨部門數據共享、金融等領域，其對區塊鏈的可擴展性和性能要求較高，節點的規模可能在數百上千，并且吞吐量要達到萬級，PBFT共識算法難以適用于這些場景。作為區塊鏈的核心技術之一，共識機制在很大程度上決定了區塊鏈的吞吐量、可擴展性、安全性等，因此，改進現有的共識機制是切實解決這些問題的有效方法。

針對上述PBFT共識算法存在的問題，文獻［20］引入了協調器技術對PBFT算法進行改進，首先將交易交給協調器進行分類，從中篩選出存在異常的交易，只對這部分交易執行完整的共識，使得共識延時縮短了79%；但是，該算法由于引入了協調器，會存在協調器單點故障導致整個系統失效的問題。文獻［21］提出網絡自聚類的分組方法，提升了PBFT擴展性不佳的問題，但是節點間頻繁的通信導致通信復雜度增加，共識效率難以保證。文獻［22］提出一種分組策略，利用K-medoids聚類算法對節點進行特征聚類和層次劃分，使得單次共識耗時縮短了20%，通信次數最佳能夠降低3個數量級；但是該算法的時間復雜度依然是O（n2），并且搭建公識網絡的速度更慢，而且可能導致區塊鏈網絡所有節點的數據缺乏一致性。文獻［23］在文獻［22］的基礎上，在分組策略中加入了仿生優化算法，提升了分組效率，又將組內共識改變為Raft共識機制，使得組內共識算法的時間復雜度優化為O（n），提升了共識效率；但仍然在一致性上存在問題，且文獻［23］因為其通信流程設計，使得下層節點僅能知道上層節點的決定，不能作出干預，故下層節點的存在意義存疑。文獻［24］提出一種基于一致性hash均勻分組的雙層共識算法，解決了分組不均的問題，但是在分組時的多次hash增加了計算復雜度，降低了算法性能。

僅改進PBFT算法，不能解決其算法設計層面帶來的時間復雜度高的問題，可擴展性差的問題也不能從根源上解決。Raft共識機制是一種強領導型的共識算法，時間復雜度僅為O（n），在節點規模龐大的情況下，也能使得共識效率處于較好的水平，但是Raft共識機制本身不存在抗拜占庭攻擊的能力。因此，本文結合Raft共識機制的高效率特性和PBFT共識算法的抗拜占庭攻擊的特性，構建一種基于Raft和PBFT算法的雙層共識（DL_RBFT）算法，在保證可擴展性的同時，保證共識網絡的抗拜占庭節點攻擊能力。

本文的主要研究工作如下：a）針對聯盟鏈實用拜占庭共識機制在大規模節點場景出現的時延爆炸問題，結合Raft共識算法提出了一種基于改進Raft共識算法和PBFT共識算法的雙層共識算法（double layer consensus algorithm based on improved Raft consensus algorithm and PBFT，DL_RBFT）；b）針對改進算法的安全性、一致性、活性進行討論分析，論證了DL_RBFT算法的可行性；c）對DL_RBFT算法的共識延時、吞吐量和容錯性進行仿真實驗測試，驗證其有效性和安全性；d）對下層改進的Raft算法中的選主策略進行仿真模擬，驗證算法的有效性。

1 相關知識

1.1 PBFT算法

1999年，Castro等人［25］提出了實用拜占庭共識算法，改進了BFT算法的效率，使其時間復雜度從O（nf+1）降為O（n2），在滿足網絡中的總節點數N和拜占庭節點數f滿足N≥3f+1關系的前提下，可以保證網絡的正常運行。

三階段共識流程和視圖更換流程是實用拜占庭共識機制的兩個主要流程［26］。

在三階段共識流程中，分為請求（request）、預準備（pre-prepare）、準備（prepare）、確認（commit）、回復（reply）五個階段。在request階段，客戶端會向主記賬人（主節點）發送請求消息。主節點收到消息后，流程進入pre-prepare階段，主節點會生成預準備消息廣播給網絡中所有的記賬人節點（從節點）。在prepare階段，所有的從節點接收到預準備消息并通過驗證后，會將其余所有節點廣播準備消息。commit階段，當節點收到來自不同節點的準備消息的數量>2f（不包括自己），就會向網絡中除自己以外的所有節點發送確認消息。當節點收到來自不同節點的確認消息的數量>2f+1，進入reply階段，并向客戶端發送回復消息。當客戶端收到超過f+1個節點的有效回復消息后，會將這一次的共識判定為成功。其執行流程如圖1所示。

當主節點出現異常，并且被從節點判定已失效，就會進入視圖更換流程，切換主節點，進入新一輪共識，以保證共識的正常進行。

1.2 Raft共識算法

2014年，Ongaro等人［27］提出了Raft算法。Raft的兩個核心部分是領導選舉和日志復制。在Raft共識算法中，節點有領導者（leader）、追隨者（follower）、候選人（candidate）三種狀態，節點會在這三種狀態之間有條件地切換。

系統在任一時刻，有且僅有一個leader，leader會周期性地和follower維持心跳聯系。當follower超過時間閾值仍然沒有收到來自leader的心跳，將會把自己的狀態從follower轉變為candidate，然后向其他節點廣播競選消息，邀請其余節點投票。如果candidate在競選時間超時前收到超過半數的投票，將會把自己的狀態轉變為leader，否則將會廣播下一輪競選消息。節點狀態的流程如圖2所示。

在日志復制階段，leader首先會將交易打包并廣播給網絡中所有節點，follower收到后，向leader反饋；在leader收到超過半數節點的回復信息后，會發送確認信息給follower，并且將該區塊計入賬本，follower在收到來自leader的確認信息后，也會將該區塊計入本地賬本。日志復制流程如圖3所示。

1.3 集群智能算法

典型的集群智能系統是由若干個彼此間可相互通信且只能完成簡單行為的代理組成，這個集群沒有控制中心，行為簡單，但可以通過彼此交互完成十分復雜的任務，從整體上表現出智能。典型的群體智能算法包括蟻群算法、粒子群算法、混合蛙跳算法、煙花算法等，這些算法普遍具有自組織、靈活性高、無中心控制、低能耗、高魯棒性等特點；但不同的算法有著不同的優缺點，適用于不同的問題。

在本文研究的問題中，在雙層共識網絡的下層結構網絡，節點群選擇leader和監督節點時，Raft算法的隨機性太強，在節點規模龐大時會陷入無解情況，故引入群體智能算法來解決該問題；同時還引入聲譽值作為影響決策的重要因子，并且隨著節點的不同操作，更新聲譽值；因此需要一個自適應性強、魯棒性強和全局搜索能力強的算法優化該流程。在上述的智能集群算法中，粒子群算法容易陷入局部最優解、對初始值敏感以及難以處理約束條件， 不適用于尋找最高聲譽值的問題；混合蛙跳算法依賴于不同個體之間的交流，應用在本文研究的問題中，會嚴重降低選主效率，故也不適用于選主問題；煙花算法也容易陷入局部最優解，參數過多且對參數的敏感性太高，隨機性太強，同樣不適用于選主問題。

而蟻群算法憑借以下優勢［28］，更適用于解決該問題。

a）全局搜索能力強。通過螞蟻之間的信息素交流和反饋來引導搜索過程，能夠較好地探索問題空間，并具有全局搜索能力，使得算法在求解復雜優化問題時，能夠找到較優的全局解。

b）自適應性和自組織性。蟻群算法具有自適應性和自組織性的特點，螞蟻在搜索過程中不斷調整行為策略，根據環境和信息素的變化進行適應性調整。該特性使得蟻群算法能夠應對動態、復雜的問題，適應環境的變化。

c）分布式計算和并行性。蟻群算法的計算過程是分布式的，螞蟻在搜索過程中獨立執行，各個螞蟻相互協作，通過信息素的交流和反饋來實現群體智能搜索。這種并行性使得蟻群算法在大規模問題和并行計算環境下能夠具備較好的性能和效率。

d）魯棒性和容錯性強。蟻群算法具有一定的魯棒性和容錯性，即使在搜索過程中遭遇局部最優解，通過信息素的揮發和更新，也可以幫助螞蟻擺脫陷入和跳出局部最優解，進一步搜索全局最優解。

1997年，Dorigo等人［29］提出了一種元啟發式的蟻群算法，它是通過模擬螞蟻在尋找食物過程中的行為而發展起來的一類群體智能優化算法。蟻群算法流程如圖4所示，其基本思想是模擬螞蟻在尋找食物時的行為。當一只螞蟻找到一條路徑后，它會釋放一種化學物質（信息素）來標記這條路徑，其他螞蟻探測到這些信息素后，更有可能選擇沿著被標記的路徑行走。隨著螞蟻數量的增加，更多的螞蟻選擇相同的路徑，導致該路徑上的信息素濃度增加。這樣，在信息素的引導下，螞蟻群體逐漸集中于較優的路徑上，從而找到問題的近似最優解。

2 DL_RBFT算法模型

本文結合PBFT共識算法的抗拜占庭節點的安全性和Raft共識算法的高效率的優點，提出了一種基于改進Raft共識算法和PBFT共識算法的雙層共識算法。在下層小組網絡中，設計了一種更高效、穩定的選主方式，同時在分組時，會爭取每個小組的節點數盡可能相同。為了增強Raft算法的抗拜占庭節點的能力，在小組內引入了監督節點。

2.1 DL_RBFT網絡結構

在DL_RBFT共識算法中，存在兩層共識網絡，下層共識網絡是一個個相互獨立的小組，每個小組都由1個組長節點、1個監督節點和若干個組員節點構成。每個小組的組長共同構成上層的共識網絡。DL_RBFT的網絡結構如圖5所示。

2.2 下層網絡主節點更新策略及監督機制

在Raft共識算法中，當節點數量規模達到一定程度后，會在一個時間點存在大量的candidate節點。由于每個節點處理事務的能力不同、網絡延遲不同，可能會導致follower節點的選票分散在各candidate節點上，導致選舉超時，所以可能會花費大量時間在選舉leader上。為了解決這一問題，在初次選舉leader時，本文引入聲譽機制和蟻群尋路算法，將高聲譽值節點模擬為蟻群搜尋目標。在后續重新選舉leader時，如果是有節點聲譽值達標，則采用聲譽值評判機制來作出抉擇，并且選擇出監督節點；如果是leader出現故障，則由監督節點代替leader，follower中當前聲譽值最高的擔任監督節點。下面介紹小組內節點選主策略和聲譽值機制。

在剛生成區塊鏈網絡時會隨機指定一個臨時組長，然后小組內的節點會先向所有人發送一條消息，消息中記錄著本條消息發送時間的時間戳timestampsend。當節點收到其余節點發送的消息時，會記錄收到該消息的時間戳timestampreceive，并計算時間差timedifferi=timestampreceive－timestampsend，并廣播給其余節點該節點的通信時延。當節點收到來自其余節點的通信時延消息，并且超過2/3的節點所記錄的數據差異不大時，會將自己收集到的時延信息發送給臨時組長。臨時組長會將消息整合，根據時延信息先進行標準化和歸一化，然后對所有節點的聲譽值進行初始化，如式（1）～（5）所示，其中n為節點數。

聲譽值生成后，臨時組長會將聲譽值信息廣播給所有節點，并告知節點開始進行leader競選。

在首次leader競選中，默認聲譽值排第2的節點作為臨時監督節點，聲譽值排名前x（3≤x≤10）位的節點會成為candidate節點，然后根據聲譽值和蟻群尋路算法進行leader選舉。

算法中符號含義如表1所示。

算法1 蟻群選主算法

輸入：value，random，α，i=0，β。

輸出：leader和監督節點。

a）if i＜n 轉至步驟b），else i=0，并把票數全部歸0，轉至步驟b） //檢測所有節點是否投票

b）if random<α+β，轉至步驟c）；else 轉至步驟d） /*α和β視不同情況決定*/

c）votemax++，valuemax=valuemax×1.1，轉至步驟e） /*聲譽值最大的節點的票數和聲譽值更新*/

d）隨機選擇一個不超過x的正整數，然后votem++，valuem=valuem×1.1，轉至步驟e） //隨機節點的票數和聲譽值更新

e）if 不存在節點的選票超過半數i++， 轉至步驟a）， else選票超過半數的節點成為leader，聲譽值第二大的節點成為監督節點，聲譽值和票數清零，end //選擇leader和監督節點，并對聲譽值和票數進行歸0操作

在leader產生后，會向follower節點定時發送心跳信息，如若有follower節點超時未收到心跳信息，則會向監督節點匯報leader異常，當監督節點收到超過半數的節點發來的leader節點異常信息，則會將自己的狀態轉換為leader，并廣播給所有節點，同時會指派聲譽值最高的follower節點成為監督節點來維持正常的共識功能。小組leader更新流程如圖6所示。

在共識過程中，與傳統Raft共識流程不同的是，follower節點的確認消息會同時發送給監督節點和leader，leader在記錄區塊后，也會將反饋信息發送給監督節點。如果監督節點發現消息異常，就會變成leader，然后指派聲譽值最高的follower節點作為監督節點來維持正常的共識功能。

在聲譽值機制中：

a）leader節點和監督節點不會參與聲譽值更新；

b）在產生leader和監督節點后，所有節點的聲譽值都會清0；

c）聲譽值共分為Vbad、Vnormal、Vgood、Vbetter和Vbest五個等級，分別對應0～20、21～40、41～60、61～80、81～100；

d）節點聲譽值到達100，就開始競選leader。

節點聲譽值更新公式如式（6）（7）所示。

a）懲罰公式：

b）獎勵公式：

其中：Vi表示小組內第i個節點的聲譽值，Vpreviousi表示第i個節點上一次的聲譽值。

2.3 DL_RBFT共識流程

在對鏈上所有節點進行分組、組內leader選舉形成雙層共識結構后，各組長間進行PBFT共識，組內則采用改進的Raft算法進行共識。形成的雙層共識算法在擴展性、安全性和共識效率上均取得了一定程度的提升。

DL_RBFT算法的共識流程如下：

定義小組數為G=3f+1，PBFT主節點編號為p，從節點編號為i，客戶端編號為c，客戶端請求消息的編號為reqID，請求消息為msg，請求消息的摘要為dig（msg），節點p對msg簽名后記作〈msg〉σp，消息的時間戳記作timestamp，最終執行結果為reqs，本次共識的視圖編號為Vid。

a）區塊鏈按照2.1和2.2節中的方法分成G個小組，并選舉leader，即組長。

b）客戶端c發送msg到主節點p，開始進行上層共識，即組間共識。

c）PBFT主節點p向其余從節點發送預準備消息〈〈pre_prepare，reqID，msg〉σp，dig（msg）〉。

d）PBFT從節點接受到預準備消息后，會對消息進行驗證檢查，若合法，則所有從節點向除自己以外的所有節點廣播自己簽名后的消息〈prepare，reqID，dig（msg），i〉σp。

e）當節點（組長）收到超過2f個節點的準備消息并驗證確認后，會將消息帶入小組內，進行組內共識。

（a）組長向監督節點和所有組員節點廣播消息。

（b）組員節點收到消息，驗證確認后向組長節點和監督節點發送確認信息，監督節點收到超過3n/4個節點發送的確認信息，組長節點收到超過n/2個節點發送的確認信息（n為小組組員節點總數），則進入下一階段，否則認為本輪共識無效。

（c）監督節點對組長節點進行審查，審查通過，繼續完成共識，組長節點將消息上鏈，并返回上層網絡；審查不通過，進行組長更換，具體流程如2.2節所述。

f）組長節點向PBFT網絡除自己以外的所有節點廣播確認消息〈commit，reqID，dig（msg），i〉σp。

g）當節點收到超過2f+1個來自其他節點發來的確認消息，則認定該消息已確定，并向客戶端c發送回復消息〈reply，Vid，timestamp，c，i，reqs〉σi。

DL_RBFT算法的完整共識流程如圖7所示。

3 算法分析

本文的DL_RBFT共識算法是針對聯盟鏈提出來的，本章對DL_RBFT共識算法的安全性、一致性、活性進行理論分析，對通信開銷進行分析并與PBFT、 Raft算法進行對比。DL_RBFT共識算法是基于PBFT共識算法和Raft共識算法構建的，引入了監督機制、聲譽機制和蟻群算法，也對Raft選主流程做了一定改進，使得算法的安全性和活性都有一定的提升。

3.1 安全性

在組長節點組成的上層共識網絡中，共識的安全性由PBFT算法自身的抗拜占庭節點特性提供。拜占庭節點不超過組長節點總數的1/3時，系統安全性由PBFT共識流程中的三階段共識流程保證；當主節點出現異常時，系統通過切換視圖來更換主節點，以此來保證安全性。

在下層共識網絡的小組中，在傳統的Raft算法中引入了監督機制，使得Raft算法擁有了抗拜占庭攻擊的能力。如果組長發送給監督節點的確認消息與監督節點自己從組員處收集到的消息不一致，將觸發組長更新事件來保證共識的正常進行。

假設小組內節點數量為n，拜占庭節點數量為f。拜占庭節點收到來自組長的消息msg后，可能不處理消息，或者作出假消息msg′，但是會向監督節點發送正確的消息msg。那么監督節點收到的M條一致消息中，可能存在f個拜占庭節點的惡意消息。為了保證M中存在一半以上由誠實節點發送來的消息msg，應滿足

因此，在下層共識網絡中，引入監督節點可以保證拜占庭節點在不超過n/4的情況下，共識能正常運行。

小組內的組長和監督節點也會在組員聲譽值達標或者自身出現異常時進行組長和監督節點的更新，以確保不會存在單點失效的問題。

3.2 一致性

由CAP定理［30］可知，在一個分布式系統中，最多同時滿足一致性、可用性、分區容錯性三個屬性中的兩個。但是為了保證系統的可用性，一般會根據BASE理論［31］來構建系統，達到最終一致性而非強一致性。

在組長構成的上層共識網絡中，PBFT保證了在拜占庭節點數量不超過組長節點數量的1/3時的一致性。在小組內部，通過Raft算法的日志復制來保證一致性，即使有節點宕機，也可以在恢復后從組長處下載完整的日志記錄，達成最終一致性。

3.3 活性

在上層網絡中，活性由PBFT算法的視圖切換協議來保證。當PBFT主節點出現異常，無法正常響應客戶端時，通過p=v mod k確定新的主節點來推動共識流程正常進行，p為主節點編號，v為當前視圖編號，k為參與PBFT共識的節點總數。

下層網絡中follower會和leader保持心跳消息聯系，倘若響應時間超時，則會觸發leader更新協議，使監督節點暫代leader，直至下次leader選舉；同時，新產生的leader會代替原leader履行其在上層網絡中的職責，增強了PBFT算法的活性。

3.4 通信開銷分析

在本節中，假設區塊鏈的分組數為G，每個小組的節點數為n，且G≥4，n≥4，則整個鏈上的總節點數為N=G×n。

1）單次PBFT共識流程通信次數

若使用傳統的PBFT共識算法進行一次共識，在request階段，客戶端向主節點發送請求，通信1次；在pre-prepare階段，主節點向其余節點發送預準備消息，總共通信N-1次；在prepare階段，每一個收到預準備消息的節點，向其余節點發送prepare消息，此過程通信次數為（N-1）2;在commit階段，每個節點向其余節點發送確認消息，總共通信N×（N-1）次；在reply階段，所有節點向客戶端發送回復消息，一共通信N次。由此可知，單次PBFT共識流程的總通信次數為

CPBFT=1+（N-1）+（N-1）2+N（N-1）+N=2N2-N+1（10）

2）單次Raft共識流程通信次數

若使用傳統的Raft共識算法進行一次共識，leader收到請求消息后，會向所有的follower發送消息，通信N-1次；然后follower會向leader返回處理消息，通信N-1次；日志復制會發生在下一次請求或者心跳中，故單獨計算通信次數。由此可知，單次Raft共識流程的總通信次數為

CRaft=（N-1）+（N-1）=2N-2（11）

3）單次DL_RBFT共識流程通信次數

若本文DL_RBFT共識算法進行一次共識，在上層共識網絡中，各組長進行PBFT共識，通信次數為2G2-G+1；在下層共識網絡的小組內部，leader先向監督節點和follower廣播消息，通信次數為N-1次；然后follower向leader和監督節點返回處理消息，通信2（N-2）次；最后監督節點對leader處理信息進行審查，通信次數為2。由此可知單次DL_RBFT共識流程的總通信次數為

CDL_RBFT=2G2-G+1+G［（N-1）+2（N-2）+2］=2G2+3N-4G+1（12）

由上述分析可得，DL_RBFT共識算法將PBFT的時間復雜度從O（N2）降為了O（N+G2）。圖8為不同節點數，PBFT、Raft和DL_RBFT共識算法的單次共識次數對比結果，其中展示了DL_RBFT共識算法將節點分為4組和5組的情況。

從圖8可以看出，隨著節點個數的增加，PBFT的通信次數急劇上升，當節點數為50時，需要近5 000次通信才能完成一次共識；而DL_RBFT和Raft共識算法的通信次數非常接近，且增長速度也非常緩慢。

因此，DL_RBFT共識算法顯著地降低了單次共識中的通信次數，并且隨著節點數增加，這種優勢相比于傳統PBFT算法更為顯著。

4 實驗及結果分析

本文實驗通過在一個設備上監聽多個不同的TCP端口，對PBFT共識算法、基于網絡自聚類PBFT算法（NAC-PBFT）［21］、基于主節點隨機選取的改進PBFT算法（RPBFT）［32］、基于節點分組信譽模型的改進PBFT算法（GR-PBFT）［33］以及本文DL_RBFT共識算法在共識延時和吞吐量進行對比分析，還對Raft的leader選舉效率和本文改進的選舉方案進行對比分析，實驗配置如表2所示。

4.1 共識時延測試

在區塊鏈中，共識時延指的是從客戶端提交交易請求開始，一直到完成確認所花費的時間，是評價共識算法性能的重要指標之一。在實驗中，共識時延的計算公式為

DT=timereq-timereply（13）

其中：timereply是客戶端發起請求的時間，timereq是客戶端收到足夠數量的節點回復的時間。將節點分成不同的組數，多次實驗求平均值作為共識時延，并且與PBFT共識算法和文獻［21，31，32］改進算法的時延作對比，結果如圖9、10所示。

從圖9可以看出，隨著節點數的增加，共識時延有不同程度的上升，其中PBFT系算法上升得格外迅速，但DL_RBFT算法的增長較為緩慢。當節點數為120時，PBFT的時延已經超過20 000 ms，三個改進PBFT算法均超過15 000 ms，而DL_RBFT算法的時延均不到3 000 ms，與PBFT算法相比，時延降低了近85%，與文獻［21，31，32］的改進算法相比，在大規模節點的環境下，DL_RBFT算法共識時延也降低了80%左右。因此DL_RBFT算法因其雙層共識網絡的特性，能在大規模節點網絡中保持較低的共識時延。

從圖10可以看出，在DL_RBFT算法中，將節點分成不同組數，共識時延會有細微差別，組數越少，時延起點越低，但增長速率越快，反之起點越高，但增長速率低；總體來說，時間復雜度都是O（n），算法的效率不會有太大差異，證明了DL_RBFT算法具有較強的健壯性和穩定性。

4.2 吞吐量測試

吞吐量是指系統在單位時間內處理的事務數量，在區塊鏈領域中常用每秒完成交易數（transactions per second，TPS）來衡量，假設在Δt的出塊時間內完成的交易數量為TransactionΔt，則吞吐量計算公式為

將節點分成不同的組數，多次實驗求平均值作為共識時延，并且與PBFT共識算法和文獻［21，31，32］的改進算法的吞吐量進行對比。對比結果如圖11、12所示。

從圖11可以看出，隨著節點數增加，幾種算法的TPS都呈現下降趨勢，但是PBFT算法的下降趨勢最快，在很短時間就趨近為0，而DL_RBFT算法的吞吐量下降速度很緩慢，盡管在節點數很少的情況下稍低于文獻［21，31，32］的改進算法的吞吐量，但是在本文研究的大規模節點的網絡中，仍有較好的吞吐量，這是PBFT算法與其余三種改進算法不具備的特性。因此，DL_RBFT算法適用于對吞吐量有著較高要求的聯盟鏈環境。

從圖12可以看出，將節點分成不同組數，組數不同，DL_RBFT算法的TPS也不同，但變化并不大，在大規模節點的使用環境中，仍然能保有一定的吞吐量，再次證明了DL_RBFT算法具有較強的健壯性和穩定性。

4.3 初始leader選擇效率

初始leader選擇效率是指在剛組成小組時，對正式組長選舉的效率。 在引入了聲譽機制和蟻群算法的選舉算法中，設置信息素和過往決策共占20%、40%和50%的權重，并與Raft中的傳統選擇機制進行對比，對比結果如圖13和14所示。

從圖13可以看出，隨著節點數增加，Raft原始的選舉機制所消耗的輪數增長得非常快，而引入了聲譽機制和蟻群算法的改進選舉機制則維持在一個小區間內，并且十分穩定。

從圖14也可以看出，改進后的選舉機制所消耗的時間與原來相比急劇下降，在120個節點的情況下，三種權重下的改進機制的耗時相比于原始機制都下降了50%左右，并且權重占比越高，所消耗時間越少。因此改進后的初始組長選舉機制更適用于大規模節點的情況，使得雙層共識網絡的構建更加迅速。

5 結束語

本文提出了一種基于改進Raft共識算法和PBFT共識算法的雙層共識算法——DL_RBFT。該算法很好地結合了PBFT抗拜占庭節點攻擊和Raft共識效率高的優點，并且引入監督機制、聲譽機制和蟻群算法改進選主流程，提高了算法效率，為共識過程中的安全性提供了保證。實驗結果證明，DL_RBFT通信次數、通信時延均優于PBFT算法，并且可擴展性更高，吞吐量更大，更適用于大規模網絡節點的環境，有效地突破了現有聯盟鏈的性能瓶頸。

未來將進一步完善算法的細節，提升性能，考慮結合跨鏈技術，進一步解決聯盟鏈中存在的問題。

參考文獻：

［1］Nakamoto S. Bitcoin： a peer-to-peer electronic cash system［EB/OL］. （2008）. https：//bitcoin.org/en/bitcoin-paper.

［2］Xu Min， Chen Xingtong， Kou Gang. A systematic review of blockchain［J］. Financial Innovation， 2019，5（1）： 1-14.

［3］Monrat A A， Schelén O， Andersson K. A survey of blockchain from the perspectives of applications， challenges， and opportunities［J］. IEEE Access， 2019，7： 117134-117151.

［4］Feng Tao， Liu Yufeng. Research on PoW protocol security under optimized long delay attack［J］. Cryptography， 2023，7（2）： 32.

［5］Cao Bin， Zhang Zhenghui， Feng Daquan， et al. Performance analysis and comparison of PoW， PoS and DAG based blockchains［J］. Digi-tal Communications and Networks， 2020，6（4）： 480-485.

［6］Platt M， McBurney P. Sybil in the haystack： a comprehensive review of blockchain consensus mechanisms in search of strong sybil attack resistance［J］. Algorithms， 2023，16（1）： 34.

［7］Zhang Rong， Chan W K V. Evaluation of energy consumption in block-chains with proof of work and proof of stake［J］. Journal of Physics： Conference Series， 2020，1584（1）： 012023.

［8］Bachani V， Bhattacharjya A. Preferential delegated proof of stake （PDPoS） —modified DPoS with two layers towards scalability and higher TPS［J］. Symmetry， 2022，15（1）： 4.

［9］Surjandari I， Yusuf H， Laoh E， et al. Designing a permissioned blockchain network for the Halal Industry using Hyperledger Fabric with multiple channels and the Raft consensus mechanism［J］. Journal of Big Data， 2021，8（1）： 1-16.

［10］Buchman E. Tendermint： Byzantine fault tolerance in the age of blockchains［D］.［S.l.］：University of Guelph， 2016.

［11］Zheng Xiandong， Feng Wenlong. Research on practical Byzantine fault tolerant consensus algorithm based on blockchain［J］. Journal of Physics： Conference Series， 2021，1802（3）： 032022.

［12］Gorkhali A， Li Ling， Shrestha A. Blockchain： a literature review［J］. Journal of Management Analytics， 2020，7（3）： 321-343.

［13］韋可欣， 李雷孝， 高昊昱，等. 區塊鏈訪問控制技術在車聯網中的應用研究綜述與展望［J］. 計算機工程與應用， 2023，59（24）：26-45. （Wei Kexin， Li Leixiao， Gao Haoyu， et al. Review and prospect of application research on blockchain access control technology in the Internet of Vehicles［J］. Computer Engineering and Applications， 2023，59（24）：26-45.

［14］Xu Xinhan， Chen Xiangfeng， Jia Fu， et al. Supply chain finance： a systematic literature review and bibliometric analysis［J］. International Journal of Production Economics， 2018，204： 160-173.

［15］Agbo C C， Mahmoud Q H， Eklund J M. Blockchain technology in healthcare： a systematic review［J］. Healthcare， 2019，7（2）：56.

［16］Jing Nan， Liu Qi， Sugumaran V. A blockchain-based code copyright management system［J］. Information Processing & Management， 2021，58（3）： 102518.

［17］Gai Keke， She Yufeng， Zhu Liehuang， et al. A blockchain-based access control scheme for zero trust cross-organizational data sharing［J］. ACM Trans on Internet Technology， 2022，23（3）： article No.38.

［18］Ni Shiying， Bai Xiwen， Liang Yuchen， et al. Blockchain-based traceability system for supply chain： potentials， gaps， applicability and adoption game［J］. Enterprise Information Systems， 2022，16（12）： 2086021.

［19］王謹東， 李強. 基于Raft算法改進的實用拜占庭容錯共識算法［J］. 計算機應用， 2023，43（1）： 122-129. （Wang Jindong， Li Qiang. A practical Byzantine fault tolerant consensus algorithm improved by Raft algorithm［J］. Journal of Computer Applications， 2023，43（1）： 122-129.）

［20］Seo J， Ko D， Kim S， et al. A coordination technique for improving scalability of Byzantine fault-tolerant consensus［J］. Applied Sciences， 2020，10（21）： 7609.

［21］高娜， 周創明， 楊春曉，等. 基于網絡自聚類的PBFT算法改進［J］. 計算機應用研究， 2021，38（11）： 3236-3242. （Gao Na， Zhou Chuangming， Yang Chunxiao， et al. Improvement of PBFT algorithm based on network self-clustering［J］. Application Research of Computers， 2021，38（11）： 3236-3242.）

［22］陳子豪， 李強. 基于K-medoids的改進PBFT共識機制［J］. 計算機科學， 2019，46（12）： 101-107. （Chen Zihao， Li Qiang. The improved PBFT consensus mechanism based on K-medoids［J］. Computer Science， 2019，46（12）： 101-107.）

［23］翟社平， 廉佳穎， 楊銳，等. 基于Raft分組的實用拜占庭共識算法［J］. 計算機應用研究， 2023，40（11）： 3218-3224，3234. （Zhai Sheping， Lian Jiaying， Yang Rui， et al. Practical Byzantine consensus algorithm based on Raft clustering［J］. Application Research of Computers， 2023，40（11）： 3218-3224，3234.）

［24］黃冬艷， 李浪， 陳斌，等. RBFT： 基于Raft集群的拜占庭容錯共識機制［J］. 通信學報， 2021，42（3）： 209-219. （Huang Dongyan， Li Lang， Chen Bin， et al.RBFT： Byzantine fault-tolerant consensus mechanism based on Raft clustering［J］. Journal on Communications， 2021，42（3）： 209-219.）

［25］Castro M， Liskov B. Practical Byzantine fault tolerance［C］//Proc of the 3rd Symposium on Operating Systems Design and Implementation.New York：ACM Press， 1999： 173-186.

［26］Li Wenyu， Feng Chenglin， Zhang Lei， et al. A scalable multi-layer PBFT consensus for blockchain［J］. IEEE Trans on Parallel and Distributed Systems， 2020，32（5）： 1146-1160.

［27］Ongaro D， Ousterhout J. In search of an understandable consensus algorithm［C］//Proc of USENIX Annual Technical Conference. 2014： 305-319.

［28］秦小林， 羅剛， 李文博，等. 集群智能算法綜述［J］. 無人系統技術， 2021，4（3）： 1-10. （Qin Xiaolin， Luo Gang， Li Wenbo， et al. An overview of cluster intelligence algorithms［J］. Unmanned Systems Technology， 2021，4（3）： 1-10.）

［29］Dorigo M， Gambardella L M. Ant colony system： a cooperative lear-ning approach to the traveling salesman problem［J］. IEEE Trans on Evolutionary Computation， 1997，1（1）： 53-66.

［30］Fox A， Brewer E A. Harvest， yield， and scalable tolerant systems［C］//Proc of the 7th Workshop on Hot Topics in Operating Systems. Piscataway，NJ：IEEE Press， 1999： 174-178.

［31］Pritchett D. BASE： an acid alternative： in partitioned databases， trading some consistency for availability can lead to dramatic improvements in scalability［J］. Queue， 2008，6（3）： 48-55.

［32］王森， 李志淮， 賈志鵬. 主節點隨機選取的改進PBFT共識算法［J］. 計算機應用與軟件， 2022，39（10）： 299-306. （Wang Sen， Li Zhihuai， Jia Zhipeng. Improved PBFT consensus algorithm with random primary node selection［J］. Computer Applications and Software， 2022，39（10）： 299-306.）

［33］陳蘇明， 王冰， 陳玉全，等. 基于節點分組信譽模型的改進PBFT共識算法［J］. 計算機應用研究， 2023， 40（10）： 2916-2921. （Chen Suming， Wang Bing， Chen Yuquan， et al. Byzantine fault-tolerant consensus mechanism based on Raft clustering［J］. Application Research of Computers， 2023，40（10）： 2916-2921.）