减少Aptos上Bullshark延迟:Shoal框架详解

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

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

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

背景

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

近期突破源于认识到数据传播是基于领导者协议的主要瓶颈,可从并行化中受益。Narwhal系统将数据传播与核心共识逻辑分离,所有验证者同时传播数据,共识组件仅排序少量元数据。Narwhal论文报告了160,000 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结构解释为共识协议,顶点代表提案,边代表投票。

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

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

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

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

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

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

Bullshark延迟

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

问题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)本质上需要超时,以确保每次领导者故障时协议能取得进展。没有超时,即使是崩溃的领导者也可能永远停止协议。由于在异步期间无法区分有故障和缓慢的领导者,超时可能导致验证节点在没有共识活跃度的情况下查看更改所有领导者。

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

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

评估中,我们比较了Bullshark在以下情况下有无超时:

1. 快速领导者,至少比其他验证者更快。这种情况下,两种方法提供相同延迟,因为锚是有序的且不使用超时。

2. 错误的领导者,这种情况下,无暂停的Bullshark提供更好延迟,因为验证节点将立即跳过其锚点,而有暂停的验证者将在继续前等待它们到期。

3. 缓慢的领导者,这是Bullshark超时性能更好的唯一情况。因为无暂停时,锚点可能被跳过,因为领导者无法足够快地广播它,而有暂停时,验证者将等待锚点。

在Shoal中,避免超时和领导者信誉密切相关。重复等待