DAG(有向无环图)是不同于主流区块链的一种分布式账本技术，把同步记账提升为异步记账，被不少人认为可以解决传统区块链的高并发问题，是区块链从容量到速度的一次革新。但是，DAG技术真的有这么强大吗？
本文旨在向读者介绍DAG技术的架构、发展趋势以及典型应用，希望能为大家思考区块链的未来发展提供一种新的思路。
作者：李强（Bsure创始人）
*转载请留言后台
01
什么是DAG？
DAG：Directed Acyclic Graph，中文意为「有向无环图」。
DAG原本是计算机领域一种常用数据结构，因为独特的拓扑结构所带来的优异特性，经常被用于处理动态规划、导航中寻求最短路径、数据压缩等多种算法场景。
再看传统区块链和DAG的区别，简单的说：
1）单元：区块链组成单元是Block，DAG组成单元是TX（交易）；
2）拓扑：区块链是由Block区块组成的单链，只能按出块时间同步依次写入，好像单核单线程CPU；DAG是由交易单元组成的网络，可以异步并发写入交易，好像多核多线程CPU；
3）粒度：区块链每个区块单元记录多个用户的多笔交易，DAG每个单元记录单个用户交易。
传统区块链技术存在的几个问题：
1）效率问题：传统区块链技术基于Block区块，比特币的效率一直比较低，由于BlockChain链式的存储结构，整个网络同时只能有一条单链，基于POW共识机制出块无法并发执行；例如比特币每十分钟出一个块，6个出块才能确认，大约需要一个小时；以太坊大幅改善，出块速度也要十几秒。
2）确定性问题：比特币和以太坊存在51%算力攻击问题，基于POW共识的最大问题隐患，就是没有一个确定的不可更改的最终状态；如果某群体控制51%算力，并发起攻击，比特币体系一定会崩溃；考虑到现实世界中的矿工集团，以及正在快速发展量子计算机的逆天算力，这种危险现实存在。
3） 中心化问题：基于区块的POW共识中，矿工一方面可以形成集中化的矿场集团，另一方面，获得打包交易权的矿工拥有巨大权力，可以选择哪些交易进入区块，哪些交易不被处理，甚至可以只打包符合自己利益的交易，这样的风险目前已经是事实存在。
4）能耗问题：由于传统区块链基于POW算力工作量证明，达成共识机制，比特币的挖矿能耗已经与阿根廷一个国家耗电量持平，IMF和多国政府对虚拟货币挖矿能源消耗持批评态度。
Digiconomist数据表明：全球挖矿业务总计，每年产生约2.9亿吨碳排放。
由于以上问题，有人提出疑问：为什么一定需要区块呢？DAG技术被用于尝试解决区块链的上述问题。
02
DAG起源
最早在区块链中引入DAG概念作为共识算法是在2013年，bitcointalik.org由ID为avivz78的以色列希伯来大学学者提出，也就是GHOST协议，作为比特币的交易处理能力扩容解决方案；Vitalik在以太坊紫皮书描述的POS共识协议Casper，也是基于GHOST POW协议的POS变种。
后来NXT社区有人提出用DAG的拓扑结构来存储区块，解决区块链的效率问题。区块链只有一条单链，打包出块无法并发执行。如果改变区块的链式存储结构，变成DAG的网状拓扑可以并发写入。在区块打包时间不变的情况下，网络中可以并行打包N个区块，网络中的交易就可以容纳N倍。
此时DAG跟区块链的结合依旧停留在类似侧链的解决思路，交易打包可以并行在不同的分支链条进行，达到提升性能的目的。此时DAG还是有区块的概念。
Nxt社区提出的DAG of blocks
2015年9月，Sergio Demian Lerner发表了 《DagCoin: a cryptocurrency without blocks》一文，提出了DAG-Chain的概念，首次把DAG网络从区块打包这样粗粒度提升到了基于交易层面，但DagCoin本身是一篇论文，没有代码实现。
DagCoin的思路，让每一笔交易都直接参与维护全网的交易顺序。交易发起后，直接广播全网，跳过打包区块阶段，达到所谓的Blockless。这样省去了打包交易出块的时间。如前文提到的，DAG最初跟区块链的结合就是为了解决效率问题，现在不用打包确认，交易发起后直接广播网络确认，理论上效率得到了质的飞跃。DAG进一步演变成了完全抛弃区块链的一种解决方案。
2016年7月，基于Bitcointalk论坛公布的创世贴，IOTA横空出世，随后ByteBall也闪亮登场，IOTA和Byteball是头一次DAG网络真正技术实现，也是此领域最耀眼的领军者；此时，号称无块之链、独树一帜的DAG链家族雏形基本形成。
一句话来概括：DAG是面向未来的新一代区块链，从图论拓扑模型宏观看，从单链进化到树状和网状、从区块粒度细化到交易粒度、从单点跃迁到并发写入，这是区块链从容量到速度的一次革新。
03
DAG发展现状
DAG系当前的代表项目，最知名的无疑是DAG三架马车---- IOTA、字节雪球、Nano（原来的Raiblocks），作为最新的分布式账本主力竞争技术，DAG开始引发大量关注始于IOTA在2017年下半年市值冲入币值排行榜第四名，之后基于DAG技术的新项目不断进入人们的视野。
1）IOTA
IOTA背后最主要的创新Tangle（纠缠），是一个基于DAG全新设计的分布式账簿结构，是一个既没有块也没有链的区块链。在Tangle中，每一个节点代表的是一个交易。IOTA里没有区块的概念，也没有挖矿和矿工的概念，这就代表没有交易费，整个网络的吞吐量也很高，这是IOTA的最吸引人的亮点之处。
Tangle的核心原则与区块链一致，依旧是一个分布式的数据库、P2P网络，以及共识算法来验证交易。Tangle与传统区块链之间的主要区别，就是Tangle数据结构以及共识机制。
在IOTA里没有区块的概念，取而代之的是交易网络，每一个交易都会引用过去的两条交易记录Hash，这样前一交易会证明过去两条交易的合法性，以及间接证明之前所有交易的合法性。
这样，整个网络都参与交易合法性的验证，而不像传统区块链，只有全网中的矿工（或PoS的权益所有人）这样少量节点来验证交易合法性。因此，IOTA的共识就是它自身内化特性，可以使它在没有交易费用的情况下进行规模化使用。IOTA中不再有区块的概念，共识的最小单位是交易。
The Tangle另外一个强大之处，就是可以随意的让交易从网络中剥离出来或者合并回去。这种离线异步处理的能力在物联网领域应用中尤为重要。
IOTA目前的问题是：
第一，MIT报告指出，IOTA使用了自己开发的哈希算法curl，但是curl算法的哈希值极易发生碰撞，于是就能伪造数字签名。
第二，因为共识是由全网交易确定的，那么理论上来说，如果有人能够产生1/3的交易量，他就可以将无效交易变成有效交易。另一方面，由于IOTA无手续费，所以没有矿工激励，IOTA面临着拒绝服务攻击和垃圾信息攻击可能，就像不收物业费的小区，靠业主自治很难扫清不法份子，
第三，IOTA引入闭源的中心化组件Coordinator来对全网交易进行检查（例如双花），如何有效移除Coordinator并建立一个具有良性激励机制的去中心化「Coordinator群体」，IOTA还没有给出解决方案。
2）Byteball（字节雪球）
Byteball被称为区块链3.0的代表。具有DAG体系家族中最完善的应用生态，Byteball钱包内置丰富功能，包括类似Appstore模式的BotStore，自由开发者可以在上面自由开发应用，开发者非常活跃。
Byteball在DAGCoin的基础上，创新性引入主链与见证人概念，鼓励验证多个父辈交易单元，形成一个随着交易增长、相互验证，安全性不断加强的数字签名Hash网络，Byteball创造性的发明了「主链」概念，也就是经过见证人认定的最短路径MC的Parents优选算法。主链创造了一个全网共识确定的交易时间序列，优雅地避免了双花问题。
Byteball中「见证人」真正意义就是形成共识机制；12个「见证人」发布的交易单元，在理论上无限宽广的DAG并发交易网络中划出了一道确定性的交易时间序列。正是这道无限延伸基于时间的确定性交易序列，打造了Byteball中的主链，在宽广无序的有向无环哈希世界中形成了强健有序的唯一主干。基于见证人+主链的共识机制，双重支付等问题得到了轻松解决。
Byteball取消了区块链和工作量证明挖掘的概念，而是选择了DAG数据存储技术。与基于传统区块链的加密货币相比，这具有强大的优势，Byteball中的所有交易都是以加密方式相互关联的。新产生交易将添加到tips交易单元后面。这样让网络上的所有节点（用户）都参与验证交易，完全的去中心化。
这不仅可以更快地验证付款，还可以让网络保持足够的分散。避免在比特币中的一些问题：例如可能威胁网络的大型集中式矿池；同时Byteball通过收取存储在DAG网络的每字节数据存储费用，通过类似Gas机制减少网络上的SPAM垃圾信息。
有人说Byteball的Witness存在中心化依赖，这里也为Witness正名，在Byteball的Witness节点设计中，witness节点是高度安全的，仅仅能发出见证单元，无法接触交易，所以Witness并不是矿工，Witness扮演的是WatchMan的角色，帮系统锚定交易发生时间顺序，没有留出作恶的空间；另外Witenss数量也可以根据需要设置和选择，并不局限于目前的12个见证人。
Byteball由于每个交易都有发起者的私钥签名，同时每笔交易都验证与引用从前发生的交易，以此编织成一个巨大的网络，对网络的篡改牵一发而动全身，同时不可能有人拥有全网所以用户的私钥，所以Byteball具备银行级最终确定性。
Byteball的问题是：由于主链算法和见证人发布频率有关系，交易确认的时间是不确定的；由于Byteball基于关系数据库来存储数据，SQL语言过于紧耦合算法逻辑，在一定程度上限制了Byteball目前的扩展能力和速度。
3）NANO(XRB)
Nano（原名RaiBlocks XRB），是一种基于区块点阵(Block Lattice)结构的新型加密货币。
Nano创新性地采用了一个用户一条链的方式，只记录自己的交易，也只有自己可以修改记录，不与其它帐户共享数据，从而使所有的交易都可以并行执行，能提供秒级的交易速度和无限可扩展性，并且允许他们异步地更新到网络的其余部分，从而以极小的资源开销获得快速的交易确认。
Nano一个节点可以存贮所有账户的历史账本，也可以只存贮每个账户的最后修剪记录。当一笔交易发生的时候，发出金额的一方会生成一个send tx的区块，包含记录扣除的金额；而收款账户则生成receive tx区块记录对应获得的金额。交易数据的收发是可以异步进行的，所以就算同时有多笔金额汇入一个账户也没有问题，最终的金额是收到的金额的加法。如果接收方不在线也没关系，未到账的金额会单独标记，等到接收账户上线之后，这笔金额就会从未结算区打入接收区块，完成交易。
NANO使用了DPOS共识机制，账户可以指定代表为其投票，得票最多的代表将处理分叉，这个代表会将分叉广播到网络，并观察来自高权账户节点在固定时间内的投票接结果，以此来确定保留哪一个区块。DPOS可以保证区块的合理低能耗运行。NANO也使用到了POW机制，确认交易需要非常少的工作证明（PoW）。
NANO的问题是：没有被充分测试、缺乏同行评议，共识算法可能有严重缺陷的风险。例如，如果没有足够的法定人数投票来解决网络冲突会发生什么？另一个大问题：如果NANO网络的某些部分长时间分离，当分离的网络重新加入时会发生什么？重新加入的网络是否会在不可避免发生的投票过程中瘫痪？
04
DAG革新与趋势
DAG技术正快速的发展与革新，除了三驾马车之外，新出现的DAG项目在共识算法、去中心化机制、速度与并发上，都取得了更新的进展，近期引发大家重点关注的项目包括：
1）HashGraph（哈希图）
Hashgraph是由Leemon Baird开发的一种Gossip八卦协议共识算法。所有节点随机地与其他节点共享其已知交易，因此最终所有交易可传递到各个节点。Hashgraph速度非常快（每秒交易250,000次以上），由于闭源和专利，HG适用于私链或者联盟链，短期内不会应用于公链和得到规模验证。
Hashgraph开创性的在公链环境下做异步BFT共识，传统BFT的一大问题是消息复杂度太高，大量消耗系统的网络带宽，无法很好的应对动态网络。这里Hashgraph引入了传统Gossip Protocol，并加以独特的创新，另外再加上虚拟投票机制，这样在需要共识的时候不会引起突发大规模消息传递风暴。
Hashgraph和Algorand通过从不同角度改良了BFT应用的场景和条件来使得BFT共识可以被应用到公链系统中，HG通过八卦传播哈希图以及基于哈希图做虚拟投票将传统共识所需的瞬时通信要求降到了最低，并且本地计算保证了共识高效性。
最新的Hashgraph的商业介绍书上讲述计划切换到 POS，并且支持DOPS，并可以让不运行全节点的持币者选择代理人，分享收益。
Hashgraph集各家所长，在扩展性，安全性和共识达成成本上都有很大突破，但是技术难度大，还未在大规模公链环境下运行，如果能够实现严密的数学及应用检验HG白皮书中描述，那么 Hashgraph足以成为可信互联网上探索的一个重要里程碑。
2）SPECTRE/PHANTOM
SPECTRE Protocol采用了Block+DAG的「区块有向无环图」技术，可以并行挖矿，从而带来更大的吞吐量和更快的交易确认时间；2018年2月SPECTRE的扩容协议–Phantom发布，能够大大扩充网络交易容量，并兼容智能合约。该项技术是「对中本聪提出的区块链的泛化」，解决了前者需在安全性与扩容能力之间进行取舍的问题，因而更加适合建立速度更快或规模更大的区块。
不同于闪电网络等链下解决方案，PHANTOM是链上扩容方案。同时PHANTOM采用线性排序会在一定程度上牺牲SECTRE可实现的交易确认速度。
3）Hycon
Hycon是韩国的DAG项目，定位平台型公链，还要做生态，包括价值交换媒介去中心化交易所，准备募集近一个亿美金的资金，另外70%是要靠以后挖矿挖出来的。
Hycon整个生态系统的建立分为三个阶段：价值交换媒介、区块链平台以及去中心化交易所，旨在打造集价值交换、商业应用以及 Token流通等属性于一身的价值生态系统。其中，区块链平台是整个生态系统的核心，将解决交易确认速度低、吞吐量有限的区块链性能瓶颈，从而实现商业级应用。
Hycon公链平台的主要特性是：快速交易确认时间、链上交易扩展性（在2MB/S的连接中高达3000TPS交易吞吐量）、同步出块（可基于DAG结构位置而不是时间先后链接区块）以及智能合约。
4）Algorand
最近在海内外大火的明星项目Algorand，目标是建立一个低能耗、高速度、民主化、可拓展性好而且几乎不会出现分叉的分布式账本。Algorand没有引入激励机制或发行数字加密货币。Algorand由图灵奖得主、MIT教授SivioMicali募集400万美元开发。
GHOST、SPECTRE和Meshcash是最近用来提升比特币吞吐量的部分提议，通过使用树或者有向无环图来代替底层区块链的账本结构，解决区块链分叉的冲突问题。这些协议使用POW证明共识，通过精心设计的树/图分支之间的选择规则，能大幅提高吞吐量。
中国的新技术领域跟随创新的脚本并不缓慢，基于DAG的区块链系统正在快速涌现，但在底层共识设计革新和方法创新上还有差距，我们统计了部分目前国内基于DAG技术的典型项目：
1）ITC（万物链）
基于区块链的安全物联网轻操作系统，解决方案融合了区块链技术，结合密码学非对称加密技术，半同态加密秘文计算技术，以及无数据中心的分布式架构，旨在解决目前物联网严重的安全问题，满足物联网高度并发的使用场景，实现万物互联互通。
2）TrustNote
TrustNote是支持POW挖矿的DAG公有链，具有创新的双层共识机制，面向数字通证发行、区块链游戏和社交网络等应用场景，基础代币称为「TTT」，核心在于底层公链开发，应用生态可以应用在金融征信、信息安全、物联网、游戏、社交等领域。目前，已经在应用领域有所涉及。
3）Bsure（必信链）
Bsure是专业数字保险和大健康区块链智能平台，构建基于DAG技术的数字保险和健康医疗行业公链。目前测试链已经上线，并在开发Bsure.cloud链云基础设施，赋能健康医疗和保险科技行业产品与服务创新。
Bsure行业公链平台的开发中的主要特性包括：快速交易确认时间（instant payment）、交易扩展性（通过内存计算，优化主链算法，提升交易并发能力）、Package+DAG共识创新（结合本地偏序包和公证人主链全序算法），分层赋能架构：包括独立的智能合约层、去中心化存储层、DAPP应用层、同构跨链等等。
4）Nerthus（纳尔图）
2017年下半年发起的低调项目，Nerthus基于的是字节雪球DAG结构加以改良，并使用GO语言实现了服务层，核心层，和应用层三层架构。目前还没上交易所。纳尔图应该是中国第一个的基于DAG技术开发的平台型公链项目，项目正在开发中。
5）CyberVein（数脉链）
CyberVein是基于DAG架构，包含了自己的Vein编程语言、虚拟机、新型智能合约的底层系统，致力于从技术层面和商业逻辑两方面解决大数据时代面临的数据价值定义和管理问题。
CyberVein由DAG+PoC机制+数据库虚拟机共同完成的，DAG架构只是CyberVein的一部分，CyberVein平台上还可以创建自己的智能合约，拥有操作数据库的虚拟机和编程语言，共识机制还有创新。如果把项目比作一个精装修楼房来说的话，DAG架构仅仅只是CyberVein的地基，数据库虚拟机是楼房的钢筋水泥，编程语言和智能合约是每一间房子的装修，PoC贡献证明是楼房的智能门禁系统！
6）Mixin
Mixin计划建立一个最大的对开发者友好的移动区块链网络，无限吞吐链接所有现存的区块链，基于DAG实现。
Mixin规划宏大，包括跨链、无限吞吐、基于手机号的账号和资产管理等等，立志要做中国未来用户量最大的公链。目前一款基于其的Dapp-Mixin Messenger测试版已经上线。另外几个基于Mixin的项目如Pressone,Motion,Show.one也在持续开发。
7）Travelflex
基于DAG技术的去中心化社交旅游网络和支付系统，旨在解决比特币等其他代币目前面临的可拓展性问题。
05
小结
凡事有利必有弊，DAG的速度快，吞吐量高，但作为一个很年轻的数据结构，安全性和一致性还有待更多验证和认可，应用场景也还不像传统区块链那么广泛；但DAG技术的优势和创新速度已经崭露头角，越来越多后继基于DAG的创新项目和DAPP正源源不断的迅速涌现。
当前人们喜欢把DAG与传统区块链做比较， 但是我们认为，DAG仅是分布式账本应用的一种技术实现，部分创新的区块链项目已经在探索Block+DAG的融合模式。
从广义上讲，DAG仅是广义区块链的一种组成技术。区块链和Token经济驱动作为关键组件，与AI人工智能、大数据、AR/VR虚拟现实、5G高速无线网络等共同迎接第四次价值互联网浪潮的到来。
利益相关：本文作者系DAG应用Bsure创始人李强
主要参考资料：
1、SergueiPopov*：The Tangle（IOTA官网白皮书v1.3）
2、ByteballWitePaper（BYTEBALL官网白皮书）
3、MIT：Cryptographic vulnerabilities inIOTA
4、轻度：DAG也许是真正的区块链
5、五火球教主： 一大波DAG公链正在接近
6、NPC 节点计划：区块链败局已定，Hashgraph 才是未来？ | 寻找下一个以太坊
7、雷锋网：扩容协议PHANTOM本周问世，推动DAG加区块链应用进展支持智能合约
8、NPC 节点计划：目标宏大的韩国 DAG 生态系统：Hycon 测评
9、Dagfans：https://dagfans.org/paper/2018/04/08/DagCoinDraft.html
10、汤强：十分钟讲清IOTA和DAG
11、Ghost Protocol ：http://www.cs.huji.ac.il/~avivz/pubs/13/btc_scalability_full.pdf
12、Algorand: Scaling Byzantine Agreements for Cryptocurrencies
网友评论