基于DAG的区块链新模型设计与实现

2021-10-15四川大学计算机学院四川成都610065

计算机应用与软件 2021年10期

张震李强甘俊张超(四川大学计算机学院四川成都 610065)

0 引言

自2008年中本聪发布比特币白皮书以来，比特币这类点对点电子现金系统引起了社会各界的极大重视。学者在对该系统深入研究之后，从比特币的基础架构凝炼出了区块链技术。

区块链技术巧妙融合了以共识算法为核心的诸多技术，它以去中心、自治、开放、匿名、不可篡改的特性为人知晓。区块链系统的安全性基于密码学算法，而不是传统意义上的“信用”。区块链被认为是人类社会关于信任和协作的跨越式进步。2015年10月，《经济学人》封面文章称区块链是制造信任的机器。

学术界和商业界都对区块链技术显示出了极大的兴趣。众多研究人员共同推动了区块链技术的发展，Swan[1]在《Blockchain：Blueprint for a New Economy》中将区块链技术的发展分为了3个阶段。

区块链1.0时代是以比特币为代表的加密数字货币时代。去中心的比特币系统在全球范围内平稳运行近十年更加彰显了区块链技术的不平凡之处。比特币之后，众多加密货币如雨后春笋般涌现。随着加密数字货币的兴盛，区块链的去中心特性逐渐深入人心并被更多的人接受。比特币更像是一次极为成功的社会实验，验证了区块链强大的生命力。然而，作为区块链1.0时代的标志性产物，比特币系统存在着诸多缺憾。

比特币系统采用的共识算法是PoW(Proofof Work)。自2008年至今，PoW算法始终安全可靠地维护着比特币系统的运行。然而，PoW的弊端也随之显露。弊端之一是世界范围内大算力矿池的出现，在一定程度上削弱了区块链去中心化的设计初衷，也消减了大部分小算力参与者的热情，为51%攻击提供了更多的可能性。弊端之二是PoW会导致巨量的能源浪费，每年消耗资源数十亿美元。弊端之三是区块的建议最终确认时间长达60 min左右，吞吐量是7笔/s，效率较低。

PoS(Proofof Stake)共识算法的提出正是为了解决PoW共识算法所引起的低效高耗能问题。从2011年出现相关概念开始，就出现了一大批PoS的簇拥者，他们以PoS思想为核心，提出了各自的链式结构系统。如Casper[2]、Algorand[3]、Nxt[4]、Peercoin[5]等知名区块链系统。PoS算法在改善PoW算法的同时也引进了新的弊端，如PoS类系统极易分叉、记账人权力过大等。

区块链2.0时代是以智能合约为代表的可编程金融时代。1995年Nick S首次提出智能合约概念。之后，Ethereum(以太坊)将智能合约与区块链相结合，极大地扩展了区块链的应用场景，诸如股票、债券、产权等数字资产领域纷纷与区块链结合。区块链将会重塑相关领域的交互方式，重构商业环境。

区块链2.0时代的主要工作就是扩容，提升区块链的扩展性。以以太坊为代表的诸多系统从增大区块容量、提升记账节点带宽、提升记账节点处理性能、减小区块时间和减小记账节点数量等角度对链式结构做了研究。然而，链式结构从基础架构上限制了区块链整体性能的提升。作为一种数据结构，有向无环图(Directed Acyclic Graph，DAG)从数据层给了区块链更大的性能提升，是区块链迈向3.0时代的关键技术。

区块链3.0时代是区块链技术的广泛应用时代。以去中心化自洽组织(Decentralized Autonomous Organizations，DAO)和去中心化自洽公司(Decentralized Autonomous Corporations，DAC)标志的自我管理组织常态化，人类社会协作方式出现新的可能。人们的生产、生活各个方面都会接受相应的区块链概念。万物互联互信时代是区块链3.0时代的愿景。区块链3.0时代的数据量必然是海量的，链式结构难以承受海量数据中蕴含的信息运作方式。目前看来，DAG架构是区块链性能提升的首选。

DagCoin[6]最早阐述了有关DAG式区块链的理论设想，后由IOTA[7]和ByteBall[8]一脉相承，对DAG式区块链做了扩展。DAG中融合了极多的分叉，这些分叉构成了局部交易之间的相对顺序。DAG式区块链凭借异步通信机制打破了链式区块链的性能瓶颈。众多DAG模型均自称达到了物理极限，TPS(Transaction Per Second)仅受制于物理因素。海量TPS的提升为区块链挺进3.0时代指明了方向。

