李 騰，程 哲，賈東立，賈耀清

(河北工程大學(xué)信息與電氣工程學(xué)院,河北 邯鄲 056038)

1 引言

隨著計算機(jī)和網(wǎng)絡(luò)的發(fā)展，計算機(jī)系統(tǒng)提供的服務(wù)和功能越來越多地被人們使用。近年來，隨著比特幣[1]的巨大成功，出現(xiàn)了一種新的分布式系統(tǒng)應(yīng)用“區(qū)塊鏈”并受到了高度重視。主流的分類方法將區(qū)塊鏈分為3類:公有鏈、聯(lián)盟鏈和私有鏈[2]。不同類型的區(qū)塊鏈對節(jié)點(diǎn)數(shù)量和工作要求都不一樣，但都需要保證節(jié)點(diǎn)的一致性。對共識算法的研究由此而生，不同類型的共識算法逐漸出現(xiàn)，比如適用于公有鏈的工作量證明POW(Proof-Of-Work)算法[3]和股權(quán)權(quán)益證明POS(Proof Of Stake)算法，適用于聯(lián)盟鏈的實(shí)用拜占庭容錯算法PBFT(Practical Byzantine Fault Tolerance)共識算法[4]，適用于私有鏈的Raft共識算法等。

拜占庭容錯源自于古羅馬拜占庭將軍問題[5]。如何在存在惡意節(jié)點(diǎn)的網(wǎng)絡(luò)系統(tǒng)中，保證系統(tǒng)的穩(wěn)定運(yùn)行以及信息的一致性、完整性和安全性，正是拜占庭將軍模型在去中心化網(wǎng)絡(luò)和分布式系統(tǒng)中所反映的問題，也是區(qū)塊鏈中共識算法所需要解決的問題。

為解決拜占庭容錯問題，20世紀(jì)80年代，Lamport等[6]提出了著名的拜占庭容錯BFT(Byzantine Fault Tolerance)共識算法。BFT共識算法中節(jié)點(diǎn)之間相互發(fā)送消息進(jìn)行數(shù)據(jù)的傳遞和同步，另外還需要額外的時鐘同步機(jī)制支持，算法的復(fù)雜度也是隨著節(jié)點(diǎn)增加呈指數(shù)級增大。BFT 算法由于需要展示其理論上的可行性而缺乏實(shí)用性，但是其提供的思路在解決拜占庭問題上是一種創(chuàng)新，減少了POW算法大量的資源消耗。

1999年，基于BFT共識算法，Castro等[4]提出了實(shí)用性拜占庭容錯PBFT共識算法，由拜占庭容錯帶來的系統(tǒng)開銷被大幅度降低。PBFT共識算法是一類狀態(tài)機(jī)拜占庭系統(tǒng)，其要求共同維護(hù)一個狀態(tài)，所有節(jié)點(diǎn)采取的行動一致。因?yàn)楦鱾€節(jié)點(diǎn)達(dá)成共識是在同一時刻決定的，不用等待確認(rèn)以保證當(dāng)前區(qū)塊所在的鏈?zhǔn)亲铋L鏈，所以采用PBFT共識算法的區(qū)塊鏈不會像POW算法那樣存在鏈分叉，保持了系統(tǒng)的活性[7]。

目前PBFT共識算法還存在很多不足。對于P2P[8]網(wǎng)絡(luò)來說，節(jié)點(diǎn)應(yīng)該相互通信而不是客戶端請求直接發(fā)送到主節(jié)點(diǎn)。而且由于PBFT共識算法采用C/S架構(gòu)[9]，節(jié)點(diǎn)在加入時系統(tǒng)不能及時回應(yīng)，無法正確回應(yīng)處理請求。主節(jié)點(diǎn)的選舉是按照編號輪流選取，選舉方式比較隨意，對主節(jié)點(diǎn)的可靠性沒有進(jìn)行驗(yàn)證，因此很有可能選舉出惡意節(jié)點(diǎn)，盡管惡意節(jié)點(diǎn)可以在視圖變更時被推翻，但頻繁地更換主節(jié)點(diǎn)和視圖變更會導(dǎo)致大量資源的浪費(fèi)，并降低系統(tǒng)效率。主節(jié)點(diǎn)選舉完成之后，因?yàn)榫W(wǎng)絡(luò)等原因會導(dǎo)致各個節(jié)點(diǎn)的狀態(tài)不一致[10]，需要完善的同步數(shù)據(jù)過程。共識過程通信開銷較大，需要進(jìn)行優(yōu)化和改進(jìn)。

