陳潤宇，王倫文，朱然剛

（國防科技大學(xué)電子對抗學(xué)院，合肥 230037）

0 概述

區(qū)塊鏈作為數(shù)字貨幣比特幣［1］的底層技術(shù)，隨著比特幣的發(fā)展而備受關(guān)注。區(qū)塊鏈本質(zhì)上是一種由哈希算法、數(shù)字簽名、P2P 網(wǎng)絡(luò)、共識算法、智能合約等技術(shù)構(gòu)成的分布式基礎(chǔ)架構(gòu)與計算范式［2］，具有透明可靠、防篡改可追溯、隱私安全保障、系統(tǒng)高可靠等特性［3-4］，廣泛應(yīng)用于金融、交通、隱私保護(hù)等領(lǐng)域［5-6］。共識機制［7］是區(qū)塊鏈的必要元素和核心部分，是確保區(qū)塊鏈系統(tǒng)高效合作的關(guān)鍵。共識機制是指分布式系統(tǒng)中全部節(jié)點（或大部分節(jié)點）就某個數(shù)據(jù)的真實性或者某條交易的價值達(dá)成一致并據(jù)此更新各節(jié)點記錄的機制。根據(jù)不同場景和應(yīng)用需求，需要設(shè)計不同的共識機制。典型的區(qū)塊鏈共識機制大致可分為證明類共識機制（如PoW［8］、PoS、DPoS 等）和拜占庭協(xié)議機制［9-10］，其中實用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）［11］算法因能夠解決拜占庭問題而得到廣泛應(yīng)用。PBFT 基于狀態(tài)機復(fù)制原理，通過一致性、檢查點、視圖轉(zhuǎn)換3 個協(xié)議，當(dāng)系統(tǒng)中約有1/3 的節(jié)點為惡意節(jié)點時仍能確保系統(tǒng)正常運行，同時大幅降低了共識過程的通信復(fù)雜度，但PBFT 存在主節(jié)點選取隨意［12］、通信復(fù)雜度高、共識效率低［13］等問題［14］。

針對PBFT 算法主節(jié)點選取隨意導(dǎo)致惡意節(jié)點具有較大概率成為主節(jié)點的問題：WANG等［15］提出CPBFT算法，該算法根據(jù)信用等級劃分節(jié)點，并將相應(yīng)的信用系數(shù)分配給不同級別的節(jié)點；ZHU 等［16］提出CDBFT 算法，該算法建立一種特權(quán)分類機制，有效地防止預(yù)期節(jié)點被選中；ZHANG 等［17］提出實用的基于量化角色的拜占庭共識算法（QPBFT），該算法基于層次分析法（Analytic Hierarchy Process，AHP）對節(jié)點的可靠性屬性進(jìn)行量化，通過引入量化角色，使可靠性評價得分較高的節(jié)點更有可能參與區(qū)塊生產(chǎn)；ZHENG 等［18］將C4.5決策樹與PBFT 結(jié)合，通過計算信息熵進(jìn)行節(jié)點分類的同時引入投票機制確定領(lǐng)導(dǎo)節(jié)點；GAO 等［19］將EigenTrust模型與共識算法結(jié)合，用節(jié)點間的交易來評估節(jié)點的信任程度，從而選擇網(wǎng)絡(luò)中質(zhì)量較高的節(jié)點來構(gòu)建共識層；TONG 等［20］將PeerTrust 模型與共識結(jié)合，取代了原來所有節(jié)點都參與的情況，從而使分布式網(wǎng)絡(luò)的規(guī)?？扇我鈹U展；WANG 等［21］注意到現(xiàn)有基于信譽投票改進(jìn)PBFT 的共識算法普遍存在馬太效應(yīng)造成信用價值積累問題，分別采用不同的信任模型并使用不同的積分函數(shù)來緩解上述問題，但由于部分參數(shù)設(shè)置不夠合理，信用價值累積的問題并沒有得到根本的解決。針對通信復(fù)雜度較高的問題，現(xiàn)有研究方法主要分成兩類。一類是基于上述方法，先將節(jié)點分類，再通過使更多的誠實節(jié)點參與共識過程，減少共識過程的通信復(fù)雜度。另一類是對PBFT 一致性協(xié)議［22-23］本身進(jìn)行改進(jìn)。

但上述算法仍存在兩方面的問題。一是系統(tǒng)中所有節(jié)點初始信譽值均由本地計算產(chǎn)生，缺少驗證手段，可信程度難以保證，可能會出現(xiàn)部分節(jié)點為了獲取利益而惡意篡改自身初始信譽值，進(jìn)而發(fā)動對系統(tǒng)的惡意攻擊的情況。二是過于復(fù)雜的節(jié)點分類以及選舉機制造成了額外的通信開銷?，F(xiàn)有多數(shù)算法都通過設(shè)置信譽模型、獎懲函數(shù)以及投票機制減少共識過程中的惡意節(jié)點數(shù)量，降低共識過程的通信復(fù)雜度，但忽視了設(shè)置各種模型函數(shù)本身給系統(tǒng)帶來了額外的通信復(fù)雜度。從整體上看，這些算法并沒有真正降低系統(tǒng)的通信復(fù)雜度。

