基于有向无环图的高效并行区块链

洪璇　胡军

摘  要： 区块链系统的性能制约了它的推广应用，主要表现为交易吞吐量低、交易确认时间长和算力浪费等.针对這些问题，提出一种基于有向无环图（DAG）的区块链及其共识协议，提供区块链的并行工作模式.通过3个指针提供DAG区块的连通性;根据工作量证明（PoW）机制，将较难的区块组成一条谜题链，保证区块的有序性和系统的安全性;按照最长链原则和最难链原则，制定谜题链的共识协议.本方案充分利用了网络节点的计算资源，提高了区块链系统性能，减小了计算冗余度，节省了算力.

关键词： 分布式账本; 区块链; 并行区块链; 有向无环图（DAG）; 共识协议

中图分类号： TP 311    文献标志码： A    文章编号： 1000-5137（2022）02-0135-08

Efficient parallel blockchain based on directed acyclic graph

HONG Xuan， HU Jun

（College of Information， Mechanical and Electrical Engineering， Shanghai Normal University， Shanghai 201418， China）

Abstract：The promotion and application was restricted by the performance of blockchain system， which mainly manifested in low transaction throughput， long transaction confirmation time and waste of computing power. To solve these problems， a blockchain based on directed acyclic graph （DAG） and its consensus protocol was proposed to provide a parallel work mode of blockchain. Three pointers were used to provide the connectivity of DAG blocks. Block order and system security were guaranteed by forming a main chain of difficult blocks through the use of proof-of-work （PoW） mechanism. Aconsensus protocol on the main chain was formulated according to the longest chain principle and the hardest chain principle. This scheme made full use of computing resources of network nodes which improved the performance of blockchain system and reduced computing redundancy and computing power.

Key words：distributed ledger; blockchain; parallel blockchain; directed acyclic graph （DAG）; consensus protocol

0  引言

近年来，人们对区块链技术的局限性有了更深刻的认识，其主要表现为交易吞吐量低、交易确认时间长和算力浪费等^[1]，这制约了区块链的应用和发展.因此，消除性能瓶颈可以为区块链的广泛应用提供可能.

区块链采用的共识机制是影响其性能的重要因素，目前大多数有向无环图（DAG）区块链都使用工作量证明（PoW）共识机制，因为使用其他共识机制失去了区块链去中心化的意义，存在安全性隐患^[2].PoW需要计算哈希难题，争取记账权.这种机制的优点是可以完全实现去中心化，缺点是共识达成速度较慢，浪费计算资源且算力集中.PoW共识机制能在完全去中心化的网络环境中保证数据的安全存储与共享.

区块链的数据结构本质上是一条单向块状链表，导致确认交易和生成区块的过程无法并行执行，性能较低.因此，将基于单向块状链表的区块链扩展为基于DAG的区块链，使每个DAG节点有多个出度和入度，可以支持多线程并发执行，突破了传统区块链串行处理模式的限制，提高了系统吞吐量，加快了交易速度^[3].SARFRAZ等^[4]提出了基于DAG的分布式账本埃欧塔（IOTA），实现了良好的吞吐量性能，其交易是无序的，系统安全性无法保证.LI等^[5]开发的Conflux系统将DAG中的节点按照时间先后顺序划分成若干纪元，在每个纪元内进行选择具有最高“权重”的区块，得到纪元的主链，进而得到整个系统的主链，锚定了所有区块的全序，在保持并发的情况下，能决定不同区块的顺序，但该方案较复杂，需要计算每个区块的“权重”后，才能达成区块之间的共识机制.CUI等^[6]开发的CoDAG系统将图划分为不同的级别，并通过计算其“连通性”将区块分为不同的级别，计算量较大.WANG等^[7]提出了一种基于ID分类的有向无环图数据结构，但没有对方案进行详细的设计，也没有进行性能评估与安全性分析.322C37E6-F6B0-4DBF-9636-E806FE77B2A6

