一种结合BLS签名的可拜占庭容错Raft算法

王日宏，张立锋，周 航，徐泉清

1.青岛理工大学信息与控制工程学院，山东青岛266520

2.蚂蚁金服，杭州310012

近几年，作为比特币底层技术的区块链技术取得了重大发展[1].所谓区块链，概括来说，就是去中心化的分布式记账本，综合了密码学、分布式原理等[2].它通过加密链式区块结构完成数据的存储，利用共识算法验证数据.区块链的产生对互联网乃至整个社会信用机制的建立带来了至关重要的影响.

作为区块链核心部分的共识算法主要分为非拜占庭容错共识算法和拜占庭容错(Byzantine fault tolerance, BFT)共识算法.非拜占庭容错共识算法的发展由来已久，例如：文献[3]提出了一个在副本出现宕机情况下仍能正常工作的主从节点备份算法；文献[4]提出了Paxos 算法；文献[5]在文献[4]的基础上提出了更容易理解的Raft算法，并凭借着高可拓展性和高吞吐量的优势在联盟链中得到了应用.文献[6]就在Quorum 项目中将Raft 算法作为可选算法.针对Raft 算法无法实现拜占庭容错问题，提出了一种结合Raft 算法优势的拜占庭容错算法.

拜占庭容错算法可以分为3 类：状态机拜占庭容错算法、带可信部件的拜占庭容错算法和针对区块链应用场景进行优化的拜占庭容错算法.状态机拜占庭系统的代表算法主要是PBFT 算法及其改进算法，例如没有主节点排序（hybrid quorum, HQ）算法[7]、基于投机的Zyzzyva 算法[8]、基于拜占庭锁的Zzyzx 算法[9]、优化主节点切换代价的Spining 算法[10]等.带有可信部件的拜占庭系统的代表算法主要包括A2M[11]和MinBFT[12]等，其主要思路是利用可信硬件解决节点模棱两可问题，从而提升拜占庭容错能力，实现了2f+1 的拜占庭容错能力.针对区块链应用场景进行优化的拜占庭容错算法主要包括权益证明（proof of stake, PoS）与实用拜占庭容错（practical Byzantine fault tolerance, PBFT）结合的Tendermint[13]、股份授权证明（delegated proof of stake, DPoS）[14]与PBFT结合的授权拜占庭容错（delegated Byzantine fault tolerance, dBFT）[15].除此之外，在区块链中还有一类基于密码学的共识算法，如采用聚合签名降低通信复杂度的Byzcoin[16]、采用可验证随机数的Algorand 以及利用阈值签名实现异步共识的HoneyBadgerBFT[17].

通过对已有拜占庭容错算法进行分析，提出了结合BLS 阈值签名[18]实现Raft 算法的拜占庭容错算法（Raft Byzantine fault tolerance, RBFT）.该算法实现了Leader 节点选举和日志复制过程的拜占庭容错，同时又保证了O(n)的算法复杂度，并且提出了安全状态，保证了算法的最终一致性[19].

针对Raft 算法中的问题，RBFT 算法进行了如下改进：

1）将BLS 签名与Raft 算法中的消息传递过程结合，实现了Leader 节点选举和日志复制过程的拜占庭容错.

2）基于增量哈希提出了安全状态，能保证算法在每轮共识完成之后的一致性，进一步保证了算法的安全性.

3）提出了结合Raft 算法超时时间机制的选举方案，简化了传统BFT 算法在视图切换过程中的算法复杂度.

4）引入客户端监控机制以动态监测Leader 节点运行情况，避免了拜占庭Leader 节点消极反馈情况的发生.

1 背景知识

1.1 Raft 算法

Raft 算法是一种非拜占庭容错的状态机副本复制算法[5]，分为3 种状态模型：Follower、Candidate 和Leader.状态转化模型如图1所示.

图1 Raft 算法状态转移图Figure 1 State transition diagram of Raft algorithm

