基于Raft算法改進的實用拜占庭容錯共識算法

王謹東，李 強

（四川大學 計算機學院，成都 610065）

0 引言

區(qū)塊鏈作為以比特幣［1］為代表的眾多數(shù)字貨幣的底層技術支撐，近年來受到廣泛關注并逐漸應用到眾多領域。區(qū)塊鏈的本質是網絡中的各個節(jié)點在分布式的環(huán)境下，借助密碼學、共識算法、利用智能合約操作數(shù)據的一種鏈式數(shù)據結構。作為一種全新的分布式計算范式，區(qū)塊鏈提供了去中心化、不可篡改、透明、可溯源的分布式數(shù)據庫解決方案［2］。

根據節(jié)點準入機制的不同，可將區(qū)塊鏈分為公有鏈（Public blockchain）、聯(lián)盟鏈（Consortium blockchain）、私有鏈（Private blockchain）三類［3］。其中，聯(lián)盟鏈具有一定的準入門檻，節(jié)點需要授權才能加入區(qū)塊鏈網絡，是多中心化的區(qū)塊鏈，也是未來區(qū)塊鏈發(fā)展的重要方向［4］。聯(lián)盟鏈目前在數(shù)據存儲［5］、版權管理［6］、隱私保護［7］、數(shù)據溯源［8］等方面已有眾多的應用。在大多數(shù)情況下，聯(lián)盟鏈不需要設計激勵層來推動“挖礦”和智能合約的執(zhí)行，降低了系統(tǒng)部署和維護的成本；同時，以Hyperledger Fabric［9］為代表的眾多企業(yè)級區(qū)塊鏈平臺支持可插拔的共識算法、多種語言編寫智能合約，進一步推動了大量基于聯(lián)盟鏈的應用落地。然而，聯(lián)盟鏈仍然面臨可擴展性差的問題。目前在聯(lián)盟鏈應用廣泛的實用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）［10］共識算法雖然不需要消耗大量算力，但隨著節(jié)點數(shù)量的增長，其通信開銷會呈平方級增長，導致共識效率較低。在金融、智慧城市、供應鏈管理等領域對區(qū)塊鏈的性能與可擴展性要求較高，通常要求單鏈到達萬級吞吐量、千級節(jié)點組網能力、秒級交易確認時延，PBFT 算法難以滿足這些領域的需求［11］。同時，PBFT 算法的網絡結構相對靜態(tài)，動態(tài)添加節(jié)點時必須重啟整個系統(tǒng)［12］，嚴重影響系統(tǒng)的可用性。不難發(fā)現(xiàn)，PBFT 算法目前已不能滿足部分應用場景的需求，一定程度限制了聯(lián)盟鏈的進一步發(fā)展。共識算法作為區(qū)塊鏈的核心技術，對區(qū)塊鏈的交易確認時延、吞吐量、可擴展性有著決定性的影響，對PBFT 算法進行改進能夠有效解決上述問題。

針對PBFT 共識算法存在的問題，文獻［13］提出了一種基于協(xié)調器的共識算法，通過協(xié)調器將交易分類處理，并只對異常交易執(zhí)行完整的共識，將該算法應用于PBFT 后，獲得了使共識時延縮短為原來的21%；但可能會面臨協(xié)調器單點故障導致系統(tǒng)失效的問題。文獻［14］將區(qū)塊鏈分片，在分片內部與分片之間分別執(zhí)行PBFT 算法，使共識效率提升了20%，提升了系統(tǒng)的可擴展性；但是這種算法可能導致整個區(qū)塊鏈網絡中的數(shù)據不一致。文獻［15］提出了一種基于特定硬件的PBFT 共識算法，所有節(jié)點使用硬件芯片（如Intel SGX）構建可信執(zhí)行環(huán)境（Trusted Execution Environment，TEE），并利用消息聚合技術使算法的通信開銷大幅降低；雖然這種算法提升了PBFT 算法的可擴展性，但需要所有節(jié)點都具備相同的硬件環(huán)境，在實際應用中具有一定的局限性。文獻［16］提出了一種基于EigenTrust 信任模型的PBFT 算法，通過各節(jié)點的行為來評估節(jié)點的信任度，選擇高質量的節(jié)點構建共識組以降低視圖切換概率；但這種算法在共識中的通信復雜度與PBFT 算法相同，難以顯著地提升PBFT 算法的可擴展性。文獻［17］提出了一種基于分片型區(qū)塊鏈的共識算法RapidChain，其Decentralized Bootstrapping 階段將參與共識的節(jié)點劃分為多個共識委員會。RapidChain 改進了PBFT 算法，將PBFT 算法與ErasureCode、IDA-Gossip 消息傳遞協(xié)議結合，原消息被分割為若干個片段在網絡中傳播，各節(jié)點收到消息后通過ErasureCode 恢復原消息以減少通信量。

