基于信用分級的PBFT共識算法改進方案①

丁庭琛,陳世平

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海 200093)

區(qū)塊鏈技術(shù)最早出現(xiàn)在比特幣中[1],作為已知的分布式賬本,在過去幾年中引起各界廣泛的研究.Blockchain是一種點對點分布式系統(tǒng),具有高安全性和分散存儲,高容錯和加密性等特性.為了解決現(xiàn)有中心化機構(gòu)效率低、成本高、數(shù)字資源壟斷等問題,區(qū)塊鏈整合密碼學(xué)、計算機和通信等領(lǐng)域等技術(shù),所用技術(shù)有非對稱加密、時間戳、共識機制和點對點通信[2],實現(xiàn)中心化分布式系統(tǒng).區(qū)塊鏈技術(shù)被認為是引起人類社會顛覆性變革的關(guān)鍵技術(shù)之一[3].

公有鏈和聯(lián)盟鏈?zhǔn)菂^(qū)塊鏈的兩種主要形式[4].比特幣是區(qū)塊鏈最早的應(yīng)用,也是公共區(qū)塊鏈最著名的例子.比特幣作為最早的數(shù)字貨幣,僅使用單一的去中心化技術(shù),存在很大功能局限性.隨著智能合約[5]的發(fā)展,公有鏈有了更加智能的應(yīng)用平臺.例如以太坊(etherum)平臺就是一個可編程的區(qū)塊鏈平臺[6],在系統(tǒng)資產(chǎn)自動化管理方面有顯著進步.公有區(qū)塊鏈?zhǔn)峭耆ブ行幕到y(tǒng),沒有管理和監(jiān)督,任何人都可以參與公有鏈并且訪問數(shù)據(jù).因此,公有鏈存在一定的弊端,隱私和安全性難以得到保障,可靠性差[7].為了更好地保護用戶的隱私和監(jiān)督數(shù)據(jù),提出了聯(lián)盟鏈概念,其中,Hyperledger 是經(jīng)典的聯(lián)盟鏈系統(tǒng)[8].聯(lián)盟鏈在企業(yè)級組織內(nèi)部廣泛發(fā)展[9].在聯(lián)盟區(qū)塊鏈中,只有特定允許的節(jié)點才能訪問網(wǎng)絡(luò).因此,聯(lián)盟區(qū)塊鏈可以很好地支持企業(yè)級應(yīng)用程序,并在公共和政府服務(wù)中被廣泛采用.

共識機制是區(qū)塊鏈的核心,區(qū)塊鏈中有PoW 和PoS算法[10],Raft 算法[11],PBFT 算法[12]等共識機制.一般情況下存在拜占庭問題都由PBFT 算法解決.拜占庭式故障模型[13]假設(shè)副本可以通過任意行動而被惡意攻擊[14],該模型適用于區(qū)塊鏈系統(tǒng).針對模型中的共識問題,許多理論成果相繼出現(xiàn),不過較早的協(xié)議都是從理論上解決問題,無法在實際場景中應(yīng)用.PBFT 是第一個為實際應(yīng)用開發(fā)的協(xié)議,解決了分布式文件系統(tǒng)可容忍拜占庭式故障問題.不過PBFT 無法在實際場景中廣泛應(yīng)用,它存在擴展性差,通信開銷大,效率低等問題[15].

針對聯(lián)盟鏈的應(yīng)用場景,本文提出了一種基于PBFT改進的一致性算法,稱為CLBFT (Credit-Layered Byzantine Fault Tolerance).受PoW 共識機制的啟發(fā),基于信用獎勵和懲罰節(jié)點,基于節(jié)點信用值的基礎(chǔ)上給節(jié)點分級,旨在長期維持系統(tǒng)良好運行.通過這種方案,可以大大提高參與者的積極性,減少惡意節(jié)點參與帶來的影響,提高系統(tǒng)的安全性和效率.

1 PBFT

