王 森 李志淮 賈志鵬

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116002)

0 引 言

2008年中本聰(Satoshi Nakamoto)發(fā)表了比特幣的基礎(chǔ)論文[1]，闡述了基于P2P網(wǎng)絡(luò)技術(shù)[2]、加密技術(shù)、時間戳技術(shù)、共識算法等的電子現(xiàn)金系統(tǒng)的構(gòu)架理念，這標(biāo)志著比特幣的誕生。同時也是區(qū)塊鏈這個詞的首次提出，它本質(zhì)上是一個分布式系統(tǒng)[3]，該系統(tǒng)具有去中心化、分布式和數(shù)據(jù)不可篡改等特點(diǎn)，可以解決現(xiàn)有的中心化信用機(jī)構(gòu)的效率低、成本高和數(shù)據(jù)所有權(quán)被壟斷的問題。區(qū)塊鏈技術(shù)被認(rèn)為是移動互聯(lián)網(wǎng)之后新的信息技術(shù)發(fā)展方向[4]，將促進(jìn)信用社會的建立，促使目前的信息互聯(lián)網(wǎng)向價值互聯(lián)網(wǎng)轉(zhuǎn)變。隨著區(qū)塊鏈技術(shù)的發(fā)展，共識算法方面的研究也越來越多，共識算法用于在分布式系統(tǒng)中實(shí)現(xiàn)可用性和一致性，是區(qū)塊鏈的關(guān)鍵技術(shù)[5]。

共識算法的研究在區(qū)塊鏈技術(shù)提出之前就開始了，Pease和Lamport在1980年提出的拜占庭容錯(BFT)算法[6-7]，分析了如何在有惡意節(jié)點(diǎn)或者網(wǎng)絡(luò)堵塞問題的點(diǎn)對點(diǎn)網(wǎng)絡(luò)中，實(shí)現(xiàn)數(shù)據(jù)完整性和一致性。

PBFT(Practical Byzantine Fault Tolerance)共識算法[8-9]是Castro等基于BFT算法改進(jìn)的，用于解決當(dāng)前聯(lián)盟區(qū)塊鏈環(huán)境中分布式系統(tǒng)的共識問題，PBFT算法不僅繼承了BFT算法可以容忍拜占庭節(jié)點(diǎn)的優(yōu)點(diǎn)，并且把BFT算法中通信復(fù)雜度從O(n3)降低到了O(n2)。但是PBFT共識算法在某些方面還存在著不足。首先，PBFT算法中主節(jié)點(diǎn)的選取方式是按照編號輪流擔(dān)當(dāng)主節(jié)點(diǎn)，這種主節(jié)點(diǎn)的選取方式容易受到P2P網(wǎng)絡(luò)中的DDoS攻擊和女巫攻擊，具有安全隱患，雖然在當(dāng)拜占庭節(jié)點(diǎn)沒有達(dá)到總節(jié)點(diǎn)數(shù)目的2/3時會被其他從節(jié)點(diǎn)識破，并通過視圖切換更換主節(jié)點(diǎn)，但是頻繁的視圖切換會增加系統(tǒng)開銷，影響系統(tǒng)的性能；其次，在PBFT共識算法的三階段廣播過程，需要進(jìn)行兩次通信開銷極大的全網(wǎng)轉(zhuǎn)發(fā)，嚴(yán)重影響PBFT算法共識過程中的性能；最后，PBFT共識算法節(jié)點(diǎn)不能隨意加入、退出，影響系統(tǒng)可用性。

本文針對現(xiàn)有PBFT算法中主節(jié)點(diǎn)選取方式隨意、三階段協(xié)議通信復(fù)雜度較高、節(jié)點(diǎn)不能動態(tài)加入、退出等問題，提出了一種主節(jié)點(diǎn)隨機(jī)選取的改進(jìn)拜占庭容錯算法(RPBFT)。該算法提出了一種隨機(jī)數(shù)生成方案，生成一個隨機(jī)數(shù)來進(jìn)行主節(jié)點(diǎn)的選取，并且引入聚合簽名算法[10-11]對PBFT中的三階段協(xié)議進(jìn)行改進(jìn)，成功地把通信復(fù)雜度從多項式級別降低到了線性級別，減少網(wǎng)絡(luò)壓力和延遲，提高系統(tǒng)吞吐量，同時節(jié)點(diǎn)可以動態(tài)加入與退出系統(tǒng)，增強(qiáng)系統(tǒng)的可用性。

1 相關(guān)研究與技術(shù)分析

1.1 聚合簽名

聚合簽名(Aggregate Signature)[10-11]的概念是在2003年由Boneh提出的，聚合簽名就是一種用來將多個簽名聚合成一個簽名的方案，假設(shè)系統(tǒng)中有n個用戶ui(1≤i≤n)分別對n個不同的消息進(jìn)行簽名，生成n個不同的簽名，這n個簽名可以被聚合者聚合成一個簽名，而驗證者只需要對生成的聚合簽名進(jìn)行檢驗就可以確認(rèn)上述n個簽名的正確性。聚合簽名方案可以將n個簽名聚合成一個簽名，縮短了簽名的長度；同時，可以將n次的驗證過程簡化為一次驗證就可完成，降低了系統(tǒng)的帶寬，減少了驗證時間，提升了系統(tǒng)的計算效率。

