Shoal框架解析:大幅降低Aptos上的Bullshark延迟

Aptos Labs近期解决了DAG BFT中两个关键问题,显著降低了延迟,并首次在确定性实时协议中消除了对超时的需求。总体而言,在无故障情况下Bullshark的延迟改进了40%,在故障情况下改进了80%。

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

该技术非常简单,涉及按顺序运行底层协议的多个实例。使用Bullshark实例化时,相当于一群"鲨鱼"在进行接力赛。

背景与动机

在追求区块链网络高性能时,降低通信复杂性一直是关注重点。然而,这种方法并未带来显著的吞吐量提升。例如,早期Diem中实现的Hotstuff仅达到3500 TPS,远低于10万+ TPS的目标。

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

Aptos之前介绍了Quorum Store,即Narwhal实现,将数据传播与共识分离,用于扩展当前的Jolteon共识协议。Jolteon结合了Tendermint的线性快速路径和PBFT风格的视图变更,可将Hotstuff延迟降低33%。然而,基于领导者的共识协议无法充分利用Narwhal的吞吐量潜力。

因此,Aptos决定在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结构解释为一种共识协议,其中顶点代表提案,边代表投票。

所有基于Narwhal的共识协议都具有以下结构:

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

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

3. 排序因果历史:验证者依次处理有序锚点列表,对每个锚点的因果历史中先前无序的顶点进行排序。

安全性的关键是确保在步骤(2)中,所有诚实验证节点创建的有序锚点列表共享相同前缀。Shoal观察到:所有验证者都同意第一个有序的锚点。

Bullshark延迟

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

主要存在两个问题:

1. 平均块延迟:常见情况下,奇数轮顶点需要三轮,偶数轮非锚点顶点需要四轮才能排序。

2. 故障情况延迟:如果某轮领导者未能及时广播锚点,导致锚点无法排序而被跳过,前几轮未排序的顶点必须等待下一个锚点排序。这显著降低了地理复制网络的性能。

Shoal框架

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

挑战

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

1. 之前的流水线尝试修改核心Bullshark逻辑,但这本质上似乎不可能。

2. 领导者声誉在DiemBFT中引入、Carousel中正式化,根据验证者过去表现动态选择未来领导者(Bullshark中的锚点)。虽然领导者身份分歧不违反安全性,但在Bullshark中可能导致完全不同的排序。

这些挑战导致目前生产环境中的Bullshark实现都不支持这些特性。

协议

Shoal依靠在DAG上执行本地计算的能力,实现保存和重新解释前几轮信息的能力。基于所有验证者都同意第一个有序锚点的洞察,Shoal按顺序组合多个Bullshark实例进行流水线处理,使得:

1. 第一个有序锚点是实例的切换点
2. 锚点的因果历史用于计算领导者声誉

流水线

验证者先验地就潜在锚点达成一致,即有一个已知映射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实现中起关键作用。然而,它们引入的复杂性增加了需要管理和观察的内部状态数量,增加了调试复杂性,需要更多可观察性技术。

超时也显著增加延迟,因为适当配置超时很重要,通常需要动态调整,高度依赖环境(网络)。在切换到下一个领导者之前,协议会为有故障的领导者支付完整的超时延迟惩罚。因此,超时设置不能过于保守,但如果太短,协议可能跳过好的领导者。

不幸的是,基于领导者的协议(如Hotstuff和Jolteon)本质上需要超时,以确保每次领导者出现故障时协议都能取得进展。没有超时,即使是崩溃的领导者也可能永远停止协议。由于在异步期间无法区分有故障和缓慢的领导者,超时可能导致验证节点在没有共识活跃度的情况下轮换所有领导者。

在Bullshark中,超时用于DAG构造,以确保在同步期间诚实领导者足够快地将锚点添加到DAG以便排序。

Shoal观察到DAG构造提供了估计网络速度的"时钟"。在无暂停情况下,只要n-f个诚实验证者继续向DAG添加顶点,轮次就会继续前进。虽然Bullshark可能无法以网络速度排序(由于领导者问题),但DAG仍以网络速度增长,尽管一些领导者有问题或网络异步。最终,当无故障领导者足够快地广播锚点时,锚点的整个因果历史将被排序。

在Shoal中,避免超时和领导者声誉密切相关。重复等待缓慢领导者会增加延迟,领导者声誉机制排除了缓慢验证者被选为领导者。通过这种方式,系统利用快速验证节点在所有现实场景中以网络速度运行。

需要注意,FLP不可能性结果表明没有确定性共识协议可以避免超时。Shoal不能规避这个结果,因为存在理论上的对抗性事件时间表可以阻止所有锚被排序。相反,在可配置的连续跳过锚点数量后,Shoal会退回到超时。实际上,这种情况极不可能发生。

通用响应性

Hotstuff论文普及了乐观响应的概念,虽未正式定义,但直观上意味着协议可以在良好情况(快速领导者和同步网络)下以网络速度运行。

Shoal提供了更好的属性,称为通用响应性。具体来说,与Hotstuff相比,即使领导者在可配置的连续轮数内失败或网络经历异步周期,Shoal也会继续以网络速度运行。

通用响应性在异步期间和领导者出现故障时提供了严格更好的进度保证。在与慢速领导者同步期间,这些属性无法比较,因为取决于领导者有多慢。然而,考虑到领导者声誉,Shoal中慢速领导者应该很少出现。

评估

Aptos在Narwhal实现Quorum Store之上实现了Bullshark和Shoal。下面提供一些评估亮点:

首先,为演