基于門限和環簽名的抗自適應攻擊拜占庭容錯共識算法

孫海鋒 張文芳 王小敏 馬 征 黃路非 李 暄

區塊鏈是一種去信任化的分布式計算范式[1],其概念源于2008 年中本聰在密碼學郵件組發表的《比特幣: 一種點對點電子現金系統》[2]一文,闡述了一種基于非對稱加密、共識算法、P2P (Peer-to-Peer)協議等多種技術融合構建的去中心化基礎架構.共識算法作為區塊鏈的核心技術,能夠在缺乏中央控制的網絡中,實現數據的分布式一致性,對維護系統的穩定運行和節點相互信任起著重要作用,因此逐漸成為區塊鏈的研究熱點.

根據系統開放程度不同,區塊鏈可以分為公有鏈、聯盟鏈和私有鏈.公有鏈起源于比特幣,具有完全去中心化特性,任何節點均可參與鏈上數據的維護、讀寫以及共識過程.公有鏈大多采用“Proof of X”[3]類共識算法,核心思想是通過競爭的方式解決某項難題來獲得記賬權,典型代表有工作量證明[4](Proof of work,PoW)、權益證明[5](Proof of stake,PoS)和股份授權證明[6](Delegate proof of stack,DPoS).PoW 依賴機器進行數學運算來獲取記賬權,通過激勵機制引入分布式節點的算力競爭來保證數據一致性和安全性,但挖礦造成大量的資源浪費,備受世人詬病,而且交易吞吐量低下、交易延遲過高,無法滿足商業應用需求.PoS 以權益證明代替工作量證明,由具有最高權益的節點獲得區塊的記賬權,解決了PoW 資源浪費問題,并在一定程度上縮短達成共識的時間,但易造成“富者越富”、富者支配記賬權的問題.DPoS 在PoS 的基礎上,將記賬人的角色專業化,通過貨幣持有者投票選舉“董事會”成員,“董事會”內部按照既定規則驗證交易和記賬,因此大幅縮小參與驗證和記賬節點的數量,實現秒級的共識驗證,但也導致去中心化程度降低.

由于公有鏈具有高度開放性,用戶的隱私和監管都存在不足,并且采用“Proof of X”類吞吐量低下的共識算法,無法滿足商業應用的需求.因此R3CEV、IBM 等公司紛紛推出面向行業應用的聯盟鏈.聯盟鏈是一種在融合了傳統分布式系統和當前去中心化理念的基礎上進行多中心化改造的區塊鏈,提供成員管理、認證、授權、監控、審計等安全管理功能,參與者通過授權加入網絡,組成利益相關的聯盟,聯盟成員之間共同維護區塊鏈.相比公有鏈,聯盟鏈更適用于企業之間的交易、結算或清算等多方協作場景;相比傳統分布式網絡,聯盟鏈屬于半封閉生態的交易網絡,存在不對等信任的節點.因此,考慮到商業應用對安全、性能等方面的需求,聯盟鏈一般采用拜占庭容錯算法來進行全網共識.

拜占庭容錯算法[7]最早由Lamport 等提出,是分布式系統應用復制技術解決拜占庭錯誤的通用方案.其中,拜占庭錯誤是指系統中存在惡意節點故意偽造消息導致的軟件惡意行為,對應的節點為拜占庭節點.1999 年,Castro 等[8]提出首個實用拜占庭容錯算法(Practical Byzantine fault tolerance,PBFT),采用三階段協議在副本之間進行狀態復制,并以兩兩交互的方式保證各副本狀態達成一致,從而將拜占庭容錯算法復雜度從指數級降到多項式級,目前在聯盟鏈中得到廣泛應用;然而兩兩交互導致拜占庭容錯算法通信復雜度高達O(n2),易造成網絡擁塞,可擴展性差.隨后,一系列拜占庭容錯方案[9-19]相繼得以提出.2007 年,Zyzzyva[9]采取投機技術(Speculation)避免執行高昂的三階段提交,由客戶端和副本直接交互,但投機行為導致錯誤恢復成本較高.文獻[10]在Castro 等提出的PBFT算法基礎上設計了動態拜占庭容錯算法(Dynamic PBFT),允許節點動態出入共識網絡.文獻[11-12]通過引入可信計算平臺(Trusted computing platform,TCP)限制節點進行欺騙的能力,將拜占庭容錯系統所需的服務器數量減少到 2f+1,f為拜占庭節點數量,從而降低系統開銷.文獻[14-15]通過引入門限簽名將系統通信復雜度降至O(n),但上述方案中門限簽名的合成與轉發均依賴于主節點的可靠性,魯棒性不強,一旦主節點被敵手控制或成為一個拜占庭節點,將危害系統安全性,并且主節點身份是暴露的,不能抵抗自適應攻擊.此外,一些學者利用PBFT 運行效率高、非概率性共識的優點,將PBFT 與公有鏈共識算法相結合,構造出高效的混合共識算法(Hybrid consensus)[16-19],如Tendermint[16]、ByzCoin 等[18],核心思想是先通過PoW、PoS 等算法選舉一定數量的節點作為委員會,委員會內部再依托高效的PBFT 算法生產區塊,從而大幅提升交易規模.綜合當前研究現狀,目前拜占庭容錯算法主要研究方向是進一步降低系統開銷,提高吞吐量,然而大部分方案存在以下不足.首先,大部分方案在提案之前便揭曉主節點身份,極容易遭受敵手自適應選擇主節點發起的分布式拒絕服務攻擊(Distributed denial of service,DDoS),導致主節點提案進程被中斷,嚴重影響系統活性,文獻[20]將這種攻擊稱之為自適應攻擊.為了抵抗自適應攻擊,Algorand[21]給出一種解決思路,利用加密抽簽技術隱秘選擇共識過程的驗證者和提案者,使得敵手無法事先猜測提案者身份,進而能夠抵抗自適應攻擊.然而,此方案中加密抽簽函數無意識地選擇多提案者增加了系統對多提案處理的負擔.其次,大部分拜占庭容錯方案需要進行兩兩交互來保證各副本狀態達成一致,每次交互均需 2f+1個副本收到2f+1個相同的投票才能滿足系統一致性要求,稱為“雙2f+1”條件.一旦發生消息丟失或網絡擁塞、延遲等問題,將導致“雙 2f+1 ”條件不滿足,使得系統在當前視圖無法達成一致,必須更換視圖,因此造成系統資源極大浪費.

