白尚旺，達(dá)泓宇，高改梅，劉春霞，黨偉超

（太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024）

0 引言

2008 年，中本聰首次提出比特幣，數(shù)字貨幣進(jìn)入了新篇章［1］。在比特幣創(chuàng)始論文中，區(qū)塊鏈被定義為一種數(shù)據(jù)結(jié)構(gòu)，其實(shí)質(zhì)是一個(gè)由區(qū)塊構(gòu)成的去中心化的鏈?zhǔn)劫~本，每個(gè)區(qū)塊按時(shí)間順序表示用戶之間的事務(wù)傳輸。區(qū)塊鏈具有去中心化、不可篡改、匿名性等基本特性［2］，因此它還可以作為一個(gè)分布式網(wǎng)絡(luò)協(xié)議，使彼此不認(rèn)識(shí)的不同參與者之間建立信任關(guān)系［3］，而不涉及任何中心角色或第三方。共識(shí)算法作為區(qū)塊鏈中的最重要一環(huán)，著重解決存在故障時(shí)如何協(xié)調(diào)分布式節(jié)點(diǎn)之間的交互，保證各節(jié)點(diǎn)所維護(hù)的數(shù)據(jù)副本的一致性，避免出現(xiàn)數(shù)據(jù)不一致、信息不對(duì)稱等問(wèn)題。根據(jù)區(qū)塊鏈的去中心化程度，可將其劃分為公有鏈、聯(lián)盟鏈和私有鏈。對(duì)于不同的區(qū)塊鏈，采用的共識(shí)算法也不同。

以比特幣、以太坊為代表的公有鏈去中心化程度最高，通常采用的共識(shí)機(jī)制有工作量證明機(jī)制PoW（Proof of Work）［4］、權(quán)益證明機(jī)制（Proof of Stake，PoS）［5］、委托權(quán)益證明（Delegated proof of stake，DPoS）［6］。私有鏈的去中心化程度最低，它的寫入權(quán)限由個(gè)人或某個(gè)組織機(jī)構(gòu)所掌握，一般應(yīng)用于企業(yè)內(nèi)部。以Hyperledger Fabric 為代表的聯(lián)盟鏈去中心化程度介于二者之間，一般由多個(gè)機(jī)構(gòu)共同參與管理，并允許授權(quán)的節(jié)點(diǎn)加入網(wǎng)絡(luò)。與公有鏈相比，具有更好的交易速度和安全性，是區(qū)塊鏈落地的主要方向。

目前，聯(lián)盟鏈共識(shí)算法主要分為拜占庭容錯(cuò)（Byzantine Fault Tolerance，BFT）共識(shí)算法［7］和非拜占庭容錯(cuò)共識(shí)算法兩類。BFT 算法的核心就是在存在惡意節(jié)點(diǎn)的情況下，保證其余正常節(jié)點(diǎn)間能夠達(dá)成共識(shí)。常用的BFT 共識(shí)機(jī)制主要有實(shí)用拜占庭容錯(cuò)（Practical Byzantine Fault Tolerance，PBFT）［8］、聯(lián)邦拜占庭容錯(cuò)（Federal Byzantine Fault Tolerance，F(xiàn)BFT）［9］和投機(jī)拜占庭容錯(cuò)（Speculative Byzantine Fault Tolerance，SBFT）［10］共識(shí)機(jī)制，但這類共識(shí)算法普遍存在通信復(fù)雜度較高的問(wèn)題。

非拜占庭容錯(cuò)共識(shí)算法是建立在對(duì)所有節(jié)點(diǎn)的信任機(jī)制上，具有低時(shí)延、高吞吐量的優(yōu)勢(shì)，常見(jiàn)的有Paxos［11］、Raft［12］共識(shí)算法，但不能容忍拜占庭節(jié)點(diǎn)的存在，由此提出一系列共識(shí)算法的改進(jìn)方案。Copeland 等［13］結(jié)合Raft共識(shí)算法和PBFT 共識(shí)算法的優(yōu)點(diǎn)提出Tangaroa 共識(shí)算法，該算法在日志復(fù)制的過(guò)程中添加了哈希函數(shù)，確保在有惡意節(jié)點(diǎn)攻擊的情況下仍能保持安全性，但是該算法無(wú)法容忍多個(gè)拜占庭節(jié)點(diǎn)的聯(lián)合攻擊。Martino 等［14］在Tangaroa 共識(shí)算法的基礎(chǔ)上提出一種新型高性能或可擴(kuò)展性的BFT 共識(shí)算法Scal-ableBFT，可用于實(shí)現(xiàn)大規(guī)模的高性能許可私有鏈。黃冬艷等［15］提出一種基于Raft 集群的拜占庭容錯(cuò)共識(shí)算法RBFT，將節(jié)點(diǎn)進(jìn)行分組，組內(nèi)采用Raft共識(shí)機(jī)制，而每組的Leader 節(jié)點(diǎn)重新構(gòu)成一個(gè)管理組實(shí)行PBFT 算法。該算法較好地融合了Raft共識(shí)效率高和PBFT拜占庭容錯(cuò)性能好的特點(diǎn)，但需要引入大量的監(jiān)督節(jié)點(diǎn)。

