Shoal框架:降低Aptos上Bullshark延迟的新方案

Aptos Labs最近解决了DAG BFT中两个重要的开放问题,显著降低了延迟,并首次在确定性实用协议中消除了对超时的需求。总的来说,在无故障情况下将Bullshark的延迟改进了40%,在故障情况下改进了80%。

Shoal是一个通过流水线处理和领导者声誉机制来增强基于Narwhal的共识协议(如DAG-Rider、Tusk、Bullshark)的框架。流水线处理通过在每轮引入锚点来减少DAG排序延迟,领导者声誉机制通过确保锚点与最快的验证节点相关联来进一步改善延迟问题。此外,领导者声誉使Shoal能够利用异步DAG构建来消除所有场景中的超时。这使得Shoal能够提供称为"普遍响应"的属性,它包含了通常需要的乐观响应。

Shoal的技术相当简单,涉及按顺序一个接一个地运行底层协议的多个实例。因此,当使用Bullshark实例化时,我们得到了一群进行接力赛的"鲨鱼"。

背景

在追求区块链网络高性能时,人们一直关注降低通信复杂性。然而,这种方法并没有导致吞吐量的显著提高。例如,在早期版本的Diem中实现的Hotstuff仅实现了3500 TPS,远低于我们100k+ TPS的目标。

近期的突破源于认识到数据传播是基于领导者的协议的主要瓶颈,可以从并行化中受益。Narwhal系统将数据传播与核心共识逻辑分离,提出了一种架构,所有验证者同时传播数据,而共识组件仅排序较少量的元数据。Narwhal论文报告了160,000 TPS的吞吐量。

我们的Narwhal实现Quorum Store将数据传播与共识分离,用于扩展当前的共识协议Jolteon。Jolteon是一种基于领导者的协议,结合了Tendermint的线性快速路径和PBFT风格的视图变更,可将Hotstuff延迟降低33%。然而,基于领导者的共识协议无法充分利用Narwhal的吞吐量潜力。尽管将数据传播与共识分开,随着吞吐量增加,Hotstuff/Jolteon的领导者仍然受到限制。

因此,我们决定在Narwhal DAG之上部署Bullshark,一种零通信开销的共识协议。不幸的是,与Jolteon相比,支持Bullshark高吞吐量的DAG结构带来了50%的延迟代价。

本文介绍了Shoal如何大幅减少Bullshark延迟。

DAG-BFT背景

Narwhal DAG中的每个顶点都与一个轮数相关联。为进入第r轮,验证者必须首先获得属于第r-1轮的n-f个顶点。每个验证者每轮可广播一个顶点,每个顶点至少引用前一轮的n-f个顶点。由于网络异步性,不同验证者可能在任何时间点观察到DAG的不同本地视图。

DAG的一个关键属性不是模棱两可的:如果两个验证节点在它们的DAG本地视图中具有相同的顶点v,那么它们具有完全相同的v因果历史。

总序

可以在没有额外通信开销的情况下就DAG中所有顶点的总序达成一致。为此,DAG-Rider、Tusk和Bullshark中的验证者将DAG的结构解释为一种共识协议,其中顶点代表提案,边代表投票。

虽然DAG结构上的群体交集逻辑不同,但所有现有的基于Narwhal的共识协议都具有以下结构:

1. 预定锚点:每隔几轮就会有一个预先确定的领导者,领导者的顶点称为锚点。

2. 排序锚点:验证者独立但确定性地决定排序哪些锚点以及跳过哪些锚点。

3. 排序因果历史:验证者一个一个地处理有序锚点列表,对于每个锚点,通过确定性规则对其因果历史中所有先前无序的顶点进行排序。

满足安全性的关键是确保在步骤(2)中,所有诚实的验证节点创建一个有序锚点列表,以便所有列表共享相同的前缀。在Shoal中,我们对上述所有协议做出以下观察:

所有验证者都同意第一个有序的锚点。

Bullshark延迟

Bullshark的延迟取决于DAG中有序锚点之间的轮数。虽然Bullshark最实用的部分同步版本比异步版本具有更好的延迟,但它远非最佳。

问题1:平均块延迟。在Bullshark中,每个偶数轮都有一个锚点,每个奇数轮的顶点都被解释为投票。常见情况下,需要两轮DAG才能排序锚点,然而,锚点的因果历史中的顶点需要更多轮次来等待锚点被排序。在常见情况下,奇数轮中的顶点需要三轮,而偶数轮中的非锚点顶点需要四轮。

问题2:故障案例延迟,上述延迟分析适用于无故障情况,另一方面,如果一轮的领导者未能足够快地广播锚点,则无法对锚点进行排序(因此被跳过),因此前几轮中所有未排序的顶点必须等待下一个锚点被排序。这会显著降低地理复制网络的性能,特别是因为Bullshark使用超时来等待领导者。

