基于平均稳定度的自适应PBFT算法改进

2022-06-16张世政

现代计算机 2022年7期

张世政，刘勇

（网络体系构建与融合北京市重点实验室，北京邮电大学信息与通信工程学院，北京 100876）

0 引言

“中本聪”提出的比特币，成为区块链技术的第一个成功应用的案例，自此，区块链技术开始进入大众的视野，被人们所熟知。区块链技术是一种特殊的分布式数据库，它结合了去中心化、信息加密、共识算法等多种技术，具有去中心化、不可篡改、可溯源等特征。按照应用情况，可将其分为公有链、联盟链和私有链三种。目前，区块链技术已得到极大发展，其应用场景越发广泛，在诸多领域影响深远，其在新技术变革中的重要性日渐显著。

共识算法作为区块链的核心技术之一，影响着其安全性和整体性能。目前应用较为广泛的共识算法包括工作量证明机制（proof of work，POW）、权益证明机制（proof of stake，POS）、授权权益证明机制（delegated proof of stake， DPOS）和实用拜占庭容错机制（practical byzantine fault tolerance，PBFT）等，在实际应用中，由于联盟链和私有链中的节点只有经过授权才能够加入到网络当中，因此具有更高的安全性和实用性，PBFT 共识算法由于能够有效地解决网络中的拜占庭将军问题，保证了网络可靠性和稳定性，已成为联盟链和私有链中应用最广泛的共识算法之一。但PBFT 算法的劣势也极为明显，在PBFT 共识的过程中，随着网络中节点规模的扩大，共识的时延以及通信复杂度急剧上升，从而导致共识效率较低，并且消耗大量的信道资源。PBFT算法缺少节点评估机制，不能灵活地对网络中的节点进行区分。另外，其轮流当选的视图切换策略也会影响系统的安全性和共识效率。

对于PBFT 算法的改进工作已有多种方案，但始终缺乏考虑网络整体情况、自适应的优化措施。为了解决目前PBFT 算法存在的诸多问题，本文旨在设计一种具有一定自适应性的优化算法，结合网络所有节点的整体情况，从节点评估、自适应共识节点选择等方面进行创新与改进，提升PBFT算法性能。

1 相关工作

针对PBFT 存在的效率低，时延高的问题，已有多位学者提出了改进措施。例如，文献［15］提出的基于投票的拜占庭容错算法，将网络中的节点划分为客户端、从节点和主节点三种不同的职责类型，由主节点进行投票和评分来改变每个节点的类型。文献［16］提出一种基于特征信任模型的优化实用拜占庭容错共识算法，它是一种多阶段共识算法，通过节点之间的交易来评估节点信任，从而选择网络中质量较高的节点来构建共识群。文献［17］提出基于可靠性评估的改进拜占庭容错算法，根据评分将节点划分为诚实、故障、恶意三种状态，并根据节点可靠性选择主节点组建共识节点群。上述改进措施均采用依据分数来选择共识节点的机制，具有一定的优化效果，但在面对恶意节点数量较少甚至没有恶意节点的系统中，参与共识的节点数量过多，优化效果有限。文献［18］针对PBFT 算法的改进，根据评分将节点划分为共识节点、候选节点和预备节点，并规定共识节点数量固定为总节点数量的2 3。但当恶意节点较多时，共识节点集群数量保持不变，共识失败的概率较高，甚至面临连续共识失败的风险。

以上方法都不能根据具体的共识场景自适应地选择和调整最佳的共识节点集群，针对这种现象，结合联盟链的实际特点，本文提出一种基于平均稳定度的自适应改进PBFT算法（average stability byzantine fault tolerant algorithm，AS-PBFT），引入平均稳定度的概念，依据平均稳定度控制参与共识的节点，优化PBFT 算法，以此来降低共识时延和通信复杂度，并且能够一定程度地反映系统的共识情况，及时调整共识节点所占的比例，针对不同的恶意节点情况，选择最佳的共识节点集群方案，避免连续共识失败等安全性问题。

2 AS-PBFT算法

2.1 AS-PBFT算法概述

联盟链是由多个组织或机构参与的区块链，通常情况下，每个节点都有与之对应的实际机构或组织，故在实际的应用场景中，节点产生作恶行为的概率是不同的，会有一部分稳定性强的节点，也会存在相对稳定性较差的节点。基于这种实际情况，本文提出了一种改进方案，其整体结构如图1所示。

图1 AS-PBFT算法整体结构

基于联盟链的实际特点，本文提出的算法主要分为基于历史表现评估机制、自适应共识比例控制机制和优化的一致性交互协议三部分。首先对所有节点增设稳定系数，共识开始后，由主节点按照基于历史表现的稳定性评估机制，计算所有节点当前的稳定系数，此系数可以反应当前节点的稳定性。此后，本文引入整体稳定度的概念，通过自适应共识比例控制模块，计算当前系统的整体稳定度，根据计算结果，调整共识比例。共识集群确定以后，采用优化的一致性协议进行共识节点之间的信息交互，确定共识结果，标记作恶节点，完成共识。在存在恶意节点的区块链系统中，通过上述机制，便可根据网络中恶意节点的实际情况，进行评估优化，提高共识效率。