2 PBFT共識算法流程

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，對PBFT共識算法的改進(jìn)研究明顯增多，例如，無主節(jié)點(diǎn)排序的HQ(Hybrid Quorum)算法[11]、基于投機(jī)的Zyzzyva 算法[12]和以主節(jié)點(diǎn)切換為代價進(jìn)行優(yōu)化的spining 算法[13]等。而在針對區(qū)塊鏈應(yīng)用場景進(jìn)行優(yōu)化方面，主要有POS與PBFT 結(jié)合的Tendermint[14]和DPOS(Delegated Proof Of Stake)[15]與PBFT結(jié)合的dBFT(delegated Byzantine Fault Tolerance)[16]算法等。 通過以上分析發(fā)現(xiàn)，區(qū)塊鏈共識算法及其變種都是基于PBFT共識算法的，所以本文選取PBFT 共識算法作為研究對象。

在PBFT共識算法中，客戶端是請求的發(fā)送端，主節(jié)點(diǎn)負(fù)責(zé)接收請求，并且按照順序?qū)φ埱笈判?，從?jié)點(diǎn)主要負(fù)責(zé)檢查從主節(jié)點(diǎn)發(fā)來的請求，并通過超時機(jī)制檢測主節(jié)點(diǎn)是否出錯，發(fā)生出錯時觸發(fā)視圖更換協(xié)議。PBFT共識算法流程如圖1所示。其中，Node0為主節(jié)點(diǎn)，Node3為出錯節(jié)點(diǎn)。

Figure 1 Flow chart of PBFT consensus algorithm圖1 PBFT共識算法流程

PBFT共識算法流程分為5個階段，每個階段的工作方式和作用分別介紹如下：

(1)請求階段(Request)：客戶端c產(chǎn)生交易數(shù)據(jù)并向主節(jié)點(diǎn)發(fā)送處理交易的請求消息〈REQUEST,m,t,c〉，其中,t是時間戳，m是需要共識的內(nèi)容。請求階段的主要作用是將需要共識的消息傳遞到主節(jié)點(diǎn)。

(2)預(yù)準(zhǔn)備階段(Pre-prepare)：主節(jié)點(diǎn)收到請求后為需要共識的內(nèi)容m分配序號，然后向所有從節(jié)點(diǎn)廣播預(yù)準(zhǔn)備消息〈〈PRE-PREPARE,v,N,d〉,m〉，其中,v是視圖編號，N表示消息m的序號，d是請求消息m的摘要。視圖編號v、消息序號N和摘要d是節(jié)點(diǎn)收到預(yù)準(zhǔn)備消息后要檢查的內(nèi)容。預(yù)準(zhǔn)備階段完成了共識內(nèi)容的序號分配和從主節(jié)點(diǎn)傳遞到所有從節(jié)點(diǎn)的工作。

(3)準(zhǔn)備階段(Prepare)：編號為i的從節(jié)點(diǎn)收到預(yù)準(zhǔn)備消息后，首先對消息的簽名、消息序號N和摘要d進(jìn)行驗(yàn)證。若驗(yàn)證通過，則將向所有從節(jié)點(diǎn)廣播準(zhǔn)備消息〈PREPARE,v,N,d,i〉。當(dāng)節(jié)點(diǎn)收到2f+1(f表示PBFT共識算法可容忍的錯誤節(jié)點(diǎn)數(shù)量)個從不同從節(jié)點(diǎn)發(fā)送的與預(yù)準(zhǔn)備消息一致的準(zhǔn)備消息后，準(zhǔn)備階段完成。準(zhǔn)備階段完成對預(yù)準(zhǔn)備階段和準(zhǔn)備階段收到的視圖編號、共識內(nèi)容m分配的序號和消息內(nèi)容的驗(yàn)證任務(wù)。

(4)確認(rèn)階段(Commit):從節(jié)點(diǎn)完成準(zhǔn)備階段后進(jìn)入確認(rèn)階段。從節(jié)點(diǎn)i向所有節(jié)點(diǎn)廣播確認(rèn)消息〈COMMIT,v,N,D(m),i〉,其中D(m)是對消息m的驗(yàn)證簽名。從節(jié)點(diǎn)在收到確認(rèn)消息后會檢查消息簽名和視圖編號是否一致，若檢查通過并接收到2f+1個與預(yù)準(zhǔn)備消息一致的確認(rèn)消息，則確認(rèn)階段完成。這一階段的作用是確保所有節(jié)點(diǎn)對本地確認(rèn)的請求的序號達(dá)成一致。