1.2 PBFT算法思想與流程

1.2.1PBFT算法思想

PBFT共識算法旨在解決當(dāng)整個網(wǎng)絡(luò)中存在惡意節(jié)點(diǎn)時，仍然可以保證最終一致性和正確性的問題。算法中的大多數(shù)誠實(shí)節(jié)點(diǎn)都會忽略惡意節(jié)點(diǎn)發(fā)送的錯誤信息，能容忍失效節(jié)點(diǎn)和惡意節(jié)點(diǎn)的數(shù)量不超過(|R|-1)/3(|R|為節(jié)點(diǎn)個數(shù))，并且達(dá)成最終一致性。PBFT共識算法中，節(jié)點(diǎn)被分成客戶端節(jié)點(diǎn)和副本節(jié)點(diǎn)，副本節(jié)點(diǎn)又包括主節(jié)點(diǎn)和從節(jié)點(diǎn)。

副本節(jié)點(diǎn)組成的集合用R表示，系統(tǒng)中可以容忍的失效節(jié)點(diǎn)和惡意節(jié)點(diǎn)最多為f，另外還需要2f+1個誠實(shí)節(jié)點(diǎn)，所以系統(tǒng)的副本節(jié)點(diǎn)總數(shù)為|R|=3f+1，用0到|R|-1對節(jié)點(diǎn)進(jìn)行編號。PBFT算法共識過程是在視圖中進(jìn)行，所以主節(jié)點(diǎn)的選取是通過視圖編號和副本節(jié)點(diǎn)集合來確定的，主節(jié)點(diǎn)選取公式如下：

p=vmod |R|

(1)

式中：v是視圖編號；|R|為節(jié)點(diǎn)個數(shù)；p為選取的主節(jié)點(diǎn)編號。當(dāng)主節(jié)點(diǎn)網(wǎng)絡(luò)延遲失效或者被從節(jié)點(diǎn)發(fā)現(xiàn)為拜占庭節(jié)點(diǎn)時，就會啟動視圖更換協(xié)議，并且根據(jù)式(1)選取新的主節(jié)點(diǎn)。

1.2.2PBFT算法流程

PBFT共識算法要求系統(tǒng)共同維護(hù)一個狀態(tài)，所有節(jié)點(diǎn)采取的行動一致。為此，需要運(yùn)行一些基本協(xié)議，主要包括一致性協(xié)議和視圖更換協(xié)議。其中一致性協(xié)議包含5個階段：請求(request)、預(yù)準(zhǔn)備(pre-prepare)、準(zhǔn)備(prepare)、確認(rèn)(commit)和響應(yīng)(reply)。具體流程如圖1所示。

主節(jié)點(diǎn)在接收到客戶端節(jié)點(diǎn)發(fā)送的請求提案后，廣播該提案消息到全網(wǎng)的從節(jié)點(diǎn)，從節(jié)點(diǎn)接收到主節(jié)點(diǎn)的消息并執(zhí)行，再通過prepare和commit階段，將執(zhí)行結(jié)果發(fā)送給客戶端節(jié)點(diǎn)，客戶端節(jié)點(diǎn)等待至少f+1個相同的結(jié)果，表示該系統(tǒng)在這個請求上達(dá)成最終一致性。若沒有得到f+1個相同的結(jié)果，對提案進(jìn)行舍棄，客戶端節(jié)點(diǎn)自行判斷是否需要重新提交。

1.2.3視圖更換協(xié)議

視圖更換協(xié)議可以在主節(jié)點(diǎn)失效的時候保證系統(tǒng)的活性，視圖更換協(xié)議一般由超時機(jī)制觸發(fā)，以防止客戶端或從節(jié)點(diǎn)一直等待請求的執(zhí)行。從節(jié)點(diǎn)在接收到有效請求時，會啟動計時器并且會等待請求執(zhí)行的結(jié)果，當(dāng)請求被執(zhí)行時就停止計時器。計時器超時，從節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播視圖更換消息，根據(jù)式(1)選取下一視圖的主節(jié)點(diǎn)，當(dāng)主節(jié)點(diǎn)接收到2f個有效的視圖更換確認(rèn)的消息后，進(jìn)入下一視圖。

1.3 PBFT算法問題分析

根據(jù)上一節(jié)對PBFT算法流程進(jìn)行詳細(xì)的分析，可以看出現(xiàn)有PBFT算法具有以下幾點(diǎn)問題：

1) 由PBFT算法思想中的主節(jié)點(diǎn)選取公式可知，當(dāng)發(fā)生視圖更換時，新的主節(jié)點(diǎn)編號為當(dāng)前失效主節(jié)點(diǎn)的編號+1，這種主節(jié)點(diǎn)的選取策略存在一定的問題，拜占庭節(jié)點(diǎn)可以對在自己編號之前的副本節(jié)點(diǎn)進(jìn)行拒絕服務(wù)攻擊，使在自己編號之前的副本節(jié)點(diǎn)失效，達(dá)到當(dāng)選主節(jié)點(diǎn)的目的，具體示意圖如圖2所示。

