融合可驗(yàn)證隨機(jī)函數(shù)和門限簽名的拜占庭容錯(cuò)共識(shí)算法

任永旺，段紅軍 ，王振飛，王 飛

1(鄭州大學(xué) 計(jì)算機(jī)與人工智能學(xué)院，鄭州 450001) 2(鄭州藝術(shù)幼兒師范學(xué)校，鄭州 450000)

1 引 言

2008年，Nakamoto在《比特幣：一種點(diǎn)對(duì)點(diǎn)現(xiàn)金系統(tǒng)》中首次提到區(qū)塊鏈的概念[1]，區(qū)塊鏈?zhǔn)且环N利用共識(shí)機(jī)制來(lái)生成和更新數(shù)據(jù)、使用密碼學(xué)技術(shù)來(lái)保證數(shù)據(jù)的唯一性、利用智能合約來(lái)保證合約順利執(zhí)行的一種安全的分布式基礎(chǔ)架構(gòu)和計(jì)算規(guī)范[2].其中共識(shí)機(jī)制是在缺乏中央控制和協(xié)調(diào)的分布式網(wǎng)絡(luò)中為了達(dá)成共識(shí)所使用的規(guī)則，是區(qū)塊鏈的底層核心技術(shù)，其決定了區(qū)塊鏈的安全性、一致性、擴(kuò)展性和交易速度，因此逐漸成為區(qū)塊鏈的研究熱點(diǎn).

區(qū)塊鏈根據(jù)開放程度不同，分為公有鏈、私有鏈和聯(lián)盟鏈.公有鏈?zhǔn)峭耆_放的、去中心化的，任何節(jié)點(diǎn)都能參與到共識(shí)維護(hù)的分布式賬本.由于完全開放的特性，大多數(shù)公有鏈采用如工作量證明(Proof of Work，PoW)、權(quán)益證明(Proof of Stake，PoS)等“Proof of X”類型的共識(shí)機(jī)制[3，4]，還有一些使用混合“Proof of X”類型的共識(shí)機(jī)制，如授權(quán)股份證明(Delegated Proof of Stake，DPoS)[5，6].PoW是各個(gè)節(jié)點(diǎn)通過(guò)求解一個(gè)復(fù)雜但容易驗(yàn)證的數(shù)學(xué)難題，最快解決該難題的節(jié)點(diǎn)獲得記賬權(quán)，從而獲得一定數(shù)量的虛擬貨幣作為獎(jiǎng)勵(lì)的共識(shí)機(jī)制[7].目前如比特幣、以太坊、狗狗幣等都使用該機(jī)制來(lái)達(dá)成共識(shí).該機(jī)制以“算力為王”，但是共識(shí)過(guò)程中存在高耗能、高交易延遲、低吞吐量等缺點(diǎn).PoS由系統(tǒng)中最高權(quán)益的節(jié)點(diǎn)獲得記賬權(quán)，其權(quán)益通過(guò)節(jié)點(diǎn)持有特定貨幣的數(shù)量和時(shí)間來(lái)確定[8].如未來(lái)幣就是使用該共識(shí)機(jī)制，機(jī)制以“權(quán)益為王”，在一定程度上解決了PoW中的高耗能的問(wèn)題，但是由于所有節(jié)點(diǎn)都參與競(jìng)爭(zhēng)，所以對(duì)吞吐量要求高，會(huì)出現(xiàn)“富者越富、貧者越貧”的現(xiàn)象.DPoS是在PoS的基礎(chǔ)上發(fā)展而來(lái)，貨幣持有者選舉“董事會(huì)”成員，“董事會(huì)”內(nèi)部按照一定的規(guī)則進(jìn)行記賬的共識(shí)機(jī)制.機(jī)制采用“民主集中式”共識(shí)，能夠?qū)崿F(xiàn)秒級(jí)驗(yàn)證，但是卻弱化了去中心化.公有鏈由于完全去中心化的特性，導(dǎo)致其在監(jiān)管性和隱私保護(hù)性等方面存在天然不足，因此不適用于大規(guī)模商業(yè)應(yīng)用.私有鏈?zhǔn)峭耆忾]的、中心化的，用于企業(yè)內(nèi)部的數(shù)據(jù)共享，它記錄企業(yè)內(nèi)部的交易信息，記賬權(quán)限不公開，能夠有效防止機(jī)構(gòu)內(nèi)部單點(diǎn)故障、隱瞞或者篡改數(shù)據(jù).由于私有鏈的完全封閉的特性，其不適用于大型的商業(yè)活動(dòng).聯(lián)盟鏈?zhǔn)前敕忾]的，半去中心化的，節(jié)點(diǎn)通過(guò)授權(quán)加入聯(lián)盟網(wǎng)絡(luò)，參與者組成利益聯(lián)盟，并由聯(lián)盟間共同維護(hù)的分布式賬本.擁有權(quán)限可控、部分去中心化、交易速度快和可擴(kuò)展等優(yōu)勢(shì).聯(lián)盟鏈所在的半封閉式網(wǎng)絡(luò)，存在著節(jié)點(diǎn)的信任不對(duì)等問(wèn)題，為了安全性、可用性等方面考慮，聯(lián)盟鏈?zhǔn)褂每扇萑檀嬖诓糠职菡纪ス?jié)點(diǎn)的拜占庭容錯(cuò)算法來(lái)達(dá)成共識(shí).

上述的3種區(qū)塊鏈，公有鏈由于高度開放，使用戶隱私無(wú)法保證、相關(guān)部門無(wú)法進(jìn)行有效監(jiān)督，且存在吞吐量不足、能源浪費(fèi)等問(wèn)題，使其不適用于大規(guī)模的商業(yè)應(yīng)用；私有鏈由于其封閉性，僅僅適用于測(cè)試和企業(yè)內(nèi)部，無(wú)法滿足多個(gè)企業(yè)間大規(guī)模的商業(yè)應(yīng)用；聯(lián)盟鏈由于其半封閉、授權(quán)加入、交易速度快等特性，使其存在易于監(jiān)督、權(quán)限可控等優(yōu)勢(shì)，相比于公有鏈和私有鏈，更適用于大規(guī)模商業(yè)運(yùn)用.而且聯(lián)盟鏈在分布式共識(shí)過(guò)程中，考慮到網(wǎng)絡(luò)節(jié)點(diǎn)間存在著信任不對(duì)等，采用拜占庭容錯(cuò)算法來(lái)達(dá)成共識(shí)，更加符合現(xiàn)實(shí)中的網(wǎng)絡(luò)環(huán)境.

2 相關(guān)工作

