基于信譽(yù)值投票與隨機(jī)數(shù)選舉的PBFT 共識(shí)算法

陳潤宇，王倫文，朱然剛

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

0 概述

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

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

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

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

1 實(shí)用拜占庭容錯(cuò)算法

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

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

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

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

圖1 PBFT 算法共識(shí)過程Fig.1 Consensus process of PBFT algorithm

PBFT 算法共識(shí)的簡(jiǎn)要流程如下：

1）消息請(qǐng)求。客戶端向主節(jié)點(diǎn)發(fā)送請(qǐng)求，如式（1）所示：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 RN-VPBFT 共識(shí)算法

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

2.1 RN-VPBFT 共識(shí)算法流程

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

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

2.2 初始信譽(yù)值確定

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

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

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

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

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

2.3 準(zhǔn)備階段

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

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

2.3.1 節(jié)點(diǎn)分類

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

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

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

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

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

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

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

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

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

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

1）所用時(shí)間證明

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

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

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

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

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

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

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

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

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

2.4 共識(shí)階段

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

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

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

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

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

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

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

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

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

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

2.5 結(jié)束階段

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

3.1 容錯(cuò)性分析

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

3.2 節(jié)點(diǎn)信譽(yù)值分析

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

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

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

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

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

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

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

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

表3 各共識(shí)階段成功達(dá)成共識(shí)的輪數(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 個(gè)階段的通信，對(duì)應(yīng)的通信次數(shù)分別為N、N2和N2。在計(jì)算其與用戶端的通信次數(shù)后，PBFT 算法中一個(gè)完整的共識(shí)過程所需的通信次數(shù)如下：

現(xiàn)有研究結(jié)果僅比較了傳統(tǒng)算法與改進(jìn)算法在共識(shí)過程中的通信復(fù)雜度，忽略了節(jié)點(diǎn)因分類、投票等過程給系統(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 算法雖然在共識(shí)階段將通信復(fù)雜度降至N2-N-1，但綜合考慮在共識(shí)階段之前的通信次數(shù)，總的通信次數(shù)為T=N2+N-1+N2-N-2=2N2-3，相較于PBFT算法提升較?。籖C-VPBFT算法雖然在整個(gè)共識(shí)過程中需要的通信次數(shù)僅為4N+1，但是在此之前需要進(jìn)行聚類工作，這也在一定程度上增加了通信復(fù)雜度；RN-VPBFT 算法在假設(shè)所有過程中的所有節(jié)點(diǎn)都進(jìn)行了相關(guān)數(shù)據(jù)驗(yàn)證的情況下，除了初始值確定需要額外的3N次通信外，每輪共識(shí)主要包括領(lǐng)導(dǎo)者選舉、共識(shí)、信譽(yù)值更新3 個(gè)階段，總的通信次數(shù)為T=2N1+2N1+N+2N≤7N，因此整個(gè)過程的通信復(fù)雜度由O（N2）降至O（N）。

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

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

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

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

4 結(jié)束語

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