基于可信列表的改進(jìn)拜占庭容錯算法

喬 康 湯紅波 游 偉 王領(lǐng)偉

(解放軍戰(zhàn)略支援部隊信息工程大學(xué) 河南 鄭州 450053)

0 引 言

共識算法是區(qū)塊鏈的核心技術(shù)之一[1]，是確保所有節(jié)點(包括普通節(jié)點和處理交易的節(jié)點)彼此同步，并就交易的合法性和區(qū)塊的上鏈達(dá)成一致的協(xié)議。迄今為止，研究者已就區(qū)塊鏈的共識算法做了大量研究工作，提出了多種多樣的共識算法[2～10]，如工作量證明(PoW)[2]、權(quán)益證明(PoS)[3]、股份授權(quán)證明(DPOS)[4]和實用拜占庭容錯(PBFT)[5]等。由于特別適合聯(lián)盟鏈的應(yīng)用場景，PBFT算法及其改進(jìn)算法是目前最常用的聯(lián)盟鏈共識算法[11]。

盡管采用PBFT算法后聯(lián)盟鏈的共識效率得到極大提升，但PBFT算法仍然存在通信開銷大的問題[12]。隨著網(wǎng)絡(luò)節(jié)點數(shù)目N的增加，其通信量將呈平方級O(N2)增長，當(dāng)節(jié)點數(shù)目超過一定值后，由于網(wǎng)絡(luò)帶寬的限制，將造成通信瓶頸，進(jìn)而導(dǎo)致PBFT算法性能的顯著下降。

因此，為減少通信開銷，許多研究在保證安全的前提下，以選舉方式挑選少量節(jié)點參與共識[13]。Crain等[14]借鑒PoS算法思想對PBFT算法進(jìn)行改進(jìn)，提出DBFT算法，根據(jù)節(jié)點權(quán)益值來選舉主節(jié)點和副本節(jié)點；Agarwal等[15]結(jié)合PoW算法，提出改進(jìn)算法Elastico，由普通節(jié)點相互競爭當(dāng)選；Chen等[16]則利用密碼抽簽協(xié)議，提出改進(jìn)算法AlgoRand，隨機(jī)選舉共識節(jié)點; Copeland等[17]結(jié)合Raft算法，對PBFT算法進(jìn)行改進(jìn)，提出更簡潔的Tangaroa算法。

通過選舉少量共識節(jié)點將減少節(jié)點間通信次數(shù)，從而降低開銷和時延。但是，現(xiàn)有算法仍存在以下不足，一是靈活性差，共識節(jié)點數(shù)目固定，節(jié)點身份提前確定，無法動態(tài)添加或刪除；二是容錯率低，系統(tǒng)的故障節(jié)點數(shù)量不得超過全網(wǎng)節(jié)點的1/3，導(dǎo)致容錯率相對較低；三是資源耗費高，無法避免故障節(jié)點的存在，造成通信資源的浪費和算法耗時的增加。

針對上述不足，本文提出了一種基于可信列表的改進(jìn)拜占庭容錯算法(CPBFT)，主要的改進(jìn)包括：(1) 建立一個信用節(jié)點列表。該信用節(jié)點列表有兩方面作用，一是將共識節(jié)點的參與方式由靜態(tài)改進(jìn)為動態(tài)，節(jié)點可動態(tài)進(jìn)入或退出；二是支持通過投票選出信任節(jié)點，在投票周期內(nèi)，網(wǎng)絡(luò)中的所有參與節(jié)點均可進(jìn)行投票，獲得票數(shù)最多的前位節(jié)點組成一個信任節(jié)點列表，該列表將作為共識節(jié)點的候選列表。(2) 設(shè)計一種信用評價機(jī)制。該機(jī)制是共識節(jié)點選舉的依循，包括信用值計算模型和節(jié)點選舉策略。通過該機(jī)制，可從信用節(jié)點列表中，選舉出可信的共識節(jié)點(主節(jié)點和副本節(jié)點)?？尚诺墓沧R節(jié)點，將提升系統(tǒng)容錯率，降低資源開銷。(3) 簡化算法流程?；谛庞迷u價機(jī)制，確保了共識節(jié)點的可信度，由此將PBFT算法的三階段協(xié)議簡化為二階段協(xié)議，進(jìn)一步減少通信開銷、降低算法時延。

1 實用拜占庭容錯(PBFT)算法

