周 煒， 袁曉偉， 魏志強(qiáng)， 翟翌立， 王 超， 杜丙瑜， 朱文印， 王金龍

(1.青島理工大學(xué)信息與控制工程學(xué)院， 山東 青島 266100； 2.海爾集團(tuán)技術(shù)研發(fā)中心， 山東 青島 266100；3.中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100)

伴隨著區(qū)塊鏈的發(fā)展，截至目前塊鏈大致可以分為三類：公有鏈、聯(lián)盟鏈、私有鏈。而不同類型的鏈會(huì)有不同的共識(shí)，公有鏈共識(shí)大致可以分為三類：基于算力競(jìng)爭(zhēng)記賬權(quán)的POW共識(shí)[1]、基于權(quán)益證明的POS共識(shí)[2]、基于POW共識(shí)和POS共識(shí)的改進(jìn)，例如Casper FFG共識(shí)[3]、POA共識(shí)[4]、POSV共識(shí)[5]。聯(lián)盟鏈共識(shí)大致分為兩類：一類是非拜占庭容錯(cuò)共識(shí)，這類共識(shí)不考慮節(jié)點(diǎn)采取惡意攻擊行為，只考慮崩潰節(jié)點(diǎn)不工作不回應(yīng)的情況，例如PAXOS共識(shí)[6]、RAFT共識(shí)[7]。另一類是拜占庭容錯(cuò)共識(shí)，這類共識(shí)會(huì)考慮超時(shí)錯(cuò)誤、回應(yīng)錯(cuò)誤信息、節(jié)點(diǎn)串通攻擊等情況，例如PBFT共識(shí)。私有鏈與以上兩種鏈不同，它大部分被使用于組織與集體內(nèi)部不對(duì)外公開(kāi)，不過(guò)共識(shí)大部分采用PBFT、PAXOS、RAFT等共識(shí)。

目前無(wú)論是社會(huì)結(jié)構(gòu)還是網(wǎng)絡(luò)服務(wù)結(jié)構(gòu)都是由幾個(gè)大型組織作為中心，完全去中心化顯然不符合目前發(fā)展階段，多個(gè)組織合作的聯(lián)盟鏈比較符合當(dāng)下的發(fā)展。目前一部分聯(lián)盟鏈?zhǔn)褂梅前菡纪ト蒎e(cuò)共識(shí)。非拜占庭共識(shí)的優(yōu)點(diǎn)是交易吞吐量大、延遲低。但是非拜占庭容錯(cuò)共識(shí)無(wú)法防止節(jié)點(diǎn)對(duì)系統(tǒng)的惡意攻擊，考慮到聯(lián)盟鏈?zhǔn)嵌鄠€(gè)組織參與，因此這類共識(shí)在實(shí)際場(chǎng)景中安全性很低，沒(méi)有實(shí)用價(jià)值?？紤]到聯(lián)盟鏈系統(tǒng)安全性問(wèn)題，本文針對(duì)拜占庭容錯(cuò)算法進(jìn)行研究，選取目前應(yīng)用最普遍的PBFT共識(shí)[8]。PBFT是一種基于部分異步網(wǎng)絡(luò)模型的拜占庭容錯(cuò)算法，它通過(guò)三階段提交過(guò)程保證了節(jié)點(diǎn)之間的一致性，通過(guò)節(jié)點(diǎn)之間相互傳遞簽名消息保證安全性，通過(guò)超時(shí)檢測(cè)和主節(jié)點(diǎn)切換保證活性。一致性保證了節(jié)點(diǎn)之間確認(rèn)的消息是一樣的，安全性保證了節(jié)點(diǎn)可以判斷消息是否正確，活性保證了系統(tǒng)不會(huì)出現(xiàn)一直等待不工作的狀況。