在Raft 共识算法中，消息包含RequestVote 和AppendEntries 两种消息.当Leader 节点宕机时，Candidate 在选举时通过RequestVote 消息可以获取Follower 的唯一投票.Leader 节点通过AppendEntries 消息发送日志条目到Follower 节点，此时AppendEntries 消息中包含心跳（heartbeat）信息，以证明Leader 节点能正常运行.两种消息的存在，让Raft 节点间在实现数据交流的同时完成日志复制的共识任务.

1.2 BLS 签名

BLS 签名算法是基于双线性映射构造的一种加密算法[18]，主要分为4 部分：算法初始化、密钥生成、签名和验证.

1）算法初始化

G1和G2是阶为p的乘法群，生成元分别为g1和g2,e表示双线性映射:G1×G2→GT,H:{0,1}∗→G1表示安全哈希函数，(G1,G2,GT,e,g1,g2,p,h)表示公开参数.

2）密钥生成

选择一个随机数x ∈ZP，计算v=gx2∈G2，私钥为sk=x，公钥为pk=v.

3）签名

例如对接收到的消息M进行签名生成σ=xH(M)，H(M)表示对消息M进行哈希运算的过程.

4）验证

输入消息M和签名σ，判断e(σ,g2)=e(H(M),v)是否成立.

2 算法设计

2.1 RBFT 算法基础

RBFT 算法改进了Raft 算法，利用BLS 签名实现阈值签名，以阈值签名过程代替投票过程，实现了算法的拜占庭容错.RBFT算法同样保留了Raft 算法中的3 种节点状态：Leader、Follower 和Candidate，并且针对日志结构也同样保留了任期（Term）、索引（Index）和命令（Command）的结构.为了实现拜占庭容错，RBFT 算法包含AppendEntries消息、RequestVote 消息、Request 消息和Update 消息，其中Request 消息受到了Omniledger的启发[20]，用于监测Leader 节点运行状况的Update 消息.

详细介绍如下：

1）AppendEntries 消息

AppendEntries 消息包含Leader 节点发往Follower 节点的日志消息、Leader 节点的心跳和Leader 节点选举成功的证据.证据由Leader 节点收集的签名组成，并通过结合BLS 的阈值签名组合成一个可供其他节点验证的总签名A，该过程如图2所示.

图2 BLS 阈值签名图Figure 2 BLS threshold signature diagram

2）AppendEntriesResponse 消息

AppendEntriesResponse 消息是在包含AppendEntries 消息的基础上增加了可供其他节点验证的总签名A.

3）RequestVote 消息

RequestVote 消息包含Candidate 节点的当前任期和用来验证当前任期的递增哈希值.递增哈希值由日志的任期、索引、命令三部分组成，可以通过索引号顺序计算命令的哈希得到.递增哈希值一方面可以验证当前Candidate 节点提供的任期号是否正确，保证了RBFT 算法Leader 选取的最优性；另一方面可以防止拜占庭Leader 节点对日志的舍弃或任意重排序.

4）RequestVoteResponse 消息

RequestVoteResponse 消息除了包含RequestVote 消息之外，还包含可供其他节点验证的总签名A.

5）Request 消息

Request 消息包含客户端发送到Leader 节点的消息和便于Follower 节点验证客户端消息完整性和正确性的数字签名.数字签名的存在能有效防止Leader 节点对消息的篡改.

6）Update 消息

Update 消息能增加客户端的干预，防止Leader 节点对客户端的消极反馈而引发的算法活性问题[20].

RBFT 算法针对4 种消息的节点状态转移如图3所示.

最后根据CAP 原则[21]，引入了安全状态增强来RBFT 算法的可用性，即共识完成之后实现所有非拜占庭节点状态的一致性.设立安全状态可以保证节点达到最终一致性，即任何达到安全状态的非拜占庭节点都将拥有相同的状态.

