基于位置的改進HotStuff共識機制與仿真

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

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

1 引言

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

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

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

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

2 HotStuff算法

2.1 算法概述

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

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

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,保證沒有更高的視圖可以使用,即保證了當前區(qū)塊是最安全的,后續(xù)共識在此基礎上展開。Leader形成HighQC后,在對應區(qū)塊的后面打包新的區(qū)塊并以prepare消息廣播。副節(jié)點收到prepare消息后,對該消息進行簽名摘要(投票)。

2.2.2 Pre-Commit階段

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

2.2.3 Commit階段

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

2.2.4 Decide階段

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

2.2 HotStuff復雜度分析

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

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

3 PBHS算法

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

3.1 算法概述

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

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

圖2 PBHS算法整體示意圖

3.2 Local共識階段

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

(1)

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

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

(2)

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

3.2.1 Local共識階段安全性分析

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

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

m=f+a,且a>x

(3)

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

(4)

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

(5)

代換得

m>3f

(6)

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

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

3.3 Remote共識階段

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

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

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

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

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

圖3 組間共識階段

3.4 組間視圖轉換

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

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

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

算法1視圖轉換協(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ā)生故障或拜占庭錯誤,組間視圖轉換能夠保證共識的正常運行,即其它組仍能收到請求。最終,每個節(jié)點都能收到關于請求的集合{|g∈G}。

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

(8)

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

4 仿真與分析

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

4.1 通信開銷分析

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

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

Ch=8Gm·G=8G2m

(9)

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

Cp=8Gm+fG2

(10)

令q為二者比值結果,則

(11)

(12)

4.2 吞吐量對比

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

(13)

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

圖4 HotStuff與PBHS吞吐量對比

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

4.3 平均延遲對比

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

圖5 PBHS與HotStuff平均延遲對比

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

5 總結與展望

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