基于樹形拓?fù)渚W(wǎng)絡(luò)的實用拜占庭容錯共識算法
2020-01-17 03:07:30包振山王凱旋張文博
應(yīng)用科學(xué)學(xué)報 2020年1期
包振山，王凱旋，張文博
1.北京工業(yè)大學(xué)信息學(xué)部，北京100124
2.可信計算北京市重點實驗室，北京100124
區(qū)塊鏈技術(shù)的核心價值是能夠在不可靠的網(wǎng)絡(luò)環(huán)境中建立節(jié)點間的信任關(guān)系，從而形成去中心化的可信分布式系統(tǒng)[1].共識算法是區(qū)塊鏈建立信任的核心技術(shù)[2]，能使彼此不信任的參與者以分散的方式對區(qū)塊鏈系統(tǒng)中事務(wù)的有效性進行驗證并達(dá)成一致.共識算法的效率直接影響區(qū)塊鏈系統(tǒng)的整體性能，因此研究高效的共識算法對區(qū)塊鏈技術(shù)的發(fā)展具有積極推動作用.
針對不同的系統(tǒng)模型（同步和異步系統(tǒng)、許可和非許可系統(tǒng)）以及不同的故障模型（崩潰故障和任意故障），已經(jīng)派生出許多不同的共識算法.能夠容忍任意故障的共識算法也稱為拜占庭容錯（Byzantine fault tolerance, BFT）共識算法，該算法源于Lamport 等人提出的拜占庭將軍問題[3].區(qū)塊鏈系統(tǒng)屬于典型的異步系統(tǒng)且系統(tǒng)中節(jié)點的行為是任意的，因此應(yīng)用于區(qū)塊鏈系統(tǒng)的共識算法應(yīng)在異步模型存在拜占庭節(jié)點的情況下達(dá)成共識.比特幣采用的工作量證明（proof of work, PoW）共識算法[4]的新穎貢獻(xiàn)在于其首次實現(xiàn)了非許可系統(tǒng)模型下的拜占庭共識.盡管PoW 能夠有效抵御女巫攻擊[5]，并在惡意節(jié)點算力不超過50%的情況下為比特幣系統(tǒng)提供安全性保障；可事實證明在非許可模型下達(dá)成共識是有代價的，因為比特幣系統(tǒng)每秒最多處理7 筆交易，并且每筆已確認(rèn)交易的成本約為1～6 美元[6].除PoW 之外，基于證明的共識算法還包括權(quán)益證明（proof of stake, PoS）[7]、委托權(quán)益證明（delegated proof of stake, DPoS）[8]等.PoS 通過幣齡動態(tài)調(diào)整挖礦難度以降低算力消耗，但依然面臨著嚴(yán)重的性能問題.DPoS 減少了參與共識節(jié)點的數(shù)量以提高性能，但在一定程度上違背了區(qū)塊鏈去中心化的設(shè)計初衷.
以太坊[9]創(chuàng)始人Vitalik Buterin 提出了區(qū)塊鏈的“三難困境”，即區(qū)塊鏈系統(tǒng)必須在分散性、安全性和可擴展性之間尋求權(quán)衡.比特幣等公有鏈系統(tǒng)屬于非許可模型，其系統(tǒng)架構(gòu)完全去中心化，并且不可靠的網(wǎng)絡(luò)環(huán)境對系統(tǒng)的安全性提出了極高的要求.因此，效率問題將始終是公有鏈廣泛應(yīng)用的根本障礙.在許可模型中達(dá)成共識是典型的分布式系統(tǒng)問題，Paxos[10]、Raft[11]以及實用拜占庭容錯（practical Byzantine fault tolerance,PBFT）[12]都是經(jīng)典的分布式一致性算法.Paxos 和Raft 無法容忍拜占庭類型的故障，其應(yīng)用場景一般為可信的分布式數(shù)據(jù)庫系統(tǒng).PBFT 是一種經(jīng)典的基于狀態(tài)機復(fù)制的一致性算法，能夠在拜占庭節(jié)點數(shù)量不超過1/3 的情況下達(dá)成共識，具有高吞吐量和低響應(yīng)時間的特點，因而廣泛應(yīng)用于許可鏈系統(tǒng).隨著許可鏈應(yīng)用場景規(guī)模的逐漸擴大，PBFT 算法的可擴展性問題日益凸顯.在具有n個共識節(jié)點的許可鏈系統(tǒng)中，PBFT 的通信復(fù)雜度為O(n2).隨著節(jié)點數(shù)量的增加，網(wǎng)絡(luò)中交換和處理的消息數(shù)量急劇增加.巨大的網(wǎng)絡(luò)開銷與計算開銷將導(dǎo)致事務(wù)確認(rèn)延遲顯著增加，吞吐量明顯降低.因此，傳統(tǒng)PBFT 算法只適用于小規(guī)模的局域網(wǎng)，而在大規(guī)模的廣域網(wǎng)環(huán)境下，其可擴展性瓶頸對許可鏈系統(tǒng)的性能帶來了嚴(yán)重的影響.
自從出現(xiàn)PBFT 算法后，大量的工作分別從不同角度對PBFT 進行改進以提高其性能.MinBFT[13]、CheapBFT[14]與FastBFT[15]等方案使用安全硬件構(gòu)建可信的執(zhí)行環(huán)境以減少節(jié)點或通信階段數(shù)量.例如，MinBFT 使用可信的計數(shù)器服務(wù)改進了PBFT，防止錯誤節(jié)點將相同的編號分配給不同的消息，從而將三階段協(xié)議減少為兩階段協(xié)議并將參與共識節(jié)點的數(shù)量由3f+1 減少到了2f+1，其中f為系統(tǒng)所能容忍錯誤節(jié)點的最大數(shù)量.CheapBFT、FastBFT、SBFT[16]與ReBFT[17]均屬于樂觀的BFT 算法.樂觀是指在沒有錯誤節(jié)點的情況下僅由少量活躍節(jié)點執(zhí)行共識過程以提高效率，而在錯誤節(jié)點數(shù)量超過一定閾值的情況下通過觸發(fā)轉(zhuǎn)換協(xié)議回退到“標(biāo)準(zhǔn)”BFT 算法.實際上，在大規(guī)模許可鏈場景下，系統(tǒng)發(fā)生錯誤的概率大幅增加，頻繁的回退操作將使系統(tǒng)性能顯著下降并處于極度不穩(wěn)定的狀態(tài).基于委員會的PBFT 算法[18-19]選擇網(wǎng)絡(luò)節(jié)點的一個子集作為委員會，從而達(dá)到提高共識效率的目的，其中委員會代表系統(tǒng)中所有參與者執(zhí)行小規(guī)模的PBFT 算法.然而，這種通過減少參與共識節(jié)點數(shù)量的PBFT 算法在很大程度上增強了許可鏈系統(tǒng)的中心化程度.基于聚合簽名與Gossip 協(xié)議的BFT算法[20]的核心思想比較簡單.每個節(jié)點不斷組合來自鄰居節(jié)點的部分聚合簽名，然后傳播這個聚合簽名，從而降低消息傳遞的復(fù)雜性.基于短生命周期簽名方案的PBFT 算法[21]使用低/中安全級別（56 位或80 位）的簽名代替高安全級別（128 位）的簽名，并定期更新短長度的密鑰對以保證安全性.該方案通過改善簽名的大小降低了系統(tǒng)的通信與計算開銷，是一種較為實用的改進方案.在聯(lián)盟鏈場景下，聯(lián)盟由若干個在廣域網(wǎng)中連接的成員組織構(gòu)成，而這些組織可能在其局域網(wǎng)中維護著多個節(jié)點.采用分層設(shè)計的PBFT算法[22-23]將通信盡可能本地化以減少廣域通信，從而降低系統(tǒng)的通信開銷.然而，只有當(dāng)每個組織都在其局域網(wǎng)內(nèi)部署較多節(jié)點時，該方案才會表現(xiàn)出優(yōu)良的性能.
大多數(shù)方案并不能真正為PBFT 算法的可擴展性提供顯著的幫助，因為通信復(fù)雜度沒有從根本上得到改善.為了重塑PBFT 算法的可擴展性從而提高現(xiàn)有許可鏈解決方案[24-26]在大規(guī)模應(yīng)用場景下的適用性，本文提出了一種基于樹形拓?fù)渚W(wǎng)絡(luò)的實用拜占庭容錯（practical Byzantine fault tolerance based on tree topology network,TTNPBFT）共識算法.TTNPBFT將全網(wǎng)范圍共識拆分為若干子網(wǎng)范圍共識，大幅降低了通信復(fù)雜度，為許可鏈在大規(guī)模廣域網(wǎng)的應(yīng)用與部署提供可能性.
1 預(yù)備知識
1.1 PBFT 算法
PBFT 是一種經(jīng)典的狀態(tài)機復(fù)制算法，也是當(dāng)前主流的基于投票的區(qū)塊鏈共識算法，能夠在系統(tǒng)中拜占庭節(jié)點數(shù)量不超過f的情況下通過多輪消息交換達(dá)成共識.每一輪共識過程在確定的視圖中執(zhí)行，每個視圖包括一個主節(jié)點和若干個從節(jié)點.PBFT 由一致性協(xié)議、視圖更換協(xié)議和檢查點協(xié)議組成，其執(zhí)行過程如圖1所示.
圖1 PBFT 算法的執(zhí)行過程Figure 1 Execution process of PBFT algorithm
在正常情況下，PBFT 執(zhí)行一致性協(xié)議.所有正確節(jié)點通過一個三階段通信過程達(dá)成共識，這3 個階段分別為預(yù)準(zhǔn)備階段、準(zhǔn)備階段、確認(rèn)階段.在預(yù)準(zhǔn)備階段，主節(jié)點對來自客戶端的事務(wù)請求進行排序并打包成區(qū)塊，通過預(yù)準(zhǔn)備消息將事務(wù)區(qū)塊廣播給從節(jié)點.接收到預(yù)準(zhǔn)備消息后，每個從節(jié)點都會檢驗其有效性，并向其他節(jié)點廣播一條包含區(qū)塊信息的準(zhǔn)備消息以確認(rèn)從主節(jié)點是否收到了相同的事務(wù)區(qū)塊，隨后進入準(zhǔn)備階段.收集到2f+1 個匹配的準(zhǔn)備消息后，所有節(jié)點廣播一條確認(rèn)消息以確保視圖在準(zhǔn)備階段未發(fā)生變化，隨后進入確認(rèn)階段.收集到2f+1 個匹配的確認(rèn)消息后，節(jié)點可以確定已經(jīng)達(dá)成共識，執(zhí)行區(qū)塊中的事務(wù)并將相應(yīng)的結(jié)果返回給客戶端.在整個過程中，節(jié)點接收到的所有有效的消息都應(yīng)該添加到其本地消息日志中.若主節(jié)點發(fā)生故障，則從節(jié)點將觸發(fā)視圖更換協(xié)議，選擇新的主節(jié)點并進入下一個視圖，從而保證系統(tǒng)的活性.檢查點協(xié)議會定期執(zhí)行，用以保證所有節(jié)點狀態(tài)的一致，并幫助節(jié)點及時清除過期的消息以節(jié)省存儲空間.
在具有n個共識節(jié)點的許可鏈系統(tǒng)中，PBFT 算法的通信復(fù)雜度為O(n2).在事務(wù)請求階段，客戶端發(fā)送n條消息；在預(yù)準(zhǔn)備階段，主節(jié)點發(fā)送n ?1 條消息；在準(zhǔn)備階段，所有從節(jié)點共發(fā)送(n ?1)2條消息；在確認(rèn)階段，主節(jié)點及從節(jié)點共發(fā)送n(n ?1)條消息；在回復(fù)階段，客戶端共收到n條消息.因此，PBFT 算法達(dá)成一輪共識，總共需要發(fā)送的消息數(shù)量為n+(n ?1)+(n ?1)2+n(n ?1)+n=2n2.當(dāng)節(jié)點數(shù)量n=200 時，網(wǎng)絡(luò)中發(fā)送消息的數(shù)量達(dá)到80 000，這將給通信網(wǎng)絡(luò)帶來極大的負(fù)擔(dān).
1.2 樹形拓?fù)渚W(wǎng)絡(luò)
樹形拓?fù)渚W(wǎng)絡(luò)中的節(jié)點呈樹狀排列，整體看來就像一棵倒置的樹，因而得名.樹形網(wǎng)絡(luò)是對星形網(wǎng)絡(luò)的一種改進，因由多個層次的星型結(jié)構(gòu)縱向連接而成，因而也叫多星級型網(wǎng)絡(luò).傳統(tǒng)的有線電視網(wǎng)與光纖接入網(wǎng)均采用了樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)易于擴展，容易在網(wǎng)絡(luò)中加入新的分支或新的節(jié)點.各分支節(jié)點對父節(jié)點的依賴性較大，如果高層次節(jié)點發(fā)生故障，那么對整個網(wǎng)絡(luò)的影響也較大.從這一點來看，樹形拓?fù)浣Y(jié)構(gòu)的可靠性類似于星形拓?fù)浣Y(jié)構(gòu).樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一種層級結(jié)構(gòu)，適用于分等級的層次型網(wǎng)絡(luò)系統(tǒng).這種層次關(guān)系與PBFT算法中節(jié)點之間的主從關(guān)系非常相似.
2 許可鏈系統(tǒng)模型
2.1 網(wǎng)絡(luò)假設(shè)
本文假設(shè)許可鏈系統(tǒng)中每對節(jié)點之間都通過可靠的點對點雙向信道連接.雖然FLP（Fischer, Lynch, Paterson）不可能定理[27]已經(jīng)證明：在允許節(jié)點出錯的情況下，完全異步的分布式系統(tǒng)無法保證共識能夠在有限時間內(nèi)達(dá)成.實際上，在較弱的網(wǎng)絡(luò)假設(shè)下，分布式系統(tǒng)依然能夠在異步模型中保持活性[28]，如部分同步[29]、間歇性同步[30].與PBFT 相同，本文假設(shè)網(wǎng)絡(luò)是部分同步的，即消息自發(fā)送起到被目的節(jié)點接收的延遲存在上界.假設(shè)整個網(wǎng)絡(luò)都是可訪問的，也就是系統(tǒng)中的節(jié)點可以方便地將消息傳輸?shù)饺魏喂?jié)點.每個節(jié)點都在其本地維護一個節(jié)點列表，記錄其他節(jié)點的編號、IP 地址/端口、公鑰、信譽值與狀態(tài)等信息.此外，還假設(shè)網(wǎng)絡(luò)結(jié)構(gòu)是動態(tài)的，即全網(wǎng)可以感知節(jié)點的加入與離開，這一假設(shè)可以通過在許可鏈系統(tǒng)中配置可信的證書頒發(fā)機構(gòu)（certificate authority, CA）來實現(xiàn)[31].
2.2 對抗模型
本文假設(shè)許可鏈系統(tǒng)中共有n=3f+1 個節(jié)點，f為P2P 網(wǎng)絡(luò)中任意時刻錯誤節(jié)點的最大數(shù)量.錯誤節(jié)點的行為可以是任意的，如相互勾結(jié)或保持沉默等.錯誤節(jié)點的存在可能使網(wǎng)絡(luò)中傳輸?shù)南G失、延遲、重復(fù)或者亂序，但本文假設(shè)對手不能無限期地延遲正確的節(jié)點.此外，還假設(shè)攻擊者是算力有限的，不能破解許可鏈系統(tǒng)所使用的密碼算法，從而不能偽造正確節(jié)點的簽名以進行身份假冒攻擊，不能由數(shù)字摘要進行逆運算獲得原始信息，也不能找到具有相同摘要的兩條消息.
2.3 基于信譽模型的樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)
基于“化整為零”的思想，TTNPBFT 將全網(wǎng)范圍的共識任務(wù)拆分為若干子網(wǎng)范圍的共識任務(wù)，大幅減小了PBFT 算法的通信復(fù)雜度.TTNPBFT 借助于樹形拓?fù)渚W(wǎng)絡(luò)實現(xiàn)這一目標(biāo).每個父節(jié)點（非葉子節(jié)點）與其孩子節(jié)點形成一個子網(wǎng)，父節(jié)點擔(dān)任主節(jié)點，孩子節(jié)點作為從節(jié)點.
構(gòu)建可靠的樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)是一項至關(guān)重要的任務(wù).可靠性差是樹形拓?fù)渚W(wǎng)絡(luò)的一個顯著缺點，并且錯誤節(jié)點所處的層次越高對網(wǎng)絡(luò)造成的影響將越大，因此應(yīng)盡可能地使高可靠的節(jié)點處于較高的網(wǎng)絡(luò)層次上.TTNPBFT 通過信譽模型有效評估共識節(jié)點行為的準(zhǔn)確性，并以此來衡量一個節(jié)點是否足夠可信與可靠.基于節(jié)點的信譽值能夠構(gòu)建可靠的樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)，一旦發(fā)現(xiàn)錯誤節(jié)點，網(wǎng)絡(luò)結(jié)構(gòu)便動態(tài)地進行調(diào)整.隨著時間的推移，錯誤節(jié)點的信譽值逐漸減小，其影響力將越來越低.基于信譽模型的樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)如圖2所示.
圖2 基于信譽模型的樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)Figure 2 Tree topology communication network based on reputation model
樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)的初次構(gòu)建是隨著許可鏈系統(tǒng)的部署進行的.由于所有節(jié)點的初始信譽值完全相同，一般可采用隨機方式建立樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但為了使系統(tǒng)更可靠，應(yīng)當(dāng)以參與者的實際情況作為參考.例如，社會影響力較大的組織或機構(gòu)往往具備更可靠的信用背書.因此，以參與者的信用背書為主要依據(jù)進行通信網(wǎng)絡(luò)的初次構(gòu)建更為合理.隨著時間的推移，系統(tǒng)的信譽模型將會完全取代參與者本身的信用背書.
3 TTNPBFT 共識算法設(shè)計
TTNPBFT 共識算法以PBFT 算法為基礎(chǔ)，并結(jié)合信譽模型與樹形拓?fù)渚W(wǎng)絡(luò)的特征對一致性協(xié)議與視圖更換協(xié)議進行了改進.本章對TTNPBFT 進行詳細(xì)介紹.
3.1 信譽模型
信譽模型能夠為錯誤節(jié)點檢測提供良好的基礎(chǔ).一方面，通過動態(tài)調(diào)整節(jié)點的信譽值降低錯誤節(jié)點在樹形拓?fù)渚W(wǎng)絡(luò)中的層次，能夠不斷減小錯誤節(jié)點在共識過程中的影響力，從而使許可鏈系統(tǒng)保持較高的可用性與可靠性.另一方面，可將共識節(jié)點的信譽值作為獎勵與懲罰的標(biāo)準(zhǔn)以促使節(jié)點遵循協(xié)議.
定義1信譽值是衡量節(jié)點可信程度的參考指標(biāo).信譽值R是介于0.1 和1.0 之間的實數(shù).信譽值越高，則對應(yīng)節(jié)點的可信度越高.新加入許可鏈系統(tǒng)的節(jié)點，其信譽值初始化為0.5.
定義2信譽獎懲指信譽值將根據(jù)節(jié)點在共識過程中的行為動態(tài)變化.令Rv表示某個節(jié)點在視圖v中的信譽值，則該節(jié)點在視圖v+1 中的信譽值Rv+1與Rv的關(guān)系如下：
1）如果主節(jié)點成功生成一個有效的區(qū)塊，或者從節(jié)點的消息內(nèi)容與最終結(jié)果相同，那么這些節(jié)點的信譽逐漸提高，其計算公式為
因為采用了對數(shù)公式，所以隨著誠實節(jié)點信譽的不斷提升，其信譽值的增長率會降低.采用這種方式可增加獲得高信譽值的難度，惡意節(jié)點若想具備極高的信譽值，在樹形網(wǎng)絡(luò)中處于較高的層次，則需要付出極大的努力.參數(shù)a用于避免信譽值較低時增長幅度過大的問題.
2）如果主節(jié)點本輪未能領(lǐng)導(dǎo)產(chǎn)生新的區(qū)塊，或者從節(jié)點消息內(nèi)容與最終結(jié)果不一致，甚至沒有發(fā)送任何消息，則相應(yīng)節(jié)點的信譽值會線性下降，其計算公式為
信譽值的下降速度取決于參數(shù)b，b取值的大小應(yīng)該根據(jù)具體應(yīng)用場景的需求來設(shè)置.
3）如果同一節(jié)點向其他共識節(jié)點發(fā)送不一致的消息，那么該節(jié)點將被視為拜占庭節(jié)點，其信譽直接降為最小值，即
定義3信譽狀態(tài)是限制節(jié)點權(quán)限的重要依據(jù).信譽狀態(tài)取決于節(jié)點信譽值R的大小.表1定義了節(jié)點的4 種信譽狀態(tài).
表1 節(jié)點的信譽狀態(tài)Table 1 Reputation status of node
其中，參數(shù)α與β為節(jié)點狀態(tài)變更的兩個閾值，0.5< α <1.0 且0.1< β <0.5.信譽值大于α為最優(yōu)狀態(tài)，而小于β則為最差狀態(tài).α與β的取值與許可鏈系統(tǒng)對安全性的要求程度有關(guān).圖3展示了節(jié)點不同信譽狀態(tài)之間的轉(zhuǎn)換關(guān)系.
圖3 節(jié)點信譽狀態(tài)之間的轉(zhuǎn)換關(guān)系Figure 3 Transition relationship between node reputation states
不同信譽狀態(tài)的節(jié)點擁有不同的權(quán)限.為了保證系統(tǒng)的效率與安全，規(guī)定只有優(yōu)秀節(jié)點可擔(dān)任根節(jié)點，異常節(jié)點不能擔(dān)任主節(jié)點，無效節(jié)點則不能參與共識.節(jié)點權(quán)限與其信譽狀態(tài)的對應(yīng)關(guān)系見表2.
表2 節(jié)點權(quán)限與信譽狀態(tài)的對應(yīng)關(guān)系Table 2 Relationship between node permissions and reputation status
定義4信譽恢復(fù)指節(jié)點的信譽值低于β時將逐漸恢復(fù).從原則上講，應(yīng)當(dāng)給予無效節(jié)點“改過”的機會，于是給出如下規(guī)定：每經(jīng)過T時間周期，無效節(jié)點的信譽值將上升c，但不能超過β，其具體計算公式為
式中，t為該節(jié)點最后一次參與共識距現(xiàn)在的總時間.
定義5信譽更新指節(jié)點維護其本地節(jié)點列表的過程.信譽更新發(fā)生在每一次視圖更換之前，用以保證具有最高信譽的節(jié)點當(dāng)選為主節(jié)點.在一般情況下，各個節(jié)點只需通過其本地的消息日志，根據(jù)信譽獎懲標(biāo)準(zhǔn)對其所在子網(wǎng)內(nèi)其他節(jié)點的信譽值與信譽狀態(tài)進行更新，此過程由節(jié)點獨自完成而不需要通信.但一定時間之后，可能會出現(xiàn)節(jié)點狀態(tài)不一致的情況.因此，類似于PBFT 算法的檢查點協(xié)議，子網(wǎng)范圍的信譽更新將周期性執(zhí)行，所有節(jié)點通過消息廣播的方式將子網(wǎng)內(nèi)的信譽值達(dá)成一致.信譽更新過程在各個子網(wǎng)內(nèi)獨立執(zhí)行，因此不會對系統(tǒng)整體性能產(chǎn)生明顯影響.
為了保證許可鏈系統(tǒng)的安全性，應(yīng)及時清除系統(tǒng)中的惡意節(jié)點.根據(jù)式(4)可得信譽值從最小值0.1 恢復(fù)到β所需要的時間t′為
本文將“長期”定義為在10t′時間周期內(nèi)達(dá)到3t′的時間，并將長期處于無效狀態(tài)的節(jié)點認(rèn)定為惡意節(jié)點.在信譽更新過程中，節(jié)點列表中的惡意節(jié)點將被刪除.
3.2 一致性協(xié)議
TTNPBFT 共識算法使用密碼技術(shù)來防止欺騙攻擊與重播攻擊，同時保證消息的完整性.消息包含了數(shù)字簽名和無碰撞哈希函數(shù)生成的數(shù)字摘要.為了便于描述，首先在表3中定義相關(guān)符號.
TTNPBFT 通過樹形拓?fù)渚W(wǎng)絡(luò)將全網(wǎng)劃分成若干子網(wǎng)，這些子網(wǎng)分布在不同的層次.在每個子網(wǎng)中，父節(jié)點作為主節(jié)點，領(lǐng)導(dǎo)其孩子節(jié)點在該子網(wǎng)范圍內(nèi)執(zhí)行相應(yīng)的PBFT 算法.根據(jù)樹形拓?fù)渚W(wǎng)絡(luò)的層級屬性，TTNPBFT 對PBFT 一致性協(xié)議的預(yù)準(zhǔn)備階段和回復(fù)階段進行了改進.在預(yù)準(zhǔn)備階段，全網(wǎng)主節(jié)點Sroot向其領(lǐng)導(dǎo)的子網(wǎng)內(nèi)廣播預(yù)準(zhǔn)備消息，該子網(wǎng)內(nèi)的從節(jié)點作為下一層子網(wǎng)的主節(jié)點將繼續(xù)轉(zhuǎn)發(fā)該預(yù)準(zhǔn)備消息，直至最底層子網(wǎng).與此類似，在回復(fù)階段，最底層子網(wǎng)節(jié)點的回復(fù)消息將逐層向上傳播，客戶端最終只會收到來自最高層子網(wǎng)節(jié)點的回復(fù)消息.在TTNPBFT 中，只有最底層子網(wǎng)運行完整的PBFT 算法，而高層子網(wǎng)則運行簡化的PBFT 算法（準(zhǔn)備階段與確認(rèn)階段合并）.當(dāng)n= 40, k= 4 時，樹形拓?fù)渚W(wǎng)絡(luò)中的所有子網(wǎng)處于3 個層次上.圖4給出了TTNPBFT 算法的一輪完整的共識過程.
表3 相關(guān)符號Table 3 Related symbols
圖4 TTNPBFT 的共識過程Figure 4 Consensus process of TTNPBFT
具體算法如Algorithm 1 所示：
該過程的詳細(xì)描述如下：
步驟1客戶端c向全網(wǎng)主節(jié)點Sroot發(fā)送消息
步驟2Sroot將來自于客戶端的事務(wù)請求打包成區(qū)塊b，然后在其子網(wǎng)范圍內(nèi)廣播一條預(yù)準(zhǔn)備消息<
步驟3最底層子網(wǎng)中的從節(jié)點接收到預(yù)準(zhǔn)備消息后對其合法性進行驗證，驗證內(nèi)容主要包括：預(yù)準(zhǔn)備消息簽名的正確性、視圖v的正確性、摘要d與區(qū)塊b的哈希值是否一致以及b中事務(wù)是否重放等.若預(yù)準(zhǔn)備消息有效，則將其存入本地消息日志并向子網(wǎng)內(nèi)其他節(jié)點廣播準(zhǔn)備消息，從而就區(qū)塊序列號sn 達(dá)成一致.準(zhǔn)備消息格式為
步驟4最底層子網(wǎng)中的節(jié)點（包括主節(jié)點）收集到2fk+ 1 條匹配的準(zhǔn)備消息后，它們將廣播一條確認(rèn)消息
步驟5子網(wǎng)的主節(jié)點統(tǒng)計回復(fù)信息，若存在fk+1 個匹配的預(yù)執(zhí)行結(jié)果集rs，便將rs作為該子網(wǎng)的共識結(jié)果.在將該結(jié)果集繼續(xù)向上層子網(wǎng)傳遞之前，需在其所屬的子網(wǎng)內(nèi)確認(rèn)得到了相同的事務(wù)區(qū)塊且當(dāng)前視圖未發(fā)生變化，操作同步驟4.若發(fā)現(xiàn)其主節(jié)點作惡或視圖已改變，則向下廣播一條共識失敗消息
需要注意的是：最底層子網(wǎng)完成確認(rèn)階段后，節(jié)點并不應(yīng)該直接將事務(wù)的執(zhí)行結(jié)果寫入本地賬本，因為共識還沒有完全達(dá)成.在結(jié)果向上傳送的過程中，共識依然可能會失?。欢碌念A(yù)準(zhǔn)備消息的到來意味著上一輪共識已經(jīng)結(jié)束，節(jié)點應(yīng)當(dāng)此時提交上一輪的事務(wù)到本地.
3.3 視圖更換協(xié)議
視圖更換協(xié)議用于為子網(wǎng)選擇新的主節(jié)點，以保證系統(tǒng)在發(fā)生故障時能夠保持活性.PBFT 算法基于計時器超時機制在全網(wǎng)范圍觸發(fā)視圖更換事件.TTNPBFT 共識算法通過引入信譽模型，能夠有效檢測到主節(jié)點的異常行為.如發(fā)送不一致的消息，這將同樣觸發(fā)視圖更換協(xié)議.此外，TTNPBFT 將全網(wǎng)范圍共識拆分成若干子網(wǎng)范圍共識，這些子網(wǎng)作為獨立單元并行執(zhí)行PBFT算法.它們處于相互獨立的視圖中，因此TTNPBFT 的視圖更換是局部的而非全網(wǎng)的.
若某個主節(jié)點發(fā)生故障，則將在其領(lǐng)導(dǎo)的子網(wǎng)內(nèi)觸發(fā)視圖更換協(xié)議.TTNPBFT 采取擇優(yōu)替換原則，即在該子網(wǎng)范圍內(nèi)選擇信譽值最高的節(jié)點擔(dān)任新的主節(jié)點.圖5展示了極端情況下TTNPBFT 的全網(wǎng)主節(jié)點Sroot發(fā)生拜占庭錯誤時的視圖更換過程.視圖更換協(xié)議不僅要求所有節(jié)點就新視圖達(dá)成一致，還需要考慮如何在新視圖中處理上一視圖的遺留事務(wù)，這是一個較為復(fù)雜的過程.在此采用簡化后的描述，更詳細(xì)的介紹請參考文獻(xiàn)[12].
圖5 TTNPBFT 的視圖更換過程Figure 5 View-change process of TTNPBFT
具體算法如Algorithm 2 所示：
該過程的詳細(xì)描述如下：
步驟1若某個主節(jié)點出錯或成為其他子網(wǎng)的主節(jié)點，則其所領(lǐng)導(dǎo)子網(wǎng)的所有從節(jié)點將進行信譽更新，并判斷該主節(jié)點的信譽值在子網(wǎng)范圍內(nèi)是否為最大值.若滿足條件，協(xié)議結(jié)束；否則，從節(jié)點將向其所屬的子網(wǎng)內(nèi)廣播一條視圖更換消息
步驟2子網(wǎng)內(nèi)信譽值最高的從節(jié)點收集到2fk個匹配的視圖更換消息后，它將向該子網(wǎng)內(nèi)廣播新視圖消息
步驟3該子網(wǎng)內(nèi)其他節(jié)點接收到新視圖消息后，驗證簽名的正確性以及視圖更換消息的有效性，然后將新視圖消息添加到消息日志中并進入視圖v+1.下一層子網(wǎng)內(nèi)從節(jié)點接收到新視圖消息后驗證消息的有效性，若消息有效，則檢查子網(wǎng)范圍內(nèi)是否存在某個從節(jié)點的信譽值大于被派遣主節(jié)點的信譽值.若不存在，則將新視圖消息存入日志并進入視圖v′+1.否則，將在此子網(wǎng)范圍內(nèi)再次觸發(fā)視圖更換協(xié)議.
步驟4重復(fù)步驟1～3，直至故障節(jié)點到達(dá)指定的位置，即成為較低層次子網(wǎng)的主節(jié)點或成為最底層子網(wǎng)的從節(jié)點.
信譽模型規(guī)定：故障節(jié)點的信譽值會逐漸減小，而拜占庭節(jié)點的信譽值被直接置為最小值.因此，視圖更換協(xié)議結(jié)束后故障節(jié)點在樹形拓?fù)渚W(wǎng)絡(luò)中所處的層次會降低，而拜占庭節(jié)點將直接成為最底層子網(wǎng)的從節(jié)點，作惡代價非常大.
3.4 激勵與懲罰機制
如果一個惡意節(jié)點總是付出高成本而獲得低回報，那么該節(jié)點將失去攻擊系統(tǒng)的動機，比特幣就完美地詮釋了這個道理.在基于PBFT 算法的許可鏈系統(tǒng)中，共識節(jié)點尤其是主節(jié)點通常是攻擊者的主要目標(biāo)，相對于普通的記賬節(jié)點，共識節(jié)點時刻面臨著嚴(yán)峻的安全威脅.此外，共識節(jié)點的帶寬資源、計算資源與存儲資源的開銷也是非常顯著的.因此，許可鏈系統(tǒng)同樣需要建立適當(dāng)?shù)募钆c懲罰機制以提高正確節(jié)點參與共識的積極性.
本文考慮了一種基于信譽的激勵與懲罰機制.聯(lián)盟成員共同設(shè)立獎勵基金，使長期具有高信譽的成員將獲得更多的實質(zhì)性獎勵.在懲罰方面，信譽越低的成員應(yīng)繳納更多的基金份額.同時，信譽狀態(tài)長期為無效的節(jié)點將被視為惡意節(jié)點，面臨被系統(tǒng)清除的風(fēng)險.這些獎懲規(guī)則的引入都將有效減少節(jié)點的作惡動機，促使節(jié)點嚴(yán)格遵守協(xié)議，從而顯著提高許可鏈系統(tǒng)的安全性和效率.
4 TTNPBFT 共識算法分析
4.1 通信復(fù)雜度分析
假設(shè)許可鏈系統(tǒng)中共有n個節(jié)點，而每個子網(wǎng)中共有k個節(jié)點.當(dāng)樹形拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)為滿k ?1 叉樹時，子網(wǎng)的總層次數(shù)l等于樹的高度減1
最高層子網(wǎng)數(shù)目為1，并且各層子網(wǎng)數(shù)目構(gòu)成公比為k ?1 的等比數(shù)列.因此，在子網(wǎng)層數(shù)為l的許可鏈系統(tǒng)中，子網(wǎng)總數(shù)s為
而最底層子網(wǎng)總數(shù)s′為
TTNPBFT 在最底層子網(wǎng)中執(zhí)行完整的PBFT 算法.由1.1 節(jié)可知，在節(jié)點總數(shù)為k的網(wǎng)絡(luò)中執(zhí)行PBFT 算法發(fā)送的消息總數(shù)為2k2.由3.2 節(jié)可知，TTNPBFT 在高層次子網(wǎng)中運行簡化的PBFT 算法，發(fā)送的消息總數(shù)為2k2?(k ?1)2=k2+2k ?1.因此，在異步網(wǎng)絡(luò)中達(dá)成一次共識，TTNPBFT 發(fā)送的消息總數(shù)Msum為
因此，TTNPBFT 算法的通信復(fù)雜度近似為O(nk).當(dāng)k=n時，即退變?yōu)槿W(wǎng)共識，其復(fù)雜度為O(n2).當(dāng)子網(wǎng)層數(shù)l= 5、子網(wǎng)節(jié)點數(shù)k= 4 時，全網(wǎng)節(jié)點總數(shù)n= 364.達(dá)成一輪共識，TTNPBFT 所需發(fā)送的消息總數(shù)為3 512，而PBFT 所需發(fā)送的消息總數(shù)為264 992，約為TTNPBFT 的75 倍.因此，相對PBFT 而言，TTNPBFT 極大地減小了通信開銷.此外，由于相同層次子網(wǎng)的共識過程可并行執(zhí)行，共識效率將進一步提高.
4.2 容錯性分析
TTNPBFT 共識算法以樹形拓?fù)渫ㄐ啪W(wǎng)絡(luò)為基礎(chǔ)，這使得網(wǎng)絡(luò)中的節(jié)點形成了明顯的層級關(guān)系，并且節(jié)點所處的層次越高，它們在共識過程中的影響力越大.因此，錯誤節(jié)點在樹形拓?fù)渚W(wǎng)絡(luò)中的分布情況對許可鏈系統(tǒng)的容錯能力有著直接的影響.當(dāng)錯誤節(jié)點均勻分布在每個子網(wǎng)范圍并且子網(wǎng)內(nèi)錯誤節(jié)點數(shù)量不超過(k ?1)/3 時，TTNPBFT 算法的容錯能力與傳統(tǒng)PBFT 算法相同，能夠容忍錯誤節(jié)點的數(shù)量為f, f=(n ?1)/3.事實上，信譽模型能夠幫助形成良好的節(jié)點分布，即高可靠節(jié)點處于較高層次發(fā)揮領(lǐng)導(dǎo)作用，故障節(jié)點處于較低層次產(chǎn)生較小影響，而拜占庭節(jié)點則在一定時間周期內(nèi)不能參與共識.理論上，信譽模型的引入使得TTNPBFT 能夠在一定程度上容忍超過1/3 數(shù)量的拜占庭節(jié)點.
4.3 正確性分析
作為新型的分布式數(shù)據(jù)庫，一個完全正確的區(qū)塊鏈系統(tǒng)必須能夠滿足分布式系統(tǒng)的兩個重要特性：安全性和活性.在許可鏈場景中，關(guān)于安全性與活性的定義如下：1）安全性指每個達(dá)成共識的塊中的事務(wù)都是有效的，并且誠實節(jié)點在任何給定高度上的區(qū)塊都是相同的.2）活性指許可鏈系統(tǒng)在有限時間內(nèi)對客戶端提交的事務(wù)做出正確的響應(yīng).
本文在對抗模型中假設(shè)攻擊者不能破解許可鏈系統(tǒng)使用的密碼算法，因此節(jié)點只要對事務(wù)的數(shù)字簽名、數(shù)字摘要及內(nèi)容格式的正確性進行驗證，就很容易保證事務(wù)的有效性.接下來將證明所有誠實節(jié)點的本地存儲中區(qū)塊的一致性，即在一輪共識中，若有效區(qū)塊b1、b2分別被兩個誠實節(jié)點提交到本地，那么b1=b2.
證明在某個子網(wǎng)中，若b1是有效的，則至少2fk+1 個節(jié)點對b1中的事務(wù)表示認(rèn)可并將b1提交到其本地.同理，同樣需要2fk+1 個節(jié)點對b2中的事務(wù)表示認(rèn)可并將b2提交到其本地.因此，至少需要2(2fk+1)?(3fk+1)=fk+1 個節(jié)點同時認(rèn)同b1與b2.其中，最多有fk個錯誤節(jié)點，而至少有一個誠實節(jié)點.誠實節(jié)點將嚴(yán)格遵守協(xié)議，不會在一輪共識中提交兩個不同的區(qū)塊，因此必定滿足b1=b2.
與PBFT 相同，TTNPBFT 可在網(wǎng)絡(luò)部分同步假設(shè)下通過更換視圖為系統(tǒng)提供活性.在預(yù)準(zhǔn)備階段，從節(jié)點在接收到一個有效的區(qū)塊后將啟動計時器.若系統(tǒng)處于良好狀態(tài)，則區(qū)塊中的事務(wù)請求按照一致性協(xié)議正常被處理，并且客戶端將接收到來自系統(tǒng)的響應(yīng).若計時器超時或主節(jié)點作惡，則從節(jié)點將向其所屬子網(wǎng)內(nèi)廣播Mview-change消息，新視圖的主節(jié)點在收集到2fk個Mview-change消息后，通過廣播一條Mnew-view消息成為新的主節(jié)點并繼續(xù)領(lǐng)導(dǎo)其他節(jié)點執(zhí)行共識.
綜上所述，TTNPBFT 要么在某個確定的視圖下正確地產(chǎn)生新區(qū)快，要么視圖發(fā)生變化.因此，TTNPBFT 能夠滿足許可鏈系統(tǒng)對安全性與活性的要求.
5 TTNPBFT 共識算法性能評估
本文選擇Hyperledger Fabric[32]作為實驗的基本平臺，F(xiàn)abric 是一個模塊化、可擴展的開源系統(tǒng)，可用于部署和運行許可鏈應(yīng)用.本文改進了Fabric v0.6，實現(xiàn)了TTNPBFT 算法，并與Fabric 中的PBFT 算法進行了比較.所有實驗均在廣域網(wǎng)環(huán)境下的10 臺配備英特爾i5-8500 處理器和8 GB DDR4 內(nèi)存的臺式電腦上進行.在每臺主機上運行30 個Docker[33]容器以模擬最大300 個節(jié)點的許可鏈系統(tǒng)，雖然可能會造成一定影響，但不會改變實驗結(jié)果的正確性.接下來從延遲、事務(wù)吞吐量兩方面將TTNPBFT 與傳統(tǒng)PBFT 算法進行比較.
5.1 延遲
區(qū)塊鏈系統(tǒng)的延遲可以定義為從客戶端提交事務(wù)請求到客戶端收到響應(yīng)結(jié)果的時間差.分別測試了全網(wǎng)節(jié)點數(shù)量n為20、40、60、80、100、120、140、160、180、200、220、240、260、280、300 且子網(wǎng)節(jié)點數(shù)量k為4、7、10 時PBFT 與TTNPBFT 算法的延遲，結(jié)果如圖6所示.
總體而言，PBFT 算法的延遲隨著n的增加而急劇增長，這是由其O(n2)的消息復(fù)雜度造成的，因為驗證大量的消息簽名將花費很長時間.雖然TTNPBFT 算法的延遲隨著n的增加同樣有所增長，但基本保持穩(wěn)定，因此能夠為大規(guī)模的許可鏈系統(tǒng)帶來良好的用戶體驗.對于不同的子網(wǎng)規(guī)模，k值越小，樹形拓?fù)渚W(wǎng)絡(luò)的層次數(shù)越大，消息通信階段則越多，延遲相對較大.隨著n的增長，網(wǎng)絡(luò)中消息數(shù)量急劇增加，成為產(chǎn)生延遲的主要因素；k越小，網(wǎng)絡(luò)中消息數(shù)量增長得越慢，因此越小的k對應(yīng)的延遲增長率越小.
圖6 PBFT 和TTNPBFT 的延遲與節(jié)點數(shù)量的關(guān)系Figure 6 Delay of PBFT and TTNPBFT in relation to number of nodes
5.2 事務(wù)吞吐量
區(qū)塊鏈系統(tǒng)的吞吐量可以定義為每秒處理的事務(wù)數(shù)量.分別測試了全網(wǎng)節(jié)點數(shù)量n為20、40、60、80、100、120、140、160、180、200、220、240、260、280、300 且子網(wǎng)節(jié)點數(shù)量k為4、7、10 時PBFT 與TTNPBFT 算法的事務(wù)吞吐量，結(jié)果如圖7所示.
圖7 PBFT 和TTNPBFT 的事務(wù)吞吐量與節(jié)點數(shù)量的關(guān)系Figure 7 Transaction throughput of PBFT and TTNPBFT in relation to number of nodes
由結(jié)果可知，PBFT 算法的性能受節(jié)點數(shù)量的影響較大.當(dāng)節(jié)點數(shù)量超過一定的閾值(大約為120)時，吞吐量會明顯降低，可擴展性問題非常明顯.TTNPBFT 算法的性能隨著節(jié)點數(shù)量的增加基本保持穩(wěn)定，這是因為TTNPBFT 將全網(wǎng)范圍共識拆分為若干子網(wǎng)范圍共識，大幅度減小了通信與計算開銷.因此，即便在節(jié)點數(shù)目較多的情況下，TTNPBFT 依然能夠保持較高的吞吐量，表現(xiàn)出了極高的可擴展性.此外，隨著k的減小，TTNPBFT 的整體性能有所提升，但k的取值太小會導(dǎo)致子網(wǎng)的容錯性下降.在實踐中，選擇k的最優(yōu)值是需要進一步討論的問題.
此外，還測試了全網(wǎng)節(jié)點數(shù)量n=80，子網(wǎng)節(jié)點數(shù)量k=4 時PBFT 與TTNPBFT 的事務(wù)吞吐量隨時間的變化情況，結(jié)果如圖8所示.
初始時刻，TTNPBFT 性能表現(xiàn)不如PBFT，因為高層次主節(jié)點若發(fā)生故障，將連續(xù)在多個子網(wǎng)內(nèi)觸發(fā)多次視圖更換協(xié)議.就整體而言，隨著系統(tǒng)運行時間的增長，PBFT 的吞吐量基本保持不變.TTNPBFT 的吞吐量前期增長比較明顯，隨著時間的推移，增長速度逐漸放緩，吞吐量逐漸趨于穩(wěn)定，這歸功于TTNPBFT 良好的信譽模型.隨著時間的推移，故障節(jié)點的影響逐漸減小，拜占庭節(jié)點參與共識的概率逐漸減小，視圖更換頻率明顯降低，許可鏈系統(tǒng)漸漸達(dá)到最優(yōu)狀態(tài).事實證明，信譽模型能夠有效地提高許可鏈系統(tǒng)的可靠性與穩(wěn)定性.
圖8 PBFT 和TTNPBFT 的事務(wù)吞吐量隨時間的變化情況Figure 8 Transaction throughput of PBFT and TTNPBFT over time
6 結(jié) 語
本文提出了一種基于樹形拓?fù)渚W(wǎng)絡(luò)的實用拜占庭容錯共識算法TTNPBFT.該算法對全網(wǎng)共識任務(wù)進行拆分，減小了任務(wù)的整體規(guī)模，將通信復(fù)雜度降低到O(nk)，大幅減少了帶寬與計算資源的開銷，即使在節(jié)點數(shù)量較大的情況下也能保持良好的輸出性能.
然而，TTNPBFT 仍存在一些不足.許可鏈系統(tǒng)一旦部署，子網(wǎng)節(jié)點數(shù)量k將固定.事實上，k的不同取值對系統(tǒng)的性能與安全性都有較為明顯的影響.此外，對于給定的全網(wǎng)節(jié)點數(shù)量n，并非任意的k值都能構(gòu)成近似滿k ?1 叉樹的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，而在樹形拓?fù)渚W(wǎng)絡(luò)不同層次上實現(xiàn)k的動態(tài)調(diào)整就能妥善解決這個問題.因此，未來的主要工作是實現(xiàn)具有自適應(yīng)能力的TTNPBFT 共識算法，旨在尋求效率與安全之間的均衡.