本文提出一種基于信譽值投票與隨機數(shù)選舉的RN-VPBFT 共識算法。增設(shè)初始記賬節(jié)點，降低選舉過程的通信復(fù)雜度以及提升選舉公平性。將所用時間證明（Proof of Elapsed Time，PoET）［24］的領(lǐng)導(dǎo)者選舉思想與現(xiàn)有PBFT 共識算法相結(jié)合，通過在所有共識節(jié)點內(nèi)部隨機選舉的方式避免主節(jié)點總由某些節(jié)點擔(dān)任的現(xiàn)象，降低系統(tǒng)的中心化趨勢?；谪澬乃惴ǖ母拍?，由不參與共識的節(jié)點擔(dān)任監(jiān)督節(jié)點。簡化PBFT 的共識流程，以降低共識過程的通信復(fù)雜度，提高共識效率。

1 實用拜占庭容錯算法

PBFT 算法是一種保證分布式系統(tǒng)和拜占庭故障節(jié)點一致性的通用解決方案，主要解決系統(tǒng)中惡意節(jié)點向其他節(jié)點發(fā)送錯誤信息擾亂系統(tǒng)正常運行的問題。PBFT 算法在保證系統(tǒng)安全性和可靠性的前提下提供了(n-1)/3 的容錯性，即允許系統(tǒng)至多存在1/3 的失效節(jié)點。

PBFT 要求節(jié)點共同維護(hù)一個狀態(tài)且所有節(jié)點保持一致，因此需要運行一致性、視圖轉(zhuǎn)換、檢查點等3 類基本協(xié)議。一致性協(xié)議通過三階段共識保證所有節(jié)點數(shù)據(jù)存儲的一致性，若在一致性協(xié)議中主節(jié)點被檢測出故障或作惡，則觸發(fā)視圖轉(zhuǎn)換協(xié)議以更換出現(xiàn)故障的主節(jié)點。檢查點協(xié)議是一個周期性過程，系統(tǒng)會設(shè)置一個檢查的時間點，實現(xiàn)定期處理日志、節(jié)約資源并及時糾正節(jié)點狀態(tài)的功能。

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

一致性協(xié)議又稱三階段協(xié)議，是PBFT算法的核心，主要包括預(yù)準(zhǔn)備、準(zhǔn)備、提交3個階段。PBFT算法共識過程如圖1所示，其中，Client表示客戶端，Primary node表示主節(jié)點，Replica 1，2 表示備份節(jié)點，Replica 3 被認(rèn)為是錯誤節(jié)點。

圖1 PBFT 算法共識過程Fig.1 Consensus process of PBFT algorithm

PBFT 算法共識的簡要流程如下：

1）消息請求?？蛻舳讼蛑鞴?jié)點發(fā)送請求，如式（1）所示：

其中：request 為消息名稱；o為具體操作；t為時間戳；c為客戶端標(biāo)識。

2）預(yù)準(zhǔn)備階段。主節(jié)點將客戶端的消息通過式（2）發(fā)送給其余節(jié)點：

其中：V為視圖編號；n為節(jié)點編號；d為信息摘要。若消息通過驗證，則進(jìn)入準(zhǔn)備階段。

3）準(zhǔn)備階段。備份節(jié)點之間發(fā)送如式（3）所示的消息：

當(dāng)節(jié)點接收到超過2f+1 個不同節(jié)點的pre-prepare和prepare 信息并通過驗證后進(jìn)入確認(rèn)階段。

4）確認(rèn)階段。節(jié)點之間發(fā)送如式（4）所示的確認(rèn)消息：

其中：S(m)為節(jié)點簽名集合。

5）回復(fù)階段。當(dāng)節(jié)點收到2f+1 個不同節(jié)點的確認(rèn)消息后向客戶端發(fā)送回復(fù)消息，如式（5）所示：

當(dāng)客戶端收到f+1 個消息時代表達(dá)成共識。

1.2 PBFT 算法的視圖轉(zhuǎn)換協(xié)議

若某個備份節(jié)點檢測出主節(jié)點出現(xiàn)問題時，觸發(fā)視圖轉(zhuǎn)換協(xié)議，將視圖編號V變更為V+1，同時不再接受除檢查點、視圖轉(zhuǎn)換和新視圖外的其他消息請求。PBFT 算法視圖轉(zhuǎn)換過程如圖2 所示，其中，Replica 0 表示出現(xiàn)問題的主節(jié)點，Replica 1 表示新的主節(jié)點。

