RBFT：基于Raft 集群的拜占庭容錯(cuò)共識(shí)機(jī)制

（桂林電子科技大學(xué)廣西無(wú)線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

1 引言

區(qū)塊鏈起源于比特幣[1]，其實(shí)質(zhì)是一個(gè)基于對(duì)等網(wǎng)絡(luò)（P2P,peer to peer）和密碼學(xué)的分布式數(shù)據(jù)庫(kù)，具有去中心化、不可篡改和公開(kāi)透明等特點(diǎn)。應(yīng)用區(qū)塊鏈可解決信息不對(duì)稱問(wèn)題，實(shí)現(xiàn)多個(gè)主體之間的協(xié)作信任與一致行動(dòng)。

區(qū)塊鏈的核心技術(shù)包括共識(shí)機(jī)制、分布式存儲(chǔ)技術(shù)、密碼學(xué)和智能合約[2]。其中，共識(shí)機(jī)制著重解決分布式系統(tǒng)的一致性問(wèn)題，旨在保證所有節(jié)點(diǎn)維護(hù)的數(shù)據(jù)副本的一致性，避免數(shù)據(jù)不統(tǒng)一和信息不對(duì)稱問(wèn)題的發(fā)生。不同的場(chǎng)景對(duì)共識(shí)機(jī)制的擴(kuò)展性、共識(shí)效率和隱私性有不同的需求[3-4]?，F(xiàn)有的共識(shí)機(jī)制包括工作量證明（PoW,proof of work）[1]、權(quán)益證明（PoS,proof of stake）[5]、委托權(quán)益證明（DPoS,delegated proof of stake）[6]等概率一致性共識(shí)機(jī)制，實(shí)用拜占庭容錯(cuò)（PBFT,practical Byzantine fault tolerance）[7]、Paxos[8]、Raft[9]等絕對(duì)一致性共識(shí)機(jī)制，以及多種混合共識(shí)機(jī)制，如DPoS+PBFT 混合的Tendermint[10]、迅雷鏈的DPoA（DPoA,delegated proof of ability）+PBFT 的同構(gòu)多鏈共識(shí)機(jī)制[11]等。

從去中心化的角度，可以將區(qū)塊鏈分為公有鏈、私有鏈和聯(lián)盟鏈。公有鏈的去中心化程度最高，任何節(jié)點(diǎn)都可加入，如比特幣[1]、以太坊[5]等。私有鏈的去中心化程度最低，一般由個(gè)人或某個(gè)小團(tuán)體創(chuàng)建，僅使用區(qū)塊鏈技術(shù)進(jìn)行記賬。聯(lián)盟鏈的去中心化程度介于公有鏈和私有鏈之間，一般由多個(gè)不同利益方的機(jī)構(gòu)組成，節(jié)點(diǎn)必須經(jīng)過(guò)聯(lián)盟鏈節(jié)點(diǎn)成員管理服務(wù)進(jìn)行身份確認(rèn)和鑒權(quán)，獲得準(zhǔn)入證才可以加入聯(lián)盟鏈網(wǎng)絡(luò)[12]。聯(lián)盟鏈支持節(jié)點(diǎn)管理、可插拔的框架和模塊化的共識(shí)機(jī)制，因此在性能和隱私保護(hù)上比公有鏈更有優(yōu)勢(shì)，是區(qū)塊鏈落地的主要趨勢(shì)。

聯(lián)盟鏈在供應(yīng)鏈管理[13]、產(chǎn)品溯源[14]、智能制造[15]等領(lǐng)域有著廣闊的應(yīng)用前景。但要將聯(lián)盟鏈真正落地，迫切需要解決其擴(kuò)展性差、安全性低和吞吐量小的問(wèn)題。在節(jié)點(diǎn)數(shù)量上，實(shí)際商業(yè)應(yīng)用的節(jié)點(diǎn)規(guī)模在幾十到數(shù)百不等；在吞吐量上，諸如去中心化電商、車聯(lián)網(wǎng)等領(lǐng)域要求節(jié)點(diǎn)規(guī)模在萬(wàn)級(jí)以上；在安全性方面，區(qū)塊鏈金融、數(shù)字資產(chǎn)等金融領(lǐng)域?qū)Π踩砸笙鄬?duì)較高。同時(shí)，為了保證用戶體驗(yàn)，絕大多數(shù)的交易需要更低的時(shí)延。這些典型應(yīng)用場(chǎng)景的要求遠(yuǎn)超現(xiàn)有區(qū)塊鏈網(wǎng)絡(luò)在時(shí)延、吞吐量和拓展性等方面所能達(dá)到的性能。共識(shí)機(jī)制是區(qū)塊鏈的核心技術(shù)，決定了區(qū)塊鏈的吞吐量、安全性和拓展性等性能。因此，改進(jìn)共識(shí)機(jī)制是解決這些問(wèn)題的有效手段。

聯(lián)盟鏈的共識(shí)機(jī)制需要兼顧高效、安全與可拓展性，尤其是在大規(guī)模網(wǎng)絡(luò)環(huán)境下仍需保持高吞吐量和低時(shí)延。目前，已有的共識(shí)機(jī)制尚不能同時(shí)滿足這些需求，例如，公有鏈項(xiàng)目中常用的共識(shí)機(jī)制PoW效率太低，PoS/DPoS 以及類似算法瑞波協(xié)議[16]、Algorand 共識(shí)協(xié)議[17]等易導(dǎo)致“富豪統(tǒng)治”，且這些共識(shí)機(jī)制均依賴代幣，而很多聯(lián)盟鏈的實(shí)際應(yīng)用場(chǎng)景并不需要發(fā)行代幣。

