SRaft:基于Schnorrkel簽名和信用值機制的Raft共識算法

陳 鵬,秦偉杰,余肖生

(三峽大學 計算機與信息學院,湖北 宜昌 443002)

0 引 言

從開放程度來看,區塊鏈主要分為公有鏈、聯盟鏈和私有鏈等。由于聯盟鏈兼有公有鏈的擴展能力和私有鏈的管理便利性,因此其已經成為最具實際應用前景的區塊鏈技術。區塊鏈集群中需要使用某種共識算法來實現集群中節點的分布式一致性[1]。聯盟鏈中的共識算法主要分為兩大類:一類是拜占庭容錯共識算法,其中具有代表性的有實用拜占庭容錯算法(PBFT)及其相關變體,如:可通過動態監管策略實現問題追溯的DDPBFT等[2];另一類則是非拜占庭容錯共識算法,具有代表性的有Raft共識算法等。Raft共識算法的強領導性使其在共識過程中具有更高的效率,其簡潔的共識過程也讓Raft算法具有很好的擴展性[3]。

Raft是一種非拜占庭容錯的共識算法。針對此共識算法中的共識效率及拜占庭問題,一些學者先將節點進行分組,組內遵循基于PageRank優化的Raft共識,主節點作為組長參與組間遵循的PBFT共識[4];另外一些學者則將區塊鏈分片后,使用K-medoids聚類算法將節點分為節點簇,簇內部使用帶有監督節點的Raft共識,簇中心節點再使用PBFT進行共識[5]。雖然這些改進提高了共識的吞吐量和共識效率,且具備了一定的拜占庭容錯能力,但是Raft在選舉階段因沖突而引發的選舉效率問題及主節點的隱私安全性問題并未得到有效解決。針對這兩個問題,該文提出了結合Schnorrkel簽名和信用值機制的共識算法,即,在主節點選取階段引入了信用值機制和日志復制階段引入了Schnorrkel聚合簽名。節點通過在共識過程中的表現改變其信任值,進而調節隨機超時時長的上下限值,在增大優質節點當選概率的同時能夠有效避免選舉沖突的發生,提升選舉階段的效率[6];通過日志復制階段的聚合簽名的生成,能夠隱匿主節點的公鑰信息,同時從節點可以驗證消息信息中的客戶端簽名,確保消息未被主節點篡改,實現了部分拜占庭容錯。實驗證明,SRaft算法能夠篩選出優質節點,并提升其作為主節點的概率;在節點數量較大的情況下,SRaft算法能夠有效避免選舉沖突的發生,并提升了選舉階段的效率。

1 相關工作

1.1 Schnorrkel簽名算法

Schnorrkel簽名算法是由Claus Schnorr于1989年提出的Schnorr簽名算法的變體之一。由于該算法能夠進行線性計算,便于生成聚合簽名,在性能、交易體積和隱私性方面具有優勢,所以Schnorrkel簽名在區塊鏈中已得到廣泛的應用。Schnorrkel簽名使用一個隨機數k以及橢圓曲線G和標量s來生成簽名,如式(1)(2)所示[7-8]。

R=k·G

(1)

s=k+H(P,R,M)·sk

(2)

其中,sk為私鑰,P為公鑰,m為消息,H()表示哈希運算。

簽名的有效性驗證,采用式(3)來完成:

s·G=R+H(P,R,M)·P

(3)

在生成Schnorrkel簽名的基礎上,通過節點間相互交換公鑰信息,多個Schnorrkel公鑰可以以線性加和的方式進行組簽,形成新的聚合簽名。聚合簽名可以被其余節點進行驗證,并且無法從聚合簽名中反向推導出參與節點的公鑰信息[9]。

對一組私鑰(n個)生成簽名后得到n個簽名。且這n個簽名可以通過線性相加,最終得到一個聚合簽名,過程如圖1所示。一旦聚合簽名通過驗證,則代表n個私鑰的簽名全部通過驗證[10]。

圖1 Schnorrkel簽名聚合過程

Schnorrkel簽名中,可利用一對私鑰(Sk1,Sk2)和隨機數k1、k2通過公式(4)(5)分別得到相應的簽名,將得到的簽名S1、S2通過線性運算相加生成共享簽名S[11]。

P=P1+P2=Sk1·G+Sk2·G

(4)

Si=Ki+H(P,R,M)·Ski

(5)

