丁庭琛,陳世平
(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)
區(qū)塊鏈技術(shù)最早出現(xiàn)在比特幣中[1],作為已知的分布式賬本,在過去幾年中引起各界廣泛的研究.Blockchain是一種點(diǎn)對(duì)點(diǎn)分布式系統(tǒng),具有高安全性和分散存儲(chǔ),高容錯(cuò)和加密性等特性.為了解決現(xiàn)有中心化機(jī)構(gòu)效率低、成本高、數(shù)字資源壟斷等問題,區(qū)塊鏈整合密碼學(xué)、計(jì)算機(jī)和通信等領(lǐng)域等技術(shù),所用技術(shù)有非對(duì)稱加密、時(shí)間戳、共識(shí)機(jī)制和點(diǎn)對(duì)點(diǎn)通信[2],實(shí)現(xiàn)中心化分布式系統(tǒng).區(qū)塊鏈技術(shù)被認(rèn)為是引起人類社會(huì)顛覆性變革的關(guān)鍵技術(shù)之一[3].
公有鏈和聯(lián)盟鏈?zhǔn)菂^(qū)塊鏈的兩種主要形式[4].比特幣是區(qū)塊鏈最早的應(yīng)用,也是公共區(qū)塊鏈最著名的例子.比特幣作為最早的數(shù)字貨幣,僅使用單一的去中心化技術(shù),存在很大功能局限性.隨著智能合約[5]的發(fā)展,公有鏈有了更加智能的應(yīng)用平臺(tái).例如以太坊(etherum)平臺(tái)就是一個(gè)可編程的區(qū)塊鏈平臺(tái)[6],在系統(tǒng)資產(chǎn)自動(dòng)化管理方面有顯著進(jìn)步.公有區(qū)塊鏈?zhǔn)峭耆ブ行幕到y(tǒng),沒有管理和監(jiān)督,任何人都可以參與公有鏈并且訪問數(shù)據(jù).因此,公有鏈存在一定的弊端,隱私和安全性難以得到保障,可靠性差[7].為了更好地保護(hù)用戶的隱私和監(jiān)督數(shù)據(jù),提出了聯(lián)盟鏈概念,其中,Hyperledger 是經(jīng)典的聯(lián)盟鏈系統(tǒng)[8].聯(lián)盟鏈在企業(yè)級(jí)組織內(nèi)部廣泛發(fā)展[9].在聯(lián)盟區(qū)塊鏈中,只有特定允許的節(jié)點(diǎn)才能訪問網(wǎng)絡(luò).因此,聯(lián)盟區(qū)塊鏈可以很好地支持企業(yè)級(jí)應(yīng)用程序,并在公共和政府服務(wù)中被廣泛采用.
共識(shí)機(jī)制是區(qū)塊鏈的核心,區(qū)塊鏈中有PoW 和PoS算法[10],Raft 算法[11],PBFT 算法[12]等共識(shí)機(jī)制.一般情況下存在拜占庭問題都由PBFT 算法解決.拜占庭式故障模型[13]假設(shè)副本可以通過任意行動(dòng)而被惡意攻擊[14],該模型適用于區(qū)塊鏈系統(tǒng).針對(duì)模型中的共識(shí)問題,許多理論成果相繼出現(xiàn),不過較早的協(xié)議都是從理論上解決問題,無法在實(shí)際場(chǎng)景中應(yīng)用.PBFT 是第一個(gè)為實(shí)際應(yīng)用開發(fā)的協(xié)議,解決了分布式文件系統(tǒng)可容忍拜占庭式故障問題.不過PBFT 無法在實(shí)際場(chǎng)景中廣泛應(yīng)用,它存在擴(kuò)展性差,通信開銷大,效率低等問題[15].
針對(duì)聯(lián)盟鏈的應(yīng)用場(chǎng)景,本文提出了一種基于PBFT改進(jìn)的一致性算法,稱為CLBFT (Credit-Layered Byzantine Fault Tolerance).受PoW 共識(shí)機(jī)制的啟發(fā),基于信用獎(jiǎng)勵(lì)和懲罰節(jié)點(diǎn),基于節(jié)點(diǎn)信用值的基礎(chǔ)上給節(jié)點(diǎn)分級(jí),旨在長(zhǎng)期維持系統(tǒng)良好運(yùn)行.通過這種方案,可以大大提高參與者的積極性,減少惡意節(jié)點(diǎn)參與帶來的影響,提高系統(tǒng)的安全性和效率.
Castro 和Liskov 在1999年提出的實(shí)用的拜占庭容錯(cuò)協(xié)議(PBFT)被認(rèn)為是解決拜占庭將軍問題的最經(jīng)典協(xié)議.PBFT 是為解決分布式系統(tǒng)中存在拜占庭故障節(jié)點(diǎn)從而達(dá)成信息一致性的問題.為保障系統(tǒng)正常運(yùn)轉(zhuǎn),當(dāng)系統(tǒng)中無效或者惡意點(diǎn)數(shù)為f時(shí),要求總節(jié)點(diǎn)n不小于3f+1.PBFT 算法主要包括一致性協(xié)議,視圖切換協(xié)議和檢查點(diǎn)協(xié)議3 個(gè)部分.
一致性協(xié)議是PBFT 算法的核心,主要作用是保證區(qū)塊鏈系統(tǒng)中信息的正確和相同.在PBFT 算法中存在客戶端(client),主節(jié)點(diǎn)(primary),從節(jié)點(diǎn)(replica)3 種角色.客戶端c主要作用是向主節(jié)點(diǎn)發(fā)送請(qǐng)求<REQUEST,o,t,c>,o為請(qǐng)求的具體操作,t為時(shí)間戳.主節(jié)點(diǎn)通過視圖編號(hào)以及節(jié)點(diǎn)數(shù)集合來確定,主節(jié)點(diǎn)公式如下:p=vmod|R|,其中v是視圖編號(hào),|R|是節(jié)點(diǎn)個(gè)數(shù),p是主節(jié)點(diǎn)編號(hào).主節(jié)點(diǎn)和從節(jié)點(diǎn)作為副本節(jié)點(diǎn)參與算法的主要3 個(gè)通信階段:預(yù)準(zhǔn)備階段(pre-prepare)、準(zhǔn)備階段(prepare)、確認(rèn)階段(commit).
1)預(yù)準(zhǔn)備階段:主節(jié)點(diǎn)接受到客戶端c 的請(qǐng)求,丟棄錯(cuò)誤請(qǐng)求,對(duì)正確的請(qǐng)求進(jìn)行排序,并分配編號(hào)n.然后主節(jié)點(diǎn)向系統(tǒng)中的其他從節(jié)點(diǎn)廣播一條<<PRE-PERPARE,v,n,d>,m>消息.
2)準(zhǔn)備階段:節(jié)點(diǎn)對(duì)收到的預(yù)準(zhǔn)備消息進(jìn)行判斷,如果同意預(yù)準(zhǔn)備消息,則進(jìn)入準(zhǔn)備階段,然后向其他節(jié)點(diǎn)(包括主節(jié)點(diǎn))廣播<PREPARE,v,n,d,i>消息.
3)確認(rèn)階段:當(dāng)節(jié)點(diǎn)收到2f+1 個(gè)通過驗(yàn)證的消息時(shí)準(zhǔn)備階段結(jié)束進(jìn)入確認(rèn)階段,節(jié)點(diǎn)向包括主節(jié)點(diǎn)在內(nèi)的其他節(jié)點(diǎn)發(fā)送<COMMIT,v,n,D(m),i>消息.
圖1是一次一致性協(xié)議過程.“Client”是客戶端,“Primary”是主節(jié)點(diǎn),“Replical1”、“Replical2”、“Replical3”是3 個(gè)從節(jié)點(diǎn).即使“Replical3”是故障節(jié)點(diǎn),系統(tǒng)任可以通過一致性協(xié)議.
圖1 一致性協(xié)議交互過程
視圖切換協(xié)議是針對(duì)主節(jié)點(diǎn)發(fā)生故障時(shí),維持系統(tǒng)正確運(yùn)行的協(xié)議.1 個(gè)視圖中有1 個(gè)主節(jié)點(diǎn),當(dāng)主節(jié)點(diǎn)發(fā)生故障時(shí),視圖需要改變,視圖編號(hào)加1 即v+1,更換新的主節(jié)點(diǎn).主節(jié)點(diǎn)發(fā)生故障時(shí),從節(jié)點(diǎn)觸發(fā)視圖切換協(xié)議,系統(tǒng)設(shè)置兩個(gè)觸發(fā)條件:從最近完成的一個(gè)區(qū)塊的時(shí)間戳T開始,在限定時(shí)間T1內(nèi)沒有收到新主節(jié)點(diǎn)的Pre-prepare 廣播,或是在限定時(shí)間T2內(nèi)沒有生成新的區(qū)塊,其中T1<T2.上述兩個(gè)觸發(fā)條件滿足其中一個(gè)就會(huì)觸發(fā)視圖切換協(xié)議.為了保證系統(tǒng)的正確性和一致性,視圖切換也要進(jìn)行節(jié)點(diǎn)間的交互通信.View-Change 的工作過程如下:
1)視圖切換協(xié)議開啟后,從節(jié)點(diǎn)進(jìn)入視圖v+1,并向所有節(jié)點(diǎn)廣播View-Change 消息.
2)副本節(jié)點(diǎn)在收到2f+1 條(包括自身)View-Change消息后,向視圖v+1 中的主節(jié)點(diǎn)發(fā)送View-Change-Ack消息,新主節(jié)點(diǎn)收到View-Change-Ack 消息后進(jìn)入New-View 階段.
3)新的主節(jié)點(diǎn)選擇檢查點(diǎn)作為“New-View”請(qǐng)求的起始狀態(tài),然后根據(jù)本地塊鏈接數(shù)據(jù)執(zhí)行一致性協(xié)議.
在共識(shí)過程中,節(jié)點(diǎn)會(huì)生成大量的日志,系統(tǒng)長(zhǎng)期運(yùn)行下就會(huì)存儲(chǔ)大量信息.檢查點(diǎn)協(xié)議的作用就是減小節(jié)點(diǎn)信息存儲(chǔ)規(guī)模,釋放經(jīng)過共識(shí)認(rèn)證的日志消息,降低系統(tǒng)內(nèi)存開銷.某些節(jié)點(diǎn)由于自身故障或網(wǎng)絡(luò)問題沒有和其他節(jié)點(diǎn)同步,影響系統(tǒng)的運(yùn)行,因此需要Checkpoint 協(xié)議周期性工作,它在確認(rèn)節(jié)點(diǎn)的一致性后清除經(jīng)過驗(yàn)證的證書.
雖然PBFT 算法對(duì)區(qū)塊鏈的共識(shí)性能改善很大,但是任然存在通信開銷大,擴(kuò)展性差,效率低等問題.首先PBFT 算法是一種部分同步模式共識(shí)算法,為了保證非故障節(jié)點(diǎn)以相同順序執(zhí)行客戶端的請(qǐng)求,需要三階廣播通信實(shí)現(xiàn)異步模式下的安全性,造成大量的通信開銷.其次,PBFT 算法需要點(diǎn)對(duì)點(diǎn)通信進(jìn)行拜占庭容錯(cuò)共識(shí).在N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中,PBFT 通信的時(shí)間復(fù)雜度是O (N2),經(jīng)過三階段共識(shí)之后消息傳輸次數(shù)為2N(N-1).由于通信的復(fù)雜性,當(dāng)節(jié)點(diǎn)數(shù)超過一定量時(shí),PBFT 協(xié)議的性能會(huì)急劇下降.最后是PBFT 算法主節(jié)點(diǎn)選取隨意,選到惡意節(jié)點(diǎn)的概率偏高,影響系統(tǒng)效率.
PBFT 算法中選取主節(jié)點(diǎn)隨意.它是根據(jù)編號(hào)的順序依次得到主節(jié)點(diǎn),并且選出的主節(jié)點(diǎn)沒有任何檢驗(yàn),無法保證系統(tǒng)的安全性.用這種方法選舉出來的主節(jié)點(diǎn)存在惡意節(jié)點(diǎn)的可能性很大,從識(shí)破惡意節(jié)點(diǎn)到通過視圖切換協(xié)議更換主節(jié)點(diǎn),造成大量網(wǎng)絡(luò)通信開銷,降低了系統(tǒng)效率.本文采用信用評(píng)估和節(jié)點(diǎn)分級(jí)協(xié)議對(duì)PBFT 算法加以改進(jìn),提出了CLBFT 共識(shí)機(jī)制.CLBFT主要改進(jìn)的地方有:
1)制定信用積分規(guī)則,評(píng)估節(jié)點(diǎn)信用狀態(tài).
2)依據(jù)信用積分對(duì)節(jié)點(diǎn)進(jìn)行分級(jí),選擇積極節(jié)點(diǎn)參與一致性協(xié)議,提高節(jié)點(diǎn)動(dòng)態(tài)性.
3)在可信節(jié)點(diǎn)層選擇主節(jié)點(diǎn),大大減少惡意節(jié)點(diǎn)對(duì)系統(tǒng)運(yùn)行的破壞,減少通信開銷,提高系統(tǒng)效率.
定義Ci代表節(jié)點(diǎn)的信用積分,節(jié)點(diǎn)的信用級(jí)別劃分為4 個(gè)級(jí)別:A、B、C、D.剛加入的節(jié)點(diǎn)的信用值為Cnormal,根據(jù)節(jié)點(diǎn)在系統(tǒng)中的行為增加信用積分或減少信用積分.節(jié)點(diǎn)在系統(tǒng)中參與一次有效區(qū)塊的生成則節(jié)點(diǎn)信用積分加1;節(jié)點(diǎn)在系統(tǒng)中未生成有效區(qū)塊則信用積分減5.信用值在Cnormal≤Ci<Cgood區(qū)間的節(jié)點(diǎn)信用級(jí)別為B,初入節(jié)點(diǎn)也在此列;當(dāng)節(jié)點(diǎn)的信用值大于Cgood時(shí),即Ci>Cgood,節(jié)點(diǎn)信用級(jí)別為A;信用值為Cbad≤Ci<Cnormal時(shí),節(jié)點(diǎn)信用級(jí)別為C;當(dāng)節(jié)點(diǎn)的信用值低于Cbad時(shí),即Ci<Cbad節(jié)點(diǎn)的信用級(jí)別為D.節(jié)點(diǎn)信用分級(jí)轉(zhuǎn)換如圖2所示.
圖2 節(jié)點(diǎn)信用狀態(tài)分級(jí)圖
依據(jù)信用分級(jí)協(xié)議將節(jié)點(diǎn)劃分為四類,每類節(jié)點(diǎn)有不同的權(quán)限.A 類節(jié)點(diǎn)信用級(jí)別最高,優(yōu)先擔(dān)任主節(jié)點(diǎn).其次是B 類節(jié)點(diǎn),當(dāng)A 類節(jié)點(diǎn)被選擇完畢或不存在A 類節(jié)點(diǎn),可以從B 類節(jié)點(diǎn)中選擇主節(jié)點(diǎn).C 類節(jié)點(diǎn)由于信用級(jí)別偏低不適合擔(dān)任主節(jié)點(diǎn),但任然可以作為從節(jié)點(diǎn)參與區(qū)塊共識(shí).D 類節(jié)點(diǎn)信用級(jí)別太低,不能參與共識(shí).權(quán)限分類不僅能夠大大提高節(jié)點(diǎn)的積極性,而且有效預(yù)防惡意節(jié)點(diǎn)成為主節(jié)點(diǎn).有效地減少惡意節(jié)點(diǎn)參與共識(shí)帶來的通信損失和減少View-Change 變更次數(shù),提高系統(tǒng)效率,如表1區(qū)分節(jié)點(diǎn)權(quán)限.
表1 節(jié)點(diǎn)權(quán)限分類
CLBFT 算法的過程如圖3所示.首先,根據(jù)信用分級(jí)協(xié)議對(duì)節(jié)點(diǎn)進(jìn)行分級(jí).信用分級(jí)協(xié)議的周期為zCT,其中CT是檢查點(diǎn)協(xié)議的周期,z為系數(shù).依據(jù)系統(tǒng)中節(jié)點(diǎn)數(shù)量調(diào)整合適的系數(shù)z按照周期間隔zCT更新節(jié)點(diǎn)信用積分,節(jié)點(diǎn)依據(jù)信用積分分成不同級(jí)別.然后,不同級(jí)別的節(jié)點(diǎn)有不同的權(quán)限,有相應(yīng)權(quán)限的節(jié)點(diǎn)參與選出主節(jié)點(diǎn).節(jié)點(diǎn)根據(jù)自身的行為獲得相應(yīng)的信用積分,當(dāng)節(jié)點(diǎn)積分滿足A 類信用級(jí)別時(shí),進(jìn)入集合A.集合A中的節(jié)點(diǎn)獲得視圖編號(hào),參與主節(jié)點(diǎn)選擇,保證主節(jié)點(diǎn)選取的最優(yōu)性.接下來,主節(jié)點(diǎn)選出后參與一致性協(xié)議,并監(jiān)督一致性協(xié)議以判斷主節(jié)點(diǎn)是否觸發(fā)View-Change 中設(shè)置的兩個(gè)超時(shí)觸發(fā)條件.若超時(shí),觸發(fā)視圖切換協(xié)議,更換主節(jié)點(diǎn),視圖v+1,否則生成新區(qū)塊寫入?yún)^(qū)塊鏈.最后執(zhí)行改進(jìn)的檢查點(diǎn)協(xié)議(Checkpoint)釋放經(jīng)過共識(shí)認(rèn)證的日志消息,降低系統(tǒng)內(nèi)存開銷.
圖3 CLBFT 流程圖
PBFT 算法的主節(jié)點(diǎn)選取較為隨意,是根據(jù)編號(hào)的順序依次得到主節(jié)點(diǎn).用這種方法選舉出來的主節(jié)點(diǎn)存在惡意節(jié)點(diǎn)的可能性很大,視圖切換協(xié)議較多會(huì)造成大量網(wǎng)絡(luò)通信開銷,降低了系統(tǒng)效率.本文提出的CLBFT 算法是對(duì)PBFT 算法的改進(jìn).制定信用積分規(guī)則,評(píng)估節(jié)點(diǎn)信用狀態(tài).依據(jù)信用積分對(duì)節(jié)點(diǎn)進(jìn)行分級(jí),積極節(jié)點(diǎn)參與一致性協(xié)議,消極節(jié)點(diǎn)權(quán)限受限,提高節(jié)點(diǎn)動(dòng)態(tài)性.在可信節(jié)點(diǎn)層選擇主節(jié)點(diǎn),減少惡意節(jié)點(diǎn)對(duì)系統(tǒng)運(yùn)行的破壞,減少通信開銷,提高系統(tǒng)效率.
吞吐量一般指單位時(shí)間內(nèi)系統(tǒng)處理的事務(wù)數(shù),吞吐量的高低顯示了系統(tǒng)承受負(fù)載,處理事務(wù)或者請(qǐng)求交易的能力.在區(qū)塊鏈領(lǐng)域中,一般用每秒交易數(shù)TPS(Transaction PerSecond)來表示,即:
其中,transcations為出塊時(shí)間內(nèi)系統(tǒng)處理交易數(shù),Δt為出塊時(shí)間.
系統(tǒng)硬件配置為:Inter Core i5-7300 CPU,8GB 內(nèi)存.Linux 系統(tǒng)是Ubuntu16.04,根據(jù)Hyperledger Fabric V1.1 的環(huán)境建立仿真平臺(tái).采用多節(jié)點(diǎn)運(yùn)行分布式共識(shí)過程.
假設(shè)系統(tǒng)的節(jié)點(diǎn)總數(shù)為n,系統(tǒng)發(fā)生視圖切換協(xié)議的概率為p(p是平均發(fā)生視圖切換協(xié)議次數(shù)占總共識(shí)次數(shù)的占比),w用于統(tǒng)計(jì)通信次數(shù).
PBFT一致性協(xié)議經(jīng)過三階段廣播,通信的時(shí)間復(fù)雜度是O(N2),通信次數(shù)為2n(n-1).視圖切換協(xié)議的通信次數(shù)為n(n-1).所以PBFT 在p概率下發(fā)生視圖切換協(xié)議后的總通信次數(shù)可以計(jì)算2n(n-1)+pn(n-1),即:
CLBFT 使用信用分級(jí)協(xié)議有效地預(yù)防錯(cuò)誤節(jié)點(diǎn)成為主節(jié)點(diǎn),并降低錯(cuò)誤節(jié)點(diǎn)參與共識(shí)的概率.CLBFT算法發(fā)生視圖切換的概率為p1,p1<p.信用分級(jí)協(xié)議周期性觸發(fā),系統(tǒng)通過一個(gè)周期中各個(gè)節(jié)點(diǎn)所得信用積分給節(jié)點(diǎn)分不同等級(jí),然后通過副本節(jié)點(diǎn)廣播給其他節(jié)點(diǎn),所用通信次數(shù)為:(n-1).所以CLPBFT算法在p1概率下發(fā)生視圖切換協(xié)議總通信次數(shù)為:2n(n-1)+p1n(n-1)+(n-1),所以:
CLBFT 算法應(yīng)用節(jié)點(diǎn)信用分級(jí)協(xié)議,惡意節(jié)點(diǎn)參與區(qū)塊共識(shí)幾率下降,視圖切換概率大大降低,所以p1<p.系數(shù)對(duì)復(fù)雜度為O (N2)通信開銷影響很大.
圖4所示,縱坐標(biāo)為系統(tǒng)吞吐量,橫坐標(biāo)為系統(tǒng)運(yùn)行時(shí)間.系統(tǒng)設(shè)置100 個(gè)節(jié)點(diǎn),錯(cuò)誤節(jié)點(diǎn)隨機(jī)變化但不超過33 個(gè),滿足總節(jié)點(diǎn)n不少于3f+1,f為惡意節(jié)點(diǎn),比較PBFT 和CLBFT 的吞吐量隨時(shí)間變化.在容錯(cuò)范圍內(nèi),PBFT 的效率在整個(gè)模擬過程中是穩(wěn)定的.隨著系統(tǒng)長(zhǎng)期運(yùn)行,基于信用分級(jí)的CLBFT 算法有效地提高系統(tǒng)的吐吞量.由于惡意節(jié)點(diǎn)參與共識(shí)概率大大降低,主節(jié)點(diǎn)錯(cuò)誤率下降,視圖切換協(xié)議的概率隨之下降,系統(tǒng)穩(wěn)定性和效率得到提升.
在圖5中,縱坐標(biāo)為區(qū)塊平均生成一次的通信次數(shù),橫坐標(biāo)為系統(tǒng)中的節(jié)點(diǎn)數(shù),節(jié)點(diǎn)數(shù)分別取20,40,60,80,100 比較PBFT 和CLBFT 隨著節(jié)點(diǎn)增多通信變化.隨著系統(tǒng)內(nèi)節(jié)點(diǎn)的增加,CLBFT 通信開銷比PBFT越來越小,如圖5所示.
圖4 PBFT 和CLBFT 的TPS 隨時(shí)間比較
圖5 PBFT 和CLBFT 隨著節(jié)點(diǎn)增多通信變化
近年來,區(qū)塊鏈在多個(gè)領(lǐng)域日益流行.作為區(qū)塊鏈的兩種主要形式,公有鏈和聯(lián)盟鏈在不同應(yīng)用領(lǐng)域研究各自核心共識(shí)機(jī)制.針對(duì)聯(lián)盟應(yīng)用場(chǎng)景,現(xiàn)有實(shí)用拜占庭容錯(cuò)算法(PBFT)存在視圖變更頻繁,系統(tǒng)通信開銷過大,大量節(jié)點(diǎn)加入后系統(tǒng)效率低下等問題.本文提出了一種基于PBFT 改進(jìn)的CLBFT 算法,設(shè)置節(jié)點(diǎn)基于信用分級(jí)的方法,依據(jù)節(jié)點(diǎn)在系統(tǒng)中的表現(xiàn)賦予節(jié)點(diǎn)不同的權(quán)限.降低惡意節(jié)點(diǎn)參與共識(shí)的概率,從而有效避免頻繁的視圖變更帶來的通信資源浪費(fèi).仿真結(jié)果表明,在系統(tǒng)長(zhǎng)期運(yùn)行下,CLBFT 降低了系統(tǒng)通信開銷,提高了系統(tǒng)效率.