适用于区块链的高效异步拜占庭容错算法

王耀启 刘扬 李向阳 刘鑫磊 曹浩浩

摘 要：针对现有异步共识算法存在的多轮次通信开销大、随机抽签算法中缺乏信誉机制导致了较多的抽取次数等不足，提出了一种高效的异步拜占庭容错算法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-），男，河南南阳人，硕士，主要研究方向为区块链.