基于信任委托的區(qū)塊鏈分層共識優(yōu)化

段 靚,呂 鑫,b,劉 凡,b

(河海大學 a.計算機與信息學院; b.海岸災(zāi)害及防護教育部重點實驗室,南京 210098)

0 概述

區(qū)塊鏈作為一種去中心化的分布式系統(tǒng),鏈上的數(shù)據(jù)需要在全網(wǎng)節(jié)點間進行一致性分發(fā)和冗余存儲,以此保證數(shù)據(jù)無法被篡改或偽造[1]。這一特性是區(qū)塊鏈技術(shù)的優(yōu)勢,但也是區(qū)塊鏈應(yīng)用的瓶頸。區(qū)塊鏈系統(tǒng)需要消耗大量的計算、存儲和網(wǎng)絡(luò)資源實現(xiàn)全網(wǎng)節(jié)點間的數(shù)據(jù)和業(yè)務(wù)協(xié)同,這使得區(qū)塊鏈系統(tǒng)在業(yè)務(wù)處理上的性能遠低于傳統(tǒng)中心化的系統(tǒng)[2],而且網(wǎng)絡(luò)規(guī)模越大,這種差異就越明顯。

公有鏈的共識算法主要是從PoW(Proof of Work)和PoS(Proof of Stake)這2種算法上派生演化的,而聯(lián)盟鏈共識算法則大多基于經(jīng)典分布式一致性算法CFT(Crash Fault Tolerance)和BFT(Byzantine Fault Tolerance)[3-4]。無論是公有鏈還是聯(lián)盟鏈,采用分片技術(shù)和并行技術(shù)都可以解決區(qū)塊鏈平臺擴展性問題。分片技術(shù)包括計算分片、通信分片和存儲分片,例如公有鏈采用的多鏈、跨鏈等混合共識機制[5],聯(lián)盟鏈采用的分組、分層共識機制等[6]。

本文提出一種基于信任委托的分層共識優(yōu)化機制。該機制將共識網(wǎng)絡(luò)劃分成不同的子區(qū)域,子區(qū)域內(nèi)的節(jié)點根據(jù)可信程度選舉出代理人委托其參與全局共識。

1 共識算法

本文重點研究聯(lián)盟鏈的共識算法,這是因為公有鏈目前最廣泛的應(yīng)用場景還是開放環(huán)境中的加密貨幣,而在政府和企業(yè)級應(yīng)用場景中,節(jié)點都是經(jīng)過身份認證的,因此多采用聯(lián)盟鏈架構(gòu)[7]。

聯(lián)盟鏈中最通用的共識協(xié)議就是實用拜占庭容錯(Practical Byzantine Fault Tolerance,PBFT),其本質(zhì)是一種基于投票的共識機制[8]。當節(jié)點數(shù)增大時,共識交互消息會成幾何倍數(shù)增長。如果節(jié)點分布在互聯(lián)網(wǎng)上,網(wǎng)絡(luò)延時會導致共識協(xié)議時間迅速增加,嚴重影響共識服務(wù)的吞吐量。為解決這一問題,業(yè)界主要從優(yōu)化共識協(xié)議和改進共識架構(gòu)兩方面開展研究[9]。

1)優(yōu)化共識協(xié)議。文獻[10]提供一種基于聚合簽名的優(yōu)化方法dBFT,將m條消息簽名聚合為1條,空間復雜度降為原先的1/m,但計算復雜度提升為O(3m)。文獻[11]提出一種基于環(huán)簽名的PBFT區(qū)塊鏈共識算法改進方案,節(jié)點在環(huán)簽名時自行組成環(huán),使PBFT算法能夠支持節(jié)點的動態(tài)加入與退出,從而提高超時導致的共識效率低下問題。文獻[12]提出一種基于投票機制的優(yōu)化算法VPBFT。通過引入投票證明將共識節(jié)點分成投票人、管理人、候選人和普通用戶,候選人由投票人選舉產(chǎn)生。生產(chǎn)節(jié)點根據(jù)任期內(nèi)是否生成有效的數(shù)據(jù)塊來獲得相應(yīng)的分數(shù),分數(shù)高的節(jié)點將允許進入下一輪投票。該方法消耗的帶寬是PBFT的2/3。文獻[13]提出一種基于Gossip協(xié)議的PBFT算法。該算法將PBFT的消息廣播改為利用Gossip協(xié)議,節(jié)點自行選擇鄰近節(jié)點進行信息交換。通過主動探測故障節(jié)點,使共識網(wǎng)絡(luò)可以容錯一半的節(jié)點,達到XFT容錯能力。文獻[14]提出一種不依賴計算能力的共識算法C-BFT。在主從多鏈模型中,使用時間閾值來約束各鏈之間的共識協(xié)作,動態(tài)調(diào)整節(jié)點間的通信延遲,確保主鏈節(jié)點在時間閾值內(nèi)寫入數(shù)據(jù)。另有一些算法采用基于DAG的分布式賬本改進性能,通過節(jié)點中非同步的平行共識來加快數(shù)據(jù)傳輸。文獻[15]提出一種基于Lachesis協(xié)議的PBFT算法ONLAY,使用分層和層次化的DAG圖對數(shù)據(jù)進行異步排序以保障共識完成的時間。基于該算法的Fantom平臺能達到300K TPS的吞吐量。