Castro 和Liskov 在1999年提出的實用的拜占庭容錯協(xié)議(PBFT)被認為是解決拜占庭將軍問題的最經(jīng)典協(xié)議.PBFT 是為解決分布式系統(tǒng)中存在拜占庭故障節(jié)點從而達成信息一致性的問題.為保障系統(tǒng)正常運轉(zhuǎn),當(dāng)系統(tǒng)中無效或者惡意點數(shù)為f時,要求總節(jié)點n不小于3f+1.PBFT 算法主要包括一致性協(xié)議,視圖切換協(xié)議和檢查點協(xié)議3 個部分.

1.1 一致性協(xié)議

一致性協(xié)議是PBFT 算法的核心,主要作用是保證區(qū)塊鏈系統(tǒng)中信息的正確和相同.在PBFT 算法中存在客戶端(client),主節(jié)點(primary),從節(jié)點(replica)3 種角色.客戶端c主要作用是向主節(jié)點發(fā)送請求＜REQUEST,o,t,c＞,o為請求的具體操作,t為時間戳.主節(jié)點通過視圖編號以及節(jié)點數(shù)集合來確定,主節(jié)點公式如下:p=vmod|R|,其中v是視圖編號,|R|是節(jié)點個數(shù),p是主節(jié)點編號.主節(jié)點和從節(jié)點作為副本節(jié)點參與算法的主要3 個通信階段:預(yù)準(zhǔn)備階段(pre-prepare)、準(zhǔn)備階段(prepare)、確認階段(commit).

1)預(yù)準(zhǔn)備階段:主節(jié)點接受到客戶端c 的請求,丟棄錯誤請求,對正確的請求進行排序,并分配編號n.然后主節(jié)點向系統(tǒng)中的其他從節(jié)點廣播一條＜＜PRE-PERPARE,v,n,d＞,m＞消息.

2)準(zhǔn)備階段:節(jié)點對收到的預(yù)準(zhǔn)備消息進行判斷,如果同意預(yù)準(zhǔn)備消息,則進入準(zhǔn)備階段,然后向其他節(jié)點(包括主節(jié)點)廣播＜PREPARE,v,n,d,i＞消息.

3)確認階段:當(dāng)節(jié)點收到2f+1 個通過驗證的消息時準(zhǔn)備階段結(jié)束進入確認階段,節(jié)點向包括主節(jié)點在內(nèi)的其他節(jié)點發(fā)送＜COMMIT,v,n,D(m),i＞消息.

圖1是一次一致性協(xié)議過程.“Client”是客戶端,“Primary”是主節(jié)點,“Replical1”、“Replical2”、“Replical3”是3 個從節(jié)點.即使“Replical3”是故障節(jié)點,系統(tǒng)任可以通過一致性協(xié)議.

圖1 一致性協(xié)議交互過程

1.2 視圖切換協(xié)議

視圖切換協(xié)議是針對主節(jié)點發(fā)生故障時,維持系統(tǒng)正確運行的協(xié)議.1 個視圖中有1 個主節(jié)點,當(dāng)主節(jié)點發(fā)生故障時,視圖需要改變,視圖編號加1 即v+1,更換新的主節(jié)點.主節(jié)點發(fā)生故障時,從節(jié)點觸發(fā)視圖切換協(xié)議,系統(tǒng)設(shè)置兩個觸發(fā)條件:從最近完成的一個區(qū)塊的時間戳T開始,在限定時間T1內(nèi)沒有收到新主節(jié)點的Pre-prepare 廣播,或是在限定時間T2內(nèi)沒有生成新的區(qū)塊,其中T1＜T2.上述兩個觸發(fā)條件滿足其中一個就會觸發(fā)視圖切換協(xié)議.為了保證系統(tǒng)的正確性和一致性,視圖切換也要進行節(jié)點間的交互通信.View-Change 的工作過程如下:

1)視圖切換協(xié)議開啟后,從節(jié)點進入視圖v+1,并向所有節(jié)點廣播View-Change 消息.

2)副本節(jié)點在收到2f+1 條(包括自身)View-Change消息后,向視圖v+1 中的主節(jié)點發(fā)送View-Change-Ack消息,新主節(jié)點收到View-Change-Ack 消息后進入New-View 階段.

3)新的主節(jié)點選擇檢查點作為“New-View”請求的起始狀態(tài),然后根據(jù)本地塊鏈接數(shù)據(jù)執(zhí)行一致性協(xié)議.

