一種區塊鏈實用拜占庭容錯算法的改進

韓鎮陽 宮寧生 任珈民

(南京工業大學計算機科學與技術學院 江蘇 南京 211816)

0 引 言

Satoshi Nakamoto(中本聰)[1]在2008年初次提出了區塊鏈技術概念，這一技術的產生實現了真正意義上的去中心化可信任的數字貨幣交易系統，其本質是分布式系統，具有去中心化與安全可信的特點。隨著區塊鏈技術不斷發展，共識算法也逐漸被研究人員所重視，其中共識算法如何選擇是區塊鏈設計的核心部分[2]。共識算法的研究很早便已經開始，例如工作量證明(Proof of Work，POW)[3]、權益證明(Proof of Stake，POS)、實用性拜占庭容錯算法[4]以及Raft算法[5]等。拜占庭共識算法起源于古羅馬時代的拜占庭將軍問題，簡單來說這是分布式一致性的問題，拜占庭將領們必須所有人統一協商是否在某一時刻對敵人發起進攻。假如將領中存在背叛者，背叛者會發出虛假消息來迷惑其他將領們的進攻，將領們怎樣在存在背叛者的前提下達成統一的決定，并最終攻下敵軍正是問題的核心內容。拜占庭容錯算法，在分布式系統領域可以闡述為：怎樣在存在作惡節點的系統中確保系統運行狀態良好以及數據信息的真實性、一致性和完整性，并且作出正確的決定。

20世紀80 年代，Leslie Lamport等通過拜占庭將軍問題提出了著名的拜占庭容錯(Byzantine Fault Tolerance, BFT)算法。與Bitcoin的“挖礦”工作量證明POW共識算法不同，BFT 類協議通過各個節點相互發送消息對提案和指令達成最終統一的共識結果，然而正是由于這些特點造成了節點之間消息遞歸傳遞呈指數級復雜度，加上節點的加入和退出這一步驟需要進行特殊處理，BFT算法并不太具有實際操作性。雖然這一算法存在很多缺點，但是它在解決拜占庭問題上給出了一種新型的思路，不像POW那樣消耗大量的公共電力資源，為后來實用性拜占庭容錯算法PBFT的出現作了鋪墊。

1999年，Miguel Castro和Barbara Liskov等提出多項式級別的實用性拜占庭容錯算法改進于拜占庭共識算法BFT，繼承了它的優點，并且大規模降低了拜占庭協議的開銷，因此拜占庭算法在區塊鏈系統中能夠被應用。PBFT算法是基于狀態機副本復制的算法，每個狀態機副本都能保存服務狀態，滿足用戶的合法請求，不僅可以完成交易，還能夠實現不同類型的操作。系統中最多可以滿足f=(N-1)/3(N為節點總數)數量的作惡節點，這樣仍能保持系統的安全性和活性[6]，最終達成一致的分布式共識。

目前的PBFT算法還存在很多不足，隨著大規模區塊鏈系統的發展和興起，研究人員逐漸著眼于怎樣簡化實用性拜占庭協議的設計，優化拜占庭協議的性能，用來提高容忍數據產生的多種錯誤。首先，PBFT算法采用C/S架構[7]，不能動態感知節點數目的變化，更不能應用于P2P[8]網絡模型，如果想要增加節點，系統必須重啟，造成系統資源不必要的浪費，影響實用性和用戶體驗，尤其在某些應用中經常性的系統重啟是非常致命的。在主節點選舉上也沒有對主節點的真偽性進行驗證，因此很有可能選舉出惡意節點并且具有非常高的危險性。三階段協商中高強度的網絡通信和網絡傳輸開銷同樣需要進一步的改進優化。PBFT協議中的視圖轉換算法中存在漏洞，客戶端重復請求會導致視圖不停地進行變更，從而影響正常的服務，甚至陷入宕機，如果主節點作惡，它可能會給不同的請求編上相同的序號，或者不去分配序號，或者讓相鄰的序號不連續。

