融合可驗證隨機函數的改進Raft共識算法

楊 州,周創明

(空軍工程大學防空反導學院,西安,710051)

2008年中本聰發表《Bitcoin:A Peer-to-Peer Electronic Cash System》[1]標志著以比特幣為代表應用的區塊鏈技術的誕生。區塊鏈是密碼學、數學、計算機科學等多學科的交叉研究領域,其具有的組織體系去中心化、鏈上數據不可篡改等特性引起了學界和產業界的廣泛關注和研究,被認為是實現互聯網價值的關鍵技術。

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

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

1 Raft算法與可驗證隨機函數

1.1 Raft算法

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

Raft算法達成系統一致性的主要工作過程如下:

1)Leader選舉。節點在當選為Leader后會按照固定的時間間隔向其他Follower發送心跳日志(空的附加日志)以標識自己在系統中仍正常工作。一旦有Follower在設定的時間內沒有接收到心跳日志,即可認為當前任期的Leader發生了故障,Follower會轉變為Candidate,進行下一任期的Leader選舉。

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

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

Raft算法中節點3種角色狀態的轉換如圖1所示。

圖1 Raft算法中角色轉換示意圖

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

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

1.2 可驗證隨機函數

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

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

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

π=VRF_Proof(m,SK)

(1)

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

VRF_Verify(m,π,PK)=true

(2)

VRF具備以下3個性質:

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

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

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

可驗證隨機函數在提出后,多用于數字簽名[20]等領域。隨著可驗證隨機函數在各組件上的關鍵技術突破和區塊鏈技術的深入研究與發展,越來越多的新鏈在設計共識算法時都會引入可驗證隨機函數來隨機抽取節點,從而達到隱藏關鍵節點的目的,降低被惡意節點攻擊風險。

2 試驗方案設計

本節按照實際中的系統應用詳細設計了VRF方案和融合了VRF的改進Raft算法流程。

2.1 VRF方案設計

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

1)生成一組公私鑰對。設橢圓曲線在有限域F上,階數為素數n,取橢圓曲線上一點O,公私鑰對生成算法如下:

步驟1選擇一個隨機數x,0

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

2)生成隨機數及其證明。

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

輸出隨機數r,證明π。

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

H=f1(salt_value,m)

(3)

步驟2使用f2()函數將H轉換為字符串:

h=f2(H)

(4)

步驟3選擇一個隨機數x,0

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

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

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

(5)

步驟6計算:

s=r-cxmodn

(6)

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

3)驗證隨機數及其證明。

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

輸出正確性(true or false)。

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

H=f1(salt-value,m)

(7)

步驟2計算:

u=cO+sY

(8)

v=cβ+sH

(9)

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

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

(10)

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

表1 VRF方案設計中各公共函數及其作用

2.2 改進Raft算法設計

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

步驟1當前系統利用信息m(可以為當前時間與任期的組合)計算得到一個隨機整數值Z,Z在本輪選舉中對系統的所有節點都是可見且唯一的。

步驟2選舉開始,系統中的節點按照隨機順序利用信息m2計算得到隨機整數Z′,比較Z與Z′的大小。若Z′Z,不滿足條件,由下一節點重新執行步驟2。

步驟3滿足條件的當前節點即是本輪選中的Leader。Leader首先將Z′與自己的私鑰輸入可驗證隨機函數的生成隨機數與證明模塊函數,得到r和π,再將需要給其他節點驗證的必要參數Y,m2,π和本輪要更新的日志項一起廣播給系統中所有Follower節點。

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

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

改進方案流程圖如圖2所示。

3 改進方案分析

3.1 系統安全性分析

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

3.2 系統穩定性分析

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

4 試驗測試

4.1 試驗環境介紹

試驗環境為Windows 10操作系統;AMD Ryzen 5 600 H,3.30 GHz;內存為16 GB,DDR4;2 T固態硬盤;使用Golang1.17實現系統的業務邏輯;可驗證隨機函數實現方面基于Golang的crypto包,橢圓曲線采用ed25519,Hash函數采用sha-256以及sha-512。

4.2 可驗證隨機函數測試

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

表2 VRF各模塊的算法運行時間

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

4.3 選主用時測試

