基于联盟链PBFT的BRaft共识算法

白尚旺，达泓宇，高改梅，刘春霞，党伟超

（太原科技大学 计算机科学与技术学院，山西 太原 030024）

0 引言

2008 年，中本聪首次提出比特币，数字货币进入了新篇章［1］。在比特币创始论文中，区块链被定义为一种数据结构，其实质是一个由区块构成的去中心化的链式账本，每个区块按时间顺序表示用户之间的事务传输。区块链具有去中心化、不可篡改、匿名性等基本特性［2］，因此它还可以作为一个分布式网络协议，使彼此不认识的不同参与者之间建立信任关系［3］，而不涉及任何中心角色或第三方。共识算法作为区块链中的最重要一环，着重解决存在故障时如何协调分布式节点之间的交互，保证各节点所维护的数据副本的一致性，避免出现数据不一致、信息不对称等问题。根据区块链的去中心化程度，可将其划分为公有链、联盟链和私有链。对于不同的区块链，采用的共识算法也不同。

以比特币、以太坊为代表的公有链去中心化程度最高，通常采用的共识机制有工作量证明机制PoW（Proof of Work）［4］、权益证明机制（Proof of Stake，PoS）［5］、委托权益证明（Delegated proof of stake，DPoS）［6］。私有链的去中心化程度最低，它的写入权限由个人或某个组织机构所掌握，一般应用于企业内部。以Hyperledger Fabric 为代表的联盟链去中心化程度介于二者之间，一般由多个机构共同参与管理，并允许授权的节点加入网络。与公有链相比，具有更好的交易速度和安全性，是区块链落地的主要方向。

目前，联盟链共识算法主要分为拜占庭容错（Byzantine Fault Tolerance，BFT）共识算法［7］和非拜占庭容错共识算法两类。BFT 算法的核心就是在存在恶意节点的情况下，保证其余正常节点间能够达成共识。常用的BFT 共识机制主要有实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）［8］、联邦拜占庭容错（Federal Byzantine Fault Tolerance，FBFT）［9］和投机拜占庭容错（Speculative Byzantine Fault Tolerance，SBFT）［10］共识机制，但这类共识算法普遍存在通信复杂度较高的问题。

非拜占庭容错共识算法是建立在对所有节点的信任机制上，具有低时延、高吞吐量的优势，常见的有Paxos［11］、Raft［12］共识算法，但不能容忍拜占庭节点的存在，由此提出一系列共识算法的改进方案。Copeland 等［13］结合Raft共识算法和PBFT 共识算法的优点提出Tangaroa 共识算法，该算法在日志复制的过程中添加了哈希函数，确保在有恶意节点攻击的情况下仍能保持安全性，但是该算法无法容忍多个拜占庭节点的联合攻击。Martino 等［14］在Tangaroa 共识算法的基础上提出一种新型高性能或可扩展性的BFT 共识算法Scal-ableBFT，可用于实现大规模的高性能许可私有链。黄冬艳等［15］提出一种基于Raft 集群的拜占庭容错共识算法RBFT，将节点进行分组，组内采用Raft共识机制，而每组的Leader 节点重新构成一个管理组实行PBFT 算法。该算法较好地融合了Raft共识效率高和PBFT拜占庭容错性能好的特点，但需要引入大量的监督节点。

本文在分析Raft 算法的不足后，通过对已有拜占庭算法进行研究，使用RSA 签名以防止节点身份伪造和消息篡改，解决在共识过程中Leader 节点作恶的问题。同时，在PBFT 算法三段协议的基础上引入标识位W 保证算法的一致性，实现Raft 算法在日志复制过程中的拜占庭容错，目的在于提高Raft 算法安全性的同时又保证比PBFT 更低的算法复杂度。

1 相关工作

1.1 PBFT共识算法