图3 RBFT 算法状态转移图Figure 3 State transition diagram of RBFT algorithm

2.2 容错机制的实现

RBFT 算法容错机制的实现依赖于结合BLS 签名的阈值签名，阈值签名的构造过程是通过Shamir 秘密分享方法[22]进行的.引入阈值签名的目的是将投票过程转化为签名过程，并且以2/3 节点数作为签名收集的阈值.结合了BLS 签名的阈值签名方案主要分为四部分：算法初始化、密钥生成、签名和验证.

1）初始化

初始化过程与1.2 节BLS 签名中的初始化过程相同.

2）密钥生成

首先选择一个随机数x ∈ZP，计算v=gx2∈G2，总私钥为msk=x，总公钥为mpk=v；然后进行随机化过程，随机选取xi ∈ZP上的t −1 阶多项式P，并且满足P(0) =x，计算签名者i的私钥为xi，公钥为vi；最后公开mpk 以及所有用户的公钥

3）签名

签名过程即针对日志的复制过程，与投票过程相同.节点i对Leader 节点接收来的携带有客户端签名的AppendEntries 消息M进行验证，根据数字签名验证消息是否被Leader 节点篡改，验证通过后计算签名σi=H(M)xi，然后将σi广播给Leader 节点，Leader 节点收到σi后进行验证.首先通过双线性映射函数验证签名的正确性，即e(σi,g2) =e(H(M),vi)，若等式成立则验证通过，Leader 将签名记录下来；其次等待收到其余2/3 的Follower 节点的正确签名；最后Leader 节点根据这些签名计算出完整的签名

式中

4）验证

Leader 节点通过AppendEntriesResponse 消息向Follower 节点传递消息M和签名σ，判断e(σ,g2)=e(H(M),mpk)是否成立，从而完成整个验证过程.

2.3 Leader 节点选举

在Raft 算法中，Leader 节点选举依赖于随机超时时间.超时时间短的Candidate 节点优先向其他节点发送RequestVote 命令进行索票，票数多的Candidate 节点当选为Leader 节点.在不存在拜占庭节点的情况下，Leader 节点选举过程将顺利达成，但在存有拜占庭节点的情况下，Leader 节点选举过程会遇到伪造投票消息的情况，即拜占庭节点在选举过程中伪造自己接收到了大多数其他节点的投票消息.RBFT 算法针对Leader 节点选举问题，采用了结合BLS 签名的阈值签名方案，将Raft算法中通过RequestVote 获取选票的过程转化为通过RequestVote 获取Follower 节点对该消息进行阈值签名的过程.在第1 阶段，当某个Candidate 节点优先收集到超过2/3的Follower 节点的部分签名后会得到完整签名.在第2 阶段，该节点转发附有完整签名的RequestVoteResponse 消息，等待其他节点验证这个完整签名的有效性.如果验证通过则返回一个正反馈，否则返回一个负反馈，最后当选的Candidate节点发送携带正反馈的可验证消息给其他节点，完成整个选举过程.图4为Leader 节点选举阶段示意图.

图4 RBFT 算法Leader 节点选举过程图Figure 4 RBFT algorithm Leader election process diagram

RBFT 算法引入结合BLS 签名的阈值签名方案，保证了Leader 节点选举的安全性和效率，将同类型PBFT 的算法复杂度由O(n2)（在最坏情况下的算法复杂度为O(n4)）降低到O(n).

2.4 日志复制

RBFT 算法在Raft 算法基础上，针对Leader 节点和Follower 节点可能出现的拜占庭错误进行了容错.当Leader 节点是拜占庭节点时，拜占庭错误分为以下几种：Leader 节点篡改来自客户端的消息、Leader 节点提交未经验证的消息和Leader 节点忽略或消极反馈客户端消息.当Follower 节点是拜占庭节点时，拜占庭Follower 节点可能会篡改来自Leader 节点的消息.

