包振山，王凱旋，張文博

1.北京工業(yè)大學信息學部，北京100124

2.可信計算北京市重點實驗室，北京100124

區(qū)塊鏈技術的核心價值是能夠在不可靠的網(wǎng)絡環(huán)境中建立節(jié)點間的信任關系，從而形成去中心化的可信分布式系統(tǒng)[1].共識算法是區(qū)塊鏈建立信任的核心技術[2]，能使彼此不信任的參與者以分散的方式對區(qū)塊鏈系統(tǒng)中事務的有效性進行驗證并達成一致.共識算法的效率直接影響區(qū)塊鏈系統(tǒng)的整體性能，因此研究高效的共識算法對區(qū)塊鏈技術的發(fā)展具有積極推動作用.

針對不同的系統(tǒng)模型（同步和異步系統(tǒng)、許可和非許可系統(tǒng)）以及不同的故障模型（崩潰故障和任意故障），已經(jīng)派生出許多不同的共識算法.能夠容忍任意故障的共識算法也稱為拜占庭容錯（Byzantine fault tolerance, BFT）共識算法，該算法源于Lamport 等人提出的拜占庭將軍問題[3].區(qū)塊鏈系統(tǒng)屬于典型的異步系統(tǒng)且系統(tǒng)中節(jié)點的行為是任意的，因此應用于區(qū)塊鏈系統(tǒng)的共識算法應在異步模型存在拜占庭節(jié)點的情況下達成共識.比特幣采用的工作量證明（proof of work, PoW）共識算法[4]的新穎貢獻在于其首次實現(xiàn)了非許可系統(tǒng)模型下的拜占庭共識.盡管PoW 能夠有效抵御女巫攻擊[5]，并在惡意節(jié)點算力不超過50%的情況下為比特幣系統(tǒng)提供安全性保障；可事實證明在非許可模型下達成共識是有代價的，因為比特幣系統(tǒng)每秒最多處理7 筆交易，并且每筆已確認交易的成本約為1～6 美元[6].除PoW 之外，基于證明的共識算法還包括權益證明（proof of stake, PoS）[7]、委托權益證明（delegated proof of stake, DPoS）[8]等.PoS 通過幣齡動態(tài)調(diào)整挖礦難度以降低算力消耗，但依然面臨著嚴重的性能問題.DPoS 減少了參與共識節(jié)點的數(shù)量以提高性能，但在一定程度上違背了區(qū)塊鏈去中心化的設計初衷.

以太坊[9]創(chuàng)始人Vitalik Buterin 提出了區(qū)塊鏈的“三難困境”，即區(qū)塊鏈系統(tǒng)必須在分散性、安全性和可擴展性之間尋求權衡.比特幣等公有鏈系統(tǒng)屬于非許可模型，其系統(tǒng)架構(gòu)完全去中心化，并且不可靠的網(wǎng)絡環(huán)境對系統(tǒng)的安全性提出了極高的要求.因此，效率問題將始終是公有鏈廣泛應用的根本障礙.在許可模型中達成共識是典型的分布式系統(tǒng)問題，Paxos[10]、Raft[11]以及實用拜占庭容錯（practical Byzantine fault tolerance,PBFT）[12]都是經(jīng)典的分布式一致性算法.Paxos 和Raft 無法容忍拜占庭類型的故障，其應用場景一般為可信的分布式數(shù)據(jù)庫系統(tǒng).PBFT 是一種經(jīng)典的基于狀態(tài)機復制的一致性算法，能夠在拜占庭節(jié)點數(shù)量不超過1/3 的情況下達成共識，具有高吞吐量和低響應時間的特點，因而廣泛應用于許可鏈系統(tǒng).隨著許可鏈應用場景規(guī)模的逐漸擴大，PBFT 算法的可擴展性問題日益凸顯.在具有n個共識節(jié)點的許可鏈系統(tǒng)中，PBFT 的通信復雜度為O(n2).隨著節(jié)點數(shù)量的增加，網(wǎng)絡中交換和處理的消息數(shù)量急劇增加.巨大的網(wǎng)絡開銷與計算開銷將導致事務確認延遲顯著增加，吞吐量明顯降低.因此，傳統(tǒng)PBFT 算法只適用于小規(guī)模的局域網(wǎng)，而在大規(guī)模的廣域網(wǎng)環(huán)境下，其可擴展性瓶頸對許可鏈系統(tǒng)的性能帶來了嚴重的影響.

