區(qū)塊鏈實用拜占庭容錯共識算法的改進(jìn)

甘俊 李強(qiáng) 陳子豪 張超

摘 要：針對應(yīng)用于聯(lián)盟鏈的實用拜占庭容錯（PBFT）共識算法網(wǎng)絡(luò)結(jié)構(gòu)靜態(tài)、主節(jié)點選取隨意和通信開銷較大的問題，提出了一種改進(jìn)的實用拜占庭容錯（EPBFT）共識算法。首先，給共識節(jié)點設(shè)置一系列活動狀態(tài)使得節(jié)點通過狀態(tài)轉(zhuǎn)換在系統(tǒng)中擁有完整生命周期，由此節(jié)點可以動態(tài)地加入和退出，系統(tǒng)擁有動態(tài)的網(wǎng)絡(luò)結(jié)構(gòu)。其次，對PBFT的主節(jié)點選取方式加以改進(jìn)，增加以最長鏈為選舉原則的主節(jié)點選舉過程。在主節(jié)點選舉完成之后，通過數(shù)據(jù)同步和主節(jié)點驗證過程進(jìn)一步保證主節(jié)點的可信性。最后，優(yōu)化PBFT算法的共識流程以提高共識效率，使得EPBFT算法的通信開銷在視圖變更較少發(fā)生的情況下降低為PBFT算法的1/2。實驗結(jié)果表明，EPBFT算法具有較好的有效性和實用性。

關(guān)鍵詞：實用拜占庭容錯;聯(lián)盟鏈;主節(jié)點;選舉

Abstract： Since Practical Byzantine Fault Tolerance （PBFT） consensus algorithm applied to the alliance chain has the problems of static network structure， random selection of master node and large communication overhead， an Evolution of Practical Byzantine Fault Tolerance （EPBFT） consensus algorithm was proposed. Firstly， a series of activity states were set for consensus nodes， making the nodes have complete life cycle in the system through state transition， so that the nodes were able to dynamically join and exit while the system has a dynamic network structure. Secondly， the selection method of master node of PBFT was improved with adding the election process of master node with the longest chain as the election principle. After the election of master node， the reliability of master node was further ensured through data synchronization and master node verification process. Finally， the consensus process of PBFT algorithm was optimized to improve the consensus efficiency， thus the communication overhead of EPBFT algorithm was reduced to 1/2 of that of PBFT algorithm with little view changes. The experimental results show that EPBFT algorithm has good effectiveness and practicability.

Key words： Practical Byzantine Fault Tolerance （PBFT）; alliance chain; master node; election

0 引言

區(qū)塊鏈?zhǔn)且环N新型的去中心化協(xié)議，它通過將數(shù)字加密[1]、共識算法、分布式存儲、時間戳[2]等技術(shù)結(jié)合構(gòu)建去中心化的分布式系統(tǒng)，其中共識算法的作用是為了解決拜占庭將軍[3]問題。拜占庭將軍問題抽象于現(xiàn)實世界，在點對點（Peer to Peer， P2P）網(wǎng)絡(luò)[4]中，可能出現(xiàn)硬件故障、網(wǎng)絡(luò)擁堵甚至惡意攻擊等不可預(yù)知的問題。另外系統(tǒng)在任意時刻可能存在多個提案，因為提案的成本很低。共識算法除了要處理這些失效之外，還要完成提案的最終一致性，在區(qū)塊鏈中有著非常重要的作用。

關(guān)于共識算法的研究很早便已經(jīng)開始，最早由Pease等[5]和Lamport等[6]在20世紀(jì)80年代通過拜占庭將軍問題進(jìn)行描述和分析，提出了著名的拜占庭容錯（Byzantine Fault Tolerance， BFT）算法。不同于比特幣系統(tǒng)“挖礦”的工作量證明（Proof of Work， PoW）[7]系列共識算法（達(dá)成共識的概率上的最終一致），BFT類協(xié)議依靠節(jié)點之間相互傳遞消息對提案達(dá)成確定性共識結(jié)果;然而也是由于這些特性造成節(jié)點間需要兩兩之間遞歸傳遞指數(shù)級復(fù)雜度的消息，不太具有可實際操作性，而且節(jié)點的加入和退出過程需要進(jìn)行特別處理。這些研究起初常被人們忽視。直到區(qū)塊鏈技術(shù)和比特幣的出現(xiàn)，BFT算法重新引起關(guān)注，因為這一算法雖然存在很多缺點，但它為解決拜占庭問題提供了一種不同于PoW那樣的需要耗費巨大算力新思路，為以后的實用拜占庭容錯（Practical Byzantine Fault Tolerance， PBFT）算法的出現(xiàn)作出了準(zhǔn)備。

在1999年，Castro等[8]提出了實用拜占庭容錯（Practical Byzantine Fault Tolerance， PBFT）共識算法，改進(jìn)于BFT算法，繼承了它的優(yōu)點，同時將算法復(fù)雜度由指數(shù)級降為多項式級。由此實用拜占庭容錯算法在實際系統(tǒng)應(yīng)用中變得可行。PBFT算法是基于狀態(tài)機(jī)副本復(fù)制的算法，每個狀態(tài)機(jī)副本保存服務(wù)狀態(tài)，實現(xiàn)客戶合法請求，除了交易之外，還可以完成其他類型的操作，應(yīng)用范圍廣泛。在系統(tǒng)中存在（n-1）/3的數(shù)量的錯誤節(jié)點的情況下，仍可保證系統(tǒng)安全性和活性，正確地達(dá)成分布式共識。

然而現(xiàn)有的PBFT算法還存在一些不足。首先，其網(wǎng)絡(luò)結(jié)構(gòu)是靜態(tài)類型，如果動態(tài)增加節(jié)點，必須重啟應(yīng)用，造成不必要的損失，影響系統(tǒng)可用性，尤其在某些行業(yè)，經(jīng)常性的重啟系統(tǒng)是不能忍受的。PBFT算法中主節(jié)點的選舉方式是按編號依次輪流作主節(jié)點，這種主節(jié)點的選舉方式較為隨意，在選舉成功主節(jié)點后也沒有對主節(jié)點的真?zhèn)涡赃M(jìn)行驗證，使得選舉出來的主節(jié)點很有可能是惡意節(jié)點，具有一定的安全隱患，盡管在后續(xù)的共識過程中主節(jié)點的惡意性有可能被從屬節(jié)點識破并通過視圖變更將其推翻，但是仍然會造成一定的損失，頻繁的視圖變更也會增加系統(tǒng)開銷，降低系統(tǒng)效率。三階段廣播過程，需要比較大的網(wǎng)絡(luò)傳輸和通信開銷，要進(jìn)一步優(yōu)化。在主節(jié)點選舉成功后也沒有完善的數(shù)據(jù)同步過程，在每一個視圖變更后，集群中的節(jié)點可能出現(xiàn)保存的副本數(shù)據(jù)有多有少的情況，因為由于網(wǎng)絡(luò)等原因會導(dǎo)致各個節(jié)點的進(jìn)度不一致，從而導(dǎo)致狀態(tài)不一致[9]，所謂狀態(tài)一致，即是指交易編號、區(qū)塊高度、視圖號等信息都保持一致，所以在新的主節(jié)點選舉出來以后，需要進(jìn)行集群中節(jié)點的數(shù)據(jù)同步。