雖然拜占庭容錯(cuò)PBFT共識(shí)目前發(fā)展的比較成熟，但目前還存在一些問(wèn)題。首先，雖然節(jié)點(diǎn)兩兩之間相互通信可以保證節(jié)點(diǎn)判斷消息的正確性，但造成通信復(fù)雜度過(guò)高((O(n2))。由于消息確認(rèn)需要兩次且隨著節(jié)點(diǎn)數(shù)量變多，通信復(fù)雜度會(huì)增長(zhǎng)過(guò)快，進(jìn)而影響系統(tǒng)可擴(kuò)展性。其次，雖然PBFT共識(shí)采用主從模式保證了交易順序的一致性，但是導(dǎo)致了通信會(huì)集中于主節(jié)點(diǎn)，引起主節(jié)點(diǎn)通信壓力過(guò)大。最后，PBFT共識(shí)失敗率高。采用主節(jié)點(diǎn)輪次交換的方式，而在3f+1個(gè)節(jié)點(diǎn)中，如果有f個(gè)拜占庭節(jié)點(diǎn)，輪換到錯(cuò)誤節(jié)點(diǎn)的概率接近1/3，共識(shí)失敗率較高，會(huì)導(dǎo)致主節(jié)點(diǎn)切換頻繁，共識(shí)效率下降。

隨著現(xiàn)代計(jì)算機(jī)和互聯(lián)網(wǎng)的發(fā)展，數(shù)據(jù)規(guī)模不斷增長(zhǎng)，處理的數(shù)據(jù)量越來(lái)越大，單一節(jié)點(diǎn)處 理數(shù)據(jù)和存儲(chǔ)數(shù)據(jù)壓力越來(lái)越大，分布式系統(tǒng)在提高數(shù)據(jù)處理效率同時(shí)保證了系統(tǒng)可靠性，緩解節(jié)點(diǎn)存儲(chǔ)壓力。不過(guò)分布式系統(tǒng)在多節(jié)點(diǎn)合作協(xié)調(diào)一致性方面存在技術(shù)挑戰(zhàn)，因此分布式系統(tǒng)中如何保證共識(shí)是個(gè)經(jīng)典的技術(shù)問(wèn)題。

共識(shí)協(xié)議從大的方面可分為自比特幣誕生以來(lái)產(chǎn)生的POW等中本聰共識(shí)協(xié)議和拜占庭容錯(cuò)(BFT)類共識(shí)協(xié)議這兩大類協(xié)議。其中，在計(jì)算機(jī)科學(xué)的分布式系統(tǒng)研究領(lǐng)域，近年來(lái)，越來(lái)越多的聯(lián)盟鏈平臺(tái)大部分集中在對(duì)BFT類共識(shí)協(xié)議的研究。由此本文對(duì)BFT類協(xié)議進(jìn)行了綜述性概覽分析，并從改進(jìn)思路上將現(xiàn)有BFT類共識(shí)協(xié)議分為三大類：針對(duì)無(wú)拜占庭錯(cuò)誤場(chǎng)景優(yōu)化的協(xié)議、針對(duì)拜占庭錯(cuò)誤場(chǎng)景優(yōu)化的協(xié)議以及為公鏈應(yīng)用而優(yōu)化的協(xié)議。

針對(duì)無(wú)拜占庭錯(cuò)誤場(chǎng)景進(jìn)行優(yōu)化又分為基于協(xié)約方法的優(yōu)化，例如Chain協(xié)議[9]、Ring協(xié)議[10]、BFT-SMaRt協(xié)議[11]；基于Quorum方法的優(yōu)化，例如Q/U協(xié)議(Query/Update)[12]、HQ協(xié)議(Hybrid Quorum)[13]、Quorum協(xié)議[14]；基于Speculation方法的優(yōu)化，例如Zyzzyva協(xié)議[15]、Zeno協(xié)議[16]、ZZ協(xié)議[17]；基于客戶端方法的優(yōu)化，例如OBFT(Obfuscated BFT)協(xié)議[18]；基于可信組件方法的優(yōu)化，例如CheapBFT協(xié)議[19]；基于拜占庭鎖方法的優(yōu)化，例如Zzyzx協(xié)議[20]；基于分離一致性與執(zhí)行請(qǐng)求方法的優(yōu)化，例如ODRC協(xié)議[21]。

上面介紹的一類協(xié)議均是針對(duì)沒(méi)有錯(cuò)誤的場(chǎng)景對(duì)BFT協(xié)議進(jìn)行簡(jiǎn)化而設(shè)計(jì)，因此當(dāng)遇到拜占庭錯(cuò)誤時(shí)，這類協(xié)議的性能一般都會(huì)下降比較多，甚至很難保證系統(tǒng)活性。而另一類針對(duì)有錯(cuò)誤的場(chǎng)景對(duì)BFT協(xié)議的改進(jìn)目的是為了有效對(duì)拜占庭行為(甚至是一些罕見(jiàn)的行為)進(jìn)行容錯(cuò)，降低系統(tǒng)在有無(wú)拜占庭錯(cuò)誤這兩種場(chǎng)景下的表現(xiàn)差異。其中比較典型的協(xié)議，例如Aardvark協(xié)議[22]、Prime協(xié)議[23]、Spinning協(xié)議[24]、Redundant-BFT協(xié)議[25]。

傳統(tǒng)PBFT及類似協(xié)議，其自身的特性導(dǎo)致應(yīng)用場(chǎng)景有較多限制，例如消息復(fù)雜度隨節(jié)點(diǎn)數(shù)成平方級(jí)別上升、主節(jié)點(diǎn)容易成為系統(tǒng)性能瓶頸、節(jié)點(diǎn)列表需要提前固定且節(jié)點(diǎn)間相互已知。所以在分布式賬本系統(tǒng)中，更多應(yīng)用于聯(lián)盟鏈或私有鏈場(chǎng)景中。為了適應(yīng)公有鏈場(chǎng)景中的大規(guī)模擴(kuò)展需求，有不少項(xiàng)目進(jìn)行了有益嘗試，具體方式可主要包括與公鏈共識(shí)結(jié)合以及基于密碼學(xué)機(jī)制等兩大類方式。與公鏈共識(shí)結(jié)合的典型協(xié)議，例如DPOS+BFT協(xié)議[26]、DBFT協(xié)議[27]、Tendermint BFT協(xié)議[28]、FBA協(xié)議[29]；基于密碼學(xué)優(yōu)化的典型協(xié)議，例如基于聚合簽名的Zilliqa[30]、基于可驗(yàn)證隨機(jī)函數(shù)的VBFT協(xié)議[31]、基于門限簽名的HoneyBadger BFT[32]。

通過(guò)以上分析發(fā)現(xiàn)，區(qū)塊鏈共識(shí)算法及其變種都集中在PBFT算法上，所以本文選取了部分同步網(wǎng)絡(luò)模型的PBFT算法作為研究對(duì)象。

PBFT算法是一種狀態(tài)機(jī)副本復(fù)制算法，所有副本在視圖編號(hào)v的輪轉(zhuǎn)中運(yùn)行，視圖是連續(xù)編號(hào)的整數(shù)，在同一視圖編號(hào)下，節(jié)點(diǎn)角色被分為客戶端、主節(jié)點(diǎn)和從節(jié)點(diǎn)?？蛻舳耸钦?qǐng)求的發(fā)送方，主節(jié)點(diǎn)負(fù)責(zé)接收客戶端的請(qǐng)求，并且按照順序?qū)φ?qǐng)求進(jìn)行排序，從節(jié)點(diǎn)主要是負(fù)責(zé)檢查從主節(jié)點(diǎn)接收到的請(qǐng)求，并且通過(guò)超時(shí)機(jī)制檢測(cè)主節(jié)點(diǎn)是否宕機(jī)，當(dāng)發(fā)生出節(jié)點(diǎn)宕機(jī)時(shí)，觸發(fā)視圖切換機(jī)制。