拜占庭容錯(cuò)算法(Byzantine Fault Tolerance，BFT)是應(yīng)用復(fù)制技術(shù)解決分布式系統(tǒng)中拜占庭錯(cuò)誤的通用方案，時(shí)間復(fù)雜度是指數(shù)級(jí)的[9].其中，拜占庭錯(cuò)誤是敵手節(jié)點(diǎn)惡意錯(cuò)發(fā)或者補(bǔ)發(fā)消息造成的錯(cuò)誤，其中的惡意節(jié)點(diǎn)被稱為拜占庭節(jié)點(diǎn).1999年Castro與Liskov提出實(shí)用拜占庭容錯(cuò)算法(Practical Byzantine Fault Tolerant，PBFT)[10]，算法采用預(yù)準(zhǔn)備(Pre-prepare)、準(zhǔn)備(Prepare)和提交(Commit)3階段協(xié)議，來(lái)保證副本間的狀態(tài)復(fù)制.在Prepare階段和Commit階段，節(jié)點(diǎn)間采用兩兩交互的方式保證副本狀態(tài)機(jī)的一致，如果總節(jié)點(diǎn)數(shù)為3f+1，則每次交互都至少需要2f+1個(gè)副本節(jié)點(diǎn)收集2f+1個(gè)投票才能滿足系統(tǒng)一致性需求，在這兩個(gè)階段的交互過(guò)程中，PBFT的通信復(fù)雜度為O(n2).PBFT把BFT達(dá)成共識(shí)的難度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)別，因此在聯(lián)盟鏈中得到廣泛應(yīng)用.由于網(wǎng)絡(luò)傳輸?shù)牟豢煽啃院途W(wǎng)絡(luò)關(guān)系的復(fù)雜性，PBFT在數(shù)據(jù)交換過(guò)程中，很容易造成網(wǎng)絡(luò)擁堵，降低共識(shí)效率.之后一系列改進(jìn)的拜占庭容錯(cuò)方案被提出.Zyzzyva采用投機(jī)技術(shù)避免執(zhí)行三階段提交[11]，由客戶端和副本直接進(jìn)行交互，并且由客戶端決定是否達(dá)成共識(shí)，但是這種投機(jī)行為導(dǎo)致錯(cuò)誤恢復(fù)成本較高.拜占庭委托容錯(cuò)(Delegated Byzantine fault tolerance，DBFT)是一種改進(jìn)的拜占庭容錯(cuò)算法[12]，算法按照節(jié)點(diǎn)的信譽(yù)度(Trust)來(lái)選出記賬節(jié)點(diǎn)，記賬節(jié)點(diǎn)使用拜占庭容錯(cuò)算法來(lái)達(dá)成共識(shí)，由于算法采用代理記賬節(jié)點(diǎn)，使得安全性降低，易造成事實(shí)上的中心.HoneyBadgerBFT采用分割交易來(lái)緩解主節(jié)點(diǎn)的帶寬瓶頸[13]，并結(jié)合隨機(jī)交易塊和門限加密來(lái)提升交易吞吐量，但是在網(wǎng)絡(luò)節(jié)點(diǎn)較少的情況下(如8個(gè)節(jié)點(diǎn))，性能低于PBFT.文獻(xiàn)[14]引入門限簽名來(lái)降低通信復(fù)雜度，但是其主節(jié)點(diǎn)身份是暴露的，不能抵抗自適應(yīng)攻擊.此外，運(yùn)用PBFT和“Proof of X”等機(jī)制相結(jié)合的混合共識(shí)算法相繼被提出[15,16]，如Tendermint、ByzCoin等.這些混合共識(shí)算法運(yùn)用公有鏈的共識(shí)機(jī)制來(lái)選取一定數(shù)量節(jié)點(diǎn)組成委員會(huì)，并在委員會(huì)內(nèi)部運(yùn)用PBFT算法來(lái)達(dá)成共識(shí).

綜上所述，對(duì)于BFT算法的當(dāng)前研究方向主要是降低通信復(fù)雜度、改變主節(jié)點(diǎn)的選取方式和提高吞吐量.然而大部分的方案都使用固定排序的主節(jié)點(diǎn)，每一輪主節(jié)點(diǎn)的身份都在排序完成后就確定了，然后根據(jù)排序依次來(lái)提交提案，這些提前暴露主節(jié)點(diǎn)的方案很容易受到敵手的分布式拒絕服務(wù)攻擊(Distributed Denial of Service，DDoS)[17]，導(dǎo)致主節(jié)點(diǎn)無(wú)法正常提案，從而影響系統(tǒng)活性.為了抵抗DDoS攻擊，Micali提出了Algorand共識(shí)機(jī)制[18]，采用BA★算法來(lái)達(dá)成共識(shí)，BA★算法的每一輪的提案者和每一步的驗(yàn)證者都是隨機(jī)產(chǎn)生的，從而使該算法能夠抵擋DDoS攻擊.其中提案者就是下文所說(shuō)的主節(jié)點(diǎn)(Leader)，驗(yàn)證者就是下文所說(shuō)的備份節(jié)點(diǎn)(BackUp).然而此算法的停止時(shí)間不固定，且由于每一步都重新選舉驗(yàn)證者，使得系統(tǒng)負(fù)擔(dān)增加.文獻(xiàn)[19]提出一種健壯拜占庭容錯(cuò)共識(shí)算法(Robust Byzantine Fault Tolerance，RBFT)，其通過(guò)環(huán)形簽名來(lái)匿名選取提案者，并通過(guò)門限簽名來(lái)達(dá)成共識(shí)，該方案提出的匿名提案者能夠抵抗DDoS攻擊，并且門限簽名降低了達(dá)成共識(shí)過(guò)程中的網(wǎng)絡(luò)負(fù)擔(dān).

針對(duì)大部分拜占庭容錯(cuò)算法難以抵抗自適應(yīng)攻擊、擴(kuò)展性不足等問(wèn)題，本文以區(qū)塊鏈在高校學(xué)生信息存儲(chǔ)中的應(yīng)用為假設(shè)背景，提出一種融合可驗(yàn)證隨機(jī)函數(shù)和門限簽名方法的拜占庭容錯(cuò)共識(shí)算法(VRF_TS_BFT).算法首先利用VRF來(lái)對(duì)下一任候選主節(jié)點(diǎn)進(jìn)行提案，運(yùn)用VRF的隨機(jī)性和零知識(shí)證明來(lái)達(dá)到隱藏主節(jié)點(diǎn)身份的目的；然后運(yùn)用能夠代表指定數(shù)量節(jié)點(diǎn)意愿的門限簽名機(jī)制進(jìn)行投票，選舉出主節(jié)點(diǎn)和達(dá)成共識(shí)，從而減輕主節(jié)點(diǎn)選取和達(dá)成共識(shí)過(guò)程中的網(wǎng)絡(luò)壓力.分析表明，本文所提方案能夠在系統(tǒng)減少開銷的同時(shí)，提升系統(tǒng)的魯棒性、可擴(kuò)展性和抗DDoS攻擊的能力，為BFT系統(tǒng)在高校學(xué)生信息存儲(chǔ)和管理系統(tǒng)中的應(yīng)用提供高可用性的支持.

3 成果論述

3.1 系統(tǒng)模型

VRF_TS_BFT共識(shí)算法能夠像PBFT共識(shí)算法一樣，契合聯(lián)盟鏈的應(yīng)用場(chǎng)景，在聯(lián)盟鏈中維護(hù)全網(wǎng)一致的分布式賬本.如圖1所示，在高?；诼?lián)盟鏈進(jìn)行學(xué)生信息存儲(chǔ)和管理的應(yīng)用場(chǎng)景中，分布在不同地理位置的記賬節(jié)點(diǎn)(監(jiān)督部門A、高校B、高校C、高校D、教育局E和勞務(wù)部門F)通過(guò)以太網(wǎng)連接在一起，每個(gè)節(jié)點(diǎn)在加入聯(lián)盟時(shí)都已獲得聯(lián)盟鏈網(wǎng)絡(luò)的授權(quán)，所有節(jié)點(diǎn)共同組成高校聯(lián)盟，聯(lián)盟成員間通過(guò)VRF_TS_BFT算法來(lái)維護(hù)全網(wǎng)一致的分布式賬本.

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

VRF_TS_BFT算法共分為基于可驗(yàn)證隨機(jī)函數(shù)的隨機(jī)選主算法和基于門限簽名的拜占庭容錯(cuò)共識(shí)算法兩部分.本文提出的共識(shí)算法是針對(duì)高校學(xué)生信息存儲(chǔ)和管理的，參與的各節(jié)點(diǎn)都是各高校、政府監(jiān)督部門和教育相關(guān)職能部門，在以高校自身信譽(yù)為背景的前提下，由監(jiān)督方和各職能部門通過(guò)選舉指定一些高校節(jié)點(diǎn)作為潛在提案者(Potential Proposer，PP)，潛在提案者負(fù)責(zé)收集交易信息.然后VRF_TS_BFT算法通過(guò)可驗(yàn)證隨機(jī)函數(shù)在潛在提案者中隨機(jī)選擇一些節(jié)點(diǎn)作為候選主節(jié)點(diǎn)(Candidate Leader，CL)，PP通過(guò)門限簽名依據(jù)一定的規(guī)則對(duì)CL進(jìn)行投票，從CL中選取一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)(Primary).主節(jié)點(diǎn)負(fù)責(zé)把收集到的交易數(shù)據(jù)打包成區(qū)塊和發(fā)起新一輪的提案，主節(jié)點(diǎn)在提案發(fā)出之后，自動(dòng)退化為備份節(jié)點(diǎn)(BackUp).然后，備份節(jié)點(diǎn)根據(jù)門限簽名機(jī)制來(lái)對(duì)提案進(jìn)行投票，任一BackUp收集到的投票數(shù)達(dá)到了門限值，則根據(jù)投票信息合成門限簽名并廣播該門限簽名信息，共識(shí)達(dá)成.

