基于信譽(yù)和聚類的動(dòng)態(tài)拜占庭容錯(cuò)算法

巫光福，楊 子，黃寶珠

1.江西理工大學(xué)信息工程學(xué)院，江西贛州341099

2.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京100878

拜占庭容錯(cuò)（Byzantine fault tolerance,BFT）[1]算法自提出以來(lái)就廣受關(guān)注。但由于其通信復(fù)雜度高，尚未在實(shí)踐中應(yīng)用。直到1999 年提出的實(shí)用拜占庭容錯(cuò)（practical Byzantine fault tolerance,PBFT）[2]將BFT 算法的復(fù)雜度從指數(shù)級(jí)降到多項(xiàng)式級(jí)，才逐漸應(yīng)用于工程領(lǐng)域。目前，PBFT 是區(qū)塊鏈[3]中應(yīng)用最多的共識(shí)算法。雖然PBFT 相較于其他共識(shí)算法提高了吞吐量，減少了交易確認(rèn)時(shí)延，但仍存在很多不足：首先PBFT 對(duì)于節(jié)點(diǎn)加入或退出沒(méi)有良好的響應(yīng)機(jī)制，其次主節(jié)點(diǎn)選取隨意。這些不足會(huì)提高拜占庭節(jié)點(diǎn)成為主節(jié)點(diǎn)的概率，從而降低共識(shí)效率，造成資源浪費(fèi)。

近些年，很多學(xué)者針對(duì)PBFT 存在的不足進(jìn)行算法改進(jìn)。例如，文獻(xiàn)[4-7] 將PBFT 與POW、POS 或DPOS 相結(jié)合，以提高共識(shí)效率，這些算法是選擇一定數(shù)量的節(jié)點(diǎn)作為委員會(huì)，然后委員會(huì)提供PBFT 算法生成區(qū)塊，雖然這些改進(jìn)算法在部分性能方面優(yōu)于原算法，但其通常適用于令牌場(chǎng)景。文獻(xiàn)[8] 提出的SBFT 算法對(duì)分散方式進(jìn)行優(yōu)化，使其輕松處理超過(guò)100 個(gè)活動(dòng)副本，解決了動(dòng)態(tài)性和去中心化的問(wèn)題。OBFT 算法[4]提出了一種新型協(xié)議，該協(xié)議保證在沒(méi)有發(fā)生故障的樂(lè)觀情況下，以全網(wǎng)絡(luò)速度處理事務(wù)，增加了PBFT 的容錯(cuò)性。CBFT[5]算法通過(guò)區(qū)塊緩存、區(qū)塊同步與簽名、節(jié)點(diǎn)變更實(shí)現(xiàn)，使算法較高的吞吐量和較低的時(shí)延，但是其交易處理和達(dá)成共識(shí)的效率需要進(jìn)一步提升。雖然這些算法可以有效降低通信開銷，提升擴(kuò)展性，但是在選取可靠主節(jié)點(diǎn)的問(wèn)題上沒(méi)有有效措施，同時(shí)也沒(méi)有良好的動(dòng)態(tài)響應(yīng)機(jī)制。

對(duì)比分析現(xiàn)有的改進(jìn)PBFT 算法后，本文提出了基于信譽(yù)和聚類的動(dòng)態(tài)拜占庭容錯(cuò)（dynamic-layering reputation-evaluation and K-medoids practical Byzantine fault tolerant,DRKPBFT）算法。算法通過(guò)改進(jìn)K-medoids 算法將節(jié)點(diǎn)劃分為K個(gè)共識(shí)區(qū)域，將傳統(tǒng)的PBFT 改進(jìn)為多中心化，多層次的拜占庭算法，提高了較多節(jié)點(diǎn)參與共識(shí)時(shí)的效率，同時(shí)能夠動(dòng)態(tài)調(diào)整節(jié)點(diǎn)加入或退出時(shí)的節(jié)點(diǎn)數(shù)量。為了選取可靠的主節(jié)點(diǎn)，提出了信譽(yù)評(píng)估算法，其能夠?qū)?jié)點(diǎn)行為進(jìn)行信譽(yù)值評(píng)估，選取信譽(yù)值高的節(jié)點(diǎn)為主節(jié)點(diǎn)，剔除信譽(yù)值低的拜占庭節(jié)點(diǎn)，提高了可靠節(jié)點(diǎn)為主節(jié)點(diǎn)的概率，減少了共識(shí)過(guò)程的資源浪費(fèi)。

1 相關(guān)知識(shí)

1.1 區(qū)塊鏈

從中本聰首次提到區(qū)塊鏈技術(shù)以來(lái)[6]，尚未形成公認(rèn)的區(qū)塊鏈定義。狹義上，區(qū)塊鏈?zhǔn)前凑諘r(shí)間順序?qū)^(qū)塊依次相連的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，是由多方維護(hù)，使用密碼學(xué)保證傳輸和訪問(wèn)安全，能夠?qū)崿F(xiàn)數(shù)據(jù)一致存儲(chǔ)，難以篡改的記賬技術(shù)[7]。廣義上，區(qū)塊鏈?zhǔn)鞘褂面準(zhǔn)浇Y(jié)構(gòu)和密碼學(xué)存儲(chǔ)驗(yàn)證數(shù)據(jù)，使用P2P 網(wǎng)絡(luò)進(jìn)行消息傳播，利用共識(shí)算法保證數(shù)據(jù)的一致性，利用腳本代碼和智能合約[8]操作數(shù)據(jù)，是一種全新的去中心化架構(gòu)模型。區(qū)塊鏈的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)如圖1 所示。