(5)回復(fù)階段(Replay):回復(fù)階段的作用是將共識成功信息發(fā)送給客戶端?；貜?fù)消息格式為〈REPLAY,v,c,i,r〉，其中r是請求的執(zhí)行結(jié)果。

對PBFT共識算法流程分析可知，算法存在著以下不足：

(1) 客戶端只向主節(jié)點(diǎn)發(fā)送請求，當(dāng)請求過多時容易造成主節(jié)點(diǎn)過載，可靠性降低，系統(tǒng)運(yùn)行消耗增加，而且這種方式也不適合區(qū)塊鏈的點(diǎn)對點(diǎn)網(wǎng)絡(luò)。

(2) 主節(jié)點(diǎn)選取比較隨意，無法保證節(jié)點(diǎn)的可靠性，如果連續(xù)選取惡意節(jié)點(diǎn)作為主節(jié)點(diǎn)，則會極大地增加系統(tǒng)消耗，降低系統(tǒng)的穩(wěn)定性和可靠性；選擇主節(jié)點(diǎn)后沒有完備的數(shù)據(jù)同步過程，節(jié)點(diǎn)之間的數(shù)據(jù)無法更好地達(dá)成一致。

(3) 算法擴(kuò)展性差，沒有完善的節(jié)點(diǎn)加入或退出機(jī)制。節(jié)點(diǎn)加入或退出時，系統(tǒng)需要重新啟動，開銷較大。如果系統(tǒng)中的節(jié)點(diǎn)更換頻率較大，將會大大降低系統(tǒng)的可用性。

(4) 共識過程網(wǎng)絡(luò)消耗較大，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較多時通信非常頻繁，容易造成網(wǎng)絡(luò)擁堵，影響請求正確執(zhí)行。

3 RPBFT共識算法設(shè)計

3.1 算法主要思想

基于角色控制的拜占庭容錯RPBFT (Role management-based Practical Byzantine Fault Tolerant)共識算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為3種類型的角色，分別是管理者(Manager)、候選者(Candidate)和普通節(jié)點(diǎn)(Normal)，通過選舉機(jī)制和獎勵機(jī)制對節(jié)點(diǎn)的角色類型進(jìn)行轉(zhuǎn)換和管理，以達(dá)到提高效率、增加可靠性和動態(tài)性的目的。針對PBFT共識算法中存在的不足，本文主要在以下幾個方面進(jìn)行了改進(jìn)：

(1) 為更好地適應(yīng)點(diǎn)對點(diǎn)網(wǎng)絡(luò)，改變客戶端單點(diǎn)提交請求到主節(jié)點(diǎn)的方案，而是向所有節(jié)點(diǎn)發(fā)送帶有時間戳和簽名信息的交易數(shù)據(jù)。

(2) 將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為3種角色。普通節(jié)點(diǎn)服從管理者的安排，只負(fù)責(zé)完成交易。候選者不僅要服從管理者對交易內(nèi)容進(jìn)行分析，而且還要監(jiān)督管理者的行為。管理者出現(xiàn)惡意行為時，將被降級為普通節(jié)點(diǎn)，候選者開始選舉管理者的過程。管理者的主要職責(zé)是負(fù)責(zé)接收客戶端的請求，同時對這些消息進(jìn)行排序，分配編號，再向網(wǎng)絡(luò)中廣播請求消息。3種角色的節(jié)點(diǎn)在一定條件下可以相互轉(zhuǎn)換，為新節(jié)點(diǎn)加入或退出提供了保證，提高了系統(tǒng)的可擴(kuò)展性。

(3) 增加選舉過程和獎勵機(jī)制。用2種機(jī)制對節(jié)點(diǎn)的角色分配進(jìn)行管理。候選者是系統(tǒng)網(wǎng)絡(luò)重要組成部分。獎勵機(jī)制下，所有節(jié)點(diǎn)每完成一次交易，都對其信用積分累計加一。當(dāng)信用積分滿足一定條件的時候，普通節(jié)點(diǎn)升級成為候選者，管理者是通過候選者之間的選舉產(chǎn)生的。2種機(jī)制確保管理者節(jié)點(diǎn)具有最高的信用積分和最大交易序列號，降低了隨意選取主節(jié)點(diǎn)帶來的風(fēng)險，提高了系統(tǒng)安全性。

(4) 增加數(shù)據(jù)同步及驗(yàn)證過程，在管理者選舉完成之后進(jìn)行數(shù)據(jù)同步，并且副本節(jié)點(diǎn)在同步過程中對主節(jié)點(diǎn)和數(shù)據(jù)進(jìn)行驗(yàn)證，驗(yàn)證沒有問題，說明管理者可靠，然后開始新的共識過程。