結(jié)合PBFT共識(shí)存在拜占庭節(jié)點(diǎn)情況下，共識(shí)失敗率較高，節(jié)點(diǎn)數(shù)量多主節(jié)點(diǎn)通信壓力過(guò)大，整體共識(shí)通信復(fù)雜度增長(zhǎng)過(guò)快的問(wèn)題，本文提出了一種分組混合共識(shí)機(jī)制，首先通過(guò)概率分組算法找出共識(shí)概率達(dá)成最高的分組方式，然后所有節(jié)點(diǎn)基于可驗(yàn)證隨機(jī)函數(shù)VRF[31]通過(guò)兩輪消息投票方式確認(rèn)分組信息，接下來(lái)分組內(nèi)部開(kāi)始進(jìn)行拜占庭容錯(cuò)chain-raft共識(shí)，按照下文中設(shè)計(jì)的算法流程在分組內(nèi)達(dá)成共識(shí)，最后，分組主節(jié)點(diǎn)之間按照PBFT共識(shí)流程達(dá)成最終共識(shí)。分組混合共識(shí)機(jī)制其中概率分組算法提高共識(shí)達(dá)成概率，減少主節(jié)點(diǎn)切換次數(shù)從而提高在存在拜占庭錯(cuò)誤情況下共識(shí)性能；隨機(jī)分組過(guò)程利用可驗(yàn)證隨機(jī)函數(shù)VRF確保節(jié)點(diǎn)之間不能串通，保證了共識(shí)的活性與安全性；混合共識(shí)算法組內(nèi)使用拜占庭容錯(cuò)chain-raft共識(shí)，引入聚合簽名使得通信復(fù)雜度為O(n)并且優(yōu)化了共識(shí)流程，縮短了整體共識(shí)時(shí)間；組間繼續(xù)使用PBFT共識(shí)，保證分組之間拜占庭容錯(cuò)，進(jìn)一步加強(qiáng)共識(shí)安全性。

