陳忠賢 李秦偉，2 羅婧雯

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 貴陽 550025）（2.貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室 貴陽 550025）

1 引言

共識(shí)問題是計(jì)算機(jī)科學(xué)領(lǐng)域的經(jīng)典問題，最早出現(xiàn)是在20個(gè)世紀(jì)80年代，Pease和Leslie Lamport對(duì)拜占庭將軍問題進(jìn)行了形式化的描述和分析［1～2］。自中本聰提出比特幣以來［3］，共識(shí)成為了區(qū)塊鏈系統(tǒng)中其中一個(gè)新的研究熱點(diǎn)［4～5］，目前，區(qū)塊鏈中主流的共識(shí)算法包括有工作量證明（PoW）［6］、股 權(quán) 證 明（PoS）［7～8］、委 任 權(quán) 益 證 明（DPoS）［9］、實(shí)用拜占庭容錯(cuò)算法（PBFT）［10］。工作量證明的思想最早來源于哈佛大學(xué)教授Cynthia Dwok［11］，其目的是為了通過郵件發(fā)送方計(jì)算一定難度的數(shù)學(xué)難題來增加垃圾郵件發(fā)送者的成本，從而解決垃圾郵件問題。在比特幣系統(tǒng)中，PoW主要應(yīng)用在數(shù)字貨幣系統(tǒng)中，旨在通過算力證明來獲得一個(gè)區(qū)塊的記賬權(quán)，從而換取獲得比特獎(jiǎng)勵(lì)的機(jī)會(huì)，這造成了為提高哈希計(jì)算而不斷優(yōu)化的挖礦設(shè)備的浪費(fèi)和大量的電力資源的消耗。PoS彌補(bǔ)了PoW的不足，使用股權(quán)機(jī)制來代替算力證明完成記賬節(jié)點(diǎn)的選取。目前，有Peercoin、NTX、Blackcoin使用了基于PoS思想的共識(shí)算法，但PoS也存在這樣一些問題：某些節(jié)點(diǎn)擁有大量的區(qū)塊鏈資產(chǎn)且長(zhǎng)期持有，這就可能造成股份分配不均，從而造成擁有大部分股權(quán)的節(jié)點(diǎn)壟斷出塊。2014年，雷恩（Larry Ren）提出PosV共識(shí)算法［12］，Slimcoin提出了PoB共識(shí)算法［13］。PosV與PoB算法既解決了PoW的能源消耗問題又規(guī)避了PoS的風(fēng)險(xiǎn)問題。DPoS對(duì)PoS中心化進(jìn)行了適當(dāng)妥協(xié)［6］，有效解決了PoW的純碎依靠算力以及PoS的首富賬戶的寡頭壟斷問題。但是DPoS對(duì)于惡意拜占庭節(jié)點(diǎn)的處理存在諸多困難。PBFT算法能容忍1/3的拜占庭節(jié)點(diǎn)，在性能上有著較好的表現(xiàn)，但三階段的大量消息廣播侵占有限帶寬從而影響執(zhí)行的效率。中國(guó)區(qū)塊鏈社區(qū)NEO提出了一種改進(jìn)的拜占庭容錯(cuò)算法DBFT［14］，該算法是一個(gè)PBFT與PoS算法的有機(jī)結(jié)合，首先根據(jù)節(jié)點(diǎn)的權(quán)益來選出一些記賬人，然后記賬人之間通過PBFT算法來達(dá)成共識(shí)。

上述常用的共識(shí)算法中，PoW和PoS是目前公有鏈［15］普遍采用的算法，PoW與PoS可拓展性良好，因?yàn)樾录尤氲墓?jié)點(diǎn)只要能提供算力證明或權(quán)益證明即可，但是兩者的吞吐量以及交易速度等眾多性能瓶頸使得很多應(yīng)用場(chǎng)景被限制。不論是PoW、PoS、DPoS亦或是其衍生算法，它們的共識(shí)機(jī)制都是依賴于代幣的，但國(guó)家法律法規(guī)不支持使用代幣。相比之下，PBFT實(shí)用拜占庭容錯(cuò)算法更適合作為服務(wù)平臺(tái)來搭建區(qū)塊鏈應(yīng)用。

1.1 相關(guān)工作

