基于位置的改進(jìn)HotStuff共識機(jī)制與仿真

張宇翔,向海昀,李 博,廖浩德

(西南石油大學(xué)計算機(jī)科學(xué)學(xué)院,四川 成都 610500)

1 引言

2008年中本聰《比特幣:一種點對點的電子現(xiàn)金系統(tǒng)》[1]問世,標(biāo)志著區(qū)塊鏈技術(shù)的誕生。區(qū)塊鏈作為一個典型的去中心化的分布式數(shù)據(jù)存儲系統(tǒng),以其安全性,不可篡改性而被人們熟知,而在區(qū)塊鏈系統(tǒng)中的所有參與者之間就一項事務(wù)達(dá)成共識需要通過共識機(jī)制來實現(xiàn)。可以說共識機(jī)制是區(qū)塊鏈的核心,共識機(jī)制不僅保證了區(qū)塊鏈的安全性,更影響著區(qū)塊鏈的性能,如何在區(qū)塊鏈系統(tǒng)中高效達(dá)成共識是制約區(qū)塊鏈技術(shù)發(fā)展應(yīng)用的重要問題[2]。

共識算法根據(jù)容錯機(jī)制的不同,可以分為故障容錯(Crash Fault Tolerance,CFT)共識算法和拜占庭容錯(Byzantine Fault Tolerance,BFT)共識算法[3]。故障容錯指參與共識過程中的節(jié)點不會作惡,只可能發(fā)生宕機(jī)等錯誤的情況下達(dá)成共識;而拜占庭容錯指存在拜占庭將軍問題[4],即在參與共識過程的節(jié)點中存在故意作惡的節(jié)點的情況下保證共識過程的成功。根據(jù)應(yīng)用場景的不同,可以分為公有鏈的共識算法和聯(lián)盟鏈的共識算法。公有鏈的共識算法主要有POW共識算法[5],POS共識算法[6],DPOS共識算法[7]等,這些共識算法可能會導(dǎo)致區(qū)塊鏈的分叉,因此在公有鏈中應(yīng)用較多,公有鏈因打包上鏈延遲大、區(qū)塊大小有限而在應(yīng)用時有諸多限制,有人針對這些缺點做出了一些改進(jìn)[8,9]。聯(lián)盟鏈的共識是以拜占庭共識算法為主的共識算法,有PBFT[10],SBFT[11],HotStuff[12]等,這些算法是強(qiáng)一致性算法,不允許區(qū)塊鏈的分叉,因此其更加適用于聯(lián)盟鏈,而聯(lián)盟鏈為了獲得更好的性能,對于共識或驗證節(jié)點的配置和網(wǎng)絡(luò)環(huán)境有一定要求[13]。

PBFT是LISCOV等人在1999年提出的一種實用拜占庭算法,該算法解決了分布式系統(tǒng)中的拜占庭問題,其容錯率為n≥3f+1,其中n是總節(jié)點數(shù)量,f是拜占庭節(jié)點數(shù)量。PBFT算法的出現(xiàn),最早使用三階段提交協(xié)議實際的解決了拜占庭將軍問題。PBFT的出現(xiàn)使得后續(xù)聯(lián)盟鏈很多都在使用該算法,最為人們熟知的就是超級賬本(Hyperledger Fabric)[14]隨著近年來區(qū)塊鏈的興起,PBFT的O(n2)的通信復(fù)雜度使得性能隨著增長的網(wǎng)絡(luò)規(guī)模而下降。因此針對PBFT性能的提升逐漸變得重要。

YIN等人在2018年提出的HotStuff算法采用了門限簽名的方法實現(xiàn)了O(n)的通信復(fù)雜度。該算法總結(jié)對比了目前主流的拜占庭類共識協(xié)議,構(gòu)建了基于經(jīng)典拜占庭共識協(xié)議實現(xiàn)PipelineBFT的共識模式。HotStuff創(chuàng)新采用了Pacemaker將活性(Liveness)和安全性(Safety)解耦,同時也提高了該共識算法的可擴(kuò)展性。由于HotStuff的高可用性和低復(fù)雜度,Facebook推出的Libra[15]正是采用了HotStuff共識算法。