DAG最大的弊端来自于异步通信造成的全局无序状态。一种解决方案是控制用户的规模，进而弱化无序状态的影响，如应用于联盟链的Hashgraph[9]系统；另一种解决方案是主链延迟选择策略。系统从过去一段时间内的历史交易中选出一些符合标准并且持续相连的交易组成主链，通过主链顺序为所有交易排序，如Byteball、Conflux[10]等。

目前，DAG式区块链的研究集中在主链延迟选择策略上。一方面，如果不同用户本地历史交易数据不一致，那么这种方法必定会造成不同用户主链的不一致，如Conflux采用的GHOST[11]主链选择算法，子树节点最多的区块当选主链区块。另一方面，目前的DAG式区块链主链共识机制多为见证人共识，易造成系统安全性降低、交易时长不可控等问题，如ByteBall。本文提出一种基于DAG的区块链新模型——权益有向无环图模型(SDAG)，将DAG这种最底层的数据组织方式与POS链式共识算法结合起来。通过DAG结构去解决链式结构吞吐量有限、易分叉等问题，同时PoS链式共识会即时构建DAG式区块链的主链，控制全局状态，控制交易时长，缩短共识时间。

1 已有研究

PoS类共识算法根据用户的资源占比赋予用户相应的投票权重。通过某种规则被选择的矿工具有发布下一个区块的权利，有投票权的一组用户对每一个合法区块进行验证并投票。主流的PoS共识模型有两种，一种是需要累积确认的链式模型，另一种是结合BFT共识的模型。Nxt和Peercoin都是对比特币链式结构的模仿，属于需要累积确认的模型。而Algorand等系统则是属于结合BFT共识的模型。

传统分布式一致性算法中，Paxos[12]和Raft[13]比较有代表性，在非拜占庭(Byzantine Fault Tolerance)环境下较为适用。Pease和Lamport 在20世纪80年代提出BFT问题和解决算法，Castro等[14]提出了实用拜占庭容错共识算法PBFT(Practical Byzantine FaultTolerance)。PBFT共识算法中，如果某个交易通过了三分之二节点的验证，那么该交易就会被所有人接受，无须等待即可达成共识。

在DAG式区块链模型中，PHANTOM[15]要求新区块的反锥面中节点数小于等于k才被允许加入系统。虽然PHANTOM具有良好的扩展性，但是不能保证强的线性排序和一定的活性。SPECTRE[16]通过一种投票算法，依据锥面节点数对区块进行排序，排序靠前的区块可信度越高。不同于SPECTRE和PHANTOM中的区块之间只有父子连接，Conflux采用了父子连接和引用连接，引用连接用来标记所有未被主链区块所引用的叶子区块，极大地提升了排序效率。

1.1 DAG式区块链和链式区块链

区块链系统是一种运行在不受控环境中，可以解决拜占庭问题的分布式系统。共识算法是区块链的核心。区块链通过设定某一条件作为分布式节点达成共识的基础。共识算法负责区块链中信息的完整性，同时防御双重花费攻击，因此是区块链技术的重要组成部分。最终目标是在没有中央机构的分布式网络中实现共识，并且与不一定相互信任的参与者达成共识[17]。

根据系统中数据的组织形式(链式或者DAG式)可以将区块链分为链式区块链和DAG式区块链，其中的共识算法也多有不同。

1.1.1链式区块链

结构上，链式区块链中的每个区块有自己的时间戳，每个时间戳应当将前一个区块的时间戳纳入其随机散列值中，每一个随后的时间戳都对之前的一个时间戳进行增强，这样就形成了一个链条。图1是链式区块链的结构。区块是区块链的网络节点，是用于记录交易的数据结构。时间戳是对区块链中的每个区块上的信息加上时间验证，对每一个数据的输入追本溯源、根据时间顺序排列、验证、确保数据的真实性，不容数据被篡改，证明数据的原创性和所有权的归属。

图1 链式区块链

区块链的链式结构是对比特币系统的延续，是链式区块链共识算法的理论基础。其共识算法是为了维护系统中只有一条唯一的合法链，任何分叉链都被视作对系统的攻击。正是基于此种考虑，比特币系统产生新块的时间被设定为10 min，系统需要足够的时间保证新块被传递给所有的用户节点，保证最长链的产生者会有更多的竞争者，保证系统会有更少的分叉(这些没有收到最新区块的用户节点会产生不合法的区块)。

在链式结构的场景中，系统内节点的周期性工作是：

(1) 接收验证。用户节点时刻监听网络中的新交易，对接收的新交易进行验证，将合法的新交易放入本地缓冲区。

(2) 选择矿工。用户节点根据共识算法程序选择出唯一的矿工，即该矿工获得记账权。

