董德寶，王云光

（1.上海理工大學(xué) 健康科學(xué)與工程學(xué)院，上海 200000；2.上海健康醫(yī)學(xué)院 醫(yī)療器械學(xué)院，上海 200120）

0 引言

拜占庭容錯(cuò)算法BFT最早由Pease和Lamport在20世紀(jì)80年代提出[1]，它是依據(jù)節(jié)點(diǎn)之間相互發(fā)送消息來達(dá)成共識(shí)協(xié)議，此協(xié)議的時(shí)間復(fù)雜度為指數(shù)級(jí)，現(xiàn)實(shí)中并未得到大量普及應(yīng)用。1999年Miguel Castro和Barbara Liskov提出 了實(shí)用拜占庭容錯(cuò)算法（Practical Byzantine Fault Tolerance，PBFT），解決了原始BFT算法的信息傳輸復(fù)雜度太高的問題，由此實(shí)用拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)中變得可行[2]。PBFT算法成功實(shí)現(xiàn)將BFT算法的時(shí)間復(fù)雜度從指數(shù)級(jí)降低到多項(xiàng)式級(jí)別[3]，在實(shí)際應(yīng)用中得到普及，但是該算法對(duì)節(jié)點(diǎn)的共識(shí)一致要求較高，更加適合私有鏈和聯(lián)盟鏈[4]。

1 PBFT共識(shí)協(xié)議

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

實(shí)用拜占庭容錯(cuò)算法由五個(gè)共識(shí)階段組成，分別為請(qǐng)求階段（request）、預(yù)準(zhǔn)備階段（pre-prepare）、準(zhǔn)備階段（prepare）、提交階段（commit）、反饋階段（reply），如圖1所示。

圖1 PBFT算法共識(shí)流程

1.2 PBFT算法共識(shí)詳情

請(qǐng)求階段：主節(jié)點(diǎn)（primary）接收來自客戶端（cilent）的請(qǐng)求信息，主要驗(yàn)證客戶端的簽名是否正確（若正確，則請(qǐng)求成功；否則，請(qǐng)求失敗），并將信息打包成格式為

預(yù)準(zhǔn)備階段：主節(jié)點(diǎn)（primary）將接收到客戶端的正確請(qǐng)求信息，按照請(qǐng)求號(hào)的先后順序依次分發(fā)給副本節(jié)點(diǎn)（replica），并將信息打包成格式為<

準(zhǔn)備階段：從節(jié)點(diǎn)（replica）收到主節(jié)點(diǎn)（primary）的預(yù)準(zhǔn)備消息后，首先，驗(yàn)證預(yù)準(zhǔn)備消息的真實(shí)性，驗(yàn)證通過再將預(yù)準(zhǔn)備消息和準(zhǔn)備消息打包發(fā)送給剩余從節(jié)點(diǎn)，并將相應(yīng)信息寫入日志文件，其信息的打包格式為

提交階段：所有的節(jié)點(diǎn)（主節(jié)點(diǎn)和從節(jié)點(diǎn)）將所有確認(rèn)過的消息廣播給其他節(jié)點(diǎn)，其信息的格式為

反饋階段：客戶端會(huì)接受來自節(jié)點(diǎn)的共識(shí)結(jié)果反饋，當(dāng)接收到（f+1）個(gè)確認(rèn)消息后，則系統(tǒng)達(dá)成共識(shí)，每個(gè)節(jié)點(diǎn)的發(fā)送信息格式為

2 PBFT算法優(yōu)化及設(shè)計(jì)

2.1 PBFT算法的不足

