【超越白皮书3】DAG技术解析与实测

摘要火币区块链应用研究院从技术角度对基于有向无环图（DAG）数据结构的分布式账本技术进行研究，并通过对典型代表项目IOTA的具体技术测试，主要得到以下研究结果:DAG技术与狭义的区块链技术相比，有其创新之处，理论上在不考虑作恶情况下可实现高可扩展性和高去中心化，因此存在一些安全隐患。

DAG项目往往以偏中心化的方式来实际运行，即降低去中心化程度来提高安全度，但同时其交易速率并没有接近理论上限。

采用基于VPS（CPU进行PoW）的40个节点网络对代表性项目IOTA进行交易压力测试，可发现TPS很低：可达到的最优结果为4.19。

经分析，其性能瓶颈目前主要还在于硬件的算法实现本身。

如果采用FPGA等其他方式来实现，应可进一步挖掘出DAG的性能潜力。

同时，为保持良好的交易处理能力，应建立足够规模的节点网络。

报告正文1.引言区块链是一种分布式账本技术，而分布式账本技术却不局限于“区块链”这一种技术形式。

在数字经济发展的浪潮中，为了改进原有技术、满足更多的实际业务应用场景，更多的分布式账本技术正在被探索和应用当中。

有向无环图（Directed Acylic Graph，以下简称“DAG”）是其中的代表之一。

DAG技术以及它背后的设计思想是什么？实际应用效果如何？我们尝试通过对DAG技术进行深层解析以及对代表性项目IOTA的实际测试运行获得分析结论。

另外需要注意的是：测试得到的指标数据结果不是也不应被视为是对IOTA平台或项目最终效果的证明或确认。

特此声明。

2.主要结论经过研究与测试分析，我们得到以下主要结论及技术建议：DAG技术与狭义的区块链技术相比，有其创新之处，理论上在不考虑作恶情况下可实现高可扩展性和高去中心化，因此存在一些安全隐患。

DAG项目往往以偏中心化的方式来实际运行，即降低去中心化程度来提高安全度，但同时其交易速率并没有接近理论上限。

采用基于VPS（CPU进行PoW）的40个节点网络对代表性项目IOTA进行交易压力测试，可发现TPS很低：可达到的最优结果为4.19。

经分析，其性能瓶颈目前主要还在于硬件的算法实现本身。

如果采用FPGA等其他方式来实现，应可进一步挖掘出DAG的性能潜力。

同时，为保持良好的交易处理能力，应建立足够规模的节点网络。

3.DAG介绍3.1.DAG原理简介DAG（Directed Acyclic Graph，有向无环图）是一种数据结构，表示的是一张有向图，并且在这个图中，从任意顶点出发都无法回到该点（无环），如图所示： 基于DAG技术的分布式账本（以下简称DAG）技术在近年来被提出后，被很多人认为有希望替代狭义上的区块链技术。

因为DAG在设计时的目标就是保留区块链的优点并且改进区块链的缺点。

和传统线性区块链结构不同，以IOTA为代表的分布式账本平台的交易记录之间形成的是一个有向无环图的关系结构，如下图所示。

3.2.DAG特性由于采用了不同于以往块链式的数据结构，基于DAG的分布式账本技术，拥有高可扩展、高并发等特性并适用于物联网场景。

3.2.1.高可扩展性、高并发性传统线性区块链（如以太坊）的数据同步机制是同步的，这可能造成网络的拥堵。

DAG 网络采用异步通讯机制，允许并发写入，多个节点可以按照不同的节奏同时交易，而不必有明确的先后顺序，因此同一时刻网络的数据可能不一致，但最终会是同步的。

3.2.2.适用于物联网场景在传统的区块链网络中，每个区块中有很多笔交易，矿工打包好后统一发送，涉及到多个用户:而在 DAG 网络中并没有“区块”的概念，网络的最小单元是“交易”，每笔新的交易需要验证前面两笔交易才能进行，这样DAG网络并不需要矿工传递信任，转账无需手续费，这使得 DAG 技术适用于小额支付。

4.技术思路分析不可能三角（trilemma），或被称为“三难困境”，是指在特定的情形下，只能选择三个有利选项中的两个或者是在三个不利选择中必须选择一个。

这一类选择困境在宗教、法律、哲学、经济学、企业管理等多种领域均有相关案例。

区块链也不例外。

区块链中的不可能三角为：可扩展性（Scalability）、去中心化（Decentralization）、安全性（Security）这三者中只能选择其中两个。

如果按照这种思路来分析DAG技术，根据前文介绍，那么无疑DAG已占据了去中心化、可扩展性这两个方面。

DAG的去中心化和可扩展性可认为是一体两面的，因为基于DAG数据结构带来的异步记账特性，同时实现了高度的参与网络节点的去中心化和交易的可扩展性。

5.存在问题既然是数据结构上的特性同时带来了去中心化和可扩展性，所以按照不可能三角的理论来推测，安全性会是一个隐患。

但由于DAG是一个比较创新、特殊的结构，是否也可比较完美的实现安全性？目前从实际效果来看并非如此。

5.1.双花问题DAG 异步通讯的特性为双花攻击创造了可能。

例如，攻击者在网络的两个不同的位置添加了两笔冲突的交易（双花），交易在网络中不断向前验证，直到它们出现在同一笔交易的验证路径上，网络才会发现冲突，这时这两笔交易汇聚成的共同祖先节点才能判断哪一笔交易是双花攻击。

而如果将交易路径控制的过短又会存在类似“Blowball”的问题：当极端情况下绝大多数交易都较为“懒惰”（Lazy Tip）、只参考早期交易时，交易网络会形成一个以少数早期交易为核心的中心拓扑。

这对依赖于交易的不断增加而提高网络可靠性的DAG来说，也不是一件好事。

因此，目前对于双花问题，需要综合考虑实际情况进行设计。

不同的DAG网络有各自的解决方案。

5.2.影子链问题由于存在双花的潜在问题，当攻击者可以构建出足够数量的交易后，就可能从真实的网络数据中分叉出一个欺诈性分支（影子链），其中包含着双花交易，然后将这个分支合并到DAG网络中，特定情况下这个分支有可能取代原有交易数据。

6.目前改进方案简介目前项目主要都是通过牺牲一部分DAG的原生特性来保证安全性。

IOTA项目中采用了马尔科夫链蒙特卡洛（Markov chain Monte Carlo，以下简称MCMC）的方式来解决该问题。

IOTA为交易引入了累积权重（Cumulative Weight）的概念用来记录该笔交易被引用的次数，目的是表示其交易的重要性。

MCMC算法通过对累积权重进行加权随机游走，选择目前网络中已存在的交易作为新增交易的参考。