从区块链到DAG（二）MEERDAG的前世今生

前言

 区块链 3.0 的发展前景曾一度被人们热议，其中 DAG 被认为是继比特币、以太坊后最有潜力崛起的新一代区块链技术，那么 DAG 区块链的由来是什么？其技术理念是什么？

                           左为Aviv Zohar    右为Yonatan Sompolinsky

 DAG 与区块链原本是两项不同的技术，而将两者结合，提出“DAG 区块链”这一概念并首次现身在人们视野，离不开两位以色列人 Yonatan Sompolinsky 和 Aviv Zohar，他们是这一先锋概念的提出者。

Aviv Zohar 提出的 GHOST 协议曾被以太坊早期采用过，该协议解决的是链分叉所带来的安全性问题，分叉的区块链数据结构在 GHOST 协议规则下从一条单链演变成一个树链（ Tree chain ）。之后 Aviv Zohar 进一步提出 Inclusive 协议，在 Inclusive 协议规则下，区块链的数据结构演变成有向无环图即 DAG。随着 DAGlabs 对 DAG 不断探索逐渐建立 BlockDAG 框架概念与技术架构，期间相继发布 SPECTRE 协议、PHANTOM 协议与 GHOSTDAG 协议。

Qitmeer 在立项之初就在探索不牺牲去中心化(分区容错性)和安全性（一致性）解决可扩容性（可用性）的共识协议，发现与 BlockDAG 的设计理念不谋而合。

BlockDAG 从狭义上可以理解为一种共识协议的技术框架，旨在保证去中心化与安全性的前提下，进一步提升高并发性能的 DAG 技术。基于工作量证明 PoW 共识机制能确保区块链网络足够去中心化，因此挖矿产生区块成为其重要的技术特点，故称为 BlockDAG。

Qitmeer Team 针对 GHOSTDAG 和 SPECTRE 的共识算法做了大量的工程级优化，保留两方协议的优点，创造出了具有自身特色的 MeerDAG 协议。

一、   DAG 的基本结构

1.1   DAG 长什么样

我们都非常熟悉 Merkle 树的这种数据结构，比特币每个区块的内部就是用 Merkle 树来记录交易信息的，见图1。

图1 区块结构

可以看出来，Merkle 树属于一种有向树结构，树里的每个顶点只能指向一个之前的顶点，整个数据有个明显流动方向。

DAG 结构则可以允许每个顶点指向多个之前的顶点，整个数据流也有一个明显的方向。另一种数据结构为有向图，与 DAG 不同的是有向图允许有数据回流，整个结构的数据流不是很明显。三者之间的区别见图2。

图2 有向树、DAG图和有向图示意

1.2   区块链是一种特殊的 DAG 结构

在对 DAG 结构有一个直观的认识之后，我们来梳理一下为什么认为区块链是一种特殊 DAG 结构？

区块链是否分叉和出块速度以及广播速度有关。当出块速度超过广播速度的时候，会出现多个区块同时在广播的情况，分叉也就产生了，分叉越多安全性越差。比特币为了减少分叉，在性能和安全性中找到的平衡点为：每十分钟出一个块。现在我们假定每次出块的时间足够长，长到不会出现前一个区块还没广播结束就有新区块挖出的情况。那么这个区块链的结构就是一条单链，如图3。

图3 单链结构

实际上，由于网络延迟等原因难免出现分叉的情况，所以实际的区块链结构会如图4所示，再通过账本共识的最长链原则只取其中一条有效的主链（白色），剩下的区块（红色）里的交易信息都是无效的，不会被采纳。

图4 结合账本共识的区块链结构

现在先抛开账本共识，即先不考虑如何选取有效的主链，单从底层网络结构上看，一个典型的区块链结构如图5所示，一个典型的 DAG 结构如图6所示。

图5 区块链结构

图6 DAG结构

可以看到，两种结构唯一的不同就是 DAG 的区块可以指向之前的多个区块，而区块链的只能指向之前的唯一的区块。具体来说区块链的区块头只能包含一个区块的哈希值，指向唯一的父区块；而 DAG 结构下区块的区块头可以包含多个区块的哈希值，指向不同的前代区块。如图7所示。

图7 区块链和DAG结构的区块头指向

现在我们引入分叉系数 K，指代网络可以允许的分叉个数。当 K=0 的时，整个网络不允许分叉，如图3。这种不允许分叉的网络就是区块链。比特币就符合这个定义；以太坊虽然有叔区块的分叉，但是这些叔区块仅仅用作判断主链权重的计数，他们最后是不会被添加到主链上的（叔区块记录的交易信息不计入主链），所以以太坊也符合这个定义。DAG 网络的 K 值一定是大于 0 的整数。所以从结构上看 DAG 是区块链结构的拓展，区块链是一种特殊的、简化的 DAG 。