本文在比較分析一些已有的經典共識算法后，基于傳統PBFT算法提出了一種能夠減少開銷、增大吞吐量的改進拜占庭共識算法IPBFT，實現了協商節點與執行節點分離。傳統的實用性拜占庭容錯算法需要3f+1個節點，但是如此多的節點會產生一定浪費，因為執行客戶端請求的節點只需要很少一部分。因此，可以將協商與執行請求分開，一部分節點負責協商請求，一部分節點負責執行請求，對于執行時間較長的請求，降低執行請求的節點的數量能夠提升系統吞吐率。IPBFT 算法中主節點的選舉方式在依據節點編號選舉方式的基礎上改為心跳檢測機制并結合最大視圖號和最大編號請求的節點選舉，也就是心跳檢測以及最長鏈選舉，使得主節點的選舉方式更加合理，選舉出的主節點更加具有穩定性和安全性。在一致性協議中，加入了自證機制，進一步減少了拜占庭節點的作惡幾率，提高了系統的穩定性。為了解決PBFT在視圖變更算法中存在的問題，IPBFT算法結合協商與執行分離原則，引入了懷疑-證明機制，IPBFT算法中的副本節點將主動檢查每條消息序號的準確性。系統設置超時機制，如果主節點失效或者惡意節點不發送客戶端的請求，向所有副本節點發送請求消息。當主節點被副本節點檢測出失效或者是惡意節點時，系統將發起視圖轉換協議View Change。

1 相關工作

1.1 傳統共識算法

在區塊鏈系統中，共識算法如何選擇非常重要，算法的核心是在區塊鏈系統中利用共識算法來保證整個系統的一致性。目前，區塊鏈中主流的算法主要包括工作量證明(PoW)、權益證明(PoS)[9]、實用拜占庭容錯算法(PBFT)以及Paxos算法的變種算法Raft、Algorand算法等。不同的算法具有不同的優劣勢，適用于不同的應用中。

1.1.1工作量證明

PoW是首個應用于區塊鏈的共識算法，由Satoshi Nakamoto在他的論文中提出，用以創立分布式去中心化無信任共識的機制，并且能夠解決雙重花費的問題。PoW不是一個全新的理念，只是Nakamoto將工作量證明算法與Merkle Tree、數字簽名和P2P網絡等一些已知的技術聯系起來，產生了一種具有實用性的分布式共識系統。Bitcoin采用的就是PoW共識算法來確定區塊鏈網絡的一致性，目前為止PoW被認為是最具有安全性的公有鏈共識算法。它的核心技術是根據節點的算力來競爭并使得數據能夠達成一致，并且共識的安全性能夠得到保證。在比特幣中，礦工們根據計算機的性能算力競爭求解一個非常復雜的SHA256哈希函數，但是這個哈希函數很容易被驗證，能夠首先解決這個哈希函數的節點可以得到下一區塊的記賬權，以及系統自動生成的獎勵——比特幣。PoW 共識也有著明顯的缺點，PoW算法所需要的強大算力造成的資源浪費是它最主要的問題。其次假設敵對者控制了全網51%以上的的節點，敵對者就能在系統中偽造區塊信息，甚至不需要51%的節點區塊鏈系統也會受到攻擊。長達十分鐘的交易確認時間過長，同樣也不適用于商業應用。

1.1.2權益證明

2012年出現的點點幣PPC第一次應用了PoS權益證明共識算法。在系統中擁有最高權益而不是最高算力的節點可以得到記賬的所有權，PPC是PoW和PoS這兩種算法結合的結果，剛開始時PoS算法使用的是PoW中的挖礦方式，這樣Token將會被公正地分配給礦工，到了后期因為挖礦難度增加，PoS將接管整個系統的算法維護。相對于PoW算法，PoS減輕了資源的浪費問題，交易確認時間也大大減少，所以比特幣產生之后，很多數字貨幣采用的都是PoS共識算法。PoS算法的缺點是核心權益掌控者在一定程度上違背了分布式賬本去中心化的初衷。

1.1.3Raft算法

