基于有向无环图的区块链技术综述

王劲松，杨唯正，赵泽宁，魏佳佳

（1.天津理工大学计算机科学与工程学院，天津 300384；2.智能计算及软件新技术天津市重点实验室，天津 300384；3.计算机病毒防治技术国家工程实验室，天津 300457）

0 概述

区块链概念自2008 年被提出以来，引起了全世界广泛关注，常见的区块链应用有比特币［1］、以太坊［2］、EOS［3］、Hyperledger Fabric［4］、波卡［5］等。近年来，区块链逐渐演变为一种提供可信溯源服务的服务架构，各个行业都在积极探索区块链的落地应用［6］。然而，传统区块链只有一条单链，打包出块无法并发执行。为了提高传统区块链系统的交易执行速度，一些研究者提出了多层区块链、分片区块链等技术。文献［7］提出混合协商一致协议Goshawk，将两层链式结构、两级工作量证明（Proof of Work，PoW）挖掘策略和票证投票机制巧妙地结合起来。文献［8］提出的HIBEChain 是一个分层区块链系统，可实现物联网（Internet of Things，IoT）设备和数据的可扩展和可问责管理，其由多个许可区块链组成，这些区块链形成一个层次树结构。HIBEChain 通过将区块链分片并行处理的方案实现了高可扩展性。为了支持HIBEChain 的层次结构，该文作者设计了一个基于身份的分散层次签名方案DHIBS，使物联网设备能够将其身份用作公钥。

在上述研究基础上，如果改变区块的链式存储结构，将单链结构转变为有向无环图（Directed Acyclic Graph，DAG）的网状拓扑结构，就可以实现并发写入，提高交易确认速度和吞吐量。假设在区块打包时间不变的情况下网络中可以并行打包n个区块，则交易确认速度就提高了n倍。由此，DAG 区块链技术开始迅速发展。

本文介绍DAG 区块链概念的提出和演化革新过程，对比分析该技术与传统区块链技术，归纳现有的DAG区块链评估系统、方法以及评估结论。同时，从交易确认速度、系统吞吐量、安全性、存储结构等4 个方面对DAG 区块链的优化方法进行总结分析，介绍DAG 区块链目前在数据管理、数据共享、数据安全等场景中的应用。在此基础上，阐述DAG 区块链技术的研究现状，并展望未来的发展方向。

1 DAG 区块链的发展

1.1 DAG 区块链的提出与发展

2013 年，ID 为avivz78 的以色列希伯来大学学者在bitcointalik.org 上首次将DAG 概念引入区块链中作为共识算法（即GHOST 协议），将其作为比特币的交易处理能力扩容解决方案。

2015 年，LERNER［9］提出一种基于DAG 结构的加密货币设计DagCoin，其中没有固定的块，并且每个交易都有自己的工作证明。此外，还提出了2 种优化方法，允许存储和动态更新更低CPU 资源消耗的DAG 区块链。通过将最新的交易存储在快速缓存中，并在不能引用旧交易的地方使用检查点，系统可以达到与比特币一样快的速度，甚至更快，DAG区块链由此产生。DAG 区块链是面向未来的新一代区块链，是区块链从容量到速度的一次革新。从图论拓扑模型角度宏观来看，其从单链结构革新到树状和网状结构，从区块粒度结构细化到交易粒度结构，并从单点写入过程优化到并发写入过程。

随着DAG 区块链技术的发展，早期形成了以IOTA、Byteball、NANO 等3 种结构为代表的DAG 区块链体系，而后发展产生了前景良好的Conflux。目前，这4 个项目是落地运行的主流DAG 区块链项目。

2016 年，POPOV［10］提出了IOTA，其中最主要的创新是基于DAG设计的分布式账本结构——缠结（Tangle），其是一个既没有区块也没有链的区块链。在Tangle中，每一个节点代表的是一个交易。IOTA中没有区块的概念，也没有挖矿和矿工的概念，没有挖矿和矿工就代表没有交易费，整个网络的吞吐量也很高，这是IOTA的显著特点。IOTA DAG 区块链结构如图1所示。

图1 IOTA DAG 区块链结构Fig.1 IOTA DAG based blockchain structure

2016 年，CHURYUMOV［11］提出了Byteball，其在DAGCoin 的基础上，创新性地引入主链与见证人的概念，鼓励验证多个父辈交易单元，形成一个随着交易增长、相互验证、安全性不断加强的数字签名Hash网络。Byteball中包含一种创新的“主链”概念，即经见证人认定的最短路径MC 的Parents 优选算法。主链创造了一个全网共识确定的交易时间序列，巧妙地避免了双花问题。

文献［12］提出的NANO 使用了委托权益证明（Delegated Proof of Stake，DPOS）共识机制，账户可以指定代表为其投票，得票最多的代表将处理分叉，这个代表会将分叉广播到网络，并观察来自高权账户节点在固定时间内的投票结果，以此来确定保留哪一个区块。NANO 通过DPOS 机制保证了区块的合理低能耗运行，同时，其也使用到了PoW 机制，以确认交易需要非常少的工作量证明。

