胡繼圓, 于 瓅

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院,安徽 淮南 232001)

0 引 言

隨著區(qū)塊鏈的迅速發(fā)展,作為區(qū)塊鏈的核心技術(shù)—共識算法,逐漸掀起研究的熱潮,應(yīng)用最廣泛的共識算法之一為實用拜占庭容錯算法(PBFT),它很大程度上解決了惡意節(jié)點的問題,具有較高的共識效率。但當(dāng)前PBFT算法也存在一些不足,如節(jié)點不能動態(tài)加入或退出,當(dāng)作惡節(jié)點出現(xiàn)時,無法踢出該節(jié)點等。針對此類問題,國內(nèi)外學(xué)者從不同方面對PBFT做出了改進(jìn)。胡振宇[1]提出設(shè)計一種信譽機制,結(jié)合環(huán)簽名方式對PBFT共識過程進(jìn)行改進(jìn)。Xu[2]等人對PBFT算法流程進(jìn)行劃分,提高算法容錯性。Tang[3]等人利用節(jié)點分級的方式賦予節(jié)點不同權(quán)限,提高了PBFT算法的共識效率。這些方案從不同角度對PBFT進(jìn)行了改進(jìn),也取得一定效果,但其目前仍存在通信次數(shù)多,算法效率低以及惡意節(jié)點當(dāng)選主節(jié)點等問題。針對上述問題,提出一種基于雙重信譽機制實用拜占庭容錯算法,選擇部分高質(zhì)量節(jié)點參與共識,減少了節(jié)點通信次數(shù),增加懲罰機制以遏制低質(zhì)量節(jié)點作惡行為,提高共識效率。

1 相關(guān)背景介紹

1.1 PBFT算法基本概念

區(qū)塊鏈中有許多種類的共識算法,PBFT作為區(qū)塊鏈中最常用的投票類算法之一,以其算法復(fù)雜度較低、適用異步環(huán)境等特點被廣泛應(yīng)用。該算法由Castro和Liskov為解決拜占庭將軍問題而設(shè)計出的,目的是解決區(qū)塊鏈網(wǎng)絡(luò)中存在惡意節(jié)點問題,其三段式共識協(xié)議保障了網(wǎng)絡(luò)的安全運行,即當(dāng)系統(tǒng)存在3f+1個節(jié)點時,允許不超過f個節(jié)點出錯,PBFT算法賦予參與節(jié)點很大伸縮性,也使區(qū)塊鏈安全更有保障。

1.2 PBFT算法共識機制

PBFT算法規(guī)定一次共識的所有節(jié)點都在一個視圖里,節(jié)點分為主節(jié)點和從節(jié)點,主節(jié)點只有一個,由從節(jié)點輪流當(dāng)選?？蛻舳税l(fā)送請求后,由主節(jié)點接收客戶端發(fā)來的請求將其進(jìn)行排序編號,之后將消息發(fā)送給所有從節(jié)點,由從節(jié)點對消息進(jìn)行驗證和廣播,將結(jié)果返回給客戶端。PBFT的共識過程主要分為:Pre-prepare,prepare和commit三個階段,流程如圖1。

2 DB-PBFT算法

2.1 算法概述

針對PBFT算法中節(jié)點通信次數(shù)較多以及惡意節(jié)點當(dāng)選主節(jié)點的問題,這里提出一種基于雙重信譽機制的實用拜占庭容錯算法(DB-PBFT),通過考慮節(jié)點自身和在共識過程中的表現(xiàn),計算出每個節(jié)點的靜態(tài)和動態(tài)信譽值作為其總的信譽積分,以此標(biāo)記節(jié)點的狀態(tài)并對節(jié)點進(jìn)行劃分,再從中選擇信譽值高的節(jié)點作為主節(jié)點和共識節(jié)點,減少惡意節(jié)點作惡的幾率。此外,DB-PBFT算法還設(shè)計了對節(jié)點的獎懲機制,對積極參與共識響應(yīng)系統(tǒng)消息的節(jié)點提高其信譽度并給予定獎金作為獎勵,對出現(xiàn)故意占用資源和延遲響應(yīng)消息的行為的節(jié)點,沒收其押金并降低信譽度,該算法提高了系統(tǒng)的效率,確保共識的安全。