Hyperledger Fabric是業(yè)界最先發(fā)展聯(lián)盟鏈的項(xiàng)目，其0.6preview 版本采用了PBFT 共識(shí)機(jī)制，1.0版本使用了效率更高的Kafka 集群共識(shí)機(jī)制[18]，最新的Fabric 2.0 使用了更靈活的Raft 共識(shí)機(jī)制，通常實(shí)測(cè)吞吐量在300～500 筆/秒（PBFT 數(shù)據(jù)，采用Raft 后有提升）。FISCO BCOS 聯(lián)盟鏈項(xiàng)目支持并行計(jì)算的PBFT 和標(biāo)準(zhǔn)Raft 這2 種模式，官方實(shí)測(cè)單鏈吞吐量可達(dá)1 000 筆/秒以上。Coco 聯(lián)盟鏈項(xiàng)目支持Paxos 共識(shí)協(xié)議，官方吞吐量是1 600 筆/秒。這些聯(lián)盟鏈的吞吐量雖然遠(yuǎn)高于比特幣、以太坊，但仍然無(wú)法滿足現(xiàn)有聯(lián)盟鏈實(shí)際應(yīng)用的需求。

在共識(shí)機(jī)制的改進(jìn)方面，文獻(xiàn)[19]提出了一種基于K-medoids 的改進(jìn)PBFT 共識(shí)機(jī)制，通過(guò)對(duì)大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)的特征進(jìn)行聚類和層次劃分，在1 000 個(gè)節(jié)點(diǎn)的模擬中，單次共識(shí)耗時(shí)縮短了20%；文獻(xiàn)[20]將PBFT 的三階段共識(shí)簡(jiǎn)化為兩階段共識(shí)，從而減少了通信開(kāi)銷，提高了共識(shí)效率；文獻(xiàn)[21]提出一種基于特征信任模型的優(yōu)化PBFT，提高了拜占庭容錯(cuò)能力；文獻(xiàn)[22]通過(guò)建立信譽(yù)模型，根據(jù)信譽(yù)值賦予節(jié)點(diǎn)不同的話語(yǔ)權(quán)并在PBFT 機(jī)制中加入預(yù)提交階段來(lái)減少通信次數(shù)，提高了算法性能并可以有效防御女巫攻擊；文獻(xiàn)[23]基于Kademlia 協(xié)議優(yōu)化了Raft 的領(lǐng)導(dǎo)者選舉和共識(shí)機(jī)制，進(jìn)一步提高了算法的領(lǐng)導(dǎo)者選舉速度和交易吞吐量。對(duì)PBFT 的改進(jìn)并不能從根本上解決PBFT 的算法瓶頸，節(jié)點(diǎn)間兩兩通信機(jī)制導(dǎo)致其擴(kuò)展性低，不適合大規(guī)模網(wǎng)絡(luò)。Raft 屬于強(qiáng)領(lǐng)導(dǎo)者型共識(shí)機(jī)制，即使在節(jié)點(diǎn)規(guī)模擴(kuò)大的情況下仍能保持算法的高共識(shí)效率，但也因此不具備拜占庭容錯(cuò)能力，僅適用于可信執(zhí)行環(huán)境的聯(lián)盟鏈。

本文的主要研究工作如下。

1) 針對(duì)聯(lián)盟鏈共識(shí)機(jī)制PBFT 在節(jié)點(diǎn)數(shù)量增多時(shí)共識(shí)效率下降的問(wèn)題，結(jié)合Raft 共識(shí)思想提出了一種基于Raft 集群的拜占庭容錯(cuò)共識(shí)機(jī)制——RBFT（Raft cluster Byzantine fault tolerance）。通過(guò)將網(wǎng)絡(luò)節(jié)點(diǎn)分組，組內(nèi)采用改進(jìn)的Raft 共識(shí)機(jī)制，由Raft共識(shí)機(jī)制選舉出的領(lǐng)導(dǎo)者組成委員會(huì)，委員會(huì)采用PBFT 共識(shí)機(jī)制，大大降低了節(jié)點(diǎn)通信量，有效地提高了共識(shí)效率。同時(shí)，引入監(jiān)督節(jié)點(diǎn)使Raft 具有了拜占庭惡意行為容忍能力，提高了組內(nèi)共識(shí)的安全性。

2) 討論了RBFT 的節(jié)點(diǎn)分組策略和監(jiān)督節(jié)點(diǎn)的監(jiān)督策略，論證了RBFT 共識(shí)機(jī)制的一致性、安全性和靈活性。

3) 對(duì)RBFT 的通信開(kāi)銷、共識(shí)時(shí)延、吞吐量和容錯(cuò)性進(jìn)行了仿真與實(shí)驗(yàn)測(cè)試，以驗(yàn)證其有效性和可靠性。

2 背景知識(shí)

2.1 PBFT 共識(shí)機(jī)制簡(jiǎn)介

PBFT 機(jī)制由Castro 等[7]提出，目的是改進(jìn)BFT的算法效率，構(gòu)建容忍拜占庭故障的高可用系統(tǒng)。它將算法的復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)，使算法能夠處理大量事務(wù)并且保證一定的效率。PBFT共識(shí)機(jī)制包含2 個(gè)重要的流程：三階段共識(shí)流程和視圖更換流程。

三階段共識(shí)流程用于對(duì)候選區(qū)塊形成共識(shí)，分為預(yù)準(zhǔn)備、準(zhǔn)備和提交3 個(gè)階段。預(yù)準(zhǔn)備階段消息由主節(jié)點(diǎn)廣播給副本節(jié)點(diǎn)，副本節(jié)點(diǎn)收到預(yù)準(zhǔn)備消息后會(huì)廣播準(zhǔn)備消息。當(dāng)某一節(jié)點(diǎn)收到不少于2f條來(lái)自不同節(jié)點(diǎn)的準(zhǔn)備消息時(shí)，該節(jié)點(diǎn)進(jìn)入提交階段并廣播提交消息。同樣，當(dāng)節(jié)點(diǎn)收到的提交消息數(shù)不少于2f+1 時(shí)，該節(jié)點(diǎn)三階段共識(shí)完成，將區(qū)塊記入本地賬本。因此，PBFT 的通信復(fù)雜度為O(N2)，在不超過(guò)1/3的節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)時(shí)仍能保持一致，即f≤(N-1)/3，其中，N為網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)。

