基于信誉值的实用拜占庭容错改进算法研究

王启河

（华北电力大学 控制与计算机工程学院，河北 保定 071003）

0 引 言

近2008年中本聪提出一种点对点的电子现金系统即比特币，使得区块链底层技术得到了社会广泛关注。区块链具有不可篡改性、去中心化、安全性高等特点。这些特点使得区块链技术在各业界的应用得到迅速发展。共识算法直接影响区块链的效率，对共识算法的研究是区块链技术的研究热点之一。

区块链可以根据去中心化程度分为公有链、联盟链和私有链三种类型。公有链去中心化程度最高，其特点是用户量大、节点数较多、且节点出入系统随意。公有链常用的共识算法为PoW。PoW 计算消耗大，为了争夺主节点奖励会产生不必要的消耗，后续出现了其他的公有链共识算法。私有链去中心化程度最低，一般的共识算法为Paxos和Raft等，这些算法记账效率高于公有链和联盟链，但去中心化程度低，一般是用于私人或一个公司内部使用。联盟链的去中心化程度介于公有链和私有链之间，一般用于组织联盟之间，应用范围较广。联盟链的共识机制是BFT 和PBFT。BFT 是1982年由Leslie Lamport等人提出，要求算法能够在有三分之一恶意节点的情况下完成共识。原文中仅提出了口信消息型和签名消息型两种解决方案，注重理论上的可解，算法复杂度太高，共识效率太低，不具备实用价值。Miguel Castro 和Barbara Liskov对BFT 改进后提出PBFT算法，成功将BFT算法的复杂度由指数级降低到多项式级别，使得拜占庭容错机制得以在实际实现中变得可行。

PBFT 算法使得联盟链中的拜占庭将军问题在实际运用中可行，但算法仍存在主节点选取随意，网络通信开销较大，公平性较低等问题。本文针对这些问题，提出一种基于信誉值的PBFT 改进算法，对主节点的选取方式、达成共识的判断条件进行改进，优化了共识过程，减少了通信量，提高了系统公平性。

1 相关工作

1.1 实用拜占庭容错算法

实用拜占庭容错算法（PBFT）能在有3+1 个节点的系统中，容忍存在个恶意或故障节点存在的情况下以多项式级别的通信量完成共识，采用密码学相关技术确保消息传递过程无法被篡改和破坏。在PBFT 算法中所有节点被分为客户端节点，主节点和备份节点三种类型，其中主节点和备份节点统称为副本节点。每一个节点都有一个编号，每一轮共识称为一个视图，视图编号为。每个视图都要经过请求（request），预准备（pre-prepare），准备（prepare），确认（commit）和响应（reply）五个阶段。算法执行流程如图1所示。

图1 PBFT 算法执行流程

具体步骤为：

请求阶段：由客户端节点发起提案请求给主节点，主节点的编号按照=mod||计算得到，为节点总数。提案请求格式为＜request，o，t，c＞，request 包含消息内容以及的摘要（），表示执行的操作，表示时间戳，表示客户端C 的标识。

预准备阶段：当主节点收到客户端的请求并验证成功后，主节点向除了自己以外的所有其他节点发送预准备信息。预准备信息格式为＜＜pre-prepare，v，n，d＞，m＞，为节点给请求分配的编号，为请求消息的摘要。需要备份节点给＜pre-prepare，v，n，d＞进行签名。

准备阶段：当其他节点收到验证成功的预准备信息后，向包括自己在内的节点发送准备信息，并把预准备信息写入日志。准备信息格式为＜prepare，v，n，d，i＞，表示当前节点的编号。且节点要对＜prepare，v，n，d，i＞进行签名。

确认阶段：当节点收到2+1 条验证成功的准备信息（包括请求和预准备信息）后，节点向所有节点发送确认信息。确认信息格式为＜commit，v，n，d，i＞，节点需要对＜commit，v，n，d，i＞签名。

响应阶段：当节点收到2+1 条验证成功的确认信息后，节点向客户端发送一条响应信息。响应信息格式为：＜reply，v，t，c，i，r＞，为请求操作结果。当客户端收到+1 条相同的响应信息后表示客户端的请求达成共识。

1.2 PBFT 算法相关改进研究

目前对PBFT 的改进方向有两种：一是减少参加共识的节点数量，即每轮只选取一部分节点进行公示，达到减少通信量的目的；二是优化共识过程，通过改进共识过程或增加节点评判机制，减少不必要的通信，达到增加共识效率的目的。

