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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

1.1 PBFT共識算法

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

Fig.1 PBFT consensus process圖1 PBFT共識過程

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

1.2 Raft共識機制

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

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

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

（3）Candidate。在Leader 選舉過程中由Follower 過渡為Leader的臨時狀態(tài)。

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

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

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

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

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

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

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

1.2.2 日志復(fù)制

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

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

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

2 BRaft共識算法

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

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

2.1 前提與假設(shè)

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

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

2.2 簽名驗證

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

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

算法1簽名驗證算法

2.3 共識過程

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

Fig.4 BRaft consensus process圖4 BRaft共識過程

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

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

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

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

3 算法分析

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

3.1 安全性

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

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

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

3.2 活性

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

4 實驗與分析

4.1 實驗環(huán)境

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

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

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

4.2 吞吐量

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

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

Fig.5 Throughput圖5 吞吐量

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

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

4.3 時延

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

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

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

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

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

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

5 結(jié)語

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