DAG(有向无环图)是计算机科学和数学领域中的一个关键概念。简而言之,DAG由节点和有向边构成,其特点是没有任何形成闭环的路径,即不存在从一个节点出发并最终回到该节点的路径。
基本定义
- 有向图 (Directed Graph) :图中的每条边都有明确的方向,从一个节点指向另一个节点。
- 无环 (Acyclic) :图中不存在任何闭环或循环。
特点
因为DAG具有无环的特性,它具有清晰定义的起点和终点。每个节点可以有多个后续节点,但不会形成回到先前节点的路径。
在DAG中,至少存在一种节点的顺序,以确保每一条有向边都从顺序的前面节点指向顺序的后面节点。
应用
在计算机科学领域,DAG经常被用来表示信息之间的依赖关系,例如在编译器优化、数据处理管道和任务调度中。
在区块链技术中,一些新兴的分布式账本技术(如IOTA和Hedera Hashgraph)选择采用DAG来替代传统的链式结构,以实现更高的吞吐量和更低的延迟。
此外,由于DAG的无环特性,它们经常被用于拓扑排序,这是一种线性化有向图的方法。拓扑排序确保对于任意两个节点U和V,如果存在从U到V的路径,那么U总是在V之前。
DAG 与区块链
- DAG:由于其并行性,DAG 可以快速处理大量并发交易,这可能导致更高的吞吐量和更短的确认时间。
- 传统区块链:交易必须等待被添加到下一个块中,并且在大多数情况下还需要等待多个确认,这可能导致较低的吞吐量和较长的确认时间。
去中心化程度
- 在理论上,DAG的去中心化可能更为显著,因为每个交易都参与验证。然而,某些DAG实现可能仍依赖于一组特定的节点来确保网络的安全性。
- 相比之下,传统的区块链,例如比特币或以太坊,尽管其目标是去中心化,但在实践中,矿工的集中可能导致中心化的趋势。
交易作为节点
- 交易作为节点:在 DAG-based 的区块链系统中,每个交易都被视为 DAG 中的一个节点。
- 验证关系:在DAG中,当某个节点(交易)加入时,它必须选择并验证一或多个先前的交易。这就要求新的交易在加入系统时证明它已经查看并验证了先前的交易,这种验证行为通过有向边表示,指向它所验证的交易。
- 并行添加:由于这种结构,多个交易可以几乎同时加入DAG,因为它们可能验证不同的先前交易。这与传统的区块链不同,后者在任何时刻只能添加一个新块。
- 权重与确认:随着时间的推移,新的交易会验证旧的交易,增加它们的权重或确认数。在某些DAG系统中,当交易达到某个权重阈值时,它被视为”完全确认”。
- 无需全局共识:由于每个交易都对先前的交易进行了验证,因此不需要像传统区块链那样的全局共识过程。随着更多的交易加入并完成验证,系统逐渐达到了分散的共识。
与传统区块链的主要差异
- 结构:传统区块链是一个线性结构,每个新块都依次添加到前一个块之后。而 DAG 是一个图结构,允许交易并行加入。
- 共识机制:在传统的区块链中,矿工或验证者通过某种共识机制(如 PoW 或 PoS)来达成共识。而在 DAG 中,共识是通过交易验证其他交易的方式分散地达成的。
- 速度与效率:DAG 的结构允许更高的交易吞吐量,因为多个交易可以并行处理。传统区块链由于其线性结构,通常受到吞吐量的限制。
DAG 区块链项目
IOTA
其中一个最为广为人知的使用DAG的区块链项目是IOTA。该项目采用了一个名为”Tangle”的DAG结构。在Tangle中,每个新交易都必须验证两个先前的交易。IOTA强调其网络设计适用于物联网(IoT)中的微交易。
Nano
Nano网络采用DAG结构,旨在实现快速、无费用的交易。在这个网络中,每个账户都有自己的链,这一独特的结构被称为“block-lattice”。
Hedera Hashgraph
尽管在技术上并非严格的DAG结构,Hashgraph采用了类似的概念。它使用投票算法来实现共识,并声称能够提供无需授权的、高速、安全的交易。
Byteball