朱小強(qiáng)，鄭明輝，喬譯萱，陳珩

（湖北民族大學(xué) 信息工程學(xué)院，恩施 445000）

區(qū)塊鏈技術(shù)是一種結(jié)合了密碼學(xué)算法的去中心化分布式賬本.目前，其研究主要分為兩個方向：底層技術(shù)和場景應(yīng)用.區(qū)塊鏈系統(tǒng)在不同的場景下需要改進(jìn)底層技術(shù)來滿足不同的需求.共識算法作為區(qū)塊鏈的底層技術(shù)之一，對保證區(qū)塊鏈的安全性和效率起著至關(guān)重要的作用.根據(jù)參與區(qū)塊鏈系統(tǒng)的節(jié)點(diǎn)權(quán)限的不同，區(qū)塊鏈可以分為公鏈與許可鏈［1］.公鏈允許任何節(jié)點(diǎn)隨時加入?yún)^(qū)塊鏈系統(tǒng)并參與其共識過程，且鏈上的所有數(shù)據(jù)都是公共的.主流的公鏈共識算法包括工作證明（PoW）、權(quán)益證明（PoS）、委托權(quán)益證明（DPoS）等［1］.許可鏈中節(jié)點(diǎn)加入?yún)^(qū)塊鏈系統(tǒng)需要提前獲得確認(rèn)，包括聯(lián)盟鏈［2-4］和私有鏈［5］.私有鏈大部分被使用于集體和組織內(nèi)部，不對外公開.而聯(lián)盟鏈上的數(shù)據(jù)既可以是公共的，也可以是內(nèi)部的，許可鏈的節(jié)點(diǎn)數(shù)量有限，數(shù)據(jù)訪問權(quán)限管理更為嚴(yán)格，一般采用Paxos［6］算法解決分布式節(jié)點(diǎn)的一致性問題.Raft算法［7］是一種具有強(qiáng)一致性的類Paxos 非拜占庭容錯算法，它將各分布式節(jié)點(diǎn)分為三種角色狀態(tài)，即領(lǐng)導(dǎo)者（Leader）、候選人（Candidate）和追隨者（Follower）.開始時，所有節(jié)點(diǎn)均以追隨者狀態(tài)進(jìn)行相互投票，部分追隨者節(jié)點(diǎn)通過投票變?yōu)楹蜻x人節(jié)點(diǎn)，當(dāng)某候選人節(jié)點(diǎn)收到半數(shù)以上投票時變?yōu)轭I(lǐng)導(dǎo)者節(jié)點(diǎn)，其余候選人節(jié)點(diǎn)恢復(fù)為追隨者狀態(tài).最終選定的領(lǐng)導(dǎo)者節(jié)點(diǎn)把客戶機(jī)狀態(tài)復(fù)制到追隨者節(jié)點(diǎn)，并在收到半數(shù)以上追隨者的確認(rèn)后提交，即可完成日志復(fù)制過程，達(dá)成非拜占庭故障下的協(xié)商一致性.領(lǐng)導(dǎo)者節(jié)點(diǎn)定期向追隨者發(fā)送心跳信號以證明其活躍性，一旦領(lǐng)導(dǎo)者發(fā)生錯誤或停止，一個或多個未接收到心跳信號的追隨者將投票成為候選人并再次發(fā)起領(lǐng)導(dǎo)者選舉.經(jīng)過投票，新當(dāng)選的領(lǐng)導(dǎo)者將繼續(xù)進(jìn)行區(qū)塊的打包與交易過程.Raft算法的三種狀態(tài)變更流程如圖1所示.

圖1 Raft狀態(tài)變更流程Fig.1 Raft state change process