為解決存在節(jié)點故障情況下的共識達(dá)成問題，1982年Lamport等提出了拜占庭容錯算法(Byzantine Fault Tolerance，BFT)。但是，長期以來，BFT算法及其改進(jìn)算法都存在復(fù)雜度過高的問題。直到1999年，Castro等[5]提出實用拜占庭容錯算法(PBFT)，將算法復(fù)雜度從指數(shù)級降到多項式級，使得拜占庭容錯算法在實際應(yīng)用中變得可行。PBFT算法可以在故障節(jié)點不超過節(jié)點總數(shù)1/3的情況下同時保證共識的安全性和靈活性[18]。PBFT算法的執(zhí)行流程如圖1所示，其包括請求過程、廣播過程和響應(yīng)過程三個過程。

(1) 請求過程。請求過程包括選主和請求兩個步驟，首先通過輪換或者隨機(jī)算法選擇某個節(jié)點為主節(jié)點，然后由客戶端向主節(jié)點發(fā)送請求消息〈〈REQUEST,operation,timestamp,client〉,σc〉，此后只要主節(jié)點不切換，就稱為一個視圖。

(2) 廣播過程。主節(jié)點收集請求消息，經(jīng)檢查后向所有其他副本節(jié)點廣播該請求消息。

(3) 響應(yīng)過程。所有節(jié)點處理完請求后，將處理結(jié)果〈REPLY，view,timestamp,client,id_node,response〉返回客戶端?？蛻舳私y(tǒng)計收到的處理結(jié)果，當(dāng)接收到至少f+1個(f為可容忍的拜占庭節(jié)點數(shù)目)來自不同節(jié)點的相同結(jié)果時，該處理結(jié)果為最終結(jié)果。

圖1 實用拜占庭容錯算法的執(zhí)行流程

其中，主節(jié)點廣播過程包括三個階段，分別為預(yù)準(zhǔn)備階段、準(zhǔn)備階段和提交階段。

① 預(yù)準(zhǔn)備階段。主節(jié)點首先為客戶端的請求分配編號，然后向各副本節(jié)點發(fā)送預(yù)準(zhǔn)備消息〈〈PRE-PREPARE,view,n,digest〉,σp,message〉，其中view是視圖號，n是提案號，message是請求消息，digest是消息的數(shù)字摘要。

② 準(zhǔn)備階段。副本節(jié)點首先驗證預(yù)準(zhǔn)備消息的合法性，通過驗證后向其他節(jié)點發(fā)送準(zhǔn)備消息〈〈PREPARE，view,n,digest,id〉,σi〉，其中id為副本節(jié)點的身份證明。副本節(jié)點在發(fā)送準(zhǔn)備消息的同時，也接收其他節(jié)點的準(zhǔn)備消息。準(zhǔn)備消息驗證后，則被添加到消息日志中，當(dāng)接收到至少2f個驗證過的準(zhǔn)備消息后，節(jié)點進(jìn)入準(zhǔn)備階段。

③ 提交階段。節(jié)點廣播確認(rèn)消息〈〈COMMIT,view,n,digest〉,σi〉，通知其他節(jié)點某個提案n在視圖view中已處于準(zhǔn)備階段，當(dāng)接收到至少2f+1個驗證過的COMMIT消息后，說明提案通過。

2 算法設(shè)計

2.1 信任節(jié)點列表建立

如圖2中第一部分所示，在投票周期T內(nèi)，區(qū)塊鏈網(wǎng)絡(luò)中的所有節(jié)點i均可參與投票，通過統(tǒng)計各節(jié)點得票數(shù)目ni，獲得票數(shù)最多的前h位節(jié)點，排序組成一個列表作為信用節(jié)點列表。投票提案vote由系統(tǒng)每隔一段時間發(fā)起，首先，投票主節(jié)點向普通投票節(jié)點廣播投票準(zhǔn)備消息PREPAREvote；其次，投票節(jié)點自由投票并將投票結(jié)果RESULTvote回復(fù)主節(jié)點；最后，由投票主節(jié)點統(tǒng)計得票結(jié)果并廣播給所有節(jié)點。信任節(jié)點列表的建立主要依賴投票制度，其前提假設(shè)為區(qū)塊鏈網(wǎng)絡(luò)中的大部分節(jié)點是合法節(jié)點。每個節(jié)點擁有一次投票機(jī)會，可選擇自己，也可選擇其他節(jié)點。信用節(jié)點列表將作為候選集，供下一步共識節(jié)點選舉使用，如圖2中第二部分所示。通過建立信用節(jié)點列表，將共識節(jié)點的參與方式由靜態(tài)改進(jìn)為動態(tài)，節(jié)點可動態(tài)進(jìn)入或退出，提高了節(jié)點的靈活性。