本文針對現(xiàn)有的PBFT算法網(wǎng)絡(luò)結(jié)構(gòu)類型靜態(tài)、主節(jié)點選舉方式隨意、不能保證主節(jié)點可信性、網(wǎng)絡(luò)開銷比較大、缺少完善的數(shù)據(jù)同步過程等問題，提出一種改進(jìn)實用拜占庭容錯（Evolution of Practical Byzantine Fault Tolerance， EPBFT）共識算法模型。參考原子消息廣播算法ZAB（ZooKeeper Atomic Broadcast）[10]，針對PBFT算法特點，將集群中的節(jié)點分為領(lǐng)導(dǎo)者與跟隨者兩種角色，依情況使節(jié)點處于不同的狀態(tài)，同時依據(jù)節(jié)點狀態(tài)的不同決定節(jié)點是否能夠進(jìn)行共識過程，從而使得集群中可以動態(tài)加入和退出節(jié)點;設(shè)計一種新的選舉方式，在原有的PBFT算法基礎(chǔ)上改變主節(jié)點的選舉方式，不再按照編號選擇主節(jié)點，而是選舉出擁有處理過最大視圖號以及最大編號的請求的節(jié)點作為主節(jié)點，在數(shù)據(jù)同步階段，可以方便進(jìn)行數(shù)據(jù)同步;在主節(jié)點選舉完成之后增加一個數(shù)據(jù)同步及驗證階段，在進(jìn)行數(shù)據(jù)同步的同時對所同步的數(shù)據(jù)進(jìn)行驗證，若驗證的數(shù)據(jù)通過，則可以確定新的主節(jié)點為可信節(jié)點，正式承認(rèn)選舉出的新的主節(jié)點，開始新一輪的共識過程。確認(rèn)階段是對準(zhǔn)備階段的再確認(rèn)，防止視圖變更發(fā)生于準(zhǔn)備階段后產(chǎn)生的不一致。在聯(lián)盟鏈的環(huán)境中，節(jié)點有監(jiān)督，網(wǎng)絡(luò)較穩(wěn)定，視圖變更情況并不會頻繁發(fā)生，且在視圖變更后增加了數(shù)據(jù)同步及驗證過程，保證了狀態(tài)一致性，所以可以省略三階段中的最后的確認(rèn)階段。本文貢獻(xiàn)如下：

1）改進(jìn)PBFT算法中主節(jié)點選舉方式，改原來的依據(jù)節(jié)點編號選舉為擁有處理過最大視圖號以及最大編號的請求的節(jié)點選舉，也就是最長鏈選舉。使得主節(jié)點的選舉方式更加合理，選舉出的主節(jié)點更加可信。

2）增加數(shù)據(jù)同步及驗證階段，在主節(jié)點選舉完成之后增加數(shù)據(jù)同步及驗證階段，進(jìn)一步驗證新主節(jié)點的可信性，在完成數(shù)據(jù)同步的同時完成對新選舉出的主節(jié)點的真?zhèn)涡赃M(jìn)行驗證，若新的主節(jié)點可信，則開始新一輪的共識;反之，重新進(jìn)行選舉過程。

3）在前兩點基礎(chǔ)上省去原來的PBFT算法中的確認(rèn)階段，由此可以減少網(wǎng)絡(luò)和時間開銷，使算法更加高效。

4）改進(jìn)原PBFT靜態(tài)結(jié)構(gòu)為動態(tài)結(jié)構(gòu)，設(shè)計一套節(jié)點加入和退出集群以及工作的完整周期，通過給節(jié)點賦予領(lǐng)導(dǎo)者與跟隨者兩種角色，以及不同狀態(tài)，使得集群中節(jié)點可以動態(tài)地加入和退出，無需重啟整個集群，提升整個集群的穩(wěn)定性和可用性。

5）實現(xiàn)本文所寫的改進(jìn)的算法模型，并通過實驗驗證，新的改進(jìn)的PBFT算法模型在保證數(shù)據(jù)可信性和安全性的前提下，有效地降低了共識需要花費的時延，提高了交易吞吐量。

1 相關(guān)工作

拜占庭容錯算法的研究很早就已開始，但近年隨著區(qū)塊鏈技術(shù)的落地才在計算機(jī)領(lǐng)域流行起來。特別是由于PBFT的提出使得拜占庭容錯算法擁有較高的效率和安全性，得以應(yīng)用于實際系統(tǒng)中實現(xiàn)，針對PBFT算法的改進(jìn)研究明顯增多。對已有的BFT類共識進(jìn)行研究，按照改進(jìn)思路的不同分類，主要可以歸納為3大類方向[11-12]：1）針對非拜占庭錯誤場景優(yōu)化;2）針對拜占庭錯誤場景優(yōu)化;3）為公鏈應(yīng)用優(yōu)化。

首先是針對假設(shè)系統(tǒng)無拜占庭節(jié)點的場景進(jìn)行優(yōu)化，即假設(shè)系統(tǒng)中基本不存在惡意節(jié)點，允許節(jié)點存在宕機(jī)行為，在這種情況下對BFT算法進(jìn)行簡化或優(yōu)化。最出名便是以Paxos[13]、Raft[14]為代表的傳統(tǒng)分布式一致性算法。Raft算法由Paxos算法簡化而來，經(jīng)過改進(jìn)簡化Raft算法易于實現(xiàn)。HQ（Hybrid Quorum）協(xié)議[15]參考并優(yōu)化了PBFT協(xié)議，針對無競爭的情況簡化通信。如果有競爭，性能也退化為和PBFT類似。應(yīng)用于ZooKeeper中的ZAB算法改進(jìn)自Paxos，共識過程簡單有效，已被廣泛用于分布式協(xié)調(diào)一致性過程，擁有較高的吞吐量和較低的時延;但由于此類算法面向的是分布式系統(tǒng)數(shù)據(jù)庫和日志等存儲領(lǐng)域，不能解決拜占庭容錯問題，所以不適合于區(qū)塊鏈環(huán)境。

然后是針對拜占庭錯誤場景進(jìn)行優(yōu)化，這類優(yōu)化基本在PBFT的基礎(chǔ)上進(jìn)行改進(jìn)，由于要處理拜占庭錯誤節(jié)點，必然要增加相互之間確認(rèn)的通信，出現(xiàn)明顯的性能下降。Tangaroa算法[16]具有Raft簡單易理解的優(yōu)點，同時兼具拜占庭容錯性。由Tangaroa演變出另一種稱為可擴(kuò)展拜占庭容錯協(xié)議——ScalableBFT[17]，能夠?qū)崿F(xiàn)比Tangaroa更好的性能。對PBFT改進(jìn)的系列算法多用于聯(lián)盟鏈中。

在為公鏈應(yīng)用優(yōu)化方面，Tendermint[18]出現(xiàn)于加密貨幣之后，內(nèi)置了簡單的數(shù)字貨幣，以此為基礎(chǔ)實現(xiàn)了股權(quán)證明（Proof of Stake， PoS）與PBFT的結(jié)合，節(jié)點需要繳納保證金，如果作惡保證金就會被沒收。相似地在2016年，小蟻提出的代理拜占庭容錯（delegated Byzantine Fault Tolerant， dBFT）算法，該算法同樣在PBFT的基礎(chǔ)上借鑒了PoS算法，共識節(jié)點按照節(jié)點的權(quán)益來選出，該算法一定程度改進(jìn)了PoS缺乏最終一致性的問題，使其能夠更適合金融場景;但這一方式也受到共識節(jié)點數(shù)量有限、中心化程度高的質(zhì)疑。2016年，Micali等[19]提出了一種快速拜占庭容錯共識算法——AlgoRand，在該算法中，共識的驗證者和領(lǐng)導(dǎo)者通過密碼抽簽技術(shù)選出，同時還構(gòu)想出一個新協(xié)議完成區(qū)塊的共識。

此外，以比特幣為應(yīng)用的PoW算法不能適應(yīng)一般應(yīng)用的高吞吐量和及時處理的需要。為應(yīng)對PoW要求的高算力帶來的巨大的資源浪費問題，提出權(quán)益證明為代表的共識算法PoS[20]，集群由可信度較高的節(jié)點組成，共識節(jié)點的選取標(biāo)準(zhǔn)依情況而定，但都是為了最大限度保證節(jié)點的可信度，但可能導(dǎo)致權(quán)益集中的問題，對交易吞吐量、延遲、區(qū)塊大小等方面也較少關(guān)注。