自從出現(xiàn)PBFT 算法后，大量的工作分別從不同角度對PBFT 進行改進以提高其性能.MinBFT[13]、CheapBFT[14]與FastBFT[15]等方案使用安全硬件構(gòu)建可信的執(zhí)行環(huán)境以減少節(jié)點或通信階段數(shù)量.例如，MinBFT 使用可信的計數(shù)器服務改進了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é)議回退到“標準”BFT 算法.實際上，在大規(guī)模許可鏈場景下，系統(tǒng)發(fā)生錯誤的概率大幅增加，頻繁的回退操作將使系統(tǒng)性能顯著下降并處于極度不穩(wěn)定的狀態(tài).基于委員會的PBFT 算法[18-19]選擇網(wǎng)絡節(jié)點的一個子集作為委員會，從而達到提高共識效率的目的，其中委員會代表系統(tǒng)中所有參與者執(zhí)行小規(guī)模的PBFT 算法.然而，這種通過減少參與共識節(jié)點數(shù)量的PBFT 算法在很大程度上增強了許可鏈系統(tǒng)的中心化程度.基于聚合簽名與Gossip 協(xié)議的BFT算法[20]的核心思想比較簡單.每個節(jié)點不斷組合來自鄰居節(jié)點的部分聚合簽名，然后傳播這個聚合簽名，從而降低消息傳遞的復雜性.基于短生命周期簽名方案的PBFT 算法[21]使用低/中安全級別（56 位或80 位）的簽名代替高安全級別（128 位）的簽名，并定期更新短長度的密鑰對以保證安全性.該方案通過改善簽名的大小降低了系統(tǒng)的通信與計算開銷，是一種較為實用的改進方案.在聯(lián)盟鏈場景下，聯(lián)盟由若干個在廣域網(wǎng)中連接的成員組織構(gòu)成，而這些組織可能在其局域網(wǎng)中維護著多個節(jié)點.采用分層設計的PBFT算法[22-23]將通信盡可能本地化以減少廣域通信，從而降低系統(tǒng)的通信開銷.然而，只有當每個組織都在其局域網(wǎng)內(nèi)部署較多節(jié)點時，該方案才會表現(xiàn)出優(yōu)良的性能.

大多數(shù)方案并不能真正為PBFT 算法的可擴展性提供顯著的幫助，因為通信復雜度沒有從根本上得到改善.為了重塑PBFT 算法的可擴展性從而提高現(xiàn)有許可鏈解決方案[24-26]在大規(guī)模應用場景下的適用性，本文提出了一種基于樹形拓撲網(wǎng)絡的實用拜占庭容錯（practical Byzantine fault tolerance based on tree topology network,TTNPBFT）共識算法.TTNPBFT將全網(wǎng)范圍共識拆分為若干子網(wǎng)范圍共識，大幅降低了通信復雜度，為許可鏈在大規(guī)模廣域網(wǎng)的應用與部署提供可能性.

1 預備知識

1.1 PBFT 算法

PBFT 是一種經(jīng)典的狀態(tài)機復制算法，也是當前主流的基于投票的區(qū)塊鏈共識算法，能夠在系統(tǒng)中拜占庭節(jié)點數(shù)量不超過f的情況下通過多輪消息交換達成共識.每一輪共識過程在確定的視圖中執(zhí)行，每個視圖包括一個主節(jié)點和若干個從節(jié)點.PBFT 由一致性協(xié)議、視圖更換協(xié)議和檢查點協(xié)議組成，其執(zhí)行過程如圖1所示.

圖1 PBFT 算法的執(zhí)行過程Figure 1 Execution process of PBFT algorithm

在正常情況下，PBFT 執(zhí)行一致性協(xié)議.所有正確節(jié)點通過一個三階段通信過程達成共識，這3 個階段分別為預準備階段、準備階段、確認階段.在預準備階段，主節(jié)點對來自客戶端的事務請求進行排序并打包成區(qū)塊，通過預準備消息將事務區(qū)塊廣播給從節(jié)點.接收到預準備消息后，每個從節(jié)點都會檢驗其有效性，并向其他節(jié)點廣播一條包含區(qū)塊信息的準備消息以確認從主節(jié)點是否收到了相同的事務區(qū)塊，隨后進入準備階段.收集到2f+1 個匹配的準備消息后，所有節(jié)點廣播一條確認消息以確保視圖在準備階段未發(fā)生變化，隨后進入確認階段.收集到2f+1 個匹配的確認消息后，節(jié)點可以確定已經(jīng)達成共識，執(zhí)行區(qū)塊中的事務并將相應的結(jié)果返回給客戶端.在整個過程中，節(jié)點接收到的所有有效的消息都應該添加到其本地消息日志中.若主節(jié)點發(fā)生故障，則從節(jié)點將觸發(fā)視圖更換協(xié)議，選擇新的主節(jié)點并進入下一個視圖，從而保證系統(tǒng)的活性.檢查點協(xié)議會定期執(zhí)行，用以保證所有節(jié)點狀態(tài)的一致，并幫助節(jié)點及時清除過期的消息以節(jié)省存儲空間.