2)改進共識架構(gòu)。無論是采用橫向分片還是縱向分層擴展,其本質(zhì)上都是將節(jié)點劃分為各自獨立的空間。文獻[16]針對聯(lián)盟鏈提出一種多中心動態(tài)共識機制,設(shè)計了一種主從多鏈結(jié)構(gòu),全局區(qū)塊鏈鏈接多個主體區(qū)塊鏈。每個主體(即中心)包含若干區(qū)塊鏈節(jié)點,維護本主體的交易區(qū)塊鏈(即從鏈),所有主體再共同維護全局區(qū)塊鏈(即主鏈)。當構(gòu)建全局區(qū)塊時,每一輪都要由一個全局主節(jié)點從全網(wǎng)選出下一輪的全局節(jié)點,采用并行方式構(gòu)建Merkle樹。該方法采用驗證群組來解決數(shù)據(jù)全局一致性的問題。文獻[17]提出一種基于“組”的層次結(jié)構(gòu),將所有節(jié)點劃分為若干組,每組有一個主節(jié)點。層次共識分為局部和全局2個階段。首先,客戶節(jié)點將請求廣播給所有節(jié)點,每一個分組都要在組內(nèi)進行一次請求的局部共識;然后,各個分組的主節(jié)點再進行一次全局共識,至此,整個請求才算完成。文獻[18]提出一種可伸縮動態(tài)多代理層次化的PBFT算法SDMA-PBFA,可以將共識過程中的通信消息復雜度從O(n2)降至O(n·k·logkn)[18]。其基本思想是將節(jié)點劃分為若干組,每個組選出一個節(jié)點作為代理人。客戶節(jié)點請求先分發(fā)給所有代理人,代理人再在分組內(nèi)部完成共識過程,最后由各個代理人通知客戶節(jié)點請求完成。文獻[19]同樣采用節(jié)點分組的方式,每個分組有一個領(lǐng)導人,PRE-PREPARE、PREPARE和COMMIT 3個階段都需要本組節(jié)點和其他組領(lǐng)導人節(jié)點參與。文獻[20]采用樹形拓撲構(gòu)建共識網(wǎng)絡(luò),引入信譽模型降低錯誤節(jié)點在共識過程中的影響,但共識消息仍要通過子網(wǎng)的父節(jié)點分發(fā)到子網(wǎng)內(nèi)進行三階段共識。

盡管上述研究通過采用分片技術(shù)和代理人節(jié)點能夠降低共識消息復雜度,提升共識性能,但卻沒有很好地解決以下問題:即如何對成員可靠性進行檢測和評估,確保選出可信的委員會成員,以保障共識網(wǎng)絡(luò)拓撲的穩(wěn)定;如果委員會成員是高可信的,分片共識協(xié)議能否進一步簡化,以提升共識網(wǎng)絡(luò)的吞吐量,如果委員會成員行為異常,共識協(xié)議能否采取主動干預(yù)機制,以減輕共識請求時間的波動。

針對上述問題,本文提出一種基于信任委托的分層共識優(yōu)化機制,在保證整體共識過程滿足PBFT協(xié)議有效性、一致性和完整性要求的同時,降低每個階段參與共識的節(jié)點數(shù)量,提升共識網(wǎng)絡(luò)的吞吐量。

2 研究思路

本文的設(shè)計思想包含信任、層次化和委托3個核心概念。下文分別定義這3個概念的內(nèi)涵。

1)信任。在社會治理領(lǐng)域,聯(lián)盟鏈是更適合政府和企業(yè)構(gòu)建行業(yè)應(yīng)用的區(qū)塊鏈方案。這是因為加入聯(lián)盟鏈的節(jié)點需要經(jīng)過審核和授權(quán),節(jié)點的行為狀態(tài)相對穩(wěn)定,可以建立信任關(guān)系[21]。這里的“信任關(guān)系”不是主觀設(shè)定的關(guān)系,而是根據(jù)節(jié)點在生成區(qū)塊過程中的行為進行客觀地評價。運行速度快、能和大多數(shù)節(jié)點形成一致共識的節(jié)點,其信任度就高;經(jīng)常響應(yīng)超時、共識消息發(fā)生錯誤的節(jié)點,其信任度就低。將節(jié)點依據(jù)信任度劃分成不同類型的節(jié)點后,就可以為不同節(jié)點分配共識過程中不同的任務(wù)。

2)層次化。在各行各業(yè)的分布式業(yè)務(wù)系統(tǒng)中,業(yè)務(wù)節(jié)點的交互和數(shù)據(jù)都存在局部現(xiàn)象。這是因為社會網(wǎng)絡(luò)作為一種復雜網(wǎng)絡(luò),宏觀上有“小世界”,中觀上有“群聚特性”,微觀上有“中心性”“聚類性”等特征。聯(lián)盟鏈在實際場景中,節(jié)點也同樣具有小世界現(xiàn)象。例如大型機構(gòu)設(shè)立分支機構(gòu),省局下設(shè)地市和區(qū)縣分局,中心節(jié)點和邊緣節(jié)點協(xié)同處理業(yè)務(wù)請求。基于此思想,可以將區(qū)塊鏈平臺在同一平面內(nèi)的節(jié)點進行層次化,劃分成若干個相互獨立的子區(qū)域。節(jié)點的信任度只要根據(jù)節(jié)點與子區(qū)域內(nèi)節(jié)點交互的行為進行評價,即只需得到子區(qū)域內(nèi)的節(jié)點認可。

3)委托。委托是在完成節(jié)點層次化和建立的節(jié)點信任度之后進行的。每個子區(qū)域有信任度的節(jié)點能被其他節(jié)點委托參與共識,經(jīng)常故障或狀態(tài)異常的不可信節(jié)點不得參與共識。信任度高的節(jié)點可以作為子區(qū)域的代表,被委托參與各個子區(qū)域之間的協(xié)調(diào)共識。

本文的層次化不同于基于分片技術(shù)的共識算法。分片通常是指針對鏈上數(shù)據(jù)進行劃分,構(gòu)建不同的子鏈,而本文是針對節(jié)點的交互范圍對節(jié)點進行劃分,降低共識過程的網(wǎng)絡(luò)復雜度。此外,基于信任度的劃分,使得共識算法可以充分考慮節(jié)點的時延、抖動、吞吐量、失敗率等性能指標,從而確保共識服務(wù)質(zhì)量。

3 系統(tǒng)整體流程

