高并行化的异步拜占庭容错协议

A Highly Parallelized Asynchronous Byzantine Fault Tolerance Protocol

摘要

异步拜占庭容错协议由于其快速可靠的优点，被广泛用于不稳定甚至对抗的区块链网络中实现对交易的共识。当前最先进的解决方案主要基于异步公共子集方法，通过分发和一致两个阶段达成共识。然而，这些方案通常存在大量通信开销，并且缺乏处理公共子集聚合的形式化设计。为了解决这些问题，提出一种高并行化的异步拜占庭容错协议，采用三阶段并行异步公共子集框架，包括分发、一致和重构阶段，提高了吞吐量并减少了延迟。在该框架中，通过在分发阶段引入纠删码和在一致阶段使用向量结构，有效降低了通信开销。此外，还提出了一种公共子集聚合机制，用于高效聚合已达成共识的公共子集。实验结果显示，本文方案相比其他异步拜占庭容错协议，交易吞吐量提高了1.2至3.5倍，交易延迟降低至13%至42%。

Abstract

Asynchronous Byzantine fault tolerance protocols, known for their fast and reliable advantages, are widely used to achieve agreement on transactions in unstable and adversarial blockchain networks. The state-of-the-art solutions mainly adopt the asynchronous common subset approach, which achieves agreement through two phases: dispersion and consensus. However, these solutions often suffer from high communication overhead and a lack of formal design for aggregating common subsets. To address these problems, this paper proposes a highly parallelized asynchronous Byzantine fault tolerance protocol featuring a three-stage asynchronous common subset framework. The framework includes dispersion, agreement, and reconstruction, thereby enhancing throughput and reducing latency. In this framework, the communication overhead is effectively reduced by introducing erasure codes in the dispersion stage and using vector structures in the agreement stage. In addition, this paper proposes a common subset aggregation mechanism for efficiently aggregating subsets that have reached agreement. Experimental results show that, compared with other asynchronous Byzantine fault tolerance protocols, our approach improves transaction throughput by 1.2-3.5 times and reduces transaction latency by 13%-42%.

Graphical abstract

关键词

异步共识协议 / 拜占庭容错 / 异步公共子集 / 区块链

Key words

asynchronous agreement protocol / Byzantine fault tolerance / asynchronous common subset / blockchain

0　 引 言

拜占庭容错(Byzantine Fault Tolerance, BFT)协议旨在确保存在故障或恶意节点（即拜占庭节点）的情况下，多个节点间仍能达成交易一致性^[1]。目前，BFT协议已在Hyperledger Fabric^[2]和Cosmos^[3]等区块链平台中得到广泛应用。与工作量证明(Proof of Work, PoW)^[4]、权益证明(Proof of Stake, PoS)^[5]和委托权益证明(Delegated Proof of Stake, DPoS)^[6]等其他共识协议相比，BFT协议在效率、稳健性和灵活性方面表现优异^[7-8]，能够更快达成共识，适用于处理异常节点行为和多样化的网络环境^[9-10]。

现有的BFT协议根据时间假设可分为三类：同步、部分同步和异步。同步协议^[7，9]假设消息在固定时间内传递，因此能够在可预测的时间内达成共识，但实际网络中延迟和中断的不可预测性限制了其应用。部分同步协议^[8，11]假设存在已知但可变的时间界限，提供了对暂时网络异步的弹性，但在不稳定的网络条件下性能将大幅下降。异步协议^[10，12]则不对时间作任何假设，通过引入随机性决策来应对无限制的网络延迟，更适合实际网络，但实现一致性更具挑战性。弗莱彻-莱维特-帕特森(Fischer Lynch Paterson, FLP)不可能性定理^[13]甚至指出，在存在恶意节点的异步分布式系统中，无法通过确定性协议确保一致性。

目前异步BFT协议主要基于有向无环图(Directed Acyclic Graph，DAG)^[14]和异步公共子集(Asynchronous Common Subset, ACS)^[15]两种方式。基于DAG的异步BFT协议^[14，16-17]通过DAG记录并组织所有节点提交交易，选举领导者节点确定最终交易顺序，从而达成全网共识。但是选举过程涉及复杂的节点竞争和协调机制，这需要消耗大量的计算资源和时间。并且领导者节点一旦出现故障或遭受攻击，可能导致交易顺序的延迟甚至混乱，严重影响系统性能。基于ACS的异步BFT协议^[18-24]包括ACS协议和公共子集聚合两部分^[25]。ACS协议包含分发和一致两个阶段。在分发阶段，节点利用可靠广播^[10]将交易子集传给所有节点，保证诚实节点接收相同子集；在一致阶段，全网节点对子集执行二元共识协议^[15]，只有达成共识的子集才会被处理。通过全网节点协同并行广播交易子集，ACS协议有效缩短了单个交易集合通信广播的长度，降低了因大量节点同时发送原始完整交易集合导致的消息广播雪崩风险。同时这类协议采用多节点分布式广播，相比基于DAG的单领导者节点方案来说安全性更高。ACS协议执行结束后，全网节点剔除达成共识的子集中重复、冲突和无效的交易，聚合成公共子集后打包成区块。

