实用拜占庭容错算法的改进研究

唐 宏，刘 双，酒英豪，贺雨萌，朱 珊

1.重庆邮电大学 通信与信息工程学院，重庆400065

2.重庆邮电大学 移动通信技术重庆市重点实验室，重庆400065

3.重庆邮电大学 国际学院，重庆400065

随着比特币[1]等数字加密货币的不断发展，保障其安全可靠的区块链技术也随之得到广泛关注，在很多领域产生深刻影响。区块链[2-3]的本质是一种去中心化的分布式账本数据库，它集成了网络通信、共识算法、密码学原理、智能合约等技术，具备去中心化、防篡改、透明可溯源的特性。共识算法[4]作为区块链系统的底层核心技术，起到确保系统中的各节点对特定时间内打包的交易顺序达成一致，即实现分布式系统各节点数据一致性的作用。

实用拜占庭容错算法（PBFT）算法[5-6]是联盟链中应用最广泛的共识算法之一，解决了拜占庭容错算法效率低的问题。但PBFT仍存在下列不足之处，大大限制了其发展。首先，PBFT三阶段通信协议中的后两阶段，节点均需要向系统中的其他所有节点发送消息，导致通信复杂度过高；其次PBFT按照编号顺序选取主节点的方式也过于简单，导致无论是否为拜占庭节点，均具备相等的当选主节点的机会，这极大威胁了系统的安全性与公平性；最后PBFT算法对拜占庭节点缺乏惩罚措施，当主节点被发现为恶意节点时，仅仅依赖视图切换协议保障共识过程的进行，恶意节点仍存在于系统中，同样威胁了系统的安全性。

当前已有诸多研究人员从多个方面对PBFT算法提出了改进方案：文献[7]引入中心化的可信节点验证新加入系统的节点身份信息，要求系统中的各节点维护一个包含节点信息的记录表，并将各节点划分为良性、缺席、恶意三种类型。根据在共识过程中的表现动态更新节点信息表，同时针对节点加入、退出等操作创新性地设计了相关协议，用以解决PBFT算法的动态性问题；文献[8]为解决PBFT不适用于动态网络的问题，提出了利用可验证随机函数（VRF）选取共识节点的方法，从而使算法满足节点的动态变化需求，使其适用于动态网络；文献[9]从安全性和计算能力两方面对节点是否可靠这一属性进行量化处理，根据量化后的数值将节点角色分成四种类型，各类型节点中只有管理节点作为候补主节点，能够被纳入到主节点的选取范围内，同时为保障系统安全性只有获得较多选票的候选节点才可以转为管理节点；文献[10]针对PBFT 算法缺乏恶意节点惩罚措施的弊端，提出了基于信誉模型的改进拜占庭容错算法，通过信誉模型评估节点在共识过程中的行为，并从信誉值高的节点中选取主节点，以此提高系统安全性；文献[11]设置投票机制选取共识节点，并为促进节点积极参与共识过程，设置激励机制与惩罚机制，从而实现对系统中的节点的管控。以上方案均从不同的角度为改进PBFT提出了创新性设想。文献[12]通过增设候补集合的方式，解决PBFT算法动态性问题，并改进了视图切换协议及主节点选举机制，提高系统效率。

上述已有研究成果针对PBFT 算法存在的相关问题都给出了一些创新性的解决方案，然而考虑问题较为片面，没有从整体角度出发制定一套完善的节点管控机制。本文对PBFT算法通信复杂度高、主节点选取方式简单、缺乏节点管控机制的问题进行全面考虑，提出了一种基于节点可靠性评估的改进拜占庭容错算法（RB-PBFT）。改进算法从评估节点可靠性的维度出发，制定管控机制，贯穿节点整个工作周期。为节点管控制定详实全面的管理规则。

本文主要贡献如下：

（1）从节点的基础配置及共识表现两个维度分析，计算得到节点的可靠性评分，用以评估各节点的可靠性。选取可靠性评分最高的节点作为主节点，引领本轮共识过程，同时选取可靠性评分高的部分节点组建共识群组参与共识过程，解决PBFT选主不安全及通信复杂度过高的问题。

（2）根据各节点的可靠性评分，将其标记为不同的信任状态，对不同信任状态的节点进行分类处理，解决PBFT缺乏节点管控机制的问题。

通过对RB-PBFT 算法进行实验，分析表明，RBPBFT 在系统的通信复杂度、安全性、公平性、容错性等方面均有一定提升。