同時(shí)，PBFT 通過(guò)視圖更換流程替換失效的主節(jié)點(diǎn)以保證共識(shí)服務(wù)的持續(xù)進(jìn)行，給算法提供活性。當(dāng)副本節(jié)點(diǎn)認(rèn)為當(dāng)前主節(jié)點(diǎn)無(wú)法在給定時(shí)間內(nèi)完成共識(shí)或收到f+1 個(gè)視圖切換消息時(shí)，進(jìn)入視圖更換，切換主節(jié)點(diǎn)進(jìn)入下一個(gè)視圖，開(kāi)始新一輪的三階段共識(shí)流程。

2.2 Raft 共識(shí)機(jī)制簡(jiǎn)介

Raft機(jī)制是由Ongaro等[9]提出的一種分布式共識(shí)機(jī)制，目標(biāo)是實(shí)現(xiàn)賬本復(fù)制的一致性。Raft 將一致性算法分解成2 個(gè)關(guān)鍵的模塊：領(lǐng)導(dǎo)者選舉和日志復(fù)制。

在Raft 中，節(jié)點(diǎn)有3 種可能的狀態(tài)：跟隨者、候選者和領(lǐng)導(dǎo)者。在任一時(shí)刻，每個(gè)節(jié)點(diǎn)都處于這3 種狀態(tài)中的一種。Raft 機(jī)制將時(shí)間劃分為若干個(gè)任意長(zhǎng)度的時(shí)間段，每個(gè)時(shí)間段稱之為一個(gè)任期。任期的編號(hào)是連續(xù)遞增的整數(shù)。每個(gè)任期開(kāi)始于一次領(lǐng)導(dǎo)者選舉。所有節(jié)點(diǎn)的初始狀態(tài)都是跟隨者，如果跟隨者沒(méi)能感知到領(lǐng)導(dǎo)者的存在，那么跟隨者就跳轉(zhuǎn)為候選者。候選者將會(huì)發(fā)起投票，要求其他節(jié)點(diǎn)選擇自己為領(lǐng)導(dǎo)者。其他節(jié)點(diǎn)將會(huì)回應(yīng)候選者的請(qǐng)求。如果候選者獲得多數(shù)節(jié)點(diǎn)贊同票，那么它就成為領(lǐng)導(dǎo)者。這個(gè)過(guò)程稱為領(lǐng)導(dǎo)者選舉。正常情況下，網(wǎng)絡(luò)中僅有一個(gè)領(lǐng)導(dǎo)者，其余節(jié)點(diǎn)均為跟隨者。領(lǐng)導(dǎo)者通過(guò)周期性地向跟隨者發(fā)送心跳包以維持其領(lǐng)導(dǎo)地位。所有經(jīng)過(guò)驗(yàn)證的交易在該任期內(nèi)都由領(lǐng)導(dǎo)者打包生成區(qū)塊。在收到超過(guò)半數(shù)節(jié)點(diǎn)回復(fù)后，領(lǐng)導(dǎo)者發(fā)送確認(rèn)信息給跟隨者，并將該區(qū)塊作為賬本上的下一個(gè)區(qū)塊。跟隨者收到領(lǐng)導(dǎo)者的確認(rèn)信息后，將該區(qū)塊作為本地賬本上的下一個(gè)區(qū)塊。這個(gè)過(guò)程稱為賬本復(fù)制。

Raft 是一種強(qiáng)領(lǐng)導(dǎo)者算法，領(lǐng)導(dǎo)者選舉是該共識(shí)協(xié)議的重要組成部分。在基于Raft 的區(qū)塊鏈系統(tǒng)中，數(shù)據(jù)僅能從領(lǐng)導(dǎo)者到其他服務(wù)器單向流動(dòng)，因而架構(gòu)簡(jiǎn)單且易于理解。Raft 具有線性的復(fù)雜度，因而共識(shí)效率很高。在容錯(cuò)性方面，Raft可以容忍不超過(guò)50%的停機(jī)故障，但不具備拜占庭容錯(cuò)能力。

3 RBFT 共識(shí)機(jī)制

為了提供一種具備高擴(kuò)展性、高安全性、低時(shí)延高吞吐量的共識(shí)算法，本文結(jié)合PBFT 的拜占庭容錯(cuò)安全性與Raft 高共識(shí)效率的優(yōu)點(diǎn)，提出一種基于Raft 集群的拜占庭容錯(cuò)共識(shí)機(jī)制——RBFT。RBFT 共識(shí)機(jī)制流程如圖1 所示。

圖1 RBFT 共識(shí)機(jī)制流程

RBFT 共識(shí)機(jī)制采用分片的思想將區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分組，各分組內(nèi)采用Raft 機(jī)制共識(shí)并選出領(lǐng)導(dǎo)者組建委員會(huì)，委員會(huì)內(nèi)部采用PBFT 機(jī)制進(jìn)行共識(shí)。RBFT 同時(shí)引入監(jiān)督節(jié)點(diǎn)，解決Raft 共識(shí)不能對(duì)抗拜占庭惡意行為的問(wèn)題，從而保證共識(shí)機(jī)制的安全性。

3.1 節(jié)點(diǎn)的分組策略

所提共識(shí)機(jī)制需要進(jìn)行網(wǎng)絡(luò)分片，根據(jù)RBFT算法的兩級(jí)共識(shí)機(jī)制，PBFT 共識(shí)需要滿足分組數(shù)k≥ 4，每個(gè)組內(nèi)的Raft 共識(shí)需要滿足節(jié)點(diǎn)數(shù)m≥ 3。此外，監(jiān)督節(jié)點(diǎn)需要同時(shí)分配到多個(gè)組內(nèi)以實(shí)現(xiàn)監(jiān)督功能?，F(xiàn)有的網(wǎng)絡(luò)分片包括基于協(xié)議分片[24]和基于地理位置分片[25]。