为了让网络节点在完全去中心化的情况下，能对高并发的DAG结构达成共识，本方案结合PoW共识机制与DAG区块链技术，设计了一种基于DAG的区块链结构及其共识机制.通过PoW机制选择一些哈希难度较高的区块组成一条谜题链，根据谜题链的最长链原则和最难链原则，得出DAG的拓扑排序.相较文献[4?7]的方案，本方案无需再进行“权重”或“连通性”等额外计算.谜题链由一些难度较大的谜题区块组成，使得区块链更加难被篡改，保证了系统的安全性和一致性.本方案的矿工链包含了矿工的历史记录，可以应用在基于个人信用的场景中，体现了本方案的扩展性.

1  数据结构设计

1.1整体结构概述

为了确保DAG上的區块达成共识机制，设计一种紧密联系DAG上所有区块，且能使之有序排列的结构.考虑到生成区块需要进行PoW计算，选择哈希难度较高的一些区块作为谜题链区块，如图1所示.本方案在DAG中嵌入一条谜题链，谜题链上的区块为谜题区块，比常规区块更难被挖掘，但谜题区块与其他区块的挖掘工作流程相一致.

另外，为了能够快速地对DAG进行拓扑排序，考虑将DAG分解退化成若干二叉树，每个节点除了有一条连接谜题链节点的边之外，还需要两条连接别的节点的边，以形成二叉树的左右分支.因此，在矿工准备生成区块的时候，需要配置3个指针指定区块之间的关系.第一个指针peer指向矿工的前一个区块，将矿工挖掘的所有区块连接到一个矿工链中，该矿工链包含了矿工的信息，比如他的哈希算力等;第二个指针main指向最长谜题链上的最新谜题区块，如果这个新区块被确认为谜题区块，那所有谜题区块都将通过这个指针与该新区块保持连接;第三个指针wait指向一个其他矿工挖掘的区块，以增强DAG节点之间的连通性.根据以上连接规则，某一区块连接节点的集合中，每个指针对应于一条有向边，区块之间按照时间先后顺序通过指针连接，即形成了一个DAG^[8].当交易量增多的时候，前驱节点有多个入度，可以同时被多个后继节点所指向，从而能够支持数据的并发执行.当交易量减少时，后继节点有多个出度，可以同时指向多个前驱节点，以加速整个图形的收敛^[9].

1.2区块结构

谜题链区块由区块体及区块头组成.区块体中包含应用数据message，区块头中包含了指定区块关系的3个指针（ptr_peer，ptr_main，ptr_wait）、生成该区块的矿工信息peer、时间戳Timestamp、应用数据message的Merkle根、解决哈希难题的解nonce等，如图2所示.

在所有区块中，整个DAG中的根节点即定义为创世区块.

1.2.1 指针

指针指定了区块之间的关系.由于通过指针可以回溯到某个区块的所有前驱区块，可以将对于某区块的共识机制扩展为所有前驱区块的共识机制.

1.2.1.1 ptr_peer和矿工链

指针ptr_peer指向由同一名矿工生成的前一个区块，如果该矿工此前没有生成过任何区块，则指向创世区块.这个指针将同一矿工挖掘的所有区块连接成链，即矿工链.矿工链包含了矿工的挖掘历史，可以根据这些信息得到矿工的状态，评估矿工的哈希算力.

1.2.1.2 ptr_main和谜题链

指针ptr_main指向一个谜题区块或者创世区块.谜题链以树形结构指向并确认其他一些常规区块.因此，只要节点对所有谜题区块达成共识，就对整个DAG达成了共识.为此，需要将所有谜题区块集合到一个链结构中，进而使所有的区块能被谜题区块所指定.

1.2.1.3 ptr_wait和连通性

为了增强DAG区块间的连通性，将谜题链的安全性扩展到DAG中所有的区块.使用指针ptr_wait指向另一个矿工的常规区块或者创世区块.

从一般区块到谜题区块的有向边起到确认所有前驱区块的作用，DAG的强连通性会带来更快的交易确认速度.

1.2.2 区块及其PoW共识机制

矿工为了得到区块的记账权，并确定区块的类型，需要提供区块的PoW.为了获得PoW，在配置了指针之后，需要不断地枚举nonce值，直到计算出符合要求的区块哈希.

设H为区块的哈希值，d为常规区块的难度值，p表示谜题区块的难度值，d和p的取值决定了矿工生成区块的难度和速度.本方案中，将p与比特币的难度值设为相同值，谜题链与比特币链的生长规则相一致，与比特币链具备相同的安全性;而d的取值需要比p的取值更容易，以减小常规区块的生成时间，提高系统吞吐量.如果H<d，则表示矿工生成了一个常规区块;如果H<p，则表示矿工生成了一个谜题区块.