(3) 打包广播。取得记账权的矿工从缓冲区中筛选出部分合法且有利的交易，将其打包并广播给所有用户节点。

(4) 最终确认。在一定时间后，该区块所在的链被逆转的风险低于用户的承受度，即完成最终确认，交易完成。

在最终确认阶段，区块链中交易顺序被改变的可能性可以被接受时，则认为完成了交易。如在比特币安全实验中，在假设攻击节点的算力占全网算力10%时，等待6个区块的确认，攻击行为成功的概率为0.059%，小于0.1%，所以比特币系统的建议确认时间是60 min左右，即历史交易需要6个新块的确认。

1.1.2DAG式区块链

在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个DAG。有向无环图常被用于交易速度极为重要的领域，比如编译器、人工智能、统计和机器学习等。

Nxt社区首次提出将DAG跟区块链结合起来。区块链本质上是DAG的受限版本，仅允许在单轨道上进行连接[6]。DAG式区块链的结构如图2所示。

在结构上。首先，不同于链式区块链中每个块只能有一个父节点，它允许每个区块指向两个或者两个以上的区块，容纳了很多分叉，这些分叉共同构成了一幅有向无环图。其次，它允许每个区块只有一个交易，如IOTA，而链式区块链中每个区块中的交易可能多达几千笔，如比特币。最后，该结构中的交易在进入系统之前就已经确立了相互之间的引用关系，该引用关系为交易确立了局部的时间先后关系，而链式区块链中默认交易之间是无序的，交易之间的顺序是由矿工来随机决定的。

在DAG式结构的场景中，每个用户节点把接收到的全部交易经初步验证后存储到本地缓冲区，然后根据主链共识算法从交易中挑选出能构成主链的交易，再剔除掉重复和双重支付的交易，最终在交易的总顺序上达成共识。系统内节点的周期性工作是：

(1) 接收验证。用户节点时刻监听网络中的新交易。

(2) 缓存交易。对接收的新交易进行验证，将合法的新交易放入本地缓冲区。

(3) 确定主链。系统根据某种主链共识算法从近期交易(区块)中筛选出唯一一条区域合法主链，进而延长从创世区块贯穿到叶子交易(区块)的主链。

(4) 最终确认。在一定时间后，主链区块被逆转的概率小于用户所能承受的风险，即交易顺序已经被绝大部分用户同意，并且很难再发生改变，则完成最终确认。

目前的主链研究工作中，主链交易(区块)均是从历史交易中筛选出来的，所以在最终确认阶段，采用累积确认的方式较多。SDAG从DAG的特殊结构出发，通过BFT类共识算法即时发布主链交易，达到快速确认的目的。

1.1.3链式区块链与DAG式区块链的不同

链式区块链与DAG式区块链除了结构上的不同，两者之间其他方面的不同如下：

(1) 链式区块链中，矿工在存入每一条交易数据之前会在全局范围内查找是否有交易与将要存储的交易数据冲突。DAG式区块链在存入数据交易之前没有全局状态，故而选择将所有数据先存储，再按某种共识将所有交易排序和剔除。

(2) 链式区块链中的交易只能由矿工按照固定时间周期添加至系统，属于定期存储策略。DAG式区块链中的交易可以由任何用户在任何时候向系统中添加，属于异步并发策略。

(3) 链式区块链的共识算法发生在阶段2(选择矿工)中，发生在将数据存入本地缓冲区之前。DAG式区块链的共识算法发生在阶段3(确定主链)，发生在将所有数据存入本地缓冲区之后。

(4) 即使某些非合法链上的区块是由诚实节点发布的，链式结构也会放弃它，并且矿工会重新打包提交给系统，浪费了很多诚实节点的算力。DAG式区块链则会保留所有人发来的交易，在排序之后剔除不合法交易。

(5) 链式区块链的共识算法的作用对象是用户节点，输出的是矿工。DAG式区块链的主链共识算法的作用对象是区块(交易)，输出的是可以构成主链的区块(交易)，是所有交易的线性顺序。

(6) 链式区块链通过保证矿工的唯一，进而确保链中交易顺序的唯一，最后通过累计确认阶段将这种交易顺序固化。DAG式区块链借助有向无环图节点(代表交易和区块)之间局部有序特性，通过主链顺序为系统中的所有交易确定顺序，最终使得所有用户在交易总顺序上达成共识。

(7) 当同时存在两个不冲突或者没有任何关系的区块(交易)的时候，链式结构规定只能保留一个，DAG式区块链则暂时全部保留。

