公平且稳定的最小值证明共识机制

余本国，弓世明，庞晓琼，聂梦飞，陈文俊，3，杨 婷

1.中北大学 软件学院，太原030051

2.中北大学 大数据学院，太原030051

3.中国人民银行 太原中心支行，太原030001

1 引言

近年来，随着比特币[1]等数字货币的兴起，其底层技术——区块链也逐渐进入人们的视野。区块链的去中心化、不可篡改、可追溯等特性，使它很快在其他方面也展现出惊人的潜力，诸如供应链管理、个人信息管理、物联网、信用征集等[2-5]。随着区块链技术的快速发展，越来越多的项目落地，区块链的应用领域不断地被探索扩张。

区块链是一个分布式的链式数据库，它由加入该区块链系统的所有在线全节点共同维护，这些全节点通过P2P 网络连接在一起，彼此不需要提前取得相互的信任，其中一个或多个节点提议一个数据区块后，所有节点通过共识机制[6-9]共同参与和认证，对这个数据区块一致达成协议[10]，若一致通过则将该数据区块添加到区块链上。由此可见，共识机制是区块链技术中的核心要素，尤其是对于公有链来说，共识机制是区块链的灵魂。目前，应用于公有链的共识机制主要有工作量证明（Proof of Work，PoW）[1]、权益证明（Proof of Stake，PoS）[11]以及授权股份证明（Delegated Proof-of-Stake，DPoS）[12]等。

2008年10月，中本聪发表了《比特币一种点对点电子现金系统》[1]，其运用的是PoW 共识机制。PoW 是最早且迄今为止最安全可靠的公有链共识机制，其核心思想是通过各个全节点（即矿工）的算力相互竞争来解决同一个求解复杂但是验证容易的SHA256数学难题（即挖矿），最快解出该难题的矿工所打包的区块即本轮共识出的合法区块[13]。然而此过程中，矿工求解该难题除了为了争夺打包合法区块所能获得的比特币奖励之外，所消耗的算力并没有为社会创造实际价值，而且对于算力强大的矿工有利，对只有平庸的算力的矿工来说不公平，造成了算力中心化的现象。并且在多个矿工算力较大且相差不大的情况下，会经常发生临时分叉的现象。

2011年7月，PoS共识机制被Quantum Mechanic首次在比特币论坛中提出[11]。PoS中各个矿工的挖矿难度与其权益成反比，其中权益为持币数量与持币天数的乘积，每挖矿成功后该矿工的权益清零。虽然PoS不会造成算力浪费和算力中心化，但是却造成了权益中心化[13]。并且在多个矿工权益较大且相差不大的情况下，会经常发生临时分叉的现象。

2013 年8 月，比特股（Bitshares）项目提出了新的共识机制——授权股份证明机制（Delegated Proof-of-Stake，DPoS）[12]。DPoS共识的基本思路类似于“董事会决策”，即系统中每个节点可以将其持有的股份权益作为选票授予一个代表，获得票数最多且愿意成为代表的前N 个节点将进入“董事会”，按照既定的时间表轮流对交易进行打包结算，并且签署（即生产）新区块[13]。其虽然降低了算力浪费，提高了共识机制的速度和稳定性，但是持票人参与投票选举的积极性并不高，造成的权益中心化会越来越大。

综上所述，PoW 会造成算力浪费和算力中心化，PoS和DPoS会造成权益中心化。为了解决现有应用于公有链共识机制中浪费算力、去中心化程度不高的缺点，同时保证共识机制的稳定性，本文提出了新的基于哈希随机选主的共识机制PoM。PoM 利用哈希算法的单向性和强抗碰撞性随机选取合法区块，使得共识过程更公平、稳定。

2 准备知识

2.1 区块链

区块链是由一个个的数据区块连接而成的数据库，每一个区块包含区块头和区块体两个组成部分。区块体中以默克尔树的形式存储着需要记录的数据，生成的默克尔树根则存在区块头中以保证区块头和区块体是一体的。

以比特币为例，其区块链结构如图1 所示，区块头中存有版本号、前一个区块的哈希值、时间戳、难度值和nonce。其中，前一个区块的哈希值可以用来连接区块以此使一个个的区块连接为链式的区块链。时间戳记录了该区块生成的时间，由于后一个区块生成的时间一定是在前一个区块之后，所以时间戳可以用来判断区块的合法性。难度值和nonce用于进行共识。

图1 比特币区块链结构示意图

图2 PoM区块链结构示意图

2.2 哈希算法

