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

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

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

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

中圖分類號：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］，開啟了人們理解分布式系統(tǒng)的新篇章。比特幣底層的區(qū)塊鏈技術具有不可竄改性等優(yōu)點，近年來受到了工業(yè)界和產(chǎn)業(yè)界的廣泛關注。經(jīng)典的拜占庭容錯算法因具有較高的共識效率、確定一致性的特性而受到聯(lián)盟鏈系統(tǒng)的青睞。

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

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

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

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

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

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

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

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

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

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

1 系統(tǒng)模型與定義

1.1 系統(tǒng)模型

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

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

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

1.2 異步二元共識協(xié)議

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

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

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

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

2 算法設計

2.1 算法架構

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

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

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

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

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

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

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

局部變量初始化：

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

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

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

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

Vi={（htx1，σtx1），（htx2，σtx2），…，（htxn，σtxn）}/*Pi執(zhí)行的交易順序存儲在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 具體內(nèi)容

2.2.1 交易廣播階段

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

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

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

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

算法2 交易廣播實例（Pi代表節(jié)點，Ps是發(fā)送者）

輸入：txs。

輸出：htxs，σtxs。

局部變量初始化：

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

// 發(fā)送者Ps執(zhí)行的協(xié)議

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執(zhí)行的協(xié)議

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中采用了異構的交易執(zhí)行模式，每個節(jié)點執(zhí)行的交易順序是不同的，因此每個節(jié)點還需要把自己的交易執(zhí)行順序告知其他所有節(jié)點。

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

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

算法3 向量廣播實例（Pi代表節(jié)點，Ps是發(fā)送者）

輸入：txs。

輸出：hVs，σVs。

局部變量初始化：

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

producedure EX-VAL（V） // 驗證V內(nèi)所有的門限簽名

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

// 發(fā)送者Ps執(zhí)行的協(xié)議

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執(zhí)行的協(xié)議

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 出塊者抽簽階段

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

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

算法4 出塊者抽簽階段

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

Pp←Lottery〈r，k〉

if PpSN //SN是網(wǎng)絡狀態(tài)較為穩(wěn)定的節(jié)點集合

Pp←Pp′//Pp′是從網(wǎng)絡狀態(tài)不穩(wěn)定的節(jié)點集合中隨機選擇的

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

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

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

CLHj=SCTRCLFj=FCTR（1）

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

節(jié)點的網(wǎng)絡狀態(tài)并不是一直穩(wěn)定的，其網(wǎng)絡狀態(tài)可能隨時間的變化而發(fā)生波動。與可信度類似，信譽值也分為成功信用CVHj和失敗信用CVFj，采用下式進行計算。

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

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

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

最后，可以計算出節(jié)點的信譽值。

Vj=CLHjCVHj+CLFjCVFf（3）

在隨機選取出出塊者Pp后，首先檢查Pp是否在網(wǎng)絡狀態(tài)較為穩(wěn)定的節(jié)點集合中，如果Pp在在網(wǎng)絡狀態(tài)較為穩(wěn)定的集合中，那么直接運行ABA協(xié)議來判定Pp的出塊權。否則，則根據(jù)在環(huán)型網(wǎng)絡拓撲結構的位置找距離其最近且網(wǎng)絡狀態(tài)較為穩(wěn)定的節(jié)點作為出塊者。

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

2.2.4 獲取缺失交易

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

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

3 算法分析

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

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

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

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

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

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

a）Pi收到了Vp內(nèi)的所有交易，那么Pi可以直接進行區(qū)塊的構建。

b）Pi沒有收到Vp內(nèi)的所有交易，那么Pi可以尋求其他節(jié)點的幫助。

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

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

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

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

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

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

4 實驗結果與分析

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

4.1 通信開銷對比

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

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

4.2 抽簽次數(shù)對比

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

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

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

4.3 吞吐量對比

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

4.4 延遲對比

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

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

5 結束語

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

參考文獻：

[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，F(xiàn)eng Huam-in，Liu Biao.Improved PBFT efficient consensus mechanism based on credit［J］.Application Research of Computers，2019，36（9）：2788-2791.）

［3]高娜，周創(chuàng)明，楊春曉，等.基于網(wǎng)絡自聚類的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：一種抗拜占庭節(jié)點的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和異步共識組的區(qū)塊鏈動態(tài)分片模型［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）；鄭州市協(xié)同創(chuàng)新重點專項資助項目（21ZZXTCX07）；河南省高等學校重點科研項目計劃基礎研究專項資助項目（23ZX017）；河南省重點科技攻關項目（232102211082）

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