可以看出，出現(xiàn)了較多PoW系列算法與PBFT結(jié)合的方式提高共識節(jié)點可信度，但是通過授權(quán)投票產(chǎn)生“超級節(jié)點”的方式會加大系統(tǒng)中心化程度，這顯然和區(qū)塊鏈初衷是相違背的。另外以Paxos、Raft為代表的傳統(tǒng)分布式一致性算法無法應(yīng)對拜占庭容錯問題，但由于其共識效率高的特點，越來越多地被拿來與PBFT相結(jié)合，這給共識算法改進(jìn)帶來新的啟發(fā)。本文提出的改進(jìn)算法同樣是基于聯(lián)盟鏈的前提下，具體的共識節(jié)點的選取可以依照不同的應(yīng)用場景而定。共識節(jié)點的準(zhǔn)入設(shè)置一定程度保證了可信度，同時增加的對主節(jié)點的選舉和驗證過程在不提高系統(tǒng)中心化程度的基礎(chǔ)上保證主節(jié)點的可信度，同時也保證了共識速度不受影響。賦予節(jié)點生命周期使節(jié)點能動態(tài)加入和退出，改進(jìn)三階段廣播流程，縮短交易確認(rèn)時延，提高了區(qū)塊吞吐量。

2 PBFT算法分析

2.1 BFT算法及流程

正PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，也就是將服務(wù)作為狀態(tài)機(jī)來建模，在分布式系統(tǒng)中，狀態(tài)機(jī)在不同的節(jié)點復(fù)制副本，所以，最初PBFT算法是用在分布式系統(tǒng)領(lǐng)域，并不是用在區(qū)塊鏈領(lǐng)域的。在PBFT算法中，一個主節(jié)點領(lǐng)導(dǎo)的共識過程處于一個視圖v之中，視圖是連續(xù)編號的整數(shù)，在各個視圖之中，都存在三種角色，分別是客戶端、主節(jié)點、從節(jié)點。主節(jié)點和從節(jié)點都是備份節(jié)點，因為它們都進(jìn)行數(shù)據(jù)備份，它們各自的功能如下。

1）客戶端?？蛻舳薱是請求的發(fā)送方，發(fā)送的請求格式為〈REQUEST，o，t，c〉，其中o是請求執(zhí)行的操作，t是時間戳，用來保證請求的唯一性，只會被執(zhí)行一次，同時還使得客戶端發(fā)送的請求是全排序的，后發(fā)送的請求的時間戳一定比之前發(fā)送的請求的時間戳更高。

2）主節(jié)點。主節(jié)點主要負(fù)責(zé)接收客戶端發(fā)來的請求，同時對這些請求進(jìn)行排序，分配編號，再向集群中的從節(jié)點廣播請求。

3）從節(jié)點。從節(jié)點主要負(fù)責(zé)接送收此處是否應(yīng)為接收主節(jié)點和其他從節(jié)點發(fā)來的消息，進(jìn)行相應(yīng)的驗證，只會之后是否應(yīng)為之后再執(zhí)行對應(yīng)的操作，最后將共識結(jié)果發(fā)回客戶端。

所有節(jié)點組成的集合用大寫字母R表示，那么集合中的每一個副本可以用0到|R|-1的整數(shù)表示，集合的理想節(jié)點數(shù)為：

其中： f是失效節(jié)點的最大個數(shù);|R|是節(jié)點數(shù)，雖然可以部署多于此數(shù)的節(jié)點，但是這樣只會降低系統(tǒng)性能，并不能對共識過程有幫助。

主節(jié)點的選取由如下公式確定：

其中：p是副本編號，v是視圖號，當(dāng)主節(jié)點失效或者被從節(jié)點推翻時，啟動視圖變更，依照此公式選取新的主節(jié)點。

接下來介紹PBFT算法的流程，總共包括五個階段，分別是請求、預(yù)準(zhǔn)備、準(zhǔn)備、確認(rèn)、回復(fù)。其中主要的階段是中間三個，即預(yù)準(zhǔn)備、準(zhǔn)備、確認(rèn)。下面介紹這五個階段：

1）請求階段。當(dāng)客戶端c向主節(jié)點p發(fā)送請求消息m。

2）預(yù)準(zhǔn)備階段。主節(jié)點P接收到客戶端c發(fā)來的請求m時，主節(jié)點為消息m分配一個編號n，然后向所有的從節(jié)點廣播預(yù)準(zhǔn)備消息，預(yù)準(zhǔn)備消息的格式為〈〈PRE-PREPARE，v，n，d〉，m〉，其中，v是視圖編號，d是請求消息m的摘要。

3）準(zhǔn)備階段。節(jié)點在接收到預(yù)準(zhǔn)備消息時會對其進(jìn)行檢驗，如果同意預(yù)準(zhǔn)備消息，則進(jìn)入準(zhǔn)備階段;如果不同意，則什么也不做。節(jié)點在進(jìn)入準(zhǔn)備階段后向除自己以外的其他節(jié)點廣播準(zhǔn)備消息，同時將預(yù)準(zhǔn)備和準(zhǔn)備消息寫入消息日志。準(zhǔn)備消息格式為〈PREPARE，v，n，d，i〉，其中i是節(jié)點自身編號。準(zhǔn)備階段完成的標(biāo)志為收到2f+1個從不同副本節(jié)點收到的與預(yù)準(zhǔn)備消息一致的準(zhǔn)備消息。對副本節(jié)點驗證預(yù)準(zhǔn)備和準(zhǔn)備消息主要檢查有：視圖編號v、消息序號n和摘要d，以及水線，水線作用是防止一個失效節(jié)點使用一個很大的序號消耗序號空間。

4）確認(rèn)階段。當(dāng)節(jié)點完成準(zhǔn)備階段后，進(jìn)入確認(rèn)階段，此時節(jié)點向除自己以外的所有節(jié)點發(fā)送確認(rèn)消息，確認(rèn)消息格式為〈COMMIT，v，n，D（m），i〉，每個節(jié)點接收確認(rèn)消息進(jìn)行的檢查有：簽名正確，消息的視圖號與當(dāng)前視圖號相同，消息的序號滿足水線的條件。定義確認(rèn)階段完成的條件為節(jié)點i已經(jīng)接收了包括自身在內(nèi)2f+1個確認(rèn)消息且與預(yù)準(zhǔn)備消息一致。

5）回復(fù)階段。當(dāng)節(jié)點完成確認(rèn)階段后，向客戶端發(fā)送回復(fù)消息〈REPLY，v，t，c，i，r〉，其中r是請求最后的執(zhí)行結(jié)果?？蛻舳酥挥惺盏絝+1個不同節(jié)點發(fā)來的同樣響應(yīng)時才認(rèn)為請求正確執(zhí)行成功。

PBFT完整流程如圖1所示。

2.2 PBFT算法不足點分析

從對PBFT流程的詳細(xì)分析可以看出，現(xiàn)有的PBFT算法具有以下幾點不足。

1）客戶端只能向主節(jié)點發(fā)送請求，若請求消息過多，可能造成主節(jié)點過載，可用性降低，不適合區(qū)塊鏈的P2P網(wǎng)絡(luò)環(huán)境。

2）主節(jié)點選取方式較為隨意，不保證主節(jié)點正確性，若出現(xiàn)連續(xù)選舉出的主節(jié)點為惡意節(jié)點，則將極大浪費系統(tǒng)資源，降低系統(tǒng)可靠性和安全性;沒有較為完善的備份數(shù)據(jù)的同步過程，隨著時間的推移，不同節(jié)點之間的數(shù)據(jù)差異越來越大。