PBFT 共识机制将原始拜占庭容错共识算法的通信复杂度从指数级降到了多项式级，共识效率得到明显提高。PBFT算法中的核心概念有3个部分：视图（view）、副本（replica）、角色（primary，backups）。视图表示当前系统的全局状态，副本表示系统中所有参与共识的节点，而在每个视图中，副本的角色又分为两类：主节点（primary）和备份节点（backups）。假设系统中的恶意节点数为f，PBFT 需要满足总节点数至少为3f+1。算法的共识过程如图1所示。

Fig.1 PBFT consensus process图1 PBFT共识过程

PBFT 的具体执行步骤如下：①请求阶段，客户端向主节点发送请求；②预准备阶段，主节点在收到客户端发出的请求后，先检查请求的合法性，若合法，主节点将此消息写入本地日志然后进入预准备阶段，并向其他副本节点广播预准备消息；③准备阶段，副本节点在收到消息后先确认消息的正确性，若正确就进入准备阶段，并向其他副本节点广播准备消息，同时将预准备消息和准备消息写入本地日志；④确认阶段，当一个节点在一段时间内接收到2f个以上的准备消息，就发送确认消息给所有副本节点；⑤应答阶段，副本节点接收到2f个来自其他节点的确认消息后，验证消息的一致性，并向客户端返回应答消息。客户端收到2f+1个应答消息，表明共识完成。

1.2 Raft共识机制

Raft 算法是Paxos 算法的改进，是从多副本状态机的角度提出，用来对多副本状态机的日志复制进行管理［16］。一个Raft群集中有若干个成员节点，这些节点有3 种角色：领导者（Leader）、参与者（Candidate）和跟随者（Follower），并由Leader统一管理。

（1）Leader。Leader 由Candidate 通过领导者选举协议选举产生，用于接收客户端的请求，并将客户端请求对应的日志项追加到自己的日志中，然后转发给Follower 进行复制，当日志复制到大多数节点时，Leader 将发送请求给Follower 进行日志提交。

（2）Follower。Follower 接收并复制由Leader 同步的日志。在Leader广播可以提交日志后，提交日志。

（3）Candidate。在Leader 选举过程中由Follower 过渡为Leader的临时状态。

参与共识的节点之间通过异步远程过程调用（RPC）进行交互，调用请求主要分为以下两种：

RequestVoteRPC：用来进行投票请求，包含Candidate节点的当前任期、日志中最后一条日志项的索引和任期等［17］，接收到请求的Follower 通过验证当前Candidate 节点提供的任期号，选取最优Leader，避免拜占庭Leader 节点丢弃日志或对日志任意排序。

AppendEntriesRPC：用来进行日志复制，包含领导者id、领导者当前任期term、新附加的日志项、前一个条目在Leader 日志中的索引prevLogIndex、任期prevLogterm 以及提交索引commitIndex。

1.2.1 领导者选举

图2 描述了3 种不同状态节点之间的关系。当服务器启动时，所有节点初始状态为Follower。经过一段随机时间后，Follower 节点当前任期加一，然后转变为Candidate 节点，Candidate 节点首先给自己投票，随后将RequestVote 请求发送给Follower 节点以获取唯一投票。当Candidate 节点接收到大多数选票时，转变为Leader节点［18］。

Fig.2 Raft state transitions图2 Raft状态转换

收到投票请求的Follower 节点首先会检查Candidate最后一条日志项的任期号，只有在发出RPC 的Candidate的日志项具有的任期号比它本地保存的日志项的任期号更大，或者在任期号相同但具有比它更大的索引值时，Follower才会将他们的选票授予该节点。

1.2.2 日志复制

日志是由日志项组成，日志项是一种包含用户指定的数据、索引值、Leader 节点任期的数据格式。如图3 所示，首先，客户端向Leader 节点发送需要执行的请求；其次，Leader 节点在收到客户端请求后会将带有客户端命令的日志项追加到自己的日志中，并向Follower 节点发送AppendEntriesRPC，进行日志复制。

Fig.3 Log copy process图3 日志复制过程