1.2 共識(shí)算法

由于區(qū)塊鏈中缺乏中央權(quán)威，因此需要一個(gè)共識(shí)算法來(lái)保持?jǐn)?shù)據(jù)的一致性[9]。共識(shí)算法在決定區(qū)塊鏈系統(tǒng)的效率和安全性方面起著重要作用，即所選擇的算法類型對(duì)系統(tǒng)的性能有著重大影響。常用共識(shí)算法如下。

1.2.1 工作量證明

工作量證明（proof of work,POW）的過(guò)程是各節(jié)點(diǎn)通過(guò)大量算力競(jìng)爭(zhēng)來(lái)解決一個(gè)（求解復(fù)雜但驗(yàn)證容易）的難題，最快解出難題的節(jié)點(diǎn)將獲得區(qū)塊記賬權(quán)[10]。在比特幣中，POW 就是各礦工共同競(jìng)爭(zhēng)解決SHA256 這個(gè)數(shù)學(xué)難題（挖礦），當(dāng)節(jié)點(diǎn)最快找出區(qū)塊頭的雙哈希值小于或等于目標(biāo)哈希值的nonce 值時(shí)，其就獲得區(qū)塊記賬權(quán)以及比特幣獎(jiǎng)勵(lì)。POW 的優(yōu)點(diǎn)是可以通過(guò)算力競(jìng)爭(zhēng)保障比特幣系統(tǒng)的安全性和去中心性，缺點(diǎn)是需要進(jìn)行大量無(wú)現(xiàn)實(shí)意義的計(jì)算，而且將近10 min 的交易確認(rèn)時(shí)間不適合某些應(yīng)用。

1.2.2 權(quán)益證明

權(quán)益證明（proof of stack,POS）[11]是針對(duì)POW 的資源浪費(fèi)等不足提出的共識(shí)機(jī)制。它以具有最高權(quán)益獲得區(qū)塊記賬權(quán)。在Peercoin[12]中，權(quán)益表現(xiàn)為幣齡。當(dāng)記賬競(jìng)爭(zhēng)開始時(shí)，節(jié)點(diǎn)以幣齡下注，擁有最高幣齡的將成為驗(yàn)證者。驗(yàn)證者獲得記賬權(quán)生成區(qū)塊后，其幣齡將清空，然后節(jié)點(diǎn)獲取相應(yīng)的利息。POS 是依靠?jī)?nèi)部幣齡和權(quán)益，而不是像POW 消耗外部算力和資源，從根本上解決了共識(shí)算力浪費(fèi)的問(wèn)題，能夠在一定程度上縮短共識(shí)時(shí)間。

1.2.3 委托權(quán)益證明

委托權(quán)益證明（delegated proof of stake,DPOS）類似于投票選舉，即系統(tǒng)中每個(gè)擁有token 的股東節(jié)點(diǎn)進(jìn)行投票選舉代表[13]，獲得票數(shù)最多且愿意成為代表的前101 個(gè)節(jié)點(diǎn)將進(jìn)入候選池，從候選池中選出區(qū)塊生成者，區(qū)塊生成者根據(jù)隨機(jī)順序進(jìn)行出塊，生成的新區(qū)塊經(jīng)過(guò)2/3 區(qū)塊生產(chǎn)者驗(yàn)證后，節(jié)點(diǎn)獲得獎(jiǎng)勵(lì)。由此可知DPOS 中每個(gè)節(jié)點(diǎn)都能夠自主決定其信任的授權(quán)節(jié)點(diǎn)，同時(shí)由這些節(jié)點(diǎn)輪流記賬生成新區(qū)塊，因此DPOS 大幅減少了參與驗(yàn)證和記賬的節(jié)點(diǎn)數(shù)量，實(shí)現(xiàn)了快速共識(shí)驗(yàn)證。

1.2.4 Raft 共識(shí)算法

Raft 是用于管理復(fù)制日志的共識(shí)算法，其過(guò)程分為leader 選舉和日志復(fù)制兩個(gè)階段。即首先選取一個(gè)leader，賦予leader 記賬的權(quán)力。然后任何leader 從客戶端接收記賬請(qǐng)求，完成記賬操作，生成區(qū)塊，并復(fù)制其他記賬節(jié)點(diǎn)。Raft 是非拜占庭故障下達(dá)成共識(shí)的強(qiáng)一致協(xié)議，常用于私有鏈[14]。

1.2.5 實(shí)用拜占庭容錯(cuò)機(jī)制