2.2 基于历史表现评估机制

为了解决PBFT 算法无法对节点进行评估的问题，提出了基于历史表现的稳定性评估机制。首先为所有节点增设稳定系数，在系统开始共识前，将每个节点的稳定系数初始化为50，并规定其下限为0，上限为100。增设共识状态表，此表格记录系统中每个节点近三次共识的状态，节点共识状态包括稳定、出错和没有参加共识三种，分别用0、1、2 表示，每一轮共识结束后，都将更新该表以及时反应节点的最新状态，对节点稳定系数的调整如表1所示。

表1 稳定系数调整

系统根据共识状态表来判断每个节点的历史状态，并将前三轮按照2∶1∶1 的比例进行权值分配，按照稳定系数的调整规则，计算对应三次的系数调整结果并进行累加，成为节点新的系数调整值。通过这种稳定系数调整机制，可以反映出节点的历史状态，从而对一个节点的稳定系数做出综合评估，削弱随机性带来的影响，更容易区分出恶化概率较高的节点，提升算法的稳定性和安全性。并且给没有参与共识的节点进行缓慢的加分，保证共识节点集群的动态性。

2.3 自适应共识比例控制

针对PBFT 算法随着节点数量的增多，共识时延上升明显的问题，提出自适应共识比例控制机制，动态调整参与共识的节点所占的比例。基于评估机制中设置的稳定系数，本文引入平均稳定度的概念，即网络中所有节点的平均稳定系数，计算方法如公式（1）所示，其中，A为第轮共识的平均稳定度，S代表节点第轮的稳定系数，ΔS代表节点第轮稳定系数的调整，代表总节点数。

由公式（1）计算每轮共识的平均稳定度，并且规定50 ≤A≤100，基于得到的当前整体的平均稳定度，采用公式（2）计算下一轮参与共识的节点数目，其中为计算所得的共识节点数量。

根据公式（2）可以得出，当平均稳定度为初始状态的50 时，全部节点都将参与共识，平均稳定度到达上限100时，计算得到的共识节点所占比例为2 3，并且按照规定，数量下限应该大于总节点数量的2 3，从而通过判断进行适当调整。由此可以得出结论，在网络中作恶节点较少，或者没有作恶节点时，共识节点的数目经过几轮调整以后，将会趋于总节点的2 3，并且在确定共识节点之前，先会将节点按照稳定系数进行降序排列，从而使得选取的节点都是稳定系数高的。

在本文提出的优化方案中，由于减少了共识节点的数量，故在恶意节点较多的情况下存在共识失败的可能性，控制机制在面对共识失败的情况下，会将所有节点的稳定系数减20，则平均稳定度A下降20，进而通过公式（2）计算得到的下一轮共识节点的数量就会增加，对共识失败的消息进行重新共识，降低共识失败的概率。此后，再通过评估机制进行慢恢复，避免连续失败的情况发生。

通过本文提出的共识节点选择机制，能够保证绝大多数情况下，参与共识的节点是稳定性强的节点，稳定性较差的节点则会逐渐剔除出共识集群。因此，在恶意节点数量较少的情况下，共识失败的概率很低，共识节点数量趋于总节点数量的2 3，而在恶意节点数量较多的情况下，也能自适应地对共识节点集群进行控制，避免连续共识失败。因此，本文中的共识比例控制机制可以针对不同情况进行自适应的动态调整，以得到最优的共识节点群，提高共识效率。

2.4 优化一致性协议

2.4.1 优化视图切换策略

对于传统的PBFT 算法的一致性交互协议，在进行视图切换时是按照公式（3）进行新的主节点选择的。

其中代表新选择的主节点的编号，代表上一次主节点的编号，为总的节点数量。可以看出，传统的一致性协议的视图切换是一种轮流当选的方式，对于存在恶意节点的系统中，这种选举方式是极其随意的，并且也会面临着多个恶意节点连续当选为新的主节点的风险。

针对这个问题，结合本算法提出的基于历史表现的节点评估机制，对一致性协议的视图切换策略进行改进，在共识过程中需要进行视图切换的时候，将每个节点的稳定系数作为主要参考指标，将节点的历史表现考虑进来，按照稳定系数降序的顺序，进行新的主节点的选择。利用这种视图切换策略，可以有效地降低恶意节点当选为主节点的概率，减少视图切换的频率与次数，进一步提高算法的共识效率。

2.4.2 恶意节点筛选策略

为维护系统的共识状态表，向评估机制提供稳定系数调整的参考依据，故在改进后的一致性交互协议中，对有恶意行为的节点进行筛选和记录。

（1）本文为每个节点增设共识集群表，记录当前共识过程中，参与共识的节点的编号集合。该表在每轮共识开始之前，由主节点根据基于历史表现的评估机制和共识比例控制机制进行更新和调整，主节点在Pre-prepare 阶段将该表添加至Pre-prepare 消息中，分发给每个节点，节点根据共识集群表确定后续的消息广播和接收的节点范围。