针对以上问题，RBFT 算法进行如下优化：

1）针对拜占庭Leader 节点篡改来自客户端的消息问题，RBFT 算法引入数字签名，使客户端发往Leader 节点的Request 消息中包含客户端对消息的数字签名.如果Leader 节点对消息进行篡改，则接收到消息的Follower 节点将会通过客户端公钥进行检验，这种机制可以阻止拜占庭Leader 节点对消息的篡改.

2）针对拜占庭Leader 节点提交未经验证的消息问题，RBFT 算法引入了容错机制，其过程如图5所示：

图5 RBFT 算法日志复制过程图Figure 5 Diagram of RBFT algorithm log replication process

该过程分为3 个阶段：Pre-commit 阶段、Commit 阶段、Reply 阶段.在Pre-commit阶段，Leader 节点发送AppendEntries 消息到Follower 节点，Follower 节点在验证AppendEntries 中的数字签名确实来自客户端后对其进行签名，并将结果返回给Leader 节点.当Leader 节点接收到超过2/3 的Follower 节点的签名后，通过阈值签名组成完整签名，这样就完成了Pre-commit 阶段.在Commit 阶段，Leader 节点发送AppendEntriesResponse 消息到Follower 节点，Follower 节点验证AppendEntriesResponse 中的完整签名的正确性，并将验证结果返回给Leader 节点.当Leader 节点收到超过2/3 的Follower 节点的验证通过后返回正反馈，完成Commit 阶段.在Reply 阶段，Leader 节点发送携带可验证正反馈的消息给Follower 节点后，Follower 节点同步状态，使所有非拜占庭Follower 节点达到安全模式，此时Leader 节点提交消息给客户端，完成Reply 阶段.

RBFT 算法采用结合BLS 签名的阈值签名方案，将PBFT 中Prepare 阶段和Commit 阶段O(n2)的算法复杂度优化到了O(n)，大大增加了数据吞吐量，降低了交易延迟，提升了算法的可拓展性.

3 算法分析

RBFT算法作为拜占庭容错的Raft 算法，需要在拜占庭节点存在的情况下满足安全性和活性的要求.算法分析部分参考了Raft 算法文献中的安全性和活性要求，并以此作为参照标准分析RBFT 算法的安全性和活性.

3.1 安全性分析

安全性指的是所有坏的事情不会发生[23]，也就是所有诚实节点最终提交一致性结果.Raft 算法的安全性体现在：Leader 节点选举的安全性、Leader 节点只允许附加不允许删除和修改、Leader 节点的完整性、日志匹配机制以及状态机的安全性.针对以上内容，结合拜占庭容错问题对RBFT 算法进行了以下分析.

3.1.1 Leader 节点选举的安全性

在Raft 算法运行过程中，Leader 节点会定期发送包含日志和心跳的AppendEntries 消息给Follower 节点，以证明Leader 节点的正常运行.当Leader 节点宕机时，Follower 节点因收不到Leader 节点的心跳消息而触发选举.选举需要规定随机超时时间，优先完成这个时间的节点可以向其他节点发送RequestVote 消息.这个消息包含当前节点的任期，以此保证了整个选举过程的安全性.然而，拜占庭Leader 节点可能以伪造投票的方式当选.为了保证RBFT算法Leader 节点选举的安全性，提出了采用结合BLS 签名的阈值签名方案来防止这种情况的发生，具体可见2.2 部分.

3.1.2 Leader 节点的安全性问题分类

在Raft 算法中，Leader 节点的安全性问题分为两类：Leader 节点的日志完整性和Leader节点只允许附加日志而不允许删除日志.针对Leader 节点的日志完整性问题，RBFT 算法通过增量哈希和日志复制的容错机制保证了所有非拜占庭节点都处于同样的安全状态，并且通过选举机制保证了所有当选的Leader 节点都是到达安全状态的节点，即保证了Leader 节点的日志完整性.针对Leader 节点只允许附加日志而不允许删除的问题，RBFT 算法依赖于增量哈希的安全状态，保证了所有通过共识的日志都会被保存，而不允许任意的节点删除或修改.