聯(lián)盟鏈由多個機(jī)構(gòu)或組織形成的聯(lián)盟來管理，在數(shù)據(jù)溯源［8］、檔案管理［9］等領(lǐng)域有著廣闊的應(yīng)用前景，但其項目的真正落地需要解決其安全性差以及吞吐量小的問題.通常情況下聯(lián)盟鏈中節(jié)點(diǎn)均被默認(rèn)為已經(jīng)確認(rèn)，但實(shí)際情況中仍會有存在拜占庭節(jié)點(diǎn)的可能性，文獻(xiàn)［10］提出，Raft算法中的拜占庭節(jié)點(diǎn)是指由于硬件故障或網(wǎng)絡(luò)環(huán)境惡劣等原因，在點(diǎn)對點(diǎn)通信的傳輸信息過程中出現(xiàn)的有篡改通信內(nèi)容等行為的節(jié)點(diǎn).假如拜占庭節(jié)點(diǎn)成為記賬節(jié)點(diǎn)，對于整個區(qū)塊鏈系統(tǒng)是致命的.文獻(xiàn)［11］提出了一種多輪Leader 輪值的Raft 共識算法，即讓每個節(jié)點(diǎn)充分發(fā)表意見后再由小組長節(jié)點(diǎn)根據(jù)每個節(jié)點(diǎn)的意見及其他節(jié)點(diǎn)的修改意見進(jìn)行最后統(tǒng)稿達(dá)成最終共識，算法將傳統(tǒng)Raft 算法的通信復(fù)雜度從O(n) 提升為O(n2)；文獻(xiàn)［12］中提出了一種結(jié)合RSA 簽名和嵌套哈希［13］實(shí)現(xiàn)的Raft 算法，其通過犧牲一定的領(lǐng)導(dǎo)者選舉效率和吞吐量來提高其選舉安全性和拜占庭容錯能力；文獻(xiàn)［14］提出的BRaft算法保證了擁有最完備日志列表的節(jié)點(diǎn)才具備當(dāng)選為Leader 的能力，利用SHA-256 算法進(jìn)行日志項摘要生成，并通過RSA 算法對日志項摘要進(jìn)行數(shù)字簽名，最后對消息進(jìn)行序列化與反序列化處理實(shí)現(xiàn)Leader 節(jié)點(diǎn)選舉過程，但該算法在選舉階段增加了約一倍的時間消耗.

上述算法均針對Raft算法在Leader節(jié)點(diǎn)選舉過程中的安全性進(jìn)行了改進(jìn)，但當(dāng)節(jié)點(diǎn)數(shù)量上升時，共識延遲增加，選舉效率有所下降.本文通過對Raft算法進(jìn)行分析，提出了結(jié)合可驗證秘密共享體制［15］實(shí)現(xiàn)的Raft 算法.利用安全性高的可驗證秘密共享算法中子秘密分發(fā)過程取代Raft 算法中的Follower節(jié)點(diǎn)投票過程，通過驗證承諾值取代Raft 共識算法中Candidate 節(jié)點(diǎn)的計票過程.該算法可以有效抵御惡意節(jié)點(diǎn)偽造選票攻擊，實(shí)現(xiàn)了Leader 節(jié)點(diǎn)選舉的拜占庭容錯，提高了算法安全性，且維持了算法O(n)的通信復(fù)雜度，保證了算法可用性.

1 基于可驗證秘密共享的Raft算法

秘密共享（Secret Sharing，SS）技術(shù)本質(zhì)上是單一秘密的拆分管理.SHAMIR 在1979 年提出了(t，w)門限方案［16］，即通過構(gòu)造一個t- 1 次多項式，將需要共享的主秘密S作為常數(shù)項，同時將主秘密碎片化為w個，分配至w個參與者，當(dāng)碎片秘密數(shù)量大于或者等于t時，就可以求解出這個主秘密S.SHAMIR的門限方案解決了多方計算的數(shù)據(jù)隱私問題，但此方案的前提是所有參與者包括秘密管理中心都必須是誠實(shí)的，即當(dāng)存在不誠實(shí)參與方時，對于一個秘密需要有相應(yīng)的算法來驗證其就是秘密的有效片段，否則不存在秘密可言.因此，F(xiàn)ELDMAN［17］于1987 年根據(jù)SHAMIR 門限秘密方案及離散對數(shù)假設(shè)提出了一種高效的非交互式可驗證門限方案（Verifiable Secret Sharing，VSS），即Feldman VSS.此算法中秘密分發(fā)者除了給出秘密的分片數(shù)據(jù)外，還要提供對應(yīng)的系數(shù)承諾使得秘密碎片的數(shù)據(jù)可以被驗證.

