GBFT：一种实用拜占庭容错算法改进方案∗

李 彬 张新有

（西南交通大学信息科学与技术学院 成都 611756）

1 引言

区块链作为数字加密货币的重要底层技术，最早于2008 年由化名为中本聪［1］的学者提出。区块链技术的去中心化、数据不可篡改、数据安全等特点，使得其在数字货币、物流溯源、数据取证和金融交易等领域都有很好的应用前景［2］。

当前，区块链发展成为三种差异化类型：公有链，联盟链，私有链［3］。其中，部分去中心化的联盟链得益于参与节点数量较为固定、网络规模较小、节点的信用度好等特点，具备了交易确认延迟低、吞吐量高、耗能小等优势，因此在近年来得到迅速发展。共识算法作为区块链中最为核心的技术，对区块链的整体性能表现有着直接的影响。现有的许多适用于公有链场景的共识算法，因为有着巨大的共识成本和算力开销，明显不适用于联盟链场景下的区块链［3］。2014 年，随着IBM 的联盟链项目Hyperledger Fabric 的推出［4］，人们把目光聚焦到了实用拜占庭容错算法（Practical Byzantine Fault Tolerance，PBFT）。

本文针对联盟链的应用场景，分析了PBFT 共识机制存在的不足，并基于PBFT算法的思想，提出了一种分级的共识方案（Graded Byzantine Fault Tolerance，GBFT），以期在系统的长期运行中达到更高的共识效率和吞吐量及更低的资源消耗。

2 共识机制

一致性问题是分布式系统面临的核心问题之一。分布式系统中如果仅存在非拜占庭错误，如网络延迟、节点宕机，可以通过Paxos［5］和Raft［6］等算法解决一致性问题。但是区块链网络作为一个低信任的分布式系统，节点之间属于互相不了解的参与者。受到利益的驱使，网络中还可能产生拜占庭错误［7］。拜占庭错误是指存在节点主动向其他节点发送错误信息的可能，拜占庭节点指可以产生拜占庭错误的节点。在一个存在拜占庭节点的系统中，需要使用有拜占庭容错能力的共识算法［8］。目前主流的区块链共识机制主要有工作量证明、权益证明、股份授权证明以及实用拜占庭容错算法等［9］。

2.1 工作量证明

工作量证明（PoW）的概念最早由Cynthia Dwork 和Moni Naor 在1993 年的论文中提出，主要用于解决当时日益严重的垃圾邮件问题［10］。几年后，Markus Jakobsson 和Ari Juels 正式提出了术语“Proof of Work”，并给出了PoW 的形式化定义［11］。在一个区块链网络中，必须有负责记录交易的节点存在，最简单的方法是进行随机选择。然而，随机选择会使系统随时暴露在可被攻击的环境中。因此，如果一个节点想要发布一个交易区块，就必须完成大量的工作来证明该节点几乎没有恶意攻击网络的可能性。一般来说，上述所谓的“工作”即计算机算力。工作量证明机制的优点在于算法简单、去中心化程度高、网络扩展性强、节点加入退出灵活。它的缺点是无用的工作量计算导致能源、算力等资源的严重浪费。此外，PoW 共识的效率较低，过长的出块时间和交易确认时间难以满足现实需求。

2.2 权益证明

权益证明（PoS）［12］试图通过将采矿能力与节点持有的权益相联系来解决PoW 中算力竞争的问题。PoS 的核心思想是持有较高权益的节点有更大的可能性来获得区块打包权。在使用PoS 机制的网络中，依然需要节点求解PoW 中类似的数学难题。但是每个节点面对的数学难题的难度是不同的，这个难度与节点持有的代币数量正相关。这意味着节点持有的代币数量越多，它所需要求解的数学难题的难度越低，那么该节点解出这个难题并获得区块打包权的概率也就越大。PoS 的去中心化能力、网络扩展性与PoW 相当，同时还有效降低了对资源的浪费。但是PoS 中存在的“无利害攻击”，“长程攻击”等问题也让PoS 的安全性备受质疑。

