適用于區塊鏈的高效異步拜占庭容錯算法

王耀啟 劉揚 李向陽 劉鑫磊 曹浩浩

摘 要：針對現有異步共識算法存在的多輪次通信開銷大、隨機抽簽算法中缺乏信譽機制導致了較多的抽取次數等不足，提出了一種高效的異步拜占庭容錯算法PenguinBFT。首先，在廣播交易時直接廣播原文，降低了共識通信開銷。其次，引入了節點信譽評估機制，從網絡情況相對穩定的節點集合中選取出塊者，以減少隨機抽取次數。最后，對網絡節點進行分區，在請求交易缺失時，讓不同的節點訪問不同的分區進行交易恢復，既能減少通信開銷又能提升交易恢復效率。實驗結果表明，當節點規模達到64時，提出的PenguinBFT算法相較于HoneyBadgerBFT、DumboBFT和DispersedLedger算法，在通信開銷、吞吐量和交易確認時延等方面均有50%以上的提升。

關鍵詞：區塊鏈； 異步拜占庭容錯算法； 傳輸效率； 信譽模型； 分區

中圖分類號：TP311?? 文獻標志碼：A

文章編號：1001-3695（2023）09-004-0000-00

doi：10.19734/j.issn.1001-3695.2023.02.0029

Efficient asynchronous Byzantine fault tolerance algorithm for blockchain

Wang Yaoqi， Liu Yang， Li Xiangyang， Liu Xinlei， Cao Haohao

（College of Information Science & Engineering， Henan University of Technology， Zhengzhou 450001， China）

Abstract：To address the limitations of existing asynchronous consensus algorithms， such as high communication overhead during multiple rounds and random selections due to the lack of reputation mechanism in random sampling， this paper proposed an efficient asynchronous Byzantine fault-tolerant algorithm called PenguinBFT. Firstly， this paper broadcasted transactions directly during transaction broadcasting to significantly reduce consensus communication overhead. Secondly， this paper introduced a node reputation evaluation mechanism to select a block generator from a relatively stable node set， which reduced the number of random selections required. Finally， this paper partitioned network nodes and different nodes access different partitions for transaction recovery when necessary， reducing communication overhead and improving transaction recovery efficiency. Experimental results demonstrate that when the number of nodes exceeds 64， the PenguinBFT algorithm shows more than 50% improvement in communication overhead， throughput， and transaction confirmation delay when compared to the HoneyBadgerBFT， DumboBFT， and DispersedLedger algorithms.

Key words：blockchain; asynchronous Byzantine fault tolerance algorithm; transmission efficiency; reputation model; partition

0 引言

2008年，中本聰首次提出了比特幣［1］，開啟了人們理解分布式系統的新篇章。比特幣底層的區塊鏈技術具有不可竄改性等優點，近年來受到了工業界和產業界的廣泛關注。經典的拜占庭容錯算法因具有較高的共識效率、確定一致性的特性而受到聯盟鏈系統的青睞。

經典的拜占庭容錯算法可以根據系統中有無領導者分為基于領導者的部分同步拜占庭容錯算法［2～5和無領導者的異步拜占庭容錯算法［6～10兩類。

到目前為止，研究者們為了規避FLP不可能定理［11］提出了不同種類的異步拜占庭容錯算法：a）弱化一致性保證，通過有向無環圖（directed acyclic graph，DAG）結構僅保證最終一致性。b）采用隨機化的異步二元共識協議規避FLP不可能定理。

在基于DAG結構的異步拜占庭容錯算法的研究中，Baird［12］提出了Hashgraph算法。Hashgraph把經典的拜占庭容錯算法應用在DAG上，采用虛擬投票的方式對DAG內的區塊順序達成一致。周藝華等人［6］提出了基于信譽度的Hashgraph共識算法，解決了Hashgraph中共識過程復雜、缺乏有效監督機制等問題，縮短了交易完成確認時間。Keidar等人［13］提出了DAG-Rider，節點不需要額外的投票協議就可以從DAG中選擇一條路徑進行交易的排序。

基于DAG結構的異步拜占庭容錯算法僅保證最終一致性，從而不需要隨機化的算法就可以規避FLP不可能定理。但是Gao等人［14］指出基于DAG結構的異步拜占庭容錯算法可能會面臨內存占用較高的問題，并且根據Li等人［15］的研究結果，基于DAG的共識算法中存在交易沖突的問題。因此在聯盟鏈系統中較少采用基于DAG結構的異步拜占庭容錯算法。

