Practical Byzantine Fault Tolerance

Practical Byzantine Fault Tolerance 实用拜占庭容错，是传统BFT的一种可用性实现，算法的时间复杂度为O(n2)

PBFT 算法中, 存在一个主节点(primary) 和其他的备份节点 (replica), PBFT 共识机制主要包含两部分:

• 第一部分是分布式共识达成,在主节点正常工作时, PBFT 通过预准备 (pre-prepare)、准备 (prepare) 和承诺 (commit) 三个步骤完成共识;
• 第二部分是视图转换 (view-change), 当主节点出现问题不能及时处理数据请求时, 其他备份节点发起视图转换, 转换成功后新的主节点开始工作. 主节点以轮转 (round robin) 的方式交替更换；

PBFT 的分布式共识达成过程

• 请求 (propose). 客户端 (client) 上传请求消息 m 至网络中的节点, 包括主节点和其他备份节点.
• 预准备 (pre-prepare). 主节点收到客户端上传的请求消息 m, 赋予消息序列号 s, 计算得到预准备消息 (pre-prepare, H(m), s, v), 其中 H(·) 是单向哈希函数, v 代表的是此时的视图 (view), 视图一般用于记录主节点的更替, 主节点发生更替时, 视图随之增加 1. 消息发送者节点在发送消息前需利用自身私钥对消息实施数字签名. 主节点将预准备消息发送给其他备份节点.
• 准备 (prepare). 备份节点收到主节点的预准备消息, 验证 H(m) 的合法性, 即对于视图 v 和序列号s 来说, 备份节点先前并未收到其他消息. 验证通过后, 备份节点计算准备消息 (prepare, H(m), s, v) 并将其在全网广播. 与此同时, 所有节点收集准备消息, 如果收集到的合法准备消息数量大于等于 2f + 1(包含自身准备消息) 个, 则将其组成准备凭证 (prepared certificate).
• 承诺 (commit). 如果在准备阶段中, 节点收集到足够的准备消息并生成了准备凭证, 那么节点将计算承诺消息 (commit, s, v) 并广播, 将消息 m 放入到本地日志中. 与此同时节点收集网络中的承诺消息,如果收集到的合法承诺消息数量大于等于 2f +1(包含自身承诺消息), 那么将其组成承诺凭证 (committedcertificate), 证明消息 m 完成最终承诺.
• 答复 (reply). 备份节点和主节点中任意收集到足够承诺消息并组成承诺凭证的节点, 将承诺凭证作为对消息 m 的答复发送给客户端, 客户端确认消息 m 的最终承诺.

PBFT的视图切换过程

在 PBFT 中, 存在检查点 (checkpoint) 机制, 由于每个消息都被赋予了一定的序列号, 如消息 m 对应的序列号为 118, 当不少于 2f + 1 个节点组成消息 m 的承诺凭证, 完成消息承诺之后, 序列号 118 成为当前的稳定检查点 (stable checkpoint). 检查点机制被用于实现存储删减, 即当历史日志内容过多时, 节点可以选择清除稳定检查点之前的数据, 减少存储成本. 另外稳定检查点在 PBFT 的视图转换中也起到了关键作用.

当主节点超时无响应或其他节点大多数认为其存在问题时, 会进入视图转换过程. PBFT的视图转换过程如下:

• 视图转换信息广播. 备份节点 i 的当前视图 v, 当前稳定检查点 S∗, 对于稳定检查点 S∗的凭证 C(即 2f + 1 个节点的有效承诺凭证). U 为节点 i 当前视图下, 序列号大于 S∗, 且已经形成准备凭证的消息集合. 节点 i 计算视图转换消息: vci: (view-change, v + 1, S∗, C, U, i), 并将其在全网广播.
• 视图转换确认. 备份节点收集对视图 v + 1 的转换消息并验证其合法性, 验证通过后计算视图转换确认消息 vcai: (view-change-ack, v + 1, i, j, H(vcj)), 其中 i 是当前备份节点, j 是发送视图转换消息 vcj的节点, H(vcj) 是视图转换消息的摘要. vcai消息相当于对每个节点发出的视图转换消息确认. 备份节点将消息 vcai直接发送给视图 v + 1 对应的新的主节点. 视图 v + 1 的主节点由轮转方式决定.
• 新视图广播. 对于每个视图转换消息, 如节点 j 的消息 vcj, 如果 vcj合法, 则其他节点将会向主节点发送对 vcj的视图转换确认消息, 因此, 当主节点收集到 2f − 1 个对 vcj的视图转换确认消息, 则可认为 vcj有效, 并将 vcj和其对应的视图转换确认消息放入到集合 S 中. 主节点收集其他节点的有效视图转换消息, 如果 S 中消息不少于 2f 个, 则主节点计算新视图消息 nv : (new-view, v + 1, S, U∗). 其中 U∗包括当前的稳定检查点和稳定检查点之后序列号最小的预准备消息.

如上就是PBFT算法的主要两部分，PBFT 实现了状态机复制的一致性和活性, 在协议正常运行时, 通信复杂度为 O(n2). 在视图转换时, 通信复杂度为 O(n3).

基于PBFT的一些改进算法

Hot-Stuff

它对 PBFT 做出改进. Hot-Stuff 网络模型为部分同步网络, 敌手模型为 n = 3f + 1. 其采用并行流水线处理提议, 相当于将 PBFT 中的准备和承诺 阶段合并成一个阶段（使用门限签名技术），采用线性视图转换降低了视图转换中的通信复杂度。综合 LVC 和门限签名技术, Hot-Stuff 最终每轮的通信复杂度为O(n2).

SBFT 主要解决拜占庭容错协议在应用到区块链中的去中心化和扩容问题，能够允许 200 多个节点同时完成共识. SBFT 利用领导者作为信息、签名的收集者, 采用门限签名降低通信复杂度. 在 PBFT 中, 每一轮的投票, 节点需要向网络中其他节点广播投票, 并且收集其他节点的投票,而 SBFT 利用领导者收集每一轮投票, 收集到的签名数量达到门限要求以后, 领导者便能恢复总的门限签名, 从而将通信复杂度从 O(n3) 降低为 O(n2).

大体参照 https://github.com/corgi-kx/blockchain_consensus_algorithm 具体实现 https://www.github.com/kid1999/simple-pbft

对网络部分使用RPC进行替换

计划补充：

• Leader的选举和轮换（视图切换）

数据从客户端输入，到接收到节点们的回复共分为5步

1. 客户端向主节点发送请求信息
2. 主节点N0接收到客户端请求后将请求数据里的主要信息提出，并向其余节点进行preprepare发送
3. 从节点们接收到来自主节点的preprepare，首先利用主节点的公钥进行签名认证，其次将消息进行散列（消息摘要，以便缩小信息在网络中的传输大小）后，向其他节点广播prepare
4. 节点接收到2f个prepare信息（包含自己）,并全部签名验证通过，则可以进行到commit步骤，向全网其他节点广播commit
5. 节点接收到2f+1个commit信息（包含自己），并全部签名验证通过，则可以把消息存入到本地，并向客户端返回reply消息

区块链共识算法研究综述

区块链共识机制研究综述*

Practical Byzantine Fault Tolerance 论文

https://github.com/corgi-kx/blockchain_consensus_algorithm