圖1 PBFT共識流程

2.2 雙重信譽機制

2.2.1 節(jié)點靜態(tài)信譽積分

節(jié)點第一次加入?yún)^(qū)塊鏈網(wǎng)絡(luò)時,應(yīng)考慮到其CPU利用率、投入固定成本和內(nèi)存等自身因素,假設(shè)區(qū)塊鏈網(wǎng)絡(luò)中有n個參與節(jié)點(n≥4)。

(1)CPU利用率

當(dāng)存在n個節(jié)點時,對于參與的每個節(jié)點i,一段時間t內(nèi)其CPU利用率為用戶狀態(tài)和內(nèi)核狀態(tài)下CPU的使用占總體的比值,用公式(1)計算:

CPU(t)=

(1)

(2)投入固定成本

節(jié)點i加入?yún)^(qū)塊鏈網(wǎng)絡(luò)時需要提交一定的押金Mi作為信任度的憑證,假設(shè)所有節(jié)點押金之和為Mn,節(jié)點投入固定成本對節(jié)點信任度的影響量為式(2):

(2)

(3)內(nèi)存利用率

設(shè)節(jié)點的總內(nèi)存為MEMTotal,一段時間內(nèi)閑置內(nèi)存為MEMFree,節(jié)點的內(nèi)存利用率計算方式為式(3):

(3)

通過上述公式的計算,可得出節(jié)點i靜態(tài)信譽值的計算方式為式(4):

(4)

2.2.2 節(jié)點動態(tài)信譽積分

影響節(jié)點動態(tài)信譽值的因素主要從節(jié)點通信積極度、節(jié)點共識影響度和共識表現(xiàn)行為等方面考慮。

(1)節(jié)點通信積極度

即節(jié)點在Δt時間內(nèi)請求通信消息次數(shù)MES(Δt)占總通信次數(shù)M的比例為式(5):

(5)

(2)節(jié)點共識影響度

設(shè)節(jié)點i在Δt時間內(nèi)成功參與共識次數(shù)為Gi,該段時間網(wǎng)絡(luò)內(nèi)總成功共識次數(shù)為G,節(jié)點未完成共識次數(shù)為Fi,共識失敗總次數(shù)為F,表示為式(6):

(6)

(3)共識表現(xiàn)行為

設(shè)θ為共識影響指數(shù),S為網(wǎng)絡(luò)中總的共識次數(shù),e為節(jié)點i最近一次參與共識的輪次數(shù),則共識表現(xiàn)行為表示為式(7):

(7)

計算節(jié)點i動態(tài)信譽積分為式(8):

Di=β1Vi+β2INFi+β3Ui(β1,β2,β3為權(quán)重值)

(8)

節(jié)點總信譽值為式(9):

Ri=u1Qi+u2Di(μ1,μ2為權(quán)重值)

(9)

節(jié)點更新自身信譽值需要耗費一定時間和算力,而長時間不更新信譽值會造成對節(jié)點狀態(tài)判斷的不準(zhǔn)確。因此設(shè)定每五次共識為一個周期,每一個周期開始前,節(jié)點都會更新自身狀態(tài)值以此作為節(jié)點劃分標(biāo)準(zhǔn)。

2.3 節(jié)點狀態(tài)劃分

為解決PBFT通信次數(shù)較多的問題,通過信譽值對節(jié)點進(jìn)行劃分,選擇部分節(jié)點參與共識。假設(shè)區(qū)塊鏈網(wǎng)絡(luò)中有3f+1個節(jié)點,經(jīng)過k輪共識后,劃分規(guī)則及不同節(jié)點的權(quán)限為:

(4)信譽值低于Kn的節(jié)點為Low節(jié)點。

表1 節(jié)點權(quán)限

2.4 獎懲機制與節(jié)點狀態(tài)轉(zhuǎn)移