僅對PBFT 算法進行改進并不能從根本上解決PBFT 算法存在的問題，當節(jié)點數(shù)量增加時，三階段提交過程會使其性能大幅降低。因此，本文提出了一種基于Raft 算法改進的實用拜占庭容錯共識算法K-RPBFT（K-medoids Raft based Practical Byzantine Fault Tolerance）。首先，以節(jié)點之間的通信時延作為歐氏距離，利用K-medoids 聚類算法將區(qū)塊鏈分片；其次，每個分片的主節(jié)點之間使用PBFT 算法進行共識，在分片內部使用基于監(jiān)督節(jié)點改進的Raft 算法進行共識。該算法大幅降低了PBFT 算法的通信開銷與共識時延，提升了吞吐量，并且使系統(tǒng)擁有動態(tài)的網絡結構。本文的主要工作如下：

1）提出了一種帶監(jiān)督節(jié)點的拜占庭容錯共識算法K-RPBFT，闡述了K-RPBFT 算法的分片策略、監(jiān)督機制、共識流程。

2）對K-RPBFT 算法的安全性、一致性、活性進行了分析，以證明K-RPBFT 算法的有效性。

3）通過實驗對K-RPBFT 算法進行了評估，與PBFT 算法、Raft 算法在單次共識通信次數(shù)、共識時延、吞吐量等方面進行了對比。

1 相關背景

1.1 PBFT算法

PBFT 算法由Castro 等［10］于1999 年提出，最初被用于構建支持拜占庭容錯的分布式系統(tǒng)，能夠在系統(tǒng)內拜占庭節(jié)點數(shù)量（n為節(jié)點總量）的情況下保證系統(tǒng)的可用性。隨著區(qū)塊鏈技術的不斷發(fā)展，PBFT 算法常被用于聯(lián)盟鏈中節(jié)點的共識過程。

PBFT 算法的共識過程包含請求（request）、預準備（preprepare）、準備（prepare）、提交（commit）、回復（reply）等階段。主節(jié)點（Leader）在收到客戶端的請求消息后，將會生成預準備消息并廣播給所有從節(jié)點（replica）。從節(jié)點在收到預準備消息并且通過驗證后，將向所有節(jié)點發(fā)送準備消息。當從節(jié)點收到2f個不同節(jié)點（不包括自己）的有效準備消息時，將會向其他節(jié)點廣播確認消息。此時節(jié)點將會收集所有的確認消息，當收到2f+1 個來自不同節(jié)點的有效確認消息時，此請求消息將會被提交，同時向客戶端發(fā)送回復消息。當客戶端收到f+1 個不同節(jié)點的有效回復消息后，會認為一次共識成功。PBFT 算法的共識流程如圖1 所示。

圖1 PBFT算法的共識流程Fig.1 Consensus flow of PBFT algorithm

當從節(jié)點檢測到主節(jié)點失效或為拜占庭節(jié)點時，將觸發(fā)視圖切換（view-change）協(xié)議重新選舉主節(jié)點。在PBFT 算法中，主節(jié)點按照編號輪流當選。視圖切換協(xié)議保證了即使主節(jié)點為拜占庭節(jié)點，系統(tǒng)仍能正常工作。

PBFT 是一個三階段提交算法，從節(jié)點之間的相互驗證導致PBFT 的通信復雜度為O(N2)，使得算法的可擴展性不強，在具有大規(guī)模節(jié)點的區(qū)塊鏈系統(tǒng)下，可能會導致網絡風暴。

1.2 Raft算法

Raft 算法由Ongaro 等［18］于2014 年提出，是一種相較于Paxos［19］更易理解與實現(xiàn)的共識算法。Raft 的核心由日志復制與領導者選舉兩部分構成，節(jié)點的狀態(tài)將會根據不同的條件在領導者（Leader）、跟隨者（Follower）、候選者（Candidate）之間變遷。系統(tǒng)在任意時刻只擁有1 個領導者，并與所有跟隨者之間維持周期性的心跳消息。當跟隨者超時仍未收到領導者的心跳消息時，將會轉變?yōu)楹蜻x者狀態(tài)。候選者將會向其他節(jié)點發(fā)送投票請求消息，申請成為新的領導者，如果此候選者在超時前收到超過半數(shù)節(jié)點的確認消息，則轉換為領導者。節(jié)點狀態(tài)的詳細變遷過程如圖2 所示。

圖2 Raft算法的節(jié)點狀態(tài)變遷過程Fig.2 Node state transition process of Raft algorithm

在日志復制階段，所有的交易均由領導者打包生成區(qū)塊并向所有的跟隨者廣播，在收到超過一半的跟隨者回復后，領導者將會向所有節(jié)點發(fā)送確認信息，此時該區(qū)塊將會被提交上鏈。

Raft 算法的通信復雜度為O(N)，共識效率較高，具有良好的擴展性。Raft 算法在系統(tǒng)內不超過一半的節(jié)點宕機時仍能正常工作，但是不支持拜占庭容錯，因此通常應用于節(jié)點完全可信的私有鏈中。

