基于獎勵積分機制的高效拜占庭容錯算法DIG-PBFT

吳言，藍雯飛*，王俊，張瀟，謝元艾, ，向鑫

（1 中南民族大學(xué) 計算機科學(xué)學(xué)院， 武漢 430074；2 香港教育大學(xué) 數(shù)學(xué)與資訊科技學(xué)系， 香港特別行政區(qū) 999077）

自從比特幣問世以后，區(qū)塊鏈技術(shù)在各個領(lǐng)域快速發(fā)展［1-4］. 以太坊的智能合約［5］和IBM 的Hyperledger Fabric［6］推動了區(qū)塊鏈在企業(yè)領(lǐng)域的應(yīng)用.而在如今區(qū)塊鏈技術(shù)仍在不斷發(fā)展［7］，并且更加注重安全性、可擴展性和可編程性.

區(qū)塊鏈是一種去中心化的分布式數(shù)據(jù)庫技術(shù)［8］.與傳統(tǒng)的中心化系統(tǒng)相比，區(qū)塊鏈技術(shù)不僅解決了安全和單點故障的問題，而且提升了交易速度和透明度.共識算法是區(qū)塊鏈最核心的技術(shù)，解決了信任和一致性問題，是決定區(qū)塊鏈系統(tǒng)性能的主要因素.目前按照區(qū)塊鏈的類型，對共識算法可以分為三類：公有鏈共識，私有鏈共識和聯(lián)盟鏈共識.其中公有鏈主要應(yīng)用工作量證明（PoW），該算法的實用性較差［9］；私有鏈主要采用分布式一致性算法Raft達成共識；聯(lián)盟鏈主要使用PBFT算法.

文獻［10］提出了一種匹配主從鏈結(jié)構(gòu)的分層拜占庭容錯算法HBFT.每一次的共識系統(tǒng)會根據(jù)參與節(jié)點屬性的不同，分別執(zhí)行HBFT 算法中速度快、開銷小的簡化共識算法SCA（Simplified Consensus Algorithm）和開銷較大、容錯能力強的拜占庭容錯算法PBFT.文獻［11］提出了SG-PBFT 算法，將所有節(jié)點進行分組，并初始化賦予積分，每次共識都會調(diào)整節(jié)點積分，一個時間周期結(jié)束根據(jù)積分調(diào)整分組，積分過低將不參與共識.文獻［12］提出了一種PBFT 優(yōu)化算法，依靠引入C4.5 和積分投票機制來確定主節(jié)點.文獻［13］提出了一個弱化主節(jié)點的概念，優(yōu)化整體的共識過程來提升性能.文獻［14］引入選舉投票機制，改變原本主節(jié)點的隨機選擇，通過投票機制選取主節(jié)點.文獻［15］提出了QS-PBFT共識算法，優(yōu)化了主節(jié)點選取.上述方案能夠有效地提高共識的效率但是依然存在計算開銷較大、主節(jié)點選取安全性低、惡意節(jié)點未被處理等問題.本文所提出的DIG-PBFT（Dynamic Integral Grouping PBFT）共識算法引入了獎勵積分機制，在共識過程中網(wǎng)絡(luò)中的節(jié)點會根據(jù)積分機制規(guī)則動態(tài)進行調(diào)整，信用度過低的節(jié)點會被加入候選集中并且禁止參與共識，從而大大提高了共識效率.本算法的核心是在共識過程中通過動態(tài)的思想篩選出拜占庭節(jié)點，使得安全性更高的節(jié)點參與到共識中，大大提高主節(jié)點選取的安全性，并且通過分組來控制參與共識的節(jié)點數(shù)量以及優(yōu)化算法復(fù)雜的通信過程，來降低算法的時延，以提高算法性能.

1 共識機制

