融合可驗(yàn)證隨機(jī)函數(shù)的改進(jìn)Raft共識算法

楊 州,周創(chuàng)明

(空軍工程大學(xué)防空反導(dǎo)學(xué)院,西安,710051)

2008年中本聰發(fā)表《Bitcoin:A Peer-to-Peer Electronic Cash System》[1]標(biāo)志著以比特幣為代表應(yīng)用的區(qū)塊鏈技術(shù)的誕生。區(qū)塊鏈?zhǔn)敲艽a學(xué)、數(shù)學(xué)、計(jì)算機(jī)科學(xué)等多學(xué)科的交叉研究領(lǐng)域,其具有的組織體系去中心化、鏈上數(shù)據(jù)不可篡改等特性引起了學(xué)界和產(chǎn)業(yè)界的廣泛關(guān)注和研究,被認(rèn)為是實(shí)現(xiàn)互聯(lián)網(wǎng)價值的關(guān)鍵技術(shù)。

共識算法是區(qū)塊鏈底層的核心技術(shù),用于在分布式系統(tǒng)中使所有節(jié)點(diǎn)達(dá)成共識。從管理權(quán)限和數(shù)據(jù)讀寫權(quán)限角度區(qū)塊鏈可分為公有鏈、聯(lián)盟鏈和私有鏈。公有鏈?zhǔn)亲罘蠀^(qū)塊鏈最初設(shè)想的概念實(shí)現(xiàn),公有鏈系統(tǒng)中所有節(jié)點(diǎn)都可以參與到整個共識過程,是完全去中心化的。目前公有鏈的共識算法主要分為以算力競爭出塊權(quán)的工作量證明(proof of work,POW)[1]、以已持有的數(shù)字貨幣量和時間競爭出塊權(quán)的權(quán)益證明(Proof of Stake,POS)[2]和以自身擁有的權(quán)益來投票選舉代表生產(chǎn)區(qū)塊的委托權(quán)益證明(DPOS)[3]。然而正是由于公有鏈的去中心化特性,使其在隱私保護(hù)和政策監(jiān)管等方面存在天然缺陷,并不適用于大部分的社會應(yīng)用場景。與公有鏈對應(yīng)的是私有鏈,它是完全封閉的、中心化的,由某個公司或組織創(chuàng)建,記錄其內(nèi)部的數(shù)據(jù)信息,共識和數(shù)據(jù)讀取權(quán)限掌握在少數(shù)內(nèi)部節(jié)點(diǎn)手里。私有鏈的這些特性雖然保護(hù)了內(nèi)部數(shù)據(jù)的安全且在共識效率上也遠(yuǎn)遠(yuǎn)高于公有鏈和聯(lián)盟鏈,但是其封閉性也決定了它難以適用于大部分的社會應(yīng)用場景[4]。聯(lián)盟鏈介于公有鏈和私有鏈之間,即“半開放、半去中心化”,由若干公司或組織聯(lián)合創(chuàng)建,只限于聯(lián)盟成員參與[5]。數(shù)據(jù)讀取權(quán)限和共識機(jī)制等均需遵循聯(lián)盟鏈中的規(guī)定進(jìn)行運(yùn)作,并按照準(zhǔn)入規(guī)則接納外部節(jié)點(diǎn)的加入。聯(lián)盟鏈的半開放、半去中心化、規(guī)則清晰等特性,使其具有易于政策監(jiān)管、權(quán)限可控等優(yōu)勢,相比公有鏈和私有鏈,更適用于大部分的社會應(yīng)用場景。目前聯(lián)盟鏈流行的共識算法分為兩類:一類是非拜占庭容錯共識,這類共識機(jī)制不考慮惡意節(jié)點(diǎn)的攻擊行為,但可以容忍系統(tǒng)崩潰、節(jié)點(diǎn)網(wǎng)絡(luò)故障等情況,如Zookeeper[6]、Paxos[7]、Raft[8]等。另一類是拜占庭容錯[9]共識,這類共識機(jī)制會考慮惡意節(jié)點(diǎn)攻擊、故意回復(fù)虛假消息、串通作惡等情況,如Pbft共識算法[10]。選用哪類共識機(jī)制要根據(jù)具體的應(yīng)用場景,綜合考慮系統(tǒng)的復(fù)雜性與安全性進(jìn)行折中設(shè)計(jì)。

本文分析了聯(lián)盟鏈中常用的非拜占庭容錯類的共識算法——Raft共識算法中存在的安全問題和多輪選舉問題,通過引入可驗(yàn)證隨機(jī)函數(shù)(verifiable random function,VRF)[11]對原算法進(jìn)行改進(jìn),提高了RAFT算法在Leader選舉過程中的安全性和效率。

