高效的实用拜占庭共识算法*

王薛平

（西安邮电大学计算机学院 西安 710121）

1 引言

区块链技术［1］因具有去中心化、防篡改等特点被广泛应用到金融、物联网和贸易管理中，是将数字加密、智能合约［2］、共识机制等技术结合起来构建而成的一种分布式的系统架构，由于去中心化的特性，应用领域［3］也越来越广泛。区块链的网络架构一般采用点对点网络［4］架构，所有节点的地位都是对等的，并且以拓扑结构相互连接，节点间采用中继转发的模式进行通信。由于没有中心化的参与，所以节点间的一致性由共识算法来保持。

区块链的共识算法［5］是为了解决状态一致性和拜占庭将军问题。早先为了解决拜占庭将军问题，提出了拜占庭容错（BFT）算法［6］，依靠节点间传递消息对提案达成共识，由于消息复杂度的问题使得BFT 的实用性较低。1999 年，Castro 等提出实用拜占庭容错共识算法（PBFT）［7］，在BFT共识算法的基础上进行改进，降低了复杂度，在实际应用中有了较高的可行性。

PBFT 算法［8］被应用至联盟链中，但是相对应的也会产生一些缺陷，首先PBFT 算法的验证阶段较为繁琐，出于安全性的考虑会对准备阶段的信息进行重新验证，以防止视图更改后出现信息不一致的情况。在联盟链的环境中，会对每个节点进行认证以及监督，网络较为稳定，视图也不会频繁发生变化，即使在视图发生变化后增加同步和验证过程也同样能够确保数据的一致性［9］，从而可以优化共识过程。

本文针对上述问题，结合区块链应用的特点，提出一种改进的PBFT算法。本算法淡化了原算法中主节点的功能转化为客户端直接向网络中的节点通信，由网络中的节点来进行广播。在其他节点收到请求消息后，进行消息的验证，其次通过request和prepare-response两个阶段来完成共识并且减少了节点间的通信开销。

2 背景及相关工作

在目前区块链的共识算法中工作量证明（PoW）［10］以及权益证明（PoS）［11］主要应用于公有链，前者依靠算力后者则依靠数字货币来进行共识操作，由于资源消耗较大以及实际场景没有数字货币等问题，导致了实用性较差的结果。方轶等提出一种基于环签名的PBFT 共识算法改进方案［12］，通过特殊的签名方式有效提高了效率以及吞吐量，但是通信开销的问题并没有得到解决。张仕将等提出了一种基于Gossip协议的拜占庭共识算法［13］，通过Gossip协议进行通信提升了算法的安全性，但是根本的效率问题并没有改善。徐浩等提出动态实用拜占庭容错［14］，该协议允许节点的动态加入和退出，具有很好的安全性和鲁棒性，在效率方面的表现较差。

3 优化后的EPBFT算法

针对PBFT 算法中通信开销过大、效率低下的缺点，本文提出了优化后的EPBFT 算法。主要应用场景为节点相对较为固定的联盟链，根据联盟链的特点对传统的PBFT 算法进行了改进，优化其共识过程，在不影响其安全的前提下，提升了效率并且减少了网络开销。

3.1 算法设计

在联盟链中，每个节点都有较高的信誉度，网络运行环境相对稳定，在此情景下通过选取主节点再进行广播消息的方式极大的影响了效率。因此本文算法通过数据备份和验证阶段代替选取主节点，可以保证安全性［15］的同时提高了效率。并且改变客户端向主节点提交请求的过程，在联盟链中所有节点都可以将消息广播至整个网络［16］。

3.2 算法过程

系统初始化后，网络中的节点开始进行数据备份和验证。为了满足共识的要求，每个节点需有相同的区块数据、视图编号、区块高度等。完成验证和备份后，系统进入请求阶段和准备响应阶段，以下为算法具体步骤：

Step 1：系统初始化，进行数据验证和备份阶段，每个节点从链最长的节点开始备份，获取后进行验证再将其保存。

Step 2：超过2f+1 个节点备份成功时验证成功。

Step 3：事务发起者C 节点向其他节点广播已签名的事务。

Step 4：各节点接受到消息后，验证其合法性，进入请求阶段，当累计数量每个节点超过2f+1时对其他节点进行广播。

Step 5：进入准备响应阶段并验证消息合法性，如果合法返回C 节点进行缓存，等收到足够数量的交易后，生成一个区块。

