华东师范大学区块链实验室论文阅读分享会于2024年4月2日在线下进行，硕士研究生叶哲名分享了论文Flexible Advancement in Asynchronous BFT Consensus。该论文由上海交通大学、蚂蚁集团发表在SOSP2023上，作者是Shengyun Liu,Wenbo Xu,Chen Shan等。
论文链接：https://dl.acm.org/doi/pdf/10.1145/3600006.3613164
1 研究背景和动机
1.1 区块链场景下共识协议所面临的问题
拜占庭容错(BFT)协议是区块链场景下分布式一致性的重要解决方案，协议保证在一个存在故障或恶意节点的非可信环境中，系统中的大多数节点能够达成正确的共识。过去十几年，许多BFT协议如PBFT、HotStuff等被提出，并且被广泛运用于各种许可或非许可区块链。传统BFT协议大多是基于部分同步网络假设的，并且通过设立领导者来完成提议的发送和客户端请求的排序。
随着区块链技术的不断发展，其底层共识协议面临一些新的挑战。首先，大多数区块链应用程序都部署在广域网（WAN）上，其网络延迟可能很高且不可预测。其次，相较于传统分布式数据库系统，区块链系统的节点数量更多，尤其是在公链场景下，数量可以达到几百到几千甚至更多。另外，区块链系统中的每个节点可能专门为其客户服务，并且不希望将区块的生成委托给其它节点。而正如前文所提到的，传统BFT协议大多是基于部分同步网络假设和的有主共识协议。在部分同步网络假设下，消息只保证在GST时间后，在某个界限∆之后被递送，但是∆可能是时变的甚至是协议设计者未知的，在现如今的不可预测的高延迟场景下，∆的设置是一个棘手的问题。过大的∆无法精准快速的感知到故障的发生，而过小容易频繁的触发故障恢复机制从而导致系统性能下降。同时，领导者的设置也使得领导者本身的系统带宽容易成为整个系统的性能瓶颈，这是由于在有主共识协议下，领导者需要将提议转发给其它所有节点同时接受来自其它节点的回复以及客户端的请求，因此在系统节点数量较大的情况下，容易形成单点瓶颈。并且，在有主共识协议中区块的生成完全由领导者负责，这不符合如今区块链场景下，一些节点可能不希望将区块的生成委托给其它节点的要求。
因此，针对现如今的区块链系统，底层共识协议需要具备不依赖网络假设、每个节点平等提出请求和行动的无主设置等特点，而这正是异步共识的优点。
1.2 异步共识
在异步网络中，攻击者可以在任何时间内以任何顺序传递消息，但最终在正确节点之间发送的消息必须被传递。由于在异步网络中，消息只保证最终能在正确节点之间传递而不保证传递的时延，无法有效地区分“消息到达慢”和“消息没有发送”之间的区别，因此在异步网络中的节点通常不使用时钟（如Raft中的timeout）作为改变自身运行状态的触发器，只根据它们接收到的消息的顺序采取行动。
FLP定理从理论上证明了，在异步网络中，即使在故障节点的数量只有一个这样最简单的情况下，理论上也不存在一定能在有限时间内结束的确定性共识算法。简单来说，在任何的初始设置下，我们总能找到一条系统“前进”的路径，使得系统无法达成正确的一致。虽然我们无法从根本上避免这条路径的产生，但我们可以从另外一个角度放宽对这个结果的容忍度，即让这条路径出现的概率无限趋近于0，换句话说，我们可以容忍一个异步共识协议以概率1完成共识。这也是传统异步共识协议设置“随机化”阶段的原因。在大多数异步共识协议中都会采用Common Coin作为随机化的手段，简单来说，在异步网络中会出现无法达成共识的情况，也就是针对同一件事，可能会出现有一部分节点表示同意，另一部分节点表示不同意，此时无法达成共识。解决这种分歧的方案很简单，当一个节点发现针对某一件事网络中的所有节点有分歧时，它通过“抛硬币”的方式来做决策。当然这样简单抛一次硬币可能还是无法使得所有节点做出同样的决策，如果一次不够，那就多抛几次，最终一定有那么一次大家做出了同样的决策。
1.3 现有异步共识协议问题
在传统异步共识协议中，协议的运行单位称为epoch，其中在每个epoch之后，一批新的交易被附加到提交的日志。每个epoch会包含r轮，r是个不确定的数，在每个epoch中，每个节点都需要提出自己的提议（一批交易）。传统异步共识协议将每个epoch抽象为异步公共子集(ACS)问题，即每个节点提出自己的输入，最终每个节点输出包含至少N−2f个正确节点的输入的并集。这里N-2f的设置是由于在异步网络下，消息的延迟理论上无上限，因此无法区分还未发送到和恶意节点不发送这两者的区别，因此节点不可能永远等待所有N条消息全部送达，至多等待N-f条消息的发送，而这N-f条消息中至少包含N-2f个正确节点。
以Honey Badger BFT为例，传统异步共识协议将ACS问题解耦为可靠广播(RBC)和二值共识(BA)两个部分以得到ACS的高效实现。其中,RBC保证所有的正确节点都会接受同样的值，那些仅由恶意节点广播的值，所有的正确节点要么都接受该值要么都不接受。而BA则是将复杂的是否同意某个提议的共识问题简化为对二值0和1的共识，每个节点都会提出自己的二值提议，最终所有正确节点都会决定同样的值0/1，在BA中，Common Coin是解决节点分歧，避开FLP定理使得协议收敛的手段。在相关一些工作中，也通过实验证明了异步共识协议在更复杂的网络情况下能取得更好的鲁棒性。
但现有异步共识协议仍然存在一些问题，仍然以Honey Badger BFT为例。首先，在每个epoch中，所有节点都需要提出自己的提议，我们将这种范式称为“fix-slot”，也就是每个节点都有一个对应自己的槽位，每个epoch等待节点将交易填充进入槽位后，对这些槽位进行简单的排序后即可得到交易的执行顺序。但这种范式带来的问题就是，在实际场景下，每个节点的工作负载可能是倾斜的，可能一些节点会频繁的收到客户端的请求从而每时每刻都有需要提出的提议，而一些节点可能由于地域性等原因，很少收到来自客户端的请求因此很长一段时间都没有需要提出的协议。而在“fix-slot”范式下，一个epoch需要等待所有正确节点都提出自己的提议填充槽位，这就使得那些工作负载大的节点需要等待那些负载小的节点收到请求然后发起提议，这样整个协议才能推进。同时，为了使得协议能够终止，在BA阶段如果节点确认了最后的输出会包含N-f个1，那么会对剩下的没有决定的提议输入0，这将导致那些慢的提议最终容易被中止。当然，针对这个问题的优化也可以很简单，那就是允许每个节点提出“空提议”，这也是本文后续的优化思路之一。但如果简单的允许“空提议”，会造成低吞吐的出现。这是由于传统异步共识协议中BA阶段会耗费大量的时间，前文也提到，每个epoch仅保证最后的输出包含N-2f个正确节点输入，如果这N-2f里还包含了大量的“空提议”，再加上完成epoch的时间很长，最终系统的性能表现会很差。这也引出了现有异步共识协议的第二个问题，也就是BA阶段耗费时间长的本质原因，即Common Coin阶段的设置，已有工作指出在大规模部署下，Common Coin会使得协议的时间复杂性大大增加。
2 本文贡献
针对上述现有异步共识协议的问题，本文提出了一种基于时间戳（timestamp）的异步共识协议，设计并采用了如下名为“flexible-advancement”的全新范式。
- 每个节点都可以在有未决请求时提出自己的提议（无主）
- 每个节点只有在有挂起的请求时才需要提议（区别于fix-slot范式）
- 当给定时刻只有少数节点有提议时，协议快速推进；当大多数节点都在提议时，协议放慢推进速度以容纳更多提议
在此基础上，本文对传统的BA进行了优化，设计了SuperMA作为MyTumbler的重要组成部件。在SuperMA中，通过快速协商等机制的设计，使得当所有正确节点意见相同时，在BA阶段可以快速绕过Common Coin阶段，从而使得BA阶段能够更快速的终止。
3方案设计
3.1 MyTumbler概览
在正式介绍MyTumbler之前，我们首先从最本质的复制状态机(SMR)协议讨论起。SMR协议需要保证单槽一致性（single-slot consensus），具体来说，SMR协议给每一个提议B分配一个位置𝜑(𝐵)，对所有提议进行排序并按序执行，𝜑(𝐵)可以是一个序列号、轮数、在DAG中的深度等，而在MyTumbler中，𝜑(𝐵)是一个时间戳，这是因为在无主的共识协议中，非常容易出现不同的提议对同一位置𝜑(𝐵)的竞争，如果将𝜑(𝐵)设置为序列号等离散的小整数，那么产生竞争的概率会变得很大，而时间戳从时间尺度上来说是连续的，虽然一些表现形式可能还是整数但本质上能使得产生竞争的概率变小。
回到SMR协议，在给每个提议分配了位置后，接下来要考虑的问题就是什么时候可以执行一个提议（如一个或一批交易）。显然，一种最直观的方案，当且仅当所有𝐵’,𝜑(B’ )<𝜑(𝐵)都已经被执行，B才可以被执行。那么随之带来的问题就是，我们要如何知道所有的满足𝜑(B’ )<𝜑(𝐵)的𝐵’呢？在“fix-slot”范式中，这个问题很简单，因为我们给所有的节点都维护了一个槽位，这些槽位被填满后，最终我们会得到其子集（ACS保证），我们只要简单对其排序即可。而在第2节我们简单介绍了本文提出的“flexible-advancement”范式，在这种范式下，每个节点只有在有挂起的请求时才需要提议，那么我们就没有办法提前获知有哪些提议在当前收到的提议之前，那么我们要如何知道该提议是否可以执行呢？这也是本文的核心问题之一。
换个角度想，我们其实没有必要去知道所有的在当前提议之前的所有提议，我们只需要一个基准，来使得我们知道什么时候执行一个提议是安全的即可。这个思想很类似于Flink系统中的“水位线”(watermark)机制。简单来说， 每个节点维护一个“值”并不断通过某个方式更新这个值，每当这个值得到更新，我们遍历本地所有还未执行但已提交的提议，判断该提议的位置是否在水位线之前，如果是，那么说明该提议可以被安全执行，然后对所有这些可以安全执行的提议按序进行执行即可。这样一来，我们要考虑的问题就从如何知道所有在前的提议转化为了如何更新水位线。在MyTumbler中，通过PASS机制给出了水位线的更新方法，简单来说，为了使得新提交的提议可以被执行，每个节点不断pass一个新位置𝜑(𝐵)，表明该节点承诺不会在𝜑(𝐵)之前接受任何其它新的提议。通过不断更新水位线，水位线下的提议而已被安全执行。但这样的方案同时也带来了一个新的问题，如果一些正确节点认为可以pass一个位置𝜑(𝐵)，而其它一些正确节点已经收到了一个在位置在𝜑(𝐵)之前的提议，如何判断该提议是否应该提交？这不正是BA的作用所在吗？BA的存在可以保证当节点存在分歧的时候，节点最终会得到一致的决定。
在MyTumbler中，由于前面采用的范式与传统的“fix-slot”范式不同，因此整体用来设计异步共识协议的框架也与传统的RBC+BA的框架不同。在MyTumbler中，整个协议被抽象为一种可中止的可靠广播(ARBC)，每个ARBC实例表示为𝑀𝐴(ts,senderID,B)，其中ts表示该实例对应的提议的时间戳，senderID显然就是提议的发起者，而B就是提议本身。如果该实例最终decides的值不为1，则B不会被提交，反之，B被提交。MA实例接受两个外部信号，ENDORSE和ABORT。简单来说，ARBC就是一个多值共识协议到二值共识协议的转化，从外接收两种外部信号ABORT、EDORSE两种信号以及提议本身三个值，然后通过MyTumbler的PASS机制更新水位线，然后根据水位线等信息对所有的提议输入ABORT/ENDORSE信号，然后如果正确节点存在分歧，则进入BA阶段。同时，前文也提到，在MyTumbler中，BA阶段采用了传统BA的优化版本SuperMA，在一些情况下可以绕过Commom Coin阶段实现快速中止。接下来，我们对MyTumbler协议进行更深入的介绍。
3.2 PASS机制与SKIP机制
在正式介绍PASS机制之前，我们先来思考一个问题。在3.1节中我们提到，PASS机制可以认为是节点承诺不接受在𝜑(𝐵)之前任何其它新的提议，但这种承诺是如何生效的呢？显然，只有一个节点承诺不会接受𝜑(𝐵)之前的其它新的提议，不会对整个系统是否接受某个提议造成太大的影响。那么多少个节点承诺才能发挥作用？另外这些承诺为什么能发挥作用？为了解决这个问题，我们进行一些定量的分析。
首先，我们假设有𝑄_p个节点承诺不再接受𝜑(𝐵)之前的提议，那么一个在𝜑(𝐵)之前的提议最多被𝑛−𝑄_𝑝+𝑓个节点接受。假设一个提议要想被提交至少需要被𝑄_𝐴个节点接受。如果这𝑛−𝑄_𝑝+𝑓个节点和上述𝑄_𝐴 个节点至少有f+1个重合，那么至少有一个正确的节点既承诺不再接受𝜑(𝐵)之前的提议，又接受了𝜑(𝐵)之前的提议，这显然是矛盾的。因此，我们只需要合理的对𝑄_p，Q_A进行赋值，就可以使得一个过时的提议不会被提交。这里，我们直接给出𝑄_p=Q_A=N-f=2f+1，在此基础上我们可以定量分析。在这样的设置下，𝑄_p中至少有f+1个正确节点，那么至多有f个正确节点会接受𝜑(𝐵)之前的提议，那么至多有f+f=2f个节点会接受𝜑(𝐵)之前的提议，不可能通过𝑄_𝐴=𝑛−𝑓=2𝑓+1的仲裁。于是在设置Q_A=2f+1的情况下，我们可以得到如下引理，这也是贯彻MyTumbler整个协议设计的思想。
1 | Lemma1. 如果N-f个节点承诺他们不会再接受一个提议B，那么B不可能被提交。 |
有了引理一，我们就可以给出PASS机制的具体设计。我们先给出MyTumbler的一些基础设置以简化后续的讨论。每个节点本地存储当前已经收到的MA实例endorsed、已经提交的MA实例committed、所有节点pass的时间pass_ts、水位线exec_ts，当节点需要提出一个提议时，广播消息<𝑃𝑟𝑜𝑠𝑜𝑠𝑒,𝑡𝑠,𝐵>，其中ts是本地时钟时间戳。其它节点收到后，初始化MA实例，值得注意的是，这里初始化不代表输入信号（ABORT/ENDORSE），如果本地pass的时间pass_ts[i]小于ts，则向该MA实例输入ENDORSE，同时将MA添加到endorsed（这里可以发现，当本地pass的时间pass_ts[i]大于等于ts时，如何对该MA进行处理还未给出，包括是否给予ABORT信号也还未讨论，这会在后面讨论）。如果该MA最终decide 1，则将其添加到committed中。可以发现，在这个过程中，最关键的点在于本地pass的时间pass_ts[i]，这也正是PASS机制所要维护的内容。有了这些基础说明，我们就可以对PASS机制展开进一步的说明。
在某个epoch中，针对第i个节点而言，如果有N-f个不同节点的MA实例被提交，那么取出其中最小的ts作为自己最新的pass的时间戳，pass_ts[i] = ts，然后发送消息<𝑃𝐴𝑆𝑆,𝑖,𝑡𝑠,𝑒𝑛𝑑𝑜𝑟𝑠𝑒𝑑>给所有节点，表明自己承诺不会再接受ts之前的新的提议B，随后节点清空本地endorsed。这里将本地endorsed包含在消息里的好处是可以帮助其它收到该消息的节点发现那些自己还没收到的提议，以促进对应的MA实例更快终止。
但上面的描述事实上存在一个问题，我们前面提到过，MyTumbler采用了“flexible-Advancement”范式，只有节点有需要提出的请求的时候才需要提出请求，也就是说，在某个epoch里，可能提出的请求根本不会达到N-f个，那么也就不会有N-f个MA实例，那么上述“如果有N-f个不同节点的MA实例被提交”是如何满足的呢？这就需要在PASS机制的基础上引入一个互补的SKIP机制。所谓SKIP机制，其实很好理解，如果一个节点i收到一个有效的来自其它节点的proposal，并且此时本地没有挂起的请求，那么它会发送消息<𝑆𝐾𝐼𝑃,𝑖,𝑡𝑠>给其它所有节点，相当于发送一个空的提议来快速跳过这个epoch。这样，我们只需简单对PASS机制的条件进行修改，即“如果有N-f个不同节点的MA实例被提交或发送了skip消息”，那么节点会发送PASS消息。
图1给出了PASS机制的两个具体例子，(a)图中B_0,B_1,…B_3分别由node0,node1,…node3提出，其时间戳分别为ts0~ts3，其中B_0,B_2,B_3已经被提交而B_1因为网络传输问题还未被其它节点收到，node0~node2在收到了N-f=3(这里node3为恶意节点)个提议后发出PASS消息，PASS的时间为最小的时间戳ts0，并附上了它们各自收到的提议，这种情况下几乎所有节点都有提议，因此MyTumbler的epoch整体节奏放慢，包含了更多的提议。而在(b)图中，只有node0，node3发出了提议，并且只有B_0被提交，此时node1,node2在收到B_0后发现本地无需要提出的提议，因此发出了SKIP消息，随后节点在收到2个SKIP消息和一个B_0提议后，满足了N-f=3的要求，因此发出PASS消息，PASS的时间仍为ts0，这种情况下几乎没有节点有提议，MyTumbler能够根据SKIP机制快速推进。
进一步的，基于PASS机制，我们可以得到更新水位线的方式。节点i在收到其它节点的<𝑃𝐴𝑆𝑆,𝑗,𝑡𝑠,𝑒𝑛𝑑𝑜𝑟𝑠𝑒𝑑>后，首先对endorsed中的每个未收到的MA初始化MA实例(不输入)，然后更新pass_ts[j] = ts。随后更新水位线exec_ts为pass_ts中第N-f大的值，这样一来就会有至少N-f个节点承诺不会再接受exec_ts之前的提议B，那么根据引理一，提议B不可能被提交，因此在exec_ts之前的所有提议可以被安全执行。但正如上文提到的，一些提议可能被节点pass但却已经被一些正确节点接受了，那么我们需要通过BA来决定是否接受该提议。因此，节点对所有还未输入，且满足𝑀𝐴.ts≤exec_ts的MA输入ABORT信号来对这些MA的去留进行共识，最后等待所有在水位线之前的所有的未决定的MA decide后，按时间戳顺序执行在水位线之前的committed中的MA包含的提议。这里，我们可以进一步思考，为什么这些“有分歧”的提议可以得到一致的执行或者中止。如果一个提议在最后我们等待的这些未决定的MA中，那么一个MA的decide过程已经保证了最后共识结果的一致性。而如果一个提议不在这些未决的MA中，我们回来头来看PASS消息中包含的endorsed其实就是一个节点本地收到的提议，节点在收到其它节点的PASS消息后，会对其中未收到的MA进行初始化。而现在，一个提议不在这些MA中，说明无论是节点本身还是其它节点的endorsed中都没有该提议，而更新水位线需要N-f个pass消息，因此N-f个节点都没有收到这个提议，那么根据引理一，这个提议不可能被提议，因此无论是那种情况，提议是否被接受或者进一步的执行会得到一致的决定。
3.3 SuperMA
事实上，在3.2节介绍完PASS机制和SKIP机制以及相应的水位线更新机制之后，MyTumbler的整体框架我们已经讨论完成。接下来的问题就剩下MA实例要如何终止。我们之前提到过，MA实例是ARBC的一个具体表示，而ARBC的作用相当于在传统异步共识中的RBC+BA。MyTumbler提出并设计了一种ARBC的高效实现——SuperMA，通过快速协商等方式使得在一些条件下能够绕过BA阶段中的Common Coin阶段，从而使得MA实例能够更快的终止。
首先，我们来回顾传统BA中的一些问题。在传统BA中，每个节点都会针对某件事提出自己的意见（0/1，可以理解为同意或不同意某件事），然后通过一轮广播（BV_Broadcast）过滤掉仅由恶意节点广播的值并收集所有节点的提议。然后从本地收集到的提议中随机选取一个作为本轮的“合法值”并通过一轮广播发送给所有节点。在两轮广播过后，每个节点都得到了全局投票结果的一个局部子集，根据这个子集中包含的“是否产生分歧”和Common Coin抛硬币得到的结果，节点决定decide某个值或者进入下一轮。这个过程是随机性的，虽然从期望上来说运行的轮数是常数（如在Honey Badger BFT中是4轮，其它一些工作优化到了3轮），但是轮数很大的概率依旧存在。事实上，如果我们可以保证所有正确节点都不可能提出某个值，那么完全可以不抛硬币，直接决定就好了，这个思想其实和引理一紧密相关，只要我们通过和引理一中一样的仲裁设置，就可以保证抛硬币阶段只有某些值可以作为合法值。
有了以上的讨论，我们就可以非常轻松地讨论快速协商机制和FastBA，其中FastBA是MyTumbler中BA的优化版本。首先，我们先来介绍快速协商机制，快速协商机制是在进入BA阶段之前针对ENDORSE/ABORT信号的绕过BA阶段的快速路径。之前我们提到，ARBC接受两个外部信号，然而我们还没说明收到这些信号以后节点的行为。具体来说，当收到ENDORSE输入时，节点发送<𝐸𝑁𝐷𝑂𝑅𝑆𝐸,ℎ>，同样，当收到ABORT输入时，节点发送<𝐸𝑁𝐷𝑂𝑅𝑆𝐸,⊥>。如果如果节点收到了N-f条<𝐸𝑁𝐷𝑂𝑅𝑆𝐸,ℎ>，向FastBA输入1，更进一步，如果此时该节点从来没有发送过<𝐸𝑁𝐷𝑂𝑅𝑆𝐸,⊥>，则发送一条<𝑃𝑅𝑂𝑀,ℎ>，收到ABORT信号部分可以和上述内容对称得到。如果节点收到了N-f个
而如果快速协商机制没有成功，节点最终还是会进入BA阶段。MyTumbler对传统的BA进行了优化，设计并实现了FastBA。FastBA和传统BA类似，事实上也是两轮投票加上一轮抛硬币阶段。在第一轮投票中，和传统BA一样，会收集其它节点的提议并过滤仅由恶意节点广播的值。另外，如果节点曾经发送过
图2给出FastBA的两种不同情况，(a)图中node0~node2在收到node3对于0的投票之前就已经收到了各自对于1的投票(N-f=3条)，由于它们从未发送过对0的投票，因此它们分别发送了对于1的承诺，随后在收到了各自的承诺消息后(N-f=3条)，node0~node3完成了对1的decide从而绕过了common coin阶段。(b)图中，node1~node3都发送了对于0和1的投票，因此它们会发送普通的AUX消息，进而后续所有节点不可避免的进入Common Coin阶段，最终经过若干轮后完成了decide。
4 实验验证
4.1 实验设置
本文实验将节点和客户端部署在五大洲，节点设置为8cpu、32GB RAM、5Gbps 网络带宽的Ubuntu 20.04.3 LTS虚拟机。实验的对比Baseline为BKR（即RBC+传统BA，如HB-BFT）、BKR-SuperMA（将BKR的BA换成SuperMA），Tusk（一个最近提出的DAG-based 异步共识协议）和HotStuff（部分同步BFT）。
4.2 Fault-Free下的性能对比
本文首先对没有任何错误（包括崩溃和拜占庭错误）发生情况下各个协议的性能进行了测试。不断增加交易请求发送的速率，该实验测试了不同协议在不同吞吐下的延时。
如图3所示，BKR-SuperMA实现了最小的平均延迟，这表明通过SuperMA现有的异步协议的延迟可以显着减少。而MyTumbler在平均延迟上的表现不是最优的原因在于，相较于传统BKR协议，PASS机制的设置使得其在通信层面多了一轮消息通信，MyTumbler(c1，表示普通的MyTumbler)在适度较高的延迟（多了一轮pass通信）上，实现了更高的tps峰值。实验中发现，Tusk采用了一个节点运行两个进程，一个进程用来传播区块，一个进程用来进行其它任务的方式，取得比其它协议更高的峰值tps，因此对MyTumbler也采用了同样的实现记为c2，获得了最高的tps。通过观察可以发现，BKR在大规模实验中延时发生了巨大的变化，这是因为随机硬币在大规模部署中对于协议时间复杂度的增加，这也说明了绕开随机硬币的重要性。
4.3 仅Crash Fault下的性能
在这部分实验中，本文对仅发生崩溃容错（Crash Fault）的情况下各协议的性能进行了测试。
如图4所示，实验中，MyTumbler获得了最小的平均延时，这是因为BKR需要等待N-f个节点全部提出提议，并且需要给对应的BA instance输入0使其decide而MyTumbler则能更灵活的推进协议。通过观察可以发现，HotStuff几乎没有进展，这源自为提高吞吐量而引入的流水线优化，并且实验设置中选主超时设置为5s（开源实现的默认值），同时也说明异步共识协议鲁棒性更强。
4.4 拜占庭容错下的性能
在这部分实验中，本文对MyTumbler在有恶意节点存在的拜占庭容错环境下的性能进行了测试。实验中，恶意节点的行为为仅将提议传播到f个正确节点，不转发任何提议。设置节点个数为N=10，恶意节点数f=3（弗兰克福的2个节点和加拿大的1个节点是恶意节点）。
如图5所示，实验表明，在拜占庭容错环境下，MyTumbler平均延迟仅适度增加，峰值tps接近于仅Crash Fault，这是由于虽然无法进入快速通道，但是最终SuperMA仍然可以输出0，并且仅有0和1都成为合法值时(n-f)才会进入随机硬币阶段，但恶意节点很难做到精确的消息转发。
4.5 实际场景模拟实验
在这部分实验中，本文对实际应用中的三种不同场景进行了模拟，并对各协议的性能进行了相应的测试。
首先，本文模拟了模拟跨境金融应用，具体场景为一个节点（法兰克福）与其它节点相距较远。
如图6所示，在MyTumbler和BKR中，法兰克福提议的延时相较于其他地区翻倍，但MyTumbler整体取得了最低的延时。由于前三个节点看到法兰克福（较远节点）的提议时，已经进入了下一轮，所以BKR-SuperMA和Tusk没有提交它的区块，因此没有实验数据。本文认为可以对较远的节点的时间戳进行调整，这可以留给未来的工作。
随后，本文模拟了企业对企业电子发票应用程序，具体场景为请求很少发出即工作负载较轻。
如图7所示，MyTumbler具有最小的延时，这是因为pass机制可以更灵活的传递提议并且SuperMA可以跳过随机硬币阶段，而Tusk、BKR等还需要等到N-f个区块才可以完成一个epoch。
最后，本文模拟了跨境汇款应用程序，其中五个区域中只有一个或三个区域有请求，模拟了工作负载不均衡的场景。因为真实活跃的节点数目少于N-f，因此没有请求的区域需要提出空提议。
如图8所示，MyTumbler取得最低的延时，这是因为空闲节点可以由SKIP机制快速跳过。
5 总结
针对现有异步共识协议范式存在的问题，本文提出了一种基于时间戳（timestamp）的异步共识协议，设计并采用了“flexible-advancement”的全新范式，使得协议能够更灵活的根据实际负载场景快速推进。同时，针对传统BA中Common Coin阶段对整体性能带来的影响，本文设计了SuperMA，通过快速协商等方式能在一定条件下绕过Common Coin阶段甚至绕过BA阶段，大大加快协议推进速度，提高了系统性能。
作者：叶哲名，华东师范大学区块链实验室硕士研究生