(5) 改進(jìn)共識算法通信過程，去掉確認(rèn)階段。在去掉確認(rèn)階段的情況下，需要保證共識過程中發(fā)生視圖變更后系統(tǒng)節(jié)點(diǎn)狀態(tài)的一致性。本文使用交易序列號和區(qū)塊高度來判定區(qū)塊狀態(tài)，舍棄視圖這個概念，發(fā)生視圖變更時通過重新選舉來保證一致性。發(fā)生網(wǎng)絡(luò)擁堵或節(jié)點(diǎn)惡意行為導(dǎo)致需要視圖變更時，系統(tǒng)進(jìn)入重新選舉的過程，以此來消除系統(tǒng)可能面臨的不一致性。

3.2 算法流程

系統(tǒng)初始化時，選取節(jié)點(diǎn)編號較小的2f+1個節(jié)點(diǎn)作為初始候選者。然后進(jìn)行選舉過程選出管理者，管理者通過發(fā)送數(shù)據(jù)塊和序列號與所有節(jié)點(diǎn)進(jìn)行數(shù)據(jù)同步達(dá)到狀態(tài)一致，即存儲數(shù)據(jù)、最大序列號和區(qū)塊高度等信息完全一致。采用密碼技術(shù)保證數(shù)據(jù)傳遞過程中的完整性和安全性，定義Si為消息簽名，Di為消息摘要。節(jié)點(diǎn)初始化完成之后系統(tǒng)開始認(rèn)證(Authentication)和提交(Submit)2個階段的共識過程。

RPBFT共識算法流程如圖2所示，各階段具體過程描述如下:

Figure 2 Flow chart of RPBFT consensus algorithm圖2 RPBFT共識算法流程

客戶端c廣播請求到所有節(jié)點(diǎn)，共識節(jié)點(diǎn)收到請求后驗(yàn)證交易簽名并將驗(yàn)證成功的交易數(shù)據(jù)存儲在自己的內(nèi)存中。

(1)認(rèn)證階段(Authentication):管理者收到請求后為交易數(shù)據(jù)分配序號N，然后向所有節(jié)點(diǎn)廣播認(rèn)證消息〈〈AUTHENTICATION,cp,N,Si,Di〉,data〉，其中,cp(credit points)是節(jié)點(diǎn)信用積分值，data是需要共識的交易數(shù)據(jù)。從節(jié)點(diǎn)i∈{0,1,…,|R|-1}(|R|為節(jié)點(diǎn)總數(shù))在接收到認(rèn)證消息時會對消息序號N、信用積分cp、簽名和摘要進(jìn)行檢驗(yàn)，如果同意認(rèn)證消息，則進(jìn)入提交階段，如果不同意，則對管理者產(chǎn)生質(zhì)疑，廣播重新選舉消息。

(2)提交階段(Submit):進(jìn)入提交階段后，所有從節(jié)點(diǎn)向除自己以外的節(jié)點(diǎn)廣播提交消息〈SUBMIT,N,Si,Di,i〉。節(jié)點(diǎn)收到提交消息后對消息序號N、信用積分cp、簽名和摘要進(jìn)行檢驗(yàn)，認(rèn)證成功將認(rèn)證消息和提交消息寫入消息日志。節(jié)點(diǎn)收到2f+1個來自不同從節(jié)點(diǎn)且與認(rèn)證消息一致的提交消息時，提交階段完成。如果在一定的時間內(nèi)沒有收集到足夠多的消息，則認(rèn)定此交易過程失效，發(fā)起重新選舉過程。

當(dāng)節(jié)點(diǎn)完成提交階段后向管理者發(fā)送已完成消息，管理者收到來自2f+1個不同節(jié)點(diǎn)的完成消息時，對客戶端進(jìn)行回復(fù)。

3.3 獎勵機(jī)制

信用積分cp是衡量節(jié)點(diǎn)可信任程度的指標(biāo)，節(jié)點(diǎn)成功完成交易任務(wù)數(shù)量越多，信用積分值越高，所有節(jié)點(diǎn)根據(jù)信用積分值cp的不同分為不同角色。初始狀態(tài)下所有節(jié)點(diǎn)cp值為0，選舉管理者之后每次完成管理者分配的交易任務(wù)即提交階段完成，cp值加1并且記錄在自己的日志中。由于網(wǎng)絡(luò)延遲或節(jié)點(diǎn)惡意行為導(dǎo)致節(jié)點(diǎn)無法完成任務(wù)，節(jié)點(diǎn)需要接受降級懲罰。管理者發(fā)生故障時，信用積分清除到初始狀態(tài)，并將角色類型變?yōu)槠胀ü?jié)點(diǎn)，管理者自身發(fā)起重新選舉過程；候選者發(fā)生故障時，信用積分清除到初始狀態(tài)，并降級成為普通節(jié)點(diǎn)。