圖2為VRF_TS_BFT的算法示意圖，算法分為Pre-prepare、Prepare和Commit 3個(gè)階段.為了更好的表示，在圖中設(shè)定Primary0為主節(jié)點(diǎn)，BackUp3為無(wú)法正常通信的節(jié)點(diǎn)，其他節(jié)點(diǎn)為能夠正常通信的BackUp節(jié)點(diǎn).客戶首先在請(qǐng)求階段(Request)把交易請(qǐng)求發(fā)送給主節(jié)點(diǎn).在Pre-prepare階段，Primary依據(jù)一定的規(guī)則，把客戶的交易信息組裝成區(qū)塊B，并把該區(qū)塊B、主節(jié)點(diǎn)投票信息和主節(jié)點(diǎn)驗(yàn)證信息組裝成PRE_PREPARE消息，然后把該消息廣播給所有的BackUp節(jié)點(diǎn)，消息發(fā)送完成后Primary自動(dòng)退化為BackUp節(jié)點(diǎn).在Prepare階段，BackUp節(jié)點(diǎn)收到主節(jié)點(diǎn)發(fā)來(lái)的信息，首先驗(yàn)證該信息是不是主節(jié)點(diǎn)所發(fā)，如果是再驗(yàn)證區(qū)塊的合法性，如果區(qū)塊合法，則用部分門限簽名合成自己的投票信息，再把投票信息和簽名信息等合成PREPARE消息，并廣播PREPARE消息，與此同時(shí)收集其他BackUp的投票信息，如果某個(gè)BackUp收集到足夠的投票信息，如圖2中的BackUp2，則根據(jù)投票信息合成門限簽名(ThresholdSig).在Commit階段，然后把門限簽名信息合成COMMIT消息，并廣播COMMIT信息.其他節(jié)點(diǎn)收到該COMMIT消息，只需驗(yàn)證門限簽名的正確性，如果通過(guò)，就不再需要收集其它節(jié)點(diǎn)的發(fā)送的對(duì)該區(qū)塊的投票信息，直接認(rèn)定區(qū)塊合法，把區(qū)塊加入到自己維護(hù)的區(qū)塊鏈中，并把共識(shí)達(dá)成的消息發(fā)送出去，共識(shí)完成.

圖2 VRF_TS_BFT算法示意圖Fig.2 Schematic diagram of VRF_TS_BFT algorithm

本文算法在Commit階段，根據(jù)門限簽名的易驗(yàn)證性，弱化PBFT中的Commit階段的信息交換頻率和數(shù)據(jù)包的大小.在Commit階段，任意一個(gè)節(jié)點(diǎn)如果收集到滿足門限值的部分門限簽名信息，可以合成門限簽名，并把確認(rèn)信息發(fā)送給其他節(jié)點(diǎn).其它節(jié)點(diǎn)只需通過(guò)門限簽名就能確認(rèn)達(dá)成共識(shí)，從而減少主節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)擔(dān)和BackUp的簽名驗(yàn)證的次數(shù).分析表明，本方案在減少系統(tǒng)和網(wǎng)絡(luò)開銷的同時(shí)，保障系統(tǒng)的活性和安全性，增加共識(shí)過(guò)程的魯棒性，為高可用拜占庭系統(tǒng)提供支持.

3.2 相關(guān)假設(shè)和定義

假設(shè)2.在聯(lián)盟鏈中，由于存在一定數(shù)量的拜占庭節(jié)點(diǎn)，且節(jié)點(diǎn)之間通過(guò)異步網(wǎng)絡(luò)進(jìn)行連接，如果系統(tǒng)中的Primary發(fā)布虛假消息或者臨時(shí)崩潰時(shí)，為了保證系統(tǒng)的活性，在一定延時(shí)MaxDelay內(nèi)如果不能達(dá)成共識(shí)，防止副本節(jié)點(diǎn)無(wú)限期地等待接收請(qǐng)求去執(zhí)行，PP啟動(dòng)視圖轉(zhuǎn)換.其中PP等待時(shí)間delay=CurrentT-StartT，每輪共識(shí)結(jié)束，PP節(jié)點(diǎn)都會(huì)啟動(dòng)一個(gè)計(jì)時(shí)器，StartT表示計(jì)時(shí)器啟動(dòng)時(shí)間，CurrentT表示當(dāng)前計(jì)時(shí)器時(shí)間，當(dāng)PP等待時(shí)間delay的值超過(guò)MaxDelay的話，則會(huì)啟動(dòng)視圖轉(zhuǎn)換協(xié)議.

定義1.備份節(jié)點(diǎn).備份節(jié)點(diǎn)(BackUp)參與共識(shí)的三階段流程，并把達(dá)成共識(shí)的區(qū)塊數(shù)據(jù)保存到本地區(qū)塊鏈中，共識(shí)節(jié)點(diǎn)根據(jù)職責(zé)不同，有4種不同的叫法：普通備份節(jié)點(diǎn)、PP、CL和Leader，其中普通備份節(jié)點(diǎn)下面統(tǒng)稱為備份節(jié)點(diǎn)或者BackUp節(jié)點(diǎn)；PP是一些指定的負(fù)責(zé)收集交易信息，可以通過(guò)選舉成為主節(jié)點(diǎn)的BackUp節(jié)點(diǎn)；CL是PP通過(guò)VRF發(fā)現(xiàn)自己是主節(jié)點(diǎn)候選人的時(shí)候的稱呼，是PP到Primary的一個(gè)過(guò)渡階段；Primary是一種特殊的BackUp節(jié)點(diǎn)，是由PP轉(zhuǎn)換而來(lái)，Primary負(fù)責(zé)打包區(qū)塊并對(duì)打包區(qū)塊進(jìn)行提案，發(fā)布完消息后，Primary退化為BackUp節(jié)點(diǎn).BackUp負(fù)責(zé)對(duì)提案進(jìn)行投票，以確定是否達(dá)成共識(shí)，并可以轉(zhuǎn)發(fā)滿足門限簽名條件的確認(rèn)信息.

定義2.簽名.簽名分為部分門限簽名，門限簽名和節(jié)點(diǎn)簽名3種.其中部分門限簽名(PartSig)，是各BackUp節(jié)點(diǎn)根據(jù)保存的部分門限簽名的私鑰對(duì)消息進(jìn)行簽名，該簽名表示對(duì)消息進(jìn)行投票，如PartSigi就是表示BackUpi運(yùn)用部分門限簽名對(duì)X進(jìn)行簽名，表示對(duì)X進(jìn)行投票；門限簽名(ThresholdSig)，當(dāng)某個(gè)節(jié)點(diǎn)收集到對(duì)X的部分門限簽名的數(shù)量超過(guò)門限值時(shí)，就能合成門限簽名信息，表示投票的共識(shí)達(dá)成，如ThresholdSig表示對(duì)消息X的共識(shí)達(dá)成.節(jié)點(diǎn)簽名(Sig)，使用節(jié)點(diǎn)自身保存的私鑰對(duì)信息進(jìn)行簽名，是為了表明消息是某個(gè)BackUp所發(fā)，如Sigi就表明消息X是由BackUpi所發(fā)，且通過(guò)公鑰解析出消息X，能夠驗(yàn)證X在傳輸過(guò)程中的正確性.