但是当前的基于ACS的异步BFT协议仍然存在以下挑战。第一，ACS协议虽然降低了消息丢失的可能性，但交易子集频繁的并行广播导致通信成本较高，消息广播雪崩的风险未彻底解决；第二，现有的基于ACS的异步BFT协议多集中于分发和一致阶段的性能优化，缺乏公共子集聚合机制的形式化设计，导致后续公共子集聚合过程效率低下，限制了其在区块链网络中的实际应用。

为解决以上挑战，本文沿着ACS的技术路线设计一种高并行化的异步BFT协议。针对通信成本较高的问题，我们设计了包含分发(Dispersion)、一致(Consistency)和重构(Reconstruction)的三段式ACS协议（以下简称DCR）。在分发阶段引入纠删码技术，减轻通信负载；在一致阶段通过设计向量结构的广播格式支持多个交易子集的并行共识，进一步降低通信开销；在重构阶段本方案实现了并行处理纠删码的恢复操作，降低了时延。此外，针对异步BFT协议的完整性问题，本文还提出一种高效的公共子集聚合机制，基于二叉树结构进行高效的交易子集聚合，并确保交易无重复、无冲突且有效，最终以区块形式上链。该聚合机制与DCR协议结合，构成完整的异步BFT协议，促进其在区块链系统中的落地应用。

1　 基础知识

1.1　异步公共子集

异步公共子集(ACS)协议的核心流程包含分发和一致两个阶段。在分发阶段，每个节点通过可靠广播将交易子集分发至所有节点，确保所有诚实节点接收一致的交易子集。此过程中，节点需要对收到的消息进行来源验证以及完整性检查，确保信息的可靠性。在一致阶段，节点对每个子集运行二元共识协议，以对是否确认交易子集上链达成全网共识。对于达成共识的交易子集，节点会将其聚合到公共子集，然后打包成区块上链。ACS的分发和一致阶段支持并行执行，显著提升了整体效率，这一优势已在文献[21]中得到验证。ACS协议应满足以下属性：

1） 一致性。如果任何诚实节点输出一个公共子集subs，则所有诚实节点都会输出相同的subs。

2） 有效性。如果任何诚实节点输出一个公共子集subs，则subs中的提案来源于n-f个节点，其中，n表示节点总数，f表示恶意节点的数量。

3） 终止性。如果n-f个诚实节点有输入，则所有诚实节点最终都会产生输出。

1.2　可靠广播

可靠广播(Reliable Broadcast, RBC)^[10]是用于ACS分发阶段的具体协议，它通过多轮广播将一个节点（发送者）提出的交易子集sub在异步网络中可靠传递给其他节点。RBC协议应满足以下属性：

1） 一致性。如果任何诚实节点输出子集sub，则所有诚实节点都会输出相同的子集sub。

2） 完整性。对于任何输入子集sub，所有诚实节点输出且最多输出子集sub一次。

3） 有效性。如果任何诚实节点输出子集sub，则sub一定由一个发送方节点输入。

1.3　异步二元共识

异步二元共识(Asynchronous Binary Agreement, ABA)^[15]是在ACS一致阶段用来达成共识的多轮协议。它确保即使在异步网络条件下，所有诚实节点仍能对分发阶段中的发送者提出子集sub达成一致意见。ABA协议应满足以下属性：

1） 一致性。如果任何诚实节点输出一个比特\delta，则每个诚实节点都会输出相同的比特\delta。

2） 终止性。如果所有诚实节点都以一个比特作为输入，则每个诚实节点最终都会输出一个比特。

3） 有效性。如果任何诚实节点输出一个比特\delta，则至少有一个诚实节点必须以\delta作为输入。

2　 方案设计

2.1 系统模型

本文异步BFT协议涉及四种实体：区块链节点、客户端、密钥生成机构(Key Distribution Dealer, KDD)和抛硬币机构(Coin Flipping Dealer, CFD)，如图1所示。具体来说，区块链节点处于异步对等网络中，其中每个节点都持有身份证书，并可以与系统中的所有其他节点建立安全连接。每个节点维护一个交易池、一个缓冲区和一个等待区作为存储。每个实体和存储区域的作用如下：

1） 客户端生成交易并传递给区块链节点。

2） 区块链节点将从客户端收到的交易广播到全网，并使用本文异步BFT协议达成共识。

3） KDD生成用于门限签名和门限加密的私钥和公钥，并在收到请求时返回给区块链节点。

4） CFD根据门限签名生成公共硬币，并在收到请求时返回给区块链节点。

5） 节点的交易池存储从客户端生成的、由其他节点广播但尚未由该节点提出的交易。

6） 节点的缓冲区存储各节点提出的已完成分发阶段但尚未完成一致阶段的子集。

7） 节点的等待区存储已达成共识、等待聚合并记录到区块的公共子集。

2.2 系统假设

假设区块链网络处于异步环境中，即节点之间通信的延迟不确定，消息可能因网络波动或蓄意攻击而无序到达，但诚实节点发送的消息最终会传输到接收方。网络中的节点可以分为恶意节点（拜占庭节点）和诚实节点，诚实节点严格遵循协议，而拜占庭节点则不遵守协议，可能通过发送错误信息、拒绝共识或合谋等方式干扰协议的正常执行。本文假设参与节点总数为n，其中拜占庭节点数量为f，且满足n≥3f+1，使系统能够容忍最多n/3的拜占庭故障。此外，本文假设恶意节点的计算能力有限，无法突破系统使用的加密算法，从而保障协议的计算安全性。