文獻(xiàn)[24]提出了一種基于ELASTICO 協(xié)議的網(wǎng)絡(luò)分片機(jī)制。節(jié)點(diǎn)根據(jù)自身IP 地址、公鑰以及一個(gè)隨機(jī)數(shù)進(jìn)行Hash 運(yùn)算，將所得的Hash 值作為自己所在網(wǎng)絡(luò)分片在區(qū)塊鏈系統(tǒng)中的身份，Hash 值的后若干位代表了節(jié)點(diǎn)所在的分片ID。區(qū)塊鏈系統(tǒng)中的交易會(huì)并發(fā)地分配到各個(gè)分片中并行處理。

文獻(xiàn)[25]提出了一種區(qū)塊鏈系統(tǒng)，該系統(tǒng)使用基于地理位置的分片機(jī)制。根據(jù)節(jié)點(diǎn)所處的地理位置范圍，將范圍內(nèi)的節(jié)點(diǎn)劃分到一個(gè)分組內(nèi)。

基于ELASTICO 協(xié)議的分片機(jī)制中，Hash 的運(yùn)算結(jié)果的隨機(jī)性較大，容易導(dǎo)致分片不均；基于地理位置的分片機(jī)制中，人為的干預(yù)性較大，但是這2 種分片機(jī)制都不能實(shí)現(xiàn)監(jiān)督節(jié)點(diǎn)的分配。本文引入一致性Hash 算法[26]的設(shè)計(jì)思想，利用一致性Hash 算法平衡、分散、單調(diào)的特點(diǎn)，提出一種適用于RBFT 的節(jié)點(diǎn)分組算法，如算法1 所示。

算法1RBFT 節(jié)點(diǎn)分組算法

根據(jù)組內(nèi)節(jié)點(diǎn)數(shù)m≥3 及每個(gè)組內(nèi)至少含一個(gè)監(jiān)督節(jié)點(diǎn)的條件，確定分組是否合理，若是，轉(zhuǎn)至步驟5)；若否，轉(zhuǎn)至步驟2)

5) 分組完畢

一致性Hash 計(jì)算的結(jié)果是一個(gè)uint32 類型的大整數(shù)，結(jié)果同樣具有Hash 的抗碰撞性，根據(jù)結(jié)果可將節(jié)點(diǎn)映射的Hash 值分布在0～232的圓上。一致性Hash 的平衡分散性能夠保證計(jì)算的結(jié)果盡可能地呈均勻分布，并使每個(gè)組內(nèi)的領(lǐng)導(dǎo)者負(fù)載均衡，解決分片不均的問(wèn)題。此外，其單調(diào)性降低了節(jié)點(diǎn)的加入和退出對(duì)分組的影響。

采用一致性Hash 算法的分組策略如圖2 所示。設(shè)每r組分配一個(gè)監(jiān)督節(jié)點(diǎn)，監(jiān)督節(jié)點(diǎn)的數(shù)量滿足

圖2 采用一致性Hash 算法的分組策略

如圖2 所示，假設(shè)分組數(shù)為4，每三組分配一個(gè)監(jiān)督節(jié)點(diǎn)，則s≥2 。根據(jù)算法1，按順時(shí)針進(jìn)行分配，監(jiān)督節(jié)點(diǎn)1 被同時(shí)分配到組A、組B和組D 中，監(jiān)督節(jié)點(diǎn)2 被同時(shí)分組到組A、組C和組D 中。

當(dāng)分組數(shù)較少時(shí)，容易因?yàn)榉制粔蚓鶆蚨斐蓴?shù)據(jù)傾斜問(wèn)題，即部分分片中承載了大多數(shù)節(jié)點(diǎn)，導(dǎo)致負(fù)載失衡。一致性Hash 的理想結(jié)果是如果分組ID 有K個(gè)，承載的節(jié)點(diǎn)的Hash 值有N個(gè)，那么每個(gè)分組應(yīng)該承載N/K個(gè)。RBFT 中的分組算法引入了一致性Hash 算法虛擬節(jié)點(diǎn)的概念，對(duì)實(shí)際分組設(shè)置多個(gè)虛擬分組來(lái)擴(kuò)大分組數(shù)，使分組更均勻。

根據(jù)算法1 得到RBFT 共識(shí)機(jī)制的分組結(jié)果，分別如圖3 和表1 所示。

圖3 區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)實(shí)體構(gòu)成

表1 分組結(jié)果

3.2 監(jiān)督節(jié)點(diǎn)的監(jiān)督策略

監(jiān)督節(jié)點(diǎn)的存在是對(duì)Raft 安全性的一大改進(jìn)。監(jiān)督節(jié)點(diǎn)的加入使Raft 具備了抵抗拜占庭惡意節(jié)點(diǎn)的能力。

在Raft 共識(shí)機(jī)制中，如果領(lǐng)導(dǎo)者作惡，向組內(nèi)跟隨者下發(fā)惡意信息，則會(huì)破壞共識(shí)的一致性。如圖3 所示，假設(shè)每三組分配一個(gè)監(jiān)督節(jié)點(diǎn)，根據(jù)分組數(shù)不同，每個(gè)組內(nèi)可能有一個(gè)或多個(gè)監(jiān)督節(jié)點(diǎn)。監(jiān)督節(jié)點(diǎn)負(fù)責(zé)監(jiān)督組內(nèi)的領(lǐng)導(dǎo)者，因此監(jiān)督節(jié)點(diǎn)不參與領(lǐng)導(dǎo)者選舉，只作為跟隨者參與組內(nèi)Raft 共識(shí)。同時(shí)，監(jiān)督節(jié)點(diǎn)需要保證匿名性以防領(lǐng)導(dǎo)者進(jìn)行針對(duì)性的欺詐。