Shoal框架

Shoal通过流水线处理增强了Bullshark(或任何其他基于Narwhal的BFT协议),允许在每一轮中都有一个锚点,并将DAG中所有非锚点顶点的延迟减少到三轮。Shoal还在DAG中引入了零开销领导者声誉机制,这使得选择偏向于快速领导者。

挑战

在DAG协议背景下,流水线处理和领导者声誉被认为是困难的问题,原因如下:

1. 以前的流水线处理试图修改核心Bullshark逻辑,但这从本质上讲似乎是不可能的。

2. 领导者声誉在DiemBFT中引入并在Carousel中正式化,是根据验证者过去的表现动态选择未来领导者(Bullshark中的锚)的想法。虽然在领导者身份上存在分歧并不违反这些协议中的安全性,但在Bullshark中,它可能导致完全不同的排序,这引出了问题的核心,即动态和确定性地选择轮锚是解决共识所必需的,而验证者需要就有序历史达成一致以选择未来的锚。

作为问题难度的证据,我们注意到Bullshark的实现,包括目前在生产环境中的实现,都不支持这些特性。

协议

尽管存在上述挑战,但事实证明解决方案隐藏在简单之中。

在Shoal中,我们依靠在DAG上执行本地计算的能力,并实现了保存和重新解释前几轮信息的能力。凭借所有验证者都同意第一个有序锚点的核心洞察力,Shoal按顺序组合多个Bullshark实例对它们进行流水线处理,使得(1)第一个有序锚点是实例的切换点,以及(2)锚点的因果历史用于计算领导者的声誉。

流水线处理

与Bullshark类似,验证者先验地就潜在的锚点达成一致,即,有一个已知的映射F:R -> V将轮次映射到领导者。Shoal一个接一个地运行Bullshark的实例,这样对于每个实例,锚由映射F预先确定。每个实例都排序一个锚,这会触发切换到下一个实例。

最初,Shoal在DAG的第一轮启动Bullshark的第一个实例并运行它直到确定第一个有序锚点,比如在第r轮。所有验证者都同意这个锚点。因此,所有验证者都可以确定地同意从第r+1轮开始重新解释DAG。Shoal只是在第r+1轮启动了一个新的Bullshark实例。

在最好的情况下,这允许Shoal在每一轮都排序一个锚。第一轮的锚点按第一个实例排序。然后,Shoal在第二轮开始一个新的实例,它本身有一个锚点,该锚由该实例排序,然后,另一个新实例在第三轮中排序锚点,然后该过程继续。

领导者声誉

在Bullshark排序期间跳过锚点时,延迟会增加。在这种情况下,流水线处理技术无能为力,因为在前一个实例排序锚点之前无法启动新实例。Shoal通过使用声誉机制根据每个验证节点最近活动的历史为每个验证节点分配一个分数来确保将来不太可能选择相应的领导者来处理丢失的锚点。响应并参与协议的验证者将获得高分,否则,验证节点将被分配低分,因为它可能崩溃、缓慢或作恶。

其理念是在每次分数更新时,确定性地重新计算从回合到领导者的预定义映射F,偏向于得分较高的领导者。为了让验证者在新的映射上达成一致,他们应该在分数上达成一致,从而在用于派生分数的历史上达成一致。

在Shoal中,流水线处理和领导者声誉可以自然结合,因为它们都使用相同的核心技术,即在就第一个有序锚点达成一致后重新解释DAG。

事实上,唯一的区别是,在第r轮中对锚点进行排序后,验证者只需根据第r轮中有序锚点的因果历史,从第r+1轮开始计算新的映射F'。然后,验证节点从第r+1轮开始使用更新的锚点选择函数F'执行Bullshark的新实例。

没有更多超时

超时在所有基于领导者的确定性部分同步BFT实现中起着至关重要的作用。然而,它们引入的复杂性增加了需要管理和观察的内部状态的数量,这增加了调试过程的复杂性,并且需要更多的可观察性技术。

超时也会显著增加延迟,因为适当地配置它们非常重要,并且通常需要动态调整,因为它高度依赖于环境(网络)。在转移到下一个领导者之前,该协议会为有故障的领导者支付完整的超时延迟惩罚。因此,超时设置不能过于保守,但如果超时时间太短,协议可能会跳过好的领导者。例如,我们观察到,在高负载情况下,Jolteon/Hotstuff中的领导者不堪重负,并且在他们推动进展之前超时就已到期。

不幸的是,基于领导者的协议(如Hotstuff和Jolteon)本质上需要超时,以确保每次领导者出现故障时协