2.3 股份授权证明

股份授权证明（DPoS）［13］，可以看做PoS的一个变种，由Bitshares 的首席开发者Dan Larimer 提出并应用。它通过实施去中心化的民主方式，每个节点可以将其持有的权益作为选票投给一名代表。系统将选出得票较高的前N 个节点组成见证人网络。见证人网络中的节点使用专业运行的网络服务器，收集交易、打包区块，引导促进区块链项目的发展。在完成本职工作的同时，这些节点还可以领取区块奖励和交易手续费。DPoS 通过投票、选举降低了参与共识的节点数目，因此与POS、POW 相比，它具有更低的交易处理时延和更高的吞吐量。但是DPoS中存在的“超级节点”也让它的去中心化能力备受争议。

2.4 实用拜占庭容错

实用拜占庭容错（PBFT），最早由Castro等［14］在1999 年提出，是解决存在拜占庭节点的分布式系统一致性问题的通用方案。PBFT算法基于状态机复制原理（State Machine Replication）［15］，主要由三个协议组成：一致性协议、检查点协议以及视图更换协议。区块生成过程中，一致性协议用来保证全网所有的节点保存数据的一致性，其通过三阶段节点间的互相通信来实现；当运行一致性协议无法达成一致时产生超时事件，启动视图更换协议进行视图转换，以保证节点之间顺利达成共识；检查点协议主要有两个用途：一是定期清除节点的过期数据，以减轻存储压力；二是检查系统状态，将系统中的节点同步到一个相同状态。目前在区块链领域中，PBFT 共识机制主要应用于联盟链场景，例如hyperledger fabric（v0.6）、FISCO BCOS［16］等联盟链平台都在进行该共识机制的实际部署应用。

在PBFT 算法中，一个消息从发起到达成共识需要经过5 个阶段。图1 中，C 代表客户端，0、1、2、3 表示4 个参与共识的节点，其中节点3 为拜占庭节点。具体步骤如下：

图1 PBFT算法的一致性协议

1）request阶段：客户端发送请求到主节点；

2）pre-prepare阶段：主节点收到客户端请求后将其封装为一个pre-prepare 消息，然后将pre-prepare消息广播给从节点；

3）prepare 阶段：从节点收到pre-prepare 证书后将其封装为prepare 消息，并广播给其他从节点，从节点进入pre-prepared状态；

4）commit 阶段：当系统中存在f 个拜占庭节点时，要求系统中总节点数量不能小于3f+1。若一个节点收到包括自己节点prepare消息在内的2f+1 个prepare 消息后，则该节点进入prepared 状态，并向其他节点广播commit消息；

5）reply 阶段：节点收到包括自己节点的commit消息在内的2f+1个commit消息后进入commited状态，并向客户端返回reply响应消息。

传统拜占庭容错算法由于指数级别的时间复杂度而难以在实际系统中应用。PBFT算法则将时间复杂度降到了多项式级别，还能提供1/3 的容错性。但PBFT算法的缺点也很明显。一是算法在收到客户端请求之后，需要经过5 个阶段才能达成共识。其中prepare阶段与commit阶段是全节点参与的广播过程，使得共识过程产生巨大的通信开销；二是PBFT算法中的主节点由所有节点依次轮流担当，这种主节点选择策略过于随意，使得主节点身份可以被轻易预测，增加了其被攻击的风险；三是算法中的每个节点都维护了一个固定的节点列表，缺少节点的加入、退出机制，不能灵活应对网络规模的动态变化。

不同的共识算法在不同的评判项目中，具有不同的表现。对上述4 种共识算法，从高往低分别用5分至1分对各项评测功能点做出评测，结果如表1所示［17］。

表1 四种共识算法性能比较

除以上四种经典共识算法外，近年来还涌现了多种新型共识算法，如Algorand［18］、Omniledger［19］、Rapidchain［20］、2-hop［21］。这些算法本质上都是多种经典共识算法融合的产物，它们不约而同地体现了同一个共识算法改进思路：基于实际应用场景对处理效率和规模的不同需求，将各具优势的共识算法相融合，取长补短，从而在各项指标中取得最佳平衡。这也是本文提出的改进方案的基本思路。