1.1 方案設(shè)計

本文提出的基于可驗證秘密共享體制的共識算法是在Raft 算法的基礎(chǔ)上加入FELDMAN 可驗證秘密共享技術(shù).利用可驗證秘密共享中子秘密分發(fā)，承諾值驗證和主秘密恢復(fù)的過程取代傳統(tǒng)Raft共識算法Leader 節(jié)點(diǎn)選舉過程中投票與請求投票以及計票的過程，加入秘密分發(fā)者角色進(jìn)行初始主秘密的生成與分發(fā)，同時也保留了Raft 共識算法的三種節(jié)點(diǎn)狀態(tài)，以及任期、隨機(jī)超時時間的機(jī)制.此外，通過可驗證秘密共享算法，以2/3 總節(jié)點(diǎn)數(shù)作為門限值，可以實(shí)現(xiàn)基于Raft算法的拜占庭容錯.

基于可驗證秘密共享的Raft算法狀態(tài)轉(zhuǎn)移模型如圖2所示.其主要過程如下：

圖2 基于可驗證秘密共享的Raft算法節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移模型Fig. 2 Raft algorithm node state transition model based on verifiable secret sharing

（1）秘密生成與分發(fā)階段：Raft集群與各節(jié)點(diǎn)啟動，秘密分發(fā)者生成一個主秘密、與節(jié)點(diǎn)數(shù)量相同的子秘密和承諾值，隨機(jī)分發(fā)子秘密至各節(jié)點(diǎn)，同時廣播承諾值；

（2）子秘密驗證階段：為防止秘密分發(fā)者作惡，各Follower 節(jié)點(diǎn)通過廣播的承諾值驗證收到子秘密的真?zhèn)危?/p>

（3）投票階段：與Raft 算法相同，各節(jié)點(diǎn)在隨機(jī)時間后超時，根據(jù)超時時間變更狀態(tài)為Candidate，此時Candidate 節(jié)點(diǎn)向其他節(jié)點(diǎn)索要子秘密作為投票，首先獲得大于2/3 總節(jié)點(diǎn)數(shù)子秘密的Candidate節(jié)點(diǎn)可恢復(fù)出主秘密；

（4）Leader 節(jié)點(diǎn)確認(rèn)階段：得到主秘密的Candidate 節(jié)點(diǎn)向秘密分發(fā)者提交其回復(fù)結(jié)果.若正確，秘密分發(fā)者廣播其結(jié)果，此時各節(jié)點(diǎn)再次向此Candidate節(jié)點(diǎn)投票，獲得最高票數(shù)的Candidate節(jié)點(diǎn)成為此任期的Leader 節(jié)點(diǎn).反之選舉失敗，當(dāng)前任期失效，并開始下一輪選舉.

1.2 算法詳細(xì)描述

本節(jié)主要針對改進(jìn)后算法的詳細(xì)流程進(jìn)行闡述，算法偽代碼如下：

29.產(chǎn)生Leader節(jié)點(diǎn)，共識完成.

Leader節(jié)點(diǎn)被確認(rèn)后就開始為客戶請求提供日志復(fù)制等服務(wù)，且Leader 節(jié)點(diǎn)周期性地向Follower節(jié)點(diǎn)發(fā)送心跳包來維持其領(lǐng)導(dǎo)地位.驗證的交易在該任期內(nèi)均由Leader 節(jié)點(diǎn)打包生成區(qū)塊并在收到超二分之一節(jié)點(diǎn)回復(fù)后，發(fā)送確認(rèn)信息至Follower節(jié)點(diǎn)，將該區(qū)塊作為賬本上的下一個區(qū)塊，完成區(qū)塊鏈賬本日志復(fù)制過程.

2 算法分析

表1列出了Pbft，Raft算法及本文算法在適用環(huán)境，通信復(fù)雜度以及最大容錯節(jié)點(diǎn)數(shù)的對比.由表1可知相比Pbft 共識算法，Raft 算法缺少了拜占庭容錯的能力，而本文算法具備了3f+ 1 ＜=N的拜占庭容錯能力，通信復(fù)雜度維持O(n).且本文改進(jìn)的算法繼承了Raft 共識算法原有的特性，在其共識效率及可用性未明顯降低的情況下具有了抵御偽造選票攻擊的能力與拜占庭容錯能力.

