基于有向无环图的支持合约的分布式账本共识方法与系统

摘要

本发明公开了一种基于有向无环图的支持合约的分布式账本共识方法与系统，属于区块链技术领域。本发明设计了基于有向无环图的去中心化分布式账本数据结构，通过引入强连接、弱连接关系实现有向无环图内的局部全序关系，从而支持智能合约；并通过具备权值更新的顶点添加方法，为并发添加顶点提供可验证的规则；此外，还设计了分叉剪枝方法，利用权值对顶点进行可信或不可信标记，并删除不可信顶点及相关边，解决了现实中分布式账本存在的网络延迟、黑客攻击等问题。与现有技术相比，本发明结合了有向无环图的高并发优势和区块链的全序关系优势，在支持智能合约的基础上，提高了去中心化分布式账本的并发性能，使其应用领域更为开阔。

权利要求

1.一种基于有向无环图的支持合约的分布式账本共识方法，其特征在于，所述分布式账本的创世顶点不连接有向无环图的任意顶点，第二个添加到有向无环图的顶点必须连接创世顶点；从第三个添加到有向无环图的顶点开始，顶点类型包括合约定义顶点和合约交易顶点；第二个添加到有向无环图的顶点类型必须为合约定义顶点；每个顶点含两个编号，一个是合约编号，一个是交易编号，且每个交易编号均不相同；当添加到有向无环图的顶点的类型为合约定义顶点时，顶点的合约编号不得与有向无环图中任意其他顶点的合约编号相同；当添加到有向无环图的顶点的类型为合约交易顶点时，顶点的合约编号必须属于在有向无环图中所有顶点的合约编号构成的集合；当添加到有向无环图的顶点的类型为合约交易顶点时，顶点必须强连接有向无环图中的一个顶点，并弱连接有向无环图中至少一个顶点；网络节点在定义一个新的智能合约时，或者根据现有的智能合约及其状态发起一笔新的交易时，向有向无环图中添加顶点，并将账本同步到网络中的其他网络节点，具体顶点添加的步骤包括：

为即将添加到有向无环图中的新顶点赋权值，所述权值为正整数；

预选择零个或一个可被强连接的顶点，预选择一个或多个可被弱连接的顶点，然后将新顶点强连接到预选择的可被强连接的顶点上，并弱连接到所有预选择的可被弱连接的顶点上；所述强连接满足新顶点与预选择的顶点含有相同的合约编号，所述弱连接满足新顶点与预选择的顶点含有不同的合约编号；

对有向无环图中顶点的权值进行更新；

在添加顶点后，对有向无环图进行分叉剪枝，所述分叉是一个或多个类型为合约交易顶点的新顶点未强连接到最新的可被强连接的顶点，导致多个顶点强连接到同一个顶点的现象，所述剪枝是将部分顶点和与这些顶点有关的边删除，使得含相同合约编号的顶点依次连接构成一条链。

2.根据权利要求1所述的基于有向无环图的支持合约的分布式账本共识方法，其特征在于，顶点选择策略是：如果新顶点的类型是合约定义顶点，则不选择可被强连接的顶点，且预选择至少两个可被弱连接的顶点；如果新顶点类型是合约交易顶点，则预选择一个可被强连接的顶点，预选择至少一个可被弱连接的顶点。

3.根据权利要求1所述的基于有向无环图的支持合约的分布式账本共识方法，其特征在于，预选择可被强连接的顶点时，选择有向无环图中所有可被强连接的顶点集合中最新的一个顶点。

4.根据权利要求1所述的基于有向无环图的支持合约的分布式账本共识方法，其特征在于，根据如下方法预选择可被弱连接的顶点：首先根据新顶点的合约编号和交易编号代入生成伪随机数的函数中，获取多个输出值；

然后选取前k个输出值，每个输出值均在由有向无环图中已存在的合约编号构成的集合里；其中k为配置的最大弱连接数；

再从选取的输出值中，选择一个以该输出值为合约编号的顶点，且该顶点是在所有以该输出值为合约编号的顶点中最新添加到有向无环图的，至多选择k个顶点作为预选择可被弱连接的顶点。

5.根据权利要求1所述的基于有向无环图的支持合约的分布式账本共识方法，其特征在于，所述创世顶点的合约编号、交易编号与权值均为0。

