基于信任评估模型的PBFT共识算法

任玺羽，童向荣*，张伟

（1.烟台大学 计算机与控制工程学院，山东 烟台 264005；
2.山东外国语职业技术大学 二级学院，山东 日照 276826）

区块链系统［1］是多中心、防篡改、公开透明、安全可靠、用于存储交易信息的分布式数据库系统，由系统中所有的节点共同进行维护。数据的存储通过哈希函数加密的链式区块结构［2］，数据的产生和更新通过区块链系统中节点间的共识过程。区块链中的数据存储在每一个节点上，即使有部分节点发生故障，可以利用区块链系统网络层中的Gossip协议［3］进行数据同步和恢复。

共识算法是区块链系统中的核心技术，利用它可以解决分布式系统的一致性问题。起初，分布式计算机领域的共识问题是由Lamp⁃ort［4］提出在一组可能存在故障节点，并通过点对点消息通信的独立处理器网络中，保证非故障节点能够针对特定值达成共识。2008年末，随着比特币的提出，拜占庭容错共识算法逐渐获得实际的应用，拜占庭将军问题是区块链技术核心思想的根源，对区块链共识系统的实现有重要影响。

目前，已经提出了工作量证明共识（Proof of Work，PoW）［5］、权 益 证 明（Proof of Stake，PoS）［6］、授权股份证明（Delegated Proof of Stake，DPoS）［7］、PBFT［8］等共识算法。Saputra等［9-10］提出基于Hashcash的PoW共识算法，系统中的所有节点为了生成区块的资格，必须找到能满足系统要求的随机数，这将大大浪费哈希功率。PoS算法［11］要求每个节点都根据自己的利害关系来寻找随机数。为进一步提高共识效率，Bitshares等［12］提出了DPoS 共识算法，此算法是让所有节点参与选举，共同选出一组证人节点，生成新的区块。PoW、PoS和DPoS共识算法，虽然可以容忍拜占庭节点，但是在生成区块的过程中可能会导致分叉。相比之下，对于联盟区块链来说，PBFT共识算法是更理想的共识算法，它能够保证系统中不会产生分叉行为，还可以容忍一定数量的拜占庭节点。

PBFT共识算法有效解决了原拜占庭容错算法［13］共识效率不高的问题，能够接受小于1/3的拜占庭节点。但其通信复杂度会随着网络中节点数量增加而增加，通信复杂度达到O（N2），系统的扩展性也不够好。文献［14］提出了基于PBFT的可伸缩多层共识算法，将节点分为多层，降低单层PBFT共识的通信量，解决了原PBFT共识算法的可扩展性不足的问题，但忽略了对主节点的信任度评价。文献［15］提出了EPBFT共识算法，该算法可以根据系统所处的网络环境采取不同的步骤来达成共识，此算法采用了VRF来选举共识节点，能够适用于动态的网络环境。但在EPBFT中，共识过程接收客户端请求消息的主节点可能是拜占庭节点，造成系统的通信开销较大。

针对以上问题，为了选取更可靠的主节点，根据节点的交互历史，选取信任评估值较高且一直稳定的节点，优先作为共识过程的主节点，提高系统的可靠性。为了解决系统中通信量过大的问题，对系统中的节点进行分层和分组共识，以主节点为初始中心，以距离为标准进行聚类分组，因此组内节点数量较少。原PBFT共识算法通过节点全网广播来达成一致，将会大幅度消耗系统中的通信资源。改进后进行组内广播，降低了通信量，保证总体通信量远低于原PBFT共识算法。

本文的主要贡献如下：

（1） 为了使共识算法能够应用到大规模的网络系统中，引入了双层PBFT系统模型，利用聚类方法将系统中的节点进行分层分组，减少通信复杂度，提高系统的灵活性；

（2） 在小组共识前，改进了主节点的选取。利用节点信任评估模型，依据节点在系统中的历史行为进行评估，选取信任值最高的节点作为共识小组的主节点，提高系统的效率和可靠性；

（3） 通过分析，改进算法的通信复杂度小于原PBFT算法的通信复杂度O（N2）。通过实验验证，该改进的算法优于基线算法。