RBFT 在Raft 共識(shí)時(shí)加入了簽名驗(yàn)證環(huán)節(jié)。領(lǐng)導(dǎo)者下發(fā)日志同步消息給跟隨者時(shí)，需要對(duì)消息進(jìn)行簽名。監(jiān)督節(jié)點(diǎn)在收到不同領(lǐng)導(dǎo)者的日志消息后，需要對(duì)簽名進(jìn)行驗(yàn)證并比對(duì)內(nèi)容，從而判斷領(lǐng)導(dǎo)者是否為拜占庭惡意節(jié)點(diǎn)。

監(jiān)督節(jié)點(diǎn)監(jiān)督領(lǐng)導(dǎo)者的策略如圖4 所示，分為取證、舉證和驗(yàn)證3 個(gè)階段。

圖4 監(jiān)督節(jié)點(diǎn)監(jiān)督領(lǐng)導(dǎo)者的策略

1) 取證階段。進(jìn)行Raft 組內(nèi)共識(shí)時(shí)，監(jiān)督節(jié)點(diǎn)可以同時(shí)監(jiān)聽(tīng)3 個(gè)分組內(nèi)的領(lǐng)導(dǎo)者（記賬人）下發(fā)至跟隨者的記賬信息，在驗(yàn)證節(jié)點(diǎn)簽名后對(duì)領(lǐng)導(dǎo)者下發(fā)的信息進(jìn)行甄別，當(dāng)發(fā)現(xiàn)一個(gè)領(lǐng)導(dǎo)者下發(fā)的信息與其他領(lǐng)導(dǎo)者不同時(shí)，則可以判定其為惡意節(jié)點(diǎn)。根據(jù)節(jié)點(diǎn)簽名鎖定節(jié)點(diǎn)身份，進(jìn)行取證。

2) 舉證階段。對(duì)惡意節(jié)點(diǎn)取證完成后，監(jiān)督節(jié)點(diǎn)打包一個(gè)舉證消息

3) 驗(yàn)證階段。成員管理服務(wù)根據(jù)舉證內(nèi)容，判斷被舉證的惡意節(jié)點(diǎn)的公鑰等信息并驗(yàn)證舉證的合法性，對(duì)是否罷免惡意節(jié)點(diǎn)的領(lǐng)導(dǎo)者身份做出判決。

3.3 RBFT 共識(shí)流程

主記賬人將若干條收聽(tīng)到的客戶端請(qǐng)求信息打包成一個(gè)區(qū)塊后進(jìn)行共識(shí)，共識(shí)流程如算法2 和圖5 所示。

算法2RBFT 共識(shí)流程

1) PBFT-Stage:A client sends a request

2) The primary broadcasts

3) Replica broadcasts

4) Replica counts the number of Prepare messages and denotes it as Count1，if Count1 ≥2f,broadcasts

5) Replica counts Commit messages and denotes it as Count 2，if Count2 ≥2f+1,enters Raft-Stage//副節(jié)點(diǎn)判斷提交階段是否完成，進(jìn)入Raft 共識(shí)階段

6) Raft-Stage:The leader broadcasts

7) Followers reply AppendLog Prepared messages to leader//跟隨者節(jié)點(diǎn)接收消息并反饋

8) The leader counts the number of AppendLog Prepared messages received and denotes it as Count,if,commit Log//領(lǐng)導(dǎo)者節(jié)點(diǎn)根據(jù)消息反饋結(jié)果，判斷是否達(dá)成共識(shí)并提交日志

9) Reply client//共識(shí)完成，回復(fù)客戶端

算法2 中，V表示當(dāng)前視圖的編號(hào)，N表示當(dāng)前請(qǐng)求的編號(hào)，M表示消息的內(nèi)容，D(M)表示消息的摘要，i表示節(jié)點(diǎn)的編號(hào)，f表示拜占庭節(jié)點(diǎn)個(gè)數(shù)。

4 RBFT 的一致性、安全性與活性

根據(jù)FLP（Fischer-Lynch-Patterson）[27]和CAP（consistency-availability-partition tolerance）理論[28]，異步模型系統(tǒng)中不存在一個(gè)可以使系統(tǒng)取得強(qiáng)一致性的確定性共識(shí)機(jī)制。一個(gè)分布式系統(tǒng)最多只能同時(shí)滿足一致性、可用性和分區(qū)容忍性三項(xiàng)中的兩項(xiàng)。這里的一致性指強(qiáng)一致性，是系統(tǒng)成功操作返回后所有節(jié)點(diǎn)在同一時(shí)刻的數(shù)據(jù)完全一致。大多數(shù)情況下要遵循 BASE（basically available-soft state-eventual consistency）理論[29]弱化一致性，但要采取適當(dāng)?shù)姆绞竭_(dá)到最終一致性，即所有副本在經(jīng)過(guò)一定時(shí)間后，最終能夠達(dá)成一致的狀態(tài)。

RBFT 共識(shí)機(jī)制基于PBFT 和Raft 構(gòu)建，其一致性、安全性和活性繼承了PBFT 和Raft 原有的優(yōu)良特性，并通過(guò)監(jiān)督機(jī)制和分組增強(qiáng)了安全性和活性。

圖5 共識(shí)流程

4.1 一致性

RBFT 通過(guò)PBFT 機(jī)制保證了共識(shí)一致性，通過(guò)Raft 協(xié)議的AppendEntry RPC 機(jī)制保障了最終一致性。在RBFT 兩級(jí)共識(shí)階段，委員會(huì)共識(shí)遵從PBFT 共識(shí)協(xié)議來(lái)保證算法的一致性，在容錯(cuò)范圍f≤(k-1)/3內(nèi)可以保證PBFT 階段正常共識(shí)。組內(nèi)共識(shí)遵從 Raft 共識(shí)協(xié)議，當(dāng)故障節(jié)點(diǎn)數(shù)f≤(m-1)/2時(shí)，Raft 共識(shí)階段也可以順利進(jìn)行。