其中,參與方彼此間需要先交換R值,然后再進行各自的簽名。通過線性運算得到的聚合簽名,生成過程簡單,且能夠隱藏參與生成簽名的節點信息。

1.2 Raft共識算法

Raft算法是一種有代表性的Paxos共識算法的變體,并且是一種具有強領導性的共識算法,主節點的安全隱私性也是算法整體的安全瓶頸。集群中的所有節點被分配到隨機時長進行超時選舉,完成隨機選舉超時(Randomize Election Timeout,RET)的節點可向其余節點索票,獲得集群中半數以上節點的票,則當選為主節點,并向其余從節點發送心跳間隔檢測(Append Entries)。當客戶端發送消息更新的請求后,主節點將向全網發送更新指令,收到半數以上從節點的回復后,則進行日志更新并復制給所有從節點[12]。

Raft是一種更易于理解的分布式共識協議,它加強了日志項之間的串行性,簡化了協議的設計。Raft中的每個節點都維護一個遞增的變量,稱為任期(term)。任期本質上是節點共同維護的邏輯時鐘。通過任期,節點可以發現過時的消息。具體而言,節點間發送消息時,需要攜帶自身當前的任期。如果節點收到的消息攜帶的任期值小于該節點自身當前的任期值,則拒絕接受該消息;否則,更新自身當前的任期值[13]。節點向日志添加新的日志項時,會將自身當前的任期值也保存在日志項中,這將成為該日志項的任期。

Raft共識算法中的主節點(Leader)、從節點(Follower)、候選節點(Candidate)等角色轉變如圖2所示。初始狀態下,所有的節點都是從節點,通過選舉超時產生主節點,任期結束后,重新進入選舉階段[14]。

圖2 Raft算法節點角色轉變

2 結合聚合簽名和信用值模型的SRaft共識算法

目前,在Raft共識的研究中,通過將分層后的節點分別使用PBFT與Raft共識,實現拜占庭容錯,而重復的選舉過程降低了算法整體的選舉效率[15];通過在共識算法的網絡層結合雙層Kademlia路由協議來優化算法的選舉過程,其提升選舉效率的同時也增加了網絡開銷[16];信用值模型提升了算法中優質節點當選主節點的概率,卻無法保證主節點本身的安全隱私性[17]。

該文提出了一種結合Schnorrkel簽名以及信用值模型的SRaft算法,其流程如圖3所示,在選舉階段(a)結合信用值機制,篩選出優質節點作為領導,提高系統的效率和安全性;在日志復制階段(b),結合Schnorrkel簽名算法,隱匿主節點信息,并對客戶端消息進行驗證,避免拜占庭主節點。

圖3 SRaft算法流程

如圖3,任期開始時,首先根據節點在共識過程中的表現情況實現信用值動態更新,獲取節點在本任期內的RET超時范圍。選舉階段,優先完成超時的節點向其余節點索票,得到半數以上投票后當選為主節點。接收到客戶端信息后進入日志復制階段。日志復制階段中,得到信息的主節點將選取若干從節點共同生成一個Schnorrkel聚合簽名,參與生成聚合簽名的從節點可以驗證信息中客戶端的簽名,確保主節點未篡改客戶端信息。驗證通過后將信息全網廣播并更新日志。

由于信用值較高的節點能夠分配到更短的超時時長,完成選舉超時(Election Timeout),為了保證選舉的隨機性,該文采取了優增劣減的信用值機制,即所有節點的初始信用值相同,根據節點在每個任期(term)內的表現,進行信用值的增減。通過一個較長周期來篩選出一部分高質量節點,從概率角度縮小主節點的候選范圍,盡可能地使表現良好的節點當選為主節點。

在主節點進行心跳間隔檢測以及從節點進行回復(Append Entries Response)的過程中,通過Schnorrkel簽名算法能夠隱匿所有節點的個人信息,從而提升主節點的隱私安全性,降低集群系統被外界攻擊的風險,同時能夠保證來自客戶端的信息在傳遞過程中沒有被主節點進行篡改。在安全和穩定的基礎上,加入信用值機制,篩選出部分表現優良的節點作為主節點的候選節點,得到一個效率和穩定性相對平衡的共識模型。

2.1 信用值機制的實現

每個節點的信用值以任期(Term)為周期進行更新。在任期中,影響節點信用值變更的因素主要有兩種:時長(Time)、失效次數(Failure Times)。前者用于評定節點完成指令的效率高低,后者判定節點是否能夠完成指令。