本文提出的共識機制是一個基于“監(jiān)控-評價-反饋”的流程,包含狀態(tài)監(jiān)控、信任度評價、委托代理人和分層共識4個部分,如圖1所示。其中,節(jié)點狀態(tài)監(jiān)控是基礎(chǔ),信任度評價是核心,委托代理人是手段,分層共識是目標,4個階段相互關(guān)聯(lián),循環(huán)往復。

圖1 監(jiān)控-評價-反饋系統(tǒng)流程Fig.1 Procedure of monitor-evaluate-feedback system

狀態(tài)監(jiān)控包括節(jié)點狀態(tài)監(jiān)控和共識過程監(jiān)控。前者主要檢測節(jié)點的網(wǎng)絡(luò)和服務(wù)狀態(tài),例如服務(wù)是否在線、節(jié)點是否宕機等;后者則監(jiān)控節(jié)點共識過程中的行為,例如完成消息的時間、共識的結(jié)果等。

信任度評價根據(jù)狀態(tài)監(jiān)控的數(shù)據(jù)計算節(jié)點信任度的各個影響因子,進而對當次共識過程中節(jié)點的表現(xiàn)進行評價。信任度更新則是結(jié)合節(jié)點過往信任度,合理穩(wěn)健地更新節(jié)點的信任度,保障節(jié)點信任狀態(tài)的穩(wěn)定。

委托代理人則依據(jù)各個節(jié)點的信任度,選舉出不同級別的代理人參與分層共識。在分層共識的過程中,共識算法還會依據(jù)節(jié)點的信任狀態(tài)動態(tài)選擇可靠的共識節(jié)點,識別故障或惡意節(jié)點,并提前干預(yù),從而改善共識算法的性能,提升系統(tǒng)共識效率。

4 信任度評價

4.1 信任度定義

對共識節(jié)點可信度的評價主要基于節(jié)點的3種行為,即正常、故障和惡意行為。節(jié)點的不同行為會導致信任度發(fā)生相應(yīng)變化。在上一輪評估信任度的基礎(chǔ)上,正常行為會增加信任度,故障行為會減少信任度,一旦發(fā)現(xiàn)惡意行為,信任度直接歸0。

根據(jù)信任度的大小進一步將節(jié)點分成4種類型。使用3個閾值Ctrust、Cnormal和Cabnormal分別表示可信節(jié)點、普通節(jié)點和故障節(jié)點的信任度下限,也就是各類型節(jié)點的信任度閾值,其值滿足Ctrust>Cnormal>Cabnormal。Ctrust默認值為0.8,Cnormal默認值為0.5,Cabnormal默認值為0.2。系統(tǒng)初始化時節(jié)點狀態(tài)均為普通節(jié)點,如果某節(jié)點長期穩(wěn)定運行,性能優(yōu)越,則隨著其可信度增高,節(jié)點將會升級為可信節(jié)點;如果某節(jié)點運行不穩(wěn)定,可信度會逐步降低,節(jié)點降級為故障節(jié)點;如果節(jié)點故障長時間得不到修復,可信度降至Cabnormal之下,或者被檢測存在惡意行為,則將被立刻標記為惡意節(jié)點,并拒絕其參與共識過程。

4.2 信任度因子

信任度的計算基于對節(jié)點行為的評估,節(jié)點行為可以從不同角度描述。例如有的節(jié)點活躍度高,頻繁參與共識,有的節(jié)點運行不穩(wěn)定,經(jīng)常超時等等。這些不同的表現(xiàn)可通過節(jié)點活躍情況、總體運行狀況、事務(wù)影響程度、節(jié)點行為等因素來體現(xiàn)。這些因素可以統(tǒng)稱為信任度因子。將這些相關(guān)因子以不同權(quán)重加入信用度的計算中,就可以通過信用度評價共識過程中節(jié)點的行為狀態(tài)。

定義1(節(jié)點活躍度) 指節(jié)點在一定時間T內(nèi)參與共識的頻度,反映了節(jié)點在系統(tǒng)中的活躍程度。節(jié)點活躍度ρ(n)表示為:

(1)

定義2(節(jié)點共識完成率) 指節(jié)點完成其所參與共識的頻度,反映了節(jié)點在共識網(wǎng)絡(luò)中的運行狀況。節(jié)點共識完成率γ表示為:

(2)

其中,s表示成功完成的共識次數(shù),n為總共參與共識的次數(shù),γ值隨s與n比值增大而增大,γ越大表示節(jié)點越穩(wěn)定。

定義3(節(jié)點歷史影響度) 指節(jié)點歷史信任度對當前信任度的影響程度。節(jié)點歷史影響度ω(Δt)表示為:

(3)

定義4(事務(wù)重要級別因子) 用于標識請求事務(wù)的重要程度。設(shè)交易重要性參數(shù)為m,則事務(wù)影響函數(shù)F(m)可表示為:

(4)

其中,M0為交易重要性參數(shù)的閾值,本文取3,F(m)的值隨m值增大而增大,F(m)越大表示事務(wù)重要程度越高。

定義5(行為評價值) 對節(jié)點參與共識過程的行為進行綜合評價,行為評價值E表示為:

(5)

4.3 信任度的評價與更新

在每次共識過程完成后,系統(tǒng)會對各節(jié)點在本次過程中的表現(xiàn)進行評價。子區(qū)域i中節(jié)點j的信任度評價Sij表示為:

(6)

其中,Cinit為節(jié)點信任度初值,ρ(n)為節(jié)點活躍度,γ為共識完成率,ω(Δt)為歷史影響度,F(m)為事務(wù)重要級別因子,E為行為評價值。該模型可以準確地反映節(jié)點在本次共識過程中的表現(xiàn)。如果節(jié)點活躍度高且共識的完成情況好,或者完成級別較高的事務(wù)獲得較好的評價,都會使節(jié)點獲得較高的信任度評價。反之,如果節(jié)點活躍度較低,無法完成共識過程,則會導致節(jié)點獲得較低的信任度評價。