近年来，随着区块链的快速发展，根据去中心化的程度可以把区块链分为公有链、联盟链和私有链［16］。这三种区块链都有各自的共识算法，公有链共识可以分为PoW共识、PoS共识、基于PoW共识和PoS共识的改进，例如POA共识［17］、POSV共识［18］等。联盟链共识总体可以分为两类：拜占庭容错共识和非拜占庭容错共识，非拜占庭容错共识又称作故障容错类共识，指的是在系统发生宕机问题时，能够保障系统的可靠性，但当出现不诚实的节点时，无法保证区块链系统的可靠性，例如PAXOS 共识［19］、RAFT 共识［20］；
拜占庭容错共识是指节点对广播的信息进行伪造并恶意响应，但系统中能够允许存在一定数量的不诚实节点，例如PBFT共识。私有链和其他两种链不同，只用于组织内部，大部分采用PBFT、RAFT等共识。

联盟链可以用于多个组织或机构之间的合作，有利于信息共享，比较符合当下的发展趋势。对于联盟区块链来说，PBFT共识算法是更加理想的共识算法，容忍一定数量的拜占庭节点，它通过核心三阶段的共识过程可以保证网络中节点的一致性，通过超时检测和视图变更协议保证了系统的活性，通过节点交互过程签名消息确保了系统的安全性。但原始PBFT共识算法也存在一定的缺陷，比如不适用节点数量较大的网络、无法识别系统中的拜占庭节点等。在共识过程中，只要收到超过一定数量的回复消息就认为是达成共识等。由于区块链技术的快速发展，众多学者也针对PBFT算法出现的问题进行了研究，为推进此算法的广泛应用做出了贡献。

对PBFT共识算法的改进主要是在改进共识结构和解决通信复杂度过高两方面。在改进共识结构方面，文献［21］通过改进C4.5提高节点分类的准确度，引入积分机制，有效缓解了在节点数量规模较大的情况，原PBFT共识算法共识效率低下的问题。文献［22］提出了一种可以任意扩展的分布式模型，把PBFT共识算法和P2P信任计算模型相结合，能够提高系统的容错率和可信度。

在解决通信复杂度方面，文献［23］对具有PBFT共识的Hyperledger fabric v0.6的性能进行了评估，此共识算法能够为系统贡献较大的吞吐量，但随着节点数量的增加，系统的性能会有下降趋势。文献［24］提出了积分机制来解决通信复杂度过高的问题，通过节点积分来选取共识节点，来降低通信开销。文献［25］提出了G-PBFT，利用固定物联网设备的地理信息达成共识，减少了验证和记录交易的开销。本节将简要介绍已有的相关工作。

1.1 拜占庭将军问题

目前，大多数专家学者所研究的共识问题主要包括两种，算法共识和决策共识。这两种共识问题最初来源于拜占庭将军问题，区块链系统共识的基础也是拜占庭将军问题。

拜占庭将军问题是指在拜占庭帝国里的将军率领他们各自的军队对敌方的城池进行围攻，由于军队相隔较远，每个将军只能控制自己的军队，要想商榷一个合理的作战计划并达成共识，只能通过信使传送消息给其他的将军。但将军中可能存在叛徒，他们在传递消息的过程中，试图传播错误的行动计划，来欺骗其他忠诚的将军。拜占庭将军问题即找到一个可行的算法，当存在少数叛徒的情况下，忠诚的将军们仍能够达成共识。

1.2 PBFT共识算法

PBFT共识算法能够应用于异步网络［26］环境，是在联盟链中采用最多的共识算法，该算法允许存在拜占庭节点，但不能识别拜占庭节点，只要系统收到超过一半的回复消息即达成共识。

PBFT共识算法是一种基于状态即复制的容错算法［27］，它可以提供不超过（n-1）/3故障的容错保证。为了保护分布式系统免受恶意用户的攻击［28］，共识过程中节点的角色划分有三种，包括客户端、主节点和副本节点。PBFT共识算法核心是由一致性协议、检查点协议和视图变更协议组成。网络系统在正常运行的情况下，只执行一致性协议和检查点协议。当主节点出错或者系统运行缓慢的情况下，会进行视图更换协议，以维持系统能够继续响应客户端的请求。

1.2.1 一致性协议

一致性协议将系统中的共识节点划分为主节点和副本节点。主节点对客户端发出的请求进行排序；
副本节点按照主节点提供的顺序执行请求。所有的节点都在相同的配置下工作，这个配置信息称为视图（view），每更换一次主节点，视图就会随之变化。