1 相关背景介绍

1.1 实用拜占庭容错共识算法

PBFT 算法于1999 年由Miguel Castro 和Barbara Liskov提出，该算法主要用于解决拜占庭将军问题，即如何在网络中存在恶意节点的情况下，确保最终决策的一致性与正确性，PBFT将拜占庭容错算法的复杂度从指数级降到了多项式级别，是拜占庭容错算法的首次实现。该算法在保障系统安全可靠的前提下，能够提供的容错性，即允许系统中存在不超过1/3的拜占庭节点。

PBFT中参与共识过程的节点被分成主节点（Primary）、备份节点（Backup）两类，其中主节点负责从客户端接收请求完成排序，并将相关消息广播给所有的备份节点，备份节点负责验证接收到的消息，执行相关操作并将结果返回给客户端。PBFT的三阶段通信协议是算法的核心部分，保障了共识结果的正确性。该三阶段协议又称为一致性协议，是典型的基于投票的共识协议，具体包括预准备（Pre-Prepare）、准备（Prepare）、确认（Commit）三阶段，如图1所示，图中备份节点3为拜占庭节点。

图1 PBFT一致性协议执行流程Fig.1 Implementation process of PBFT algorithm conformance protocol

1.2 信誉模型

1.2.1 EigenTrust信誉模型

EigenTrust[13-14]是P2P网络中广泛使用的信任度评估模型，以节点i为例，模型中每个节点维护两个值：（1）根据与其他节点交互历史得到的局部信任值Cij；（2）整个系统赋予节点i的全局信任值ti。EigenTrust模型计算信任值的过程如下：

（1）计算局部信任值。以节点i为例，根据交互历史，利用公式（1）对节点j进行评价，计算得到局部信任值Sij，其中Sat(i,j)代表历史交互中满意的次数，Unsat(i,j)代表不满意的次数。

（2）规范化局部信任值。得到Sij后，为防止恶意节点之间相互打高分，威胁系统安全，利用公式（2）对Sij进行标准化处理，得到规范化的局部信任值Cij：

（3）整合局部信任值。采用传递信任及多次迭代的思想，使节点i获得全局视野，利用公式（3）得到全局信任值。其中p是预先信任的节点集合，a是决定预先信任节点集合p中各节点权重的参数。

EigenTrust 信誉模型虽然具备使用简单、易扩展的优势，但其过度依赖预先信任节点集合。在EigenTrust信誉模型中，预先信任的节点有很高的地位，其他节点以这些节点为中心，信任这些节点所信任的节点，即使预先信任的节点存在恶意行为，其他节点仍会持续信任该节点。导致即使系统中其他诚实节点从未作恶，但若不在预先信任集合中，也会得不到重视，从而被逐渐边缘化。这极大威胁了系统的安全性。为解决上述问题，Kurdi 于2015 年提出了HonestPeer 信誉模型，实验证明HonestPeer信任模型相较于EigenTrust模型能够实现更高的成功率和更低的错误文件下载率。

1.2.2 HonestPeer信誉模型

HonestPeer[15]信任模型旨在解决EigenTrust 模型过度依赖预先信任节点，导致其他诚实节点被边缘化的问题。在HonestPeer 模型中，诚实节点有最高的地位，如果诚实节点在预先信任的节点集合p中，那么p中各节点在决定其他节点的信任值时仍然有很大影响力；但若诚实节点不在集合p中，p中各节点的影响力就会被减弱，诚实节点会发挥较高的影响力，如公式（4）所示，其中h为诚实节点。

HonestPeer模型允许节点根据以往交易历史，认证识别诚实节点，并通过判断诚实节点是否在系统预先信任的节点组中，来降低对预先信任节点的依赖，提高了信任模型的安全性及成功率。

2 RB-PBFT算法设计方案

2.1 算法概述

PBFT 算法要求系统中的所有节点均参与共识，并按照三阶段协议完成共识过程，其中完成一次共识，系统中广播的信息总量过多，导致系统通信复杂度过高效率较差。RB-PBFT 算法全面考虑节点的属性，利用层次分析法对节点的基础配置进行处理，得到节点的静态基础评分Bj；引入HonestPeer信任模型，根据节点间的交互历史，得到节点的动态信誉评分Rj；对两参数进行赋权计算，得到节点的综合可靠性评分Cj，以此来评估节点的可靠性。