Conflux［13］是一家公有区块链系统研发商，其使用DAG 结构并结合独特的算法，使共识不再是扩容的瓶颈。Conflux 协议将区块组织成一个新的树图区块链结构，这是一个嵌入到有向无环图中的树。Conflux 为每个块指定一个权重，该权重表示这个块最终对其祖先块的贡献度。为了进一步适应环境变化，文献［14］重新设计了Conflux 的共识协议，编码了2 种不同的块生成策略：一种允许快速确认的乐观策略，以及一种确保交易共识的保守策略。Conflux 使用自适应权重机制将这2 种策略结合到一个统一的一致性协议中，以应对不同的工作场景。

1.2 DAG 区块链的演化与革新

随着DAG 区块链技术的不断发展，研究者提出了许多新的DAG 区块链技术（如Hashgraph 共识机制、SPECTRE 协议、PHANTOM 协议等），在去中心化机制、速度与并发方面都取得了进展，但这些技术迄今为止还未落地实施。

文献［15］提出的Hashgraph 在公链环境下实现了异步BFT 共识。传统BFT 的一大问题是消息复杂度太高，大量消耗网络带宽，且无法很好地应对动态网络，而Hashgraph 引入了Gossip 协议，同时运用虚拟投票机制，避免在共识时引起突发大规模消息传递风暴。文献［16］分析了一种非常强大的区块链替代技术——Hashgraphs，并解释其架构和功能，给出进一步开发的方向和预测。文献［17］对基于DAG 的模型IOTA 和Hashgraph 进行了对比分析，并且对模型特征和功能进行概述。同时，定义评估这2种区块链所需标准，对2个系统进行了深入分析，并确定了IOTA 和Hashgraph 在IoT 中的应用面临的挑战。

文献［18］提出的SPECTRE协议采用了Block+DAG的“区块有向无环图”技术，可以并行挖矿，从而获得更大的吞吐量和更快的交易确认速度。该项技术是对中本聪提出的区块链的泛化，解决了前者需要在安全性与扩容能力之间进行取舍的问题，因而更适合建立速度更快或规模更大的区块。但是该协议在受到“双花”攻击时，攻击区块在发布以前几乎不会与诚实节点产生的区块相关联，因为在这个阶段诚实区块不知道这些攻击区块的存在，所以自然不会引用它们。综合来看，这些恶意攻击都有一个显著特点：恶意节点产生的区块与诚实节点产生的区块之间的连通度比较低，反之，诚实节点产生的区块之间的连通度会比较高。文献［19］中的Hycon 使用SPECTRE 协议作为共识机制来保证交易速度和灵活性，其主要特性是快速交易确认时间、链上交易扩展性（在2 MB/s 的连接中高达3 000 笔交易每秒的吞吐量）、同步出块（基于DAG 结构位置而不是时间先后链接区块）以及智能合约。

文献［20］介绍了一种在任何网络状况下都是安全的交易确认协议PHANTOM。PHANTOM 不会受到比特币协议所面临的安全性和可扩展性需要权衡的问题，其利用带区块的有向无环图blockDAG 作为比特币区块链的一个扩展，支持生成更快和更大的区块，但需要更长的时间传播。PHANTOM 在blockDAG 上使用贪婪算法来区分诚实节点正确挖矿的区块和选择偏离挖矿协议的非合作节点创建的块。利用这一特点，PHANTOM 在blockDAG 上提供了一个健壮的完整命令，最终使得所有诚实节点达成共识。文献［21］提出的PHANTOM 协议的投票原则正是基于这个原理，通过判断不同区块间的连通度进行投票。

1.3 传统区块链与DAG 区块链的对比

传统的区块链将交易打包在块中形成链式结构［22］，而基于DAG 的分布式账本将交易作为边存储在有向无环图中，这就使得传统区块链在安全性方面更加突出［23］，而DAG 区块链在效率上更为突出。文献［24］比较了传统区块链和DAG 区块链在分布式设计上相关的特性，同时研究了优化分类账户维护、共识机制、交易确认可信度、分类账户大小以及可扩展性问题的数据结构。文献［25］研究了区块链中的3 种主流共识机制，即PoW、权益证明（Proof of Stake，PoS）和有向无环图，并根据生成新区块的平均时间、确认延迟、每秒交易确认数（Transactions Per Second，TPS）和交易确认失败概率进行评价。结果表明，共识过程受网络资源（包括计算能力、缓冲区大小等）和网络负载条件的影响，且PoW 和PoS对网络资源的变化更敏感，而DAG 对网络负载条件更敏感。与PoW 和PoS 不同，在DAG 中创建新区块不存在竞争，所有交易都是直接或间接关联的。文献［26］从数据结构、共识机制、交易模型这3 个方面对物联网的分散共识系统进行了研究。对基于链式结构区块链的系统（如比特币和以太坊）和基于DAG 的分布式账本（如IOTA 和Byteball）进行了综合比较，通过分析和总结利弊，发现基于DAG 的分布式账本在可扩展性、交易确认速度和分散性方面更优异。文献［27］指出，基于DAG 的分布式账本因其具有高并发特性，有望突破传统区块链中的性能瓶颈，且在基于DAG 的分布式账本中，最为核心和关键的技术是共识机制，并为此对该关键技术进行了深入研究。本文对DAG 区块链技术与传统区块链技术进行了对比，如表1 所示。

表1 DAG 区块链技术与传统区块链技术的对比Table 1 Comparison of DAG based blockchain technology and traditional blockchain technology