2 K-RPBFT算法模型

本文結合PBFT 算法的拜占庭容錯特性與Raft 算法的高效性，提出一種帶監(jiān)督節(jié)點的分片區(qū)塊鏈共識算法K-RPBFT。在區(qū)塊鏈中引入若干監(jiān)督節(jié)點，基于K-medoids聚類算法將區(qū)塊鏈分片，令分片數(shù)量K等于監(jiān)督節(jié)點數(shù)量，并為每個分片分配一個監(jiān)督節(jié)點。在分片內部使用改進的Raft 算法進行共識，在每個分片的Raft 領導者之間使用PBFT算法進行共識。

2.1 K-RPBFT分片策略

K-medoids 算法是一種常見的無監(jiān)督聚類算法，初始的聚類中心點限定在樣本點中，且K-medoids 對于樣本中噪聲的魯棒性相較于K-means 等算法更好［20］，因此基于K-medoids 算法對區(qū)塊鏈網絡進行分片，具體過程如下。

1）節(jié)點探測。

定義區(qū)塊鏈網絡中的節(jié)點集合V={v1，v2，…，vn}，對于?vi∈V，在初始分片時向節(jié)點集合V中的所有節(jié)點發(fā)送探測消息PING，vi，timestampi，signi，其中PING 為探測消息標識，vi為節(jié)點編號，timestampi為探測消息發(fā)送時的時間戳，signi為消息簽名。?vj∈V(i≠j)，收到此探測消息后將會記錄時間戳timestampji，并驗證消息的合法性，通過驗證后則由式（1）計算出節(jié)點vi到vj的單向距離。

節(jié)點vj將d(vi，vj) 記錄到本地并構造回復消息REPLY，vj，d(vi，vj)，signj發(fā)送給vi，其中REPLY 為回復消息標識，vj為節(jié)點編號，d(vi，vj)為單向距離，signj為消息簽名。

當探測結束后，所有節(jié)點將會計算出一個全局一致的距離矩陣：

其中dij(1 ≤i≤n，1 ≤j≤n)由式（3）計算：

2）初始分片。

使用K-medoids 算法將節(jié)點聚類為K個簇，并使K等于區(qū)塊鏈網絡中監(jiān)督節(jié)點的數(shù)量。用Ci表示每個簇，在每一輪迭代過程中，Ci都有一個當前聚類的簇中心節(jié)點ni，定義所有的簇中心節(jié)點集合N={n1，n2，…，nK}。根據距離矩陣D，構建節(jié)點vi的隸屬函數(shù)：

根據隸屬函數(shù)可以得到迭代的目標函數(shù)：

根據K-medoids 算法流程，在節(jié)點集合V中隨機選取K個節(jié)點作為初始聚類中心節(jié)點。根據式（4）將剩余節(jié)點分配到相應的簇中心。在每個簇中，計算每個節(jié)點對應的準則函數(shù)，選擇準則函數(shù)最小時的節(jié)點作為新的簇中心。重復迭代上述過程直至所有的簇中心不再發(fā)生變化。

當K-medoids 算法迭代收斂后，此時的目標函數(shù)值最小。按照迭代生成的聚類結果將區(qū)塊鏈劃分為K個分片，簇中心節(jié)點作為分片的領導者，其余的節(jié)點作為跟隨者，并為每個分片分配監(jiān)督節(jié)點。在所有的簇中心節(jié)點之間執(zhí)行“片間共識”，在每個簇內部執(zhí)行“片內共識”。此時分片區(qū)塊鏈的模型結構如圖3 所示。

圖3 分片區(qū)塊鏈模型Fig.3 Model of sharding-based blockchain

3）重分片。

區(qū)塊鏈網絡的運行過程中，可能會存在節(jié)點動態(tài)加入或退出的情況。K-RPBFT 分片模型所使用的節(jié)點探測與K-medoids 算法的迭代過程均需要消耗資源。為了更好地控制分片過程的資源消耗，引入重分片上限閾值與重分片下限閾值參數(shù)。節(jié)點動態(tài)加入區(qū)塊鏈時，將直接加入節(jié)點數(shù)量最少的分片中，當有節(jié)點加入或退出區(qū)塊鏈網絡時，都會對每個分片的節(jié)點數(shù)量進行檢查，若某一分片的節(jié)點數(shù)量大于重分片上限閾值或者小于重分片下限閾值時，將會按照分片模型重新進行區(qū)塊鏈分片。定義穩(wěn)定系數(shù)S為重分片上限閾值與重分片下限閾值之差：當S較大時，區(qū)塊鏈的各節(jié)點結構較為穩(wěn)定，不會頻繁發(fā)生重分片，但隨著節(jié)點地不斷加入或退出，可能會導致區(qū)塊鏈的分片方式與理論最優(yōu)分片方式出現(xiàn)一定偏差；當S較小時，區(qū)塊鏈的結構更容易反映真實的聚類情況，但資源消耗較高。在實際應用中，可設置不同的穩(wěn)定系數(shù)以滿足算法在不同場景下的需求；同時，傳統(tǒng)的PBFT 算法并不支持節(jié)點動態(tài)加入，新的節(jié)點加入時系統(tǒng)必須重啟，而每個分片內部使用的Raft 算法賦予了系統(tǒng)動態(tài)添加或刪除節(jié)點的能力，提高了系統(tǒng)的靈活性，使系統(tǒng)具有動態(tài)的網絡結構。

