RB-Raft:一種抗拜占庭節點的Raft共識算法

收稿日期：2022-03-22；修回日期：2022-05-05" 基金項目：國家自然科學基金資助項目（61762046，62166019）；江西省教育廳科學技術研究項目（GJJ209412）；國家級大學生創新創業訓練項目（201913434005）

作者簡介：李淑芝（1964-），女，江西贛州人，教授，碩士，主要研究方向為軟件工程、信息隱藏；鄒懿杰（1999-），男，江西贛州人，碩士研究生，主要研究方向為區塊鏈；鄧小鴻（1982-），男（通信作者），湖北天門人，副教授，碩導，博士，主要研究方向為網絡信息安全、區塊鏈（deng_xh@jxust.edu.cn）；羅志瓊（1999-），女，江西吉安人，碩士研究生，主要研究方向為區塊鏈；劉惠文（1987-），女，江西吉安人，講師，碩士，主要研究方向為區塊鏈及其應用.

摘 要：

針對Raft算法無法抵抗拜占庭節點的攻擊和日志易竄改等問題，設計了一種抵抗拜占庭節點的RB-Raft（resist Byzantine-Raft）算法。首先采用哈希鏈的方式對每一塊日志進行迭代哈希處理，通過動態驗證機制對日志進行驗證，使得對leader節點的惡意行為具有一定的容錯率，解決了日志偽造與驗證的問題。其次，提出基于門限加密的遺書機制，使得candidate節點拉取選票具有合法性，防止拜占庭節點隨意拉取選票更換leader節點的攻擊，解決了拜占庭節點影響系統一致性的問題。實驗結果表明，提出的RB-Raft算法具有抗拜占庭節點的能力，其日志識別率可以達到100%。同時，相比PBFT，該算法共識時延降低了53.3%，并且吞吐量提高了61.8%，適用于在不可信聯盟鏈中進行共識。

關鍵詞：共識機制； 拜占庭容錯； 哈希鏈； 門限加密； 遺書機制

中圖分類號：TP393.0"" 文獻標志碼：A"" 文章編號：1001-3695（2022）09-004-2591-06

doi： 10.19734/j.issn.1001-3695.2022.03.0090

RB-Raft：Raft consensus algorithm for anti-Byzantine nodes

Li Shuzhi1， Zou Yijie1， Deng Xiaohong2， Luo Zhiqiong1， Liu Huiwen2

（1.College of Information Science， Jiangxi University of Science amp; Technology， Ganzhou Jiangxi 341000， China; 2.School of Electronics amp; Information Engineering， Gannan University of Science amp; Technology， Ganzhou Jiangxi 341000， China）

Abstract：Aiming at the problems that the Raft algorithm cannot resist the attacks of Byzantine nodes and the logs are easy to tamper with，this paper proposed a RB-Raft algorithm that resisted Byzantine nodes. Firstly，this paper used the method of hash chain to iteratively hash each log. At the same time，it verificated the log through the dynamic verification mechanism，so that the malicious behavior of the leader node had a certain fault tolerance rate，which solved the problem of log forgery and verification. Secondly，this paper proposed a legacy mechanism based on threshold encryption，which made it legal for candidate nodes to pull votes. This mechanism could prevent Byzantine nodes from randomly the attack of pulling votes to replace leader nodes，and solved the problem that Byzantine nodes affect the system consistency. The experimental results show that the proposed RB-Raft algorithm has the ability to resist Byzantine nodes，and its log recognition rate can reach 100%. At the same time，compared with PBFT，the consensus latency of the algorithm in this paper is reduced by 53.3%，and the throughput is increased by 61.8%. The proposed algorithm is suitable for consensus in untrusted consortium chains.

Key words：consensus mechanisms; Byzantine fault tolerance; hash chain; threshold encryption; legacy mechanism

0 引言

中本聰［1］于2008年發表的論文標志著比特幣的正式推出。在隨后的十幾年，區塊鏈作為比特幣的底層核心技術不斷發展，衍生出了不同類型的區塊鏈，如以以太坊［2］為代表的公鏈、以Hyperledger Fabric［3］為代表的聯盟鏈，以及阿里巴巴的螞蟻區塊鏈［4］為代表的私鏈等。區塊鏈是一種去中心化、不可竄改、可追溯的分布式數據庫系統，融合了經濟學、P2P網絡、共識算法、非對稱加密等多種技術，是互聯網技術高度融合的產物。區塊鏈作為一種分布式數據庫系統，其最重要的問題就是設計一種共識算法［5，6］來解決分布式節點之間數據的一致性。在不同的區塊鏈中采用的共識算法不同，比特幣中采用的是工作量證明（proof of work，PoW）［7］，而聯盟鏈中一般采用的是實用拜占庭容錯（practical Byzantine fault tolerance，PBFT）［8］，而在私鏈中就一般采用經典的一致性算法如Raft［9］、Paxos［10］。其中Raft算法在現有的工程領域應用廣泛，是具有強一致性、高性能、高可靠的分布式協議，相比于Paxos易于理解和實現，但是因不能夠抵抗拜占庭節點，所以僅限于私鏈當中。因此如何將Raft算法進行改進，使其能夠運用在聯盟鏈，甚至在公鏈中是當下研究的熱門話題。