PBFT算法主要解決了缺少可信的中央節(jié)點(diǎn)和可信任的通道的情況下，分布在網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)如何達(dá)成共識(shí)的問題。PBFT是由Miguel Castro和Barbara Liskov在1999年的OSD199會(huì)議上提出來的，它改進(jìn)了拜占庭算法效率不高的問題，將算法復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)，使得拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)應(yīng)用中變得可行［6］。PBFT算法容錯(cuò)模型為3f+1，即當(dāng)存在f個(gè)錯(cuò)誤節(jié)點(diǎn)時(shí)，總節(jié)點(diǎn)數(shù)n≥3f+1時(shí)，拜占庭將軍問題可以被解決，其容錯(cuò)性為33%。但PBFT也存在這樣的問題：要實(shí)現(xiàn)節(jié)點(diǎn)之間的協(xié)商狀態(tài)一致，需要經(jīng)過三階段（預(yù)準(zhǔn)備階段、準(zhǔn)備階段、確認(rèn)階段）的節(jié)點(diǎn)間通信，其中有兩次全網(wǎng)全節(jié)點(diǎn)廣播，大量的消息廣播非常占用通信資源。其次，從PBFT算法流程可知，傳統(tǒng)的PBFT算法針對(duì)的是靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)。該算法中節(jié)點(diǎn)數(shù)目的增多可以增強(qiáng)系統(tǒng)的容錯(cuò)性，但PBFT算法不能夠動(dòng)態(tài)的感知節(jié)點(diǎn)的加入或者退出，那么就無法根據(jù)拜占庭節(jié)點(diǎn)數(shù)量和總結(jié)點(diǎn)數(shù)量進(jìn)行動(dòng)態(tài)變化，這無疑是浪費(fèi)了新加入節(jié)點(diǎn)的資源。

1.2 改進(jìn)方案

針對(duì)上一節(jié)提出的PBFT算法的不足，并根據(jù)文獻(xiàn)［16］，提出基于時(shí)間分組的GBFT算法，該算法主要從以下幾個(gè)方面進(jìn)行了優(yōu)化。

1）根據(jù)節(jié)點(diǎn)之間的通信時(shí)間分組分層進(jìn)行共識(shí)。

GBFT算法的實(shí)現(xiàn)通過分組、選舉、以及分層進(jìn)行共識(shí)?；谧疃掏ㄐ艜r(shí)間，將區(qū)塊鏈所有副本節(jié)點(diǎn)進(jìn)行分組，每個(gè)組都有一個(gè)組長(zhǎng)節(jié)點(diǎn)。首先各個(gè)組分別在組內(nèi)進(jìn)行三階段的共識(shí)，組內(nèi)共識(shí)依然嚴(yán)格遵循3f+1的原則，當(dāng)組內(nèi)各個(gè)節(jié)點(diǎn)收到的來自同一組不同節(jié)點(diǎn)的消息數(shù)為2f+1，即可進(jìn)入下一階段。在組內(nèi)共識(shí)完成后，各組組長(zhǎng)節(jié)點(diǎn)根據(jù)收到的消息執(zhí)行全局共識(shí)，全局共識(shí)的執(zhí)行過程和組內(nèi)共識(shí)基本一致，最終由率先收到滿足共識(shí)條件的組長(zhǎng)節(jié)點(diǎn)更新區(qū)塊鏈。

GBFT算法的改進(jìn)主要是通過減少節(jié)點(diǎn)之間的消息數(shù)來進(jìn)行改進(jìn)，組內(nèi)共識(shí)與全局共識(shí)依然遵循3f+1的容錯(cuò)模型，在效率提升的同時(shí)，也保證了安全性。

2）動(dòng)態(tài)感知節(jié)點(diǎn)的加入和離開，資源利用最大化。

通過節(jié)點(diǎn)探測(cè)可以實(shí)時(shí)根據(jù)在線節(jié)點(diǎn)數(shù)目，調(diào)整分組的組數(shù)和組員數(shù)量。為每個(gè)節(jié)點(diǎn)設(shè)立的評(píng)分表可以動(dòng)態(tài)刪除共識(shí)表現(xiàn)差的節(jié)點(diǎn)。

2 GBFT算法的設(shè)計(jì)與實(shí)現(xiàn)

2.1 算法定義

1）GBFT算法分為組內(nèi)共識(shí)與全局組長(zhǎng)節(jié)點(diǎn)之間的共識(shí)，令組Gj中最大能容忍惡意節(jié)點(diǎn)的數(shù)量為f1，令全局組長(zhǎng)節(jié)點(diǎn)中最大能容忍惡意節(jié)點(diǎn)的數(shù)量為f2，wj表示組Gj的組員個(gè)數(shù)，G表示所有組長(zhǎng)節(jié)點(diǎn)的數(shù)目，則有：