在完成對節(jié)點行為的評價后,需要以一定的策略更新節(jié)點的信任度,從而更新節(jié)點的信任類型。

設(shè)節(jié)點在開始共識前的信任度為Tij,本次共識過程完成后,節(jié)點信任度的評價值為Sij,則節(jié)點信任度按式(7)的規(guī)則更新:

(7)

其中,θ為信任度更新調(diào)節(jié)因子,若節(jié)點本次信任度評價高于往次,可適當調(diào)高信任度,反之則調(diào)低信任度。

如果節(jié)點因故障發(fā)生離線,信用度Cij會逐步衰減,即每次共識評價值Sij值為Cinit,直至Cij∈[0.9·Cinit,1.1·Cinit]或節(jié)點重新恢復服務(wù)。如果節(jié)點有惡意行為,信任度會變?yōu)?,后續(xù)該節(jié)點將被禁止參與共識。

信任度更新調(diào)節(jié)因子θ按式(8)的規(guī)則更新:

(8)

當本次信用度評價與前次評價值相差較大時,較小的信用度所占權(quán)重較大。這是因為當信用度評價值突然變大時,很有可能是節(jié)點在利用重要級別事務(wù)惡意提升自己的信任度,而該因子調(diào)節(jié)方式可以抑制信用度異常變化行為。

5 基于信任度的委托選舉

當節(jié)點完成信任度評估并確認信任類型后,就可以依據(jù)信任度進行委托選舉。

5.1 代理人選舉過程

PBFT協(xié)議本質(zhì)上是一種基于投票的共識機制,下面參照選舉制度為例來闡述節(jié)點委托的概念。圖2是一個三層的樹狀共識網(wǎng)絡(luò),其中節(jié)點包含4種類型:1)三級代理人節(jié)點,由信任類型為普通的節(jié)點組成,如果把每個子區(qū)域看做一個州,其類似于州一級的議員;2)二級代理人節(jié)點,從其直接子節(jié)點(即圖2中三級代理人節(jié)點)中的信任類型為可信的節(jié)點中選出,可以代表其所有子節(jié)點,類似于國會議員;3)一級代理人節(jié)點,從全網(wǎng)二級代理人節(jié)點中選出,具有最高的共識權(quán)重,類似于大選中獲勝的總統(tǒng);4)非共識節(jié)點,通常是故障或惡意節(jié)點,不參與共識過程,由于選舉是自下而上的,當?shù)鸵患壌砣松墳楦咭患壌砣酥?其空缺的位置將根據(jù)節(jié)點信任度排名自動遞補。

圖2 分層共識網(wǎng)絡(luò)架構(gòu)Fig.2 Hierarchical consensus network architecture

在系統(tǒng)初始化階段,根據(jù)應(yīng)用需求、網(wǎng)絡(luò)環(huán)境等條件預(yù)先規(guī)劃樹狀網(wǎng)絡(luò)結(jié)構(gòu),并根據(jù)節(jié)點的處理能力設(shè)置初始時各級代理人節(jié)點。在節(jié)點完成組網(wǎng)后,各級別節(jié)點分工合作,實現(xiàn)對全網(wǎng)節(jié)點請求事務(wù)的共識過程。類似于各級議員和總統(tǒng)分工合作實現(xiàn)對國家事務(wù)的治理。

為降低全網(wǎng)共識過程的通信復雜度,將共識分為局部和全局兩級共識過程。首先是各個子區(qū)域內(nèi)的節(jié)點進行局部共識,子區(qū)域的二級代理人節(jié)點負責定時生成區(qū)塊,二級和三級代理人節(jié)點會先對區(qū)塊進行一次局部共識過程,類似州議員投票形成一個州議案。全網(wǎng)所有的二級代理人和一級代理人再對區(qū)塊進行一次全局共識過程,對區(qū)塊進行最終確認。其他子區(qū)域的二級代理人節(jié)點將區(qū)塊異步地分發(fā)給各自區(qū)域內(nèi)的三級代理人節(jié)點,更新其節(jié)點的賬本數(shù)據(jù)庫。類似國會議員和總統(tǒng)對州議會的提案進行投票,形成全國性的法案,并將法案分發(fā)給其他各州執(zhí)行。

與其他基于分組的PBFT共識機制不同之處在于,由于采用了基于節(jié)點信任度的授權(quán),參與全局共識的節(jié)點是可信節(jié)點,可以代表其所在區(qū)域的所有節(jié)點進行共識投票,這樣極大地降低了共識的通信復雜度。

平臺將根據(jù)各級節(jié)點在共識過程中的表現(xiàn)(如完成共識的時間)確定節(jié)點的信任度。當某個代理人節(jié)點的信任度低于特定的閾值或因故障不能正常提供服務(wù)時,平臺將重新選舉新的代理人。當重新選舉時,如果是二級代理人節(jié)點,則僅需要本區(qū)域內(nèi)的節(jié)點完成一次選舉;如果是一級代理人節(jié)點,則需要全網(wǎng)節(jié)點重新進行選舉。

5.2 模型形式化定義

定義9(代理人節(jié)點狀態(tài)) 代理人節(jié)點分為:1)正常狀態(tài),即節(jié)點可以在規(guī)定時間內(nèi)完成共識過程;2)故障狀態(tài),即節(jié)點因為服務(wù)器宕機或網(wǎng)絡(luò)中斷導致的故障狀態(tài),該故障狀態(tài)如果能在指定時間內(nèi)恢復正常狀態(tài),則可以不重新選舉代理人節(jié)點;3)異常狀態(tài),即節(jié)點被檢測出惡意破壞和攻擊PBFT共識過程,此時,該節(jié)點被排除出共識網(wǎng)絡(luò),系統(tǒng)重新選擇代理人節(jié)點替代其職能。