時長是指完成客戶端指令的時間長度。對于主節點(Leader)而言,是指將客戶端發送的信息變更請求通過心跳間隔(Append Entries)發送給從節點,收到回復并完成日志更新的時長;對于從節點(Follower)而言,則指從收到心跳間隔開始,到發送給主節點回執(Response)的時長。

失效次數是指節點的宕機次數,即在某一任期中,節點未能對指令做出響應的次數。對于主節點而言,是指未能將客戶端發來的消息請求更新到日志內的次數;對于從節點而言,則指未能對主節點發來的心跳間隔發送回執的次數。

根據在共識過程中不同身份的節點的表現情況,動態調整其信任值[18]。每個新加入的節點都將被分配到一個相同的初始信任值r。每當該節點在共識過程中出現宕機情況,將依照不同的權值公式對其信任值進行扣分。信任值越低的節點獲得的RET時長上限將會提升,即低分節點需要更長的時間完成選舉超時,當選為領導者節點的概率更低。

r={leader,follower}

(6)

式中,Δcredit為主節點在任期內的信任值變更量,E(tr)表示平均時長的期望值,ti表示節點執行一筆任務(驗證和傳播共識)的實際時長。當實際時長大于期望時長,則數值為負,本次共識過程為信用值減分項;反之,若實際時長小于期望時長,數值為正,本次共識過程為信用值加分項。S表示信任值變更的速度,是一個系統常數,可以根據集群內參與共識的節點數量進行調整[19]。D為負值,其絕對值表示角色職責系數,主、從節點的職責系數不同,主節點的職責系數絕對值更大,對信用值的影響更顯著。MF表示主/從節點在參與共識的過程中出現的宕機次數。

該文設定集群中所有節點的信用初始值C均為50,根據信用值變更公式(7),節點在第n個周期的信用值為:

(7)

在整體的共識過程中,無論以何種身份參與的節點,在不同的任期中都可能會出現信任值的消耗和提升。在某一任期結束后,根據信任值的變更量來修改選舉超時范圍的上、下限。根據節點角色的不同,信用值的變更權值也有差異,主節點的扣分權值相對更高,表現良好的從節點得分權值較高。

在一定周期后,主節點選舉(Leader Selection)階段,每個節點根據之前周期中的表現,獲得各自的信用值。該文設定節點信用值范圍是0～100,且所有節點的初始信用值均為50。在若干任期后,RET的范圍會隨信用值的變化而變化。信用值高的節點,其RET范圍的上下限值將整體降低;而信用值低的節點,其RET范圍的上下限值將整體提高。RET區間更短,更容易完成選舉超時成為候選節點。

2.2 主節點選舉

當某個共識周期開始時,集群中的所有節點,首先需要獲取其當前的信用值,而新加入節點則獲得初始信用值。根據信用值分配隨機超時時長范圍,完成主節點的選舉。

設定Timemax、Timemin分別為該節點當前超時時長的上限和下限;Tmax、Tmin分別是該節點上一周期中的超時時長的上限和下限;Δcredit表示此節點在兩個周期的信用值變化量;N為該集群中包含的節點總數;k表示RET上下限值的變化參數。

當一個任期結束后,節點的信用值產生變化,導致節點的RET的上下限值也會隨之變化,當Δcredit>0時,兩者間的關系滿足公式(8)(9)。

Timemax=Tmax-Δcredit·N·k

(8)

Timemin=Tmin-Δcredit·N·2k

(9)

當Δcredit<0時,關系滿足公式(10)(11)。

Timemax=Tmax-Δcredit·N·2k

(10)

Timemin=Tmin-Δcredit·N·k

(11)

根據信用值的增減情況調整上下限的變化幅度,可以降低選舉沖突發生的概率。

經過某一共識周期后,若某節點的信用值增加,系統則降低其RET的時長上限值以及下限值,并使其能夠更快完成超時,成為候選者節點;節點的信用值降低,此時的Δcredit為負值,系統則提高其RET的時長的上限值以及下限值,使其完成超時所需的時間更長,難以成為候選者節點。

通過節點在共識過程中的表現,如能否對接收到的消息請求做出響應以及響應的時長,來判斷其信用值在該周期內的增減情況。當下一周期開始時,將繼承該周期的信用值進入選舉階段。

2.3 日志復制