2）根據(jù)視圖編號(hào)v、當(dāng)前區(qū)塊高度h以及參與共識(shí)的節(jié)點(diǎn)總數(shù)n，可計(jì)算出主節(jié)點(diǎn)P，即：

2.2 分組

2.2.1 最優(yōu)分組

只考慮平均時(shí)延的情況下，使用共識(shí)過程中的交互消息數(shù)計(jì)算出最優(yōu)分組。

主節(jié)點(diǎn)發(fā)起提案ConsensusProposal發(fā)送消息數(shù)：

組內(nèi)準(zhǔn)備GroupedPrepare與組內(nèi)確認(rèn)Grouped-Commit發(fā)送消息數(shù)：

wj表示組Gj的組員個(gè)數(shù)，G為組數(shù)。

全局共識(shí)GlobalPrepare與GlobalCommit階段共發(fā)送消息數(shù)：

由式（4）、（5）、（6）相加整理得到：

s為方差，由式（7）可看出，當(dāng)s=0時(shí)，即平均分組時(shí)，MGBFT可以得到最小值。所以得到：

式（8）兩邊同時(shí)對(duì)G求導(dǎo)得到：

由式（9）可知，當(dāng)n與G滿足=0時(shí)，MGBFT最小，即所發(fā)送的消息數(shù)最少。

2.2.2 節(jié)點(diǎn)探測(cè)階段

假設(shè)在整個(gè)區(qū)塊鏈網(wǎng)絡(luò)最初啟動(dòng)時(shí)，全網(wǎng)節(jié)點(diǎn)都處于孤立節(jié)點(diǎn)狀態(tài)。首先給區(qū)塊鏈網(wǎng)絡(luò)內(nèi)所有在線的參與共識(shí)的副本節(jié)點(diǎn)編號(hào)，用｛1，2，3…n｝表示各個(gè)副本節(jié)點(diǎn)的ID，參與共識(shí)算法的記賬代表節(jié)點(diǎn)從ID號(hào)最小的節(jié)點(diǎn)開始，向比自己ID號(hào)大的節(jié)點(diǎn)發(fā)送探測(cè)消息＜DET ECT，status，self，t1＞，sel f包含節(jié)點(diǎn)自身信息，包括IP地址等信息，st at us字段有兩個(gè)不同的狀態(tài)，1表示請(qǐng)求計(jì)算通信時(shí)間的信息，2表示對(duì)請(qǐng)求信息的響應(yīng)。t1為發(fā)送消息時(shí)區(qū)塊鏈網(wǎng)絡(luò)上的時(shí)間。其余共識(shí)節(jié)點(diǎn)在收到來自Ri的探測(cè)消息后，以區(qū)塊鏈網(wǎng)絡(luò)時(shí)間為標(biāo)準(zhǔn)，記錄收到消息的時(shí)間t2，計(jì)算Ri與Rj之間的通信時(shí)間Tij=t2-t1，之后回復(fù)消息給相應(yīng)的共識(shí)節(jié)點(diǎn)Ri，消 息 格 式 為＜D ET ECT-REP LY，status，self，Tij，t1＞，此時(shí)status置為2，表示對(duì)收到的消息進(jìn)行回復(fù)。同樣的Ri也會(huì)根據(jù)來自Rj的探測(cè)回復(fù)消息計(jì)算出Ti'j=t2-t1，Ri根據(jù)自己計(jì)算出的與來自Ri計(jì)算的Tij計(jì)算Ri與Rj平均通信時(shí)間=(Ti'j+Tij)/2，并將計(jì)算出來的記錄在由共識(shí)節(jié)點(diǎn)組成的鄰接表中。

等待節(jié)點(diǎn)Ri完成自己的鄰接表后，向Ri之前的i-1個(gè)節(jié)點(diǎn)以及下一個(gè)節(jié)點(diǎn)Ri+1發(fā)送消息＜C OM M U N IC AT IO N-T IM E，sel f，sch ed ule＞，schedule表示由Ri更新后的通信時(shí)間鄰接表，前i-1個(gè)已經(jīng)完成節(jié)點(diǎn)探測(cè)的節(jié)點(diǎn)根據(jù)后續(xù)節(jié)點(diǎn)發(fā)送的消息，更新各自的鄰接表，下一個(gè)節(jié)點(diǎn)Ri+1除了保存由上一個(gè)節(jié)點(diǎn)Ri發(fā)送的鄰接表，還要向比自己ID號(hào)小的節(jié)點(diǎn)發(fā)送探測(cè)消息，也就是重復(fù)Ri節(jié)點(diǎn)的操作，直到節(jié)點(diǎn)Rn-1完成探測(cè)并將更新后的鄰接表廣播，則區(qū)塊鏈網(wǎng)絡(luò)內(nèi)已經(jīng)建立一個(gè)由各個(gè)節(jié)點(diǎn)組成的通信時(shí)間表。