2 DAG 区块链的评估

2.1 评估系统

DAG 区块链采用不同的优化机制，为评估这些优化机制的有效性，一些研究者设计实现了DAG 区块链仿真系统对DAG 区块链的关键指标进行评估。文献［28］提出了一个基于DAG 的可配置交互式分布式账本技术（Distributed Ledger Technology，DLT）仿真框架CIDDS，以实现数千节点级的大规模仿真，使用户能够使用数千个节点执行大规模模拟，并在受控条件下研究网络的不同特性。文献［29］为基于DAG 的加密货币提供了一个异步、连续时间和多代理的仿真框架DAGsim，对系统中诚实和半诚实的参与者进行建模，以分析特定加密货币IOTA 的行为。模拟结果表明，具有低延迟和高连接度的代理在网络中以诚实和半诚实策略接受交易的概率更高。文献［30］扩展了DAGsim 模拟器，提出分层分析模型来探索确认正态分布，并发现确认正态分布在DAG 层中，这导致了高斯模型的特征化。同时，利用该模型估计专用物联网的RWT，并通过实验结果进行验证。文献［31］提出一个DAG 区块链的性能评估框架DAGBENCH。该框架提供了许多示例工作负载和适配器，可以有效且轻松地评估不同的DAG，从吞吐量、延迟、可扩展性、成功指标、资源消耗、交易数据大小、交易费用等各个方面衡量性能。

2.2 评估结论

一些研究者对现有DAG 区块链系统不同方面的属性进行了评估。文献［32］对基于DAG 的区块链系统进行了全面分析，通过解构开源系统和回顾学术研究，总结系统的主要组成部分和特征属性，并提出了建立DAG 区块链的方法。该文指出：1）基于DAG 的区块链由于其不兼容的设计、缺乏标准、不可靠的安全性、不同的性能和未完成的实现，距离商业应用仍然较远；2）DAG 结构有可能提高可扩展性和性能，但不可避免地会牺牲某些属性，如一致性和终结性；3）基于DAG的系统各不相同，一个统一的形式化模型很难涵盖所有关键点，相反地，一个松散和非正式的模型对于更好地理解不同的DAG区块链系统非常有益；4）虽然将DAG结构应用于经典的分布式系统和区块链系统是一个相当具有挑战性的问题，但许多相关系统的研究已经取得了很大的进展。文献［33］研究了物联网中网络负载对基于DAG 的区块链共识过程的影响，利用马尔科夫链模型说明基于DAG 的区块链网络的共识中的动态过程，在交易到达率波动引起的不稳定状态下，分析了累积权重和交易确认延迟等关键性能指标。文献［34］对具有代表性的基于DAG 的区块链IOTA 进行了一系列全面的实验研究，主要从性能和安全两个方面特性出发，揭示了以下事实：1）物联网的吞吐量高于传统区块链结构的吞吐量，但是即使是在放大配置的情况下也远低于白皮书中报告的数千TPS；2）数据库查询严重影响物联网的性能，甚至超过PoW 计算过程。文献［35］介绍了一组关于IOTA的综合性实验研究。IOTA是DAG 区块链的代表，该文主要从性能、安全性、系统鲁棒性等3 个方面展示其独特的特性，同时开发了一系列基准工具，并进行了基础配置，以使用现实中的私有物联网进行实验测试。文献［36］通过调查研究发现，基于DAG 的分布式账本缺乏详细的性能评估，与传统区块链相比，基于DAG 的DLT 在设计上提供了更好的性能和可扩展性，并且重点研究了DAG 区块链在物联网中的性能评估。综上所述，DAG 区块链在交易确认速度、吞吐量以及可扩展性方面相对于传统区块链有较大提升，但在安全性、技术标准、可实施性等方面较传统区块链还有较大的差距。

3 DAG 区块链的优化

DAG 区块链具有可扩展、不兼容等特性，因此，研究者在设计时对交易确认速度、系统吞吐量、安全性、存储结构等方面进行优化，以使其适用于不同的应用场景。

3.1 优化交易确认速度的方法

现有优化交易确认速度的方法主要有：1）通过优化交易网络结构增强并发性，加快交易确认速度；2）通过优化缠结共识算法加快交易确认速度；3）通过优化交易传输加快交易确认速度。表2 简要结归纳了部分DAG 区块链优化交易确认速度的方法。

表2 DAG 区块链优化交易确认速度的方法归纳Table 2 Induction of method for optimizing transaction confirmation speed in DAG based blockchain