在日志復制(Log Replication)階段,該文結合了Schnorrkel簽名算法。如圖4所示,當客戶端向主節點發送信息請求(Request)時,客戶端需要對消息內容進行數字簽名。當主節點接收到帶有客戶端數字簽名的消息后,主節點與部分高信用值從節點通過Schnorrkel算法生成新的聚合簽名,同時,參與Schnorrkel的從節點會通過客戶端公鑰驗證消息內容是否被主節點篡改。確認后,主節點向其余從節點發送帶有信息的心跳間隔,當收到半數以上從節點的反饋信息后,主節點提交日志,并且全網廣播進行日志復制。

圖4 日志復制過程

日志復制過程中,從節點能夠保證客戶端發來的消息請求是未經主節點篡改的,并且參與了Schnorrkel簽名的生成。由于聚合簽名的隱私性,外界攻擊者無法從聚合簽名中得到主節點的公鑰及相關信息,從而確保主節點的隱私安全性。

2.4 算法描述

輸入:集群節點信息,信用值變動參數k

Step1:主節點選舉。

(2)根據得到的節點信用值,計算節點的RET超時范圍上限值Timemax和下限值Timemin,當Δcredit>0,上限值Timemax=Tmax-Δcredit·N·k,下限值Timemin=Tmin-Δcredit·N·2k。當Δcredit<0,上限值Timemax=Tmax-Δcredit·N·2k,下限值Timemin=Tmin-Δcredit·N·k。

(3)節點在對應的超時范圍內隨機獲得一個時長,進行超時選舉,完成超時的節點向其余節點索票,首先獲得N/2以上票數的節點當選為主節點。

Step2:日志復制。

(1)當主節點接受到客戶端發來的消息,根據P=P1+P2=Sk1·G+Sk2·G和Si=Ki+H(P,R,M)·Ski,向部分高信用值從節點發起生成聚合簽名S的申請。

(2)從節點接收申請后,利用客戶端的公鑰驗證消息中客戶端的簽名是否正確,正確則參與生成聚合簽名S;不正確則中止該任期,并重新進入選舉階段。

(3)主節點使用聚合簽名S對消息簽名,并進行全網廣播,收到廣播的節點更新本地文件,并給主節點反饋信息。

(4)主節點得到N/2以上的節點反饋后,更新日志,并向客戶端發送回復。

3 仿真實驗

該文使用go語言實現Raft算法,通過結合Schnorrkel簽名和信用值模型實現了SRaft算法。在Windows環境下,通過本地多節點進行了較長周期的模擬實驗,得到選舉階段時長(包括主節點宕機后重新選舉),日志復制時長,以及多個任期中主節點的當選情況等關鍵數據。最后通過對比實驗分析SRaft在各方面的性能。

3.1 實驗環境

實驗中選用的測試平臺的開發環境為ubuntu 16.02,Golang1.17。實驗的主要測試目標是該共識算法機制完成每個共識周期的時長,節點信用值變更情況以及算法出現選舉沖突的次數和選舉階段時長。

3.2 信用值變更

該文使用了不同的參數來調節不同節點數量的集群中信用值變化的幅度,且不同角色的節點參數也會有所區別。實驗選取了節點在不同節點數量下參與共識的信用值變化過程。

由于集群內的節點數量可能變動,該文的信用值變動參數也與集群內的節點總數有關。當集群內節點數量較少時,信用值的變動參數值較大,能夠在短期內篩選出表現良好的節點;當集群內節點數量較多時,信用值的變動參數值較小,避免個別節點信用值增長過快導致選舉失去隨機性。

在5個、10個、20個節點的集群環境下,節點在25個共識周期中的表現以及各自的信用值變更情況,如圖5所示。通過計算每個任期中節點的平均信用值,可以發現在節點初始信用值均為50的情況下,集群中節點信用的平均值呈上升趨勢,并且集群內節點數量越多,節點的平均信用值增長速率越慢,當節點數量大于10個后,集群平均信用值增長速率趨于穩定,保障了系統的穩定性,避免部分節點信用值增長過快危及算法的隨機性。

圖5 節點數量-信用值趨勢

3.3 主節點當選的概率

在SRaft共識算法中,節點按照各自的角色正常進行共識,自身的信用值會保持相對穩定的增長速度。當節點的執行效率降低,則會相應降低其信用值;若在某周期內出現了惡意主節點,即不響應客戶端信息請求或篡改信息內容的主節點,則立刻停止當前任期,并重新進入選舉環節。