算法中，為每個(gè)節(jié)點(diǎn)設(shè)置評(píng)分，初始評(píng)分設(shè)置為0分。

2.2.3 平均時(shí)延估計(jì)

各個(gè)共識(shí)節(jié)點(diǎn)Ri根據(jù)鄰接表的值，計(jì)算出平均通信時(shí)延。平均時(shí)延的估計(jì)，是為了在后續(xù)分組中，將分散的節(jié)點(diǎn)分為多個(gè)通信時(shí)間基本一致的組。根據(jù)計(jì)算出的平均時(shí)延，各個(gè)節(jié)點(diǎn)分別統(tǒng)計(jì)在平均時(shí)延以內(nèi)的節(jié)點(diǎn)編號(hào)數(shù)量di、節(jié)點(diǎn)編號(hào)Ri和通信時(shí)間，并根據(jù)通信時(shí)間升序。

2.2.4 分組形成階段

根據(jù)公式計(jì)算出的主節(jié)點(diǎn)P在給定的共識(shí)時(shí)間間隔Δtc，發(fā)起一輪新的共識(shí)。由主節(jié)點(diǎn)啟動(dòng)快速分組協(xié)議，按照以下五個(gè)步驟進(jìn)行分組。

步驟1：根據(jù)全網(wǎng)共識(shí)節(jié)點(diǎn)的數(shù)目計(jì)算出最優(yōu)分組的組數(shù)G和最佳組員人數(shù)W，G和W的值由上一節(jié)介紹的最優(yōu)分組中式（6）決定。

步驟2：凡是滿足di≥W的節(jié)點(diǎn)為擬組長(zhǎng)節(jié)點(diǎn)（擬組長(zhǎng)節(jié)點(diǎn)是尚未組建成功的節(jié)點(diǎn)，若成功組建則成為組長(zhǎng)節(jié)點(diǎn)），各個(gè)擬組長(zhǎng)節(jié)點(diǎn)開始根據(jù)鄰接表選取組員，將選取的節(jié)點(diǎn)添加到分組向量表chosen中，向選擇的組員節(jié)點(diǎn)發(fā)送消息＜Q UI C KG R OU P，sel f，fl ag，ID＞σi，self包含節(jié)點(diǎn)自身信息，包括IP地址，節(jié)點(diǎn)編號(hào)等，fla g置1表示組長(zhǎng)節(jié)點(diǎn)。選取組員滿足以下幾個(gè)規(guī)則。

規(guī)則1：di最小的擬組長(zhǎng)節(jié)點(diǎn)Ri為第一組G1的組長(zhǎng)節(jié)點(diǎn)首先選取組員，若多個(gè)節(jié)點(diǎn)的di相同，則由ID號(hào)最小的節(jié)點(diǎn)優(yōu)先分組。

規(guī)則2：Ri將通信時(shí)間在以內(nèi)的前W-1個(gè)的節(jié)點(diǎn)選為組員，被選取的節(jié)點(diǎn)不再參與下一輪的選取。

規(guī)則3：若共識(shí)節(jié)點(diǎn)Ri的鄰接表里在平均通訊時(shí)延以內(nèi)的節(jié)點(diǎn)不足W-1個(gè)，則依次順延至下一個(gè)擬組長(zhǎng)節(jié)點(diǎn)。

規(guī)則4：若根據(jù)規(guī)則3遍歷整個(gè)擬組長(zhǎng)節(jié)點(diǎn)，仍不能組建組員通信時(shí)間在以內(nèi)且人數(shù)為W的組，則Ri根據(jù)鄰接表選取通信時(shí)間為前W-1個(gè)節(jié)點(diǎn)作為組員。

步驟3：組員節(jié)點(diǎn)收到QUICK-GROUP后，解密驗(yàn)證，看到組長(zhǎng)節(jié)點(diǎn)發(fā)送的消息fla g的值為1，表示組長(zhǎng)節(jié)點(diǎn)在選舉組員，立即根據(jù)self的值作出回復(fù)，向組長(zhǎng)節(jié)點(diǎn)回復(fù)消息＜GROUPRE P L Y，self，flag，ID＞σi，fl ag置0表示為非組長(zhǎng)節(jié)點(diǎn)。