由于谜题区块的哈希值是难以计算的，由谜题区块所组成的谜题链保证了整个DAG结构的安全性，难以被篡改.

1.3DAG结构

本节引入一些符号和定义来描述DAG结构，根据图1所示的DAG区块链结构，用G表示区块集合，用B表示某个谜题区块.

对于任意谜题区块B_m∈G，由它确认的子集为：322C37E6-F6B0-4DBF-9636-E806FE77B2A6

2  共识协议设计

DAG的结构由所有网络节点以分布式方式集体创建和维护，下文描述了每个节点所要遵循的协议，并描述算法伪代码.协议的目标是让所有节点对相同的DAG达成共识，并使用相同的DAG构建有序账本.

2.1接收区块

假设节点a本地存储了（G_a，B_m），G_a是节点a的本地DAG结构，B_m是G_a中的谜题区块.

此时，节点a通过广播接收到区块B.

首先，检查B对G_a是否合法.如果是，在DAG结构中添加B，并更新G_a;否则，丢弃该区块.

然后，根据最长链原则和最难链原则更新B_m：

即如果新的谜题区块高度比原来的更高，则更新B_m;如果两个谜题区块的高度一样高，但新的谜题区块的难度比原来的更难，则更新B_m;其他情况，不更新.最长链原则和最难链原则使得每个谜题区块都是当前水平集中生成难度最大的区块，保证了区块链更加难以被篡改.

2.2交易分配

按照DAG的并行工作模式，同一交易可能被多个矿工重复纳入多个区块中，造成数据冗余，增加存储负载，浪费系统算力.因此，需要设计一种交易分配机制，有效降低一个交易被多个矿工处理的概率.通过计算哈希值H（H（B_i），T）作为交易T和矿工状态B_i（矿工i的矿工链上的最新区块）之间的距离，动态地限制矿工可以处理交易的数量，再通过矿工链统计出该矿工i在水平集中生成的区块的比例q_i∈[0，1]，作为该矿工哈希算力的评估值.如果满足条件

2.3生成区块

生成區块算法如图6所示.假设矿工i本地存储了（G_a，B_m，B_i），其中，G_a是矿工i的本地DAG结构;B_m是G_a中的谜题区块;B_i是i的矿工链上的最新区块.

如果矿工想生成一个新区块B_n，并让它成为其本地DAG的一部分，则需要按如下步骤进行工作：

1） 根据式（1），筛选符合条件的交易信息，生成message.

2） 配置B_n.ptr_main←H（B_m）;配置B_n.ptr_peer←H（B_a），其中，B_n和B_a是矿工i生成的两个连续的区块;配置B_n.ptr_wait←H（B_w），其中，B_w是另一条矿工链的常规区块.

3） 进行PoW，生成nonce.不断地调整nonce值，并对这个区块进行哈希运算，直到H（B）<d.

4） 最后，通过点对点网络广播B_n.

2.4奖励方案

为了提高区块链系统的性能，在2.3节中定义合法指针的基础上，指针还应满足以下约束：

1） 新区块应指向自己矿工链上的最新区块;

2） 新区块应指向最新谜题区块;

3） 新区块应指向另一条矿工链上的最新常规区块.

因此，为了激励矿工遵守上述约束规则，设计奖励方案.矿工可以从一个区块中获得多少奖励取决于三个因素：区块类型、区块位置及区块中交易的有效性.

首先讨论区块类型，因为分叉的谜题链形成了一棵谜题树，在计算奖励时，将不在最长谜题链上的谜题区块视为常规区块.为了便于描述，以下将常规区块和分支谜题区块统称为非谜题区块.因为谜题区块更难生成，所以设置r_m>r_n，其中，r_m表示谜题区块的固定奖励，r_n表示非谜题区块的固定奖励.