6.根据权利要求1所述的基于有向无环图的支持合约的分布式账本共识方法，其特征在于，根据如下方法更新有向无环图中顶点的权值：新顶点所属的强连接链包含的除该新顶点以外的每个顶点的权值w修改为其中，w′为更新后的权值，th为配置的顶点可信阈值；

新顶点所属的弱连接链包含的除该新顶点以外的每个顶点的权值w修改为其中，表示自然数；新顶点所属的弱连接链指被所述新顶点弱连接的顶点所属的强连接链的中所有顶点的集合。

7.根据权利要求1所述的基于有向无环图的支持合约的分布式账本共识方法，其特征在于，为避免由于网络延迟、黑客攻击导致网络节点并不能总是将一个合约交易顶点与最新的与其合约编号相同的顶点强连接，网络节点在添加顶点后，还根据如下方法对有向无环图进行分叉剪枝：

在新顶点添加完毕后，扫描该顶点所属的强连接链与弱连接链，将链上所有权值小于等于可信阈值的、且未标记为“可信的”顶点，标记为“可信的”；其中顶点v所属的弱连接链指被顶点v弱连接的顶点所属的强连接链的中所有顶点的集合；

然后在被新标记为“可信的”顶点所强连接的先序顶点，如果被其他顶点强连接，则将其他这些顶点标记为“不可信的”；

再将强连接被标记为“不可信的”顶点的顶点标记为“不可信的”，直至不再有顶点强连接被标记为“不可信的”顶点；

最后删除所有被标记为“不可信的”顶点，及有关的边。

8.一种基于有向无环图的支持合约的分布式账本共识系统，其特征在于，所述分布式账本的创世顶点不连接有向无环图的任意顶点，第二个添加到有向无环图的顶点必须连接创世顶点；从第三个添加到有向无环图的顶点开始，顶点类型包括合约定义顶点和合约交易顶点；第二个添加到有向无环图的顶点类型必须为合约定义顶点；每个顶点含两个编号，一个是合约编号，一个是交易编号，且每个交易编号均不相同；当添加到有向无环图的顶点的类型为合约定义顶点时，顶点的合约编号不得与有向无环图中任意其他顶点的合约编号相同；当添加到有向无环图的顶点的类型为合约交易顶点时，顶点的合约编号必须属于在有向无环图中所有顶点的合约编号构成的集合；当添加到有向无环图的顶点的类型为合约交易顶点时，顶点必须强连接有向无环图中的一个顶点，并弱连接有向无环图中至少一个顶点；所述系统包括多个网络节点，所述网络节点设有顶点添加模块和分叉剪枝模块，用于在定义一个新的智能合约时，或者根据现有的智能合约及其状态发起一笔新的交易时，向有向无环图中添加顶点；所述顶点添加模块包括：新顶点赋权值单元，用于为即将添加到有向无环图中的新顶点赋权值，所述权值为正整数；

现有节点连接单元，用于预选择零个或一个可被强连接的顶点，预选择一个或多个可被弱连接的顶点，然后将新顶点强连接到预选择的可被强连接的顶点上，并弱连接到所有预选择的可被弱连接的顶点上；所述强连接满足新顶点与预选择的顶点含有相同的合约编号，所述弱连接满足新顶点与预选择的顶点含有不同的合约编号；

权重更新单元，用于对有向无环图中顶点的权值进行更新；

以及同步单元，用于将账本同步到网络中的其他网络节点；

所述分叉剪枝模块，用于在添加顶点后，对有向无环图进行分叉剪枝，所述分叉是一个或多个类型为合约交易顶点的新顶点未强连接到最新的可被强连接的顶点，导致多个顶点强连接到同一个顶点的现象，所述剪枝是将部分顶点和与这些顶点有关的边删除，使得含相同合约编号的顶点依次连接构成一条链。

9.根据权利要求8所述的一种基于有向无环图的支持合约的分布式账本共识系统，其特征在于，所述分叉剪枝模块包括：

可信顶点标记单元，用于在新顶点添加完毕后，扫描该顶点所属的强连接链与弱连接链，将链上所有权值小于等于可信阈值的、且未标记为“可信的”顶点，标记为“可信的”；其中顶点v所属的弱连接链指被顶点v弱连接的顶点所属的强连接链的中所有顶点的集合；

直接不可信顶点标记单元，用于在被新标记为“可信的”顶点所强连接的先序顶点，如果被其他顶点强连接，则将其他这些顶点标记为“不可信的”；