3）沒有靈活的共識節(jié)點加入和退出機(jī)制，使得節(jié)點在加入或退出集群時很不靈活，特別是在集群中節(jié)點較多或者節(jié)點變更比較頻繁的情況下，系統(tǒng)將更加難以應(yīng)對，大幅度降低了系統(tǒng)可用性。

4）三階段廣播，包括一次單節(jié)點廣播，加兩次全節(jié)點全網(wǎng)廣播，特別是后兩次全節(jié)點廣播，非常消耗網(wǎng)絡(luò)帶寬，在區(qū)塊鏈這樣的P2P環(huán)境下，若請求過頻，容易造成網(wǎng)絡(luò)擁堵。假設(shè)全網(wǎng)節(jié)點數(shù)為N，則完成一次三階段共識過程，總共需要進(jìn)行消息傳遞的次數(shù)Z為：

顯然，當(dāng)集群中節(jié)點較多時，消息傳遞次數(shù)將急劇增加。

3 EPBFT算法設(shè)計與實現(xiàn)

3.1 整體思想

經(jīng)典的PBFT算法基于狀態(tài)機(jī)復(fù)制原理，最初用于分布式文件系統(tǒng)協(xié)調(diào)一致，除了關(guān)注解決拜占庭容錯問題之外，還著重解決所有副本節(jié)點在全局都執(zhí)行相同順序的請求操作序列，所以在將PBFT算法應(yīng)用于區(qū)塊鏈系統(tǒng)中時有諸多地方需要改進(jìn)以適應(yīng)區(qū)塊鏈系統(tǒng)。在聯(lián)盟鏈系統(tǒng)中節(jié)點的進(jìn)入經(jīng)歷了相應(yīng)的身份認(rèn)證機(jī)制，如基于第三方的身份認(rèn)證、純分布式的身份認(rèn)證等結(jié)合密碼學(xué)技術(shù)可以有效防止女巫攻擊問題。根據(jù)第2章對PBFT算法的分析，結(jié)合區(qū)塊鏈系統(tǒng)實際應(yīng)用情況，提出以下幾點主要改進(jìn)方案：

1）改變客戶端單點提交請求到主節(jié)點方案，而是向全網(wǎng)廣播附上簽名的交易數(shù)據(jù)。這樣的方式更適合P2P環(huán)境。

2）增加主節(jié)點選舉過程，在主節(jié)點宕機(jī)或者被從節(jié)點“推翻之后”，進(jìn)行主節(jié)點選舉，選舉標(biāo)準(zhǔn)按照最長鏈原則，選取擁有處理過最大視圖號與最大編號請求的節(jié)點為新的主節(jié)點。

3）增加數(shù)據(jù)同步及驗證過程，在主節(jié)點選舉完成后進(jìn)行數(shù)據(jù)同步，同步時從節(jié)點對同步數(shù)據(jù)進(jìn)行驗證，若驗證通過，才正式承認(rèn)新的主節(jié)點，開始下一輪共識過程。

4）通過給節(jié)點設(shè)置一系列狀態(tài)，在不同的狀態(tài)節(jié)點擁有不同的行為，共識節(jié)點通過在不同狀態(tài)之間的轉(zhuǎn)換從而在集群中擁有完整生命周期，從節(jié)點與主節(jié)點通過心跳保持聯(lián)系，從而使集群中的節(jié)點可以動態(tài)地加入和退出，使得在節(jié)點變動時不必重啟系統(tǒng)，增加系統(tǒng)可用性。節(jié)點的狀態(tài)轉(zhuǎn)換過程如圖2所示。

5）去掉三階段中的確認(rèn)階段，PBFT的確認(rèn)階段作用是確保其他節(jié)點都已經(jīng)收到足夠多的信息來達(dá)成共識。這一階段發(fā)送的COMMIT消息沒有同意或者不同意的信息，只是起一個統(tǒng)計票數(shù)的作用，在PBFT三階段共識過程中那些處于預(yù)準(zhǔn)備和準(zhǔn)備階段的消息在視圖變更發(fā)生后將被丟棄。一個消息完成了確認(rèn)階段說明已經(jīng)有足夠多的節(jié)點都完成了準(zhǔn)備階段，因此確認(rèn)階段保證了PBFT在更換主節(jié)點后減少數(shù)據(jù)同步操作直接可以進(jìn)入下一個視圖狀態(tài)執(zhí)行新的共識過程（這并不能完全消除不一致，因為COMMIT消息同樣可能延遲甚至丟失）。PBFT算法是解決傳統(tǒng)分布式系統(tǒng)容錯，確認(rèn)階段其實是對準(zhǔn)備階段的一種“確認(rèn)”。當(dāng)消息完成準(zhǔn)備階段之后即說明該消息已經(jīng)被合法數(shù)量的節(jié)點驗證通過，即為系統(tǒng)所共識，但是由于存在網(wǎng)絡(luò)延遲等不確定因素，可能存在某些節(jié)點不能同時完成準(zhǔn)備階段，如果在準(zhǔn)備階段之后發(fā)生視圖變更，將會導(dǎo)致不一致性。在聯(lián)盟鏈區(qū)塊鏈環(huán)境，需要保證的是節(jié)點具有相同的初始狀態(tài)，也就是具有相同區(qū)塊高度和視圖號，這兩者可以通過區(qū)塊同步和視圖變更保證。另外在聯(lián)盟式區(qū)塊鏈在有監(jiān)督且較穩(wěn)定的環(huán)境中，視圖變更不會也不應(yīng)是常態(tài)，為確認(rèn)階段所花費的數(shù)據(jù)傳輸開銷應(yīng)該設(shè)法避免。

在省略確認(rèn)階段的情況下，消息在完成準(zhǔn)備階段后提交，需要保證在準(zhǔn)備階段之后發(fā)生視圖變更后系統(tǒng)的一致性。本文設(shè)計利用視圖變更過程來保證一致性，在視圖變更時加入了選舉過程與同步驗證過程。選舉過程的作用是選出系統(tǒng)共識節(jié)點中區(qū)塊鏈結(jié)構(gòu)最長的節(jié)點作為待定主節(jié)點，待定主節(jié)點選舉出來后進(jìn)行同步驗證過程，以此消除由于網(wǎng)絡(luò)原因造成的狀態(tài)不一致性。另外待定主節(jié)點在同步過程中可能同步非法區(qū)塊，而利用區(qū)塊鏈的特性可以容易地檢驗區(qū)塊合法性，所以設(shè)計出同步驗證過程，監(jiān)督待定主節(jié)點在同步過程中行為的合法性。如果待定主節(jié)點在同步過程中出現(xiàn)惡意行為，那么將再次選舉新的待定主節(jié)點?；谝陨戏治?，EPBFT所設(shè)計的改進(jìn)的共識流程可以在不影響系統(tǒng)容錯性的情況下降低共識過程的數(shù)據(jù)傳輸量與通信開銷，提升了共識效率。具體情況下的通信開銷在實驗部分論述。一般情況下假設(shè)全網(wǎng)節(jié)點數(shù)為N，此時完成一次共識過程需要進(jìn)行的消息傳遞次數(shù)Z為：

當(dāng)節(jié)點數(shù)較多時，可以節(jié)省對網(wǎng)絡(luò)帶寬的消耗，縮短共識過程。

3.2 算法設(shè)計

3.2.1 算法符號表示

1）集群中節(jié)點分為兩種，一種是主節(jié)點（master），一種是從節(jié)點（slave），所有節(jié)點集合用集合R表示，兩種節(jié)點都稱為備份節(jié)點，用編號{0，1，…，i，…，|R|-1i的前后兩邊都有點號，書寫正確嗎？請明確?；貜?fù)：點號表示省略了編號從1到i和i到R-1的其他節(jié)點編號}表示。

2）令集合R中最大能容忍的惡意節(jié)點數(shù)為f，則集合R大小必須滿足公式：