針對(duì)PBFT共識(shí)存在的問(wèn)題，本文提出了一種適合聯(lián)盟鏈的分組混合共識(shí)機(jī)制。之所以適合聯(lián)盟鏈，是因?yàn)槁?lián)盟鏈?zhǔn)菧?zhǔn)入制可以知道系統(tǒng)中有多少個(gè)參與節(jié)點(diǎn)，有利于分組構(gòu)建。之所以分組，是因?yàn)楣?jié)點(diǎn)進(jìn)行分組，雖然增加了一個(gè)分組過(guò)程，但是重新分組只會(huì)發(fā)生在最終共識(shí)達(dá)成失敗的情況，根據(jù)本文概率分組算法，共識(shí)失敗率低于PBFT共識(shí)，因此緩解了共識(shí)失敗主節(jié)點(diǎn)切換頻繁造成的通信壓力，并且此分組過(guò)程也保證了系統(tǒng)活性。然后分組之后每組都有主節(jié)點(diǎn)，此方式會(huì)緩解主從模式主節(jié)點(diǎn)作為通信中心的壓力。隨機(jī)分組讓拜占庭節(jié)點(diǎn)無(wú)法預(yù)知分組結(jié)果進(jìn)而串通攻擊分組，保證了系統(tǒng)安全性。之所以要混合共識(shí)，一方面本文拜占庭容錯(cuò)chain-raft算法在拜占庭容錯(cuò)的基礎(chǔ)上通信復(fù)雜度為(O(n))，并且借鑒HotStuff共識(shí)[33]流水線化的共識(shí)流程，讓先后兩筆交易不同階段同時(shí)進(jìn)行，縮短了上述共識(shí)算法的時(shí)間。另一方面，考慮到聯(lián)盟鏈目前大部分使用PBFT共識(shí)，本文設(shè)計(jì)的共識(shí)機(jī)制可以作為PBFT共識(shí)的一種擴(kuò)展，這樣可以很好的兼容當(dāng)前的PBFT共識(shí)。

本文的貢獻(xiàn)在于：一是采用概率分組算法，提高共識(shí)達(dá)成概率；二是采用隨機(jī)分組過(guò)程，防止拜占庭節(jié)點(diǎn)串通，保證共識(shí)安全性；三是提出一種新的組內(nèi)拜占庭容錯(cuò)chain-raft共識(shí)，在拜占庭容錯(cuò)的基礎(chǔ)上引入共識(shí)流程并行化，優(yōu)化共識(shí)流程，組間繼續(xù)使用PBFT共識(shí)算法，保證了分組拜占庭容錯(cuò)和對(duì)已有PBFT共識(shí)算法的兼容性。

1 分組混合共識(shí)機(jī)制

本文構(gòu)建了基于分組混合共識(shí)機(jī)制，如圖1所示其中分為三個(gè)階段，分別進(jìn)行介紹。

圖1 分組混合共識(shí)機(jī)制架構(gòu)圖

概率分組階段：PBFT共識(shí)算法若有3f+1個(gè)節(jié)點(diǎn)，最多可容納f個(gè)拜占庭節(jié)點(diǎn)，共識(shí)失敗率最高接近1/3，導(dǎo)致頻繁觸發(fā)viewchange切換主節(jié)點(diǎn)拖慢系統(tǒng)性能。根據(jù)概率分組可以降低共識(shí)失敗率提高系統(tǒng)性能。

隨機(jī)化分組階段：PBFT共識(shí)算法隨著節(jié)點(diǎn)數(shù)量的增加，節(jié)點(diǎn)間通信復(fù)雜度增長(zhǎng)過(guò)快，主節(jié)點(diǎn)通信壓力會(huì)越來(lái)越大，分組后先組內(nèi)共識(shí)，然后組間共識(shí)，降低了通信復(fù)雜度同時(shí)減緩了通信復(fù)雜度增長(zhǎng)速度，組內(nèi)有主節(jié)點(diǎn)，組間有主節(jié)點(diǎn)，降低了單一主節(jié)點(diǎn)通信壓力。隨機(jī)化分組的目的是為了防止拜占庭節(jié)點(diǎn)可能會(huì)串通攻擊一定數(shù)量的分組破壞共識(shí)達(dá)成，因此使用可驗(yàn)證VRF隨機(jī)函數(shù)隨機(jī)分組讓每個(gè)節(jié)點(diǎn)無(wú)法預(yù)先判斷分到哪個(gè)組，從而保證共識(shí)活性。

