Shoal：我们如何降低 Aptos 区块链上 Bullshark 的延迟

由 Balaji Arun 和 Alexander Spiegelman 撰写

世界一流的工程技术与 Aptos 的前沿研究相遇。更多详情，请参考Shoal 论文。

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

Shoal 是一个框架，用于通过流水线和领导者声誉来增强任何基于 Narwhal 的共识协议（例如，DAG-Rider、Tusk、Bullshark）。流水线通过每轮引入一个锚点来减少 DAG 排序延迟，领导者声誉通过确保锚点与最快的验证者相关联来进一步改进它。此外，领导者声誉使 Shoal 能够利用异步 DAG 构造来消除所有（但极其罕见）场景中的超时。这使得 Shoal 能够提供我们称之为普遍响应（Prevalent Responsiveness）的属性，该属性包含通常期望的乐观响应（Optimistic Responsiveness）。

我们的技术非常简单，包括按顺序一个接一个地运行底层协议的多个实例。因此，当与 Bullshark 一起实例化时，我们得到一群鲨鱼在进行接力赛跑。

动机

在追求区块链网络高性能的过程中，人们一直专注于降低通信复杂度。然而，这种方法并没有带来吞吐量的显著提高。例如，Hotstuff（在早期版本的 Diem 中实现）仅实现了 3500 TPS，远低于我们 实现 10 万+ TPS 的目标。

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

在之前的一篇文章中，我们介绍了 Quorum Store，我们 Narwhal 的实现，用于将数据传播与共识分离，以及我们如何使用它来扩展我们当前的共识协议 Jolteon。Jolteon 是一种基于领导者的协议，它将 Tendermint 的线性快速路径与 PBFT 风格的视图变更相结合，以将 Hotstuff 的延迟降低 33%。然而，越来越明显的是，基于领导者的共识协议无法完全利用 Narwhal 的吞吐量潜力。尽管将数据传播与共识分离，但随着吞吐量的增加，Hotstuff/Jolteon 中的领导者仍然受到限制。

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

在这篇文章中，我们将介绍 Shoal，并解释我们如何大幅降低 Bullshark 的延迟。

DAG-BFT 背景

让我们从理解这篇文章的相关背景开始。有关 Narwhal 和 Bullshark 的详细描述，请参阅 DAG meets BFT 这篇文章。

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

图 1. 轮次 2 中由验证者 2 标识的顶点的因果历史以绿色高亮显示。

DAG 的一个关键属性是非伪造性：如果两个验证者在其 DAG 的本地视图中具有相同的顶点 v，则它们具有完全相同的 v 的因果历史。

全局排序

无需额外的通信开销，就可以就 DAG 中所有顶点的全局排序达成一致。为了做到这一点，验证者在 DAG-Rider、Tusk 和 Bullshark 中，将 DAG 的结构解释为共识协议，其中顶点代表提案，边代表投票。

虽然 DAG 结构上的仲裁交集逻辑有所不同，但所有现有的基于 Narwhal 的共识协议都具有以下结构：

1. 预定的锚点。 每隔几轮（例如，在 Bullshark 中为两轮），就会有一轮具有预定的领导者。领导者的顶点称为锚点。
2. 对锚点进行排序。 验证者独立但确定性地决定要排序哪些锚点以及要跳过哪些锚点。
3. 对因果历史进行排序。 验证者逐个处理其排序的锚点列表，并且对于每个锚点，通过一些确定性规则对其因果历史中所有先前未排序的顶点进行排序。

图 2. Bullshark 协议中 DAG 可能的本地视图的说明。在此示例中，红色和黄色锚点已排序，而绿色（不在 DAG 中）已跳过。因此，为了对 DAG 进行排序，验证者首先确定性地对红色锚点的因果历史进行排序，然后立即对黄色的因果历史进行排序。

满足安全性的关键是确保在上面的步骤 (2) 中，所有诚实验证者都创建一个排序的锚点列表，以便所有列表共享相同的前缀。在 Shoal 中，我们对所有上述协议进行了以下观察：

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

Bullshark 延迟

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

问题 1：平均区块延迟。 在 Bullshark 中，每隔一轮都有一个锚点，并且每隔一轮中的顶点都被解释为投票。在常见情况下，需要两个 DAG 轮次才能对锚点进行排序。但是，锚点因果历史中的顶点需要更多轮次才能等待锚点被排序。在常见情况下，奇数轮中的顶点需要三轮，而偶数轮中的非锚点顶点需要四轮（参见图 3）。

图3. 在常见情况下，第 i+1 轮中的锚点需要两轮才能排序。第 i 轮中的顶点同时排序，因此它们的延迟为三轮。但是，第 i+1 轮中的顶点必须等待下一个锚点排序（第 i+3 轮中的锚点），因此它们的排序延迟为四轮。