在基于鏈式結構的異步拜占庭容錯算法的研究中，Ben-Or［16］提出了一種基于隨機化的異步二元共識算法來規避 FLP 不可能定理。異步拜占庭二元共識算法采用局部拋硬幣的方式來協調所有節點的行為，能在有限步驟內讓所有誠實節點達成一致。Cachin等人［17］采用門限簽名方案設計出一種僅需常數輪即可終止的異步拜占庭容錯算法。Mostéfaoui等人［18］提出了一種基于公有幣的異步二元共識算法，該算法的期望運行輪數為4。HoneyBadgerBFT［19］是第一個實用的異步拜占庭容錯算法，它采用可靠廣播協議（reliable broadcast， RBC）進行交易，并使用異步二元共識協議（asynchronous binary agreement， ABA）決定交易是否提交。郭兵勇等人［8］提出了“先共識交易哈希，后請求缺失交易”的方式減少了節點間不必要的消息傳輸，實現了比HoneyBadgerBFT更高的共識效率。Duan等人提出了BEAT［20］，根據不同的應用場景對HoneyBadgerBFT作出了不同程度的優化。Yang等人［21］提出了DispersedLedger，采用先共識“微塊”后同步完整區塊的方式使排序與區塊廣播能夠并行地運行。DumboBFT［22］發現對每個節點Pi所提議的交易txi都要運行一次ABA協議來決定是否提交太過耗時。為了降低ABA協議的運行次數，DumboBFT讓每個節點Pi提出一個交易子集TXsi，再使用Cachin等人［23］提出的多值拜占庭容錯協議（multi-valued validated Byzantine agreement， MVBA）從所有節點提出的交易子集中選擇一個進行提交，將ABA協議的運行次數降為了常數級。

鏈式結構的異步拜占庭容錯算法［8，19～21］通常會采用基于糾刪碼方案的可靠廣播協議進行交易的提案，而經過糾刪碼處理后的數據塊會包含額外的冗余數據，從而導致較高的通信開銷。根據Cachin等人［24］的研究結果，若讓每個節點收到|v|大小的數據，那么基于糾刪碼方案的可靠廣播協議產生的通信開銷為（n2/n-2f）|v|。而在多值拜占庭共識協議［23］中缺乏信譽評估機制不能有效地評估節點的網絡狀態，需要多次抽取出塊者才可以終止。因此，如何減少異步拜占庭容錯算法的通信開銷以及把信譽機制更好地應用于異步拜占庭容錯算法中是一個亟待解決的問題。

針對以上問題，在DumboBFT的基礎上，提出了一種高效的異步拜占庭容錯算法PenguinBFT。本文主要貢獻如下：

a） 針對基于糾刪碼方案的可靠廣播協議造成較高的通信開銷問題，在廣播交易時，不再使用糾刪碼方案對交易進行拆分，從而避免了冗余數據的傳輸，降低了通信開銷。

b） 引入信譽機制對節點網絡狀態進行評估。在DumboBFT中出塊者是隨機抽取的，如果出塊者的網絡環境較差，那么系統中大部分節點可能都沒有收到出塊者的提議。因此，若出塊者的網絡狀態不穩定，那么運行ABA的輸出結果很可能為0。本文引入信譽機制，抽取網絡狀態較好的節點作為出塊者減少隨機抽取次數，從而降低了ABA的運行次數。

c） 對網絡節點進行分區。節點可以在請求缺失交易時并行地訪問不同的節點集合，在提高交易恢復效率的同時也能減少通信開銷。

1 系統模型與定義

1.1 系統模型

本文在n=3f+1的系統中構建異步拜占庭容錯算法。

a）敵手模型。在系統中，敵手最多能夠控制f個拜占庭節點，敵手可以獲取這些拜占庭節點的相關信息。敵手在算法初始化時可以任選f個節點作為拜占庭節點，但在算法開始運行后，敵手不能再腐化誠實節點。

b）異步網絡模型。在系統中，節點之間傳遞的消息可以被敵手任意地延遲，但是這些消息最終會到達相應的節點。

1.2 異步二元共識協議

本文采用異步二元共識協議（asynchronous binary agreement，ABA）協議作為投票協議使所有節點達成一致。ABA協議具有以下特性：

a）Agreement：如果一個誠實節點輸出了b，那么所有誠實節點都會輸出b。

b）Termination：如果所有誠實節點提供相同的輸入b，那么所有誠實節點都輸出b。

c）Validity：如果一個誠實節點輸出了b，那么至少有一個誠實節點將b作為輸入。

2 算法設計

2.1 算法架構

在PenguinBFT中，所有節點都有權提出新的交易，因此可以充分釋放系統的并發執行能力。PenguinBFT可以分為四個階段：交易廣播階段、交易順序廣播階段、出塊者抽簽階段以及獲取缺失交易階段，如圖1所示。

