基于組播通信的PBFT 算法改進(jìn)*

楊孝天，馬 冉，李 江，高 飛

（西藏大學(xué) 信息科學(xué)技術(shù)學(xué)院，西藏 拉薩 850000）

0 引言

區(qū)塊鏈采用P2P（peer-to-peer）通信模式，P2P 是一種分布式網(wǎng)絡(luò)，節(jié)點之間可以直接進(jìn)行信息交換。P2P為區(qū)塊鏈提供高效、安全、通用的網(wǎng)絡(luò)通信基礎(chǔ)，支持區(qū)塊鏈進(jìn)行單播、組播和廣播通信[1]。P2P 具有如下功能：(1)標(biāo)識區(qū)塊鏈節(jié)點，每一個區(qū)塊鏈節(jié)點都被唯一標(biāo)識，區(qū)塊鏈節(jié)點通過唯一的節(jié)點標(biāo)識進(jìn)行尋址;(2)管理網(wǎng)絡(luò)連接，負(fù)責(zé)維護(hù)區(qū)塊鏈節(jié)點之間的正常連接和異常連接;(3)消息發(fā)送，支持區(qū)塊鏈消息進(jìn)行單播、組播和廣播;(4)同步狀態(tài)，完成區(qū)塊鏈節(jié)點間信息的同步。

PBFT 算法起源于拜占庭將軍問題，為解決拜占庭將軍問題，Leslie Lamport 提出了BFT（拜占庭容錯算法）。基于BFT 拜占庭容錯算法，Miguel Castro(卡斯特羅)和Barbara Liskov(利斯科夫)于1999 年提出了PBFT算法，將BFT 算法復(fù)雜度從指數(shù)級降到多項式級，使得PBFT 共識算法可應(yīng)用于實際系統(tǒng)中[2]。PBFT 作為一種共識機(jī)制被應(yīng)用于區(qū)塊鏈，相較主流共識機(jī)制POW[3]10 min 出一塊，PBFT 算法可以做到秒級確認(rèn)交易，節(jié)約算力資源，并且可以容錯1/3 的錯誤節(jié)點（故障節(jié)點、欺騙節(jié)點等）。但是PBFT 仍存在網(wǎng)絡(luò)復(fù)雜度高、延遲高、性能隨節(jié)點的增多而下降等問題。

當(dāng)前學(xué)者就PBFT 算法存在的問題做出了大量的研究，研究可以分為如下幾類：通過分組來提高算法效率，如王謹(jǐn)東[4]提出使用K-medoids 聚類算法將所有節(jié)點劃分為多個節(jié)點簇，提出了一種基于PBFT 與Raft 改進(jìn)的拜占庭容錯共識算法K-RPBFT；引入信譽(yù)機(jī)制改善PBFT 算法，如楊昕宇[5]提出一種基于演化博弈的理性實用拜占庭容錯共識算法，基于信譽(yù)對共識節(jié)點進(jìn)行劃分；基于角色的PBFT 算法改進(jìn)，如李騰[6]提出一種基于角色管理的拜占庭容錯（RPBFT）共識算法，首先將系統(tǒng)中的節(jié)點劃分為管理者、候選者和普通節(jié)點3 類具有不同職責(zé)的角色節(jié)點，通過分配不同節(jié)點不同的任務(wù)進(jìn)而提高PBFT 算法的效率。當(dāng)前相關(guān)PBFT 算法的研究大多數(shù)都是基于算法的優(yōu)化[7-9],進(jìn)而提高算法的效率。本文從通信技術(shù)方面改進(jìn)PBFT 算法，引入組播通信應(yīng)用于基于角色的PBFT 算法[10-11]，優(yōu)化PBFT 共識算法，通過角色分配和組播通信兩大技術(shù)實現(xiàn)動態(tài)地選取參與共識的節(jié)點，以解決傳統(tǒng)PBFT 共識算法存在高時延、高復(fù)雜性、不能處理大規(guī)模節(jié)點等問題。

1 算法設(shè)計

1.1 一致性算法