節(jié)點(diǎn)從故障到恢復(fù)后作為Raft 的跟隨者角色存在，從領(lǐng)導(dǎo)者處更新自己的日志列表來(lái)保持一致。如圖6 所示，S1為一個(gè)Raft 集群的領(lǐng)導(dǎo)者，節(jié)點(diǎn)擁有與其他集群一致的日志，S1和S3擁有完備的日志列表，S2和S5可能處在日志的復(fù)制階段，S4可能是宕機(jī)節(jié)點(diǎn)。當(dāng)宕機(jī)節(jié)點(diǎn)從宕機(jī)狀態(tài)恢復(fù)后，會(huì)從領(lǐng)導(dǎo)者處進(jìn)行日志同步，從而保證最終所有節(jié)點(diǎn)的日志的一致性。

4.2 安全性

RBFT 共識(shí)的第一階段通過(guò)PBFT 的共識(shí)特性[7]保證了安全。預(yù)準(zhǔn)備、準(zhǔn)備和提交的三階段消息必須在同一個(gè)視圖內(nèi)完成，且完成的時(shí)間必須小于節(jié)點(diǎn)需要通過(guò)超時(shí)觸發(fā)視圖切換的時(shí)間，所有的消息均遵從PBFT 共識(shí)協(xié)議的摘要、序列號(hào)和簽名驗(yàn)證等步驟。

RBFT 共識(shí)的第二階段的安全性由監(jiān)督節(jié)點(diǎn)的監(jiān)督功能來(lái)保證。根據(jù)3.2 節(jié)監(jiān)督節(jié)點(diǎn)的監(jiān)督策略可知，監(jiān)督節(jié)點(diǎn)的監(jiān)督行為使組內(nèi)共識(shí)具備了對(duì)抗拜占庭惡意行為的能力，增強(qiáng)了RBFT 共識(shí)第二階段的安全性。Raft 組內(nèi)普通節(jié)點(diǎn)需要收到領(lǐng)導(dǎo)者提交的消息且收到成員管理服務(wù)對(duì)消息結(jié)果驗(yàn)證為真時(shí)，才可提交日志信息上鏈；若為假（監(jiān)督節(jié)點(diǎn)發(fā)現(xiàn)有領(lǐng)導(dǎo)者作惡，領(lǐng)導(dǎo)者身份被罷免），則需等待下一任期同步新領(lǐng)導(dǎo)者的日志，防止惡意信息上鏈保證安全性。

對(duì)于監(jiān)督節(jié)點(diǎn)本身，RBFT 設(shè)計(jì)了3 種機(jī)制保證安全性。①增加分組內(nèi)監(jiān)督節(jié)點(diǎn)的占比。對(duì)于網(wǎng)絡(luò)環(huán)境較差或者安全可靠性低的場(chǎng)景，需要適當(dāng)增加分組內(nèi)監(jiān)督節(jié)點(diǎn)的占比來(lái)提高安全性。當(dāng)組內(nèi)部分監(jiān)督節(jié)點(diǎn)受攻擊或者宕機(jī)時(shí)，可以由其他監(jiān)督節(jié)點(diǎn)執(zhí)行監(jiān)督職責(zé)。② 監(jiān)督節(jié)點(diǎn)重選。監(jiān)督節(jié)點(diǎn)定期向成員管理服務(wù)發(fā)送監(jiān)管狀態(tài)信息

4.3 活性

RBFT 算法的活性由PBFT 階段的視圖切換和Raft 階段的領(lǐng)導(dǎo)者選舉等提供。在PBFT 階段，記賬節(jié)點(diǎn)通過(guò)p=vmodk來(lái)確定主節(jié)點(diǎn)，視圖編號(hào)v從0 開(kāi)始遞增。當(dāng)副本記賬節(jié)點(diǎn)的計(jì)時(shí)器超時(shí)或者收到一組f+1個(gè)有效視圖切換消息時(shí)，意味著當(dāng)前視圖的主節(jié)點(diǎn)已無(wú)法完成共識(shí)，副本必須進(jìn)入下一個(gè)視圖重新進(jìn)行共識(shí)服務(wù)。

此外，在RBFT 算法中，委員會(huì)成員是各分組的領(lǐng)導(dǎo)者通過(guò)Raft 的領(lǐng)導(dǎo)者選舉產(chǎn)生的。當(dāng)委員會(huì)成員宕機(jī)時(shí)，其對(duì)應(yīng)分組內(nèi)的跟隨者節(jié)點(diǎn)接收不到領(lǐng)導(dǎo)者的心跳檢測(cè)而觸發(fā)領(lǐng)導(dǎo)者重選流程，由新領(lǐng)導(dǎo)者替換失效的委員會(huì)成員。因此，RBFT 算法增強(qiáng)了委員會(huì)PBFT 共識(shí)階段的節(jié)點(diǎn)宕機(jī)故障恢復(fù)能力，增強(qiáng)了算法的活性。

Raft 的領(lǐng)導(dǎo)者選舉和心跳檢測(cè)機(jī)制使副本節(jié)點(diǎn)在接收日志超時(shí)或者當(dāng)前任期領(lǐng)導(dǎo)者宕機(jī)時(shí)開(kāi)啟一個(gè)新的任期并重新選舉領(lǐng)導(dǎo)者對(duì)外提供服務(wù)，維持了RBFT 算法組內(nèi)共識(shí)的活性。

圖6 Raft 共識(shí)日志狀態(tài)的一致性

5 仿真與實(shí)驗(yàn)分析

本節(jié)將從通信開(kāi)銷、共識(shí)時(shí)延、吞吐量和容錯(cuò)性4 個(gè)方面對(duì)比RBFT 與其他主流算法的表現(xiàn)，以此論證RBFT 的有效性和可靠性。

5.1 仿真方案與實(shí)驗(yàn)設(shè)置