圖2 PBFT 算法視圖轉(zhuǎn)換過程Fig.2 View change process of PBFT algorithm

PBFT 算法視圖轉(zhuǎn)換的簡要流程如下：

1）視圖轉(zhuǎn)換階段。當(dāng)系統(tǒng)中任一備份節(jié)點發(fā)現(xiàn)主節(jié)點出現(xiàn)問題時，將“視圖轉(zhuǎn)換”驗證廣播給所有節(jié)點。

2）確認(rèn)視圖轉(zhuǎn)換。當(dāng)一個節(jié)點收到2f+1 個確認(rèn)信息后（包括自己的信息），將“確認(rèn)視圖轉(zhuǎn)換”信息發(fā)送給視圖V+1 的主節(jié)點。新的主節(jié)點在接收到“視圖轉(zhuǎn)換”以及“確認(rèn)視圖轉(zhuǎn)換”信息后進(jìn)入新的視圖。

3）新視圖階段。新節(jié)點確認(rèn)系統(tǒng)狀態(tài)后根據(jù)本地塊鏈數(shù)據(jù)執(zhí)行一致性協(xié)議。

PBFT 算法雖然在一定程度上改善了傳統(tǒng)共識算法通信復(fù)雜度高的問題，但由于惡意節(jié)點的存在，使得整個共識過程中節(jié)點間必須通過兩兩通信以確保消息的可靠。隨著系統(tǒng)規(guī)模的不斷擴大，PBFT 通信復(fù)雜度增長迅速，因此本文針對該問題對算法進(jìn)行改進(jìn)，進(jìn)一步降低算法復(fù)雜度。

2 RN-VPBFT 共識算法

本文提出一種基于信譽值投票和隨機數(shù)選舉的RN-VPBFT 共識算法，通過建立節(jié)點信譽模型、增設(shè)監(jiān)督節(jié)點以及改進(jìn)主節(jié)點選取方式，保證系統(tǒng)安全，降低共識過程的通信復(fù)雜度和系統(tǒng)的集中化趨勢，提高共識效率。

2.1 RN-VPBFT 共識算法流程

RN-VPBFT 共識算法流程如圖3 所示，執(zhí)行過程以輪為單位，每一輪執(zhí)行過程分為準(zhǔn)備、共識、結(jié)束3 個階段。在第一輪共識過程開始前，需要通過投票確定系統(tǒng)中所有節(jié)點的初始信譽值。

圖3 RN-VPBFT 算法流程Fig.3 Procedure of RN-VPBFT algorithm

2.2 初始信譽值確定

所有新加入系統(tǒng)的節(jié)點需要通過相互投票的方式確定初始信譽值。現(xiàn)有算法多數(shù)通過節(jié)點間的相互通信確定得票數(shù)，并在本地通過計算得到自身的初始信譽值，可能會出現(xiàn)部分節(jié)點惡意篡改自身初始信譽值的現(xiàn)象。設(shè)置初始記賬節(jié)點能夠?qū)⑺型镀庇涗浖杏谝粋€節(jié)點，這樣既避免了節(jié)點的兩兩通信，又確保了投票結(jié)果的真實性。初始信譽值確定的具體步驟如下：

1）確定初始記賬節(jié)點。所有節(jié)點首先按照進(jìn)入系統(tǒng)的先后順序分配各自的節(jié)點編號1，2，…，N，然后系統(tǒng)隨機產(chǎn)生1 到N的一個隨機數(shù)，節(jié)點編號與該隨機數(shù)相同的節(jié)點即為初始記賬節(jié)點。

2）投票。每個節(jié)點對系統(tǒng)中所有其他節(jié)點投贊成或反對票，并將投票結(jié)果復(fù)制兩份，一份寫入本地日志，另一份發(fā)送給記賬節(jié)點，由記賬節(jié)點計算初始信譽值。

3）確定初始信譽值。初始記賬節(jié)點首先將所有節(jié)點的投票結(jié)果進(jìn)行匯總并統(tǒng)計各個節(jié)點獲得的贊成票Si(i=1，2，…，N)與反對票Ai，然后根據(jù)式（6）計算得到每個節(jié)點的初始信譽值，按信譽值的降序排序T1>T2>…>Tn。最后將各個節(jié)點的初始信譽值（Ti）及其對應(yīng)排名發(fā)送給相應(yīng)節(jié)點。