本文在分析Raft 算法的不足后，通過(guò)對(duì)已有拜占庭算法進(jìn)行研究，使用RSA 簽名以防止節(jié)點(diǎn)身份偽造和消息篡改，解決在共識(shí)過(guò)程中Leader 節(jié)點(diǎn)作惡的問(wèn)題。同時(shí)，在PBFT 算法三段協(xié)議的基礎(chǔ)上引入標(biāo)識(shí)位W 保證算法的一致性，實(shí)現(xiàn)Raft 算法在日志復(fù)制過(guò)程中的拜占庭容錯(cuò)，目的在于提高Raft 算法安全性的同時(shí)又保證比PBFT 更低的算法復(fù)雜度。

1 相關(guān)工作

1.1 PBFT共識(shí)算法

PBFT 共識(shí)機(jī)制將原始拜占庭容錯(cuò)共識(shí)算法的通信復(fù)雜度從指數(shù)級(jí)降到了多項(xiàng)式級(jí)，共識(shí)效率得到明顯提高。PBFT算法中的核心概念有3個(gè)部分：視圖（view）、副本（replica）、角色（primary，backups）。視圖表示當(dāng)前系統(tǒng)的全局狀態(tài)，副本表示系統(tǒng)中所有參與共識(shí)的節(jié)點(diǎn)，而在每個(gè)視圖中，副本的角色又分為兩類：主節(jié)點(diǎn)（primary）和備份節(jié)點(diǎn)（backups）。假設(shè)系統(tǒng)中的惡意節(jié)點(diǎn)數(shù)為f，PBFT 需要滿足總節(jié)點(diǎn)數(shù)至少為3f+1。算法的共識(shí)過(guò)程如圖1所示。

Fig.1 PBFT consensus process圖1 PBFT共識(shí)過(guò)程

PBFT 的具體執(zhí)行步驟如下：①請(qǐng)求階段，客戶端向主節(jié)點(diǎn)發(fā)送請(qǐng)求；②預(yù)準(zhǔn)備階段，主節(jié)點(diǎn)在收到客戶端發(fā)出的請(qǐng)求后，先檢查請(qǐng)求的合法性，若合法，主節(jié)點(diǎn)將此消息寫入本地日志然后進(jìn)入預(yù)準(zhǔn)備階段，并向其他副本節(jié)點(diǎn)廣播預(yù)準(zhǔn)備消息；③準(zhǔn)備階段，副本節(jié)點(diǎn)在收到消息后先確認(rèn)消息的正確性，若正確就進(jìn)入準(zhǔn)備階段，并向其他副本節(jié)點(diǎn)廣播準(zhǔn)備消息，同時(shí)將預(yù)準(zhǔn)備消息和準(zhǔn)備消息寫入本地日志；④確認(rèn)階段，當(dāng)一個(gè)節(jié)點(diǎn)在一段時(shí)間內(nèi)接收到2f個(gè)以上的準(zhǔn)備消息，就發(fā)送確認(rèn)消息給所有副本節(jié)點(diǎn)；⑤應(yīng)答階段，副本節(jié)點(diǎn)接收到2f個(gè)來(lái)自其他節(jié)點(diǎn)的確認(rèn)消息后，驗(yàn)證消息的一致性，并向客戶端返回應(yīng)答消息。客戶端收到2f+1個(gè)應(yīng)答消息，表明共識(shí)完成。

1.2 Raft共識(shí)機(jī)制