其中黑色節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，白色節(jié)點(diǎn)為誠實(shí)節(jié)點(diǎn)，當(dāng)主節(jié)點(diǎn)編號與拜占庭節(jié)點(diǎn)接近時，拜占庭節(jié)點(diǎn)就可以對主節(jié)點(diǎn)以及自身編號之前的節(jié)點(diǎn)進(jìn)行拒絕服務(wù)攻擊，例如圖2的4號節(jié)點(diǎn)分別對編號為1、2、3號的節(jié)點(diǎn)進(jìn)行攻擊，就可以造成連續(xù)的視圖更換，使4號節(jié)點(diǎn)當(dāng)選主節(jié)點(diǎn)，達(dá)到作惡的目的。但是，由于拒絕服務(wù)攻擊是需要成本的，所以作惡節(jié)點(diǎn)不會在與主節(jié)點(diǎn)編號差距過大時發(fā)動攻擊。由于在攻擊過程中進(jìn)行了多次的視圖更換，造成了大量的通信開銷，嚴(yán)重影響了系統(tǒng)的可用性。

2) 在PBFT算法的三階段廣播協(xié)議中，有兩次消息的全網(wǎng)轉(zhuǎn)發(fā)，嚴(yán)重占用系統(tǒng)帶寬，造成系統(tǒng)堵塞，當(dāng)節(jié)點(diǎn)數(shù)目增多時，消息傳遞次數(shù)急劇增加，影響系統(tǒng)性能。

3) 系統(tǒng)中節(jié)點(diǎn)不能靈活地加入和退出，不適合開放的區(qū)塊鏈網(wǎng)絡(luò)，同時頻繁的加入、退出操作會嚴(yán)重影響系統(tǒng)的可用性。

1.4 相關(guān)研究

隨著區(qū)塊鏈技術(shù)的發(fā)展，拜占庭容錯算法的研究越來越多，特別是由于PBFT算法在點(diǎn)對點(diǎn)網(wǎng)絡(luò)中的安全性和高效性，使得針對PBFT共識算法的研究越來越多。

在文獻(xiàn)[12-13]中提出的Paxos算法和Raft算法是PBFT算法針對沒有拜占庭節(jié)點(diǎn)存在的分布式環(huán)境中的改進(jìn)，但是這種改進(jìn)方案主要用于數(shù)據(jù)庫或者日志的存儲系統(tǒng)，并不能解決區(qū)塊鏈網(wǎng)絡(luò)中的拜占庭節(jié)點(diǎn)問題。在文獻(xiàn)[14]引入了一種淡化主節(jié)點(diǎn)模式的EPBFT共識算法，并且把PBFT中三階段流程刪去了COMMIT階段，使PBFT的通信開銷降低了一半，但是系統(tǒng)的復(fù)雜度還是O(n2)，還可以進(jìn)一步進(jìn)行簡化。文獻(xiàn)[15]引入了一種基于信用投票選取主節(jié)點(diǎn)的方案IPBFT，但是在區(qū)塊鏈去中心化的模式下，引入信任機(jī)制是與區(qū)塊鏈去信任模式原則相違背的。文獻(xiàn)[16]提出了一種POS共識機(jī)制與PBFT共識機(jī)制結(jié)合的快速拜占庭容錯算法AlgoRand，該共識協(xié)議利用密碼抽簽技術(shù)對共識的驗證者和領(lǐng)導(dǎo)者進(jìn)行隨機(jī)選取，同時還提出了BA*二階段共識協(xié)議來對完成系統(tǒng)的一致性，但是領(lǐng)導(dǎo)者的隨機(jī)選取過程需要等待POS和VRF過程，給系統(tǒng)帶來一定的延遲。文獻(xiàn)[18]提出了POW與PBFT結(jié)合的共識算法，可以提高共識節(jié)點(diǎn)的可信度，但是會加大系統(tǒng)的中心化程度，這與區(qū)塊鏈去中心化去信任的模式相違背?？梢钥闯?，雖然針對PBFT算法的研究有很多，但是每種算法都有各自的優(yōu)勢和不足，PBFT共識算法在性能和可用性上面仍然還有改進(jìn)空間。

2 RPBFT共識算法

2.1 算法思想

通過對PBFT共識算法的流程和一系列改進(jìn)的PBFT算法進(jìn)行分析，并結(jié)合聚合簽名和隨機(jī)數(shù)方案提出了一種改進(jìn)的拜占庭容錯算法(RPBFT)，方案主要有以下幾點(diǎn)改進(jìn)：

