基于DAG的联盟链共识机制研究与分析

宋东翔，马伽洛伦，王怡然，朱福林通信作者）

1.德宏师范高等专科学校，云南德宏，678400；2.德宏职业学院，云南德宏，678400； 3.德宏州卫生健康委员会计划生育协会，云南德宏，678400

0 引言

有向无环图DAG（directed acyclic graph）采用了有向无环图的存储结构，是一种新的区块链存储结构[1]。但其仍然面临着许多问题，例如是否能够像链式区块链存储那样可以使分布式存储的信息保持一致、是否会产生拜占庭将军问题、双花问题要怎么处理等[2]。近年来，已经有很多学术论文和科技公司针对这些问题做了大量的研究。拜占庭将军问题（byzantine failures）是由莱斯利·兰伯特提出的点对点通信中的基本问题[3]，而一个可能呈现任意行为的节点被称为拜占庭。任意行为意味着“所有能想象到的事情”，比如根本不发送任何消息、向不同的邻居发送不同且错误的消息以及谎报自己的输入值。双花问题简单来说就是消费两次，例如：在A商店买了一瓶水，在B商店买了一包瓜子，两个商店几乎同时消费；假设商店都不等待确认，如果A或B商店支付结束后其中一家没有收到货币，这样就实现了一次双花。对于这些问题，IOTA团队提出使用PoW权重比较进行共识的解决方案[4]；Byteball和TrustNote则提出选取公证人共识节点进行共识，由公证共识节点提交公证单元来完成MC定序，判断查找出无效单元，避免双花攻击。本文主要基于DAG的区块链拜占庭共识和双花问题进行研究，对IOTA-PoW权重、Byteball公证人节点和TrustNote公证人节点的共识方法进行比较[5-6]。

1 DAG的技术

如图1所示，G单元为创世单元，无序号单元为未引用单元（或无字单元），单元14被蓝色单元15引用，称为直接引用。由蓝色单元15顺着图的方向到达创世单元G的主链MC（main chain），对所有单元进行的排序称为主链索引MCI（main chain index）[7]。单元9被MC上的单元10和不在MC上的黄色单元11所引用，由于单元10在MC上面，单元10的MCI为10；黄色单元11不在MC上，但是黄色单元11被MC的单元11直接引用，所以黄色单元11分配的MCI为11。同理，黄色单元15被MC上的单元15引用，称为间接引用，黄色单元的MCI为15。如果一个DAG序列受到双花攻击，有可能出现两种情况。①两个相同数据输出的单元被有序引用，即一个单元（直接或间接）中包括另一个单元；如图1所示，在先提交了蓝色单元14之后，后来的蓝色单元15如果提交相同的输出，此时通过判断父单元的数据发现双花，则利用DAG的共识安全地拒绝后面的蓝色单元15。②建立单元之间的总序后，他们隐藏在足够深的新单元里；如图1所示，黄色的单元11和单元15都不属于同一序列，他们之间是无序关系，此时系统无法分辨出哪个单元的信息有效，只能先接收，再通过后续主链单元间接引用共识数据。

2 方法研究

2.1 IOTA

IOTA提出了自己的系统结构Tangle（缠结），基于有向无环图结构（DAG）不是一种连续的链式架构，不能够定期添加区块[8]。如图2所示，每个表示交易的小方块右下角的数字被称为权重，这个权重t是和PoW所付出的计算量相关的。假如有2笔交易，通过PoW（proof of work）算出来的二进制值分别为x和y，x的开头是2个0，y的开头是4个0，得到y所需要的计算量一定是大于x的，所以交易y的权重会比交易x的权重大。在IOTA里，权重的取值范围是3n，所以权重t的取值只可能是如1、3、9、27之类的数。方块里左上角的数字被称为累积权重，等于这个交易自己的权重加上所有直接或间接指向它的交易的权重总和。比如交易F，直接或间接指向F的有A、B、C、E，所以F的累计权重为1+3+1+1+3=9。IOTA解决双花问题的方法是：节点会计算每个交易的权重值，选择权重高的交易来进行验证，有助于增加自己的交易被后来交易验证的可能性。如果这笔交易非法绑定，后来的交易则不会选择这笔交易来验证。交易数量越来越多，这笔没有被验证的交易就会被网络抛弃。如图2所示，通过协议选择累计权重高的单元F去计算权重值，需要计算的权重值为3，F单元的累计权重为9，后来通过验证F成功产生的单元Q是在F之后，完成验证。

2.2 Byteball