本文針對大部分拜占庭容錯算法難以抵抗自適應攻擊,并且存在可擴展性不足、魯棒性較差等問題,提出一種契合聯盟鏈場景的健壯拜占庭容錯共識算法(Robust Byzantine fault tolerance,RBFT).首先,該算法利用環簽名構造無條件匿名的公開承諾,每個副本在不泄露各自承諾內容的前提下得到各自承諾在所有公開承諾中的排序位置,并根據排序位置被依次選為提案者進行提案,從而達到隱匿提案者身份、保障系統活性的目的.其次,通過在多輪投票中合成代表大多數投票者意愿的門限簽名,弱化“雙 2f+1 ”條件,以保證在最小連通性的網絡環境中實現低延遲、高魯棒性的拜占庭容錯共識算法,從而減少視圖更換、簽名驗證等開銷.分析表明,系統在減少系統開銷、提升可擴展性的同時,具有較高的安全性,在提案前和提案后均能保證系統活性,為高可用拜占庭系統提供支持.

1 預備知識

1.1 系統模型

聯盟鏈是一種對特定的組織開放,具有準入機制的區塊鏈.本文提出的健壯拜占庭容錯共識算法(RBFT)是一種狀態機副本復制機制,提供對請求的順序性、原子性和錯誤補償操作,使整個系統共同維護全網一致的分布式賬本,該機制能夠很好地契合聯盟鏈應用場景.如圖1 所示,分布在不同地理位置的節點或客戶端,通過授權機制加入聯盟網絡,組成利益相關的聯盟,聯盟成員通過RBFT 算法共同維護全網一致的分布式賬本.

圖1 聯盟鏈應用場景Fig.1 Alliance chain application scenario

RBFT 算法共包括兩部分: 基于環簽名的匿名排序選主算法和基于門限簽名的拜占庭容錯算法.RBFT 算法首先通過環簽名構造匿名排序選主算法,隱匿確定區塊鏈中不同高度下的潛在提案者(Potential proposer,PP),PP 負責收集交易、打包區塊和發起提案,并且在提案之前隱藏身份.然后,誠實副本基于門限簽名按照一致次序處理提案,為公共賬本創建高度遞增的區塊,形成全網一致的分布式賬本.圖2 為RBFT 算法示意圖,主要包括提案(Proposal)、準備(Prepare)、提交(Commit)三個階段.在提案階段,潛在提案者公布身份憑證并廣播區塊,之后退變為正常副本,盡管此刻敵手可以對暴露身份的提案者發起自適應攻擊,但不能撤銷已經發出的提案.在準備階段,所有副本首先驗證提案者身份的合法性,然后對收到的提案進行投票,投票基于門限簽名.在提交階段,副本收集投票,任何收到大于法定人數投票意愿的副本部分簽名(Part signature)都可以合成有效的門限簽名(Threshold signature)并進行廣播,其他副本只需驗證一條合法的門限簽名,即可確認系統狀態轉換的有效性.

圖2 RBFT 算法示意圖Fig.2 RBFT algorithm diagram