所有節(jié)點在接收到初始記賬節(jié)點發(fā)送的信息后均可以向初始記賬節(jié)點提出質(zhì)疑，通過訪問初始記賬節(jié)點的本地數(shù)據(jù)來確認(rèn)接收信息的真實性。若初始記賬節(jié)點在接受查詢的過程中出現(xiàn)問題，則重新執(zhí)行上述流程，同時該節(jié)點的信譽值清零且被系統(tǒng)記錄為惡意節(jié)點，并無法參與共識協(xié)議，只能被動接收經(jīng)過共識后的數(shù)據(jù)；若所有節(jié)點的初始信譽值均正確，則擔(dān)任初始記賬節(jié)點的節(jié)點信譽值將根據(jù)自身的初始信譽值的大小獲得不同程度的獎勵。

2.3 準(zhǔn)備階段

RN-VPBFT 共識算法準(zhǔn)備階段主要完成節(jié)點分類以及主節(jié)點選舉工作，如圖4 所示。

圖4 RN-VPBFT 算法準(zhǔn)備階段示意圖Fig.4 Schematic diagram of the preparation stage of the RN-VPBFT algorithm

2.3.1 節(jié)點分類

RN-VPBFT 算法節(jié)點模型如圖5所示，節(jié)點被劃分為主節(jié)點、共識節(jié)點、備份節(jié)點和監(jiān)督節(jié)點4 種節(jié)點。4 種節(jié)點各司其職，相互監(jiān)督，共同維護(hù)系統(tǒng)平衡：

圖5 RN-VPBFT 算法節(jié)點模型Fig.5 Node model of RN-VPBFT algorithm

1）備份節(jié)點。備份節(jié)點不參與共識過程，只能根據(jù)主節(jié)點傳遞的信息更新本地信息。同時，備份節(jié)點能夠?qū)ΡO(jiān)督節(jié)點進(jìn)行監(jiān)督，并有權(quán)彈劾監(jiān)督節(jié)點。所有加入系統(tǒng)的網(wǎng)絡(luò)節(jié)點都是備份節(jié)點。

2）共識節(jié)點。共識節(jié)點負(fù)責(zé)接收并驗證主節(jié)點傳遞的信息，保證系統(tǒng)一致性。通過對系統(tǒng)中所有N個節(jié)點信譽值進(jìn)行比較，選取信譽值較高的前N1個節(jié)點為共識節(jié)點。

3）主節(jié)點。主節(jié)點負(fù)責(zé)接收用戶需求、確認(rèn)提交數(shù)據(jù)、打包并生成新區(qū)塊。

4）監(jiān)督節(jié)點。監(jiān)督節(jié)點主要保證系統(tǒng)的安全。有權(quán)查詢其他所有節(jié)點的本地日志，監(jiān)督整個共識過程，查詢備份節(jié)點的信息更新情況以及負(fù)責(zé)每輪共識結(jié)束后節(jié)點的信譽值更新。

2.3.2 主節(jié)點和監(jiān)督節(jié)點選舉

PBFT 的主節(jié)點選舉方式如式（7）所示：

其中：P為主節(jié)點。

由于算法中主節(jié)點編號與視圖編號有很大的相關(guān)性，因此能夠很容易被系統(tǒng)中的惡意節(jié)點預(yù)測，進(jìn)而達(dá)到提前攻擊的目的，不利于保證系統(tǒng)的安全性?，F(xiàn)有PBFT 改進(jìn)算法多數(shù)基于節(jié)點的信譽值排序，選取信譽值最高（可信度最高）的節(jié)點擔(dān)任主節(jié)點，這樣雖然能夠在很大程度上保證系統(tǒng)的安全，但每一輪共識結(jié)束后，主節(jié)點相較于其他節(jié)點往往會獲得更多的報酬，隨著時間累積，主節(jié)點往往僅會由某幾個節(jié)點擔(dān)任且節(jié)點之間的信譽值差值會越來越大，出現(xiàn)系統(tǒng)的集中化趨勢。針對該問題，本文基于所用時間證明的領(lǐng)導(dǎo)者選舉思想，所有共識節(jié)點在信譽值的基礎(chǔ)上隨機選舉主節(jié)點。

1）所用時間證明