R≥3f+1（5）

一般情況下，集合數(shù)取3f+1，因為更多的共識節(jié)點不會對共識過程有幫助，反而會降低整體性能。

3）集合中節(jié)點具有四種狀態(tài)，分別命名為：尋找（searching）、待領(lǐng)導(dǎo)（undetermined）、領(lǐng)導(dǎo)（mastering）、服從（slaving）。

4）視圖編號用整數(shù)v表示，請求編號用整數(shù)n表示，視圖變更或遇到新請求時，v和n加1。在一個視圖中，n必須在水線之間：

H≥n≥h（6）

5）兩階段分別命名為快提案階段（fast-proposal）和快確認(rèn)階段（fast-confirm）。

3.2.2 算法流程

初始化系統(tǒng)時，先經(jīng)過主節(jié)點選舉過程選舉出主節(jié)點，接下來進(jìn)行數(shù)據(jù)備份與驗證階段，因為在去中心化的區(qū)塊鏈共識系統(tǒng)中，如果要達(dá)到共識的目的，各共識節(jié)點需要開始于相同的狀態(tài)。所謂達(dá)到相同的狀態(tài)就是各個備份節(jié)點存儲的數(shù)據(jù)一致，視圖號和請求編號即區(qū)塊高度、上一塊區(qū)塊哈希值等信息一致。完成數(shù)據(jù)備份與驗證階段后，系統(tǒng)開始預(yù)準(zhǔn)備和準(zhǔn)備兩階段共識過程。在消息傳遞過程中，使用密碼學(xué)技術(shù)保證消息的完整性和真實性，定義Si為消息簽名，Di為消息摘要。

具體的算法流程如下：

若系統(tǒng)有主節(jié)點，直接從第三步開始進(jìn)行。直接進(jìn)入快提案階段。此處指代不明確，指哪一步？請調(diào)整語句當(dāng)系統(tǒng)沒有主節(jié)點時，進(jìn)行主節(jié)點選舉過程，所有節(jié)點處于searching狀態(tài)，先經(jīng)過主節(jié)點選舉過程選舉出主節(jié)點，此時當(dāng)選的節(jié)點變?yōu)閡ndetermined狀態(tài)。

接著進(jìn)行數(shù)據(jù)備份與驗證階段，各個從節(jié)點需要從擁有最長鏈的待定主節(jié)點處備份數(shù)據(jù)，從節(jié)點在得到備份數(shù)據(jù)后需要對數(shù)據(jù)進(jìn)行驗證，驗證通過后保存。只有超過2f+1的從節(jié)點驗證通過，才算是正式承認(rèn)主節(jié)點，主節(jié)點從undetermined狀態(tài)轉(zhuǎn)變?yōu)閙astering狀態(tài)，其余節(jié)點從searching狀態(tài)轉(zhuǎn)變?yōu)閟laving狀態(tài)，成為從節(jié)點，視圖號v加1。若主節(jié)點備份數(shù)據(jù)驗證失敗，說明待定主節(jié)點不可信，將該節(jié)點排除出系統(tǒng)，重新選舉主節(jié)點。

交易發(fā)起者c向集群中節(jié)點發(fā)送一個已簽名交易，若接收節(jié)點向全網(wǎng)廣播交易，各共識節(jié)點（包括主節(jié)點）收到交易后驗證交易的合法性，若合法，則緩存起來。主節(jié)點待收到足夠的交易或者到一段時間間隔以后，生成一個區(qū)塊。

快提案階段 主節(jié)點為產(chǎn)生的區(qū)塊生成快提案消息，分配一個編號n，然后向所有的從節(jié)點廣播快提案消息，快提案消息的格式為〈〈FAST-PROPOSAL，v，n，Si，Di〉，block〉，其中：v是視圖編號，block是需要共識的區(qū)塊。從節(jié)點i∈{0，1，…，|R|-1}在接收到快提案消息是會對其進(jìn)行檢驗，如果同意快提案消息，則進(jìn)入快確認(rèn)階段，如果不同意，則對主節(jié)點表示懷疑，廣播視圖變更消息。副本節(jié)點驗證快提案消息主要檢查有：視圖編號v、消息序號n、簽名和摘要、水線、區(qū)塊交易驗證。

快確認(rèn)階段 節(jié)點在進(jìn)入快確認(rèn)階段后向除自己以外的其他節(jié)點廣播快確認(rèn)消息，同時將快提案和快確認(rèn)消息寫入消息日志?？齑_認(rèn)消息格式為〈FAST-CONFIRM，v，n，Si，Di，i〉，其中i是節(jié)點自身編號?？齑_認(rèn)階段完成的標(biāo)志為收到2f+1個從其他不同副本節(jié)點收到的與快提案消息一致的快確認(rèn)消息，若到時間超時為止未收到足夠快確認(rèn)消息，將區(qū)塊丟棄。副本節(jié)點驗證快確認(rèn)消息主要檢查有：視圖編號v、消息序號n、簽名和摘要以及水線。

當(dāng)共識節(jié)點完成快確認(rèn)階段后，提交請求，保存區(qū)塊，表明該區(qū)塊加入?yún)^(qū)塊鏈尾部。

算法主要流程如圖3所示。

3.2.3 主節(jié)點選舉

主節(jié)點選舉依據(jù)最長鏈原則，選出集群服務(wù)器中最后一個共識完成的擁有最大視圖號的編號最大的服務(wù)器作為主節(jié)點。視圖號與編號合起來用一個long型數(shù)據(jù)存儲，分別占據(jù)高32位和低32位，用vnid（view-number id）表示選舉過程主要分為以下幾種情況（圖34～5此處指代圖4、5吧？請明確括號中三個數(shù)依次為：節(jié)點編號，目標(biāo)節(jié)點編號，目標(biāo)vnid）。

1）集群初始化主節(jié)點選舉。

各服務(wù)器初始化后，各共識節(jié)點都處于searching狀態(tài)，都投票給自己，并將自己的一票存入自己的票箱，服務(wù)器收到所有外部投票后，進(jìn)行選票PK，相應(yīng)更新自己的選票并廣播出去，并將合適的選票存入自己的票箱。選票PK有三種情況，分別是：

a）若收到的選票中最大vnid小于自己當(dāng)前主張的vnid，忽略。

b）若收到的選票中最大vnid等于自己當(dāng)前主張的vnid，若此時節(jié)點編號也相同，將選票存入自己的票箱。否則比較節(jié)點編號，若當(dāng)前主張節(jié)點編號較高，忽略消息;否則清空票箱，相應(yīng)更新自己的選票存入票箱并廣播出去。

c）若收到的選票中最大vnid大于自己當(dāng)前主張的vnid，清空票箱，更新當(dāng)前主張的vnid，相應(yīng)更新自己的選票存入票箱并廣播出去。

當(dāng)票箱中有來自不同節(jié)點的2f+1個目標(biāo)一致的選票時，選舉完成，清空票箱，向其目標(biāo)主節(jié)點發(fā)送確認(rèn)消息。被其他節(jié)點認(rèn)同且收到至少2f+1個來自不同節(jié)點的確認(rèn)消息的節(jié)點成為待定主節(jié)點的節(jié)點進(jìn)入undetermined狀態(tài)。選舉過程如圖4～5所示。

2）slave進(jìn)入集群投票給自己。

slave進(jìn)入集群，或者發(fā)生網(wǎng)絡(luò)分區(qū)后找不到master，會進(jìn)入searching狀態(tài)并發(fā)起新的一輪投票。集群中其他節(jié)點將告知其當(dāng)前主節(jié)點信息，收到超過來自不同節(jié)點的2f+1個節(jié)點一致信息后，該節(jié)點與當(dāng)前主節(jié)點建立心跳聯(lián)系，進(jìn)入slaving狀態(tài)，成為從節(jié)點。如圖65所示。