一方面,“雙 2f+1 ”條件使拜占庭容錯算法的網絡通信復雜度高達 O(n2);另一方面,當聯盟鏈出現節點離線或網絡延遲等問題時,將導致“雙 2f+1 ”條件不滿足,因此現有的基于“雙 2f+1 ”條件的拜占庭容錯算法難以適應實際的聯盟鏈環境.為了有效解決上述問題,本文提出的RBFT 算法將弱化“雙 2f+1 ”條件,保證任何時候只要存在一個狀態良好的副本能夠合成并傳達代表法定人數投票意愿的門限簽名,即可在最小連通性的網絡環境中實現低延遲、高魯棒性的拜占庭容錯共識算法.如圖2中紅色線條即構成一個最小連通性網絡,由狀態良好的副本P2 合成并傳達代表法定人數 (3 個) 投票意愿的門限簽名.最小連通性網絡構成最小共識單元,最小共識單元即可實現全網共識,因此本方案可以很好地節省網絡資源,具有更好的擴展性.RBFT算法的相關假設與定義如下.

假設 1.參與副本Pi {P1,···,PN},N表示參與共識副本總數量,其中拜占庭節點數量為f,拜占庭節點行為可以是任意的,可以通過合謀方式欺騙誠實節點,破壞系統一致性,但是拜占庭節點計算能力有限,無法在多項式時間內突破密碼機制.同時,在滿足f(N-1)/3」的條件下,能夠保障系統安全性和活性.

假設 2.在聯盟鏈中,節點之間通過異步網絡連接,網絡中的消息可能丟失、亂序或延時到達.設delay(t)表示消息從時刻t第1 次發出到最終被接受方收到的時間間隔,當副本等待提案時間超過預設值delay(t) 時,觸發視圖變換協議,保證系統活性.

定義 1.共識節點.共識節點參與共識流程并保存區塊數據,根據職責不同可分為: 潛在提案者和普通副本兩類.潛在提案者負責打包區塊、定時提案;普通副本負責對提案進行投票、達成一致.潛在提案者在提案之前隱藏身份,敵手無法發起自適應攻擊;在提案之后暴露身份,退變為普通副本.

定義 2.有序承諾序列 (OrderedCom).有序承諾序列OrderedCom{Com1,···,ComM},其中Com為公開承諾,并且Com1＞,···,＞ComM.OrderedCom指定一組身份隱藏的潛在提案者,根據排序位置被依次選為潛在提案者進行提案.OrderedComi表示Comi背后對應的潛在提案者.

定義 3.區塊 (Block).區塊存放批量交易數據,根據存放數據類型不同可分為: 一般區塊和特殊區塊兩類.一般區塊由舊的有序承諾序列中前M-1位潛在提案者打包提交,包含交易內容;特殊區塊由舊的有序承諾序列中最后一位潛在提案者打包提交,包含新的有序承諾序列OrderedComnew.

定義 4.消息msgs.副本之間通過提案消息、投票消息來達成共識,根據消息簽名類型不同可分為:Sig(m)消息、PartSig(m) 消息和ThresholdSig(m)消息.

1)Sig(m) 消息指潛在提案者用于發布提案的一般簽名消息,具體消息格式為〈Sig(CP,v,h,Hash(Block)),Block〉,CP為承諾憑證,v為當前視圖編號,h為當前提案區塊高度,Hash(Block) 為提案區塊的哈希值,采用SHA-256 算法.

2)PartSig(m) 消息指每個副本參與投票的部分簽名消息,如果副本接受提案,則對區塊Block進行部分簽名投票,一定數量的PartSig(m) 消息能夠合成ThresholdSig(m) 消息,具體消息格式為〈PartSig(v,h,Hash(Block))〉.

3)ThresholdSig(m) 消息指代表法定人數投票結果的門限簽名消息.對于一個包含 3f+1 臺服務器的拜占庭系統,需要收集到 2f+1 臺服務器發送的一致信息,才能保證達成一致的非拜占庭服務器數量大于拜占庭服務器數量.因此,設門限值t2f+1,任何副本收到t個投票內容一致的PartSig(m)消息都能合成ThresholdSig(m) 消息,具體消息格式為 〈ThresholdSig(v,h,Hash(Block))〉.

1.2 環簽名

2001 年,Rivest 等[22]提出環簽名的概念,環中成員以一種完全匿名的方式對消息進行簽名,驗證者能確定簽名者為環中一員,但無法得知真實簽名者是誰.在基于環簽名的匿名排序選主算法中,參與共識的副本構成環,環中成員基于確定的公開參數計算各自承諾,并以匿名方式公開,環中成員能夠在不泄露身份的前提下得到各自承諾在所有公開承諾中的排序位置,并依據排序位置依次被選為主節點進行提案.為防止惡意副本公開多個承諾,破壞系統活性,本文使用關聯環簽名[23],通過在環簽名的基礎上添加關聯標簽,確保每個副本在一次匿名排序選主中只能產生一個匿名公開承諾,從而防止惡意副本匿名性作惡.環簽名的一般模型如下:

1) 密鑰生成Gen: 輸入安全參數k,輸出公鑰PK和私鑰SK.

2) 簽名Sign: 輸入安全參數k、消息m和n個環成員的公鑰集合L{PK1,PK2,···,PKn}以及真實簽名者的私鑰SK后,輸出環簽名σ.

3) 驗證Verify: 輸入安全參數k、消息m、環成員公鑰集合L和環簽名σ后,輸出判斷值“接受”或者“拒絕”.

1.3 門限簽名

(t,n)門限簽名[24]是指群體的簽名密鑰被n個成員以門限方式共享,任意大于等于t個成員的子集可以代表這個群體產生簽名,而任意少于t個成員的子集則不能.在基于門限簽名的拜占庭容錯的共識算法中,將群體的簽名權利以門限方式分散給各副本,各個副本采用門限的方式進行投票,投票達到門限值t時,才能生成決議的有效簽名.這樣的方法即保證了共識結果得到大多數副本的許可,又可在最小連通性的網絡環境中實現低延遲、高魯棒性的拜占庭容錯共識算法.根據子密鑰分發方式的不同,門限簽名可分為兩種類型: 由可信任中心分發子密鑰的門限簽名方案和分布式分發子密鑰的門限簽名方案.本文采用分布式分發子密鑰的門限簽名方案,避免可信中心成為系統安全瓶頸.門限簽名的一般模型如下:

1) 密鑰生成Gen: 輸入安全參數k,輸出系統公鑰PK以及每個成員的私鑰SKi(i1,2,···,n).

2) 簽名Sign: 輸入安全參數k、消息m以及成員私鑰SKi,產生部分簽名σi,然后再由指定成員將達到門限值t的部分簽名σi合成門限簽名σ.

3) 驗證Verify: 輸入安全參數k、消息m、系統公鑰PK和門限簽名σ后,輸出判斷值“接受”或者“拒絕”.

2 抗自適應攻擊的健壯拜占庭容錯共識算法

在聯盟鏈中,節點和客戶端進入區塊鏈網絡需要進行權限認證,我們假設聯盟網絡中存在認證中心(Certificate authority,CA),為所有聯盟節點頒發相應的公鑰證書,同時由于本方案引入了門限簽名和環簽名進行共識,所以CA 還需為門限簽名公鑰和環簽名公鑰頒發證書.

假設消息為m,副本Pj對消息m進行的一般簽名表示為Sigj(m),環簽名表示為RingSigj(m),門限簽名表示為ThresholdSigj(m) 以及門限簽名中的部分簽名表示為PartSigj(m).

2.1 基于環簽名的匿名排序選主算法

本節基于關聯環簽名構造無條件匿名和計算綁定的公開承諾,每個副本Pj(j1,2,···,N) 計算承諾如下:

其中,Comj為綁定的第j個公開承諾,last_block為最近達成共識的特殊區塊,Hash為安全哈希函數,CP為承諾憑證(Commitment proof),是對特殊區塊last_block的簽名.副本Pj計算完承諾后,再計算匿名承諾AComj:

其中,k為安全參數,L為公鑰集合,Link為關聯標簽.本文的關聯環簽名參考文獻[23]中的算法,但將關聯標簽修改為

其中,H表示哈希函數,x為副本Pj對應的環簽名私鑰.通過將Link和每輪匿名選主中的last_block綁定,使得每一個副本的Link在不同輪的選主過程中都會發生動態變化,因此既能防止惡意副本在同一輪選主過程中產生多個匿名承諾以影響排序結果,又使得當前輪次的承諾打開無法破壞下一輪環簽名的匿名性.如果某副本產生了多個匿名承諾,則只取其中一個來構造有序承諾序列OrderedCom.

承諾Com通過哈希函數隱藏了背后承諾憑證CP,一方面一個承諾憑證對應一位提案者,哈希函數的單向性特點使敵手不能知曉承諾背后對應的提案者;另一方面承諾憑證是對特殊區塊的簽名,任何人無法偽造簽名并冒充.提案者在承諾打開時,其他副本只須對承諾憑證進行一次哈希運算,并與有序承諾序列OrderedCom中對應的承諾Com進行對比,即可證明潛在提案者身份的合法性.匿名承諾ACom實現對承諾的匿名認證,驗證者能夠驗證承諾來自環中成員,保障承諾來源的可靠性,但無法得知真實簽名者是誰.