2.3 方案流程

本文提出的高度并行化的异步BFT协议主要包括两个部分：一是分发(Dispersion)、一致(Consistency)和重构(Reconstruction)三阶段并行的广播协议DCR完成区块链交易的全网共识；二是并发计算的高效公共子集聚合机制实现区块打包上链。

DCR协议的具体执行流程如图2所示。本文中，时隙s的下标（1,2，…，n）分别表示该时隙所属节点的编号（P₁，P₂,…,P_n ）。在分发阶段，整个DCR协议使用门限加密算法对提出的子集进行加密确保广播过程的安全性，即恶意节点无法获得真实的广播子集，直到子集达成共识后才会进行解密。使用纠删码减少分发阶段节点需要广播的事务子集大小，从而减少在分发阶段的通信负担。在一致阶段，该阶段通常比分发阶段运行时间更长，导致节点的缓冲区积累大量已完成分发但尚未达成共识的子集。为了避免共识通信消耗过多带宽导致的消息广播雪崩问题，本文为一致阶段的广播设计了向量结构，可以在一致阶段同时处理所有节点提出的多个连续时隙的分发子集以提高效率。在重构阶段，利用其不涉及广播只需在节点本地重构的特点，将此阶段与前面两阶段的广播并行运行，最大限度地利用了可用的带宽资源，而且保证了分发和一致阶段的通信操作不受影响。最后，DCR协议结束时就公共子集达成共识，设计了高效的基于二叉树结构的聚合机制，可以快速剔除重复交易、冲突交易和无效交易，完成交易区块上链。

1）　分发阶段

在分发阶段，每个区块链节点提出一个子集并通过可靠广播发送给其他区块链节点。该协议由三个步骤实现可靠广播：发送步骤、响应步骤和确认步骤。每个区块链节点P_i(i\in [n])维护一个交易池（tx_pool _i ）和一个缓冲区（buf _i,1,buf _i,2,…,buf _i,n ），其中，tx_pool _i 由多个由客户端生成，buf _i,1,buf _i,2,…,buf _i,n 分别存储来自P₁，P₂,…,P_n 的子集的信息。每个buf _i,j 中存储的子集信息都采用形如\left(s_j,e_i,{\sum }_{s_j}\right)的格式，s_j代表该子集对应的时隙，e_i是由一个发送方P_j(j\in [n])发送的sub的纠删码数据，而{\sum }_{s_j}是门限签名，可证明该sub在当前时隙的分发阶段被确认。整个分发阶段流程的伪代码如算法1所示。

（a） 发送步骤。该步骤中，发送方提出一个子集并使用纠删码处理后，将其发送给其他区块链节点。具体来说，发送方节点P_j(j\in [n])在当前时隙s_j从其交易池tx_pool _j 中随机选择交易子集sub。然后，P_j 使用(n-\mathrm{2}f,n)纠删码对sub进行编码，获得n个片段e₁,e₂,…,e_n。最后，P_j向P₁，P₂,…,P_n 分别发送消息\mathrm{V}\mathrm{A}\mathrm{L}\left(s_j,e_{\mathrm{1}},{\sum }_{s_{j-\mathrm{1}}}\right),\mathrm{V}\mathrm{A}\mathrm{L}\left(s_j,e_{\mathrm{2}},{\sum }_{s_{j-\mathrm{1}}}\right),\cdots ,\mathrm{V}\mathrm{A}\mathrm{L}\left(s_j,e_n,{\sum }_{s_{j-\mathrm{1}}}\right)，{\sum }_{s_{j-\mathrm{1}}}表示上一个时隙s_j-1发送的子集的门限签名。

（b） 响应步骤。该步骤中，每个区块链节点都会响应发送者并向其他节点再次广播相应的消息。具体来说，当节点P_i(i\in [n])接收到发送方P_j的VAL消息时，会使用公钥\mathrm{P}{\mathrm{K}}_{s_j-\mathrm{1}}和P_j在时隙s_j-1发送的子集信息(s_j-1,e_i )验证门限签名{\sum }_{s_{j-\mathrm{1}}}的有效性。如果有效，表示P_j在时隙s_j-1发送的子集被确认了。之后，P_i向所有区块链节点发送相应消息\mathrm{E}\mathrm{C}\mathrm{H}\mathrm{O}(s_j,{\sum }_{s_{j-\mathrm{1}}})，使得P_i的子集能进一步被扩散。

（c） 确认步骤。该步骤中，每个区块链节点收到足够的相应消息后，向其他节点广播确认消息，通知它们将子集放入缓冲区。具体来说，当收到来自不同节点的n-f条相应消息ECHO时，每个节点P_i,i\in [n]向KDD获取最新的公钥\mathrm{P}{\mathrm{K}}_{s_j}和私钥\mathrm{S}{\mathrm{K}}_{s_j,i}生成部分签名{\sigma }_{s_j,i}，并给所有节点发送确认消息\mathrm{R}\mathrm{E}\mathrm{A}\mathrm{D}\mathrm{Y}\left(s_j,{\sigma }_{s_j,i}\right)。当P_i收到2f+1条READY消息后，就会将部分签名{\left\{{\sigma }_{s_j,}{i}_k\right\}}_{k=\mathrm{1}}^{\mathrm{2}f+\mathrm{1}}聚合成当前时隙s_j的门限签名{\sum }_{s_j}，然后将子集以\left(s_j,e_i,{\sum }_{s_j}\right)的形式存入缓冲区\mathrm{b}\mathrm{u}{\mathrm{f}}_{i,j}中。

