记账最新方法get起来——DAG技术的妙用

DAG的英语全称是Directed Acyclic Graph，中文是“有向无环图”。听上去令人懵逼，其实那是很简单的一个概念。

首先它是一个“图”。图其实就是点(vertex)与边(edge)的集合。两点之间如果有直接通路那就构成了“边”。

下面这货就是一个典型的“图”。它一共有8个点，但并不是任意两点间有直接通路，比如说从3到7，它当中必须经过5。如下图：

如果在上图基础之上，给每条路设定一个走向，那这个图就称之为“有向图”。比如说我只能从1走到2，但是2没办法走回到1，好比是单行道。如下图所示：

 

接着上面的图我们再来看，如果从1走出去以后，还想让自己回来，那我们就要建一个回路。比如在6和1之间再建一条路，如下图所示：

上图中1，3，5，6就构成了一个闭环。也就是说如果沿着1->3->5->6->1的路线一直走，可以永远走下去没有穷尽。

判断一个图有无闭环最好的办法，就是从任意一个点开始，尽可能地遍历所有的通路，看看能不能走回来，如果可以走回来那就说明存在闭环，否则就说明没有闭环。所以DAG——有向无环图，就是一个不存在闭环的有向图。

基于DAG的交易模型

了解了DAG的定义以后，我们来看看它是如何应用在区块链交易模型上的？

我们都知道比特币的记账方式是把一系列的交易记录存放在区块里面，所以在记账以前，必须要准备好一个新的区块，就好比是一个空账本。这些活虽然矿工都会包办，但是他们不白干。作为奖励，他们收取交易费以及一定数量的出块奖励，而这就是造成网络拥堵和算力浪费的根源。

先来看网络拥堵：

随着比特币交易变得越来越频繁，在短时间内必然会有大量交易等着存进区块中，所以矿工势必会通过交易费竞标来提高自己的收益，那交易费给得比较少的当然就要“排很长队”了。

再来看算力浪费：

随着时间推移，挖矿的难度会越来越高，普通的家用电脑永远都没法挖出一个新的区块。所以有大量的定制化挖矿机器涌现,  这些机器拥有超高的算力但同时也消耗非常多的电力。它们的作用仅仅是为了挖矿，那显然是一种资源的浪费。

如果有一种新的玩法可以取缔矿工的存在，那这两个问题自然迎刃而解，而这便是DAG的最大的创新。我们看看它是如何做到的？

以IOTA的Tangle架构为例：它首先取消了区块，因为这套新的玩法不需要用区块来存储交易信息。每一笔交易是通过被另一笔交易确认的方式来进行记账的，也就是说每个用户兼具着交易与记账的两项职能。

这套玩法有三个重要的规则：

· 只有被确认过的交易才会记入账本。

· 每一笔交易只能确认一个时间单位之前的未确认交易。

· 确认的交易之间不能相互矛盾。

如果我们把每一笔交易看作一个点的话，那它被某一笔交易确认就相当于两点之间搭了一条通路。由于这样的确认关系是单向的，所以这条路也有固定的走向。如下图所示：

其中T1, T2和T3分别为三个不同时间发生的交易。按照时间先后次序，T2确认了T1，T3确认了T2，所以T3也间接确认了T1。对于T1来讲，T2就是它的确认者(approver), 而T1就是T2的被确认方(approvee)。

我们看到T2到T1, T3到T2之间分别构建了一条单向通路。于是T1,T2,T3之间组成的就是一个有向无环图——DAG。换句话来说，我们可以用DAG来存储账本。

它存储了两样东西：1.交易内容，2. 每笔交易之间的确认关系。另外一点值得注意的是，只有T1和T2被确认了（标白色），而T3却没有被确认（标灰色），所以T3是不被认可的交易。我们把那些没有被确认过的交易称为Tip。

第一笔交易一定是被所有其他交易直接或者间接确认的，我们称其为创世交易(genisis transaction)。创世交易一般包含改加密货币的总量。这个很好理解，因为之后的所有交易都会从它这边衍生出来。