间接不可信顶点标记单元，用于将强连接被标记为“不可信的”顶点的顶点标记为“不可信的”，直至不再有顶点强连接被标记为“不可信的”顶点；

以及剪枝单元，用于删除所有被标记为“不可信的”顶点，及有关的边。

10.一种计算机系统，其特征在于，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述计算机程序被加载至处理器时实现根据权利要求1‑7任一项所述的基于有向无环图的支持合约的分布式账本共识方法。

说明书

基于有向无环图的支持合约的分布式账本共识方法与系统

技术领域

[0001] 本发明公开了一种基于有向无环图的支持合约的分布式账本共识方法与系统，属于区块链技术领域。

背景技术

[0002] 分布式账本是一种在网络节点之间共享、复制和同步的数据库。按网络节点的结构划分，可分为中心化的结构和非中心化的结构两种。中心化的结构意味着这些网络节点
中存在一个核心节点，管理着其他节点，或者在数据库的运作过程中扮演重要角色，一旦该
核心节点失效，一个或多个数据库操作便无法进行。去中心化的结构意味着这些网络节点
地位平等，不存在一个核心节点，即在一定数量的节点失效时，数据库仍能正常运作。比特
币、以太坊和超级账本等区块链平台所使用的基于区块链的数据库就属于去中心化分布式
账本。

[0003] 智能合约是一种旨在以信息化方式传播、验证或执行合约的计算机协议。智能合约允许在没有第三方的情况下进行可信交易，这些交易可追踪且不可逆转，天然地适合与
区块链等去中心化分布式账本技术结合，从而开发出去中心化的、基于智能合约的应用程
序，实现自动化可信交易等功能。超级账本、以太坊和一些基于以太坊的区块链平台，都是
支持智能合约的去中心化分布式账本平台。

[0004] 目前，不少去中心化的分布式账本采用的是“区块链”数据结构。区块链由一个个“区块”按时间顺序连接而成，形成链表。区块包含了区块头和区块体，区块头中记录着前一
个区块的哈希值、当前区块的哈希值，另外还有时间戳和交易数量等元信息。区块体中记录
着交易的详细内容，如交易发起方、收款方、金额和时间戳等。一个区块体可以包含一笔或
若干笔交易。根据区块链平台的不同，区块链的具体实现有所区别。

[0005] 但是，去中心化分布式账本的性能问题一直是研究的热点。以以太坊为例，它的吞吐量大约为每秒15笔交易，交易确认延迟大约为10分钟。在实际应用中，这种交易处理能力
是远远不足的。为了提高性能，现有一些方法放弃使用基于链表结构的区块链，转而使用基
于非链表结构的分布式账本技术，如采用有向无环图。对于有向无环图来说，如果认为图中
的每个顶点是一笔交易，新的交易以某种方式连接到现有的图上，由于有向无环图天然地
只具备偏序关系，而不具备全序关系，在提高了交易的并发能力从而提高吞吐量的同时，严
格的交易顺序变得难以确定。智能合约由于涉及数据状态的有序修改，与分布式账本的结
合必然要求分布式账本具备全序关系。如何使得有向无环图具备全序关系从而支持智能合
约的同时，分布式账本的性能优良，就变得十分重要。

发明内容

[0006] 发明目的：针对现有技术的不足，本发明的目的在于提供一种基于有向无环图的支持合约的分布式账本共识方法与系统，在支持智能合约的基础上，提高去中心化分布式
账本的并发性能，使得去中心化分布式账本的应用领域更为开阔。

[0007] 技术方案：为实现上述发明目的，本发明采用如下技术方案：

[0008] 一种基于有向无环图的支持合约的分布式账本共识方法，所述分布式账本的创世顶点不连接有向无环图的任意顶点，第二个添加到有向无环图的顶点必须连接创世顶点；
从第三个添加到有向无环图的顶点开始，顶点类型包括合约定义顶点和合约交易顶点，网
络节点在定义一个新的智能合约时，或者根据现有的智能合约及其状态发起一笔新的交易
时，向有向无环图中添加顶点，并将账本同步到网络中的其他网络节点，具体顶点添加的步
骤包括：

[0009] 为即将添加到有向无环图中的新顶点赋权值，所述权值为正整数；