1 Raft算法與可驗(yàn)證隨機(jī)函數(shù)

1.1 Raft算法

分布式系統(tǒng)的一個關(guān)鍵問題是如何保證系統(tǒng)中各節(jié)點(diǎn)的存儲數(shù)據(jù)的一致性[12]。經(jīng)典的解決方案是利用狀態(tài)機(jī)保證數(shù)據(jù)復(fù)制的一致性。Paxos算法是Leslie Lamport于1998年提出的一種基于消息傳遞的分布式一致性算法。Paxos算法通過消息傳遞機(jī)制來就分布式網(wǎng)絡(luò)中的某個提議達(dá)成一致。算法通過一系列日志項(xiàng)的復(fù)制達(dá)成整個網(wǎng)絡(luò)的一致性,具有很快的執(zhí)行效率,但是該算法對于學(xué)習(xí)者來說非常難理解,且沒有適用的搭建實(shí)用系統(tǒng)的基礎(chǔ),因此難以在實(shí)踐中落地。為了解決這些問題,Diego Ongaro和John Ousterhout于2014年提出了Raft算法。提出Raft算法就是為了簡化Paxos算法,同時Raft算法在一致性、效率、安全等方面與Paxos算法相比基本一致。Raft系統(tǒng)中的角色有領(lǐng)導(dǎo)人(Leader)、跟隨者(Follower)和候選人(Candidate)3種。與Paxos算法相比,Raft算法增加了對日志更新方式和選舉過程的限制。首先更新日志的操作必須是連續(xù)的;其次是在Leader選舉時只有擁有最新、最全日志的節(jié)點(diǎn)才有資格被選為Leader[13]。

Raft算法達(dá)成系統(tǒng)一致性的主要工作過程如下:

1)Leader選舉。節(jié)點(diǎn)在當(dāng)選為Leader后會按照固定的時間間隔向其他Follower發(fā)送心跳日志(空的附加日志)以標(biāo)識自己在系統(tǒng)中仍正常工作。一旦有Follower在設(shè)定的時間內(nèi)沒有接收到心跳日志,即可認(rèn)為當(dāng)前任期的Leader發(fā)生了故障,Follower會轉(zhuǎn)變?yōu)镃andidate,進(jìn)行下一任期的Leader選舉。

2)日志復(fù)制。成功選舉出Leader后,客戶端將請求發(fā)送到系統(tǒng)中的任一節(jié)點(diǎn)。若Leader接收到請求,則將該日志復(fù)制到系統(tǒng)中的所有Follower節(jié)點(diǎn);若Follower接收到請求,則會將該請求轉(zhuǎn)發(fā)給Leader,確保始終只由Leader與客戶端交互。在日志復(fù)制過程中,如果Follower節(jié)點(diǎn)崩潰、運(yùn)行緩慢或網(wǎng)絡(luò)丟包,Leader會不斷地重試直到所有的Follower最終都存儲了最全、最新的日志條目。最后由Leader將執(zhí)行結(jié)果返回給客戶端。

3)安全性。Raft算法的安全性主要體現(xiàn)在節(jié)點(diǎn)狀態(tài)機(jī)安全方面。在系統(tǒng)中如果有任何一個節(jié)點(diǎn)已經(jīng)應(yīng)用了一個確定的日志條目到它的狀態(tài)機(jī)中,那么其他節(jié)點(diǎn)就不能在同一個日志索引位置應(yīng)用一個不同的指令。

Raft算法中節(jié)點(diǎn)3種角色狀態(tài)的轉(zhuǎn)換如圖1所示。

圖1 Raft算法中角色轉(zhuǎn)換示意圖

但是這樣的執(zhí)行過程也存在問題:①可能會導(dǎo)致在選舉中產(chǎn)生投票分歧,即多個Candidate獲得了相同且均是最高的票數(shù),這樣系統(tǒng)就不會選出唯一的Leader,只能宣告本次選舉失敗,然后將任期加1,重新發(fā)起選舉。Raft算法為了解決這個問題采用了隨機(jī)的選舉超時時間策略,具體為Candidate會在固定的時間區(qū)間內(nèi)隨機(jī)選擇選舉的超時時間,這樣可以保證通常只會有1個Candidate發(fā)生選舉超時,進(jìn)而向其他節(jié)點(diǎn)請求選票,且保證在其他節(jié)點(diǎn)發(fā)生超時前贏得選舉,并發(fā)送心跳包。然而隨著系統(tǒng)的節(jié)點(diǎn)數(shù)增多,各節(jié)點(diǎn)隨機(jī)的超時時間重復(fù)的幾率也會增加,仍然會存在投票分歧問題,導(dǎo)致要進(jìn)行多輪選舉才會有Leader當(dāng)選。這會使選舉過程的通信量和時間增加,影響系統(tǒng)運(yùn)行效率。②Raft算法在選舉出Leader后會不斷向其他節(jié)點(diǎn)發(fā)送心跳日志,頻繁的節(jié)點(diǎn)間通信可能會使Leader節(jié)點(diǎn)的身份暴露給惡意節(jié)點(diǎn),招致惡意攻擊,如分布式拒絕服務(wù)攻擊(distributed denial of service,DDoS)[14]。