问题 2：故障情况延迟。 上述延迟分析适用于无故障情况。另一方面，如果一轮的领导者未能足够快地广播锚点，则无法对锚点进行排序（因此跳过），因此先前轮次中的所有未排序顶点必须等待下一个锚点排序。这会显著降低异地复制网络中的性能，尤其因为 Bullshark 使用超时来等待领导者。

Shoal 框架

Shoal 解决了这两个延迟问题。它通过流水线增强了 Bullshark（或任何其他基于 Narwhal 的 BFT 协议），这允许每轮都有一个锚点，并将 DAG 中所有非锚点顶点的延迟降低到三轮。Shoal 还在 DAG 中引入了零开销的领导者声誉机制，这使得选择偏向于快速领导者。

挑战

在 DAG 协议的背景下，流水线和领导者声誉被认为是难题，原因如下：

-先前的流水线尝试试图修改核心 Bullshark 逻辑，但这本质上似乎是不可能的。 -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 在第二轮中启动一个新实例，该实例本身有一个锚点。该锚点由该实例排序。然后，另一个新实例在第三轮中对一个锚点进行排序，并且该过程继续。有关说明，请参见下图：

图4. 与由 F 确定的领导者相对应的顶点用皇冠标记。Bullshark 的第一个实例通过解释 DAG 来开始，其中锚点位于第 1、3 和 5 轮中。Bullshark 确定第 1 轮中的锚点（用绿色复选标记标记）是第一个在第一个实例中排序的锚点。（请注意，在一般情况下，可以跳过此锚点，而其他一些锚点将是第一个排序的锚点。）然后，忽略第一个实例的其余部分，并在第 2 轮中从 Bullshark 的一个新实例开始，其中锚点标记在第 2 轮和第 4 轮中。

领导者声誉

当在 Bullshark 排序期间跳过锚点时，延迟会增加。在这种情况下，流水线技术无法提供帮助，因为在上一个实例对锚点进行排序之前，无法启动新实例。Shoal 通过确保使用声誉机制根据验证者最近活动的记录为每个验证者分配一个分数，从而使相应的领导者在未来不太可能被选中来处理错过的锚点。响应迅速并参与协议的验证者将被分配一个高分。否则，验证者将被分配一个低分，因为它可能已崩溃、速度慢或恶意。

这个想法是每次更新分数时，确定性地重新计算从轮次到领导者的预定义映射 F，从而偏向于得分较高的领导者。为了使验证者对新映射达成一致，他们应该对分数达成一致，因此也应对用于得出分数的历史记录达成一致。

在 Shoal 中，流水线和领导者声誉可以自然地结合在一起，因为它们都利用了在同意第一个排序的锚点之后重新解释 DAG 的相同核心技术。

实际上，唯一的区别是，在第 r 轮中对锚点进行排序之后，验证者只需根据第 r 轮中排序锚点的因果历史，从第 r+1 轮开始计算新的映射 F’。然后，验证者从第 r+1 轮开始使用更新的锚点选择函数 F’ 执行 Bullshark 的一个新实例。请参见下图的说明：

图 5. 与由 F 确定的领导者相对应的顶点用透明的皇冠标记。Bullshark 的第一个实例在第 1 轮中对锚点进行排序，并用绿色复选标记标记。然后，根据锚点因果历史中的信息计算新的映射 F’。由 F’ 确定的领导者用彩色的皇冠标记。

不再需要超时！

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

超时也会显著增加延迟，因为适当地配置它们并非易事，并且通常需要根据环境（网络）动态调整。协议会为有故障的领导者支付完整的超时延迟惩罚，然后才能转移到下一个领导者。因此，超时不能设置得过于保守。但是，如果超时太短，则协议可能会跳过良好的领导者。例如，我们观察到，在高负载下，Jolteon/Hotstuff 中的领导者不堪重负，并且超时在其能够推动进度之前过期。

不幸的是，基于领导者的协议（如 Hotstuff 和 Jolteon）本质上需要超时，以确保每次领导者出现故障时协议都能取得进展。如果没有超时，即使是崩溃的领导者也可能会永远阻止协议。由于在异步期间不可能区分有故障的领导者和速度较慢的领导者，因此超时可能会导致验证者在没有共识活跃度的情况下查看所有领导者。

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

我们观察到 DAG 构造提供了一个“时钟”，用于估计网络速度。如果没有超时，只要 n-f 个诚实的验证者继续将顶点添加到 DAG 中，轮次就会不断前进。虽然 Bullshark 可能无法按网络速度进行排序（由于领导者出现故障），但即使某些领导者出现故障或网络处于异步状态，DAG 仍会按网络速度增长。最终，当无故障领导者足够快地广播锚点时，将对锚点的整个因果历史进行排序。

