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

丁庭琛,陳世平

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

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

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

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

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

1 PBFT

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

1.1 一致性協議

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

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

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

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

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

圖1 一致性協議交互過程

1.2 視圖切換協議

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

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

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

3)新的主節點選擇檢查點作為“New-View”請求的起始狀態,然后根據本地塊鏈接數據執行一致性協議.

1.3 檢查點協議

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

1.4 PBFT 存在的問題

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

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

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

1)制定信用積分規則,評估節點信用狀態.

2)依據信用積分對節點進行分級,選擇積極節點參與一致性協議,提高節點動態性.

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

2.1 信用分級協議

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

圖2 節點信用狀態分級圖

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

表1 節點權限分類

2.2 CLBFT 共識過程

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

圖3 CLBFT 流程圖

3 性能分析與實驗

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

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

其中,transcations為出塊時間內系統處理交易數,Δt為出塊時間.

系統硬件配置為:Inter Core i5-7300 CPU,8GB 內存.Linux 系統是Ubuntu16.04,根據Hyperledger Fabric V1.1 的環境建立仿真平臺.采用多節點運行分布式共識過程.

3.1 算法分析

假設系統的節點總數為n,系統發生視圖切換協議的概率為p(p是平均發生視圖切換協議次數占總共識次數的占比),w用于統計通信次數.

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

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

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

3.2 吞吐量測試

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

3.3 通信開銷驗證

在圖5中,縱坐標為區塊平均生成一次的通信次數,橫坐標為系統中的節點數,節點數分別取20,40,60,80,100 比較PBFT 和CLBFT 隨著節點增多通信變化.隨著系統內節點的增加,CLBFT 通信開銷比PBFT越來越小,如圖5所示.

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

圖5 PBFT 和CLBFT 隨著節點增多通信變化

4 結論

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