定義3.消息.副本之間通過(guò)預(yù)準(zhǔn)備消息(PRE_PREPARE)，準(zhǔn)備消息(PREPARE)和確認(rèn)消息(COMMIT)來(lái)達(dá)成共識(shí).

預(yù)準(zhǔn)備消息(PRE_PREPARE)指Primary用于發(fā)布提案的消息，具體格式為PartSigi，Sigi，block>.其中v為當(dāng)前視圖標(biāo)號(hào)，h為主節(jié)點(diǎn)為打包區(qū)塊block分配的序列號(hào)，i為當(dāng)前節(jié)點(diǎn)的標(biāo)號(hào)，hash(block)為block的摘要信息，block是主節(jié)點(diǎn)根據(jù)交易信息打包而成的區(qū)塊，PartSigi表示主節(jié)點(diǎn)對(duì)消息X進(jìn)行投票，Sigi表示消息X是節(jié)點(diǎn)i所發(fā).該消息一方面把打包區(qū)塊分發(fā)下去，另一方面，也代表主節(jié)點(diǎn)對(duì)該區(qū)塊的投票.

準(zhǔn)備消息(PREPARE)除主節(jié)點(diǎn)外的所有備份節(jié)點(diǎn)對(duì)該P(yáng)RE_PREPARE消息進(jìn)行投票，其具體格式為PartSigi>，其余參數(shù)與預(yù)準(zhǔn)備消息中同名參數(shù)含義相同.

確認(rèn)消息(COMMIT)是對(duì)提案信息的投票結(jié)果進(jìn)行確認(rèn)，其具體格式為ThresholdSig>，其中ThresholdSig表示對(duì)block的共識(shí)達(dá)成.對(duì)于包含3f+1個(gè)節(jié)點(diǎn)的拜占庭系統(tǒng)，至少需要收集2f+1條對(duì)block的投票信息才能進(jìn)行最終確認(rèn).當(dāng)收集到其他副本發(fā)送的2f個(gè)投票信息后，加上自身的投票信息，達(dá)到門限值t，就可以得到門限簽名，從而組合成確認(rèn)消息，對(duì)投票信息進(jìn)行確認(rèn).

3.3 可驗(yàn)證隨機(jī)函數(shù)

可驗(yàn)證隨機(jī)函數(shù)是Silvio Micali等人于1999提出的一類具有可驗(yàn)證功能的偽隨機(jī)函數(shù)[20].對(duì)于一個(gè)輸入Seed和私鑰(Secret Key，SK)，VRF會(huì)產(chǎn)生一組隨機(jī)數(shù)r和r的證明proof，驗(yàn)證者可以通過(guò)公鑰(Public Key，PK)、r、Seed和proof驗(yàn)證出r是否由PK的持有人根據(jù)Seed所產(chǎn)生的.VRF的流程如下：

1)使用者通過(guò)非對(duì)稱加密算法生成一組公私鑰對(duì)(PK，SK)，其中PK為公鑰，SK為私鑰.

2)輸入Seed和SK，VRF會(huì)生成一個(gè)r和一個(gè)可以實(shí)現(xiàn)對(duì)r進(jìn)行零知識(shí)證明的proof，如公式(1)所示:

Seed+SK→r+proof

(1)

3)通過(guò)r和proof可以驗(yàn)證它們是否是一起產(chǎn)生的，如果是則為true.

VRFverify(r，proof)==true

(2)

否則為false.

4)通過(guò)輸入Seed、PK和proof，可以驗(yàn)證該proof是不是PK的持有人根據(jù)Seed所產(chǎn)生的，如果是則為true.

PubVerify(proof，Seed，PK)==true

(3)

否則為false.

VRF具有可驗(yàn)證性、確定性和隨機(jī)性：

1)可驗(yàn)證性：在只知道proof、Seed、PK和r的情況下，證明r是否為PK的持有者根據(jù)Seed所生成.

2)確定性：如果輸入的Seed和SK相同，則得到的r一定是相同的.

3)隨機(jī)性：在未給定proof的情況下，r和一個(gè)隨機(jī)數(shù)對(duì)于敵手來(lái)說(shuō)是不可區(qū)分的.

3.4 門限簽名

(t，n)門限簽名(Threshold Signature，TS)是指由n名成員組成一個(gè)簽名群體[21]，該群體有一對(duì)群體簽名公鑰和私鑰，群體的簽名私鑰被n個(gè)成員以門限的方式共享，只有群體內(nèi)大于等于門限值t個(gè)誠(chéng)實(shí)的成員才能代表群體用群體簽名私鑰進(jìn)行簽名，且任何人都很容易通過(guò)群體公鑰來(lái)驗(yàn)證簽名.門限簽名的這些特性，使其可以用于BFT共識(shí)過(guò)程中，以減少共識(shí)過(guò)程中的網(wǎng)絡(luò)負(fù)擔(dān).本文所用門限簽名的流程如下所示：

1)公鑰和群成員私鑰的生成：輸入安全參數(shù)s，門限值t和成員數(shù)N，返回每個(gè)成員部分簽名所用的私鑰PartSigSKi(i=1，2，…，N)，私鑰每個(gè)成員保存一個(gè)，用于生成部分門限簽名，PK用于驗(yàn)證門限簽名，如公式(4)所示:

s+t+N→PK+L

(4)

其中(L={PartSig1，PartSig2，… ，PartSigN}).

2)生成部分門限簽名：輸入消息msg以及成員私鑰PartSigSKi，產(chǎn)生部分簽名PartSigi，如公式(5)所示:

msg+PartSigSKi→PartSigi

(5)

3)合成門限簽名：如果某個(gè)成員收集到的有效部分簽名PartSigi達(dá)到門限值t，則可以用這些PartSigi合成門限簽名ThresholdSig.

4)驗(yàn)證門限簽名：輸入消息msg、公鑰PK和門限簽名ThresholdSig，返回判斷結(jié)果true和false，其中true表示驗(yàn)證通過(guò)，false表示未通過(guò)驗(yàn)證，如公式(6)所示:

verify(msd，PK，ThresholdSig)→trueorfalse

(6)

4 改進(jìn)的拜占庭容錯(cuò)共識(shí)算法

4.1 基于可驗(yàn)證隨機(jī)函數(shù)的主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換

主節(jié)點(diǎn)選舉是從PP節(jié)點(diǎn)中根據(jù)主節(jié)點(diǎn)選舉規(guī)則選舉出發(fā)起下一輪提案的主節(jié)點(diǎn).基于可驗(yàn)證隨機(jī)函數(shù)的Leader的選舉過(guò)程如下，一個(gè)PP節(jié)點(diǎn)，在接收到當(dāng)前主節(jié)點(diǎn)發(fā)送的PRE_PREPARE息后，根據(jù)里面的信息算出seednext來(lái)確定自己是不是下一輪次的主節(jié)點(diǎn)的候選人.確定一個(gè)PP節(jié)點(diǎn)是不是候選主節(jié)點(diǎn)的具體過(guò)程如下：

視圖轉(zhuǎn)換協(xié)議的目的是為了防止BackUp節(jié)點(diǎn)無(wú)限制的等待接收?qǐng)?zhí)行消息，保證共識(shí)機(jī)制的活性，主動(dòng)更換Leader.在如下所示的3種條件下會(huì)觸發(fā)視圖轉(zhuǎn)換：

1)系統(tǒng)中Primary節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)發(fā)布虛假信息；

2)系統(tǒng)中Primary節(jié)點(diǎn)的崩潰而無(wú)法進(jìn)行正常提案；

3)當(dāng)BackUp等待接收?qǐng)?zhí)行消息超過(guò)一定時(shí)限.