信用積分在選舉管理者和推選候選者中具有重要的作用。在選舉過程中，候選者通過發(fā)起投票選舉出信用積分最大的候選者，當(dāng)選者升級成為管理者，然后進(jìn)行數(shù)據(jù)同步和驗(yàn)證。候選者是共識節(jié)點(diǎn)的主要部分，是保證系統(tǒng)可靠性和穩(wěn)定性的重要力量。候選者的數(shù)量要占系統(tǒng)節(jié)點(diǎn)數(shù)量的大多數(shù)，假設(shè)算法可容錯節(jié)點(diǎn)數(shù)量為f，則候選者的數(shù)量至少需要2f，確保即使在有f個候選者出現(xiàn)錯誤時，候選者數(shù)量依然可以代表系統(tǒng)的決策。候選者數(shù)量的保證，也可以在選舉管理者時更加公平，避免惡意操縱候選者選舉出惡意管理者帶來的危險。在數(shù)據(jù)同步驗(yàn)證過程中，管理者統(tǒng)計由不同節(jié)點(diǎn)發(fā)送來的信用積分值并選擇2f個信用積分較高的從節(jié)點(diǎn)分配為候選者。

為避免在短時間內(nèi)通過大量交易刷信用積分的惡意行為，在管理者內(nèi)部設(shè)立一個閾值K，當(dāng)在一定時間內(nèi)來自同一個節(jié)點(diǎn)的交易數(shù)量大于或等于K時，管理者認(rèn)為該節(jié)點(diǎn)具有惡意行為，將該節(jié)點(diǎn)降級為普通節(jié)點(diǎn)并清除其信用積分。

3.4 選舉過程

管理者的選舉依據(jù)最大信用積分原則，選出候選者中信用積分(cp)最大即擁有最多完成交易記錄的節(jié)點(diǎn)作為管理者。系統(tǒng)在沒有管理者或管理者出錯的情況下發(fā)起選舉。

節(jié)點(diǎn)收到選舉消息后，判斷自己的角色，候選者首先將自己的cp值記錄下來，然后對照存儲的候選者列表將自己的cp值發(fā)送給所有候選者。候選者在收到所有候選者cp值后進(jìn)行比較，如果cp值小于自己存儲的值，則什么也不做；如果cp值與自己所存儲的值相等，則比較節(jié)點(diǎn)編號，將節(jié)點(diǎn)編號較小的節(jié)點(diǎn)和cp值存入內(nèi)存中；如果cp值大于存儲的值，則清除原來存儲，更換為較大的cp值。當(dāng)cp值比較完成之后，將更新后的cp值及其節(jié)點(diǎn)編號廣播給所有候選者，候選者如果收到了f+1個來自不同候選者的內(nèi)容一致的投票消息，則更新自己的存儲，給消息中的目標(biāo)節(jié)點(diǎn)發(fā)送確認(rèn)消息。候選者收到至少f+1個來自不同候選者發(fā)送的確認(rèn)消息后升級成為管理者。

管理者在發(fā)生錯誤或由于網(wǎng)絡(luò)原因?qū)е鲁霈F(xiàn)不一致性時，將被降級為普通節(jié)點(diǎn)，然后由候選者發(fā)起新一輪的投票，投票過程與上述相同。

管理者選擇完成之后，為使各節(jié)點(diǎn)保持狀態(tài)一致并進(jìn)一步驗(yàn)證管理者是否為惡意節(jié)點(diǎn)，需要管理者發(fā)起數(shù)據(jù)同步和驗(yàn)證過程。具體過程如下：

管理者發(fā)送同步數(shù)據(jù)請求消息，消息格式為〈SYN-REQUEST,cp,Si,i〉，其他節(jié)點(diǎn)收到請求消息后，對比自己cp值，如果沒有異議，則向管理者回復(fù)確認(rèn)同步消息，消息格式為〈SYN- COMMIT,Si,i〉；如果產(chǎn)生質(zhì)疑則向所有節(jié)點(diǎn)廣播否定同步消息，并發(fā)起重新選舉過程。