為了解決這些問題,學(xué)者們進(jìn)行了許多研究。榮寶俊等[15]提出了FL＿Raft模型,基于聯(lián)邦學(xué)習(xí)技術(shù)篩選出高性能節(jié)點(diǎn)組并根據(jù)權(quán)益值計(jì)算出唯一不變的領(lǐng)導(dǎo)者節(jié)點(diǎn),提高了集群的效率和穩(wěn)定性;鄒賢等[16]提出基于信用評分改進(jìn)Raft共識機(jī)制,利用信用評分的方式替代節(jié)點(diǎn)投票避免選舉糾紛,提高Raft選主的速度和對惡意節(jié)點(diǎn)的適應(yīng)能力;Huang等[17]在私有鏈上提出了一個Raft網(wǎng)絡(luò)分裂的模型,并利用此模型預(yù)測網(wǎng)絡(luò)分裂的時間和概率,以此優(yōu)化Raft共識算法中的參數(shù);Rong等[18]基于聯(lián)邦重構(gòu)技術(shù),對Raft節(jié)點(diǎn)特征數(shù)據(jù)集進(jìn)行訓(xùn)練、更新和評估,將性能較好的節(jié)點(diǎn)構(gòu)建為Leader候選委員會,提高選舉質(zhì)量和速度,還設(shè)計(jì)了半異步緩沖機(jī)制和抵御惡意節(jié)點(diǎn)攻擊的策略,解決了聯(lián)合聚合的不一致性和安全性問題;Du等[19]提出了一種多策略Leader選舉機(jī)制,允許節(jié)點(diǎn)在認(rèn)為Leader存在性能問題時主動觸發(fā)新一輪的Leader選舉,并在指定的優(yōu)先級隊(duì)列中替換這個Leader,該機(jī)制可以在不增加選舉時間開銷的情況下提高系統(tǒng)的吞吐量。不過,以上研究對Raft算法的安全性方面關(guān)注較少,本文將進(jìn)一步討論如何借助可驗(yàn)證隨機(jī)函數(shù)提高RAFT算法的安全性和運(yùn)行效率。

1.2 可驗(yàn)證隨機(jī)函數(shù)

1999年Silvio Micali等[10](verifiable random functions,VRF),提出可驗(yàn)證隨機(jī)函數(shù)。VRF是基于公私鑰密碼學(xué)和零知識證明技術(shù)所構(gòu)建的具有可驗(yàn)證功能的,非交互式的偽隨機(jī)函數(shù)。對于一個特定輸入信息m和證明者的私鑰(secret key,SK),VRF會生成一個隨機(jī)數(shù)r以及r的證明π,驗(yàn)證者可以通過m、r、π和證明者持有的公鑰(public key,PK)來驗(yàn)證r是否由PK的持有者根據(jù)m所產(chǎn)生。在這個過程中不用暴露證明者的私鑰,同時由零知識證明技術(shù)保證驗(yàn)證者除了知道“r是由PK的持有者根據(jù)m所產(chǎn)生的”這個信息外,得不到其他任何有價值的信息,保障了證明者和輸入m的安全。VRF的執(zhí)行流程如下:

1)用戶首先通過非對稱加密算法申請一組公私鑰對(PK,SK),PK為公鑰,SK為私鑰。

2)傳入m和SK,VRF_Proof函數(shù)會生成一個r和一個可對r進(jìn)行零知識證明的π。

π=VRF_Proof(m,SK)

(1)

3)VRF_Verify函數(shù)通過m、π和PK驗(yàn)證該證明π是否由原始輸入m和證明人的PK所產(chǎn)生的,是返回true,否返回false。

VRF_Verify(m,π,PK)=true

(2)

VRF具備以下3個性質(zhì):

1)可驗(yàn)證性。驗(yàn)證者通過π可以驗(yàn)證出r是由m和證明者SK所生成的;

2)隨機(jī)性。在不確定π的情況下,r和其他任意一個隨機(jī)數(shù)對于攻擊者來說是不可區(qū)分的;

