楊 州,周創(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)價(jià)值的關(guān)鍵技術(shù)。

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

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

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

1.1 Raft算法

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

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

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

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

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

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

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

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

為了解決這些問(wèn)題,學(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]提出基于信用評(píng)分改進(jìn)Raft共識(shí)機(jī)制,利用信用評(píng)分的方式替代節(jié)點(diǎn)投票避免選舉糾紛,提高Raft選主的速度和對(duì)惡意節(jié)點(diǎn)的適應(yīng)能力;Huang等[17]在私有鏈上提出了一個(gè)Raft網(wǎng)絡(luò)分裂的模型,并利用此模型預(yù)測(cè)網(wǎng)絡(luò)分裂的時(shí)間和概率,以此優(yōu)化Raft共識(shí)算法中的參數(shù);Rong等[18]基于聯(lián)邦重構(gòu)技術(shù),對(duì)Raft節(jié)點(diǎn)特征數(shù)據(jù)集進(jìn)行訓(xùn)練、更新和評(píng)估,將性能較好的節(jié)點(diǎn)構(gòu)建為L(zhǎng)eader候選委員會(huì),提高選舉質(zhì)量和速度,還設(shè)計(jì)了半異步緩沖機(jī)制和抵御惡意節(jié)點(diǎn)攻擊的策略,解決了聯(lián)合聚合的不一致性和安全性問(wèn)題;Du等[19]提出了一種多策略Leader選舉機(jī)制,允許節(jié)點(diǎn)在認(rèn)為L(zhǎng)eader存在性能問(wèn)題時(shí)主動(dòng)觸發(fā)新一輪的Leader選舉,并在指定的優(yōu)先級(jí)隊(duì)列中替換這個(gè)Leader,該機(jī)制可以在不增加選舉時(shí)間開銷的情況下提高系統(tǒng)的吞吐量。不過(guò),以上研究對(duì)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í)證明技術(shù)所構(gòu)建的具有可驗(yàn)證功能的,非交互式的偽隨機(jī)函數(shù)。對(duì)于一個(gè)特定輸入信息m和證明者的私鑰(secret key,SK),VRF會(huì)生成一個(gè)隨機(jī)數(shù)r以及r的證明π,驗(yàn)證者可以通過(guò)m、r、π和證明者持有的公鑰(public key,PK)來(lái)驗(yàn)證r是否由PK的持有者根據(jù)m所產(chǎn)生。在這個(gè)過(guò)程中不用暴露證明者的私鑰,同時(shí)由零知識(shí)證明技術(shù)保證驗(yàn)證者除了知道“r是由PK的持有者根據(jù)m所產(chǎn)生的”這個(gè)信息外,得不到其他任何有價(jià)值的信息,保障了證明者和輸入m的安全。VRF的執(zhí)行流程如下:

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

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

π=VRF_Proof(m,SK)

(1)

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

VRF_Verify(m,π,PK)=true

(2)

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

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

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

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

可驗(yàn)證隨機(jī)函數(shù)在提出后,多用于數(shù)字簽名[20]等領(lǐng)域。隨著可驗(yàn)證隨機(jī)函數(shù)在各組件上的關(guān)鍵技術(shù)突破和區(qū)塊鏈技術(shù)的深入研究與發(fā)展,越來(lái)越多的新鏈在設(shè)計(jì)共識(shí)算法時(shí)都會(huì)引入可驗(yàn)證隨機(jī)函數(shù)來(lái)隨機(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ī)特性。不過(guò)基于RSA實(shí)現(xiàn)的VRF要起到足夠的安全性,需要RSA的密鑰長(zhǎng)度比較長(zhǎng),這點(diǎn)限制了其在很多場(chǎng)景下的應(yīng)用。而橢圓曲線加密因其密鑰長(zhǎng)度小、安全性能高,逐漸成為首選的非對(duì)稱加密實(shí)現(xiàn)方案。本實(shí)驗(yàn)的ECVRF方案設(shè)計(jì)主要包括以下3個(gè)函數(shù)部分:

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

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

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

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

輸入私鑰x,信息m,公共混淆值salt_value(一個(gè)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選擇一個(gè)隨機(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′,則通過(guò)驗(yàn)證,輸出true;否則驗(yàn)證不通過(guò),輸出false。

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

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

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

步驟1當(dāng)前系統(tǒng)利用信息m(可以為當(dāng)前時(shí)間與任期的組合)計(jì)算得到一個(gè)隨機(jī)整數(shù)值Z,Z在本輪選舉中對(duì)系統(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ā)來(lái)的信息后,將m2、π與Leader的公鑰Y輸入可驗(yàn)證隨機(jī)函數(shù)的驗(yàn)證隨機(jī)數(shù)與證明模塊函數(shù)得到c′。如果c=c′,則隨機(jī)數(shù)有效,驗(yàn)證通過(guò),則將信息中的日志項(xiàng)同步到本地?cái)?shù)據(jù)庫(kù)中,并且向Leader反饋已接受信息;否則隨機(jī)數(shù)無(wú)效,驗(yàn)證不通過(guò),不接收此日志項(xiàng),并且向Leader反饋錯(cuò)誤信息。

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

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

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

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

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

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

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

4 試驗(yàn)測(cè)試

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ù)測(cè)試

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

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

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

4.3 選主用時(shí)測(cè)試

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

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

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

4.4 腦裂情況下選主用時(shí)測(cè)試

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

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

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

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

4.5 DDOS攻擊時(shí)選主用時(shí)測(cè)試

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

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

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

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

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

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

4.6 完成共識(shí)用時(shí)測(cè)試

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

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

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

4.7 穩(wěn)定性測(cè)試

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

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

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

4.8 不同共識(shí)算法的對(duì)比

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

表3 不同共識(shí)算法在各需求場(chǎng)景下的表現(xiàn)對(duì)比

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

5 結(jié)語(yǔ)

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