在减少参加共识的节点数量改进方面：文献[13]提出一种VPBFT 算法。引入投票机制，将节点分为投票者、管理者、候选人、普通用户四类，每种节点有不同权限，这样做的本质是减少参加共识过程节点的数量。文献[14]提出一种基于网络自聚的NAC-PBFT 算法，文献[15]也提出一种K-PBFT类聚算法，两种算法核心思想都是将节点分组，每个分组内共识后由骨干节点再进行公示，在有大量节点的情况下减少通信量。此种类聚算法本质上是分组类聚减少每次共识的节点数量。文献[16]提出一种基于树形网络拓扑图的共识算法，通过对全网共识任务进行拆分，减小任务的整体规模。以上的四类算法都是通过减少参与共识过程的节点来达到减少通信量的目的。通过聚类分组或以其他分组结构（如树形网络拓扑）的方式分组进行公示，最后达到全局共识。此类算法适用于节点数目较多的情况，若节点数太少优势不明显。

在优化共识过程方面：文献[17]提出一种IPBFT 算法，将节点分为协商节点和执行节点，引入节点的自证机制，使得在长期共识过程中的共识效率提高，是一种优化共识过程的算法。文献[18]提出一种基于时间权重的PBFT 算法。算法给每个节点赋予一个时间权重，存在时间越长权重越大，对共识影响越大。对主节点选取算法根据权重选取，优化共识流程，提高系统安全性。文献[19]提出一种E-PBFT 算法，通过优化主节点选举方式以及优化共识流程对算法进行改进，减少算法的通信量。文献[20]提出一种PBFT 改进算法，通过对交易分类为平等交易和不平等交易，只对错误交易进行公示，减少共识次数来增加区块链共识的效率且增加了算法的可扩展性。文献[21]提出一种RB-PBFT 算法，引入信誉模型和节点的可信度评估，对恶意节点有惩罚机制。RBPBFT算法通过信誉值排名来决定哪些节点进入下一轮共识，减少参与共识节点数目。以上几类算法的核心思想都是增加信誉值或者其他方式，对PBFT 算法流程进行改进，达到减少通信量和提高算法公平性的目的。

通过对以上算法的研究，本文提出一种改进的PBFT 算法，算法引入一种更合理的信誉机制，提高算法的公平性。同时，改进算对共识流程进行优化，优化部分不必要的通信，减少共识所需要的通信量。

2 改进算法

2.1 算法思想概述

PBFT 算法中每一轮共识中所有节点的影响力都相同，这样对于诚实节点来说是不公平的。在实际情况中，故障节点和作恶节点对于共识的贡献是零甚至是在破坏共识，所以共识成功的节点应该在下一轮的共识中更有影响力。本文提出一种PBFT 的改进算法，对每个节点增加一个信誉值。信誉值会随着节点的行为变化，信誉值的大小就是节点在共识过程中影响力的大小。随着共识轮次的增加，系统中故障节点和恶意节点影响力变小，诚实节点影响力变大。

2.2 信誉值调节机制

节点的信誉值情况由节点在本地进行维护。每经过一轮共识，各个节点根据接收到的数据确认情况更新信誉值。诚实节点信誉值会得到提升，故障节点和恶意节点信誉值会不同程度的降低。节点按照表1分为诚实节点、故障节点、恶意节点三种节点类型。高信誉值节点也可能会在某一轮共识中作恶，惩罚方案是信誉值越高，作恶惩罚越大。

表1 节点分类表

假设共有个节点，一轮共识后有个诚实节点，个故障节点，个恶意节点（++=）

故障节点信誉值更新公式：

其中表示第个故障节点更新后的值，表示第个故障节点更新前的值，为故障节点更新系数。1≤≤，0 ＜＜1。

故障节点信誉值降低值总和：

恶意节点信誉值更新公式：

其中表示第个恶意节点更新后的值，表示第个恶意节点更新前的值，为无效响应节点更新系数。1≤≤，0 ＜＜1。

恶意节点信誉值降低值总和：

所有非诚实节点信誉值降低总和为：

诚实节点信誉值更新公式为：

其中w表示第个有效响应节点更新后的值，w表示第个恶意节点更新前的值。

2.3 主节点选取算法