1) 在視圖切換協(xié)議過程中提出主節(jié)點(diǎn)隨機(jī)選取方案，根據(jù)隨機(jī)數(shù)進(jìn)行主節(jié)點(diǎn)的選取，在主節(jié)點(diǎn)當(dāng)選之前，其他節(jié)點(diǎn)都無法預(yù)知主節(jié)點(diǎn)的身份，拜占庭節(jié)點(diǎn)只能對當(dāng)前主節(jié)點(diǎn)發(fā)起攻擊，但無法預(yù)知自己是否能夠當(dāng)選主節(jié)點(diǎn)，也就無法達(dá)到通過對誠實(shí)節(jié)點(diǎn)進(jìn)行拒絕服務(wù)攻擊使自己當(dāng)選主節(jié)點(diǎn)的目的。同時由于成本問題，作惡節(jié)點(diǎn)在不知道能否當(dāng)選主節(jié)點(diǎn)的情況下不會發(fā)起攻擊，故可以增強(qiáng)系統(tǒng)安全性，減少視圖更換的頻率，提高系統(tǒng)可用性，降低系統(tǒng)延遲。

2) 增加節(jié)點(diǎn)同步過程，給新加入系統(tǒng)的節(jié)點(diǎn)設(shè)置一個待同步狀態(tài)，當(dāng)節(jié)點(diǎn)同步到共識過程的最低水位時，就可以轉(zhuǎn)化為從節(jié)點(diǎn)，并進(jìn)入共識過程，從而使系統(tǒng)中的節(jié)點(diǎn)可以動態(tài)加入、退出，增強(qiáng)系統(tǒng)可用性。

3) 對PBFT共識算法的三階段流程進(jìn)行簡化，結(jié)合聚合簽名技術(shù)對其進(jìn)行優(yōu)化改進(jìn)，去掉三段式流程中的兩次消息的全網(wǎng)廣播，改為消息聚合轉(zhuǎn)發(fā)，降低算法共識過程中的通信復(fù)雜度，增強(qiáng)系統(tǒng)的可擴(kuò)展性。

2.2 算法設(shè)計

2.2.1RPBFT算法流程

RPBFT算法流程還是分為5個階段：請求(request)、預(yù)準(zhǔn)備(pre-prepare)、準(zhǔn)備(prepare)、確認(rèn)(commit)和響應(yīng)(reply)。具體流程如圖3所示。

1) 請求階段?？蛻舳薱向主節(jié)點(diǎn)p發(fā)送請求。o表示請求的具體操作，t表示請求時客戶端追加的時間戳，c表示客戶端標(biāo)識。REQUEST:包含消息內(nèi)容m，以及消息摘要d(m)，最后客戶端對請求進(jìn)行簽名。

2) 預(yù)準(zhǔn)備階段。主節(jié)點(diǎn)檢驗客戶端請求簽名是否正確，簽名非法就丟棄，簽名正確就分配一個編號vi，編號vi主要用于對客戶端的請求進(jìn)行排序。然后廣播一條<,σp,m>消息給其他副本節(jié)點(diǎn)。其中，v是視圖編號，m是消息內(nèi)容，σp是主節(jié)點(diǎn)對要廣播的消息進(jìn)行的簽名。

3) 準(zhǔn)備階段。從節(jié)點(diǎn)i檢驗來自主節(jié)點(diǎn)簽名后的消息，檢驗簽名和視圖序號是否正確，若檢驗通過，則進(jìn)入準(zhǔn)備階段。從節(jié)點(diǎn)i發(fā)送一條<,m,i>σi消息到主節(jié)點(diǎn)。其中i是從節(jié)點(diǎn)編號，σi是從節(jié)點(diǎn)i對PREPARE消息的簽名。記錄PRE-PREPARE和PREPARE消息到本地log日志中，用于在視圖切換時完成本輪共識中未完成的請求操作。系統(tǒng)中一共存在f個拜占庭節(jié)點(diǎn)，當(dāng)主節(jié)點(diǎn)接收到2f個PREPARE消息時，就會對接收到的消息進(jìn)行聚合，主節(jié)點(diǎn)會把所有接收到的從節(jié)點(diǎn)的簽名σi、PREPARE消息和從節(jié)點(diǎn)的公鑰PKi進(jìn)行聚合，可以將所有簽名聚合成一個短簽名σ，然后將聚合后的消息σ發(fā)送給其他從節(jié)點(diǎn)進(jìn)行驗證。

4) 確認(rèn)階段。從節(jié)點(diǎn)接收到主節(jié)點(diǎn)發(fā)送的消息,并且驗證生成聚合簽名消息的節(jié)點(diǎn)個數(shù)是否大于2f+1個，若驗證通過，則進(jìn)入COMMIT階段，并發(fā)送一條<,m,i>σi消息給主節(jié)點(diǎn)，σi是從節(jié)點(diǎn)對COMMIT消息的簽名。主節(jié)點(diǎn)收到2f個COMMIT消息后，會再次進(jìn)行聚合并且發(fā)送聚合后的消息給從節(jié)點(diǎn)進(jìn)行驗證，并且把COMMIT消息保存到本地的log日志。