在具有n個共識節(jié)點的許可鏈系統(tǒng)中，PBFT 算法的通信復雜度為O(n2).在事務請求階段，客戶端發(fā)送n條消息；在預準備階段，主節(jié)點發(fā)送n ?1 條消息；在準備階段，所有從節(jié)點共發(fā)送(n ?1)2條消息；在確認階段，主節(jié)點及從節(jié)點共發(fā)送n(n ?1)條消息；在回復階段，客戶端共收到n條消息.因此，PBFT 算法達成一輪共識，總共需要發(fā)送的消息數(shù)量為n+(n ?1)+(n ?1)2+n(n ?1)+n=2n2.當節(jié)點數(shù)量n=200 時，網(wǎng)絡中發(fā)送消息的數(shù)量達到80 000，這將給通信網(wǎng)絡帶來極大的負擔.

1.2 樹形拓撲網(wǎng)絡

樹形拓撲網(wǎng)絡中的節(jié)點呈樹狀排列，整體看來就像一棵倒置的樹，因而得名.樹形網(wǎng)絡是對星形網(wǎng)絡的一種改進，因由多個層次的星型結(jié)構(gòu)縱向連接而成，因而也叫多星級型網(wǎng)絡.傳統(tǒng)的有線電視網(wǎng)與光纖接入網(wǎng)均采用了樹形網(wǎng)絡拓撲結(jié)構(gòu).樹形網(wǎng)絡拓撲結(jié)構(gòu)易于擴展，容易在網(wǎng)絡中加入新的分支或新的節(jié)點.各分支節(jié)點對父節(jié)點的依賴性較大，如果高層次節(jié)點發(fā)生故障，那么對整個網(wǎng)絡的影響也較大.從這一點來看，樹形拓撲結(jié)構(gòu)的可靠性類似于星形拓撲結(jié)構(gòu).樹形網(wǎng)絡拓撲結(jié)構(gòu)是一種層級結(jié)構(gòu)，適用于分等級的層次型網(wǎng)絡系統(tǒng).這種層次關系與PBFT算法中節(jié)點之間的主從關系非常相似.

2 許可鏈系統(tǒng)模型

2.1 網(wǎng)絡假設

本文假設許可鏈系統(tǒng)中每對節(jié)點之間都通過可靠的點對點雙向信道連接.雖然FLP（Fischer, Lynch, Paterson）不可能定理[27]已經(jīng)證明：在允許節(jié)點出錯的情況下，完全異步的分布式系統(tǒng)無法保證共識能夠在有限時間內(nèi)達成.實際上，在較弱的網(wǎng)絡假設下，分布式系統(tǒng)依然能夠在異步模型中保持活性[28]，如部分同步[29]、間歇性同步[30].與PBFT 相同，本文假設網(wǎng)絡是部分同步的，即消息自發(fā)送起到被目的節(jié)點接收的延遲存在上界.假設整個網(wǎng)絡都是可訪問的，也就是系統(tǒng)中的節(jié)點可以方便地將消息傳輸?shù)饺魏喂?jié)點.每個節(jié)點都在其本地維護一個節(jié)點列表，記錄其他節(jié)點的編號、IP 地址/端口、公鑰、信譽值與狀態(tài)等信息.此外，還假設網(wǎng)絡結(jié)構(gòu)是動態(tài)的，即全網(wǎng)可以感知節(jié)點的加入與離開，這一假設可以通過在許可鏈系統(tǒng)中配置可信的證書頒發(fā)機構(gòu)（certificate authority, CA）來實現(xiàn)[31].

2.2 對抗模型

本文假設許可鏈系統(tǒng)中共有n=3f+1 個節(jié)點，f為P2P 網(wǎng)絡中任意時刻錯誤節(jié)點的最大數(shù)量.錯誤節(jié)點的行為可以是任意的，如相互勾結(jié)或保持沉默等.錯誤節(jié)點的存在可能使網(wǎng)絡中傳輸?shù)南G失、延遲、重復或者亂序，但本文假設對手不能無限期地延遲正確的節(jié)點.此外，還假設攻擊者是算力有限的，不能破解許可鏈系統(tǒng)所使用的密碼算法，從而不能偽造正確節(jié)點的簽名以進行身份假冒攻擊，不能由數(shù)字摘要進行逆運算獲得原始信息，也不能找到具有相同摘要的兩條消息.

2.3 基于信譽模型的樹形拓撲通信網(wǎng)絡

基于“化整為零”的思想，TTNPBFT 將全網(wǎng)范圍的共識任務拆分為若干子網(wǎng)范圍的共識任務，大幅減小了PBFT 算法的通信復雜度.TTNPBFT 借助于樹形拓撲網(wǎng)絡實現(xiàn)這一目標.每個父節(jié)點（非葉子節(jié)點）與其孩子節(jié)點形成一個子網(wǎng)，父節(jié)點擔任主節(jié)點，孩子節(jié)點作為從節(jié)點.