將Raft算法移植到聯盟鏈中最大的問題在于如何實現拜占庭容錯［11］，拜占庭容錯是要確保誠實的節點在受到惡意節點干擾的情況下也能達成共識，保證系統正常運行。PBFT降低了拜占庭容錯協議的運行復雜度，使算法復雜度從指數級別O（n（f+1））降低到多項式級別O（n2），使拜占庭協議在分布式系統應用中成為可能，也是現在主流的聯盟鏈中所使用的共識算法。在PBFT中最大容錯節點數量是（n-1）/3，而在Raft算法中最大的容錯節點（宕機節點）數量是（n-1）/2，以及算法通信復雜度上Raft的O（n）也是遠少于PBFT的O（n2），所以研究者們嘗試改進Raft，使之同時具有Raft和PBFT的優點。

2016年，Copeland等人［12］提出在Raft算法基礎上借鑒PBFT算法的一些特性（包括簽名、惡意領導探測、選舉校驗等）來實現拜占庭容錯性，兼顧可實現性和魯棒性。文獻［13］要求follower節點在投出選票時在選票上進行簽名，防止選票被偽造，其次要求客戶端在發送日志時在上面簽名，防止拜占庭的leader偽造日志，在一定程度上提高了抗拜占庭節點能力。文獻［14］針對Raft共識算法leader節點選舉中存在的多candidate節點分票和follower節點增多引發的投票效率問題，利用雙層Kademlia協議建立的K桶實現candidate節點集合內的穩定選舉，并且針對Raft共識算法日志復制過程中，leader節點單節點日志復制過程效率低以及節點負載不均的問題，提出了均衡leader節點負載的多candidate節點并行日志復制方案。文獻［15］采用了兩級共識機制，將Raft中的所有節點進行分組，每個組內選出領導者組成網絡委員會，組內采用Raft共識，網絡委員會中采用PBFT機制進行共識，是將Raft與PBFT結合的一種方式，但是無法有效抑制組內拜占庭節點的存在。文獻［16］將Raft選票拉取過程轉換成閾值簽名過程，阻止了拉取空白選票的行為，并引入增量哈希保證日志不可竄改，增量哈希使得日志體增大，有一定的局限性，而且不能阻止拜占庭節點成為candidate強行拉取選票將leader進行更換。

綜上所述，Raft算法可以通過優化來抵御拜占庭節點，但仍需解決如下問題：a）日志易竄改，沒有進行加密處理；b）選票的投出沒有保障，僅僅靠任期大小判斷是否將選票投出不夠安全以及選票容易造假。針對上述問題，本文提出RB-Raft算法，

對于拜占庭的leader節點容易偽造日志，造成日志被竄改的問題，采用基于哈希鏈的動態日志驗證機制，實現了日志防竄改以及日志可驗證；

對于選票造假以及選票容易被拜占庭節點利用來更換當前leader的問題，設計一種基于門限加密的遺書機制，當leader節點并未宕機時，follower節點都不會將選票投出，除非拿到leader節點宕機后的遺書，而遺書的獲取需要通過門限加密得到，避免了leader節點被拜占庭節點異常替換。

1 問題的提出

1.1 Raft工作流程

在Raft算法中有三種角色，每個節點都能擔任不同的角色，但是不能多種角色存在于同一個節點上。這三種角色分別是leader（領導者）、follower（跟隨者）、candidate（候選者）。每個角色都有著不同的任務：leader負責與客戶端交互信息，并將日志信息同步給follower節點，與follower通過HeartBeat保持聯系；follower負責響應leader的日志同步請求，響應candidate的投票選舉請求，將leader的日志文件同步到本地，在所有節點剛啟動的時候都是為follower狀態；candidate負責選舉投票，當leader宕機時，通過投票選舉轉為leader狀態。Raft算法開始時需要在集群中選舉出leader來負責日志復制的管理，leader接受來自客戶端的事務請求（日志），并將它們復制給集群的其他節點，然后負責通知集群中其他節點提交日志，leader負責保證其他節點與他的日志同步，當leader宕機后，集群其他節點會發起選舉，選出新的leader。Raft算法工作流程基本由Raft節點狀態機決定，如圖1所示。