文献［37-41］针对交易网络进行优化。文献［37］描述了DAG 区块链的优势，解决了传统区块链技术交易确认速度慢、扩展性差等问题，并表明有向无环图是通过形成平行链而不是普通区块链网络中的单个链来优化网络节点之间的交易速度和扩展信道宽度的。文献［38］提出一个可扩展性模型3D-DAG。该模型由主链和侧链两层组成，分别用于维护轴心序列和提高并行性。主链使用经典的区块链数据结构和PoW 共识机制来继承比特币对资产交易的强大信任和安全性，而DAG用于构建侧链，以实现细粒度的并行交易处理。文献［39］对基于DAG 加密货币的固有结构进行了分析，通过对现有基于区块链的加密货币进行多次尝试，突破交易处理速度的限制，产生了多种形式的解决方案，如侧链、链外或数据分片，其中，基于DAG 的加密货币具有更快的交易发行和确认速度。然而，现有基于DAG 的加密货币也存在性能不稳定的问题，因此，研究者构建了基于DAG 的加密货币在计算参数时的通用性能模型。根据导出的模型，提出一些新的策略来提高基于DAG 的加密货币系统的性能，该系统鼓励加密货币的参与者（包括交易者和节点）在保持账本健壮性的同时提高交易处理速度。文献［40］提出一种无权限区块链DLattice，该区块链具有一种新的双DAG体系结构DLattice，其中每个账户都有自己的账户DAG，所有账户组成一个更大的节点DAG 结构。DLattice 使每个帐户的DAG 的增长并行，且不受其他帐户无关交易的影响。文献［41］提出一种轻型区块链体系结构V-lattice，该体系结构使用了VANET的DAG晶格结构。在V-Lattice 中，每个节点（车辆或路边单元）都有自己的账户链，其生成的电子交易可以异步和并行地添加到区块链中，资源受限的车辆可以存储修剪后的区块链，并正常执行与区块链相关的操作。

文献［42-44］针对共识算法进行优化。文献［42］介绍了Re Tangle，这是一种新型的基于DAG 的区块链加速架构，其探索了以低能耗成本执行大规模并行操作的可能性。文献［43］对IOTA DAG 架构中的缠结连接机制进行了简单优化，以确保所有交易在有限时间内得到验证，并保留蒙特卡罗选择算法的基本特征。该文提出一种新的混合小费选择算法，解决了DAG 区块链的分叉问题，并可以在有限时间内验证所有交易。改进后的算法提高了交易入链的速度，但在一定程度上降低了原算法的安全性，可能导致恶意缠绕链的现象，如双花攻击。文献［44］指出，有向无环图正成为分布式账本技术替代传统区块链体系结构的一个有效的替代方案，通过对IOTA DAG 架构中缠结连接机制改进，能够确保所有交易在有限时间内得到验证。

文献［45-46］针对数据交易传输过程进行优化。文献［45］阐述了区块链和DAG 有向无环图的基础及其演变过程，DAG 试图解决区块链中的大多数问题，并为物联网产业构建一个稳定的系统。其中，MAM 是一种辅助数据通信协议，其增加了通过DAG 释放和访问加密数据流（如RSS）的能力。文献［46］提出了拜占庭共识协议Blockmania，其中，节点发出的块形成一个有向无环图，随后由每个节点分别解释，以确保安全、活跃和最终的一致性，由于解释由每个节点独立执行，因此不需要跨节点在消息中携带证据，从而提高了效率。

3.2 优化系统吞吐量的方法

优化DAG 区块链系统的吞吐量可以进一步增强其应对短时高并发数据的处理能力，更加适用于物联网等环境。目前在该方向中有分片并行计算、修改区块链结构、优化共识机制这3 种方法。表3 简要归纳了DAG 区块链优化系统吞吐量的方法。

表3 DAG 区块链优化系统吞吐量的方法归纳Table 3 Induction of method for optimizing system throughput in DAG based blockchain

文献［47-48］提出分片并行计算方法。文献［47］设计了一个新的区块链系统DEXON。首先，为区块链提供了一个高度可扩展、采用任意数量的单链分片框架，并将该框架转换为块晶格数据结构，实现了高可扩展性和低交易确认延迟，且具有渐近最优的通信开销。块晶格结构是由许多单链组成的有向无环图。然后，使用总排序算法在区块链上达成共识，从而确保所有用户认可所有区块的排序。由于单链可以同时增长，因此DEXON 的吞吐量可以很容易地扩展。文献［48］则构建一个并行挖掘模型来提高基于状态的区块链的TPS。

文献［13-14，49-51］针对DAG 区块链结构进行优化。除了上文提到的Conflux 协议［13-14］之外，文献［49］分析了比特币和基于区块链的比特币NG 系统的特点，提出了一种改进的区块链系统实现方法，用图形数据结构代替原有的区块链结构GraphChain。GraphChain是一种特制的数据结构，并非典型的DAG，其中每个区块代表一笔交易，同时包含交易员的余额状态，通过将原有争夺采矿者的方式改为选举和平行开采来提高资源利用率。文献［50］提出了一种链的替代结构，由带区块的有向无环图组成，其允许以更高的速率运行。DAG 结构是通过允许块引用多个前辈而创建的，并且需要交易接受规则，这些规则甚至包含来自看似冲突的块的交易。该规则从DAG 内选择主链，然后有选择地将链外区块的内容合并到日志中，前提是它们与以前包含的内容不冲突。因此，系统可以容忍传播时间较长的较大数据块，并且可以增加交易量。文献［51］提出了收敛有向无环图CDAG 以替代其他区块链协议中使用的链和DAG 结构。CDAG 允许对分类账进行多次并行更新，并在下一步将其聚合，从而保证了区块链的最终一致性。CDAG 将更新划分为不相交的交易桶，以防止冲突块的生成，并将时间划分为多个时隙，以便为它们在网络中传播提供足够的时间，通过多个同步更新提高吞吐量。