共識機制是一種在分布式系統(tǒng)中用于確定事實或狀態(tài)的算法.在該機制下，參與者通過協(xié)作來達成一致并生成新的區(qū)塊或更新現(xiàn)有的區(qū)塊鏈.共識機制可以確保網(wǎng)絡(luò)上的所有節(jié)點都同意最終的狀態(tài)，并且防止任何一方篡改數(shù)據(jù).一些常見的共識機制又可以分為證明類和拜占庭類［16］.

1.1 證明類共識機制

證明類的共識機制主要會依據(jù)某一種條件來選擇主節(jié)點.常見的證明類機制有工作量證明（Proof of Work，PoW）、股權(quán)證明（Proof of Stake，PoS）以及委托股權(quán)證明（Delegated Proof of Stake，DPoS）［17］等等. PoW依賴于計算機的計算能力來解決數(shù)學(xué)難題，以此來獲得區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點的信任和認可.在PoW 中，礦工需要通過計算哈希函數(shù)來查找一個特定的數(shù)字，使其滿足預(yù)定的條件，這個過程被稱為挖礦［18］.礦工將自己的計算能力投入到網(wǎng)絡(luò)中，競爭誰最先找到下一個合法區(qū)塊，并且得到相應(yīng)的獎勵.由于挖礦需要大量的計算能力和電力支持，因此PoW 算法存在一些不足，例如，它對能源的需求可能導(dǎo)致對環(huán)境的不良影響，并且由于算力集中度較高，可能會出現(xiàn)中心化的問題；PoS 通過驗證節(jié)點擁有的加密貨幣數(shù)量來選擇下一個出塊節(jié)點，而不是像PoW 一樣通過計算能力的競爭，這是因為這些節(jié)點將會抵押一定數(shù)量的加密貨幣作為“股份”，以獲得參與下一個出塊節(jié)點的機會，與PoW 相比，PoS算法在節(jié)約能源方面具有優(yōu)勢，因為它不需要進行大量計算來解決數(shù)學(xué)難題，PoS 算法也存在一些不足，例如可能會出現(xiàn)寡頭壟斷、網(wǎng)絡(luò)安全性問題等；DPoS 與PoW，PoS 都不相同，DPoS 并不選擇出塊節(jié)點，而是通過選舉一組代表來管理網(wǎng)絡(luò).DPoS 算法主要解決了PoW 存在的能源浪費和PoS可能出現(xiàn)的中心化問題.然而，DPoS 也存在一些短處.例如，由少數(shù)代表管理網(wǎng)絡(luò)可能導(dǎo)致中心化風(fēng)險等.

1.2 拜占庭類共識機制

拜占庭類中一種常見的共識算法是Paxos［19］，該算法主要用于解決分布式系統(tǒng)中的數(shù)據(jù)一致性問題，并被廣泛地應(yīng)用在分布式數(shù)據(jù)庫、分布式文件系統(tǒng)和分布式共識算法中.Paxos算法主要適用于拜占庭容錯（Byzantine Fault Tolerance，BFT）的環(huán)境中.該算法通過提議階段、承諾階段、提議接受階段以及提議被接受階段等多個階段的消息交換，選出一個主節(jié)點并達成一致性，從而確保系統(tǒng)中的數(shù)據(jù)一致，然而該算法在性能方面存在一些問題，因為它需要進行多次信息交換和狀態(tài)轉(zhuǎn)換，這會增加系統(tǒng)的延遲并且?guī)眍~外的開銷；另一個最常見的共識算法是PBFT［20］，它可以允許存在最多f個惡意節(jié)點的情況下保證分布式系統(tǒng)的一致性和可行性.在PBFT中，所有節(jié)點按照一定的順序輪流擔(dān)任主節(jié)點，其他節(jié)點則作為備份節(jié)點.當(dāng)一個客戶端需要發(fā)送請求時，它將請求發(fā)送給當(dāng)前的主節(jié)點，主節(jié)點將請求廣播給其他備份節(jié)點，并等待至少f+1 個節(jié)點響應(yīng)確認信息.如果主節(jié)點收到了足夠數(shù)量的確認信息，就會執(zhí)行請求并將結(jié)果廣播給所有節(jié)點；否則，它會繼續(xù)等待確認信息.每個節(jié)點都會維護一個日志來記錄所有已處理的請求，以確保系統(tǒng)的一致性.PBFT 算法的優(yōu)點在于其能夠在容忍一定數(shù)量的惡意節(jié)點的同時保證系統(tǒng)的一致性，且在正常情況下具有較高的效率、低延遲.PBFT的3個階段如圖1所示.在圖中C 表示發(fā)起請求的客戶端，0 表示主節(jié)點，1、2、3為從節(jié)點，這里假設(shè)節(jié)點3為拜占庭節(jié)點.