在管理者收到2f+1個不同節(jié)點(diǎn)發(fā)送的確認(rèn)同步消息后，進(jìn)入數(shù)據(jù)同步階段，發(fā)送數(shù)據(jù)同步消息〈〈SYN-DATA,cp,Si,i〉,data〉。節(jié)點(diǎn)收到同步數(shù)據(jù)消息后，更新自己的備份數(shù)據(jù)區(qū)塊，向其他節(jié)點(diǎn)廣播同步成功消息，當(dāng)節(jié)點(diǎn)收到2f+1個來自不同節(jié)點(diǎn)的對數(shù)據(jù)同步消息的同步成功消息后，數(shù)據(jù)同步和驗(yàn)證過程完成。選舉和數(shù)據(jù)同步驗(yàn)證過程如圖3所示。

Figure 3 Schematic diagram of election process and data synchronization圖3 選舉過程和數(shù)據(jù)同步示意圖

3.5 節(jié)點(diǎn)加入和退出

本文將共識節(jié)點(diǎn)分為3種角色，每種角色有自己的職責(zé)。普通節(jié)點(diǎn)在系統(tǒng)網(wǎng)絡(luò)中只負(fù)責(zé)對交易的處理和轉(zhuǎn)發(fā)，對候選者和管理者的狀態(tài)不產(chǎn)生影響，這樣有利于節(jié)點(diǎn)以普通節(jié)點(diǎn)的身份動態(tài)地加入系統(tǒng)網(wǎng)絡(luò)。

節(jié)點(diǎn)加入后處于無管理者狀態(tài)，發(fā)起對管理者的搜尋(Searching)過程。系統(tǒng)中的其它節(jié)點(diǎn)將告知其當(dāng)前管理者的消息，當(dāng)收到來自不同節(jié)點(diǎn)的2f+1個節(jié)點(diǎn)一致信息后，該節(jié)點(diǎn)與當(dāng)前管理者建立聯(lián)系，然后進(jìn)入工作狀態(tài)，如圖4所示。

Figure 4 Schematic diagram of adding new nodes圖4 新節(jié)點(diǎn)加入示意圖

候選者或者普通節(jié)點(diǎn)退出時，向所有節(jié)點(diǎn)廣播退出請求，管理者收到請求之后向除退出請求節(jié)點(diǎn)外的所有節(jié)點(diǎn)發(fā)送確認(rèn)消息；管理者退出時，向所有節(jié)點(diǎn)廣播退出請求并將降級為普通節(jié)點(diǎn)，同時啟動選舉過程。選舉過程完畢之后由新當(dāng)選的管理者發(fā)送確認(rèn)消息。其它節(jié)點(diǎn)收到確認(rèn)消息后查看是否與退出請求一致，如果一致則向退出請求節(jié)點(diǎn)發(fā)送退出回復(fù)消息。退出節(jié)點(diǎn)收到f+1個來自不同節(jié)點(diǎn)的退出回復(fù)消息時，節(jié)點(diǎn)退出成功，停止參與節(jié)點(diǎn)共識過程。

4 實(shí)驗(yàn)分析

本文是在PBFT共識算法的基礎(chǔ)上提出的RPBFT共識算法，對通信開銷、時延、動態(tài)性、可靠性和容錯性方面進(jìn)行了改進(jìn)和優(yōu)化。本節(jié)在配置為Iitel I5-337U處理器、8 GB內(nèi)存、256 GHz固態(tài)硬盤的Windows 10系統(tǒng)中，通過Java多線程機(jī)制模擬網(wǎng)絡(luò)中的共識節(jié)點(diǎn)通信過程。同時與PBFT共識算法進(jìn)行比較，以此驗(yàn)證改進(jìn)算法的有效性和可用性。

4.1 通信開銷

PBFT共識算法的通信開銷主要在預(yù)準(zhǔn)備、準(zhǔn)備、確認(rèn)和視圖更換過程中；RPBFT共識算法的通信開銷主要在認(rèn)證、提交2個階段和選舉、數(shù)據(jù)同步過程。

假設(shè)系統(tǒng)共識節(jié)點(diǎn)個數(shù)為n。PBFT共識算法預(yù)準(zhǔn)備階段主節(jié)點(diǎn)發(fā)送預(yù)準(zhǔn)備消息給所有從節(jié)點(diǎn)需要通信的次數(shù)為(n-1)。準(zhǔn)備階段從節(jié)點(diǎn)之間相互通信所需通信次數(shù)為(n-1)2。確認(rèn)階段每個節(jié)點(diǎn)向除自己以外的節(jié)點(diǎn)發(fā)送消息，所需通信次數(shù)為n(n-1)。即PBFT共識算法共識過程共需通信次數(shù)為2n(n-1)。視圖變更過程中，從節(jié)點(diǎn)廣播視圖變更消息所需通信次數(shù)為(n-1)2。主節(jié)點(diǎn)收到視圖變更消息后廣播確認(rèn)消息所需通信次數(shù)為(n-1)。若出現(xiàn)視圖變更的概率為p，則總共通信次數(shù)為：