文献［52-54］针对共识机制进行优化。文献［52］介绍了一个新型亚稳态无领导拜占庭容错协议族。这些协议在拜占庭对手面前提供了强大的概率安全保障，同时并发性使它们能够实现高吞吐量和可扩展性。与依赖工作量证明的区块链不同，在Avalanche 协议的网络系统中，如果有人想在2 笔交易中花费同一笔钱，那么鉴于Avalanche 协议本身的属性，无法在这2 笔交易中做出选择，从而会导致这笔钱丢失，间接地惩罚了尝试攻击者。因为Avalanche 协议的重点只是达成共识，并不是做出选择。文献［53］提出的Perlin 是一个强化并推广了Avalanche 一致性协议的分布式账本，其在有向无环图上基于亚稳态机制构建部分同步拜占庭容错协议，以实现极高的吞吐量和可扩展性。文献［54］提出一种基于DAG 的联盟区块链拜占庭容错共识算法Jointgraph，以提高安全性和效率。在Jointgraph 中，交易被打包到事件中，并由不少于2/3 的所有成员验证。在该文设计中，引入了一位监督人以监督成员的行为，提高共识效率。

3.3 优化系统安全性的方法

一些研究者注重于优化DAG 区块链的系统安全性，即提高DAG区块链系统对于抵抗各种攻击的能力。他们主要从DAG 区块链系统安全性分析、优化协议和共识机制提高安全性、修改DAG 区块链架构提高安全性等3 个方面进行系统安全性优化。表4 简要归纳了DAG 区块链优化系统安全性的方法。

表4 DAG 区块链优化系统安全性的方法归纳Table 4 Induction of method for optimizing system security in DAG based blockchain

文献［55-58］针对系统安全性进行分析。文献［55］指出，在设计基于DAG 的区块链系统时，基于Tangle的结构是较好的解决方案，但性能提升可能会带来潜在的安全风险。该文提出3 种综合评估的攻击类型，即寄生虫攻击、双花攻击和混合攻击，以分层建立攻击策略。在此基础上，对不同的攻击进行了多维度分析。文献［56］考虑了基于DAG 的DLT 不同体系结构在物联网领域应用的适用性，并着重考虑账本的防篡改安全性。该文分析了一种常见的攻击场景——“寄生虫链攻击”，此攻击在于破坏IOTA 基金会的基于DAG 的系统中的分类帐的不可逆性，同时使用马尔科夫链模型，研究IOTA的核心提示选择方法针对该攻击的漏洞，并对算法进行扩展，以提高该场景中账本的弹性，其中重点讨论了基于有向无环图的DLT 的不同体系结构。文献［57］研究了最典型的DAG 共识机制Tangle，并分析网络负载对区块链性能和安全性的影响。考虑到网络负载的不稳定，首先提出一个马尔科夫链模型描述动态负载条件下DAG一致性过程的行为，然后利用一个随机模型分析在不同的网络负载情况下成功进行双花攻击的概率。文献［58］对基于DAG 的区块链架构进行分析，包括Nxt、IOTA、Orumesh、DagCoin、Byteball、Nano和XDAG，比较基于维护分类账的功能数据结构、共识算法、交易验证、分类账大小、可扩展性和流行性，并提取各种基于DAG 的区块链的最佳特征，通过对上述基于DAG 的区块链进行对比分析，制定出一个安全的DAG 区块链架构框架。

文献［59-63］针对协议和共识机制进行优化。文献［59］设计了一个基于压缩有向无环图高效、安全的区块链协议CoDAG。在该协议中，区块按级别和宽度进行组织，新生成的区块将被适当放置，并指向上一层的区块，使其成为一个连接良好的通道，并且网络中的交易将在确定的时间段内确认，同时协议保持简单的数据结构。文献［60］提出了一种新的交易验证机制。该机制依赖于参与节点合作验证新交易，在将交易包附加到Tangle之前，节点应选择2个最新提示并被批准。在基于DAG 的分散环境中，必须构建一个健壮的选择提示算法。设计这种算法的目的是推动节点选择未经批准的交易包，并解决检查交易、双重支出和伪造交易的冲突。文献［61］指出，基于有向无环图的模型旨在通过采用与BoStand 链中使用的不同协议来避免交易费用。该模型使用马尔科夫链蒙特卡罗算法更新分布式账本。然而，关于协调器节点集中化的问题仍然存在，并且选择算法的经济激励不足。该文提出了一种轻型高效的分布式账本更新算法，通过贝叶斯推理，只考虑每一步的子角度。文献［62］介绍了一种新的共识协议STAIR，实现基于DAG 的无信任系统中的快速协商一致。STAIR 使用了一种在每个节点上创建局部块DAG 的新方法x-DAG，其构建StakeDag 框架，根据参与者的利害关系将参与者区分为用户和验证器，其中两者都可以创建和验证交易块。与StakeDag 的DAG不同，x-DAG 确保每个新块都必须有来自用户和验证者的父块，以实现更安全的效果。文献［63］从DAG 的特殊结构出发，采用POS-PBFT 作为主链共识算法，将链式共识算法与DAG 相结合，提出一种区块链新模型SDAG。该模型提高了系统的扩展性，并且使交易数据的一致性和时序性优于链式结构。

