Skip to content

Latest commit

 

History

History
211 lines (134 loc) · 17.7 KB

你所需要的DAG #2 - Narwhal & Tusk.md

File metadata and controls

211 lines (134 loc) · 17.7 KB

你所需要的DAG #2 - Narwhal & Tusk

这是系列文章的第二篇，如果你还没有阅读第一篇文章，也不了解 DAG Rider，建议先阅读第一篇文章以全面理解 Tusk，因为它是 DAG Rider 的改进版本。原始论文由 George Danezis、Lefteris Kokoris-Kogias、Alberto Sonnino 和 Alexander Spiegelman 于 2022 年提出。

让我从我们试图通过 Narwhal 解决的问题开始讲起，这是一个重要的问题——将共识层与交易传播任务分离，从而形成一个高性能协议，即使在崩溃和异步期间仍能保持高吞吐量和活性。通常，部分同步协议（如 LibraBFT 和 Hotstuff）依赖于一个领导者（Leader）占用高带宽，而网络的其余部分在资源利用方面严重不足。Narwhal 通过分散资源利用来消除这种不均衡现象。

Narwhal 作为一个先进的交易池（Mempool），允许验证者运行多个工作机（worker machines）以并行化交易传播过程，并将每个工作机提供的数据批处理为子区块（sub-blocks），然后提供给主节点（Primary）。

让我们定义一些抽象操作来帮助理解 Narwhal 的关键特性：

  1. 写入操作 write(d, b)：将区块 b 和其摘要（唯一 ID）d 存储起来。写入操作会输出 c(d)，一个在成功写入操作后颁发的不可伪造的可用性证书。

  2. 验证操作 valid(d, c(d))：如果证书有效则返回 true，否则返回 false。

  3. 读取操作 read(d)：返回与摘要 d 关联的区块 b，前提是写入操作 write(b, d) 已经成功。

  4. 因果读取操作 read_causal(d)：返回一个区块集合 B，该集合包含构成区块 b 因果历史的所有区块。

Narwhal Mempool 满足以下属性：

1. 完整性（Integrity）

对于一个已认证的摘要 d，所有验证者通过 read(d) 返回的值相同，即每个区块的摘要都是唯一的。

2. 区块可用性（Block Availability）

如果写入操作 write(b, d) 对于一个诚实方成功，则 read(d) 必须始终为所有参与方返回区块 b，即该区块对所有验证者可用。

3. 包含性（Containment）

如果区块 c 是区块 b 的因果历史的一部分，那么 c 的所有因果历史也构成 b 的因果历史，并且是其一部分。

4. 2/3-因果性（2/3-Causality）

区块 b 的因果历史中至少包含写入操作 write(b, d) 被调用之前提出的 2/3 区块。这是由于要求每个区块必须引用前一轮中的 2f+1 个区块。

5. 1/2-链质量（1/2-Chain Quality）

区块 b 的因果历史中至少有 50% 的区块是由诚实验证者提出的。我们能够达到 1/2 的链质量，因为在构成区块 b 因果历史的 2f+1 区块中，最多有 f 个区块来自拜占庭验证者，剩余的 f+1 个区块则来自诚实验证者。

属性的重要性

  • 完整性和区块可用性：将数据传播与共识分离。共识层只需对小尺寸的区块摘要证书进行排序，而不是完整区块，从而提高效率。

  • 因果性和包含性：即使在部分同步环境（如 Hotstuff）的异步期间，仍然能够保证高吞吐量。验证者可以继续提议区块和证书。一旦异步期结束，系统会自动排序当前区块及其因果历史，从而消除因异步导致的间隙。

可扩展性

Narwhal 的另一个关键属性是可扩展性。它的吞吐量随着每个验证者所拥有的资源数量线性增长，同时不会对延迟造成影响。我们将在后续部分中详细解释其可扩展性特性。

设计 Narwhal

Narwhal 的设计直觉旨在：

  1. 减少双重传输：当领导者提议区块时，避免重复传输数据。
  2. 支持扩展：在更多资源可用时实现水平扩展。

问题背景：
在大多数 Mempool 实现中，交易先通过 Mempool 共享，之后领导者创建一个区块并重新共享这些交易，这就导致了“双重传输”问题，Narwhal 旨在解决此问题。

Narwhal 的 5 个关键设计步骤：