Raft 算法是Paxos 算法的改進(jìn)，是從多副本狀態(tài)機(jī)的角度提出，用來(lái)對(duì)多副本狀態(tài)機(jī)的日志復(fù)制進(jìn)行管理［16］。一個(gè)Raft群集中有若干個(gè)成員節(jié)點(diǎn)，這些節(jié)點(diǎn)有3 種角色：領(lǐng)導(dǎo)者（Leader）、參與者（Candidate）和跟隨者（Follower），并由Leader統(tǒng)一管理。

（1）Leader。Leader 由Candidate 通過(guò)領(lǐng)導(dǎo)者選舉協(xié)議選舉產(chǎn)生，用于接收客戶端的請(qǐng)求，并將客戶端請(qǐng)求對(duì)應(yīng)的日志項(xiàng)追加到自己的日志中，然后轉(zhuǎn)發(fā)給Follower 進(jìn)行復(fù)制，當(dāng)日志復(fù)制到大多數(shù)節(jié)點(diǎn)時(shí)，Leader 將發(fā)送請(qǐng)求給Follower 進(jìn)行日志提交。

（2）Follower。Follower 接收并復(fù)制由Leader 同步的日志。在Leader廣播可以提交日志后，提交日志。

（3）Candidate。在Leader 選舉過(guò)程中由Follower 過(guò)渡為L(zhǎng)eader的臨時(shí)狀態(tài)。

參與共識(shí)的節(jié)點(diǎn)之間通過(guò)異步遠(yuǎn)程過(guò)程調(diào)用（RPC）進(jìn)行交互，調(diào)用請(qǐng)求主要分為以下兩種：

RequestVoteRPC：用來(lái)進(jìn)行投票請(qǐng)求，包含Candidate節(jié)點(diǎn)的當(dāng)前任期、日志中最后一條日志項(xiàng)的索引和任期等［17］，接收到請(qǐng)求的Follower 通過(guò)驗(yàn)證當(dāng)前Candidate 節(jié)點(diǎn)提供的任期號(hào)，選取最優(yōu)Leader，避免拜占庭Leader 節(jié)點(diǎn)丟棄日志或?qū)θ罩救我馀判颉?/p>

AppendEntriesRPC：用來(lái)進(jìn)行日志復(fù)制，包含領(lǐng)導(dǎo)者id、領(lǐng)導(dǎo)者當(dāng)前任期term、新附加的日志項(xiàng)、前一個(gè)條目在Leader 日志中的索引prevLogIndex、任期prevLogterm 以及提交索引commitIndex。

1.2.1 領(lǐng)導(dǎo)者選舉

圖2 描述了3 種不同狀態(tài)節(jié)點(diǎn)之間的關(guān)系。當(dāng)服務(wù)器啟動(dòng)時(shí)，所有節(jié)點(diǎn)初始狀態(tài)為Follower。經(jīng)過(guò)一段隨機(jī)時(shí)間后，F(xiàn)ollower 節(jié)點(diǎn)當(dāng)前任期加一，然后轉(zhuǎn)變?yōu)镃andidate 節(jié)點(diǎn)，Candidate 節(jié)點(diǎn)首先給自己投票，隨后將RequestVote 請(qǐng)求發(fā)送給Follower 節(jié)點(diǎn)以獲取唯一投票。當(dāng)Candidate 節(jié)點(diǎn)接收到大多數(shù)選票時(shí)，轉(zhuǎn)變?yōu)長(zhǎng)eader節(jié)點(diǎn)［18］。

Fig.2 Raft state transitions圖2 Raft狀態(tài)轉(zhuǎn)換

收到投票請(qǐng)求的Follower 節(jié)點(diǎn)首先會(huì)檢查Candidate最后一條日志項(xiàng)的任期號(hào)，只有在發(fā)出RPC 的Candidate的日志項(xiàng)具有的任期號(hào)比它本地保存的日志項(xiàng)的任期號(hào)更大，或者在任期號(hào)相同但具有比它更大的索引值時(shí)，F(xiàn)ollower才會(huì)將他們的選票授予該節(jié)點(diǎn)。

1.2.2 日志復(fù)制

