GBFT：一種實(shí)用拜占庭容錯(cuò)算法改進(jìn)方案?

李 彬 張新有

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 成都 611756）

1 引言

區(qū)塊鏈作為數(shù)字加密貨幣的重要底層技術(shù)，最早于2008 年由化名為中本聰［1］的學(xué)者提出。區(qū)塊鏈技術(shù)的去中心化、數(shù)據(jù)不可篡改、數(shù)據(jù)安全等特點(diǎn)，使得其在數(shù)字貨幣、物流溯源、數(shù)據(jù)取證和金融交易等領(lǐng)域都有很好的應(yīng)用前景［2］。

當(dāng)前，區(qū)塊鏈發(fā)展成為三種差異化類型：公有鏈，聯(lián)盟鏈，私有鏈［3］。其中，部分去中心化的聯(lián)盟鏈得益于參與節(jié)點(diǎn)數(shù)量較為固定、網(wǎng)絡(luò)規(guī)模較小、節(jié)點(diǎn)的信用度好等特點(diǎn)，具備了交易確認(rèn)延遲低、吞吐量高、耗能小等優(yōu)勢(shì)，因此在近年來(lái)得到迅速發(fā)展。共識(shí)算法作為區(qū)塊鏈中最為核心的技術(shù)，對(duì)區(qū)塊鏈的整體性能表現(xiàn)有著直接的影響。現(xiàn)有的許多適用于公有鏈場(chǎng)景的共識(shí)算法，因?yàn)橛兄薮蟮墓沧R(shí)成本和算力開(kāi)銷，明顯不適用于聯(lián)盟鏈場(chǎng)景下的區(qū)塊鏈［3］。2014 年，隨著IBM 的聯(lián)盟鏈項(xiàng)目Hyperledger Fabric 的推出［4］，人們把目光聚焦到了實(shí)用拜占庭容錯(cuò)算法（Practical Byzantine Fault Tolerance，PBFT）。

本文針對(duì)聯(lián)盟鏈的應(yīng)用場(chǎng)景，分析了PBFT 共識(shí)機(jī)制存在的不足，并基于PBFT算法的思想，提出了一種分級(jí)的共識(shí)方案（Graded Byzantine Fault Tolerance，GBFT），以期在系統(tǒng)的長(zhǎng)期運(yùn)行中達(dá)到更高的共識(shí)效率和吞吐量及更低的資源消耗。

2 共識(shí)機(jī)制

一致性問(wèn)題是分布式系統(tǒng)面臨的核心問(wèn)題之一。分布式系統(tǒng)中如果僅存在非拜占庭錯(cuò)誤，如網(wǎng)絡(luò)延遲、節(jié)點(diǎn)宕機(jī)，可以通過(guò)Paxos［5］和Raft［6］等算法解決一致性問(wèn)題。但是區(qū)塊鏈網(wǎng)絡(luò)作為一個(gè)低信任的分布式系統(tǒng)，節(jié)點(diǎn)之間屬于互相不了解的參與者。受到利益的驅(qū)使，網(wǎng)絡(luò)中還可能產(chǎn)生拜占庭錯(cuò)誤［7］。拜占庭錯(cuò)誤是指存在節(jié)點(diǎn)主動(dòng)向其他節(jié)點(diǎn)發(fā)送錯(cuò)誤信息的可能，拜占庭節(jié)點(diǎn)指可以產(chǎn)生拜占庭錯(cuò)誤的節(jié)點(diǎn)。在一個(gè)存在拜占庭節(jié)點(diǎn)的系統(tǒng)中，需要使用有拜占庭容錯(cuò)能力的共識(shí)算法［8］。目前主流的區(qū)塊鏈共識(shí)機(jī)制主要有工作量證明、權(quán)益證明、股份授權(quán)證明以及實(shí)用拜占庭容錯(cuò)算法等［9］。

2.1 工作量證明

工作量證明（PoW）的概念最早由Cynthia Dwork 和Moni Naor 在1993 年的論文中提出，主要用于解決當(dāng)時(shí)日益嚴(yán)重的垃圾郵件問(wèn)題［10］。幾年后，Markus Jakobsson 和Ari Juels 正式提出了術(shù)語(yǔ)“Proof of Work”，并給出了PoW 的形式化定義［11］。在一個(gè)區(qū)塊鏈網(wǎng)絡(luò)中，必須有負(fù)責(zé)記錄交易的節(jié)點(diǎn)存在，最簡(jiǎn)單的方法是進(jìn)行隨機(jī)選擇。然而，隨機(jī)選擇會(huì)使系統(tǒng)隨時(shí)暴露在可被攻擊的環(huán)境中。因此，如果一個(gè)節(jié)點(diǎn)想要發(fā)布一個(gè)交易區(qū)塊，就必須完成大量的工作來(lái)證明該節(jié)點(diǎn)幾乎沒(méi)有惡意攻擊網(wǎng)絡(luò)的可能性。一般來(lái)說(shuō)，上述所謂的“工作”即計(jì)算機(jī)算力。工作量證明機(jī)制的優(yōu)點(diǎn)在于算法簡(jiǎn)單、去中心化程度高、網(wǎng)絡(luò)擴(kuò)展性強(qiáng)、節(jié)點(diǎn)加入退出靈活。它的缺點(diǎn)是無(wú)用的工作量計(jì)算導(dǎo)致能源、算力等資源的嚴(yán)重浪費(fèi)。此外，PoW 共識(shí)的效率較低，過(guò)長(zhǎng)的出塊時(shí)間和交易確認(rèn)時(shí)間難以滿足現(xiàn)實(shí)需求。

