王謹(jǐn)東，李 強(qiáng)

（四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

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

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

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

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

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

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

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

1 相關(guān)背景

1.1 PBFT算法

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

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

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

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

PBFT 是一個(gè)三階段提交算法，從節(jié)點(diǎn)之間的相互驗(yàn)證導(dǎo)致PBFT 的通信復(fù)雜度為O(N2)，使得算法的可擴(kuò)展性不強(qiáng)，在具有大規(guī)模節(jié)點(diǎn)的區(qū)塊鏈系統(tǒng)下，可能會(huì)導(dǎo)致網(wǎng)絡(luò)風(fēng)暴。

1.2 Raft算法

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

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

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

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

2 K-RPBFT算法模型

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

2.1 K-RPBFT分片策略

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

1）節(jié)點(diǎn)探測。

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

節(jié)點(diǎn)vj將d(vi，vj) 記錄到本地并構(gòu)造回復(fù)消息REPLY，vj，d(vi，vj)，signj發(fā)送給vi，其中REPLY 為回復(fù)消息標(biāo)識(shí)，vj為節(jié)點(diǎn)編號(hào)，d(vi，vj)為單向距離，signj為消息簽名。

當(dāng)探測結(jié)束后，所有節(jié)點(diǎn)將會(huì)計(jì)算出一個(gè)全局一致的距離矩陣：

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

2）初始分片。

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

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

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

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

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

3）重分片。

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

2.2 片內(nèi)共識(shí)與監(jiān)督機(jī)制

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

1）領(lǐng)導(dǎo)者廣播區(qū)塊。

領(lǐng)導(dǎo)者將區(qū)塊、領(lǐng)導(dǎo)者編號(hào)、消息簽名等信息寫入AppendEntries RPC 的entries 域中，向分片內(nèi)所有節(jié)點(diǎn)廣播。

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

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

3）監(jiān)督節(jié)點(diǎn)驗(yàn)證。

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

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

4）區(qū)塊提交。

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

圖4 片內(nèi)共識(shí)流程Fig.4 Flow of intra-shard consensus

2.3 K-RPBFT共識(shí)流程

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

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

K-RPBFT 算法的共識(shí)流程如下：

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

2）客戶端請求階段。客戶端發(fā)送msg到聚類中心節(jié)點(diǎn)的主節(jié)點(diǎn)（即PBFT 共識(shí)集群的主節(jié)點(diǎn)），開始進(jìn)行片間共識(shí)。

3）PBFT 預(yù)準(zhǔn)備階段。PBFT 共識(shí)集群的主節(jié)點(diǎn)向PBFT從節(jié)點(diǎn)廣播預(yù)準(zhǔn)備消息

4）PBFT 準(zhǔn)備階段。PBFT 從節(jié)點(diǎn)會(huì)對收到的預(yù)準(zhǔn)備消息進(jìn)行檢查，若預(yù)準(zhǔn)備消息不合法則丟棄。通過檢查后，從節(jié)點(diǎn)向其他 PBFT 共識(shí)節(jié)點(diǎn)廣播準(zhǔn)備消息，當(dāng)節(jié)點(diǎn)收到至少2f個(gè)不同的PBFT 共識(shí)節(jié)點(diǎn)的準(zhǔn)備消息，且通過合法性檢查后，執(zhí)行PBFT 確認(rèn)階段。

5）PBFT 確認(rèn)階段。當(dāng)前節(jié)點(diǎn)向所有PBFT 共識(shí)節(jié)點(diǎn)廣播確認(rèn)消息，同時(shí)此節(jié)點(diǎn)將會(huì)收到其他節(jié)點(diǎn)的確認(rèn)消息，檢查消息簽名、視圖編號(hào)、消息序號(hào)合法并收到至少2f+1 個(gè)不同節(jié)點(diǎn)的有效確認(rèn)消息時(shí)，片間共識(shí)完成，開始進(jìn)行片內(nèi)共識(shí)。

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

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

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

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

3 算法分析

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

3.1 安全性

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

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

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

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

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

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

3.2 一致性

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

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

3.3 活性

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

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

3.4 通信開銷分析

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

4.1 共識(shí)時(shí)延測試

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

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

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

圖7 共識(shí)時(shí)延對比Fig.7 Comparison of consensus latency

4.2 吞吐量測試

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

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

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

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

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

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

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

4.3 K-RPBFT與RapidChain的對比

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

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

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

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

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

5 結(jié)語

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

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