在本文算法中，由于每一輪提案結(jié)束后，主節(jié)點(diǎn)退化為BackUp節(jié)點(diǎn)，而且每輪只選舉出唯一一個(gè)主節(jié)點(diǎn)，所以當(dāng)一輪共識(shí)達(dá)成，開啟下一輪共識(shí)的時(shí)候，會(huì)進(jìn)行主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換，也就是說(shuō)主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換是融合在一起同時(shí)完成的.而且為了減少主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換過(guò)程中的網(wǎng)絡(luò)壓力，主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換過(guò)程都只需潛在提案者PP進(jìn)行參與，然后轉(zhuǎn)換成功后把新一輪視圖轉(zhuǎn)換和Leader選舉成功的消息廣播給所有BackUp節(jié)點(diǎn).

如果當(dāng)前協(xié)議達(dá)成或者等待超時(shí)，且提案者PP通過(guò)計(jì)算確定自己有可能成為下一輪的Leader，則立刻啟動(dòng)視圖轉(zhuǎn)換，視圖轉(zhuǎn)換協(xié)議的具體過(guò)程如算法流程1所示.

算法1.基于可驗(yàn)證隨機(jī)函數(shù)的主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換

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

輸出：新的主節(jié)點(diǎn)和全局一致的新的視圖信息

1. IFBackUpis notPPTHEN

2. RETURN

3. WHILE true THEN

4. IFVerify(COMMIT)is OK ||PPiis TIMEOUT THEN

5. IFverify(isProtentialLeader)THEN

6. BroadCastVIEW_CHANGE

7. IF(TIMEOUT)THEN

8.minMSGis the minimalVIEW_CHANGE

9. IFminMSG== null THEN

10.num++

11. continue

12. ELSE THEN

13. GenerateVOTE_MSG

14. BroadCaseVOTE_MSG

15.voteMSGs(incomingSig.iterator()

16.counts←{}

17. WHILE true THEN

18.vmsg←voteMSGs.next()

19. IF((vmsg.ThresholdSigis existence)&&verfiy(vmsg.ThresholdSig))THEN

20. IF is Primary THEN

21. BroadCastNEW_VIEWk

22. RETURN

23. ELSE IFverify(vmsg.PartSig)THEN

24. ++counts[CLk]

25. IF(counts[CLk]>=t)THEN

26. GenerateThresholdSig

27. IF is not Primary THEN

28. SendThresholdSigtoPrimary

29. ELSE THEN

30. BroadCastNEW_VIEWk

31. RETURN

32. ELSE THEN

33. BroadCastNEW_BLOCKk

主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換的流程：

1)如果等待時(shí)間耗盡或者上一個(gè)區(qū)塊已經(jīng)達(dá)成共識(shí)，且PPi是CL，則啟動(dòng)視圖轉(zhuǎn)換協(xié)議.首先讓視圖編號(hào)加1，然后發(fā)送視圖轉(zhuǎn)換消息VIEW_CHANGEi.VIEW_CHANGEi是指PPi發(fā)送的視圖轉(zhuǎn)換消息，其具體內(nèi)容是Sigt>，其中vnew=(v+1)%N，N是BackUp節(jié)點(diǎn)的總數(shù)；h是指當(dāng)前區(qū)塊鏈的高度；i是當(dāng)前節(jié)點(diǎn)的編號(hào)；r和proof是VRF根據(jù)seednext計(jì)算出來(lái)的自己是否是潛在Leader的證明，Sigi是節(jié)點(diǎn)對(duì)X進(jìn)行簽名，為了驗(yàn)證消息是BackUpi所發(fā).

2)在一定時(shí)間內(nèi)，所有PP節(jié)點(diǎn)收集其他PP節(jié)點(diǎn)發(fā)送過(guò)來(lái)的視圖轉(zhuǎn)換消息.時(shí)間到后，根據(jù)查找主節(jié)點(diǎn)的方法，找到自己認(rèn)為的主節(jié)點(diǎn)信息，然后對(duì)其進(jìn)行投票.minMSG如果為null，表示本輪沒有產(chǎn)生CL，num++之后，根據(jù)VRF產(chǎn)生的隨機(jī)值，繼續(xù)查找CL；如果minMSG不為空，則對(duì)下一任Leader進(jìn)行投票，發(fā)出投票信息VOTE_MSG.VOTE_MSG的具體內(nèi)容為partSigk，ThresholdSig>Sigk，其中partSigk表示是k投的票，里面的i指的是投票PPi作為一下任Leader節(jié)點(diǎn)，r和proof也是i所產(chǎn)生的隨機(jī)數(shù)和隨機(jī)數(shù)的證明.

3)PP接收投票信息，對(duì)投票信息進(jìn)行如下3種判斷：

① 如果下一任Leader收到的投票信息中含有合法的對(duì)新視圖投票的ThresholdSig，則認(rèn)為當(dāng)前視圖轉(zhuǎn)換完成，并其廣播視圖轉(zhuǎn)換完成的消息NEW_VIEWk給所有的BackUp節(jié)點(diǎn)，表示視圖轉(zhuǎn)換完成.PP收到視圖轉(zhuǎn)換完成的消息后不再接收其他視圖轉(zhuǎn)換的消息.

② 如果投票信息中，只包含對(duì)潛在新Leader的投票，則對(duì)投票數(shù)量進(jìn)行統(tǒng)計(jì)，當(dāng)某個(gè)PP接收到的投票數(shù)量達(dá)到門限值，并成功合成門限簽名后ThresholdSig，則認(rèn)為已經(jīng)選出了下一輪的Leader.如果ThresholdSig就是下一任Leader自身合成的，則直接廣播NEW_VIEWk消息，表示視圖轉(zhuǎn)換完成；如果不是下一任Leader合成的，這把門限簽名信息，發(fā)送給下一任Leader.

③ 如果PP收到的消息既不包含合法的ThresholdSig，也不包含對(duì)新視圖的投票信息，則選擇廣播新的提案消息NEW_BLOCKk給所有BackUp節(jié)點(diǎn)，新提案的具體內(nèi)容為Sigk，partSigk，blocknew>其中blocknew為新提案的區(qū)塊的具體內(nèi)容.

如果BackUp節(jié)點(diǎn)收到NEW_VIEW消息，則認(rèn)為主節(jié)點(diǎn)和視圖轉(zhuǎn)換已經(jīng)完成；如果BackUp節(jié)點(diǎn)收到NEW_BLOCK消息，則對(duì)其中包含的新提案blocknew進(jìn)行投票，其具體過(guò)程與基于門限簽名的拜占庭容錯(cuò)共識(shí)算法的流程保持一致.

4.2 基于門限簽名的拜占庭容錯(cuò)共識(shí)算法

在PBFT的Prepare階段和Commit階段，都需要所有BackUp節(jié)點(diǎn)間進(jìn)行信息交換，但是由于各個(gè)BackUp所在的地理位置的分散性以及網(wǎng)絡(luò)傳輸?shù)牟豢煽啃?，大量的?shù)據(jù)交換容易造成網(wǎng)絡(luò)擁堵，從而導(dǎo)致節(jié)點(diǎn)間難以達(dá)成共識(shí).本文通過(guò)引入門限簽名機(jī)制，在Commit階段，當(dāng)任一節(jié)點(diǎn)收集到的合法簽名人數(shù)到達(dá)門限值t的時(shí)候，就可以合成門限簽名并廣播該門限簽名，其他尚未合成門限簽名的人，只需驗(yàn)證一條合法的門限簽名，就停止接收該區(qū)塊的投票信息，并確認(rèn)區(qū)塊得到驗(yàn)證.這樣就降低了Commit階段達(dá)成共識(shí)所需要的條件，減少了Commit階段的驗(yàn)證次數(shù)，使得Commit階段在不穩(wěn)定網(wǎng)絡(luò)環(huán)境中達(dá)成共識(shí)的成功率更高.具體過(guò)程如算法流程2所示.

算法2.基于門限簽名的拜占庭容錯(cuò)共識(shí)算法.

輸入：交易信息

輸出：全局一致賬本

1.StartT←Time()

2. IF(Leader)THEN

3. Prepareblock

4. IFTime()-StartT