收到AppendEntriesRPC 请求的Follower 节点首先将自身最新条目与RPC 中的条目进行比较。如果两个日志项具有相同的索引和任期，Follower 会将接收到的新的日志项附加到其日志并将AppendEntriesRPC 发送给Leader，表示复制成功。当Leader 在收到集群中大多数Follower 复制成功的响应后，将此日志项标记为已提交。日志项中的指令交由状态机执行，并将结果反馈给客户端。

2 BRaft共识算法

在Raft 算法中，日志是否提交由Leader 节点判断，Leader 节点在向所有Follower 节点复制日志项时，如果收到一定数量Follower 节点的响应，Leader 将日志项中的指令交由状态机执行，并在未来的心跳消息或者日志复制消息中广播给Follower 节点。但在拜占庭环境下，Leader 节点可以发送错误消息给Follower 节点，Follower 节点可以在没有将日志项添加至日志列表时恶意响应Leader，以误导Leader 收到了一定数量的响应。由此可知，仅依赖Leader无法确保日志项被正确复制，进而无法确保算法安全性。

BRaft 通过对客户端的消息进行数字签名以防止拜占庭节点作恶。在Follower 节点对Leader 的消息进行验证之后，算法在结合PBFT 的三段协议的基础上引入标识位W，确保在拜占庭节点作恶的情况下日志项依然能够被正确提交。这样，不仅减少了Follower 节点作恶的可能性，并且相比于PBFT 算法的准备和确认阶段，节点之间不再需要额外通信，理论上提高了日志追加的时效。

2.1 前提与假设

假设BRaft 集群中一共包含n 个节点，f 个拜占庭节点BRaft算法需要满足式（1）以确保算法的容错能力。

在共识过程中，节点存在宕机或者作恶的可能性，BRaft 的容错能力分两种情况：①当Leader 节点为拜占庭节点，Follower 集群节点数为n-1，Follower 节点中存在的拜占庭节点数为f-1，如果n-1-（f-1）个节点已经达成共识，来自f-1 个拜占庭节点的决策不会影响正常节点的决策（n-1-（f-1）-（f-1）＞f-1），由此可知BRaft 集群节点总数需要满足n＞3f-2；②当Leader 节点为正常节点时，Follower 集群节点数为n-1，Follower 节点中存在的拜占庭节点数为f，如果n-1-f个节点已经达成共识，来自f个拜占庭节点的决策不会影响正常节点的决策（n-1-f-f＞f），此时BRaft 集群节点总数需要满足n＞3f+1。

2.2 签名验证

BRaft 通过RSA 数字签名作为消息被篡改的检测机制，且在算法运行过程中，所有的共识节点均拥有客户端的公钥PK。在签名过程中，首先，客户端对原文进行Hash运算，得到摘要M，并使用客户端私钥SK对摘要M进行加密，形成数字签名D；然后，将原文和数字签名一同发送给Leader，Leader 节点在收到客户端发来的数字签名及原文后，会将自身信息与客户端消息打包一起发给Follower 节点，Follower 节点在收到数字签名后，先用客户端公钥PK对摘要进行解密，确定是客户端消息之后，再用同样的Hash 算法对原文计算摘要值，判断Leader 是否对消息进行篡改。

在Follower 节点对客户端消息验证之后，BRaft 结合PBFT 三段协议的思想，并通过标识位W保持在拜占庭环境节点的一致性，即每一个Follower 节点存在一个标识位W（0 表示验证不通过，1 表示验证通过），每个标识位的初始状态为0。当Follower 节点经过验证之后的标识位c为1，且有2f+1 个c发生变化且值的总和至少为f+1 时，可以证明Leader 为正常节点。当Follower 节点经过验证之后的标识位c为0，Follower 集群中当有2f-1 个标识位发生变化，且这2f-1 个c值的总和至多为f-1 时，证明Leader 节点为拜占庭节点，此时系统重新进行选举。

算法1签名验证算法

2.3 共识过程

BRaft 将共识过程分为4 个阶段：提出区块、验证区块、更新区块和应答阶段。具体共识过程如图4所示。

Fig.4 BRaft consensus process图4 BRaft共识过程