SHA256 是一种哈希算法，在比特币区块链中应用广泛[1]。哈希算法是一种可以将任意长度的消息压缩到某一固定长度的消息摘要的函数，而且非常相似的两个消息，经过哈希运算后得到的消息摘要很可能相差很大。如果已知一个经过哈希运算后得到的消息摘要，想要求得消息本身是非常困难的，而已知一个消息，想要求得该消息经过哈希运算后的消息摘要是非常简单的。

由于哈希算法的这些特点，在区块链中，哈希算法不仅运用在区块体的默克尔树中和区块与区块的链接中，在共识机制中也有很大的作用。

3 PoM

本章主要介绍本文提出的一种新的共识机制PoM。PoM不仅有较高的去中心化程度，还有较高的稳定性。

在使用PoM 共识的区块链网络中，每个矿工都会实时更新全网矿工的个数，并将矿工的个数记为n，由于每时每刻都有可能有新的矿工加入也有旧的矿工退出，所以n 的值虽然是动态变化的但一般不会出现骤增骤减的情况。

3.1 PoM的区块结构

PoM的区块结构如图2所示，其包含有区块头和区块体两部分，区块体利用默克尔树的结构存储信息，区块头中包含版本号、前一个区块的哈希值（perHash）、默克尔树根、时间戳、打包该区块的矿工的公钥（pk）、minimum。minimum的计算如等式（1）所示：

3.2 PoM的共识过程

PoM的运行从时间上被划分为一个一个的周期，每一个周期产生一个区块，每一个周期又被划分为两个阶段，每个阶段都有对应的时间限制，设第一阶段的时间限制为t1，设第二阶段的时间限制为t2。其具体架构如图3所示。

图3 PoM共识过程示意图

第一阶段：各个矿工通过等式（1）计算出本轮共识中自己的minimum，当minimum 的前m 位为0 时，则从交易池中筛选合法交易打包区块并广播至全网。m 的计算方法如等式（2）所示：

第二阶段：各个矿工比较从第一阶段中收到的区块，将比较得出的区块头中minimum最小的合法区块添加到区块链中。若第一阶段没有一个区块被广播，则将一个空区块添加到区块链中。空区块的结构图如图4所示，其区块体中的交易数量为0，Merkle根的值为空，打包该区块的矿工的公钥为空，minimum 为空，时间戳为t1结束的时刻。

当有新的矿工想要加入时，它相邻的矿工会将自己记录的区块链中最新的区块发给新矿工，新矿工将收到的区块进行对比，选择最一致的区块同步其整个区块链，即全网最统一的区块链是合法的。

图4 PoM空区块结构示意图

共识生成区块的伪代码算法如下：

Procedure CreatBlock

Input：version：version number of block chain；Bprev：previous block；publicKeyminer：the miner’s public key；

Output：A block with transactions or null

minimum=SHA256（SHA256（Bprev），publicKeyminer）

for placeminimumin m

if placeminimum.number!=0

end procedure

end if

end for

PreviousHash←Bprev

BlockBody←Block.wrap（transaction）

//The miner creates a warpped block that includes as many transcations as it wishes to include

MerkleRoot←HASH（BlockBody）

BlockHeader←（version，PreviousHash，Address，Merkle-Root，Timestamp，publicKeyminer，minimum）

Block←（BlockHeader，BlockBody）

return Block

end procedure

Procedure SelectBlock

Input：Blocks：Receive the legitimate block broadcasted

Output：A block with transactions or a empty block

if length（Blocks）==0

Block←EmptyBlock

return Block

end procedure

end if

Block←Block[0]

for 1≤i＜length（Blocks）

if Block[i].BlockHeader.minimum＜Block[i-1].Block-Header.minimum

Block←Block[i]

end if

end for

return Block

end procedure

3.3 PoM的临时分叉

在一轮共识中，当出现有不止一个矿工打包了minimum 相同且为最小值的合法区块时，区块链会发生临时分叉。

出现临时分叉的共识过程如图5所示。

图5 PoM临时分叉示意图

第一阶段：各个矿工通过等式（1）计算出本轮共识自己的minimum，当minimum 的前m 位为0 时，则从交易池中筛选合法交易打包区块并广播至全网。

第二阶段：各个矿工比较从第一阶段中收到的区块，若收到有不止一个minimum相同且为最小值的合法区块，则将这些区块都链接在区块链的末尾。