[0010] 预选择零个或一个可被强连接的顶点，预选择一个或多个可被弱连接的顶点，然后将新顶点强连接到预选择的可被强连接的顶点上，并弱连接到所有预选择的可被弱连接
的顶点上；所述强连接满足新顶点与预选择的顶点含有相同的合约编号，所述弱连接满足
新顶点与预选择的顶点含有不同的合约编号；

[0011] 对有向无环图中顶点的权值进行更新。

[0012] 作为优选，顶点选择策略是：如果新顶点的类型是合约定义顶点，则不选择可被强连接的顶点，且预选择至少两个可被弱连接的顶点；如果新顶点类型是合约交易顶点，则预
选择一个可被强连接的顶点，预选择至少一个可被弱连接的顶点。

[0013] 作为优选，预选择可被强连接的顶点时，选择有向无环图中所有可被强连接的顶点集合中最新的一个顶点。

[0014] 作为优选，根据如下方法预选择可被弱连接的顶点：

[0015] 首先根据新顶点的合约编号和交易编号代入生成伪随机数的函数中，获取多个输出值；

[0016] 然后选取前k个输出值，每个输出值均在由有向无环图中已存在的合约编号构成的集合里；其中k为配置的最大弱连接数；

[0017] 再从选取的输出值中，选择一个以该输出值为合约编号的顶点，且该顶点是在所有以该输出值为合约编号的顶点中最新添加到有向无环图的，至多选择k个顶点作为预选
择可被弱连接的顶点。

[0018] 作为优选，所述创世顶点的合约编号、交易编号与权值均为0。

[0019] 作为优选，根据如下方法更新有向无环图中顶点的权值：

[0020] 新顶点所属的强连接链包含的除该新顶点以外的每个顶点的权值w修改为

[0021]

[0022] 其中，w′为更新后的权值，th为配置的顶点可信阈值；

[0023] 新顶点所属的弱连接链包含的除该新顶点以外的每个顶点的权值w修改为

[0024]

[0025] 其中，表示自然数；新顶点所属的弱连接链指被所述新顶点弱连接的顶点所属的强连接链的中所有顶点的集合。

[0026] 作为优选，为避免由于网络延迟、黑客攻击导致网络节点并不能总是将一个合约交易顶点与最新的与其合约编号相同的顶点强连接，网络节点在添加顶点后，还根据如下
方法对有向无环图进行分叉剪枝：

[0027] 在新顶点添加完毕后，扫描该顶点所属的强连接链与弱连接链，将链上所有权值小于等于可信阈值的、且未标记为“可信的”顶点，标记为“可信的”；其中顶点v所属的弱连
接链指被顶点v弱连接的顶点所属的强连接链的中所有顶点的集合；

[0028] 然后在被新标记为“可信的”顶点所强连接的先序顶点，如果被其他顶点强连接，则将其他这些顶点标记为“不可信的”；

[0029] 再将强连接被标记为“不可信的”顶点的顶点标记为“不可信的”，直至不再有顶点强连接被标记为“不可信的”顶点；

[0030] 最后删除所有被标记为“不可信的”顶点，及有关的边。

[0031] 基于相同的发明构思，本发明提供的一种基于有向无环图的支持合约的分布式账本共识系统，所述分布式账本的创世顶点不连接有向无环图的任意顶点，第二个添加到有
向无环图的顶点必须连接创世顶点；从第三个添加到有向无环图的顶点开始，顶点类型包
括合约定义顶点和合约交易顶点；所述系统包括多个网络节点，所述网络节点设有顶点添
加模块，用于在定义一个新的智能合约时，或者根据现有的智能合约及其状态发起一笔新
的交易时，向有向无环图中添加顶点；所述顶点添加模块包括：

[0032] 新顶点赋权值单元，用于为即将添加到有向无环图中的新顶点赋权值，所述权值为正整数；

[0033] 现有节点连接单元，用于预选择零个或一个可被强连接的顶点，预选择一个或多个可被弱连接的顶点，然后将新顶点强连接到预选择的可被强连接的顶点上，并弱连接到
所有预选择的可被弱连接的顶点上；所述强连接满足新顶点与预选择的顶点含有相同的合
约编号，所述弱连接满足新顶点与预选择的顶点含有不同的合约编号；

[0034] 权重更新单元，用于对有向无环图中顶点的权值进行更新；

[0035] 以及同步单元，用于将账本同步到网络中的其他网络节点。

[0036] 进一步地，所述网络节点还设有分叉剪枝模块，用于对有向无环图进行分叉剪枝；包括：