2.2 權(quán)益證明

權(quán)益證明（PoS）［12］試圖通過(guò)將采礦能力與節(jié)點(diǎn)持有的權(quán)益相聯(lián)系來(lái)解決PoW 中算力競(jìng)爭(zhēng)的問(wèn)題。PoS 的核心思想是持有較高權(quán)益的節(jié)點(diǎn)有更大的可能性來(lái)獲得區(qū)塊打包權(quán)。在使用PoS 機(jī)制的網(wǎng)絡(luò)中，依然需要節(jié)點(diǎn)求解PoW 中類似的數(shù)學(xué)難題。但是每個(gè)節(jié)點(diǎn)面對(duì)的數(shù)學(xué)難題的難度是不同的，這個(gè)難度與節(jié)點(diǎn)持有的代幣數(shù)量正相關(guān)。這意味著節(jié)點(diǎn)持有的代幣數(shù)量越多，它所需要求解的數(shù)學(xué)難題的難度越低，那么該節(jié)點(diǎn)解出這個(gè)難題并獲得區(qū)塊打包權(quán)的概率也就越大。PoS 的去中心化能力、網(wǎng)絡(luò)擴(kuò)展性與PoW 相當(dāng)，同時(shí)還有效降低了對(duì)資源的浪費(fèi)。但是PoS 中存在的“無(wú)利害攻擊”，“長(zhǎng)程攻擊”等問(wèn)題也讓PoS 的安全性備受質(zhì)疑。

2.3 股份授權(quán)證明

股份授權(quán)證明（DPoS）［13］，可以看做PoS的一個(gè)變種，由Bitshares 的首席開(kāi)發(fā)者Dan Larimer 提出并應(yīng)用。它通過(guò)實(shí)施去中心化的民主方式，每個(gè)節(jié)點(diǎn)可以將其持有的權(quán)益作為選票投給一名代表。系統(tǒng)將選出得票較高的前N 個(gè)節(jié)點(diǎn)組成見(jiàn)證人網(wǎng)絡(luò)。見(jiàn)證人網(wǎng)絡(luò)中的節(jié)點(diǎn)使用專業(yè)運(yùn)行的網(wǎng)絡(luò)服務(wù)器，收集交易、打包區(qū)塊，引導(dǎo)促進(jìn)區(qū)塊鏈項(xiàng)目的發(fā)展。在完成本職工作的同時(shí)，這些節(jié)點(diǎn)還可以領(lǐng)取區(qū)塊獎(jiǎng)勵(lì)和交易手續(xù)費(fèi)。DPoS 通過(guò)投票、選舉降低了參與共識(shí)的節(jié)點(diǎn)數(shù)目，因此與POS、POW 相比，它具有更低的交易處理時(shí)延和更高的吞吐量。但是DPoS中存在的“超級(jí)節(jié)點(diǎn)”也讓它的去中心化能力備受爭(zhēng)議。

2.4 實(shí)用拜占庭容錯(cuò)

實(shí)用拜占庭容錯(cuò)（PBFT），最早由Castro等［14］在1999 年提出，是解決存在拜占庭節(jié)點(diǎn)的分布式系統(tǒng)一致性問(wèn)題的通用方案。PBFT算法基于狀態(tài)機(jī)復(fù)制原理（State Machine Replication）［15］，主要由三個(gè)協(xié)議組成：一致性協(xié)議、檢查點(diǎn)協(xié)議以及視圖更換協(xié)議。區(qū)塊生成過(guò)程中，一致性協(xié)議用來(lái)保證全網(wǎng)所有的節(jié)點(diǎn)保存數(shù)據(jù)的一致性，其通過(guò)三階段節(jié)點(diǎn)間的互相通信來(lái)實(shí)現(xiàn)；當(dāng)運(yùn)行一致性協(xié)議無(wú)法達(dá)成一致時(shí)產(chǎn)生超時(shí)事件，啟動(dòng)視圖更換協(xié)議進(jìn)行視圖轉(zhuǎn)換，以保證節(jié)點(diǎn)之間順利達(dá)成共識(shí)；檢查點(diǎn)協(xié)議主要有兩個(gè)用途：一是定期清除節(jié)點(diǎn)的過(guò)期數(shù)據(jù)，以減輕存儲(chǔ)壓力；二是檢查系統(tǒng)狀態(tài)，將系統(tǒng)中的節(jié)點(diǎn)同步到一個(gè)相同狀態(tài)。目前在區(qū)塊鏈領(lǐng)域中，PBFT 共識(shí)機(jī)制主要應(yīng)用于聯(lián)盟鏈場(chǎng)景，例如hyperledger fabric（v0.6）、FISCO BCOS［16］等聯(lián)盟鏈平臺(tái)都在進(jìn)行該共識(shí)機(jī)制的實(shí)際部署應(yīng)用。