將原來相關(guān)節(jié)點廣播的算法改為組內(nèi)組播算法過程如圖1 所示,其中,×表示拜占庭節(jié)點，О 表示非訂閱節(jié)點，非訂閱節(jié)點不參與共識。WRPBFT 算法模塊包括Request、Pre-request、Prepare、Commit、Reply 5 個階段，非訂閱節(jié)點不參與共識過程。

圖1 一致性算法原理圖

(1) Request：客戶節(jié)點發(fā)送Request 請求。

(2) Pre-prepare：主節(jié)點收到客戶節(jié)點發(fā)送的Request 請求，產(chǎn)生簽名包，并將簽名包與Pre-prepare 進(jìn)行組播，發(fā)送給訂閱節(jié)點。

(3) Prepare：收集簽名包，節(jié)點收集滿2·f+1 簽名包后，開始廣播Commit。

(4) Commit：收集Commit，節(jié)點收集滿2·f+1 Commit 包，開始廣播Reply。

(5) 統(tǒng)計Reply 信息，統(tǒng)計完后將最新的區(qū)塊提交至主節(jié)點。

1.2 節(jié)點類型與共識節(jié)點選擇

1.2.1 節(jié)點類型

節(jié)點包括以下4 種：Client 客戶節(jié)點、Primary 主節(jié)點、Replica 共識節(jié)點、Candidate 候選節(jié)點，其功能如表1所示。客戶節(jié)點負(fù)責(zé)發(fā)送交易請求。主節(jié)點負(fù)責(zé)接收客戶節(jié)點的交易請求，并進(jìn)行交易打包，篩選參與本次共識的共識節(jié)點并發(fā)布訂閱信息。每輪只有一個主節(jié)點，主節(jié)點也是共識節(jié)點，是由共識節(jié)點選舉而出的。共識節(jié)點負(fù)責(zé)完成區(qū)塊共識，共識節(jié)點有多個，每個共識節(jié)點都具有相同的處理過程。候選節(jié)點負(fù)責(zé)校驗每個區(qū)塊共識節(jié)點簽名是否到達(dá)2/3，校驗區(qū)塊的執(zhí)行結(jié)果是否一致。

表1 不同節(jié)點類型功能表

1.2.2 共識節(jié)點選擇

參與共識算法的節(jié)點有共識節(jié)點和候選節(jié)點，共識節(jié)點負(fù)責(zé)執(zhí)行PBFT 共識算法，并具備成為主節(jié)點的資格。候選節(jié)點不具備成為主節(jié)點的資格，負(fù)責(zé)對共識節(jié)點的合法性驗證，候選節(jié)點具備成為新的共識節(jié)點資格。共識節(jié)點也并不是一直保持不變，每經(jīng)過i次共識，共識節(jié)點便與候選節(jié)點完成一次替換；并且可以動態(tài)地設(shè)置共識節(jié)點個數(shù)，達(dá)到動態(tài)配置共識節(jié)點。如圖2 所示，替換周期i通過設(shè)置替換周期。

圖2 共識節(jié)點選擇核心思想圖

1.3 組播通信通信模型

1.3.1 引入Topic

基于AMOP（Advanced Messages Onchain Protocol）鏈上信使協(xié)議，通過訂閱Topic 來實現(xiàn)節(jié)點間組播通信，引入組播通信包括以下兩個部分：(1)共識節(jié)點執(zhí)行PBFT 共識算法的過程，從共識節(jié)點選取參與本次共識的rc個共識節(jié)點進(jìn)行節(jié)點間組播，組播完成PBFT 共識算 法Request、Pre-request、Prepare 共識過 程；(2)候選節(jié)點執(zhí)行節(jié)點驗證，采用組播通信的方式選擇參與驗證的節(jié)點?；贏MOP 實現(xiàn)組播通信，AMOP 支持點對點的實時通信，為區(qū)塊鏈提供安全高效的消息傳輸信道，AMOP 基于SSL 通信加密，確保消息無法被竊聽，消息收發(fā)均有異常重傳、超時檢測和路徑規(guī)劃機(jī)制，其實現(xiàn)組播通信原理如圖3 所示：一個發(fā)送者，多個接收者。消息發(fā)送者（Message Queue 消息隊列是應(yīng)用程序之間的通信方法）獲取到連接以及Message Queue 通道，綁定隊列到交換機(jī)。每一個接收者都有自己的隊列并綁定到交換機(jī)，消息發(fā)送者將信息發(fā)送到交換機(jī)。消息發(fā)送者發(fā)送的信息經(jīng)過交換機(jī)到達(dá)隊列，實現(xiàn)一個信息多個接收者獲取的目的。