（2）在全广播消息交互阶段，每个节点需要收到2+1 条一致消息才能认为投票通过，进而在投票过程中，记录收到的不一致消息的来源节点编号，在回复阶段，将该消息一起发送给共识信息的请求端。

（3）共识请求端节点验证共识成功以后，将收到的恶意节点集合进行取并集处理，得到本轮筛选出的恶意节点集合，将其发送给主节点，由主节点根据该集合对所有节点稳定系数进行调整。

3 实验及结果分析

本文基于Java 语言构建一个多节点区块链系统，分别对PBFT 算法和本文提出的AS-PBFT算法进行实现和验证，记录分析AS-PBFT 算法在共识过程中的变化情况，从共识时延和通信量方面与PBFT 算法进行比较，并且对本算法的自适应性进行实验验证分析。

3.1 AS-PBFT算法共识过程分析

本文提出了基于平均稳定度来控制共识节点比例的优化思想，为贴近联盟链中节点的实际场景，设定系统中节点作恶的概率不同，选择1 3 的节点设置其作恶概率为80%，再取1 3的节点规定其作恶概率为50%，另外的节点作恶概率为10%，并且每一轮恶意节点的总数不变。因此，在恶意节点数量较少的情况下，共识失败的概率很低。选定总节点数为16，作恶节点数为4，其前十次共识过程中，系统的平均稳定度和共识节点数的变化如图2所示。

图2 平均稳定度和共识节点数量变化

根据图2可知，第一轮平均稳定度为初始值50，所有节点都参与共识，随着共识过程的进行，基于历史表现的评估机制对所有节点的稳定系数进行评估，平均稳定度逐步上升，进而参与共识的节点数量呈下降趋势，最终数量稳定在11 个节点。另外，恶意节点数量不同，对平均稳定度增长速率会产生影响，如图3 所示，在恶意节点数量较少的情况下，其数量越少，平均稳定度上升越快，共识节点数量达到下限的时间就越短。

图3 不同数量作恶节点下平均稳定度变化情况

3.2 共识时延

共识时延为算法开始进行一轮共识到共识结束所消耗的时间，反应了共识算法的效率。本文分别对PBFT算法和AS-PBFT算法的共识时延进行评估，在恶意节点为(- 1) 3 的情况下，对不同节点数分别进行多次实验，计算其进行十轮共识以后单次共识消耗时间的平均值，对比结果如图4 所示。随着共识节点数量的增加，两种算法的共识时延都呈上升趋势，但相较于PBFT 算法，本算法参与共识的节点数量趋于总节点数量的2 3，并且发生视图切换的概率小很多，因此，在不同节点数量的情况下，共识时延均明显减小。

图4 PBFT和AS-PBFT算法共识时延对比

3.3 通信开销

通信开销是指完成单次共识所需要通信的次数，分别对PBFT和AS-PBFT算法，在恶意节点为(- 1) 3 的情况下进行多次实验比较，计算其第十轮共识以后的单次通信量的平均值。两种算法的通信开销如图5所示。

图5 PBFT和AS-PBFT算法通信开销对比

本文对视图切换时主节点的选择策略做了优化，将视图切换的概率大大降低，减少了因视图切换造成的通信开销。并且，根据共识比例控制机制，减少了参与共识的节点数量，故其单次共识的通信量明显降低。

3.4 自适应分析

本文提出的AS-PBFT 算法，能够根据作恶节点的数量和共识情况进行自适应调整，故设置两组不同作恶节点数量的实验，进行对比分析。

（1）将系统中的恶意节点数量设置为0，模拟没有节点作恶的情况，与常见改进方法中所采用的分数选择机制来选择共识节点的方式进行多次实验对比，记录其平均共识时延。在没有节点作恶的情况下，最终所有节点的稳定系数都将达到上限100，若采用分数选择机制选择节点，全部节点都将符合要求参与共识，与传统的PBFT 算法类似，AS-PBFT 算法会根据公式（2），将共识节点的数量维持在总节点数量的2 3 左右。如图6 所示，本文提出的基于平均稳定度选择机制的共识时延更低，更加适用于没有作恶节点的情况。

图6 分数选择机制和平均稳定度选择机制共识时延对比

（2）设置系统中恶意节点的数量为(- 1) 3，因减少了参与共识的节点数量，故当恶意节点数量较多时，便有可能产生接收到的一致性投票数量达不到2f+1 的情况，从而导致无法成功完成共识，此时就需要重新对该信息进行操作。在这种情况下，将基于平均稳定度选择机制和常用的改进方案中采用的固定前2 3 比例节点作为共识节点的机制进行对比，对其分别进行100 轮共识，并进行多次实验，求得失败次数的平均值，如图7 所示。因ASPBFT 算法采用基于平均稳定度的控制机制，逐步降低其共识节点比例，并且一旦出现共识失败的现象，会立刻降低系统的平均稳定度，增加共识节点数量，以降低失败概率，故其失败次数明显小于采用固定前2 3节点作为共识节点的方式，并且避免了连续共识失败的可能，增强了系统的安全性。因此AS-PBFT 共识算法具有更强的自适应性。