a）交易廣播階段。在廣播交易時，直接廣播交易原文，直接廣播交易原文的好處有以下兩點：（a）節點收到交易原文后可以直接驗證交易，若采用糾刪碼方案，節點只有從不同的數據塊中還原出交易原文后才可以進行交易的驗證（如果交易的提議者是拜占庭節點，不能及時地判斷節點是否作惡）;（b）降低了通信開銷，若采用糾刪碼方案將交易拆分為不同的數據塊，則這些數據塊中會包含額外的冗余信息。

在交易廣播階段，每個節點都可以廣播交易來充分釋放系統的并發執行能力。PenguinBFT采用了異構的交易執行模式，因此還需要額外的機制讓所有節點提交同構的區塊。

b）交易順序廣播階段。在交易順序廣播階段，每個節點需要把自己執行的交易順序告知給所有節點。在廣播交易順序向量時，不再廣播交易原文而是廣播交易的元數據（交易的哈希值以及交易的門限簽名）來避免不必要的通信開銷。在交易順序廣播階段結束后，節點可以獲知其他節點收到的交易順序。之后需要從所有節點中選一個出塊者，系統將會按照出塊者提議的交易順序進行區塊的構建使得每個節點都可以提交同構的區塊。

c）出塊者抽簽階段。在出塊者抽簽階段，引入信譽機制評估每個節點的網絡狀態。在抽取出塊者時，從網絡狀態較為穩定的節點集合中進行抽取。在出塊者被抽中后，執行ABA協議讓所有節點投票決定出塊者是否有出塊權。若出塊者有出塊權，那么所有節點都按照出塊者提出的的交易順序向量進行區塊的構建；否則，選取新的出塊者進行下一輪的投票。

d）請求缺失交易階段。在出塊者抽簽階段獲取到出塊者的交易順序向量后，每個節點還需要檢查自己是否收到了交易順序向量內的所有交易。如果節點沒有收到交易順序向量內的所有交易，那么節點需要訪問不同的分區來獲取缺失交易。

算法1 PenguinBFT算法（Pi代表節點，r是當前輪次）

局部變量初始化：

SC←{P1：0，P2：0，…，Pn：0} // 出塊成功次數

SR←{P1：［］，P2：［］，…，Pn：［］}// 出塊成功輪次

FC←{P1：0，P2：0，…，Pn：0}// 出塊失敗次數

FR←{P1：［］，P2：［］，…，Pn：［］}// 出塊失敗輪次

Vi={（htx1，σtx1），（htx2，σtx2），…，（htxn，σtxn）}/*Pi執行的交易順序存儲在Vi中，htxj是交易txj的哈希值，σtxj是交易txj的門限簽名*/

Len←0

Di←{}

upon receiving transaction txi from the client do

broadcast txi to all nodes

upon delivery of （htxj，σtxj） from Pj

Vi［Pj］ = （htxj，σtxj） //存儲合法的交易簽名

Len=Len+1

upon Len=n-f do

broadcast Vi to all nodes

upon delivery Vj from Pj do

Di=Di∪ Vj

upon |Di| =n-f do

participate producer lottery stage

upon delivery Vp from producer lottery stage do

SC［Pp］=SC［Pp］+1

SR［Pp］=append（SC［Pp］，r）

if Pi receives all the transactions in Vp then

commit

else

for each （htxj，σtxj）∈Vp do

if Pi has not received txj do

retrieve txj from the partition in which Pi is located

2.2 具體內容

2.2.1 交易廣播階段

在廣播交易時為了防止惡意節點給不同的節點發送不同的交易，交易的提議者Pi只有在得到至少2f+1來自不同節點的投票后才可以證明自己給所有節點發送的交易是一致的。

最初，提議者Pi在收到附近客戶端的交易txi后，會將txi廣播給系統內的所有節點。接收者Pj收到txi后會驗證txi的合法性。如果txi合法，Pj會根據txi生成部分簽名ρ〈txi，j〉并將ρ〈txi，j〉發送給Pi。Pi在收到2f+1個合法的部分簽名ρ〈txi，j〉后會計算出門限簽名σtxi并將σtxi廣播給所有節點。

在PenguinBFT中，每個節點都可以提出出塊請求，因此每個節點都要經歷上述的“廣播交易—獲取投票—廣播投票結果”的過程。

為了更清晰地描述交易廣播階段，引入了一個新的表達方式交易廣播實例。每個交易廣播實例TBi的輸入為交易txi，輸出為交易的哈希值htxi和交易的門限簽名σtxi。每個節點Pi通過TBi來廣播交易。如果節點Pj得到了TBi的輸出，代表節點Pi給所有節點發送的交易是一致的。交易廣播實例如算法2所示。

算法2 交易廣播實例（Pi代表節點，Ps是發送者）

輸入：txs。

輸出：htxs，σtxs。

局部變量初始化：

