术语： ACS：异步公共子集协议（Asynchronous Common Subset）

ABA：异步二进制协议（Asynchronous Binary Agreement protocol）

RBC：可靠广播协议(Reliable Broadcast Protocol）

MVBA: 多值验证拜占庭协议(multi-value validated Byzantine agreement)

摘要。HoneyBadgerBFT是Miller等人[35]提出的第一个实用的异步原子广播协议，它展示了令人印象深刻的性能。 HoneyBadgerBFT (HB-BFT)的核心是利用Ben-Or等人的异步公共子集协议(ACS)实现批处理共识，由n个可靠广播协议(RBC)组成，每个节点提出自己的输入，然后n个异步二进制协议(ABA)对每个建议值(n为节点总数)做出决策。

本文提出了两种新的原子广播协议(Dumbo1, Dumbo2)，它们都具有渐近的和实际的更好的效率。特别是，Dumbo1的ACS只运行很小的$\kappa$个ABA实例(独立于n个实例)，而Dumbo2的ACS进一步将其降低为常数!我们的技术的核心是两个主要的观察结果:(1)减少ABA实例的数量显著提高效率;(2)更谨慎地使用多值验证拜占庭协议(multi-value validated Byzantine agreement, MVBA)，该协议被认为是[35]中ACS的次优方案，实际上可以导致更有效的ACS。

我们实现了Dumbo1和Dumbo2，并在100 Amazon EC2 t2上部署了它们和HB-BFT。介质实例均匀分布在全球10个不同的地区，并在相同的环境中进行广泛的实验。实验结果表明，我们的协议在延迟和吞吐量上都比HoneyBadgerBFT提高了好几倍，特别是当系统规模变大时。

介绍

拜占庭容错(BFT)协议使一组不受信任的对等体能够达成共识。作为分布式计算的一个基础研究领域，该问题已经得到了广泛的研究。BFT协议的一个主要分类是基于时间(或网络)假设。同步BFT协议假定所有诚实对等体发送的值都将在一定的时间内发送给接收方，这是每个人(包括协议设计者)都知道的。而部分同步的BFT协议则放宽了这一网络需求，允许存在但未知的时间限制。异步BFT协议最不依赖于网络假设，即它不需要存在这样的时间限制，只需要所有的值最终都会被传递。

最受欢迎的异步BFT。在早些年，考虑到BFT协议主要部署在对等体连接良好的传统内部场景中，BFT的研究努力集中在减少(加密)计算[5,41]，或增加协议可以容忍[21]的恶意参与者的阈值，假设网络是同步的。近年来，关于同步设置的Nice工作不断出现[11,1,33]。放松网络同步假设的努力也存在。一个值得注意的例子是经典的实用拜占庭容错(PBFT)协议[18]，它需要部分同步。然而，由于鲁棒性和效率的原因，在实际应用中完全取消同步假设变得越来越可取。

最近，加密货币和区块链技术的成功总体上为BFT协议带来了更广泛的应用场景，也证明了在广域网(WAN)上达成共识的可能性。开放的互联网环境提供了一个更具对抗性的设置，即对等体之间的网络延迟可以是时变的。然而，同步(或部分同步)BFT只能在连接良好的节点的相对“私有”网络中执行，以保证网络在一定的时间范围内交付。如果时间假设不成立，这些协议将无法取得进展，并陷入停滞。事实上，最近的工作[35]正式表明PBFT在“间歇同步网络”中无法取得任何进展，在这种网络中，对手只选择在特定的时间点延迟消息。这种“攻击”同样适用于一类基于leader的BFT协议[4,10,20,19,42,5]。

异步协议的另一个重要原因可能是由于效率，特别是一个称为响应性的属性。在设计同步BFT协议时，用假定的网络延迟作为参数，通常选择较大的网络延迟，使实际的网络延迟确实更小，从而保证了同步假设。因此，大多数同步BFT协议的效率取决于假定的网络延迟。而“响应性”则要求性能只与实际的网络延迟相关，因此它不应该依赖于任何计时假设，只要消息被传递，协议就会推进。

此外，众所周知，异步协议在实际构建分布式系统时大大简化了工程工作，因为不需要超时机制。在构建实现同步协议的系统时，应该设计各种特别的、容易出错的超时机制。

第一个实用的异步BFT[35]。尽管在真实的广域网中部署异步BFT在很多情况下是可取的，甚至是必要的，但在[35]中提出第一个实用的协议HoneyBadgerBFT之前，大多数关于异步BFT的研究都是理论上的。以前的异步BFT协议通常是低效的，例如，通信复杂度(每条消息)很高(如果有n个对等体，可以达到$O(n^2)$甚至$O(n^3)$[26,41,15,9,17,2]。随着系统规模的扩大，这些协议的性能将急剧下降。另一方面，HoneyBadgerBFT[35]的出色工作，提供了一些关键的观察结果，推动异步BFT向实用的方向发展。

第一个观察结果是，原子广播协议是对维护不断增长日志的BFT协议的持续执行(或者换句话说，常规BFT协议可以被视为它的一次性实例)，可以从称为异步公共子集(asynchronous common subset, ACS)的较弱变体和阈值加密方案轻松构建。ACS协议只要求对等体对它们所有输入的一个子集达成一致，最初提出这个协议是为了不同的目的[7]。

更重要的是，在[35]中观察到，Ben-Or等人[23]提出的经典ACS协议在渐近和实际效率上都更有希望（比另一种称为多值验证拜占庭协议（MVBA）的相关协议）[15]（稍后将进一步解释），请仔细选择底层构建基块。 [9,35]中的ACS协议是基于两个子协议构建的：可靠广播（RBC）和异步二进制协议（ABA）。结构非常简单：每个节点都调用RBC广播其输入值，并参与ABA协议的n个实例，以商定要包括哪些输入子集，见图1。

实验结果表明，HoneyBadgerBFT具有良好的性能。在[22]的出色工作中，作者对考虑不同部署场景时HB-BFT最合适的构建块实例(同时保持协议结构完整)进行了广泛的研究。我们选择了不同的道路，提出了以下问题:

我们能否重新设计ACS协议以提高其渐近性和实用性?

我们的贡献

我们设计了两种新的ACS协议，这两种协议都能渐进地提高系统的运行时间。我们的实验结果表明，当它们在Amazon AWS上的相同环境中反复运行时，比HoneyBad- gerBFT[35]有了成倍的改进。更有趣的是，我们的两个主要观察结果(1。应该减少ABA实例的数量;2. 如果对ACS谨慎使用，MVBA将更有效)，导致我们的两个协议更有独立性。让我们在下面详细说明。

Dumbo1:更快的异步BFT。首先，我们稍微详细地回顾一下HB-BFT中使用的ACS协议的结构:首先，每个对等体通过一个RBC实例广播其输入;当对等体从对等体Pi接收到值时，它将第i个ABA实例的输入设置为1，并启动ABA协议。一旦一个诚实的对等体从n - f ABA实例中得到1，它将输入0到所有剩余的还没有输入的ABA实例，然后继续。

识别主要瓶颈。由于著名的FLP不可能[23]，ABA必须是随机协议。这带来了以下缺点：尽管每个ABA协议的预期“回合”次数是恒定的，但运行n个并发ABA会话的预期回合数可能会很大，至少$O(log n)$[8] 更严重的是，这些ABA实例并不能真正以完全并发的方式执行：（1）并非所有实例都同时启动，因此某些实例可能由于未交付（先前RBC）的输入而稍后启动；（2）正常节点还面临着大规模并发执行的效率下降（CPU内核数量不足等）。当n变大并且网络不稳定时，很可能会有一些ABA实例终止得很慢。最慢的ABA实例确定HoneyBadgerBFT ACS的运行时间。

为了了解ABA协议对性能的实际影响，我们进行了HB-BFT实验，并对RBC和ABA之间的平均运行时间进行了统计。如图2所示，很明显，对于HB-BFT，ABA的成本占主导地位2。随着系统规模的扩大，这种模式变得更加重要。这种简单的观察启发我们减少了ACS协议中所需的ABA实例的数量。

减少ABA实例的数量。我们重新设计了ACS的结构，并提出了Dumbo1-ACS。与HoneyBadgerBFT（以及BEAT协议）不同，Dumbo1-ACS仅需要运行$\kappa$个而不是所有n个ABA实例，即可达到$O(log \kappa)$运行时间，其中$\kappa$是独立于n的安全性参数。其他复杂性指标保持不变。

在简化视图中，第sdfaksdafjksadjfefjaksdlf;iwejfias一阶段保持不变：每个节点都通过RBC实例广播其输入。然后，想象一下，如果我们有一个诚实的节点来担任领导者，那么它可以先完成n-f个RBC实例，然后通知所有其他节点输出这些RBC实例的交货。为了获得这样一个诚实的节点，我们可以选择少量的$\kappa$个节点作为“领导者”，以使其中至少有一个是诚实的。

由于现在两个诚实节点可能会从不同的选定“领导者”那里收到不同的值，因此需要进一步的注意。接下来，我们应该使诚实节点能够确定要选择的$\kappa$个选定节点中的哪个。它实际上变得类似于HB-BFT，我们可以调用ABA实例以确认要包含的子集的提名。一旦一些ABA实例输出1，就可以识别并输出相应的消息。重要的是，现在对等方只需要在$\kappa$个节点（可能比n个小得多）上达成共识。参见图3中的图示。

我们想强调的是，其余部分的变化保持在最小程度，因此ABA实例的减少也带来了重大的实际改进。看起来我们比HB-BFT有少量额外的RBC实例；但是，我们在这些额外的(索引)-RBC实例中将每个对等方的输入设置为一个很小的索引集（用Si代替实际的数据负载）。一个诚实的玩家如果确实收到与Si对应的所有消息，则为第i个ABA输入1。此外，为选择$\kappa$个节点而添加的投币协议只是ABA协议的子例程。因此，与消除ABA实例的成本相比，那些增加的开销将是不明显的。

看看为什么它工作:当一个诚实的节点决定输出对应Si的值，它必须是第i个ABA实例输出1位的情况。ABA的属性确保了(1)所有其他诚实节点也将输出1，(2)至少有一个诚实节点为这个ABA实例输入1。后者意味着至少有一个诚实的节点确实接收到索引集Si对应的所有输入值是${v_j}$。因此，遵循RBC的安全性，所有其他诚实的节点最终也将收到这些值。而条件(1)确保所有诚实的节点将实际输出相同的值子集。

Dumbo2:一个更快的异步BFT。Dumbo1现在只运行k个并发的ABA实例，我们现在问一个更有野心的问题:我们能把它一直推到常数吗?

将ABA推至最小值。HoneybadgerBFT需要执行n次ABA实例，因为每个ABA实例只确定来自一个对等体的输入。Dumbo1可以减少它，因为现在“委员会”成员已经准备好了一个值向量。但是，Dumbo1仍然需要运行k个实例:RBC阶段之后的过程非常类似于HB-BFT的结构，它选择一个包含索引集${S_i}$的公共子集作为元素。因为每个节点将调用/输入第i个ABA实例，一旦它从第i委员会接收到Si和所有与Si对应的值。这导致了一个挑战，不同的节点可能会进入不同的ABA实例，这些实例没有“全局协调器”，因此唯一可行的方法是并发运行所有的实例。

原则上，我们仍然“浪费” $\kappa - 1$个ABA实例。这启发我们找到一种方法来正确地识别一个输入向量，从而导致我们重新检查多值验证拜占庭协议(multi-value validated Byzantine agreement, MVBA)的适用性，它输出n个对等体中的一个输入，只要输入满足某些预定义的谓词。在[35]中, MVBA被认为不适合构建ACS。原因是现有结构通信复杂度高，即[15]中的MVBA协议在预期3中通信复杂度为$O(n^2\vert m\vert + \lambda n^2 + n^3)$，其中$\vert m\vert$表示MVBA输入值的大小。在许多情况下, $\vert m\vert > \lambda n(log n)$,因此,控制项的每条消息通信直接施工的ACS [15] $O(n^2 \vert m\vert) = \Omega(n^3)$(尽管[15]并没有明确提到ACS,其原子广播已经包含建设MVBA ACS,和最近的复杂性仍然甚至改善MVBA[2]),使MVBA协议用于构建ACS的不切实际。

但是，只有当MVBA直接调用大尺寸输入时，上述说法才成立。如果我们仔细观察，我们注意到，如果$\vert m\vert$很小，那么MVBA的整体通信复杂度(以及相应的ACS[15])并不比HoneyBadgerBFT中的ACS大，甚至要小很多! 见第6节的表1。而且MVBA具有ABA实例数量恒定的好处[15]。关键的挑战现在被简化为如何在输入较小的情况下调用MVBA来构造一个可能仍有较大输入的ACS。这让我们想起了在密码学的环境中被广泛使用的 “混合加密 “的传统智慧。

应用MVBA的正确方法。我们通过对MVBA的创新使用，提出了一个更快的异步BFT协议，我们称之为Dumbo2。它实现了渐进最优（恒定）的运行时间，即Dumbo2只需要运行（预计）三个连续的ABA实例，其他复杂度保持不变5。

要想解决ACS的细节问题，需要进一步的思路。由于ACS输出的是输入的子集，所以我们首先会通过RBC类型的协议为每个对等节点准备一个输入的向量。更重要的是，我们不把这些消息向量输入到MVBA协议中，而是进一步给每个对等节点准备一个很短的 “指示器”（图4中的$W_i$），并把它作为输入加入MVBA协议。MVBA协议将输出一个这样的 “指示器”，用来通知每个诚实的对等体挑选相应的RBC实例。棘手的是，在MVBA协议中，诚实的对等体可能会输出来自恶意对等体的输入（这里是短的 “指示器”）。

我们通过设计 “指示器 “的方式来解决这个问题，任何一个 “指示器 “都可以作为所有诚实的对等体收到相应消息的保证。我们制定了一个新的基元，称为可证明的可靠广播（PRBC），它增强了RBC，并进一步输出一个简洁的证明（即使是恶意节点），证明至少有一个诚实的对等体已经收到了输入。这可以通过RBC索引上的阈值签名来实现。MVBA内的ABA只需要重复（预计）三次。参见图4的图解，其中$\pi$是一个随机的排列组合。

来看看它为什么会工作：MVBA的实际输入$W_i$包括一个指数集和相应的证明。当一个诚实节点输出$W_i$时，$W_i$中的证明是有效的。这意味着$W_i$中的指数对应的消息都被足够多的对等体接收到了，而这些对等体中至少包括一个诚实的对等体。那么所有其他诚实节点最终也会收到这些消息。

我们指出，尽管Dumbo2在大多数情况下都优于Dumbo1，但为了表述的清晰，我们选择保留Dumbo1：在Dumbo1中使用每个ABA来投票是否输出每个 “委员会 “成员的向量，而不是像HB-BFT中的每个输入，这个想法是简单而直观的。这种更有效的投票的可能性可以看作是激励投票只输出一个人的向量的想法的垫脚石，最终导致Dumbo2使用MVBA的想法。另外，由于MVBA还是相当复杂的，在一些良性的情况下，当f非常小的时候，Dumbo2未必比Dumbo1好。

实现和实验评估。除了渐进式的改进（见第6节表1），我们还实现了Dumbo1和Dumbo2，并在实际的广域网环境中测试了我们的方案的性能。我们在100个Amazon EC2 t2.medium实例上部署了Dumbo1、Dumbo2和HoneyBadgerBFT，这些实例均匀地分布在全球10个不同的地区。为了公平比较，我们使用了与[35]相同的语言和密码学库，并在相同的环境下进行了各种测试。结果表明，我们方案的效率确实比HB-BFT高出数倍，尤其是当系统足够大时。例如，当n=100时，Dumbo1的基本延迟只有22%，Dumbo2的延迟只有HB-BFT的5%。此外，Dumbo1的峰值吞吐量为$3.5/times$，而Dumbo2的峰值吞吐量为HB-BFT的$9/times$以上。关于更多测试的细节请参见第7节。

为了展示我们观察到的减少ABA实例数量的有效性，我们从一个实验中选取结果（随机节点记录的每个子协议的运行时间），其中n=32，105个事务（每个250字节）作为输入，见图5。在图中，对于每个协议，每一行表示一个子协议实例的执行情况，例如，HB-BFT第一行的两根柱子分别对应第一个实例RBC1和ABA1，第二行对应第二个实例RBC2/ABA2，以此类推。Dumbo2中的一致广播(CBC)协议是MVBA的一部分，可以看作是RBC的简化版(详细定义见附录)。

模型和问题陈述

系统模型

现在我们描述一下我们的系统模型。

设置。具体来说，它涉及一组指定的n个节点{$P_i$}$_{i\in[n]}$，我们用[n]来表示整数{1,2,…,n}。我们认为这些节点的身份是公开的，例如，由PKI认证。我们用$(PK_i，SK_i)$表示节点$P_i$的公钥/私钥对。除了已经建立的身份之外，一个可信的第三方也会在协议之前运行，以建立所有涉及的阈值密码系统。

干扰破坏。我们假设有f个故障节点$(3f+1 \leq n)$，并认为这些故障节点完全由对手控制[35,15]。这样的敌方模型意味着在协议开始前，允许敌方选择f个节点将其完全破坏，那么敌方可以得到所有故障节点的初始内部状态，也可以让这些节点在协议执行过程中任意误操作。

异步网络。我们考虑的底层通信网络由异步的完全混合认证的点对点（p2p）信道组成。在这个模型中，在任何两个节点之间，都有一个已建立的认证的p2p信道。然而，对手可以完全控制所有信道上传递的值，即对手可以任意延迟，但诚实节点之间发送的值最终会被传递，这明确地暗示了两个事实。(一) 敌方可以任意重新排序数值，(二) 网络不会从诚实节点上丢弃任何数值。

设计目标

原子广播。我们的最终目标是在上述系统模型下设计一个n个节点之间的原子广播协议。形式上，一个原子广播协议以压倒性的概率满足以下特性：

协议。如果一个诚实节点输出一个值v，那么每个诚实节点都输出v。
总顺序。如果两个诚实节点分别输出值序列 $\langle v_0,v_1,…,v_j \rangle$ 和 $ \langle v’_0,v’_1,…,v’_j’ \rangle$ ，那么当 $v_i = v’_i$ 时 $i \leq min(j,j’)$。
弹性审查。如果一个值v被输入到n - f个诚实节点，那么它最终被每个诚实节点输出。

我们要求这三个特性以压倒性的概率成立。简而言之，我们将采用与HoneybadgerBFT[35]相同的模型，即在异步网络中针对f个静态损坏的n个节点之间进行原子广播。

原子广播协议以连续的纪元为单位进行，每一个纪元后，输出一批新的事务，并追加到已提交的日志中（见附录8.1）。

异步公共子集(ACS)。HoneyBadgerBFT[35]的一个很好的观察是，从一个较弱的变体，称为异步共同子集(ACS)，再加上阈值加密，高效而简单地转换为原子广播。ACS本质上是让每个节点输出所有节点输入的共同子集。形式上，它满足。

协议。如果一个诚实节点输出一个集合V ，那么每个诚实节点都输出V 。
有效性。如果一个诚实节点输出了一个集合V ，那么$\vert V\vert \geq n - f $，并且V至少包含n - 2f个诚实节点的输入。
完全性。如果n - f个诚实节点有一个输入，那么所有诚实节点都可以产生一个输出。

值得注意的是，从ACS到原子广播存在一个简单的转换，通过添加阈值加密，我们参考附录8.1和[35]中的细节。

复杂度测量。BFT协议的实用性很大程度上取决于其计算复杂度。在本文中，我们考虑以下三个度量:

消息复杂度：诚实节点在协议期间产生的消息的预期总数量。
通信复杂度：诚实节点在协议期间产生的消息的预期总位长。
时间(轮)复杂度：协议终止前预期的通信轮数。

此外，请注意，在本文中，我们始终考虑n=3f+1，因此，我们的BFT协议也是一种最优的弹性，它只是考虑了多少个节点可能被破坏。

前言

我们介绍一些基础构件的定义。

可靠广播(RBC)是运行在一组n个节点之间的协议，其中有一个节点称为sender，其目的是向所有其他节点广播一个值。更正式地说，一个RBC协议满足以下属性:

协议。如果任意两个诚实节点分别输出v和v’，则v=v’。
完全性。如果一个诚实节点输出v，那么所有诚实节点都输出v。
有效性。如果发送者是诚实的，并且输入v，那么所有的诚实节点都输出v。

一致性广播(CBC)与RBC类似，但它不提供完全性。

异步二进制协议(ABA)是n个节点之间的一种特殊的异步拜占庭协议。在ABA协议中，每个节点都有一个单比特(single-bit)(0/1)输入，它们的目标是就决定的比特达成协议[37,16,14]。更正式地说，ABA协议具有以下保证:

协议。如果任何一个诚实节点决定比特b，那么每个诚实节点都决定b。
终止。如果所有诚实节点都收到输入，那么每个诚实节点决定一个位。
有效性。如果任何诚实节点决定b，那么至少有一个诚实节点收到b作为输入。

备注。与之前的许多作品[37,14,16,35]一样，这里的ABA的终止属性只需要所有诚实的节点来决定(在输出一个值供进一步应用的意义上，同时不停止协议)。有可能它们各自决定一个值，但有些节点仍然在协议中继续等待消息[35]。和[35]一样，我们在ABA中的一个位上互换使用 “输出 “和 “决定”。RBC、CBC和ABA 7协议的具体构造详见附录8.2。

多值拜占庭协议（MVBA）。MVBA[2,15]允许就任意值达成协议，而不限于二进制值。该协议有一个全局的、所有节点都知道的多项式时间可计算的谓词Q，它由特定的应用决定。该协议的基本思想是每一方提出一个包含一定验证信息的（不同）值作为输入，并输出一个满足Q的值作为决策值。该协议确保决策值至少由一方提出。每个诚实节点只向MVBA输入一个满足Q的值。

更正式地说，一个MVBA协议除了概率可以忽略不计外，还满足以下特性。

终止。如果每个诚实节点$P_i$输入的是一个外部有效值$v_i$，那么每个诚实节点都会输出一个值。
外部有效性。如果一个诚实节点输出一个值v，那么Q(v)=真。
协议性。所有终止的诚实节点都输出相同的值。
完整性。如果所有节点都是诚实的，如果有些节点输出v，那么有些节点提出v。

阈值签名方案： 让$0 \leq t \leq n $，A(t,n)-非交互式阈值签名方案是一个涉及n个节点且最多可以破坏t-1个节点的算法元组，其中每个节点都有一个私有函数SigShare，以及三个公共函数ShareVerify、Combine和Verify（形式定义见附录8.2）。签名模式满足以下属性:

不可伪造性。在多项式时间内，没有任何敌手能在不查询签名算法的情况下，伪造任何消息m的签名，并能得到正确的验证（由诚实的各方）。
稳健性。当提供信息m作为签字算法的输入时，所有诚实的当事方最终都能得到可以正确核实的m的签字。

$(1,k, \epsilon)$–委员会选举（CE）: CE协议在n个节点(从1到n)中执行。如果至少有f+1个诚实节点参与，协议终止，诚实节点输出一个k大小的委员会集C，使得C中至少有一个是诚实节点。特别是，一个协议被称为$(1,k,\epsilon)$-委员会选举，如果它满足以下属性，除了在密码安全参数$\lambda$中的概率可以忽略不计:

终止。如果f+1个诚实节点激活协议CE，诚实节点之间的所有消息都到达，则所有诚实节点输出C。
协议。任何两个诚实节点输出同一组C。
有效性。如果任何一个诚实节点输出C，（i）$\vert C\vert=k$，（ii）每个节点$P_i \in C$的概率相同，（iii）C至少包含一个诚实节点，概率至少为$1-\epsilon$。
不可预测性。在被一个诚实节点调用之前，对手预测返回委员会的概率最多为$1/(^n_k)$。

请注意，一个$(1,k, \epsilon)$-CE可以直接从阈值掷硬币中构造出来(见附录8.2)，它可以很容易地从阈值签名中得到。在C中至少有一个诚实的节点以压倒性的概率$1-\epsilon-negl(\lambda)$当选，其中$negl(\lambda)$是密码安全参数$\lambda$中的一个可忽略的函数，而$\epsilon$是$exp(-\Omega(k))$ (详见Lemma 1)。

Dumbo1: 一个快速异步BFT协议

在本节中，我们将介绍我们的第一个ACS，它被称为Dumbo1-ACS。应用同样的从ACS到原子广播的转换[35]（增加阈值加密），我们可以得到一个新的原子广播。Dumbo1。下面我们将重点介绍ACS协议。

Dumbo1-ACS

概述。 我们设计的核心是减少ACS执行中所需要的ABA实例数量。正如在引言中简单阐述的那样，HoneyBadgerBFT（也包括BEAT）需要n个ABA实例的原因是：对等体需要通过一个ABA实例来商定如何处理每个对等体的输入。请观察，在第一个RBC阶段之后，每个对等体都准备了一个输入子集。

我们不会为每个输入投入一个ABA，而是让少量的k个 “聚合者 “来提名输出哪个输入子集（基于它已经收到的东西）。这样一来，现在每个ABA实例都被用来让节点确定它们是否同意第i个提名子集$S_i$。我们再次指出，提名过程也是使用RBC，但是，输入的只是指数集$S_i$，而不是实际的数据负载。同时，提名人/委员会的选举最多只是一次掷硬币，因此与保存的ABA实例相比，开销是最小的。

需要注意的是，仍然需要k个ABA协议实例，否则一个诚实的节点可能决定跟随$S_i$，而另一个诚实的节点可能决定跟随$S_j$ ，因为他们每个人确实都收到了相应的输入值，但最终违反了协议。

稍微详细一点，如引言中的图3所示，我们的Dumbo1-ACS包括RBC的两个阶段，分别表示为数据-RBC和索引-RBC。数据-RBC实例由节点执行，以广播他们的输入，然后选择k个领导者。索引-RBC实例只有在被选中的成员从这些数据-RBC实例中接收到n - f个值时才会被启动。每一个索引-RBC都用来广播表示被选中的成员已经收到哪些n-f值的索引。在最后一个阶段，如果一个诚实的节点已经收到了$S_i$(大小为n - f)和数据-RBC实例中所有相应的值，它将向第i个ABA实例输入1。

委员会选举。这些委员会/提名人的选举是标准做法，即随机选择k个节点，以确保其中一个节点以压倒性的概率诚实，概率在 k 内。通常，k个随机同行中没有一个是诚实的概率最多为$(1/3)^k$(见Lemma 1)。在实践中，我们可以让系统设计者在他喜欢的任何小的$\epsilon_0$上选择$k= min(k_0，f+1)$的方式，使$(1/3)^{k_0} \leq \epsilon_0$。

Dumbo1-ACS的构造。 现在我们介绍一下我们的Dumbo1-ACS的构造。Dumbo1-ACS的详细过程如算法1所示。如图3简介中所示，我们的Dumbo1-ACS包括两个阶段的RBC，第一阶段是广播值，第二阶段是广播索引。

Dumbo1-ACS协议由五个逻辑阶段组成，详细协议流程如下：

值广播。(第02行). 所有节点$P_i$向$RBC_i$协议输入自己的值$v_i$。
委员会选举：（03-03行）。(03-03行)。所有节点都参与CE协议来选择委员会C，并将委员会成员的身份放入一组CMIS中。
索引广播：（06-09行）。(06-09行)。当委员会成员从不同的RBC实例中接收到n-f个Value消息后，将这些n-f个Value消息的索引通过RBC进行广播。
ABA阶段。(第10-17行). 当一个诚实节点已经从委员会成员$P_j$接收到索引消息($S_j$)和RBC实例中所有对应的值消息时，则向$ABA_j$实例输入1;如果一个诚实节点从任何$ABA_j$和$j\in CMIS$中获得输出，则向尚未提供输入的其他ABA实例输入0。
输出阶段。(第18-25行). 当一个节点在ABA的所有k个实例中终止时，对于任何$x \in CMIS$，如果$ABA_x$输出1，则该节点等待来自$RBC_x$的索引消息，得到一个集合S，并进一步等待值消息，从$RBC_j$得到所有$j \in S$的$v_j$，最后输出$ \lbrace v_j \rbrace _{j \in S}$。

安全分析

Dumbo1通过ACS和阈值加密的结合实现了原子广播。为了证明Dumbo1的安全性，我们需要分两步走。(1)将原子广播还原为ACS和阈值加密；(2)证明我们新构建的Dumbo1-ACS协议确实满足ACS特性。

步骤1的证明已经在[35]中给出，更多细节请参考附录8.1。这里我们主要关注步骤2，并证明Dumbo1-ACS满足ACS的所有性质。

Lemma 1. (CE的有效性：)如果n＝3f＋1，k＜＝f，CE(id)返回一个集合C，那么集合C中至少包含一个诚实的节点，除非有$exp(-\Omega(k))$概率。

证明。由于伪随机性，因此，随机选择k个节点的总情况是$(^n_k)$，不包含诚实节点的集合C的总情况是$(^f_k)$。设p为集C中不含诚实节点的概率。所以，我们有

注释：如果f很小，我们可以简单地设k= f+1。算法4满足CE的终止性、协议性和不可预测性的特性，由抛币阈值的特性可知。

定理1。 除$exp(-\Omega(k))$概率外，Dumbo1-ACS协议满足ACS的协议性、有效性和完全性，假设底层的RBC、CE和ABA协议是安全的。

证明。协议性。为了证明Dumbo1-ACS满足协议属性，我们证明当一个诚实节点输出V时，那么每个诚实节点都输出V。假设一个诚实节点P的输出$V = \lbrace v_j \rbrace _{j \in S}$。

索引S必须包含在一些索引集中。W.l.o.g，我们假设S只包含一个索引集$S_k$，(索引，$S_k$)在某个RBC(表示为$RBC_k$)中被接收，那么该节点一定在相应的ABA实例(表示为$ABA_k$)中接收了1。由于ABA的协议属性，所有诚实节点也会在$ABA_k$中收到1。因此，所有诚实节点都会等待$RBC_k$输出的索引消息，由于RBC的总体性和协议性，所以所有其他诚实节点都会收到相同的索引消息(索引，$S_k$)。

另一方面，由于ABA的有效性，至少有一个诚实节点P’向$ABA_k$输入1。这意味着这个诚实节点一定收到了索引消息(索引$S_k$)和和这些Value消息$\lbrace Value, v_j \rbrace _{j \in S_k}$对应的索引集$S_k$。现在，RBC的总体性和协议性可以保证包括P在内的所有其他诚实节点对任何$j \in S_k$都会收到$\lbrace Value, v_j \rbrace$。

因此，每个诚实节点都输出 $ \lbrace v_j \rbrace _{j \in S_k} = \lbrace v_j \rbrace _{j \in S} = V $.

有效性。为了证明Dumbo1-ACS满足有效性属性，我们证明当一个诚实节点输出一个集合V时，$\vert V \vert \geq n - f $，且V至少包含$n - 2f$个诚实节点的输入。

如果一个诚实节点$P_i$输出一个集合$V = \lbrace v_j \rbrace _{j \in S} $ ，W.l.o.g，我们假设S只包含一个索引集$S_k$，(索引$S_k$)被收到索引-$RBC_k$中。根据算法1，我们可以知道$ABA_k$返回1，由于ABA的有效性，至少有一个诚实的节点(如P’)向$ABA_k$输入1。这意味着P’一定收到了索引消息(索引$S_k$)和所有值消息$\lbrace Value, v_j \rbrace _{j \in S_k}$对应的索引集$S_k$，其中 $\vert S_k \vert =n - f$。

现在RBC的总体性和协议性可以保证包括$P_i$在内的所有诚实节点都能收到$\lbrace Value, v_j \rbrace _{j \in S_k}$ ，其中$\vert S_k \vert = n - f$ 。所以，$ V = \lbrace v_j \rbrace _{j \in S_k}$ 。因此，我们有$ \vert V \vert \geq n - f $。注意，最多存在f个容错节点，在集V中必须有至少n - 2f个来自诚实节点的输入。

完全性。为了证明Dumbo1-ACS满足完全性属性，我们证明，如果n-f个诚实节点有输入，所有诚实节点都会产生输出。

由于n - f个诚实节点有一个输入，根据RBC的有效性，因此，每个委员会成员可以从不同的RBC实例中接收n - f个Value消息。因此，每个委员会成员都可以激活第二阶段的RBC实例。此外，根据CE协议，至少有一个诚实节点(如$P_i$)属于委员会。

接下来，我们将证明至少有一个ABA实例返回1。

首先，假设所有ABA实例都输出0，在这种情况下，第14-17行永远不会执行，也就是说，0永远不会被诚实节点输入到任何一个ABA实例中。但是，根据ABA的有效性，至少有一个诚实节点向ABA输入0，这就诱发了矛盾。

其次，由于委员会成员$P_i$可以激活第二阶段的$RBC_i$实例，如果所有的诚实节点一直没有收到任何ABA的1，在这种情况下，所有的诚实节点都可以收到来自$P_i$的有效Index消息(RBC的有效性)和来自RBC实例的相应Value消息(RBC的总量)，接下来，所有的诚实节点都向$ABA_i$输入1。同样根据ABA的有效性，$ABA_i$将向所有人返回1。

因此，至少存在一个ABA（比如说$ABA_k$）实例返回1。由于ABA的有效性，至少有一个诚实节点（比如说P’）向$ABA_k$输入1。这意味着这样的诚实节点一定收到了索引消息(索引$S_k$)和对应索引集$S_k$的所有Value消息$ \lbrace Value , v_j \rbrace _{j \in S_k} $。现在RBC的总体性和协议性可以保证所有诚实节点都能收到$ \lbrace Value , v_j \rbrace _{j \in S_k} $。因此，所有诚实节点都可以产生输出$ \lbrace v_j \rbrace _{j \in S_k} $。

Dumbo2: 更快的异步BFT协议

在本节中，我们提出了一种进一步改进的ACS协议Dumbo2-ACS，它将ABA实例的数量减少为常数，从而保证在恒定的运行时间内终止。我们展示了一种使用RBC和MVBA的ACS新构造。更有趣的是，我们的新方法展示了对MVBA的创新使用实际上可以带来更高效的ACS，而在[35]中，这被认为是比使用RBC和ABA更不乐观的。

Dumbo2-ACS

概述。如上所述，Dumbo1改进了HB-BFT，其意义在于将ABA实例的数量减少到了k，但它们仍然都需要运行。为了尽量减少ABA的使用量，我们需要：（1）给每个对等节点准备一个来自足够多的对等节点的输入矢量；（2）找到一种方法来识别并输出其中的一个。前者很容易，一个RBC阶段已经实现了。后者启发我们重新审视MVBA的可能性，它只输出一个输入（不一定来自诚实节点，但满足一些条件）。正如在引言中所解释的那样（在第6节的表1中也有解释），当前的MVBA构造被认为对ACS不切实际，因为它的通信复杂性很高。然而，如果我们检查通信复杂度中的所有项，当消息大小变小时，主导项就会发生变化，MVBA甚至可以超常发挥! 更重要的是，MVBA[15]只需要在期望中连续运行三个ABA实例。

考虑到混合加密的传统智慧，较重的公钥加密仅用于隐藏一个短的会话密钥，而实际（可能是大的）消息将使用会话密钥的对称密钥加密。与此类似，我们同样使用指数作为输入来调用MVBA。现在我们还有一个挑战，即MVBA可能会从一个不诚实的节点输出一个这样的索引集。为了解决这个问题，我们提出了可证明的RBC，它进一步输出一个简洁的证明s.t.，无论谁产生这样的证明，它都保证所有诚实的节点都能收到输入值。

可证明的可靠广播（PRBC）。 获得这种（简洁）证明的自然方法是获得足够多节点的确认，这可以通过RBC标识符上的阈值签名来实现。带有标识符id，以及验证算法Verify的PRBC协议被表示为$PRBC_{id}$。从形式上看，一个$PRBC_{id}$协议除了概率可以忽略不计外，还满足以下特性:

协议。如果一个诚实节点输出v，另一个诚实节点输出v’，那么v=v’。
完全性。如果任何节点输出一对(id, $\sigma$)，且$ Verify(id, \sigma)=1 $，那么所有诚实节点都输出一个值v和(id, $\sigma$)
有效性。如果发送者是诚实的，并且输入了v，那么所有诚实的节点都会输出v和有效的字符串（id，$\sigma$）。
简洁性。有效字符串 $\sigma$ 的长度（大小）与值v的长度无关。

由RBC和阈值签名可以构造一个PRBC，如算法2所示。PRBC协议可以分解为三个逻辑阶段，具体内容如下:

值广播阶段。(02-04行)。如果节点为发送方，则节点$P_s$向RBC协议输入值与。
输出值阶段。(05-07行)。如果诚实的节点从发送方接收到一个值，那么节点向所有节点发送一个id的阈值共享签名。
输出签名阶段：（08-13行）。(08-13行) 如果节点收到了id的f+1个有效的阈值共享签名，就可以将这些共享签名组合成id的阈值签名$\sigma$，然后输出。

Dumbo2-ACS的构造。现在我们给出我们的Dumbo2-ACS协议的构造，具体内容如算法3所示。我们将$MVBA_r$表示为MVBA协议，标识为r，如引言中的图4所示，Dumbo2-ACS包括两个部分。PRBC和MVBA。

我们将使用 $W =\lbrace (s_1,\sigma 1),(s_2,\sigma _2),…,(s_n,\sigma _n)\rbrace$ 作为每个节点的 $MVBA_r$ 的输入。特别是，如果接收到$s_i$上对应的i，则将$s_i$放入W中。如果W中至少有n - f个不同的i满足$ s_i \not= \bot $，$MVBA_r$的断言Q将输出1，对于W中的每一个 $(s_i, \sigma _i)$，都是PRBC的有效输出，即$Verify{f+1}(\langle r, s_i \rangle , \sigma _i)=1$，如果$s_i \not= \bot $ 。Dumbo2-ACS协议可以分解为三个逻辑阶段，详细的协议过程如下:

值广播阶段。(03-04行). 所有节点$P_i$向PRBC协议输入自己的值$v_i$，并等待n-f个不同的Finish消息。
Honey Badger of BFT

小飞象(DumboBFT)

介绍