如圖3 所示,有序承諾序列OrderedCom為所有承諾Com按照大小排序的集合,提供了一組身份隱藏的潛在提案者,每個副本依據各自承諾Com在有序承諾序列OrderedCom中的排序位置被依次選為提案者,只有滿足有序承諾序列OrderedCom要求的提案者才是有效的提案者.為了保證所有副本得到全局一致的有序承諾序列OrderedCom,每個副本計算完匿名承諾ACom后,向聯盟鏈網絡廣播匿名承諾ACom和承諾Com.當輪到有序承諾序列OrderedCom中的最后一個潛在提案者PPM提案時,潛在提案者PPM收集網絡中的匿名承諾ACom和承諾Com,并通過公鑰集合L來驗證匿名承諾ACom的簽名正確性,以實現對Com的匿名驗證.潛在提案者PPM將通過驗證的匿名承諾ACom和承諾Com打包進特殊區塊進行提案,再通過第3.3.2 節的基于門限簽名的拜占庭容錯算法達成全局一致的有序承諾序列.

圖3 有序承諾序列Fig.3 Ordered commitment sequence

2.2 基于門限簽名的拜占庭容錯共識算法

相對傳統中心化網絡,聯盟鏈網絡關系更加復雜、位置分散以及網絡傳輸的不可靠性,導致“雙2f+1”條件難以保證.本節通過引入門限簽名技術實現在最小連通性網絡環境中的低延遲、高魯棒性的拜占庭容錯共識算法,門限簽名包含法定人數投票結果,使得當收到大于或等于門限值的副本投票部分簽名時,任何狀態良好的副本都可以合成并廣播代表法定人數投票結果的門限簽名,其他副本只要收到一條合法的門限簽名,即可對投票結果的一致性進行安全驗證.

基于以上邏輯,本文所提的基于門限簽名的RBFT 算法如算法1 所示.

算法1.基于門限簽名的拜占庭容錯共識算法

輸入.提案區塊

輸出.全局一致的可信賬本

RBFT 算法詳細流程如下:

1) 按照有序承諾序列OrderedCom規定的潛在提案者提案順序,設本輪潛在提案者為PPiOrderedComv,v是當前視圖編號.PPi將一段時間內收集到的交易統一檢查和打包進區塊.如果PPi是OrderedCom中的最后一位潛在提案者,則收集新一輪匿名承諾{ACom1,ACom2,···,AComm}和承諾{Com1,Com2,···,Comm}進行打包,形成特殊區塊.隨后,PPi向其他共識副本廣播提案消息,其消息格式為〈Sigi(Proposal,CP,v,h,Hash(Block)),Block〉,其中CP是承諾憑證,v是當前視圖編號,h是當前提案區塊高度,Hash(Block)是對區塊Block的消息摘要.潛在提案者PPi在提案之后退變為普通副本,參與后續投票過程.

2) 其他的副本節點Pj(j1,2,···,N),在收到潛在提案者PPi發送的提案后,檢查消息簽名是否正確、視圖編號是否一致,并驗證潛在提案者PPi身份的合法性,即判斷Hash(CP)OrderedComv是否成立.如果驗證通過,則向除自己之外的副本發送準備消息,即基于部分簽名的投票消息sj,具體消息格式為 〈PartSigj(Prepare,k,v,h,Hash(Block))〉,其中k是安全參數,v是視圖編號,h是區塊高度,Hash(Block)是對區塊Block的消息摘要.

3) 副本Pj收到大于等于t-1 個不同副本發來的對同一個區塊Block的部分簽名Prepare 消息后,首先驗證部分簽名是否正確、視圖編號是否一致;如果驗證通過,且連同自己的一條 Prepare 消息,對區塊Block的投票數達到預期門限值t時,副本Pj合成門限簽名ThresholdSigjThresholdSig(s1,s2,···,st),其中,sj(j1,2,···,t) 是基于部分簽名的投票消息.隨后,Pj向其他副本廣播提交消息,具體消息格式為〈ThresholdSigj(Commit,v,h,Hash(Block))〉,其中,v是視圖編號,h是區塊高度,Hash(Block)是對區塊Block的消息摘要.

4) 各副本只要收到一條對區塊Block的門限簽名消息,并且簽名驗證是正確的,視圖編號也一致時,則本輪提案在系統中達成共識,各副本狀態達成一致,此時即可將區塊信息寫入本地賬本,并令視圖編號vv+1 modm(m為有序承諾序列大小),進而開啟新一輪共識過程.

2.3 視圖轉換

視圖轉換協議負責主動更換提案者,啟動新視圖處理,使得提案者在失效的時候仍然保證系統的活性.設新的潛在提案者PPnewvnewv+1,當vnew0 modm時 (m為有序承諾序列大小),即為有序承諾序列中最后一位潛在提案者,此時令vnew0,并啟用新的有序承諾序列.

當副本等待時間超過預設值delay(t) 時,協議將觸發以避免副本陷入無限等待.其流程如下:

1) 當副本Pi進入視圖轉換后,令視圖編號vnewv+1,向其他副本廣播視圖轉換消息,其消息格式為〈Sigi(V iew-Change,vnew,h,PartSig,Threshold-Sig)〉,其中h為區塊高度,PartSig為在視圖v中發送的部分簽名消息,ThresholdSig為在視圖v中收到的門限簽名消息,如果沒有,則為NULL.