3)確定性。VRF在π和SK不變的情況下,輸出的r也是不變的。

可驗(yàn)證隨機(jī)函數(shù)在提出后,多用于數(shù)字簽名[20]等領(lǐng)域。隨著可驗(yàn)證隨機(jī)函數(shù)在各組件上的關(guān)鍵技術(shù)突破和區(qū)塊鏈技術(shù)的深入研究與發(fā)展,越來越多的新鏈在設(shè)計(jì)共識算法時都會引入可驗(yàn)證隨機(jī)函數(shù)來隨機(jī)抽取節(jié)點(diǎn),從而達(dá)到隱藏關(guān)鍵節(jié)點(diǎn)的目的,降低被惡意節(jié)點(diǎn)攻擊風(fēng)險(xiǎn)。

2 試驗(yàn)方案設(shè)計(jì)

本節(jié)按照實(shí)際中的系統(tǒng)應(yīng)用詳細(xì)設(shè)計(jì)了VRF方案和融合了VRF的改進(jìn)Raft算法流程。

2.1 VRF方案設(shè)計(jì)

本試驗(yàn)的VRF方案是按照IETF擬定的VRF標(biāo)準(zhǔn)草案[21]設(shè)計(jì)的。草案的實(shí)現(xiàn)方案有2套體系,一套是基于RSA算法的(RSA full domain Hash VRF,RSA-FDH-VRF),另一套是基于橢圓曲線的(elliptic curve verifiable random function,ECVRF)。2套實(shí)現(xiàn)體系都能滿足可信唯一、可信防碰撞和完全偽隨機(jī)特性。不過基于RSA實(shí)現(xiàn)的VRF要起到足夠的安全性,需要RSA的密鑰長度比較長,這點(diǎn)限制了其在很多場景下的應(yīng)用。而橢圓曲線加密因其密鑰長度小、安全性能高,逐漸成為首選的非對稱加密實(shí)現(xiàn)方案。本實(shí)驗(yàn)的ECVRF方案設(shè)計(jì)主要包括以下3個函數(shù)部分:

1)生成一組公私鑰對。設(shè)橢圓曲線在有限域F上,階數(shù)為素?cái)?shù)n,取橢圓曲線上一點(diǎn)O,公私鑰對生成算法如下:

步驟1選擇一個隨機(jī)數(shù)x,0

步驟2生成一對非對稱密鑰,其中私鑰即為x,公鑰為Y=xO(這里的乘法不是常用的系數(shù)與坐標(biāo)乘法,而是橢圓曲線上對應(yīng)的乘法規(guī)則)

2)生成隨機(jī)數(shù)及其證明。

輸入私鑰x,信息m,公共混淆值salt_value(一個8位字符串,在輸入內(nèi)容的任意位置插入用于加強(qiáng)安全性,如果輸入的密碼套件已經(jīng)實(shí)現(xiàn)了該部分則可不使用此值)。

輸出隨機(jī)數(shù)r,證明π。

步驟1使用f1()將信息m映射到橢圓曲線上一點(diǎn):

H=f1(salt_value,m)

(3)

步驟2使用f2()函數(shù)將H轉(zhuǎn)換為字符串:

h=f2(H)

(4)

步驟3選擇一個隨機(jī)數(shù)x,0

步驟4隨機(jī)數(shù)r由函數(shù)nonce_generation(x,h)生成;

步驟5使用f3()函數(shù)得到整數(shù)

c=f3(Y,H,β,rO,rH)

(5)

步驟6計(jì)算:

s=r-cxmodn

(6)

步驟7使用拼接函數(shù)將(f2(β),f4(c,cLen),f4(s,nLen))拼接得到證明π(nLen取值為滿足 2^(8nLen)>n的最小整數(shù),cLen的取值是nLen/2或者接近它)。

3)驗(yàn)證隨機(jī)數(shù)及其證明。

輸入公鑰Y,信息m,證明π,公共混淆值salt_value;

輸出正確性(true or false)。

步驟1使用f1()將信息m映射到橢圓曲線上一點(diǎn):

H=f1(salt-value,m)

(7)

步驟2計(jì)算:

u=cO+sY

(8)

v=cβ+sH

(9)

步驟3使用f3()函數(shù)得到整數(shù):

c′=f3(Y,H,β,u,v)

(10)

步驟4如果c=c′,則通過驗(yàn)證,輸出true;否則驗(yàn)證不通過,輸出false。

表1 VRF方案設(shè)計(jì)中各公共函數(shù)及其作用

2.2 改進(jìn)Raft算法設(shè)計(jì)