構(gòu)建可靠的樹形拓撲通信網(wǎng)絡是一項至關重要的任務.可靠性差是樹形拓撲網(wǎng)絡的一個顯著缺點，并且錯誤節(jié)點所處的層次越高對網(wǎng)絡造成的影響將越大，因此應盡可能地使高可靠的節(jié)點處于較高的網(wǎng)絡層次上.TTNPBFT 通過信譽模型有效評估共識節(jié)點行為的準確性，并以此來衡量一個節(jié)點是否足夠可信與可靠.基于節(jié)點的信譽值能夠構(gòu)建可靠的樹形拓撲通信網(wǎng)絡，一旦發(fā)現(xiàn)錯誤節(jié)點，網(wǎng)絡結(jié)構(gòu)便動態(tài)地進行調(diào)整.隨著時間的推移，錯誤節(jié)點的信譽值逐漸減小，其影響力將越來越低.基于信譽模型的樹形拓撲通信網(wǎng)絡如圖2所示.

圖2 基于信譽模型的樹形拓撲通信網(wǎng)絡Figure 2 Tree topology communication network based on reputation model

樹形拓撲通信網(wǎng)絡的初次構(gòu)建是隨著許可鏈系統(tǒng)的部署進行的.由于所有節(jié)點的初始信譽值完全相同，一般可采用隨機方式建立樹形網(wǎng)絡拓撲結(jié)構(gòu)，但為了使系統(tǒng)更可靠，應當以參與者的實際情況作為參考.例如，社會影響力較大的組織或機構(gòu)往往具備更可靠的信用背書.因此，以參與者的信用背書為主要依據(jù)進行通信網(wǎng)絡的初次構(gòu)建更為合理.隨著時間的推移，系統(tǒng)的信譽模型將會完全取代參與者本身的信用背書.

3 TTNPBFT 共識算法設計

TTNPBFT 共識算法以PBFT 算法為基礎，并結(jié)合信譽模型與樹形拓撲網(wǎng)絡的特征對一致性協(xié)議與視圖更換協(xié)議進行了改進.本章對TTNPBFT 進行詳細介紹.

3.1 信譽模型

信譽模型能夠為錯誤節(jié)點檢測提供良好的基礎.一方面，通過動態(tài)調(diào)整節(jié)點的信譽值降低錯誤節(jié)點在樹形拓撲網(wǎng)絡中的層次，能夠不斷減小錯誤節(jié)點在共識過程中的影響力，從而使許可鏈系統(tǒng)保持較高的可用性與可靠性.另一方面，可將共識節(jié)點的信譽值作為獎勵與懲罰的標準以促使節(jié)點遵循協(xié)議.

定義1信譽值是衡量節(jié)點可信程度的參考指標.信譽值R是介于0.1 和1.0 之間的實數(shù).信譽值越高，則對應節(jié)點的可信度越高.新加入許可鏈系統(tǒng)的節(jié)點，其信譽值初始化為0.5.

定義2信譽獎懲指信譽值將根據(jù)節(jié)點在共識過程中的行為動態(tài)變化.令Rv表示某個節(jié)點在視圖v中的信譽值，則該節(jié)點在視圖v+1 中的信譽值Rv+1與Rv的關系如下：

1）如果主節(jié)點成功生成一個有效的區(qū)塊，或者從節(jié)點的消息內(nèi)容與最終結(jié)果相同，那么這些節(jié)點的信譽逐漸提高，其計算公式為

因為采用了對數(shù)公式，所以隨著誠實節(jié)點信譽的不斷提升，其信譽值的增長率會降低.采用這種方式可增加獲得高信譽值的難度，惡意節(jié)點若想具備極高的信譽值，在樹形網(wǎng)絡中處于較高的層次，則需要付出極大的努力.參數(shù)a用于避免信譽值較低時增長幅度過大的問題.

2）如果主節(jié)點本輪未能領導產(chǎn)生新的區(qū)塊，或者從節(jié)點消息內(nèi)容與最終結(jié)果不一致，甚至沒有發(fā)送任何消息，則相應節(jié)點的信譽值會線性下降，其計算公式為

信譽值的下降速度取決于參數(shù)b，b取值的大小應該根據(jù)具體應用場景的需求來設置.

3）如果同一節(jié)點向其他共識節(jié)點發(fā)送不一致的消息，那么該節(jié)點將被視為拜占庭節(jié)點，其信譽直接降為最小值，即

定義3信譽狀態(tài)是限制節(jié)點權限的重要依據(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)對安全性的要求程度有關.圖3展示了節(jié)點不同信譽狀態(tài)之間的轉(zhuǎn)換關系.

圖3 節(jié)點信譽狀態(tài)之間的轉(zhuǎn)換關系Figure 3 Transition relationship between node reputation states

不同信譽狀態(tài)的節(jié)點擁有不同的權限.為了保證系統(tǒng)的效率與安全，規(guī)定只有優(yōu)秀節(jié)點可擔任根節(jié)點，異常節(jié)點不能擔任主節(jié)點，無效節(jié)點則不能參與共識.節(jié)點權限與其信譽狀態(tài)的對應關系見表2.

表2 節(jié)點權限與信譽狀態(tài)的對應關系Table 2 Relationship between node permissions and reputation status