日志是由日志項(xiàng)組成，日志項(xiàng)是一種包含用戶指定的數(shù)據(jù)、索引值、Leader 節(jié)點(diǎn)任期的數(shù)據(jù)格式。如圖3 所示，首先，客戶端向Leader 節(jié)點(diǎn)發(fā)送需要執(zhí)行的請(qǐng)求；其次，Leader 節(jié)點(diǎn)在收到客戶端請(qǐng)求后會(huì)將帶有客戶端命令的日志項(xiàng)追加到自己的日志中，并向Follower 節(jié)點(diǎn)發(fā)送AppendEntriesRPC，進(jìn)行日志復(fù)制。

Fig.3 Log copy process圖3 日志復(fù)制過(guò)程

收到AppendEntriesRPC 請(qǐng)求的Follower 節(jié)點(diǎn)首先將自身最新條目與RPC 中的條目進(jìn)行比較。如果兩個(gè)日志項(xiàng)具有相同的索引和任期，F(xiàn)ollower 會(huì)將接收到的新的日志項(xiàng)附加到其日志并將AppendEntriesRPC 發(fā)送給Leader，表示復(fù)制成功。當(dāng)Leader 在收到集群中大多數(shù)Follower 復(fù)制成功的響應(yīng)后，將此日志項(xiàng)標(biāo)記為已提交。日志項(xiàng)中的指令交由狀態(tài)機(jī)執(zhí)行，并將結(jié)果反饋給客戶端。

2 BRaft共識(shí)算法

在Raft 算法中，日志是否提交由Leader 節(jié)點(diǎn)判斷，Leader 節(jié)點(diǎn)在向所有Follower 節(jié)點(diǎn)復(fù)制日志項(xiàng)時(shí)，如果收到一定數(shù)量Follower 節(jié)點(diǎn)的響應(yīng)，Leader 將日志項(xiàng)中的指令交由狀態(tài)機(jī)執(zhí)行，并在未來(lái)的心跳消息或者日志復(fù)制消息中廣播給Follower 節(jié)點(diǎn)。但在拜占庭環(huán)境下，Leader 節(jié)點(diǎn)可以發(fā)送錯(cuò)誤消息給Follower 節(jié)點(diǎn)，F(xiàn)ollower 節(jié)點(diǎn)可以在沒(méi)有將日志項(xiàng)添加至日志列表時(shí)惡意響應(yīng)Leader，以誤導(dǎo)Leader 收到了一定數(shù)量的響應(yīng)。由此可知，僅依賴Leader無(wú)法確保日志項(xiàng)被正確復(fù)制，進(jìn)而無(wú)法確保算法安全性。

BRaft 通過(guò)對(duì)客戶端的消息進(jìn)行數(shù)字簽名以防止拜占庭節(jié)點(diǎn)作惡。在Follower 節(jié)點(diǎn)對(duì)Leader 的消息進(jìn)行驗(yàn)證之后，算法在結(jié)合PBFT 的三段協(xié)議的基礎(chǔ)上引入標(biāo)識(shí)位W，確保在拜占庭節(jié)點(diǎn)作惡的情況下日志項(xiàng)依然能夠被正確提交。這樣，不僅減少了Follower 節(jié)點(diǎn)作惡的可能性，并且相比于PBFT 算法的準(zhǔn)備和確認(rèn)階段，節(jié)點(diǎn)之間不再需要額外通信，理論上提高了日志追加的時(shí)效。

2.1 前提與假設(shè)

假設(shè)BRaft 集群中一共包含n 個(gè)節(jié)點(diǎn)，f 個(gè)拜占庭節(jié)點(diǎn)BRaft算法需要滿足式（1）以確保算法的容錯(cuò)能力。

在共識(shí)過(guò)程中，節(jié)點(diǎn)存在宕機(jī)或者作惡的可能性，BRaft 的容錯(cuò)能力分兩種情況：①當(dāng)Leader 節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，F(xiàn)ollower 集群節(jié)點(diǎn)數(shù)為n-1，F(xiàn)ollower 節(jié)點(diǎn)中存在的拜占庭節(jié)點(diǎn)數(shù)為f-1，如果n-1-（f-1）個(gè)節(jié)點(diǎn)已經(jīng)達(dá)成共識(shí)，來(lái)自f-1 個(gè)拜占庭節(jié)點(diǎn)的決策不會(huì)影響正常節(jié)點(diǎn)的決策（n-1-（f-1）-（f-1）＞f-1），由此可知BRaft 集群節(jié)點(diǎn)總數(shù)需要滿足n＞3f-2；②當(dāng)Leader 節(jié)點(diǎn)為正常節(jié)點(diǎn)時(shí)，F(xiàn)ollower 集群節(jié)點(diǎn)數(shù)為n-1，F(xiàn)ollower 節(jié)點(diǎn)中存在的拜占庭節(jié)點(diǎn)數(shù)為f，如果n-1-f個(gè)節(jié)點(diǎn)已經(jīng)達(dá)成共識(shí)，來(lái)自f個(gè)拜占庭節(jié)點(diǎn)的決策不會(huì)影響正常節(jié)點(diǎn)的決策（n-1-f-f＞f），此時(shí)BRaft 集群節(jié)點(diǎn)總數(shù)需要滿足n＞3f+1。

