一种改进的区块链共识算法*

郭春梅 朱保平

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

2008年，中本聪发表了《比特币：一种点对点的电子信息系统》一文［1］，区块链的概念首次被提出。区块链运用了密码学，分布式共识，自动化脚本等技术，具有去中心化，可信任的特点［2］。在传统的支付方法中存在一个问题：一般需要一个可信任的第三方机构［3］。而区块链的去中心化特点恰巧能够解决这一问题，因此区块链的概念在被提出之后就立刻吸引了极大的关注并且被认为是最有潜力的技术之一。

区块链的最大特点即是去中心化，每个节点都能够验证交易［4］。区块链的共识机制主要是为了解决关于某个问题的形成一致性意见的过程，主要解决谁来记账以及如何维护账本的问题，是区块链的重要部分之一。

本文希望结合PBFT算法的优点，将它与区块链结合起来，更加适应区块链。并且考虑到PBFT算法记账节点一经确定无法修改的缺点［5］，我们对这一点进行改进，使得节点状态能够动态变化。同时我们考虑到对于联盟链并不需要POW共识算法那么高的容错性，所以用联盟链以太坊进行实验，与采用传统POW共识算法的联盟链以太坊和选择改进的PBFT算法的联盟链以太坊进行对比分析，验证我们提出的P-PBFT共识算法的性能。

2 相关工作

POW共识机制即为工作量证明机制，它采用解决一个复杂的数学难题的方式来决定新区块的归属问题［6］。因此POW主要依靠算力，算力越大，挖到矿的概率越大。由于POW共识算法极大的依靠算力，造成能源的浪费，因此主要适用于公有链。

POS共识机制即为权益证明机制，它的提出主要是为了解决POW算法上拥有大量设备的矿工更可能挖到新矿的不公平问题［7］。POS共识机制缓解了POW共识机制不公平及能源浪费的问题，但是可能导致节点离线从而容易造成网络攻击。

DPOS共识机制即股份权益证明机制［8］，是POS共识机制的进化版。DPOS共识机制没有挖矿的过程，能够提高共识的效率。但是这种共识机制将投票的权益集中到少数节点手上，可能会产生不公正的结果。

随着共识机制的进一步发展，人们不单单把目光集中在POW等共识机制上，逐渐地转向传统的分布式共识算法。拜占庭容错技术是一种解决分布式系统容错的通用方案［9］。由于安全问题越来越受到人们的重视，而拜占庭容错技术能够解决安全漏洞等问题［10］，而很多经典算法并没有能够解决拜占庭容错问题，所以PBFT算法的出现具有重要的意义。PBFT算法于1999年由Miguel Castro和Barbara Liskov提出，是一种能够容忍拜占庭错误的状态机复制算法［11］。

3 改进的PBFT共识算法

3.1 基本定义

定义1：假设系统中够容忍的最大错误节点的个数为f，那么根据拜占庭容错［12］可以假设区块链系统中共有3f+1个节点。

3.2 状态变化

我们在算法中引进状态变更，给不同节点授予不同的状态，在一段时间内，如果一个节点为共识表现较差的节点时，我们对该节点进行降级并且剔除出当前正在参与共识的节点集合，同时该时间段内候选节点集合内表现较好的节点可以进行升级加入到正在参与共识的节点集合。通过引进这种升降级的动态变化的机制，能够减轻异常节点的影响。

3.2.1 节点状态

为了减轻恶意节点的影响，防止恶意节点持续性地产生无效区块，我们给每种节点定义一个状态标识。

本文定义了两种状态如下：

1）Good：Good代表节点状态良好，可以正常参加参与共识；

2）Bad：Bad代表节点状态不佳，可能为恶意节点，不能正常参与共识。

3.2.2 状态变更

我们将算法中选出来的共识记账代表分为两个部分，GD部分以及BD部分。GD部分表示节点状态为Good的节点集合，BD部分表示节点状态为Bad的节点集合。GD部分节点存储在集合R1中，BD部分节点存储在集合R2中。

GD中存储的是正在参与共识的节点集合，根据拜占庭容错，假设能容忍的最大的恶意节点的数量为f，那么GD内节点数量必须满足以下公式：

BD中存储的是候补节点集合，一段时间内，GD集合内排名倒数x的节点将被降级，变为Bad状态同时加入到BD中。

为了不失一般性，我们令

状态变更的流程图如下：

图1 状态变更示意图

1）参与共识算法的记账代表节点，需要在全网注册，等待投票审核通过以后，正式成为一名候选代表，并将其信息在全网进行广播。

2）全网所有利益持有节点投票选举出自己的记账代表，共计N位。初始的时候，我们将这N位记账代表随机分配，分为3∶2的两部分。其中GD占三分之二，BD占三分之一，所有初始记账代表的初始值都是0。

3）我们给每个节点进行积分，然后根据积分进行排名。当一个主节点被从节点怀疑而引发配置变更，若变更成功，则主节点积分-2，从节点积分加1；产生区块的节点积分加1。

4）一段时间后根据积分进行排名，GD集合内排名倒数x的节点将被降级，变为Bad状态同时加入到BD中。

3.3 算法流程

PBFT算法进行一次正常的执行请求的过程主要分为pre-prepare，prepare，commit三个过程。