原Raft算法的問題一方面在于Leader選舉完成后要不斷向其他節(jié)點(diǎn)發(fā)送心跳日志,這樣可能會導(dǎo)致Leader身份暴露給攻擊者,另一方面節(jié)點(diǎn)數(shù)量增多會增加產(chǎn)生投票分歧的概率而影響系統(tǒng)效率。針對以上問題,本實(shí)驗(yàn)利用可驗(yàn)證隨機(jī)函數(shù)生成的隨機(jī)數(shù)以及工作過程中的非交互式特性來改進(jìn)原算法。改進(jìn)算法的流程設(shè)計(jì)如下:

步驟1當(dāng)前系統(tǒng)利用信息m(可以為當(dāng)前時間與任期的組合)計(jì)算得到一個隨機(jī)整數(shù)值Z,Z在本輪選舉中對系統(tǒng)的所有節(jié)點(diǎn)都是可見且唯一的。

步驟2選舉開始,系統(tǒng)中的節(jié)點(diǎn)按照隨機(jī)順序利用信息m2計(jì)算得到隨機(jī)整數(shù)Z′,比較Z與Z′的大小。若Z′Z,不滿足條件,由下一節(jié)點(diǎn)重新執(zhí)行步驟2。

步驟3滿足條件的當(dāng)前節(jié)點(diǎn)即是本輪選中的Leader。Leader首先將Z′與自己的私鑰輸入可驗(yàn)證隨機(jī)函數(shù)的生成隨機(jī)數(shù)與證明模塊函數(shù),得到r和π,再將需要給其他節(jié)點(diǎn)驗(yàn)證的必要參數(shù)Y,m2,π和本輪要更新的日志項(xiàng)一起廣播給系統(tǒng)中所有Follower節(jié)點(diǎn)。

步驟4Follower在收到Leader發(fā)來的信息后,將m2、π與Leader的公鑰Y輸入可驗(yàn)證隨機(jī)函數(shù)的驗(yàn)證隨機(jī)數(shù)與證明模塊函數(shù)得到c′。如果c=c′,則隨機(jī)數(shù)有效,驗(yàn)證通過,則將信息中的日志項(xiàng)同步到本地?cái)?shù)據(jù)庫中,并且向Leader反饋已接受信息;否則隨機(jī)數(shù)無效,驗(yàn)證不通過,不接收此日志項(xiàng),并且向Leader反饋錯誤信息。

步驟5Leader在收到大部分Follower的接受信息后即可向客戶端反饋日志寫入成功,本輪日志復(fù)制完成,下一輪從步驟1開始重復(fù)執(zhí)行所有流程。

改進(jìn)方案流程圖如圖2所示。

3 改進(jìn)方案分析

3.1 系統(tǒng)安全性分析

Raft算法通過在Leader選舉時增加一些限制來增強(qiáng)安全性,并且給出了領(lǐng)導(dǎo)人完整特性(leader completeness property)[8]的簡要證明,保證了每一個狀態(tài)機(jī)會按照相同的順序執(zhí)行相同的指令。前文設(shè)計(jì)的改進(jìn)算法利用可驗(yàn)證隨機(jī)函數(shù)產(chǎn)生的隨機(jī)數(shù)來確定哪個節(jié)點(diǎn)被選為Leader,同時由于可驗(yàn)證隨機(jī)函數(shù)的非交互性,Follower在收到復(fù)制指令前并不會知道當(dāng)前系統(tǒng)的Leader具體是哪個節(jié)點(diǎn)。當(dāng)Follower收到Leader的日志復(fù)制指令后則會根據(jù)指令來源節(jié)點(diǎn)給出的VRF證明通過驗(yàn)證函數(shù)得到結(jié)果,由算法保證得到驗(yàn)證結(jié)果就立即判斷是否接受最新日志。當(dāng)結(jié)果為true則將最新日志同步到本地?cái)?shù)據(jù)庫中并且向Leader反饋已同步信息;結(jié)果為false則不接收此日志項(xiàng)并且向Leader反饋未通過驗(yàn)證信息。Leader在收到大多數(shù)節(jié)點(diǎn)的同步信息后給客戶端返回寫入成功的信息,此輪日志復(fù)制結(jié)束。通過上述策略可以在日志復(fù)制操作前隱藏Leader節(jié)點(diǎn)的身份,增強(qiáng)系統(tǒng)的安全性。

3.2 系統(tǒng)穩(wěn)定性分析