在PBFT 算法中，一個(gè)消息從發(fā)起到達(dá)成共識(shí)需要經(jīng)過(guò)5 個(gè)階段。圖1 中，C 代表客戶端，0、1、2、3 表示4 個(gè)參與共識(shí)的節(jié)點(diǎn)，其中節(jié)點(diǎn)3 為拜占庭節(jié)點(diǎn)。具體步驟如下：

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

1）request階段：客戶端發(fā)送請(qǐng)求到主節(jié)點(diǎn)；

2）pre-prepare階段：主節(jié)點(diǎn)收到客戶端請(qǐng)求后將其封裝為一個(gè)pre-prepare 消息，然后將pre-prepare消息廣播給從節(jié)點(diǎn)；

3）prepare 階段：從節(jié)點(diǎn)收到pre-prepare 證書后將其封裝為prepare 消息，并廣播給其他從節(jié)點(diǎn)，從節(jié)點(diǎn)進(jìn)入pre-prepared狀態(tài)；

4）commit 階段：當(dāng)系統(tǒng)中存在f 個(gè)拜占庭節(jié)點(diǎn)時(shí)，要求系統(tǒng)中總節(jié)點(diǎn)數(shù)量不能小于3f+1。若一個(gè)節(jié)點(diǎn)收到包括自己節(jié)點(diǎn)prepare消息在內(nèi)的2f+1 個(gè)prepare 消息后，則該節(jié)點(diǎn)進(jìn)入prepared 狀態(tài)，并向其他節(jié)點(diǎn)廣播commit消息；

5）reply 階段：節(jié)點(diǎn)收到包括自己節(jié)點(diǎn)的commit消息在內(nèi)的2f+1個(gè)commit消息后進(jìn)入commited狀態(tài)，并向客戶端返回reply響應(yīng)消息。

傳統(tǒng)拜占庭容錯(cuò)算法由于指數(shù)級(jí)別的時(shí)間復(fù)雜度而難以在實(shí)際系統(tǒng)中應(yīng)用。PBFT算法則將時(shí)間復(fù)雜度降到了多項(xiàng)式級(jí)別，還能提供1/3 的容錯(cuò)性。但PBFT算法的缺點(diǎn)也很明顯。一是算法在收到客戶端請(qǐng)求之后，需要經(jīng)過(guò)5 個(gè)階段才能達(dá)成共識(shí)。其中prepare階段與commit階段是全節(jié)點(diǎn)參與的廣播過(guò)程，使得共識(shí)過(guò)程產(chǎn)生巨大的通信開(kāi)銷；二是PBFT算法中的主節(jié)點(diǎn)由所有節(jié)點(diǎn)依次輪流擔(dān)當(dāng)，這種主節(jié)點(diǎn)選擇策略過(guò)于隨意，使得主節(jié)點(diǎn)身份可以被輕易預(yù)測(cè)，增加了其被攻擊的風(fēng)險(xiǎn)；三是算法中的每個(gè)節(jié)點(diǎn)都維護(hù)了一個(gè)固定的節(jié)點(diǎn)列表，缺少節(jié)點(diǎn)的加入、退出機(jī)制，不能靈活應(yīng)對(duì)網(wǎng)絡(luò)規(guī)模的動(dòng)態(tài)變化。

不同的共識(shí)算法在不同的評(píng)判項(xiàng)目中，具有不同的表現(xiàn)。對(duì)上述4 種共識(shí)算法，從高往低分別用5分至1分對(duì)各項(xiàng)評(píng)測(cè)功能點(diǎn)做出評(píng)測(cè)，結(jié)果如表1所示［17］。

表1 四種共識(shí)算法性能比較

