区块链知识拼图：DAG，以IOTA为例
区块链，伴随着比特币在币圈的爆热，逐渐被社会大众所知晓。区块链的基本概念，不是这篇分享的主要内容，便不再赘述。今天，我们一起分享的是区块链结构中的一名另类的成员：DAG链。
基本概念
在正式分享之前，必须先了解什么是DAG。DAG，即Directed Acyclic Graph（有向无环图）。有过图论和计算机科学背景的小伙伴应该都比较熟悉这个概念。简单来说，当一个有向图无法从某个定点出发最后回到原地时，这个图便可以叫做DAG。下面这张图便是一个典型的例子：
而在传统的区块链结构中，采用的是更为常见的单链式结构，如下图所示：
可以看到，简单的单链结构使得每次矿工们产生的区块只能有一个区块最终被合法化在链上，这大大限制了交易的量。而如果采用DAG这种结构，则可以让多个区块同时链接到一个先前的区块上，这样便大大提高了交易量。下一部分，我们将以IOTA为例，介绍DAG如何应用在区块链中。
IOTA
IOTA是一款以IoT为背景设计的，助力IoT数据与价值交换的加密货币。它使用了一种基于DAG的Tangle数学模型。
在Tangle中，每个节点代表一个交易（没错，IOTA撇弃了区块的概念，而将最小单位变为了一笔交易），称之为site。所以，一个site包含着交易的具体信息，比如说交易发起者、交易接收者、交易金额等。每个site都会存在至少两条出度的边（edge），连接到别的site上。而当某个site被至少两条edge连接到的时候，这个site便被确认为合法的site。同时，我们也称那些没有被确认的（即没有被至少两条edge指向的）site为Tangle的尖端（tip）。
当一笔新的交易产生的时候，它将以site的形式加入到这个DAG网络中去。它会随机选择一个tip并且类似传统区块验证那样验证确认这个tip是否合法。IOTA规定当site连接到两个合法的tip后，这个site边成为了新的tip。下图中，绿色表示已经达成共识的交易，红色表示还没有达成共识的交易，灰色表示tip交易。
在传统的区块链结构中，越靠前的区块越被大家所承认，因为后面的区块会直接或者间接地不断验证前面区块的合法性。同理，为了在DAG结构区块链中实现这一效果，IOTA为每个site设置了累计权重。一个site的累计权重=工作量权重+引用权重，其中工作量权重与记录这笔交易的节点所投入的工作量成正比，记为3n，而引用权重表示直接和间接引用这个交易的其他交易的工作量相加。所以每当有新的site加入到Tangle中来，与该site直接或者间接相关的site的累计权重便会增加。较早的site通常具有较高的累积权重，这是有意义的，因为它们已经被多次验证。
IOTA的特点
IOTA利用了DAG结构，使其具有了传统区块链所不具备的特点：
- 基于DAG结构和以交易为最小验证单元的设计，极大地增加了交易吞吐量。
- 在IOTA里没有区块的概念，取而代之的是交易网络，每一个交易都会引用过去的两条交易。
- IOTA无手续费，没有激励机制。
- 共识是由全网交易确定的。理论上来说，如果有人能够产生1/3的交易量，他就可以将无效交易变成有效交易。