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

（太原科技大學 計算機科學與技術學院，山西 太原 030024）

0 引言

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

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

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

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

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

1 相關工作

1.1 PBFT共識算法

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

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

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

1.2 Raft共識機制

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

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

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

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

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

RequestVoteRPC：用來進行投票請求，包含Candidate節(jié)點的當前任期、日志中最后一條日志項的索引和任期等［17］，接收到請求的Follower 通過驗證當前Candidate 節(jié)點提供的任期號，選取最優(yōu)Leader，避免拜占庭Leader 節(jié)點丟棄日志或對日志任意排序。

AppendEntriesRPC：用來進行日志復制，包含領導者id、領導者當前任期term、新附加的日志項、前一個條目在Leader 日志中的索引prevLogIndex、任期prevLogterm 以及提交索引commitIndex。

1.2.1 領導者選舉

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

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

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

1.2.2 日志復制

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

Fig.3 Log copy process圖3 日志復制過程

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

2 BRaft共識算法

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

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

2.1 前提與假設

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

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

2.2 簽名驗證

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

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

算法1簽名驗證算法

2.3 共識過程

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

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

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

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

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

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

3 算法分析

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

3.1 安全性

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

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

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

3.2 活性

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

4 實驗與分析

4.1 實驗環(huán)境

在實際運行環(huán)境中，節(jié)點間的通信均通過RPC 實現(xiàn)，對外提供完全一致的接口。實驗環(huá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 算法進行數(shù)據(jù)吞吐量測試。測試過程采用Jmater 工具，通過設置不同線程數(shù)模擬多個客戶端向Leader節(jié)點發(fā)送Request消息，最后隨機選取10組數(shù)據(jù)進行比較。由于BRaft算法在日志復制過程中存在對消息簽名的解密驗證，比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ù)吞吐量的關系如圖6 所示。實驗結果表明，隨著節(jié)點數(shù)量的增加，BRaft 的數(shù)據(jù)吞吐量所受到的影響較小，是因為BRaft 算法在Raft 算法原有共識邏輯的基礎上，擁有比PBFT 更低的通信復雜度。

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

4.3 時延

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

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

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

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

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

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

5 結語

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