定義10(法定選舉票數(shù)) 共識網(wǎng)絡(luò)完成共識過程需要的全網(wǎng)節(jié)點的最少票數(shù)。一個共識節(jié)點只有一張選票,但二級代理人節(jié)點在全局共識時可以擁有子區(qū)域內(nèi)的所有選票,類似大選中的贏者通吃策略。

定義11(票數(shù)權(quán)重) 一級和二級代理人節(jié)點在進行全局共識過程中代表其子節(jié)點票數(shù)的權(quán)重。如某個二級代理人節(jié)點下有10個三級代理人節(jié)點。當權(quán)重為100%時,其全局共識算作10張選票。當權(quán)重為50%時,其全局權(quán)重算作5張選票。票權(quán)隨著節(jié)點信用度的變化而改變。

定義12(區(qū)塊) 區(qū)塊鏈上的區(qū)塊由一組請求事務(wù)及其哈希值組成,表示為B=([tx1,tx2,…,txk],h)。區(qū)塊在全局有唯一的序號s。

定義13(局部共識) 每個子集合內(nèi)的節(jié)點執(zhí)行PBFT協(xié)議,完成共識過程,得到一個局部合法的區(qū)塊。

定義14(全局共識) 代表各個子集的二級代理人節(jié)點和一級代理人節(jié)點執(zhí)行PBFT協(xié)議,對局部共識進行二次共識過程,得到最終全局合法的區(qū)塊。

6 分層共識過程

本文提出的基于信任授權(quán)的分層共識協(xié)議TDH-PBFT,其核心思想是通過對共識節(jié)點進行劃分后,利用不同子區(qū)域的局部共識和委托代理人的全局共識降低傳統(tǒng)PBFT協(xié)議連接的節(jié)點數(shù)量,從而降低完成共識的時間,提高系統(tǒng)的吞吐量。

6.1 代理人選舉

在聯(lián)盟鏈共識網(wǎng)絡(luò)中,各級代理人節(jié)點可以由管理方預(yù)先設(shè)定,也可以隨機從節(jié)點中選擇。當節(jié)點運行一段時間,更新節(jié)點信任度之后,即可以依據(jù)信任度定期選舉各級代理人節(jié)點。

代理人選舉算法如算法1所示。

算法1TDH-PBFT代理人選舉算法

輸入對等數(shù)量n,對等節(jié)點N[n],組數(shù)m,節(jié)點組數(shù)G[m][n],三級代理人節(jié)點數(shù)TD_number[m],投票人權(quán)重FD_weight,SD_weight[m]

全局變量:FD,SD[m],TD[m][n],FD_credit,SD_credit[m],TD_credit[m][n]

1.procedure TDHPBFT_ELECTION()

2.for I ← 0,m do

3.TD[i][n]←delegatorElection(G[i][n],TD_number[i]+1)

4.end for

5.SD[m] ← delegatorElection(TD[m][n],1)

6.FD,k ← delegatorElection(SD[m],1)

7.SD[k] ← delegatorElection(TD[k][n],1)

8.TD[k][n] ← delegatorElection(G[k][n],1)

9.end procedure

H-PBFT初始化算法首先從各個子集中選取三級代理人節(jié)點。這里選擇的數(shù)量要比指定的三級代理人數(shù)量多一個,因為被選出的三級代理人節(jié)點將再執(zhí)行一次delegatorElection,推舉出二級代理人節(jié)點。同樣,二級代理人節(jié)點將選舉出擁有最高共識權(quán)重的一級代理人節(jié)點。假設(shè)被選中的一級代理人來自第k個集合,此時,由于k集合二級代理人晉升導致其崗位空缺。該集合將先從三級代理人中補選一個二級代理人,再從普通節(jié)點中增補一個三級代理人。

不同信任狀態(tài)的節(jié)點擁有不同的權(quán)限。可信節(jié)點權(quán)限最大,通常是一級、二級代理人節(jié)點,或者有機會作為候選人被選為一級、二級代理人節(jié)點。普通節(jié)點作為三級代理人節(jié)點正常參與局部共識過程。故障節(jié)點雖然狀態(tài)不穩(wěn)定,但仍然可以參與共識。但是一旦共識消息響應(yīng)超過時限,二級代理人節(jié)點可以在滿足允許的容錯節(jié)點數(shù)量前提下,主動放棄等待其返回的消息。惡意節(jié)點不參與共識,應(yīng)及時通知系統(tǒng)管理員進行故障修復。

6.2 分層共識算法

TDH-PBFT分層共識協(xié)議分為本地共識和全局共識2個階段執(zhí)行:

階段1(子集內(nèi)部的本地共識階段) 子集內(nèi)的二級代理人節(jié)點發(fā)起本地共識。由于子集內(nèi)有不少于4個節(jié)點參與共識,即節(jié)點數(shù)大于3f+1,因此可以抵御f個惡意節(jié)點的拜占庭攻擊。共識過程分為PROPOSE、WRITE和ACCEPT 3步。二級代理人節(jié)點首先向其他節(jié)點廣播PROPOSE消息。其他節(jié)點驗證PROPOSE消息后就進入WRITE階段,廣播WRITE消息。當各節(jié)點接收到2f+1個WRITE消息后,節(jié)點進入ACCEPT階段,廣播ACCEPT消息。當各節(jié)點接收到2f+1個ACCEPT消息后,表示大部分節(jié)點對二級代理人節(jié)點發(fā)起的請求達成了共識。此時,階段1的本地共識完成。