圖1 PBFT共識算法的信息交換Fig.1 Information exchange of PBFT

2 目前共識算法存在的問題

共識機制具有較高的安全性、去中心化、較高的可擴展性、較強公平性等優(yōu)勢，使其能夠更好地解決分布式環(huán)境下的數(shù)據(jù)同步和一致性問題.但是從現(xiàn)實中共識機制的應(yīng)用不難發(fā)現(xiàn)其存在一些問題有待解決.

PBFT 算法主要用于解決分布式網(wǎng)絡(luò)系統(tǒng)中存在的拜占庭將軍問題，在一個分布式系統(tǒng)中，因為存在網(wǎng)絡(luò)延遲、消息丟失等，節(jié)點之間可能會出現(xiàn)數(shù)據(jù)信息不一致的情況.PBFT 算法可以使各個節(jié)點在達成一致的同時，保證系統(tǒng)的安全性和可用性.PBFT算法是聯(lián)盟鏈中常見的共識算法，依舊存在一些問題，如主節(jié)點的選取十分隨機，對惡意節(jié)點沒有進行處理，通信效率較低等.

2.1 主節(jié)點的選取

傳統(tǒng)PBFT 算法中主節(jié)點的選取一般是通過輪流機制來實現(xiàn)的，每個節(jié)點按照一定的順序依次擔(dān)任主節(jié)點.具體來說，PBFT 算法中使用了一個叫做“視圖”的概念來進行主節(jié)點的選擇.在PBFT中，每個節(jié)點維護著一個叫做“視圖號”的變量，用于記錄當(dāng)前節(jié)點所處的視圖編號.當(dāng)某個節(jié)點需要選出主節(jié)點時，它會向網(wǎng)絡(luò)中廣播一個包含當(dāng)前視圖號的消息，其他節(jié)點收到該消息后會將自己的視圖號與之比較，如果發(fā)現(xiàn)自己的視圖號較小，則更新自己的視圖號，并等待當(dāng)前視圖的主節(jié)點發(fā)送下一個請求.最終主節(jié)點編號確定是通過視圖編號和共識節(jié)點的數(shù)量進行模運算得出來的.基于以上原則，PBFT算法能夠確保每個節(jié)點都有機會成為主節(jié)點，但是網(wǎng)絡(luò)中存在惡意節(jié)點，在最壞的情況下，惡意節(jié)點成為主節(jié)點的概率將會有大約三分之一，這樣高的概率在車聯(lián)網(wǎng)系統(tǒng)中是不能存在的.總之，傳統(tǒng)的PBFT算法在選擇主節(jié)點方面是不合適的，惡意節(jié)點成為主節(jié)點的概率過大會導(dǎo)致系統(tǒng)面臨較大的安全風(fēng)險.

2.2 惡意節(jié)點的處理