定義4信譽恢復指節(jié)點的信譽值低于β時將逐漸恢復.從原則上講，應當給予無效節(jié)點“改過”的機會，于是給出如下規(guī)定：每經(jīng)過T時間周期，無效節(jié)點的信譽值將上升c，但不能超過β，其具體計算公式為

式中，t為該節(jié)點最后一次參與共識距現(xiàn)在的總時間.

定義5信譽更新指節(jié)點維護其本地節(jié)點列表的過程.信譽更新發(fā)生在每一次視圖更換之前，用以保證具有最高信譽的節(jié)點當選為主節(jié)點.在一般情況下，各個節(jié)點只需通過其本地的消息日志，根據(jù)信譽獎懲標準對其所在子網(wǎng)內(nèi)其他節(jié)點的信譽值與信譽狀態(tài)進行更新，此過程由節(jié)點獨自完成而不需要通信.但一定時間之后，可能會出現(xiàn)節(jié)點狀態(tài)不一致的情況.因此，類似于PBFT 算法的檢查點協(xié)議，子網(wǎng)范圍的信譽更新將周期性執(zhí)行，所有節(jié)點通過消息廣播的方式將子網(wǎng)內(nèi)的信譽值達成一致.信譽更新過程在各個子網(wǎng)內(nèi)獨立執(zhí)行，因此不會對系統(tǒng)整體性能產(chǎn)生明顯影響.

為了保證許可鏈系統(tǒng)的安全性，應及時清除系統(tǒng)中的惡意節(jié)點.根據(jù)式(4)可得信譽值從最小值0.1 恢復到β所需要的時間t′為

本文將“長期”定義為在10t′時間周期內(nèi)達到3t′的時間，并將長期處于無效狀態(tài)的節(jié)點認定為惡意節(jié)點.在信譽更新過程中，節(jié)點列表中的惡意節(jié)點將被刪除.

3.2 一致性協(xié)議

TTNPBFT 共識算法使用密碼技術來防止欺騙攻擊與重播攻擊，同時保證消息的完整性.消息包含了數(shù)字簽名和無碰撞哈希函數(shù)生成的數(shù)字摘要.為了便于描述，首先在表3中定義相關符號.

TTNPBFT 通過樹形拓撲網(wǎng)絡將全網(wǎng)劃分成若干子網(wǎng)，這些子網(wǎng)分布在不同的層次.在每個子網(wǎng)中，父節(jié)點作為主節(jié)點，領導其孩子節(jié)點在該子網(wǎng)范圍內(nèi)執(zhí)行相應的PBFT 算法.根據(jù)樹形拓撲網(wǎng)絡的層級屬性，TTNPBFT 對PBFT 一致性協(xié)議的預準備階段和回復階段進行了改進.在預準備階段，全網(wǎng)主節(jié)點Sroot向其領導的子網(wǎng)內(nèi)廣播預準備消息，該子網(wǎng)內(nèi)的從節(jié)點作為下一層子網(wǎng)的主節(jié)點將繼續(xù)轉(zhuǎn)發(fā)該預準備消息，直至最底層子網(wǎng).與此類似，在回復階段，最底層子網(wǎng)節(jié)點的回復消息將逐層向上傳播，客戶端最終只會收到來自最高層子網(wǎng)節(jié)點的回復消息.在TTNPBFT 中，只有最底層子網(wǎng)運行完整的PBFT 算法，而高層子網(wǎng)則運行簡化的PBFT 算法（準備階段與確認階段合并）.當n= 40, k= 4 時，樹形拓撲網(wǎng)絡中的所有子網(wǎng)處于3 個層次上.圖4給出了TTNPBFT 算法的一輪完整的共識過程.

表3 相關符號Table 3 Related symbols

圖4 TTNPBFT 的共識過程Figure 4 Consensus process of TTNPBFT

具體算法如Algorithm 1 所示：

該過程的詳細描述如下：

步驟1客戶端c向全網(wǎng)主節(jié)點Sroot發(fā)送消息 σc請求執(zhí)行事務tx.

步驟2Sroot將來自于客戶端的事務請求打包成區(qū)塊b，然后在其子網(wǎng)范圍內(nèi)廣播一條預準備消息< σSroot,Sroot,b >.若該子網(wǎng)中的從節(jié)點同時作為下一層子網(wǎng)的主節(jié)點，則以相同的消息格式（更換視圖與簽名后）繼續(xù)在其領導的子網(wǎng)內(nèi)廣播該預準備消息.重復這個過程，直至最底層子網(wǎng).

步驟3最底層子網(wǎng)中的從節(jié)點接收到預準備消息后對其合法性進行驗證，驗證內(nèi)容主要包括：預準備消息簽名的正確性、視圖v的正確性、摘要d與區(qū)塊b的哈希值是否一致以及b中事務是否重放等.若預準備消息有效，則將其存入本地消息日志并向子網(wǎng)內(nèi)其他節(jié)點廣播準備消息，從而就區(qū)塊序列號sn 達成一致.準備消息格式為σi,i為從節(jié)點在子網(wǎng)中的編號.