由于PBFT共識(shí)算法的主節(jié)點(diǎn)僅有一個(gè)且選取隨意，它負(fù)責(zé)對(duì)客戶端的請(qǐng)求進(jìn)行排序[4]，每個(gè)請(qǐng)求打上需求號(hào)標(biāo)記，在接下來的區(qū)塊打包過程中，按照需求號(hào)從低到高的順序進(jìn)行處理，并將主節(jié)點(diǎn)收到的信息廣播給其他從節(jié)點(diǎn)。由于隨意選取主節(jié)點(diǎn)，有概率選擇的主節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)，在經(jīng)過五輪算法共識(shí)后，結(jié)果不一致，就會(huì)觸發(fā)視圖轉(zhuǎn)換（view-change）機(jī)制，更換下一個(gè)節(jié)點(diǎn)（也有可能為拜占庭節(jié)點(diǎn)）作為主節(jié)點(diǎn)，無法防止主節(jié)點(diǎn)作惡，這種情況下就增加了網(wǎng)絡(luò)開銷和通信時(shí)延，使算法的效率下降。

2.2 N-P PBFT算法思路

筆者通過閱讀大量文獻(xiàn)發(fā)現(xiàn)，很多學(xué)者將選取主節(jié)點(diǎn)為主要方向，引入積分制、可信列表、隨機(jī)函數(shù)、門限簽名等優(yōu)化主節(jié)點(diǎn)選取機(jī)制。本文提出無主節(jié)點(diǎn)共識(shí)算法（NO-PRIMARY PBFT，簡稱N-P PBFT）思路，即將主節(jié)點(diǎn)負(fù)責(zé)的客戶端需求按序處理，并將客戶端信息分發(fā)給從節(jié)點(diǎn)的處理過程置于共識(shí)算法之外，由客戶端負(fù)責(zé)“擔(dān)任”主節(jié)點(diǎn)，客戶端將以時(shí)間戳先后順序處理業(yè)務(wù)請(qǐng)求，其N-P PBFT共識(shí)算法的流程如圖2所示。

2.3 優(yōu)化的PBFT算法設(shè)計(jì)

N-P PBFT共識(shí)算法在原來PBFT共識(shí)算法的基礎(chǔ)上省去了選取主節(jié)點(diǎn)的流程，采用無主節(jié)點(diǎn)共識(shí)流程，其具體分為：處理階段（dispose）、準(zhǔn)備階段（prepare）、提交階段（commit）、回復(fù)階段（reply）、分發(fā)階段（distribute），如圖2所示。

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

處理階段：引入外部服務(wù)（extra-service）用來接收和處理客戶端請(qǐng)求，按照時(shí)間戳將需求分配任務(wù)號(hào)依次處理請(qǐng)求，并將信息打包成格式為

準(zhǔn)備階段：將外部服務(wù)處理好的需求，依次發(fā)給參與共識(shí)的所有區(qū)塊節(jié)點(diǎn)，并將信息打包成格式為<

提交階段：所有的節(jié)點(diǎn)將所有確認(rèn)過的消息廣播給其他節(jié)點(diǎn)，其信息的格式為

反饋階段：客戶端會(huì)接受來自節(jié)點(diǎn)的共識(shí)結(jié)果反饋，當(dāng)接收到（f+1）個(gè)確認(rèn)消息后，則系統(tǒng)達(dá)成共識(shí)，其每個(gè)節(jié)點(diǎn)的發(fā)送信息格式為

分發(fā)階段：客戶端接收到參與共識(shí)的節(jié)點(diǎn)的結(jié)果反饋后，通過外部服務(wù)判斷接收到共識(shí)的消息個(gè)數(shù)是否大于（f+1）個(gè)，若滿足，則認(rèn)為本次共識(shí)過程成功達(dá)成，反之，共識(shí)失敗。

3 N-P PBFT與PBFT算法實(shí)驗(yàn)對(duì)比

本課題采用的操作系統(tǒng)為MICROSOFT WINDOWS 11專業(yè)版、版本為10.0.22000 BUILD 22000、類型為X64-BASED PC、處理器為INTEL64 FAMILY 6 MODEL 142 STEPPING 10 GENUINEINTEL～1801 MHZ的PC電 腦，通 過JavaScript程序?qū)崿F(xiàn)。

