跳转至

区块 DAG（Directed Acyclic Graph，有向无环图）

​区块 DAG（Directed Acyclic Graph，有向无环图）​​ 是一种数据结构，用于描述区块链或分布式账本中交易或区块之间的关联关系。与传统区块链的线性链式结构不同，DAG 通过​​网状拓扑​​组织交易，允许多个交易并行处理，从而提升系统的扩展性和吞吐量。

最早在区块链中引入 DAG 概念作为共识算法是在 2013 年，bitcointalik.org 由 ID 为 avivz78 的以色列希伯来大学学者提出，也就是 GHOST 协议，作为比特币的交易处理能力扩容解决方案；Vitalik 在以太坊紫皮书描述的 POS共识协议 Casper，也是基于 GHOST POW 协议的 POS 变种。

后来 NXT 社区有人提出用 DAG 的拓扑结构来存储区块，解决区块链的效率问题。区块链只有一条单链，打包出块无法并发执行。如果改变区块的链式存储结构，变成 DAG 的网状拓扑可以并发写入。在区块打包时间不变的情况下，网络中可以并行打包 N 个区块，网络中的交易就可以容纳 N 倍。

此时 DAG 跟区块链的结合依旧停留在类似侧链的解决思路，交易打包可以并行在不同的分支链条进行，达到提升性能的目的。此时 DAG 还是有区块的概念。

2015年9月，Sergio Demian Lerner 发表了 《DagCoin: a cryptocurrency without blocks》一文，提出了 DAG-Chain 的概念，首次把 DAG 网络从区块打包这样粗粒度提升到了基于交易层面，但 DagCoin 本身是一篇论文，没有代码实现。

DagCoin 的思路，让每一笔交易都直接参与维护全网的交易顺序。交易发起后，直接广播全网，跳过打包区块阶段，达到所谓的 Blockless。这样省去了打包交易出块的时间。如前文提到的，DAG 最初跟区块链的结合就是为了解决效率问题，现在不用打包确认，交易发起后直接广播网络确认，理论上效率得到了质的飞跃。DAG 进一步演变成了完全抛弃区块链的一种解决方案。

2016 年 7 月，基于 Bitcointalk 论坛公布的创世贴，IOTA 横空出世，随后 ByteBall 也闪亮登场，IOTA 和 Byteball 是头一次 DAG 网络真正技术实现，也是此领域最耀眼的领军者；此时，号称无块之链、独树一帜的 DAG 链家族雏形基本形成。

一句话来概括：DAG是面向未来的新一代区块链，从图论拓扑模型宏观看，从单链进化到树状和网状、从区块粒度细化到交易粒度、从单点跃迁到并发写入，这是区块链从容量到速度的一次革新。

  1. 非线性结构：交易（或区块）之间通过引用（指针）相互连接，形成网状图，而非单链。每个新交易需要引用多个历史交易的哈希值（类似“确认”前序交易；
  2. 有向性：图中的边具有方向性（例如，交易 A 引用交易 B，则边为 \(A \rightarrow B\)，不可以反向引用）；
  3. 无环性：不允许出现循环依赖（例如，交易 A 引用交易 B，交易 B 引用交易 C，交易 C 引用交易 A，则形成一个循环），确保数据一致性。
特性 传统区块链 DAG
结构 线性链式结构 网状拓扑结构
交易确认方式 顺序打包，线性链式结构，需要多个区块确认 并行处理，网状结构，交易之间相互引用，无需多个区块确认
吞吐量 受限于区块大小和出块速度 理论上可以无限扩展
延迟 高（需要等待区块确认） 低（交易即时传播）
典型应用 比特币、以太坊 IOTA、Nano、Hedera Hashgraph
  1. 交易创建：用户发起交易时，需引用多个已确认的历史交易（作为“基础”）。引用越多，交易的可信度越高（类似共识机制）。
  2. 交易传播：新交易广播到网络，其他节点验证其引用的历史交易是否有效。验证通过后，交易被加入DAG网络。
  3. 冲突解决：若两个交易互相矛盾（例如双花攻击），DAG通过​​拓扑排序​​或​​共识算法​​（如Tangle）决定最终状态。
  1. 高扩展：无需矿工打包区块，交易可并行处理，适合高频场景（如物联网支付）；
  2. 低延迟：交易即确认，无需等待区块生成；
  3. 去中心化：节点间直接交互，减少对中心化矿池对依赖。
  1. 数据存储：网状结构可能导致存储需求指数级增长；
  2. 双花攻击风险：若恶意用户持续发起冲突交易，可能破坏网络一致性（需依赖强共识机制）；
  3. 复杂性：开发难度高于传统区块链，需设计高效的冲突检测和解决算法。