除以上四種經(jīng)典共識(shí)算法外，近年來(lái)還涌現(xiàn)了多種新型共識(shí)算法，如Algorand［18］、Omniledger［19］、Rapidchain［20］、2-hop［21］。這些算法本質(zhì)上都是多種經(jīng)典共識(shí)算法融合的產(chǎn)物，它們不約而同地體現(xiàn)了同一個(gè)共識(shí)算法改進(jìn)思路：基于實(shí)際應(yīng)用場(chǎng)景對(duì)處理效率和規(guī)模的不同需求，將各具優(yōu)勢(shì)的共識(shí)算法相融合，取長(zhǎng)補(bǔ)短，從而在各項(xiàng)指標(biāo)中取得最佳平衡。這也是本文提出的改進(jìn)方案的基本思路。

3 改進(jìn)方案GBFT

由圖1 知，PBFT 算法的一致性協(xié)議中有兩個(gè)階段（prepare 階段和commit 階段）的全節(jié)點(diǎn)廣播。隨著節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)中的通信開(kāi)銷會(huì)增長(zhǎng)迅速，影響算法的共識(shí)效率。針對(duì)此問(wèn)題，結(jié)合聯(lián)盟鏈的特點(diǎn)，本文引入了非拜占庭容錯(cuò)的共識(shí)協(xié)議，以降低節(jié)點(diǎn)之間的通信開(kāi)銷；為了配合非拜占庭容錯(cuò)的共識(shí)協(xié)議，同時(shí)提出了一種基于節(jié)點(diǎn)行為的選舉制度；在非拜占庭容錯(cuò)協(xié)議、選舉機(jī)制、PBFT 容錯(cuò)協(xié)議的基礎(chǔ)上構(gòu)建了三級(jí)共識(shí)機(jī)制。

3.1 整體思想

根據(jù)模塊功能的不同，可以將一個(gè)使用PBFT共識(shí)機(jī)制的區(qū)塊鏈系統(tǒng)抽象為四個(gè)層次［22］（圖2）：應(yīng)用層、執(zhí)行引擎層、共識(shí)層、數(shù)據(jù)層。其中，應(yīng)用層代表各種基于區(qū)塊鏈網(wǎng)絡(luò)的應(yīng)用；執(zhí)行引擎層提供了區(qū)塊鏈網(wǎng)絡(luò)的運(yùn)行時(shí)環(huán)境；共識(shí)層定義了系統(tǒng)所使用的共識(shí)協(xié)議；數(shù)據(jù)層定義了區(qū)塊、交易等結(jié)構(gòu)以及與這些結(jié)構(gòu)相關(guān)的增刪改查操作。通過(guò)2.4節(jié)的分析可知，PBFT 共識(shí)機(jī)制的性能瓶頸主要在于準(zhǔn)備階段和提交階段的兩次全節(jié)點(diǎn)廣播。隨著區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增多，網(wǎng)絡(luò)通信量會(huì)急劇增長(zhǎng)，從而增加帶寬的壓力，導(dǎo)致了交易確認(rèn)時(shí)間長(zhǎng)、吞吐量低、網(wǎng)絡(luò)擴(kuò)展性差等問(wèn)題。

圖2 使用PBFT共識(shí)機(jī)制的區(qū)塊鏈系統(tǒng)架構(gòu)

針對(duì)PBFT 共識(shí)機(jī)制的性能瓶頸，本文提出以下三點(diǎn)舉措解決問(wèn)題。

1）引入非拜占庭容錯(cuò)的一致性協(xié)議。在聯(lián)盟鏈場(chǎng)景中，節(jié)點(diǎn)都是經(jīng)過(guò)一定準(zhǔn)入機(jī)制才能加入?yún)^(qū)塊鏈網(wǎng)絡(luò)，這使得聯(lián)盟鏈中的節(jié)點(diǎn)相比公有鏈中的節(jié)點(diǎn)有更高的可信度。據(jù)此可以認(rèn)為聯(lián)盟鏈中大多數(shù)情況下是沒(méi)有拜占庭節(jié)點(diǎn)的，此時(shí)在網(wǎng)絡(luò)中運(yùn)行拜占庭容錯(cuò)的一致性協(xié)議并不是十分必要。因此，可以在在共識(shí)層引入一種非拜占庭容錯(cuò)的一致性協(xié)議。系統(tǒng)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)狀態(tài)來(lái)選擇執(zhí)行不同的一致性協(xié)議：當(dāng)參與共識(shí)的節(jié)點(diǎn)中不存在拜占庭節(jié)點(diǎn)時(shí)，運(yùn)行非拜占庭容錯(cuò)協(xié)議；當(dāng)使用非拜占庭容錯(cuò)協(xié)議無(wú)法達(dá)到一致時(shí)，運(yùn)行PBFT 的一致性協(xié)議。

