DAG（有向无环图）是计算机科学和数学领域中的一个关键概念。简而言之，DAG由节点和有向边构成，其特点是没有任何形成闭环的路径，即不存在从一个节点出发并最终回到该节点的路径。

基本定义

• 有向图 (Directed Graph) ：图中的每条边都有明确的方向，从一个节点指向另一个节点。
• 无环 (Acyclic) ：图中不存在任何闭环或循环。

特点

因为DAG具有无环的特性，它具有清晰定义的起点和终点。每个节点可以有多个后续节点，但不会形成回到先前节点的路径。

在DAG中，至少存在一种节点的顺序，以确保每一条有向边都从顺序的前面节点指向顺序的后面节点。

 Applications

在计算机科学领域，DAG经常被用来表示信息之间的依赖关系，例如在编译器优化、数据处理管道和任务调度中。

在区块链技术中，一些新兴的分布式账本技术（如IOTA和Hedera Hashgraph）选择采用DAG来替代传统的链式结构，以实现更高的吞吐量和更低的延迟。

此外，由于DAG的无环特性，它们经常被用于拓扑排序，这是一种线性化有向图的方法。拓扑排序确保对于任意两个节点U和V，如果存在从U到V的路径，那么U总是在V之前。

DAG 与区块链

速度与吞吐量

• DAG：由于其并行性，DAG 可以快速处理大量并发交易，这可能导致更高的吞吐量和更短的确认时间。
• 传统区块链：交易必须等待被添加到下一个块中，并且在大多数情况下还需要等待多个确认，这可能导致较低的吞吐量和较长的确认时间。

• 在理论上，DAG的去中心化可能更为显著，因为每个交易都参与验证。然而，某些DAG实现可能仍依赖于一组特定的节点来确保网络的安全性。
• 相比之下，传统的区块链，例如比特币或以太坊，尽管其目标是去中心化，但在实践中，矿工的集中可能导致中心化的趋势。

交易作为节点

• 交易作为节点：在 DAG-based 的区块链系统中，每个交易都被视为 DAG 中的一个节点。
• 验证关系：在DAG中，当某个节点（交易）加入时，它必须选择并验证一或多个先前的交易。这就要求新的交易在加入系统时证明它已经查看并验证了先前的交易，这种验证行为通过有向边表示，指向它所验证的交易。
• 并行添加：由于这种结构，多个交易可以几乎同时加入DAG，因为它们可能验证不同的先前交易。这与传统的区块链不同，后者在任何时刻只能添加一个新块。
• 权重与确认：随着时间的推移，新的交易会验证旧的交易，增加它们的权重或确认数。在某些DAG系统中，当交易达到某个权重阈值时，它被视为”完全确认”。
• 无需全局共识：由于每个交易都对先前的交易进行了验证，因此不需要像传统区块链那样的全局共识过程。随着更多的交易加入并完成验证，系统逐渐达到了分散的共识。

与传统区块链的主要差异