對系統存在50～200節點分別進行選主時間測試,測試結果見圖4所示。

圖4 原算法與改進算法選主時間對比

由圖4可知,原Raft算法和本試驗改進的Raft算法在節點增多的情況下選主用時都是逐漸上升的。但在節點增多的情況下原算法更有可能出現因投票分歧而影響系統的執行效率的問題。在節點越來越多的情況下,改進后的算法選主用時比原Raft算法越來越少的原因在于規避了原算法可能出現的因投票分歧而導致選舉超時重新進行選舉的問題,因此,在系統節點越來越多時改進的Raft算法執行效率會越來越高。

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

使用Mininet搭建了仿真網絡,在該仿真網絡中對系統可能會出現的腦裂情況進行模擬,并分別對原Raft算法和改進后的Raft算法在腦裂情況下選主用時進行測試,測試結果見圖5。

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

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

而原Raft算法和改進后的Raft算法在腦裂情況下的不同節點數的選主用時很接近的原因是每個節點的選舉超時時間是隨機生成的,并且每個節點都會在超時后成為候選人并廣播選舉請求。如果腦裂情況發生,節點之間的通信可能會受到影響,導致某些節點無法接收到其他節點的選舉請求,這些節點將不會投票給其他節點,并且不會增加任何節點的票數。因此,因為每個節點都是獨立進行選舉的,即使節點數量不同,每個節點的選舉用時也差不多。另外,節點之間的通信也受到了網絡分區的模擬,這意味著有些節點可能無法與其他節點進行通信。這會導致節點無法接收到其他節點的心跳消息,從而無法成為領導者。因此,即使節點數量不同,選舉用時也可能相似。

4.5 DDOS攻擊時選主用時測試

同樣的,我們在仿真網絡中模擬了DDOS攻擊,并分別測試了原Raft算法和改進后的Raft算法在DDOS攻擊下的表現,測試結果見圖6。

圖6 原算法與改進算法完成共識時間對比

由圖6可知,改進后的Raft算法在DDOS攻擊下明顯比原Raft算法表現更優,主要原因有:

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

2)降低了網絡傳輸負載。DDoS 攻擊可能會導致網絡擁塞,使得消息傳輸延遲增加。改進后的 RAFT算法通過在選舉過程中減少消息傳輸的數量,減輕網絡傳輸負載,進而減少選主的用時。

3)提高消息認證和安全性。通過引入可驗證隨機函數,增加了消息認證和安全性,因為可驗證隨機函數可以幫助驗證消息的真實性和完整性。這可以防止攻擊者發送偽造的消息來破壞Raft算法的正常運行。

4.6 完成共識用時測試

分別對系統存在50～200節點進行共識完成時間測試,測試結果見圖7。

圖7 原算法與改進算法完成共識時間對比

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

4.7 穩定性測試

分布式系統由于各個節點間都是獨立的,經常會遇到某個節點或一群節點因為各種原因而失去聯系的情況,所以設計算法也需要對系統進行可靠性測試。本實驗分別測試了有5個節點和10個節點的系統中若干節點失聯情況下系統的可靠性,測試結果見圖8。

圖8 系統穩定性測試

試驗測試了系統在失去若干節點聯系情況下的運行狀態,測試了從失去聯系到節點重聯所用的時間。這里的實驗結果與是否應用可驗證隨機函數并無關聯,實驗設計此部分是為了驗證加入可驗證隨機函數是否會影響系統的穩定性。結果表明系統在失去若干節點聯系到節點重聯的過程中仍能保持穩定的運行狀態。

4.8 不同共識算法的對比

設計各種共識算法是為了適應不同的應用場景,表3為聯盟鏈中常用的共識算法在各需求場景下的表現比較。

表3 不同共識算法在各需求場景下的表現對比

由表3可知,本文通過在Raft算法中引入可驗證隨機函數,在保留了原Raft算法優點的基礎上減少了選舉過程中信息通信量,減輕了網絡流量負載,并且利用可驗證隨機函數的加密與解密機制幫助驗證消息的真實性和完整性,提高了系統的整體可靠性。本文改進后的Raft算法在非拜占庭容錯類共識算法中綜合表現最優。

5 結語

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