(8) 由于DAG式区块链中，没有固定的角色向系统添加交易数据，几乎不会存在单点故障，任何人想要重建历史交易网络的可能性几乎为0。

1.2 现有DAG区块链系统

现有区块链系统中，国外以IOTA和ByteBall最为知名，国内以Conflux最为知名。

IOTA的系统模型是Tangle。系统中每个区块只有一个交易，DAG结构的节点是一条交易，每个交易必须引用两个或两个以上历史交易，以此构建DAG。新交易对历史交易的引用代表新交易的发送者对历史交易的认可，可进行分区并行验证。IOTA的共识机制是置信度共识，即新交易对历史交易的认可度。只有置信度达到一定阈值的交易才被认为是被完全确认。IOTA的优势是并行验证，劣势是无全局状态、交易时长不可控、安全性取决于活跃用户占比。目前的IOTA系统依靠中心化的协调器维护。

ByteBall系统是对IOTA的发展，引入了主链共识等重要概念。ByteBall系统采用特定人数的权威见证人帮助用户达成共识，属于主链共识。用户节点通过在历史交易有向无环图中选择出富集权威见证人交易最多的一条链，依此锚定其他交易的全局顺序，是主链延迟选择的策略。ByteBall的优势在于主链共识能够帮助交易确定全局状态，劣势是主链选择算法复杂，本地交易视图不同的用户选择出的主链容易出现不一致，见证人选择及操作偏向中心化。

Conflux系统是对比特币系统的扩展，通过使用DAG提升比特币系统的扩展性。Conflux采用主链共识机制，主链共识算法采用GHOST协议，通过挑选出子树最多的交易来延长主链，也是主链延迟选择策略。由于依然使用PoW算法，Conflux的劣势是耗时耗资源，并且主链延迟选择会导致主链不一致。

本文提出的SDAG模型主要是对主链延迟选择策略的改进，利用DAG的特殊结构，提出一种主链并行即时选择策略。

2 SDAG区块链模型设计

DAG结构中交易之间天然部分有序，整体无序。每个用户节点都有向系统写入数据的权利，并且可以为交易指定前置交易。只需要维护一条贯穿整个有向无环图的主链，所有交易间的顺序就可以被线性化。基于BFT的PoS类共识算法能够即时确认历史交易，具有数学可证的安全性、不分叉等特点，可以被用来维护主链。

2.1 SDAG模型中的角色和交易

模型中有两种角色，一类是普通用户，另一类是主链委员会用户。普通用户节点中权益排名靠前的节点成为主链委员会用户，主链委员会用户可以同时保留普通用户的角色。

普通用户负责将自己的交易广播给其他人，同时将监听到的交易缓存到本地缓冲区。主链委员会用户负责周期性共识出一个主链交易。

SDAG模型中没有区块，只有交易，可类比于区块链中的一个块中只有一笔交易，而不是上千笔交易。交易有两种类型，一种是普通交易，另一种是主链交易。普通交易由普通用户发出，只包含用户自己的交易数据以及该交易引用了哪些父交易。这些引用构成了有向无环图的单向箭头，而每一笔交易成为了有向无环图的节点。

如图3所示是SDAG中的交易结构。一个交易由时间戳、交易hash值、签名、引用hash值、交易内容组成。时间戳标识了该交易的产生时间，交易hash值确保交易数据的完整性和不可篡改，签名标识交易的发出者是哪一个用户，引用hash值用来指明该交易的父交易是哪些，交易内容则记录了用户的交易数据或者操作信息。

主链交易是由主链委员会周期性共识产生的，每个主链交易不包含任何有效交易内容，交易内容仅仅是主链交易的标识。主链交易只包含交易发出时主节点本地视图中的所有叶子节点，如图4中主链交易A1引用了交易I和交易J，主链交易A2引用了交易I2、交易H2、交易J2。

图4 SDAG的数据结构

模型规定普通用户必须引用两个或两个以上的历史交易，主链交易引用所有的叶子节点交易。主链交易引用的交易数量可能远超普通交易。两个主链交易之间的时间段是一个时间间隙，如图4中主链交易A1和主链交易A2之间存在时间间隙。

在交易构成的DAG中，将一个时间间隙内的所有交易称作交易子图，如图4中的(A2,B1,C1,D1,E1,F1,G1,I1,H1,J1)构成了一幅交易子图。

2.2 SDAG的主链共识算法

模型中的主链交易通过主链共识算法周期性产生。主链共识算法是PoS-PBFT，它仅仅是将PoS构想和PBFT相结合，是对PBFT中的角色进行定义。

2.2.1PBFT算法