master宕機(jī)后，或者在被slave發(fā)起的視圖變更推翻后，將當(dāng)前master排除出集群，進(jìn)入searching狀態(tài)并發(fā)起新的一輪投票，并且都將票投給自己，投票過程與第一種情況相同，此處不再贅述。

為節(jié)點定義一個完整的生命周期為選舉階段提供基礎(chǔ)的同時，實現(xiàn)了集群中節(jié)點的動態(tài)變更，極大地提高了系統(tǒng)靈活性和可用性。

3.2.4 數(shù)據(jù)備份與驗證

當(dāng)選出待定主節(jié)點之后進(jìn)行的數(shù)據(jù)備份與驗證階段，是為了使各節(jié)點狀態(tài)達(dá)到一致，這在前面已有解釋，同時還可以進(jìn)一步驗證待定主節(jié)點是否為惡意節(jié)點。過程如下。

數(shù)據(jù)同步階段 選舉過程完成后，從節(jié)點向待定主節(jié)點發(fā)送同步請求消息，消息格式為〈SYN-REQUEST，v，vnid，Si，此處有兩個逗號，且均為下標(biāo)，是否應(yīng)該為一個逗號，且逗號不應(yīng)該為下標(biāo)，請明確。后面仍有此類書寫，請一并核對。i〉，如前所述，v為視圖號，vnid為各自提交的最大事務(wù)號，待定主節(jié)點接收到該消息后首先檢查視圖號是否合法，若是則查看對比自己的末尾區(qū)塊編號與消息中的vnid是否一致，若一致直接發(fā)送同步成功消息〈SYN-SUCCESS，v，Si，i〉給該從節(jié)點;否則根據(jù)其他節(jié)點所擁有的數(shù)據(jù)區(qū)塊的不同，向集群中其他節(jié)點分別發(fā)送同步消息和相應(yīng)的備份數(shù)據(jù)區(qū)塊，消息格式為〈〈SYN-DATA，v，Si，i〉，blocks〉，blocks為相應(yīng)的備份數(shù)據(jù)區(qū)塊。

數(shù)據(jù)驗證階段 其他的節(jié)點收到待定主節(jié)點的備份數(shù)據(jù)區(qū)塊后，驗證其合法性。如果合法，則保存起來，廣播驗證通過消息，消息格式為〈SYN-ACK，v，Si，i，d〉，d為收到的備份數(shù)據(jù)區(qū)塊中最后一個區(qū)塊的摘要;否則將其丟棄。同時保存收到的來自其他節(jié)點的驗證結(jié)果消息。因為這一過程驗證目標(biāo)明確，所以只需要一次消息廣播過程即可確定待定主節(jié)點的合法性。當(dāng)從節(jié)點收到來自其他不同節(jié)點的2f+1個通過消息且消息中d一致后，驗證成功，這樣可以保證待定主節(jié)點發(fā)送給每個從節(jié)點的備份數(shù)據(jù)區(qū)塊都是一致的。此時從節(jié)點向主節(jié)點發(fā)送〈SYN-ACHIEVE，v，Si，i〉消息。節(jié)點進(jìn)入slaving狀態(tài)，成為從節(jié)點;反之，認(rèn)為待定主節(jié)點是惡意節(jié)點，排除該節(jié)點，重新進(jìn)行選舉。

驗證確認(rèn)階段 當(dāng)待定主節(jié)點收到2f+1的同步完成消息后，表示有足夠的從節(jié)點正式同意自己，且系統(tǒng)中有足夠的共識節(jié)點。這時待定主節(jié)點進(jìn)入mastering狀態(tài)，正式成為主節(jié)點。

該過程如圖76所示。

3.2.5 切換視圖

在原算法的基礎(chǔ)上更進(jìn)一步，不止在主節(jié)點失效時觸發(fā)視圖變更，當(dāng)從節(jié)點懷疑主節(jié)點時同樣廣播視圖變更消息，從而可能觸發(fā)視圖變更，推翻主節(jié)點。具體流程如下：

1）當(dāng)從節(jié)點發(fā)現(xiàn)主節(jié)點失效或者懷疑主節(jié)點是惡意節(jié)點時，向集群中其他節(jié)點廣播視圖變更消息，前文已闡明懷疑過程，此處不再贅述。視圖變更消息格式為（VIEWCHANGE，vnew，vold，Si，i），vnew為新的視圖號，vold為舊的視圖號，i為節(jié)點編號，vnew=vold+1。

2）其他從節(jié)點在收到視圖變更消息后，驗證消息中的vold是否與當(dāng)前一致，且vnew=vold+1，同時檢查主節(jié)點是否失效：若主節(jié)點未失效且不認(rèn)為主節(jié)點發(fā)來的提案有問題，則忽略該消息;若驗證通過后，廣播視圖變更確認(rèn)消息，消息格式為（VIEWCHANGE-CONFIRM，vnew，vold，Si，i）。

3）當(dāng)從節(jié)點收到2f+1個來自不同節(jié)點的視圖變更確認(rèn)消息后，切換為searching狀態(tài)，進(jìn)入主節(jié)點選舉階段，開始重新選舉主節(jié)點。

4 實驗分析

本章從通信開銷、時延、吞吐量和安全性方面對EPBFT進(jìn)行測試，同時與原來的PBFT算法進(jìn)行比較對照，以此驗證改進(jìn)算法的有效性和可用性。實驗網(wǎng)絡(luò)環(huán)境采用實驗室局域網(wǎng)通信，使用6臺配置相同的Windows系統(tǒng)臺式機(jī)作為共識節(jié)點。

4.1 系統(tǒng)設(shè)計

為了測試改進(jìn)的算法的有效性和可用性，實現(xiàn)了以改進(jìn)算法為核心的區(qū)塊鏈系統(tǒng)。系統(tǒng)底層為一般區(qū)塊鏈技術(shù)架構(gòu)，采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，使用P2P網(wǎng)絡(luò)架構(gòu)，加密方法采用橢圓曲線非對稱加密，整個系統(tǒng)是去中心化的。整個系統(tǒng)分為數(shù)據(jù)上傳、選舉與同步、共識、數(shù)據(jù)存儲四三此處書寫有誤，“選舉與同步”模塊是“共識”模塊的子模塊，在共識模塊中已有說明。原文“整個系統(tǒng)分為：數(shù)據(jù)上傳，選舉與同步，共識，數(shù)據(jù)存儲四個模塊?！毙薷臑椤罢麄€系統(tǒng)分為：數(shù)據(jù)上傳，共識，數(shù)據(jù)存儲三個模塊。”個模塊。

數(shù)據(jù)上傳模塊 此模塊負(fù)責(zé)產(chǎn)生模擬交易數(shù)據(jù)，并持續(xù)向共識模塊傳遞交易數(shù)據(jù)，這些交易將被存入?yún)^(qū)塊并被共識模塊共識，以此測出時延和吞吐量等數(shù)據(jù)。

共識模塊 此模塊將數(shù)據(jù)上傳模塊傳遞來的交易后，產(chǎn)生區(qū)塊進(jìn)行共識，是整個系統(tǒng)的關(guān)鍵模塊，共識流程采用本文提出的EPBFT算法。其中共識模塊又分為主節(jié)點選舉、數(shù)據(jù)同步及驗證和區(qū)塊共識三個子模塊。主節(jié)點選舉模塊負(fù)責(zé)主節(jié)點的選舉以及所有節(jié)點加入和退出以及狀態(tài)的轉(zhuǎn)換邏輯;數(shù)據(jù)同步及驗證負(fù)責(zé)在選舉出新的主節(jié)點后向其他節(jié)點同步數(shù)據(jù)以及對同步的數(shù)據(jù)進(jìn)行驗證;區(qū)塊共識則是進(jìn)行改進(jìn)后的區(qū)塊共識過程。