如果矿工生成了一个谜题区块，除了固定奖励r_m和有效交易的费用外，还会获得额外βR（B_m）奖励.假设参数β=2%，矿工将额外获得高于该谜题区块所在水平集中所有常规区块2%的奖励.另外，由于额外的奖励取决于水平集中的区块数量，这将激励矿工将新区块指向另一个矿工链上的最新常规区块，以最大化该水平集中区块的数量.矿工链的分叉区块产生的奖励为0，从而激励矿工保持自己生成一个没有分叉的矿工链，如表1所示.322C37E6-F6B0-4DBF-9636-E806FE77B2A6

2.5构建分布式账本

分布式账本是交易的有序列表，要构建分布式账本，需要获得DAG中区块的有序序列.根据上述共识协议，网络节点拥有相同的DAG，再使用同一个算法来对相同的交易集进行排序，就能构建出相同顺序的分布式账本，如图7所示.

根据前文描述，DAG中的区块是按水平集组织的，因此，首先根据水平集中谜题区块的高度从低到高划分每个水平集，再对每个水平集内的区块进行排序.每个水平集其实是一棵有向二叉树，树的根节点是第k个谜题区块B_m，k，树的每一条有向边是指针集合{ptr_peer，ptr_wait}.这里不考虑ptr_main，因为它指向前一个水平集.使用深度优先搜索（DFS）的后序遍历方法，从根B_m，k开始沿着有向边遍历这棵树，先按ptr_peer遍历，再按ptr_wait遍历，即可得到每个水平集中区块的顺序.虽然对二叉树进行排序，有很多种排序算法，都能够产生唯一的序列达成共识目的，但采用DFS的后序遍历能保持矿工链上区块的时间顺序排列，优先遍历到的区块，即为生成时间较早的区块.

按照上述的水平集顺序和每个水平集中的DFS后序排序即可得到一个有序的交易列表.

2.6应用场景分析

遵循以上DAG区块链结构及其共识协议，最终在点对点网络上的节点都将拥有相同的本地DAG视图和相同的分布式账本.本方案适用于需要去中心化、业务高效并行、记录个体信用、分离业务数据的应用场景，例如物联网应用场景.

因为物联网内的智联设备需要实现端到端的自动化连接，所以物联网本身就是一个去中心化的网络模型.另外，随着物联网的发展，在网络中有海量业务数据需要实时高速地传输和共享.传统区块链的串行工作模式显然不能满足物联网的业务需求，而使用本方案的DAG区块链模型，除了能满足以上基本需求，还能利用矿工链分别记录单个设备的日志数据，以供网络维护，并进行精确查询分析;还能利用指针ptr_wait将不同设备的矿工链进行耦合，以表示设备间的通信关系.

3  结论

本方案结合了经典PoW共识机制与新型DAG区块链技术，设计了一种以谜题链为主链的DAG区块链结构及其共识机制，在不牺牲安全性且实现去中心化的前提下，提高了系统性能.

对于DAG结构的设计，提供了区块链系统的并行工作模式，提高了系统节点的算力利用率，提高了交易吞吐量，缩短了交易确认时间.并行的区块和分散的奖励也减小了矿工们组成大型矿池的需求，避免算力集中和大部分攻击隐患，进一步提高了系统安全性.

对于谜题链的设计，保证了本方案的安全性和一致性.通过哈希值难度即可筛选谜题区块，不用额外计算区块的权值、连通性.谜题链由难度最大的一些谜题区块组成，使得区块链更加难以被篡改，而且由于DAG的强连通性，谜题链的安全性将扩展到DAG中所有的区块.此外，谜题链还提供了交易顺序，以便所有矿工一旦对DAG达成共识，就能够建立相同的分布式账本.

矿工链的设计，提供了本方案的扩展性.矿工链包含了矿工的历史记录，可以将本方案应用在基于个人信用的场景，甚至可以抽象为某个业务部门的业务链，分离一个集团内不同部门的数据.此外，根据矿工链中的矿工信息，能够设计出一种基于DAG的交易分配机制，该方法可以根据矿工链状态，以不同的概率将交易分配给他们，降低同一个交易被多个区块重复记录的概率，降低了数据冗余，从而减少资源的浪费，进一步提高了处理效率，缩短了交易确认时间.

参考文献：[1]  YUAN Y， WANG F Y. Blockchain： the state of the art and future trends [J]. Acta Automatica Sinica，2016，42（4）：481-494.