Paxos算法由Leslie Lamport在1990年提出，具有高度容錯性，其復雜的原理和算法非常難懂也難以實現，于是就有了Paxos的簡化版——Raft 算法。領導者、跟隨者和候選人是Raft算法中的三種主要節點，隨著時間和環境的變化它們能夠相互轉換。Raft算法主要有兩個過程：日志復制和領導者選舉。日志復制又被分為兩個階段：記錄日志和提交數據。(N-1)/2是系統中能夠承受的最大的故障節點數量(N為總節點數)。但是，Raft算法是面向數據而不是面向交易的，只支持容錯故障節點，而不支持容錯作惡節點，沒有考慮到系統中作惡節點存在的情況，加入系統中的作惡節點發送惡意消息，整個系統將會存儲惡意錯誤的信息。

1.1.4Algoand算法

Algorand[10]算法可以避免區塊鏈分叉，確認交易的時間也將大大減少，算法的總流程主要由兩個部分組成：BA*和塊提議。拜占庭協議BA*是Algorand算法中的核心技術，具有很強的擴展性，用戶只能夠保留私鑰。在塊提議中，根據加密抽簽選舉的方式在普通節點中選擇出委員會成員，接著從委員會成員中再次以加密抽簽選舉出提議者，每個提議者都擁有提議塊的權利。然后連同哈希和證明一起傳播到網絡上。根據BA*協議，當所有委員會成員接到同樣的消息后對塊達成共識。

1.2 PBFT算法

PBFT算法旨在解決如何在整個系統中存在作惡節點的情況下依然能保證最終決策的一致性和正確性的問題，該算法給傳輸來的消息進行共識，得到一個全局的序。在惡意節點不高于總數1/3的情況下，該算法能夠同時保證安全性(Safety)和活性(Liveness)[11]，該算法首次將拜占庭容錯算法復雜度從指數級降低到了多項式級O(N2)。PBFT算法中所有節點被分為客戶端、主節點和副本節點三種類型，流程被分為一致性協議、視圖變更協議和檢查點協議。其中一致性協議又被分為三個階段：預準備階段(PRE-PREPARE)、準備階段(PREPARE)和確認階段(COMMIT)。具體過程如圖1所示。

圖1 PBFT一致性協議算法流程圖

當客戶端收到了至少N+1個節點的結果是相同的情況下，才認可最終結果有效。PBFT算法針對分布式系統并且按照系統中的指令順序執行，其基于C/S架構。一致性協議的整個過程分為三個階段，具有三次信息的廣播，因此網絡的帶寬一定會有浪費，尤其是后兩次的全節點廣播，非常消耗網絡帶寬，在區塊鏈系統中，若請求消息過于頻繁很容易造成網絡擁堵。在傳統PBFT算法中完成一次三階段共識過程共需要傳遞的消息次數M為：

M=2N2-2N

(1)

由式(1)可知，消息傳遞的次數隨著集群中節點數目增大急劇增多。

客戶端只可以向主節點發送信息，如果請求消息太多容易造成主節點負載過大，效率將大大降低。主節點的選取不具有安全性，假如連續選取的主節點都是惡意節點，將會導致系統資源的極大浪費并且降低系統安全性；在視圖轉換協議中PBFT算法存在被拒絕服務惡意攻擊的可能，當發生客戶端重復請求的惡意情況時，會使得視圖不停地進行視圖轉換，影響正常的服務或者系統陷入宕機。如果主節點作惡，它可能會不去分配序號，為不同的請求編上相同的序號，或者產生本該相鄰的序號不連續等情況影響系統的安全性。

2 IPBFT算法設計

2.1 協議常量定義

與傳統拜占庭算法類似，改進的拜占庭算法IPBFT模型中視圖view由編號v唯一標記某個視圖，視圖中的節點會被稱為主節點或是領導節點(Primary)，其余的節點都叫副本節點或是從節點(Backups)。

R是所有節點的集合，用一個整數來表示每一個節點，依次用{0，1，…，i，…，|R|-1}表示，集合R必須滿足：

|R|=3f+1

(2)

式中：f是系統中可容忍的錯誤節點最大值。一個視圖中的主節點為pi，主節點可表示為:

pi=vmod|R|

(3)

從0開始一直連續下去，當每次視圖轉換協議View Change發生時依次從主節點p0到主節點p|R|-1，來自客戶端c的請求由主節點pi排序并根據序號發送給副本節點。