PBFT算法中有三种角色：客户端、主节点、从节点。功能如下：

(1) 客户端：发送交易请求消息。

(2) 主节点：将接收到的消息排序编号，广播消息给从节点。

(3) 从节点：验证从主节点和其他从节点处接收到的消息并回应。

如果所有节点中存在f个恶意节点，那么PBFT算法需要2f+1个诚实节点就可以保证系统的正常运行。

如图5所示，PBFT共有五个阶段：request，pre-prepare，prepare，commit和reply。

图5 PBFT的共识阶段

request阶段：客户端c向主节点0发送请求消息m，格式是，其中：o代表的是请求的操作；t代表消息的时间戳；c代表消息的发出者是客户端。

pre-prepare阶段：主节点0给消息m编号，并将消息广播给从节点1、从节点2、从节点3。消息的格式是<,m>，其中:v代表视图编号；d代表消息m的摘要。

prepare阶段：三个从节点对收集到的pre-prepare消息进行验证，并将自己的验证结果广播给其他人。如果从节点认为消息有误，则不会发送消息。只有收集到包含自身在内超过2f+1个一致的回复，节点才会进入下一阶段。消息的格式是，其中i是节点自身的编号。

commit阶段：节点完成消息对应操作后，会把自己的完成状态广播给其他人，消息的格式是。节点同样需要收集包含自身在内超过2f+1个一致的回复才会进入下一个阶段。

reply阶段：节点收集足够的消息后进入reply阶段，然后向客户端发送完成消息，消息的格式是，其中r是节点的执行结果。客户端只有收集到f+1个不同节点的响应才会认为request请求被完成。

一个交易经过3个阶段验证，就会被系统中的绝大部分人确认，那么该交易就可以被认为是完全确认的。

2.2.2POS-PBFT主链共识算法

PBFT运行最少需要3f+1个节点，也就是4个节点。系统中参与共识的节点越少，共识的速度越快，去中心化越低。本文从每个用户节点的权益值出发，使得权益占有总数大于一半的普通节点参与共识，既保证了系统的共识速度，又保证了系统的去中心化程度。由于实验节点规模所限，本文从所有用户中筛选出权益最高的5个用户节点，这5个用户节点共同组成了主链交易委员会，在每轮交易周期后，系统会计算出排名靠前的用户节点，用来替换上一周期的主链交易委员会，而主链交易委员会的席位总是固定的。

在PBFT中有三种角色：客户端、主节点、从节点。将权益最高的用户节点作为主节点，主节点同时也作为客户端发起request请求，权益排名第2至第5的用户节点作为从节点。

不同于矿工独享记账权，SDAG中的所有普通节点都拥有向系统添加普通交易的权利。但是，主链交易只有主节点可以作为客户端的身份发起。主链交易不包含任何交易信息，只包含主链交易引用了哪些叶子交易。主节点提交的主链交易会经历PBFT共识，通过共识的主链交易才会被所有的用户接收。

所有用户接收到主链交易后，会根据主链交易提供的叶子节点信息对本地交易子图进行更新，如果缺少对应的交易，用户可以向其他节点请求同步，保证数据的一致性。在数据一致性的基础上，用户在本地运行排序算法。排序算法输入的是交易子图，输出的是交易子图内交易的线性顺序。并把该交易子图的顺序连接在上一个交易子图的线性顺序之后，主链得以延伸，全局状态取得一致。

由于模型SDAG中数据的一致性，用户节点能够依据本地数据同步更新各节点的权益，每一轮主链交易委员会由最新一轮状态中的前5名用户担任，这保证了委员会的去中心性。而作为模型中权益最多的前5名用户，他们的权益之和会远远大于其他用户，只要委员会保持行动一致，他们的行动就能代表系统中绝大多数诚实节点的利益，因为如果系统受到攻击，委员会成员的利益将会受损最大。

2.2.3POS-PBFT算法流程

系统初始化，所有用户节点中权益前五的用户节点成为主链交易委员会成员，权益第一的用户节点成为主节点。

主链交易的产生和普通交易的产生并行执行。主链委员会周期性产生主链交易，并且更新委员会成员，成员更换信息可以被用户节点在本地感知，无须消耗额外通信资源。网络中所有用户节点监听其他用户的交易信息，对于接收到的消息进行判断，如果是普通交易则缓存至本地缓冲区，如果是主链交易，则用户执行交易子图的排序算法，执行完毕后将排在后面的双花交易剔除，最后缓冲区中的数据被持久化到本地数据库。图6是SDAG模型中一个普通用户节点的工作流程，算法1是主链共识算法伪代码。