5. GeneratePRE_PREPARE

6. BroadCastPRE_PREPARE

7. ELSE THEN

8. RETURN TIMEOUT

9. ELSE THEN

10. ReceivedPRE_PREPARE

11. IF(Verify(PRE_PREPARE)&&Time()-StartT

12. GeneratePREPARE

13. BroadCastPREPARE

14. ELSE THEN

15. RETURN TIMEOUT

16.partSigMsgs←incomingPartSig.iterator

17.thresholdSigMsgs←incomingThresholdSig.iterator

18.counts←{}

19. WHILE true THEN

20. IF(time()-StartT>=MaxDelay)THEN

21. RETURN TIMEOUT

22.ThresholdSig←thresholdSigMsgs.next()

23. IF(verfy(ThresholdSig)==true)THEN

24. Committedblockon the local blockchain

25. BroadCastCOMMIT

26. RETURN

27.PartSig←partSigMsgs.next()

28. IF(verify(PartSig)==false)THEN

29. CONTINUE

30. ELSE THEN

31. ++counts[block]

32. IF(count[block] >=t&&Time()-StartT

33.GenerateCOMMIT

34.BroadCastCOMMIT

35. Committedblockon the local blockchain

36. RETURN

把每一輪的開始時(shí)間記錄到開始時(shí)間StartT，VRF_TS_BFT的算法流程如下：

1)如果節(jié)點(diǎn)是Leader的話，則把交易信息打包到區(qū)塊block，然后把block、投票信息、簽名信息等打包成PRE_PREPARE消息，如果未超時(shí)間限制，則把PRE_PREPARE廣播給其他BackUp節(jié)點(diǎn).

2)如果不是Leader，則等待接收Leader發(fā)送來(lái)的PRE_PREPARE消息，收到該消息后，對(duì)消息進(jìn)行驗(yàn)證，如果驗(yàn)證通過(guò)，則廣播含有自身投票信息的PREPARE消息，對(duì)區(qū)塊進(jìn)行投票.

3)所有BackUp節(jié)點(diǎn)都收集別的BackUp節(jié)點(diǎn)發(fā)送的PREPARE消息和含有門限簽名ThresholdSig的COMMIT消息.如果收到門限簽名，并通過(guò)verfy(thresholdSig)驗(yàn)證，則提交該區(qū)塊進(jìn)入本地維護(hù)的賬本，本區(qū)塊的驗(yàn)證結(jié)束，并把COMMIT消息廣播出去，后續(xù)不再接收該區(qū)塊的投票信息和門限簽名消息.

4)在未收到某個(gè)區(qū)塊的ThresholdSig之前，收集到的PREPARE中的部分門限簽名消息超過(guò)門限值t的話，則合成門限簽名ThresholdSig，并廣播含有門限簽名的COMMIT消息，同時(shí)把區(qū)塊信息添加到本地區(qū)塊鏈，本區(qū)塊的驗(yàn)證結(jié)束，此后不再接收該區(qū)塊的投票信息和門限簽名信息.

5 實(shí)驗(yàn)分析驗(yàn)證

5.1 系統(tǒng)安全性證明

系統(tǒng)安全性是指所有的誠(chéng)實(shí)副本都按照一致次序處理請(qǐng)求，每次達(dá)成共識(shí)需要系統(tǒng)中大多數(shù)誠(chéng)實(shí)節(jié)點(diǎn)做出一致承諾.

5.2 不可臨時(shí)分叉性證明

在同一區(qū)塊高度h，兩個(gè)不同的Leader節(jié)點(diǎn)發(fā)出的不同的區(qū)塊信息，如果這兩個(gè)區(qū)塊都達(dá)成共識(shí)，則會(huì)在高度h上出現(xiàn)一個(gè)臨時(shí)性的分叉.假設(shè)系統(tǒng)中在高度h上有兩個(gè)不同的塊block1和block2同時(shí)達(dá)成共識(shí)，則block1為達(dá)到門限值所獲得的由部分門限簽名構(gòu)成的投票數(shù)t1≥2f+1，block2對(duì)應(yīng)的投票數(shù)t2≥2f+1，兩式相加可得t1+t2≥4f+2.由于副本數(shù)共有3f+1個(gè)，假定副本中拜占庭節(jié)點(diǎn)數(shù)為最大值f，則誠(chéng)實(shí)節(jié)點(diǎn)數(shù)為2f+1，因?yàn)檎\(chéng)實(shí)節(jié)點(diǎn)對(duì)區(qū)塊鏈上同一個(gè)高度的區(qū)塊只能投票一次，所以誠(chéng)實(shí)節(jié)點(diǎn)只能對(duì)block1或者block2其中之一進(jìn)行投票，也就是在高度h誠(chéng)實(shí)節(jié)點(diǎn)的票數(shù)最多為2f+1票，因?yàn)镹-f=2f+1.如果所有的拜占庭節(jié)點(diǎn)間已經(jīng)組成了聯(lián)盟，由于拜占庭節(jié)點(diǎn)可以作弊，所以假設(shè)所有拜占庭節(jié)點(diǎn)都分別對(duì)block1和block2進(jìn)行了投票，這時(shí)候?qū)lock1和block2的投票中，拜占庭節(jié)點(diǎn)投票數(shù)最多是2f票.因?yàn)榘菡纪ス?jié)點(diǎn)投票數(shù)最多為2f票，誠(chéng)實(shí)節(jié)點(diǎn)投票數(shù)最多是2f+1票，所以t1和t2總票數(shù)最大值為4f+1，即max(t1+t2)=2f+(2f+1)=4f+1.把t1+t2=4f+1帶入t1+t2≥4f+2可得4f+1≥4f+2，解該不等式得1>2，出現(xiàn)矛盾.所以系統(tǒng)在高度h上不可能有兩個(gè)不同的塊block1和block2同時(shí)達(dá)成共識(shí).

5.3 活性證明

系統(tǒng)活性是指請(qǐng)求最終能夠被誠(chéng)實(shí)節(jié)點(diǎn)正確執(zhí)行，本文VRF_TS_BFT共識(shí)算法能夠在提案過(guò)程中始終保持系統(tǒng)活性.

5.3.1 基于可驗(yàn)證隨機(jī)函數(shù)的選主算法系統(tǒng)活性

采用固定順序輪流選主的方式是當(dāng)前主流的選主方式，在備份節(jié)點(diǎn)成為主節(jié)點(diǎn)的順序固定的情況下，主節(jié)點(diǎn)很容易遭受敵手的DDoS攻擊，破壞系統(tǒng)活性.本文基于VRF的隨機(jī)選主算法，所有潛在提案者，在選主之前，都不知道其他節(jié)點(diǎn)是否為候選主節(jié)點(diǎn)，主節(jié)點(diǎn)也不能提前知道哪個(gè)備份節(jié)點(diǎn)將成為候選主節(jié)點(diǎn)，成為候選主節(jié)點(diǎn)的過(guò)程完全隨機(jī).在投票階段，根據(jù)可驗(yàn)證隨機(jī)函數(shù)的可驗(yàn)證性，所有節(jié)點(diǎn)都可以很容易的驗(yàn)證某個(gè)節(jié)點(diǎn)是否為候選主節(jié)點(diǎn)，然后根據(jù)主節(jié)點(diǎn)選舉算法，選舉出下一輪的主節(jié)點(diǎn).基于可驗(yàn)證隨機(jī)函數(shù)的選主過(guò)程，由于其隨機(jī)性和零知識(shí)證明的特性，可以有效的防止DDoS攻擊，保證系統(tǒng)的活性.

5.3.2 基于視圖轉(zhuǎn)換的活性

