韓鎮(zhèn)陽 宮寧生 任珈民

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

0 引 言

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

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

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

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

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

1 相關工作

1.1 傳統(tǒng)共識算法

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

1.1.1工作量證明

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

1.1.2權益證明

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

1.1.3Raft算法

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

1.1.4Algoand算法

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

1.2 PBFT算法

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

圖1 PBFT一致性協(xié)議算法流程圖

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

M=2N2-2N

(1)

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

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

2 IPBFT算法設計

2.1 協(xié)議常量定義

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

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

|R|=3f+1

(2)

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

pi=vmod|R|

(3)

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

IPBFT算法結構一共分為三種：客戶端、協(xié)商副本和執(zhí)行副本。協(xié)商集群是協(xié)商副本的集合，執(zhí)行集群是執(zhí)行副本的集合?？蛻舳说淖饔孟喈斢谵D換端，可以與協(xié)商副本、執(zhí)行副本同時進行交互，其中協(xié)商副本為傳遞來的請求分配序號，執(zhí)行副本通過協(xié)商副本發(fā)來的指定序號執(zhí)行請求，并且將結果返回客戶端。

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

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

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

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

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

2.2 算法流程

2.2.1一致性協(xié)議

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

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

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

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

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

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

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

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

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

2.2.2主節(jié)點選舉

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

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

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

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

2.3 檢查點協(xié)議

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

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

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

當協(xié)商副本k發(fā)現(xiàn)Checkpoint_Interval取余恒等于0時，觸發(fā)檢查點創(chuàng)建協(xié)議，按照如下步驟執(zhí)行：協(xié)商副本k廣播檢查點消息：

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

2.4 視圖轉換協(xié)議

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

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

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

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

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

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

視圖轉換協(xié)議完成后，系統(tǒng)處于新的一致狀態(tài)，并開始新的客戶端請求處理。

3 實驗分析

3.1 系統(tǒng)結構圖

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

圖2 系統(tǒng)結構圖

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

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

3.2 性能測試

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

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

3.2.1功耗性能

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

Bandwidth=N×(N-1)×Blocksize

(4)

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

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

從圖3可以看出，在同一個網(wǎng)絡環(huán)境下、節(jié)點數(shù)目都相同、傳輸?shù)臄?shù)據(jù)信息都一樣的情況下，IPBFT算法的網(wǎng)絡帶寬消耗總體明顯低于PBFT算法和dBFT算法，因此IPBFT算法具有更低的功耗。

3.2.2吞吐量

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

TPS=TransactionsΔt/Δt

(5)

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

三種算法在相同條件下吞吐量對比如圖4所示?？梢钥闯?，隨著節(jié)點數(shù)量的增加，三種算法的吞吐量增長都趨近平穩(wěn)，但是IPBFT算法的吞吐量明顯高于其他兩種算法，并且隨著交易量的加大，吞吐量將會提升得更加明顯。

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

3.2.3時延性

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

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

4 結 語

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