圖3 組播通信原理圖

1.3.2 引入索引列表

(1)通過索引列表添加訂閱節(jié)點ID 和Topic 訂閱信息，提高通信效率與管理效率；(2)考慮到節(jié)點ID 與Topic（PBFT 共識算法以公鑰作為節(jié)點ID，一般是64 B）在共識過程中會消耗部分寬帶，引入節(jié)點索引，可以減少通信過程中的帶寬消耗。所有共識節(jié)點共同維護(hù)一份公共的共識節(jié)點與Topic 列表，所有的候選節(jié)點共同維護(hù)一張公共的驗證節(jié)點與Topic 列表。節(jié)點列表記錄了每個共識節(jié)點ID 在這個列表中的位置，如圖4 所示，索引列表對節(jié)點進(jìn)行重新的排序并添加排序編號，記錄節(jié)點Topic 訂閱信息。發(fā)送消息時，只需要帶上節(jié)點編號，其他節(jié)點即可以從公共的節(jié)點列表中索引出節(jié)點的ID 和相應(yīng)的組播信息實現(xiàn)區(qū)塊鏈網(wǎng)絡(luò)組播通信。

圖4 索引列表原理圖

2 算法實現(xiàn)

2.1 共識機(jī)制

(1) 選取共識節(jié)點：開始WRPBFT 選取n個共識節(jié)點參與共識（共識節(jié)點列表為listR[n-1]）,為確保去中心化和系統(tǒng)的安全性，每經(jīng)過i輪的共識需要進(jìn)行共識節(jié)點和候選節(jié)點的替換，確保每個節(jié)點都具備參與共識的權(quán)力。候選節(jié)點替換共識節(jié)點替換策略如下：將節(jié)點索引為list[i]的共識節(jié)點從共識節(jié)點中剔除，并加入(list[i].idx+K)%(n-1)對應(yīng)候選節(jié)點作為新的共識節(jié)點。其中i為第i輪，list[i].idx為編號為i對應(yīng)的節(jié)點索引，n為共識節(jié)點總數(shù)，K為出塊數(shù)，%為取余操作。替換成功后從索引列表刪除對應(yīng)共識節(jié)點和加入新的共識節(jié)點。

(2) 選取主節(jié)點：PBFT 共識過程中，共識節(jié)點輪流成為主節(jié)點，主節(jié)點選取策略如下：

其中，m表示共識節(jié)點個數(shù)，n表示驗證節(jié)點個數(shù)，v表示視圖數(shù)。

(3) 選取進(jìn)行組播通信節(jié)點：主節(jié)點選取后，主節(jié)點首先判斷當(dāng)前主節(jié)點與自己索引是否相同，相同則選取rc個共識節(jié)點編號進(jìn)行節(jié)點間相互訂閱，訂閱完成后進(jìn)行節(jié)點之間的組播，根據(jù)共識節(jié)點索引列表listR[n-1]選取rc個共識節(jié)點，選取策略如下：

其中，n表示共識節(jié)點總個數(shù)，Rc表示在[0，n-1]內(nèi)隨機(jī)選取的數(shù)。

(4) 節(jié)點開始打包：首先獲取最新的區(qū)塊高度，并基于最高高度的區(qū)塊產(chǎn)生新的區(qū)塊，取最高區(qū)塊作為當(dāng)前區(qū)塊的父哈希，記錄當(dāng)前時間為時間戳，交易記為空。從交易池中獲取交易，添加為新的交易記錄，組裝成新的塊，將新塊添加到Prepare 包中，向所有訂閱節(jié)點進(jìn)行組播，訂閱節(jié)點收到后進(jìn)行Pre-request 階段。

(5) Pre-request 負(fù)責(zé)判斷是否存在重復(fù)的Prepare包，判斷當(dāng)前節(jié)點處于的區(qū)塊高度，當(dāng)前節(jié)點區(qū)塊的父哈希節(jié)點塊是否正確，完成對區(qū)塊的執(zhí)行并組播簽名包。