1. 广播区块而非交易

验证者直接广播区块，而领导者仅提议区块的哈希值，同时依赖 Mempool 层提供完整性保护的区块内容。此设计需要确保交易数据在任何需要时对所有验证者可用。

2. 引入可用性证书

为了确保数据可用性，领导者签发一个短证书，证明区块的可用性：

  • 该证书由至少 2f+1 个验证者的签名构成，证明该区块已广播到这些验证者。
  • 因为在 2f+1 个验证者中至少有 f+1 是诚实的，证书可以高度确保区块内容是可用的。
  • 挑战：当前每个 Mempool 区块需要一个证书。如果共识协议暂时失去活性，所需证书的数量可能无限增加。

3. 因果性优化

通过引入因果性，一个可用性证书可以引用多个 Mempool 区块及其完整因果历史：

  • 领导者的带宽消耗大大降低。
  • 即使共识延迟，Mempool 区块仍然可以持续生成并最终提交，从而避免因延迟对平均吞吐量的影响。

存在的问题：

  1. 高速验证者滥用资源：高速验证者可能通过快速生成区块迫使其他验证者执行大规模下载。
  2. 带宽不足导致审查：诚实验证者可能因带宽不足无法共享区块，进而被审查。

4. 通过链质量限制区块生成速率

为了解决上述问题，Narwhal 通过 链质量（Chain Quality） 施加限制：

  • 即使验证者生成速度很快，也必须等待 2f+1 个区块生成后才能进入下一轮，其中至少有 f+1 是由诚实验证者生成的。
  • 所有区块都必须引用前一轮的 2f+1 个区块，这再次保证了至少 f+1 个诚实区块被包含在其因果历史中。
  • 优势：Narwhal-Hotstuff 成为唯一在部分同步环境中提供抗审查能力的基于仲裁的协议。

5. 支持水平扩展

通过允许每个验证者使用多台工作机器共享 Mempool 子区块（称为批次），最终由一个主节点将这些引用整合到 Mempool 主区块中：

  • 这种设计支持准线性扩展。
  • 验证者可以投入更多的计算、存储和网络资源以共享交易。

总结

Narwhal 是上述五个设计步骤的集大成者，将基础的 Mempool 设计演变为一个稳健且高效的数据传播和可用性层：

  • 传统共识协议的优化：Narwhal 可用于减轻 HotStuff 等传统共识协议的关键路径负担。
  • 完全异步共识：Narwhal 可利用包含性属性实现完全异步的共识。

区块提议和验证

  • 在本地轮次 r 中：

    • 验证者从客户端接收交易，并从其他验证者接收轮次 r 的可用性证书。
    • 验证者将交易和证书分别积累到交易列表和证书列表中。
    • 一旦接收到 2f+1 个来自轮次 r 的证书，验证者将其本地轮次推进到 r+1。

  • 验证者广播自己创建的每个区块以确保其完整性和可用性：

    • 验证其他验证者的区块是否有效。
    • 如果有效，回复带有自己签名的确认。

在 Narwhal 中，一个有效的区块需要满足以下条件：

  1. 包含创建者的有效签名。
  2. 属于验证者正在检查的本地轮次 ( r )（即相同轮次）。
  3. 包含来自前一轮次 ( r-1 ) 至少 ( 2f+1 ) 个区块的证书。
  4. 是该创建者在轮次 ( r ) 中提议的第一个区块（每个验证者每轮只能提议一个区块）。

如果一个区块有效，验证者会存储该区块并通过签署其区块摘要、轮次号以及创建者身份来确认其有效性。准则交集（quorum intersection）确保了区块的可用性和完整性（避免双重签名），因为在 2f+1 个签名中，至少有 f+1 个来自诚实验证者，这保证了在需要对交易排序时，区块可以被可靠地检索。

接下来，我们将探讨一个部分同步共识协议——Hotstuff，如何通过结合 Narwhal 提高其整体性能。

Narwhal-Hotstuff

Hotstuff依赖领导者提议经过验证者认证的交易区块，这会导致资源利用的严重失衡。领导者需要消耗大量带宽，而网络的其余部分带宽则未被充分利用。Narwhal通过始终高效、均匀地共享大批量交易信息，显著优化了网络资源的利用率。Narwhal允许领导者提议可用性证书（而非交易区块）。在提交时，证书的所有未提交的因果历史都会被确定性排序并提交。这些证书提供了类似于DAG Rider的DAG设计，任何确定性规则都能确保所有验证者对区块的总排序一致，从而实现共识。