文献［64-67］针对DAG 区块链架构进行优化。文献［64］提出了一种新型的DAG 结构IDAG，其工作原理与DAG 类似，但没有包含结果节点，而是包含因果效应节点。IDAG 允许以直观和严格的方式演示交互，有助于区分效应变异背后的因果机制和非因果机制。该文通过实验研究了如何以经验评估节点相互作用，以及如何在保证区块链整体性能的基础上总结区块链接规律。文献［65］描述了一个轻量级、有弹性的分布式账本系统DLedger，通过将DLedger 安装到存储受限的物联网设备中，当供应的空间接近耗尽时，实体可以经过修剪一段时间后保持未确认的所有记录来减小本地DAG的大小，并取出远离尾部记录的历史确认记录。利用DAG 和PoA，即使是受限制的设备也可以通过“挖掘”自己的记录并得到确认来参与，从而提高数据的可用性、完整性和真实性。文献［66］利用形式化方法设计了一种块DAG 架构，并且提出了维护该架构所需的协议。DAG 区块本质上是将块之间的关系用Lamport编码，且任何确定性拜占庭容错协议都可以嵌入到这个块DAG 中，同时保持其安全性和灵活性。文献［67］介绍了一个具有三维账本架构的安全、高性能区块链系统Spacechain，以实现区块链在物联网中的开放性。首先，设计一个具有新颖数据结构的三维体系结构，使用宏块构造有向无环图；然后，将许多微型块连接到DAG区块链形成第3 个维度，从而应对物联网网络的异构性和可扩展性；最后，提出空间链的三维贪婪最重观测子树（3D-GHOST）一致性机制，以提高安全性和网络性能。

3.4 优化存储结构的方法

除了DAG 区块链共识机制和架构，DAG 区块链交易的存储和查找也是限制DAG 区块链系统性能的重要问题，一些学研究者对此进行了研究。表5 简要归纳了DAG 区块链优化存储结构的方法。

表5 DAG 区块链优化存储结构的方法归纳Table 5 Induction of method for optimizing storage structure in DAG based blockchain

文献［68］提出一种基于有向无环图的新通证设计模型，允许在不检查整个区块链的情况下有效地探索通证历史。该模型将通证的每个状态从过去关联到最新，并涵盖通证之间关系的表达式，例如合并和拆分，这不仅提高了跟踪效率，而且还有助于跟踪溯源，包括合并、拆分、分支通证历史。

文献［69-71］针对数据存储方法进行优化。文献［69］提出了一种基于轻量级有向无环图的区块链LDV，并提出了基于社会的数据约简方法。具体而言，每个节点只在感兴趣的主题组中存储感兴趣的数据，而忽略不感兴趣的数据。为了避免在具有大量数据的大型组中产生巨大的存储成本，进一步提出了组内历史数据剪枝方法，通过减少每个节点中存储的重复数据数量来满足存储需求。文献［70］为物联网区块链设计一种高效的共识算法Teegraph，其包括基于Gossip协议的消息通信机制，以生成用于高效共识过程的基于有向无环图的数据结构。当没有创建新交易时，Teegraph 就像一种节省资源的机制，可以减少通信开销并节省存储空间。文献［71］基于改进的区块链方法，利用有向无环图，为NMG 提出一个安全的随机能源管理框架，使用分散透明的区块链技术提高网络安全性并降低风险，从而消除金融欺诈，降低总运营成本。为解决传统区块链模型中由于哈希地址计算的存储和高复杂性问题，该文提出一种基于DAG 方法的改进区块链技术，此外，还设计新的数据恢复技术，以适当精度恢复数据。

唯一地址检查是确保每个用户帐户（钱包）的每笔交易都与唯一的私钥/公钥对相关联的基本过程，其中公钥和私钥将分别用作交易的地址和签名。目前，基于DAG 的区块链系统通常采用基于数据库的方法，依靠耗时耗空间的数据库查询来执行唯一地址检查过程。文献［72-74］针对此问题进行研究。文献［72］设计了一个嵌入IOTA 轻量级客户端的布谷鸟过滤器，以帮助加速地址检查过程。这种设计基于这样一种假设，即在快照之后可以重用地址，快照会定期执行以减少缠结大小。该文为当前混乱中的地址构建bloom 过滤器，以保证唯一性。然而，这种假设是不现实的，使得这种设计很难在实践中部署。文献［73］提出了一种称为ABACUS 的方法，利用两级分区bloom 过滤器执行地址检查。分区bloom 过滤器负责根据其前缀存储所有已用地址，每个分区bloom 过滤器的一个SBF（子bloom过滤器）保存在内存中并写入缓冲区。然而，这种方法的重点是优化bloom 过滤器更新操作，以加速唯一地址检查。此外，ABACUS 假设所有地址检查过程都在支付帐户内执行，而忽略地址的时间位置。文献［74］提出了一种热感知细粒度bloom 过滤器HF-BF，用于对基于DAG 的区块链进行唯一地址检查。BFU 是细粒度bloom 过滤器散列函数，为了管理BFU 的大存储空间并尽可能减少用于检查地址的I/O 数量，该文设计了一种自适应BFU 管理方案，在内存和磁盘之间调度活动BFU。但是此解决方案具有一定的安全性风险，由于地址未存储，一旦区块链网络发生错误，交易就无法被追溯，从而导致交易无法确认。