[0037] 可信顶点标记单元，用于在新顶点添加完毕后，扫描该顶点所属的强连接链与弱连接链，将链上所有权值小于等于可信阈值的、且未标记为“可信的”顶点，标记为“可信
的”；其中顶点v所属的弱连接链指被顶点v弱连接的顶点所属的强连接链的中所有顶点的
集合；

[0038] 直接不可信顶点标记单元，用于在被新标记为“可信的”顶点所强连接的先序顶点，如果被其他顶点强连接，则将其他这些顶点标记为“不可信的”；

[0039] 间接不可信顶点标记单元，用于将强连接被标记为“不可信的”顶点的顶点标记为“不可信的”，直至不再有顶点强连接被标记为“不可信的”顶点；

[0040] 以及剪枝单元，用于删除所有被标记为“不可信的”顶点，及有关的边。

[0041] 基于相同的发明构思，本发明提供的一种计算机系统，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述计算机程序被加载至处理器时实现所
述的基于有向无环图的支持合约的分布式账本共识方法。

[0042] 有益效果：本发明通过在有向无环图中引入“合约编号”和“强连接”等概念，并添加一些约束条件，形成一种新型基于有向无环图的分布式账本数据结构，使得在具有相同
合约编号的顶点之间具备了全序关系，从而实现了基于有向无环图的分布式账本对智能合
约的支持。此外，本发明提供的顶点添加算法和分叉剪枝算法解决了因网络延迟、恶意攻击
等原因导致的异常现象，为分布式账本的安全性和可靠性提供了保证。

附图说明

[0043] 图1为本发明实施例的共识流程图。

[0044] 图2为本发明实施例中基于有向无环图的分布式账本数据结构示意图。

具体实施方式

[0045] 下面结合附图和具体实施例对本发明做进一步说明。

[0046] 本发明设计了基于有向无环图的去中心化分布式账本数据结构，通过引入强连接、弱连接等关系实现有向无环图内的局部全序关系，从而支持智能合约。具体而言，该基
于有向无环图的分布式账本数据结构，包括如下内容：

[0047] (1)创世顶点不连接有向无环图的任意顶点；

[0048] (2)第二个添加到有向无环图的顶点必须连接创世顶点；

[0049] (3)从第三个添加到有向无环图的顶点开始，顶点必须至少连接两个有向无环图中已有的顶点；

[0050] (4)从第三个添加到有向无环图的顶点开始，顶点类型可选以下两种类型其一：合约定义顶点、合约交易顶点；

[0051] (5)第二个添加到有向无环图的顶点类型必须为合约定义顶点；

[0052] (6)每个顶点含两个编号，一个是合约编号，一个是交易编号，且每个交易编号均不相同；

[0053] (7)当添加到有向无环图的顶点的类型为“合约定义顶点”时，顶点的合约编号不得与有向无环图中任意其他顶点的合约编号相同；

[0054] (8)当添加到有向无环图的顶点的类型为“合约交易顶点”时，顶点的合约编号必须属于在有向无环图中所有顶点的合约编号构成的集合；

[0055] (9)当添加到有向无环图的顶点的类型为“合约交易顶点”时，顶点必须强连接有向无环图中的一个顶点，并弱连接有向无环图中至少一个顶点。

[0056] 其中，“创世顶点”的含义是，第一个添加到有向无环图的顶点。

[0057] 其中，“顶点A连接顶点B”的含义是在有向无环图中添加一条由顶点A指向顶点B的有向边，然后对顶点B包含的业务数据执行哈希计算，将计算后的结果保存到顶点A中。

[0058] 其中，“顶点A强连接顶点B”的含义是顶点A连接顶点B，且满足顶点A与顶点B含相同的合约编号。

[0059] 其中，“顶点A弱连接顶点B”的含义是顶点A连接顶点B，且满足顶点A与顶点B含不同的合约编号。

[0060] 基于上述分布式账本数据结构，本发明实施例提供的还提供分布式账本的共识方法如图1所示，主要包括顶点添加和分叉剪枝两个部分。其中，顶点添加和分叉剪枝是由网
络节点基于所述数据结构执行的。

[0061] 由于每个顶点的交易编号在有向无环图中是唯一的，因此下文以“顶点X”作为“交易编号为X的顶点”的简要表述。