IPBFT算法結構一共分為三種：客戶端、協商副本和執行副本。協商集群是協商副本的集合，執行集群是執行副本的集合。客戶端的作用相當于轉換端，可以與協商副本、執行副本同時進行交互，其中協商副本為傳遞來的請求分配序號，執行副本通過協商副本發來的指定序號執行請求，并且將結果返回客戶端。

IPBFT算法由一致性協議、視圖轉換協議以及檢查點協議三個子協議組成，其中：一致性協議組織各個群組執行請求；視圖轉換協議在當前的局部主節點發生錯誤時協調新的局部主節點；檢查點協議能夠減少視圖轉換協議執行的成本。

Lamport在1977年第一次描述了安全性(Security)與活性(Liveness)的概念，但目前傳統拜占庭算法的安全性指整個系統在一定時間內所有已經完成的請求都不可能再被更改,但是它可以被后來的請求查詢到，活性指的是系統可以執行非拜占庭客戶端的請求，不會被任何因素影響而導致非拜占庭客戶端[12]。

本文中安全性是指系統能夠始終保持一致性并對任務進行長時間的原子操作，如果只依靠安全性并不能徹底解決拜占庭節點造成的損害，因為拜占庭節點沒有限制的攻擊會對任務本身造成影響，比如某個任務是在計算后對文件進行寫入，而拜占庭節點通過向文件寫入無意義的內容可能會導致任務失敗。面對這種特殊情況，IBPFT算法把讀寫等敏感操作的權限交給節點完成，大大降低了風險。本文的活性指的是任務在一定的拜占庭節點數目的前提下，必會在規定時間內得出相同的一致性結果，即IPBFT算法會在有限時間內返回一個有效值。本協議對每個副本節點提出了兩個限定條件：

(1) 非拜占庭服務器輸入相同的信息，產生的結果一致。

(2) 當輸入的信息正確，非拜占庭服務器接受信息并計算相應的結果。

2.2 算法流程

2.2.1一致性協議

(1) 主節點向客戶端發送請求。客戶端c請求系統執行操作o，客戶端c向協商集群的每個副本節點廣播請求消息〈REQUEST,o,t,c〉σc。在該消息中，o表示操作;t表示本地時間戳，可以保證該消息的時效性，時間戳是全序排列的，因為客戶端發出的請求只有一次，后續比早先發出的請求時間戳序號更高;c為客戶端。此時客戶端設置2個計時器Timer1和Timer2并開始計時，Timer1用于收集執行副本j自證消息的返回時間，Timer2用于收集操作結果的返回時間。

(2) 主節點收到請求后向客戶端發送自證消息。主節點p接收到請求消息〈REQUEST,o,t,c〉σc后，啟動三階段協商：包括FAST-PRE-PREPARE、FAST-PREPARE以及FAST-CONFIRM三階段，并將其廣播到剩余副本節點，執行副本j向客戶端發送自證消息〈PRE-REPLY,v,t,n,j,r〉σj證明自己不是拜占庭節點，v是視圖編號，n是消息序號，j是副本自身編號，r是請求執行后得到的結果response。

如果客戶端c在Timer1范圍內收到自證消息PRE-REPLY，客戶端c將對收到的f+1個響應進行驗證，首先驗證消息簽名、時間戳t和執行結果r是否一致，如果相同，r就被視為客戶端的正確執行結果，失效的副本節點不超過f個，因此f+1個副本節點的一致響應保證結果是正確的。

如果客戶端c沒有在Timer1范圍內收到自證消息，請求將向所有執行副本進行廣播，如果該請求執行副本已經處理過，就向客戶端重發一遍執行結果r。如果沒有處理過，就把請求轉發給主節點p要求重新發送請求。

(3) 快預準備階段FAST-PRE-PREPARE。在快預準備階段，主節點p分配一個序列號n給收到的請求REQUEST，然后協商副本k向執行副本j發送預準備消息，消息的格式為〈〈FAST-CONSULT,v,n,d,j,var〉σj,m〉，d是請求消息m的摘要，var是操作o的參數集，快預準備消息的序號n必須在水位(Watermark)上下限h和H之間，水位用于防止一個失效節點占用很大序號消耗空間資源，m是客戶端發送的請求消息。該信息送達到各執行副本j后，首先驗證m是否為一個完整的請求信息，n是否在水位之間，d是否為m的正確摘要，最大的n序列號是否增加1，v的序列號與自己所在的視圖view編號是否一致，如果上述條件都滿足，則表示執行副本接受了主節點p分配給該請求的這個編號n并將其加入日志中，它就會進入下面的FAST-PREPARE階段。