分組的最終結(jié)果是形成以組長(zhǎng)節(jié)點(diǎn)為中心的多個(gè)圓簇，每個(gè)組長(zhǎng)節(jié)點(diǎn)負(fù)責(zé)維護(hù)組內(nèi)成員。

圖2 分組形成過程

2.2.5 重新分組

每次共識(shí)的發(fā)起都有一定的時(shí)間間隔，共識(shí)的時(shí)間間隔根據(jù)區(qū)塊鏈網(wǎng)絡(luò)內(nèi)的交易數(shù)據(jù)來決定，但并不是每次共識(shí)都會(huì)發(fā)起一次分組協(xié)議。重新分組主要考慮以下幾個(gè)方面。

1）拜占庭節(jié)點(diǎn)增多

每個(gè)組設(shè)立一個(gè)拜占庭區(qū)，通過組內(nèi)共識(shí)，組內(nèi)每個(gè)節(jié)點(diǎn)都可以知道哪些節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，將拜占庭節(jié)點(diǎn)添加至拜占庭區(qū)，當(dāng)某一組的拜占庭區(qū)的節(jié)點(diǎn)數(shù)目多于f1，則認(rèn)為這個(gè)組宕機(jī)，這個(gè)組的所有節(jié)點(diǎn)不再參與到組內(nèi)共識(shí)與全局共識(shí)當(dāng)中，組內(nèi)非拜占庭節(jié)點(diǎn)向區(qū)塊鏈網(wǎng)絡(luò)內(nèi)其他節(jié)點(diǎn)廣播宕機(jī)消息＜DOWN-ME S S AG E，sel f＞σi，其余節(jié)點(diǎn)根據(jù)監(jiān)測(cè)到的消息將宕機(jī)的整個(gè)組的組員添加至拜占庭區(qū)，當(dāng)拜占庭區(qū)的組數(shù)大于f2時(shí)，則需重新進(jìn)行分組。

如果某一個(gè)組Gj的組長(zhǎng)節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，而Gj組的拜占庭區(qū)的節(jié)點(diǎn)數(shù)目少于f1，Gj組仍可以繼續(xù)參與共識(shí)，此時(shí)由除拜占庭節(jié)點(diǎn)外評(píng)分最高的節(jié)點(diǎn)擔(dān)任組長(zhǎng)節(jié)點(diǎn)，若分?jǐn)?shù)相同，則取ID號(hào)最小的節(jié)點(diǎn)擔(dān)任，并向其余組長(zhǎng)節(jié)點(diǎn)廣播變更消息＜GROUP-C HA N G E，self，chosen＞σi，這里chosen僅為Gj組的組員向量表。

2）節(jié)點(diǎn)的加入

當(dāng)有新的節(jié)點(diǎn)加入共識(shí)，新加入節(jié)點(diǎn)需要向全網(wǎng)發(fā)送探測(cè)消息，在收到新節(jié)點(diǎn)的探測(cè)消息后向新節(jié)點(diǎn)發(fā)送通信時(shí)間鄰接表sch edule，新加入節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)探測(cè)階段所描述的方法計(jì)算平均通信時(shí)延以及更新鄰接表schedule，并將新的鄰接表廣播至全網(wǎng)。每次當(dāng)有新的節(jié)點(diǎn)加入，則由主節(jié)點(diǎn)發(fā)起新一輪的快速分組協(xié)議。

2.3 共識(shí)

我們定義主節(jié)點(diǎn)作為一次共識(shí)的發(fā)起者，如同比特幣網(wǎng)絡(luò)中，通過調(diào)節(jié)難度控制出塊時(shí)間為10min，我們可以根據(jù)區(qū)塊鏈網(wǎng)絡(luò)的交易數(shù)量，調(diào)控主節(jié)點(diǎn)發(fā)起一次共識(shí)的時(shí)間間隔。在整個(gè)區(qū)塊鏈網(wǎng)絡(luò)中，所有的共識(shí)節(jié)點(diǎn)都有可能是最終的記賬節(jié)點(diǎn)，所以不僅參與共識(shí)也要保存區(qū)塊鏈數(shù)據(jù)。當(dāng)收到交易數(shù)據(jù)，所有共識(shí)節(jié)點(diǎn)驗(yàn)證交易合法性，將通過驗(yàn)證的交易數(shù)據(jù)添加至自己的內(nèi)存中并根據(jù)前一區(qū)塊的哈希索引、版本號(hào)、區(qū)塊高度等信息構(gòu)造一個(gè)候選區(qū)塊，并廣播至其他共識(shí)節(jié)點(diǎn)，不合法則直接丟棄，這確保了只有有效的交易才能在區(qū)塊鏈網(wǎng)絡(luò)中傳播。