2.2 片內共識與監(jiān)督機制

在分片內部，如果進行Raft 共識的領導者為拜占庭節(jié)點，向分片中的跟隨者發(fā)送錯誤的數(shù)據，將會導致此分片與系統(tǒng)中其他分片的數(shù)據不一致。為了預防“單片接管攻擊（Single-shard takeover attack）”，監(jiān)督節(jié)點將會參與片內共識，并在適當?shù)臅r機觸發(fā)Raft 算法的Leader election 協(xié)議，賦予了Raft 算法一定的拜占庭容錯的能力。片內共識的詳細過程如下：

1）領導者廣播區(qū)塊。

領導者將區(qū)塊、領導者編號、消息簽名等信息寫入AppendEntries RPC 的entries 域中，向分片內所有節(jié)點廣播。

2）監(jiān)督節(jié)點收集區(qū)塊。

與傳統(tǒng)的Raft算法不同的是，分片內的跟隨者收到領導者的同步請求后不會立即響應，而是將收到的消息發(fā)送給監(jiān)督節(jié)點，等待監(jiān)督節(jié)點的確認消息。監(jiān)督節(jié)點收到領導者的數(shù)據后將會檢查區(qū)塊中的交易集是否一致，當在超時時間內收到超過3n/4（n為分片內節(jié)點數(shù)量）個交易集一致的區(qū)塊并且與領導者發(fā)送的區(qū)塊中的交易集一致，則進入監(jiān)督節(jié)點驗證環(huán)節(jié)，否則觸發(fā)執(zhí)行Leader election協(xié)議，并重新執(zhí)行片內共識。

3）監(jiān)督節(jié)點驗證。

監(jiān)督節(jié)點通過安全散列算法（Secure Hash Algorithm，SHA）［21］計算區(qū)塊中交易集的信息摘要，向所有分片的監(jiān)督節(jié)點廣播驗證消息，其 中CHECK 為驗證消息標識，ci為監(jiān)督節(jié)點編號，digi為當前區(qū)塊的交易集信息摘要，timestampi為時間戳，termi為當前分片的領導者節(jié)點任期。

當前監(jiān)督節(jié)點也會相應地收到來自其他監(jiān)督節(jié)點的驗證消息。監(jiān)督節(jié)點將檢查收到的驗證消息的合法性，并判斷其中的信息摘要與當前分片領導者廣播的區(qū)塊交易集的信息摘要是否相等。若相等，則說明這兩個監(jiān)督節(jié)點所管理分片的領導者下發(fā)了一致的數(shù)據，當前監(jiān)督節(jié)點維護的有效驗證消息數(shù)量加1；若監(jiān)督節(jié)點在超時時間內收到超過K/2 個有效的驗證消息，則向當前分片的所有跟隨者發(fā)送確認消息，否則發(fā)送領導者重選消息；若監(jiān)督節(jié)點發(fā)現(xiàn)此分片的領導者下發(fā)的數(shù)據與其他大多數(shù)分片的領導者不一致時，將向分片內的所有節(jié)點發(fā)送領導者重選消息。

4）區(qū)塊提交。

若分片內的節(jié)點收到了監(jiān)督節(jié)點的確認消息，則繼續(xù)執(zhí)行Raft 算法的余下流程，收到領導者的commit 消息時提交日志并將區(qū)塊上鏈，否則將會執(zhí)行Leader election 協(xié)議，并重新執(zhí)行片內共識。片內共識流程如圖4 所示。

圖4 片內共識流程Fig.4 Flow of intra-shard consensus

2.3 K-RPBFT共識流程

客戶端發(fā)送至主節(jié)點的若干交易被打包成一個區(qū)塊，等待完成共識后上鏈。

定義分片數(shù)量為K=3f+1，PBFT 主節(jié)點編號為p，PBFT 從節(jié)點編號為i，當前視圖編號為vId，請求編號為rId，客戶端請求消息為msg，dig(msg)為請求消息msg的摘要，為節(jié)點p對msg進行數(shù)字簽名，timestamp為時間戳，client為客戶端編號，res為請求的執(zhí)行結果。

K-RPBFT 算法的共識流程如下：

1）區(qū)塊鏈分片。按照2.1 節(jié)中的分片策略將區(qū)塊鏈分為K個片，開始等待共識。