3.1.2.1 日志

RBFT 算法保留了Raft 算法的日志结构，并在此基础上提出了日志复制过程中的拜占庭容错方法，通过两轮提交保证了拜占庭节点存在情况下日志的正确性，具体可见2.4 部分.

3.1.2.2 状态机

RBFT 算法修改了状态机提交需要1/2 节点同意的前提，为了实现拜占庭容错，将状态机提交前提修改为2/3 节点，并且结合区块链的使用场景将提交状态机过程转化为Leader 节点把交易写入区块的过程.

以上分析表明：RBFT 算法符合安全性要求.

3.2 活性分析

活性指的是所有好的事情一定发生[23]，也就是在一定时间范围内完成整个共识过程.在Raft 共识算法中，活性主要体现在随机超时时间t的设立.t ⊆[T,2T]并且满足T ≫T(broadcast time)的条件，以避免因为消息延迟而导致的不必要的Leader 节点切换，同时t的设立又可以让系统在有限的时间内产生一个Leader 节点，保证系统的正常运行.

RBFT 算法保留了Raft 算法关于保证算法活性的内容.针对随机超时时间t，文献[5]给出了一个t ⊆[150 ms, 300 ms]的建议，T(broadcast time)=15 ms，Leader 节点心跳间隔T(heartbeat)=50 ms.随机超时时间的产生是在考虑AppendEntries 消息延迟的基础上进行的，同时文献[5]建议采用这种较大时间间隔的原因也是考虑到可能存在的节点分票的情况.增大时间间隔既可以有效地降低分票的可能性，又可以降低因消息延迟而导致的不必要的Leader节点切换.

RBFT 算法是通过设置最大消息延迟时间来保证算法活性的.该算法将随机超时时间t设置为t ⊆[150 ms, 600 ms]，是因为除了考虑消息延迟外还要考虑拜占庭容错过程中的多轮消息交换和聚合签名过程.Leader节点心跳间隔设置为T(heartbeat)=150 ms，并且通过实验发现在这个心跳间隔内算法可以避免不必要的Leader 节点切换.如果在心跳间隔内Leader节点无响应，就重新进行节点切换，保证了算法的活跃度.另外，受到Omniledger 分布式一致性算法[20]的客户端监测机制的启发，客户端对Leader 节点进行监控.当发现Leader 节点消极反馈来自客户端的消息时，通过Update 消息进行新一轮的Leader 选举，防止了拜占庭Leader 节点消极反馈的情况.

4 仿真实验

RBFT 算法将BLS 签名容错过程与Raft 算法结合，实现了Raft 算法的拜占庭容错.RBFT 算法高可拓展性和高数据吞吐量的实现，一方面得益于BLS 签名容错过程的低算法复杂度，另一方面得益于Raft 算法高效的共识逻辑.

首先，本文采用go 语言实现了Raft 算法，并在改进Raft 算法的基础上得到了RBFT 算法；然后，采用本地多节点模拟共识过程，记录数据吞吐量、共识时延等关键数据，完成对比实验；最后，通过实验对比发现，RBFT 算法实现了高数据吞吐量、低延迟以及高可拓展性.

4.1 数据吞吐量测试

数据吞吐量作为衡量区块链共识算法性能的关键指标，表示的是区块链每秒可处理的交易数量（transaction per second, TPS）.

数据吞吐量的测试过程如下：首先在本地开启8 个节点作为服务器节点，另外开启一个新端口作为客户端节点，客户端节点可以发送Request 消息和Update 消息；然后分别测试PBFT 算法、Raft 算法和RBFT 算法在相同环境下的数据吞吐量，同时测试公有链企业级操作系统(enterprise operation system, EOS)项目的股份授权证明（delegated proof of stake, DPoS）算法的数据吞吐量.测试过程采用EOSBenchTool 工具，设置Thread number为8，Transaction pool size 为3 000，Transaction batch size 为2 500; 最后随机选取测试数据中的20组进行比较，如图6所示.