PBFT 的共識(shí)過(guò)程包括請(qǐng)求階段（Request）、預(yù)準(zhǔn)備階段（Pre-prepare）、準(zhǔn)備階段（Prepare）、確認(rèn)階段（Commit）以及響應(yīng)階段（Reply）。在PBFT 協(xié)議中，有客戶端、主節(jié)點(diǎn)（Primary）、從節(jié)點(diǎn)（Backup）三種身份。PBFT 的共識(shí)過(guò)程如圖2 所示。

圖2 PBFT 共識(shí)過(guò)程Figure 2 PBFT consensus process

1）請(qǐng)求階段 客戶端向主節(jié)點(diǎn)發(fā)送請(qǐng)求〈REQUEST,O,T,C〉,O代表具體執(zhí)行的操作，T代表時(shí)間戳，C表示客戶端編號(hào)。

2）預(yù)準(zhǔn)備階段 收到客戶端請(qǐng)求后，主節(jié)點(diǎn)會(huì)檢查合法性，然后給請(qǐng)求分配序列號(hào)N，然后向從節(jié)點(diǎn)廣播預(yù)準(zhǔn)備消息〈PRE-PREPARE,V,N,D,M〉,V表示當(dāng)前視圖序號(hào)，D是請(qǐng)求的摘要，M代表客戶端的請(qǐng)求信息。

3）準(zhǔn)備階段 從節(jié)點(diǎn)收到預(yù)準(zhǔn)備消息，進(jìn)行一些驗(yàn)證，驗(yàn)證通過(guò)后進(jìn)入準(zhǔn)備階段，廣播準(zhǔn)備消息〈PREPARE,V,N,D,I〉，I代表從節(jié)點(diǎn)編號(hào)。

4）確認(rèn)階段 節(jié)點(diǎn)收到2f+1 個(gè)合法的準(zhǔn)備消息，廣播確認(rèn)消息〈COMMIT,V,N,M,I〉,從節(jié)點(diǎn)收到確認(rèn)消息，進(jìn)行驗(yàn)證，驗(yàn)證通過(guò)后將COMMIT 插入本地log。

5）回復(fù)階段 執(zhí)行此階段時(shí)，所有節(jié)點(diǎn)會(huì)向客戶端發(fā)送回復(fù)消息〈REPLY,V,T,C,I,R〉,R指執(zhí)行結(jié)果。

根據(jù)表1 的共識(shí)算法對(duì)比，PBFT 具有較高的吞吐量和執(zhí)行速度，但是仍然存在主節(jié)點(diǎn)選取隨意，共識(shí)速度慢，可擴(kuò)展性低等問(wèn)題?；诖?，本文提出的DRKPBFT 算法解決了主節(jié)點(diǎn)選取的問(wèn)題，設(shè)計(jì)了節(jié)點(diǎn)動(dòng)態(tài)加入和退出機(jī)制，使得算法具有較好的容錯(cuò)性，擴(kuò)展性。

表1 共識(shí)算法對(duì)比Table 1 Comparison among consensus algorithms

1.3 聚類算法

K-medoids 算法[15]是基于劃分的聚類算法，具體過(guò)程如下：假設(shè)有m個(gè)n維特征的對(duì)象節(jié)點(diǎn)作為聚類數(shù)據(jù)集。節(jié)點(diǎn)數(shù)據(jù)集V={V1,V2,···,Vm}表達(dá)為

算法通過(guò)距離函數(shù)來(lái)表達(dá)兩個(gè)節(jié)點(diǎn)的相似度,同時(shí)通過(guò)隸屬函數(shù)將數(shù)據(jù)集分為K 簇和K個(gè)聚類中心節(jié)點(diǎn)集。

2 DRKPBFT 共識(shí)算法方案

DRKPBFT 共識(shí)方案包括共識(shí)系統(tǒng)初始化，KPBFT 共識(shí)以及信譽(yù)評(píng)估算法3 個(gè)部分。

2.1 系統(tǒng)初始化

本文方案為了使K-medoids 更加適用于區(qū)塊鏈模型，采用改進(jìn)聚類算法選取K個(gè)聚類中心節(jié)點(diǎn)。（K個(gè)中心節(jié)點(diǎn)不是從所有樣本中隨機(jī)選擇的，而是根據(jù)具體應(yīng)用通過(guò)監(jiān)管機(jī)構(gòu)進(jìn)行嚴(yán)格審查排名，篩選出K個(gè)社會(huì)公信度較高的節(jié)點(diǎn)）。K個(gè)中心節(jié)點(diǎn)構(gòu)成代理節(jié)點(diǎn)群，然后計(jì)算其余節(jié)點(diǎn)距離K個(gè)代理節(jié)點(diǎn)的距離函數(shù)和隸屬函數(shù)，最后根據(jù)歐式距離進(jìn)行聚類分層，形成相應(yīng)的子共識(shí)集群。節(jié)點(diǎn)分類如圖3 所示。

圖3 共識(shí)節(jié)點(diǎn)圖Figure 3 Consensus node graph

2.2 KPBFT 過(guò)程