2）客戶端請求階段?？蛻舳税l(fā)送msg到聚類中心節(jié)點的主節(jié)點（即PBFT 共識集群的主節(jié)點），開始進行片間共識。

3）PBFT 預準備階段。PBFT 共識集群的主節(jié)點向PBFT從節(jié)點廣播預準備消息

4）PBFT 準備階段。PBFT 從節(jié)點會對收到的預準備消息進行檢查，若預準備消息不合法則丟棄。通過檢查后，從節(jié)點向其他 PBFT 共識節(jié)點廣播準備消息，當節(jié)點收到至少2f個不同的PBFT 共識節(jié)點的準備消息，且通過合法性檢查后，執(zhí)行PBFT 確認階段。

5）PBFT 確認階段。當前節(jié)點向所有PBFT 共識節(jié)點廣播確認消息，同時此節(jié)點將會收到其他節(jié)點的確認消息，檢查消息簽名、視圖編號、消息序號合法并收到至少2f+1 個不同節(jié)點的有效確認消息時，片間共識完成，開始進行片內共識。

6）片內共識階段。此時PBFT 共識節(jié)點將作為分片的領導者，執(zhí)行基于Raft 算法改進的片內共識算法，片內的共識流程見2.2 節(jié)。跟隨者完成共識后，向領導者反饋消息，當領導者收到超過一半的跟隨者節(jié)點反饋后，確認片內達成共識，此領導者進入PBFT 提交階段。

7）PBFT 提交階段。當PBFT 節(jié)點所屬的分片內部共識完成后，此節(jié)點向客戶端發(fā)送回復消息

K-RPBFT 算法共識的完整流程如圖5 所示。

圖5 K-RPBFT算法的共識流程Fig.5 Consensus flow of K-RPBFT algorithm

3 算法分析

K-RPBFT 算法作為一種面向聯(lián)盟鏈的共識算法，需要在系統(tǒng)具有少量拜占庭節(jié)點的情況下工作。本章對算法的安全性、一致性、活性進行了分析，并對K-RPBFT 算法、PBFT 算法、Raft 算法的通信次數(shù)進行了分析與對比。K-RPBFT 算法一定程度上繼承了PBFT 算法與Raft 算法的安全性、一致性與活性；同時，監(jiān)督節(jié)點的引入進一步增強了K-RPBFT 算法的安全性與活性。

3.1 安全性

在片間共識中，PBFT 算法自身的三階段提交過程保證了在拜占庭節(jié)點數(shù)量小于2/3 時的安全性。如果PBFT 從節(jié)點在共識過程中檢測到主節(jié)點異常（不響應客戶端請求、故意發(fā)送錯誤的請求）時，將會執(zhí)行視圖切換協(xié)議重新選擇主節(jié)點。

在片內共識中，監(jiān)督節(jié)點保證了Raft 算法在系統(tǒng)中含有拜占庭節(jié)點時的安全性。由于監(jiān)督節(jié)點將會與其他分片的監(jiān)督節(jié)點進行相互驗證，如果分片的領導者向整個分片廣播了錯誤的消息，監(jiān)督節(jié)點將不會向分片中的跟隨者發(fā)送確認消息，同時罷免當前領導者并觸發(fā)Leader election 協(xié)議以確保鏈上信息的正確性；如果領導者向分片發(fā)起了一個并不存在的區(qū)塊同步請求，監(jiān)督節(jié)點在發(fā)出驗證消息后，經過超時時間仍未收到足夠的由其他監(jiān)督節(jié)點發(fā)出的驗證消息時，將重置超時時間并觸發(fā)Leader election 協(xié)議重選領導者；如果Raft 主節(jié)點故意攔截區(qū)塊同步請求，監(jiān)督節(jié)點在陸續(xù)收到其他監(jiān)督節(jié)點的驗證消息時，會感知到主節(jié)點異常，進而觸發(fā)Leader election 協(xié)議重新選舉領導者。

這里對片內共識的拜占庭容錯性進行討論。設分片內的節(jié)點數(shù)量為n，拜占庭節(jié)點數(shù)量為f。拜占庭節(jié)點在收到領導者的消息m后，可能對其作出錯誤的共識（不處理m或將m替換為偽造消息m′），并且向監(jiān)督節(jié)點發(fā)送含有正確消息m的區(qū)塊以欺騙監(jiān)督節(jié)點。因此監(jiān)督節(jié)點收到的x個交易集一致的區(qū)塊中可能含有f個拜占庭節(jié)點發(fā)送的區(qū)塊，為了確保超過一半的誠實節(jié)點收到正確消息m，則x應滿足：

由前文可知，x=3n/4，即：

因此，監(jiān)督節(jié)點的存在能保證分片內拜占庭節(jié)點數(shù)量小于n/4 時共識的正常進行。