混合共識(shí)階段：如果只是PBFT共識(shí)分組，組內(nèi)還是PBFT共識(shí)，通信復(fù)雜度為o(n2)，因此組內(nèi)使用拜占庭容錯(cuò)的chain-raft共識(shí)，通過(guò)聚合簽名確認(rèn)消息，并且并行化共識(shí)階段，共識(shí)通信復(fù)雜度為o(n)，進(jìn)一步降低了系統(tǒng)通信復(fù)雜度，而且組間PBFT共識(shí)，保證分組間拜占庭容錯(cuò)和已有PBFT共識(shí)算法的兼容性。

1.1 概率分組算法

概率分組算法的步驟：

第一步：先求解出組數(shù)滿足N>=3f+1和組內(nèi)節(jié)點(diǎn)數(shù)滿足N>=3f+1的分組方式求解算法如表1。

表1 分組算法

第二步：根據(jù)已經(jīng)求出的分組方式，求出該分組方式的拜占庭容錯(cuò)節(jié)點(diǎn)個(gè)數(shù)，求出該分組方式達(dá)成共識(shí)的概率，例如總共有16個(gè)節(jié)點(diǎn)，分為4組，每組有4個(gè)節(jié)點(diǎn)，該分組方式拜占庭容錯(cuò)節(jié)點(diǎn)個(gè)數(shù)為5個(gè)，達(dá)成共識(shí)的概率為

(1)

第三步：在滿足達(dá)成共識(shí)概率最高和容納拜占庭節(jié)點(diǎn)最多的條件下得出分組方式。

本文概率分組算法不僅提高共識(shí)達(dá)成概率，還發(fā)現(xiàn)在同樣的節(jié)點(diǎn)數(shù)，不同的分組方式會(huì)影響達(dá)成共識(shí)的概率。根據(jù)拜占庭容錯(cuò)，N≥3f+1，其中N是節(jié)點(diǎn)總數(shù)，f是拜占庭節(jié)點(diǎn)數(shù)。如果有28個(gè)節(jié)點(diǎn)分為4組，一組為7個(gè)節(jié)點(diǎn)，這種分組方式若有9個(gè)拜占庭節(jié)點(diǎn)，達(dá)成共識(shí)的概率為:

(2)

若分為7組每組4個(gè)節(jié)點(diǎn)，這種分組方式若為9個(gè)拜占庭節(jié)點(diǎn)共識(shí)達(dá)成概率為

(3)

同樣節(jié)點(diǎn)分組變多會(huì)提升共識(shí)的達(dá)成概率。

1.2 隨機(jī)分組過(guò)程

如果分組按照一定的規(guī)則，例如選取分組，分組結(jié)果就是可預(yù)測(cè)的，拜占庭節(jié)點(diǎn)非常容易串通破壞共識(shí)，例如，有16個(gè)節(jié)點(diǎn)，分成4組，每組有4個(gè)節(jié)點(diǎn)，根據(jù)拜占庭共識(shí)結(jié)論，N>=3f+1，所以總體最多可以允許5個(gè)拜占庭節(jié)點(diǎn)，每個(gè)分組只能允許1個(gè)拜占庭節(jié)點(diǎn)，允許一個(gè)分組為拜占庭分組，假如這5個(gè)節(jié)點(diǎn)串通，分成2和3分別分入兩個(gè)分組之中，就會(huì)導(dǎo)致兩個(gè)拜占庭分組出現(xiàn)從而導(dǎo)致整體無(wú)法達(dá)成共識(shí)。為此本文提出一種結(jié)合可驗(yàn)證隨機(jī)函數(shù)VRF[31]的隨機(jī)分組過(guò)程，分為隨機(jī)分組信息生成和隨機(jī)分組信息的確認(rèn)。

哈希函數(shù)其值域是離散的、均勻分布的，給定不同的輸入值，其輸出值沒(méi)有規(guī)律，隨機(jī)的灑落、分布在值域區(qū)間內(nèi)，因此，哈希函數(shù)的輸出值是無(wú)法預(yù)知的，從而保證分組信息的隨機(jī)性。VRF是一種結(jié)合非對(duì)稱密鑰技術(shù)的哈希函數(shù)，具體流程：

①證明者計(jì)算proof=VRF_PROVE(sk,info)，sk是私鑰。