圖2 基于信用列表的共識節(jié)點選舉

2.2 節(jié)點信用評價機(jī)制

為從信用節(jié)點列表中選擇出高可信度的共識節(jié)點，本文設(shè)計了一種節(jié)點信用評價機(jī)制，該機(jī)制包括了信用值計算模型和共識節(jié)點選舉策略。

2.2.1信用值計算模型

首先，對節(jié)點信用值計算進(jìn)行建模，信用值的計算分為兩種情況：一是信用獎勵，如式(1)所示；二是信用懲罰，如式(2)所示。

Ci=(ni/N)×K-(t/T)×Z+X

(1)

Ci=(ni/N)×K-(t/T)×Z-X

(2)

式中：Ci代表節(jié)點i的信用值;ni代表節(jié)點i獲得的投票數(shù);N代表總的投票數(shù);K代表信用參數(shù);t為節(jié)點添加到列表后經(jīng)歷的時間(0

節(jié)點信用值計算模型的描述。節(jié)點的信用值計算模型由三部分組成:初始信用值Cinit，Cinit=(ni/N)×K,由節(jié)點的初始得票情況決定；信用衰減值Cfall=(t/T)×Z，在一輪投票周期T內(nèi)，隨著時間t的增加，節(jié)點信用值將不斷衰減；信用獎懲值Cmotiva=X，如果節(jié)點作為共識節(jié)點成功完成一輪共識，則獲取信用值獎勵，增加X，如果節(jié)點在共識中出現(xiàn)故障，則受到懲罰，減少X。根據(jù)實際的共識算法要求，設(shè)置合理的參數(shù)，可以建立合適的節(jié)點信用值計算公式。

2.2.2共識節(jié)點選舉策略

經(jīng)信用值計算得出節(jié)點信用值后，通過以下策略為節(jié)點劃分信用等級，并選舉出可信共識節(jié)點：

(1) 當(dāng)節(jié)點i的信用值Ci≥Cgreat時，將該節(jié)點劃分為高信用等級節(jié)點。然后，將節(jié)點i添加到主節(jié)點的候選集，如果每次共識主節(jié)點的數(shù)目需求為1個，則將候選集中的節(jié)點按照信用值大小排序，輪流擔(dān)任主節(jié)點；

(2) 當(dāng)節(jié)點i的信用值Cgood≤Ci

(3) 當(dāng)節(jié)點i的信用值Ci

此外，為激勵節(jié)點參與維護(hù)區(qū)塊鏈，本文設(shè)置經(jīng)濟(jì)激勵措施來回饋共識節(jié)點的工作。每筆交易會按照比例收取一定的服務(wù)費，作為獎勵金。共識完成后，所有共識節(jié)點(主節(jié)點和副本節(jié)點)均分50%的服務(wù)費，負(fù)責(zé)成塊的主節(jié)點額外獲得剩余50%的服務(wù)費。為最大化收益，參與節(jié)點會盡可能提高信用值，以增大成為主節(jié)點的幾率。該方式利用經(jīng)濟(jì)博弈論思想來降低節(jié)點作惡風(fēng)險。

通過節(jié)點信用評價機(jī)制，可從信用節(jié)點列表中，選舉出可信的共識節(jié)點(主節(jié)點和副本節(jié)點)。可信的共識節(jié)點，將提升系統(tǒng)容錯率，降低資源浪費。

2.3 改進(jìn)共識算法

基于上述方法，本文提出基于可信列表的改進(jìn)拜占庭容錯算法(CPBFT)。與PBFT算法不同，CPBFT算法的執(zhí)行流程包括選舉過程和共識過程，如圖3所示。

圖3 CPBFT共識算法的執(zhí)行流程

值得注意的是：(1) CPBFT算法的選舉過程并非每輪共識前都進(jìn)行，而是在一輪投票周期內(nèi)執(zhí)行一次選舉，然后支持多輪共識；(2) CPBFT算法的共識過程由PBFT算法的三階段協(xié)議簡化為二階段協(xié)議。

算法1CPBFT共識算法

開始

選舉過程

1.clientvote→primnodevote:〈〈REQUESTvote,operation,timestamp,client〉,σvc〉

//投票請求

2.primnodvote→nodevote:〈〈PREPAREvote，vote,digest〉，σvp,messagevote〉

//投票準(zhǔn)備

3.IfHash(messagevote)=digest

//投票消息校驗

4.nodevote→clientvote:〈〈REPLYvote,vote,digest2,id〉，σvi,messagereply〉

//投票響應(yīng)

5.IfHash(messagereply)=digest2

//響應(yīng)消息校驗

6.clientvote→primnodevote:〈〈RESULTvote,vote,digest3,client〉，σvcl,messageresult〉

//共識過程

7.clientcon→primnodecon:〈〈REQUESTcon,operation,timestampcon,clientcon〉，σc〉

//共識請求

8.primnodecon→replica:〈〈PRE-PREPAREcon,view,n,digestcon〉,σp,messagecon〉

//預(yù)準(zhǔn)備

9.IfHash(messagecon)=digestcon

//共識消息校驗

10.replica→primnodecon,replicai:〈〈COMMITcon,view,n,digestcon〉,σi〉

//提交

11.primnodecon,replica→clientvote: 〈〈REPLYcon,view,timestampcon,clientcon,id_node,response〉,σi〉

結(jié)束

CPBFT算法的選舉過程包括投票請求、投票準(zhǔn)備、投票響應(yīng)和廣播結(jié)果四個階段。

(1) 投票請求階段?？蛻舳讼蛲镀敝鞴?jié)點發(fā)送請求消息〈〈REQUESTvote,operation,timestamp,client〉,σvc〉，其中:client是請求投票的客戶端號，timestamp是申請投票的時間，σvc是投票客戶端對消息的簽名。