傳統(tǒng)的PBFT 算法中沒有任何的方案對惡意節(jié)點進行處理.那么當(dāng)惡意節(jié)點成為主節(jié)點時，系統(tǒng)會因為無法按時達成共識而觸發(fā)視圖轉(zhuǎn)換來重新選擇主節(jié)點，這個過程需要消耗額外的時間和資源，并且會延長整個共識過程的時間.根據(jù)視圖轉(zhuǎn)換規(guī)則，這個被替換的惡意節(jié)點在之后的共識過程中依然有機會再次成為主節(jié)點，然后還會觸發(fā)視圖轉(zhuǎn)換，那么不處理惡意節(jié)點，有可能導(dǎo)致系統(tǒng)進入惡意循環(huán).如果惡意節(jié)點的數(shù)量超過了算法所能容忍的范圍，那么就無法保證系統(tǒng)的安全性和正確性.

2.3 通信效率

第一點，因為PBFT 未能對惡意節(jié)點進行處理，當(dāng)惡意節(jié)點成為主節(jié)點后又要進行視圖轉(zhuǎn)換，并且惡意節(jié)點仍有機會成為主節(jié)點，使得系統(tǒng)不得不多次進行視圖轉(zhuǎn)換，這大大增加了系統(tǒng)的通信開銷；第二點，PBFT 在執(zhí)行共識過程中經(jīng)歷3 個階段：預(yù)準備、準備和提交.其中，預(yù)準備階段和提交階段都需要所有節(jié)點向其他節(jié)點發(fā)送請求消息，以確定進入下一階段所需的最小數(shù)量的準備消息.這個過程需要所有節(jié)點之間進行通信，并且必須等待所有節(jié)點都完成后才能進入下一階段，這使得通信復(fù)雜度達到了Ο(n2)級別.然而車聯(lián)網(wǎng)對通信效率的要求很高，那么執(zhí)行傳統(tǒng)的共識算法，運行效率可能會偏低.

3 DIG-PBFT算法模型

3.1 PBFT共識算法設(shè)計

針對共識算法存在的問題，為了能夠更好地貼合實際應(yīng)用，本文在PBFT 算法的基礎(chǔ)上做出一些改進，引入了獎勵積分分組機制，提出了DIG-PBFT（Dynamic Integral Grouping PBFT），具體的改進如下：

（1）本方案會將所有的節(jié)點分為共識節(jié)點集和候選節(jié)點集，初始化時所有的節(jié)點會被分配初始的積分以及信用度，并且在一開始所有的節(jié)點都將分配到共識節(jié)點集中.共識節(jié)點集中的節(jié)點將會進行共識過程，而候選節(jié)點集中的節(jié)點只是被迫接受共識結(jié)果并保存，并且等待處理.

（2）在不斷共識過程中，節(jié)點的積分以及信用度會根據(jù)獎勵積分機制變化.每一次共識結(jié)束后會對節(jié)點進行判斷，當(dāng)節(jié)點的節(jié)分或者信用度低于閾值時，該節(jié)點將會被加入候選節(jié)點集等待系統(tǒng)對其進行檢查處理.這一點體現(xiàn)了該算法的動態(tài)分組特性.并且積分機制會使得積分和信用度高的節(jié)點被劃分到共識節(jié)點集中參與共識，而可能的惡意節(jié)點將大概率被劃分到候選節(jié)點集中.積分機制有效地提升了算法的安全性，并且即便是攻擊者想要控制積分較高的節(jié)點，那么他需要付出相對更多代價才行.換而言之，引入了獎勵積分機制后，在不斷的共識過程中可以使得安全性更高的節(jié)點有更大的幾率當(dāng)選主節(jié)點.

（3）改變主節(jié)點的選取方式.本方案的主節(jié)點選取將只在共識節(jié)點集中進行.每次選取主節(jié)點時，將對共識節(jié)點集中的節(jié)點進行隨機編號，之后以節(jié)點的積分和信用度分別作為一級和二級評判依據(jù)，選取最優(yōu)節(jié)點作為主節(jié)點.