Shares←{} // 存儲部分簽名

// 發送者Ps執行的協議

upon receiving txs from the client do

broadcast txi to all nodes

wait until |Shares|=2f+1

σtxs←Combine2f+1（Shares） // 計算門限簽名

multicast（Done， htxs，σtxs）

upon receiving （Ack， htxs，ρ〈txs，j〉） from the Pj do

if ShareVerify2f+1（htxs， ρ〈txs，j〉）=true then // 驗證部分簽名

Shares←Shares ∪ρ〈txs，j〉

// Pi執行的協議

upon receiving txs from the sender do

if txs is valid then

ρ〈txs，i〉←SigShare（htxs，ski） // 生成部分簽名

send（Ack， htxs， ρ〈txs，i〉） to Ps

upon receiving （Done， htxs，σtxs） from the Ps do

if Verify （htxs，σtxs）=true then // 驗證門限簽名

return （htxs，σtxs）

2.2.2 交易順序廣播階段

在PenguinBFT中采用了異構的交易執行模式，每個節點執行的交易順序是不同的，因此每個節點還需要把自己的交易執行順序告知其他所有節點。

在節點Pi得到了n-f個交易廣播實例的輸出后，Pi會根據交易廣播實例的輸出順序把交易的哈希值和交易的門限簽名放入交易順序向量Vi里廣播給所有節點。接收者Pj收到Vi后會對Vi內所有的門限簽名進行驗證，如果所有的門限簽名都合法，Pj會根據生成部分簽名ρ〈Vi，j〉并將ρ〈Vi，j〉發送給Pi。Pi在收到2f+1個合法的部分簽名ρ〈Vi，j〉后會計算出門限簽名σVi并將σVi廣播給所有節點。

為了更清晰地描述交易順序廣播階段，引入新的表達方式“向量廣播實例”。每個向量廣播實例VBi的輸入為交易順序向量Vi，輸出為交易順序向量的門限簽名σVi。每個節點Pi通過VBi來廣播交易。如果節點Pj得到了VBi的輸出，代表節點Pi給所有節點廣播的向量是一致的。向量廣播實例如算法3所示。

算法3 向量廣播實例（Pi代表節點，Ps是發送者）

輸入：txs。

輸出：hVs，σVs。

局部變量初始化：

Shares←{} // 存儲部分簽名

producedure EX-VAL（V） // 驗證V內所有的門限簽名

if |V|

return false

for each （htxj，σtxj）∈V do

if Pi delivered σtxj then

continue

else if ShareVerify2f+1（htxj，σtxj）=false then

return false

return true

// 發送者Ps執行的協議

upon delivering n-f TB instances do

multicast（Send， hVs，Vs）

wait until |Shares|=2f+1

σVs←Combine2f+1（Shares） // 計算門限簽名

multicast（Done， hVs， σVs）

upon receiving （Ack， hVs， ρ〈Vs，j〉） from the Pj do

if ShareVerify2f+1（hVs， ρ〈Vs，j〉）=true then // 驗證部分簽名

Shares←Shares∪ρ〈Vs，j〉

// Pi執行的協議

upon receiving txs from the sender do

if txs is valid then

ρ〈Vs，i〉←SigShare（hVs，ski） // 生成部分簽名

send（Ack， htxs， ρ〈Vs，i〉） to Ps

upon receiving （Done， hVs，σVs） from the Ps do

if Verify （hVs，σVs）=true then // 驗證門限簽名

return （hVs，σVs）

2.2.3 出塊者抽簽階段

在出塊者抽簽階段，需要讓所有節點提交同構的區塊來維持系統的一致性。PenguinBFT需要以下兩個步驟讓所有節點提交同構的區塊：a）隨機選取一個出塊者；b）所有節點參與投票決定是否按照出塊者執行的交易順序進行區塊的構建。

為了選取隨機的出塊者，將門限簽名與SHA256算法結合。每個節點在參與出塊者選取時都會廣播部分簽名coinshare。節點收到f+1個合法的部分簽名coinshare后可以計算出總簽名coinsig。得益于門限簽名的特性，即使每個節點收到的部分簽名不同，每個節點仍能計算出相同的總簽名。為了保證隨機性，對coinsig進行SHA256運算取余后可以得到出塊者Pp。

算法4 出塊者抽簽階段

for each k∈{1，2，…，n}

Pp←Lottery〈r，k〉

if PpSN //SN是網絡狀態較為穩定的節點集合

Pp←Pp′//Pp′是從網絡狀態不穩定的節點集合中隨機選擇的

if Pi delivers VBp then

input 1 to ABA〈r，k〉

else

input 0 to ABA〈r，k〉

Pp←ABA〈r，k〉

if d=1 then

if Pi delivers VBp then