1.2.2 检查点协议

检查点协议用于从日志中安全地丢弃消息，并帮助落后的节点同步最新的状态。在一致性协议中，系统每执行一个请求，节点都需要记录日志。如果日志不能及时清理，就会导致系统资源被大量日志所占用，影响系统的性能，即可用性。另一方面，由于拜占庭节点的存在，一致性协议并不能保证每一个节点都执行了相同的请求，不同节点状态可能不一致。因此，设置周期性的检查点协议，可以将系统中的节点同步到某一个相同状态。

1.2.3 视图变更协议

主节点对客户端发出的请求消息不进行响应或主节点向所有共识节点广播不一致的预准备消息时，视图变更协议（view change）可以帮助系统继续正常工作。视图变更协议一共包含viewchange、view-change-ack和new-view三个阶段。

系统正常运行的情况下，客户端将请求消息发送给主节点，然后，由主节点将请求消息广播给其他副本节点，进行一个视图view。但当接收请求消息的主节点出错或者不响应消息时，此时就会进行视图更换操作，采用轮换法选择主节点，视图编号为view+1，进入下一个共识过程。

1.3 PBFT共识算法共识过程

在主节点没有故障的情况下，PBFT共识算法一次完整的共识过程需要经历请求（re⁃quest）、预准备（pre-prepare）、准备（prepare）、确认（commit）和回复（reply）五个阶段［29］，其中预准备阶段、准备阶段、提交阶段是共识过程中的核心三阶段。

请求阶段：客户端发送请求消息给主节点，附带时间戳等信息。时间戳可以保证该请求不会重复执行。根据时间戳t，能够辨别操作的执行顺序。

预准备阶段：主节点响应客户端发出的请求，验证通过，给该请求消息分配编号，然后，把预准备消息广播给其他的副本节点。

准备阶段：节点接收到来自主节点的预准备消息进行验证其有效性，如果验证通过，则向其他节点广播准备消息。

确认阶段：当节点接收到至少2f（f为拜占庭节点的数量）个准备消息，验证通过后，向全网广播确认消息。副本节点将确认消息发送给其余副本节点。当系统中节点接收到2f+1个有效的确认消息后，就可以向客户端发送回复消息。

回复阶段：副本节点执行完上述操作，副本节点向客户端发送回复消息，当客户端接收到2f+1个独立的返回结果，就认为达成共识。

本节对改进的PBFT共识算法做了描述，介绍了节点信任度评估模型中的相关定义。

2.1 问题描述

为了解决节点数量规模较大的问题，并选取可信的节点作为主节点参与共识过程，提出了基于信任评估模型的双层PBFT系统，如图1所示。第一层有一个主节点和q个副本节点组成了一个共识小组，第二层一共有Z个节点。经过对节点的信任评估，选取信任值最高的节点作为共识小组中的主节点，避免故意不响应消息或响应错误消息的节点作为主节点，可以提高系统的安全性和可靠性。经过信任评估选出可信的主节点作为初始化的聚类中心节点。

2.2 节点的信任度评估

为了选出信任度值高的节点作为主节点，对节点的信任度进行评估，以此提高系统的安全性和可靠性。系统中不同的节点有不同行为，某些节点积极主动参与共识过程，能够及时对系统的消息做出应答；
亦存在一些恶意节点，不对系统发出的消息做出应答或响应错误消息。对节点进行评估主要分为两方面，一是对节点的静态评价，通过对节点在系统中发生的历史共识行为和共识参与程度进行评价，二对节点的动态评价，通过共识过程中节点之间的交互行为进行评价。

定义1 节点信任度。节点i的信任度评估模型为

其中，Trusti表示节点i当前的信任度值。信任度值由对节点i的静态评价和对节点i的动态评价两部分共同组成。TSi是节点i的历史共识行为和参与度来对其进行评价，即节点i的静态评价。TDti是节点i和其他节点之间的交互行为进行评价，即节点i的动态评价。α和β分别是静态评价和动态评价所对应的权重。

定义2 节点i的静态信任度值。根据节点在共识过程中的历史行为来进行计算，可以表示为