然而,HotStuff算法的通信模式為全節(jié)點直接通信,若節(jié)點分布地域較廣,節(jié)點間通信將會帶來高延遲,從而極大降低吞吐量,造成較大的通信代價[16]這是影響聯(lián)盟鏈共識效率的重要因素。鑒于此,本文提出一種基于位置分組的根據(jù)HotStuff算法思想改進(jìn)的共識協(xié)議,將節(jié)點根據(jù)位置的不同分為若干組,組內(nèi)單獨進(jìn)行共識,再由各組主節(jié)點將共識結(jié)果傳輸給其它組進(jìn)行共識,每次可以同時處理若干個請求,提高了共識的效率。

2 HotStuff算法

2.1 算法概述

設(shè)節(jié)點總數(shù)為n,拜占庭節(jié)點的個數(shù)為f,且滿足n≥3f+1。共識過程采用視圖(View)的方式進(jìn)行,即每個視圖達(dá)成一輪共識,視圖有其唯一編號(ViewNumber)且單調(diào)遞增,用來標(biāo)識視圖,每個視圖都有一個主節(jié)點(Leader)領(lǐng)導(dǎo)所有副節(jié)點(Replica)共識,在當(dāng)前共識完成后,執(zhí)行View編號遞增并開啟下一輪共識。如果遇到了主節(jié)點宕機(jī)或者主節(jié)點作惡的情況,則更換主節(jié)點并開始下一輪視圖。

HotStuff采用了門限簽名的機(jī)制,引入了一個新的概念“仲裁證書”(QuorumCertificate,QC)。QC指在一個三元組之上且組合了n-f個副節(jié)點部分簽名進(jìn)而達(dá)成共識的證明。當(dāng)前階段Leader收集到超過n-f個Replica簽名確認(rèn)過的數(shù)據(jù)包及ViewNumber形成的一個集合,用于表示當(dāng)前階段已經(jīng)被副節(jié)點達(dá)成共識。

HotStuff三階段共識流程如圖1所示

圖1 HotStuff共識各階段流程

2.2 共識過程

2.2.1 Prapare階段

在每一輪View開始的時候,所有Replica向Leader發(fā)送NewView消息,表示新視圖的開始。NewView消息包含每個副節(jié)點對最新區(qū)塊的投票簽名prepareQC(允許為空),Leader收到超過n-f個NewView消息后,將收到的NewView中區(qū)塊最高的prepareQC形成HighQC,保證沒有更高的視圖可以使用,即保證了當(dāng)前區(qū)塊是最安全的,后續(xù)共識在此基礎(chǔ)上展開。Leader形成HighQC后,在對應(yīng)區(qū)塊的后面打包新的區(qū)塊并以prepare消息廣播。副節(jié)點收到prepare消息后,對該消息進(jìn)行簽名摘要(投票)。

2.2.2 Pre-Commit階段

此時Leader收集副節(jié)點的簽名消息,當(dāng)Leader收集到n-f個投票后,形成prepareQC,并以pre-commit消息向所有副本廣播prepareQC。副節(jié)點通過pre-commit投票對Leader做出響應(yīng),并對提案進(jìn)行投票。

2.2.3 Commit階段

Commit階段類似于Pre-Commit階段,副節(jié)點收到prepareQC后,對prepareQC投票,此時Leader收集副節(jié)點的投票,當(dāng)收集到n-f個pre-commit投票時,將其組合為precommitQC,以commit類型消息廣播,此時副節(jié)點接收使用commit消息響應(yīng),對precommitQC進(jìn)行投票。

2.2.4 Decide階段

進(jìn)入Decide階段后Leader節(jié)點開始收集副節(jié)點的投票,當(dāng)其收到n-f個commit投票后,將它們合并為commitQC,并以decide消息的形式將commitQC發(fā)送給其余副節(jié)點。當(dāng)副節(jié)點收到decide消息后,獲取commitQC,將該commitQC中包含的提案視為已經(jīng)提交的請求,并在自己的副本中執(zhí)行該請求。完成后,副節(jié)點增加viewNumber并啟動下一個視圖。

2.2 HotStuff復(fù)雜度分析

在HotStuff的每個階段,只有Leader向所有副節(jié)點廣播,而副節(jié)點使用部分簽名向發(fā)送者回復(fù)一次以完成簽名和部分投票。在Leader的角度下,每階段形成的QC都是由n-f個來自副節(jié)點的投票組成。因此,在每個階段下,通信的復(fù)雜度是O(n)。由于有固定的階段數(shù),每個視圖的總體復(fù)雜度為O(n)。