VRF_TS_BFT算法候選主節(jié)點(diǎn)CL會(huì)根據(jù)超時(shí)機(jī)制或在協(xié)議成功達(dá)成共識(shí)時(shí)觸發(fā)視圖轉(zhuǎn)換來(lái)保證系統(tǒng)活性.當(dāng)觸發(fā)視圖轉(zhuǎn)換協(xié)議時(shí)，CL節(jié)點(diǎn)會(huì)自動(dòng)廣播視圖轉(zhuǎn)換消息VIEW_CHANGE；然后所有PP節(jié)點(diǎn)都發(fā)送VOTE_MSG對(duì)CL進(jìn)行投票，并依據(jù)門限簽名選出下一任主節(jié)點(diǎn).任一PP節(jié)點(diǎn)根據(jù)部分門限簽名PartSig成功合成ThresholdSig，都會(huì)將門限簽名信息發(fā)送給下一任主節(jié)點(diǎn).下一任主節(jié)點(diǎn)在收到或合成ThresholdSig后，都會(huì)就會(huì)向所有BackUp節(jié)點(diǎn)廣播NEW_VIEW消息宣告視圖轉(zhuǎn)換成功.

視圖轉(zhuǎn)換的消息在CL節(jié)點(diǎn)等待超時(shí)或上一輪共識(shí)已經(jīng)達(dá)成共識(shí)時(shí)提出，新視圖生成的消息可有任一成功合成門限消息的PP節(jié)點(diǎn)生成并發(fā)送給當(dāng)選主節(jié)點(diǎn)的PP節(jié)點(diǎn)，由主節(jié)點(diǎn)宣布視圖轉(zhuǎn)換完成.由于CL產(chǎn)生的隨機(jī)性，可以防止敵手在視圖轉(zhuǎn)換中發(fā)起的DDoS攻擊.

綜上所述，VRF_TS_BFT能夠在選主過(guò)程和視圖輪換過(guò)程中保證系統(tǒng)的活性.

5.4 可用性分析

系統(tǒng)的可用性是指系統(tǒng)在面對(duì)網(wǎng)絡(luò)異常時(shí)可以正確提供服務(wù)的能力.由于聯(lián)盟鏈中節(jié)點(diǎn)眾多、各節(jié)點(diǎn)間位置分散和網(wǎng)絡(luò)連接狀態(tài)不確定等問(wèn)題，本文所提出的VRF_TS_BFT能夠保證只要任一節(jié)點(diǎn)能夠根據(jù)部分門限簽名PartSig合成門限簽名ThresholdSig，并把該ThresholdSig傳遞出去，則系統(tǒng)狀態(tài)就能達(dá)成一致.其在最小信息交換的情況下，達(dá)成共識(shí)的流程如圖2中的帶箭頭的實(shí)線所示，圖中Request階段主節(jié)點(diǎn)Primary接收客戶端發(fā)送的交易信息.

1)Pre-prepare階段Primary把交易信息打包成PRE_PREPARE消息并把該信息廣播給其他備份節(jié)點(diǎn)；

2)Prepare階段，所有BackUp節(jié)點(diǎn)對(duì)收到的PRE_PREPARE中的區(qū)塊信息進(jìn)行投票，假設(shè)由于網(wǎng)絡(luò)波動(dòng)，只有BackUp2集齊了超過(guò)門限值t的部分門限簽名，其就能根據(jù)PartSig合成門限簽名ThresholdSig；

3)Commit階段，BackUp2把確認(rèn)信息廣播給所有BackUp節(jié)點(diǎn)，其他BackUp節(jié)點(diǎn)收到BackUp2發(fā)送的確認(rèn)消息，只要門限簽名驗(yàn)證通過(guò)，就能認(rèn)定該提案區(qū)塊達(dá)成了一致性共識(shí)，然后把共識(shí)達(dá)成的消息廣播出去.當(dāng)至少有f+1個(gè)節(jié)點(diǎn)成功達(dá)成一致性共識(shí)，則認(rèn)定協(xié)議完成.

5.5 概率學(xué)角度分析成功達(dá)成共識(shí)的概率

從概率角度對(duì)系統(tǒng)可用性進(jìn)行分析，假設(shè)每個(gè)BackUp網(wǎng)絡(luò)完全獨(dú)立且在有限時(shí)間范圍內(nèi)收到法定人數(shù)投票的概率為p，則n個(gè)BackUp節(jié)點(diǎn)組成的共識(shí)算法網(wǎng)絡(luò)中，k個(gè)BackUp節(jié)點(diǎn)收到法定投票人數(shù)的概率服從二項(xiàng)分布，其概率如公式(7)所示:

(7)

在PBFT中，因?yàn)镻repare階段和Commit階段這兩個(gè)階段，每個(gè)節(jié)點(diǎn)都至少要收到2f+1個(gè)確認(rèn)信息才能保證提案得到通過(guò)，這兩個(gè)階段中，每個(gè)階段提案成功的概率如公式(8)所示:

(8)

在VRF_TS_BFT中，需要Prepare階段有任一誠(chéng)實(shí)節(jié)點(diǎn)收集夠2f+1個(gè)確認(rèn)信息就能夠保證提案通過(guò)，因此為了保證存在一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)能夠傳達(dá)共識(shí)結(jié)果，至少需要f+1個(gè)共識(shí)單元.VRF_TS_BFT算法提案成功的概率公式(9)所示:

(9)

圖3中(a)，(b)，(c)，(d)，(e)，(f)分別表示n取7，16，22，28，46，61時(shí)無(wú)拜占庭節(jié)點(diǎn)的情況下PBFT和VRF_TS_BFT成功提案的概率分布對(duì)比圖，PBFT在不同節(jié)點(diǎn)下的成功提案的概率分布圖為圖3(g)，VRF_TS_BFT在不同節(jié)點(diǎn)下的成功提案的概率分布圖為圖3(h)，其中橫軸為每個(gè)副本節(jié)點(diǎn)在有效時(shí)間內(nèi)收到法定人數(shù)投票的概率，縱軸為成功提案的概率.從圖3中可以看出，隨著法定人數(shù)投票成功的概率P的增加提案成功概率呈現(xiàn)上升趨勢(shì)，且VRF_TS_BFT比PBFT上升的快；同等投票成功的概率P的情況下，VRF_TS_BFT算法大于等于PBFT算法提案成功的概率，且VRF_TS_BFT比PBFT提案成功的概率更快的趨近于1.對(duì)比PBFT和VRF_TS_BFT在不同節(jié)點(diǎn)數(shù)下的成功提案概率分布圖，可以看出，PBFT在P≥0.8時(shí)候，提案成功的概率才趨近于1，而VRF_TS_BFT在P≥0.6的時(shí)候，成功提案的概率就已經(jīng)趨近于1；PBFT在P<0.6時(shí)，提案成功的概率可以忽略不計(jì)，而VRF_TS_BFT在P≥0.4時(shí)，提案成功的概率大于60%.通過(guò)對(duì)比可知，在相同投票成功的概率的情況下，VRF_TS_BFT

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

提案成功的概率更高；在相同提案成功率的情況下，VRF_TS_BFT對(duì)投票成功的概率要求更低.可見在相同的環(huán)境下，VRF_TS_BFT對(duì)投票成功的概率要求沒有PBFT的高，且在同等投票成功率的情況下，VRF_TS_BFT更容易達(dá)成共識(shí)，所以相較于PBFT，VRF_TS_BFT的魯棒性更強(qiáng).

5.6 隨機(jī)選主算法成功找到候選主節(jié)點(diǎn)的概率

P{X=NPP}=(1-p)NPP

(10)

圖4表示在不同個(gè)PP節(jié)點(diǎn)的情況下，1次到4次內(nèi)能夠成功找到候選主節(jié)點(diǎn)的概率，從圖中可以看出：當(dāng)只有4個(gè)PP節(jié)點(diǎn)的時(shí)候，一次能找到候選主節(jié)點(diǎn)的概率最低，約為94%，兩次能找到候選主節(jié)點(diǎn)的概率就約等于100%了；當(dāng)有10個(gè)主節(jié)點(diǎn)的情況下，一次找到候選主節(jié)點(diǎn)的概率約為99%，兩次的概率接近100%；而且隨著PP節(jié)點(diǎn)數(shù)的增加，一次能找到CL的概率就會(huì)越來(lái)越高，當(dāng)節(jié)點(diǎn)數(shù)超過(guò)16的時(shí)候，一次成功的概率就接近100%.由此可以看出，在做Leader選舉和視圖轉(zhuǎn)換的時(shí)候，本文提出的方法，在一個(gè)時(shí)間段內(nèi)，能夠確保主節(jié)點(diǎn)選舉和視圖轉(zhuǎn)換成功.