Raft算法在系統(tǒng)發(fā)生網(wǎng)絡(luò)分割(network partiton)時會造成腦裂(brain split)問題。系統(tǒng)中路由節(jié)點(diǎn)或者某些節(jié)點(diǎn)在網(wǎng)絡(luò)故障的情況下,會將系統(tǒng)分割成若干個彼此獨(dú)立的集群,而在選舉超時后擁有多數(shù)節(jié)點(diǎn)的集群會產(chǎn)生新的Leader,導(dǎo)致系統(tǒng)中存在多位Leader的情況,出現(xiàn)腦裂問題,如圖3所示。腦裂問題可能會導(dǎo)致數(shù)據(jù)的覆蓋丟失。Raft算法通過任期(Term)屬性來解決這個問題,Term初始設(shè)為1,此后每次選舉出新Leader則Term加1。同時規(guī)定每輪任期只能有一個Leader。這樣在發(fā)生網(wǎng)絡(luò)分割情況下,節(jié)點(diǎn)多的集群產(chǎn)生新的Leader的任期必定比其他集群Leader的任期大,而且其他集群的Leader即使收到客戶端的寫請求并將日志復(fù)制到其他節(jié)點(diǎn)后也會因?yàn)榈貌坏酱蠖鄶?shù)節(jié)點(diǎn)的回應(yīng)而無法告知客戶端寫入成功。在這樣的策略下,當(dāng)網(wǎng)絡(luò)被修復(fù)后,其他集群的節(jié)點(diǎn)包括Leader節(jié)點(diǎn)會發(fā)現(xiàn)系統(tǒng)中存在任期更大的Leader,則都會轉(zhuǎn)為Follower并同步當(dāng)前系統(tǒng)的最新最全日志數(shù)據(jù)。本文的試驗(yàn)保留了Raft節(jié)點(diǎn)的任期屬性以及在選舉Leader時的限制條件,所以改進(jìn)后的試驗(yàn)方案能保證在出現(xiàn)網(wǎng)絡(luò)分割情況下系統(tǒng)仍然穩(wěn)定。

4 試驗(yàn)測試

4.1 試驗(yàn)環(huán)境介紹

試驗(yàn)環(huán)境為Windows 10操作系統(tǒng);AMD Ryzen 5 600 H,3.30 GHz;內(nèi)存為16 GB,DDR4;2 T固態(tài)硬盤;使用Golang1.17實(shí)現(xiàn)系統(tǒng)的業(yè)務(wù)邏輯;可驗(yàn)證隨機(jī)函數(shù)實(shí)現(xiàn)方面基于Golang的crypto包,橢圓曲線采用ed25519,Hash函數(shù)采用sha-256以及sha-512。

4.2 可驗(yàn)證隨機(jī)函數(shù)測試

試驗(yàn)首先對VRF進(jìn)行性能測試,本試驗(yàn)實(shí)現(xiàn)的VRF主要包括3個模塊:生成公私鑰對、生成隨機(jī)數(shù)及其證明、驗(yàn)證隨機(jī)數(shù)及其證明。VRF各模塊的算法運(yùn)行時間如表2所示。

表2 VRF各模塊的算法運(yùn)行時間

由測試結(jié)果可以看出,本試驗(yàn)設(shè)計(jì)的VRF各模塊算法的運(yùn)行時間都在ms級。將這樣時間消耗的算法添加在Raft算法的Leader選舉過程中,不會增加原算法時間上的復(fù)雜度。

4.3 選主用時測試

對系統(tǒng)存在50～200節(jié)點(diǎn)分別進(jìn)行選主時間測試,測試結(jié)果見圖4所示。

圖4 原算法與改進(jìn)算法選主時間對比

由圖4可知,原Raft算法和本試驗(yàn)改進(jìn)的Raft算法在節(jié)點(diǎn)增多的情況下選主用時都是逐漸上升的。但在節(jié)點(diǎn)增多的情況下原算法更有可能出現(xiàn)因投票分歧而影響系統(tǒng)的執(zhí)行效率的問題。在節(jié)點(diǎn)越來越多的情況下,改進(jìn)后的算法選主用時比原Raft算法越來越少的原因在于規(guī)避了原算法可能出現(xiàn)的因投票分歧而導(dǎo)致選舉超時重新進(jìn)行選舉的問題,因此,在系統(tǒng)節(jié)點(diǎn)越來越多時改進(jìn)的Raft算法執(zhí)行效率會越來越高。

4.4 腦裂情況下選主用時測試

使用Mininet搭建了仿真網(wǎng)絡(luò),在該仿真網(wǎng)絡(luò)中對系統(tǒng)可能會出現(xiàn)的腦裂情況進(jìn)行模擬,并分別對原Raft算法和改進(jìn)后的Raft算法在腦裂情況下選主用時進(jìn)行測試,測試結(jié)果見圖5。

圖5 原算法與改進(jìn)算法在腦裂情況下的選主時間對比