HotStuff算法將拜占庭容錯類共識算法復(fù)雜度降低到了O(n),縮小了節(jié)點間的通信開銷,但是忽略了實際因素的影響。當(dāng)節(jié)點與節(jié)點間的距離過大,會導(dǎo)致難以避免的通信延遲和負(fù)擔(dān),從而導(dǎo)致吞吐量的急劇下降,隨著節(jié)點間距離的增大,延遲也會隨之增長。隨著聯(lián)盟鏈的擴(kuò)大,節(jié)點也將分布的越來越廣,考慮位置因素是將會變得尤為重要。

3 PBHS算法

隨著聯(lián)盟鏈的廣泛應(yīng)用,各行各業(yè)都置身于聯(lián)盟鏈中,在實際應(yīng)用場景下,節(jié)點間的各節(jié)點間距離跨域很大,節(jié)點間通信有一定延遲,這就導(dǎo)致鏈中節(jié)點間共識效率降低,而共識效率是影響聯(lián)盟鏈實際使用的重要影響因素。將位置因素納入考慮,根據(jù)HotStuff的算法思想,本文提出一種改進(jìn)的共識算法PBHS(PositionBasedHotStuff)算法。

3.1 算法概述

假設(shè)系統(tǒng)中的總節(jié)點有n個,分為G組,每組m個節(jié)點,gi(id)表示第i組第id個節(jié)點,其中m滿足m≥3f+1,其中f是每個組內(nèi)所能容納的最大拜占庭節(jié)點。網(wǎng)絡(luò)模型使用部分同步模型,即存在一個不確定的全局穩(wěn)定時間GST(GlobalStableTime),在指令發(fā)出后的一定時間Δ后,所有的非拜占庭節(jié)點都能對指令的順序及結(jié)果產(chǎn)生共識,從而使得網(wǎng)絡(luò)狀態(tài)確定。

PBHS算法分為兩個階段,分別是Local共識階段和Remote共識階段。在每輪共識開始時,每組僅僅處理當(dāng)?shù)氐恼埱?通過Local共識階段可以是的組內(nèi)達(dá)成共識并產(chǎn)生一個最終證書,該證書包含了組內(nèi)節(jié)點對請的簽名。接下來,每組與每組之間共享本地的請求和最終證書,為了減小組與組之間的通信,使用新的樂觀響應(yīng)協(xié)議。每組將收到的請求和最終證書在組內(nèi)共識,此時如果發(fā)現(xiàn)錯誤,可以啟用遠(yuǎn)程視圖更改協(xié)議。最后,在收到所有的請求和證書后,執(zhí)行該系列請求,但是每個組僅返回當(dāng)?shù)卣埱蟮慕Y(jié)果。整體共識示意圖如圖2所示。各分組節(jié)點內(nèi)部進(jìn)行共識,后由主節(jié)點將共識結(jié)果在組間進(jìn)行共識,進(jìn)而達(dá)成整體共識,執(zhí)行請求后由分組返回當(dāng)?shù)卣埱蠼Y(jié)果。

圖2 PBHS算法整體示意圖

3.2 Local共識階段

本地共識采用HotStuff的共識方式,使用門限簽名,在prepare、pre-commit、commit、decide階段均由Leader節(jié)點收集副節(jié)點的部分簽名形成相應(yīng)階段的QC。在PBHS算法中,decide階段完成后各副本并不是直接執(zhí)行請求,而是形成一個最終證書(finalCertificate,fc)。

(1)

Local共識階段的任意一輪共識滿足以下兩點:(1)任意一個非拜占庭節(jié)點最終能夠正確執(zhí)行客戶端請求。(2)所有的非拜占庭節(jié)點在一輪視圖中處理的是同一個請求。定理1保證了Local共識階段在同一視圖中只有一個請求被執(zhí)行。

定理1:對于任意兩個合法QC1和QC2,如果兩種QC的類型相同,則必然有QC1和QC2所帶表的視圖不同,組內(nèi)視圖中保證同時最多只有一個請求能夠被執(zhí)行。即:

(2)

