DAG的妙用（一）——记账新方法

本文转载自公众号：[区块链中那些事儿] 作者：区块君的《DAG的妙用（一）——记账新方法》，已获授权。

前言

好久没跟大家聊咯，之前花了很多章节跟大家探讨过比特币运作的机制和原理 [1] 。比特币作为第一个加密货币开创了区块链的先河，它独创的那套共识算法的体系使得它可以准确无误地进行分布式记账。

但是它的缺点也是显而易见的。它最大的缺点，也是被人吐槽最多的就是它的“慢”。这个在我之前的文章也有分析过，由于12分钟的出块时间限制，使得它每秒钟只能处理7笔交易。而且它的工作证明(POW)的共识算法机制 [2] 使矿工不得不进行大规模的算力竞争，所以大量算力资源被白白浪费。这也变相地滋生了大矿主的垄断。由于手握大部分的算力资源，所以绝大多数的比特币集中在极少数矿主手中。比特币的建立的初衷是为了去中心，但是比特币资产的持有又是非常中心化的。这样的经济模型显然不是良性的。

针对以上这些弊端，世人进行了很多探索和尝试，其中不乏一些独创性的架构异军突起，标识着区块链发展的未来。而DAG便是其中之一。它起初是一个图论的概念，后来被广泛应用于各种算法的数据结构中。

我会分三个章节来跟大家介绍一下它在区块链技术层面的使用场景，来帮助大家掌握其中的原理。今天我们先来探讨一下它在区块链交易模型和共识算法上的应用，看看它是如何解决“慢”这个问题的。

什么是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)。创世交易一般包含改加密货币的总量。这个很好理解，因为之后的所有交易都会从它这边衍生出来。

Tip选取策略

有了DAG数据结构作为交易记录的承载，我们确实可以快速地进行记账。接下来我们得分析下整个DAG网络的稳定性。

假设交易频率为λ，如果λ接近于零，那就意味着需要等很久才会出现一笔新的交易。在这种情况下，每一个交易只能确认前一笔发生的交易，所以整个图就相当于一条单链的形状，如下图所示：

（图片来源： IOTA白皮书）

如果λ非常大，那就代表单位时间内会出现许多交易，那这些交易都会指向第一笔，如下图所示：

（图片来源： IOTA白皮书）

当然实际情况不会那么简单，我们往往看到的是λ介于两者之间，所以每笔交易所面临的往往是两笔以上的未确认交易(Tip)。如下图所示：

这时候交易5就面临一个选择，到底是在2，3，4中确认哪一笔呢？这里就涉及到了一个Tip的选取策略。 Tip的选取策略是这套玩法最重要的基石，因为它决定了整个DAG网络发展的走向 。

首先，选1个还是选多个？

这没有固定的答案，需要根据具体情况实验来定，在数学里称为探索值(heuristic value)。我们假设这个值为n：

n=1个不合理，因为它会让网络变成一个单调的树形结构，如下图：

这样的坏处在于：它的“树叶”节点永远确认不了，所以tip的数量只会不断增大。一旦λ突然变大，整个网络稳定性就会失控，最终会留下一堆没有被确认的交易。

可是如果n非常大也不行，因为这样子就会增加很高的错误率。毕竟并不是所有的节点都是好的，如果有人刻意作恶释放大量虚假交易信息的话，就会对整个DAG网络造成巨大破坏。所以为了使错误率降到最低，必须要选择一个尽可能小的值，Tangle架构定的是2。之后的内容我们会以n=2的规则来和大家分析。

概率均匀分布的随机选择

我们先采取最简单的办法——在所有的Tip当中任意选取两个来进行确认。

有一点需要注意的是，由于交易确认以后广播到全网会有一定程度的时延，所以我们要这一部分的交易信息“隐藏“起来。一般我们把时延的长度定为一个时间单位，我们只要在计算的过程中自动把这一时间段之内所有交易信息全部过滤掉就可以了。

为了方便起见，我们可以把DAG的路径方向取反，然后从创世交易那一点开始遍历整个网络，如果有多条路径，便随机选择其中的一条路走（每条路径的概率相同），直到走到终点为止。而那个终点就是选出来的tip。

算法的代码如下：