5) 響應(yīng)階段。從節(jié)點(diǎn)i對確認(rèn)階段發(fā)送的聚合簽名進(jìn)行檢驗，如果驗證聚合簽名正確，則執(zhí)行客戶端發(fā)起的請求操作,并發(fā)送一個消息給客戶端節(jié)點(diǎn)，r為節(jié)點(diǎn)執(zhí)行請求的結(jié)果。若客戶端接收到f+1個響應(yīng)消息就達(dá)成了一致性。

2.2.2聚合簽名方案設(shè)計

上述流程中用到的聚合簽名過程主要分為6個部分，分別是系統(tǒng)建立、密鑰生成、從節(jié)點(diǎn)簽名生成、單個簽名驗證、聚合簽名生成、聚合簽名驗證等，具體流程如下：

1) 系統(tǒng)建立。定義群G1為大素數(shù)q階加法群，G2為q階循環(huán)乘法群，P為G1的生成元，e為G1×G1→G2的雙線性映射，選取兩個哈希函數(shù):H1:{0,1}*→G1，H2:{0,1}2×G1×{0,1}*→Zm。結(jié)合當(dāng)前視圖編號v計算:Pv=vP，公開系統(tǒng)參數(shù)params={G1,G2,e,P,Pv,H1,H2}。

2) 密鑰生成。節(jié)點(diǎn)i選擇隨機(jī)數(shù)xi作為用戶秘密值，并根據(jù)節(jié)點(diǎn)身份IDi，其中0

3) 節(jié)點(diǎn)簽名的生成。根據(jù)節(jié)點(diǎn)的身份IDi、私鑰Di、消息mi，隨機(jī)選取ri∈Zm，計算Ui=riP，hi=H2(mi,Ui,IDi)，Vi=hiDi+riPv，輸出節(jié)點(diǎn)i對消息mi的簽名σi=(Vi,Ui)，并將簽名發(fā)送給主節(jié)點(diǎn)聚合。

4) 單個簽名的驗證。對于簽名σi，主節(jié)點(diǎn)計算hi=H2(mi,Ui,IDi)，若等式e(P,Vi)=e(Ui+hiDi,Pv)成立，則說明σi有效。

2.2.3視圖更換

視圖切換協(xié)議可以有效保證PBFT共識算法的活性，基于PBFT共識算法改進(jìn)的RPBFT共識算法在原有協(xié)議的基礎(chǔ)上增加了隨機(jī)選取主節(jié)點(diǎn)的步驟。視圖切換的觸發(fā)條件主要有主節(jié)點(diǎn)超時失效、主節(jié)點(diǎn)作惡等幾種。視圖切換的流程如圖4所示。

(1) 系統(tǒng)滿足上述視圖切換的觸發(fā)條件之一。

(2) 發(fā)現(xiàn)主節(jié)點(diǎn)有上述的問題的從節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播視圖切換消息，并對消息進(jìn)行簽名，其中v是當(dāng)前視圖編號，vi是當(dāng)前視圖共識的序號，i是發(fā)現(xiàn)主節(jié)點(diǎn)問題的從節(jié)點(diǎn)編號，m是主節(jié)點(diǎn)存在的問題消息。

(3) 其他從節(jié)點(diǎn)接收到節(jié)點(diǎn)i發(fā)送的VIEW-CHANGE消息，首先檢查消息中的視圖編號v是否正確，其次檢查主節(jié)點(diǎn)是否存在問題，若編號v錯誤或者消息m錯誤，則忽略此消息；若檢驗通過，則發(fā)送一條消息到提案節(jié)點(diǎn)，其中v、vi、i、m等參數(shù)與VIEWCHANGE中意義相同,si為從節(jié)點(diǎn)i選擇的一個數(shù)字。

(4) 節(jié)點(diǎn)i對接收到的VIEWCHANGE-ADOPT消息進(jìn)行聚合，將聚合后的消息VIEW-COMMIT,v，v+1,vi,i,m>θi發(fā)送給其他節(jié)點(diǎn)進(jìn)行確認(rèn)。其他從節(jié)點(diǎn)接收到消息后進(jìn)行確認(rèn)，確認(rèn)通過后向全網(wǎng)廣播VIEW-COMMIT消息，當(dāng)任意一個節(jié)點(diǎn)接收到2f個確認(rèn)消息后，就會進(jìn)行視圖更換并選取主節(jié)點(diǎn)K，主節(jié)點(diǎn)K的具體選取過程在下一節(jié)中進(jìn)行介紹。

(5) 主節(jié)點(diǎn)選取完成之后，為了保證數(shù)據(jù)的準(zhǔn)確性，需要進(jìn)行數(shù)據(jù)校驗和確認(rèn)，確保在新的視圖中繼續(xù)完成上個視圖中未完成的共識。如果上個視圖有提案到達(dá)了準(zhǔn)備階段，并且記錄到日志中，新的主節(jié)點(diǎn)會發(fā)起數(shù)據(jù)同步，繼續(xù)完成未完成的一致性協(xié)議。

2.2.4隨機(jī)數(shù)K的選擇