步驟4最底層子網(wǎng)中的節(jié)點（包括主節(jié)點）收集到2fk+ 1 條匹配的準備消息后，它們將廣播一條確認消息 σi以確認視圖沒有發(fā)生變化.若隨后最底層子網(wǎng)中的從節(jié)點收集到2fk+ 1 條匹配的確認消息，則向主節(jié)點發(fā)送回復信息σi，rs 為預執(zhí)行結(jié)果集.

步驟5子網(wǎng)的主節(jié)點統(tǒng)計回復信息，若存在fk+1 個匹配的預執(zhí)行結(jié)果集rs，便將rs作為該子網(wǎng)的共識結(jié)果.在將該結(jié)果集繼續(xù)向上層子網(wǎng)傳遞之前，需在其所屬的子網(wǎng)內(nèi)確認得到了相同的事務區(qū)塊且當前視圖未發(fā)生變化，操作同步驟4.若發(fā)現(xiàn)其主節(jié)點作惡或視圖已改變，則向下廣播一條共識失敗消息 σi直至最底層子網(wǎng)，其中φ為2fk個匹配的確認消息，用以證明共識失敗，此時sn 所對應的區(qū)塊b將作廢.若一切正常，則將結(jié)果集rs 發(fā)送給上層子網(wǎng).重復該過程，直至最高層子網(wǎng).最高層子網(wǎng)中的節(jié)點不再向主節(jié)點發(fā)送回復消息，而是直接向客戶端提交結(jié)果.客戶端一旦收到fk+1 個匹配的結(jié)果便可確認共識已經(jīng)達成.

需要注意的是：最底層子網(wǎng)完成確認階段后，節(jié)點并不應該直接將事務的執(zhí)行結(jié)果寫入本地賬本，因為共識還沒有完全達成.在結(jié)果向上傳送的過程中，共識依然可能會失??；而新的預準備消息的到來意味著上一輪共識已經(jīng)結(jié)束，節(jié)點應當此時提交上一輪的事務到本地.

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ā)生故障，則將在其領導的子網(wǎng)內(nèi)觸發(fā)視圖更換協(xié)議.TTNPBFT 采取擇優(yōu)替換原則，即在該子網(wǎng)范圍內(nèi)選擇信譽值最高的節(jié)點擔任新的主節(jié)點.圖5展示了極端情況下TTNPBFT 的全網(wǎng)主節(jié)點Sroot發(fā)生拜占庭錯誤時的視圖更換過程.視圖更換協(xié)議不僅要求所有節(jié)點就新視圖達成一致，還需要考慮如何在新視圖中處理上一視圖的遺留事務，這是一個較為復雜的過程.在此采用簡化后的描述，更詳細的介紹請參考文獻[12].

圖5 TTNPBFT 的視圖更換過程Figure 5 View-change process of TTNPBFT

具體算法如Algorithm 2 所示：

該過程的詳細描述如下：

步驟1若某個主節(jié)點出錯或成為其他子網(wǎng)的主節(jié)點，則其所領導子網(wǎng)的所有從節(jié)點將進行信譽更新，并判斷該主節(jié)點的信譽值在子網(wǎng)范圍內(nèi)是否為最大值.若滿足條件，協(xié)議結(jié)束；否則，從節(jié)點將向其所屬的子網(wǎng)內(nèi)廣播一條視圖更換消息σi，sn 為其本地最后一次提交的區(qū)塊的序列號.

步驟2子網(wǎng)內(nèi)信譽值最高的從節(jié)點收集到2fk個匹配的視圖更換消息后，它將向該子網(wǎng)內(nèi)廣播新視圖消息σi，同時向其領導的下一層子網(wǎng)（若存在）內(nèi)廣播新視圖消息σi，φ′為2fk個視圖更換消息的集合，用以證明其獲得了足夠的支持，v′為下層子網(wǎng)的當前視圖，p為被替代的主節(jié)點，Rp為被替代主節(jié)點的信譽值.

步驟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重復步驟1～3，直至故障節(jié)點到達指定的位置，即成為較低層次子網(wǎng)的主節(jié)點或成為最底層子網(wǎng)的從節(jié)點.

信譽模型規(guī)定：故障節(jié)點的信譽值會逐漸減小，而拜占庭節(jié)點的信譽值被直接置為最小值.因此，視圖更換協(xié)議結(jié)束后故障節(jié)點在樹形拓撲網(wǎng)絡中所處的層次會降低，而拜占庭節(jié)點將直接成為最底層子網(wǎng)的從節(jié)點，作惡代價非常大.

3.4 激勵與懲罰機制