其中，Bi是节点i在共识过程中的历史行为因子，Pi是节点i在共识过程中的历史参与程度因子，γ和θ是各自所对应的权重。

定义3 历史行为因子。节点i的历史行为对其信任值的影响程度。节点i历史行为因子，可以表示为

其中，Ris表示为节点i在曾经的共识过程中表现出诚实行为的次数。Rif表示为节点i在共识过程中有恶意行为的次数。φ和ϖ是对应的权重，φ+ϖ=1。Ri表示节点i曾参加共识过程的次数，Ri=Ris+Rif。由此公式可以看出，节点做出诚实行为的次数越多，对增加节点信任度值的影响越大。

定义4 节点参与程度。评价节点是否积极参与共识，表示为

其中，R表示为节点参与过共识过程的总次数。Ri表示节点i参与过共识过程的次数。

定义5 节点i的动态评价。节点之间相互进行评价。节点i的动态评价可以表示为

其中，节点i和节点j是两个不同的节点（i≠j），N表示系统中节点的总数，t表示客户端发出请求消息的请求周期，l表示在周期t内的共识次数，m是第m次共识，是在第m次共识中，节点j和节点i进行交互后，对节点i的评分。f(m)表示为时间衰减因子，可以表示为

其中，f(m)的值大小代表共识次数与当前的共识轮次的远近，与当前共识轮次距离越远，时间衰减较大，对节点的动态评价影响越小。

基于节点信任评估模型，根据节点以往的行为对其进行信任度评估，并更新节点的信任度。选取信任度值高的节点作为共识过程的主节点，保证共识顺利进行，使网络环境的可靠性得到提升。

通过上述对原始PBFT共识算法共识过程的描述，可以看出系统对网络节点之间的通信要求较多，导致通信复杂度较大。在准备阶段和确认阶段，需要进行两次全网通信，才能保证达成共识，通信的复杂度为O（N2）。在节点数量较少的网络中，原始PBFT算法在延迟、资源需求等方面尚能体现较好的性能，但当系统中节点规模较大，其通信的复杂度是系统不能承受的。因此，对原算法进行改进，使其能应用到较大规模的网络系统中，提高系统安全性。假设所研究的区块链网络中节点数个数为N（N≥4，N∈N+）。

基于无线网络定位技术，可以获取对象的空间位置信息，并将其投影到二维空间中，获得节点的无线网络坐标（Wireless Network Coor⁃dinates，WNC），节点 i的坐标表示为（xi，yi），节点 i，j之间的距离表示为 d（i，j）：

通过改进的K-means算法对网络中的节点进行聚类，并采用信任度评估模型选取信任度较高的前n位节点来作为初始的中心节点，然后形成n个共识小组，经过信任度评估，选取可靠的节点作为各共识小组的主节点，如图2所示。

针对基于信任评估模型的双层PBFT系统，提出一个新的共识协议，其中第一层的副本节点表示为，上标1表示的是层号，下标i表示副本节点索引。通过对节点历史行为进行信任度评估选取的可靠的主节点，作为相应的第二层副本（）节点的主节点，一个主节点和它相应的副本节点一起，形成一个共识组，共同组成树状的拓扑结构，并假设第一层节点能够顺利达成共识。

当每个共识小组达成共识，组内节点会给此小组的主节点发送消息，而不是对客户端进行回复。对应的主节点收集回复消息，并代表共识小组将其发送给客户端，如图3所示。当网络结构发生改变的时候，进行更新操作。

4.1 客户端

客户端c开始发送一个请求消息R=给主节点。其中，o表示操作，t是时间戳，时间戳按照时间顺序排列，越往后时间戳的值越大。请求消息被送到副本节点，副本节点的标识从先前回复的视图号中提取。在接收请求时，主节点广播消息使用下面所述的协议。

所有共识小组的主节点直接向客户端发送回复消息。其中，v是当前视图号，i是副本节点，r是执行结果，rc是相关证书，GP描述副本节点的分配情况。

假设第一层有q个副本节点，第二层有Z-n个副本节点，在共识组中错误副本节点的数量是fw（区别于f）。如果主节点收到了来自同一共识组的有效回复fw+1，则该共识组就达成了共识。当超过一半的共识小组给出相同的应答时，就认为达成共识。客户端只接受来自共识组主节点的结果，要保证至少有一半是一致的。

4.2 第一层共识协议