[0062] 基于有向无环图的去中心化分布式账本数据结构示意图如图2所示。去中心化分布式账本是由若干参与该账本的网络节点(以下简称“网络节点”)所同步的。任意网络节点
在向账本中添加新顶点(即定义新合约，或根据合约发起交易)时，必须在其本地执行本发
明提供的共识方法，然后将账本同步到其他网络节点。该账本的起始是创世顶点(即顶点
0)，该顶点由创建者网络节点创建并同步到其他网络节点。创建者网络节点可以在创世顶
init
点中可以定义该账本的参数以初始化整个账本，如新增顶点的初始权值2 ，顶点可信的
阈值th，用于选择待弱连接的顶点的合约编号的随机函数Ran(ScNo,VNo,Nonce)和最大弱
连接数k等。为了与后继的合约定义顶点与合约交易顶点作区分，创世顶点的合约编号、交
init
易编号与权值均为0。图2展示了一个新增顶点的初始权值2 为32，顶点可信的阈值th为
2，最大弱连接数k为3的账本。

[0063] 账本的第一个智能合约由某个网络节点在账本的第二个顶点(顶点1)中定义，且该顶点必须弱连接创世顶点。从第三个顶点起，顶点类型可以是：合约定义顶点，网络节点
在定义一个新的智能合约时添加；合约交易顶点，网络节点根据现有的智能合约及其状态
发起一笔新的交易，以改变对应智能合约状态时添加。为了区别不同的智能合约，以合约编
号指代不同的智能合约，因此要求合约定义顶点的合约编号必须互不相同。为了确保某笔
交易是建立在一个现有的智能合约基础上，该合约交易顶点的合约编号必须与该合约定义
顶点的合约编号一致。图2中展示了一个由19个顶点(其中2个被删除)构成的账本。

[0064] 类似于区块链，每个顶点都必须被若干后继顶点的直接或间接的连接(证明)才可以被认为该顶点所代表的合约定义或者合约交易是可信的。在添加新的合约定义顶点和合
约交易顶点时，网络节点都可以证明与自己无关的(合约编号不同的)顶点所代表的合约定
义或合约交易是正确的，即通过计算被证明的顶点的哈希值，并将该值添加到新顶点中，从
而将新顶点与该被证明的顶点弱连接。在添加合约交易顶点时，网络节点可以且必须证明
与自己有关的(合并编号相同的)智能合约的定义(合约定义顶点)与先序状态(先序合约交
易顶点)是正确的，即通过计算与新顶点同合约编号的最新现有顶点的哈希值，并将该值添
加到新顶点中，从而将新顶点与该现有顶点强连接。图2展示了一个含5个智能合约、13个合
约交易(其中2个合约交易顶点被删除)的账本。

[0065] 为了规范在账本中添加顶点的方法，从而使网络节点在同步新顶点时，新顶点具备可验证性，本发明实施例提供的基于有向无环图的支持合约的分布式账本共识方法中，
顶点添加步骤，包括：

[0066] (1)为新顶点赋权值：网络节点在有向无环图中添加新顶点时，为该新顶点赋一个固定的权值，除对创世顶点的权值赋为0以外，其余顶点的权值均为正整数；

[0067] (2)连接现有顶点：网络节点根据顶点选择策略预选择零个或一个可被强连接的顶点，预选择一个或多个可被弱连接的顶点，然后将新顶点强连接到预选择的可被强连接
的顶点上，并弱连接到所有预选泽的可被弱连接的顶点上；

[0068] (3)权值更新：网络节点根据权值更新算法修改有向无环图中所有顶点的权值。

[0069] 根据步骤(1)，为新顶点赋的权值是一个固定值。图2显示最新的顶点3具有权值32，表明对于图2展示的账本，网络节点必须向新顶点赋权值32。

[0070] 步骤(2)中，顶点选择策略是：如果新顶点的类型是合约定义顶点，则不选择可被强连接的顶点，且预选择至少两个可被弱连接的顶点；如果新顶点类型是合约交易顶点，则
预选择一个可被强连接的顶点，预选择至少一个可被弱连接的顶点。

[0071] 预选择可被强连接的顶点时，选择有向无环图中所有可被强连接的顶点集合中最新的一个顶点。

[0072] 预选择可被弱连接的顶点包含如下步骤：

[0073] (a)为创世顶点添加一个函数Ran(ScNo,VNo,Nonce)，如果创世顶点中已存在一个函数，则跳过该步骤；