图6 SDAG普通节点工作流程

算法1主链共识算法

输入：交易子图。

输出：达成共识的主链交易。

// NEW_ROUND:

State=NEW_ROUND

//从交易子图中更新每个用户的权益值变化，取出权益值排名

//前5的节点作为委员会节点，权益值最高的节点作为主节点

proposer=get_proposers_address(transactionsGraph)

if (current_validator==proposer)

MCtransaction=create_MainChainTransaction(transactionsGraph)

broadcast_block(MCtransaction)

State=PRE_PREPARED

// PRE_PREPARED:

On MCtransaction.type==PRE_PREPARE

verify_transaction (MCtransaction)

verify_validator(MCtransaction)

broadcast_prepare(MCtransaction)

State=PREPARED

// PREPARED:

On MCtransaction.type==PREPARE

verify_prepare(MCtransaction.prepare)

verify_validator(MCtransaction.prepare)

prepare_pool.add(MCtransaction.prepare)

if (prepare_pool.length>2F+1)

broadcast_commit(MCtransaction.prepare)

State=COMMITTED

// COMMITTED:

On MCtransaction.type==COMMIT

verify_commit(MCtransaction.commit)

verify_validator(MCtransaction.commit)

commit_pool.add(MCtransaction.commit)

if (commit_pool.length>2F+1)

transactions.append(MCtransaction)

State=FINAL_COMMITTED

// FINAL_COMMITTED:

broadcast_ commited(MCtransaction)

2.3 SDAG的交易排序

交易之间的引用拓扑关系是交易的发送者指定的，为用户交易的执行设定前置条件。但是这种顺序只能是局部的，全局交易之间是完全无序的，虽然DAG追求的是所有交易都应有一个准确的线性顺序，但是这种顺序是不可求解的，也不是必须的。如在比特币系统中，虽然区块之间是线性关系，但是一个区块中有几千笔交易，这些交易之间的顺序并不是交易的发送者指定的，比特币系统默认这几千笔交易并行执行。如图7所示的那样，区块内的所有交易之间是毫无关联的。

图7 链式结构中的区块和交易

本文所述SDAG模型将区块解构为交易子图，等同于将区块中的交易展开，并附加上交易之间的原始先后关系，这种细粒度的交易执行关系对于智能合约等时序性和严谨性要求较高的适用场景是极为必要的。

交易子图的排序规则如下：

(1) 被引用的交易一定先于发出引用的交易。可以传递引用，如a引用b，b引用c，那么a一定晚于c。传递引用按照最长路径计算。

(2) 对于不在引用关系的交易按照时间戳进行排序。

(3) 对于时间戳相同的交易，按照hash值的字典顺序进行排序。

交易子图越小，该子图内的交易顺序越精确，反之越模糊。交易之间最精确的顺序是由引用关系推导出来的，把交易的时间戳纳入排序因素得到的顺序精确度次之，把交易hash值纳入排序因素得到的交易顺序最模糊。

交易排序算法见算法2。

算法2排序算法

输入：交易子图。

输出：交易子图中交易的链式顺序。

//从主链交易开始，依据叶子节点把交易子图中的交易按照引

//用关系导出为几条交易链,返回链表头部

List lists=getAllTransactionList();

List newList=new List();

While(allLisyIsNotNull){

//依次取出每条交易链表中的交易，按照时间戳和交易hash值

//的字典顺序插入到新的交易链中

newList.add( transctionFromLists );

}

return newList；

2.4 SDAG的数据一致性

虽然DAG中的交易顺序没有唯一的解，但是只要每个用户节点接收到的交易是完全一致的，并且按相同的原则处理，那么依然可以保证所有用户数据的一致性。

由于每个交易都会存储父交易的hash值，并且会把父交易的hash值作为自己交易的一部分进行hash。这种增强的关系，确保了只要叶子交易(未被其他交易引用的交易)是一致的，那么交易子图就是一致并且完整的。用户可以根据叶子节点中父交易的hash进行回溯遍历，遍历的起点是此时的主链交易，终点边界是被上一个主链交易引用过的已排序交易。

SDAG模型的一致性不仅代表交易内容的一致性，还隐含有交易执行顺序的一致性。

2.5 确认交易

由于普通交易的顺序完全取决于主链交易，所以只需要确认主链交易即可。主链共识采用PoS-PBFT共识算法，每一个新交易的产生都需要经过主链交易委员会的投票确认。获得委员会的多数通过即代表该主链交易已经被确认，该主链交易引用的交易子图中的交易也被确认。这种确认是即时的，并不依赖于后续主链交易对该主链交易的引用。