第一层的共识过程，如图4所示。首先，客户端c向主节点发送请求消息R=，并对该请求和客户端的身份进行验证。验证通过，主节点将序列号α赋给R，然后向其他节点广播预准备消息进入预准备阶段。当其他副本节点接收到预准备消息，如果同意主节点分配给该请求的序列号，进入准备阶段。其中d为R的摘要（上标是为了区分第一层的pre-prepare1预准备和第二层的pre-prepare2预准备）。

第一层中的副本节点接受来自主节点的pre-preparel消息，然后副本节点广播准备消息<，Voteti>，其中 Voteti是节点i在区块中投出的赞成票，Votefi表示反对票。收到的预准备消息和准备消息将写入消息日志。在同一时刻，可能会有多个节点在进行这个过程，节点有可能接收到其他节点发送的prepare消息，当前节点会验证这些消息和自己发出的prepare消息的d，α，v，Voteti是否一致。在一定时间范围内，某节点收到2f+1（超过2f）个其他节点的prepare消息，表示prepare阶段已经完成。

对于准备好的副本节点，它们会广播确认消息<< commitl，d，α，i，v>，voteSeti>，如果当前节点（包括主节点）收到2f+1来自其他共识节点的commitl消息，同时将该消息写入本地消息日志中，验证通过，表示共识达成。其中，voteSeti表示节点i的投票集合。

副本节点会将回复消息发送给它们小组的组长，即第一层的主节点。副本节点暂停执行，并在第二层启动另一轮协议。主节点通过检查超过一半的组成员回复一致的reply1消息（包括它自己）来确认这个组成员已经达成一致。每个共识小组的组长收集reply1并形成一个回复证书rcl（reply-certificate）。

共识过程完成后，主节点用对客户端进行回复。

4.3 识别拜占庭节点

在共识过程中，设置了投票机制。如果系统在t1之前没有达成共识，每个共识节点会在区块上广播自己的投票，然后广播收到的投票集合。假设，节点i是共识过程中的一个拜占庭节点，当它发送一个<，voteti>消息发送给共识节点j，但一个<，votefi>消息发送给共识节点k。然后在共识节点j和k发送的 commit1消息中，可以看到 Voteti∈VoteSetj而Votefi∈VoteSetk，所以每个共识节点可以通过比较它从其他共识节点接收到的commit1消息来识别拜占庭节点。

4.4 第二层协议

信任度值较高的节点被选为主节点，主节点会把新的预准备消息广播给副本节点，实现了另一轮PBFT协议。当再次提交请求时，所有的共识小组成员以4.2节中类似的方式回复主节点。主节点在同一共识组中广播一个类似于给副本节点，其中 ccl是 commit-certificate1、v、α 和 R 来自前一个进程。如果满足第一层协议中所述条件，共识小组中的副本节点将会接受该请求。

在收到有效的pre-prepare2消息时，共识小组中收到预准备消息的副本节点，会广播消息给同一共识组中的所有其他副本节点。在prepare2阶段，每个副本节点收集2fw消息，其中包含匹配的序列号α、视图v和请求R。与接收到的pre-prepare2消息一起，它形成一个定额准备证书certificate2，表示此副本节点已准备好请求。

准备好的副本节点和共识小组的主节点广播并收集具有相同视图、序列和摘要的commit2消息。这些commit2形成commit-certificate2。然后副本节点执行已提交的消息。执行后，所有小组成员向其组长（小组的主节点）回复结果，组长以第一层中类似的方式向客户端回复结果。

4.5 共识小组间共识

共识小组中的主节点代表第二层中所有节点进行小组间的共识，共识过程有准备阶段、确认阶段两个阶段。

共识小组的主节点向其他共识小组的主节点发送准备消息。当其接收到2f个准备消息，并验证通过就会进入确认阶段。各个共识小组的主节点向其他共识小组的主节点发送确认消息。当各个共识小组的主节点都收到了至少2f+1个正确的确认消息，表示共识小组之间达成共识。

在原PBFT共识算法中，准备阶段和确认阶段都需要进行全网广播通信，在这个过程中每个节点需要通信N−1次，完成一轮共识所需要的通信次数为2N（N−1），当节点数量很大，将给通信网络带来较大的负担。