（4）對PBFT 的通信過程進行了簡化.將“回應(yīng)階段”的廣播過程進行簡化，能夠在一定程度上降低通信復(fù)雜度，使得共識算法的效率有所提高.DIGPBFT 算法通信五階段如圖2 所示，圖中C 表示客戶端，0表示主節(jié)點，1、2、3、4表示從節(jié)點，其中模擬節(jié)點3為拜占庭節(jié)點，4為候選節(jié)點.

圖2 DIG-PBFT共識算法的信息交換Fig.2 Information exchange of DIG-PBFT

DIG-PBFT算法的核心如圖3所示.

圖3 DIG-PBFT算法核心Fig.3 The core of DIG-PBFT

總結(jié)而言，將積分機制引入PBFT 算法，從而設(shè)計出的DIG-PBFT 算法能對傳統(tǒng)算法的短處如主節(jié)點的選取十分隨機、對惡意節(jié)點沒有進行處理、通信效率較低等提供相應(yīng)的解決方案，能夠滿足車聯(lián)網(wǎng)高吞吐量和低網(wǎng)絡(luò)通信量的需求.

3.2 DIG-PBFT算法流程

DIG-PBFT算法的流程圖如圖4所示.

圖4 DIG-PBFT算法流程Fig.4 The process of DIG-PBFT

算法的具體流程描述如下：

（1）首先根據(jù)積分機制對所有節(jié)點進行積分的初始化，將所有節(jié)點先加入共識節(jié)點集中.根據(jù)選取主節(jié)點的規(guī)則選出主節(jié)點；

（2）判斷系統(tǒng)是否滿足共識條件，將共識節(jié)點集中的節(jié)點占總節(jié)點的比率作為判斷依據(jù)，當(dāng)該值不小于規(guī)定的閾值時，系統(tǒng)可以繼續(xù)進行共識，倘若小于閾值系統(tǒng)將進行等待；

（3）客戶端向主節(jié)點發(fā)起共識請求；

（4）主節(jié)點開始執(zhí)行共識信息交換；

（5）共識結(jié)束后，根據(jù)積分機制對所有參與共識的節(jié)點的積分以及信用度進行更新；

（6）判斷節(jié)點的積分或信用度是否低于閾值，如果節(jié)點的積分或信用度有一個低于對應(yīng)的閾值，該節(jié)點將會被加入候選節(jié)點集中，遍歷所有共識節(jié)點集中的節(jié)點；

（7）對于加入候選節(jié)點集的所有節(jié)點，都會接受系統(tǒng)的檢查和處理，等待處理完成后重新賦予初始積分，并重新添加到共識節(jié)點集中；

（8）一次請求結(jié)束.

算法的偽代碼如Algorithm 1所示.

4 實驗結(jié)果與分析

在實驗部分，本文使用Python3.9 編程實現(xiàn)PBFT、HBFT 以及DIG-PBFT 等算法，在本地開啟多個節(jié)點用來模擬各個算法的共識過程，并記錄算法的吞吐量和共識時延.仿真實驗所使用的電腦CPU型號為I5-12400F，主頻為4.4 GHz，內(nèi)存32 G，顯卡型號為RTX3070.

4.1 共識時延

共識時延是用來評估共識算法性能的主要指標之一，是指客戶端提出請求到共識結(jié)束的時間差.實驗中，將網(wǎng)絡(luò)中的節(jié)點數(shù)設(shè)定為20，共識輪數(shù)設(shè)定為60，在同一條件下分別記錄每一種算法的共識時延，實驗結(jié)果如圖5 所示.在圖5 中PBFT，HBFT以及DIG-PBFT 算法的平均時延分別為3.46 ms，2.56 ms，1.96 ms，從圖像可以看出DIG-PBFT 時延明顯低于PBFT 算法，在前期的共識中HBFT 算法和DIG-PBFT算法的時延差距不大，但是在后期能夠展現(xiàn)出DIG-PBFT 算法的優(yōu)勢.主要原因在于共識過程中不斷篩選出拜占庭節(jié)點并進行處理，使得安全性更高的節(jié)點參與共識，從而提高了達成共識的效率.隨后的實驗將共識輪數(shù)定為100輪，測試在不同節(jié)點數(shù)下，每一種共識算法的平均共識時延，實驗結(jié)果如圖6 所示.從圖6 能夠看出隨著節(jié)點數(shù)的增加，算法的共識時延增長速率越來越快，然而DIGPBFT算法的性能要明顯優(yōu)于其他算法.