由于PBFT 算法仅仅按照编号顺序选取主节点，选取主节点的方式过于简单。且一旦发现主节点为拜占庭节点，也只是依赖视图切换协议，更换主节点继续完成本轮共识过程。作恶的主节点依然留在系统中，且未受到任何惩罚，仍拥有与其他诚实节点均等当选主节点的机会，这难以保障系统的安全性及公平性。RB-PBFT算法根据降序排列的节点Cj，选取主节点并组建共识群组。等待本轮共识结束后更新节点Rj标记各节点的信任状态，根据节点不同的信任状态，设置节点管控机制。增加诚实节点入选共识群组的概率，减少恶意节点入选共识群组的概率。以此来解决系统安全性及公平性问题。

2.2 节点基础配置评分机制

考虑到节点基础配置越高，作恶成本也越高；同等条件下，高配置的节点较低配置的节点，传输信息的速度更快，效率更高。因此应将节点的基础配置纳入到评估节点可靠性的考虑范围内。在节点初入网络时，根据节点的基础配置，从影响交易处理速度的CPU 内核数量、计算机内存容量及硬盘容量大小这三方面进行评估。计算节点基础配置评分的步骤如下：

（1）由于各参数的单位不同，为了方便统一计算，利用归一化公式（5）对参数进行标准化处理，得到标准化后的数值。其中Xp为实际值，Xb为标准化处理后的数值。

（2）利用层次分析法，根据三方面参数的重要性分级构造判别矩阵，得到符合重要性排名的权重向量。

（3）根据权重向量及标准化处理后的数值，为各参数进行权重赋值，得到节点的基础评分Bj。

2.3 节点信誉评分机制

引入HonestPeer 信誉模型监测节点行为。首先初始化各节点的全局信誉值；选取共识群组成员，等待本轮共识结束后，更新各节点的信誉值，同时根据更新后的信誉值将节点标记成不同信任状态，以便后续制定节点管控机制。下面为具体介绍：

假设系统中的总节点数为N，将所有节点的本地初始信誉值设为0.5，根据公式（6）计算节点的初始化Cj。此处将初始信誉值设为0.5是根据后续计算各节点的可靠性评分Cj时，为了使Cj一直满足(0＜Cj＜1)条件，如果初始信誉值设置得过小，各节点Cj差距不大，不便于实验观察；如果Cj设置得过大，又难以满足(0＜Cj＜1)条件，同样不利于实验分析。得到Cj后，对其进行降序排列，选取Cj最高的节点作为主节点，并按降序Cj选取不同比例a(0＜a＜1)的节点构建共识群组，参与共识过程。选取的比例一定要保证共识组中成员数量始终大于2f+1（f为系统中拜占庭节点的数量）。

待本轮共识结束后允许共识群组中各节点之间根据交互历史进行互评。共识组中节点i对同处于共识群组中的节点j根据共识过程中节点j的具体表现，标记节点j的信任状态。标记节点信任状态分类的条件如表1所示。当节点j与i之间正常传递信息，且j向i发送的信息内容，与i收到的来自其他大多数节点的发送的信息内容一致时，i即可判定j在本轮共识中的行为正常，将j标注为诚实节点；当j未在规定时间内向i发送信息，或i向j发送信息后，j声称未收到来自i的信息，则节点i判定j的行为异常，但此时不能确定j的信任状态，可能是恶意节点作恶也可能只是节点出现宕机故障。先将其标注为故障节点，一旦之后发现j出现恶意行为，将其信任标注改为恶意；当j向i发送信息，但i发现该信息内容，与其收到的来自其他大多数节点发送的信息内容不一致时，i判定j的行为异常，将其标注为恶意节点。节点i根据对节点j的信任标注，更新本地信任矩阵，得到更新后的Rj，从而计算得到更新后的Cj，重新构建共识群组中的成员。

表1 节点行为及信任状态分类表Table 1 Node behavior and trust status classification

对于非共识群组成员（即未能参与共识过程的节点）RB-PBFT 算法允许其根据以往交互历史即以往印象对其他同处于非共识群组的成员进行评分，评分与标记规则与上述共识群体中各节点互评标记的规则一致。

2.4 节点管控机制