2.2 簽名驗(yàn)證

BRaft 通過(guò)RSA 數(shù)字簽名作為消息被篡改的檢測(cè)機(jī)制，且在算法運(yùn)行過(guò)程中，所有的共識(shí)節(jié)點(diǎn)均擁有客戶端的公鑰PK。在簽名過(guò)程中，首先，客戶端對(duì)原文進(jìn)行Hash運(yùn)算，得到摘要M，并使用客戶端私鑰SK對(duì)摘要M進(jìn)行加密，形成數(shù)字簽名D；然后，將原文和數(shù)字簽名一同發(fā)送給Leader，Leader 節(jié)點(diǎn)在收到客戶端發(fā)來(lái)的數(shù)字簽名及原文后，會(huì)將自身信息與客戶端消息打包一起發(fā)給Follower 節(jié)點(diǎn)，F(xiàn)ollower 節(jié)點(diǎn)在收到數(shù)字簽名后，先用客戶端公鑰PK對(duì)摘要進(jìn)行解密，確定是客戶端消息之后，再用同樣的Hash 算法對(duì)原文計(jì)算摘要值，判斷Leader 是否對(duì)消息進(jìn)行篡改。

在Follower 節(jié)點(diǎn)對(duì)客戶端消息驗(yàn)證之后，BRaft 結(jié)合PBFT 三段協(xié)議的思想，并通過(guò)標(biāo)識(shí)位W保持在拜占庭環(huán)境節(jié)點(diǎn)的一致性，即每一個(gè)Follower 節(jié)點(diǎn)存在一個(gè)標(biāo)識(shí)位W（0 表示驗(yàn)證不通過(guò)，1 表示驗(yàn)證通過(guò)），每個(gè)標(biāo)識(shí)位的初始狀態(tài)為0。當(dāng)Follower 節(jié)點(diǎn)經(jīng)過(guò)驗(yàn)證之后的標(biāo)識(shí)位c為1，且有2f+1 個(gè)c發(fā)生變化且值的總和至少為f+1 時(shí)，可以證明Leader 為正常節(jié)點(diǎn)。當(dāng)Follower 節(jié)點(diǎn)經(jīng)過(guò)驗(yàn)證之后的標(biāo)識(shí)位c為0，F(xiàn)ollower 集群中當(dāng)有2f-1 個(gè)標(biāo)識(shí)位發(fā)生變化，且這2f-1 個(gè)c值的總和至多為f-1 時(shí)，證明Leader 節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，此時(shí)系統(tǒng)重新進(jìn)行選舉。

算法1簽名驗(yàn)證算法

2.3 共識(shí)過(guò)程

BRaft 將共識(shí)過(guò)程分為4 個(gè)階段：提出區(qū)塊、驗(yàn)證區(qū)塊、更新區(qū)塊和應(yīng)答階段。具體共識(shí)過(guò)程如圖4所示。

Fig.4 BRaft consensus process圖4 BRaft共識(shí)過(guò)程

（1）提出區(qū)塊。Leader 節(jié)點(diǎn)收集客戶端請(qǐng)求＜Client-Request，X＞sig，并驗(yàn)證請(qǐng)求的合法性，若不合法，直接丟棄，若合法，Leader 節(jié)點(diǎn)將客戶端請(qǐng)求對(duì)應(yīng)的日志項(xiàng)追加到自己的日志中，并在Client-Request 的基礎(chǔ)上加上領(lǐng)導(dǎo)者id、領(lǐng)導(dǎo)者當(dāng)前任期term、前一個(gè)日志項(xiàng)在Leader 日志中的索引prevLogIndex、任期prevLogterm，形成＜Prepare-Request，X＞，并廣播給其他Follower 節(jié)點(diǎn)。