临时分叉后，所有的矿工可以在多条链上同时进行挖矿，当出现同一高度的不同区块的minimum 不同时，临时分叉结束，保留minimum 较小的那一条链，其余因为临时分叉而产生的区块被视为不合法区块。以临时分叉产生两条链为例，如图5所示，区块链在3号区块产生了临时分叉，当出现minimum 不同的两个4 号区块时，假设4’号区块的minimum 比4 号区块的minimum大，那么上面的区块被视为非法区块而被抛弃，下面的区块被视为合法区块。

3.4 公平性及稳定性分析及实验

下面从去中心化程度和稳定性两个方面对本文方案进行分析。

不同于PoW的算力竞争，PoS和DPoS的权益竞争，在PoM 中，哈希算法的抗碰撞性保证了每个矿工打包区块的概率是完全一样的。

当1 ≤n ＜24时。当24≤n ＜233时（世界人口接近于233），0.000 015 2 ＜P1＜0.018 315 7，表明PoM每轮共识产生空区块的概率非常小，且每轮共识被广播的区块在基本上都在16～32 个（有一定的随机性，有可能小于16 个，也有可能大于32 个）。若采用m=，当23≤n ＜233时，0.003 906 2 ＜P1＜0.135 335 3，每轮共识产生空区块的概率较大，稳定性下降。若采用，当25≤n ＜233时，0.000 000 000 2 ＜P1＜0.000 336，虽然每轮共识产生空区块的概率很小，但每轮共识被广播的区块基本上都在32～64 个，对网络的压力较大。

PoM 临时分叉的概率相当于在n 个0～(2256-1) 的二进制随机数中，出现有至少两个数相等且是这n 个数的最小值，而且这个最小值的前m 位均为0 的概率。将PoM临时分叉的概率记为P2，其概率算法如等式（4）所示：

可以看出，当n ≤233时，PoM 临时分叉的概率无限接近于0。

基于提出的PoM机制，进行仿真实验。使用golang语言模拟实现了PoM。实验环境为处理器：2.7 GHz Intel Core i5，内存：8 GB 1 867 MHz DDR3，闪存：121 GB，系统：macOS Sierra 10.12.3（16D32）。验证PoM 的共识机制的公平性和稳定性。

设置了211个矿工，连续进行了10 000 次PoM 共识，其中有3 次共识出空区块，没有出现过临时分叉，每个矿工成功挖矿次数在0～13 次之间不等，实验结果如图6 所示。实验表明，PoM 具有良好的公平性和稳定性。

图6 PoM挖矿分布图

3.5 计算开销分析

下面，对本文方案进行计算开销分析，包括计算时间开销和临时存储空间开销。

3.5.1 符号定义

文中用到的符号定义如表1所示。

表1 符号定义

3.5.2 分析

本文提出的最小值证明共识机制分为两个阶段，第一阶段是矿工打包区块并广播，第二阶段是矿工挑选区块上链。

在第一阶段中，各个矿工通过等式（1）计算出本轮共识中自己的minimum，再通过等式（2）计算出m ，当minimum的前m 位为0时，则从交易池中筛选合法交易打包区块并广播至全网。开销如表2所示。

表2 第一阶段计算开销

在第二阶段中，分为三种情况：挑选一个区块添加到区块链；临时分叉；创造一个空区块添加到区块链。其中临时分叉的计算开销与挑选一个区块添加到区块链几乎相同，且后两种情况发生的概率极小。开销如表3所示。由于，Bnumber×Bs 远大于使用堆排序的方法，将所有minimum进行排序时的临时存储空间开销、通常情况下x ≫Bnumber ，且第二阶段出现第二、三种情况的概率极小，所以每轮共识每个矿工总的计算时间开销为O( )2xBnumber ，临时存储空间开销为

表3 第二阶段计算开销

4 结束语

共识算法是区块链系统的关键要素之一，已成为当前信息领域的一个新的研究热点[13]。共识机制的性能在很大程度上影响着区块链系统的性能。为了解决现有公有链的共识机制存在着去中心化程度不高和经常出现临时分叉这两个问题。本文提出一种新的应用于公有链的共识机制PoM，PoM既保障了矿工在挖矿过程中的公平性，又保障了区块链增长过程中的稳定性。

共识机制只是区块链的一部分，想要完成一个优秀的区块链系统还需要有合适的激励机制的配合[14]。共识算法规定了矿工为维护区块链账本安全性、一致性和活性而必须遵守的行为规范和行动次序[13]；激励机制则规定了在共识过程中为鼓励矿工忠实、高效地验证区块链账本数据而发行的经济权益，通常包括代币发行机制、代币分配机制、交易费定价机制[15]等。只有共识机制与激励机制联合优化，才能保障区块链系统健康稳定的运行。