由圖5可知,整體的選主時間較沒發(fā)生腦裂情況時提高了許多,這是由于網(wǎng)絡(luò)正常運(yùn)行時,Raft 算法中的候選人能夠相互交流,并通過投票來選舉出新的 Leader。然而,在腦裂的情況下,可能會出現(xiàn)分區(qū)中的候選人無法與其他分區(qū)中的節(jié)點(diǎn)進(jìn)行通信的問題,會導(dǎo)致無法達(dá)成多數(shù)選票,無法選舉出 Leader。具體來說,如果一個候選人發(fā)送選舉請求并等待投票,但沒有足夠的節(jié)點(diǎn)能夠響應(yīng)其請求,那么該候選人將無法獲得多數(shù)選票,選舉將無法完成。在這種情況下,Raft 算法會等待一段時間,然后重試選舉過程,直到有足夠的節(jié)點(diǎn)能夠參與選舉。因此,腦裂會導(dǎo)致選舉 Leader 的時間延長,具體取決于發(fā)生腦裂情況的程度和持續(xù)時間。

而原Raft算法和改進(jìn)后的Raft算法在腦裂情況下的不同節(jié)點(diǎn)數(shù)的選主用時很接近的原因是每個節(jié)點(diǎn)的選舉超時時間是隨機(jī)生成的,并且每個節(jié)點(diǎn)都會在超時后成為候選人并廣播選舉請求。如果腦裂情況發(fā)生,節(jié)點(diǎn)之間的通信可能會受到影響,導(dǎo)致某些節(jié)點(diǎn)無法接收到其他節(jié)點(diǎn)的選舉請求,這些節(jié)點(diǎn)將不會投票給其他節(jié)點(diǎn),并且不會增加任何節(jié)點(diǎn)的票數(shù)。因此,因?yàn)槊總€節(jié)點(diǎn)都是獨(dú)立進(jìn)行選舉的,即使節(jié)點(diǎn)數(shù)量不同,每個節(jié)點(diǎn)的選舉用時也差不多。另外,節(jié)點(diǎn)之間的通信也受到了網(wǎng)絡(luò)分區(qū)的模擬,這意味著有些節(jié)點(diǎn)可能無法與其他節(jié)點(diǎn)進(jìn)行通信。這會導(dǎo)致節(jié)點(diǎn)無法接收到其他節(jié)點(diǎn)的心跳消息,從而無法成為領(lǐng)導(dǎo)者。因此,即使節(jié)點(diǎn)數(shù)量不同,選舉用時也可能相似。

4.5 DDOS攻擊時選主用時測試

同樣的,我們在仿真網(wǎng)絡(luò)中模擬了DDOS攻擊,并分別測試了原Raft算法和改進(jìn)后的Raft算法在DDOS攻擊下的表現(xiàn),測試結(jié)果見圖6。

圖6 原算法與改進(jìn)算法完成共識時間對比

由圖6可知,改進(jìn)后的Raft算法在DDOS攻擊下明顯比原Raft算法表現(xiàn)更優(yōu),主要原因有:

1)提高了選主過程的效率。改進(jìn)后的 Raft 算法引入了可驗(yàn)證隨機(jī)函數(shù),使選主過程更高效?？沈?yàn)證隨機(jī)函數(shù)可以幫助減少選舉過程中的不必要的消息傳輸和等待時間,從而降低了選主所需的時間。

2)降低了網(wǎng)絡(luò)傳輸負(fù)載。DDoS 攻擊可能會導(dǎo)致網(wǎng)絡(luò)擁塞,使得消息傳輸延遲增加。改進(jìn)后的 RAFT算法通過在選舉過程中減少消息傳輸?shù)臄?shù)量,減輕網(wǎng)絡(luò)傳輸負(fù)載,進(jìn)而減少選主的用時。

3)提高消息認(rèn)證和安全性。通過引入可驗(yàn)證隨機(jī)函數(shù),增加了消息認(rèn)證和安全性,因?yàn)榭沈?yàn)證隨機(jī)函數(shù)可以幫助驗(yàn)證消息的真實(shí)性和完整性。這可以防止攻擊者發(fā)送偽造的消息來破壞Raft算法的正常運(yùn)行。

4.6 完成共識用時測試

分別對系統(tǒng)存在50～200節(jié)點(diǎn)進(jìn)行共識完成時間測試,測試結(jié)果見圖7。

圖7 原算法與改進(jìn)算法完成共識時間對比