PoET 概念是由英特爾于2016 年初提出，提供了一個現(xiàn)成的高科技工具來解決隨機領(lǐng)導(dǎo)者選舉的計算問題，通常用于許可的區(qū)塊鏈網(wǎng)絡(luò)，以決定網(wǎng)絡(luò)的采礦權(quán)或區(qū)塊獲勝者。PoET 基于公平彩票系統(tǒng)的原則，使得網(wǎng)絡(luò)參與者擁有公平的獲勝機會。PoET 算法工作流程如下：區(qū)塊鏈網(wǎng)絡(luò)中每個節(jié)點都會生成隨機等待時間并在指定的持續(xù)時間內(nèi)進(jìn)入休眠狀態(tài)。首先完成指定等待時間（具有最短等待時間）的節(jié)點被喚醒并向區(qū)塊鏈提交新塊，然后向整個對等網(wǎng)絡(luò)廣播必要的信息，最后重復(fù)相同過程以發(fā)現(xiàn)下一個新塊。PoET 整個共識過程需要具備2 個重要因素：（1）參與節(jié)點真正地選擇了隨機的時間，而不是參與者為了獲勝而故意選擇的較短持續(xù)時間；（2）獲勝者確實已經(jīng)完成了指定等待時間。由于實際的區(qū)塊鏈系統(tǒng)中所有的節(jié)點并不都是可信的，因此綜合考慮上述2 個因素以及在等待時間內(nèi)節(jié)點處于休眠狀態(tài)而造成的時間損耗問題，提出改進(jìn)的所用時間證明。

2）改進(jìn)的所用時間證明

利用監(jiān)督節(jié)點的職能，在所有共識節(jié)點內(nèi)部提出一種基于隨機數(shù)的主節(jié)點選取方式，通過節(jié)點自身的日志記錄以及監(jiān)督節(jié)點對其他節(jié)點日志的訪問，確保了當(dāng)選主節(jié)點的公平性和真實性，避免了時間浪費的同時在一定程度上解決了PoET 存在的問題。

依據(jù)式（8）和式（9）選舉產(chǎn)生主節(jié)點（L）和監(jiān)督節(jié)點（Su）：

改進(jìn)的所用時間證明算法的工作流程如下：

（1）在所有共識節(jié)點內(nèi)部生成同一范圍內(nèi)的RN(i)，并將寫入本地日志。

（2）共識節(jié)點廣播給監(jiān)督節(jié)點，監(jiān)督節(jié)點通過訪問共識節(jié)點的日志以驗證收到的隨機數(shù)無誤后廣播。當(dāng)存在多個節(jié)點同時擁有最小隨機數(shù)時，廣播。

（3）若監(jiān)督節(jié)點發(fā)現(xiàn)min(RN′(i))≠min(RN(i))，則監(jiān)督節(jié)點會向整個系統(tǒng)廣播該共識節(jié)點i，該節(jié)點將會立刻被驅(qū)逐出共識節(jié)點，并被系統(tǒng)記錄為惡意節(jié)點。

（4）由于監(jiān)督節(jié)點的高風(fēng)險性，因此所有共識節(jié)點均可以在共識過程開始之前對結(jié)果提出質(zhì)疑，通過節(jié)點間的相互監(jiān)督，保證系統(tǒng)安全。

2.4 共識階段

RN-VPBFT 算法共識階段主要執(zhí)行一致性協(xié)議，如圖6 所示。在傳統(tǒng)的PBFT 算法共識過程中：當(dāng)系統(tǒng)中存在n個節(jié)點時，達(dá)成共識所需的通信次數(shù)大致等于2n2；當(dāng)系統(tǒng)節(jié)點數(shù)不斷增加時，達(dá)成共識所需要的通信次數(shù)將迅速增多，這不僅會帶來傳遞消息的爆炸性增長，還會大大延遲達(dá)成共識所需要的時間，進(jìn)而成為系統(tǒng)性能的瓶頸。

圖6 RN-VPBFT 算法共識階段示意圖Fig.6 Schematic diagram of the consensus stage of the RN-VPBFT algorithm

為降低通信復(fù)雜度，本文提出的共識機制首先將復(fù)雜的消息驗證工作交給監(jiān)督節(jié)點完成。由于事先已按照信譽值對節(jié)點排序和分類，因此一致性協(xié)議的過程中參與共識的節(jié)點大概率為誠實節(jié)點。同時，在共識過程中，認(rèn)為每個節(jié)點都能夠做出自己的判斷，主節(jié)點僅負(fù)責(zé)匯總所有的判斷，然后做出最終決策。因此，可以用半數(shù)以上投票確認(rèn)的方式驗證數(shù)據(jù)信息的真實性，進(jìn)而將原有的通信復(fù)雜度2n2降至2n?；诤喕囊恢滦詤f(xié)議，RN-VPBFT 算法共識過程如圖7 所示，其中，Client 表示客戶端，Superior node 表示監(jiān)督節(jié)點，Primary node 表示主節(jié)點，Replica 1，2，3 表示共識節(jié)點，Replica 4 表示備份節(jié)點。

圖7 RN-VPBFT 算法共識過程Fig.7 Consensus process of RN-VPBFT algorithm

主節(jié)點在對所有判斷進(jìn)行匯總并采用多數(shù)決定原則做出判斷后，需要向所有備份節(jié)點廣播每個節(jié)點對該信息的判斷情況以及最終的決策情況。RN-VPBFT算法共識過程的簡要流程如下：

