董德寶，王云光

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

0 引言

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

1 PBFT共識協(xié)議

1.1 PBFT算法共識流程

實用拜占庭容錯算法由五個共識階段組成，分別為請求階段（request）、預準備階段（pre-prepare）、準備階段（prepare）、提交階段（commit）、反饋階段（reply），如圖1所示。

圖1 PBFT算法共識流程

1.2 PBFT算法共識詳情

請求階段：主節(jié)點（primary）接收來自客戶端（cilent）的請求信息，主要驗證客戶端的簽名是否正確（若正確，則請求成功；否則，請求失?。⑿畔⒋虬筛袷綖?REQUEST，o，t，c＞的消息分發(fā)給主要節(jié)點，其中REQUEST為請求階段標識，o表示狀態(tài)機操作（operation）的執(zhí)行，t表示時間戳（timestamp），c為客戶端（client）標識。

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

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

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

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

2 PBFT算法優(yōu)化及設計

2.1 PBFT算法的不足

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

2.2 N-P PBFT算法思路

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

2.3 優(yōu)化的PBFT算法設計

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

圖2 NP-PBFT算法共識流程

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

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

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

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

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

3 N-P PBFT與PBFT算法實驗對比

本課題采用的操作系統(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程序實現(xiàn)。

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

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

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

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

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

圖3 兩種算法的通信開銷對比

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

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

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

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

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

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

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

表3 兩種算法的累計通信開銷比

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

圖5 兩種算法的累計通信開銷比

4 結語

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