測(cè)試平臺(tái)硬件采用了 8 核/48 GB 的Intel(R)Core(TM) i7-9700 的服務(wù)主機(jī)，通過(guò)配置多臺(tái)虛擬機(jī)加端口映射的方式來(lái)模擬多節(jié)點(diǎn)環(huán)境，映射方式如表2 所示。測(cè)試平臺(tái)軟件的開(kāi)發(fā)環(huán)境為L(zhǎng)inuxMint19.3/Golang1.14。

表2 映射方式

1) 通信開(kāi)銷

PBFT 共識(shí)機(jī)制需要兩兩節(jié)點(diǎn)進(jìn)行通信，通信量為O(N2)（其中N為節(jié)點(diǎn)數(shù)量）。Raft 共識(shí)機(jī)制的通信量為O(N)，通過(guò)網(wǎng)絡(luò)分片，RBFT 相比于PBFT共識(shí)機(jī)制，通信量由O(N2)下降到O(N/k)+O(k2)。

仿真設(shè)定一次共識(shí)過(guò)程中的消息內(nèi)容m=256 bit，消息摘要d=128 bit，回復(fù)客戶端的信息大小r=80 bit，Raft 共識(shí)過(guò)程的心跳包大小h=64 bit。

2) 共識(shí)時(shí)延

算法的共識(shí)時(shí)延定義為從客戶端發(fā)起請(qǐng)求到該請(qǐng)求被確認(rèn)并上鏈所需的時(shí)間。取連續(xù)測(cè)量30 次結(jié)果的平均值作為算法的共識(shí)時(shí)延，分別記錄相同網(wǎng)絡(luò)規(guī)模下所提算法RBFT 和對(duì)比算法PBFT、Raft 的數(shù)據(jù)。

3) 吞吐量（TPS,transaction per second）

系統(tǒng)的吞吐量定義為系統(tǒng)每秒鐘處理的事務(wù)量。在區(qū)塊鏈系統(tǒng)中，吞吐量表現(xiàn)為交易數(shù)量M與處理對(duì)應(yīng)交易時(shí)間t的比值，即

每個(gè)節(jié)點(diǎn)都可以監(jiān)聽(tīng)來(lái)自客戶端的請(qǐng)求，因此需要為每個(gè)節(jié)點(diǎn)綁定一個(gè)客戶端程序?？蛻舳嗣扛?0 ms 發(fā)起一次請(qǐng)求，每秒并發(fā)度為20N。所有的請(qǐng)求最后由主節(jié)點(diǎn)收集打包負(fù)責(zé)出塊，采用BoltDB 數(shù)據(jù)庫(kù)[30]實(shí)現(xiàn)對(duì)區(qū)塊數(shù)據(jù)的持久化存儲(chǔ)，來(lái)記錄每個(gè)塊包含的交易量M及塊共識(shí)的時(shí)間t。出塊間隔設(shè)定為10 s，取系統(tǒng)運(yùn)行5 min 后數(shù)據(jù)庫(kù)中穩(wěn)定的10 組數(shù)據(jù)的平均值作為該次測(cè)試的系統(tǒng)吞吐量。

4) 容錯(cuò)性

令f1、f2為大于0 的整數(shù)，Raft 組內(nèi)的節(jié)點(diǎn)數(shù)m≥2f1+1，分組數(shù)k≥3f2+1。每r組分配一個(gè)監(jiān)督節(jié)點(diǎn)（r≥ 2），假設(shè)每組的節(jié)點(diǎn)數(shù)目相同，則總的節(jié)點(diǎn)數(shù)N滿足

其中，

PBFT 共識(shí)階段的最大容錯(cuò)為(k-1)/3，Raft階段的最大容錯(cuò)為(m-1)/2。在監(jiān)督節(jié)點(diǎn)的參與下，RBFT 的最大容錯(cuò)為

仿真中設(shè)定每三組分配一個(gè)監(jiān)督節(jié)點(diǎn)（即r=3），并假設(shè)所有分組中包含的節(jié)點(diǎn)數(shù)目一致。

5.2 通信開(kāi)銷

圖7 為RBFT 共識(shí)機(jī)制與經(jīng)典PBFT 共識(shí)機(jī)制的通信開(kāi)銷比較。從圖7 可以看出，RBFT 共識(shí)機(jī)制的通信開(kāi)銷遠(yuǎn)小于區(qū)塊鏈網(wǎng)絡(luò)全網(wǎng)采用PBFT 共識(shí)機(jī)制的通信開(kāi)銷，如當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為117 時(shí)，經(jīng)典PBFT 共識(shí)機(jī)制的通信開(kāi)銷為63.51 ×10 bit，RBFT 共識(shí)機(jī)制的通信開(kāi)銷為44.06 ×10 bit，通信開(kāi)銷降低了98.8%，且隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增多，RBFT比PBFT 節(jié)省的通信開(kāi)銷越大。

圖7 RBFT 與經(jīng)典PBFT 共識(shí)機(jī)制的通信開(kāi)銷比較

5.3 共識(shí)時(shí)延

所提算法和對(duì)比算法的共識(shí)時(shí)延實(shí)測(cè)結(jié)果如圖8 所示。從圖8 可以看出，隨著節(jié)點(diǎn)數(shù)量的增加，共識(shí)時(shí)延逐漸增大。其中，PBFT 算法增長(zhǎng)最快，Raft 最慢。對(duì)于RBFT 而言，同樣是增加網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，保持組內(nèi)節(jié)點(diǎn)數(shù)不變而增加分組數(shù)相比保持分組數(shù)不變而增加組內(nèi)節(jié)點(diǎn)數(shù)，會(huì)引起更高的共識(shí)時(shí)延，如圖8 中RBFT（組內(nèi)節(jié)點(diǎn)數(shù)：10）和RBFT（分組數(shù)：4）所示。這是因?yàn)樵黾臃纸M數(shù)實(shí)質(zhì)上是擴(kuò)大了委員會(huì)的規(guī)模，增加了PBFT 階段的共識(shí)耗時(shí)，所以增加分組數(shù)對(duì)共識(shí)時(shí)延的影響更大。但在同樣節(jié)點(diǎn)規(guī)模下，RBFT 的時(shí)延仍遠(yuǎn)小于PBFT。從圖8 還可以看出，PBFT 的時(shí)延隨節(jié)點(diǎn)規(guī)模的增大急劇增加，而RBFT 的時(shí)延增速則較緩。因此，RBFT在節(jié)點(diǎn)規(guī)模擴(kuò)大時(shí)仍能保證高共識(shí)效率。