1.3   DAG 结构对性能的影响

简单来说，我们可以把 DAG 看成一种允许分叉的网络结构，允许的分叉个数由分叉系数 K 决定。那么一个允许分叉的网络到底意味着什么？意味着出块的速度可以超过广播速度。这一方面导致单位时间内打包的交易变多了；另一方面当一个区块 A 在被全网广播的时候，另一个分叉区块 B 也在被全网广播，最后一些节点只会确认 A，另一些节点只会确认 B，所以 DAG 允许网络中的节点在同一时间记录的不一样的信息。这两方面综合起来就使 DAG 呈现出高并发，弱同步的特点。DAG 是一种异步记账，这种记账方式可以极大的提高网络处理信息的速度，即 TPS。而区块链是一种强同步记账的网络，它要求网络中的每个节点在同一时间记录相同的信息。然而这一要求往往限制住了区块链网络处理信息的能力，使 TPS 比较低。

那么问题来了，这种允许分叉的异步记账网络要用什么样的共识？在上一篇文章中我们将详细提到基于 DAG 的共识机制。共识机制分为出块共识和账本共识，DAG 的出块共识可以和区块链一样，比如也采用 PoW，由于允许分叉，所以出块时间可以被设置的非常短。出块共识也可以和区块链不一样比如 IOTA 项目，直接取消了打包出块这一过程，只要发生交易就立刻写入网络（ DAG 图中的每个方块不是区块而是一笔笔的交易），由此获得超高速处的交易处理的能力。

DAG 账本共识要比区块链复杂得多。要如何预防节点作恶？当出现两个相互矛盾的交易时要怎么筛选？如何防止“双花”？随着底层网络结构的复杂化，账本共识也被赋予更高的要求。在后续的文章中将会着重介绍。

1.4   TXDAG 和 BlockDAG

广义的 BlockDAG (区块图)和 TxDAG (Transactional DAG , 交易型 DAG )的区别。广义上或从数据结构上说，BlockDAG 和 TxDAG 只是两种不同的数据结构。区别只是前者会将多笔交易打包成区块，账本是由区块组织而成；而后者并没有区块的概念，账本是由交易组成，也可以理解为一个区块里面只有一笔交易。由于交易有许多共同的交易描述性信息，即头部信息，这部分信息可以存在区块中，交易只需保存交易间不同的部分，这样就跳过 HASH 的过程（即挖矿），直接上链。由于 BlockDAG 既保留了 DAG 的高并发，同时一个区块内打包多笔交易，而因此 BlockDAG 账本的存储效率以及传输效率会比 TxDAG 高。

1.5   DAG 的优势

DAG 相比于区块链来说，其实是图和链的区别，对于链而言，无法只处理一个局部，因为链的入度和出度只有一个，不能把链上的节点拆成好几个节点去处理，但是对于图却可以，因为图可以有多个出度，那么可以同时处理多个出度连接的节点。

对于链式网络而言，不是节点的处理能力不强，只是链式结构不能并行计算，浪费的时间其实主要为等待时间：一个是发起交易，需要将交易同步所有节点；另一个确认时间，当有一个节点确认，需要向全网同步。对于 DAG 而言则不存在这样的问题，钱包发起交易时不需要等待自己之前有多少交易，只需要经历局部校验、全网广播、其他局部校验，相当于是把交易确认分散化，每一个节点都在做类似于拼图的工作，把自己的和别人确认的交易拼接起来。

因此总结发现 DAG 有着以下几个优势：

1.5.1   交易速度块

在达到与比特币和以太坊相同级别的去中心化和安全性的同时，DAG 局部处理和并行结算可以使得交易速度大幅度提升，使交易吞吐量 (TPS) 和最终延迟方面超过两个数量级的提升。

1.5.2   拓展性强

由于 DAG 支持异步记账，网络中的节点无需等待其他节点数据同步即可并行处理新的交易，避免了时间浪费，提高了交易效率，让每一个参与记账的节点能够快速得到大幅度延展。因此DAG 很适用于支付类项目，例如 Qitmeer Team 所倡导的跨境小额支付和普惠金融业务场景。

1.5.3.   作恶难度更大

相比于链式结构，在 DAG 中恶意修改的难度会大很多，因为 DAG 拥有着很多的出度和入度，假如要修改某一个节点，那么对应的出入度都要进行修改。

二、   MeerDAG的前世今生