(2) 投票準(zhǔn)備階段。投票主節(jié)點首先為客戶端的投票請求分配編號，然后向各普通節(jié)點發(fā)送投票準(zhǔn)備消息〈〈PREPAREvote,vote,digest〉,σvp,messagevote〉，其中:vote是提案號，messagevote是投票請求消息，digest是請求消息的數(shù)字摘要，σvp是投票主節(jié)點對消息的簽名。

(3) 投票響應(yīng)階段。普通節(jié)點首先驗證投票準(zhǔn)備消息的合法性，通過驗證后向客戶端發(fā)送投票響應(yīng)消息〈〈REPLYvote,vote,digest2,id〉,σvimessagereply〉，其中，id是各節(jié)點的身份證明，messagereply是投票響應(yīng)消息，digest2是響應(yīng)消息的數(shù)字摘要，σvi是普通投票節(jié)點對消息的簽名。

(4) 廣播結(jié)果階段?？蛻舳蓑炞C投票響應(yīng)消息的非法性，通過驗證后向各節(jié)點(包括投票主節(jié)點和普通節(jié)點)發(fā)送投票結(jié)果消息〈〈RESULTvote,vote,digest3,client〉,σvc1,messageresult〉，其中:messageresult是投票結(jié)果消息，digest3是結(jié)果消息的數(shù)字摘要，σvc1是投票客戶端對投票結(jié)果消息的簽名。

CPBFT算法的共識過程包括請求、預(yù)準(zhǔn)備、提交和響應(yīng)四個階段。

(1) 請求階段?？蛻舳讼蚬沧R主節(jié)點發(fā)送請求消息〈〈REQUESTcon,operation,timestampcon,clientcon〉，σc〉，其中：clientcon是請求共識的客戶端號，timestampcon是申請共識的時間，σc是客戶端對消息的簽名。

(2) 預(yù)準(zhǔn)備階段。主節(jié)點首先為客戶端的請求分配編號，然后向各副本節(jié)點發(fā)送預(yù)準(zhǔn)備消息〈〈PRE-PREPAREcon,view,n,digestcon〉,σp,messagecon〉，其中：view是視圖號，n是提案號，messagecon是共識請求消息，digestcon是消息的數(shù)字摘要，σp是主節(jié)點對消息的簽名。

(3) 提交階段。副本節(jié)點首先驗證預(yù)準(zhǔn)備消息的合法性，通過驗證后，副本節(jié)點廣播〈〈COMMITcon,view,n,digestcon〉，σi〉消息，通知其他節(jié)點某個提案n在視圖view中已處于準(zhǔn)備階段，當(dāng)接收到至少2f+1個驗證過的COMMITcon消息后，說明提案通過。