2）設(shè)計(jì)基于節(jié)點(diǎn)行為的選舉機(jī)制。引入非拜占庭容錯(cuò)協(xié)議的同時(shí)也引發(fā)了另外一個(gè)問(wèn)題，即網(wǎng)絡(luò)中存在拜占庭節(jié)點(diǎn)時(shí)，使用非拜占庭容錯(cuò)協(xié)議無(wú)法達(dá)到一致，那么就需要切換到PBFT 的一致性協(xié)議。如果在存在拜占庭節(jié)點(diǎn)的網(wǎng)絡(luò)中使全節(jié)點(diǎn)都參與非拜占庭容錯(cuò)協(xié)議，實(shí)際上共識(shí)機(jī)制不僅會(huì)退化為普通的PBFT 算法，還會(huì)因?yàn)轭l繁的協(xié)議切換帶了更大的共識(shí)成本。因此需要設(shè)計(jì)一種選舉機(jī)制，選出部分節(jié)點(diǎn)參與非拜占庭容錯(cuò)協(xié)議，且選出的節(jié)點(diǎn)應(yīng)當(dāng)盡量避免包含拜占庭節(jié)點(diǎn)。

3）提出三級(jí)共識(shí)機(jī)制。在計(jì)算機(jī)結(jié)構(gòu)的三級(jí)存儲(chǔ)體系中，計(jì)算機(jī)的存取速度接近于緩存的速度，而存儲(chǔ)容量由硬盤所決定。基于這種思想，提出三級(jí)共識(shí)機(jī)制。首先由選舉出的部分節(jié)點(diǎn)參與非拜占庭容錯(cuò)協(xié)議作為第一級(jí)共識(shí)，第一級(jí)共識(shí)無(wú)法達(dá)成一致的情況下進(jìn)入第二級(jí)共識(shí)。第二級(jí)共識(shí)是部分節(jié)點(diǎn)參與的PBFT 一致性協(xié)議，當(dāng)?shù)诙?jí)共識(shí)無(wú)法達(dá)成一致時(shí)進(jìn)入第三級(jí)共識(shí)。第三級(jí)共識(shí)就是原始的全節(jié)點(diǎn)參與的PBFT共識(shí)。最終希望達(dá)到的效果就是整個(gè)網(wǎng)絡(luò)的共識(shí)效率由第一級(jí)共識(shí)決定，而系統(tǒng)的容錯(cuò)性由第三級(jí)共識(shí)決定。

綜上，在共識(shí)層應(yīng)用GBFT 算法的區(qū)塊鏈系統(tǒng)架構(gòu)如圖3所示。

圖3 使用GBFT共識(shí)機(jī)制的區(qū)塊鏈系統(tǒng)架構(gòu)

3.2 改進(jìn)方案設(shè)計(jì)

3.2.1 非拜占庭容錯(cuò)協(xié)議

引入非拜占庭容錯(cuò)協(xié)議的目的在于簡(jiǎn)化PBFT共識(shí)協(xié)議中prepare階段和commit階段中的全節(jié)點(diǎn)廣播通信，本文采用了參考文獻(xiàn)［23］中提出的簡(jiǎn)化一致性協(xié)議，如圖4所示，具體內(nèi)容為

圖4 非拜占庭容錯(cuò)協(xié)議

1）主節(jié)點(diǎn)廣播pre-prepare消息到從節(jié)點(diǎn)，從節(jié)點(diǎn)驗(yàn)證消息內(nèi)容后向主節(jié)點(diǎn)回復(fù)確認(rèn)消息；

2）主節(jié)點(diǎn)收到所有從節(jié)點(diǎn)的確認(rèn)消息后，廣播confirm 消息到從節(jié)點(diǎn)，從節(jié)點(diǎn)驗(yàn)證消息內(nèi)容后向主節(jié)點(diǎn)回復(fù)確認(rèn)消息；

3）主節(jié)點(diǎn)收到所有節(jié)點(diǎn)的確認(rèn)消息則代表達(dá)成共識(shí)，否則意味著共識(shí)失敗。

3.2.2 選舉機(jī)制

在引入非拜占庭容錯(cuò)協(xié)議的系統(tǒng)中，系統(tǒng)優(yōu)先選擇非拜占庭容錯(cuò)協(xié)議作為共識(shí)協(xié)議，當(dāng)非拜占庭容錯(cuò)協(xié)議無(wú)法達(dá)成一致時(shí)再切換到PBFT的一致性協(xié)議。為了避免不同協(xié)議頻繁切換帶來(lái)的額外開(kāi)銷，我們希望每次參與非拜占庭容錯(cuò)協(xié)議的節(jié)點(diǎn)都是誠(chéng)實(shí)節(jié)點(diǎn)，為此系統(tǒng)中設(shè)計(jì)了一個(gè)基于節(jié)點(diǎn)行為的選舉機(jī)制。

