基于有向无环图的高效区块链共识算法

王壹铭, 初剑峰, 王永军, 陈彦东

(1. 吉林大学 计算机科学与技术学院, 长春 130012； 2. 长春市公安局 网安支队, 长春 130051； 3. 吉林大学第二医院 信息中心, 长春 130041)

区块链技术[1]最早作为比特币的底层技术被提出, 具有去中心化及不可篡改等特性. 但由于实现区块链技术的工作量证明(proof of work, PoW)算法对计算资源要求过高, 导致浪费大量的计算资源, 且吞吐量低, 因此并不实用. PoW算法从生成交易单到出块的时间约需10 min, 一个交易的确认需后续连续6个区块附着在该区块后, 即一个区块需约1 h才能被确认放置在主链上. 而且PoW共识算法的区块链系统每秒只能处理7笔交易, 导致区块链技术不能用于物联网或金融系统. 针对该问题, 以太坊平台提出了一种股权证明(proof of stake, PoS)共识算法, 但该算法存在其他问题, 如出块速度不稳定导致分叉的出现及持币不出块等[2]. 文献[3]尝试通过Gossip协议与实用拜占庭容错(practical Byzantine fault tolerance, PBFT)算法相结合的方式改进区块链共识算法. 文献[4]提出基于零行列式策略[5]解决矿工挖矿问题, 对节点的策略选择进行优化, 促进节点与系统获得更高的收益[6-7], 该算法虽能解决PoW算法中的算力浪费问题, 但无法解决区块链技术不能在高业务量系统中快速处理交易块的问题. 事实上, 在比特币的PoW共识算法中, 目标Hash值要求以42位0开头, 平均需要242次尝试, 从而导致了比特币的专用集成电路(application specific integrated circuit, ASIC)问题, 即大量设备被设计用于做矿机的芯片, 导致巨大的计算硬件浪费[8]. 由于现行区块链技术存在的诸多瓶颈, 导致区块链技术并不适用于目前的物联网或者金融系统. 本文通过改变区块链的数据存储结构并使数据存储结构成为共识算法的一部分, 实现区块链高效处理大量交易的目标.

1 预备知识

在区块链的3种经典共识算法PoW中, 能实现去中心化的区块链中心目标, 但需消耗大量的硬件资源, 而PoS共识算法为了解决该问题提出了采用股权证明机制, 但该共识算法可能导致拥有权益的用户有过大的权利而影响区块链工作. PoS共识算法在一定程度上是基于PBFT算法设计的, PBFT算法能避免PoW共识算法中的算力浪费问题, 但该算法达成共识的时间较长, 不利于区块链项目在短时间内处理大量交易, 这是由传统的链式结构导致的. 因此本文提出使用有向无环图结构取代传统的链式结构, 基于这种数据结构的共识算法能更好地在短时间内处理大量交易且不必占用过多的计算资源. 因此， 该算法适用于医疗大数据服务系统[9]或车载自组网系统[10].

1.1 工作量证明算法

图1 常见的区块链结构Fig.1 Normal blockchain structure

PoW算法的核心思想是通过分布式节点的算力竞争保证数据的一致性和共识的安全性. 其中每个区块的结构中都包含了上一个区块的Hash值, 从而形成链状结构, 交易被以Merkle树的形式组织. 图1为区块链常见的区块结构, 比特币项目的区块就采用了这种结构. 其中, Nonce为一个随机数, 矿工Bob在收集交易单并打成块后, 对区块头部进行Hash运算, 只有在计算结果开头0的位数满足当前区块链要求且当前没有其他矿工比Bob的计算更快时, Bob才可将该区块发布至区块链网络中, 其他矿工则负责同步这一区块, 此时Bob需等待后续的6个区块生成, 如果这6个区块附着在该区块后, 则该区块确认添加至区块链中, 矿工Bob获得奖励.

1.2 权益证明算法