在我们的评估中，我们在以下情况下比较了有和没有超时的 Bullshark：

-快速领导者，意味着比至少 f 个其他验证者更快。在这种情况下，两种方法都提供相同的延迟，因为对锚点进行了排序，并且未使用超时。 -有故障的领导者。在这种情况下，没有超时的 Bullshark 提供更好的延迟，因为验证者将立即跳过其锚点，而使用超时的验证者将等待其过期后再继续。 -慢速领导者。这是唯一一个使用超时的 Bullshark 性能会更好的情况。这是因为，如果没有超时，锚点很可能会被跳过，因为领导者将无法足够快地广播锚点，而使用超时的验证者将等待锚点。

在 Shoal 中，避免超时和领导者声誉是齐头并进的。领导者声誉机制不是重复等待速度较慢的领导者并因此而增加延迟，而是将速度较慢的验证者排除在被选为领导者的行列之外。这样，系统可以利用快速验证者在所有实际场景中以网络速度运行。

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

普遍响应性

Hotstuff 论文普及了乐观响应性的概念。尽管没有正式定义，但直观上讲，这意味着该协议可以在包括快速领导者和同步网络的良好情况下以网络速度运行。

Shoal 提供了一个严格更好的属性，我们将其称为 普遍响应性。具体而言，与 Hotstuff 相比，即使领导者在可配置数量的连续轮次中失败，或者网络遇到异步期间，Shoal 仍继续以网络速度运行。请参阅下表中的更详细的比较。

请注意，在异步期间以及领导者出现故障时，普遍响应性 提供了严格更好的进度保证。在与速度较慢的领导者同步期间，这些属性无法比较，因为它取决于领导者有多慢。但是，借助领导者声誉，速度较慢的领导者很少出现在 Shoal 中。

评估

我们在 Quorum Store（我们的 Narwhal 实现）之上实现了 Bullshark 和 Shoal。有关 Shoal、Bullshark 和 Jolteon 之间的详细比较，请参见 Shoal 论文 的评估部分。在这里，我们提供一些亮点。

首先，为了证明异步 DAG 构造的能力，我们比较了有和没有超时的 Bullshark。完整的 Bullshark 论文 假设了一个异步网络，但由于所有轮次都需要超时，因此提供了快速路径模式。我们将此版本称为 Vanilla Bullshark。我们观察到，对于独立的部分同步网络假设版本，投票轮次中的超时不是必需的。我们将此版本称为 Vanilla Bullshark w/o Vote timeout。基线 Bullshark 是没有任何超时的版本。

下图比较了超时对有和没有故障的 Bullshark 延迟的影响。显然，基线 Bullshark（没有超时）在存在故障的情况下表现最佳。在无故障的情况下，基线 Bullshark 与 Vanilla Bullshark w/o Vote timeout 相当。这是因为，如前所述，如果没有领导者声誉机制，超时在良好但速度较慢的领导者的情况下可能具有优势。

图 6. 没有故障（左）和有故障（右）的情况下超时对 Bullshark 延迟的影响。在故障情况下，有 50 个验证者。

接下来，我们使用基线 Bullshark（没有超时）实例化 Shoal，并演示了有和没有故障的情况下，流水线和领导者声誉机制的延迟改进。为了完整起见，我们还在无故障的情况下将其与 Jolteon 进行了比较。

下图 7 显示了无故障的情况。虽然流水线和领导者声誉都可以单独降低延迟，但将它们组合在一起可以实现最佳的延迟。

至于 Jolteon，它无法扩展到 20 个以上的验证者，并且即使它在消除了数据传播瓶颈的 Quorum Store 之上运行，也只能实现大约一半的 Bullshark/Shoal 吞吐量。

结果表明，Shoal 显著改善了 Bullshark 的延迟。至于 Jolteon，重要的是要注意，我们仅测量了共识延迟。由于 Jolteon 无法在 DAG 之上本地运行，因此它需要额外的延迟来分离数据传播，而我们没有测量。因此，在高负载下，Shoal 应该与 Jolteon 的端到端延迟相匹配。

图 7. 无故障情况下的吞吐量和延迟。Shoal PL 和 Shaol LR 分别仅支持流水线和领导者声誉。

下图 8 显示了有 50 个验证者的故障情况，其中领导者声誉机制通过降低被选为领导者的失败验证者的可能性来显著改善延迟。请注意，在 50 个故障中有 16 个的情况下，Shoal 实现的延迟比基线 Bullshark 低 65%。

图 8. 有 50 个验证者的故障情况下的延迟。

世界一流的工程技术与 Aptos 的前沿研究相遇。更多详情，请参考Shoal 论文。

• 原文链接： medium.com/aptoslabs/sho...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～