不同視圖中的主節(jié)點(diǎn)都是由隨機(jī)數(shù)K進(jìn)行選擇，若區(qū)塊所在視圖為初始視圖時，則K=0；若區(qū)塊不在初始視圖，隨機(jī)數(shù)K由視圖更換階段的隨機(jī)數(shù)種子和上一個區(qū)塊交易的哈希確定，確定方法如圖5所示。

假設(shè)視圖切換階段收到N個數(shù)si，其中0≤si≤|R|-1，0≤i≤N，上一個區(qū)塊哈希為BlockHash，則初始隨機(jī)數(shù)Random可以由式(1)和式(2)確定：

Hi=Hash(si)

(2)

(3)

然后對得到的隨機(jī)數(shù)Random通過SHA256計算得到的一個長度為256位的16進(jìn)制字符，取隨機(jī)字符Random最后的8位，轉(zhuǎn)化為10進(jìn)制然后；用式(3)得到隨機(jī)數(shù)K：

K=(TratoInt10(End8(Random))) mod (|R|-1)

(4)

式中的函數(shù)TratoInt10意義是16進(jìn)制轉(zhuǎn)化為10進(jìn)制，函數(shù)End8的含義是取字符串的最后8位,mod是進(jìn)行取模運(yùn)算，最后在從節(jié)點(diǎn)中選擇編號為K的節(jié)點(diǎn)當(dāng)選為主節(jié)點(diǎn)。

2.2.5垃圾回收與節(jié)點(diǎn)動態(tài)調(diào)節(jié)

在RPBFT算法流程中，為了確保視圖更換后能恢復(fù)正在執(zhí)行的請求，每個節(jié)點(diǎn)都記錄了一些消息在本地log中，為了保證算法可以正常運(yùn)行的同時減少本地存儲，可以每執(zhí)行完k條請求執(zhí)行一次狀態(tài)同步，刪除最低水位線下的本地log記錄。

給系統(tǒng)中的節(jié)點(diǎn)新加入了一個待同步狀態(tài)，新加入的節(jié)點(diǎn)或者沒有達(dá)到當(dāng)前視圖的最低水位的節(jié)點(diǎn)都屬于待同步狀態(tài)。待同步狀態(tài)的節(jié)點(diǎn)達(dá)到系統(tǒng)所需要的最低水位線后，節(jié)點(diǎn)狀態(tài)變?yōu)橥綘顟B(tài)，同時主節(jié)點(diǎn)會給其分配一個編號i，此時該節(jié)點(diǎn)就正式加入共識過程，就可以等待主節(jié)點(diǎn)發(fā)送信息。

3 實(shí)驗分析

3.1 通信開銷分析

RPBFT的改進(jìn)方案可以在不影響系統(tǒng)容錯性的情況下降低共識流程中的通信開銷，提升共識算法的效率。通信開銷主要從兩個方面進(jìn)行分析：一是在共識過程中的三個主要階段，包括預(yù)準(zhǔn)備階段、準(zhǔn)備階段和確認(rèn)階段；二是在系統(tǒng)出現(xiàn)故障時發(fā)生的視圖切換。

3.1.1三階段過程中的通信開銷

假定系統(tǒng)中共識節(jié)點(diǎn)數(shù)目為a(a>4),可以根據(jù)PBFT和RPBFT的共識流程分別進(jìn)行對比分析。其中PBFT共識算法和RPBFT共識算法的三階段總通信次數(shù)分別為：

C1=(a-1)+2a(a-1)

(5)

C2=6(a-1)

(6)

根據(jù)式(5)、式(6)可以做出兩種算法在通信開銷的對比圖，如圖6所示。

根據(jù)圖6可以看出，在三階段流程中PBFT算法的總通信開銷是多項式級別的，隨著總節(jié)點(diǎn)數(shù)的增多，通信開銷急劇增長，當(dāng)節(jié)點(diǎn)增多到一定數(shù)量時,系統(tǒng)會占用過多帶寬，造成系統(tǒng)堵塞；而改進(jìn)的RPBFT共識算法將通信開銷降低到了線性，隨著節(jié)點(diǎn)的增多，總通信次數(shù)不會出現(xiàn)太大的波動。RPBFT算法可以有效地降低通信開銷，提升共識效率，增強(qiáng)了系統(tǒng)的可用性。

3.1.2視圖更換中總通信開銷

系統(tǒng)在共識過程中出現(xiàn)故障時，從節(jié)點(diǎn)會發(fā)起視圖更換協(xié)議。在視圖更換協(xié)議中從節(jié)點(diǎn)發(fā)起視圖更換提案過程的總通信次數(shù)為(a-1)，其他節(jié)點(diǎn)接收到提案以后進(jìn)行全網(wǎng)廣播過程的總通信次數(shù)為(a-1)2，同時共識過程中視圖更換的概率為P，則兩種算法在發(fā)起視圖更換時的總通信次數(shù)為：

T1=C1+2Pa(a-1)

(7)

T2=C2+2Pa(a-1)

(8)

在PBFT和RPBFT共識算法中的拜占庭節(jié)點(diǎn)個數(shù)都是小于1/3的，所以系統(tǒng)中發(fā)起視圖更換的概率P<1/3，令P=0.33，則兩種算法的總通信開銷對比圖如圖7所示。