PBFT 算法中主节点选取方式是客户端节点根据视图编号计算得出，对节点本质上没有任何筛选，通过视图转换协议解决恶意节点或故障节点成为主节点的问题会影响共识效率。本文主节点选取算法为：

根据节点信誉值序列w筛选出信誉值大于主节点最低值的所有节点，节点编号和信誉值分别存入备选主节点编号序列c和备选主节点信誉值序列b中，1≤≤，为备选节点总数。

根据式（7）算出主节点备选序列的累积和序列，1≤≤+1。

随机生成一个随机数，0 ＜＜s+1。

遍历序列b，若满足b＜＜b，则编号为c的节点成为主节点。

所有节点在验证视图更换请求时，需要验证客户端节点所请求的主节点的信誉值是否大于，若大于则可以接受，若小于则拒绝。

2.4 算法流程

PBFT 算法的确认阶段是统计系统中大部分（大于等于2+1）节点已经共识成功，但又将结果广播于所有节点，所有节点又进行一次统计工作才将结果响应给客户端。两次广播导致算法通信复杂度较高。在改进算法中，节点对于数据的验证和确认只在第一个广播阶段完成，第二个阶段更新节点信誉值。改进算法的五个阶段为：预提案阶段（preproposal）、提案阶段（proposal）、数据确认阶段（data-commit）、信誉值更新阶段（reputation-update）、响应阶段（reply）。基于信誉值的PBFT 算法消息发送过程如图2所示。

图2 基于信誉值的PBFT 算法消息发送过程

预提案阶段：客户端节点通过主节点选取算法得到主节点编号，向主节点发送一条提案请求消息。预提案请求格式为＜pre-proposal，o，t，c，j＞，其中表示请求的操作，表示时间戳，为客户端C 的标识，为主节点编号。preproposal 中包含请求消息以及消息摘要（m），且客户端需要对预提案请求进行签名。

提案阶段：当主节点收到预提案请求后，验证客户端请求是否合法，检验客户端节点提供的信誉值序列与节点本地保存的信誉值序列是否一致以及主节点的信誉值是否大于。验证通过后主节点为提案编一个序号，然后向除了自己以外的其余节点发送一条提案信息。提案信息格式为＜＜proposal，n，j，d（m）＞，m＞，且需要对＜proposal，n，j，d＞进行签名。

数据确认阶段：当副本节点收到提案信息后（主节点完成预提案阶段后直接到数据确认阶段），验证提案信息的合法性，同时对请求数据进行验证。若通过则先将提案信息内容记录到日志，然后向所有节点发送一条数据确认信息。数据确认信息格式为：＜data-commit，n，j，d（m），i＞，为当前节点编号。且需要对＜data-commit，n，j，d（m），i＞签名。

信誉值更新阶段：当副本节点收到一条数据确认信息后，先对信息进行合法性验证。节点进入此阶段后启用一个计时器，设置一个此阶段的最大等待时间，在此阶段内接收到的数据确认信息进行下一步分类，此时间段之外的节点直接认定为故障节点。计时结束后，副本节点需要记录所接收到数据确认信息的来源，完成节点分类序列。计时结束后，向主节点发送一条信誉情况＜reputation，＜p，i，n，j＞＞，副本节点需要对＜p，i，n，j＞进行签名。主节点需要将各个节点的信誉消息汇总成信誉消息矩阵PI，PI 由主节点所接受到的所有信誉情况信息组成。然后向其余节点发送一条信誉更新信息＜reputation-update，PI，n，j＞，主节点需要对此消息签名。此阶段转发过程如图3所示。

图3 信誉消息转播示意图

其中，分类序列中值为1 表示对应节点为诚实节点。为表示一般情况，用表示不确定值。

响应阶段：当副本节点收到信誉更新信息后，先对信息进行合法性验证，然后根据信息中的信誉消息矩阵PI 进行计算得到共识结果以及得到共识过程中各个节点的分类情况，根据分类情况按信誉机制对各个节点信誉值进行更新。此后，副本节点向客户端发送一条响应信息＜reply，t，c，i，j，w，r＞，为验证结果，为更新后的信誉值序列。当客户端节点收到相同响应信息对应节点信誉值累积和大于+1 时，表示共识完成。

3 算法分析

3.1 一致性分析