4 DAG 区块链的应用

DAG 区块链通常应用在节点计算能力不足、对交易处理时间要求高而对单笔交易可信性要求不严格的场景中。本节主要介绍DAG 区块链目前在数据管理、数据共享以及数据安全等场景中的应用。

4.1 数据管理

DAG 区块链因其速度更快、无交易费用同时也无需挖矿等特点，被广泛应用于物联网等数据并发量大但设备算力不足的场景中。

文献［75］对物联网环境的特点，包括其安全性和性能要求，以及区块链技术的进展进行了系统研究，并且提出一种基于DAG 的区块链来解决区块链在物联网中应用面临的一些重大挑战。文献［65］描述了一个轻量级、有弹性的分布式账本系统DLedger。DLedger在一个有向无环图上构建分类账，而不是一个单一的区块链。DLedger没有使用计算密集型工作量证明，而是使用身份验证证明（PoA），其轻量级操作对物联网友好以达成共识。此外，DLedger建立在一个名为命名数据网络（NDN）的以数据为中心的网络上，这有助于异构物联网中的对等数据传播。文献［76］提出一种应用层协议，称为流式数据支付协议SDPP。该协议规定，数据提供者可以发送自动发票，数据消费者可以提供签字收据，以便将数据存储在不可变的分布式账本上，用于审计和争议解决。SDPP 是第一个针对物联网类型流式数据的集成数据支付记录协议，其利用了传统的TCP/IP 以及创新的基于区块链和DAG 的分布式账本技术。文献［77］提出一种基于有向无环图的分布式账本技术PowerGraph，及其在智能电网中生成、验证和确认电力交易的方案。由于基于DAG 的分布式账本不需要生成用于确认的数据块，PowerGraph 的每笔交易都会单独经历验证和确认过程。此外，PowerGraph中能够跟踪能源交易以及其他各种类型的交易，实现智能电网网络中交易的完全跟踪。

4.2 数据共享

在大规模网络环境下难以实现去中心的数据共享，而DAG 区块链可以在一定程度上解决这一问题。为了应对使用异构设备管理大规模物联网网络的挑战，文献［78］提出一种有向无环图区块链增强的用户自治频谱共享模型。由于所提出的一致性规则与系统效用密切相关，用户群智能在区块链一致性过程中逐渐达到收敛点。此外，常用的分布式数据共享方法还包括边缘计算、联邦学习等。

4.2.1 边缘计算

文献［79］提出一种称为安全无人机网络边缘服务（SDNES）的创新架构，该架构将边缘计算和基于DAG的区块链集成到无人机网络中，为无人机提供实时可靠的网络服务，并有效避免恶意行为。文献［80］提出基于DAG 的分布式边缘技术，旨在为物联网系统提供安全和隐私以及新的附加功能，解决物联网系统的现有问题，同时并使用IOTA 的屏蔽认证消息（MAM）成功地实现了物联网传感器数据的TAM 认证和安全传输，确保了数据机密性和数据认证。文献［81］提出一个跨链框架来集成多个区块链，以实现高效、安全的物联网数据管理，并基于Hyperledge Fabric 和IOTA Tangle实现了该框架的原型。在此过程中，一个挑战是物联网区块链的可扩展性。由于区块链上的每个条目都需要所有网络节点达成共识，因此基于单一架构的区块链无法很好地扩展。为了解决这个问题，该文使用有向无环图数据结构引入缠结，并将网络分解为多个类似于“侧链”的较小子缠结。然后，将这些侧链网络连接起来，形成一个分散的网络。文献［82］研究使用了一个基于物联网和区块链技术的集成框架，该框架结合了有向无环图配置的无线传感器网络（Wireless Sensor Network，WSN）和用于水污染源实时追踪的GIS工具。这项研究的新框架使用基于区块链的技术、DAG 配置中的无线传感器网络和GIS 技术从灌溉取水数据中追踪污染路径。区块链和GIS 工具被用于追踪绘制的灌溉单元的污染，并在空间上识别灌溉进水口的上游污染单元。文献［83］为IIoT 提供了一个基于信用的共识机制的区块链系统。该文提出一种基于信用的物联网设备工作量证明机制，可以同时保证系统安全和交易效率，其系统基于有向无环图结构区块链构建，利用异步一致性模型提高了系统吞吐量，在性能上比比特币式区块链更高效。文献［84］介绍了一个可分区的区块链Vegvisir，用于网络连接有限、功率受限的物联网环境，其为一个经过许可的、有向无环图结构的区块链，可用于创建一个共享的、防篡改的数据存储库，以跟踪数据来源。文献［85］提出了一个分片有向无环图区块链DagGridLedger，为可信的DNS 管理提供了可扩展的大数据体系结构，其将区块链分片和DNS 解析器端的DAG 技术相结合，能够增强大规模DNS 系统的安全性和稳定性。

4.2.2 联邦学习