(6) 共識節(jié)點收到簽名包后進(jìn)入Prepare 階段對簽名進(jìn)行合法性判斷并緩存合法的簽名包，判斷緩存的簽名包是否達(dá)到2·f+1，若收集滿則進(jìn)行廣播Commit 包。

(7) 進(jìn)入Commit 階段：Commit 階段負(fù)責(zé)判斷Commit 信息包是否合法，合法則緩存，若Commit 信息包大于2·f+1，則向主節(jié)點發(fā)送Reply 信息，產(chǎn)生新區(qū)快。

2.2 錯誤應(yīng)對機(jī)制

(1) 主節(jié)點錯誤

如果主節(jié)點宕機(jī)、不發(fā)消息，或者發(fā)送錯誤編碼、進(jìn)行篡改信息等，觸發(fā)view-change 進(jìn)行主節(jié)點重新選舉，所有共識節(jié)點都參加投票，當(dāng)有2f+1 個共識節(jié)點投票，觸發(fā)重選。選舉策略如下：

(2) 共識節(jié)點錯誤

由于采用的組播通信機(jī)制，本文已采用隨機(jī)選取共識節(jié)點來完成PBFT 共識，導(dǎo)致拜占庭容錯數(shù)量減少，即出現(xiàn)拜占庭容錯問題會增多。為減少這類事情的發(fā)生，本文采取多次組播策略，如果出現(xiàn)這樣的問題就進(jìn)行再次組播(i表示選取參與驗證的驗證節(jié)點編號)。設(shè)置進(jìn)行j輪組播后將不再進(jìn)行組播，直接進(jìn)行廣播所有共識節(jié)點進(jìn)行共識算法處理，應(yīng)對策略如下：選取上一次參加共識的共識節(jié)點索引對應(yīng)的下一個節(jié)點。

3 實驗仿真

3.1 實驗結(jié)果

實驗是基于Python 語言實現(xiàn)的PBFT 算法，模擬多個節(jié)點之間進(jìn)行PBFT 共識算法，通過一臺電腦模擬多個節(jié)點進(jìn)行共識。實驗可以人為地設(shè)定參與共識的共識節(jié)點規(guī)模，本實驗設(shè)定WRPBFT 共識節(jié)點的節(jié)點規(guī)模為節(jié)點規(guī)模1/10，參與組播節(jié)點規(guī)模為共識節(jié)點的1/3。

吞吐量能夠反映出共識機(jī)制對事務(wù)并發(fā)的處理能力。在區(qū)塊鏈系統(tǒng)中，吞吐量通常用區(qū)塊鏈系統(tǒng)在單位時間內(nèi)處理的交易總量(Transaction Per Second,TPS)表示，單位為t/s。實驗對比處理不同個事務(wù)請求在PBFT算法與RPBFT 和WRPBFT 算法的吞吐量，如圖5 所示。由圖可知，WRPBFT 算法相較其他兩種算法具備更高的吞吐量。這是因為更少的共識節(jié)點參與共識，共識過程處理的交易量較少，進(jìn)而提高了算法的吞吐量。

圖5 算法吞吐量對比圖

時延表示交易從客戶端提交到交易被寫入?yún)^(qū)塊的時間差。如圖6 所示，對比PBFT、RPBFT、WRPBFT 算法在不同事務(wù)請求規(guī)模情況下時延隨處理請求事務(wù)的折線圖。由圖可得，隨著處理事務(wù)量的增加，WRPBFT算法相較其他兩種算法的時延更低，這是因為相同節(jié)點規(guī)模下WRPBFT 算法更少的節(jié)點參與共識，節(jié)省了共識處理過程的時延。

圖6 算法時延對比圖

共識過程信息量記錄了request、pre_prepare、prepare、commit、reply、view_change 發(fā)送的信息包之和，信息量反映網(wǎng)絡(luò)通信復(fù)雜度情況。如圖7 所示，對比不同算法在共識過程處理信息量，WRPBFT 算法在共識處理過程處理的信息量要低于傳統(tǒng)的PBFT 算法，有效降低了網(wǎng)絡(luò)通信復(fù)雜度。

