Skip to content

DAG-RIDGER.md

Latest commit

 

History

History
49 lines (49 loc) · 6.14 KB

DAG-RIDGER.md

File metadata and controls

49 lines (49 loc) · 6.14 KB

DAG-Rider 是一种基于有向无环图（DAG）的异步拜占庭容错（BFT）共识算法，旨在解决区块链系统中高吞吐量、低延迟和高可扩展性的需求。以下是对 DAG-Rider 共识算法的详细解释：

1. 背景与核心思想

  1. DAG-Rider 由 Ittai Abraham 等人在 2021 年提出，发表在 PODC 2021 会议上（论文标题：All You Need is DAG）。它通过将数据传播与元数据排序解耦，利用 DAG 结构来实现高效的共识。与传统的链式区块链（如比特币或以太坊）不同，DAG-Rider 允许并行处理多个区块，从而显著提高吞吐量，同时保持异步网络环境下的安全性与活性。 核心思想是：
  2. DAG 作为通信抽象：每个节点（验证者）通过可靠广播（Reliable Broadcast）发布提案（Proposal），这些提案形成一个 DAG，其中节点（Vertex）代表提案，边（Edge）代表对其他提案的引用。
  3. 零通信开销的共识：共识过程通过本地解释 DAG 结构完成，无需额外的通信消息，从而降低网络开销。
  4. 异步容错：DAG-Rider 在完全异步网络中也能保证安全性（Safety）和活性（Liveness），即使有不超过三分之一的恶意节点（即 f < n/3，其中 ( n ) 为节点总数，( f ) 为恶意节点数）。

2. 算法工作原理

DAG-Rider 的工作流程分为两个主要层次： （1）第一层：构建 DAG

  1. 可靠广播：每个验证者在每一轮（Round）广播一个提案（包含交易或数据）。这些提案通过可靠广播协议传播，确保所有诚实节点最终收到相同的提案。
  2. DAG 结构：每个提案引用前一轮至少 n-f个提案（即至少引用 2f+1个节点的消息），形成一个有向无环图。引用关系通过边表示，边的存在表明提案对被引用提案的认可。
  3. 轮次机制：DAG 按轮次组织，每个提案关联一个轮次编号。验证者只有在收到前一轮的足够多提案（至少 n-f个）后，才能进入下一轮并广播新提案。
  4. 弱边（Weak Edges）：为了确保所有诚实节点的提案最终被包含在 DAG 中，DAG-Rider 引入了弱边，指向较旧轮次的提案。这些弱边不计入共识的投票逻辑，仅用于确保提案的可达性。 （2）第二层：本地排序
  5. 无通信排序：每个节点根据本地 DAG 的结构，独立对提案进行全序（Total Order）。具体方法是：识别“锚点”（Anchor）：每一轮选择一个锚点提案，要求该提案被后续轮次的足够多提案引用（通常是 n-f个）。
  6. 追溯因果历史：锚点的因果历史（Causal History）包含其直接或间接引用的所有提案。这些提案按照某种确定性规则（例如轮次优先或哈希值排序）进行全序。
  7. 垃圾回收问题：由于异步网络中，某些提案可能延迟到达，DAG-Rider 的弱边机制会导致垃圾回收困难（无法确定何时可以安全删除旧轮次的数据）。后续的 Bullshark 算法通过引入时间戳和同步假设改进了这一点。

3. 关键特性

根据相关文献（如 和），DAG-Rider 具有以下特点：

  1. 最优容错性：支持最多 f < n/3的拜占庭节点。
  2. 最优通信复杂度：摊销通信复杂度为 ( O(n) )，即每个提案的平均通信成本与节点数线性相关。
  3. 最优时间复杂度：在异步环境中，预期延迟（以轮次计）为常数级别。
  4. 后量子安全：算法不依赖特定密码学假设，适合后量子环境。
  5. 高吞吐量：通过并行广播和处理提案，DAG-Rider 实现了网络速度的吞吐量，即使共识延迟较高。
  6. 公平性：每一轮的因果历史包含至少 n-f个提案，其中超过半数（> f）来自诚实节点，确保链的质量（Chain Quality）。

4. 与其他 DAG 共识算法的比较

DAG-Rider 是 DAG 共识算法家族的一部分，与其他算法（如 Tusk、Bullshark、Narwhal 等）有以下区别：

  1. 与 Tusk 的关系：Tusk 是 DAG-Rider 的改进版本，优化了延迟，通过减少 DAG 层数（从 4 层减少到 2 层）来加速提交（）。
  2. 与 Bullshark 的关系：Bullshark 针对部分同步（Partial Synchrony）模型优化了 DAG-Rider，引入时间戳以支持垃圾回收，并保证同步期间的公平性（）。
  3. 与 IOTA Tangle 的区别：IOTA 的 Tangle 要求每笔交易验证两个先前交易，依赖交易量来增强安全性，但存在中心化“协调者”（Coordinator）问题（）。而 DAG-Rider 是完全去中心化的 BFT 协议，适用于高安全场景。
  4. 与 Hashgraph 的区别：Hashgraph 依赖八卦协议（Gossip Protocol）传播事件，动态参与性较差，而 DAG-Rider 支持动态参与并优化了通信效率（）。

5. 优缺点

优点：

  1. 高吞吐量与低延迟：并行处理提案显著提高了交易吞吐量，适合高频交易场景。
  2. 异步安全性：在完全异步网络中保证共识，适应复杂网络环境。
  3. 简单性：通过本地 DAG 排序避免额外通信，简化了协议设计。
  4. 广泛应用：已被 Aptos、Celo、Mysten Labs 等区块链公司采用（）。 缺点：
  5. 垃圾回收问题：异步环境中，弱边机制可能导致无法安全删除旧数据，增加存储负担。
  6. 复杂性：尽管共识逻辑简单，但 DAG 结构的维护和本地排序仍需较高计算资源。
  7. 依赖可靠广播：可靠广播协议的性能直接影响 DAG-Rider 的效率。

6. 实际应用

DAG-Rider 及其衍生算法（如 Tusk 和 Bullshark）已被多个区块链项目采用，例如：

  1. Aptos：使用基于 DAG-Rider 的 Shoal++ 协议，优化了高吞吐量场景（）。
  2. Sui：结合 Mysticeti 协议，利用 DAG 结构实现低延迟共识（）。
  3. Celo 和 Somelier：探索 DAG-Rider 在高性能区块链中的应用（）。
  4. 总结 DAG-Rider 是一种高效的异步 BFT 共识算法，通过 DAG 结构和零通信开销的本地排序实现了高吞吐量和低延迟。它在安全性、容错性和通信效率方面达到理论最优，适用于下一代区块链系统。尽管存在垃圾回收等挑战，但其衍生算法（如 Bullshark）正在不断改进，使其在实际应用中更具潜力。