3 改进方案GBFT

由图1 知，PBFT 算法的一致性协议中有两个阶段（prepare 阶段和commit 阶段）的全节点广播。随着节点数量的增加，网络中的通信开销会增长迅速，影响算法的共识效率。针对此问题，结合联盟链的特点，本文引入了非拜占庭容错的共识协议，以降低节点之间的通信开销；为了配合非拜占庭容错的共识协议，同时提出了一种基于节点行为的选举制度；在非拜占庭容错协议、选举机制、PBFT 容错协议的基础上构建了三级共识机制。

3.1 整体思想

根据模块功能的不同，可以将一个使用PBFT共识机制的区块链系统抽象为四个层次［22］（图2）：应用层、执行引擎层、共识层、数据层。其中，应用层代表各种基于区块链网络的应用；执行引擎层提供了区块链网络的运行时环境；共识层定义了系统所使用的共识协议；数据层定义了区块、交易等结构以及与这些结构相关的增删改查操作。通过2.4节的分析可知，PBFT 共识机制的性能瓶颈主要在于准备阶段和提交阶段的两次全节点广播。随着区块链网络中节点数目的增多，网络通信量会急剧增长，从而增加带宽的压力，导致了交易确认时间长、吞吐量低、网络扩展性差等问题。

图2 使用PBFT共识机制的区块链系统架构

针对PBFT 共识机制的性能瓶颈，本文提出以下三点举措解决问题。

1）引入非拜占庭容错的一致性协议。在联盟链场景中，节点都是经过一定准入机制才能加入区块链网络，这使得联盟链中的节点相比公有链中的节点有更高的可信度。据此可以认为联盟链中大多数情况下是没有拜占庭节点的，此时在网络中运行拜占庭容错的一致性协议并不是十分必要。因此，可以在在共识层引入一种非拜占庭容错的一致性协议。系统根据网络中节点状态来选择执行不同的一致性协议：当参与共识的节点中不存在拜占庭节点时，运行非拜占庭容错协议；当使用非拜占庭容错协议无法达到一致时，运行PBFT 的一致性协议。

2）设计基于节点行为的选举机制。引入非拜占庭容错协议的同时也引发了另外一个问题，即网络中存在拜占庭节点时，使用非拜占庭容错协议无法达到一致，那么就需要切换到PBFT 的一致性协议。如果在存在拜占庭节点的网络中使全节点都参与非拜占庭容错协议，实际上共识机制不仅会退化为普通的PBFT 算法，还会因为频繁的协议切换带了更大的共识成本。因此需要设计一种选举机制，选出部分节点参与非拜占庭容错协议，且选出的节点应当尽量避免包含拜占庭节点。

3）提出三级共识机制。在计算机结构的三级存储体系中，计算机的存取速度接近于缓存的速度，而存储容量由硬盘所决定。基于这种思想，提出三级共识机制。首先由选举出的部分节点参与非拜占庭容错协议作为第一级共识，第一级共识无法达成一致的情况下进入第二级共识。第二级共识是部分节点参与的PBFT 一致性协议，当第二级共识无法达成一致时进入第三级共识。第三级共识就是原始的全节点参与的PBFT共识。最终希望达到的效果就是整个网络的共识效率由第一级共识决定，而系统的容错性由第三级共识决定。

综上，在共识层应用GBFT 算法的区块链系统架构如图3所示。

图3 使用GBFT共识机制的区块链系统架构

3.2 改进方案设计

3.2.1 非拜占庭容错协议

引入非拜占庭容错协议的目的在于简化PBFT共识协议中prepare阶段和commit阶段中的全节点广播通信，本文采用了参考文献［23］中提出的简化一致性协议，如图4所示，具体内容为

图4 非拜占庭容错协议