在PBFT算法中，假設(shè)算法性能測試的總節(jié)點(diǎn)個(gè)數(shù)為d（d≥3，d∈N*），當(dāng)主節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)則會(huì)進(jìn)行視圖轉(zhuǎn)換，新增的通信次數(shù)為d（d-1），假設(shè)發(fā)生視圖轉(zhuǎn)換的概率為q，并模擬存在一個(gè)拜占庭節(jié)點(diǎn)的情況下開展算法性能測試，PBFT算法的通信時(shí)間復(fù)雜度為O（N2），其中PBFT算法在完成一次完整共識(shí)（五個(gè)階段）的過程中的總通信次數(shù)SUMPBFT為：

N-P PBFT算法中，為保證測試條件的一致性，假設(shè)算法性能測試的總節(jié)點(diǎn)個(gè)數(shù)為d（d≥3，d∈N*），在SUMN-PPBFT算法中，無主節(jié)點(diǎn)參與共識(shí)，故不會(huì)存在主節(jié)點(diǎn)故障或者為拜占庭節(jié)點(diǎn)時(shí)發(fā)生視圖轉(zhuǎn)換協(xié)議概率，同時(shí)模擬系統(tǒng)中存在一個(gè)拜占庭節(jié)點(diǎn)的情況下開展算法性能測試。在處理階段和分發(fā)階段由外部服務(wù)處理和分發(fā)客戶端信息，不參與算法共識(shí)流程，故參與共識(shí)的階段為準(zhǔn)備階段，其通信次數(shù)為d；在提交階段，其通信次數(shù)為（d-1）（d-1）；在反饋階段，其通信次數(shù)為d-1。故N-P PBFT算法在完成一次完整共識(shí)的過程中的總通信次數(shù)SUMN-PPBFT為：

對(duì)比兩種算法的通信開銷性能，本次實(shí)驗(yàn)采用參與共識(shí)流程的節(jié)點(diǎn)總數(shù)以4，10，16，22，28為例，分別計(jì)算兩種算法下的通信開銷次數(shù)，如表1所示。

表1 兩種算法的通信開銷次數(shù)

通過對(duì)比PBFT和N-P PBFT算法的通信開銷性能（如圖3所示），當(dāng)參與共識(shí)的系統(tǒng)節(jié)點(diǎn)總數(shù)為4個(gè)時(shí)，兩種算法的通信開銷分別為22次和16次，通信次數(shù)相近，但是隨著系統(tǒng)中節(jié)點(diǎn)數(shù)的增加，可以看出N-P PBFT算法的通信開銷相對(duì)PBFT算法有了顯著的優(yōu)化。

圖3 兩種算法的通信開銷對(duì)比

根據(jù)PBFT和N-P PBFT算法在同一假設(shè)條件下的通信，可以看出其通信時(shí)間復(fù)雜度都是O（N2），但是PBFT算法可能存在主節(jié)點(diǎn)故障或者癱瘓，觸發(fā)視圖轉(zhuǎn)換協(xié)議增加通信次數(shù)，而N-P PBFT算法提出無主節(jié)點(diǎn)共識(shí)算法流程能夠完全避免PBFT的主節(jié)點(diǎn)相關(guān)問題。為了更加明顯地看出兩種算法在通信性能上的差異，兩種算法的單次通信開銷比б（overhead traffic）=SUMPBFT/SUMN-PPBFT，計(jì)算公式如下：

同樣，本次實(shí)驗(yàn)采用參與共識(shí)流程的節(jié)點(diǎn)總數(shù)以4，10，16，22，28為例，分別計(jì)算當(dāng)q=0和q=1時(shí)兩種算法下的通信開銷次比，如表2所示。

表2 兩種算法的單次通信開銷比