階段2(子集間的全局共識階段) 在本地共識階段完成后,接收到足夠數(shù)量消息的二級代理人節(jié)點,將作為成員參加全局共識過程。首先向一級代理人節(jié)點和各個子集的二級代理人節(jié)點廣播PROPOSE消息。這里各子集二級代理人不需要再將消息轉(zhuǎn)發(fā)到子集內(nèi)部進行本地共識,而是作為各自子集的全權(quán)代表對消息進行投票,具體代表的票數(shù)通過投票權(quán)數(shù)控制。例如,某個子集內(nèi)有4個節(jié)點,投票權(quán)重為100%,二級代理人節(jié)點擁有4張票權(quán),若投票權(quán)重為50%,則擁有2張票權(quán)。按照此規(guī)則,各節(jié)點開始廣播WRITE消息。當各節(jié)點接收到2f+1個WRITE消息后,節(jié)點進入ACCEPT階段,并廣播ACCEPT消息。當各節(jié)點接收到2f+1個ACCEPT消息后,表示大部分節(jié)點對二級代理人發(fā)來的請求達成了共識。此時,階段2的全局共識完成,一級和二級代理人將區(qū)塊寫入賬本。各子集的二級代理人通知子集內(nèi)部其他節(jié)點,各節(jié)點更新本地區(qū)塊鏈賬本,實現(xiàn)共識網(wǎng)絡(luò)數(shù)據(jù)的最終一致性。

分層共識協(xié)議消息示意圖如圖3所示。

圖3 分層共識協(xié)議消息示意圖Fig.3 Schematic diagram of hierarchical consensus protocol messages

分層共識算法如算法2所示。

算法2TDH-PBFT分層共識算法

1.Initialisation

2.s ← 0

3.B ← ⊥

4.D ← ⊥

5.accepted ← {⊥}

6.

7.Local propose phase

8.send LOCAL_PROPOSE where sp← s to all local delegators

9.

10.Upon LOCAL_PROPOSE where sp= s+1 from delegator

11.s ← sp

12.B ← Bp

13.begin Local write phase

14.

15.Local write phase

16.D ← digest(B)

17.send LOCAL_WRITE where sp← s;Bp← B;Dp← D to all local delegators

18.wait for majority of LOCAL_WRITE where sp= s,Dp= D

19.send LOCAL_ACCEPT where sp← s;Bp← B;Dp← D to all local delegators

20.

21.Upon LOCAL_ACCEPT where sp= s from delegator

22.if Dp= D then

23.accepted ← accepted {delegator}

24.if accepted contains majority of delegators then

25.begin Global propose phase

26.

27.Global propose phase

28.send GLOBAL_PROPOSE where sp← s to all global delegators

29.

30.Upon GLOBAL_PROPOSE where sp= s+1 from delegator

31.s ← sp

32.B ← Bp

33.begin Global write phase

34.

35.Global write phase

36.D ← digest(B)

37.send GLOBAL_WRITE where sp← s;Bp← B;Dp← D to all global delegators

38.wait for majority of GLOBAL_WRITE where sp=s,Dp=D

39.send GLOBAL_ACCEPT where sp← s;Bp← B;Dp← D to all global delegators

40.

41.Upon GLOBAL_ACCEPT where sp= s from delegator

42.if Dp=D then

43.accepted ← accepted {delegator}

44.if accepted contains majority of delegators then

45.decided on B

6.3 投票權(quán)數(shù)調(diào)整

在經(jīng)典PBFT算法中,一個節(jié)點只擁有一張票權(quán)。建立可變票權(quán)機制可以進一步優(yōu)化共識算法,增強共識算法的容錯能力。

節(jié)點的投票權(quán)數(shù)是根據(jù)節(jié)點的信任狀態(tài)決定的。可信節(jié)點通常具有更高的票權(quán),用Vtrust表示為:

(9)

其中,Nabnormal為故障節(jié)點數(shù)量,Ntrust為可信節(jié)點數(shù)量,N為參與共識的節(jié)點總數(shù)。從式(9)可以看出,故障節(jié)點數(shù)增加或可信節(jié)點數(shù)減少都會提升可信節(jié)點的投票權(quán)數(shù)。

普通節(jié)點投票權(quán)用Vnormal表示為:

(10)

其中,Nnormal為普通節(jié)點數(shù)量,其權(quán)重同樣受到故障節(jié)點和普通節(jié)點數(shù)量的影響。如果當前系統(tǒng)內(nèi)沒有可信節(jié)點,可以進一步提升普通節(jié)點的票權(quán),如式(11)所示:

(11)

故障節(jié)點投票權(quán)用Vabnormal表示為:

(12)

故障節(jié)點投票權(quán)數(shù)主要取決于故障節(jié)點占共識總節(jié)點數(shù)的大小。故障節(jié)點越多,其票權(quán)就越低。惡意節(jié)點沒有投票權(quán),則不參與共識過程。

6.4 基于信任度的共識優(yōu)化

利用節(jié)點的信任度,可以在共識開始前和WRITE、ACCEPT消息完成后進一步優(yōu)化共識過程。

如圖4所示,當共識過程開始時,二級代理人節(jié)點先將各節(jié)點按信用度高低排序。排除惡意節(jié)點,將可信節(jié)點、正常節(jié)點和異常節(jié)點作為本次共識的節(jié)點。

圖4 基于信任度的共識過程優(yōu)化示意圖Fig.4 Schematic diagram of consensus process optimization based on trust degree

在WRITE階段,三級代理人節(jié)點將WRITE消息廣播給其他共識節(jié)點,當二級代理人節(jié)點收到2f+1個確認消息后,進入ACCEPT階段。如果此時有節(jié)點的消息沒有正常返回,或者有惡意消息,在保證2/3共識節(jié)點數(shù)量的前提下,該節(jié)點將被移除,不再參與后續(xù)共識。二級代理人節(jié)點通過ACCEPT消息的附加屬性將移除的節(jié)點通知其他三級代理人節(jié)點。

在ACCEPT階段,三級代理人節(jié)點將WRITE消息廣播給其他共識節(jié)點,當二級代理人節(jié)點收到2f+1個確認消息后共識達成。二級代理人記錄各節(jié)點在共識過程中的行為和狀態(tài),計算并更新節(jié)點信用值和節(jié)點信用狀態(tài),再將各節(jié)點最新信任度表廣播給各個三級代理人節(jié)點。

6.5 分層共識一致性證明