区块 DAG 是一种颠覆传统区块结构的创新方案，通过网状拓扑实现并行处理和高吞吐量，适用于物联网、高频交易等场景。

我们通过一个具体的例子深入理解 DAG（有向无环图）在区块链中的工作原理。假设我们有一个基于 DAG 的轻量级支付系统（类似 IOTA 的 Tangle），以下是详细的操作流程：

场景设定

目标：用户 A 向用户 B 发送 10 元，用户 C 向用户 D 发送 5 元。

系统要求：

  1. 交易无需矿工打包，直接广播网络；
  2. 每笔新交易必须验证之前的两笔交易（防止双花）；
  3. 交易通过引用历史交易达成共识。

交易1（Tx1）

  • 发送方：用户A \(\rightarrow\) 用户B
  • 金额：10元
  • 引用：无（初始交易）
  • 签名：A 的私钥签名

交易2（Tx2）

  • 发送方：用户C \(\rightarrow\) 用户D
  • 金额：5元
  • 引用：无（初始交易）
  • 签名：C 的私钥签名

此时 DAG 中有两个独立交易，彼此无关。

交易3（Tx3）

  • 发送方：用户B \(\rightarrow\) 用户E
  • 金额：8元
  • 引用：必须引用 Tx1 和 Tx2（验证前两笔交易的有效性）
  • 签名：B 的私钥签名

验证逻辑：B 需要证明自己拥有 Tx1 中收到的 10 元（余额足够支付 8元），系统检查 Tx3 是否同时引用 Tx1 和 Tx2（防止用户恶意跳过验证）

  1. 广播：Tx3 被发送到网络中的所有节点；
  2. 验证：每个节点检查 Tx3 是否签名有效（B 的签名）；检查 Tx3 引用的 Tx1 和 Tx2 是否已经被确认（未被双花）
  3. 确认：如果验证通过，Tx3 被标记为“已确认”，并成为后续交易的引用基础。

假设用户 A 尝试作弊：

  • 交易4（Tx4）：A 发送同一笔 10 元给用户 F，并引用 Tx1 和 Tx3；
  • 问题：Tx1 已经被 Tx3 引用，但 Tx4 试图再次使用 Tx1 的余额。

系统如何解决？

  1. 拓扑排序：节点根据时间戳对交易排序，Tx4 必须晚于 Tx3；
  2. 共识规则：如果一个交易引用的 UTXO（未花费交易输出）已被其他交易使用，则后续交易无效；
  3. 结果：Tx4 被标记为“无效”，拒绝加入 DAG。

最终交易之间的引用关系形成如下网状结构：

graph TB
    Tx1[Tx1 A->B]
    Tx2[Tx2 C->D]
    Tx3[Tx3 B->E]

    Tx3 --> Tx1
    Tx3 --> Tx2
  • 方向性： Tx3 引用了 Tx1 和 Tx2，但 Tx1 无法反向引用 Tx3；
  • 无环性：不存在循环引用，确保数据一致性。

Q&A

双花防护机制

DAG 通过以下规则防止双花：

  1. UTXO 消费标记：每笔交易引用 UTXO 后，立即将其标记为“已消费”；
  2. 拓扑排序验证：节点按时间顺序处理交易，确保后续交易无法引用已处理的 UTXO；
  3. 冲突检测：若两个交易尝试引用同一 UTXO，后发生的交易会被拒绝。

评论