1）主節(jié)點(diǎn)P向所有副本節(jié)點(diǎn)發(fā)起共識(shí)提案，消息格式為＜C O NSE N S US-P RO P OSA L，v，n，h，d，self＞σi，b l ock，t1＞，v為當(dāng)前視圖編號(hào)，n為在當(dāng)前視圖編號(hào)下主節(jié)點(diǎn)分配的序列號(hào)，h為當(dāng)前區(qū)塊的高度，block為請(qǐng)求的區(qū)塊信息，d為block的摘要，t1為時(shí)間戳，目的是為了計(jì)算通信時(shí)延，不斷更新鄰接表。

其余的副本節(jié)點(diǎn)收到來自P的共識(shí)提案后，驗(yàn)證簽名、檢查提案、h的值、n的值是否在水線范圍內(nèi)。若為真，則進(jìn)入組內(nèi)共識(shí)階段。若發(fā)現(xiàn)提案為假或在超過共識(shí)間隔時(shí)間后仍未發(fā)起共識(shí)提案，備份節(jié)點(diǎn)懷疑主節(jié)點(diǎn)失效，則進(jìn)行視圖變更。詳細(xì)的變更細(xì)節(jié)在文章的后續(xù)做出介紹。

5）與全局準(zhǔn)備階段一致，組長(zhǎng)節(jié)點(diǎn)間互發(fā)確認(rèn)消 息＜GL OB A L-C O M MIT，v，n，h，d，self，t1＞σi，當(dāng)組長(zhǎng)節(jié)點(diǎn)中的任意一個(gè)在收到來自2f2+1個(gè)其他組長(zhǎng)的相同確認(rèn)消息后，即認(rèn)為共識(shí)達(dá)成，可以發(fā)布來自主節(jié)點(diǎn)提案的區(qū)塊block。

6）其余節(jié)點(diǎn)根據(jù)最新的區(qū)塊，將自己內(nèi)存中的與區(qū)塊block中相同的交易刪除，同時(shí)開始構(gòu)造新的區(qū)塊，準(zhǔn)備下一輪的共識(shí)。

算法中，產(chǎn)生區(qū)塊的節(jié)點(diǎn)評(píng)分score加1分，若主節(jié)點(diǎn)被副本節(jié)點(diǎn)懷疑，引發(fā)視圖變更，若變更成功，則主節(jié)點(diǎn)score減2分，該備份節(jié)點(diǎn)score加1分。

整個(gè)算法的共識(shí)過成如圖3所示。

圖3 GBFT算法流程

2.3.1 鄰接表更新

鄰接表建立之后并不是一成不變的，除了節(jié)點(diǎn)的加入和退出需要變更鄰接表外，組內(nèi)共識(shí)和全局共識(shí)動(dòng)態(tài)更新部分的鄰接表的通信時(shí)間。

組內(nèi)共識(shí)以及全局共識(shí)的消息都包含時(shí)間戳，根據(jù)節(jié)點(diǎn)探測(cè)一節(jié)介紹的通信時(shí)間的計(jì)算方法，每次收到共識(shí)階段內(nèi)的消息后自動(dòng)計(jì)算傳播時(shí)間并記錄，待一輪共識(shí)完成后，將所有收集到的消息的通信時(shí)間累加并取平均值，將計(jì)算出的值填入鄰接表的對(duì)應(yīng)位置。

2.3.2 組長(zhǎng)節(jié)點(diǎn)的輪換

我們?yōu)槊總€(gè)共識(shí)節(jié)點(diǎn)都設(shè)置了評(píng)分score，在GBFT算法中，根據(jù)評(píng)分建立一個(gè)忠誠(chéng)度表1。

表1 忠誠(chéng)度計(jì)算方法

每個(gè)節(jié)點(diǎn)計(jì)算出各自的忠誠(chéng)度c：

c的計(jì)算是綜合了score與擔(dān)任組長(zhǎng)次數(shù)t的結(jié)果，平衡每個(gè)節(jié)點(diǎn)成為組長(zhǎng)節(jié)點(diǎn)的幾率，避免分?jǐn)?shù)高的節(jié)點(diǎn)長(zhǎng)期擔(dān)任組長(zhǎng)。α與β為調(diào)節(jié)系數(shù)。c的值最高的成為下一輪次的組長(zhǎng)節(jié)點(diǎn)。

2.3.3 視圖變更