圖5 共識時延結(jié)果對比Fig.5 Comparison of consensus delay results

圖6 平均共識時延對比Fig.6 Comparison of average consensus delay

4.2 吞吐量

吞吐量也是用來評估共識算法性能的主要指標之一.是指一個系統(tǒng)或網(wǎng)絡(luò)在單位時間內(nèi)可以處理的數(shù)據(jù)量.在高性能計算領(lǐng)域，吞吐量也可以用于描述系統(tǒng)在單位時間內(nèi)可以執(zhí)行的操作數(shù)或計算量.在本文的實驗中，吞吐量TPS表現(xiàn)為單位時間系統(tǒng)完成共識的數(shù)量，在不同節(jié)點數(shù)下，實驗中設(shè)置客戶端發(fā)送1000次共識請求，并記錄每一秒完成的共識數(shù)量.實驗結(jié)果如圖7 所示.可以看出，各個算法的吞吐量隨著節(jié)點數(shù)的增加而減少.顯然DIGPBFT算法達到了更好的效果.因為該算法通過動態(tài)積分分組在大量的共識過程中有著更高的效率，也就使得共識所消耗的時間更短，同等的時間內(nèi)能夠處理更多的共識請求.

圖7 吞吐量對比Fig.7 Throughput comparison

4.3 安全性分析

DIG-PBFT算法在主節(jié)點的選擇上與PBFT算法的視圖轉(zhuǎn)換技術(shù)不同，采用了選擇共識節(jié)點組中信用度更高的節(jié)點作為主節(jié)點的方案，該方案大大降低了PBFT算法選取主節(jié)點的不可靠性和低安全性.

本文中主節(jié)點的選取方案主要依賴節(jié)點的信用度.在節(jié)點參與共識的過程中，節(jié)點的積分和信用度會根據(jù)節(jié)點的行為進行調(diào)整改變，安全誠實節(jié)點的積分和信用度會增加，惡意節(jié)點的積分和信用度會降低，每次共識結(jié)束后，積分或者信用度低于閾值的節(jié)點將會被認定為惡意節(jié)點，并被加入候選節(jié)點組，同時禁止其參與共識，等待處理.這樣做保證了能使絕大部分安全誠實節(jié)點有更多的機會當(dāng)選主節(jié)點并參與共識.總體來看DIG-PBFT 算法能在保證容錯性不變的基礎(chǔ)上，通過動態(tài)地調(diào)整參與共識的節(jié)點，提高了系統(tǒng)的共識效率和安全性.

5 總結(jié)

本文通過分析PBFT 算法所存在的問題（如主節(jié)點的選取十分隨機、對惡意節(jié)點沒有進行處理、通信效率較低等），提出了DIG-PBFT 算法.文中將動態(tài)積分分組機制引入算法，通過該機制，可以在共識過程中動態(tài)地篩選出拜占庭節(jié)點并禁止其參與共識，使得安全性更高的節(jié)點最大可能地參與到共識過程中，極大地提高了共識效率.仿真實驗結(jié)果證明了DIG-PBFT 算法的吞吐量更大、時延更低.同時通過實驗結(jié)果也能發(fā)現(xiàn)當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)量大量增加，對算法的影響非常大.在未來的工作中，將進一步研究在網(wǎng)絡(luò)中存在大量節(jié)點的情況下，如何提高算法的性能.