Byteball解决双花问题，是通过观察网络的一些参与者，他们可能是非匿名长期参与社区并且拥有良好信誉的，或许是主动维护网络健康发展的，这些参与者统称为证人[9]，证人会在一个周期内循环发布公证单元参与系统的共识。如果需要验证公证单元的真实性，回溯DAG链中的MC，统计成为公证单元的个数（对于重复的公证单元不会被重复计数）。如图3所示，把P作为证人发布的公证单元，选择一个MC上的交易单元W，在MC上向创世单元G做回溯，统计成为公证单元的数量为5个，分别是单元9、单元7、单元6、单元4和单元1。回溯时遇到公证单元则停止前进，计算从创世单元到停止单元的长度，这个长度被称为停止单元的级别。例如在回溯到公证单元7和公证单元6时，看见公证单元，停止回溯，通过计算，选择的最大停止单元级别为7，同时该公证单元的父母单元被选择为最佳父母单元。如果同时存在一些较大见证级别的竞争者参与竞争，则会选择其中最低级别的父母单元。如果一个攻击者自己秘密建立一个属于自己的单元长链（影子链），其中还包含了双花，如图3所示，在图中红色圈内显示为灰色的单元链就是影子链。影子链最终合并到了DAG序列中，这时最佳父母选择算法会在合并点处把影子链驱动到MC的最佳父母单元，由于影子链中的单元被最佳父母单元15直接和间接引用，所以他们的MCI只能为15，但这些单元数据都不在MC上，所以这段影子链的单元数据都被视为无效。

2.3 TrustNote

TrusNote团队提出了TrustME-PoW的共识算法，使用PoW的工作量证明共识机制选取公证人[10]。TrustME-PoW中提出了超级节点的概念，只有超级节点才具有争夺成为公证人的资格。要成为超级节点，需要满足以下的条件：①具有良好的网络带宽资源、存储空间和运算能力，有独立公网IP的最好；②需要在共识周期内有足够的TrusNote虚拟货币作为激励机制的奖励；③在之前的共识中，提交的所有公证单元都被全网认证为有效。该算法每轮共识都会选择参与竞选的少量超级节点成为公证节点，并确定公证节点的优先级。每一轮TrustMEPoW共识算法的执行周期是五分钟，每次共识完成都会选出不超过二十个超级节点作为公证节点，被选择的公证节点有权利发送公证单元并且以此获得虚拟货币作为公证奖励。该算法解决双花问题的方法是尝试在DAG图上找到一条以创世单元为起点的MC，并给位于MC上的单元分配索引，创世单元的索引为0，创世单元的子单元索引为1，以此类推。然后，对于不在MC上的单元，定义其索引等于引用此单元的第一个MC单元的索引。最终，DAG序列上的每笔交易都拥有了一个索引。如果两笔交易尝试使用同一笔输出，只需要比较MCI的大小，小的有效，大的无效，由此解决双花问题。例如DAG中存在两笔双花交易，首先通过MC为单元定序MCI，当确定了它们的MCI，其中一笔双花的MCI是11，而另一笔双花的MCI是15；通过比较两笔交易的MCI，判断具有较小MCI的交易11有效，大的MCI交易15无效。

3 综合分析

通过模拟实验测试，对以下四个性能指标进行分析。①时延：表示改进的共识算法在执行过程中所花的时间，该时间的减少会减少用户的等待时间，改善用户对应用的体验。②成本：是指对于全网系统的经济投入，如果参与全网的共识节点的经济投入太大，则不利于小型联盟链的建立和发展。③功耗：主要指的是在共识算法的执行过程中，对于CPU的利用率，PoW的共识算法对于CPU的利用率非常高。④容错性：是指在系统参与共识的节点中，可以容忍出现错误共识节点的数量；容错性可以保证在遭受修改共识节点信息等攻击时，系统仍然可以良好地运行。如表1所示，IOTA的优点是采用了工作量证明，将系统容错率提升为50%。PoW算法设置的难题比区块链简单，解题时间在5～20分钟之内；缺点是每一次交易都需要节点去提供算力，PoW的原理就是要耗费发起者一定量的计算资源，并且使用PoW共识的时延较高。Byteball使用选取12名公证人的共识机制，比PoW功耗低、时延高，但是这12名公证人是人为设定的，系统的容错率较低。TrusNote同样使用PoW共识，但系统使用超级节点，通过虚拟货币的激励机制保证系统中的超级节点都努力维护系统的稳定运行，使系统的功耗低、时延低。

表1 性能比较

4 结语

本文综合分析了IOTA的工作量证明共识、Byteball的选取公证人机制和TrusNote的TrustME-PoW共识算法三种基于DAG数据结构的共识方法。这三种方法都能够应对拜占庭容错和双花攻击问题，但通过性能分析，三种方法都不适用于当前联盟链的应用场景。本文综合三种方法，基于TrustME-PoW共识算法提出了改进思想：①取消超级节点的设定，降低联盟链中节点配置所产生的经济成本；②取消PoW工作量证明的提供算力的算法，降低对节点的资源消耗；③删除使用虚拟代币作为奖励的激励机制，采用信用积分机制来作为系统共识的凭据。希望在日后的研究中，能够根据思路完成改进。