當(dāng)備份節(jié)點(diǎn)懷疑主節(jié)點(diǎn)或者在共識(shí)間隔時(shí)間Δtc后仍未發(fā)起新的共識(shí)，則由懷疑主節(jié)點(diǎn)的備份節(jié)點(diǎn)或隨機(jī)選取的備份節(jié)點(diǎn)發(fā)起視圖變更消息，具體的變更流程如下。

1）令新的視圖vnew=vold+1，假設(shè)由備份節(jié)點(diǎn)Ri向全網(wǎng)發(fā)送視圖變更消息＜V IEW-C H A N GE，vold，vnew，h，Ri＞σi。

2）其余備份節(jié)點(diǎn)收到視圖變更消息后，驗(yàn)證消息的簽名、vold以及h的值是否為真，若為真，則拒絕主節(jié)點(diǎn)的共識(shí)提案并向全網(wǎng)廣播視圖變更確認(rèn) 消 息＜V IE W-CH A N GE-C ON FIR M，vold，vnew，h＞σi。

3）任何一個(gè)節(jié)點(diǎn)如果收到來自其他（2n-1）/3條圖變更確認(rèn)消息后，視圖變更得到確認(rèn)，新的視圖編號(hào)變?yōu)関new。新的主節(jié)點(diǎn)開始下一輪的共識(shí)提案。

3 實(shí)驗(yàn)?zāi)M與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

本算法的基礎(chǔ)是分布式系統(tǒng)，即需要在多個(gè)節(jié)點(diǎn)下運(yùn)行，為模擬出大量的分布式節(jié)點(diǎn)的計(jì)算，有如下設(shè)計(jì)。

1）共識(shí)節(jié)點(diǎn)：以進(jìn)程來模擬共識(shí)節(jié)點(diǎn)，共識(shí)節(jié)點(diǎn)的端口號(hào)分布在10001～20000之間，共識(shí)節(jié)點(diǎn)是整個(gè)系統(tǒng)的關(guān)鍵，負(fù)責(zé)交易和區(qū)塊的共識(shí)確認(rèn)。

2）交易產(chǎn)生節(jié)點(diǎn)：以進(jìn)程來模擬交易節(jié)點(diǎn)，一個(gè)進(jìn)程一個(gè)交易節(jié)點(diǎn)，每個(gè)進(jìn)程擁有不同的的端口號(hào)，端口號(hào)分布在20001～30000之間，交易節(jié)點(diǎn)主要負(fù)責(zé)交易數(shù)據(jù)的模擬，以最快的速度生產(chǎn)交易信息并發(fā)送給共識(shí)節(jié)點(diǎn)。

3）由于共識(shí)節(jié)點(diǎn)是在同一局域網(wǎng)下一臺(tái)或多臺(tái)電腦上進(jìn)行模擬，為了更好地驗(yàn)證算法的有效性，用隨機(jī)函數(shù)事先生成一個(gè)n×n的對(duì)稱矩陣模擬通信延遲時(shí)間。

4）整個(gè)區(qū)塊鏈系統(tǒng)采用Python語言編寫，搭建了Linux操作系統(tǒng)環(huán)境，用腳本語言開啟多個(gè)進(jìn)程。本實(shí)驗(yàn)以PBFT算法作為對(duì)照，分別對(duì)99個(gè)、216個(gè)、336個(gè)、420個(gè)、512個(gè)節(jié)點(diǎn)進(jìn)行改進(jìn)共識(shí)算法GBFT的時(shí)間測(cè)試。實(shí)驗(yàn)中，各個(gè)進(jìn)程依次開啟，開始執(zhí)行GBFT算法。針對(duì)不同數(shù)量的共識(shí)節(jié)點(diǎn)，我們各測(cè)試10次，取10次的平均值來作為最后的結(jié)果。

3.2 運(yùn)行效率分析

GBFT設(shè)計(jì)的目的就是為了提高區(qū)塊鏈系統(tǒng)運(yùn)行的效率。以PBFT算法作為對(duì)照，分別對(duì)99個(gè)、130個(gè)、176個(gè)、216個(gè)、273個(gè)、350個(gè)節(jié)點(diǎn)進(jìn)行PBFT算法、GBFT算法的時(shí)間測(cè)試。測(cè)試結(jié)果如圖4所示。

圖4 不同節(jié)點(diǎn)數(shù)PBFT與GBFT共識(shí)時(shí)間折線圖

從圖4知隨著共識(shí)體系中節(jié)點(diǎn)數(shù)量不斷的增加，GBFT的效率提升越明顯。

3.3 吞吐量

區(qū)塊鏈應(yīng)用中對(duì)于吞吐量的定義是：