(4) 快準備階段FAST-PREPARE。在完成上述操作o后得到結果r，協商副本k開始向各執行副本j發送請求消息，內容為〈〈PREPARE,v,n,d,r〉σj,m〉。首先進行快協商階段中的驗證操作，在準備階段，完成的標志為執行副本j將消息(m,v,n)記入其消息日志REQUEST-LOG，快協商消息m在視圖v中的編號n，以及2f個從不同執行副本j收到的與快協商消息一致的準備消息。

只有在時間戳t大于tc的時候執行副本j才會接受請求并將請求加入到日志REQUEST-LOG中，tc為主節點p之前所接受過的最大時間戳。如果執行副本j在時間上限內未接收到請求消息，將向主節點p發送探測消息〈SEARCH-MES,v〉σj。如果主節點p回復探測消息，將再次激活計時器重新計時；否則觸發視圖轉換協議。

(5) 快確認階段FAST-CONFIRM 。當協商副本k發現有2f+1個執行副本同意編號分配時，協商副本就會廣播出去一條確認信息〈〈FAST-CONFIRM,v,n,d,j,r〉σj,m〉到執行副本j，告知其產生了證書Prepared Certificate，執行副本j收到FAST-CONFIRM信息的節點達到2f條后進行驗證，驗證r是否與自己所得結果相同，m是否是一個完整的請求消息，d是否是m的正確摘要，v是否與自己保存的視圖號相同。如果上述條件滿足，則將該請求加入日志，該節點擁有確認證書Confirmed Certificate，表明執行副本j同意了編號n的分配，該請求就會被節點執行，接著廣播發送〈REPLY,v,c,t,j,r〉σj到客戶端c，如果不滿足則拒絕，當執行副本j連續拒絕協商副本k兩次時，啟用視圖轉換協議。

(6) 主節點向客戶端返回操作結果。正常情況下，如果客戶端c接收到回復消息〈REPLY,v,t,c,r〉σj中f+1個結果是一致的，則表明結果r是正確的。

2.2.2主節點選舉

主節點選舉依據的是心跳檢測機制和最長鏈原則，副本節點定期會向主節點發送一次Ping命令做一次心跳檢測，規定在時間Down-After-Milliseconds內Ping連接成功，且在該集群中最后一個共識完成的擁有最大視圖號且編號最大的節點作為主節點，視圖號v與編號i存儲的類型為long，視圖v占據高32 位，編號i占據低32位，用vi表示選舉過程：

系統初始化后，各節點都處于搜尋狀態，并給自己投票，服務器收到所有其他節點投票后進行票選，更新自己的票數并廣播出去，將其他節點廣播來的選票信息存入選票日志中。票選可能產生以下有三種情況，分別是：(1) 收到的選票中最大vi小于自己當前的vi，忽略該選票。(2) 收到的選票中最大vi與當前vi相同，節點編號也一致，將選票信息存入選票日志中。如果編號不一致，則比較節點編號，如果當前節點編號較高，則忽略消息；否則清除選票日志，更新自己的票選信息并廣播出去。(3) 收到的選票最大vi大于當前的vi，則直接清空選票日志并更新當前的vi，將自己的選票信息廣播出去。

當選票日志中有不同節點的2f+1個目標相同的選票時，系統自動清除日志，向新的主節點發送確認信息。當主節點收到至少2f+1個來自不同節點的確認消息的節點成為準主節點進入待定狀態。在選舉完成后，副本節點要驗證準主節點的合法性，發送驗證請求消息〈SYN-ACK,v,vi,d,j〉σj，準主節點接收到消息后進行驗證操作，首先檢查視圖號是否一致，對比區塊編號尾部是否與vi一致，若一致則發送同步成功消息〈SYN-SYCCESS,v,d,j〉σj給該節點；否則將其丟棄，同時將來自其他節點的消息記錄到日志中。當副本節點收到不同節點的2f+1個成功消息且消息中各項數據匹配后，驗證成功，這樣可以保證準主節點發送給每個副本節點的備份數據區塊都是一致的，表示有足夠的備份節點同意自己，這時準主節點正式成為主節點。