根据各节点的不同信任状态，制定管控机制，对节点进行分类处理：当节点j被标注为诚实状态时，节点i对j打+1 分，根据公式（4），诚实节点j的信任值Rj将持续增加；当节点j被标注为故障状态，计算节点i对j的局部信任值时，节点i对j打0分，使得故障节点的全局信任值维持不变，观察后续行为，做出相应处理；当节点j被标注为恶意状态，改进HonestPeer 模型，计算节点i对j的局部信任值时，允许i对j打-1分，节点j的全局信任值将持续减少。

2.5 节点可靠性评分计算机制

根据静态的基础评分及动态更新的信任值计算节点的可靠性评分，评估节点可靠性，要为两个参数赋予不同的权重比例K1、K2。虽然节点的基础配置会加快信息传递速度，提高系统性能，但为了抵御恶意节点成员聚集起来利用高配置设备进行攻击，节点的基础配置评分占比不应过高。因而相较于基础配置，节点在共识过程中的动态可信度在评估节点可靠性方面，应占较高比重，即权重参数满足(K1＜K2)。根据公式（6）计算节点的可靠性评分。

计算得到节点更新后的Rj，利用公式（6）更新节点的Cj，当恶意节点j的可靠性评分小于未参与共识过程的其他备份节点的可靠性评分时，节点j将被踢出共识节点组，不能继续参与共识过程。从未参与共识的其他备份节点中随机选取可靠性评分高于节点j的某个节点，取代j在共识组中的位置，参与共识过程。从而减少共识组中恶意节点的数目，提高共识过程及系统的安全性及公平性。

3 实验及理论分析

3.1 可靠性分析

安全性即各诚实节点能否对广播的事件结果达成一致性共识，并将正确结果成功输出。若成功输出正确结果，则认为系统安全性较高。在PBFT 算法中，主节点是依靠公式（7）进行计算，式中P为选取的主节点编号、V为当前视图编号、R为系统中的节点数目。可以看出根据取模运算，实际上就是按照顺序编号选取主节点，这使得拜占庭节点和诚实节点拥有相等的被选为主节点的机会，这种选主方式极大地威胁了系统的安全性。

在RB-PBFT 算法中，引入了共识群组的概念。综合评估节点的基础配置及共识表现，得出节点动态的可靠性评分，根据降序排列的可靠性评分，选取评分高的成员进入共识组。其中可靠性评分主要被节点信誉值影响，信誉值是节点间互评的结果，代表了节点之间的信任关系，节点作恶的概率与信誉值成反比关系。即高信誉值的节点作恶可能性低。由于共识组中的成员均是信誉值较高的节点，因此系统的安全性会得到提高。同时RB-PBFT 设置了节点管控机制，一旦节点被发现存在恶意行为，其可靠性评分将会随之降低，当评分低于非共识群组中的某节点评分时，该作恶节点将会被踢出共识组，系统安全性得到进一步保障。

实验所需硬件配置如表2所示，利用实验室不同基础配置的电脑搭建联盟链环境，使用docker容器技术模拟多个实验所需的虚拟节点。

表2 实验配置信息Table 2 Experiment configuration information

假设当前网络中共有20 个节点，即每台电脑利用docker容器模拟4个节点。首先根据各节点的基础配置计算基础评分，设置每个节点的初始信任值为0.5，得到初始化的节点可靠性评分。选取可靠性评分排在前a%的节点入选共识群组，即参与共识的节点数目为aN，未参与公式过程的节点数目为(1-a)N。当a=0.5 时，根据PBFT算法容错性，设置共识组内拜占庭节点数目为3，进行20轮共识。为了防止恶意节点通过高配置硬件设备作恶，节点在共识组中的表现影响力应超过基础配置，因此取基础配置赋权参数K1=0.3，信誉赋权参数K2=0.7。记录共识组内恶意节点可靠性评分如图2所示，新加入共识组的诚实节点可靠性评分如图3 所示，组内恶意节点数如图4所示。

图2 恶意节点可靠性评分Fig.2 Malicious node reliability score

图3 诚实节点可靠性评分Fig.3 Honest node reliability score

图4 共识组中恶意节点数目Fig.4 Number of malicious nodes in consensus group

可见，随着共识轮数的增加，共识组内恶意节点的可靠性评分随之下降，诚实节点的可靠性评分随之增加。当恶意节点的可靠性评分小于非共识组中某节点评分时，该节点将被取代共识组成员位置；同时共识组内恶意节点的数目随着组内成员动态变化而减少，最终为0。图中出现共识次数增加而恶意节点数维持不变的情况是当恶意节点仅做出故障节点行为使得信任值保持不变或该节点的可靠性评分仍大于候补节点的情况，但恶意节点数总体仍保持减少的趋势。