下文證明采用TDH-PBFT協(xié)議實現(xiàn)分布式一致性,并且滿足分層共識網(wǎng)絡(luò)的活性和安全屬性。

證明由于TDH-PBFT協(xié)議包含了局部共識和全局共識2個階段,下面將通過分析2個階段中協(xié)議的執(zhí)行過程來證明TDH-PBFT可以實現(xiàn)分布式一致性。

綜上所述,TDH-PBFT共識過程是2個連續(xù)的PBFT過程,且區(qū)塊序號在2次協(xié)議執(zhí)行中保持不變。由于PBFT協(xié)議已被證明實現(xiàn)了分布式一致性,因此TDH-PBFT在全局共識協(xié)議中實現(xiàn)了一致性,滿足區(qū)塊鏈網(wǎng)絡(luò)的有效性、一致性、完整性和全序關(guān)系等屬性。

引理1TDH-PBFT協(xié)議滿足分層共識網(wǎng)絡(luò)有效性Validity。

1)如果二級代理人SDi未被錯誤懷疑,則所有參與全局共識的節(jié)點都會對區(qū)塊B達成共識,即所有無故障的二級代理人節(jié)點都會獲得B,并將該區(qū)塊分發(fā)給各自區(qū)域內(nèi)的節(jié)點進行提交。如果某個二級代理人發(fā)生故障,它會先根據(jù)全局故障恢復機制得到處理,并最終獲取區(qū)塊B。因此,請求tx將最終在共識過程中被提交。

引理2TDH-PBFT協(xié)議滿足分層共識網(wǎng)絡(luò)一致性Agreement。

證明如果某個子區(qū)域i內(nèi)的節(jié)點N提交一個請求tx,根據(jù)分布式共識服務(wù)的“連續(xù)序號”和“不重復請求”屬性,則有:1)該節(jié)點所在區(qū)域的二級代理人節(jié)點SDi必然提交了包含tx且序號為s的區(qū)塊B;2)區(qū)塊B必然已經(jīng)完成了一次全局共識;3)各級節(jié)點必然已經(jīng)獲取了所有小于序號s的區(qū)塊;4)沒有任何小于序號s的區(qū)塊會包含tx。由此可得,在分層共識網(wǎng)絡(luò)中,如果正常狀態(tài)的代理人節(jié)點接收到序號為s的區(qū)塊B和序號為s′的區(qū)塊B′,若s=s′,則B=B′。

引理3TDH-PBFT協(xié)議滿足分層共識網(wǎng)絡(luò)完整性Integrity。

證明假設(shè)某二級代理人節(jié)點SDi發(fā)送了序號為s+1的區(qū)塊Bs+1,根據(jù)分布式共識服務(wù)的“連續(xù)序號”和“不重復請求”屬性,則必然有某二級代理人節(jié)點SDj已經(jīng)提交了序號為s的區(qū)塊Bs,且該區(qū)塊已經(jīng)完成全局共識,并被各節(jié)點提交至賬本。二級代理人節(jié)點SDi在發(fā)起請求s+1前,使用哈希函數(shù)對本地賬本數(shù)據(jù)庫存儲的前一個區(qū)塊s進行簽名,將得到的哈希值H(B)和最新的tx事務(wù)一起打包。這樣新的區(qū)塊Bs+1必然滿足哈希鏈完整性。

引理4TDH-PBFT協(xié)議滿足分層共識網(wǎng)絡(luò)全序關(guān)系Total order。

證明假設(shè)來自子區(qū)域i和j的2個客戶節(jié)點ci和cj分別發(fā)起了事務(wù)請求txi和txj。子區(qū)域i和j各自的二級代理人SDi和SDj將對txi和txj打包成區(qū)塊Bi和Bj。下面分兩種情況來說明該引理成立。

1)如果ci和cj位于同一個子區(qū)域,則SD將按照請求提交的時間對txi和txj進行排序。接下來txi和txj可能都被按序打包進序號為s的區(qū)塊B中,當區(qū)塊完成全局共識分發(fā)至各節(jié)點后,txi必將先于txj被提交至賬本。txi和txj還有可能分別打包進序號為s的區(qū)塊Bs以及序號為s+1的區(qū)塊Bs+1。由分布式共識服務(wù)的“連續(xù)序號”屬性可知,Bs將先于Bs+1完成全局共識并被提交,則txi也將先于txj被提交至賬本。

2)如果ci和cj位于不同的子區(qū)域,則有txi和txj分別被SDi和SDj打包至區(qū)塊Bi和Bj中。

(1)由于客戶節(jié)點ci在執(zhí)行請求事務(wù)時,必須選擇至少包含F(xiàn)D、SDi和TDki在內(nèi)的3個代理人節(jié)點。3個節(jié)點返回的事務(wù)執(zhí)行結(jié)果必須相同,即保證賬本數(shù)據(jù)庫在全局和局部完全一致,客戶節(jié)點才會將請求發(fā)送給SDi,從而開始2次共識過程。

(2)一級代理人節(jié)點FD擁有的全局事務(wù)視圖,是協(xié)調(diào)各個子區(qū)域請求事務(wù)順序的關(guān)鍵。

SDi在將事務(wù)tx打包成區(qū)塊B時,將詢問FD其區(qū)域允許打包事務(wù)的開始和結(jié)束區(qū)間。當區(qū)間內(nèi)沒有鍵值修改沖突時,例如txi先于txj修改了鍵為k的值,SDi將按照預(yù)定的區(qū)塊大小或默認時間間隔進行打包。這樣,Bi先于Bj被提交參與共識,可確保Bi中的事務(wù)txi先于txj被提交至賬本;否則,假設(shè)txj先于txi修改了鍵為k的值,SDi將打包至SDj修改k的前一次修改事務(wù)到區(qū)塊Bi,SDj將從修改k的事務(wù)開始打包Bj。此時,當Bi和Bj完成全局共識后,Bj中的事務(wù)txj先于txi被提交至賬本。