在區(qū)塊鏈網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都由一個(gè)信用分屬性。所有節(jié)點(diǎn)被劃分為兩類：共識(shí)節(jié)點(diǎn)、非共識(shí)節(jié)點(diǎn)。共識(shí)節(jié)點(diǎn)與非共識(shí)節(jié)點(diǎn)的比例為1∶1。選舉模塊選取共識(shí)節(jié)點(diǎn)時(shí)遵循兩個(gè)原則：一是信用分高的節(jié)點(diǎn)優(yōu)先；二是信用分相同時(shí)編號(hào)較小的節(jié)點(diǎn)優(yōu)先。共識(shí)過(guò)程中，首先由共識(shí)節(jié)點(diǎn)參與一級(jí)共識(shí)，若達(dá)成一致，則每個(gè)參與節(jié)點(diǎn)可獲得2 信用分；若無(wú)法達(dá)成一致，參與節(jié)點(diǎn)扣3 信用分，然后進(jìn)入二級(jí)共識(shí)。若系統(tǒng)執(zhí)行二級(jí)共識(shí)達(dá)成一致，每個(gè)參與節(jié)點(diǎn)獲得1 信用分；若無(wú)法達(dá)成一致，每個(gè)參與節(jié)點(diǎn)扣2 信用分，然后進(jìn)入三級(jí)共識(shí)。三級(jí)共識(shí)執(zhí)行的是全節(jié)點(diǎn)參與的PBFT 一致性協(xié)議，三級(jí)共識(shí)中不再對(duì)節(jié)點(diǎn)信用分進(jìn)行增減。如此往復(fù)，節(jié)點(diǎn)會(huì)因?yàn)樽陨硇袨槎@取、損失信用分，分值代表了節(jié)點(diǎn)的可信度。圖5 是一個(gè)節(jié)點(diǎn)的信用分的狀態(tài)轉(zhuǎn)換圖，其中X代表一個(gè)節(jié)點(diǎn)的信用分。

圖5 節(jié)點(diǎn)信用分狀態(tài)轉(zhuǎn)換圖

共識(shí)節(jié)點(diǎn)選舉機(jī)制將會(huì)在以下三種情況發(fā)生時(shí)被觸發(fā)：

1）區(qū)塊鏈系統(tǒng)啟動(dòng)的初始時(shí)刻。此時(shí)所有節(jié)點(diǎn)信用分為0，根據(jù)信用分相同時(shí)編號(hào)較小的節(jié)點(diǎn)優(yōu)先原則，選舉模塊將選擇編號(hào)較小的前50%節(jié)點(diǎn)作為共識(shí)節(jié)點(diǎn)。

2）發(fā)生了共識(shí)級(jí)別轉(zhuǎn)換。若某次請(qǐng)求的共識(shí)過(guò)程中發(fā)生了共識(shí)級(jí)別轉(zhuǎn)換，意味著共識(shí)節(jié)點(diǎn)集合中存在拜占庭節(jié)點(diǎn)。最壞情況下，該請(qǐng)求依然可以通過(guò)三級(jí)共識(shí)在各節(jié)點(diǎn)間達(dá)成一致，然而在下一個(gè)請(qǐng)求到來(lái)時(shí)共識(shí)節(jié)點(diǎn)集合中還是存在拜占庭節(jié)點(diǎn)，那么通過(guò)一級(jí)共識(shí)始終無(wú)法達(dá)成一致，總是要執(zhí)行共識(shí)級(jí)別轉(zhuǎn)換，帶來(lái)額外的資源消耗。因此，每當(dāng)發(fā)生了共識(shí)級(jí)別轉(zhuǎn)換，在當(dāng)前請(qǐng)求完成后，都要重新進(jìn)行共識(shí)節(jié)點(diǎn)選舉。

3）共識(shí)節(jié)點(diǎn)強(qiáng)制選舉計(jì)時(shí)器超時(shí)。共識(shí)節(jié)點(diǎn)長(zhǎng)時(shí)間運(yùn)行一級(jí)共識(shí)會(huì)使這些節(jié)點(diǎn)始終處于忙碌狀態(tài)，而非共識(shí)節(jié)點(diǎn)無(wú)法獲得信用分，沒(méi)有上升通道，也浪費(fèi)了算力。為了避免這種情況的發(fā)生，在系統(tǒng)中設(shè)定一個(gè)共識(shí)節(jié)點(diǎn)強(qiáng)制選舉計(jì)時(shí)器。當(dāng)該計(jì)時(shí)器超時(shí)，將所有節(jié)點(diǎn)信用分清零，強(qiáng)制進(jìn)行共識(shí)節(jié)點(diǎn)選舉。共識(shí)節(jié)點(diǎn)編號(hào)ni由式（1）和式（2）計(jì)算得出。

其中：timestamp為共識(shí)節(jié)點(diǎn)強(qiáng)制選舉計(jì)時(shí)器超時(shí)時(shí)刻的時(shí)間戳，N為節(jié)點(diǎn)總數(shù)。

3.2.3 三級(jí)共識(shí)機(jī)制