SRaft算法能夠通過節點自身具有的信用值的差異,影響選舉超時的時長,從而調控其當選為主節點的概率。一段時間后,集群中的高效和低效節點的當選概率會出現明顯差異。以此對節點進行篩選,使得高效節點更容易成為主節點,提高集群整體的效率和穩定性。

本實驗中,A節點模擬發生過宕機且響應速度較慢的情況;B、C、D、E節點正常參與共識過程,其中B節點的響應速度更快。5個節點在50個共識周期中當選為主節點的次數,如圖6所示。由圖6可知,在前20個共識周期中,5個節點當選為主節點的次數相當,即每個節點的當選概率比較接近。在30個共識周期后,發現節點A和節點B當選的概率出現明顯差異。表明集群篩選出了高效和低效節點,并調控了其當選為主節點的概率。

圖6 節點當選分布

3.4 選舉沖突時長

Raft共識算法中,主節點的選取是通過RET完成的。當集群內的節點數量較多時,可能出現若干節點的隨機超時時長非常接近的情況。這些節點幾乎同時完成RET成為候選者節點,并向網絡內其余節點發送投票申請(Request Vote)。此時可能發生選舉沖突,即進行全網索票的多個候選者節點沒有一個能獲得半數以上的選票。這種情況下只能通過一定的等待時間再次進行RET,并且依然有較大概率出現選舉沖突的情況。

SRaft共識算法中,信用值機制能夠在較大程度上解決選舉沖突問題,當各個節點的信用值出現差異后,每個新任期的選舉階段,不同節點都會分配到不同區間的隨機超時時長,可以有效避免選舉沖突的情況,顯著減少選舉階段的時長。

在10個節點的集群中,設定RET的范圍為1 000 ms ～5 000 ms,通過主節點宕機模擬了20次重新選舉主節點的情況,實驗結果如圖7所示。選舉用時時長超過3 500 ms即發生選舉沖突。在20次實驗中,原Raft算法共計發生7次選舉沖突,SRaft算法無選舉沖突產生,且比較發現SRaft整體的平均選舉時長均低于原Raft算法。通過對節點分配不同區間的超時時長可以顯著減少選舉階段沖突情況的產生,并且由于Schnorrkel聚合簽名的匿名性,主節點的信息安全性也得到了保證。

圖7 選舉時延

3.5 安全性分析

Raft算法的強領導性使得主節點的安全性問題成為了集群整體安全性的短板,針對主節點信息的隱私安全性,該文在SRaft算法的日志復制階段結合了Schnorrkel聚合簽名。主節點在廣播消息前,需要與其余n個從節點共同形成一個聚合簽名。由于橢圓曲線上的點可滿足乘法結合律,設橢圓曲線上存在兩點X、Y,兩點對應的標量x、y作為它們的私鑰,以及原點G,可得:

X+Y=x·G+y·G=(x+y)·G

(12)

對于Schnorrkel聚合簽名的驗證,可將驗證方程相加:

S1=s1·G+s2·G+…+sn·G=

(s1+s2+…+sn)·G

(13)

對于驗證者而言,Schnorrkel聚合簽名和一般Schnorrkel簽名并無區別,其中節點的公鑰和簽名都不會暴露,可有效隱匿主節點的公鑰信息[20]。

在生成聚合簽名的過程中,從節點對客戶端消息的簽名進行驗證,確保主節點未篡改信息內容,實現了主節點的拜占庭容錯能力。同時Schnorrkel聚合簽名能夠完全隱匿主節點的個人信息,保證主節點的安全性,減少受到外界攻擊的概率,從而提升算法整體的安全性。

4 結束語

SRaft算法是一種融入信用值機制和Schnorrkel聚合簽名的Raft算法,在選舉階段,根據節點表現,動態變更其信用值,使之獲得不同范圍內的隨機超時時長;在日志復制階段,主節點與部分高信用值從節點生成Schnorrkel聚合簽名,隱匿主節點信息,避免拜占庭錯誤。SRaft算法能在監管主節點的同時,篩選出部分優質節點作為候選主節點,能在一定程度上解決了Raft的主節點拜占庭容錯問題,降低了投票沖突導致的選舉階段時長。通過實驗對比能夠發現,SRaft算法實現了更高的穩定性,隱私性以及高效率的平衡。