其算法的流程图如图1所示。

图1 EPBFT算法流程图

系统初始化后的备份和验证阶段，目的是通过备份使每个节点数据信息一致，验证获取数据的节点是否为恶意节点。

备份阶段：需进行备份的节点C1 向最长链节点C2 发送请求，待收到请求到检查视图编号是否一致。如果编号一致，则同步消息到C1，如果不一致，根据其他节点拥有的不同数据块，将备份请求和对应数据区块发送至其他节点。

验证阶段：其他节点在收到最长链节点C2 发送的备份数据后，会验证其合法性。如果合法，将数据保存并把消息广播至整个网络。如果验证失败，将其丢弃并保存其他节点发送的验证结果。当节点C1 同步其他节点返回的消息数量超过2f+1时，可确保每个节点的信息状态一致。在验证完成后，每个节点将信息广播至整个网络进入共识阶段。

以下为具体的共识过程。

请求阶段：C 向其他节点进行广播，其他节点收到消息后，如果消息通过则进入准备响应阶段，如果未通过验证，表明C 节点可能为恶意节点需要进行验证并广播更改视图。

准备响应阶段：节点向其他节点广播准备响应消息，并保存请求和准备响应消息。当消息数量超过2f+1与其他节点一致，则该阶段完成。

4 实验分析

本节将通过通信开销、时延、吞吐量等指标对EPBFT 算法进行测试，并与原PBFT 算法进行对比以验证算法的实用性。

4.1 通信开销对比

1）PBFT通信开销

通过对前文的PBFT 算法进行分析，共识过程总通信次数为2n（n-1）。

更改视图时，通信的次数为（n-1）2。从其他节点收到视图变更后，发送变更确认信息至其他节点，此阶段通信次数为（n-1）。假设视图变更的概率为P时，通信的总次数为

C=2n（n-1）+Pn（n-1） （1）

2）EPBFT通信开销

上文对EPBFT 算法的共识过程分析可知通信次数为n（n-1）。

同步信息在数据同步验证阶段发送至其他节点通信次数为（n-1）。在同步验证的过程中，所有节点将信息发送到除自身之外的所有节点，该过程的通信次数为（n-1）2，同步完成后，所有节点将信息返回，通信次数为（n-1）。因此算法的总通信次数为

C=n（n-1）+P（n2-1） （2）

以4个节点、6个节点、8个节点为例，当不更改视图的情况下，测试其通信次数，实验结果如图2所示。

图2 通信开销对比图

基于以上分析，EPBFT算法的设计有效减少了共识过程的数据传输次数以及通信开销，且不减少系统的容错能力，提高了共识效率。

4.2 吞吐量对比

吞吐量指在单位时间内系统处理的事务数，用TPS（Transaction Per Second）表示。本次实验设置从客户端发出1000 条请求，在不同的节点数下记录每秒完成的交易数并进行对比，如图3所示。

图3 吞吐量对比图

通过对图3 的分析，在节点越来越多的情况下吞吐量缓缓下降，在对比后可知优化后的EPBFT算法远高于原PBFT 算法。平均吞吐量从原来的351TPS提高到696TPS。

4.3 通信时延对比

本次通信时延实验的对比在搭建的基于java的考试系统上进行，环境搭建在vmware 中，操作系统是ubuntu16.4。

图4通过查询考试结果信息为例，以40次查询结果为例，横坐标x 表示了第x 次查询，纵坐标t 表示查询时Fabric 的响应时间。实验结果表明，使用原PBFT 算法是时延均值为39ms，而使用优化后的EPBFT 时延的均值为30ms。相比较之下系统时延方面有较好的提升，使得用户拥有更好的体验。

图4 系统响应时间

5 结语

提出了一种基于PBFT 算法改进的EPBFT 算法。PBFT 算法中选取主节点的过程，在不影响整体操作的情况下进行了省略，极大地提高了数据同步以及验证的效率，同时优化了共识过程。通过优化使得EPBFT算法更适用于联盟区块链的环境。

通过实验可知，共识过程中通信开销从原来的2n（n-1）缩短至n（n-1），有效减少了通信开销。吞吐量从原来的351TPS 提高至696TPS。通过搭建的区块链平台进行测试，系统响应时延从原来的39ms减少到30ms。

在未来的工作中，可对算法的安全性进行提高，增加节点的动态添加功能，对算法进一步优化，提高算法的适用性。