(4) 響應(yīng)階段。所有節(jié)點處理完請求后，將處理結(jié)果〈〈REPLYcon,view,timestampcon,clientcon,id_node,response〉,σi〉返回客戶端，其中：id_node是節(jié)點編號，response是節(jié)點回復(fù)，σi是節(jié)點對消息的簽名?？蛻舳私y(tǒng)計收到的處理結(jié)果，當(dāng)接收到至少f+1個來自不同節(jié)點的相同結(jié)果，則該結(jié)果作為最終結(jié)果。

3 仿真分析

為綜合評價CPBFT共識算法的性能，以交易吞吐量、交易時延和通信帶寬開銷三個指標(biāo)為衡量標(biāo)準(zhǔn)，進(jìn)行仿真實驗。其中吞吐量是衡量算法執(zhí)行效率的指標(biāo)，時延是衡量算法響應(yīng)能力的指標(biāo)，帶寬開銷是衡量算法通信復(fù)雜度的指標(biāo)。

3.1 吞吐量和時延分析

吞吐量是指每秒完成的交易數(shù)，定義吞吐量的計算式為：

TPS=SizeBlock/SizeTx/Tblock

(3)

式中：TPS代表吞吐量;SizeBlock代表區(qū)塊的存儲容量;SizeTx代表交易的大小;Tblock代表成塊的時間，即共識達(dá)成的時間。以比特幣的工作量證明算法(PoW)為例，成塊時間約為10分鐘，在現(xiàn)有的大多數(shù)區(qū)塊鏈平臺中，區(qū)塊的存儲容量約為1 MB，交易的大小約為250 B，因此，比特幣的交易吞吐量TPS約為7筆/秒。

對于單筆交易，時延是指請求時間(t1)和共識完成時間(t2)的差值(t2-t1)。對于一組交易，時延是指一組交易中第一筆交易的請求時間和最后一筆交易共識完成時間的差值，即最大單筆交易時延。

為評價CPBFT算法的吞吐量和時延情況，在配置為Intel Core i7-6700M @3.40 GHz處理器和16 GB內(nèi)存，安裝了64位Windows 7系統(tǒng)的PC，通過Eclipse2018平臺用Java語言編程實現(xiàn)了PBFT和CPBFT算法，并進(jìn)行了時延和吞吐量測試。其中，PBFT算法的實現(xiàn)與測試?yán)昧薌ithub平臺上的pbftSimulator項目所共享的部分代碼。每組實驗獨立運行10次并求平均值作為測試結(jié)果，主要參數(shù)設(shè)置如表1所示。

表1 吞吐量和時延實驗參數(shù)表

圖4展示了吞吐量和交易數(shù)量的關(guān)系，隨著交易數(shù)量的增加，除在交易數(shù)為7 000時有拐點外，兩個算法的吞吐量整體均呈線性增加趨勢。當(dāng)交易數(shù)量小于100時，CPBFT算法的吞吐量小于PBFT算法；當(dāng)交易數(shù)量大于1 000時，CPBFT算法的吞吐量大于PBFT算法，且隨著交易數(shù)量增加，吞吐量差值逐漸增大。

圖4 吞吐量和交易數(shù)量的關(guān)系

在不考慮時延的情況下，討論吞吐量是不嚴(yán)謹(jǐn)且無意義的，并且時延也是衡量算法響應(yīng)能力的指標(biāo)，因此本文還測試了時延和交易數(shù)量的關(guān)系，結(jié)果如圖5所示?？梢钥闯?，隨著交易數(shù)量的增加，兩個算法的時延均呈線性增加，且當(dāng)交易數(shù)小于100時，CPBFT算法的時延大于PBFT，當(dāng)交易數(shù)大于1 000時，CPBFT算法的時延小于PBFT算法。

圖5 時延和交易數(shù)量的關(guān)系

由圖4和圖5可見，隨著交易數(shù)量的增加，吞吐量和時延均呈線性增加，但是在實際的聯(lián)盟鏈應(yīng)用中，一般要求時延小于3秒。由圖5可知，3秒時延對應(yīng)的交易數(shù)量約為4 000筆；再由圖4可知，4 000筆交易對應(yīng)的吞吐量約為1 400筆/秒。因此，基于實際應(yīng)用考慮，討論CPBFT和PBFT算法的吞吐量和時延比較，應(yīng)限制在時延小于3秒和交易數(shù)低于4 000筆的范圍內(nèi)。在本文實驗條件下，當(dāng)交易數(shù)為4 000時，CPBFT算法的時延為2 812 ms，PBFT算法的時延為2 900 ms；CPBFT算法的吞吐量為1 422筆/秒，PBFT算法的吞吐量為1 379筆/秒。此時，相較于PBFT算法，CPBFT算法的吞吐量提升了約3.12%，時延降低了約3.03%。