图6 吞吐量图Figure 6 Throughput diagram

图6结果显示：RBFT 算法基本保留了Raft 算法的高数据吞吐量，比PBFT 算法的数据吞吐量提高了25%，但作为实现拜占庭容错的代价是比Raft 算法的数据吞吐量下降了58%，其主要原因是在容错过程中多轮的消息传递和签名收集.RBFT 算法的数据吞吐量比EOS 中DPoS 算法的数据吞吐量下降9%，主要原因是RBFT算法的代码实现存在可优化空间.

主节点切换速度会对共识效率产生影响，因为主节点切换时共识停止，所以主节点切换时间也会影响算法的数据吞吐量产生.采用同样的配置环境，模拟主节点宕机的情况，分别记录Raft 算法、RBFT 算法和PBFT 算法的主节点切换时间，随机选取10 组数据进行对比，如图7所示.

由图7可以看出：RBFT 算法相比于PBFT 算法在主节点切换时间方面有了30%的提升，相比于非拜占庭容错的Raft算法仅仅降低了20%.分析图6和7 可以得出RBFT 算法和Raft 算法的性能差异，RBFT 算法的主节点切换性能提升明显，一方面是因为合理的最大消息延迟时间和高效的容错算法；另一方面是因为安全状态保证了当选Leader 的正确性，避免了重复选举.

图7 Leader 选举时间图Figure 7 Leader election time diagram

RBFT 算法作为一种高可拓展性算法，在客户端发送相同请求数量的情况下，服务器节点数和数据吞吐量的关系如图8所示.实验过程分别针对4 节点、8 节点、12 节点、16 节点的情况对数据吞吐量进行测试.实验结果显示：相比于PBFT 算法，RBFT 算法的数据吞吐量受节点数目增加的影响较弱，并且就线段趋势而言，RBFT 算法的优势将伴随着节点数目的增多而增强.关于RBFT 算法保持高可拓展性的原因在于：一方面RBFT 算法保留了Raft 算法高效的共识逻辑，另一方面RBFT 算法具有低通信复杂度.

图8 节点数与数据吞吐量关系图Figure 8 Relationship between node and throughput

4.2 共识时延测试

共识时延表示的是客户端向区块链提交交易到另一方看到交易被提交的时间差，低的共识时延将会大大提升区块链的性能.PBFT 算法和RBFT 算法的共识时延测试同样在本地8节点的前提下进行.根据4.1 节返回的时间戳计算共识时延，进而得到如图9所示的时延图.

图9显示了RBFT 算法拥有更低的共识时延.共识时延是算法性能的最终体现，表明RBFT算法相比于PBFT 算法拥有更高的性能.

5 结 语

图9 时延图Figure 9 Time delay diagram

RBFT 算法是一种可拜占庭容错的Raft 算法，解决了Raft 算法在拜占庭场景下的Leader选举和日志篡改问题.首先，将容错过程与Raft 算法的AppendEntries 消息和RequestVote消息结合，利用BLS 阈值签名代替投票过程，实现了RBFT 算法的高可拓展性和高数据吞吐量.安全状态的提出，保证了所有非拜占庭节点日志在每轮共识结束后的最终一致性；然后，结合Raft 算法对RBFT 算法的安全性和活性进行了分析证明；最后，由实验数据表明：RBFT算法相比于PBFT 算法，其数据吞吐量提升了25%，主节点切换速度提升了30%；相比于非拜占庭容错的Raft 算法，其数据吞吐量和主节点切换速度下降也不明显.综上所述，RBFT算法是一种可应用于公链的高拓展性、高数据吞吐量、高安全性的共识算法.