圖7 算法信息量對比圖

3.2 實驗分析

(1) 時間復(fù)雜度不受節(jié)點規(guī)模的影響：客戶節(jié)點進(jìn)行組播復(fù)雜度為nr，共識節(jié)點進(jìn)行組播復(fù)雜度為nr2，共識Pre-prepare 階段雜度為nr，共識Prepare 階段雜度為nr2，共識Commit 階段雜度為nr2，回復(fù)給客戶節(jié)點雜度為nr，所以總的時間復(fù)雜度為：nr+nr2+nr+nr2+nr2+nr=3·nr2+3nr=3nr(nr+1)。共識算法復(fù)雜度是基于選取參與共識節(jié)點的規(guī)模，與總的節(jié)點規(guī)模無關(guān)，只與參與共識的共識節(jié)點規(guī)模有關(guān)。

(2) 帶寬占用低：如果每個節(jié)點都進(jìn)行信息的廣播與轉(zhuǎn)發(fā)可能會導(dǎo)致帶寬被占滿，導(dǎo)致系統(tǒng)癱瘓。本文采用組播通信模式：只取部分共識節(jié)點之間進(jìn)行組播，以達(dá)成共識，可以有效節(jié)省帶寬。在具有n個共識節(jié)點和m個候選節(jié)點的區(qū)塊鏈系統(tǒng)中，采用組播進(jìn)行選取rv＜n個共識節(jié)點，rc＜m個候選節(jié)點進(jìn)行驗證，假設(shè)共識一次信息大小為BS，在理想狀態(tài)下每共識進(jìn)行一次共識都需要向rv個共識節(jié)點發(fā)送信息，共識節(jié)點帶寬為(rv·BS)，(rv·BS)＜((n+m)·BS）。帶寬不受節(jié)點規(guī)模影響而是隨著rv節(jié)點個數(shù)的減小而減小，WRPBFT 可以將帶寬降低為原來的rv/(n+m)。雖然WRPBFT 算法采用二進(jìn)制標(biāo)識對應(yīng)索引表中Topic 會增加通信信息量，可能會產(chǎn)生相應(yīng)的時延。相應(yīng)算法如下：假設(shè)共識規(guī)模為10 000個，則會增加100 00 bit 的帶寬。一個節(jié)點ID 為64 B=64·1024 bit（1B=1024 bit，一個bit 是計算機(jī)中的最小單位,簡單的說就是一個0 或一個1）相當(dāng)于增加0.152 個節(jié)點ID，僅僅增加在索引列表，幾乎不影響算法性能。

(3) WRPBFT 算法也存在以下缺點：如果選擇參與共識的節(jié)點代表性低，將不能作為平均分布代表。因為參與共識的節(jié)點數(shù)量少，將會降低算法的容錯率，并且出現(xiàn)共識錯誤后，處理共識錯誤復(fù)雜增加。其中容錯性分析如下：假設(shè)共有N個共識節(jié)點，拜占庭容錯節(jié)點為1/n，參與共識過程的共識節(jié)點選取規(guī)則為1/r，則令參與共識節(jié)點個數(shù)為A=N·(1/r)，令拜占庭節(jié)點為B=N·(1/n)。出現(xiàn)拜占庭錯誤節(jié)點的概率為：

其中，A·（1/3）＜i≤B。

4 結(jié)論

針對PBFT 算法通信復(fù)雜度高、性能受節(jié)點增加而下降等問題，本文提出了一種改進(jìn)的WRPBFT 算法。通過實驗仿真表明，WRPBFT 算法相較PBFT 與RPBFT 算法具有更高的吞吐量和更低的時延，且需要處理的信息量更少，性能不受節(jié)點數(shù)規(guī)模增加而下降。同時，本文也指出了WRPBFT 算法存在容錯率高的缺點，今后將在算法容錯性方面展開研究。此外，本文在實驗仿真過程中缺少實驗仿真的細(xì)化，并不能做到所有理論都應(yīng)用于實踐，仿真實驗有待進(jìn)一步完善，希望各位學(xué)者能給出意見，共同探討。