證明:對于任意的QC1和QC2,假設(shè),QC1的類型和QC2的類型相同,且屬于同一個視圖,因為QC是組內(nèi)超過m-f=2f+1個節(jié)點投票得出,若形成了兩個相同類型的QC且屬于同一個視圖則代表至少有一個正常工作的節(jié)點對不同的請求投票兩次,而每輪共識中每個正常節(jié)點僅對消息投票一次,二者相悖,故不可能有多個請求在同一組內(nèi)被同時執(zhí)行,證明完畢。

3.2.1 Local共識階段安全性分析

定理2:對于組內(nèi)共識,由于該階段內(nèi)分組仍滿足m≥3f+1,所以組內(nèi)系統(tǒng),即本地共識階段仍滿足拜占庭容錯,該階段安全性在拜占庭節(jié)點數(shù)量滿足條件的情況下能夠得到保證。

證明:分組節(jié)點數(shù)量是m,設(shè)拜占庭節(jié)點數(shù)量為f,非拜占庭節(jié)點數(shù)量為a,最終能夠保證安全性所需非拜占庭節(jié)點數(shù)量為x,則有

m=f+a,且a>x

(3)

為保證在非拜占庭節(jié)點正常接收消息并做出回應(yīng),必須滿足

(4)

由式(3)(4)合并得出

(5)

代換得

m>3f

(6)

式(6)滿足題設(shè)m≥3f+1,證畢。

在節(jié)點數(shù)量方面,多數(shù)拜占庭容錯類共識算法的實際部署節(jié)點數(shù)量較小,但其安全性卻是嚴(yán)格的,因此在分組后組內(nèi)節(jié)點數(shù)量變少不會對本地共識階段造成安全性影響。

3.3 Remote共識階段

當(dāng)組內(nèi)完成請求的Local共識之后,將進(jìn)入Remote共識階段,即將請求與形成的最終證書與其它組共享。設(shè)g∈G為一個組,在g的第i輪本地達(dá)成共識后,將請求r和最終證書fc發(fā)送給其它組,消息格式為,其中g(shù)表示分組編號,r表示請求內(nèi)容,fc代表形成的最終證書,v代表視圖編號。發(fā)送消息同時接收來自其它組的請求和最終證書。此時需要組間通信,通信開銷較大,為達(dá)到算法目的,應(yīng)該在保證可靠性的前提下盡可能減少通信開銷,在各組Leader可信的情況下,采用一種樂觀通信方法降低節(jié)點間通信。

不失一般性,以兩個組為例說明。假設(shè)系統(tǒng)包含兩個組g1,g2,當(dāng)g1完成Local共識階段后,將消息發(fā)送給g2,在采用樂觀的方式下,即主節(jié)點不發(fā)生故障且通信可靠的情況下,g1中的主節(jié)點Leaderg1僅發(fā)送一條消息給g2中的主節(jié)點Leaderg2是無法達(dá)成有效傳播的,需要給g2中的節(jié)點發(fā)送f+1條消息。當(dāng)g2中的節(jié)點收到來自g1的消息后,在組內(nèi)廣播該條消息。

定理3:樂觀條件下,即發(fā)送組主節(jié)點不發(fā)生故障,通信可靠,f+1條消息就能保證組間消息正常收發(fā)。

證明:若只由Leader節(jié)點間發(fā)送一條消息,考慮以下情況:1)Leaderg1是拜占庭節(jié)點,在組內(nèi)共識時表現(xiàn)正常,組內(nèi)節(jié)點無法發(fā)現(xiàn)其是拜占庭節(jié)點,但該節(jié)點不將任何消息發(fā)送給Leaderg2;2)Leaderg1是正常節(jié)點,將消息發(fā)送給Leaderg2,但Leaderg2是拜占庭節(jié)點,在組內(nèi)表現(xiàn)正常,但是不轉(zhuǎn)達(dá)Leaderg1的消息。以上兩種情況都會導(dǎo)致組間消息無法傳達(dá)。對于每個組,組內(nèi)節(jié)點至多有f個拜占庭節(jié)點,樂觀條件下,即通信狀態(tài)可靠、Leaderg1不發(fā)生故障時,f+1條消息能夠保證g2中的所有副本至少有一個非拜占庭副本能夠正常接收消息并廣播。而對于收到的消息,因為其中的fc是包含了該組m-f個消息的最終證書,任何拜占庭節(jié)點都無法偽造,故所有其它節(jié)點很容易驗證該條消息的真?zhèn)巍?/p>