最终同步共识协议在异步时期以及领导者为拜占庭节点时，无法保证活性。在这样的时期，传统的Mempool吞吐量降为零。而相比之下，Narwhal即使在异步网络中仍然能够共享区块并形成可用性证书，因此区块始终以最大吞吐量被认证。一旦共识协议成功提交某个摘要，验证者也会提交其因果历史，从而避免了异步时期产生的任何空缺。

垃圾回收

尽管我们保证所有验证者的DAG本地视图最终会收敛，但无法保证具体的时间点。这可能迫使验证者始终保留所有区块和证书，以：

  1. 帮助其他节点追赶进度。
  2. 处理任意旧消息。

为了解决这个问题，Narwhal引入了基于轮次的结构，使验证者能够仅使用当前轮次的信息来验证新区块的有效性，而无需检查整个区块历史。一旦某个区块达成共识，早期轮次的内容可以被垃圾回收（即安全地丢弃），而不会影响系统的运行。验证者通过共识协议的属性达成对垃圾回收轮次的协议。如果验证者在交易被包含到DAG之前删除了这些交易，可以将其重新注入到后续轮次中，从而确保所有交易最终被纳入共识输出。即使某些实际的DAG区块可能被审查，所有交易最终都会被包含在区块中，并根据1/2链质量保证在常数轮次内加入共识输出。

因此，Narwhal中的验证者可以在固定大小的内存下运行，即每个验证者需要的内存使用量为O(n)，仅需包含当前轮次的区块和证书即可正确运行。此外，存储和服务请求可以被卸载到被动且可扩展的分布式存储，或由运营内容分发网络（CDN）的外部提供商处理。

接下来，我们将重点讨论使Narwhal达到最大潜力的两个关键实践挑战：

基于仲裁的可靠广播

Narwhal中的可靠广播实现了一种抗拒绝服务攻击（DoS）且高效的“拉取”机制。由于可靠广播的完备性可能无法完全满足——即部分区块可能未被所有验证者观察到——但由于因果性，任何在后续轮次中提议的区块都会包含签名，确保至少有2f+1个区块通过其因果历史可用。由于这些签名中至少有f+1来自诚实节点，在向少量验证者请求后，获得正确响应的概率会呈指数增长。

在任何时刻，每个区块最多只有O(1)个请求处于活动状态。一旦收到包含目标区块的正确响应，所有未完成的请求都会被丢弃。这种情况下，平均仅需O(1)次请求即可完成，除非攻击者主动攻击网络连接，这时最多需要O(n)次请求，这与理论上的最坏情况下限相匹配。区块可用性认证、后续区块中对这些认证的包含以及“拉取机制”共同构成了一个可靠的广播协议。重传的存储需求受限于轮次推进时间和认证区块检索时间，存储空间的需求在仲裁大小O(n)范围内（且常数较小）。

扩展性验证者

Narwhal通过一种多计算机的验证者系统，解决了单个验证者在带宽、存储和处理能力方面的限制，成功实现了扩展性架构。

我们采用一个简单的主节点-工作节点架构（如图所示）。首先将协议消息分为交易数据和元数据。作者强调，传输和存储交易数据是一项“极易并行化”的任务：负载均衡器确保所有工作节点以相似的速率接收交易数据；工作节点创建交易批次，并将其发送到其他验证者的工作节点；一旦收到仲裁节点的确认，该交易批次的加密哈希会被发送给主节点，以包含到区块中。

此外，只有当主节点确认所包含的批次已存储在自己的工作节点中时，才会对区块签名。通过归纳法，可以确保任何证书所指代的数据都可以被检索。

主节点实现了一种拉取机制以请求缺失的批次：当收到包含未存储批次的区块时，主节点指示其工作节点直接从该区块创建者的工作节点拉取缺失的批次。此操作仅需要有限的内存。