KPBFT 共識(shí)過(guò)程如圖4 所示。首先每一個(gè)集群內(nèi)的節(jié)點(diǎn)達(dá)成共識(shí)，然后代理節(jié)點(diǎn)收集共識(shí)結(jié)果。經(jīng)過(guò)一段時(shí)間后，根據(jù)2.3 節(jié)信譽(yù)評(píng)估算法進(jìn)行聚類中心（代理節(jié)點(diǎn)）更換，然后重新進(jìn)行共識(shí)。

圖4 KPBFT 過(guò)程Figure 4 KPBFT process

1）請(qǐng)求階段 客戶端C 向第1 層代理節(jié)點(diǎn)發(fā)送消息，即向代理主節(jié)點(diǎn)發(fā)送請(qǐng)求消息，代理主節(jié)點(diǎn)為客戶端的請(qǐng)求進(jìn)行排序，然后與PBFT 采用廣播的方式不同，本模型為了節(jié)省網(wǎng)絡(luò)資源，采用組播向代理節(jié)點(diǎn)群中的其他代理節(jié)點(diǎn)傳遞消息。

2）預(yù)準(zhǔn)備階段 進(jìn)入此階段，共識(shí)群里已初步分為K個(gè)區(qū)域。每個(gè)代理節(jié)點(diǎn)向其區(qū)域內(nèi)的共識(shí)節(jié)點(diǎn)群中廣播預(yù)準(zhǔn)備消息，當(dāng)區(qū)域內(nèi)的子共識(shí)節(jié)點(diǎn)接受到消息，預(yù)準(zhǔn)備階段完成。然后K個(gè)代理節(jié)點(diǎn)與其子共識(shí)節(jié)點(diǎn)在各自的區(qū)域內(nèi)進(jìn)行準(zhǔn)備階段，確認(rèn)階段，當(dāng)每個(gè)代理節(jié)點(diǎn)收到超過(guò)本區(qū)域2/3 的回復(fù)消息，進(jìn)入下一階段。

3）回復(fù)階段 回復(fù)階段分為區(qū)內(nèi)回復(fù)和區(qū)間回復(fù)兩部分。區(qū)內(nèi)回復(fù)是各個(gè)區(qū)域內(nèi)的子共識(shí)節(jié)點(diǎn)將執(zhí)行結(jié)果發(fā)給所屬的代理節(jié)點(diǎn)；區(qū)間回復(fù)是代理節(jié)點(diǎn)記錄各個(gè)區(qū)域內(nèi)的區(qū)內(nèi)結(jié)果并發(fā)送給客戶端?？蛻舳烁鶕?jù)組播請(qǐng)求的總數(shù)和接收到同意消息的總數(shù)，即總數(shù)是否大于惡意節(jié)點(diǎn)總數(shù)f+1 來(lái)確定是否接收結(jié)果。

2.3 信譽(yù)評(píng)估算法

本文方案在選取K個(gè)可信聚類中心（代理節(jié)點(diǎn)）問(wèn)題上，提出了一個(gè)信譽(yù)評(píng)估算法。信譽(yù)評(píng)估算法包括行為獎(jiǎng)罰機(jī)制，節(jié)點(diǎn)劃分機(jī)制，角色轉(zhuǎn)換機(jī)制，節(jié)點(diǎn)剔除機(jī)制。即整個(gè)模型通過(guò)獎(jiǎng)懲機(jī)制對(duì)節(jié)點(diǎn)的行為進(jìn)行信譽(yù)值評(píng)估，根據(jù)信譽(yù)值將節(jié)點(diǎn)分類成無(wú)效節(jié)點(diǎn)、普通節(jié)點(diǎn)、投票節(jié)點(diǎn)、代理節(jié)點(diǎn)，并在代理節(jié)點(diǎn)中選出信譽(yù)值最高的當(dāng)作下一個(gè)視圖的代理主節(jié)點(diǎn)（如果沒(méi)有單一最高信譽(yù)值，則選取信譽(yù)值高且序號(hào)最小的當(dāng)作代理主節(jié)點(diǎn)）。節(jié)點(diǎn)的等級(jí)可以通過(guò)信譽(yù)值進(jìn)行動(dòng)態(tài)轉(zhuǎn)換，保證了系統(tǒng)的動(dòng)態(tài)性、穩(wěn)定性。最后會(huì)將信譽(yù)值低的無(wú)效節(jié)點(diǎn)剔除出共識(shí)集合，保證了系統(tǒng)的安全性。通過(guò)信譽(yù)評(píng)估算法，為下一視圖選擇K個(gè)代理節(jié)點(diǎn)提供依據(jù)，增加了可信節(jié)點(diǎn)參加共識(shí)集合的概率，實(shí)現(xiàn)了快速可信的共識(shí)。

2.3.1 節(jié)點(diǎn)劃分機(jī)制