Raft中采用心跳機制操控著leader宕機后節點的重新選舉。每個leader都會向集群中的所有節點發送心跳信號，證明自己還存活未宕機。leader節點宕機時無法發送心跳信號，此時當follower節點在規定的一段時間內沒有收到來自leader的心跳后會將自身的狀態切換成為candidate，向其他節點發送選舉請求，如果自身的日志比對方節點的日志更新以及term更大就會收到對方節點的選票，否則對方節點將拒絕投票。倘若獲取到的選票數量到達n/2 （n為節點個數）以上時，會將自身的狀態置為leader，任期號加1。若在投票選舉過程中重新收取到leader的心跳信號，就會將自身狀態重新置為follower。

1.2 選票造假問題

類似于PBFT中的視圖，Raft使用了一個term的概念，當term增加時相當于PBFT中的視圖切換，每個term都是一個連續遞增的編號，leader身份由一個節點更換成另一個節點的時間就是一個term周期，在一個term中只能產生一個leader。Raft算法開始時所有的follower的term為1，其中一個follower邏輯時鐘到期后發現集群中沒有leader心跳，即轉換為candidate，term加1，此時任期為2。誰的term更大，誰就有更高的優先選擇權力， term大的節點不會向term小的節點投出選票，若leader發現自身的term小于某一個follower節點，則該leader會自動成為follower節點。可以說每次term的遞增都將發生新一輪的選舉，在Raft正常運轉中所有節點的term都是一致的，在節點不發生故障時一個term會一直保持下去，當某節點收到的請求中term比當前term小時則拒絕該請求。

Raft集群中的選票數量影響著誰能夠成為leader，因為在原始的Raft中，誰的選票數量多，就代表著誰發現leader節點宕機的時間越早，節點是無條件將選票投出給比自己term大的節點，即成為candidate節點的時間也越早，term比其他節點要更大，所以算法為了更快地選出新的leader，就選擇以選票數量作為挑選leader的指標，使得集群能夠快速恢復到正常狀態。而在Raft算法中節點為何種身份，由自身的狀態機決定，即拜占庭節點可以隨意更換自己身份，當本輪leader節點沒有宕機的時候，拜占庭節點可以成為candidate節點，增大自身的term，向其他節點拉取選票，當獲取到足夠的選票以后就會將本輪的正常leader節點替換。

1.3 日志易偽造問題

日志復制是Raft算法的核心之一，保證了Raft數據的一致性。在一個Raft集群中只有leader節點才能接受客戶端的請求，然后由leader向其他follower轉發請求日志，leader不會刪除任何日志，follower只會接收來自leader所發送的日志信息。日志結構如圖2所示，其中x、y代表的是某種指令，日志由序號和條目（內容）組成，每個條目又由任期（term）和指令（command）組成，committed范圍為超過半數以上的節點接受并儲存的日志。

在Raft集群中可通過條目索引號、任期號來確定唯一的條目，并且該條目之前的所有條目都是一致的，當leader節點宕機后，新的leader被選舉出來，此時集群中所有的節點會以新leader的本地日志結構為標準進行同步，僅保留序號與任期號完全相同的部分，超出部分會被刪除，少于部分會進行同步，使集群中日志保持一致。

從上述Raft的日志復制過程以及日志結構可以看出，Raft中的follower節點是無條件地接受并與leader的日志結構保持相同的，即使自己的日志是比leader節點更新。而日志消息又是由leader節點進行打包并傳播給其他的節點，若此時leader節點為拜占庭節點，有可能將客戶端傳入的日志消息進行竄改。所以確保日志內容不被偽造、不被竄改對于抵抗拜占庭節點算法來說至關重要。

2 RB-Raft算法

2.1 基于哈希鏈的動態日志驗證機制

哈希鏈概念最早是由 Lamport［17］于1981年提出，旨在解決密碼在傳輸過程中會被入侵者竊取、竄改的問題。哈希鏈通過哈希函數對密碼進行多次迭代加密，具有良好的抗干擾性，且服務器端只需保存最后一次加密的密文即可驗證全部密文序列。因為日志結構要保證日志順序不變，每塊日志體不變，所以采用哈希鏈的方式將所有的日志塊串聯起來，只需要驗證最末尾哈希值即可驗證前面所有的日志塊是否相同。

1）日志哈希鏈的生成

當客戶端在批量打包日志的時候，對日志塊進行哈希鏈運算，日志哈希鏈生成過程如圖3所示。其中，log代表日志塊體，proof代表驗證哈希。

算法1 構造日志哈希鏈

輸入：日志塊序列log［］。

輸出：日志哈希鏈表ProofTable。

1 int i，j=1//定義i為日志循環編號，j為proof循環編號

2 while（i！=MaxLength（log））//沒有將哈希鏈覆蓋到全日志時

3" string file=getLogBlockToflie（log［i］）//獲取日志

4" int proof//每次循環定義一個新的proof

5" if i==1 //判斷是否為第一塊日志

6"" proof=MD5toFile（file）;

7"" ProofTable［j］=proof;

8"" j++，i++;