在票選的同時，副本節點會定期檢測已經成為主節點的節點是否發生了故障，副本節點采用心跳檢測機制，會在Down-After-Milliseconds時間內向主節點發送心跳Ping命令確認主節點是否存活，如果主節點在期間內不回應或者回復了一個錯誤的消息，那么這個副本節點會主觀地認為這個主節點已經不可用，會要求其他副本節點確認該主節點是否丟失，如果超過2f+1個副本節點確認，則認為該主節點失效下線，重新進入選票階段進行選舉。

2.3 檢查點協議

為了節省內存和系統安全性，系統需要刪除日志中的無異議消息，而在執行副本刪除消息日志前，必須保證至少有f+1個正確消息對應的請求，并且可以在視圖變更時證明。如果執行副本錯失部分請求消息而且這些消息已經被刪除，要想實現同步就必須通過回滾部分甚至全部服務狀態。

但是每一步都需要證明是十分損耗資源的，因此，證明過程只有在請求序號被檢查點間隔Checkpoint_Interval整除的時候才會周期性地進行，例如：在傳統的PBFT和zyzzyv等算法中，副本節點會收集2f+1個檢查點消息作為證據，由于收集證據的計算成本太高，所以會在執行假設Checkpoint_Interval為100次的請求后進行證據計算，可以將這些請求執行后得到的狀態稱作檢查點Checkpoint。

在本協議中，一旦執行副本j執行了主節點p發出的對n號請求的簽名，它就會將自己的n號請求運算結果刪除，主節點p在客戶端收到了回復消息后也會將自己的n號請求運算結果刪除。此外，如果執行副本j丟失了部分消息，也需要通過發送全部或部分服務狀態來為其更新狀態，這些狀態由檢查點提供，默認情況下，檢查點創建間隔Checkpoint_Interval為200。

當協商副本k發現Checkpoint_Interval取余恒等于0時，觸發檢查點創建協議，按照如下步驟執行：協商副本k廣播檢查點消息：

〈〈CHECKPOINT,n′,d,j〉σj,〈SIGNATURE,v,n〉〉這里n′是上一個影響狀態的請求序號，n為當前任務的序列號。執行副本j在各自的日志中收集并記錄檢查點消息，并且驗證消息有效性，驗證通過，添加到證書；否則，直接丟棄該消息。收到的來自2f+1個具有相同序號n和摘要d的消息組合成檢查點的正確性證明，這些具有證明能力的檢查點就是穩定檢查點。之后開始狀態回收，例如從日志中刪除所有序號小于或等于n的快預準備、快準備和快確認消息，以及之前的檢查點和檢查點消息。檢查點協議主要用于視圖轉換時為選取主節點提供依據，并且保持節點日志中的數據有序、有界。

2.4 視圖轉換協議

傳統PBFT算法中的視圖轉換協議可能存在被拒絕服務的惡意攻擊的問題，IPBFT算法針對這個問題對視圖轉換協議進行了改進，增加了驗證機制，保證服務不會頻繁地惡意啟動視圖變更算法。View Change確保系統在主節點錯誤的狀態下仍然具有活性。當副本節點等待時間超過預設值時或協商副本被連續拒絕時，視圖轉換協議將啟動以避免系統陷入死循環等待狀態。發送請求的副本節點j在發送VIEW-CHANGE消息前，需要確認至少f+1個正確的副本向主節點發送過消息m，當副本節點j懷疑主節點發生了錯誤后，并不是馬上向其他副本節點發送VIEW-CHANGE消息，而是先發送預準備消息〈PRE-VIEWCHANGE,v,d,j〉σj，當收到大于2f+1條相同的PRE-VIEWCHANGE消息后，這時正確的執行副本中向主節點p發送過消息m的最少有f+1個，接著發送視圖轉換請求消息VIEW-CHANGE。

IPBFT采用的視圖轉換協議能夠處理作惡節點有選擇的發送特定虛假信息造成主節點不斷進行View Change并消耗資源的問題，下面詳細介紹視圖轉換協議協議。