②證明者把proof和info公布出去。

③驗(yàn)證者計(jì)算True/False=VRF_Verify(proof,info,pk)，pk是公鑰。

隨機(jī)分組信息的確認(rèn)采用二次確認(rèn)過(guò)程，這樣保證了部分同步網(wǎng)絡(luò)模型下節(jié)點(diǎn)之間的一致性。

步驟如圖2所示：

圖2 隨機(jī)分組信息確認(rèn)流程

第一步：主節(jié)點(diǎn)根據(jù)自己的私鑰sk簽名接收到client的信息作為data-sk，當(dāng)前輪數(shù)作為n，分組信息作為VRF_PROVE的info，不斷隨機(jī)info計(jì)算出自己這一輪的proof。如果滿足抽簽閾值，就廣播到其他節(jié)點(diǎn)驗(yàn)證。

第二步：副本節(jié)點(diǎn)收到驗(yàn)證信息，查看輪數(shù)n是否比之前的大，然后驗(yàn)證VRF_Verify(proof,info,pk)，如果驗(yàn)證通過(guò)就用私鑰簽名確認(rèn)信息并回復(fù)。

第三步：主節(jié)點(diǎn)接收到回復(fù)，如果收到2f+1的節(jié)點(diǎn)簽名確認(rèn)就組合成data-sk-list，然后廣播到其他節(jié)點(diǎn)，其他副本節(jié)點(diǎn)驗(yàn)證消息是否得到了2f+1個(gè)節(jié)點(diǎn)簽名并且驗(yàn)證VRF_Verify(proof,info,pk)是否通過(guò)，若通過(guò)再次用私鑰簽名確認(rèn)回復(fù)。

第四步：主節(jié)點(diǎn)收集到2f+1個(gè)節(jié)點(diǎn)簽名確認(rèn)信息，發(fā)送信息到其他副本節(jié)點(diǎn)，副本節(jié)點(diǎn)通過(guò)最終的proof確認(rèn)對(duì)應(yīng)的分組信息。上述四步消息格式如表2。

表2 發(fā)送接受對(duì)象之間的消息格式

1.3 mix-raft-pbft混合共識(shí)算法

如圖3所示，mix-raft-pbft共識(shí)流程分為組內(nèi)共識(shí)和組間共識(shí)，其中組內(nèi)共識(shí)是拜占庭容錯(cuò)chain-raft算法分為兩個(gè)階段保證部分同步網(wǎng)絡(luò)模型下數(shù)據(jù)的一致性，其中包含組內(nèi)預(yù)確認(rèn)階段和組內(nèi)確認(rèn)階段。組內(nèi)共識(shí)階段：①組內(nèi)主節(jié)點(diǎn)用私鑰簽名接收到的client交易數(shù)據(jù)data，生成交易數(shù)據(jù)哈希值data-hash保證數(shù)據(jù)的完整性，為這筆交易數(shù)據(jù)標(biāo)記唯一data-ID，組成消息發(fā)送到副本節(jié)點(diǎn)；②副本節(jié)點(diǎn)接收到消息，用主節(jié)點(diǎn)公鑰pk解密消息，首先驗(yàn)證交易數(shù)據(jù)data-ID是否已經(jīng)存在，若已存在拒絕接收，若不存在繼續(xù)驗(yàn)證交易數(shù)據(jù)data是否與data-hash一致，若一致用私鑰簽名確認(rèn)回復(fù)消息；③主節(jié)點(diǎn)接收到其他副本節(jié)點(diǎn)消息確認(rèn)當(dāng)超過(guò)2f+1個(gè)確認(rèn)主節(jié)點(diǎn)組合簽名data-sk-list，然后發(fā)送其他副本節(jié)點(diǎn)消息；④副本節(jié)點(diǎn)接收到消息，確認(rèn)data-ID是否存在pre-commit 消息，驗(yàn)證主節(jié)點(diǎn)簽名，驗(yàn)證data-sk-list 簽名集合是否超過(guò)2f+1，驗(yàn)證通過(guò)回復(fù)消息到主節(jié)點(diǎn)。組間共識(shí)階段組間節(jié)點(diǎn)之間完成三階段PBFT共識(shí)。

圖3 mix-raft-pbft共識(shí)流程

