区块链词汇 | 什么是有向无环图(DAG)

有向无环图(Direct Acyclic Graph或DAG)是近些年来区块链项目的技术热点之一。

按照数学上的定义，DAG是一个没有有向循环的、有限的有向图。具体来说，它由有限个顶点和有向边组成，每条有向边都从一个顶点指向另一个顶点；从任意一个顶点出发都不能通过这些有向边回到原来的顶点。

在数学学科中，DAG与代数拓扑学中被深入研究的偏序集（Partially Ordered Set或Poset）有紧密联系。事实上，任何一个DAG都唯一对应一个Poset, 而所有的Poset都是DAG，所以它们在本质上是一种事物。

在区块链的应用上，DAG图的每个顶点代表在某一个时间新挖出的区块。一般的线性区块链是DAG的一种特殊情况，也即每个时间段整个系统只能产生一个区块。不同的是，DAG允许不同节点按自己的节奏生成区块，只要每个区块选择一个或多个区块作为自己的子区块。

DAG相对于传统线性区块链的优势是非常明显的，主要在于可延展性和交易吞吐量上。由于采取DAG的数据结构的话，每个节点不需要再等其它节点的数据达到统一就可以处理新的交易，避免了因网络延迟和数据同步造成的时间浪费。因此，参与DAG记账的节点很容易大幅延展。此外，DAG的尾端可以平行增加任意多的新数据，因此天生具有很强的交易吞吐量。这一点更是完胜线性区块链。线性区块链每次只能增加一个区块大小的数据量，所以可以处理的交易量是很难改变的。

DAG的主要安全问题是双花和影子链攻击，DAG异步处理数据的特征导致攻击者可能利用节点间的信息差进行双花。DAG允许多重并行交易的特征，导致攻击者可能暗中生成一条影子链，并且时不时地将影子链跟主链进行对接以逃避检测算法。极端情况下，这条影子链有可能代替主链成为全网的共识。