數(shù)據(jù)存儲模塊 此模塊負(fù)責(zé)將完成共識的區(qū)塊進(jìn)行存儲，數(shù)據(jù)同步驗證過程將保證每個節(jié)點在視圖變更后存儲當(dāng)前完整區(qū)塊鏈數(shù)據(jù)。存儲的數(shù)據(jù)可以被查詢顯示，不可被修改。

整個系統(tǒng)架構(gòu)如圖87所示。

4.2 性能測試

理論上在減去了原PBFT共識過程中的確認(rèn)階段的改進(jìn)算法在共識速度上將獲得提升?，F(xiàn)通過基于改進(jìn)算法構(gòu)建的實驗系統(tǒng)對通信開銷、吞吐量、時延和安全性四方面進(jìn)行測試，并與原PBFT算法進(jìn)行比較，從而驗證改進(jìn)算法的有效性和可用性。在測試過程中保證實驗機(jī)器中可能的故障節(jié)點和惡意節(jié)點都是相同的節(jié)點f個，在這里的實驗中采用f=1。因為集群節(jié)點數(shù)至少為3f+1，所以選擇3組對比實驗，分別使用4個節(jié)點，5個節(jié)點與6個節(jié)點作為共識節(jié)點。

4.2.1 通信開銷分析

設(shè)現(xiàn)在平臺共識節(jié)點數(shù)為n（n>3），可以利用共識算法流程計算出一次完整的PBFT共識需要的通信次數(shù)，計算范圍只包括預(yù)準(zhǔn)備階段、準(zhǔn)備階段和確認(rèn)階段三個主要階段。同時設(shè)視圖變更概率p，p=1/q（平均每q次共識發(fā)生1次視圖變更）。

1）PBFT通信開銷。

首先由前文對PBFT共識過程分析知三階段總通信次數(shù)為2n（n-1）。

對于視圖變更過程，視圖變更階段每個從節(jié)點廣播視圖變更消息，本階段共識網(wǎng)絡(luò)中的通信次數(shù)為（n-1）2。視圖變更確認(rèn)階段新視圖的主節(jié)點收到來自其他從節(jié)點的視圖變更后發(fā)送視圖變更確認(rèn)消息給所有從節(jié)點，本階段共識網(wǎng)絡(luò)中發(fā)生的通信次數(shù)為（n-1），那么系統(tǒng)在p概率下發(fā)生視圖變更時通信總次數(shù)為：

2）EPBFT通信開銷。

由前文對EPBFT共識過程分析知二階段總通信次數(shù)為n（n-1）。

在主節(jié)點選舉過程中，投票第一輪各個從節(jié)點發(fā)送自己的投票給除了自己之外的從節(jié)點。本階段共識網(wǎng)絡(luò)中的通信次數(shù)為（n-1）2。投票第二輪各個從節(jié)點通過選票PK更改投票對象，更改后將投票發(fā)送至除了自己之外的從節(jié)點，該過程通信次數(shù)為（n-1）2。完成選舉的從節(jié)點發(fā)送確認(rèn)消息給待定主節(jié)點，該過程通信次數(shù)為（n-1）。

在數(shù)據(jù)同步驗證階段中，數(shù)據(jù)同步過程中待定主節(jié)點給每一個從節(jié)點發(fā)送其對應(yīng)的同步消息，該過程次數(shù)為（n-1）。同步驗證過程中所有從節(jié)點發(fā)送驗證通過消息給除了待定主節(jié)點和自己之外的所有從節(jié)點，該過程通信次數(shù)為（n-1）（n-2）。驗證確認(rèn)過程中所有從節(jié)點在同步完成后發(fā)送同步完成消息給待定主節(jié)點，該過程通信次數(shù)為（n-1）。

所以選舉過程與同步過程總通信次數(shù)為3n2-4n+1。根據(jù)假設(shè)，若系統(tǒng)在概率p下發(fā)生視圖變更，則總共的通信次數(shù)為：

3）通信開銷對比。

令兩種算法通信開銷比值為I，則在沒有出現(xiàn)視圖變更情況的共識過程中，兩種算法通信次數(shù)比值I1為：

由式（9）可知I1恒等于2，所以如果系統(tǒng)沒有發(fā)生視圖變更，那么EPBFT算法是PBFT通信次數(shù)的一半，有效降低了共識過程中的網(wǎng)絡(luò)通信次數(shù)。

而在視圖變更發(fā)生的情況下，兩種算法通信次數(shù)比值I2為：

經(jīng)過系統(tǒng)實驗驗證，將發(fā)生視圖變更概率P作為自變量，兩種共識算法在節(jié)點數(shù)固定的情況下參與共識下的通信次數(shù)比I。當(dāng)P=0.5時I趨近于1，此時兩種算法的網(wǎng)絡(luò)通信次數(shù)基本相等。當(dāng)P<0.5，也就是每當(dāng)大于兩次共識過程后才可能發(fā)生一次視圖變更時PBFT的網(wǎng)絡(luò)通信次數(shù)大于EPBFT，當(dāng)P越小，I越趨近于2，也就是說視圖變更情況出現(xiàn)概率越小，EPBFT的通信次數(shù)越接近PBFT的一半，因為系統(tǒng)需要為選舉和同步驗證過程所花費通信開銷的情況越少。在聯(lián)盟鏈系統(tǒng)環(huán)境和節(jié)點比較穩(wěn)定的情況下，系統(tǒng)發(fā)生視圖變更的概率是很小的，通信開銷接近為PBFT的一半。如果區(qū)塊鏈平臺每兩次共識就會發(fā)生一次視圖變更，這樣的情況對系統(tǒng)來說是不可接受的，因此，EPBFT算法可以有效減少系統(tǒng)在共識過程中的通信開銷。

4.2.2 吞吐量測試

吞吐量一般指單位時間內(nèi)系統(tǒng)處理的事務(wù)數(shù)，吞吐量的高低顯示了系統(tǒng)承受負(fù)載，處理事務(wù)或者請求交易的能力。在區(qū)塊鏈領(lǐng)域中，一般用每秒交易數(shù)（Transaction Per Second， TPS）來表示，即：

其中：TransactionsΔt為出塊時間內(nèi)系統(tǒng)處理交易數(shù)，Δt為出塊時間。吞吐量隨著每個區(qū)塊的容量增大相應(yīng)地也會變大，但隨著區(qū)塊容量的增大，共識時間和網(wǎng)絡(luò)負(fù)載也會增大，所以當(dāng)大到一定程度時吞吐量會有所下降。為了便于對照，控制變量，將一個塊中包含的交易數(shù)固定為10個。測試了在4、5、6個共識節(jié)點下的三組對照實驗。多次測試取平均值，得出統(tǒng)計結(jié)果。

兩種算法在相同條件下吞吐量對比如圖98所示。

可以看出兩種情況下隨著節(jié)點數(shù)增加，吞吐量都略微減少，但是改進(jìn)的EPBFT算法吞吐量更高，幾乎比原PBFT算法高出一倍，并且隨著交易量的加大，吞吐量提升得更加明顯。

4.2.3 時延測試

共識時延（DelayTime）是衡量共識算法運行速度的重要指標(biāo)，較低的共識時延使得交易可以快速得到確認(rèn)，區(qū)塊鏈安全性更高，同時也能變得更為實用。在本文中測試的共識時延為區(qū)塊完成一次共識過程的時間，即：

其中：Tconfirm為區(qū)塊完成確認(rèn)時間，Ttransmit為快提案階段開始時間。多次測試取平均值，得出統(tǒng)計結(jié)果。

兩種算法在相同條件下共識時延對比如圖109所示。

4.2.4 算法安全性