multicast（Final， Vp， σVp）

else if Pi receives Vp then

multicast（Final， Vp，⊥）

else if d=0 then

FC［Pp］=FC［Pp］+1

FR［Pp］=append（FC［Pp］， r）

upon delivering Vp amng 2f+1 Final messages do

return Vp

由于選用了隨機化的方式進行出塊者選取，不能保證每次都能抽到網絡情況較為穩定的節點（出塊者有可能掉線或者網絡波動較大）。PenguinBFT引入了信譽機制根據歷史出塊記錄對每個節點的信譽進行量化并選取網絡狀態較好的節點作為出塊者降低了抽取次數。

節點的可信度分為成功記錄CLHj和失敗記錄CLFj，采用如下公式進行計算。

CLHj=SCTRCLFj=FCTR（1）

在CLHj中SC表示出塊成功的次數，TR表示總的運行輪次。在CLFj中FC表示出塊失敗的次數。

節點的網絡狀態并不是一直穩定的，其網絡狀態可能隨時間的變化而發生波動。與可信度類似，信譽值也分為成功信用CVHj和失敗信用CVFj，采用下式進行計算。

CVHJ=∑SRt=1F（Tc－THtj）

CVFJ=∑FRt=1F（Tc－TFtj）（2）

在CVHj中Tc表示當前輪次，THtj表示節點第tth次成功出塊的輪次，SR 是一個集合記錄了節點成功出塊的所有輪次。F（x）是一個調整頻率和時效的權重函數， 一個經典形式可以為F（x）=e-x/m， 其中M是超參數。CVFj的解釋類比上式。

最后，可以計算出節點的信譽值。

Vj=CLHjCVHj+CLFjCVFf（3）

在隨機選取出出塊者Pp后，首先檢查Pp是否在網絡狀態較為穩定的節點集合中，如果Pp在在網絡狀態較為穩定的集合中，那么直接運行ABA協議來判定Pp的出塊權。否則，則根據在環型網絡拓撲結構的位置找距離其最近且網絡狀態較為穩定的節點作為出塊者。

如果ABA協議的輸出為1，那么所有節點都會廣播Final消息（Final消息包含了Vp）來保證所有的誠實節點都能得到Vp。出塊者抽簽階段如算法4所示。

2.2.4 獲取缺失交易

在交易的順序確定后，有的節點因為網絡延遲較高的原因還沒收到相應的交易。當交易順序確定后，節點Pi需要檢查自己是否收到了所有交易，如果Pi缺失了部分交易，那么Pi需要尋求其他節點的幫助，讓其他節點幫助其恢復缺失的交易。

如果節點Pi詢問所有節點，那么會對系統造成額外的開銷，影響共識效率。若Pi僅從一個節點Pj處請求幫助，那么Pj可能會返回虛假交易不再滿足拜占庭容錯。因此本文構建了分區機制，每個分區內的節點數為2f+1，節點可以并行地訪問不同的分區來恢復缺失交易，如圖2所示。節點的地理位置不同會造成不同的通信時延，因此每個節點可以選取距離自己較近的2f+1個節點作為一個分區。在獲取缺失交易txj時，Pi先在自身所處的分區Si內找到收到txj的節點Pj，之后Pi自可以從Pj處獲取txj。Pj發向Pi的txj可能會被無限期地延遲，但是根據異步網絡假設，txj最終會到達Pi。

3 算法分析

引理1 如果一個誠實節點輸出了v，另一個誠實節點輸出了v′，則v= v′。

證明 假設v和v′不同。如果一個誠實節點輸出了v，則v得到了誠實節點集合S1 （|S1|≥2f+1）的背書。同理，如果另一個誠實節點輸出了交易v′，則得到了誠實節點集合S2 （|S2|≥2f+1）的背書。系統中只有2f+1個誠實節點，則S1與S2存在交集（有一個誠實節點同時把票投給了v和v′）。由于誠實節點只能投一次票，則假設不成立。

引理2 安全性。如果一個誠實節點輸出了交易順序向量Vp，那么所有誠實節點都會輸出Vp。

證明 如果系統中存在一個誠實節點按照Vp進行交易的排序與提交，那么可以推出ABA的協議輸出為1。根據ABA協議的Validity特性，至少有一個誠實節點輸出了出塊者Pp所提議的向量廣播實例VBP，這表明至少有f+1個誠實節點收到了Vp。根據ABA協議的Agreement特性，如果一個誠實節點輸出了1，那么所有誠實節點都會輸出1。此時系統中至少有f+1個誠實節點會廣播Final消息，由于敵手最多只能控制f個節點，因此，所有的節點都能收到Vp并輸并出Vp。

引理3 如果一個誠實節點輸出了交易順序向量Vp，那么該誠實節點能得到Vp內的所有交易。