以上描述的拜占庭容錯(cuò)chain-raft算法共識(shí)流程是一筆交易先進(jìn)行pre-commit階段，主節(jié)點(diǎn)收集簽名集合data-sk-list，然后進(jìn)入commit階段主節(jié)點(diǎn)再次收集簽名集合data-sk-list，這個(gè)流程交易是一筆交易走完兩個(gè)階段然后下一筆交易再次走完這兩個(gè)階段，其實(shí)當(dāng)主節(jié)點(diǎn)正在進(jìn)行第一筆交易commit階段的時(shí)候，可以同時(shí)發(fā)送第二筆交易的pre-commit消息，這樣主節(jié)點(diǎn)就可以同時(shí)收到副本節(jié)點(diǎn)第一筆commit-ack回復(fù)和第二筆交易的pre-commit-ack回復(fù)，優(yōu)化了共識(shí)流程，如圖4所示。

圖4 chain-raft流程優(yōu)化圖

1.4 共識(shí)算法分析

1.4.2 安全性分析 隨機(jī)分組防止了拜占庭節(jié)點(diǎn)之間的串通，分組需要2f+1個(gè)節(jié)點(diǎn)確認(rèn)，保證在最多f個(gè)拜占庭節(jié)點(diǎn)的條件下，分組可以正確完成。

組內(nèi)chain-raft共識(shí)不存在同一個(gè)交易ID中不同的交易都能收到足夠多投票的情況，保證最終存儲(chǔ)的一致性。

證明：假設(shè)N=3f+1為節(jié)點(diǎn)總數(shù)，f為拜占庭節(jié)點(diǎn)最大數(shù)量，那么當(dāng)收到2f+1投票為足夠多投票。因兩個(gè)區(qū)塊都收到至少2f+1，投票總量至少為 2(2f+1)=N+f+1，能看到至少有f+1對(duì)同一個(gè)交易ID中不同的交易都投了票，與f個(gè)拜占庭節(jié)點(diǎn)假設(shè)矛盾。

1.4.3 活性分析 活性指的是所有好的事情一定發(fā)生，就是要在一定時(shí)間范圍內(nèi)完成整個(gè)共識(shí)過(guò)程，并保證所有誠(chéng)實(shí)節(jié)點(diǎn)提交一致性結(jié)果。共識(shí)算法活性出現(xiàn)的原因主要是節(jié)點(diǎn)之間可能存在的傳輸延遲，傳輸延遲會(huì)導(dǎo)致節(jié)點(diǎn)無(wú)法產(chǎn)生一致性結(jié)果。

隨機(jī)分組過(guò)程活性主節(jié)點(diǎn)必須在一定時(shí)間內(nèi)收集到2/3個(gè)節(jié)點(diǎn)簽名，如果在一定時(shí)間內(nèi)沒(méi)有收集到足夠的簽名，其他節(jié)點(diǎn)會(huì)代替主節(jié)點(diǎn)，在N>=3f+1的條件下，一定時(shí)間內(nèi)是可以保障主節(jié)點(diǎn)活性。

組內(nèi)拜占庭chain-raft共識(shí)算法中，活性主要體現(xiàn)在隨機(jī)超時(shí)時(shí)間t的設(shè)立。t∈[T,2T]并且滿足T>=randomtime的條件，以避免因?yàn)橄⒀舆t而導(dǎo)致的不必要的主節(jié)點(diǎn)切換，同時(shí)t的設(shè)立又可以讓系統(tǒng)在有限的時(shí)間內(nèi)產(chǎn)生一個(gè)主節(jié)點(diǎn)，保證系統(tǒng)的正常運(yùn)行。

2 仿真實(shí)驗(yàn)

本文通過(guò)go語(yǔ)言實(shí)現(xiàn)PBFT和分組混合共識(shí)機(jī)制，使用線程監(jiān)聽(tīng)不同的端口代替節(jié)點(diǎn)，線程之間的交互使用TCP協(xié)議，模擬分布式系統(tǒng)共識(shí)過(guò)程。環(huán)境中包含RSA信息加解密過(guò)程和網(wǎng)絡(luò)信息傳遞延遲，如表3所示。

表3 實(shí)驗(yàn)環(huán)境

2.1 模擬網(wǎng)絡(luò)信息通信延遲

本文混合共識(shí)適用于聯(lián)盟鏈，聯(lián)盟鏈?zhǔn)褂谜叽蟛糠譃槠髽I(yè)，因此模擬企業(yè)最普遍的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)星型結(jié)構(gòu)，依照此結(jié)構(gòu)計(jì)算網(wǎng)絡(luò)信息傳遞延遲。