2.1   DAG 技术的起源

2013年在著名的区块链发源地 bitcointalk.org 一名 ID 为 Avivz78 的以色列希伯来大学学者，他提出将 DAG 概念作为一种共识算法引入到区块链结构中，并创造出 GHOST 协议。

图8 GHOST协议

在 GHOST 协议提出后，Yonatan Sompolinsky 提出另一种新的设想，新产生的区块指向所有已知的分叉末端区块，即一个区块有多个父亲，此时区块链就从一条链变为多条分叉链共同组成的的结构，这样的链结构就被叫做 DAG(有向无环图)。

图9 DAG(有向无环图)

2016年发布 SPECTRE 技术协议论文，该论文进一步完善了技术架构的细节，形成了初代 BlockDAG 协议雏形，并提出了网络延迟无参数化（或称延迟参数自适应）的宏伟构思。

图10 SPECTRE区块链示意图

2018年，DAGlabs 推出了 PHANTOM 协议，解决了 SPECTRE 协议不能交易线性排序的问题，并在不断优化后形成了 GHOSTDAG 协议，算是第一个工业级的 BlockDAG 协议，同时也标志着 BlockDAG 走向成熟。

图11 连通度为2的GHOSTDAG协议下的DAG图

Yonatan Sompolinsky 在 GHOSTDAG 协议论文结尾处，曾设想将 GHOSTDAG + SPECTRE 结合起来的可能协议，但最终没有详细展开介绍。

三、  MeerDAG 的技术选型的思考

3.1   MeerDAG 技术选型思考

在 Qitmeer Network 的第一个阶段麦加时期（Mecca Network），正值扩容技术探索的热潮，面对着众多链上链下主流扩容方案，在进行 Qitmeer 公链技术选型的时候，也面临着艰难的抉择。

在扩容技术选型上，业界普遍面临着一个不可能三角的难题， 无法同时达到可扩展性（Scalability）、去中心化（Decentralization）、安全（Security），三者只能得其二。当时的 Qitmeer 团队也同样面临着这样的难题，在研究过众多扩容方案后，最终一种称为 BlockDAG 的技术受到了团队的青睐。

3.2   SPECTRE 协议简介

SPECTRE 是一个支持快速确认的 blockDAG 协议。SPECTRE 的共识算法是一个投票算法，一旦发现有冲突交易，则包含冲突交易的区块作为候选人接受所有区块的投票，每个区块一票。SPECTRE 的投票有放大效应，比如说区块会跟随其过去集中票数的大多数投票，所以收敛速度很快，一点细微的票数差异就能造成优胜者的巨大优势。让诚实区块投票给诚实的区块，后边的诚实区块会给前边的堆叠算力，从而让恶意攻击失败，保障网络的安全性。

SPECTRE 只能保证诚实区块的快速确认，对于发布时间接近的两个冲突区块，SPECTRE 的确认时间是不确定的，这就是 SPECTRE 提出的弱活性的概念，即不能保证所有区块都能在某个合理的时间内得到最终确认。

SPECTRE 是基于交易系统的共识协议，在交易系统中只有作恶者才能制造双花交易，也就是说，双花交易并不会对诚实区块造成太大的影响。而制造双花交易对于时间的控制又是异常苛刻，一般情况下很难造成攻击。因此 Qitmeer Team 认为 SPECTRE 这个弱活性的问题在实际项目中是可以接受的。

3.3   GHOSTDAG 协议简介

从上面 SPECTRE 的简介可以看出，SPECTRE 可以很好的排除冲突交易，抵御攻击。如果项目和比特币一样只作为支付用途的话，SPECTRE 协议的快速确认已经足够，但若是要集成智能合约功能，那 SPECTRE 无法胜任。

因为 SPECTRE 只能对冲突交易做一个相对排序（判断冲突交易间的先后顺序），无法给所有的区块都做一个绝对排序。又因为智能合约的语言是图灵完备，就像我们编写一段计算机程序一样，需要按严格的顺序执行各种运算，所以，具备智能合约功能的网络都有一个特征：网络中的交易可以按时间先后做线性排序（时序性）。

对此 Yonatan Sompolinsky 新设计了 GHOSTDAG 协议来对 DAG 区块形成一个线性顺序，其中 SPECTRE 和 GHOSTDAG 则是两个完整的独立协议，而不是一个协议对另一个协议的补充。

GHOSTDAG 的挖矿机制和 SPECTRE 一样，会产生同样类型的 DAG 结构，不同的是 GHOSTDAG 通过对区块连通度分析，判定区块诚实还是恶意，按照分类对区块排序，对 DAG 区块产生一个严格的线性顺序，通过线性顺序来判断冲突交易有效性。