主链交易的定期产生和即时确认特性保证了SDAG中交易的确认时间是可控的，不会出现DAG式区块链中常见的交易时长不可控问题和主链偏差问题。

3 SDAG区块链模型的实现

3.1 SDAG架构

SDAG模型中的普通交易由普通用户实时产生并广播，主链交易由主链交易委员会周期性共识产生并广播，这两部分工作可以并行进行，只要用户节点在收到主链交易的时候对本地数据进行同步检查即可。

如图8是SDAG的架构，由网络层、共识层、缓冲区和本地数据库四部分组成。图中的加粗黑色圆环代表主链交易，而细实线圆代表普通交易。网络层负责用户节点间的点对点通信，所有交易通过网络层进行广播。共识层负责定期产生主链交易。缓冲区负责对接收到的数据进行初步验证，保留合法数据。本地数据库用以持久化经过全局验证的合法交易。

3.2 系统平台和开发工具

本文使用Java平台实现SDAG模型，开发环境如表1所示。

3.3 程序结构

图9是SDAG系统的程序结构，分为以下几个部分：dao部分用来实现用户节点的数据持久化；service部分实现了节点收到交易后的一系列操作；socket部分实现了节点间的网络通信；resources部分存储了节点的配置文件；test部分用以对相关功能的测试。

图9 SDAG系统的程序结构

3.4 网络层实现

SDAG系统采用P2P网络结构，各节点之间无须通过服务器或者其他节点中转。节点之间使用TCP协议，通过Socket套接字通信。交易数据通过指定的端口和用户节点的IP地址进行传输。

主链交易和普通交易都是通过网络层传输。transocket部分用来实现普通交易的传输和接收，MCsocket部分用来实现主链交易的共识算法部分的通信。模型实现过程中，使用5个用户节点，分别为2种交易分配端口1和端口2，每个用户对端口1保持监听从而收集网络中的普通交易，对端口2进行监听从而收集网络中的主链交易。

3.5 数据层实现

数据层实现了对交易进行hash运算和存储。系统采用SHA-256算法对交易进行hash运算。具体做法是在生成交易信息后，对时间戳、交易内容和引用的父hash三部分进行hash运算得到一串字符串，并将它作为交易的唯一识别标识。

系统采用MySQL数据库对交易数据进行持久化。在交易数据被持久化到数据库中之前，系统会使用一个缓冲队列去保存被初步验证过的普通交易，直到接收到主链交易后，缓冲区内的所有交易作为一个交易子图被持久化到数据库中。

3.6 普通交易的方法实现

3.6.1普通交易的产生

当普通用户节点P1产生一条新交易时，他会首先为自己的交易选择两个历史交易作为父交易。这两个历史交易可以是该用户指定的，也可以是系统随机选择的，其中选择最新的历史交易最佳。P1发出的普通交易结构如图10所示。

3.6.2普通交易的广播和接收

用户在广播的时候，会选择所有其他用户的IP地址，使用端口1进行发送数据。多个用户可以同时发起并广播交易。

所有用户在通过Java ServerSocket接收方式监听端口1的时候，会接收到P1发送的交易数据。由于实际运行过程中会接收到很多不同用户的交易，SDAG系统中的用户需要使用线程池提供多线程的方式接收突然而至的大量数据。在接收到P1的交易数据时，用户节点会调用普通交易的验证方法，并把合法交易放在缓冲区中。

3.7 主链交易的方法实现

系统初始化的时候会为所有用户节点分配一定的权益值，权益值是总数一定的积分，无论各节点间的权益如何转让，系统中的权益总和是不变的。权益值最高的用户节点会自动当选为PoS-PBFT主链共识算法中的主节点。

收到主链交易后，每个用户节点会自动根据交易子图中的交易信息感知该时间间隙内的权益变化。权益值最高的用户自动当选下一周期的主链节点，权益值最高的5个节点当选为下一个周期内的主链委员会用户。如果交易子图中并无权益流动转移，则原有节点的角色不变。

模型实现的过程中分配给P1最多的权益，即P1当选主链委员会中的主节点，P2、P3、P4和P5为主链委员会用户中的从节点。主链交易由主节点P1发起，并引用主节点本地的所有叶子节点。主节点P1将主链交易通过端口2和IP地址发送给其他主链委员会用户进行投票确认。主链交易结构如图11所示。

3.8 主链交易的共识过程

(1) 从节点Pi(i=2,3,4,5)收到主节点P1的交易后，验证并生成准备消息，对准备消息进行签名后进行广播。