圖5為n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，任意兩個(gè)節(jié)點(diǎn)ni,nj的延遲，若(ni,nj)?同一個(gè)hub，延遲為30～50 ms，若(ni,nj)?同一個(gè)hub，若相隔hub個(gè)數(shù)為k，延遲為30～50 kms。節(jié)點(diǎn)延遲是一個(gè)包含幾個(gè)值的集合，這些值用于模擬節(jié)點(diǎn)路由到不同節(jié)點(diǎn)之間的延遲。

圖5 星型網(wǎng)絡(luò)結(jié)構(gòu)

2.2 共識(shí)實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)從共識(shí)時(shí)延和吞吐量?jī)蓚€(gè)方面對(duì)比PBFT與分組混合共識(shí)機(jī)制，結(jié)果如下

圖6是在本文算法在100筆交易，隨著節(jié)點(diǎn)數(shù)量增加，共識(shí)時(shí)間對(duì)比。chain-raft共識(shí)隨著節(jié)點(diǎn)數(shù)增加，共識(shí)時(shí)間接近線性增長(zhǎng)趨勢(shì)，而pbft共識(shí)接近多項(xiàng)式級(jí)平方增長(zhǎng)。本文混合共識(shí)機(jī)制組內(nèi)使用拜占庭容錯(cuò)chain-raft共識(shí)，降低了整體共識(shí)的消息復(fù)雜度和共識(shí)時(shí)間，提高了系統(tǒng)性能。

圖6 共識(shí)時(shí)延對(duì)比

圖7是本文共識(shí)在100筆交易分為四組的情況下與PBFT共識(shí)在不同節(jié)點(diǎn)下的對(duì)比，可以看出PBFT隨著節(jié)點(diǎn)數(shù)量增加，共識(shí)時(shí)間迅速增加，而本文共識(shí)由于分組，在分為4組的情況下，組間共識(shí)時(shí)間基本不變，而組內(nèi)共識(shí)時(shí)延增長(zhǎng)為線性、組內(nèi)節(jié)點(diǎn)數(shù)量增加緩慢并且分組之間共識(shí)并行化，最終整體達(dá)成共識(shí)時(shí)間增加緩慢。隨著節(jié)點(diǎn)的增加與PBFT共識(shí)時(shí)間的優(yōu)勢(shì)會(huì)越來(lái)越大。

圖7 共識(shí)時(shí)延對(duì)比

圖8是本文共識(shí)算法在10筆交易，100個(gè)節(jié)點(diǎn)分為不同組數(shù)情況下的共識(shí)時(shí)間。因?yàn)榻M間是PBFT共識(shí)，通信復(fù)雜度o(n2)，所以隨著分組變少，共識(shí)時(shí)間變少，但隨著組內(nèi)節(jié)點(diǎn)變多，對(duì)整體共識(shí)時(shí)間影響變大，因此最終分組的確定需要與達(dá)成共識(shí)概率做一個(gè)平衡。

圖8 mix-raft-pbft不同分組共識(shí)時(shí)延

圖9是在不同的節(jié)點(diǎn)數(shù)量分為四組的情況下，mix-raft-pbft與PBFT吞吐量的對(duì)比，mix-raft-pbft由于組內(nèi)節(jié)點(diǎn)數(shù)量增加導(dǎo)致整體吞吐量下降，不過(guò)整體吞吐量容然有較大提升。

圖9 mix-raft-pbft與PBFT吞吐量對(duì)比

3 結(jié)語(yǔ)

在本文中，簡(jiǎn)要介紹了PBFT算法。針對(duì)PBFT的共識(shí)效率，提出了一種基于PBFT的分組混合共識(shí)機(jī)制來(lái)提升效率并且保證了安全性不變。分組混合共識(shí)機(jī)制包括三個(gè)階段，第一階段概率分組算法，提升了共識(shí)達(dá)成概率；第二階段隨機(jī)分組，防止拜占庭節(jié)點(diǎn)的串通；第三個(gè)階段mix-raft-pbft混合共識(shí)算法，組內(nèi)使用拜占庭容錯(cuò)chain-raft算法，組間使用PBFT算法，因?yàn)橐呀?jīng)完成分組，所以分組之間可以同時(shí)進(jìn)行共識(shí)，最終分組之間完成PBFT算法共識(shí)，組內(nèi)拜占庭容錯(cuò)chain-raft算法降低了通信復(fù)雜度，分組減少了最終PBFT算法共識(shí)的參與節(jié)點(diǎn)同時(shí)減小了主節(jié)點(diǎn)通信壓力，從而大大縮短了整體共識(shí)時(shí)間。