有向无环图 DAG

DAG ，也就是 Directed Acyclic Graph 有向无环图，在区块链领域是一个非常有曝光度的技术。而有意思的是 DAG 其实并不是区块链，这个一会儿咱们会聊到。本文给出的只是简介，DAG 技术具体细节大家可以参考文中给出的那些使用 DAG 的知名项目。

DAG 在图论中的本意

DAG 是一种图，那么从图论的基本理论角度，DAG 是什么呢？

咱们先从区块链说起。如果你有编程知识背景，肯定知道链表的概念，链表就是一条很多节点链接成的一条链，每个节点中包含指向前一个节点的链接。区块链之所以能连成一条链，是因为新区块中有指向上一个区块的指针，所以说区块链的数据结构是一个链表。但是区块链的问题就在于它是一条线，假设一个区块生成的时间是固定的，那么这样一条线的结构就会造成性能瓶颈。因为每隔这个固定时间，只允许有一个区块添加到链上。所以要提升区块链的性能，大概有两个思路，一个是缩短生成一个区块的时间，而对于采用了 DAG 技术的区块链项目，走的就是另外一个思路了，也就是改变数据的结构，让新数据的添加可以平行进行。

DAG 数据结构不是链表，而是 Graph 图。Graph 上有很多节点，也叫做 Vertices 顶点，连接两个节点的叫做 edges 边。没错，就是咱们中小学数学课上学到的顶点和边的概念。链表，Tree ，图是三个复杂度递进的数据结构。链表就是一条有方向的线。Tree 是有分叉的，但是任意两个节点间只有一条路径能到达另外一点，也就是不能形成闭合的图形。而图是可以有闭合的图形的。当然，深入一点说，Tree 也属于 Graph 的一个特例了，这个我们不深究。

DAG 最后一个字母 G 指的就是 Graph 图，那 D 和 A 是什么意思呢? D 对应单词是 Directed 有向，也就是有明确的方向的意思。A 节点中有指向 B 节点的指针，而 B 节点中是没有指向 A 新节点的指针的，如果画出来就是一个从 A 到 B 的单向的箭头。在 DAG 中，一个节点到另外一个节点的指向是单向的，这就是 D 有向的含义。再说 A ，A 对应的单词是 Acyclic 无环，意思是整张图上不允许出现沿着箭头从一个节点出发最后能又回到起点的情况。

这样，我们就理解了，从图论的角度，什么是 DAG 了。

区块链中使用 DAG 的基本方式

下面来看看到了区块链项目中 DAG 怎么玩。我们从基于 DAG 如何来实现常见的区块链功能来聊。

第一个功能，交易验证。常见的做法是，DAG 项目会要求后发起交易的人必须选择一个或多个之前的交易来验证。DAG 项目中不会把交易打包成区块，这样每个交易就是一个节点，交易之间的指针就是边，交易历史就形成了一个 DAG 。

第二个共识。只有交易验证，保证不了系统的安全。如何有人发恶意交易，出现了各种争端，谁来解决呢？基本的共识思路是通过某种规则选择出几十个见证人，让见证人通过 BFT 协议或者其他规则来见证交易。Byteball 项目规则是选出12个实名制的见证人，IOTA 则采用了一个临时的中心化 Coordinator 机制。

第三个是激励。DAG 类的项目中一般没有挖矿，通常的做法是一次性发行所有币。例如，Nano 项目就是通过在创世账户中直接发放的形式，来一次性发行所有的币的。参与验证的机器会获得代币激励。

这些就是使用 DAG 类项目如何达成各项功能的方式了。

DAG 的优点和缺点

最后来聊一下 DAG 的优缺点。

先说优点，最明显的就是高速度零费用。DAG 条件下，交易不会打包成区块。每笔交易都是单独被验证的，所以大量的交易验证都可以并行进行。理论上交易吞吐量是没有上限的。用户互相之间互相验证交易，于是 DAG 项目可以实现0手续费交易。这些优点对于 IOTA 这样的服务物联网的区块链项目是非要必要的，因为 IOTA 要处理的是机器和机器之间的交易，通常都是非常高频和小额的交易，如果过程中再收取手续费，就没法进行了。

再说说使用 DAG 的缺点。DAG 这个思路应该说安全性还是有待验证的，各种安全漏洞不断的被曝出。中心化问题也相对比较严重，这一点从上面提过的几个项目达成共识的方式可以看到。

总之，DAG 技术优势明显，但是还是有待验证。

总结

对于 DAG 有向无环图的这篇简介，内容到这里了。总结起来，DAG 就是一个从任何节点出发，只要按照指针方向走，无论选择哪种路径都不能回到起点的图。DAG 应用到区块链领域可以实现非常高的性能和零手续费，但是最终的可行性还有待验证。

参考：

https://www.youtube.com/watch?v=LtWUJtnQbKs&t=296s

https://en.wikipedia.org/wiki/Directedacyclicgraph

https://en.wikipedia.org/wiki/Tree(graphtheory)

https://www.coinbureau.com/education/directed-acyclic-graphs-dags/