(2)Pi(i=1,2,3,4,5)接收到其他用户节点的准备消息后进行验证。若来自不同节点的消息数量超过2f+1(f为作恶节点)并且消息一致无误，Pi节点生成提交消息，签名后广播。

(3)Pi(i=2,3,4,5)接收到其他用户节点的提交消息后进行验证。若来自不同节点的消息数量超过2f+1并且消息一致无误，Pi节点生成确认提交消息，签名后广播。

(4) 主节点P1收到包含自己在内f+1个一致的确认提交消息后，即可认为发出的主链交易获得了主链委员会的共识。

3.9 交易的确认和存储

在接收到共识的主链交易后，所有用户会做出调整，保证在该时间间隙内与主节点具有相同的叶子节点交易和交易子图。主链交易的连续性和hash值的持续增强，保证了该时间间隙内所有节点的交易子图完整性和唯一性。

所有用户节点根据主链交易内引用的叶子节点构造该时间间隙内的交易子图。用户节点运行交易子图排序方法，进而为每一个交易安排一个唯一的全局顺序。最后每个用户会对双重花费交易等恶意交易进行剔除。至此，所有用户对历史交易的顺序达成共识。

交易子图内的交易和主链交易会被存储到每个用户的本地数据库中。

4 模型分析

由于SDAG数据组织方式是DAG，并且每个用户节点都有普通交易的读写权限，系统可以实现并行写入。同时普通交易的产生和主链交易的产生也可以并行进行，因为主链交易仅仅只是在普通交易子图中做了个标记。主链交易不包含需要被复杂程序验证的交易数据，验证简单，带宽消耗少。以下公有链数据均来自官方文档。

本文实验采用30个用户节点去实现SDAG模型。实验环境所用带宽是10 Mbit，表2是实验节点的配置。

4.1 吞吐量分析

TPS代表每秒系统交易数，计算公式为:

TPS=TransactionNum/t

式中：t代表时间段；TransactionNum代表系统处理的交易数量。TPS是系统承载能力的指标，单位时间内系统能够处理的交易越多，系统的TPS越高。图12是本系统在实验环境下的5节点吞吐量测试数据，5个节点时系统TPS最高为380。如图13所示，随着普通用户节点的增多，参与共识节点数量不变的情况下，TPS稳定在330左右。

4.2 确认时间测试

由于SDAG采用PoS-PBFT共识算法，参与共识节点少，主链交易处理程序简单，故而系统确认时间可以达到秒级，并且随着系统规模的扩大，系统的确认时间仅与网络规模相关性较强。而比特币的确认时间是10 min左右，conflux的确认时间在7 min左右。

如图14所示，随着节点数的增多，SDAG的确认时间稳定在3 350 ms左右，可以为系统提供即时确认。

4.3 数据一致性分析

SDAG的主链共识算法采用PoS-PBFT，通过主链交易这个检查点，能够以点带面，保证交易子图的完全一致，进而使得所有用户节点的本地状态保持一致。SDAG的一致性相对于Conflux采用的GHOST共识更高，比Byteball等采用的见证人共识等滞后确定主链方案更可靠即时。

此外，DAG能给交易附加引用边，该引用可以由用户为交易设定，用来控制交易的细粒度执行顺序，使得SDAG的一致性在交易的执行顺序上更加深入细腻。SDAG较高的一致性使它更符合重要场景的需求，更符合智能合约的部署。

4.4 安全性分析

SDAG应用PoS-PBFT共识算法来选择主链交易，因此，SDAG主链的安全性不低于PBFT共识算法的安全性，只要恶意用户节点的权益低于系统总权益的三分之一，系统就是安全的。由于系统中的权益是封闭的，非系统节点不会获得权益，权益也无法从外部补充，只能在封闭系统内部流转，所以系统的安全性要高于PBFT的安全性。

主链共识算法为系统所有交易确定了线性顺序，只要主链交易得到确认，那么全局顺序就是确定的，是不可逆的。

由于系统内的最小数据单元是交易，完全重复的交易很容易被识别并被清除，所以系统不会出现链式结构中重复区块分叉现象，诚实算力不会被浪费，恶意节点会被最大程度地压制。

DAG是一种特殊的数据组织结构，其拓扑排序是唯一的。一方面，DAG中海量的分叉结构使得交易之间联系更加紧密，另一方面普通用户也有存储数据的权利，所以即使攻击者获得了系统的掌控权，他也不可能伪造一份新的历史交易，从而消除自己的历史花费。特殊的结构使得SDAG也不会遭受PoS链式结构中的无风险支持分叉攻击、理性分叉、币龄攻击、长程攻击等攻击。