3.2 通信帶寬開銷分析

CPBFT算法的執(zhí)行選舉和共識過程均產(chǎn)生通信帶寬開銷。其中，選舉過程包括投票請求、準(zhǔn)備、響應(yīng)和廣播結(jié)果四個階段，共識過程包括請求、預(yù)準(zhǔn)備、提交和響應(yīng)四個階段，定義其帶寬開銷為：

Bandwithcpbft=k×[1+(N-1)+N×(N-1)+N]×message+

[1+(NV-1)+NV+NV]×Vote=

k×(N2+N)×message+3NV×Vote

(4)

式中：Bandwithcpbft為通信帶寬開銷；N為總的共識節(jié)點數(shù)目;NV是總的投票節(jié)點數(shù)目(NV?N);message為驗證消息;Vote為投票消息;k為一輪投票周期內(nèi)執(zhí)行的共識次數(shù)。

將CPBFT算法應(yīng)用于區(qū)塊鏈中，共識過程驗證的消息為區(qū)塊數(shù)據(jù)(SizeBlock)，選舉過程傳遞的數(shù)據(jù)為投票數(shù)據(jù)(Vote)，SizeBlock?Vote,此時帶寬開銷為：

Bandwithcpbft=k×(N2+N)×SizeBlock+3NV×Vote

(5)

同理，PBFT[19]算法僅執(zhí)行共識過程，包括請求、預(yù)準(zhǔn)備、準(zhǔn)備、提交和響應(yīng)五個階段，定義其帶寬開銷為：

Bandwithpbft=k×[1+(N-1)+(N-1)×(N-1)+

N×(N-1)+N]×message=

k×(2N2-2N+N+1)×message

(6)

將PBFT算法應(yīng)用于區(qū)塊鏈中，帶寬開銷為：

Bandwithpbft=k×(2N2-2N+N+1)×SizeBlock

(7)

DBFT[22]算法執(zhí)行選舉和共識兩個過程，選舉過程包括廣播節(jié)點身份一個階段，共識過程包括請求、預(yù)準(zhǔn)備、準(zhǔn)備、提交和響應(yīng)五個階段，定義其帶寬開銷為：

Bandwithdbft=k×(2N2-2N+N+1)×

message+NV×Vote

(8)

將DBFT算法應(yīng)用于區(qū)塊鏈中，帶寬開銷為：

Bandwithdbft=k×(2N2-2N+N+1)×

SizeBlock+NV×Vote

(9)

其中，由于廣播節(jié)點身份的數(shù)據(jù)量和投票的數(shù)據(jù)量大致相當(dāng)，為便于對比，本文用投票數(shù)據(jù)Vote替代廣播節(jié)點身份的數(shù)據(jù)。

為評價CPBFT算法通信帶寬開銷情況，在相同配置的計算機(jī)上進(jìn)行仿真，通過MATLAB 2018a對CPBFT、PBFT和DBFT共識算法進(jìn)行數(shù)學(xué)計算仿真，參數(shù)設(shè)置如表2所示。

表2 帶寬開銷實驗參數(shù)表

第一組仿真是為比較不同算法的帶寬開銷情況。圖6展示了不同算法的帶寬開銷和共識節(jié)點數(shù)目的關(guān)系，該實驗中固定NV=1 000,k=5。隨共識節(jié)點數(shù)目的增加，三種算法的帶寬開銷均呈指數(shù)遞增，且CPBFT算法的增長率較小，PBFT和DBFT算法的增長率相近且較大；在共識節(jié)點數(shù)少于15時，算法帶寬開銷由大到小排序為CPBFT算法、DBFT算法、PBFT算法，這是由于CPBFT和DBFT算法與PBFT算法相比，增加了選舉過程的通信開銷；當(dāng)共識節(jié)點數(shù)目大于25后，算法帶寬開銷由大到小排序為DBFT算法、PBFT算法、CPBFT算法，且PBFT算法帶寬開銷有超越DBFT算法的趨勢。在本文實驗條件下，當(dāng)節(jié)點數(shù)目為50時，PBFT算法的帶寬開銷約為2.576×104KB，DBFT算法的帶寬開銷約為2.476×104KB，CPBFT算法的帶寬開銷為1.475×104KB，此時，CPBFT算法較PBFT算法帶寬開銷下降了約42.74%，較DBFT算法帶寬開銷下降了約40.43%?？梢缘贸?，在共識節(jié)點數(shù)目較多的情況下，CPBFT算法具有更低的帶寬開銷。