綜上可得,TDH-PBFT協(xié)議滿足分層共識網(wǎng)絡(luò)的全序關(guān)系要求。

7 實驗評估

為深入了解TDH-PBFT模型的運行機制,使用SimPy模擬器對其運行流程進行建模。SimPy是基于進程的離散事件模擬器,它包含實體(Process)、事件(Event)和資源(Resource)3個主要概念。在TDH-PBFT中,實體主要是各級代理人節(jié)點,事件包括局部和全局共識的PROPOSE、WRITE、ACCEPT等。為了便于對比參照,還使用SimPy實現(xiàn)了標準的PBFT算法以及單純采用分組的H-PBFT算法。H-PBFT算法中,各分組的頭結(jié)點用于轉(zhuǎn)發(fā)其他分組的消息,而并非像TDH-PBFT算法,代表組內(nèi)節(jié)點直接參與共識。

首先比較3種共識算法在系統(tǒng)節(jié)點數(shù)為17、49、97這3種情況下的性能,主要考察吞吐量和延時2個指標,PBFT的性能數(shù)據(jù)是實驗的基準線。從圖5和圖6可以看出,PBFT算法性能隨著節(jié)點數(shù)的增多而下降。吞吐量從3 164 TPS迅速下降至1 233 TPS,下降了61%。事務(wù)請求平均延時從750 ms增大到1 103 ms。基于分組的H-PBFT共識算法性能有所改善,這得益于分組降低了全網(wǎng)共識消息。TDH-PBFT的吞吐量是三者中最優(yōu)的,隨著共識節(jié)點數(shù)從17增大到97,吞吐量僅下降了14.7%。節(jié)點數(shù)為97時的事務(wù)請求平均延時為762 ms,接近PBFT算法在節(jié)點數(shù)為17時的延時。該實驗展現(xiàn)了TDH-PBFT共識算法具有良好的伸縮性能,可以有效緩解當共識網(wǎng)絡(luò)節(jié)點數(shù)增大時,消息數(shù)量爆炸導致的性能下降。

圖5 不同共識算法下系統(tǒng)吞吐量的對比Fig.5 Comparison of system throughput under different consensus algorithm

圖6 不同共識算法下系統(tǒng)延時的對比Fig.6 Comparison of system delay under different consensus algorithm

然后比較區(qū)塊大小對系統(tǒng)性能的影響。分別選取0.5 MB、1 MB、2 MB和4 MB 4種取值,這也是實際系統(tǒng)部署時常選取的4種取值。從圖7可以看出,當區(qū)塊大小從0.5 MB增大到2 MB時,系統(tǒng)吞吐量從6 023 TPS增加到7 989 TPS,增加了33%。但單個事務(wù)請求的平均延時從608 ms增大到753 ms。這是因為增大區(qū)塊大小可以減少共識次數(shù),提升系統(tǒng)的整體處理能力,但對于個別請求,等待打包的時間增加了其請求時長。當區(qū)塊大小從2 MB增大到4 MB時,系統(tǒng)吞吐量增加了2%,系統(tǒng)延時也進一步增大。可以看出,此時增加區(qū)塊大小對系統(tǒng)性能提升的作用已不顯著,2 MB是TDH-PBFT算法首選的區(qū)塊大小值。

圖7 區(qū)塊大小對系統(tǒng)吞吐量和延時的影響Fig.7 Influence of block size on system throughput and latency

最后比較共識節(jié)點部署在不同類型網(wǎng)絡(luò)下的系統(tǒng)性能差異。選取17個節(jié)點的共識網(wǎng)絡(luò),第1類場景模擬所有節(jié)點全部都在局域網(wǎng)環(huán)境內(nèi),節(jié)點之間使用百兆網(wǎng)絡(luò)互連。第2類場景模擬節(jié)點混合部署,即一級和二級代理人之間的全局共識網(wǎng)絡(luò)使用10兆網(wǎng)絡(luò)互連,二級和三級代理人之間的局部共識網(wǎng)絡(luò)使用百兆網(wǎng)絡(luò)互連。第3類場景模擬所有節(jié)點全部都在互聯(lián)網(wǎng)環(huán)境內(nèi),節(jié)點之間使用10兆網(wǎng)絡(luò)互連。從圖8可以看出,3種算法在有節(jié)點處于互聯(lián)網(wǎng)環(huán)境時,隨著共識時間變長,吞吐量均會下降。但無論在哪種網(wǎng)絡(luò)類型下,TDH-PBFT的吞吐量都是最優(yōu)的。即使在完全互聯(lián)網(wǎng)環(huán)境中,TDH-PBFT的性能也優(yōu)于H-PBFT在完全局域網(wǎng)環(huán)境的性能。分層共識算法減少了共識消息的數(shù)量,使網(wǎng)絡(luò)帶寬對共識算法性能的影響降到最低。

圖8 網(wǎng)絡(luò)對系統(tǒng)吞吐量的影響Fig.8 Influence of network on system throughput

8 結(jié)束語

為優(yōu)化大規(guī)模聯(lián)盟鏈網(wǎng)絡(luò)的共識過程,本文提出一種基于信任委托的分層共識優(yōu)化機制。根據(jù)節(jié)點運行狀態(tài)建立信任度,選舉出可信的代理人節(jié)點進行局部和全局2次共識過程,從而降低消息廣播的數(shù)量,提升共識網(wǎng)絡(luò)吞吐率。實驗結(jié)果表明,該模型能夠滿足聯(lián)盟鏈平臺的性能擴展性需求,當全網(wǎng)節(jié)點數(shù)增大時,系統(tǒng)依然可以保持較好的性能。在TDH-PBFT共識算法中,二級與三級節(jié)點配比、權(quán)重票數(shù)和全局共識閾值等參數(shù)均對系統(tǒng)性能產(chǎn)生顯著影響,后續(xù)將對參數(shù)的作用做進一步研究。