表1 本文算法對比Raft與Pbft算法Tab.1 The algorithm in this paper compared with Raft and Pbft algorithm

2.1 安全性分析

所提出的算法解決了Raft 算法在Leader 選舉過程中的安全性問題.利用可驗證秘密共享體制取代了單一的選票計數(shù)方案，消除了不誠實(shí)的Candidate 節(jié)點(diǎn)導(dǎo)致的“虛假選票”的作弊風(fēng)險，同時也修改了Leader 節(jié)點(diǎn)選舉需要有大于1/2 非拜占庭節(jié)點(diǎn)進(jìn)行投票的前提，將門限值設(shè)置為2/3 節(jié)點(diǎn)實(shí)現(xiàn)其拜占庭容錯能力.并且可驗證秘密共享體制相對傳統(tǒng)秘密共享體制也做了安全性的提升，避免了秘密分發(fā)者作惡的可能性，利用廣播承諾值的方式讓每個節(jié)點(diǎn)確認(rèn)其得到的子秘密是否真實(shí).改進(jìn)后的Raft 共識算法選舉出的Leader 節(jié)點(diǎn)也進(jìn)一步保證了其后續(xù)狀態(tài)機(jī)復(fù)制的安全性.由于承諾值c被公開，即此密碼體制的安全性是建立在離散對數(shù)問題難解性的基礎(chǔ)上，所以它擁有計算上的安全性.

基于可驗證秘密共享的Raft算法具有拜占庭容錯能力，即只有當(dāng)節(jié)點(diǎn)總數(shù)為N，拜占庭節(jié)點(diǎn)數(shù)量小于N/3 的狀態(tài)下，非拜占庭節(jié)點(diǎn)的Candidate 節(jié)點(diǎn)可成功驗證承諾值并恢復(fù)主秘密，切換節(jié)點(diǎn)狀態(tài)為Leader，而當(dāng)拜占庭節(jié)點(diǎn)超過設(shè)定的閾值時驗證無法通過，需要重新進(jìn)行選舉及投票.當(dāng)Candidate 作為拜占庭節(jié)點(diǎn)偽造選票時，由于秘密分發(fā)者采用廣播的方式公布承諾值，任何節(jié)點(diǎn)均可驗證子密鑰是否真實(shí)，且承諾值具有計算上的安全性，所以此Candidate 節(jié)點(diǎn)不能利用虛假選票同其他節(jié)點(diǎn)的正確子秘密一起恢復(fù)正確主秘密，進(jìn)而在廣播主秘密時無法被其他節(jié)點(diǎn)承認(rèn)為Leader 節(jié)點(diǎn).以上特性使其擁有對抗偽造選票攻擊的能力.

以上分析表明：改進(jìn)后的共識算法具備拜占庭容錯能力，可以抵御偽造選票攻擊，符合算法安全性要求.

2.2 效率分析

Raft 算法達(dá)成共識的過程只需Candidate 節(jié)點(diǎn)與Follower 節(jié)點(diǎn)之間相互通信，達(dá)成共識之后的日志復(fù)制過程也只需Follower 節(jié)點(diǎn)與Leader 節(jié)點(diǎn)通信即可完成，F(xiàn)ollower 節(jié)點(diǎn)之間無需溝通.當(dāng)聯(lián)盟鏈中總結(jié)點(diǎn)數(shù)為n時，Leader 節(jié)點(diǎn)選擇過程的通信次數(shù)為n，日志記錄過程通信次數(shù)為n- 1，所以其總通信次數(shù)為2n- 1，故算法通信復(fù)雜度為O(n).本文提出的算法中，選擇Leader 節(jié)點(diǎn)的過程中廣播承諾值，投票與索取投票的通信次數(shù)為2n+ 1，日志記錄過程通信次數(shù)為n- 1，總通信次數(shù)為3n，所以算法通信復(fù)雜度同樣為O(n).保持了算法的高效性.