以太坊在前期均采用PoW共识算法初始积累权益, 而后期以太坊则转向PoS共识算法, 通过权益证明机制缩短达成共识的时间, 并在一定程度上解决了PoW算力浪费的问题, 因此比特币后的许多区块链项目均采用了PoS共识算法. 在PoS共识机制中, 由系统中具有最高权益而非最高算力的节点获得记账权, 其中权益体现为节点对特定数量货币的所有权, 成为币龄或币天数(coin days)[11]. 在采用PoS共识机制的区块链项目中, 矿工所获得的收益奖励主要来自于用户交易.

采用PoS共识算法的区块链项目前期需使用PoW共识算法公平分配权益, 在一定程度上仍会导致算力浪费, 且PoS共识算法并不能解决区块链技术在处理大量交易时效率较低的问题, 从而导致基于PoS共识算法的区块链技术不能应用在物联网或金融系统中.

1.3 实用拜占庭算法

实用拜占庭算法[12-13]用于解决分布式系统中各节点达成共识的问题, 当系统中错误节点少于1/3时系统可达成共识. 该算法分为如下3个阶段.

1) pre-prepare: 主节点向所有备份节点发送准备消息, 此时节点状态为pre-prepare;

2) prepare: 包括主节点在内的所有备份节点在收到准备消息后, 确定无误, 向外广播消息, 并且进入prepare阶段；

3) commit: 当收到若干来自其他副本的prepare信息后即可进入commit阶段.

PBFT算法相对PoW算法计算简单, 不需要消耗大量计算资源, 但如果在大规模的区块链网络中使用, 其通信量会急速上升导致出现系统瓶颈[14]. PBFT算法并不能解决区块链处理区块时的效率低问题[15].

2 区块链数据结构设计

2.1 基本区块结构

图2为一个基于ID分类的有向无环图结构. 该数据结构的主要功能是建立高效的生成区块机制. 基本区块结构由ID块、 交易块和起始块组成. 在该区块链系统中, 每个用户都可以拥有多重身份, 用户既可作为交易方寻求与他人交易, 也可作为矿工帮助其他用户认证交易块. 其中, 每个用户都拥有一个独立的ID, 当用户注册并进入区块链系统时即产生一个与该ID相关的ID块, 交易块附于相对应的ID块后, 负责记录每笔交易的内容. 而起始块是所有ID块的父节点. 通过基于ID分类的有向无环图结构可实现所有矿工能在同一时间生成区块而不必等待其他矿工打包区块, 该机制从根本上解决了区块链无法应用于短时间内处理大量交易的问题. 图2中箭头表示区块的先后附属关系, 在每个ID块的后续区块都应根据双方的交易笔数有序地附着在区块后, 标号为0的区块即为起始块, 其为所有ID块的父节点, 其中A/B/C/D为ID块,BA为用户ID为B的用户与ID为A的用户产生交易的交易链起始区块(区块结构为交易块, 但交易内容为空),BA1为B与A之间的第一笔交易. 图2中的4位用户可同时开展交易并等待矿工签名完成即可确认区块, 不需像PoW类共识算法等待6个区块才能确认区块. 通过这种基于ID分类的有向无环图结构能有效提升区块链项目处理交易的效率.

2.2 ID块

ID块的内容包括身份编号、 公钥和数字签名, 其中ID编号为有向无环图中交易块分类的标准, 其子节点记录的交易块内容为该ID拥有者与其他用户交易的记录. 同时, ID块中存储的内容可用于证明该ID拥有者的身份, 并能轻松被他人验证.

2.3 交易块

系统中的每个用户拥有一个公开的包含一系列交易的区块链, 交易块内容包括交易块身份编号、 交易发起方身份编号、 交易发起方数字签名、 交易接收方身份编号、 交易接收方数字签名、 前一区块身份编号、 前一区块Hash值、 Merkle树根节点值、 前一区块矿工签名列表、 交易内容、 剩余签名次数、 本区块矿工签名列表、 矿工奖励列表、 区块完成时间. 其中交易块ID编号表明交易块所处区块链中的位置, 交易双方签名用于确保交易内容为真, 前一区块信息用于矿工比对交易块位置, Merkle树记录当前区块矿工签名列表, 但只保留根节点值(如果同时有两组矿工完成区块出块, 则拥有更小的Merkle树根节点值的区块完成区块出块操作), 避免了不同矿工之间不能公平获得挖矿机会的问题, 如果剩余签名次数为0, 则表明该交易块正处于完成矿工签署阶段等待被同步至区块链网络中, 或该区块已经签署失败, 此时需交易发起方重新组织区块发布至区块链网络中等待签署.