證明 如果一個誠實節點Pi輸出了Vp，那么其可能面臨以下兩種情況：

a）Pi收到了Vp內的所有交易，那么Pi可以直接進行區塊的構建。

b）Pi沒有收到Vp內的所有交易，那么Pi可以尋求其他節點的幫助。

假對于Vp內的每一個σtxj ≠ ⊥，都至少有f+1個誠實節點到了txj。假設Pi沒有收到txj，那么Pi需要尋求2f+1個節點的幫助。在這2f+1個節點中包含了一個誠實節點集合S1（|S1|≥f+1）。已知系統內有|S2|≥f+1個誠實節點收到了txj。由于|S1|+|S2|≥2f+2>2f+1，那么至少有一個誠實節點即收到了txj又把txj返回給了Pi，因此Pi可以收到txj。

對于其他的缺失交易也可以通過上述的描述獲取，所以Pi能得到Vp內的所有交易。

引理4 全局有序。如果一個誠實節點輸出的交易順序是tx1，tx2，…，txj，另一個誠實節點輸出的交易順序是tx′1， tx′2，…， tx′j，對于i≤j，均有txi=txj。

證明 根據引理2，所有節點在出塊者抽簽階段都會輸出一樣的交易順序向量Vp。對于Vp所包含的每筆交易，根據引理3，所有誠實節點都會輸出同樣的交易。由于Vp內包含的交易是有序的，因此所有節點都能得到一致的交易順序。

引理5 活性。如果有n-f個誠實節點得到了相同的交易tx，則tx最終會被輸出。

證明 由于系統中有n-f個誠實節點得到了輸入，所以所有誠實節點都會在交易廣播階段輸出足夠多的交易廣播實例后進入交易順序廣播階段。所有誠實節點都會使用向量廣播實例廣播自己在交易廣播階段輸出的交易。所有誠實節點都會在輸出n－f個向量廣播實例后進入出塊者抽取階段。系統中有≥f+1個誠實節點滿足門限簽名的閾值，因此系統能成功隨機抽取出一名出塊者。根據引理2，所有的誠實節點都會輸出Vp。對于Vp內的每一個門限簽名，根據引理3節點能獲取到相應的交易，因此tx最終會被輸出。

4 實驗結果與分析

本文在兩臺本地服務器中運行HoneyBadgerBFT、DumboBFT、DispersedLedger和PenguinBFT算法。服務器的型號為戴爾R740，擁有40個CPU核心（CPU型號為Intel Xeon Gold 5218，主頻為2.10 GHz）和128 GB的運行內存。在兩臺R740服務器上使用VirtualBox軟件創建64個虛擬機來充當節點。每臺虛擬機的配置為1個CPU核心和2GB的運行內存，操作系統環境為Ubuntu18.04。算法均采用Python3.6實現（https：//github.com/yylluu/dumbo）。

4.1 通信開銷對比

在測量通信開銷時，將每個節點提議的交易集合大小固定在4 096筆。每筆交易大小為250 Byte。

測量發現HoneyBadgerBFT、DumboBFT和DispersedLedger的通信開銷基本一樣。PenguinBFT在廣播交易時并沒有使用糾刪碼方案對交易進行拆分，避免了冗余數據的傳輸。其次，在請求缺失交易時，PenguinBFT構建了分區機制使得節點尋求2f+1個節點的幫助就可以恢復缺失交易減少了交易恢復的通信開銷。因此PenguinBFT的通信開銷僅為HoneyBadgerBFT、DumboBFT和DispersedLedger的一半，如圖3所示。

4.2 抽簽次數對比

在進行節點的信譽評估測試時，令n=7，運行5 000次PenguinBFT算法，每隔500次進行一次節點信譽的計算。同時，每隔500次隨機選擇兩個節點作為故障節點觀察其信譽是否會隨之變化。從圖4中可以看出，當節點掉線時，其信譽也會隨之變化（當節點掉線時，其信譽會降到0以下）。因此，信譽模型可以有效地評估節點的網絡狀態。

在PenguinBFT中采用的是“先隨機選取出塊者，后判斷出塊者網絡狀況”的思路避免了出塊權壟斷問題。即使某個節點具有很高的信譽，但其在后續共識過程中并不一定還被隨機選為出塊者。

在測試抽簽次數時分別將DumboBFT和PenguinBFT算法運行一萬次來比較兩種算法的抽簽次數。由于PenguinBFT算法采用了信譽模型可以有效地評估節點的網絡狀態，并選用網絡狀態較為穩定的節點作為出塊者，可以有效地降低出塊者抽取次數，所以抽簽次數相較于DumboBFT減少了24%，如圖5所示。

4.3 吞吐量對比

