Narwhal 和 Tusk：基于 DAG 的内存池和高效的 BFT 共识

George Danezis Mysten Labs & UCL. Alberto Sonnino Mysten Labs

Lefteris Kokoris-Kogias IST Austria. Alexander Spiegelman Aptos

摘要

我们建议将可靠的交易传播任务与交易排序分开，以实现高性能的拜占庭容错基于仲裁的共识。
我们设计并评估了一个 mempool 协议 Narwhal，该协议专门用于高吞吐量可靠传播和交易因果历史的存储。
Narwhal 可以容忍异步网络并在出现故障的情况下保持高性能。 Narwhal 的设计目的是在每个验证节点上使用多个工作线程轻松扩展，我们证明我们可以实现的吞吐量没有可预见的限制。

将 Narwhal 与部分同步的共识协议 (Narwhal-HotStuff) 组合在一起，即使在存在故障或由于异步导致的间歇性失去活力的情况下，也能产生明显更好的吞吐量。
但是，失去活性会导致更高的延迟。为了在发生故障时获得整体良好的性能，我们设计了 Tusk，一个零消息开销的异步共识协议，与 Narwhal 一起工作。我们展示了它在各种配置和故障下的高性能。

作为结果总结，在 网络上，Narwhal-Hotstuff 在不到 2 秒的延迟下实现了超过 130,000 次/秒的传输，而 Hotstuff 在 1 秒的延迟下实现了 1,800 次/秒的传输。
额外的工作人员将吞吐量线性增加到 600,000 tx/秒，而没有任何延迟增加。
Tusk 以大约 3 秒的延迟达到 160,000 tx/秒。在故障情况下，两种协议都保持高吞吐量，但 Narwhal-HotStuff 的延迟增加。

简介

用于构建可靠分布式系统的拜占庭共识协议 [15, 19, 21] 和状态机复制范式 [13] 已经研究了 40 多年。
然而，随着区块链的普及，人们对设计高性能共识协议重新产生了兴趣。具体来说，为了提高比特币 [33] 仅 4 tx/sec 的吞吐量，早期工作 [29] 建议基于委员会的共识协议。
对于更高的吞吐量和更低的延迟，需要基于委员会的协议，并且现在正在成为POS证明设计的规范。
提高分布式账本性能的现有方法侧重于创建成本更低的共识算法，最终以 Hotstuff [38] 为顶点，该算法在部分同步设置中实现了线性消息复杂性。
为了实现这一点，Hotstuff 利用收集、聚合和广播其他验证者消息的领导者。然而，理论上的消息复杂度不应该是唯一的优化目标。进一步来说：

• 任何（部分同步）协议最小化整体消息数量，但依赖于领导者产生提案和协调共识，无法捕捉这对不可避免地成为瓶颈的领导者施加的高负载。
• 消息复杂度计算元数据消息（例如，投票、签名、哈希）的数量，与散装交易数据（块）的传播相比，这些消息占用的带宽最少。 由于块比典型的共识消息（100B）大几个数量级（10MB），渐近消息复杂性实际上被固定的中型委员会（最多 50 个节点）分摊。

此外，共识协议已经将许多功能组合成一个单一的协议。
在典型的分布式账本中，例如比特币或 LibraBFT1 [12]，客户端将交易发送到使用 Mempool 协议共享它们的验证者。
然后，这些交易的一个子集会定期重新共享并作为共识协议的一部分提交。迄今为止，大多数研究旨在提高共识层的吞吐量。

本文提出了以下假设：更好的内存池，可靠地分配交易，是高性能分类账的关键推动者。它应该完全从共识协议中分离出来，让共识只剩下订购小型固定大小参考的工作。这导致整个系统的吞吐量在很大程度上不受共识吞吐量的影响。

这项工作证实了这一假设；单体协议将交易传播置于共识的关键路径，对性能的影响比共识本身更严重。
使用 Narwhal，我们表明我们可以将可靠的交易分发卸载到 Mempool 协议，并且仅依靠共识来对非常少量的元数据进行排序，从而显着提高性能。
因此，理论上对于隔离共识协议的渐近最优与在真正的分布式账本中提供良好性能之间存在明显的差距。

在无许可协议 [9, 35] 和许可协议 [19] 中缩小这一差距的先前工作侧重于分离大消息和元数据的传输，而不是保证可靠性。
结果，它们在没有故障的情况下工作得非常好，但在最轻微的网络故障时会遭受严重的损失。
为了评估这种现有的方法，我们采用 Hotstuff 将块传播分离到一个单独的 Mempool 层中，并将生成的系统称为 Batched-HS（第 6 节）。
在 Batched-HS 中，验证者在 Mempool 中广播交易块，领导者在共识期间提出块哈希，而不是在关键路径中广播交易，性能比现有实现提高 50 倍。
然而，这种设计仅在理想的网络条件下表现良好，即领导者的提议可以迅速提供给大多数验证者。
为了制作一个健壮的内存池，我们设计了 Narwhal，这是一个基于 DAG 的结构化内存池，它实现了交易块的因果顺序可靠广播，充分利用了验证者的可用资源。
将 Narwhal Mempool 与 HotStuff (Narwhal-HS) 相结合，即使在故障或不稳定的网络条件下（但不可避免的更高延迟）也能提供良好的吞吐量。
为了减少故障和异步下的延迟，我们可以用抛硬币的随机方法扩展Narwhal以提供异步共识，我们称之为 Tusk。
Tusk 是一个完全异步、无等待的共识，其中每一方通过检查其本地 DAG 来决定商定的值，而无需发送任何额外的消息。

• 我们构建了 Narwhal，这是一种先进的 Mempool 协议，即使在异步情况下也能保证最佳吞吐量（基于网络速度），并将其与我们的 Hotstuff 实现相结合，以适度的延迟代价提高吞吐量。
• 我们利用 Narwhal 的结构并随机增强它以获得 Tusk，这是 DAG-Rider [28] 的实际扩展。 Tusk 是一种高吞吐量、DDoS 弹性和零开销的共识协议。 我们通过实验证明了它在 WAN 中的高性能，即使发生故障也是如此。

图 1 总结了基于 Narwhal 的系统（星形标记）与 HotStuff（圆形标记）在不同数量的验证者和工作人员（交叉标记，“W”后的工作人员数量）没有发生故障时的相对 网络 性能 . 吞吐量（x 轴）随着单个 Narwhal 工作人员的增加而增加，并且当利用 Narwhal 的可并行化特性达到超过 500,000 tx/秒的吞吐量时，吞吐量（y 轴）大大增加，延迟（y 轴）低于 3.5 秒。