對于監(jiān)督節(jié)點自身而言，由于不能動態(tài)加入區(qū)塊鏈，且由上層監(jiān)督者進行指定，因而只存在監(jiān)督宕機的情況。分片內的從節(jié)點將與監(jiān)督節(jié)點之間保持定期的心跳消息以確認監(jiān)督節(jié)點存活，當超時無響應時會觸發(fā)重分片，縮減分片數(shù)量以保證每個分片至少有一個可用的監(jiān)督節(jié)點。同時，監(jiān)督節(jié)點之間的通信以及監(jiān)督節(jié)點與片內節(jié)點之間的通信均采用數(shù)字簽名技術［22］以防止消息偽造。

3.2 一致性

根據CAP 定理［23］，在一個分布式系統(tǒng)中，一致性（Consistency）、可用性（Availability）、分區(qū)容忍性（Partition tolerance）最多只能同時滿足其中兩項。而為了保證系統(tǒng)的高可用，通常根據BASE（Basically Available，Soft state，Eventually consistent）即（基本可用、軟狀態(tài)、最終一致性）理論［24］來構建分布式系統(tǒng)。這里的一致性即指最終一致性而并非強一致性。

在片間共識中，PBFT 算法保證了在拜占庭節(jié)點數(shù)量小于節(jié)點總量1/3 時的一致性。在分片內部，Raft 算法的Log Replication 過程保證了片內共識的最終一致性，領導者將通過AppendEntries RPC 將日志同步到跟隨者，并在收到大多數(shù)跟隨者的反饋后提交日志。即使有部分節(jié)點宕機，在恢復后通過日志復制也能保證所有節(jié)點數(shù)據的最終一致性。

3.3 活性

PBFT 算法的view-change 協(xié)議提供了保證了K-RPBFT 片間共識的活性。當PBFT 主節(jié)點無法響應客戶端請求時，會通過p=vIdmodK確定新的主節(jié)點編號以推動共識的繼續(xù)進行，其中vId為當前視圖編號，K為PBFT 共識節(jié)點數(shù)量。此外，進行PBFT共識的節(jié)點將同時作為片間Raft共識的領導者，而Raft跟隨者會與領導者之間通過心跳消息保持聯(lián)系，若超時未響應將觸發(fā)Leader election 協(xié)議進行領導者重選，新的領導者將替換失效的領導者參加PBFT 共識，加快了PBFT 算法對失效節(jié)點的檢測與替換，增強了PBFT 算法的活性。

Raft 算法的Leader election 協(xié)議保證了片內共識算法的活性，當跟隨者超時仍未收到領導者的心跳消息時，將轉變?yōu)楹蜻x者狀態(tài)以進行新的領導者選舉，新的領導者將替換原有已失效的領導者，保證共識的繼續(xù)進行。

3.4 通信開銷分析

本節(jié)對K-RPBFT 算法單次共識所需的通信次數(shù)與傳統(tǒng)的PBFT 算法和Raft 算法進行對比。為便于分析，假設區(qū)塊鏈的分片數(shù)量為K(K≥4)，每個分片的節(jié)點數(shù)量為n(n≥3)，可得系統(tǒng)中的總節(jié)點數(shù)：

1）PBFT 單次共識的通信次數(shù)。

若系統(tǒng)中的節(jié)點使用PBFT 算法進行一次共識，在預準備階段主節(jié)點將向所有從節(jié)點發(fā)送預準備消息，此過程的通信次數(shù)為(N-1)。在準備階段，每一個從節(jié)點將向其余節(jié)點發(fā)送準備消息，此過程的通信次數(shù)為(N-1)*(N-1)；在確認階段，所有節(jié)點將向其他節(jié)點發(fā)送確認消息，此過程的通信次數(shù)為N*(N-1)；在回復階段，參與共識的節(jié)點將向客戶端發(fā)送回復消息，此過程的通信次數(shù)為N。因此可以得到PBFT 單次共識的通信次數(shù)：

2）Raft 單次共識的通信次數(shù)。

若系統(tǒng)中的節(jié)點使用Raft 算法進行一次共識，在Log Replication 階段，領導者向所有跟隨者發(fā)送包含一個區(qū)塊的日志記錄，此過程的通信次數(shù)為N-1。跟隨者在收到領導者的日志記錄后，向領導者發(fā)送回復消息，此過程的通信次數(shù)為N-1；領導者在收到超過一半的跟隨者的回復消息后，向發(fā)送客戶端回復消息，并向所有跟隨者發(fā)送確認消息以將此區(qū)塊提交上鏈，此過程的通信次數(shù)為N。因此可以得到Raft 單次共識的通信次數(shù)：

3）K-RPBFT 單次共識的通信次數(shù)。