2.4 起始块

起始块是所有ID块的父节点, 本身不记录信息, 用于维持整个区块链的有向无环图结构.

3 共识算法设计

3.1 交易块生成算法

交易块生成算法主要分为三阶段: 第一阶段由交易双方生成交易单并完成创建起始交易块, 对交易块的交易内容进行签名以保证交易块的合法性; 第二阶段即矿工验证区块并签名阶段, 矿工签名完成即表示完成对交易块内容合法性的确认； 第三阶段则是最后一位参与签名的矿工将第二阶段完成的交易块广播至整个区块链网络, 所有节点同步新的区块, 至此交易成功并被记录至区块链中.

在第一阶段中, 交易双方需要协商并完成对交易内容的签名, 完成签名后, 由交易发起方创建区块, 完成交易区块的主体结构后将交易块广播至区块链网络中, 等待被矿工签名并验证合法性, 最终生成的区块需要被附着到交易发起方所在ID区块的链上.

在第二阶段中, 矿工需要完成对第一阶段生成的初始交易块的签名验证工作：

1) 矿工端首先检查rst字段, 如果该字段值为0, 则该区块(T-Block)被拒绝并广播给网络中的其他矿工, 这一区块在该矿工端的交易块生成算法终止, 表示为

(1)

其中:m为区块信息;T-Block为区块; Forward( )函数表示广播区块;Tpbml表示区块进行第二步操作; pbml为前一区块的矿工签名列表;

2) 检查前一区块矿工签名列表, 如果该矿工的ID出现在此列表中, 则说明该矿工已参与过该区块的签名, 此时区块应该被拒绝并广播给网络中的其他矿工, 这一区块在该矿工端的交易块生成算法终止;

3) 判断已签名矿工ID(p)是否出现在前一矿工签名列表中, Serch( )函数表示如果发现存在已签名矿工ID与前一矿工签名列表中的矿工ID匹配成功, 则说明存在矿工违反操作规则的情况, 区块被拒绝并广播给网络中的其他矿工, 这一区块在该矿工端的交易块生成算法终止, 表示为

Tcheck=Search(msl,pbml,p),

(2)

其中msl为本区块矿工签名列表;

4) rst值自减1, 表示为

rst=rst-1;

(3)

5) 通过区块中交易双方的公钥验证双方签名是否合法, 如果签名合法性验证失败, 则矿工拒绝签名并将区块广播给网络中的其他矿工, 这一区块在该矿工端的交易块生成算法终止, 表示为

Tsignature=Ω(CheckSign(T-Block,ga,Pub-keya),CheckSign(T-Block,gb,Pub-keyb)),

(4)

其中:Ω表示对双方签名验证结果的校验函数; CheckSign( )函数表示对矿工签名合法性验证;ga,gb分别为交易双方数字签名; Pub-keya,Pub-keyb分别为交易双方公钥;

6) 检查区块是否被放在正确的位置, 如果检查失败, 则拒绝区块并将区块广播给网络中的其他矿工, 这一区块在该矿工端的交易块生成算法终止;

7) 依次检查矿工签名列表中其他矿工的签名是否合法, 如果任意一个签名验证失败, 则该区块签名失败, 拒绝该区块并将其广播给网络中的其他矿工, 这一区块在该矿工端的交易块生成算法终止;

8) 矿工对该区块进行签名, 使用椭圆曲线数字签名(ECDSA)方式通过区块m、 随机数r及私钥Keyprivate生成数字签名(m,g), 表示为

Tsign=ECDSA(m,r,keyprivate)=(m,g);