9"" break;//進入下一個循環

10 end if

11 proof=MD5toFile（file）;

12 ProofTable［i］=HybridMD5（proof，ProofTable［i-1］）;

//混合哈希

13" j++，i++;

14" break;

15 end while

以上為哈希鏈生成部分全過程，接著需要對follower節點拿到的日志塊進行校驗。在本文中采用follower節點向客戶端發送校驗信息的方式。

當需要對日志進行校驗時，follower節點將自身所存儲的日志做哈希鏈計算得出最后一塊日志塊的proof，proof代表了本節點所有的日志塊，然后將最后一塊日志塊序號作為請求參數發送給客戶端，客戶端返回相應的proof，節點與其進行對比，假如對比失敗，兩者完全不相同，說明自身日志與客戶端發送過的日志存在不一致。

當日志對比失敗后首先需要對日志進行回滾，回滾到上一層proof再次進行對比，不一致的話就繼續回滾，直到proof一致則不再進行回滾，錯誤proof的日志塊將會被刪除，并且向客戶端獲取同步錯誤的日志塊。

2）日志動態驗證機制

日志對比失敗存在幾種可能性：a）當前leader節點為拜占庭節點，對日志進行了修改；b）之前leader節點存在拜占庭節點，只不過是沒有被發現；c）在傳輸過程中因為一些異常情況，如網絡波動、I/O讀寫錯誤，導致日志缺少、錯誤。因為無法確定是何種原因導致日志塊發生錯誤，所以當日志發生錯誤時不能直接否定該leader節點。設計以下動態驗證機制用來對上述三種情況進行容錯：

每個follower節點會每隔T份日志向客戶端發送檢測請求，返回當前本地日志索引號所對應的proof，并將本地日志作迭代式哈希，判斷是否一致。本文利用對數函數在1附近能夠快速收斂的性質，設計了如式（1）所示的分段函數。Tn代表第n輪T值，x的作用類似于信用值，初始值為1，步長為0.1。

Tn=Tn-1×2「logx2" err≠1∧x≤1

Tn-1×2logx2」" err≡1∧xgt;1

（1）

當驗證錯誤時，應該縮短檢測的份數，即增大檢測頻率，如x初始值為1，當驗證發現錯誤時，x首先會降低0.1，當xlt;1時logx2為負數，并且向上取整，此時2x為減函數，導致Tnlt;Tn-1，縮短檢測跨度，加快了檢測頻率。而當檢測正確時，x增加0.1，當xgt;1時logx2為正數并且向下取整，此時2x為增函數，導致Tngt;Tn-1，使得檢測跨度變大，檢測頻率降低，以避免增大客戶端的檢測壓力，符合本算法的需求。

當T變成1時，即leader節點每同步一次日志，follower節點就需要向客戶端進行檢驗，說明該leader節點在該follower節點中已經不可信，當這種follower節點達到一半時客戶端會將其替換掉，重新再競選一個新leader節點。何時替換leader節點的主要由三個因素影響，即T值大小、leader節點發送錯誤日志份數，以及集群同步速度，后面兩個因素都無法人為地控制，但是可以通過控制T值的初始大小來設置該機制的嚴厲程度，T值的下降速度為logT2，當T較大時，就允許較大的錯誤率，當T較小時就是相對比較嚴格。

2.2 基于門限加密的遺書機制

遺書最早理解為通過公開的信件來約定好如何分配已去世人財產等身后事宜。在Raft算法中當leader節點宕機后，follower節點僅僅依據任期大小來選擇是否將選票投出，而任期的大小又是通過是否接收到來自leader節點的心跳信號而決定的，這是很容易被拜占庭節點所利用的，拜占庭節點可以通過修改自身任期來達到獲取大量選票，從而替換當前正常的leader節點。

為了解決上述問題，本文設計遺書機制，在節點成為leader時產生一份遺書（立下遺囑），其他節點獲取到遺書內容才有資格向follower節點拉取選票（分配財產），而遺書內容只能當leader節點宕機后才可以打開。為了確保遺書的安全性，本文利用門限加密對遺書進行加密，門限加密由Desmedt等人［18］提出的。門限密碼通過將密鑰信息發放給多個用戶進行存儲，任意少于門限數量的密鑰信息無法進行解密，必須擁有超過門限數量的密鑰信息才能獲取到密文信息。只有當大部分的follower節點將門限密鑰給出才能夠將遺書進行解密（打開），從而獲取到遺書內容并拉取選票（分配財產），而是否給出門限密鑰又取決于leader節點的心跳信號（該過程類似于驗證leader節點是否存活），形成了一個完整的驗證閉環，避免了拜占庭節點修改任期將正常的leader節點異常替換。具體步驟如下：

在基于門限加密的遺書機制中，將遺書內容定義為需要加密的密文（Lmsg，leagcy-message），設定leader編號以及成為leader時間為原始數據即Lmsg。