1）主节点广播pre-prepare消息到从节点，从节点验证消息内容后向主节点回复确认消息；

2）主节点收到所有从节点的确认消息后，广播confirm 消息到从节点，从节点验证消息内容后向主节点回复确认消息；

3）主节点收到所有节点的确认消息则代表达成共识，否则意味着共识失败。

3.2.2 选举机制

在引入非拜占庭容错协议的系统中，系统优先选择非拜占庭容错协议作为共识协议，当非拜占庭容错协议无法达成一致时再切换到PBFT的一致性协议。为了避免不同协议频繁切换带来的额外开销，我们希望每次参与非拜占庭容错协议的节点都是诚实节点，为此系统中设计了一个基于节点行为的选举机制。

在区块链网络中，每个节点都由一个信用分属性。所有节点被划分为两类：共识节点、非共识节点。共识节点与非共识节点的比例为1∶1。选举模块选取共识节点时遵循两个原则：一是信用分高的节点优先；二是信用分相同时编号较小的节点优先。共识过程中，首先由共识节点参与一级共识，若达成一致，则每个参与节点可获得2 信用分；若无法达成一致，参与节点扣3 信用分，然后进入二级共识。若系统执行二级共识达成一致，每个参与节点获得1 信用分；若无法达成一致，每个参与节点扣2 信用分，然后进入三级共识。三级共识执行的是全节点参与的PBFT 一致性协议，三级共识中不再对节点信用分进行增减。如此往复，节点会因为自身行为而获取、损失信用分，分值代表了节点的可信度。图5 是一个节点的信用分的状态转换图，其中X代表一个节点的信用分。

图5 节点信用分状态转换图

共识节点选举机制将会在以下三种情况发生时被触发：

1）区块链系统启动的初始时刻。此时所有节点信用分为0，根据信用分相同时编号较小的节点优先原则，选举模块将选择编号较小的前50%节点作为共识节点。

2）发生了共识级别转换。若某次请求的共识过程中发生了共识级别转换，意味着共识节点集合中存在拜占庭节点。最坏情况下，该请求依然可以通过三级共识在各节点间达成一致，然而在下一个请求到来时共识节点集合中还是存在拜占庭节点，那么通过一级共识始终无法达成一致，总是要执行共识级别转换，带来额外的资源消耗。因此，每当发生了共识级别转换，在当前请求完成后，都要重新进行共识节点选举。

3）共识节点强制选举计时器超时。共识节点长时间运行一级共识会使这些节点始终处于忙碌状态，而非共识节点无法获得信用分，没有上升通道，也浪费了算力。为了避免这种情况的发生，在系统中设定一个共识节点强制选举计时器。当该计时器超时，将所有节点信用分清零，强制进行共识节点选举。共识节点编号ni由式（1）和式（2）计算得出。

其中：timestamp为共识节点强制选举计时器超时时刻的时间戳，N为节点总数。

3.2.3 三级共识机制

为了进一步提高共识效率与网络扩展性，结合非拜占庭容错协议、PBFT 一致性协议以及选举机制，提出的三级共识机制流程如图6所示。

图6 三级共识算法流程

具体内容为

1）选举产生共识节点。

2）接收来自客户端的交易请求。

3）共识节点执行一级共识。若达成一致，进入6）；否则，进入4）。

4）执行共识级别转换，共识节点参与二级共识。若达成一致，进入6）；否则，进入5）。

5）执行视图转换，所有节点参与三级共识。若达成一致，进入6）；否则，继续执行5）。

6）所有节点接受共识结果，执行客户端请求。7）更新每个节点的信用分。

8）若发生了共识级别转换，则选举产生新的共识节点。

9）一次请求结束。

4 实验场景及结果分析

本章从吞吐量、交易确认时延和容错性能等三方面分别对原始PBFT 和GBFT 进行测试。通过对照，验证了改进方案的有效性和可用性。

4.1 实验场景