根據(jù)圖7中PBFT和RPBFT算法在發(fā)生視圖更換時的總通信次數(shù)對比，在發(fā)生視圖更換的概率為1/3時，RPBFT算法可以極大地降低系統(tǒng)的通信開銷，可以達(dá)到降低PBFT算法的通信復(fù)雜度的目的。根據(jù)圖6和圖7綜合來看，在一次完整的共識流程中，總節(jié)點(diǎn)的數(shù)目越多，兩種算法的通信開銷差距越大，因此，RPBFT算法可以在不影響系統(tǒng)可靠性的前提下有效減少通信總開銷，提升系統(tǒng)的可用性。

3.2 實(shí)驗設(shè)置與性能測試

為驗證本文方法確實(shí)能夠提升系統(tǒng)性能，且不降低系統(tǒng)的容錯性和安全性，實(shí)驗以文獻(xiàn)[16]提出的AlgoRand共識算法和Fabric中的PBFT算法作為對比算法，對比三種算法在吞吐量、時延、穩(wěn)定性、安全性等方面的表現(xiàn)。本實(shí)驗選用Windows系統(tǒng)為實(shí)驗環(huán)境，選用simblock區(qū)塊鏈模擬器模擬區(qū)塊鏈網(wǎng)絡(luò)，以Gradle- 6.3工具進(jìn)行構(gòu)建，實(shí)驗數(shù)據(jù)用MATLAB進(jìn)行繪制。在本文的實(shí)驗中需要對某些參數(shù)進(jìn)行設(shè)置，同時需要一些假設(shè)條件：

(1) 為了降低區(qū)塊大小對實(shí)驗數(shù)據(jù)的影響，在本文實(shí)驗中將一個區(qū)塊包含的交易固定在100個。

(2) 在系統(tǒng)穩(wěn)定性測試中，定義攻擊規(guī)則為當(dāng)作惡節(jié)點(diǎn)編號與主節(jié)點(diǎn)編號差距小于等于2時，發(fā)動拒絕服務(wù)攻擊。同時還要保證由于攻擊掉線的節(jié)點(diǎn)，可以恢復(fù)并加入到系統(tǒng)中。

3.2.1吞吐量測試

吞吐量代表一個系統(tǒng)在單位時間內(nèi)處理事務(wù)的能力，通常用TPS(Transaction Per Second，每秒交易數(shù))來表示：

TPS=SumTransactionΔt/Δt

(9)

式中：Δt為交易發(fā)送后到寫入?yún)^(qū)塊的時間間隔；SumTransactionΔt為該時間間隔中寫入?yún)^(qū)塊的交易總數(shù)。為了驗證在不同規(guī)模下RPBFT算法的吞吐量，設(shè)置在不同節(jié)點(diǎn)個數(shù)的區(qū)塊鏈網(wǎng)絡(luò)下，統(tǒng)計三種算法分別完成20 000筆交易的平均時間，并根據(jù)式(9)計算平均TPS，如圖8所示。

可以看出隨著系統(tǒng)內(nèi)節(jié)點(diǎn)總數(shù)的增多，三種算法的TPS都有不同程度的下降，但RPBFT共識算法的TPS明顯更高，并且隨著節(jié)點(diǎn)的增多這種差距會越來越大。本改進(jìn)方案在系統(tǒng)運(yùn)行過程中，可能會由于主節(jié)點(diǎn)問題發(fā)起視圖更換，視圖切換時會伴有隨機(jī)數(shù)的生成，在這一段時間中會略微影響系統(tǒng)性能，但算法總體性能還是高于其他兩種算法，達(dá)到了提升系統(tǒng)吞吐量的目的。

3.2.2時延測試

時延是指一筆交易從開始提交到交易確認(rèn)之間消耗的時間，在區(qū)塊鏈網(wǎng)絡(luò)中時延是衡量系統(tǒng)的共識算法和網(wǎng)絡(luò)性能的標(biāo)準(zhǔn)，較低的時延會更加快速地確認(rèn)交易，出現(xiàn)分叉的概率也會大大降低。在本文中用式(10)來對時延進(jìn)行計算。

DelayTimetx=Tc-Tp

(10)

式中：DelayTimetx表示交易的時延；Tc表示交易在區(qū)塊中確認(rèn)的時間；Tp表示發(fā)起提案的時間。為了驗證不同規(guī)模下RPBFT算法的延遲，設(shè)置在不同節(jié)點(diǎn)個數(shù)的區(qū)塊鏈網(wǎng)絡(luò)下，統(tǒng)計三種算法分別完成20 000筆交易的平均延遲，并統(tǒng)計結(jié)果如圖9所示。

