Shoal框架:提升Aptos区块链性能的创新方案

Aptos Labs近期提出了Shoal框架,旨在解决DAG BFT共识中的两个关键问题,显著降低延迟并首次消除了确定性异步协议中对超时的依赖。总体而言,Shoal在无故障情况下将Bullshark的延迟提高了40%,在故障情况下提高了80%。

Shoal通过流水线和领导者声誉机制来增强基于Narwhal的共识协议(如DAG-Rider、Tusk、Bullshark等)。流水线技术通过每轮引入一个锚点来减少DAG排序延迟,领导者声誉机制则通过确保锚点与最快的验证节点相关联来进一步改善延迟。此外,领导者声誉使Shoal能够利用异步DAG构建来消除所有场景中的超时,从而实现了普遍响应性。

Shoal的核心思路是按顺序运行底层协议的多个实例。以Bullshark为例,可以将其想象成一群正在接力赛跑的"鲨鱼"。

动机

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

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

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

因此,Aptos决定在Narwhal DAG之上部署Bullshark,一种零通信开销的共识协议。但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. 排序因果历史:验证者逐个处理有序锚点列表,对每个锚点的因果历史中之前未排序的顶点进行排序。

满足安全性的关键是确保所有诚实验证节点创建的有序锚点列表共享相同的前缀。Shoal对所有这些协议做出一个重要观察:所有验证者都同意第一个有序锚点。

Bullshark的延迟问题

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

主要存在两个问题:

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

2. 故障情况延迟:如果一轮的领导者未能及时广播锚点,该锚点将被跳过,前几轮所有未排序顶点必须等待下一个锚点排序。这显著降低了地理分布网络的性能,尤其是因为Bullshark使用超时等待领导者。

Shoal框架

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

挑战

在DAG协议中实现流水线和领导者声誉被认为是困难的:

1. 之前尝试修改Bullshark核心逻辑似乎不可行。

2. 领导者声誉可能导致不同的排序,而验证者需要就有序历史达成一致以选择未来锚点。

作为问题难度的佐证,目前生产环境中的Bullshark实现都不支持这些特性。

协议

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

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

流水线

与Bullshark类似,验证者预先就潜在锚点达成一致,即有一个已知映射F:R->V将轮次映射到领导者。Shoal按顺序运行Bullshark实例,每个实例排序一个锚点并触发切换到下一个实例。

Shoal从DAG第一轮启动Bullshark第一个实例,直到确定第一个有序锚点(假设在第r轮)。所有验证者都同意这个锚点,因此可以确定性地同意从r+1轮重新解释DAG。Shoal在r+1轮启动新的Bullshark实例。

理想情况下,这允许Shoal每轮排序一个锚点。第一轮锚点由第一个实例排序,然后在第二轮开始新实例排序该轮锚点,以此类推。

领导者声誉

当Bullshark跳过锚点时,延迟会增加。流水线技术在这种情况下无能为力,因为必须等前一个实例排序锚点才能启动新实例。Shoal通过声誉机制为每个验证节点分配分数,根据其最近活动历史。响应迅速的验证者获得高分,否则获得低分。

理念是在每次分数更新时,确定性地重新计算从轮次到领导者的映射F,偏向高分领导者。为使验证者在新映射上达成一致,他们需要在分数上达成一致,进而在用于派生分数的历史上达成一致。

在Shoal中,流水线和领导者声誉可以自然结合,因为它们都基于在第一个有序锚点达成一致后重新解释DAG。唯一的区别是,在第r轮排序锚点后,验证者根据该锚点的因果历史从r+1轮开始计算新映射F'。然后从r+1轮开始使用更新后的F'执行新的Bullshark实例。

消除超时

超时在所有基于领导者的确定性部分同步BFT实现中都很关键。然而,它们增加了复杂性,需要更多的内部状态管理和观察,使调试更加困难。

超时还会显著增加延迟,因为正确配置很重要,且通常需要动态调整。在切换到下一个领导者之前,协议要为有故障的领导者支付完整的超时延迟惩罚。因此,超时设置不能过于保守,但如果太短又可能跳过好的领导者。

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

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

我们观察到DAG构建提供了一个估计网络速度的"时钟"。只要n-f个诚实验证者继续向DAG添加顶点,轮次就会前进。虽然Bullshark可能无法以网络速度排序,但DAG仍以网络速度增长。最终,当一个无故障领导者足够快地广播锚点时,锚点的整个因果历史将被排序。

在评估中,我们比较了有无超时的Bullshark:

1. 快速领导者:两种方法延迟相同,因为锚点被排序且不使用超时。

2. 错误的领导者:无超时Bullshark延迟更低,因为验证节点会立即跳过其锚点。

3. 缓慢的领导者:有超时Bullshark表现更好,因为验证者会等待锚点,而无超时可能跳过锚点。

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

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

普遍响应性

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

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

普遍响应性在异步期间和领导者故障时提供了严格更好的进度保证。在与慢速领导者同步期间,这些特性无法直接比较,因为取决于领导者的速度。但考虑到领导者声誉机制,Shoal中缓慢领导者应该很少出现。

![万字详解Shoal框架：如何减