如果一個惡意節(jié)點總是付出高成本而獲得低回報，那么該節(jié)點將失去攻擊系統(tǒng)的動機，比特幣就完美地詮釋了這個道理.在基于PBFT 算法的許可鏈系統(tǒng)中，共識節(jié)點尤其是主節(jié)點通常是攻擊者的主要目標，相對于普通的記賬節(jié)點，共識節(jié)點時刻面臨著嚴峻的安全威脅.此外，共識節(jié)點的帶寬資源、計算資源與存儲資源的開銷也是非常顯著的.因此，許可鏈系統(tǒng)同樣需要建立適當?shù)募钆c懲罰機制以提高正確節(jié)點參與共識的積極性.

本文考慮了一種基于信譽的激勵與懲罰機制.聯(lián)盟成員共同設立獎勵基金，使長期具有高信譽的成員將獲得更多的實質(zhì)性獎勵.在懲罰方面，信譽越低的成員應繳納更多的基金份額.同時，信譽狀態(tài)長期為無效的節(jié)點將被視為惡意節(jié)點，面臨被系統(tǒng)清除的風險.這些獎懲規(guī)則的引入都將有效減少節(jié)點的作惡動機，促使節(jié)點嚴格遵守協(xié)議，從而顯著提高許可鏈系統(tǒng)的安全性和效率.

4 TTNPBFT 共識算法分析

4.1 通信復雜度分析

假設許可鏈系統(tǒng)中共有n個節(jié)點，而每個子網(wǎng)中共有k個節(jié)點.當樹形拓撲網(wǎng)絡結(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)絡中執(zhí)行PBFT 算法發(fā)送的消息總數(shù)為2k2.由3.2 節(jié)可知，TTNPBFT 在高層次子網(wǎng)中運行簡化的PBFT 算法，發(fā)送的消息總數(shù)為2k2?(k ?1)2=k2+2k ?1.因此，在異步網(wǎng)絡中達成一次共識，TTNPBFT 發(fā)送的消息總數(shù)Msum為

因此，TTNPBFT 算法的通信復雜度近似為O(nk).當k=n時，即退變?yōu)槿W(wǎng)共識，其復雜度為O(n2).當子網(wǎng)層數(shù)l= 5、子網(wǎng)節(jié)點數(shù)k= 4 時，全網(wǎng)節(jié)點總數(shù)n= 364.達成一輪共識，TTNPBFT 所需發(fā)送的消息總數(shù)為3 512，而PBFT 所需發(fā)送的消息總數(shù)為264 992，約為TTNPBFT 的75 倍.因此，相對PBFT 而言，TTNPBFT 極大地減小了通信開銷.此外，由于相同層次子網(wǎng)的共識過程可并行執(zhí)行，共識效率將進一步提高.

4.2 容錯性分析

TTNPBFT 共識算法以樹形拓撲通信網(wǎng)絡為基礎，這使得網(wǎng)絡中的節(jié)點形成了明顯的層級關系，并且節(jié)點所處的層次越高，它們在共識過程中的影響力越大.因此，錯誤節(jié)點在樹形拓撲網(wǎng)絡中的分布情況對許可鏈系統(tǒ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ā)揮領導作用，故障節(jié)點處于較低層次產(chǎn)生較小影響，而拜占庭節(jié)點則在一定時間周期內(nèi)不能參與共識.理論上，信譽模型的引入使得TTNPBFT 能夠在一定程度上容忍超過1/3 數(shù)量的拜占庭節(jié)點.

4.3 正確性分析

作為新型的分布式數(shù)據(jù)庫，一個完全正確的區(qū)塊鏈系統(tǒng)必須能夠滿足分布式系統(tǒng)的兩個重要特性：安全性和活性.在許可鏈場景中，關于安全性與活性的定義如下：1）安全性指每個達成共識的塊中的事務都是有效的，并且誠實節(jié)點在任何給定高度上的區(qū)塊都是相同的.2）活性指許可鏈系統(tǒng)在有限時間內(nèi)對客戶端提交的事務做出正確的響應.

本文在對抗模型中假設攻擊者不能破解許可鏈系統(tǒng)使用的密碼算法，因此節(jié)點只要對事務的數(shù)字簽名、數(shù)字摘要及內(nèi)容格式的正確性進行驗證，就很容易保證事務的有效性.接下來將證明所有誠實節(jié)點的本地存儲中區(qū)塊的一致性，即在一輪共識中，若有效區(qū)塊b1、b2分別被兩個誠實節(jié)點提交到本地，那么b1=b2.

證明在某個子網(wǎng)中，若b1是有效的，則至少2fk+1 個節(jié)點對b1中的事務表示認可并將b1提交到其本地.同理，同樣需要2fk+1 個節(jié)點對b2中的事務表示認可并將b2提交到其本地.因此，至少需要2(2fk+1)?(3fk+1)=fk+1 個節(jié)點同時認同b1與b2.其中，最多有fk個錯誤節(jié)點，而至少有一個誠實節(jié)點.誠實節(jié)點將嚴格遵守協(xié)議，不會在一輪共識中提交兩個不同的區(qū)塊，因此必定滿足b1=b2.

