正文

DAG技术解析与实测

巴比特区块链教程2018-08-14 06:42:00

【超越白皮书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算法通过对累积权重进行加权随机游走，选择目前网络中已存在的交易作为新增交易的参考。即被参考越多的交易路径越容易被算法选中。游走策略在1.5.0版本中也进行了优化，可将交易拓扑的“宽度”控制在一个合理范围内，使得网络更加安全。

但在平台启动初期，由于参与节点和交易数量均有限，所以很难避免一个恶意机构通过大量节点发送出海量的恶意交易使得整个网络受到影子链的攻击。因此就需要一个权威的仲裁机构来判定交易的有效性。在IOTA中，这一节点为Coordinator，它会定期对目前交易数据网络（Tangle）进行快照；包含在快照中的交易即被确认为有效交易。但Coordinator并不会一直存在。随着整个网络的运行和成长，IOTA会在未来某一时间取消掉Coordinator。

Byteball改进方案的特色在于其对于见证人（witness）和主链的设计。因为DAG的结构带来了很多偏序关系的交易，而要避免双花则需要对这些交易建立一个全序关系，形成一个交易主链。主链上较早的一笔交易作为有效交易。而由知名用户或机构担任的见证人通过不断的发送交易确认其他用户交易，从而形成主链。

以上方案也可能会对基于DAG结构的平台带来不一样的改变。以IOTA为例，因为引入了Coordinator，一定程度上降低了去中心化特性。

7.实际运行情况

7.1.正面效果

采用了除了解决安全问题之外，以上方案还可以在一定程度上解决智能合约问题。

由于DAG原生特性带来的两个潜在问题：（1）交易时长不可控，当前通过请求重发的机制需要在客户端进行一些较为复杂的超时机制设计，希望能够存在更简单的一次性确认机制；（2）不存在全局排序机制，导致系统支持的操作类型受限。因此在基于DAG技术的分布式账本平台上，较难实现出图灵完备的智能合约体系。

为了保证智能合约可以运行，需要一个机构来完成上述工作。目前的Coordinator或主链可实现类似的效果。

7.2.负面效果

作为最为直观的指标之一，DAG的TPS在理论上应该是可以无限的。如果把IOTA平台的最大TPS比喻为一个工厂的产能，那么日常运行的TPS就是工厂的日常产量。

对于最大TPS，2017年4月份的IOTA压力测试显示，网络具有112CTPS和895TPS的交易处理能力。这是在一个由250个节点所组成的小型测试网络上得到的结果。

对于日常运行的TPS，从目前可公开获取的数据看到，近期主网平均TPS为8.2左右，CTPS（每秒确认交易数量）为2.7左右。

而测试网近期的平均TPS为4左右，CTPS为3左右。

数据来源 discord bot: generic-iota-bot#5760

这是否与Coordinator的存在有关？需要实际测试来进一步论证。

8.实测分析

公开测试网的运行统计数据与诸多因素都有关系。为了进一步分析，我们继续以IOTA平台为例，搭建一个私有测试环境进行技术实测分析。

8.1.测试架构

我们本次测试搭建的各组件间关系如下图所示。

其中：

- 为了避免主网或测试网上的其他因素对测试结果的影响，我们搭建了一个40个节点的小型私有IOTA测试网络。构建过程参考“Private IOTA Testnet”项目（https://github.com/schierlm/private-iota-testnet.git），并对其中使用的IRI（IOTA Reference Implementation）版本更新为了最新的v1.5.0版本。此外，在测试过程中，使用该工具提供的Coordinator模拟工具，定期生成快照对交易进行确认。

- 使用基于Python的开源负载测试工具Locust（https://locust.io/），以便控的发送出交易数据。在开始测试后，随机向所有私有网络中的节点发送出交易数据。

- 在节点启动时，增加“--zmq-enabled”参数，以便启动IOTA的ZeroMQ支持，将节点得到的交易数据中通过消息队列方式发送给观测端。在观测端使用ZeroMQ事件解析脚本（https://github.com/lunfardo314/tps_zmq.git）观察节点交易数据情况。

8.2.测试硬件环境

服务器采用亚马逊AWS EC2 C5.4xlarge: 16 核 3GHz, Intel Xeon Platinum 8124M CPU，32GB内存，服务器间为10Gbps局域网网络，通讯延迟（ping）小于1ms，操作系统为Ubuntu 16.04。

8.3.测试场景及结果分析

8.3.1.默认PoW难度值

虽然没有“矿工”等概念，但在发送交易前，IOTA节点仍然需要进行工作量证明，以避免发送大量交易淹没网络。PoW难度值（Minimum Weight Magnitude）与比特币类似，是PoW的结果应得出“9”的位数，其中9在IOTA采用的三进制中为“000”。IOTA难度值可在节点启动前进行设置。

目前对于生产网络，IOTA的难度值设置为14；测试网设置为9。因此，我们首先采用测试网的默认难度值9来进行测试，得到以下测试结果。

由于每个IOTA的交易包（bundle）中会包含多笔transfer，因此实际处理的TPS会比发送速率高。但通过执行解析zmq的脚本可观察到，目前TPS很低。而另一个现象是，每秒可发送成功的请求数量也很低。

经过分析，原因在于测试使用的是VPS，所以在PoW时，主要使用CPU来进行运算，因此交易速度主要受发送速度的影响。

8.3.2.降低PoW难度值

将难度值降低为1后重新进行测试，得到以下结果。

从结果可看到，降低难度后，TPS会有所上升。所以目前IOTA项目的TPS并没有到达Coordinator所在的瓶颈，而主要是发送交易的客户端本身硬件以及网络等方面原因导致。IOTA社区目前在研发基于FPGA的Curl算法实现以及CPU指令集优化等工作。我们的测试结果也印证可通过这一方式继续挖掘DAG平台的性能潜力。

8.3.3.减少测试网络节点数量

由于DAG的特性，平台实际TPS和网络节点数量可能也存在着关系。因此在难度值保持为1的情况下，将网络节点数减为10后重新进行测试，得到以下结果。