1）當(dāng)某一節(jié)點需要對數(shù)據(jù)庫進(jìn)行更新操作時，首先向主節(jié)點提出請求，主節(jié)點收到請求后可將待更新的數(shù)據(jù)通過式（10）發(fā)送給所有的共識節(jié)點進(jìn)行驗證：

2）每個共識節(jié)點收到主節(jié)點發(fā)送的消息后，對消息的真實性做出判斷，并將自身對消息的判斷通過式（11）發(fā)送回主節(jié)點。

3）當(dāng)主節(jié)點收到至少2f+1 個來自不同節(jié)點的信息時，對該數(shù)據(jù)信息進(jìn)行最終判斷，并將最終判斷結(jié)果返回給系統(tǒng)中的所有節(jié)點。

需要注意的是，當(dāng)主節(jié)點中存儲的已驗證的數(shù)據(jù)信息達(dá)到一定數(shù)量時，主節(jié)點必須將這些信息打包并廣播給系統(tǒng)中的所有節(jié)點。

在整個共識過程中，節(jié)點間傳遞的信息量較傳統(tǒng)PBFT 算法減少了視圖編號信息以及信息摘要，取而代之的是節(jié)點對獲得消息做出判斷。

2.5 結(jié)束階段

RN-VPBFT 結(jié)束階段主要完成數(shù)據(jù)打包、節(jié)點信譽值更新、惡意節(jié)點記錄等工作，如圖8 所示。信譽值更新的偽代碼如算法1 所示。

圖8 RN-VPBFT 算法結(jié)束階段示意圖Fig.8 Schematic diagram of the end stage of the RN-VPBFT algorithm

定義1共識輪數(shù)R指在一個共識階段中達(dá)成共識次數(shù)Rs與未達(dá)成共識次數(shù)Rf的總和。根據(jù)主節(jié)點選舉規(guī)則，為確保理論上每個共識階段中所有共識節(jié)點都有機會擔(dān)任主節(jié)點，R和N1的關(guān)系一般滿足R=2N1。

定義2每R個共識輪數(shù)稱為一個共識階段St。當(dāng)系統(tǒng)進(jìn)入一個新的共識階段后，需要對系統(tǒng)內(nèi)部節(jié)點的信譽值進(jìn)行更新，然后重新確定各節(jié)點的角色。

在每個共識階段結(jié)束后，監(jiān)督節(jié)點根據(jù)系統(tǒng)中所有節(jié)點在當(dāng)前共識階段的表現(xiàn)并綜合節(jié)點在前一輪共識階段的表現(xiàn)，按照式（12）對每個節(jié)點的信譽值進(jìn)行更新，并通過式（13）發(fā)送給各個節(jié)點。各個節(jié)點收到監(jiān)督節(jié)點的消息后進(jìn)行驗證，待驗證結(jié)束后監(jiān)督節(jié)點根據(jù)其他節(jié)點的反饋，再對自身的信譽值進(jìn)行更新。待所有節(jié)點完成信譽值更新后，系統(tǒng)會記錄當(dāng)前階段出現(xiàn)的惡意節(jié)點編號，所有被記錄的節(jié)點在之后的所有過程中只能充當(dāng)備份節(jié)點，根據(jù)主節(jié)點發(fā)送的消息更新本地信息。

其中：α、β為加權(quán)系數(shù)，滿足α+β=1；T1表示信譽值更新規(guī)則；表示更新后的節(jié)點信譽值；behaviour 表示節(jié)點在當(dāng)前共識階段中的表現(xiàn)；role 表示節(jié)點在上一階段系統(tǒng)中擔(dān)任的角色。

對于不同的節(jié)點類型，α、β、T1的取值不同，同時考慮到節(jié)點更新后的信譽值在很大程度上應(yīng)由節(jié)點在本輪共識階段的表現(xiàn)決定，因此α≤β。根據(jù)上文對每個節(jié)點在系統(tǒng)中的職能，將各類節(jié)點按照在系統(tǒng)中的作用做如下排序：監(jiān)督節(jié)點>主節(jié)點>共識節(jié)點>備份節(jié)點，并根據(jù)節(jié)點的作用大小，設(shè)置不同參數(shù)α、β、T1，如表1 所示。

表1 信譽值更新參數(shù)Table 1 Reputation value update parameters