與PBFT 相同，TTNPBFT 可在網(wǎng)絡部分同步假設下通過更換視圖為系統(tǒng)提供活性.在預準備階段，從節(jié)點在接收到一個有效的區(qū)塊后將啟動計時器.若系統(tǒng)處于良好狀態(tài)，則區(qū)塊中的事務請求按照一致性協(xié)議正常被處理，并且客戶端將接收到來自系統(tǒng)的響應.若計時器超時或主節(jié)點作惡，則從節(jié)點將向其所屬子網(wǎng)內(nèi)廣播Mview-change消息，新視圖的主節(jié)點在收集到2fk個Mview-change消息后，通過廣播一條Mnew-view消息成為新的主節(jié)點并繼續(xù)領導其他節(jié)點執(zhí)行共識.

綜上所述，TTNPBFT 要么在某個確定的視圖下正確地產(chǎn)生新區(qū)快，要么視圖發(fā)生變化.因此，TTNPBFT 能夠滿足許可鏈系統(tǒng)對安全性與活性的要求.

5 TTNPBFT 共識算法性能評估

本文選擇Hyperledger Fabric[32]作為實驗的基本平臺，F(xiàn)abric 是一個模塊化、可擴展的開源系統(tǒ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é)果的正確性.接下來從延遲、事務吞吐量兩方面將TTNPBFT 與傳統(tǒng)PBFT 算法進行比較.

5.1 延遲

區(qū)塊鏈系統(tǒ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)的消息復雜度造成的，因為驗證大量的消息簽名將花費很長時間.雖然TTNPBFT 算法的延遲隨著n的增加同樣有所增長，但基本保持穩(wěn)定，因此能夠為大規(guī)模的許可鏈系統(tǒng)帶來良好的用戶體驗.對于不同的子網(wǎng)規(guī)模，k值越小，樹形拓撲網(wǎng)絡的層次數(shù)越大，消息通信階段則越多，延遲相對較大.隨著n的增長，網(wǎng)絡中消息數(shù)量急劇增加，成為產(chǎn)生延遲的主要因素；k越小，網(wǎng)絡中消息數(shù)量增長得越慢，因此越小的k對應的延遲增長率越小.

圖6 PBFT 和TTNPBFT 的延遲與節(jié)點數(shù)量的關系Figure 6 Delay of PBFT and TTNPBFT in relation to number of nodes

5.2 事務吞吐量

區(qū)塊鏈系統(tǒng)的吞吐量可以定義為每秒處理的事務數(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 算法的事務吞吐量，結(jié)果如圖7所示.

圖7 PBFT 和TTNPBFT 的事務吞吐量與節(jié)點數(shù)量的關系Figure 7 Transaction throughput of PBFT and TTNPBFT in relation to number of nodes

由結(jié)果可知，PBFT 算法的性能受節(jié)點數(shù)量的影響較大.當節(jié)點數(shù)量超過一定的閾值(大約為120)時，吞吐量會明顯降低，可擴展性問題非常明顯.TTNPBFT 算法的性能隨著節(jié)點數(shù)量的增加基本保持穩(wěn)定，這是因為TTNPBFT 將全網(wǎng)范圍共識拆分為若干子網(wǎng)范圍共識，大幅度減小了通信與計算開銷.因此，即便在節(jié)點數(shù)目較多的情況下，TTNPBFT 依然能夠保持較高的吞吐量，表現(xiàn)出了極高的可擴展性.此外，隨著k的減小，TTNPBFT 的整體性能有所提升，但k的取值太小會導致子網(wǎng)的容錯性下降.在實踐中，選擇k的最優(yōu)值是需要進一步討論的問題.

此外，還測試了全網(wǎng)節(jié)點數(shù)量n=80，子網(wǎng)節(jié)點數(shù)量k=4 時PBFT 與TTNPBFT 的事務吞吐量隨時間的變化情況，結(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)漸漸達到最優(yōu)狀態(tài).事實證明，信譽模型能夠有效地提高許可鏈系統(tǒng)的可靠性與穩(wěn)定性.

圖8 PBFT 和TTNPBFT 的事務吞吐量隨時間的變化情況Figure 8 Transaction throughput of PBFT and TTNPBFT over time

6 結(jié) 語

本文提出了一種基于樹形拓撲網(wǎng)絡的實用拜占庭容錯共識算法TTNPBFT.該算法對全網(wǎng)共識任務進行拆分，減小了任務的整體規(guī)模，將通信復雜度降低到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)絡拓撲結(jié)構(gòu)，而在樹形拓撲網(wǎng)絡不同層次上實現(xiàn)k的動態(tài)調(diào)整就能妥善解決這個問題.因此，未來的主要工作是實現(xiàn)具有自適應能力的TTNPBFT 共識算法，旨在尋求效率與安全之間的均衡.