（1）提出区块。Leader 节点收集客户端请求＜Client-Request，X＞sig，并验证请求的合法性，若不合法，直接丢弃，若合法，Leader 节点将客户端请求对应的日志项追加到自己的日志中，并在Client-Request 的基础上加上领导者id、领导者当前任期term、前一个日志项在Leader 日志中的索引prevLogIndex、任期prevLogterm，形成＜Prepare-Request，X＞，并广播给其他Follower 节点。

（2）验证区块。当Follower 节点i收到来自Leader 节点的＜Prepare-Request，X＞请求后，验证以下条件：①通过Verify（PK，D，X）验证Leader 节点是否篡改客户端消息；②验证新附加的日志项的任期号term是否大于等于Follower 本身的任期号；③验证本地日志的prevLogIndex位置处的日志项与对应的prevLogterm是否匹配。如果以上条件都满足，则Follower 节点i接受来自Leader 节点的Prepare-Request 请求。此时，标识位Wi为1，并向Leader 节点发送＜AgreePrepare-Request，Wi＞。

（3）更新区块链。当Leader 节点收到2f+1 个Follower节点发来的＜AgreePrepare-Request，Wi＞时，且这2f+1 个Wi值的总和至少为f+1，可以证明Follower 节点已经做好准备进行日志复制。此时Leader 节点广播＜AppendEntries，X＞给集群中的所有Follower 节点。

（4）应答。Follower 节点收到＜AppendEntries，X＞后根据条件在本地追加收到的日志项，响应追加结果。当Leader 节点在收到2f+1 个应答结果时，表示共识已完成。Leader 将日志项中的指令交由状态机执行，随后将处理结果返回给客户端并通过心跳消息通知Follower 节点执行已提交的日志项。

3 算法分析

BRaft 算法作为Raft 的改进算法，需要在存在恶意节点的情况下，保证算法的安全性和活性，下文将对以上两点进行具体分析。

3.1 安全性

安全性是指所有坏的事情不会发生，BRaft 算法的安全性体现在两方面：Leader 节点选举阶段的安全性和日志复制阶段的安全性。

在Leader 选举阶段，BRaft 通过心跳触发Leader 选举。Leader 节点会定期向Follower 节点发送心跳消息（包含在AppendEntriesRPC 中），以证明节点的正常运行。如果Follower 节点在一段时间内没有收到Leader 的心跳，就会在一段随机时间之后转换为Candidate 节点，触发新一轮的选举。Candidate 节点向其余Follower 节点发送RequestVote请求，以获取唯一投票。RequestVote 请求包含当前节点最后一条日志项的任期和索引，只有发出投票请求的Candidate 节点的任期及索引比将要进行投票的Follower 节点更高时，Follower 才会将他们的选票授予该节点，以此保证整个选举过程的安全性。

在日志复制阶段，BRaft 算法保留了Raft 算法的日志结构，通过数字签名实现消息篡改检测和防止身份伪造，并依赖PBFT 三段协议保证共识的一致性，保证了拜占庭节点存在情况下日志仍能够被正确提交。BRaft 修改了状态机提交需要1/2 节点同意的前提，当Leader 节点为拜占庭节点，在容错范围f＜(n+2)/3 内，可以保证BRaft 的安全性。当Leader 节点为正常节点时，在容错范围f＜(n-1)/3内，可以保证BRaft算法的安全性。

3.2 活性

活性（Liveness）是分布式共识算法的另一重要属性，是指所有好的事情一定发生。BRaft 算法保证在任何时刻算法均具备可用性，它是单Leader 的拜占庭容错算法，即任意时刻BRaft 需要存在一个可用的Leader。当Leader 节点是正常节点时，算法始终遵循算法正常的日志复制逻辑运行，当Leader 节点为拜占庭节点时，将篡改后的日志项发给其余Follower 节点，Follower 节点在收到日志项后，通过数字签名可以发现日志项被篡改，拒绝将日志项添加到其日志列表中，并转换为Candidate 状态，发起新一轮的Leader 选举。此时，之前被篡改的日志项并未在集群中达成共识，而发起投票的Candidate 在获得一定数量投票后，成为新一轮的Leader，BRaft 集群即恢复正常运行状态，上述整个过程仅耗费了一次Leader 选举耗时，BRaft 算法保持着极高的活性。