若系統(tǒng)中的節(jié)點使用K-RPBFT 算法進行一次共識，在片間進行PBFT 共識的通信次數(shù)為2K2-K。對于單個分片內部，領導者首先向所有跟隨者以及監(jiān)督節(jié)點廣播區(qū)塊，此過程的通信次數(shù)為n；然后監(jiān)督節(jié)點將收集所有跟隨者的區(qū)塊，此過程的通信次數(shù)為(n-1)。在監(jiān)督節(jié)點驗證階段，監(jiān)督節(jié)點將向其余分片的監(jiān)督節(jié)點廣播驗證消息，此過程的通信次數(shù)為(K-1)；在提交階段，監(jiān)督節(jié)點將向所有跟隨者發(fā)送確認消息，然后跟隨者向領導者發(fā)送消息，此過程的通信次數(shù)為2(n-1)。因此可以得到K-RPBFT 單次共識的通信次數(shù)：

由分析可知，相較于PBFT 單次共識O(N2)的通信復雜度，K-RPBFT 的通信復雜度僅為O(N+K2)。圖6 為不同節(jié)點數(shù)量下算法的單次共識通信次數(shù)對比?？梢钥闯?，隨著節(jié)點數(shù)量的增加，PBFT 算法的單次共識通信次數(shù)將大幅增加，當節(jié)點數(shù)量為40 時，需要進行超過3 000 次通信才能達成共識。K-RPBFT 的單次共識通信次數(shù)與Raft 算法非常相近，遠小于PBFT 算法且增長十分緩慢。

圖6 通信次數(shù)對比Fig.6 Comparison of communication times

表1 為節(jié)點數(shù)量N為100 時K-RPBFT 的通信次數(shù)，當分片數(shù)量為4 時取得最小通信次數(shù)428，而此時PBFT 算法完成一次共識需要進行19 900 次通信。隨著分片數(shù)量的增多，片間參與PBFT 共識的節(jié)點數(shù)量將會相應增多，導致K-RPBFT算法單次共識的通信次數(shù)上升，但仍遠小于PBFT 算法。

表1 節(jié)點數(shù)量為100時K-RPBFT算法的通信次數(shù)Tab.1 Communication times of K-RPBFT algorithm when the number of nodes is 100

因此，K-RPBFT 顯著降低了單次共識的通信次數(shù)，當系統(tǒng)中具有100 個節(jié)點時，相較于PBFT 算法，K-RPBFT 能使通信次數(shù)降低兩個數(shù)量級，且隨著節(jié)點總量的增加，這種優(yōu)勢將更加明顯。

4 仿真實驗

為了驗證K-RPBFT 算法的有效性，本文使用Netty 4.1.42 作為網絡通信組件，Java 作為編程語言實現(xiàn)了本算法，通過在同一設備上監(jiān)聽多個不同的TCP 端口模擬多節(jié)點環(huán)境。本章從共識時延、吞吐量等方面與PBFT 算法、Raft 算法進行了比較。此外，由于RapidChain 共識算法在性能和安全性上已經達到了較好的效果，因此本章對K-RPBFT 與Rapidchain 進行了對比。

4.1 共識時延測試

共識時延是衡量算法性能的重要指標，指客戶端發(fā)起請求到區(qū)塊被確認上鏈所需的時間。在實驗中K-RPBFT 共識時延的計算公式為：

式中：Timereq表示客戶端發(fā)起共識請求的時刻，Timereply表示客戶端收到足夠的PBFT 回復消息的時刻。

取多次實驗數(shù)據的平均值作為共識時延，并與PBFT 算法、Raft 算法進行對比。算法的共識時延對比測試結果如圖7 所示。由圖7 可知，三種算法的共識時延隨著節(jié)點數(shù)量的增加均逐漸增大，但K-RPBFT 與Raft 的時延增加較為緩慢，PBFT 的時延增加較為劇烈。K-PBFT 算法的共識時延與Raft相近，當節(jié)點數(shù)量為12 時，PBFT 的共識時延約為K-RPBFT的2.5 倍，而當節(jié)點數(shù)量增加到40 時，PBFT 的共識時延超過了K-RPBFT 的4.5 倍。因此K-RPBFT 算法在大規(guī)模節(jié)點的環(huán)境下能顯著降低共識時延。

圖7 共識時延對比Fig.7 Comparison of consensus latency

4.2 吞吐量測試

吞吐量指系統(tǒng)在單位時間內處理的事務數(shù)量，在區(qū)塊鏈領域中通常用每秒完成的交易數(shù)量（Transactions Per Second，TPS）來計算，即：

其中：Δt為出塊時間，TransactionΔt為出塊時間內處理的交易總量。吞吐量不僅與節(jié)點數(shù)量有關，還與區(qū)塊中包含的交易數(shù)量有關，因此進行兩組不同的實驗對算法的吞吐量進行驗證。

實驗一 將每個區(qū)塊中包含的交易數(shù)量固定為1 000，將系統(tǒng)中參加共識的節(jié)點設置為12～36，取多次實驗數(shù)據的平均值作為吞吐量實驗結果，并與PBFT 算法、Raft 算法進行對比，實驗結果如圖8 所示。由圖8 可以看出，算法的吞吐量均隨著節(jié)點數(shù)量的增加而呈下降趨勢，但K-RPBFT 算法的吞吐量仍然遠高于PBFT 算法，且與Raft 算法相近。