算法活性是指共識一定能發(fā)生.Raft 算法的活性體現(xiàn)在其隨機(jī)超時時間t的設(shè)定，t∈[150 ms，300 ms]且t遠(yuǎn)大于Raft共識中的消息時延.目的是保證有限時間內(nèi)產(chǎn)生Leader 節(jié)點(diǎn)，且可以避免不必要的消息延遲導(dǎo)致的Leader 節(jié)點(diǎn)切換，保證共識系統(tǒng)的穩(wěn)定運(yùn)行.

本文算法完全保留了Raft算法對于保持算法活性的設(shè)計，若在t時間段內(nèi)沒有Leader 節(jié)點(diǎn)做出回應(yīng)，則Candidate 節(jié)點(diǎn)重新啟動選舉，且較大的時間間隔也考慮到算法中存在的可驗證秘密共享體制，預(yù)留時間給秘密分發(fā)，合成及驗證過程.保證了算法活性.

3 仿真實(shí)驗

為了評估改進(jìn)后算法的性能，本實(shí)驗著重研究了其領(lǐng)導(dǎo)者選舉的效率，與傳統(tǒng)Raft 算法進(jìn)行了比較.評估指標(biāo)為選舉延遲即當(dāng)Leader 節(jié)點(diǎn)宕機(jī)時重新完成選舉所需的時間，以及改進(jìn)后的聯(lián)盟鏈每秒處理的事務(wù)數(shù).實(shí)驗測試中采用Python 語言實(shí)現(xiàn)Raft 算法以及改進(jìn)后的可驗證秘密共享算法，將兩者結(jié)合實(shí)現(xiàn)了一種基于可驗證秘密共享體制的共識算法. 實(shí)驗測試平臺采用8 核心16 線程AMD Ryzen（TM）7 4800H 處理器，16GB 內(nèi)存的硬件平臺.利用Python 配置輕量級web 框架Flask 模擬了聯(lián)盟鏈中的多節(jié)點(diǎn)通信，操作系統(tǒng)為Windows 10 專業(yè)版64 位，測試軟件為PyCharm 2021，Python 3.8，F(xiàn)lask 2.0.1.

圖3 表示基于蒙哥馬利算法對Feldman 可驗證秘密共享算法進(jìn)行優(yōu)化后，當(dāng)素數(shù)p分別為10bit 與12bit大小時，加解密及承諾值驗證的過程中所需的時間（圖中Montgomery-VSS 指基于蒙哥馬利算法優(yōu)化的可驗證秘密共享算法；VSS 指原Feldman 可驗證秘密共享算法）.從圖3 可知：隨著節(jié)點(diǎn)數(shù)及素數(shù)p的增大，原算法的時間消耗迅速增加，計算復(fù)雜度明顯增大，當(dāng)10 節(jié)點(diǎn)，素數(shù)為12bit 時，其時間消耗已大于50000 ms，應(yīng)用在Raft共識算法中意義不大.經(jīng)過蒙哥馬利算法優(yōu)化后的可驗證秘密共享算法在大數(shù)條件下減少了取模的次數(shù)，簡化了運(yùn)算復(fù)雜度，效率提高約為原算法的850倍（隨機(jī)素數(shù)取值為12bit，節(jié)點(diǎn)數(shù)7個以上時），同時節(jié)點(diǎn)數(shù)和隨機(jī)素數(shù)p的大小對算法的計算難度影響較小，具有高擴(kuò)展性，可以應(yīng)用于Raft共識算法中.

圖3 蒙哥馬利算法對加解密時間的影響Fig.3 The influence of Montgomery algorithm on encryption and decryption time

圖4 表示當(dāng)節(jié)點(diǎn)的數(shù)量為5 個到40 個時，兩種算法下Leader 選舉所需要的時間.隨著節(jié)點(diǎn)數(shù)量的增加，傳統(tǒng)Raft 算法的選舉所需時間受節(jié)點(diǎn)數(shù)量影響較小.本文所提出算法中選舉Leader 節(jié)點(diǎn)的時間隨著節(jié)點(diǎn)數(shù)量的增加而增加.原因是節(jié)點(diǎn)必須對來自其他節(jié)點(diǎn)的提交進(jìn)行等待與確認(rèn)，而承諾值驗證與秘密恢復(fù)過程的資源消耗也會因節(jié)點(diǎn)數(shù)量的逐漸增加而增大.