節(jié)點每成功完成一次共識,系統(tǒng)將其信譽值增加0.1,同時系統(tǒng)會發(fā)放一定獎金以激勵其正確行為,當(dāng)節(jié)點發(fā)生故障時會扣除其0.5的信譽值,并沒收押金作為懲罰。當(dāng)?shù)偷裙?jié)點信譽值不斷增加大于Kn時,其節(jié)點狀態(tài)會變?yōu)镹ormal節(jié)點,隨著信譽值增加到Kt,該節(jié)點狀態(tài)將轉(zhuǎn)變?yōu)門rust節(jié)點,當(dāng)信譽值達(dá)到Kg時,其節(jié)點狀態(tài)會變?yōu)镾uperior節(jié)點,可以優(yōu)先成為主節(jié)點。若共識節(jié)點被判定為出現(xiàn)節(jié)點故障時,會降低其信譽值,直到低于閾值Kn,將被踢出共識群組。節(jié)點狀態(tài)轉(zhuǎn)移過程如圖2。

圖2 節(jié)點狀態(tài)轉(zhuǎn)換

3 實驗和分析

為證明DB-PBFT算法的優(yōu)越性,這里基于go語言來進(jìn)行算法的代碼編寫,實驗硬件為8GB內(nèi)存和Windows10的操作系統(tǒng),通過Hyperledger Fabric 2.0搭建平臺,由于共識需要的節(jié)點較多,故使用docker容器來仿真節(jié)點,對比實驗為PBFT和CLBFT[7]。

圖3 時延對比

3.1 共識時延

這里考慮拜占庭節(jié)點對系統(tǒng)的破壞為占用資源導(dǎo)致延遲響應(yīng),當(dāng)網(wǎng)絡(luò)中的節(jié)點為8,10,12,14,16和18時,分別對其做100次重復(fù)實驗,取最后的平均值為測試結(jié)果。

從圖3中可以看出,隨著節(jié)點數(shù)增多時,DB-PBFT共識時延明顯低于其他兩種算法。表現(xiàn)出較高的共識效率。

3.2 通信次數(shù)

當(dāng)區(qū)塊鏈網(wǎng)絡(luò)中有N個節(jié)點時,傳統(tǒng)PBFT算法的通信次數(shù)C為式(10):

C=2N2-2N

(10)

CLBFT算法的通信次數(shù)C＇為式(11):

C′=(P+2)N(N-1)+(N-1) (P∈(0,1))

(11)

(12)

圖4為三種算法在給定節(jié)點的情況下的通信次數(shù)對比圖,這里使用的對比算法CLBFT通信次數(shù)與概率P有關(guān),當(dāng)P為0時取得最小通信次數(shù)。

圖4 通信次數(shù)對比

從圖4中可以看出DB-PBFT算法的通信次數(shù)明顯低于其他兩種算法,當(dāng)節(jié)點增多時這種效果更加明顯,有效減少系統(tǒng)的通信開銷。

3.3 吞吐量測試

吞吐量的大小體現(xiàn)的是節(jié)點處理交易數(shù)據(jù)和響應(yīng)請求的能力,這里工作的節(jié)點設(shè)定為64,惡意節(jié)點是隨機產(chǎn)生的,但不超過21個,三種算法的吞吐量測試為圖5所示。

圖5 吞吐量對比

從圖5中可以看出,三種算法的吞吐量隨著共識次數(shù)增多都逐漸減小,這是由于節(jié)點自身工作性能影響導(dǎo)致的,但DB-PBFT算法實驗結(jié)果明顯高于另外兩種算法的吞吐量,有效提升了系統(tǒng)的工作效率。

4 結(jié) 語

通過對聯(lián)盟鏈中的PBFT共識算法進(jìn)行研究,發(fā)現(xiàn)其存在主節(jié)點選擇隨意、通信復(fù)雜度較高以及惡意節(jié)點無法排除等缺點,提出了一種基于雙重信譽機制的拜占庭容錯算法,根據(jù)節(jié)點信譽值選取部分高質(zhì)量節(jié)點參與共識,減少了主節(jié)點出錯的概率的同時降低了通信次數(shù)。通過實驗比對兩種算法可以看出,相較于PBFT和CLBFT算法,DB-PBFT更加節(jié)約資源,系統(tǒng)吞吐量以及工作效率都顯著提高。