圖8 所提算法和對(duì)比算法的共識(shí)時(shí)延實(shí)測(cè)結(jié)果

5.4 吞吐量

RBFT 與PBFT 的吞吐量測(cè)試結(jié)果如圖9 所示。共識(shí)效率是影響TPS 的主要因素，共識(shí)效率越高，交易處理能力越強(qiáng)。此外，節(jié)點(diǎn)并發(fā)度是影響TPS的另一因素，節(jié)點(diǎn)并發(fā)度越高，交易量越大。但區(qū)塊體積增大，對(duì)帶寬的要求更高（實(shí)驗(yàn)時(shí)采用虛擬機(jī)模擬環(huán)境，并未達(dá)到帶寬上限，可等效為無(wú)窮大）。影響TPS 的因素還包括各節(jié)點(diǎn)對(duì)并發(fā)數(shù)據(jù)的處理能力、對(duì)數(shù)據(jù)庫(kù)的I/O 讀寫(xiě)能力等。

圖9 RBFT 與PBFT 的吞吐量測(cè)試結(jié)果

從圖9 可以看出，隨著節(jié)點(diǎn)數(shù)量的增加，節(jié)點(diǎn)并發(fā)度增加，但由于PBFT 在節(jié)點(diǎn)增加時(shí)共識(shí)效率降低，交易處理耗時(shí)更長(zhǎng)，吞吐量降低。對(duì)于RBFT，節(jié)點(diǎn)被分為四組，當(dāng)增加組內(nèi)節(jié)點(diǎn)數(shù)時(shí)，由5.3 節(jié)可知，算法共識(shí)效率影響較小，節(jié)點(diǎn)并發(fā)度是影響TPS 的主要因素。隨著節(jié)點(diǎn)數(shù)量的增大，TPS 逐漸增大。當(dāng)固定組內(nèi)節(jié)點(diǎn)數(shù)增加分組數(shù)時(shí)，共識(shí)效率成為影響TPS 的主要因素。隨著分組數(shù)的增加，TPS 逐漸下降。但在同等網(wǎng)絡(luò)規(guī)模情況下，RBFT 的TPS 約為經(jīng)典PBFT 的300%～400%。因此，RBFT 更適用于對(duì)TPS 要求更高的聯(lián)盟鏈應(yīng)用場(chǎng)景。

5.5 容錯(cuò)性

監(jiān)督節(jié)點(diǎn)的數(shù)量不會(huì)影響RBFT 的共識(shí)效率與TPS，這是因?yàn)楸O(jiān)督節(jié)點(diǎn)本身位于多個(gè)組內(nèi)，在參與共識(shí)過(guò)程中的通信是獨(dú)立的，監(jiān)督節(jié)點(diǎn)本身的通信強(qiáng)度增加，但是共識(shí)算法整體的通信強(qiáng)度不變。在容錯(cuò)性上，一個(gè)監(jiān)督節(jié)點(diǎn)出錯(cuò)相當(dāng)于包含該監(jiān)督節(jié)點(diǎn)的分組都有一個(gè)節(jié)點(diǎn)出錯(cuò)，RBFT 算法的最大容錯(cuò)由式(5)給出。RBFT 共識(shí)機(jī)制與經(jīng)典PBFT 共識(shí)機(jī)制、Raft 共識(shí)機(jī)制的最大容錯(cuò)性能對(duì)比如圖10所示。

由圖10 可以看出，RBFT 具有比PBFT 和Raft更高的容錯(cuò)性。如當(dāng)網(wǎng)絡(luò)被分為四組，每三組分配一個(gè)監(jiān)督節(jié)點(diǎn)時(shí)（相當(dāng)于圖3(b)分組方式2），則N=8。單獨(dú)采用PBFT 的最大容錯(cuò)為2，采用Raft 的最大容錯(cuò)為3，而采用RBFT 的最大容錯(cuò)為4（相當(dāng)于三組共識(shí)，每組2 個(gè)節(jié)點(diǎn)，三組共用一個(gè)監(jiān)督節(jié)點(diǎn)的極限情況）。隨著網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模的擴(kuò)大，RBFT 容錯(cuò)性增加。因此，RBFT 具有高安全性。

圖10 RBFT 共識(shí)機(jī)制與經(jīng)典PBFT 共識(shí)機(jī)制、Raft 共識(shí)機(jī)制的最大容錯(cuò)性能對(duì)比

6 結(jié)束語(yǔ)

本文提出了一種基于Raft 集群的拜占庭容錯(cuò)共識(shí)機(jī)制——RBFT。所提共識(shí)機(jī)制很好地融合了Raft 共識(shí)效率高和PBFT 拜占庭容錯(cuò)性好的特點(diǎn)。測(cè)試結(jié)果表明，該共識(shí)機(jī)制具有通信開(kāi)銷小、時(shí)延低、吞吐量高、容錯(cuò)性強(qiáng)、可擴(kuò)展性高的優(yōu)勢(shì)，適用于大規(guī)模節(jié)點(diǎn)網(wǎng)絡(luò)，能有效突破制約當(dāng)前聯(lián)盟鏈落地的性能瓶頸，有助于推動(dòng)聯(lián)盟鏈的發(fā)展。未來(lái)研究可以結(jié)合跨鏈技術(shù)，進(jìn)一步解決聯(lián)盟鏈單鏈的擴(kuò)展性低、隱私隔離性差的問(wèn)題。