為了進(jìn)一步提高共識(shí)效率與網(wǎng)絡(luò)擴(kuò)展性，結(jié)合非拜占庭容錯(cuò)協(xié)議、PBFT 一致性協(xié)議以及選舉機(jī)制，提出的三級(jí)共識(shí)機(jī)制流程如圖6所示。

圖6 三級(jí)共識(shí)算法流程

具體內(nèi)容為

1）選舉產(chǎn)生共識(shí)節(jié)點(diǎn)。

2）接收來(lái)自客戶端的交易請(qǐng)求。

3）共識(shí)節(jié)點(diǎn)執(zhí)行一級(jí)共識(shí)。若達(dá)成一致，進(jìn)入6）；否則，進(jìn)入4）。

4）執(zhí)行共識(shí)級(jí)別轉(zhuǎn)換，共識(shí)節(jié)點(diǎn)參與二級(jí)共識(shí)。若達(dá)成一致，進(jìn)入6）；否則，進(jìn)入5）。

5）執(zhí)行視圖轉(zhuǎn)換，所有節(jié)點(diǎn)參與三級(jí)共識(shí)。若達(dá)成一致，進(jìn)入6）；否則，繼續(xù)執(zhí)行5）。

6）所有節(jié)點(diǎn)接受共識(shí)結(jié)果，執(zhí)行客戶端請(qǐng)求。7）更新每個(gè)節(jié)點(diǎn)的信用分。

8）若發(fā)生了共識(shí)級(jí)別轉(zhuǎn)換，則選舉產(chǎn)生新的共識(shí)節(jié)點(diǎn)。

9）一次請(qǐng)求結(jié)束。

4 實(shí)驗(yàn)場(chǎng)景及結(jié)果分析

本章從吞吐量、交易確認(rèn)時(shí)延和容錯(cuò)性能等三方面分別對(duì)原始PBFT 和GBFT 進(jìn)行測(cè)試。通過(guò)對(duì)照，驗(yàn)證了改進(jìn)方案的有效性和可用性。

4.1 實(shí)驗(yàn)場(chǎng)景

租用了一臺(tái)云服務(wù)器作為實(shí)驗(yàn)平臺(tái)，在服務(wù)器上安裝了Ubuntu 操作系統(tǒng)以及docker、docker-compose、Go 語(yǔ)言等基本環(huán)境。然后在Hyperledger Fabric 原生的PBFT 算法的基礎(chǔ)上實(shí)現(xiàn)了GBFT。最后在服務(wù)器上分別對(duì)應(yīng)用原始PBFT 算法的Hyperledger Fabric 和應(yīng)用GBFT 算法的Hyperledger Fabric 進(jìn)行測(cè)試。實(shí)驗(yàn)平臺(tái)的軟硬件配置如表2所示。

表2 實(shí)驗(yàn)環(huán)境配置信息表

4.2 吞吐量測(cè)試

吞吐量是衡量系統(tǒng)運(yùn)行效率的一個(gè)重要標(biāo)準(zhǔn)。在區(qū)塊鏈網(wǎng)絡(luò)中，一般用每秒交易數(shù)（tps）來(lái)表示，即：

其中：transactions 為出塊時(shí)間內(nèi)系統(tǒng)處理交易數(shù)，t為出塊時(shí)間。設(shè)計(jì)兩種共識(shí)機(jī)制在4、5、6、7、8 個(gè)節(jié)點(diǎn)下的對(duì)照實(shí)驗(yàn)，多次測(cè)試取平均值，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 兩種算法的吞吐量比較

從圖7 的實(shí)驗(yàn)結(jié)果可以看出，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增加，兩種情況下吞吐量都下降明顯。這是因?yàn)楣?jié)點(diǎn)數(shù)目的增加使得網(wǎng)絡(luò)中通信開(kāi)銷增大，導(dǎo)致網(wǎng)絡(luò)運(yùn)行效率下降。還可以看出，在節(jié)點(diǎn)數(shù)目相同的情況下，相比于原始PBFT 算法，GBFT 始終具有更高的吞吐量。

4.3 時(shí)延測(cè)試

交易確認(rèn)時(shí)延指客戶端發(fā)送一個(gè)交易請(qǐng)求到客戶端確認(rèn)交易完成的時(shí)間間隔，即：

其中：Tconfirm為交易得到確認(rèn)的時(shí)間，Trequest為發(fā)送交易請(qǐng)求的開(kāi)始時(shí)間。設(shè)計(jì)兩種共識(shí)機(jī)制在4、5、6、7、8 個(gè)節(jié)點(diǎn)下的對(duì)照實(shí)驗(yàn)，多次測(cè)試取平均值，實(shí)驗(yàn)結(jié)果如圖8所示。帶來(lái)的通信成本增加所導(dǎo)致的結(jié)果，但是原始PBFT算法的時(shí)延上升速率更大，而GBFT由于引入了非拜占庭容錯(cuò)一致性協(xié)議與選舉機(jī)制，使得它的時(shí)延上升速率是隨節(jié)點(diǎn)數(shù)目的增加而下降的。此外，在節(jié)點(diǎn)數(shù)目相同的情況下，相比于PBFT，GBFT始終具有更低的交易確認(rèn)時(shí)延。