设系统中参与共识过程的节点个数为N，第二层共有Z个节点。第一层节点个数为N−Z（N−Z≥4），Z较大时，可忽略不计。因此，将重点对第二层中通信次数进行分析。二层中总节点数为Z（N≈Z），把Z个节点分为n个共识小组，假设每个小组内节点数量为，共识算法所需的通信次数具体分析如下，如表1所示。

为了评估改进共识算法的性能，基于Java编程语言对T-PBFT和PBFT的共识流程进行了仿真模拟。实验环境为Intel Xeon Gold 6148 CPU@ 2.40 GHz 2.39 GHz（2个处理器）和16 GB内存操作系统为64位Win10。实验结果用Matlab对数据进行了处理。实验分别测试了总节点N为40、50、60、70、80、90两种共识算法的耗时和吞吐量。为了减少实验误差，实验重复进行了10次最终取平均值。本节从通信开销、共识过程的耗时和吞吐量三方面对两种算法进行对比。

6.1 通信开销分析

PBFT和T-PBFT两种共识算法的通信次数比值C，n为共识小组的数量，如图5所示。PBFT共识算法是通过节点进行全网广播，进行信息的传递，将会大幅度消耗系统中通信资源。通信开销作为算法效率的指标之一，通过对两种算法对比，验证改进算法可以提高共识效率，减少通信资源的浪费。

经过分析可得，节点总数为N，没有对节点进行分组时，两种算法的通信次数是相同的。当节点总数不变，共识小组数量增加，每个共识小组内的节点数量减少，T-PBFT共识算法能够在小范围内达成共识，与原PBFT共识算法相比可以有效地减少系统中的通信次数。当分组数量达到最大，共识小组数量增多，同时要进行组内和小组之间的共识，会导致通信次数增多。当共识小组达到和节点总数一致时，与原PBFT共识算法通信次数将会再次达到一致。但从整体来说，T-PBFT共识算法所需的通信次数要小于原PBFT共识算法。

6.2 共识过程耗时分析

共识过程的耗时是指从共识过程开始到共识过程完全结束所需要的时间。为了对比两种共识算法的共识耗时，进行了10次的独立对比实验，对改进的共识算法和原始的PBFT共识算法单次共识的耗时进行了记录，如图6所示。

从图中可以看出，通过10次重复实验计算出PBFT单次共识的平均耗时为591.6 ms，改进共识算法单次共识的耗时为447.2 ms。通过实验可以看出，改进的共识算法的单次共识耗时比原始的PBFT共识算法提升了25%。

6.3 吞吐量分析

吞吐量是指在该系统中单位时间内处理交易的数量，系统处理交易的能力高低取决于吞吐量的大小，吞吐量越大说明处理交易的的能力越高，反之亦然。吞吐量计算公式如下：

其中，transactionsΔt是系统在共识过程中处理交易的数量，time是系统处理交易所需要的时间。两种算法的对比方案，在相同的网络测试环境中，节点个数分别设置40、50、60、70、80、90六组数据进行对比。

原PBFT共识算法，系统中的吞吐量受节点数量影响较大。改进的共识算法，将系统中节点划分为n个共识组，首先在共识组内进行共识，然后再由共识小组的主节点之间进行共识组间的共识，仅需要n个共识小组中的主节点参与，有效减少了通信的开销，要优于原共识算法中的吞吐量。在节点数量较大的情况下，与原算法相比也会有较高的吞吐量，如图7所示。

本文针对原PBFT共识算法存在的问题，提出了基于信任度评估模型的PBFT共识算法。在第一层的共识过程中，可以根据节点收到的投票结果，识别出拜占庭节点，减少了共识过程中恶意节点作恶的行为。根据系统中节点的历史行为，利用信任评估模型分别从节点动态行为和静态行为两方面进行评估，选取可靠节点作为第二层共识小组的主节点，防止共识中的主节点是恶意节点，这有利于减少系统的通信开销。通过实验验证了该改进算法的有效性，在网络稳定的情况下，可以以较少的通信量达成共识。对PBFT共识算法的不断改进和优化，能够使其应用在各大联盟链平台。

此改进的共识算法存在一定的不足之处，划分共识小组的组内成员数量在某范围内，效率能达到最高。在未来工作中，将对其继续研究，并对信任评估模型进一步完善，提高系统的安全性。