(5)

9) 矿工需确认自己是否为最后一位参与签名的矿工, 即检查待签名人数(rst)字段, 如果rst≠0, 则该矿工不是最后一位参与签名的矿工, 该区块则广播给网络中的其他矿工, 该矿工对这一区块的工作完成, 表示为

(6)

10) 若该矿工为最后一位参与签名的矿工, 则需检查签名失败次数是否符合设计要求(不能多于2次), 如果签名失败次数超过2次, 则宣告该区块签名失败, 此时应通知交易发起方重新组织区块, 表示为

(7)

q=10-count(msl),

(8)

其中: msl为矿工奖励列表中的矿工ID; count( )函数用于统计数量;q表示失败次数;

11) 最后一位矿工创建一个奖励列表以标明每位参与签名矿工的奖励, 当他完成了该项工作时, 区块正式生成并添加至区块链中, 每位区块链中的全部节点记录这一区块.

在第三阶段中, 已经签署完成的区块由最后一位参与签名的矿工广播至区块链网络中, 每位参与该区块签名的矿工此时得到奖励, 如果最后一位矿工在奖励发放部分作弊, 则每位参与签名的矿工都可向区块链网络中广播最后一位矿工作弊的信息, 如果超过1/3的参与该区块签名的矿工发布该信息, 则该区块签名过程中作弊矿工的奖励作废, 并由参与签名前两位矿工生成交易块, 将作弊矿工的失信信息作为交易内容存储于区块链中. 由于本系统采用有向无环图结构, 记录矿工失信信息并不影响后续区块的生成, 因此不会对交易块的高效处理产生影响.

3.2 算法分析

3.2.1 有向无环图结构 该算法中采用的数据结构有别于有向无环图结构, 是在有向无环图的基础上根据用户ID再进行分类. 这种数据结构能保证所有用户均可在同一时间创建起始区块, 而不必如传统区块链那样等待其他区块生成完毕后才获得机会生成区块, 并且在生成区块后, 不需要如PoW共识算法那样需连续6个区块的确认才能保证区块成功添加至区块链系统中.

3.2.2 奖励机制 在PoW类型的区块链共识算法中, 奖励机制是基于矿工挖矿的速度决定奖励值, 只有计算最快的那个矿工可获得奖励, 而其他参与计算的矿工则浪费了算力资源. 本文算法中区块生成后参与签名的矿工都可获得奖励, 且不以签名的先后次序决定奖励值, 从而避免了PoW类型的区块链共识算法中由于矿工竞争而导致的资源浪费.

3.2.3 安全性 由于算法中同一组矿工不能在1 d内一起签署超过一个区块, 因此当恶意矿工控制多个用户时也不会影响区块链系统的整体运行. 该机制同时也保证了每位矿工挖矿的公平性, 不同于PoW类型的区块链共识算法中拥有更多计算能力的矿工可获得签署区块的权利, 在本文算法区块链系统中, 所有活跃的矿工均可公平地获得签署区块的权利.

3.2.4 出块效率分析 不同于PoW类型共识算法, 本文算法中参与签名的矿工只在计算Merkle树时会占用计算资源, 显著低于PoW共识算法, 且不同于PoS共识算法中根据用户具有多少权益决定出块权利, 因此本文算法减少了投票的步骤, 同时保证了矿工参与挖矿过程的公平性.

综上所述, 针对传统区块链算法存在效率低和大量资源浪费的问题, 本文提出了一种将区块链设计成有向无环图结构, 并通过设计区块生成共识算法将矿工签名与区块存储结构相结合的算法, 解决了现存区块链项目在面对大量交易时效率较低的问题, 同时节省了计算资源. 该算法能快速处理大量交易, 并支持全体用户在同一时间进行交易同时生成区块, 解决了现存区块链项目中矿工由于等待其他区块生成所需耗费更多时间的问题. 不需要采用PoS类算法的区块链项目通过选举产生记录区块权力的方法, 因此本文算法比PoS类算法能更公平且高效地生成区块.