圖8 不同節(jié)點數(shù)量下的吞吐量對比Fig.8 Comparison of throughput under different node numbers

實驗二 將系統(tǒng)中參加共識的節(jié)點固定為12 個，將每個區(qū)塊中包含的交易數(shù)量設置為1 000～4 000，取多次實驗數(shù)據的平均值作為吞吐量實驗結果，并與PBFT 算法、Raft 算法進行對比，實驗結果如圖9 所示。由圖9 可以看出，K-RPBFT算法的吞吐量與Raft 算法較為接近。當區(qū)塊中的交易數(shù)量沒有超過節(jié)點的處理能力時，各算法的吞吐量均隨著交易量的增加而提升。交易數(shù)量為1 000，K-RPBFT 算法相較于PBFT 算法能夠提升700 左右的吞吐量，且隨著交易數(shù)量的增加，吞吐量的提升更加明顯。吞吐量的最大值在交易量為3 000 左右時取得，此時K-RPBFT 的吞吐量約為PBFT 的3.5倍。受限于實驗設備的處理能力，當區(qū)塊中的交易數(shù)量超過3 000 時，此時繼續(xù)向區(qū)塊中增加交易將會使算法的吞吐量均有所下降，但K-RPBFT 算法的吞吐量仍然高于PBFT算法。

圖9 不同交易數(shù)量下的吞吐量對比Fig.9 Comparison of throughput under different transaction numbers

因此，K-RPBFT 算法擁有比PBFT 更大的吞吐量，能夠在單位時間內處理更多的事務，適用于對吞吐量要求較高的聯(lián)盟鏈環(huán)境。

4.3 K-RPBFT與RapidChain的對比

RapidChain 是 由Zamani 等［17］于2018 年提出的共識算法，對比的數(shù)據來自于文獻［17］中所給出的實驗數(shù)據。

兩種算法的吞吐量與共識時延對比結果如圖10 所示。在吞吐量方面，K-RPBFT 的吞吐量整體上大于RapidChain 的吞吐量，兩者吞吐量差值的最大值在區(qū)塊大小為512 KB 時取得，此時RapidChain 的吞吐量僅為K-RPBFT 的70%，隨著區(qū)塊的增大，兩者的差距有所減小，但K-RPBFT 的吞吐量仍大于RapidChain 的吞吐量；在共識時延方面，K-RPBFT 的共識時延整體上小于RapidChain 的共識時延，RapidChain 的共識時延是K-RPBFT 的1.4～1.7 倍。

圖10 兩種算法的吞吐量與共識時延對比Fig.10 Comparison of throughput and consensus latency between two algorithms

在容錯性方面，由于RapidChain 的委員會內部共識本質上還是基于PBFT 算法，因此RapidChain 的容錯率為N/3（N為參與共識的節(jié)點數(shù)量），與PBFT 算法的容錯率一致。由于K-RPBFT 算法在片內共識引入了Raft 算法，盡管對Raft 算法的共識過程進行了改進，但K-RPBFT 算法的容錯性仍然小于PBFT 算法。通過第3 章的算法分析可知，K-RPBFT 的片內容錯率為n/4（n為片內節(jié)點數(shù)量）。因此，K-RPBFT 算法的容錯性弱于RapidChain 算法。

通過以上分析可以發(fā)現(xiàn)，K-RPBFT 算法首先通過K-medoids 算法將區(qū)塊鏈分片，并且在片內共識中引入基于監(jiān)督節(jié)點改進的Raft 算法，使K-RPBFT 算法在性能方面優(yōu)于RapidChain 算法，但是安全性低于RapidChain 算法。

5 結語

本文提出了一種基于PBFT 與Raft 算法改進的共識算法模型K-RPBFT，該算法較好地結合了PBFT 算法支持拜占庭容錯與Raft 算法共識效率較高的特性，并使用K-medoids 算法將全局共識改進為多中心化的兩層共識。實驗結果表明，K-RPBFT 算法的單次共識通信次數(shù)與共識時延均小于PBFT算法，且具有更高的吞吐量，更適用于擁有大規(guī)模網絡節(jié)點的區(qū)塊鏈環(huán)境，能夠有效解決現(xiàn)有聯(lián)盟鏈共識算法可擴展性不足的問題。

目前K-RPBFT 算法仍處于實驗階段，未來將進一步完善算法細節(jié)與性能，并將該算法應用到某一具體的區(qū)塊鏈系統(tǒng)中，同時也會考慮將多中心兩層次的K-RPBFT 算法衍進為多中心多層次化的結構，進一步提升在大規(guī)模節(jié)點下區(qū)塊鏈的共識效率，以推動區(qū)塊鏈技術的不斷發(fā)展。