如圖9所示，隨著系統(tǒng)內(nèi)共識節(jié)點(diǎn)的增多，三種算法的時延都有不同程度的增長，相比較看AlgoRand算法中的時延是最長的，是由于AlgoRand算法在共識中加入了領(lǐng)導(dǎo)者和驗證者隨機(jī)選取，影響了系統(tǒng)性能。RPBFT共識算法雖然在視圖切換協(xié)議中加入了隨機(jī)數(shù)生成和主節(jié)點(diǎn)隨機(jī)選取過程，但避免了連續(xù)視圖切換問題，并且改進(jìn)了PBFT算法的三階段通信協(xié)議，使得RPBFT算法在保證安全性和可靠性的基礎(chǔ)上降低了PBFT算法的交易時延，縮短了確認(rèn)時間，提高了系統(tǒng)的可用性。

3.2.3穩(wěn)定性測試

視圖切換的觸發(fā)的條件主要有主節(jié)點(diǎn)網(wǎng)絡(luò)問題超時、主節(jié)點(diǎn)作惡、主節(jié)點(diǎn)被攻擊等幾種情況。故可以用平均視圖切換次數(shù)來表示系統(tǒng)的穩(wěn)定性。穩(wěn)定性測試主要為驗證在大規(guī)模的區(qū)塊鏈網(wǎng)絡(luò)中，RPBFT算法可以更穩(wěn)定地運(yùn)行。設(shè)置在有120個節(jié)點(diǎn)的區(qū)塊鏈網(wǎng)絡(luò)中，統(tǒng)計不同拜占庭節(jié)點(diǎn)比率下的視圖切換次數(shù)如圖10所示。

根據(jù)圖10可以看出在拜占庭節(jié)點(diǎn)占比較低的情況下兩種算法的視圖切換次數(shù)都很少，隨著拜占庭節(jié)點(diǎn)的增多，視圖切換次數(shù)都有不同程度的增長，但同時RPBFT算法的視圖切換次數(shù)一直小于PBFT算法。這是由于RPBFT共識算法可以規(guī)避作惡節(jié)點(diǎn)根據(jù)主節(jié)點(diǎn)選取順序發(fā)起的攻擊，減少了部分由于惡意攻擊導(dǎo)致的視圖切換，增強(qiáng)了系統(tǒng)的安全性與穩(wěn)定性，使系統(tǒng)可在大規(guī)模網(wǎng)絡(luò)中穩(wěn)定安全運(yùn)行。

3.3 安全性分析

RPBFT算法在主節(jié)點(diǎn)的選擇上與AlgoRand算法的密碼抽簽技術(shù)不同，采用了生成隨機(jī)數(shù)來進(jìn)行主節(jié)點(diǎn)選取的方案，但同時選擇概率性算法需要考慮公平性、可驗證性和不可預(yù)測性。

本文中的主節(jié)點(diǎn)概率選擇算法的公平性是根據(jù)節(jié)點(diǎn)編號平均分配,保證每個節(jié)點(diǎn)當(dāng)選主節(jié)點(diǎn)的概率是均勻的,視圖切換中生成的原始隨機(jī)數(shù)Random足夠大,遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)數(shù)目,所以根據(jù)式(4)得到的主節(jié)點(diǎn)編號K是符合公平性原則的;RPBFT算法在視圖更換階段中產(chǎn)生隨機(jī)數(shù)的種子都是可追溯的，保證了最終隨機(jī)數(shù)符合概率選擇中的可驗證性；當(dāng)發(fā)生視圖更換時,絕大多數(shù)誠實(shí)節(jié)點(diǎn)會發(fā)送自己選擇數(shù)字并且進(jìn)行簽名加密,節(jié)點(diǎn)并不會獲得其他節(jié)點(diǎn)的種子，根據(jù)式(3)、式(4)的計算，會得到一個隨機(jī)數(shù)K，由于產(chǎn)生隨機(jī)數(shù)的過程有大量的節(jié)點(diǎn)參與，隨機(jī)種子足夠多，所以本算法的主節(jié)點(diǎn)選擇方案符合不可預(yù)測的原則?？傮w來看RPBFT算法在保證容錯性不變的基礎(chǔ)上，提高了共識效率和安全性，增強(qiáng)了系統(tǒng)的可用性。

4 結(jié) 語

本文根據(jù)區(qū)塊鏈中的實(shí)用拜占庭容錯(PBFT)共識算法中存在的一些問題，提出了一種主節(jié)點(diǎn)隨機(jī)選取的改進(jìn)拜占庭容錯(RPBFT)共識算法。并且對PBFT算法、RPBFT共識算法、AlgoRand共識算法進(jìn)行模擬對比實(shí)驗，通過對通信開銷、吞吐量、時延、視圖切換次數(shù)等實(shí)驗數(shù)據(jù)的對比分析，驗證了本文所提出的算法方案確實(shí)可以在不降低系統(tǒng)容錯性的前提下提高系統(tǒng)的性能和安全性。

未來可以進(jìn)一步對RPBFT算法的視圖更換階段進(jìn)行改進(jìn)，提出通信量更小的視圖更換方案，提升系統(tǒng)性能。同時，也可以將RPBFT算法應(yīng)用到有向無環(huán)圖(DAG)新型區(qū)塊鏈技術(shù)上進(jìn)一步提升系統(tǒng)的性能。