Q=2n(n-1)+pn(n-1)

(1)

RPBFT共識過程沒有錯誤發(fā)生時，2階段的通信次數(shù)為n(n-1)。當(dāng)系統(tǒng)節(jié)點(diǎn)出錯或因網(wǎng)絡(luò)導(dǎo)致超時，進(jìn)行選舉過程，候選者將自己的節(jié)點(diǎn)信息發(fā)送至其他候選者，這一階段共需的通信次數(shù)為4(n-1)2/9。候選者收到其它節(jié)點(diǎn)信息并進(jìn)行比較之后，將更新信息發(fā)送至其他候選者，該過程通信次數(shù)為4(n-1)2/9。管理者發(fā)送同步數(shù)據(jù)請求，該過程通信次數(shù)為(n-1)。節(jié)點(diǎn)驗(yàn)證成功發(fā)送確認(rèn)同步過程的通信次數(shù)為(n-1)。確認(rèn)同步完畢之后，管理者向其它節(jié)點(diǎn)發(fā)起數(shù)據(jù)更新的通信次數(shù)為(n-1)。由此分析可知，總共通信次數(shù)為:

(2)

假設(shè)網(wǎng)絡(luò)環(huán)境相同，則每次通信對網(wǎng)絡(luò)的消耗相同。2種算法通信次數(shù)比值W如式(3)所示：

(3)

由式(3)可以得出，當(dāng)p=0時，W的值恒等于2，此時RPBFT共識算法的通信效率是PBFT共識算法的一半；當(dāng)p=1時，W的值趨近于1，此時2種算法的網(wǎng)絡(luò)通信次數(shù)相等；當(dāng)p<1時，W的值恒大于1，而且p的值越小，W的值越趨近于2。這說明在需要視圖變更情況出現(xiàn)較少時，RPBFT共識算法的共識過程通信開銷接近于PBFT共識算法的一半。多次實(shí)驗(yàn)結(jié)果表明，在運(yùn)行穩(wěn)定的區(qū)塊鏈環(huán)境中，系統(tǒng)發(fā)生視圖變更的概率很小，所以RPBFT共識算法的通信開銷會減少將近一半，有效降低了系統(tǒng)在共識過程中的通信開銷。

4.2 時延測試

共識時延作為衡量共識算法的重要指標(biāo)，在區(qū)塊鏈中表示交易從發(fā)起到完成的時間差。較低的時延使得區(qū)塊鏈的可用性和安全性更高。在同樣的網(wǎng)絡(luò)環(huán)境下，RPBFT共識算法通信次數(shù)更少，降低了共識延時。測試共識延時的計算方法如式(4)所示：

DelayTime=TSubmit-TAuthentication

(4)

其中，TSubmit為區(qū)塊完成共識確認(rèn)的時間，TAuthentication為認(rèn)證階段開始時間。固定交易數(shù)量為10個，在容錯節(jié)點(diǎn)數(shù)量不超過1的前提下，分別取4,5,6,7,8,9,10個節(jié)點(diǎn)進(jìn)行3組對照實(shí)驗(yàn)。對每組節(jié)點(diǎn)進(jìn)行多次測試取平均值，得出2種算法在相同條件下的共識延時對比，如圖5所示。

Figure 5 Consensus delay comparison between two algorithms圖5 2種算法共識延時對比

由圖5可知，RPBFT共識算法的時延明顯低于PBFT共識算法的，而且隨著節(jié)點(diǎn)數(shù)量的增加，2種算法時延差距也會變大。

4.3 動態(tài)性

PBFT共識算法采用靜態(tài)請求響應(yīng)模式，當(dāng)節(jié)點(diǎn)加入或退出時需要重新啟動系統(tǒng)和數(shù)據(jù)同步過程。RPBFT共識算法將整個網(wǎng)絡(luò)的節(jié)點(diǎn)分為3種不同的角色，并通過一定的機(jī)制控制角色之間的轉(zhuǎn)換。其中，候選者是系統(tǒng)的關(guān)鍵節(jié)點(diǎn)，候選者負(fù)責(zé)選舉管理者，并且候選者數(shù)量需要保證為系統(tǒng)節(jié)點(diǎn)數(shù)量的大多數(shù)。節(jié)點(diǎn)加入時增加了尋找管理者的過程，節(jié)點(diǎn)退出時增加了退出確認(rèn)過程，2個過程使系統(tǒng)可以感知節(jié)點(diǎn)加入或退出，相應(yīng)地調(diào)整候選者的數(shù)量，并保證系統(tǒng)的可靠性和穩(wěn)定性。