為驗證EPBFT的安全性，從兩個方面考慮：一方面是對集群中惡意節(jié)點數(shù)量的控制，二是測試在主節(jié)點為惡意節(jié)點或者失效時系統(tǒng)的反應(yīng)。

首先在共識節(jié)點中設(shè)置一個惡意節(jié)點的情況下，可以完成共識，當(dāng)在總節(jié)點數(shù)不變，惡意節(jié)點增加以后超出系統(tǒng)所能承受的最大惡意節(jié)點數(shù)量，無法完成共識。

然后再讓主節(jié)點傳播惡意請求（如將請求序號設(shè)置的很大），系統(tǒng)無法完成共識，發(fā)生視圖變更將存在惡意行為的主節(jié)點“推翻”，重新選舉新主節(jié)點。再驗證新共識算法在主節(jié)點宕機(jī)行為下的安全性與容錯性，設(shè)置主節(jié)點在一次共識過程中宕機(jī)。PBFT算法中從節(jié)點檢測主節(jié)點宕機(jī)后執(zhí)行視圖變更過程的兩個階段，隨后更新視圖號，保證上一輪中完成快確認(rèn)階段的消息全部處理結(jié)束，其他未完成快確認(rèn)階段的請求全部丟棄，之后開始新的共識;EPBFT在檢測到主節(jié)點失效后開始前文所述主節(jié)點選舉過程。選出新主節(jié)點后，主節(jié)點與所有從節(jié)點進(jìn)行同步與驗證階段，保證了在新視圖開始時全局?jǐn)?shù)據(jù)的一致性。同步結(jié)束后開始下一輪共識。

實驗表明EPBFT共識算法在提高了共識速度并減少共識時延的基礎(chǔ)上與原PBFT共識算法一樣能夠保證分布式系統(tǒng)一致性和安全性，提供f=（n-1）/3的容錯性，證明了改進(jìn)的算法是有效和可靠的。

5 結(jié)語

本文提出了一種基于PBFT改進(jìn)的算法模型EPBFT，給集群中節(jié)點定義一個完整的生命周期，使得節(jié)點可以動態(tài)加入和退出;對原PBFT的主節(jié)點選舉方式加以改進(jìn)，選舉出的主節(jié)點更為可信;在主節(jié)點選舉完成之后，共識過程執(zhí)行之前增加一個對主節(jié)點是否所拜占庭節(jié)點的主節(jié)點驗證及數(shù)據(jù)過程，增加一個主節(jié)點驗證及數(shù)據(jù)同步過程，判斷主節(jié)點是否為拜占庭節(jié)點，此處語句不通順，需調(diào)整。回復(fù)：增加一個對主節(jié)點是否所拜占庭節(jié)點的主節(jié)點驗證及數(shù)據(jù)過程”調(diào)整為“增加一個主節(jié)點驗證及數(shù)據(jù)同步過程，判斷主節(jié)點是否為拜占庭節(jié)點，進(jìn)一步保證主節(jié)點的可信性使全節(jié)點在共識開始時狀態(tài)一致。依據(jù)區(qū)塊鏈環(huán)境優(yōu)化共識過程，加快共識過程。未來工作將繼續(xù)優(yōu)化算法細(xì)節(jié)，進(jìn)一步降低網(wǎng)絡(luò)通信量?？梢栽谝院笠牍?jié)點評分機(jī)制，綜合選取最優(yōu)節(jié)點。將算法應(yīng)用于某一實際領(lǐng)域的區(qū)塊鏈系統(tǒng)中，為區(qū)塊鏈的應(yīng)用及普及作出貢獻(xiàn)。

參考文獻(xiàn) （References）

[1] BONNEAU J， MILLER A， CLARK J， et al. SoK： research perspectives and challenges for bitcoin and cryptocurrencies [C]// Proceedings of the 2015 IEEE Symposium on Security and Privacy. Washington， DC： IEEE Computer Society， 2015： 104-121.

[2] 蔡維德，郁蓮，王榮，等.基于區(qū)塊鏈的應(yīng)用系統(tǒng)開發(fā)方法研究[J].軟件學(xué)報，2017，28（6）：1474-1487.（CAI W D， YU L， WANG R， et al. Blockchain application development techniques[J]. Journal of Software， 2017， 28（6）： 1474-1487.）

[3] EYAL I， CENCER A E， SIRER E G， et al. Bitcoin-NG： a scalable blockchain protocol[C]// Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2016： 45-59.

[4] AMALARETHINAM D I G， BALAKRISHNAN C， CHARLES A. An improved methodology for fragment re-allocation in peer-to-peer distributed databases[C]// Proceedings of the 4th International Conference on Advances in Recent Technologies in Communication and Computing. Piscataway， NJ： IEEE， 2012： 78-81.

[5] PEASE M， SHOSTAK R， LAMPORT L. Reaching agreement in the presence of faults[J]. Journal of the ACM， 1980， 27（2）： 228-234.

[6] LAMPORT L， SHOSTAK R， PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems， 1982， 4（3）： 382-401.

[7] LI J R， WOLF T. A one-way proof-of-work protocol to protect controllers in software-defined networks[C]// Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems. New York： ACM， 2016： 123-124.

[8] CASTRO M， LISKOV B. Practical Byzantine fault tolerance[C]// Proceedings of the 3rd Symposium on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 1999： 173-186.

[9] REITER M K. A secure group membership protocol[J]. IEEE Transactions on Software Engineering， 1996， 22（1）： 31-42.

[10] JUNQUEIRA F， REED B. ZooKeeper分布式過程協(xié)同技術(shù)詳解[M].謝超，周貴卿，譯.北京：機(jī)械工業(yè)出版社，2016：188-193.（JUNQUEIRA F， REED B. Detailed Explanation of Zookeeper Distributed Process Collaboration Technology[M]. XIE C， ZHOU G Q， translated. Beijing： China Machine Press， 2016： 188-193.）

[11] 袁勇，王飛躍.區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀與展望[J].自動化學(xué)報，2016，42（4）：481-494.（YUAN Y， WANG F Y. Blockchain： the state of the art and future trends[J]. Acta Automatica Sinica， 2016， 42（4）： 481-494.）

[12] 韓璇，劉亞敏.區(qū)塊鏈技術(shù)中的共識機(jī)制研究[J].信息網(wǎng)絡(luò)安全，2017（9）：147-152.（HAN X， LIU Y M. Research on the consensus mechanisms of blockchain technology[J]. Netinfo Security， 2017（9）： 147-152.）

[13] LAMPORT L. The part-time parliament[J]. ACM Transactions on Computer Systems， 1998， 16（2）： 133-169.

[14] ONGARO D， OUSTERHOUT J. In search of an understandable consensus algorithm[C]// Proceedings of the 2014 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2014： 305-319.

[15] COWLING J， MYERS D， LISKOV B， et al. HQ replication： a hybrid quorum protocol for Byzantine fault tolerance[C]// Proceedings of the 7th Symposium on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2006： 177-190.

[16] COPELAND C， ZHONG H. Tangaroa： a Byzantine fault tolerant raft [EB/OL].[2018-10-25]. http：//www.scs.stanford.edu/14aucs244b/labs/projects/copeland zhong.pdf.

[17] MARTINO W. KADENA： the first scalable， high performance private blockchain [EB/OL].[2018-10-25]. http：//kadena.io/docs/Kadena ConsensusWhitePaperAug2016.pdf.

[18] KWON J. Tendermint： consensus without mining[EB/OL]. [ 2018-10-25].https：//tendermint.com/static/docs/tendermint.pdf.

[19] GILAD Y， HEMO R， MICALI S， et al. Scaling Byzantine agreements for cryptocurrencies [EB/OL].[2018-10-25]. http：//eprint.iacr.org/2017/454.

[20] QUANTUM M. Proof of stake [EB/OL].[2018-10-25]. https：//en.bitcoin.it/wiki/Proof of Stake.