3.2 公平性分析

PBFT中，若发现主节点存在恶意行为，算法仅依靠视图切换协议，切换当前视图更换本轮共识的主节点，以保证共识过程。作恶的主节点仍然存在于系统中，且没有受到任何惩罚，下次当选主节点的概率依然与其他诚实节点相等，这对于诚实节点是不公平的，导致系统公平性较差。

RB-PBFT 算法则通过引入信誉模型的方法，允许共识群组中的各节点之间根据在共识过程中的表现进行互评；非共识组中各节点根据以往交互历史进行互评。标记节点的信任状态，设置节点管控机制。一旦节点被标记为恶意节点，其信誉值将随之降低，导致可靠性评分随之减少，将可能被移除共识组无法参与共识过程；而非共识组中的诚实节点，可靠性评分会随其诚实行为而增加，将有机会进入共识群组参与共识过程。简而言之，诚实节点会因其诚实行为而获得奖励；恶意节点会因其恶意行为受到惩罚。这种机制极大地提高了系统公平性。

3.3 通信复杂度分析

通信复杂度即完成一次共识，系统中广播的信息总数，过高的通信复杂度会影响系统的效率。PBFT算法、RB-PBFT算法及文献[12]的IPBFT算法完成一轮共识，系统所需广播的消息数目对比如表3所示。

表3 不同算法通信量对比Table 3 Comparison of traffic volume of different algorithms

根据表3 列举的各算法通信量，分别取a=0.5、a=0.25，绘制各算法广播通信量对比图5、图6。由于IPBFT算法通信量表达式中P为视图切换的概率，为方便观察数据，设置系统拜占庭节点数f=0，则P=0。

图5 a=0.5 时各算法通信量对比Fig.5 Traffic volume comparison of each algorithm when a=0.5

从图5 及图6 可以看出在a=0.5 及a=0.25，设定系统中不存在恶意节点的情况下，PBFT 算法及IPBFT算法均高于RB-PBFT 算法，且在RB-PBFT 算法中，通信量与参数a的取值成正比关系，a的取值减小，系统中广播的消息数量也随之减少。因此本算法提出的选取可靠性评分较高的部分节点参与共识的方案能够有效地减少系统中广播的通信量，降低系统复杂度，提高效率。

图6 a=0.25 时各算法通信量对比Fig.6 Traffic volume comparison of each algorithm when a=0.25

3.4 容错性分析

容错性指的是系统中最多能容纳的恶意节点数，PBFT中为保证顺利完成共识，系统仅支持容错性，而RB-PBFT系统中将节点划分到不同的群组：共识群组及非共识群组，使得系统容错性达到+(1-a)N，只有当a=1 时，两算法的容错性才相等，即全部节点均参与共识；而参数比例参数a是满足a≤1 的条件，即RB-PBFT算法最坏的情况的容错性与PBFT算法相同，因此本算法的容错性优于PBFT算法，两算法性能对比如表4所示。

表4 算法性能对比Table 4 Comparison of algorithm performance

4 结束语

本文针对原始PBFT 算法通信复杂度高、主节点选取简单、缺乏节点管控机制的弊端，提出了一种基于节点可靠性评估的改进拜占庭容错算法（RB-PBFT）。RB-PBFT从节点的基础配置及信任状态两方面评估节点可靠性，首先计算节点的基础评分，接着引入Honest-Peer 信任模型，根据节点在共识过程中的行为，标记节点的信任状态，允许共识组中各节点根据历史交互信息进行互评，非共识组中的各节点根据以往交互印象进行互评，得到节点动态变化的信任值，最后对这两个参数进行赋值权重，综合计算节点的可靠性评分。标记节点信任状态，设置节点管控机制。最终恶意节点的可靠性评分将随着共识次数的增加而逐渐减少，诚实节点的可靠性评分将不断增加。实验表明RB-PBFT算法能够提高共识过程的安全性及公平性，减少系统通信复杂度，同时在系统容错性方面也有良好表现。

本算法引入了信用模型，增加了计算可靠性的步骤，相较于原始PBFT 算法，进行共识时，增大了计算量。因此在传递相同数目信息，进行相同轮次共识时，RB-PBFT 算法的运行时间及传输时延略高于PBFT 算法。接下来将研究如何尽可能低的降低时间损耗，减小对算法运行效率的影响。