為了貼近實際，假設(shè)備份節(jié)點能夠在接收到主節(jié)點發(fā)送的信息后及時對本地數(shù)據(jù)進(jìn)行更新而不會惡意篡改數(shù)據(jù)，不存在惡意行為。此外，所有誠實節(jié)點的信譽值范圍為0～1，惡意節(jié)點的信譽值不超過0.5。設(shè)置節(jié)點信譽值動態(tài)更新機制既可以有效減少惡意節(jié)點對系統(tǒng)的不利影響，鼓勵節(jié)點遵守系統(tǒng)規(guī)則，又可以保證節(jié)點的積極性，防止高信任度節(jié)點在共識過程中出現(xiàn)的惡意行為，激勵節(jié)點在共識過程中做出誠實行為。與現(xiàn)有多數(shù)改進(jìn)算法中設(shè)置的獎懲函數(shù)不同，本文設(shè)計的獎懲函數(shù)在此基礎(chǔ)上還能很好地區(qū)分惡意節(jié)點與誠實節(jié)點，并且保證所有誠實節(jié)點的信譽值相近，降低了系統(tǒng)集中化的可能性。

3 實驗與結(jié)果分析

實驗通過對比多種共識算法在容錯性、節(jié)點信譽值、通信復(fù)雜度以及系統(tǒng)集中化趨勢4 個方面的表現(xiàn)，測試RN-VPBFT 共識算法的性能。實驗環(huán)境為Windows 10 操作系統(tǒng)，系統(tǒng)內(nèi)存為16 GB，CPU 為Intel Core i7 處理器。實驗基于Python 對RNVPBFT、PBFT、CPBFT、RC-VPBFT 在內(nèi)的多種共識算法進(jìn)行模擬仿真，開發(fā)語言為Python 3.7。

3.1 容錯性分析

假定節(jié)點總數(shù)是N，故障或者惡意節(jié)點數(shù)為f，剩余正確節(jié)點數(shù)為N-f，RN-VPBFT 和傳統(tǒng)PBFT 共識算法本質(zhì)上相同，只要收到N-f個消息且N-f>f就能做出決定，但N-f個消息中可能存在f個惡意節(jié)點冒充的消息（或因網(wǎng)絡(luò)延遲導(dǎo)致f個惡意節(jié)點的消息先被收到），則正確消息數(shù)為N-f-f。為達(dá)到多數(shù)一致，正確消息必須占多數(shù)，也就是N-f-f>f，因此N至少等于3f+1。

3.2 節(jié)點信譽值分析

利用Python 搭建小型區(qū)塊鏈系統(tǒng)，系統(tǒng)共設(shè)30 個節(jié)點，包含9 個拜占庭節(jié)點。每次實驗經(jīng)過4 個共識階段，每個階段包含40 輪共識過程，分別對每個階段結(jié)束后各節(jié)點的信譽值進(jìn)行記錄，如圖9 所示。每個共識階段結(jié)束后，所有誠實節(jié)點之間信譽值的最大差值如表2 所示。

圖9 各共識階段不同節(jié)點的信譽值分布Fig.9 Reputation value distribution of different nodes in each consensus stage

表2 共識階段結(jié)束后誠實節(jié)點之間信譽值的最大差值Table 2 Maximum difference in reputation value between honest nodes after the consensus phase ends

結(jié)合圖9 和表2 可分析得出：

1）系統(tǒng)中惡意節(jié)點的編號分別為7、10、12、16、17、20、22、26、29。

2）在共識階段2 結(jié)束后，系統(tǒng)中的誠實節(jié)點與惡意節(jié)點已基本能夠通過信譽值的大小進(jìn)行區(qū)分，進(jìn)而保證了整個系統(tǒng)后續(xù)運行的安全性與穩(wěn)定性。

3）隨著共識過程的進(jìn)行，各階段在誠實節(jié)點處的曲折程度趨向平穩(wěn)，誠實節(jié)點的信譽值差距逐漸減小。

4）節(jié)點編號為7、10、17、26 的錯誤節(jié)點在共識階段1 后信譽值均超過了閾值0.5，主要原因是這4 個節(jié)點相較于其他錯誤節(jié)點初始信譽值更低，在共識階段1中沒有能夠獲得擔(dān)任主節(jié)點以及監(jiān)督節(jié)點的權(quán)利，因此未被系統(tǒng)發(fā)現(xiàn)，但在共識階段1 后，其擔(dān)任了對應(yīng)角色，最終被系統(tǒng)記錄。各共識階段成功達(dá)成共識的輪數(shù)如表3 所示。由表3 中數(shù)據(jù)可知，共識階段1 的共識成功率較低，這是因為節(jié)點的初始信譽值主要依靠節(jié)點之間投票決定，具有一定的偶然性，可能會出現(xiàn)部分惡意節(jié)點獲得較高的初始信譽度的情況，但隨著共識過程的不斷深入，系統(tǒng)將所有惡意節(jié)點一一記錄，共識成功率達(dá)到100%。

表3 各共識階段成功達(dá)成共識的輪數(shù)Table 3 The number of rounds that successful reached consensus at each consensus stage