租用了一台云服务器作为实验平台，在服务器上安装了Ubuntu 操作系统以及docker、docker-compose、Go 语言等基本环境。然后在Hyperledger Fabric 原生的PBFT 算法的基础上实现了GBFT。最后在服务器上分别对应用原始PBFT 算法的Hyperledger Fabric 和应用GBFT 算法的Hyperledger Fabric 进行测试。实验平台的软硬件配置如表2所示。

表2 实验环境配置信息表

4.2 吞吐量测试

吞吐量是衡量系统运行效率的一个重要标准。在区块链网络中，一般用每秒交易数（tps）来表示，即：

其中：transactions 为出块时间内系统处理交易数，t为出块时间。设计两种共识机制在4、5、6、7、8 个节点下的对照实验，多次测试取平均值，实验结果如图7所示。

图7 两种算法的吞吐量比较

从图7 的实验结果可以看出，随着网络中节点数目的增加，两种情况下吞吐量都下降明显。这是因为节点数目的增加使得网络中通信开销增大，导致网络运行效率下降。还可以看出，在节点数目相同的情况下，相比于原始PBFT 算法，GBFT 始终具有更高的吞吐量。

4.3 时延测试

交易确认时延指客户端发送一个交易请求到客户端确认交易完成的时间间隔，即：

其中：Tconfirm为交易得到确认的时间，Trequest为发送交易请求的开始时间。设计两种共识机制在4、5、6、7、8 个节点下的对照实验，多次测试取平均值，实验结果如图8所示。带来的通信成本增加所导致的结果，但是原始PBFT算法的时延上升速率更大，而GBFT由于引入了非拜占庭容错一致性协议与选举机制，使得它的时延上升速率是随节点数目的增加而下降的。此外，在节点数目相同的情况下，相比于PBFT，GBFT始终具有更低的交易确认时延。

图8 两种算法的交易确认时延比较

图8 中，两种方案的交易确认时延都随节点数目的增加呈上升趋势，这同样是由节点数目的增加

4.4 容错性分析

设区块链网络中共有N（N ≥4）个节点，其中有F 个拜占庭节点。改进方案中，系统会根据节点信用度的高低选出N/2 个节点纳入共识节点组，设共识节点组中的拜占庭节点数目为f（f ≤F），则有：

1）第一级共识：共识节点组参与简化协议。若共识节点组中没有拜占庭节点，即f=0，则顺利达成一致；若f ≥1，则通过非拜占庭容错协议无法达成一致，进入第二级共识。

2）第二级共识：共识节点组参与PBFT 共识协议。若1 ≤f≤（N/2-1）/3，已知PBFT算法的容错性为（N-1）/3，可知第二级共识顺利达成一致；若f>（N/2-1）/3，则第二级共识无法达成一致，进入第三级共识。

3）第三级共识：全节点参与PBFT 共识。此时共识机制退化为原始的PBFT 算法，有f=F。当f≤（N-1）/3 时，节点之间顺利达成一致；当f >（N-1）/3，整个网络无法达成一致。

以上分析证明，GBFT 的容错性是由第三级共识的容错性决定的。即采用GBFT 作为共识机制的区块链网络中共N个节点时，整个网络可以提供（N-1）/3的容错性。

5 结语

基于PBFT 算法的思想，结合联盟链应用场景中节点可信度相对更高的特点，提出一种改进的共识算法。首先在保留PBFT一致性协议的同时引入了非拜占庭容错协议，以降共识过程中的通信开销；为了避免两种一致性协议的频繁切换带来的额外开销，提出了基于节点行为的选举机制；最后在非拜占庭容错协议、选举机制、PBFT一致性协议的基础上构建了三级共识机制。实验结果表明，相比于PBFT 算法，本文提出的GBFT 算法有效提高了区块链网络的吞吐量，降低了交易确认时延，同时还保持了PBFT 算法的容错性。在GBFT 中，将信用分排名前50%的节点纳入了共识节点集，这样的设定可能无法适用于所有的应用场景。下一步的工作中可以考虑将共识节点集的容量设置为一个可配置的参数，以灵活调整网络的去中心化程度。