Remote共識階段流程如圖3所示:

圖3 組間共識階段

3.4 組間視圖轉(zhuǎn)換

為了能夠及時發(fā)現(xiàn)并更正錯誤,除了本地視圖轉(zhuǎn)換外,還需要使用組間視圖轉(zhuǎn)換來保證安全性。組間視圖轉(zhuǎn)換分為兩個部分,分別是檢查階段和視圖轉(zhuǎn)換階段。

1)檢查階段:檢查階段分為兩部分,首先g2中的節(jié)點在收到Leaderg1發(fā)送的包含fc的消息后,廣播該消息,每個節(jié)點收到消息后,驗證該消息是否符合規(guī)范,當(dāng)發(fā)現(xiàn)消息不符合規(guī)范時,進(jìn)入視圖轉(zhuǎn)換階段。其次等待超時后,節(jié)點仍未收到消息,認(rèn)為消息丟失,進(jìn)入視圖轉(zhuǎn)換階段。視圖轉(zhuǎn)換的消息格式為i,其中g(shù)代表目標(biāo)分組編號,v代表當(dāng)前視圖編號,i代表當(dāng)前分組編號。

2)視圖轉(zhuǎn)換階段:每個節(jié)點向g1對應(yīng)節(jié)點發(fā)送視圖轉(zhuǎn)換請求,當(dāng)g1中的節(jié)點收到消息后,在組內(nèi)廣播視圖轉(zhuǎn)換請求,當(dāng)組內(nèi)節(jié)點收到m-f個請求后,啟動組內(nèi)視圖轉(zhuǎn)換協(xié)議。

算法1視圖轉(zhuǎn)換協(xié)議(以g1,g2為例)

1) Check Phase

2) for node in g2do:

3) if m: is not legal ‖ timeout:

4) go to ViewChangePhase.

5) else

6) excute remote consensus.

7)

8) ViewChange Phase

9) for node in g2(representas:g2(id)) do:

10) send messageito g1(id).

11) for node in g1do:

12) receive messageifrom g2.

13) broadcast messagei.

14) after receive n-f messageido:

15) v=v+1.

3.4 請求排序與執(zhí)行

一旦所有組都接收到各組的消息請求,接下來的工作就是對收到的請求做排序并執(zhí)行。

定理3如通信可靠,且延遲有界,則每個節(jié)點最終都能收到一個請求集合

{|g∈G}

(7)

該集合包含了所有組收到的請求。

證明:在樂觀條件下,定理2保證了Remote共識能夠使非請求客戶端所在組能夠正常收到請求;而如果請求客戶端所在分組主節(jié)點發(fā)生故障或拜占庭錯誤,組間視圖轉(zhuǎn)換能夠保證共識的正常運行,即其它組仍能收到請求。最終,每個節(jié)點都能收到關(guān)于請求的集合{|g∈G}。

由于每個分組都有其編號,所以要設(shè)定唯一的請求執(zhí)行順序比較容易實現(xiàn),即根據(jù)分組編號{g1,g2,…,gG}所對應(yīng)的請求{r1,r2,…,rG}排序。由于這樣將會導(dǎo)致編號靠前的分組將一直處于高優(yōu)先級執(zhí)行,所以每進(jìn)行ρ輪共識后就對分組編號重新排序以保證各組優(yōu)先級均勻分布。

(8)

分組轉(zhuǎn)換方式如式(3)所示,每執(zhí)行ρ輪后,將分組編號依次改變,并相應(yīng)改變其請求編號。當(dāng)每組都對請求有排序后,所有節(jié)點都執(zhí)行當(dāng)前請求集合{R},每當(dāng)一個請求執(zhí)行完畢后,立即向客戶端返回執(zhí)行結(jié)果。在返回請求處理結(jié)果時,僅由對應(yīng)分組返回對應(yīng)請求結(jié)果以節(jié)省組間通信開銷。

4 仿真與分析