在系統(tǒng)初始化時(shí)，將K個(gè)代理節(jié)點(diǎn)的信譽(yù)值設(shè)為8，其余子共識(shí)節(jié)點(diǎn)信譽(yù)值設(shè)為6。經(jīng)過(guò)t輪KPBFT 共識(shí)后進(jìn)行共識(shí)節(jié)點(diǎn)角色劃分。根據(jù)獎(jiǎng)勵(lì)懲罰機(jī)制對(duì)前t輪共識(shí)過(guò)程的節(jié)點(diǎn)行為進(jìn)行信譽(yù)值評(píng)估，依此篩選出信譽(yù)值小于0 的無(wú)效節(jié)點(diǎn)，信譽(yù)值為0～6 分的普通節(jié)點(diǎn)，信譽(yù)值為6～8 分的投票節(jié)點(diǎn)，及信譽(yù)值為大于8 分的代理節(jié)點(diǎn)，規(guī)定最高信譽(yù)值為20 分。普通節(jié)點(diǎn)服從投票節(jié)點(diǎn)的安排，只完成共識(shí)過(guò)程。投票節(jié)點(diǎn)在共識(shí)過(guò)程中監(jiān)督代理節(jié)點(diǎn)的行為，決定是否更換代理節(jié)點(diǎn)。通過(guò)節(jié)點(diǎn)劃分機(jī)制可以有效防止網(wǎng)絡(luò)中故障或惡意節(jié)點(diǎn)成為主節(jié)點(diǎn)，減少了節(jié)點(diǎn)的共識(shí)通信開銷，提高了整個(gè)系統(tǒng)的共識(shí)效率。

2.3.2 行為獎(jiǎng)懲機(jī)制

當(dāng)節(jié)點(diǎn)有如下行為，進(jìn)行信譽(yù)值獎(jiǎng)勵(lì)。若節(jié)點(diǎn)實(shí)際共識(shí)時(shí)間小于平均共識(shí)時(shí)間，信譽(yù)值+1；若節(jié)點(diǎn)通過(guò)反饋舉報(bào)其他節(jié)點(diǎn)惡意行為或宕機(jī)行為，也給予信譽(yù)值+1；當(dāng)節(jié)點(diǎn)進(jìn)行如下操作時(shí)，則會(huì)扣除相應(yīng)的信譽(yù)值。如節(jié)點(diǎn)故意拖延一段時(shí)間不傳遞消息，信譽(yù)值-1；節(jié)點(diǎn)濫用舉報(bào)消息信譽(yù)值-3；節(jié)點(diǎn)對(duì)收到的信息始終不傳播信譽(yù)值-5；最后如果傳播惡意消息并廣播出去，信譽(yù)值-8。通過(guò)節(jié)點(diǎn)的共識(shí)行為進(jìn)行信譽(yù)值評(píng)估，根據(jù)信譽(yù)值進(jìn)行角色劃分，然后行使不同的功能，可以很好的維護(hù)節(jié)點(diǎn)之間的安全與穩(wěn)定。

2.3.3 角色轉(zhuǎn)換機(jī)制

節(jié)點(diǎn)的角色是動(dòng)態(tài)轉(zhuǎn)換的，主要跟節(jié)點(diǎn)在共識(shí)過(guò)程中的行為有關(guān)。普通節(jié)點(diǎn)積極誠(chéng)實(shí)共識(shí)可升級(jí)為投票節(jié)點(diǎn)，投票節(jié)點(diǎn)亦可升級(jí)為代理節(jié)點(diǎn)，所以節(jié)點(diǎn)越是積極誠(chéng)實(shí)進(jìn)行共識(shí)，則相應(yīng)的信譽(yù)值就會(huì)越高，成為代理節(jié)點(diǎn)的可能性越大；反之節(jié)點(diǎn)故意或者惡意進(jìn)行共識(shí)，則進(jìn)行降級(jí)變成普通節(jié)點(diǎn)，甚至可能變成無(wú)效節(jié)點(diǎn)，無(wú)法參與共識(shí)過(guò)程。同時(shí)，如果代理節(jié)點(diǎn)和代理主節(jié)點(diǎn)出現(xiàn)錯(cuò)誤時(shí)，則降級(jí)為普通節(jié)點(diǎn)；或者投票節(jié)點(diǎn)經(jīng)過(guò)一段時(shí)間進(jìn)行投票，將代理節(jié)點(diǎn)降級(jí)為普通節(jié)點(diǎn)，這樣可以避免共識(shí)過(guò)程中系統(tǒng)過(guò)度中心化的問(wèn)題，降低某些節(jié)點(diǎn)一直是代理節(jié)點(diǎn)帶來(lái)的安全性問(wèn)題。節(jié)點(diǎn)角色轉(zhuǎn)換如圖5 所示。

圖5 節(jié)點(diǎn)角色轉(zhuǎn)換圖Figure 5 Node role conversion diagram

2.3.4 節(jié)點(diǎn)剔除機(jī)制

將信譽(yù)值小于0 的節(jié)點(diǎn)視為無(wú)效節(jié)點(diǎn)，剔除共識(shí)過(guò)程。節(jié)點(diǎn)剔除機(jī)制進(jìn)一步降低了共識(shí)節(jié)點(diǎn)中拜占庭節(jié)點(diǎn)存在和作惡的可能性，規(guī)范了共識(shí)節(jié)點(diǎn)的誠(chéng)實(shí)度，提高了系統(tǒng)的共識(shí)效率和安全性。