由此可見，RPBFT共識算法能夠在節(jié)點(diǎn)加入或退出時動態(tài)調(diào)整各個角色數(shù)量，避免了系統(tǒng)重啟的過程，減少了節(jié)點(diǎn)加入或退出時帶來的網(wǎng)絡(luò)資源消耗。

4.4 安全性

假設(shè)系統(tǒng)中有n個節(jié)點(diǎn)，每個節(jié)點(diǎn)出錯的概率為q,交易次數(shù)為M。在PBFT共識算法下主節(jié)點(diǎn)由式(5)計算得出：

P=vmodn

(5)

節(jié)點(diǎn)出錯后視圖編號變更為v+1，通過式(5)選擇主節(jié)點(diǎn)。假設(shè)在M次交易過程中每次出錯的節(jié)點(diǎn)均為當(dāng)前主節(jié)點(diǎn)編號加一的節(jié)點(diǎn)，此時視圖變更后選擇的主節(jié)點(diǎn)為上一個視圖的出錯節(jié)點(diǎn)，系統(tǒng)處于高風(fēng)險。由此可知PBFT共識算法在最壞的情況下有q的概率處于高風(fēng)險環(huán)境中。

在RPBFT共識算法進(jìn)行M次交易之后最壞的情況是有f個節(jié)點(diǎn)連續(xù)M次無法正常工作，每次出錯重新更換管理者，并將原管理者降級為普通節(jié)點(diǎn)。則此時存在2f-M個節(jié)點(diǎn)處于全部成功完成交易的狀態(tài)，信用積分為M；存在M個節(jié)點(diǎn)處于積分不為零的狀態(tài)。管理者就是從這2f個節(jié)點(diǎn)中選擇信用積分最高的節(jié)點(diǎn)，即選擇原來出錯節(jié)點(diǎn)的概率為零。對比之下，RPBFT共識算法在增加系統(tǒng)安全性方面有所改進(jìn)。

為驗(yàn)證系統(tǒng)在管理者行為出錯下的行為，實(shí)驗(yàn)中設(shè)置管理者線程在系統(tǒng)運(yùn)行10 s之后關(guān)閉。結(jié)果表明，RPBFT共識算法檢測到管理者失效后重新選舉管理者，并且與所有從節(jié)點(diǎn)進(jìn)行數(shù)據(jù)同步，數(shù)據(jù)同步過程中從節(jié)點(diǎn)對新管理者進(jìn)行檢測，保證了管理者的可靠性。接著開始新的共識過程。而且在整個過程中參與選舉和驗(yàn)證的可信節(jié)點(diǎn)數(shù)量超過了2f，保證了系統(tǒng)(n-1)/3的容錯性。

實(shí)驗(yàn)表明,RPBFT共識算法減少了系統(tǒng)開銷，縮短了共識延時，增加了算法的動態(tài)性，并且與PBFT共識算法一樣能夠保證分布式系統(tǒng)運(yùn)行的一致性和安全性，證明了該算法的有效性和可靠性。

5 結(jié)束語

本文對在區(qū)塊鏈中應(yīng)用廣泛的PBFT共識算法進(jìn)行深入研究，并提出了一種基于PBFT共識算法的改進(jìn)算法RPBFT共識算法。RPBFT共識算法動態(tài)管理節(jié)點(diǎn)的3種角色，使得節(jié)點(diǎn)可自由加入或者退出；對管理者的選擇方式加以改進(jìn)，選舉出來的節(jié)點(diǎn)更為可信；選舉完成之后的數(shù)據(jù)同步和驗(yàn)證過程，在驗(yàn)證管理者的可信性的同時，保證了節(jié)點(diǎn)的一致性；優(yōu)化的共識過程更加適應(yīng)區(qū)塊鏈的網(wǎng)絡(luò)環(huán)境，并減少了消耗，加快了共識速度。但是，RPBFT共識算法依然存在不足，如何進(jìn)一步降低網(wǎng)絡(luò)通信量，在保證通信效率的前提下提高容錯性，在將來需要進(jìn)一步深入研究。