1）遺書生成階段 leader節點首先使用KeyGen（λ，n，t）生成密鑰，輸入安全參數λ、用戶數量n和門限值t，門限值一般設定為集群數量的一半，輸出公鑰pk和節點私鑰分享sk=（skid1，…，skidn），通過Enc（pk，Lmsg）獲得門限加密后的密文L。

2）分發密鑰及遺書階段 向所有節點發送一份遺書（L，即對Lmsg門限加密以后的密文）、該follower節點所對應的私鑰分享skidj以及該Lmsg的散列值HashLeagcy。

3）遺書解密階段 當follower節點在心跳超時器結束以后依舊沒有收到心跳，那么該節點會通過向其他節點獲取解密分享Lid的方式對L進行門限解密，解密算法為Dec（skid，L），輸入自身私鑰分享skid以及L，得出Lid。此時該節點必須擁有t個Lid通過Combine（Lid1，…，Lidt）算法才能獲取到Lmsg。其中當節點收到來自其他節點的門限請求時，會判斷距離上次收到心跳信息是否超過M時間，超過M時間則將門限私鑰給出，否則拒絕交出門限私鑰。當leader節點并未宕機時，必定有節點在M時間內收到心跳，所以就推翻了leader節點宕機的這一定論，因此不會將私鑰分享出去。M值的設置為follower節點心跳超時器時間的2/3，在實驗中發現大部分節點都在前2/3的心跳超時時間中收到心跳信息，幾乎沒有超過該長度的節點，所以將M設置為該值，便于加快效率。

4）選票拉取階段 當獲取到遺書內容后會將自身狀態轉換成為candidate向其他follower節點發送requestVote消息拉去選票，而被拉取選票節點需判斷來自candidate節點的Lmsg是否正確，通過對Lmsg進行哈希運算與之前leader節點發送的HashLeagcy進行對比，對比通過才允許進入正常的投票判斷環節，否則不對其進行投票操作。

遺書生成和解密大致流程如圖4所示，之后的正常選票拉取階段在2.1節中已經介紹，不再贅述。

基于門限加密的遺書機制部分算法描述如下：

算法2 遺書生成算法

輸入：Lmsg，n，t，λ。

輸出：sk，pk，L。

1 if node.status=leader and flag=true then //節點成為leader

2 pk，sk=KeyGen（λ，n，t） //公私密鑰生成

3 L=Enc（pk，Lmsg） //遺書加密

4 HashLeagcy=h（Lmsg）

5 Broadcast（pk，sk，L，HashLeagcy） //廣播遺書

6 end if

算法3 門限分享算法

輸入：L，skid。

輸出： Lid。

1 if node.status=follower and getLMessage then

//follower節點被請求門限私鑰

2 if Tgt;timeout then //當T值大于超時時間

3" return Lid=Dec（skid，L） //給出節點門限私鑰

4 else

5" return err

算法4 遺書解密算法

輸入：Lid1，…，Lidj，L。

輸出：Lmsg。

1 if node.status=follower and heartbeat=1 then //follower節點未收到心跳信息

2 if count（Lid1，…，Lidj）gt;=t then

3" Lmsg=combine（Lid1，…，Lidj） //遺書解密

4" node.status=candidate

5" return Lmsg

6 else

7"" return err

算法5 遺書驗證算法

輸入：Lmsg，HashLeagcy。

輸出：vote。

1 if node.status=follower and getLmsg then //收到其他節點的投票請求

2 if HashLeagcy==h（Lmsg） then

3" 進入正常投票判斷

4" if 通過判斷 then

