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

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

1 引言

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

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

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

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

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

2 PBFT共識(shí)算法流程

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

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

Figure 1 Flow chart of PBFT consensus algorithm圖1 PBFT共識(shí)算法流程

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

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

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

(3)準(zhǔn)備階段(Prepare)：編號(hào)為i的從節(jié)點(diǎn)收到預(yù)準(zhǔn)備消息后，首先對(duì)消息的簽名、消息序號(hào)N和摘要d進(jìn)行驗(yàn)證。若驗(yàn)證通過(guò)，則將向所有從節(jié)點(diǎn)廣播準(zhǔn)備消息〈PREPARE,v,N,d,i〉。當(dāng)節(jié)點(diǎn)收到2f+1(f表示PBFT共識(shí)算法可容忍的錯(cuò)誤節(jié)點(diǎn)數(shù)量)個(gè)從不同從節(jié)點(diǎn)發(fā)送的與預(yù)準(zhǔn)備消息一致的準(zhǔn)備消息后，準(zhǔn)備階段完成。準(zhǔn)備階段完成對(duì)預(yù)準(zhǔn)備階段和準(zhǔn)備階段收到的視圖編號(hào)、共識(shí)內(nèi)容m分配的序號(hào)和消息內(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)是對(duì)消息m的驗(yàn)證簽名。從節(jié)點(diǎn)在收到確認(rèn)消息后會(huì)檢查消息簽名和視圖編號(hào)是否一致，若檢查通過(guò)并接收到2f+1個(gè)與預(yù)準(zhǔn)備消息一致的確認(rèn)消息，則確認(rèn)階段完成。這一階段的作用是確保所有節(jié)點(diǎn)對(duì)本地確認(rèn)的請(qǐng)求的序號(hào)達(dá)成一致。

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

對(duì)PBFT共識(shí)算法流程分析可知，算法存在著以下不足：

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

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

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

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

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

3.1 算法主要思想

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

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

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

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

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

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

3.2 算法流程

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

RPBFT共識(shí)算法流程如圖2所示，各階段具體過(guò)程描述如下:

Figure 2 Flow chart of RPBFT consensus algorithm圖2 RPBFT共識(shí)算法流程

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

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

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

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

3.3 獎(jiǎng)勵(lì)機(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ú)法完成任務(wù)，節(jié)點(diǎn)需要接受降級(jí)懲罰。管理者發(fā)生故障時(shí)，信用積分清除到初始狀態(tài)，并將角色類(lèi)型變?yōu)槠胀ü?jié)點(diǎn)，管理者自身發(fā)起重新選舉過(guò)程；候選者發(fā)生故障時(shí)，信用積分清除到初始狀態(tài)，并降級(jí)成為普通節(jié)點(diǎn)。

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

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

3.4 選舉過(guò)程

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

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

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

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

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

在管理者收到2f+1個(gè)不同節(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個(gè)來(lái)自不同節(jié)點(diǎn)的對(duì)數(shù)據(jù)同步消息的同步成功消息后，數(shù)據(jù)同步和驗(yàn)證過(guò)程完成。選舉和數(shù)據(jù)同步驗(yàn)證過(guò)程如圖3所示。

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

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

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

節(jié)點(diǎn)加入后處于無(wú)管理者狀態(tài)，發(fā)起對(duì)管理者的搜尋(Searching)過(guò)程。系統(tǒng)中的其它節(jié)點(diǎn)將告知其當(dāng)前管理者的消息，當(dāng)收到來(lái)自不同節(jié)點(diǎn)的2f+1個(gè)節(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)退出時(shí)，向所有節(jié)點(diǎn)廣播退出請(qǐng)求，管理者收到請(qǐng)求之后向除退出請(qǐng)求節(jié)點(diǎn)外的所有節(jié)點(diǎn)發(fā)送確認(rèn)消息；管理者退出時(shí)，向所有節(jié)點(diǎn)廣播退出請(qǐng)求并將降級(jí)為普通節(jié)點(diǎn)，同時(shí)啟動(dòng)選舉過(guò)程。選舉過(guò)程完畢之后由新當(dāng)選的管理者發(fā)送確認(rèn)消息。其它節(jié)點(diǎn)收到確認(rèn)消息后查看是否與退出請(qǐng)求一致，如果一致則向退出請(qǐng)求節(jié)點(diǎn)發(fā)送退出回復(fù)消息。退出節(jié)點(diǎn)收到f+1個(gè)來(lái)自不同節(jié)點(diǎn)的退出回復(fù)消息時(shí)，節(jié)點(diǎn)退出成功，停止參與節(jié)點(diǎn)共識(shí)過(guò)程。

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

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

4.1 通信開(kāi)銷(xiāo)

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

假設(shè)系統(tǒng)共識(shí)節(jié)點(diǎn)個(gè)數(shù)為n。PBFT共識(shí)算法預(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)階段每個(gè)節(jié)點(diǎn)向除自己以外的節(jié)點(diǎn)發(fā)送消息，所需通信次數(shù)為n(n-1)。即PBFT共識(shí)算法共識(shí)過(guò)程共需通信次數(shù)為2n(n-1)。視圖變更過(guò)程中，從節(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共識(shí)過(guò)程沒(méi)有錯(cuò)誤發(fā)生時(shí)，2階段的通信次數(shù)為n(n-1)。當(dāng)系統(tǒng)節(jié)點(diǎn)出錯(cuò)或因網(wǎng)絡(luò)導(dǎo)致超時(shí)，進(jìn)行選舉過(guò)程，候選者將自己的節(jié)點(diǎn)信息發(fā)送至其他候選者，這一階段共需的通信次數(shù)為4(n-1)2/9。候選者收到其它節(jié)點(diǎn)信息并進(jìn)行比較之后，將更新信息發(fā)送至其他候選者，該過(guò)程通信次數(shù)為4(n-1)2/9。管理者發(fā)送同步數(shù)據(jù)請(qǐng)求，該過(guò)程通信次數(shù)為(n-1)。節(jié)點(diǎn)驗(yàn)證成功發(fā)送確認(rèn)同步過(guò)程的通信次數(shù)為(n-1)。確認(rèn)同步完畢之后，管理者向其它節(jié)點(diǎn)發(fā)起數(shù)據(jù)更新的通信次數(shù)為(n-1)。由此分析可知，總共通信次數(shù)為:

(2)

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

(3)

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

4.2 時(shí)延測(cè)試

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

DelayTime=TSubmit-TAuthentication

(4)

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

Figure 5 Consensus delay comparison between two algorithms圖5 2種算法共識(shí)延時(shí)對(duì)比

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

4.3 動(dòng)態(tài)性

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

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

4.4 安全性

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

P=vmodn

(5)

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

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

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

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

5 結(jié)束語(yǔ)

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