通過將PBFT與N-P PBFT算法的通信開銷進(jìn)行對(duì)比，在圖4中可以看出其бcommunicationtimesratio值恒大于1，同時(shí)，考慮到PBFT算法可能會(huì)發(fā)生視圖轉(zhuǎn)換的概率q，本次實(shí)驗(yàn)采取了q=0和q=1兩種情況，q=0即主節(jié)點(diǎn)是正常節(jié)點(diǎn)，未發(fā)生視圖轉(zhuǎn)換；q=1即主節(jié)點(diǎn)故障或者為拜占庭節(jié)點(diǎn)，從而會(huì)發(fā)生視圖轉(zhuǎn)換，導(dǎo)致PBFT算法中通信開銷增加?？紤]到現(xiàn)實(shí)的一般性，現(xiàn)實(shí)中的бcommunicationtimesratio在圖4中表現(xiàn)位于бcommunicationtimesratio（q=1）和бcommunicationtimesratio（q=0）之間，本次實(shí)驗(yàn)采取兩種極端情形。從圖4可以看出，當(dāng)q=0時(shí)，бcommunicationtimesratio值恒大于1，可以看出隨著節(jié)點(diǎn)數(shù)的增加，бcommunicationtimesratio值也會(huì)呈現(xiàn)正相關(guān)，說明N-P PBFT對(duì)優(yōu)化算法的通信開銷有較大的提升。

圖4 兩種算法的單次通信開銷比

為了更明顯地看出兩種算法通信開銷比的相對(duì)差異和N-P PBFT算法相對(duì)于PBFT算法的優(yōu)化量化數(shù)據(jù)，假設(shè)在沒有遇到視圖轉(zhuǎn)換協(xié)議的情況下，即q=0，采用ψ表示累計(jì)通信開銷比，其計(jì)算方法為d∈N*），詳細(xì)的計(jì)算公式如下：

同樣，本次實(shí)驗(yàn)采用參與共識(shí)流程的節(jié)點(diǎn)總數(shù)以4，10，16，22，28為例，分別計(jì)算當(dāng)q=0時(shí)兩種算法下的累計(jì)通信開銷次比，如表3所示。

表3 兩種算法的累計(jì)通信開銷比

由兩種算法的累計(jì)通信開銷比（見圖5）可以看出，隨著系統(tǒng)節(jié)點(diǎn)數(shù)的增加，累計(jì)通信開銷比ψsumcommunicationoverhead呈現(xiàn)類似一次函數(shù)趨勢增長，k值約等于0.684，在假設(shè)PBFT算法沒有發(fā)生視圖轉(zhuǎn)換的情況下（q=0），PBFT算法的通信次數(shù)最小。從圖5可以看出累計(jì)通信開銷比ψsumcommunicationoverhead的增長趨勢，由此可以得出N-P PBFT相對(duì)于PBFT算法的性能得到進(jìn)一步優(yōu)化。

圖5 兩種算法的累計(jì)通信開銷比

4 結(jié)語

通過優(yōu)化傳統(tǒng)的PBFT算法，在原有算法達(dá)成一致性共識(shí)流程中，引入外部服務(wù)擔(dān)任主節(jié)點(diǎn)角色，避免在選取主節(jié)點(diǎn)時(shí)帶來的一定概率選中拜占庭節(jié)點(diǎn)或者節(jié)點(diǎn)宕機(jī)情形，從而觸發(fā)視圖轉(zhuǎn)換協(xié)議，增加一致性共識(shí)階段的通信開銷，改善了原有五個(gè)階段的共識(shí)方式，有效降低了通信次數(shù)，通過最終實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，N-P PBFT相對(duì)于PBFT算法在通信復(fù)雜度都為O（N2）的基礎(chǔ)上，在實(shí)驗(yàn)設(shè)置的假設(shè)條件中，N-P PBFT有效降低了原有算法的通信開銷，系統(tǒng)的算法共識(shí)一致性效率得到明顯提升。