Shoal框架:如何减少Aptos上的Bullshark延迟?

概述

Aptos labs解决了DAG BFT中两个重要的开放问题,大幅减少了延迟,首次消除了确定性实际协议中对暂停的需求。总体上,在无故障情况下将Bullshark的延迟改进了40%,在故障情况下改进了80%。

Shoal是一个通过流水线和领导者声誉增强基于Narwhal的共识协议的框架。流水线通过每轮引入锚点来减少DAG排序延迟,领导者声誉通过确保锚点与最快的验证节点关联来进一步改善延迟。此外,领导者声誉使Shoal可以利用异步DAG构造来消除所有场景中的超时。这允许Shoal提供普遍响应的属性,包含通常需要的乐观响应。

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

动机

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

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

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

因此决定在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. 排序因果历史:验证者一个一个处理有序锚点列表,对每个锚点的因果历史中所有先前无序顶点进行排序。

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

Bullshark延迟

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

主要有两个问题:

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

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

Shoal框架

Shoal通过流水线增强Bullshark,允许每轮有一个锚点,将所有非锚点顶点的延迟减少到三轮。Shoal还引入了零开销领导者声誉机制,偏向选择快速领导者。

挑战

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

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

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

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

协议

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

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

流水线

Shoal一个接一个运行Bullshark实例,每个实例订购一个锚,触发切换到下一个实例。

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

理想情况下,这允许Shoal每轮订购一个锚点。

领导者声誉

当Bullshark跳过锚点时,延迟会增加。Shoal通过声誉机制为每个验证节点分配分数,确保将来不太可能选择缓慢的领导者。

在每次分数更新时,确定性地重新计算从轮次到领导者的映射F,偏向高分领导者。为了让验证者在新映射上达成一致,他们应该在分数上达成一致。

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

无需超时

超时在基于leader的确定性部分同步BFT实现中起关键作用,但引入了复杂性并显著增加延迟。

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

避免超时和领导声誉密切相关。重复等待缓慢领导者会增加延迟,而声誉机制排除了缓慢验证者被选为领导者。

普遍响应

Shoal提供了普遍响应的属性,即使在领导者失败或网络异步的情况下也能以网络速度运行。这优于Hotstuff的乐观响应概念。

评估

实现了Bullshark和Shoal,并与Jolteon进行了比较。主要发现:

1. 无超时的Baseline Bullshark在出现故障时表现最佳。

2. Shoal的流水线和领导者声誉机制显著改善了Bullshark延迟。

3. 在50次失败中有16次失败时,Shoal的延迟比Baseline Bullshark低65%。

4. Jolteon无法扩展到超过20个验证节点,吞吐量约为Bullshark/Shoal的一半。

总的来说,Shoal极大地改善了Bullshark延迟,在高负载下应该可以与Jolteon的端到端延迟相匹配。