圖4 開始狀態(tài)Leader節(jié)點(diǎn)選舉延遲Fig.4 The Leader node election delay in start status

圖5表示了兩種算法在節(jié)點(diǎn)數(shù)量為5個到40個且Leader 節(jié)點(diǎn)存在時，模擬Leader 節(jié)點(diǎn)在宕機(jī)時重新完成選舉的延遲：在聯(lián)盟鏈共識算法正常運(yùn)行時手動停止當(dāng)前實(shí)驗中的Leader 節(jié)點(diǎn)，使兩種共識算法分別重新自主選擇Leader 節(jié)點(diǎn)，并在不同數(shù)量的節(jié)點(diǎn)存在時多次進(jìn)行測試.結(jié)果表明，所提出的基于可驗證秘密共享體制的Raft 算法能夠保持高效率，但資源消耗略大于Raft算法.

圖5 宕機(jī)狀態(tài)下Leader節(jié)點(diǎn)選舉的延遲Fig.5 The Leader node election delay in outage states

由圖4 及圖5 分析得出，改進(jìn)后的算法相比于非拜占庭容錯的Raft算法在Leader節(jié)點(diǎn)的切換速度上有了約25%的性能下降，即Raft 算法與基于可驗證秘密共享的Raft 算法的性能存在一定差異，隨著網(wǎng)絡(luò)中測試節(jié)點(diǎn)數(shù)量的增加，傳統(tǒng)Raft 算法所受影響較小，但可驗證秘密共享算法中對子秘密與承諾值進(jìn)行的驗證過程：

會消耗一定的計算資源，帶來更高的選舉延遲.

TPS（Transactions Per Second），即數(shù)據(jù)吞吐量是衡量程序性能的重要指標(biāo)，代表單位時間內(nèi)區(qū)塊鏈能夠處理的交易數(shù)量，圖6 所示的測試結(jié)果中可以看出隨著節(jié)點(diǎn)數(shù)量即其并發(fā)處理量的增加，兩種算法中日志復(fù)制耗時均變長，數(shù)據(jù)吞吐量不斷降低.但基于可驗證秘密共享的Raft算法相比傳統(tǒng)Raft共識算法，其吞吐量下降的比例從10%降低為4.2%.原因在于隨著節(jié)點(diǎn)數(shù)量的增加，可驗證秘密共享算法的計算成本相對于資源總消耗的比例逐漸變小，且由于其算法安全性保證了當(dāng)選Leader 的正確性，避免了重復(fù)選舉情況的發(fā)生.因此，基于可驗證秘密共享體制的Raft算法更適用于對TPS要求更高的多節(jié)點(diǎn)場景.

圖6 數(shù)據(jù)吞吐量測試Fig.6 Data throughput test

4 結(jié)語

本文所提出的基于可驗證秘密共享的共識算法是一種可拜占庭容錯的Raft 算法，其利用效率改進(jìn)的Feldman VSS 方案替代Leader 選舉過程中投票與請求投票的步驟，解決了Raft 算法在拜占庭場景下Leader 選舉中投票造假的問題，并結(jié)合常規(guī)Raft算法對改進(jìn)后算法的安全性和效率進(jìn)行了分析證明.實(shí)驗結(jié)果表明，基于可驗證秘密共享的區(qū)塊鏈共識算法相比傳統(tǒng)Raft算法擁有Leader節(jié)點(diǎn)選舉過程中抵抗Candidate 節(jié)點(diǎn)選票造假的能力即拜占庭容錯能力.并且相比非拜占庭容錯的傳統(tǒng)Raft算法，其主節(jié)點(diǎn)的選舉過程仍然可以高效進(jìn)行.綜上所述，基于可驗證秘密共享體制的Raft 共識算法是一種可以應(yīng)用于聯(lián)盟鏈中的安全性高，時延低，可容錯的高可拓展性共識算法.