GHOSTDAG 协议不仅使 DAG 获得了交易线性排序能力，也解决 SPECTRE 协议的弱活性问题。同时，GHOSTDAG 协议也是第一个支持交易线性排序的 BlockDAG 协议。

3.4   MeerDAG 协议

Yonatan Sompolinsky 在 GHOSTDAG 协议论文结尾曾设想的 GHOSTDAG + SPECTRE 结合起来的可能协议，更多的是在思路上提供指导，侧重点还是在论证算法的严谨性，涉及到诸多工程实践问题，还需要依据实际情况不断实践与测试，其中最典型的一个问题就是性能，如果按照原文的参考算法直接去实现，性能几乎是没法接受的。

Qitmeer Team 考虑到公链底层的应用场景主要是普惠金融、数字资产交易、供应链管理。在综合考虑区块的奖励机制和账本共识对于线性排序能力要求，同时兼顾对价值交换体验更加重要的交易确认速度。虽然 GHOSTDAG 的蓝色集（诚实区块）比较难以稳定，确认时间会比 SPCTRE 长很多。但由于区块奖励对于确认时间的要求不高，并不会对网络造成影响。所以，选择了 GHOSTDAG 协议为基础共识协议、 SPECTRE 协议作为辅助共识协议。

MeerDAG 这种融合了 SPECTRE 和 GHOSTDAG 的混合共识方案，便是一个符合经典区块链设定（开放，公平，安全，可扩展性）、并且能兼容经典区块链模型 UTXO 。虽然经典区块链会把最长链之外的区块全部抛弃，但 MeerDAG 的 BlockDAG 协议的合作模型，会保留所有的区块，因此，保障真实交易级的高吞吐量的同时也能对交易进行快速确认。其次，BlockDAG 是基于最重链规则，能达到跟比特币相当的51%容错性。再者，BlockDAG 网络是不存在任何特殊节点的, 也不对节点在线与否做要求。在挖矿中，这种协作模型在安全性、开放性、公平性和可扩展性之间实现了经典区块链度量的理想平衡，通过工作量证明机制，可以自由进出网络。

在Qitmeer Network Medina 时期，网络引入真实算力环境测试，团队不断迭代 PoW 算法并提升算法运行效率，充分保留 GHOSTDAG + SPECTRE 协议优点，在工程实现中不断降低协议的实现难度，例如：按照初版的 GHOSTDAG 算法论文，算反锥体是要去穷举的，算法复杂度是 O（n^3），经过大量工程级别测试将复杂程度降低两个数量级达到 O（n），极大的满足可用性需求。在保证安全性、去中心化和公平性的基本要求下，TPS 性能得到最大的释放。为高性能的区块链网络提出了自己的解决方案，Qitmeer Network旨在构建为去中心化应用程序提供的一个更高效、安全、开放的去中心化平台。

Qitmeer Team 创新性的将 GHOSTDAG+SPECTRE 协议结合起来并形成具有自身特色的 MeerDAG 协议，成为新一代 BlockDAG 的技术原型。Qitmeer 的 BlockDAG 底层网络核心定位便是作为价值流通网络， 在 Layer2 层结合 Meer DAG驱动的可拔插虚拟机系统构建丰富的区块链应用，拥抱整个区块链生态。

参考资料：

[1] 从区块链到DAG（二）—— DAG的基本结构：https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg

[2] 从区块链到区块DAG：https://www.youtube.com/watch?v=tk38AAV_whw

[3] Jeff Zhou：DAG高速异步区块链技术：https://www.jianshu.com/p/45d73e0e74ec

[4] GHOST, SPECTRE, PHANTOM的技术原理：https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q

[5] Qitmeer Team：《Qitmeer中文白皮书》：https://github.com/Qitmeer/whitepaper/releases/download/v0.6.5/qitmeer_whitepaper_cn.pdf

[6] Yonatan Sompolinsky、Yoad Lewenberg 和 Aviv Zohar： 《SPECTRE：工作量证明事件的排序: 通过递归投票来确认交易》 https://eprint.iacr.org/2016/1159.pdf

[7] Sompolinsky、Yonatan、Shai Wyborski 和 Aviv Zohar：《PHANTOM GHOSTDAG：可扩展的中本聪共识的泛化》 https://dl.acm.org/doi/abs/10.1145/3479722.3480990

郑重声明：本文版权归原作者所有，转载文章仅为传播信息之目的，不构成任何投资建议，如有侵权行为，请第一时间联络我们修改或删除，多谢。