2) 其他副本Pj在收到視圖轉換消息后,同樣令視圖編號vnewv+1,廣播視圖轉換消息,其消息格式為〈Sigj(V iew-Change,vnew,h,PartSig,ThresholdSig)〉.

3) 潛在提案者PPnew利用收到的視圖轉換消息中的PartSig和ThresholdSig字段,構造新視圖消息:

a) 如果PPnew收到的視圖轉換消息中至少有一條合法的ThresholdSig消息,則向其他副本廣播新視圖消息,其消息格式為〈SigP Pnew(New-V iew,CP,vnew,h,ThresholdSig)〉.

b) 如果PPnew收到的視圖轉換消息中有t個對同一個區塊的部分簽名PartSig,則合成門限簽名ThresholdSig,并向其他副本廣播新視圖消息,其消息格式為〈SigP Pnew(New-V iew,CP,vnew,h,ThresholdSig)〉.

c) 如果PPnew既沒收到一條合法的門限簽名ThresholdSig,也沒有收到t個部分簽名PartSig,則選擇新的提案Blocknew,并向其他副本廣播新的提案消息,其消息格式為〈SigP Pnew(New-V iew,CP,vnew,h,Hash(Blocknew),Blocknew)〉.

4) 如果副本收到〈SigP Pnew(New-V iew,CP,vnew,h,ThresholdSig)〉消息,則認為跨視圖處理中系統狀態達成一致,并將區塊信息寫入本地賬本;如果副本收到〈SigP Pnew(New-V iew,CP,vnew,h,Hash(Blocknew),Blocknew)〉消息,繼續對新的提案Blocknew進行投票,處理過程與RBFT 類似,此處不再贅述.

視圖轉換協議算法如算法2 所示.

算法 2.視圖轉換協議

輸入.視圖轉換消息

輸出.新視圖主節點以及全局一致性的新視圖消息

3 安全分析與證明

3.1 安全性證明

門限簽名作為各副本驗證系統賬本狀態是否達成一致的標準,當門限值t設為 2f+1,則在達成一致結果中,可保證誠實副本數量大于非誠實副本數量,滿足系統安全性要求.

假設系統在高度h提交了兩個不同區塊,使系統產生分叉區塊,即Block1和Block2.如果要使分叉條件滿足,則需要Block1和Block2的投票數均達到門限值t,即滿足t1≥n-f且t2≥n-f,兩式相加得t1+t2≥2n-2f.根據系統假設,總副本數量為n,誠實副本在同一高度只會對Block1或Block2投一次票.假設惡意副本的數量達到系統所能容忍的最大值 (即為f),且惡意副本已經合謀,如果惡意副本要使系統產生分叉區塊,則需同時對Block1與Block2進行投票,進而得投票總數t1+t2≥n+f,代入式t1+t2≥2n-2f,得3f≥n.已知f ≤[(n-1)/3],與上式矛盾,故可證明系統在容錯范圍內無法分叉.

3.2 活性證明

系統活性指請求最終能夠被正確副本執行,本文所提RBFT 算法在提案前和提案后均能保證系統活性.

1)基于匿名選主的活性保障

現有大多數方案采用固定順序輪流選主方式,主節點的身份在提案之前已經暴露,敵手容易針對性地發起自適應攻擊,破壞系統活性.為了抵抗自適應攻擊,本方案基于關聯環簽名構造匿名排序選主算法,參與共識的副本構成環,環中成員基于確定的公開參數計算各自承諾,并以匿名方式公開,環中成員能夠在不泄露身份的前提下得到各自承諾在所有公開承諾中的排序位置,并根據排序位置依次被選為主節點進行提案.

潛在提案者可選擇在適當的時機將承諾打開,在提案者公開承諾之前,承諾使用哈希函數完美地隱藏了提案者身份,哈希函數的單向性特點使敵手不能獲得任何承諾內容,進而無法推斷承諾背后對應的副本身份,從而有效防止自適應攻擊,保證了系統在提案之前的活性.

2)基于視圖轉換的活性保障

楊小水沉默了好幾分鐘，然后才開口。沒想過還能見到那個畜生。大水過后，我再也沒想過那天的事。不是不想，是不敢想，害怕。我老是強迫自己忘了，可越強迫記憶反而越深刻，越折磨人。幾十年過去了，那事還像發生在昨天。

在本文所提RBFT 算法中,副本基于超時機制檢測潛在提案者狀態,通過觸發視圖轉換來保證協議活性.當觸發視圖轉換協議時,各副本廣播View-Change消息,系統安全性關鍵在于確保誠實副本接收到狀態一致的新視圖消息.View-Change消息包括兩個重要參數: 部門簽名PartSig和門限簽名ThresholdSig.ThresholdSig攜帶視圖v中法定人數的投票信息,使其能夠傳播到新視圖中.如果ThresholdSig為NULL,則由大于等于t(t2f+1)個部門簽名PartSig,即可合成門限簽名ThresholdSig,從而繼續在新視圖廣播,保證在跨視圖轉換時各副本狀態保持一致.