2）　一致阶段

在一致阶段，所有区块链节点对分发阶段从不同发送方接收的子集达成共识。该阶段包括四个步骤：评估步骤、投票步骤、批准步骤和决策步骤。对于每个区块链节点P_i,i\in [n]，假设\mathrm{s}{\mathrm{c}}_{j,i}是由发送方P_j(j\in [n])更新的子集的最新时隙，\mathrm{s}{\mathrm{c}}_j是在当前一致阶段中达成共识的发送方P_j的时隙，\mathrm{s}{\mathrm{p}}_j是在前一个一致阶段中达成共识的发送方P_j的时隙。此外，本文考虑一个向量 AG 存储每个节点P_i对所有发送方提出的子集的共识消息，以及一个向量 RES 存储在当前一致阶段中已经达成共识的子集的发送方节点的索引。每个一致阶段会循环多轮，直到 RES 包含的发送方节点数量达到n-f，表示在当前一致阶段中已经对足够多的发送方子集达成共识。一个时隙内一致阶段流程的伪代码如算法2所示。

（a） 评估步骤。该步骤中，每个区块链节点根据缓冲区中存储的信息评估期望共识的子集。具体来说，每个节点P_i(i\in [n])遍历缓冲区每个发送方P_j(j\in [n])的子集更新情况。如果P_j更新的子集的最新时隙\mathrm{s}{\mathrm{c}}_{j,i}大于在前一个一致阶段中达成共识的P_j的时隙\mathrm{s}{\mathrm{p}}_j，则将值v_{j,i}设置为1，表示P_i对P_j的子集的二元投票值。当n-f个发送方{\left\{P_{j_k}\right\}}_{k=\mathrm{1}}^{n-f}的投票值{\left\{v_{j_k,i}\right\}}_{k=\mathrm{1}}^{n-f}赋值为1，P_i将剩下节点的投票值v_{j,i}赋值为0。之后P_i初始化一个空向量 AG，并为每个发送方P_j的子集提出消息\mathrm{B}\mathrm{V}\mathrm{A}\mathrm{L}\left(s{c}_{j,i},v_{j,i}\right)，并将该消息推入 AG 中。

（b） 投票步骤。该步骤中，每个区块链节点向其他节点广播投票消息，投票表明对所有节点更新的子集的初步意见。具体来说，每个节点P_i(i\in [n])将BVAL消息以向量 AG 的形式广播给所有节点，当一个节点收到来自不同节点的\mathrm{2}f+\mathrm{1}条BVAL消息时，将这\mathrm{2}f+\mathrm{1}个投票值{\left\{v_{j_k,i}\right\}}_{k=\mathrm{1}}^{\mathrm{2}f+\mathrm{1}}放入投票集合bvals。

（c） 批准步骤。该步骤中，每个区块链节点向其他节点广播共识消息，进一步缩小共识范围。具体来说，每个节点P_i(i\in [n])的投票集合bvals不为空之后，就会从中随机选出一个共识值w_{j,i}（0或1），提出消息\mathrm{A}\mathrm{U}\mathrm{X}\left(\mathrm{s}{\mathrm{c}}_{j,i},w_{j,i}\right)，并放入向量 AG 中广播给其他节点。当一个节点P_i收到来自不同节点的n-f条AUX消息时，P_i向CFD请求公共硬币值c_j，来防止拜占庭节点协同提前预测共识结果。当CFD收到f+1个请求后，就会生成公共硬币值c_j。

（d） 决策步骤。该步骤中，每个区块链节点根据批准步骤选出的共识值和公共硬币值的情况判断是否达成共识。具体来说，每个节点P_i如果收到的共识值{\left\{w_{j_k,i}\right\}}_{k=\mathrm{1}}^{n-f}相同，在这个基础上，如果共识值w_{j,i}等于公共硬币值c_j，则表示达成共识，并将当前一致阶段中达成共识的发送方P_j的时隙\mathrm{s}{\mathrm{c}}_j更新为收到的时隙信息集合{\left\{\mathrm{s}{\mathrm{c}}_{j,i_k}\right\}}_{k=\mathrm{1}}^{n-f}中第n-\mathrm{2}f大的值，以此保证不会被拜占庭节点操纵结果且有足够的纠删码片段来恢复原始交易子集；如果共识值不等于c_j，则将投票值v_{j,i}更新为共识值w_{j,i}，并跳转到投票步骤再次执行重新投票；如果收到的共识值{\left\{w_{j_k,i}\right\}}_{k=\mathrm{1}}^{n-f}不相同，则将投票值v_{j,i}更新为公共硬币值c_j，并跳转到投票步骤再次执行一致阶段。当P_i对P_j的连续多个子集达成共识后，会提出决策消息\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}\left({\left\{s_j,e_i,{\sum }_{s_j}\right\}}_{s_j=\mathrm{s}{\mathrm{p}}_j}^{\mathrm{s}{\mathrm{c}}_j}\right)并放入向量 AG 中广播给其他节点。一方面，CALL消息携带的达成共识的子集的纠删码片段能在后续的重构阶段恢复出完整子集，另一方面向其他节点宣告共识结果，可帮助其他还在运行中的节点尽快达成共识。