4 实验与分析

4.1 实验环境

在实际运行环境中，节点间的通信均通过RPC 实现，对外提供完全一致的接口。实验环境相关软硬件信息如表1所示，节点IP地址如表2所示。

Table 1 Experimental environment configuration information表1 实验环境配置信息

Table 2 Node IP address表2 节点IP地址

4.2 吞吐量

吞吐量指区块链每秒钟处理交易的数量，吞吐量越高代表算法在单位时间能处理的交易越多，性能越好。

在相同实验环境下，对Raft、BRaft 和PBFT 算法进行数据吞吐量测试。测试过程采用Jmater 工具，通过设置不同线程数模拟多个客户端向Leader节点发送Request消息，最后随机选取10组数据进行比较。由于BRaft算法在日志复制过程中存在对消息签名的解密验证，比Raft 算法的数据吞吐量低10%左右，但与PBFT 算法相比，数据吞吐量提高1/4左右，因而BRaft在性能上仍有很大优势，如图5所示。

Fig.5 Throughput图5 吞吐量

BRaft 共识算法在保证其他条件不变的情况下，分别测试了5 节点、10 节点、15 节点、20 节点下的数据吞吐量。节点数量和数据吞吐量的关系如图6 所示。实验结果表明，随着节点数量的增加，BRaft 的数据吞吐量所受到的影响较小，是因为BRaft 算法在Raft 算法原有共识逻辑的基础上，拥有比PBFT 更低的通信复杂度。

Fig.6 The relationship between the number of nodes and data throughput图6 节点数量与数据吞吐量关系

4.3 时延

时延是衡量拜占庭容错的分布式共识算法的另一个重要指标，时延标识了单个请求从被客户端发送开始直至客户端收到响应所需要的时间，包括客户端发送请求、网络传输、日志复制和客户端接收响应五阶段所需时间。

图7 为Raft、BRaft 和PBFT 算法针对不同数量的客户端请求达成共识所需时间。节点数目固定（n=5），在客户端请求数量从5 递增至1 000 的过程中，Raft 和BRaft 所需达成共识的时间均呈线性增长趋势，且当客户端请求数量等于1 000 时，Raft 需要4 732 ms 达成共识，BRaft 算法需要

Fig.7 Consensus time for different numbers of client request图7 不同数量客户端请求达成共识时间

7 749 ms 达成共识，PBFT 需要9 237 ms。虽然，BRaft 应用数字签名和哈希算法，它们对性能的损耗存在一定影响，但与PBFT 算法相比，达成共识的时间有了一定提升。

如图8 所示，W 标识位的使用增加了Follower 节点响应Follower 节点请求的额外开销，但减少了Follower 节点反馈错误消息给Leader 的可能性，且相比于PBFT 这种需要各节点之间相互进行通信的共识过程而言，算法的通信复杂度更低，且本身计算并不复杂，网络传输耗时可以忽略。

Fig.8 Time consuming to discover malicious nodes图8 发现恶意节点耗时

5 结语

本文选取非拜占庭共识算法Raft 作为研究对象，针对拜占庭Leader 节点篡改客户端消息的问题，采用RSA 数字签名作为消息的检验机制，同时在结合PBFT 的三段协议的基础上引入标识位W，实现Raft 算法在日志复制过程中的拜占庭容错，确保在拜占庭节点发送错误消息的情况下日志项依然能够被正确提交，很好地融合了Raft 高效和PBFT 可容错的特点。经过改进的BRaft 共识算法相较于PBFT 共识算法通信复杂度更低，并在保证算法的可理解性和共识效率的同时，提高了算法安全性。但是本文算法还存在一些问题，如在领导者选举阶段无法选择最优Leader，以及对拜占庭节点无法进行动态删除、修改等操作，未来可针对这些问题加以重点研究。