export const randomWalk = ({links, start}) => { //定义起始点 let particle = start; //判断当前点是否为Tip //若是Tip则终止遍历 while (!isTip({links, node: particle})) { //找到当前点所有的路径 const approvers = getApprovers({links, node: particle}); //随机选取一条路径 particle = choose(approvers); } return particle; };

以下是算法过程的模拟图：

（图片来源： IOTA博客）

其中蓝线代表当前点的可选择路径，红线代表已走过的路径，灰色点如（7，13）为未确认交易，而那些浅色透明点如（9，11，10）就是由于单位时间的时延所隐藏起来的交易。正由于10被隐藏起来了，所以即使它已经确认了8，8仍旧会作为tip被12再次确认一遍。

加权随机策略

首先看看上一种策略有什么问题，如果是概率均匀分布的话，就说明任何一条路径被选择的概率都是相同的，这样一来就没有任何激励使比较新的交易优先被确认。那用户也就没有动力去更新他的DAG网络，他只要不断去确认那些旧的交易信息就可以了。如下图所示：

（图片来源： IOTA白皮书）

图中交易14忽略了中间最新的交易点，直接去确认像1和3那些比较旧的交易信息。按照概率均匀分布的随机选择策略，他仍旧会被其他的交易选中，没有任何惩罚。

所以为了应对这样的情况，我们必须建立合理的奖惩机制。要让这些“懒惰”的用户付出代价，最好的办法就是调整概率分布，让他们的交易被确认的可能性降低。比如我们引入一个打分的策略，每个节点都可以计算一个分数出来，然后分数越高权重也越高，被选中的概率也越大。

计算分数的方法很简单，我们先计算该点被直接或间接确认次数的总和，最后再加上1就可以了，如下图所示：

（图片来源： IOTA白皮书）

图中点3被5直接确认，被8，7，10 间接确认，所以最后的分值为1+3+1=5。

我们用一个实际的例子来看看这套机制是如何运作的。下图中，交易16为“懒惰”节点，它确认了一个较旧的交易点7：

（图片来源： IOTA白皮书）

上图中当我们运行这套算法的时候，7这个点有两条路径可走：一个是通往9，一个是通往16。但是16并不太可能被选中，因为它的分值只有1，远小于9这个节点的分值7。所以16也不太可能被确认。

可能有人要问，为什么要弄成随机呢？直接选择分值最大的那个点不就行了？通过计算机模拟，有如下DAG图：

（图片来源： IOTA白皮书）

上图中我们不难发现，所有被确认的交易点都集中在中间，而两边的点由于分值较小所以永远也不会被确认。这样以来整个网络就会剩下许多无法被确认的交易。

所以为了平衡起见，我们引入一个状态转移函数：

其中Pxy为x点到y点的概率，Hy是y点的分值，而z ~> x表示z直接确认x。α如果等于1就相当于概率均匀分布。如果α非常大那就接近于非随机状态。所以选取一个合适的α是非常重要的。以下为α=0.5时候的模拟：

（图片来源： IOTA博客）

如何防止双花（double spend）

双花一直是区块链要解决的一个头疼问题。比特币通过它交易模型[3]中的交易输入来过滤双花。我们来看看DAG有什么比较好的办法。

我们先来看一个简单情况，假设小张的账户上有10块钱，小李为0元。然后小张给小李10块钱，那小张的账户上就扣掉10块钱变成0元，小李的账户上就多了10元，如下所示：

由于在结束状态时，小张和小李账户上的余额仍旧大于等于0，所以这条交易记录我们可以认为是合理的。

如果小张要给小李15块钱，那这条交易记录就不合理，因为在结束状态时，小张的账户余额会小于0。 DAG规定任何不合理的交易都无法被确认 。

接下来我们看一个复杂的情况:

小张给小李10块钱，但是这个交易发送了两次。由于每笔交易都是独立的，所以这两笔交易都会被认为是合理的。但是事实上两笔交易合起来以后，小张的余额就变成了-10元。这显然是不对的。这种情况就是双花。如下图所示：

它的解决方案还是通过前面所说的那个Tip选取的随机遍历算法。由于T3是不合理的交易，所以从创世交易开始一步步走，是没有办法走到T3的。随着时间的推移，其中一条分支会逐步壮大，另一条分支就会被抛弃，所以这也说明了每一笔交易即使被其他交易确认，也不能立马作出判断。

那什么情况下可以做出判断呢？Tangle引入了一个 可信度 的计算方法。一条交易记录只有达到足够高的可信度（95%以上），才能被最终认定。 这套算法也是DAG的共识算法。

可信度具体计算方法就是，把整个随机遍历算法运行100次，然后获得该点被访问的次数，最终可以得到改点被访问的概率，而这个概率值就是可信度。

如下图所示，交易9的可信度只有0.54，所以这笔交易是没有办法最终敲定的。

（图片来源： IOTA博客）

随着时间的推移，上图中的交易9有可能会逐渐提升可信度，我们只有等到它达到95%以上才能最终敲定这笔交易。

今天关于DAG在交易模型和共识算法上的应用就讲到这里。下一章我来给大家讲下DAG的其他妙用。