Step2執行副本j在有效時間內發送消息〈VIEW-CHANGE,v+1,n′,d,P,Q,j〉σj后，進入視圖v+1，啟動計時器，停止接收來自于前一個視圖v的消息，在計時器超時前，執行副本j如果沒有收到來自新的主節點pnew的NEW-VIEW消息，執行副本j將計時器重置，并進入視圖v+2，重新進入Step1執行，直到在計時器時間內執行副本j收到新的主節點pnew發送的NEW-VIEW消息。

Step3進入視圖v+2后，新的執行副本jnew收到消息〈VIEW-CHANGE,v+1,n′,d,P,Q〉σjnew，發送消息視圖變換確認消息VIEW-CHANGE-ACK消息〈VIEW-CHANGE-ACK,v+1,j,jnew,d〉μjnew給新的主節點pnew。

Step4在新的主節點pnew收到2f+1條VIEW-CHANGE消息和至少2f-1條VIEW-CHANGE-ACK消息后，向所有的副本節點廣播NEW-VIEW消息〈NEW-VIEW,v+1,Y,X〉σjnew，其中Y是由〈j，d〉組成的集合，X是主節點pnew的所有檢查點的摘要和處于PREPARE狀態的消息組成的集合。

Step5當新的副本節點jnew收到〈NEW-VIEW,v+1,Y,X〉σpnew后，對消息中的每個元素進行驗證，驗證NEW-VIEW與上一個視圖的消息是否對應，視圖編號v是否加1，Y集合是否一致，X中的檢查點摘要和PREPARE消息組成的集合是否一致。若上述元素都正確，說明確認該消息來自于主節點pnew，然后進行Reply操作，執行節點回滾到Reply起始位置，協商節點重新協商Reply請求，pnew負責發送預準備PRE-PREPARE消息，而非主節點負責發送準備PREPARE消息，開始新的三階段協議過程。

視圖轉換協議完成后，系統處于新的一致狀態，并開始新的客戶端請求處理。

3 實驗分析

3.1 系統結構圖

為了測試該改進算法的實用性和有效性，圖2是改進算法的區塊鏈系統結構圖。該結構底層為區塊鏈協議層，數據采用的是鏈式數據結構，網絡結構為P2P，加密使用橢圓曲線非對稱加密算法，整個系統是去中心化的。整個系統分為三個層面：協議層、擴展層和應用層，其中協議層又可以分為共識層和存儲層。

圖2 系統結構圖

應用層是客戶可以直接接觸的產品，本算法從協議層開始，把最終的目的指向應用層。擴展層類似于驅動程序，這個層面可以讓區塊鏈更為實用，智能合約就是典型的擴展層面的應用開發，這是區塊鏈技術重要的發展方向，擴展層使用的技術有分布式存儲、機器學習、物聯網、大數據等，因為可以與協議層完全分離，所以可以選擇更加自由的編程語言，具有很高的擴展性。協議層是整個區塊鏈系統最底層的技術，這個層級維護網絡節點，僅提供API供調用，協議層主要包括共識算法、網絡編程、加密簽名和數據存儲技術等4個方面，共識層收到傳遞來的交易后，產生區塊進行共識過程，是整個區塊鏈系統的關鍵步驟。

共識采用的是IPBFT 算法，共識模塊又分為一執行協議、主節點選舉、檢查點協議和視圖轉換等4個子模塊。存儲層負責將已經達成共識的區塊存儲起來，數據信息的同步驗證過程保證了各個節點在視圖變換協議啟動后，能夠存儲當前完整的區塊鏈數據。存儲的數據信息能被查詢，但不能被修改。

3.2 性能測試

本文提出的IPBFT算法，在能耗、吞吐量和容錯性等方面也得到了進一步的改善，現通過基于IPBFT算法構建的區塊鏈系統對這三個方面進行測試，并與傳統的PBFT 算法和小蟻鏈中的dBFT算法進行比較，以此來驗證算法的實用性和有效性。