5""" return vote

6" return err

3 安全性分析

RB-Raft算法為能夠抵抗拜占庭節點攻擊的Raft算法，在安全性方面需要滿足以下幾個要求：a）日志不允許被leader節點修改，即所有節點提交的日志需要保證一致，這是Raft作為一種共識算法所需要具備的最重要的特質；b）確保leader不被異常替換，即被惡意的candidate拉取選票導致term切換。

3.1 日志完整性

要保證日志完整性就要確保兩點，即日志順序不變，且每個日志塊是相同的。以下是日志完整性分析：

定義1 記日志塊為Bi，igt;0且i為正整數，哈希序列為Hj，jgt;0且j為正整數，i， j∈Euclid ExtraaBp。

定義2 h（Text）為哈希函數，在本文中采用MD5，返回哈希值。

由上述算法流程可知：

Hj=h（h（h（h（B1），B2），…），Bi－1） j=i

惡意的拜占庭節點將其中任意一個日志塊Bk修改部分內容后得到的日志塊記為B′k，得到H′j如下：

Hj′=h（h（h（h（h（h（B1），B2），…），B′k），…），Bi） i=jgt;k

因此必然存在Hj′≠Hj，即可判定在日志序列中某份日志被竄改導致Hj改變，發現被竄改以后可以向客戶端同步被竄改的日志，保證了日志序列的完整性和真實性。

3.2 節點選舉安全性

在Raft算法中，leader節點需要定時向follower節點發送心跳信息AppendEntries，用來向其他節點宣稱自己仍然存活，可以正常工作，當leader節點宕機時，因follower節點在自身設置的心跳超時時間內還未收到來自leader節點的Append-Entries消息，所以會將term增加，并且轉換成為candidate身份進行選舉，向其他follower節點拉取選票成為新的leader節點。

在存在拜占庭節點的環境下，candidate拉取選票的時間缺乏限制，即使leader并沒有宕機，惡意的candidate節點可以通過拉取選票將當前leader替換（因為candidate的term比leader大，所以會將手中的選票投出）。為避免這種情況的發生，提出了基于門限簽名的遺書機制來避免leader節點的異常更換，通過門限簽名方式保證了拜占庭節點的數量必須超過門限值t才會獲取到遺書，通常t值一般會設置為n/2，具體方式詳見2.2節。該方式確保candidate節點的拉取選票是有證據（未收到leader心跳）的背書，保證了節點選舉的安全性。

3.3 抗拜占庭節點能力分析

Raft算法本身是屬于私鏈的一種共識算法，是不允許拜占庭節點存在，只允許部分宕機節點的存在。而RB-Raft是以Raft為原型改進的聯盟鏈算法，允許拜占庭節點的存在，所以主要與聯盟鏈中主流的PBFT算法進行對比。

相對于聯盟鏈來說，能抵抗攻擊的指標主要取決于能夠允許多少拜占庭節點的存在。假設集群節點總數為n，拜占庭節點個數為f。在RB-Raft中，根據少數服從多數原則，集群中的正常節點只需要比f個節點再多一個節點即可進行正常的共識，可得n=2f+1，因此RB-Raft算法支持的最大容錯節點數量f為（n-1）/2。在PBFT算法中，假設存在故障節點和拜占庭節點都是不同的節點，那么就會有f個故障節點和f個拜占庭節點，當發現故障節點后，算法會將其排除在集群外，因此正常節點需要比拜占庭節點多一個節點，可得n=3f+1，PBFT算法支持的最大容錯節點數量f為（n-1）/3。綜上所述，在聯盟鏈共識算法當中，RB-Raft算法要比PBFT算法多允許（n-1）/6的拜占庭節點的存在，抗拜占庭節點的能力比PBFT要高。

4 仿真實驗

本文采用go語言實現了RB-Raft算法，然后采用本地單機多節點模擬共識過程，記錄數據吞吐量、共識時延、以及拜占庭節點行為等數據，完成對比實驗。最后通過實驗對比表明該算法具有抗拜占庭能力以及高吞吐量、低延時的優點。

4.1 抗拜占庭節點性能測試

在本節實驗中，引入可控的拜占庭節點以用來測試集群抗拜占庭能力，并且采取不同身份以及行為進行實驗。

1）日志防偽測試

在本節中首先對日志防偽性能進行測試。由于選舉過程的隨機性，無法指定可控節點作為leader，所以將可控節點的選舉超時器的時間設置為遠小于其他正常節點，而又比正常通信所花費時間長，使得集群初始化時可控節點能夠第一時間進行選舉，從而成為leader，便于實驗的開展。然后從客戶端發送相同的500份日志到leader節點中，leader節點采用偽隨機數生成［1，500］的10份日志序號，并進行修改，監測follower節點是否能夠正確發現被竄改日志并回滾。上述操作分別在Raft與RB-Raft集群中開展，得到實驗結果如表1所示。

從表中可以看出，Raft與RB-Raft算法在準確率上面屬于兩個極端，Raft算法完全無法發現錯誤日志，對任何leader節點發送過來的日志都進行了同步，顯然在存在拜占庭節點的情況下是不可取的，而RB-Raft算法對隨機竄改的日志塊都能夠準確發現，并且進行回滾，準確率達到了100%，因此RB-Raft具有良好的抵抗日志偽造的優點。

接著需要對動態驗證機制進行實驗，測試對于惡意的leader節點能否快速將其替換，對于正常的leader節點能否縮短檢測頻率以減輕節點驗證壓力。在該實驗中，以follower節點的視角，分別測試拜占庭leader節點修改日志和節點正常的兩種情況中follower節點的T值變化曲線，實驗中T值初始值都設置為8，實驗結果如圖5所示。

從圖中可以看出，常規leader節點在第11輪次后將T值增大到了16，增大了檢測跨度，降低了檢測頻率，減輕了節點壓力。而拜占庭leader在第二輪次修改日志后T值快速降低到1，即達到了不可信的狀態，使得惡意的leader節點被替換，達到了抵抗拜占庭節點的攻擊目的。上述實驗主要是由于式（1）的分段函數所致，x值可以類比于信用值，通過x的增減來影響T值的變化。

2）遺書機制測試

在本節實驗中同樣需要引入可控的惡意節點，引入方法與上節相同。然后通過可控節點在leader節點并未宕機的情況下分別向Raft算法集群和RB-Raft算法集群中節點發出選票拉取，在20 ms后統計兩個集群中收到的follower節點的選票數量，實驗結果如表2、3所示。

從表2、3中可以看出，對于Raft算法中節點的拜占庭行為是無法遏制住的，在leader節點未宕機的情況下依舊獲取到了半數以上的節點選票，因此可以將正常的leader節點替換。而在RB-Raft中獲取到的選票數量都為0，門限簽名數量也分別為15%、14.4%，不足門限閾值，因此獲取不到遺書內容，自然無法獲取到其他節點的選票，避免了節點惡意將leader節點替換。

4.2 共識時延

共識時延是衡量共識算法的一項重要指標，在共識算法中表示從客戶端發出命令開始到客戶端收到集群發出同步完成命令的時間差。在本節中主要對經典PBFT共識機制、Raft算法，以及RB-Raft算法的共識時延進行對比，如圖6所示。

實驗結果顯示PBFT的時延大部分比Raft與RB-Raft算法要更高，其原因還是在于算法的復雜程度上，PBFT要經過多階段的通信才能達到集群一致。而RB-Raft算法因為增加的密鑰發放以及遺書機制，時延方面要比Raft稍高，但也是在可接受范圍之內。因此RB-Raft算法損失一定的效率換取到了抵抗拜占庭節點的能力。

4.3 吞吐量測試

數據吞吐量是衡量區塊鏈性能的一種重要工具，代表單位時間內處理的交易數量，表示為TPS（transactions per second）。共識效率是影響TPS的主要因素，共識效率越高，事務處理能力就越強。影響TPS的因素還包括節點對并發數據的處理能力，對數據庫的I/O讀寫能力等，測試過程采用EOSBenchTool工具。在本節實驗中采用控制變量法，只將算法作為唯一變量，其他環境因素均不變，對比了Raft、PBFT以及RB-Raft算法吞吐量，最后隨機選取測試數據中的20組進行比較，得出吞吐量測試結果如圖7所示。

實驗結果顯示，RB-Raft與Raft算法都具有高數據吞吐量，吞吐量比Raft算法低了39.1%，但是比PBFT算法提高了61.8%，因為實現了拜占庭容錯，節點交互時會互相驗證身份，以及集群的數據通信量增加，所以吞吐量會相對于Raft下降，但是相比于PBFT的數據吞吐量還是較高的。

4.4 算法性能對比

本節對PBFT、Raft、RB-Raft算法部分性能進行匯總比較，比較結果如表4所示。

從表中可以看出，在抗拜占庭節點方面，因為PBFT算法容錯f個節點需要3f+1個總節點，所以其允許存在的拜占庭節點數量為（n-1）/3。而Raft是不允許拜占庭節點存在的，但是RB-Raft算法只需要保證有半數以上的節點能夠成功同步日志即可，所以是允許（n-1）/2的拜占庭節點存在，RB-Raft算法是允許存在拜占庭節點最多的，即其抗拜占庭節點能力是最強。而在共識時延方面，RB-Raft算法是小于PBFT但是比原始Raft算法還是稍微要大一些，在吞吐量方面也同樣是要大于PBFT但是要小于原始Raft算法，而通信開銷方面是遠小于PBFT的O（n2），與原始Raft算法相當。

接著將本文算法與其他Raft拜占庭容錯類進行比較，結果如表5所示。

從表中可以看出，本文算法允許存在的拜占庭節點與文獻［13］相當，比其他算法要更高，但是在leader選舉時間方面并沒有優化。文獻［14］利用雙層Kademlia協議建立的K桶實現candidate節點集合內的穩定選舉，因此文獻［14］是這些文獻中leader選舉時間最短的算法。其中文獻［15］是一種分組思想，采用了組內Raft組間PBFT的共識機制，決定容錯率的還是由PBFT算法所決定，所以其對Raft算法沒有比較大的改進。但是本文RB-Raft算法在日志加密、選票驗證方面進行了優化，在抗拜占庭節點的全面性上做了較好的工作。

5 結束語

本文提出了一種可抵抗拜占庭節點的Raft算法——RB-Raft算法，解決了Raft在不確定環境下的日志竄改和不能拜占庭容錯的問題。首先采用哈希鏈的方式對日志進行處理，并且通過動態驗證機制進行日志驗證，解決了日志偽造問題并降低節點的驗證壓力。其次，提出基于門限加密的遺書機制，通過門限加密使得接收心跳信號擁有節點的肯定作為背書用于防止拜占庭節點拉取選票更換leader節點，解決了拜占庭節點影響系統一致性的問題。最后，實驗數據表明：RB-Raft算法相比于Raft算法具有抗拜占庭節點的能力，其算法吞吐量比PBFT提高了61.8%，平均共識時延比PBFT降低了53.3%。綜上所述，RB-Raft適合聯盟鏈在不安全的環境下進行共識，如車聯網、物聯網這種要求共識效率高，而又容易存在惡意節點對系統攻擊的應用需求。RB-Raft算法具有共識低時延和高安全性，適用于在車聯網等去中心化環境下進行共識，未來的工作將圍繞著如何把本算法應用到車聯網、物聯網場景當中展開。

參考文獻：

［1］Nakamoto S. Bitcoin： a peer to peer electronic cash system ［EB/OL］. （2008）. https：//bitcoin. org/bitcoin. pdf.

［2］Ferretti S，D’Angelo G. On the Ethereum Blockchain structure： a complex networks theory perspective ［J］. Concurrency and Computation： Practice and Experience，2020，32（12）： e5493.

［3］Wang Guizhou，Zhang Si，Yu Tao，et al. A systematic overview of blockchain research ［J］. Journal of Systems Science and Information，2021，9（3）： 205-238.

［4］Li Wenzheng，He Mingsheng，Sang Haiquan. An overview of blockchain technology： applications，challenges and future trends ［C］// Proc of the 11th IEEE International Conference on Electronics Information and Emergency Communication. Piscataway，NJ： IEEE Press，2021： 31-39.

［5］Arnold R，Longley D. Continuity： a deterministic Byzantine fault tole-rant asynchronous consensus algorithm ［J］. Computer Networks，2021，199（11）： 108431-108443.

［6］鄧小鴻，王智強，李娟，等. 主流區塊鏈共識算法對比研究 ［J］. 計算機應用研究，2022，39（1）： 1-8. （Deng Xiaohong，Wang Zhiqiang，Li Juan，et al. Comparative research on mainstream blockchain consensus algorithms ［J］. Application Research of Compu-ters，2022，39（1）： 1-8.）

［7］Meneghetti A，Sala M，Taufer D. A survey on pow-based consensus ［J］. Annals of Emerging Technologies in Computing，2020，4（1）： 8-18.

［8］Li Yixin，Wang Zhen，Fan Jia，et al. An extensible consensus algorithm based on PBFT ［C］// Proc of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. Pis-cataway，NJ： IEEE Press，2019： 17-23.

［9］Ongaro D，Ousterhout J. In search of an understandable consensus algorithm ［C］// Proc of USENIX Conference on USENIX Annual Technical Conference.［S.l.］： USENIX Association，2014： 305-319.

［10］Lamport L. Fast Paxos ［J］. Distributed Computing，2006，19（2）： 79-103.

［11］Lamport L，Shostak R，Pease M. The Byzantine generals problem ［J］. ACM Trans on Programming Languages and System，1982，4（3）： 382-401.

［12］Copeland C，Zhong H. Tangaroa： a Byzantine fault tolerant Raft ［D］. California： Stanford University，2016.

［13］Tian Sihan，Liu Yun，Zhang Yansong，et al. A Byzantine fault-tolerant Raft algorithm combined with Schnorr signature ［C］// Proc of the 15th International Conference on Ubiquitous Information Management and Communication. Piscataway，NJ： IEEE Press，2021： 1-5.

［14］王日宏，周航，徐泉清，等. 用于聯盟鏈的非拜占庭容錯共識算法 ［J］. 計算機科學，2021，48（9）： 317-323. （Wang Rihong，Zhou Hang，Xu Quanqing，et al. Non-Byzantine fault tolerance consensus algorithm for consortium blockchain ［J］. Computer Science，2021，48（9）： 317-323.）

［15］黃冬艷，李浪，陳斌，等. RBFT： 基于Raft集群的拜占庭容錯共識機制 ［J］. 通信學報，2021，42（3）： 209-219. （Huang Dongyan，Li Lang，Chen Bin，et al. RBFT： a new Byzantine fault-tolerant consensus mechanism based on Raft cluster ［J］. Journal on Communications，2021，42（3）： 209-219.）

［16］王日宏，張立鋒，周航，等. 一種結合BLS簽名的可拜占庭容錯Raft算法 ［J］. 應用科學學報，2020，38（1）： 93-104. （Wang Rihong，Zhang Lifeng，Zhou Hang，et al. A Byzantine fault tolerance Raft algorithm combines with BLS signature ［J］. Journal of Applied Sciences，2020，38（1）： 93-104.）

［17］Lamport L. Password authentication with insecure communication ［J］. Communications of the ACM，1981，24（11）： 770-772.

［18］Desmedt Y，Frankel Y. Threshold cryptosystems ［C］// Advances in Cryptology—CRYPTO’89. Berlin： Springer，1989： 307-315.