（2）驗(yàn)證區(qū)塊。當(dāng)Follower 節(jié)點(diǎn)i收到來(lái)自Leader 節(jié)點(diǎn)的＜Prepare-Request，X＞請(qǐng)求后，驗(yàn)證以下條件：①通過(guò)Verify（PK，D，X）驗(yàn)證Leader 節(jié)點(diǎn)是否篡改客戶端消息；②驗(yàn)證新附加的日志項(xiàng)的任期號(hào)term是否大于等于Follower 本身的任期號(hào)；③驗(yàn)證本地日志的prevLogIndex位置處的日志項(xiàng)與對(duì)應(yīng)的prevLogterm是否匹配。如果以上條件都滿足，則Follower 節(jié)點(diǎn)i接受來(lái)自Leader 節(jié)點(diǎn)的Prepare-Request 請(qǐng)求。此時(shí)，標(biāo)識(shí)位Wi為1，并向Leader 節(jié)點(diǎn)發(fā)送＜AgreePrepare-Request，Wi＞。

（3）更新區(qū)塊鏈。當(dāng)Leader 節(jié)點(diǎn)收到2f+1 個(gè)Follower節(jié)點(diǎn)發(fā)來(lái)的＜AgreePrepare-Request，Wi＞時(shí)，且這2f+1 個(gè)Wi值的總和至少為f+1，可以證明Follower 節(jié)點(diǎn)已經(jīng)做好準(zhǔn)備進(jìn)行日志復(fù)制。此時(shí)Leader 節(jié)點(diǎn)廣播＜AppendEntries，X＞給集群中的所有Follower 節(jié)點(diǎn)。

（4）應(yīng)答。Follower 節(jié)點(diǎn)收到＜AppendEntries，X＞后根據(jù)條件在本地追加收到的日志項(xiàng)，響應(yīng)追加結(jié)果。當(dāng)Leader 節(jié)點(diǎn)在收到2f+1 個(gè)應(yīng)答結(jié)果時(shí)，表示共識(shí)已完成。Leader 將日志項(xiàng)中的指令交由狀態(tài)機(jī)執(zhí)行，隨后將處理結(jié)果返回給客戶端并通過(guò)心跳消息通知Follower 節(jié)點(diǎn)執(zhí)行已提交的日志項(xiàng)。

3 算法分析

BRaft 算法作為Raft 的改進(jìn)算法，需要在存在惡意節(jié)點(diǎn)的情況下，保證算法的安全性和活性，下文將對(duì)以上兩點(diǎn)進(jìn)行具體分析。

3.1 安全性

安全性是指所有壞的事情不會(huì)發(fā)生，BRaft 算法的安全性體現(xiàn)在兩方面：Leader 節(jié)點(diǎn)選舉階段的安全性和日志復(fù)制階段的安全性。

在Leader 選舉階段，BRaft 通過(guò)心跳觸發(fā)Leader 選舉。Leader 節(jié)點(diǎn)會(huì)定期向Follower 節(jié)點(diǎn)發(fā)送心跳消息（包含在AppendEntriesRPC 中），以證明節(jié)點(diǎn)的正常運(yùn)行。如果Follower 節(jié)點(diǎn)在一段時(shí)間內(nèi)沒(méi)有收到Leader 的心跳，就會(huì)在一段隨機(jī)時(shí)間之后轉(zhuǎn)換為Candidate 節(jié)點(diǎn)，觸發(fā)新一輪的選舉。Candidate 節(jié)點(diǎn)向其余Follower 節(jié)點(diǎn)發(fā)送RequestVote請(qǐng)求，以獲取唯一投票。RequestVote 請(qǐng)求包含當(dāng)前節(jié)點(diǎn)最后一條日志項(xiàng)的任期和索引，只有發(fā)出投票請(qǐng)求的Candidate 節(jié)點(diǎn)的任期及索引比將要進(jìn)行投票的Follower 節(jié)點(diǎn)更高時(shí)，F(xiàn)ollower 才會(huì)將他們的選票授予該節(jié)點(diǎn)，以此保證整個(gè)選舉過(guò)程的安全性。