測量吞吐量時，通過改變系統的交易量大小來比較不同算法在不同節點規模下的吞吐量。在測試時，每筆交易的大小為250 Byte。由于PenguinBFT的通信開銷為HoneyBadgerBFT、 DumboBFT和DispersedLedger的一半，當HoneyBadgerBFT、 DumboBFT和DispersedLedger遇到吞吐量瓶頸時，PenguinBFT的吞吐量還能繼續增大。如圖6所示，當節點規模達到64時，PenguinBFT的吞吐量相較于HoneyBadgerBFT提升了290%，相較于DumboBFT提升了50%，相較于DispersedLedger提升了86%。

4.4 延遲對比

在衡量交易延遲時，以節點發起交易的時間作為起始時間，以系統中n-f個節點提交交易的時間作為結束時間。在測量時延時，每個節點提出大小為1 MB的交易。

如圖7中所示，PenguinBFT具有更低的交易確認延遲，主要原因是PenguinBFT在降低通信開銷的同時也減少了抽簽次數。當節點規模達到64時，PenguinBFT的時延為HoneyBadgerBFT的18%，DumboBFT的50%，DispersedLedger的24%。

5 結束語

本文提出了一種高效的異步拜占庭容錯算法PenguinBFT。通過實驗發現，PenguinBFT的通信開銷為HoneyBadgerBFT和DumboBFT的一半。當節點規模達到64時，PenguinBFT的吞吐量相較于 DumboBFT提升了50%，相較于HoneyBadgerBFT提升了290%，相較于DispersedLedger提升了86%。PenguinBFT的交易確認時延僅為DumboBFT的50%，HoneyBadgerBFT的18%，DispersedLedger的24%。提出的異步共識算法允許每個節點都提出交易請求，具有并發特征，通過直接分發交易從而顯著降低算法通信開銷，引入的節點信譽機制能夠大大減少現有異步共識算法中ABA協議的運行次數，分區機制可以使節點并行地訪問不同節點集合來獲取缺失交易從而提高了交易恢復效率。盡管本文降低了DumboBFT的通信開銷與抽簽次數，但本文仍使用ABA協議規避FLP不可能定理，當節點規模較大或者網絡延遲較高時，ABA協議需要很長時間才能終止。未來的工作將考慮如何在移除ABA協議的同時規避FLP不可能定理使異步拜占庭容錯算法更好地應用于區塊鏈系統中。

參考文獻：

[1]Nakamoto S.Bitcoin：a peer-to-peer electronic cash system［EB/OL］.（2008）.https：//bitcoin.org/en/bitcoin-paper.

［2]徐治理，封化民，劉飚.一種基于信用的改進PBFT高效共識機制［J］.計算機應用研究，2019，36（9）：2788-2791.（Xu Zhili，Feng Huam-in，Liu Biao.Improved PBFT efficient consensus mechanism based on credit［J］.Application Research of Computers，2019，36（9）：2788-2791.）

［3]高娜，周創明，楊春曉，等.基于網絡自聚類的PBFT算法改進［J］.計算機應用研究，2021，38（11）：3236-3242.（Gao Na，Zhou Chuangming，Yang Chunxiao，et al.Improved PBFT algorithm based on network self clustering［J］.Application Research of Computers，2021，38（11）：3236-3242.）

［4]李淑芝，鄒懿杰，鄧小鴻，等.RB-Raft：一種抗拜占庭節點的Raft共識算法［J］.計算機應用研究，2022，39（9）：2591-2596.（Li Shuzhi，Zou Yijie，Deng Xiaohong，et al.RB-Raft：Raft consensus algorithm for anti-Byzantine nodes［J］.Application Research of Computers，2022，39（9）：2591-2596.）

［5]陳佳偉，冼祥斌，楊振國，等.結合BLS聚合簽名改進實用拜占庭容錯共識算法［J］.計算機應用研究，2021，38（7）：1952-1955，1962.（Chen Jiawei，Xian Xiangbin，Yang Zhenguo，et al.Improved practical Byzantine fault tolerant consensus algorithm combined with BLS aggregating signature［J］.Application Research of Computers，2021，38（7）：1952-1955，1962.）

［6]周藝華，賈立圓，賈玉欣，等.基于信譽度的Hashgraph共識算法［J］.計算機應用研究，2021，38（9）：2590-2593，2599.（Zhou Yihua，Jia Liyuan，Jia Yuxin，et al.Hashgraph consensus algorithm based on credit［J］.Application Research of Computers，2021，38（9）：2590-2593，2599.）

［7]潘吉飛，黃德才.基于跳躍Hash和異步共識組的區塊鏈動態分片模型［J］.計算機科學，2020，47（3）：273-280.（Pan Jifei，Huang Decai.Blockchain dynamic sharding model based on jump hash and asynchronous consensus group［J］.Computer Science，2020，47（3）：273-280.）