文献［86］提出了一种基于模型更新的有向无环图联邦学习中去中心化方法，客户端不需要训练统一的全局模型，而是专注于本地数据，同时根据各自数据的相似性使用其他客户机的模型更新。这种特性隐式地出现在基于DAG 的通信和模型更新的选择中。与传统基于DAG 的共识机制相比，其DAG 模型中的交易不属于绝对类别“有效”或“无效”。为解决联邦学习（Federated Learning，FL）中的设备异步和异常检测问题，同时避免区块链造成的额外资源消耗，文献［87］构建一个基于DAG 的区块链系统授权联邦学习的框架DAG-FL。首先从三层架构详细介绍了DAG-FL，然后设计了运行在不同节点上的DAG-FL 控制和DAG-FL更新2 种算法，最后详细阐述了DAG-FL 共识机制的运行过程。该文作者还在文献［88］中介绍了一个基于DAG的区块链系统授权联邦学习的框架，并建立了一个泊松过程模型，讨论了在不同的联邦学习任务中如何设置部署参数以保持DAG-FL 的稳定。

4.3 数据安全

目前DAG 区块链应用于数据安全的场景主要有访问控制和隐私保护2 种。

4.3.1 访问控制

文献［89］推出了一个基于区块链的物联网系统B-IoT，该系统包含基于信用的共识机制。为了保护敏感物联网数据的机密性，该文设计一种数据权限管理方法来规范对传感器数据的访问。同时，基于有向无环图结构的区块链构建系统，得到较比特币类型的区块链更高的效率。文献［90］介绍了一个许可的区块链系统CAPER，用于支持协作分布式应用程序的内部和跨应用程序交易。在CAPER 中，区块链分类账形成为一个DAG，其中每个应用程序只访问和维护自己的分类账视图，包括其内部和所有跨应用程序交易。CAPER 还引入了3 种一致性协议，用于在具有不同内部一致性协议的应用程序之间全局排序跨应用程序交易。文献［91］介绍了一种无信任系统的通用模型StakeDag，其目的是在基于DAG的无信任系统中实现PoS 共识。在该模型中，参与者通过他们的利益或信任来区分用户和验证器。用户是没有假定信任的正常参与者，而验证器是具有已建立信任的知名参与者。

4.3.2 隐私保护

文献［92］提出并调查了物联网的主要安全问题。除了用于网络、通信和管理的协议外，还审查并分类了物联网分层体系结构方面的常见安全问题，并提出了一种DAG 区块链解决方案。文献［93］指出，基于DAG 的分布式账本可以通过设计来解决性能和可扩展性问题。首先对分布式账本技术在物联网中的应用以及这种分散系统的性能进行全面的评估；然后在对不同基于DAG 的分布式账本技术进行简要描述，同时对物联网进行了详细的技术概述；最后利用物联网协议并遵循关注点分离（Separation of Concerns，SoC）设计原则，提出一种可扩展的交易式智能家居基础设施。文献［94］通过利用基于有向无环图的DLT 并遵循SoC 设计原则，提出一种可扩展的交易式智能家居基础设施，并对40 个家庭节点进行了实验验证。结果表明，此解决方案具有高TPS/CTP和良好的可扩展性，以及在物联网环境中重要的数据安全和小额支付方面的良好性能。文献［95］针对电动汽车需要的充电桩数量有限且充电比加油更耗时的情况，提出一种基于DAG 区块链和双拍卖机制的安全高效的计费调度系统，同时设计一个轻量级计费调度框架，该框架集成了DAG 区块链和现代密码技术，能够确保在执行调度和完成交易期间的安全性和可扩展性。

5 未来研究展望

DAG 区块链吞吐量高、交易处理速度快等特性使其与传统区块链技术的优劣对比十分明显，但在单笔交易安全性上却存在不足。未来研究可从以下4 个方面进行展开：

1）研究能够落地应用的高效DAG 区块链技术。尽管目前针对DAG 区块链的研究有较大进展，但是部分协议距离落地应用还存在一定距离，并且现有的DAG 区块链技术形式多样，难以统一且未形成标准，在未来这些方面还需要完善。

2）优化存储结构，加快交易查找速度。在DAG区块链共识过程中，数据库交易查找严重影响区块链性能，如何创建高效的数据索引结构加快交易查找速度，以及如何减少共识过程中的交易查找数量，是优化DAG 区块链的重要研究方向。

3）优化共识机制，提高DAG 区块链抗攻击能力。目前采用DAG 区块链会让交易序列化变得复杂，“双花”问题难以得到解决，且DAG 区块链中的交易确认是概率可信，难以实现最终一致性的共识。因此，改进DAG 区块链共识机制，提高DAG 区块链抗攻击能力是未来重要的研究方向。

4）探索DAG 区块链在工业互联网等领域的应用。工业互联网是新一代信息通信技术与工业经济深度融合的新型基础设施、应用模式和工业生态。工业互联网具备和物联网相同的计算能力差、数据高并发等问题，因此，DAG 区块链在工业互联网等领域，尤其是在工业互联网产品溯源、故障处置、供应链等方面具有广泛的应用前景。

6 结束语

本文从DAG 区块链的发展、评估、优化、应用等方面出发，阐述DAG 区块链技术的研究进展，同时指出现有DAG 区块链技术形式多样未能统一，并且其商业化应用仍存在技术难以落地和安全性问题等诸多不足。在目前DAG 区块链技术不断创新发展且新应用大量涌现的背景下，未来将对区块链架构、存储结构、共识机制等方面进行深入研究，探索提高DAG 区块链系统运行效率和安全性的有效方法。