1.3 檢查點協(xié)議

在共識過程中,節(jié)點會生成大量的日志,系統(tǒng)長期運行下就會存儲大量信息.檢查點協(xié)議的作用就是減小節(jié)點信息存儲規(guī)模,釋放經(jīng)過共識認證的日志消息,降低系統(tǒng)內(nèi)存開銷.某些節(jié)點由于自身故障或網(wǎng)絡(luò)問題沒有和其他節(jié)點同步,影響系統(tǒng)的運行,因此需要Checkpoint 協(xié)議周期性工作,它在確認節(jié)點的一致性后清除經(jīng)過驗證的證書.

1.4 PBFT 存在的問題

雖然PBFT 算法對區(qū)塊鏈的共識性能改善很大,但是任然存在通信開銷大,擴展性差,效率低等問題.首先PBFT 算法是一種部分同步模式共識算法,為了保證非故障節(jié)點以相同順序執(zhí)行客戶端的請求,需要三階廣播通信實現(xiàn)異步模式下的安全性,造成大量的通信開銷.其次,PBFT 算法需要點對點通信進行拜占庭容錯共識.在N個節(jié)點的網(wǎng)絡(luò)中,PBFT 通信的時間復(fù)雜度是O (N2),經(jīng)過三階段共識之后消息傳輸次數(shù)為2N(N-1).由于通信的復(fù)雜性,當(dāng)節(jié)點數(shù)超過一定量時,PBFT 協(xié)議的性能會急劇下降.最后是PBFT 算法主節(jié)點選取隨意,選到惡意節(jié)點的概率偏高,影響系統(tǒng)效率.

2 基于分級的高效共識機制

PBFT 算法中選取主節(jié)點隨意.它是根據(jù)編號的順序依次得到主節(jié)點,并且選出的主節(jié)點沒有任何檢驗,無法保證系統(tǒng)的安全性.用這種方法選舉出來的主節(jié)點存在惡意節(jié)點的可能性很大,從識破惡意節(jié)點到通過視圖切換協(xié)議更換主節(jié)點,造成大量網(wǎng)絡(luò)通信開銷,降低了系統(tǒng)效率.本文采用信用評估和節(jié)點分級協(xié)議對PBFT 算法加以改進,提出了CLBFT 共識機制.CLBFT主要改進的地方有:

1)制定信用積分規(guī)則,評估節(jié)點信用狀態(tài).

2)依據(jù)信用積分對節(jié)點進行分級,選擇積極節(jié)點參與一致性協(xié)議,提高節(jié)點動態(tài)性.

3)在可信節(jié)點層選擇主節(jié)點,大大減少惡意節(jié)點對系統(tǒng)運行的破壞,減少通信開銷,提高系統(tǒng)效率.

2.1 信用分級協(xié)議

定義Ci代表節(jié)點的信用積分,節(jié)點的信用級別劃分為4 個級別:A、B、C、D.剛加入的節(jié)點的信用值為Cnormal,根據(jù)節(jié)點在系統(tǒng)中的行為增加信用積分或減少信用積分.節(jié)點在系統(tǒng)中參與一次有效區(qū)塊的生成則節(jié)點信用積分加1;節(jié)點在系統(tǒng)中未生成有效區(qū)塊則信用積分減5.信用值在Cnormal≤Ci＜Cgood區(qū)間的節(jié)點信用級別為B,初入節(jié)點也在此列;當(dāng)節(jié)點的信用值大于Cgood時,即Ci＞Cgood,節(jié)點信用級別為A;信用值為Cbad≤Ci＜Cnormal時,節(jié)點信用級別為C;當(dāng)節(jié)點的信用值低于Cbad時,即Ci＜Cbad節(jié)點的信用級別為D.節(jié)點信用分級轉(zhuǎn)換如圖2所示.

圖2 節(jié)點信用狀態(tài)分級圖