［8]郭兵勇，李新宇.一個高傳輸效率的多值拜占庭共識方案［J］.密碼學報，2018，5（5）：516-528.（Guo Bingyong，Li Xinyu.Multi-valued Byzantine consensus scheme with high transmission efficiency［J］.Journal of Cryptologic Research，2018，5（5）：516-528.）

［9]Abraham I，Malkhi D，Spiegelman A.Asymptotically optimal validated asynchronous Byzantine agreement［C］//Proc of the 38th ACM Symposium on Principles of Distributed Computing.New York：ACM Press，2019：337-346.

［10]Liu Chao，Duan Sisi，Zhang Haibin.Epic：efficient asynchronous BFT with adaptive security［C］//Proc of the 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks.Piscataway，NJ：IEEE Press，2020：437-451.

［11]Fischer M J，Lynch N A，Paterson M S.Impossibility of distributed consensus with one faulty process［J］.Journal of the ACM，1985，32（2）：374-382.

［12]Baird L.The swirlds hashgraph consensus algorithm：fair，fast，Byzantine fault tolerance，SWIRLDS-TR-2016-01［R］.［S.l.］：Swirlds，2016.

［13]Keidar I，Kokoris-Kogias E，Naor O，et al.All you need is DAG［C］//Proc of the 40th ACM Symposium on Principles of Distributed Computing.New York：ACM Press，2021：165-175.

［14]Gao Yingzi，Lu Yuan，Lu Zhenliang，et al.Dumbo-NG：fast asynchronous BFT consensus with throughput-oblivious latency［C］//Proc of the 29th ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2022：1187-1201.

［15]Li Chenxing ，Li Peilun ，Zhou Dong ，et al.A decentralized blockchain with high throughput and fast confirmation［C］//Proc of the 31st USENIX Annual Technical Conference.［S.l.］：USENIX Association，2020：515-528.

［16]Ben-Or M.Another advantage of free choice（extended abstract） completely asynchronous agreement protocols［C］//Proc of the 2nd annual ACM Symposium on Principles of Distributed Computing.New York：ACM Press，1983：27-30.

［17]Cachin C，Kursawe K，Shoup V.Random oracles in constantinople：practical asynchronous Byzantine agreement using cryptography［J］.Journal of Cryptology，2005，18（3）：219-246.

［18]Mostéfaoui A，Moumen H，Raynal M.Signature-free asynchronous Byzantine consensus with t

［19]Miller A，Xia Yu ，Croman K，et al.The honey badger of BFT protocols［C］//Proc of the 23rd ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2016：31-42.

［20]Duan S，Reiter M K，Zhang H.BEAT：asynchronous BFT made practical［C］//Proc of the 25th ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2018：2028-2041.

［21]Yang Lei，Park S J，Alizadeh M，et al.DispersedLedger：high-throughput Byzantine consensus on variable bandwidth networks［C］//Proc of the 19th USENIX Symposium on Networked Systems Design and Implementation.［S.l.］：USENIX Association，2022：493-512.

［22]Guo Bingyong，Lu Zhenliang ，Tang Qiang，et al.Dumbo：faster asynchronous BFT protocols［C］//Proc of the 27th ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2020：803-818.

［23]Cachin C，Kursawe K，Petzold F，et al.Secure and efficient asynchronous broadcast protocols［C］//Advances in Cryptology—CRYPTO 2001：Proc of the 21st Annual International Cryptology Conference.Berlin：Springer，2001：524-541.

［24]Cachin C，Tessaro S.Asynchronous verifiable information dispersal［C］//Proc of the 24th IEEE Symposium on Reliable Distributed Systems.Piscataway，NJ：IEEE Press，2005：191-201.

收稿日期：2023-02-22；

修回日期：2023-04-10

基金項目：河南省重大科技專項資助項目（201300210200，201300210100）；鄭州市協同創新重點專項資助項目（21ZZXTCX07）；河南省高等學校重點科研項目計劃基礎研究專項資助項目（23ZX017）；河南省重點科技攻關項目（232102211082）

作者簡介：王耀啟（1998-），男，河南駐馬店人，碩士，主要研究方向為區塊鏈；劉揚（1978-），女（通信作者），河南鄭州人，教授，博導，博士，主要研究方向為分布式系統、區塊鏈（liu_yang@haut.edu.cn）；李向陽（1998-），女，河南安陽人，碩士，主要研究方向為區塊鏈；劉鑫磊（1997-），男，河南平頂山人，碩士，主要研究方向為區塊鏈；曹浩浩（1997-），男，河南南陽人，碩士，主要研究方向為區塊鏈.