本文通過仿真共識,設(shè)備配置為COREi5-6300處理器,16G運行內(nèi)存,Windows10操作系統(tǒng),用編程語言通過多端口仿真多節(jié)點實現(xiàn)HotStuff算法和PBHS算法并進(jìn)行比較。仿真從通信開銷對兩個算法進(jìn)行分析,并從吞吐量,延遲兩個方面進(jìn)行仿真并對結(jié)果進(jìn)行比較。

4.1 通信開銷分析

通信開銷指達(dá)成共識的過程中所需要的通信次數(shù)總和。設(shè)系統(tǒng)中的總節(jié)點有n個,分為G組,每組m個節(jié)點,其中m滿足m≥3f+1,其中f是每個組內(nèi)所能容納的最大拜占庭節(jié)點。

對于HotStuff算法,每輪公式處理1個請求,每處理1個請求所需要的通信開銷為8Gm,處理G筆請求所需要的通信開銷為

Ch=8Gm·G=8G2m

(9)

對于PBHS算法,由于該算法分組執(zhí)行本組請求,對請求執(zhí)行結(jié)果再做組間共識,所以每次共識能夠處理G個請求,每組內(nèi)的通信開銷為8m,G組執(zhí)行G個請求,所以Local階段開銷為8Gm,G組Remote共識開銷為fG2,則PBHS整體通信開銷為

Cp=8Gm+fG2

(10)

令q為二者比值結(jié)果,則

(11)

(12)

4.2 吞吐量對比

吞吐量指在單位時間內(nèi)系統(tǒng)平均能夠處理請的數(shù)量,該值用TPS(Transaction Per Second)來表示,計算方法為

(13)

為方便仿真,分組設(shè)置為3,由客戶端發(fā)送2000次請求,并設(shè)置不同節(jié)點數(shù)分別對HotStuff和PBHS算法進(jìn)行仿真,實驗中記錄并計算得出兩算法的吞吐量,仿真結(jié)果如圖4所示。

圖4 HotStuff與PBHS吞吐量對比

從仿真結(jié)果可以看出,兩種算法隨著參與節(jié)點的增多,吞吐量均有所下降,但是PBHS算法的吞吐量整體明顯高于HotStuff算法,PBHS算法在節(jié)點總數(shù)增高的同時仍然能夠保證較高的吞吐量,該實驗說明PBHS算法整體吞吐量優(yōu)于HotStuff算法。

4.3 平均延遲對比

延遲一般指客戶端請求提交到共識完成并響應(yīng)所花費的時間,平均延遲指在進(jìn)行多次請求,對請求達(dá)成共識并執(zhí)行后的平均延遲。對PBHS算法設(shè)置分組為3,設(shè)置不同節(jié)點數(shù),對其平均延遲進(jìn)行對比分析,仿真結(jié)果如圖5所示。

圖5 PBHS與HotStuff平均延遲對比

仿真結(jié)果顯示,PBHS算法的平均延遲要低于HotStuff算法。分析可知,雖然單筆共識所進(jìn)行的共識流程要多于HotStuff,但是當(dāng)處理多個請求時,由于PBHS算法分組分別對組內(nèi)請求進(jìn)行共識,同時能夠處理請求數(shù)量多于HotStuff算法,所以平均延遲要低于HotStuff算法。

5 總結(jié)與展望

共識算法的優(yōu)劣對于區(qū)塊鏈性能的影響是至關(guān)重要的,共識算法不僅要保證區(qū)塊鏈節(jié)點間的共識的高效,更要保證在共識發(fā)生錯誤時的容錯性。本文針對HotStuff算法忽略了位置因素對于共識算法吞吐量的影響,結(jié)合基于位置分組的思想,提出了基于位置分組的HotStuff改進(jìn)算法,組內(nèi)通過HotStuff的低復(fù)雜度實現(xiàn)快速共識,組間減小了距離較遠(yuǎn)節(jié)點間的通信,每組分別處理當(dāng)?shù)卣埱?提高了整體共識算法的吞吐量。實驗結(jié)果表明,PBHF算法相較于HotStuff算法提高了一定吞吐量。在出錯情況下能夠保證共識的正常進(jìn)行。算法較于原本的HotStuff算法雖然有了一定的性能提升,但分組主節(jié)點更換將對共識過程造成消極影響,如何根據(jù)特征參數(shù)評價節(jié)點穩(wěn)定性將是本文下一步的研究方向。