新視圖提案者由匿名選主算法產生,使得敵手在視圖轉換中也不能發起自適應攻擊破壞系統活性.綜上,本文所提的RBFT 算法無論在提案之前還是在提案之后都可以保證系統活性.

3.3 可用性分析

系統的可用性(Availability)指系統在面對各種網絡異常時可以正確提供服務的能力.面對聯盟鏈參與節點眾多,位置分散,網絡連接狀態不可預測等問題.本文所提RBFT 算法弱化“雙 2f+1 ”條件,保證只要存在任意一個狀態良好的節點能夠合成并傳達代表法定人數投票意愿的門限簽名,系統狀態即可達成一致.如圖4 所示 (圖4 為圖2 中紅色線條構成部分),以副本P2為例構成一個最小連通性網絡,即最小共識單元.在Proposal 階段,潛在提案者PP發布共識提案;在Prepare 階段,各副本對共識提案進行投票,廣播部分簽名,但由于網絡波動,除了副本P2,其他副本均沒有收到t(t2f+1)個來自不同副本的投票消息,于是只有P2能夠合成門限簽名;在Commit 階段,P2廣播代表法定人數投票的門限簽名,其他副本通過驗證該門限簽名的合法性,即可對投票結果的一致性進行驗證,從而保證在最小共識單元中實現全網共識.

圖4 最小連通性網絡Fig.4 Minimum connectivity network

從一致性上來講,門限簽名是由至少t個節點的部分簽名合成的,潛在提案者以及任何副本無法偽造門限簽名,所以如果驗證門限簽名是合法的,則代表至少有 2f+1 個副本投票同意本輪區塊提案.表1 對本文所提RBFT 算法和其他拜占庭容錯算法進行了性能分析與比較.可以看出,在擴展性方面,PBFT[8]、Tendermint[16]等共識算法需要進行兩兩交互來保證各副本狀態達成一致,其通信復雜度高達 O(n2),其性能會隨著節點數的增加而急劇下降,可擴展性差;并且每次交互均需 2f+1 個副本收到 2f+1 個相同的投票才能滿足系統一致性要求,魯棒性差.文獻[14-15]通過引入門限簽名降低了系統通信復雜度并提升了系統擴展性,但是這兩種方案都是由特定主節點收集副本節點的簽名來進行門限簽名的合成,這種方式嚴重依賴于主節點的可靠性,一旦主節點被敵手控制或成為一個拜占庭節點,將嚴重影響系統安全性和可用性,因此魯棒性差;并且主節點身份是完全暴露的,不能抵抗自適應攻擊.本文所提RBFT 算法,在提案前采用基于環簽名的匿名選主算法,隱藏了提案者的身份,能夠抵抗自適應攻擊;在提案后采用門限簽名算法在最小共識單元中即可實現全網共識,為防止主節點作惡,本文至少選擇f+1 個最小共識單元,保證至少存在一個非拜占庭副本能夠合成并傳達法定人數的投票意愿,即可在最小共識單元中達成共識,通信復雜度比文獻[14-15]略高,但系統魯棒性明顯增強.

表1 拜占庭容錯算法性能對比Table 1 The performance comparison of Byzantine fault tolerant algorithm

另外,從概率角度分析,假設每個副本在有效時間內收到法定人數投票的概率為p,則在具有n臺服務器的拜占庭容錯協議中,k個副本收到法定人數投票的事件服從二項分布,即其概率分布為

圖5 給出了n分別取16,31,46,61 時的概率分布曲線圖,可以看出,系統成功提案的概率隨著副本收到法定人數投票概率p的增大呈上升趨勢.很明顯,本文所提RBFT 算法整體上升趨勢較快,同等概率p下,RBFT 成功提案的概率遠大于PBFT,能夠自適應滿足不同網絡狀況的性能需求.RBFT算法在p≥0.6 時,成功提案的概率接近于“1”,即使在p0.4 時,系統也能以大于0.7 的概率保證各副本的狀態達成一致.反觀,PBFT 由于需要滿足“雙2f+1”條件,因此只有在網絡狀態非常良好的情況下,才能保證各副本的狀態達成一致,而在p ≤0.6時,PBFT 能夠達成一致的概率可以忽略不計.此外,在計算PBFT 成功提案的概率時,并沒有考慮拜占庭錯誤.假設系統存在f個拜占庭節點,則PBFT要求 2f+1個非拜占庭副本均收到 2f+1 條相同的提案才有可能達成共識,系統魯棒性極其脆弱;而RBFT 只要求在 2f+1 個非拜占庭副本中存在一個狀態良好的副本能夠傳達代表法定人數投票意愿的門限簽名,即可在最小連通性的網絡環境中達成共識,系統魯棒性表現較強.