圖4 存在候選主節(jié)點(diǎn)的概率Fig.4 Probability of candidate master nodes

5.7 比較PBFT和VRF_TS_BFT的吞吐量和成功率

為了測(cè)試PBFT和VRF_TS_BFT在不同網(wǎng)絡(luò)環(huán)境中的吞吐量，以此來(lái)比較這兩種算法的優(yōu)劣.使用GoLang語(yǔ)言，分別模擬PBFT和VRF_TS_BFT實(shí)現(xiàn)過(guò)程.實(shí)驗(yàn)采用4核的Intel Core i5處理器(8個(gè)邏輯內(nèi)核)，8G內(nèi)存的硬件平臺(tái)，采用GoLang語(yǔ)言中的多進(jìn)程和多線程模擬1個(gè)客戶端和7個(gè)BackUp節(jié)點(diǎn)的拓?fù)渚W(wǎng)絡(luò)，VRF_TS_BFT所用的門限簽名是根據(jù)shamir秘密共享方案改進(jìn)而來(lái)[22]，PBFT和VRF_TS_BFT的拓?fù)浣Y(jié)構(gòu)如圖5所示，其中每次試驗(yàn)客戶端發(fā)送100組交易數(shù)據(jù)給指定的主節(jié)點(diǎn)Primary0.在節(jié)點(diǎn)間達(dá)成共識(shí)的過(guò)程中，為了模擬網(wǎng)絡(luò)延時(shí)，在Pre_prepare階段和Prepare階段每個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的時(shí)候，都會(huì)隨機(jī)延時(shí)1-5ms的時(shí)間，同時(shí)為了模擬網(wǎng)絡(luò)丟包現(xiàn)象，使用隨機(jī)數(shù)，按設(shè)定的百分比使得數(shù)據(jù)傳輸失?。蝗绻?00ms內(nèi)共識(shí)沒有達(dá)成，共識(shí)失敗，啟動(dòng)視圖輪換，開始重新發(fā)送數(shù)據(jù).

圖5 網(wǎng)絡(luò)拓?fù)鋱DFig.5 Network topology

實(shí)驗(yàn)結(jié)果和實(shí)驗(yàn)數(shù)據(jù)如圖6和表1所示，圖6是對(duì)表1的數(shù)據(jù)的圖形化展示.在圖6中，每個(gè)子圖都對(duì)應(yīng)表1中PBFT和VRF_TS_BFT相同宕機(jī)節(jié)點(diǎn)數(shù)的數(shù)據(jù)，如圖6(b)對(duì)應(yīng)了表一中宕機(jī)節(jié)點(diǎn)數(shù)為1的PBFT和VRF_TS_BFT的數(shù)據(jù)；X軸表示數(shù)據(jù)發(fā)送成功率(%)；Y軸表示時(shí)間(s)；Z軸表示成功數(shù).在圖6的圖標(biāo)中：PTSR表示PBFT數(shù)據(jù)傳輸成功率，如PTSR 100%表示數(shù)據(jù)傳輸成功率為100%；VTSR表示VRF_TS_BFT數(shù)據(jù)傳輸成功率，如VTSR 80%表示數(shù)據(jù)傳輸成功率為80%.圖6(a)中7個(gè)BackUp節(jié)點(diǎn)都可以正常工作，對(duì)應(yīng)于表1中的宕機(jī)節(jié)點(diǎn)數(shù)為0的數(shù)據(jù)；圖6(b)中7個(gè)BackUp節(jié)點(diǎn)有一個(gè)節(jié)點(diǎn)宕機(jī)，對(duì)應(yīng)于表1中的宕機(jī)節(jié)點(diǎn)數(shù)為1的數(shù)據(jù)；圖6(c)中7個(gè)BackUp節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)宕機(jī)，對(duì)應(yīng)于表1中的宕機(jī)節(jié)點(diǎn)數(shù)為2的數(shù)據(jù)；圖6(d)為3種數(shù)據(jù)混合顯示.從圖6(a)可以看出，在所有BackUp都正常工作的情況下，VRF_TS_BFT在VTSR 70%的情況下，達(dá)成共識(shí)的概率是100%，而PBFT對(duì)數(shù)據(jù)傳輸成功率就特別敏感，在PTSR 70%的情況時(shí)，達(dá)成共識(shí)的概率只有55%左右.從圖6(b)可以看出，在一個(gè)BackUp節(jié)點(diǎn)宕機(jī)的情況下，VRF_TS_BFT在VTSR 70%的情況下，達(dá)成共識(shí)的概率接近100%，而PBFT在PTSR 90%的情況下，達(dá)成共識(shí)的概率約為85%.圖6(c)中當(dāng)節(jié)點(diǎn)宕機(jī)數(shù)達(dá)到最大值，此時(shí)，雙方雖然對(duì)數(shù)據(jù)傳輸成功率表現(xiàn)都很敏感，但是VRF_TS_BFT在各方面表現(xiàn)都比PBFT好，VRF_TS_BFT在VTSR 80%的情況下，達(dá)成共識(shí)的概率也為95%，而PBFT在PTSR 90%的情況下，達(dá)成共識(shí)的概率只有10%左右.通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以看出，在相同數(shù)據(jù)傳輸成功率的前提下，VRF_TS_BFT表現(xiàn)出更強(qiáng)的魯棒性.而且在達(dá)成共識(shí)的時(shí)候，能夠更快的轉(zhuǎn)入下一區(qū)塊的生成，不需要等待時(shí)間超時(shí)，更換視圖重新提出提案，所以，在處理同等數(shù)量的提案，VRF_TS_BFT所用時(shí)間往往會(huì)比PBFT更少.也就是說(shuō)，通過(guò)實(shí)驗(yàn)數(shù)據(jù)表明，在相同條件下，相比PBFT，本文VRF_TS_BFT速度更快、魯棒性更強(qiáng).

圖6 不穩(wěn)定環(huán)境下節(jié)點(diǎn)達(dá)成共識(shí)數(shù)據(jù)對(duì)比Fig.6 Comparison of consensus data between nodes in unstable environment

表1 不穩(wěn)定環(huán)境下節(jié)點(diǎn)達(dá)成共識(shí)數(shù)據(jù)對(duì)比Table 1 Comparison of consensus data between nodes in unstable environment

6 結(jié) 論

本文針對(duì)拜占庭容錯(cuò)算法難以抵抗DDoS攻擊、共識(shí)速度慢、魯棒性差等問(wèn)題，利用可驗(yàn)證隨機(jī)函數(shù)的隨機(jī)性和零知識(shí)證明特性，以及門限簽名只有達(dá)到門限值才能達(dá)成共識(shí)的特性，設(shè)計(jì)一種可用于聯(lián)盟鏈的改進(jìn)拜占庭容錯(cuò)共識(shí)算法VRF_TS_BFT.算法能夠隨機(jī)選取候選主節(jié)點(diǎn)，使主節(jié)點(diǎn)選舉過(guò)程避免遭遇敵手DDoS攻擊；同時(shí)，利用門限簽名可以增強(qiáng)對(duì)不穩(wěn)定網(wǎng)絡(luò)的適應(yīng)能力，提高在極端網(wǎng)絡(luò)環(huán)境下達(dá)成共識(shí)的概率.分析表明，本方案能夠在提升達(dá)成共識(shí)速度的同時(shí)，提升達(dá)成共識(shí)的幾率，具有更強(qiáng)的魯棒性.