圖8 兩種算法的交易確認(rèn)時(shí)延比較

圖8 中，兩種方案的交易確認(rèn)時(shí)延都隨節(jié)點(diǎn)數(shù)目的增加呈上升趨勢(shì)，這同樣是由節(jié)點(diǎn)數(shù)目的增加

4.4 容錯(cuò)性分析

設(shè)區(qū)塊鏈網(wǎng)絡(luò)中共有N（N ≥4）個(gè)節(jié)點(diǎn)，其中有F 個(gè)拜占庭節(jié)點(diǎn)。改進(jìn)方案中，系統(tǒng)會(huì)根據(jù)節(jié)點(diǎn)信用度的高低選出N/2 個(gè)節(jié)點(diǎn)納入共識(shí)節(jié)點(diǎn)組，設(shè)共識(shí)節(jié)點(diǎn)組中的拜占庭節(jié)點(diǎn)數(shù)目為f（f ≤F），則有：

1）第一級(jí)共識(shí)：共識(shí)節(jié)點(diǎn)組參與簡(jiǎn)化協(xié)議。若共識(shí)節(jié)點(diǎn)組中沒(méi)有拜占庭節(jié)點(diǎn)，即f=0，則順利達(dá)成一致；若f ≥1，則通過(guò)非拜占庭容錯(cuò)協(xié)議無(wú)法達(dá)成一致，進(jìn)入第二級(jí)共識(shí)。

2）第二級(jí)共識(shí)：共識(shí)節(jié)點(diǎn)組參與PBFT 共識(shí)協(xié)議。若1 ≤f≤（N/2-1）/3，已知PBFT算法的容錯(cuò)性為（N-1）/3，可知第二級(jí)共識(shí)順利達(dá)成一致；若f>（N/2-1）/3，則第二級(jí)共識(shí)無(wú)法達(dá)成一致，進(jìn)入第三級(jí)共識(shí)。

3）第三級(jí)共識(shí)：全節(jié)點(diǎn)參與PBFT 共識(shí)。此時(shí)共識(shí)機(jī)制退化為原始的PBFT 算法，有f=F。當(dāng)f≤（N-1）/3 時(shí)，節(jié)點(diǎn)之間順利達(dá)成一致；當(dāng)f >（N-1）/3，整個(gè)網(wǎng)絡(luò)無(wú)法達(dá)成一致。

以上分析證明，GBFT 的容錯(cuò)性是由第三級(jí)共識(shí)的容錯(cuò)性決定的。即采用GBFT 作為共識(shí)機(jī)制的區(qū)塊鏈網(wǎng)絡(luò)中共N個(gè)節(jié)點(diǎn)時(shí)，整個(gè)網(wǎng)絡(luò)可以提供（N-1）/3的容錯(cuò)性。

5 結(jié)語(yǔ)

基于PBFT 算法的思想，結(jié)合聯(lián)盟鏈應(yīng)用場(chǎng)景中節(jié)點(diǎn)可信度相對(duì)更高的特點(diǎn)，提出一種改進(jìn)的共識(shí)算法。首先在保留PBFT一致性協(xié)議的同時(shí)引入了非拜占庭容錯(cuò)協(xié)議，以降共識(shí)過(guò)程中的通信開(kāi)銷；為了避免兩種一致性協(xié)議的頻繁切換帶來(lái)的額外開(kāi)銷，提出了基于節(jié)點(diǎn)行為的選舉機(jī)制；最后在非拜占庭容錯(cuò)協(xié)議、選舉機(jī)制、PBFT一致性協(xié)議的基礎(chǔ)上構(gòu)建了三級(jí)共識(shí)機(jī)制。實(shí)驗(yàn)結(jié)果表明，相比于PBFT 算法，本文提出的GBFT 算法有效提高了區(qū)塊鏈網(wǎng)絡(luò)的吞吐量，降低了交易確認(rèn)時(shí)延，同時(shí)還保持了PBFT 算法的容錯(cuò)性。在GBFT 中，將信用分排名前50%的節(jié)點(diǎn)納入了共識(shí)節(jié)點(diǎn)集，這樣的設(shè)定可能無(wú)法適用于所有的應(yīng)用場(chǎng)景。下一步的工作中可以考慮將共識(shí)節(jié)點(diǎn)集的容量設(shè)置為一個(gè)可配置的參數(shù)，以靈活調(diào)整網(wǎng)絡(luò)的去中心化程度。