其中，Δt為交易發(fā)出到區(qū)塊確認(rèn)的時(shí)間，即出塊時(shí)間，transacti on為Δt時(shí)間段內(nèi)打包進(jìn)區(qū)塊的交易數(shù)。

實(shí)驗(yàn)對(duì)PBFT算法以及GBFT算法，統(tǒng)計(jì)1000條交易所花費(fèi)的共識(shí)時(shí)間，根據(jù)式（11），計(jì)算出吞吐量，如圖5是PBFT算法與GBFT算法的吞吐量折線圖。

圖5 PBFT與GBFT吞吐量折線圖

從吞吐量折線圖可知，PBFT算法與GBFT算法的吞吐量與參與共識(shí)的節(jié)點(diǎn)數(shù)成反比，節(jié)點(diǎn)越多，吞吐量越低。但在相同節(jié)點(diǎn)數(shù)量的情況下GBFT算法的吞吐量是遠(yuǎn)高于PBFT算法的。

3.4 安全性分析

1）主節(jié)點(diǎn)的選取根據(jù)視圖編號(hào)和區(qū)塊高度計(jì)算所得，而組長(zhǎng)節(jié)點(diǎn)的選取根據(jù)最小ID號(hào)，兩者的選取都具有隨機(jī)性和公平性。

2）由主節(jié)點(diǎn)P發(fā)起的快速分組并不是說全網(wǎng)的副本節(jié)點(diǎn)全部由主節(jié)點(diǎn)安排分組，而是根據(jù)節(jié)點(diǎn)探測(cè)階段所統(tǒng)計(jì)的通信時(shí)間以及隨機(jī)ID號(hào)進(jìn)行分組，這個(gè)組要獲得最大利益就會(huì)根據(jù)鄰接表選擇通信時(shí)間最短的成為組員，這樣不僅可以防止主節(jié)點(diǎn)成為拜占庭節(jié)點(diǎn)后安排最差的分組，而且可以提高節(jié)點(diǎn)間的通信時(shí)間。

3）GBFT共識(shí)算法的實(shí)質(zhì)是將PBFT算法分解為組內(nèi)共識(shí)與全局共識(shí)兩個(gè)階段，共識(shí)協(xié)議和試圖更換的核心并沒有改變，依然嚴(yán)格遵循3f+1的模型。

4）每個(gè)組設(shè)立拜占庭區(qū)，且每個(gè)節(jié)點(diǎn)都獨(dú)立監(jiān)聽其余節(jié)點(diǎn)的狀態(tài)，根據(jù)最大容仍失效節(jié)點(diǎn)的數(shù)目動(dòng)態(tài)調(diào)整算法，當(dāng)拜占庭節(jié)點(diǎn)數(shù)大于f個(gè)，則觸發(fā)重新分組協(xié)議。

5）信用評(píng)分協(xié)議與組長(zhǎng)更換協(xié)議使得各個(gè)節(jié)點(diǎn)成為組長(zhǎng)節(jié)點(diǎn)的機(jī)會(huì)均等，滿足區(qū)塊鏈去中心以及節(jié)點(diǎn)間對(duì)等的特性。

4 結(jié)語

針對(duì)區(qū)塊鏈共識(shí)算法中的實(shí)用拜占庭容錯(cuò)算法表現(xiàn)出的由于大量的消息廣播造成的通信資源浪費(fèi)和效率低下問題，提出基于通信時(shí)間分組分層算法。在分組形成前，采用節(jié)點(diǎn)探測(cè)獲知共識(shí)節(jié)點(diǎn)的“地理位置”——構(gòu)建一個(gè)通信時(shí)間對(duì)稱矩陣，根據(jù)通信時(shí)間對(duì)稱矩陣將節(jié)點(diǎn)分成多個(gè)以組長(zhǎng)節(jié)點(diǎn)為中心，平均通信時(shí)延為半徑的圓。在組保持階段，根據(jù)節(jié)點(diǎn)的行為進(jìn)行信用評(píng)分與組長(zhǎng)更換，使得所有節(jié)點(diǎn)成為組長(zhǎng)節(jié)點(diǎn)的概率盡可能均等。整個(gè)共識(shí)算法可以通過節(jié)點(diǎn)探測(cè)動(dòng)態(tài)感知新加入節(jié)點(diǎn)，拜占庭區(qū)的設(shè)立感知失效節(jié)點(diǎn)，從而確定是自適應(yīng)調(diào)整共識(shí)還是調(diào)整分組結(jié)構(gòu)。仿真表明，本文算法很好地解決了PBFT算大的通信資源消耗和效率低下問題。