3.3 通信復(fù)雜度分析

在PBFT 算法中，廣播消息需要進(jìn)行預(yù)準(zhǔn)備、準(zhǔn)備和確認(rèn)3 個階段的通信，對應(yīng)的通信次數(shù)分別為N、N2和N2。在計算其與用戶端的通信次數(shù)后，PBFT 算法中一個完整的共識過程所需的通信次數(shù)如下：

現(xiàn)有研究結(jié)果僅比較了傳統(tǒng)算法與改進(jìn)算法在共識過程中的通信復(fù)雜度，忽略了節(jié)點因分類、投票等過程給系統(tǒng)帶來的額外通信復(fù)雜度。本文綜合考慮了上述因素，將RN-VPBFT 與PBFT、CPBFT、RC-VPBFT 算法的通信復(fù)雜度進(jìn)行分析比較，結(jié)果如圖10 所示。

圖10 不同算法的通信復(fù)雜度比較Fig.10 Comparison of communication complexity among different algorithms

由圖10 可以看出：CPBFT 算法雖然在共識階段將通信復(fù)雜度降至N2-N-1，但綜合考慮在共識階段之前的通信次數(shù)，總的通信次數(shù)為T=N2+N-1+N2-N-2=2N2-3，相較于PBFT算法提升較??；RC-VPBFT算法雖然在整個共識過程中需要的通信次數(shù)僅為4N+1，但是在此之前需要進(jìn)行聚類工作，這也在一定程度上增加了通信復(fù)雜度；RN-VPBFT 算法在假設(shè)所有過程中的所有節(jié)點都進(jìn)行了相關(guān)數(shù)據(jù)驗證的情況下，除了初始值確定需要額外的3N次通信外，每輪共識主要包括領(lǐng)導(dǎo)者選舉、共識、信譽值更新3 個階段，總的通信次數(shù)為T=2N1+2N1+N+2N≤7N，因此整個過程的通信復(fù)雜度由O（N2）降至O（N）。

3.4 系統(tǒng)集中化趨勢分析

區(qū)塊鏈的核心優(yōu)勢是去中心化，因此需要考慮共識算法對系統(tǒng)去中心化程度的影響。通過對同一區(qū)塊鏈系統(tǒng)分別使用RN-VPBFT 與VPBFT［25］算法，統(tǒng)計在使用不同共識算法后系統(tǒng)中各個節(jié)點擔(dān)任主節(jié)點的次數(shù)并進(jìn)行比較，結(jié)果如圖11、圖12 所示。由圖11、圖12 可以看出：VPBFT 算法主要通過投票選出特定節(jié)點作為主節(jié)點，其他節(jié)點被選為主節(jié)點的機會很小，使得整個系統(tǒng)傾向于成為一個集中式系統(tǒng)；RN-VPBFT 算法允許更多節(jié)點參與區(qū)塊生產(chǎn)活動，所有滿足要求的節(jié)點都有機會被選舉成為主節(jié)點，能夠更好地維護(hù)系統(tǒng)的去中心化特性。

圖11 VPBFT 算法中每個節(jié)點擔(dān)任主節(jié)點的次數(shù)Fig.11 The number of times each node becomes the primary node in the VPBFT algorithm

圖12 RN-VPBFT 算法中每個節(jié)點擔(dān)任主節(jié)點的次數(shù)Fig.12 The number of times each node becomes the primary node in the RN-VPBFT algorithm

4 結(jié)束語

針對傳統(tǒng)PBFT 共識算法容易出現(xiàn)集中化趨勢、通信復(fù)雜度高等問題，本文提出一種基于隨機數(shù)選舉與投票機制的RN-VPBFT 共識算法。引入兼具高風(fēng)險和高收益的監(jiān)督節(jié)點，避免了節(jié)點間因頻繁通信帶來的高通信復(fù)雜度。利用隨機參數(shù)確保了選舉的公平性，降低了系統(tǒng)的集中化趨勢。此外，依據(jù)節(jié)點不同身份設(shè)置的信譽值更新策略不僅能夠有效區(qū)分系統(tǒng)中的誠實節(jié)點與惡意節(jié)點，而且能夠在一定程度上簡化一致性協(xié)議并保證其安全與穩(wěn)定運行。實驗結(jié)果表明，RN-VPBFT 算法相比傳統(tǒng)PBFT 共識算法具有更好的去中心化特性，并且有效降低了通信復(fù)雜度。后續(xù)將在不改變算法效率及通信復(fù)雜度的基礎(chǔ)上增強拜占庭系統(tǒng)節(jié)點的容錯性，并且分析與研究系統(tǒng)節(jié)點數(shù)量的實時變化對共識算法的影響，進(jìn)一步提升系統(tǒng)容錯性及動態(tài)性。