[0074] 其中，Ran(ScNo,VNo,Nonce)是一个以ScNo、VNo和Nonce为自变量生成伪随机数的函数，其值域为 其中，ScNo为合约编号，VNo为交易编号，Nonce为
一个自然数，SCMAX为该有向无环图所允许的最大合约编号值。

[0075] (b)将新顶点的ScNo值和VNo值代入步骤(1)函数，令Nonce分别为1,2,3,……,n，从函数获取输出值a1,a2,a3,…,an；

[0076] (c)选取前k个步骤(b)中输出值，其中，每个输出值均在由有向无环图中已存在的合约编号构成的集合里；

[0077] (d)对每个由步骤(c)选取的输出值，选择一个以该输出值为合约编号的顶点，且该顶点是在所有以该输出值为合约编号的顶点中最新添加到有向无环图的，至多选择k个
顶点作为预选择可被弱连接的顶点。

[0078] 根据步骤(2)，除第二个顶点(顶点1)以外的合约定义顶点必须弱连接至少两个顶点，合约交易顶点必须强连接一个顶点并弱连接至少一个顶点。图2显示合约定义顶点12弱
连接了顶点10、顶点5和顶点0；合约交易顶点70强连接了顶点12并弱连接了顶点15。

[0079] 步骤(3)的权值更新算法，即：

[0080] (a)为新顶点赋权值2init；

[0081] (b)新顶点所属的强连接链包含的除该新顶点以外的每个顶点的权值w修改为

[0082]

[0083] 其中，th为一个正整数；

[0084] (c)新顶点所属的弱连接链包含的除该新顶点以外的每个顶点的权值w修改为

[0085]

[0086] 其中，th为一个正整数。

[0087] 其中，“顶点vn所属的强连接链”的含义是由以下步骤产生的集合S：

[0088] (a)将顶点vn添加到集合S中；

[0089] (b)如果存在顶点vn‑1，顶点vn强连接了顶点vn‑1，则将顶点vn‑1添加到集合S中，然后令n自减1；

[0090] (c)重复步骤(b)，直至不存在一个顶点被集合S中的任何元素强连接。

[0091] 其中，“顶点v所属的弱连接链”的含义是由以下步骤产生的集合W：

[0092] (a)如果顶点v弱连接了顶点v1，v2，v3，…，vn，则将顶点v，v1，v2，v3，…，vn各自所属的强连接链中的所有元素添加到集合W中。

[0093] 对于图2展示的账本(2init＝32，th＝2，k＝3)，若某个网络节点试图将一个新顶点3(合约编号为3)添加到其中，首先需要为顶点3设置权值32，然后将其强连接到顶点77。根
据步骤(2)中顶点选择策略中的弱连接顶点的预选择方法，再选择1至3个顶点进行弱连接。
该网络节点选择了顶点25和顶点98这两个顶点，将顶点3与它们进行弱连接。连接完成后，
网络节点还需对所有涉及到的顶点进行权值更新：对于顶点3所属的强连接链中的顶点77、
74、84、70、12，权值从32、16、8、4、2更新为16、8、4、2、2，对于顶点3所属的弱连接链中的顶点
25、44、8、31、10、1、98，权值从35、19、11、7、2、2、32更新为36、20、12、0、2、2、33。

[0094] 对于顶点70、12、10、1，由于权值均为2，已经小于等于阈值th，因此在权值更新过m
程它们的权值保持不变；而对于顶点31，权值w＝7，且 (w+1)＝2 ，因而更新后的权
值为0，同样小于等于阈值th。对于一个顶点，随着被直接、间接强连接的次数增多，类似于
区块链，其可信程度越来越高，其权值最终会在有限次数内稳定在阈值或阈值以下；一个顶
点被直接、间接弱连接的次数增多，同样可以表明其可信程度越来越高，其权值同样会在有
限次数内稳定在阈值或阈值以下。因此，可以认为权值一旦小于等于阈值，该顶点就具备了
相当高的可信程度，使其能被大多网络节点所共同认可(即共识)，从而为分叉剪枝算法提
供铺垫。