3 DRKPBFT 共識(shí)算法流程

假設(shè)網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)為{0,1,···,N-1}，其中包括K個(gè)代理節(jié)點(diǎn)，N-K個(gè)其余節(jié)點(diǎn)，共同構(gòu)成K個(gè)區(qū)域。算法流程如圖6 所示：

圖6 算法流程圖Figure 6 Algorithm flow chart

1）節(jié)點(diǎn)初始化選取K個(gè)代理節(jié)點(diǎn)，進(jìn)行節(jié)點(diǎn)聚類劃分。同時(shí)將代理節(jié)點(diǎn)初始化信譽(yù)值為8，其余子節(jié)點(diǎn)初始信譽(yù)值為6。

2）選取代理主節(jié)點(diǎn)初始時(shí)，代理節(jié)點(diǎn)信譽(yù)值相同，則對(duì)K個(gè)代理節(jié)點(diǎn)排序，然后從中隨機(jī)挑選一個(gè)代理主節(jié)點(diǎn)。其中，若N≥8 時(shí)，選取代理主節(jié)點(diǎn)；若N<8，系統(tǒng)直接執(zhí)行PBFT 算法。

3）客戶端client 發(fā)送交易請(qǐng)求〈REQUEST,M,T,C〉σC，M為請(qǐng)求信息，T是時(shí)間戳，σC為客戶端簽名。

4）代理主節(jié)點(diǎn)收到客戶端請(qǐng)求后，將消息組播發(fā)給代理節(jié)點(diǎn)，每個(gè)區(qū)域內(nèi)進(jìn)行共識(shí)過(guò)程。每個(gè)區(qū)域進(jìn)行預(yù)準(zhǔn)備階段〈PRE-PREPARE,V,N,D〉M>σα（V是視圖編號(hào)，D消息摘要，σα代理節(jié)點(diǎn)簽名；準(zhǔn)備階段〈PREPARE,V,N,D,I〉σα1(I為區(qū)域內(nèi)從節(jié)點(diǎn)的編號(hào)，σα1為代理子節(jié)點(diǎn)的簽名)；確認(rèn)階段〈COMMIT,V,N,M,I〉。

5）K個(gè)代理節(jié)點(diǎn)收集本區(qū)域內(nèi)結(jié)果，然后將信息返回給客戶端。

6）客戶端根據(jù)組播請(qǐng)求的總數(shù)和接收到同意消息的總數(shù)，即總數(shù)是否大于惡意節(jié)點(diǎn)總數(shù)f+1 來(lái)確定是否接收結(jié)果.若超時(shí)未完成共識(shí)或代理節(jié)點(diǎn)行為異常，則啟動(dòng)視圖更改協(xié)議，然后根據(jù)信譽(yù)值評(píng)估算法重新選取代理節(jié)點(diǎn)。

7）信譽(yù)評(píng)估算法評(píng)估此共識(shí)過(guò)程的節(jié)點(diǎn)行為，進(jìn)行信譽(yù)值更新，根據(jù)信譽(yù)值進(jìn)行節(jié)點(diǎn)角色劃分，同時(shí)將惡意節(jié)點(diǎn)剔除，保證系統(tǒng)安全性。

叢曉榮（1983-），女，碩士，助理研究員，主要從事含油氣盆地分析、海域天然氣水合物成藏與資源評(píng)價(jià)等方面的科研工作。

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

本節(jié)將從動(dòng)態(tài)性、通信開銷、容錯(cuò)性、時(shí)延、吞吐量這5 個(gè)方面進(jìn)行實(shí)驗(yàn)分析，并對(duì)比PBFT 來(lái)驗(yàn)證本文算法的優(yōu)越性。仿真實(shí)驗(yàn)環(huán)境，在Windows10 系統(tǒng)中使用Python 語(yǔ)言，采用虛擬系統(tǒng)Ubuntu18.04.

4.1 動(dòng)態(tài)性分析

傳統(tǒng)的PBFT 采用靜態(tài)請(qǐng)求響應(yīng)模式，加入和退出時(shí)都需要重新啟動(dòng)系統(tǒng)，沒(méi)有良好的響應(yīng)機(jī)制。本文提出的DRKPBFT 算法采用信譽(yù)評(píng)估將節(jié)點(diǎn)劃分，并根據(jù)信譽(yù)值動(dòng)態(tài)轉(zhuǎn)換，節(jié)點(diǎn)的加入或退出由代理節(jié)點(diǎn)動(dòng)態(tài)管理。當(dāng)普通節(jié)點(diǎn)加入共識(shí)時(shí)，根據(jù)聚類算法，計(jì)算與哪個(gè)代理節(jié)點(diǎn)距離最為接近，將其加入該子類子群中；當(dāng)普通節(jié)點(diǎn)或投票節(jié)點(diǎn)退出共識(shí)時(shí)，代理節(jié)點(diǎn)直接將該節(jié)點(diǎn)從子群中刪除；當(dāng)代理節(jié)點(diǎn)退出時(shí)，降級(jí)為普通節(jié)點(diǎn)，然后由投票節(jié)點(diǎn)根據(jù)信譽(yù)值選舉新的代理節(jié)點(diǎn)。