在日志復(fù)制階段，BRaft 算法保留了Raft 算法的日志結(jié)構(gòu)，通過(guò)數(shù)字簽名實(shí)現(xiàn)消息篡改檢測(cè)和防止身份偽造，并依賴PBFT 三段協(xié)議保證共識(shí)的一致性，保證了拜占庭節(jié)點(diǎn)存在情況下日志仍能夠被正確提交。BRaft 修改了狀態(tài)機(jī)提交需要1/2 節(jié)點(diǎn)同意的前提，當(dāng)Leader 節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，在容錯(cuò)范圍f＜(n+2)/3 內(nèi)，可以保證BRaft 的安全性。當(dāng)Leader 節(jié)點(diǎn)為正常節(jié)點(diǎn)時(shí)，在容錯(cuò)范圍f＜(n-1)/3內(nèi)，可以保證BRaft算法的安全性。

3.2 活性

活性（Liveness）是分布式共識(shí)算法的另一重要屬性，是指所有好的事情一定發(fā)生。BRaft 算法保證在任何時(shí)刻算法均具備可用性，它是單Leader 的拜占庭容錯(cuò)算法，即任意時(shí)刻BRaft 需要存在一個(gè)可用的Leader。當(dāng)Leader 節(jié)點(diǎn)是正常節(jié)點(diǎn)時(shí)，算法始終遵循算法正常的日志復(fù)制邏輯運(yùn)行，當(dāng)Leader 節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)時(shí)，將篡改后的日志項(xiàng)發(fā)給其余Follower 節(jié)點(diǎn)，F(xiàn)ollower 節(jié)點(diǎn)在收到日志項(xiàng)后，通過(guò)數(shù)字簽名可以發(fā)現(xiàn)日志項(xiàng)被篡改，拒絕將日志項(xiàng)添加到其日志列表中，并轉(zhuǎn)換為Candidate 狀態(tài)，發(fā)起新一輪的Leader 選舉。此時(shí)，之前被篡改的日志項(xiàng)并未在集群中達(dá)成共識(shí)，而發(fā)起投票的Candidate 在獲得一定數(shù)量投票后，成為新一輪的Leader，BRaft 集群即恢復(fù)正常運(yùn)行狀態(tài)，上述整個(gè)過(guò)程僅耗費(fèi)了一次Leader 選舉耗時(shí)，BRaft 算法保持著極高的活性。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

在實(shí)際運(yùn)行環(huán)境中，節(jié)點(diǎn)間的通信均通過(guò)RPC 實(shí)現(xiàn)，對(duì)外提供完全一致的接口。實(shí)驗(yàn)環(huán)境相關(guān)軟硬件信息如表1所示，節(jié)點(diǎn)IP地址如表2所示。

Table 1 Experimental environment configuration information表1 實(shí)驗(yàn)環(huán)境配置信息

Table 2 Node IP address表2 節(jié)點(diǎn)IP地址

4.2 吞吐量

吞吐量指區(qū)塊鏈每秒鐘處理交易的數(shù)量，吞吐量越高代表算法在單位時(shí)間能處理的交易越多，性能越好。

在相同實(shí)驗(yàn)環(huán)境下，對(duì)Raft、BRaft 和PBFT 算法進(jìn)行數(shù)據(jù)吞吐量測(cè)試。測(cè)試過(guò)程采用Jmater 工具，通過(guò)設(shè)置不同線程數(shù)模擬多個(gè)客戶端向Leader節(jié)點(diǎn)發(fā)送Request消息，最后隨機(jī)選取10組數(shù)據(jù)進(jìn)行比較。由于BRaft算法在日志復(fù)制過(guò)程中存在對(duì)消息簽名的解密驗(yàn)證，比Raft 算法的數(shù)據(jù)吞吐量低10%左右，但與PBFT 算法相比，數(shù)據(jù)吞吐量提高1/4左右，因而BRaft在性能上仍有很大優(yōu)勢(shì)，如圖5所示。

Fig.5 Throughput圖5 吞吐量

BRaft 共識(shí)算法在保證其他條件不變的情況下，分別測(cè)試了5 節(jié)點(diǎn)、10 節(jié)點(diǎn)、15 節(jié)點(diǎn)、20 節(jié)點(diǎn)下的數(shù)據(jù)吞吐量。節(jié)點(diǎn)數(shù)量和數(shù)據(jù)吞吐量的關(guān)系如圖6 所示。實(shí)驗(yàn)結(jié)果表明，隨著節(jié)點(diǎn)數(shù)量的增加，BRaft 的數(shù)據(jù)吞吐量所受到的影響較小，是因?yàn)锽Raft 算法在Raft 算法原有共識(shí)邏輯的基礎(chǔ)上，擁有比PBFT 更低的通信復(fù)雜度。