圖6 通信帶寬開銷和共識節(jié)點數(shù)目的關(guān)系

圖7展示了在不同共識執(zhí)行次數(shù)k下，帶寬開銷和投票節(jié)點數(shù)目的關(guān)系，該實驗中固定N=20。當(dāng)執(zhí)行次數(shù)k相同時，隨投票節(jié)點數(shù)目的增加，CPBFT和DBFT算法的帶寬開銷均呈線性增加，且CPBFT算法的增長率更大；當(dāng)投票節(jié)點數(shù)目NV相同時，隨執(zhí)行次數(shù)k的增加，CPBFT和DBFT算法的帶寬開銷均增加，且DBFT算法增長幅度更大?？梢缘贸?，CPBFT算法的帶寬開銷受投票節(jié)點數(shù)目的影響更大，DBFT算法的帶寬開銷受執(zhí)行次數(shù)的影響更大。

圖7 通信帶寬開銷和投票節(jié)點數(shù)目的關(guān)系

第二組測試是為比較不同算法應(yīng)用于區(qū)塊鏈中時的帶寬開銷情況。應(yīng)用于區(qū)塊鏈時，共識是以包含多條交易的一個區(qū)塊為最小單元進(jìn)行的，這不同于第一組實驗中以一條交易為最小單元的共識過程，其測試結(jié)果如圖8所示。圖6和圖8變化趨勢相似，不同點在于PBFT和DBFT算法的曲線幾乎重合，而CPBFT算法的曲線一直處于兩者的下方。在本文實驗條件下，當(dāng)節(jié)點數(shù)目為50時，PBFT和DBFT算法的帶寬開銷相近且約為2.535×107KB，CPBFT算法的帶寬開銷約為1.306×107KB，此時CPBFT算法較PBFT和DBFT算法的帶寬開銷下降了約48.48%。

圖8 通信帶寬開銷和共識節(jié)點數(shù)目的關(guān)系(應(yīng)用于區(qū)塊鏈)

圖9所示為應(yīng)用于區(qū)塊鏈時通信開銷和投票節(jié)點數(shù)目的關(guān)系。圖7和圖9差別在于，當(dāng)執(zhí)行次數(shù)相同k時，隨投票節(jié)點數(shù)目NV的增加，帶寬開銷幾乎不變。這是由于共識過程驗證的消息為區(qū)塊數(shù)據(jù)SizeBlock，其數(shù)據(jù)量遠(yuǎn)大于投票消息message的數(shù)據(jù)量，相較于共識過程，投票過程的帶寬開銷占比極小。

圖9 通信帶寬開銷和投票節(jié)點數(shù)目的關(guān)系(應(yīng)用于區(qū)塊鏈)

由上述仿真結(jié)果可以得出，相較于PBFT和DBFT算法，CPBFT算法具有更低的通信帶寬開銷。

4 結(jié) 語

本文針對PBFT算法存在的靈活性差、容錯率低和資源耗費高的不足，提出了一種基于可信列表的改進(jìn)拜占庭容錯算法。首先，建立了一個信用節(jié)點列表，將共識節(jié)點的參與方式由靜態(tài)改進(jìn)為動態(tài)，節(jié)點可動態(tài)進(jìn)入或退出；其次，設(shè)計了一種節(jié)點信用評價機(jī)制，作為共識節(jié)點選舉的依循，提升了系統(tǒng)容錯率；最后，基于信用評價機(jī)制，將PBFT算法的三階段協(xié)議簡化為二階段，進(jìn)一步減少了通信開銷、降低了算法時延。區(qū)塊鏈作為一種公開的賬本系統(tǒng)，交易信息被收集并詳細(xì)記錄其中，任何參與者都可以查詢鏈上信息，故其面臨嚴(yán)重的隱私泄露風(fēng)險。下一步將重點研究區(qū)塊鏈隱私保護(hù)問題。