基于門限和環(huán)簽名的抗自適應(yīng)攻擊拜占庭容錯共識算法

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

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

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

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

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

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

1 預(yù)備知識

1.1 系統(tǒng)模型

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

圖1 聯(lián)盟鏈應(yīng)用場景Fig.1 Alliance chain application scenario

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

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

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

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

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

定義 1.共識節(jié)點.共識節(jié)點參與共識流程并保存區(qū)塊數(shù)據(jù),根據(jù)職責不同可分為: 潛在提案者和普通副本兩類.潛在提案者負責打包區(qū)塊、定時提案;普通副本負責對提案進行投票、達成一致.潛在提案者在提案之前隱藏身份,敵手無法發(fā)起自適應(yīng)攻擊;在提案之后暴露身份,退變?yōu)槠胀ǜ北?

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

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

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

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

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

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

1.2 環(huán)簽名

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

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

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

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

1.3 門限簽名

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

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

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

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

2 抗自適應(yīng)攻擊的健壯拜占庭容錯共識算法

在聯(lián)盟鏈中,節(jié)點和客戶端進入?yún)^(qū)塊鏈網(wǎng)絡(luò)需要進行權(quán)限認證,我們假設(shè)聯(lián)盟網(wǎng)絡(luò)中存在認證中心(Certificate authority,CA),為所有聯(lián)盟節(jié)點頒發(fā)相應(yīng)的公鑰證書,同時由于本方案引入了門限簽名和環(huán)簽名進行共識,所以CA 還需為門限簽名公鑰和環(huán)簽名公鑰頒發(fā)證書.

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

2.1 基于環(huán)簽名的匿名排序選主算法

本節(jié)基于關(guān)聯(lián)環(huán)簽名構(gòu)造無條件匿名和計算綁定的公開承諾,每個副本Pj(j1,2,···,N) 計算承諾如下:

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

其中,k為安全參數(shù),L為公鑰集合,Link為關(guān)聯(lián)標簽.本文的關(guān)聯(lián)環(huán)簽名參考文獻[23]中的算法,但將關(guān)聯(lián)標簽修改為

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

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

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

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

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

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

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

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

輸入.提案區(qū)塊

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

RBFT 算法詳細流程如下:

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

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

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

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

2.3 視圖轉(zhuǎn)換

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

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

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

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

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

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

b) 如果PPnew收到的視圖轉(zhuǎn)換消息中有t個對同一個區(qū)塊的部分簽名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)〉消息,則認為跨視圖處理中系統(tǒng)狀態(tài)達成一致,并將區(qū)塊信息寫入本地賬本;如果副本收到〈SigP Pnew(New-V iew,CP,vnew,h,Hash(Blocknew),Blocknew)〉消息,繼續(xù)對新的提案Blocknew進行投票,處理過程與RBFT 類似,此處不再贅述.

視圖轉(zhuǎn)換協(xié)議算法如算法2 所示.

算法 2.視圖轉(zhuǎn)換協(xié)議

輸入.視圖轉(zhuǎn)換消息

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

3 安全分析與證明

3.1 安全性證明

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

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

3.2 活性證明

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

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

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

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

2)基于視圖轉(zhuǎn)換的活性保障

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

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

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

3.3 可用性分析

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

圖4 最小連通性網(wǎng)絡(luò)Fig.4 Minimum connectivity network

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

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

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

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

圖5 狀態(tài)一致性概率曲線Fig.5 State consistency probability curve

4 實驗分析

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

圖6 網(wǎng)絡(luò)拓撲圖Fig.6 Network topology

本測試方案所用的測試用例包括測試鏈碼以及單元測試用例,測試鏈碼指區(qū)塊鏈系統(tǒng)應(yīng)用層接口,單元測試用例指Caliper 工具調(diào)用區(qū)塊鏈系統(tǒng)應(yīng)用層接口.鏈碼接口及對應(yīng)功能,如表2 所示.

表2 鏈碼接口Table 2 Chain code interface

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

4.1 網(wǎng)絡(luò)帶寬

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

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

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

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

4.2 吞吐率

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

圖9 吞吐率Fig.9 throughput

5 結(jié)束語

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