3）　重构阶段

在重构阶段，每个节点P_i(i\in [n])处理了每个来自发送者节点P_j(j\in [n])在一致阶段达成共识的每个时隙的子集。根据从其他节点P_k(k\in [n])接收的用于子集重构的n-f个纠删码片段{\left\{\left(s_j,e_k\right)\right\}}_{k=\mathrm{1}}^{n-f}，P_i使用其中n-\mathrm{2}f份纠删码片段{\left\{\left(s_j,e_k\right)\right\}}_{k=\mathrm{1}}^{n-\mathrm{2}f}来解码完整子集\left(s_j,\mathrm{s}\mathrm{u}\mathrm{b}\right)。之后将重构完成的子集\left(s_j,\mathrm{s}\mathrm{u}\mathrm{b}\right)放入等待区等待检索。同时，这些达成共识的子集将从缓冲区中清除。未达成共识的子集被放回缓冲区，等待在下一个一致阶段达成共识。这一机制确保了所有提出的子集最终都会达成共识。

4）　公共子集聚合

本文设计了一种聚合机制，用于在一轮异步公共子集协议结束后处理达成共识的交易集合。该机制包含三个步骤：初始化步骤、并行合并步骤和冲突检测步骤。该机制具体流程的伪代码如算法3所示。

（a） 初始化步骤。由于同一发送方节点P_j(j\in [n])在多个连续广播阶段提出的子集{\left\{\left(s_j,\mathrm{s}\mathrm{u}\mathrm{b}\right)\right\}}_{s_j=\mathrm{s}{\mathrm{p}}_j}^{\mathrm{s}{\mathrm{c}}_j}中的交易是互不重复的，首先可以将这些连续子集聚合为一个大的公共子集。对于所有节点的聚合结果，再按照节点编号顺序，相邻编号的节点的子集依次合并，形成一个更大的公共子集。为处理来自不同发送方的子集中的重复交易，使用二叉树结构对公共子集进行整理，每个节点的子集作为二叉树的叶节点，从左至右依编号排列。然后自下而上依次对不同节点的子集去重和合并。

（b） 并行合并步骤。在二叉树结构中，逐级合并左右子节点的公共子集，检查右子节点中的每笔交易是否在左子节点的公共子集中存在。若交易已存在，则跳过；若不存在，则进行冲突判断。无冲突的交易将添加到左子节点的公共子集中，从而构建出父节点的公共子集。沿此规则从树的底部到顶部逐层并行构建，最终根节点的公共子集即为完整的无重复无冲突的公共子集subs。

（c） 冲突检测步骤。基于UTXO（未花费交易输出）模型进行冲突检测。对于每笔交易，检查其消耗的UTXO是否可用。若所有UTXO均未被消耗，则该交易无冲突；若任一UTXO已被消耗，则视为存在冲突。当发生冲突时，依据先入先出（FIFO）原则，剔除时间戳较早的冲突交易，以确保公共子集中仅包含有效且无冲突的交易。

经过上述步骤，每个诚实节点将生成一个包含无重复、不冲突且有效交易的完整公共子集subs。随后，各节点将该公共子集subs打包成区块，并将其依次追加到本地区块链中。

3　 理论分析和实验评估

3.1 安全性分析

本部分证明设计的DCR协议实现了一致性、有效性和终止性。