由于主节点区块的大小仅包含交易批次的哈希，因此非常小。工作节点在后台持续创建和共享批次，这些小批次确保交易不会遭受超过某个最大延迟，从而在主节点区块到达之前就能提供给其他验证者。这种设计从两方面降低了延迟：

  1. 从接收到主节点区块到对其签名的等待时间减少。
  2. 在等待轮次推进期间，工作节点继续流式传输新批次，以包含到下一轮的区块中。

当前该协议的潜在瓶颈是主节点区块的大小可能因高交易率而增加，但验证者可以通过增加工作节点数量或增大批次大小来提升容量。这可能需要使用更好的累加器（如Merkle树）。尽管作者从未观察到主节点成为瓶颈，这仍是一个理论上的瓶颈。

接下来，我们讨论如何通过异步共识算法Tusk，使Narwhal即使在异步或DDoS（分布式拒绝服务攻击）下依然保持活性。

Tusk

Tusk 是基于 DAG Rider 设计的，并继承了我们在第一篇文章中讨论的所有关键特性。Tusk 的验证者使用 Narwhal Mempool 并在所有区块中实现了一个分布式完美币（distributed perfect coin），类似于 DAG Rider。Tusk 完全排序了由 Narwhal 构建的因果有序 DAG，并且没有额外的通信开销。

与 DAG Rider 不同的是，Tusk 中每个“波次”（wave）由 3 个连续的轮次组成：

  1. 第一轮：验证者提出区块（包括所有的因果历史）。
  2. 第二轮：每个验证者通过将提议区块包含在自己的区块中，对提议进行投票。
  3. 第三轮：验证者从波次的第一轮中随机选举一个领导者的区块。

一旦选出领导者，每个验证者 v 会提交波次 w 的选举领导者区块 b，如果在 v 的本地 DAG 视图中，波次第二轮中有 f + 1 个区块引用了 b。在这种情况下，v 会小心地对 b 的因果历史进行排序，直到垃圾回收点为止。

然而，由于验证者可能获得不同的 DAG 本地视图，部分验证者可能会在某个波次中提交领导者区块，而其他验证者则可能不提交。

递归过程：在最后一个已提交的领导者和当前待提交的领导者之间找到未提交的领导者的过程，与我们在 DAG Rider 中所做的相同。

Tusk 相比 DAG Rider 的主要理论保证体现在其更优的终止性（termination guarantee）：

  1. 块提交的期望轮次：

    • DAG Rider 的波次由 4 个轮次组成，因此在普通情况下，每个区块的提交期望为 5.5 轮。
    • Tusk 的波次由 3 个轮次组成，并且上一波次的最后一轮与下一波次的第一轮重叠运行，这使得 Tusk 在普通情况下每 4.5 轮 提交领导者区块。

  2. 消息开销：

    • 领导者的选举过程通过随机共享币（random shared coin）实现，且共识逻辑没有引入任何超出 Narwhal 的额外消息开销。换句话说，Tusk 在理论吞吐量上与 Narwhal 相同，且具有 零额外消息开销。

  3. 普通情况：

    • 普通情况下，网络消息延迟是随机分布的，而非由对手控制。在这种情况下，Tusk 的性能优于 DAG Rider。
    • 在异步对手控制的网络中，Tusk 仍然可以保证每 7 个轮次 提交一个领导者区块（详情参见原始论文的证明）。

Tusk 的改进之处：

  1. 优化的可靠广播：

    • Tusk 替换了传统的可靠广播协议，采用了本文描述的更高效的广播机制。

  2. 更好的提交规则：

    • 修改了块提交规则，以在普通情况下实现更低的延迟。

  3. 支持垃圾回收：

    • 通过去除弱链接（weak links），解决了 DAG Rider 无法在有限存储中实现的问题。
    • 在 DAG Rider 中，验证者必须存储所有曾接收到的区块，以防这些区块通过弱链接被引用。而在 Tusk 中：
      • 弱链接被禁止，任何未提交的、已垃圾回收的区块，其交易会被重新注入到后续轮次的新区块中。
      • 这种机制实现了 交易级别的公平性，而非块级别的公平性。

综上，Tusk 改进了延迟和存储效率，并保持了 DAG Rider 的核心理论保证，成为一个更加实用和高效的协议。

性能分析

在本节中，我将通过一些数据简单说明，将 Narwhal 与 Hotstuff 和 Tusk 结合使用，以及单独使用 Hotstuff 时的吞吐量和延迟表现，以帮助更直观地理解其性能。