由圖7可知,原Raft算法和本實(shí)驗(yàn)改進(jìn)的Raft算法在節(jié)點(diǎn)增多的情況下完成共識用時同樣是逐漸上升的。第4.6節(jié)中試驗(yàn)用時與第4.3節(jié)試驗(yàn)用時相差不大,這也符合在第4.2節(jié)測試出的VRF各模塊用時很少的結(jié)果,符合試驗(yàn)的總體預(yù)期。這里要注意的是,本節(jié)完成共識用時不是指所有日志復(fù)制成功所用時間,而是系統(tǒng)內(nèi)節(jié)點(diǎn)驗(yàn)證通過了Leader發(fā)送的身份驗(yàn)證信息且沒有錯誤反饋所用的時間。后續(xù)的日志復(fù)制等操作所用時間受各節(jié)點(diǎn)的網(wǎng)絡(luò)環(huán)境和設(shè)備性能等因素的影響。

4.7 穩(wěn)定性測試

分布式系統(tǒng)由于各個節(jié)點(diǎn)間都是獨(dú)立的,經(jīng)常會遇到某個節(jié)點(diǎn)或一群節(jié)點(diǎn)因?yàn)楦鞣N原因而失去聯(lián)系的情況,所以設(shè)計(jì)算法也需要對系統(tǒng)進(jìn)行可靠性測試。本實(shí)驗(yàn)分別測試了有5個節(jié)點(diǎn)和10個節(jié)點(diǎn)的系統(tǒng)中若干節(jié)點(diǎn)失聯(lián)情況下系統(tǒng)的可靠性,測試結(jié)果見圖8。

圖8 系統(tǒng)穩(wěn)定性測試

試驗(yàn)測試了系統(tǒng)在失去若干節(jié)點(diǎn)聯(lián)系情況下的運(yùn)行狀態(tài),測試了從失去聯(lián)系到節(jié)點(diǎn)重聯(lián)所用的時間。這里的實(shí)驗(yàn)結(jié)果與是否應(yīng)用可驗(yàn)證隨機(jī)函數(shù)并無關(guān)聯(lián),實(shí)驗(yàn)設(shè)計(jì)此部分是為了驗(yàn)證加入可驗(yàn)證隨機(jī)函數(shù)是否會影響系統(tǒng)的穩(wěn)定性。結(jié)果表明系統(tǒng)在失去若干節(jié)點(diǎn)聯(lián)系到節(jié)點(diǎn)重聯(lián)的過程中仍能保持穩(wěn)定的運(yùn)行狀態(tài)。

4.8 不同共識算法的對比

設(shè)計(jì)各種共識算法是為了適應(yīng)不同的應(yīng)用場景,表3為聯(lián)盟鏈中常用的共識算法在各需求場景下的表現(xiàn)比較。

表3 不同共識算法在各需求場景下的表現(xiàn)對比

由表3可知,本文通過在Raft算法中引入可驗(yàn)證隨機(jī)函數(shù),在保留了原Raft算法優(yōu)點(diǎn)的基礎(chǔ)上減少了選舉過程中信息通信量,減輕了網(wǎng)絡(luò)流量負(fù)載,并且利用可驗(yàn)證隨機(jī)函數(shù)的加密與解密機(jī)制幫助驗(yàn)證消息的真實(shí)性和完整性,提高了系統(tǒng)的整體可靠性。本文改進(jìn)后的Raft算法在非拜占庭容錯類共識算法中綜合表現(xiàn)最優(yōu)。

5 結(jié)語

本文分析了目前聯(lián)盟鏈常用的Raft算法在運(yùn)行過程中存在的安全隱患,在保留原算法系統(tǒng)安全性和穩(wěn)定性的前提下利用可驗(yàn)證隨機(jī)函數(shù)的隨機(jī)性、非交互性和零知識證明技術(shù)對算法進(jìn)行改進(jìn)。在選舉Leader過程中隱藏關(guān)鍵節(jié)點(diǎn)的身份來提高安全性并且規(guī)避了原算法中存在的因投票分歧導(dǎo)致的選舉超時問題。通過詳細(xì)的試驗(yàn)和分析結(jié)果表明,改進(jìn)后的Raft算法具有更高的安全性和可靠性,在系統(tǒng)的選主用時、完成共識用時等方面也都有更優(yōu)秀的表現(xiàn)。通過對比其他共識算法表明本文算法在非拜占庭容錯類共識算法中綜合表現(xiàn)最優(yōu)。但是試驗(yàn)設(shè)計(jì)在整體性考慮上還有一些局限,不僅要考慮選主過程的改進(jìn),還需要對日志復(fù)制過程也有響應(yīng)改進(jìn)。未來的工作將進(jìn)一步對可驗(yàn)證隨機(jī)函數(shù)對Raft算法整體的改進(jìn)效果進(jìn)行研究,并且使用更多的安全方法進(jìn)一步提高系統(tǒng)的安全性和可靠性。