依據(jù)信用分級協(xié)議將節(jié)點劃分為四類,每類節(jié)點有不同的權(quán)限.A 類節(jié)點信用級別最高,優(yōu)先擔(dān)任主節(jié)點.其次是B 類節(jié)點,當(dāng)A 類節(jié)點被選擇完畢或不存在A 類節(jié)點,可以從B 類節(jié)點中選擇主節(jié)點.C 類節(jié)點由于信用級別偏低不適合擔(dān)任主節(jié)點,但任然可以作為從節(jié)點參與區(qū)塊共識.D 類節(jié)點信用級別太低,不能參與共識.權(quán)限分類不僅能夠大大提高節(jié)點的積極性,而且有效預(yù)防惡意節(jié)點成為主節(jié)點.有效地減少惡意節(jié)點參與共識帶來的通信損失和減少View-Change 變更次數(shù),提高系統(tǒng)效率,如表1區(qū)分節(jié)點權(quán)限.

表1 節(jié)點權(quán)限分類

2.2 CLBFT 共識過程

CLBFT 算法的過程如圖3所示.首先,根據(jù)信用分級協(xié)議對節(jié)點進行分級.信用分級協(xié)議的周期為zCT,其中CT是檢查點協(xié)議的周期,z為系數(shù).依據(jù)系統(tǒng)中節(jié)點數(shù)量調(diào)整合適的系數(shù)z按照周期間隔zCT更新節(jié)點信用積分,節(jié)點依據(jù)信用積分分成不同級別.然后,不同級別的節(jié)點有不同的權(quán)限,有相應(yīng)權(quán)限的節(jié)點參與選出主節(jié)點.節(jié)點根據(jù)自身的行為獲得相應(yīng)的信用積分,當(dāng)節(jié)點積分滿足A 類信用級別時,進入集合A.集合A中的節(jié)點獲得視圖編號,參與主節(jié)點選擇,保證主節(jié)點選取的最優(yōu)性.接下來,主節(jié)點選出后參與一致性協(xié)議,并監(jiān)督一致性協(xié)議以判斷主節(jié)點是否觸發(fā)View-Change 中設(shè)置的兩個超時觸發(fā)條件.若超時,觸發(fā)視圖切換協(xié)議,更換主節(jié)點,視圖v+1,否則生成新區(qū)塊寫入?yún)^(qū)塊鏈.最后執(zhí)行改進的檢查點協(xié)議(Checkpoint)釋放經(jīng)過共識認證的日志消息,降低系統(tǒng)內(nèi)存開銷.

圖3 CLBFT 流程圖

3 性能分析與實驗

PBFT 算法的主節(jié)點選取較為隨意,是根據(jù)編號的順序依次得到主節(jié)點.用這種方法選舉出來的主節(jié)點存在惡意節(jié)點的可能性很大,視圖切換協(xié)議較多會造成大量網(wǎng)絡(luò)通信開銷,降低了系統(tǒng)效率.本文提出的CLBFT 算法是對PBFT 算法的改進.制定信用積分規(guī)則,評估節(jié)點信用狀態(tài).依據(jù)信用積分對節(jié)點進行分級,積極節(jié)點參與一致性協(xié)議,消極節(jié)點權(quán)限受限,提高節(jié)點動態(tài)性.在可信節(jié)點層選擇主節(jié)點,減少惡意節(jié)點對系統(tǒng)運行的破壞,減少通信開銷,提高系統(tǒng)效率.

吞吐量一般指單位時間內(nèi)系統(tǒng)處理的事務(wù)數(shù),吞吐量的高低顯示了系統(tǒng)承受負載,處理事務(wù)或者請求交易的能力.在區(qū)塊鏈領(lǐng)域中,一般用每秒交易數(shù)TPS(Transaction PerSecond)來表示,即:

其中,transcations為出塊時間內(nèi)系統(tǒng)處理交易數(shù),Δt為出塊時間.

系統(tǒng)硬件配置為:Inter Core i5-7300 CPU,8GB 內(nèi)存.Linux 系統(tǒng)是Ubuntu16.04,根據(jù)Hyperledger Fabric V1.1 的環(huán)境建立仿真平臺.采用多節(jié)點運行分布式共識過程.

3.1 算法分析