算法的一致性主要是需要所有诚实节点对数据共识结果以及对各节点的信誉值的更新结果保持一致，信誉值在共识过程中起到判断条件的作用，不同信誉值序列可能会出现不同的结果。本算法是在每一轮共识结束后，需要保持最终一致性。每一轮算法经历两次共识。第一次是在数据确认阶段，完成对数据的共识。各节点并没有在此时就直接认定此数据能通过，而是在进行各节点的行为统计，为后面的信誉值更新做准备。第二次共识是在信誉值更新阶段，完成各节点信誉值更新的共识。

在信誉值更新阶段最后各个节点会收到来自主节点发送来的信誉消息矩阵PI，为了便于说明，假设系统3f+1 个节点中节点编号1 至2+1 的2+1 个节点为诚实节点，节点编号2+2 至3+1 的个节点可能是故障节点或恶意节点。对于一次成功的共识来说，各节点收到的信誉消息矩阵如表2所示。其中共识结果中第行第列的值为1 表示编号为的节点在数据确认阶段收到节点的数据确认消息，为0 则表示未收到数据确认消息，为了表示情况的一般性，用表示不确定，即值为时值可能为0 或1。

表2 信誉消息矩阵

对于诚实节点来说，在一次成功的共识中该节点一定能接收到其他诚实节点的确认信息，所以编号为1 至2+1 的节点之间的值一定都为1。对于编号为2+2 至3+1 的节点，其余节点不确定是否能收到确认信息，且主节点不一定能收到该节点的信誉情况消息，所以涉及这些节点通信的值都为不确定。当各节点收到此消息矩阵时，便可以通过此矩阵得到共识结果以及对于信誉值的更新结果。显然，只要各个节点所收到的信誉消息矩阵一致，最终各节点对信誉值的更新结果和对数据的共识结果都是一致的。

3.2 通信量分析

通信量就是在一轮共识过程中，系统各节点之间通信次数之和。本算法中通信量与原PBFT 算法不同的地方主要是在信誉值更新阶段。在个节点的系统中，原PBFT 算法在准备阶段和确认阶段进行了两次全体广播，而改进算法只在数据确认阶段进行一次全体广播以及在信誉值更新阶段进一次主节点转播，所以改进算法通信减少量为一次全体广播的次通信减去一次主节点转播的2（-1）次通信，即本文算法通信量为（2-2）-（-2（-1））=+-2。

本文改进PBFT 算法的通信复杂度还是（）量级，但通信量大约减少了一半。原PBFT 算法，文献[21]提出的RB-PBFT 算法以及本文改进PBFT 算法通信量对比如表3所示。其中RB-PBFT 算法中的为该算法中每次筛选节点参与共识的节点的比例。RB-PBFT 算法是通过减少参与共识的节点数来减少通信量，与取值有关。

表3 算法通信量对比

3.3 公平性分析

本文算法与现有的引入信誉机制的RB-PBFT 算法相比，在公平性上也有一定的提升。RB-PBFT 算法是通过给节点信誉值排名，然后取信誉值排名靠前的一部分参加共识，这样做虽然避免了一部分恶意节点的作恶，但这属于一刀切策略。对于一些节点，可能只是因为网络延迟等原因在某次共识后导致信誉值靠后，结果被踢出系统。对于一个公平的系统来说，共识过程应该是所有节点都能参与共识，只是信誉值不同的节点对共识的影响不同，改进算法很好地做到了这一点。

原PBFT、RB-PBFT 算法和本文改进算法公平性对比如表4所示。

表4 各算法公平性对比表

4 结 论

本文针对PBFT 共识机制通信量高，主节点选取未筛选以及对各节点在共识过程中行为缺乏赏罚机制等问题，在PBFT 算法基础上引入信誉值机制。通过信誉机制的引入，对各节点在每一轮共识的行为进行评判，逐渐减小故障节点和恶意节点对共识结果的影响，通过对信誉值更新达到对节点进行赏罚的目的。在选取主节点时，从信誉值达到条件的节点中筛选，减少了新的主节点仍是非诚实节点的可能性。信誉机制的引入也提高了算法的公平性。此外，改进算法还对共识流程进行了优化，在保证一致性和安全性的同时降低了每轮共识的通信量。改进算法与原PBFT 算法相比，会产生更多关于维护节点信誉值时所产生的计算上和内存空间上的消耗，如何减少这些消耗是接下来的进一步研究方向。