[0095] 由于现实中存在的网络延迟、黑客攻击等原因，网络节点并不能总是将一个合约交易顶点与最新的与其合约编号相同的顶点强连接。举例来说，如图2，如果网络节点间的
延迟为1秒，在1秒内有两个不同的网络节点向各自的本地账本各添加了顶点31和顶点15
(合约编号均为1)。从整个分布式账本网络的全局来看，这两个顶点的添加时间总是有先有
后的，但对于这两个网络节点来说，由于两个顶点添加间隔时间太短，在向各自的本地账本
添加顶点时，合约编号为1的最新顶点都是10，从而造成了对规则“一个合约交易顶点必须
强连接最新的与其合约编号相同的顶点”的破坏。如何取舍顶点31和顶点15是分叉剪枝算
法所要做的。

[0096] 本发明实施例提供的基于有向无环图的支持合约的分布式账本共识方法中，分叉剪枝步骤包括：

[0097] (1)标记可信顶点：在新顶点添加完毕后，扫描该顶点所属的强连接链与弱连接链，将其中所有权值小于等于th的、且未标记为“可信的”顶点，标记为“可信的”；

[0098] (2)标记直接不可信顶点：在步骤(1)中被新标记为“可信的”顶点所强连接的先序顶点，如果被其他顶点强连接，则将其他这些顶点标记为“不可信的”；

[0099] (3)标记间接不可信顶点：将强连接被标记为“不可信的”顶点的顶点标记为“不可信的”，直至不再有顶点强连接被标记为“不可信的”顶点；

[0100] (4)分叉剪枝：删除所有被标记为“不可信的”顶点，及有关的边。

[0101] 其中，“分叉”的含义是，由于网络延迟、恶意攻击等现实原因，一个或多个类型为“合约交易顶点”的新顶点未强连接到最新的可被强连接的顶点，导致多个顶点强连接到同
一个顶点的现象。

[0102] 其中，“剪枝”的含义是，将部分顶点和与这些顶点有关的边删除，使得含相同合约编号的顶点依次连接构成一条链。

[0103] 如图2所示，在顶点3添加之前，顶点10被顶点31和顶点15强连接，产生了分叉，相关的顶点25、44、8、31、16、15的权值分别为35、19、11、7、32、16。顶点3添加完毕后，权值更新
为36、20、12、0、32、16。由于顶点31相对于顶点15“率先”进入可信区间(即权值小于等于阈
值)，因而顶点31被认为比顶点15更可信。根据分叉剪枝算法，将顶点31及其后继顶点暂时
保留，网络节点需要将顶点15及其后继顶点16作为不可信顶点从账本中删除，从而实现分
叉剪枝。

[0104] 基于相同的发明构思，本发明实施例公开的一种基于有向无环图的支持合约的分布式账本共识系统，系统中包括多个网络节点，所述网络节点设有顶点添加模块，用于在定
义一个新的智能合约时，或者根据现有的智能合约及其状态发起一笔新的交易时，向有向
无环图中添加顶点；所述顶点添加模块包括：

[0105] 新顶点赋权值单元，用于为即将添加到有向无环图中的新顶点赋权值，所述权值为正整数；现有节点连接单元，用于根据顶点选择策略预选择零个或一个可被强连接的顶
点，预选择一个或多个可被弱连接的顶点，然后将新顶点强连接到预选择的可被强连接的
顶点上，并弱连接到所有预选择的可被弱连接的顶点上；所述强连接满足新顶点与预选择
的顶点含有相同的合约编号，所述弱连接满足新顶点与预选择的顶点含有不同的合约编
号；权重更新单元，用于对有向无环图中顶点的权值进行更新；以及同步单元，用于将账本
同步到网络中的其他网络节点。

[0106] 网络节点还设有分叉剪枝模块，用于对有向无环图进行分叉剪枝；包括：可信顶点标记单元，用于在新顶点添加完毕后，扫描该顶点所属的强连接链与弱连接链，将链上所有
权值小于等于可信阈值的、且未标记为“可信的”顶点，标记为“可信的”；直接不可信顶点标
记单元，用于在被新标记为“可信的”顶点所强连接的先序顶点，如果被其他顶点强连接，则
将其他这些顶点标记为“不可信的”；间接不可信顶点标记单元，用于将强连接被标记为“不
可信的”顶点的顶点标记为“不可信的”，直至不再有顶点强连接被标记为“不可信的”顶点；
以及剪枝单元，用于删除所有被标记为“不可信的”顶点，及有关的边。

[0107] 基于相同的发明构思，本发明实施例公开的一种计算机系统，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，该计算机程序被加载至处理器时实
现所述的基于有向无环图的支持合约的分布式账本共识方法。