由此可見，DRKPBFT 能夠在節(jié)點(diǎn)加入和退出時(shí)，動(dòng)態(tài)調(diào)整節(jié)點(diǎn)數(shù)量，避免PBFT 節(jié)點(diǎn)加入或退出引起整個(gè)系統(tǒng)重啟的問(wèn)題，減少了網(wǎng)絡(luò)資源消耗，增強(qiáng)了共識(shí)系統(tǒng)的動(dòng)態(tài)性，保證了系統(tǒng)的穩(wěn)定性和可靠性。

4.2 通信開銷分析

對(duì)于PBFT 算法，當(dāng)系統(tǒng)節(jié)點(diǎn)為N時(shí)，從客戶端請(qǐng)求、預(yù)準(zhǔn)備階段、準(zhǔn)備階段、確認(rèn)階段到回復(fù)階段，通信次數(shù)共為1+(N-1)+(N-1)(N-1)+N(N-1)+N=2N2，其通信復(fù)雜度為O(N2)。對(duì)于本文的DRKPBFT 算法，采用分類的思想，將N個(gè)節(jié)點(diǎn)分為K類，每一類中有N/K個(gè)節(jié)點(diǎn)，客戶端向代理主節(jié)點(diǎn)發(fā)送請(qǐng)求以及代理節(jié)點(diǎn)間進(jìn)行的通信次數(shù)為K次，然后子節(jié)點(diǎn)進(jìn)行共識(shí)的通信次數(shù)為2N2/K2，最后代理節(jié)點(diǎn)回復(fù)客戶端通信次數(shù)為K次，求和得出算法總通信次數(shù)共為(2K+2N2/K2)。

實(shí)驗(yàn)先測(cè)試PBFT 與K=3 的DRKPBFT 在節(jié)點(diǎn)數(shù)增加時(shí)，單次交易完成后節(jié)點(diǎn)的通信次數(shù)，然后測(cè)試不同K值下，隨著節(jié)點(diǎn)數(shù)增加，節(jié)點(diǎn)的通信開銷。實(shí)驗(yàn)結(jié)果如圖7 和8 所示，圖7 表明隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增多，PBFT 需要大量通信開銷才能完成一次共識(shí)，而本文的DRKPBFT 進(jìn)行一次共識(shí)的通信開銷明顯低于PBFT 算法。同時(shí)圖8 則表明隨著節(jié)點(diǎn)數(shù)增加，在K=4,7,10 的情況下，完成一次共識(shí)的通信開銷是不斷減少的。實(shí)驗(yàn)結(jié)果表明，隨著節(jié)點(diǎn)數(shù)增加，可以增加K值即增加節(jié)點(diǎn)分類數(shù)來(lái)降低通信開銷，原因是由于本文的DRKPBFT 通過(guò)聚類算法將節(jié)點(diǎn)分類，減少了共識(shí)節(jié)點(diǎn)的數(shù)量，同時(shí)在確認(rèn)階段降低了共識(shí)通信次數(shù)。

圖7 PBFT vs DRKPBFTFigure 7 PBFT vs DRKPBFT

圖8 K 值不同的DRKPBFT 通信開銷Figure 8 DRKPBFT communication overhead with different values of K

4.3 容錯(cuò)性分析

針對(duì)DRKPBFT 算法進(jìn)行容錯(cuò)性分析，考慮代理節(jié)點(diǎn)存在拜占庭節(jié)點(diǎn)以及不存在拜占庭節(jié)點(diǎn)兩種情況。

若拜占庭節(jié)點(diǎn)集中在一個(gè)聚類中，則該代理節(jié)點(diǎn)將會(huì)輸出錯(cuò)誤，此時(shí)在代理節(jié)點(diǎn)群中的結(jié)果將會(huì)丟棄，同時(shí)投票節(jié)點(diǎn)將代理節(jié)點(diǎn)降級(jí)；若拜占庭節(jié)點(diǎn)均勻分布在每個(gè)聚類中，那么每個(gè)聚類中的拜占庭節(jié)點(diǎn)數(shù)不超過(guò)其區(qū)域內(nèi)節(jié)點(diǎn)總數(shù)的1/3。現(xiàn)考慮，N個(gè)節(jié)點(diǎn)被分為K個(gè)區(qū)域，每個(gè)區(qū)域最多允許拜占庭節(jié)點(diǎn)數(shù)為（N/K）/3，同時(shí)系統(tǒng)最多允許K/3 個(gè)代理節(jié)點(diǎn)全部為拜占庭節(jié)點(diǎn)，此時(shí)整個(gè)系統(tǒng)的容錯(cuò)性為

由此可得，本文的DRKPBFT 比PBFT 支持更高的容錯(cuò)性。

4.3.2 代理節(jié)點(diǎn)中存在拜占庭節(jié)點(diǎn)