圖5 狀態一致性概率曲線Fig.5 State consistency probability curve

4 實驗分析

本文參考聯盟鏈框架Hyperledger Fabric,并在此基礎上實現本文所提的RBFT 算法,同時選用PBFT 算法作參照,在同等硬件條件下采用區塊鏈性能測試工具Caliper 進行測試,分別得到PBFT 算法和本文所提RBFT 算法的網絡帶寬和吞吐量,以此來對比分析RBFT和PBFT 共識算法的性能優劣.本文實驗硬件采用2 核的Intel(R)Core(TM) i5 處理器,16 GB 內存的硬件平臺,采用四節點測試網絡拓撲,如圖6 所示.

圖6 網絡拓撲圖Fig.6 Network topology

本測試方案所用的測試用例包括測試鏈碼以及單元測試用例,測試鏈碼指區塊鏈系統應用層接口,單元測試用例指Caliper 工具調用區塊鏈系統應用層接口.鏈碼接口及對應功能,如表2 所示.

表2 鏈碼接口Table 2 Chain code interface

單元測試用例提供對四種鏈碼接口的調用,在執行測試用例過程中,啟用Caliper 工具對Docker 容器資源利用進行監測,每秒采樣一次,測試結束后獲取測試過程采樣值.

4.1 網絡帶寬

對PBFT 算法與本文所提的RBFT 算法設置相同的打包機制,以500 ms 為時間間隔進行打包,若有特殊配置請求直接打包區塊.首先對PBFT 算法與本文所提的RBFT 算法的帶寬占用量進行測試,周期性采樣流入和流出容器的數據量.測試中自變量為交易數量,對比隨著交易數量增加,總帶寬變化情況,以及不同交易類型對帶寬需求情況,測試結果如圖7(a)和圖7(b)所示,對比分析交易量增加時PBFT 算法與本文所提的RBFT 算法的網絡帶寬增加趨勢,測試結果如圖8 所示.

圖7 帶寬占用量矩形圖Fig.7 Bandwidth occupation histogram

圖8 帶寬占用量變化曲線圖Fig.8 Bandwidth occupation curves

由圖8 可得,兩種算法帶寬的占用隨交易數量的增加呈現線性增長趨勢,網絡中每增加一個區塊將產生一輪新共識,而每輪共識中若所有節點正常投票,在網絡中產生的消息量是相同的,所以帶寬占用將隨交易數量呈線性變化.比較發現,PBFT算法的增長趨勢較本文所提RBFT 算法增長趨勢大,因為PBFT 算法在共識過程中節點需要進行兩兩交互,導致系統通信復雜度高達 O(n2),而本文提出的RBFT 算法采用門限簽名弱化了“雙 2f+1 ”條件,能夠在最小連通性網絡達成共識,大大減少了網絡傳輸帶寬.

4.2 吞吐率

與網絡帶寬測試條件相同,圖9 顯示為隨著交易數量增長PBFT 算法與本文所提的RBFT 算法的吞吐率變化趨勢,可以看出本文所提的RBFT 算法性能略高.在本文所提的RBFT 算法中,通過合成代表大多數投票者意愿的門限簽名,弱化“雙2f+1”條件,保證了在最小連通性的網絡環境中實現低延遲、高魯棒性的拜占庭容錯共識算法,從而減少視圖更換等開銷.同時,由于門限簽名包含了法定人數投票意愿,其他副本只需驗證一條門限簽名即可對投票結果的一致性進行安全驗證,有效降低了簽名驗證復雜度.另外,由于實驗條件限制,實驗均在本地環境實現,節點之間網絡延遲較少,如果在聯盟鏈參與節點眾多、位置分散、網絡延遲較大的情況下,由第3.3 節可用性分析可知,本方案在性能方面會更具優勢.

圖9 吞吐率Fig.9 throughput

5 結束語

本文針對大多數拜占庭容錯算法難以抵抗自適應攻擊,并且存在可擴展性不足、魯棒性較差等問題,利用環簽名的無條件強匿名性以及門限簽名分散簽名權的特性,設計了一種契合聯盟鏈應用場景的高效健壯拜占庭容錯共識算法RBFT.該算法能夠在提案前匿名選取提案主節點,達到模糊敵手攻擊對象、抵抗自適應攻擊的目的;同時,利用門限簽名可實現對不同網絡狀況的自適應能力,以保證在最小連通性網絡環境中的拜占庭容錯共識.分析表明,該方案在減少系統開銷、提升可擴展性的同時,具有較高的安全性,在提案之前、提案之后均能有效地保證系統活性,為高可用拜占庭系統提供支持.