一種區(qū)塊鏈實(shí)用拜占庭容錯算法的改進(jìn)

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

(南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 南京 211816)

0 引 言

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

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

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

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

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

1 相關(guān)工作

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

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

1.1.1工作量證明

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

1.1.2權(quán)益證明

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

1.1.3Raft算法

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

1.1.4Algoand算法

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

1.2 PBFT算法

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

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

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

M=2N2-2N

(1)

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

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

2 IPBFT算法設(shè)計(jì)

2.1 協(xié)議常量定義

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

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

|R|=3f+1

(2)

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

pi=vmod|R|

(3)

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

IPBFT算法結(jié)構(gòu)一共分為三種：客戶端、協(xié)商副本和執(zhí)行副本。協(xié)商集群是協(xié)商副本的集合，執(zhí)行集群是執(zhí)行副本的集合。客戶端的作用相當(dāng)于轉(zhuǎn)換端，可以與協(xié)商副本、執(zhí)行副本同時進(jìn)行交互，其中協(xié)商副本為傳遞來的請求分配序號，執(zhí)行副本通過協(xié)商副本發(fā)來的指定序號執(zhí)行請求，并且將結(jié)果返回客戶端。

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

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

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

(1) 非拜占庭服務(wù)器輸入相同的信息，產(chǎn)生的結(jié)果一致。

(2) 當(dāng)輸入的信息正確，非拜占庭服務(wù)器接受信息并計(jì)算相應(yīng)的結(jié)果。

2.2 算法流程

2.2.1一致性協(xié)議

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

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

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

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

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

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

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

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

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

2.2.2主節(jié)點(diǎn)選舉

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

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

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

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

2.3 檢查點(diǎn)協(xié)議

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

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

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

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

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

2.4 視圖轉(zhuǎn)換協(xié)議

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

3.1 系統(tǒng)結(jié)構(gòu)圖

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

圖2 系統(tǒng)結(jié)構(gòu)圖

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

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

3.2 性能測試

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

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

3.2.1功耗性能

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

Bandwidth=N×(N-1)×Blocksize

(4)

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

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

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

3.2.2吞吐量

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

TPS=TransactionsΔt/Δt

(5)

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

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

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

3.2.3時延性

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

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

4 結(jié) 語

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