1） 一致性。本文设计的DCR协议的一致性由分发阶段和一致阶段保证。在分发阶段，诚实的区块链节点P_i(i\in [n])从发送者P_j(j\in [n])接收到子集sub，表明在最多容忍f个恶意节点的情况下，P_i收到至少有f+\mathrm{1}条READY消息来自诚实节点。在这f+\mathrm{1}个诚实节点中，至少一个节点收到超过n-f条ECHO消息，其中至少(n-f)/\mathrm{2}>f条来自诚实节点。对于另一个诚实节点P_{i\text{'}}(i\text{'}\in [n])，至少有一个节点已收到n-f条有效的ECHO'消息。由于诚实节点不能同时发送ECHO和ECHO'，因此能够保证所有节点达成一致性。在一致阶段，如果节点P_i对发送者P_j更新后的子集达成共识，则会广播CALL消息。当另一个节点P_{i\text{'}}接收到CALL消息时，会执行共识并再次广播CALL。此外CFD通过f+\mathrm{1}个请求门限防止恶意节点预测公共硬币，从而确保所有诚实节点对P_j的子集达成共识，保证一致阶段的一致性。最终，通过分发阶段和一致阶段，每个诚实节点在本地重构并存储子集后，所有节点都会在等待区中存储相同的子集，从而实现DCR协议的一致性。

2） 有效性。本文设计的DCR协议的有效性由分发阶段和一致阶段决定。在分发阶段，如果诚实节点P_i(i\in [n])接收子集sub，则它必须收到至少\mathrm{2}f+\mathrm{1}条有效的READY消息，其中至少f+\mathrm{1}条来自诚实节点的消息（假设有f个恶意节点）。按照类似一致性的逻辑，该子集sub至少由一个发送者P_j(j\in [n])提出，而不会凭空产生。在一致阶段，如果诚实节点P_i(i\in [n])同意发送者P_j更新的子集，则P_i收到n-f个有效向量 AG，其中至少n-\mathrm{2}f个来自诚实节点（假设有f个恶意节点）。诚实节点在AUX消息中共享相同的二元共识值并在BVAL消息中共享相同的二元投票值，并且至少一个诚实节点的时隙大于或等于最终共识的时隙，从而验证了有效性。因此，ACS协议能够实现有效性。

3） 终止性。本文设计的DCR协议的终止性由分发阶段和一致阶段决定。在分发阶段，诚实发送者P_j(j\in [n])通过VAL消息广播子集sub，其他诚实节点收到有效的VAL消息并广播ECHO消息。之后，每个诚实节点一定会收到n-f条有效的ECHO消息并广播READY消息。同样，每个诚实节点一定会收到\mathrm{2}f+\mathrm{1}条READY消息。因此，网络中的所有诚实节点最终都会接收sub。在一致阶段，诚实节点P_i为发送者P_j更新的子集广播BVAL和AUX消息。在收到n-f个包含AUX消息的 AG 向量后，它会迭代调整BVAL消息的值，直到所有诚实节点的消息收敛。即使在最坏情况下，如果只有n-f个诚实节点的消息一致，在多轮概率下，任意一个诚实节点P_{i\text{'}}(i\text{'}\in [n])都能在恶意消息到达之前达成共识并生成输出。当任意一个诚实节点就P_j更新的子集达成共识后，就会广播CALL消息，帮助其他诚实节点强制做出相同决定，终止一致阶段的当前迭代轮次。因此，DCR协议能够实现终止性。

3.2 性能分析

本部分对设计的DCR协议与现有的基于ACS的BFT协议的通信复杂度进行性能比较，并对公共子集聚合机制的处理效率进行分析。

1） DCR协议的通信复杂度。DCR协议的通信复杂度取决于并行执行的n个分发阶段和1个一致阶段。在1个分发阶段中，将大小为\left|\mathrm{s}\mathrm{u}\mathrm{b}\right|的子集sub分发到所有节点会导致O\left(\left|\mathrm{s}\mathrm{u}\mathrm{b}\right|\cdot n\right)的通信复杂度，因此n个并行的分发阶段具有O\left(\left|\mathrm{s}\mathrm{u}\mathrm{b}\right|\cdot n^{\mathrm{2}}\right)的通信复杂度。而由于门限签名和门限加密的叠加使用，会额外产生O\left(\lambda n^{\mathrm{3}}\mathrm{l}\mathrm{o}\mathrm{g}n\right)的通信复杂度，其中\lambda是安全参数的大小。假设所有更新的子集同时达成一致，1个一致阶段通过广播具有n个元素的向量的纠删码会产生O\left(\left|\mathrm{s}\mathrm{u}\mathrm{b}\right|\cdot n^{\mathrm{2}}+\lambda n\right)的通信复杂度，其中CFD请求硬币值需要O\left(\lambda n\right)的复杂度。因此，DCR协议的通信复杂度为O\left(\left|\mathrm{s}\mathrm{u}\mathrm{b}\right|\cdot n^{\mathrm{2}}+\lambda n^{\mathrm{3}}\mathrm{l}\mathrm{o}\mathrm{g}n\right)。尽管这与现有协议的复杂度量级相同，但分发阶段纠删码的使用降低了节点需要广播的数据量，一致阶段向量结构的使用优化了共识过程中的通信效率，避免了不必要的消息广播，因此总体的通信开销显著降低。

2） 公共子集聚合机制处理效率。公共子集聚合机制在并行合并步骤中利用二叉树结构实现了高效的交易合并操作。从树的底部到顶部逐层并行构建公共子集，通过快速检查右子节点交易是否在左子节点子集中，避免了大量不必要交易的比较操作。同时基于UTXO模型能快速检测并定位冲突交易，在大规模区块链网络及高并发交易中具有显著优势。

3.3 实验环境

为评估本文方案的性能，将其与最前沿的文献[18-21]方案在吞吐量和延迟上进行比较。实验部署在Ubuntu 18.04（64 bit）操作系统，256 GB RAM内存和Intel Xeon Gold 6133 CPU.50 GHz×2 CPU的环境上，其中区块链节点、客户端、KDD和CFD均在该环境下运行。实验基于Python.8.0实现，采用Jerasure.0库实现纠删码，所有协议均使用基于同态加密的门限加密算法来完成加密操作，并基于双线性配对技术实现门限签名和公共硬币协议。其中，本文和文献[21]方案的并发任务由gevent库处理。此外，为了支持全局异步通信，在每对节点之间建立了持久的TCP连接，以保证稳定的网络通信。

3.4 结果分析

用随机生成的250 B内容来模拟每笔交易，存储在所有节点的交易池中。区块链节点总数为n，拜占庭节点数量f =(n-1)/3。

3.4.1　吞吐量

通过调整区块链节点的总数和子集大小，测试了五种协议的吞吐量。吞吐量在这里被定义为单位时间内异步BFT协议处理的交易数量。

首先，根据前沿代表工作的实验规模，设置不同区块链节点总数并调整子集大小，确定不同协议在不同网络规模下的峰值吞吐量。如图3(a)所示，随着节点总数增加，5种协议的峰值吞吐量均有所下降。综合不同的节点规模可以发现，在节点数量为64时，本文方案以0.238×10³ tps的峰值吞吐量表现最佳，是文献[18]方案的3.5倍。这主要归因于本文方案并行执行了n个分发阶段和1个一致阶段，以及纠删码和向量结构的使用，使得在相同时间内能够处理更多的交易广播操作，从而提升了整体吞吐量。

其次，将区块链节点总数设置为16，并调整子集大小以测试吞吐量，测试结果如图3(b)所示。本文方案的平均吞吐量为8.396×10³ tps，在相同条件下优于其他协议。从图3(b)可知，本文方案的吞吐量最初随着子集大小的增加而上升，但随后又下降，但下降幅度相对较小。这主要得益于在分发阶段，纠删码技术有效减轻了通信负担，使得即使子集数据量增大，节点间的传输压力也能得到较好控制；在共识阶段，向量结构支持多个子集并行处理，提高了共识效率，确保交易能够及时得到处理。

因此，本文方案在处理高并发交易中具有显著优势。

3.4.2　延迟

通过调整区块链节点的总数和子集大小，测试了5种协议的延迟。这里的延迟定义为交易首次出现在发送方的交易池中，到其最终输出到节点的等待区的时间。

首先，根据前沿代表工作^[18-21]的实验规模，将子集大小设置为1，并调整区块链节点数量确定不同协议在不同网络规模下的基础延迟。如图4(a)所示，随着节点总数增加，5种协议的基础延迟呈上升趋势。本文方案的表现明显优于其他协议，综合不同的节点规模可以发现，当节点数量为64时，本文方案的基础延迟表现最佳，仅为文献[18]方案的13%。当节点总数为4时，本文方案的基础延迟仅为0.022 s。这得益于本文方案广播阶段与共识阶段的并行执行，使得交易在广播过程中即可开始进行共识相关操作，无需等待广播完全结束。同时，在重构阶段，由于其不涉及广播且可与其他阶段并行运行，减少了整体处理时间。

其次，本文将区块链节点总数设置为16，并调整子集大小。如图4(b)所示，五种协议的延迟随子集大小的增加而增加。本文方案的平均延迟为0.653 s，低于在相同条件下其他协议的延迟。这主要因为本文方案在广播阶段结束后，后续操作无需等待子集重构，能够快速将达成共识的交易子集进行处理，减少了等待时间。此外，在共识阶段，向量结构的使用优化了通信过程，使得交易能够更快地在节点间达成一致，进一步降低了延迟。

简而言之，本文方案能在大规模区块链网络环境中快速达成共识。

4　 结 语

本文提出了一种高并行化的异步BFT协议。它通过在分发阶段使用纠删码技术以及在一致阶段使用向量结构降低了协议整体的通信开销，并将重构阶段与分发阶段分离以进一步提高性能。此外，本文设计了一种公共子集聚合机制，解决了公共子集中交易重复、冲突和有效性问题，增强了协议的实际应用价值。与领先的异步BFT协议相比，本文方案表现出更高的吞吐量以及更低的延迟。考虑到并行执行的DCR协议会缓存已完成分发但未完成一致阶段的子集提案，未来研究将优化分发与一致阶段的运行时间以降低存储开销。此外，DCR协议当前依赖门限签名保证分发顺序，下一步将探索轻量化标记方法，以降低计算开销并提升性能。

参考文献

[1] DUAN S S， WANG X， ZHANG H B. FIN： Practical signature-free asynchronous common subset in constant time［C］//Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2023： 815-829. DOI：10.1145/3576915.3616633 .

[2] ANDROULAKI E， BARGER A， BORTNIKOV V， et al. Hyperledger fabric： A distributed operating system for permissioned blockchains［C］//Proceedings of the Thirteenth EuroSys Conference. New York： ACM， 2018： 1-15. DOI：10.1145/3190508.3190538 .

[3] KWON J， BUCHMAN E. Cosmos whitepaper［J］. A Network of Distributed Ledgers， 2019， 27： 1-32.

[4] MILAD M， OVEZIK C， KARAKOSTAS D， et al. Statistical confidence in mining power estimates for PoW blockchains［C］//Proceedings of the ACM Web Conference 2024. New York： ACM， 2024： 1752-1760. DOI：10.1145/3589335.3651960 .

[5] LEE D R， JANG Y， KIM H， et al. Poster： A Proof-of-Stake （PoS） blockchain protocol using fair and dynamic sharding management［C］//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2019： 2553-2555. DOI：10.1145/3319535.3363254 .

[6] LI C， XU R H， DUAN L， et al. Liquid democracy in DPoS blockchains［C］//Proceedings of the 5th ACM International Symposium on Blockchain and Secure Critical Infrastructure. New York： ACM， 2023： 25-33. DOI：10.1145/3594556.3594606 .

[7] GILAD Y， HEMO R， MICALI S， et al. Algorand： Scaling Byzantine agreements for cryptocurrencies［C］//Proceedings of the 26th Symposium on Operating Systems Principles. New York： ACM， 2017： 51-68. DOI：10.1145/3132747.3132757 .

[8] YIN M F， MALKHI D， REITER M K， et al. HotStuff： BFT consensus with linearity and responsiveness［C］//Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. New York： ACM， 2019： 347-356. DOI：10.1145/3293611.3331591 .

[9] SPIEGELMAN A， GIRIDHARAN N， SONNINO A， et al. Bullshark： DAG BFT protocols made practical［C］//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2022： 2705-2718. DOI：10.1145/3548606.3559361 .

[10] BRACHA G. Asynchronous Byzantine agreement protocols［J］. Information and Computation， 1987， 75（2）： 130-143. DOI：10.1016/0890-5401（87）90054-X .

[11] LU Y， LU Z L， TANG Q. Bolt-dumbo transformer： Asynchronous consensus as fast as the pipelined BFT［C］//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2022： 2159-2173. DOI：10.1145/3548606.3559346 .

[12] ABRAHAM I， DOLEV D， HALPERN J Y. An almost-surely terminating polynomial protocol for asynchronous Byzantine agreement with optimal resilience［C］//Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing. New York： ACM， 2008： 405-414. DOI：10.1145/1400751.1400804 .

[13] 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. DOI：10.1145/3149.214121 .

[14] KEIDAR I， KOKORIS-KOGIAS E， NAOR O， et al. All you need is dag［C］//Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. New York： ACM， 2021： 165-175. DOI：10.1145/3465084.3467905 .

[15] BEN-OR M， KELMER B， RABIN T， et al. Asynchronous secure computations with optimal resilience （extended abstract）［C］//Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing. New York： ACM， 1994： 183-192. DOI：10.1145/197917.198088 .

[16] YANG L， PARK S J， ALIZADEH M. Dispersed‑Ledger： High-Throughput byzantine consensus on variable bandwidth networks［C］//19th USENIX Symposium on Networked Systems Design and Implementation （NSDI 22）. Berkeley： USENIX Association， 2022： 493-51. DOI： 10.48550/arXiv.2110.04371 .

[17] DANEZIS G， KOKORIS-KOGIAS L， SONNINO A， et al. Narwhal and Tusk： A DAG-based mempool and efficient BFT consensus［C］//Proceedings of the Seventeenth European Conference on Computer Systems. New York： ACM， 2022： 34-50. DOI：10.1145/3492321.3519594 .

[18] ZHANG H B， DUAN S S. PACE： Fully parallelizable BFT from reproposable Byzantine agreement［C］//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2022： 3151-3164. DOI：10.1145/3548606.3559348 .

[19] ZHANG H B， DUAN S S， ZHAO B X， et al. WaterBear： Practical asynchronous BFT matching security guarantees of partially synchronous BFT［C］//USENIX Security Symposium. Berkeley： USENIX Association， 2023： 5341-5357. DOI： 10.5555/3620237.3620536

[20] GUO B Y， LU Y， LU Z L， et al. Speeding dumbo： Pushing asynchronous BFT closer to practice［C］//Proceedings 2022 Network and Distributed System Security Symposium. San Diego： Internet Society， 2022. DOI：10.14722/ndss.2022.24385 .

[21] GAO Y Z， LU Y， LU Z L， et al. Dumbo-NG： Fast asynchronous BFT consensus with throughput-oblivious latency［C］//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2022： 1187-1201. DOI：10.1145/3548606.3559379 .

[22] GUO B Y， LU Z L， TANG Q， et al. Dumbo： Faster asynchronous BFT protocols［C］//Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2020： 803-818. DOI：10.1145/3372297.3417262 .

[23] MILLER A， XIA Y， CROMAN K， et al. The honey badger of BFT protocols［C］//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 31-42. DOI：10.1145/2976749.2978399 .

[24] 韩将， 张振峰， 刘雨果， 等. 面向跨信任域互联网场景的拜占庭容错访问控制架构［J/OL］. 软件学报， 2025： 1-18. DOI： 10.13328/j.cnki.jos.007274 .

[25] HAN J， ZHANG Z F， LIU Y G， et al. Access Control Structure Based on Byzantine Fault Tolerance in Cross-trust-domain Internet Scenarios［J/OL］. Journal of Software， 2025： 1-18. DOI： 10.13328/j.cnki.jos.007274（Ch ）.

[26] 张凌越， 张宗洋， 周游， 等. 异步共识协议研究综述［J］. 密码学报（中英文）， 2024， 11（4）： 740-770. DOI： 10.13868/j.cnki.jcr.000707 .

[27] ZHANG L Y， ZHANG Z Y， ZHOU Y， et al. An overview on asynchronous consensus protocols［J］. Journal of Cryptologic Research， 2024， 11（4）： 740-770. DOI： 10.13868/j.cnki.jcr.000707（Ch ）.

基金资助

国家重点研发计划(2021YFB2700200)

中央高校基本科研业务费专项资金(2042022kf1195)

湖北省重点研发计划(2022BAA039)

山东省重点研发计划(2022CXPT055)