假設(shè)系統(tǒng)的節(jié)點總數(shù)為n,系統(tǒng)發(fā)生視圖切換協(xié)議的概率為p(p是平均發(fā)生視圖切換協(xié)議次數(shù)占總共識次數(shù)的占比),w用于統(tǒng)計通信次數(shù).

PBFT一致性協(xié)議經(jīng)過三階段廣播,通信的時間復(fù)雜度是O(N2),通信次數(shù)為2n(n-1).視圖切換協(xié)議的通信次數(shù)為n(n-1).所以PBFT 在p概率下發(fā)生視圖切換協(xié)議后的總通信次數(shù)可以計算2n(n-1)+pn(n-1),即:

CLBFT 使用信用分級協(xié)議有效地預(yù)防錯誤節(jié)點成為主節(jié)點,并降低錯誤節(jié)點參與共識的概率.CLBFT算法發(fā)生視圖切換的概率為p1,p1＜p.信用分級協(xié)議周期性觸發(fā),系統(tǒng)通過一個周期中各個節(jié)點所得信用積分給節(jié)點分不同等級,然后通過副本節(jié)點廣播給其他節(jié)點,所用通信次數(shù)為:(n-1).所以CLPBFT算法在p1概率下發(fā)生視圖切換協(xié)議總通信次數(shù)為:2n(n-1)+p1n(n-1)+(n-1),所以:

CLBFT 算法應(yīng)用節(jié)點信用分級協(xié)議,惡意節(jié)點參與區(qū)塊共識幾率下降,視圖切換概率大大降低,所以p1＜p.系數(shù)對復(fù)雜度為O (N2)通信開銷影響很大.

3.2 吞吐量測試

圖4所示,縱坐標(biāo)為系統(tǒng)吞吐量,橫坐標(biāo)為系統(tǒng)運行時間.系統(tǒng)設(shè)置100 個節(jié)點,錯誤節(jié)點隨機變化但不超過33 個,滿足總節(jié)點n不少于3f+1,f為惡意節(jié)點,比較PBFT 和CLBFT 的吞吐量隨時間變化.在容錯范圍內(nèi),PBFT 的效率在整個模擬過程中是穩(wěn)定的.隨著系統(tǒng)長期運行,基于信用分級的CLBFT 算法有效地提高系統(tǒng)的吐吞量.由于惡意節(jié)點參與共識概率大大降低,主節(jié)點錯誤率下降,視圖切換協(xié)議的概率隨之下降,系統(tǒng)穩(wěn)定性和效率得到提升.

3.3 通信開銷驗證

在圖5中,縱坐標(biāo)為區(qū)塊平均生成一次的通信次數(shù),橫坐標(biāo)為系統(tǒng)中的節(jié)點數(shù),節(jié)點數(shù)分別取20,40,60,80,100 比較PBFT 和CLBFT 隨著節(jié)點增多通信變化.隨著系統(tǒng)內(nèi)節(jié)點的增加,CLBFT 通信開銷比PBFT越來越小,如圖5所示.

圖4 PBFT 和CLBFT 的TPS 隨時間比較

圖5 PBFT 和CLBFT 隨著節(jié)點增多通信變化

4 結(jié)論

近年來,區(qū)塊鏈在多個領(lǐng)域日益流行.作為區(qū)塊鏈的兩種主要形式,公有鏈和聯(lián)盟鏈在不同應(yīng)用領(lǐng)域研究各自核心共識機制.針對聯(lián)盟應(yīng)用場景,現(xiàn)有實用拜占庭容錯算法(PBFT)存在視圖變更頻繁,系統(tǒng)通信開銷過大,大量節(jié)點加入后系統(tǒng)效率低下等問題.本文提出了一種基于PBFT 改進的CLBFT 算法,設(shè)置節(jié)點基于信用分級的方法,依據(jù)節(jié)點在系統(tǒng)中的表現(xiàn)賦予節(jié)點不同的權(quán)限.降低惡意節(jié)點參與共識的概率,從而有效避免頻繁的視圖變更帶來的通信資源浪費.仿真結(jié)果表明,在系統(tǒng)長期運行下,CLBFT 降低了系統(tǒng)通信開銷,提高了系統(tǒng)效率.