区块链学习笔记之区块链演化：DAG

DAG（有向无环图）

这个世界唯一不变的是变化本身。

——斯宾塞.约翰逊

在以技术为驱动的区块链世界里尤为如此。我把区块链技术看作是一场大的社会实验。区块链的历史使命是把人类社会的物理世界在数字世界里进行映射，真正的完成人类社会的数字化。区块链的演化速度特别之快，各种技术、思想不断涌现。

区块链存在一个不可能三角问题，即可扩展性、去中心化、安全三者之间只能平衡，技术上难以一致性解决。

可扩展性（scalability），指的是系统对变化的适应能力，当负载越来越多的时候，系统性能能不能跟得上。区块链目前的可扩展性，一直是个问题。众所周知，比特币的TPS（transaction per second）只有3-4，以太坊TPS是30-40，如此低的交易数度很难再现实中落地应用。与之相比，Visa网络有47,000 TPS，纳斯达克有100万TPS。于是，一时之间出现了很多解决该问题的技术方案，主要有：分片、侧链、DAG、DHT。高吞吐量也成了新的区块链项目的必争之地。哪个项目能够解决区块链不可能三角问题，谁就会支撑区块链的大规模应用落地，就将成为划时代的区块链3.0。

今天主要讲解一下DAG（有向无环图）技术。该技术跳出了区块链的概念束缚，没有区块，准确的说，DAG还有DHT是和区块链并列的一种技术。也许要想打破区块链的不可能三角问题，就必须跳出区块链的本身，在其他技术里寻找答案，进而取代和革新区块链。

DAG究竟是什么？在数据结构的图论中，图分为有向图和无向图两大类，在有向图中进一步进行约束形成了DAG（有向无环图），所谓无环是指它是由集合的顶点和有向边构成，每条边连接一个顶点到另一个，这样，假如顶点A开始，沿着有序的边，最终循环回再次到A是不可能的（不存在环路）。那么DAG和区块链区别到底在哪里呢？我们用下面的图来说明：

区块链是一个单一链式结构；而DAG已经是图的概念了。区块链通过区块（可以包含许多笔交易）通过每个区块对前区块的hash值包含进而链接起来。在DAG中，去掉了区块，每一笔交易发出后在验证时包含之前的比较新的交易hash，通过这种方法验证之前的交易，同时链接进图状结构，以待后面的交易链接并验证和确认。

很显然，相比较区块链而言，DAG的可扩展性变得更好，处理能力会大幅度提升。区块链在处理交易的时候，必须全网达成共识才能出块。而DAG不必全网达成共识，只需要后面链接的交易来确认即可。因为不需要单独的矿工通过挖矿来验证和确认交易，所以DAG就没有矿霸垄断算力的风险，可以更好的去中心化，转账手续费用也更低（甚至没有手续费）。

既然DAG可以比传统区块链结构更高效、更去中心化，那么DAG的安全性就是我们重点考察的方面了。我们知道，比特币区块链通过UTXO的设计巧妙的解决的双花问题。并且区块链的单一链式结构，在验证方面保证了必须全网共识才能确认交易有效，这就进一步避免了双花问题的产生。而且通过POW（工作量证明）共识机制保证了如果想修改之前的交易必须拥有51%以上的算力才能做到。以太坊等其他区块链系统也继承了比特币区块链的安全性优势。很显然，DAG系统更加复杂，其安全性究竟如何呢？

IOTA是针对物联网领域的区块链项目，其应用的就是DAG技术。我们以IOTA项目的共识算法来分析和简单了解一下IOTA是如何解决双花问题的。

IOTA的DAG叫做Tangle（纠缠）。如果向Tangle中加入一笔新的交易，该交易必须引用之前的最新的没有被确认的2笔交易。

假如红色代表冲突交易（可能是双花），绿色代表新加入的交易。如下图:

从上图我们可以看到，新加入的交易在验证过程中，会发现存在两笔有冲突的交易。这样，IOTA系统就发现了这个存在问题的两笔交易。然后由交易的随机选择（和确认的累积权重）确定一个有效，另外一个无效。引用无效交易的的后续交易会被重新加入Tangle参与验证。

这里可以明确几点：

1随着新加入的交易越来越多，新的交易选择引用之前交易是一定会引用到两个冲突交易的；

2交易被确认次数越多（简单理解就是深度越深），这个交易越安全。通过一个确认比率就可以认定该笔交易是合法有效的。

从某方面来说，DAG技术确实突破了传统区块链，带来了很多优势。但是，DAG相比较区块链的设计更为复杂，因此其共识算法的安全性还有待于长时间的实际验证，并且代码的安全性也需要团队有出色的代码编写和审计能力。

备注：本文只因作者兴趣作技术研究，不做其他用途。后一篇文章将会探讨和区块链、DAG平行的DHT（分布哈希表）技术。