然而，PBFT算法是一种经典的分布式共识算法，它的三段式执行请求的过程也是基于分布式设计的［13］。PBFT算法是一种经典的C/S响应模式的算法，它的三段式执行请求的目的主要是为了在以状态机副本为主的分布式系统中指令顺序依然执行正确。区块链共识机制的根本目标是全网达成共识，而并不要求指令的顺序完全正确［14］。区块链达成共识需要信息在全网的广播，而信息在pre-prepare阶段和prepare阶段，信息已经在全网实现广播，所以我们可以将原本的三段式过程进行合并并且简化，合并成两段式过程。这样我们能够减少信息在全网的一次传播，提高效率。

图2 系统执行一次请求的过程

由于在存在错误节点的情况下f的最小取值为1，所以系统中至少有四个节点，图2展示了包含四个节点的系统执行一次请求的过程，四个节点包含一个主节点和三个从节点。

在区块链中，交易是以区块的形式存在并在永久记录并保存在区块链中［15］。在生成区块之前，先检验交易的合法性，如果交易合法，再将交易批量写入区块中。

交易合法性的判定如下：

1）交易是否已经存在，如果已经存在则为非法交易，如果并不存在则为合法交易；

2）交易是否符合交易书写规则，如果不符合则为非法交易，如果符合则为合法交易；

3）当前区块的前一个区块是否为区块链的末尾，如果不是，则区块链产生分叉，很有可能产生双重支付，如果是，则为合法交易。

当上述条件1）～3）同时满足时交易才判定为合法。

所以，P-PBFT的具体算法流程如下：

1）交易发起者发起交易的时候，首先附上自己的签名然后向全网广播；

2）所有节点独立监听全网交易，并且将监听到的记录在内存。当节点收到一笔交易时，如果是记账代表则需要验证交易的合法性，如果是合法的则写入到内存中，如果不合法，则丢弃；

3）主节点发送共识准备信息＜＜PRE-PREPARE，v，n，d＞σp，m＞ ；

4）从节点收到共识准备信息后，先对收到的信息进行检查，若检查结果为真，则向除自己以外的其他从节点发送共识确认信息PREPARE：＜PREPARE，v，n，d，i＞＞ ；

5）若结果为假，则从节点怀疑主节点，广播一条变更消息；

6）当主节点收到的正确信息大于等于2f时，共识完成，发布新的区块block；

7）其余节点收到block之后，本轮共识结束开始新的一轮共识。

4 实验与分析

为了验证本文的算法，本文将搭建8台1GB内存虚拟机，分别搭建采用改进的PBFT算法以及POW算法的以太坊联盟链。实验的硬件环境为Intel Pentium G3240，CPU 16GB。

4.1 算力开销

POW共识机制的最大弊端就是高额的算力开销，我们首先进行POW共识机制与我们改进的PBFT共识机制的算力开销实验比较。在验证算力开销的时候，我们选择相同的机器，分别运行基于POW共识算法和改进的PBFT共识算法来比较它们的算力开销。实验结果如图2所示，POW共识算法CPU的占用率几乎达到了100%，而改进的PBFT共识算法仅需要30%左右。所以说在以太坊中采用PBFT共识算法，将它运用于联盟链能够大大地减少算力的开销。

图3 CPU占用率对比图

4.2 容错性

根据PBFT算法的理论和设计，我们改进的PBFT共识算法的容错性依然应该是通过实验来验证改进的PBFT算法的容错性以及与以太坊原有的POW共识算法的容错性进行对比。我们通过使控制8台虚拟机，使它们发生拜占庭错误，控制发生错误的虚拟机数目，看是否能够正常运行来测试容错性。

表1 容错率分析

实验结果如表1所示，改进的PBFT算法在节点错误数量为1和2时能够正常运行，但是节点错误数量为3的时候就不能正确运行，它能够容忍的最大错误数量为2。但是POW共识算法可以容忍3个节点发生错误，所以在容错率方面，POW共识算法更优一些，但是改进的PBFT算法几乎可以满足联盟链的容错要求。

4.3 吞吐量

吞吐量是衡量一个系统单位时间内处理事务、请求、交易的能力［16］。我们选择TPS（每秒交易数）来衡量。在区块链应用中，吞吐量可以用交易发生到交易确认并写入区块链的总交易数除以时间来确定。

其中AccountTrans指的是交易发生到确认并写入区块链的总的交易数，t则是交易发生到确认的时间间隔。

图4 吞吐量对比图

我们选择不同时时间间隔t来测试TPS，t的取值分别为10s，20s，40s，100s，300s，每个时间间隔测试10次，我们取10次的平均值来作为各个时间间隔的TPS。

实验结果如图4所示。

根据实验结果我们可以发现本文提出的P-PBFT算法明显提高了吞吐量。

5 结语

针对传统的区块链共识算法的弊端，本文考虑到将传统的分布式共识算法PBFT加以改进运用于联盟链。本文主要工作如下：1）本文将传统的PBFT算法的三阶段过程进行合并并且简化为两段式过程，减少了复杂度使之能够更好地适应区块链。2）引入了状态变更的升降级制度，使得节点状态动态改变，减少恶意节点的影响。3）在采用传统POW共识机制的联盟链以太坊进行对比分析，分析提出的算法的性能。