Fig.6 The relationship between the number of nodes and data throughput圖6 節(jié)點(diǎn)數(shù)量與數(shù)據(jù)吞吐量關(guān)系

4.3 時(shí)延

時(shí)延是衡量拜占庭容錯(cuò)的分布式共識(shí)算法的另一個(gè)重要指標(biāo)，時(shí)延標(biāo)識(shí)了單個(gè)請(qǐng)求從被客戶端發(fā)送開(kāi)始直至客戶端收到響應(yīng)所需要的時(shí)間，包括客戶端發(fā)送請(qǐng)求、網(wǎng)絡(luò)傳輸、日志復(fù)制和客戶端接收響應(yīng)五階段所需時(shí)間。

圖7 為Raft、BRaft 和PBFT 算法針對(duì)不同數(shù)量的客戶端請(qǐng)求達(dá)成共識(shí)所需時(shí)間。節(jié)點(diǎn)數(shù)目固定（n=5），在客戶端請(qǐng)求數(shù)量從5 遞增至1 000 的過(guò)程中，Raft 和BRaft 所需達(dá)成共識(shí)的時(shí)間均呈線性增長(zhǎng)趨勢(shì)，且當(dāng)客戶端請(qǐng)求數(shù)量等于1 000 時(shí)，Raft 需要4 732 ms 達(dá)成共識(shí)，BRaft 算法需要

Fig.7 Consensus time for different numbers of client request圖7 不同數(shù)量客戶端請(qǐng)求達(dá)成共識(shí)時(shí)間

7 749 ms 達(dá)成共識(shí)，PBFT 需要9 237 ms。雖然，BRaft 應(yīng)用數(shù)字簽名和哈希算法，它們對(duì)性能的損耗存在一定影響，但與PBFT 算法相比，達(dá)成共識(shí)的時(shí)間有了一定提升。

如圖8 所示，W 標(biāo)識(shí)位的使用增加了Follower 節(jié)點(diǎn)響應(yīng)Follower 節(jié)點(diǎn)請(qǐng)求的額外開(kāi)銷，但減少了Follower 節(jié)點(diǎn)反饋錯(cuò)誤消息給Leader 的可能性，且相比于PBFT 這種需要各節(jié)點(diǎn)之間相互進(jìn)行通信的共識(shí)過(guò)程而言，算法的通信復(fù)雜度更低，且本身計(jì)算并不復(fù)雜，網(wǎng)絡(luò)傳輸耗時(shí)可以忽略。

Fig.8 Time consuming to discover malicious nodes圖8 發(fā)現(xiàn)惡意節(jié)點(diǎn)耗時(shí)

5 結(jié)語(yǔ)

本文選取非拜占庭共識(shí)算法Raft 作為研究對(duì)象，針對(duì)拜占庭Leader 節(jié)點(diǎn)篡改客戶端消息的問(wèn)題，采用RSA 數(shù)字簽名作為消息的檢驗(yàn)機(jī)制，同時(shí)在結(jié)合PBFT 的三段協(xié)議的基礎(chǔ)上引入標(biāo)識(shí)位W，實(shí)現(xiàn)Raft 算法在日志復(fù)制過(guò)程中的拜占庭容錯(cuò)，確保在拜占庭節(jié)點(diǎn)發(fā)送錯(cuò)誤消息的情況下日志項(xiàng)依然能夠被正確提交，很好地融合了Raft 高效和PBFT 可容錯(cuò)的特點(diǎn)。經(jīng)過(guò)改進(jìn)的BRaft 共識(shí)算法相較于PBFT 共識(shí)算法通信復(fù)雜度更低，并在保證算法的可理解性和共識(shí)效率的同時(shí)，提高了算法安全性。但是本文算法還存在一些問(wèn)題，如在領(lǐng)導(dǎo)者選舉階段無(wú)法選擇最優(yōu)Leader，以及對(duì)拜占庭節(jié)點(diǎn)無(wú)法進(jìn)行動(dòng)態(tài)刪除、修改等操作，未來(lái)可針對(duì)這些問(wèn)題加以重點(diǎn)研究。