這種情況下，該節(jié)點(diǎn)可能會(huì)影響該區(qū)域的從節(jié)點(diǎn)，甚至可能篡改共識(shí)結(jié)果。如果拜占庭節(jié)點(diǎn)超過(guò)總代理節(jié)點(diǎn)數(shù)的1/3，那么系統(tǒng)將會(huì)崩潰，所以系統(tǒng)的容錯(cuò)性為（K-1）/3。但是本文從高信譽(yù)節(jié)點(diǎn)中選取代理節(jié)點(diǎn)，同時(shí)代理節(jié)點(diǎn)出錯(cuò)，投票節(jié)點(diǎn)會(huì)進(jìn)行投票更換代理節(jié)點(diǎn)并進(jìn)行降級(jí)處理，這樣有效防止拜占庭節(jié)點(diǎn)成為代理節(jié)點(diǎn)的可能，保障了系統(tǒng)的安全性。

4.4 時(shí)延分析

時(shí)延是衡量共識(shí)算法的重要指標(biāo)，過(guò)高的時(shí)延會(huì)使算法的可用性和安全性降低。實(shí)驗(yàn)設(shè)置客戶端發(fā)送100 次交易，在節(jié)點(diǎn)數(shù)10、17、20、28、32、40 時(shí)進(jìn)行3 組時(shí)延對(duì)比實(shí)驗(yàn)。將節(jié)點(diǎn)多次測(cè)試的時(shí)延結(jié)果取平均值，得出PBFT 和K=4 的DRKPBFT 的共識(shí)時(shí)延對(duì)比，結(jié)果如圖9 所示，DRKPBFT 共識(shí)算法的交易時(shí)延明顯低于PBFT，同時(shí)計(jì)算出PBFT 的平均交易時(shí)延為2.15 s，K=4 的DRKPBFT 的平均交易時(shí)延為0.27 s。由此可見，本文提出的DRKPBFT 在節(jié)點(diǎn)數(shù)增加時(shí)能夠大幅度降低交易時(shí)延。

圖9 時(shí)延對(duì)比Figure 9 Time delay contrast

4.5 吞吐量分析

吞吐量是檢測(cè)共識(shí)算法運(yùn)行效率高低的標(biāo)準(zhǔn)，較大的吞吐量能較好的反應(yīng)算法的優(yōu)劣。吞吐量為單位時(shí)間內(nèi)完成的交易數(shù)量，計(jì)算公式為TPS=B/T（其中B為T時(shí)間內(nèi)打包進(jìn)區(qū)塊的交易數(shù)，T為出塊時(shí)間）。實(shí)驗(yàn)設(shè)置客戶端發(fā)送200 條交易，然后記錄完成共識(shí)的時(shí)間，最后通過(guò)公式計(jì)算出不同節(jié)點(diǎn)數(shù)的吞吐量。如圖10 所示，當(dāng)節(jié)點(diǎn)數(shù)分別為17、21、25、28、33、37、42、45、48 時(shí)，本文算法相比于PBFT 具有更高的吞吐量，同時(shí)可以計(jì)算出PBFT 的平均吞吐量為87 TPS，K=4 的DRKPBFT 的平均吞吐量為145 TPS。最后根據(jù)圖10 的趨勢(shì)可以看出隨著節(jié)點(diǎn)數(shù)的增加，PBFT 吞吐量下降較快，穩(wěn)定性較差，而DRKPBFT 在節(jié)點(diǎn)數(shù)增加至27 以后，吞吐量趨于平緩，穩(wěn)定性較好。原因是：本文方案在聚類分區(qū)域時(shí)，選取高信譽(yù)值節(jié)點(diǎn)為代理主節(jié)點(diǎn)，且會(huì)剔除拜占庭節(jié)點(diǎn)，所以主節(jié)點(diǎn)是拜占庭節(jié)點(diǎn)的概率就會(huì)降低，那么試圖更換次數(shù)隨之減少，整個(gè)共識(shí)節(jié)點(diǎn)的數(shù)量也會(huì)減少，導(dǎo)致完成共識(shí)的時(shí)間隨之縮短。

圖10 吞吐量對(duì)比Figure 10 Throughput comparison

5 結(jié)語(yǔ)

本文針對(duì)區(qū)塊鏈應(yīng)用廣泛的PBFT 共識(shí)算法進(jìn)行了深入研究，提出了基于信譽(yù)和聚類的動(dòng)態(tài)拜占庭容錯(cuò)改進(jìn)算法。與PBFT 相比，本文算法具有通信開銷小、低時(shí)延，高吞吐量和較好的擴(kuò)展性等優(yōu)點(diǎn)。但是本文采用的K-medoids 需要反復(fù)計(jì)算簇內(nèi)節(jié)點(diǎn)到其他節(jié)點(diǎn)的歐氏距離，增加了算法的計(jì)算量，未來(lái)將考慮根據(jù)應(yīng)用場(chǎng)景選擇節(jié)點(diǎn)間地理位置，機(jī)器條件或網(wǎng)絡(luò)延遲等具體特征作為分區(qū)域的依據(jù)，同時(shí)將研究更適合的分區(qū)域算法，使之更適合應(yīng)用于現(xiàn)實(shí)區(qū)塊鏈。