此次仿區塊鏈分布式系統的實驗網絡環境采用的是實驗室的通信局域網，實驗室中有5臺配置為I7-7900X處理器、DDR4 16×2 GB內存、256 GB SSD固態硬盤和操作系統為Windows10的服務器，通過Docker容器每臺服務器上設置40個虛擬IP地址模擬區塊鏈環境，與傳統虛擬機相比，Docker容器更輕便，運行速度更快，實驗通過MATLAB R2016a對IPBFT算法、PBFT算法和dBFT算法的運行結果進行數學計算仿真。

3.2.1功耗性能

在區塊鏈網絡中，IPBFT、PBFT和dBFT三種算法都需要進行數據的傳輸和損耗，這些算法所使用的網絡帶寬可以表示為：

Bandwidth=N×(N-1)×Blocksize

(4)

式中:Bandwidth為所需要使用的網絡帶寬，N為網絡中的節點數目，Blocksize是傳輸的數據大小，在區塊鏈系統中，一個區塊的大小約為1 MB。從式(4)中能夠看出，在Blocksize固定不變時，三種算法的網絡帶寬都會隨著N的增加而增加。IPBFT、PBFT和dBFT算法所使用的網絡帶寬如圖3所示。

圖3 IPBFT、PBFT算法以及dBFT算法的帶寬消耗比較

從圖3可以看出，在同一個網絡環境下、節點數目都相同、傳輸的數據信息都一樣的情況下，IPBFT算法的網絡帶寬消耗總體明顯低于PBFT算法和dBFT算法，因此IPBFT算法具有更低的功耗。

3.2.2吞吐量

吞吐量的大小表示的是系統的負載承受能力，吞吐量的定義為單位時間內系統處理的事物總量，請求交易或者是處理事務的能力。在區塊鏈系統中，通常使用每秒成功的交易數量TPS(Transaction PerSecond)來表示：

TPS=TransactionsΔt/Δt

(5)

式中:Δt為出塊時間，其中TransactionΔt為出塊單位時間內系統處理的交易總量，隨著每個區塊的節點數目N增大，吞吐量也會變大，但同時共識的處理時間會延長，網絡負載的能力也會變大，所以當節點數目多到一定程度時吞吐總量會逐漸下降。

三種算法在相同條件下吞吐量對比如圖4所示。可以看出，隨著節點數量的增加，三種算法的吞吐量增長都趨近平穩，但是IPBFT算法的吞吐量明顯高于其他兩種算法，并且隨著交易量的加大，吞吐量將會提升得更加明顯。

圖4 IPBFT、PBFT算法以及dBFT算法的吞吐量比較

3.2.3時延性

共識算法的延時性是區塊鏈運行速度的重要指標，低延時可以使得交易得到快速的確認，節省時間。在相同的網絡環境下，三種算法都有延時逐漸遞增的趨勢，但起伏很小，傳統的PBFT算法的延時最大。從圖5中能看出IPBFT算法的延時性比dBFT算法略低，很明顯比傳統的PBFT算法低很多。在實驗中還發現節點數目越多，表現出的延時性越小。因此可以得出結論，在這三種算法的延時比較中，時延性PBFT>dBFT>IPBFT，結果說明IPBFT共識算法在網絡通信上具有更低的延時性。

圖5 IPBFT和PBFT以及dPBFT算法時延性的比較

4 結 語

本文首先介紹了拜占庭問題和一些傳統的共識算法，如POW、POS、Paxos、Raft和Algorand等，并分析了這些算法存在的問題和不足。針對這些不足，在傳統PBFT的基礎上提出了優化改進的共識算法IPBFT，將協商與執行節點分離，對于執行時間較長的請求，減少執行請求的服務器數量可以較大程度地提升系統吞吐率。將主節點的選舉方式改為心跳檢測機制和最長鏈選舉方式，進一步提高了主節點選舉的安全性和實用性。在三階段協商中加入了自證機制，進一步減少了作惡幾率，提高了系統的穩定性。通過實驗分析，IPBFT算法在通信消耗、吞吐率和延時性都有很大的提升，具有一定的可靠性。但IPBFT算法還存在一些問題，未來的工作重點將會在容錯性和進一步優化算法細節以及降低網絡通信量上，并將算法用于某一領域的實際區塊鏈項目中，提高算法的實用性。