详解实用拜占庭协议PBFT | 深入浅出区块链 | 技术博客

PBFT 算法和 Raft 算法解决的核心问题都是在分布式环境下如何保持集群状态的一致性，简而言之就是一组服务，给定一组操作，最后得到一致的结果。

 PBFT 算法假设的环境又比 Raft 算法更加的’恶劣‘，Raft 算法只支持容错故障节点，而 PBFT 算法除了需要支持容错故障节点之外，还需要容忍作恶节点。

作恶节点节点是指可能对接收到的消息作出截然相反的回复，甚至伪造消息。

 PBFT 算法中节点只有两种角色，主节点（primary） 和 副本（replica），两种角色之间可以相互转换。两者之间的转换又引入了 视图（view） 的概念，视图 在 PBFT 算法中起到逻辑时钟的作用。

  为了更多的容错性，PBFT 算法最大的容错节点数量 ( n - 1 ) / 3，也就是是说 4 个节点的集群最多只能容忍一个节点作恶或者故障。而 Raft 算法的最大容错节点是 ( n - 1) / 2，5 个节点的集群可以容忍 2 个节点故障。

为什么 PBFT 算法只能容忍 (n-1)/3 个作恶节点？

节点总数是 n，其中作恶节点有 f，那么剩下的正确节点为 n - f，意味着只要收到 n - f 个消息就能做出决定，但是这 n - f 个消息有可能由 f 个是由作恶节点冒充的，那么正确的消息就是 n - f - f 个，为了多数一致，正确消息必须占多数，也就是 n - f - f > f，但是节点必须是整数个，所以 n 最少是 3f+1 个。

或者可以这样理解，假定 f 个节点是故障节点，f 个节点是作恶，那么达成一致需要的正确节点最少就是 f+1 个，当然这是最坏的情况，如果故障节点集合和拜占庭节点集合有重复，可以不需要 f+1 个正确节点，但是为了保证最坏的情况算法还能正常运行，所以必须保证正确节点数量是 f+1 个。

  在算法开始阶段，主节点 由 p = v mod n 计算得出，随着 v 的增长可以看到 p 不断变化，论文里目前还是轮流坐庄的方法，这里是一个优化点。

  首先客户端发送消息 m 给主节点 p，主节点就开始了 PBFT 三阶段协议，三个阶段分别是 预准备（pre-prepare），准备（prepare），提交（commit）。
  其中 pre-prepare 和 prepare 阶段最重要的任务是保证，同一个 主节点 发出的请求在同一个 视图（view） 中的顺序是一致的，prepare 和 commit 阶段最重要的任务是保证请求在不同 视图 之间的顺序是一致的。

• 主节点收到客户端发送来的消息后，构造 pre-prepare 消息结构体 < <PRE-PREPARE, v, n, d>, m > 广播到集群中的其它节点。

  1. PRE-PREPARE 标识当前消息所处的协议阶段。
  2. v 标识当前视图编号。
  3. n 为主节点广播消息的一个唯一递增序号。
  4. d 为 m 的消息摘要。
  5. m 为客户端发来的消息。

• 副本(backup) 收到主节点请求后，会对消息进行检查，检查通过会存储在本节点。当节点收到 2f+1（包括自己）个相同的消息后，会进入 PREPARE 状态，广播消息 < <PREPARA, v, n, d, i> >，其中 i 是本节点的编号。对消息的有效性有如下检查：

  1. 检查收到的消息体中摘要 d，是否和自己对 m 生成的摘要一致，确保消息的完整性。
  2. 检查 v 是否和当前视图 v 一致。
  3. 检查序号 n 是否在水线 h 和 H 之间，避免快速消耗可用序号。
  4. 检查之前是否接收过相同序号 n 和 v，但是不同摘要 d 的消息。

• 副本 收到 2f+1（包括自己）个一致的 PREPARE 消息后，会进入 COMMIT 阶段，并且广播消息 < COMMIT, v, n, D(m), i > 给集群中的其它节点。在收到 PREPARE 消息后，副本同样也会对消息进行有效性检查，检查的内容是上文 1, 2, 3。

• 副本 收到 2f+1（包括自己）个一致的 COMMIT 个消息后执行 m 中包含的操作，其中，如果有多个 m 则按照序号 n 从小到大执行，执行完毕后发送执行成功的消息给客户端。

下面就是算法的流程图：

  Pbft 算法在运行的过程中，日志会不断累积的，但是在实际的系统中，无论是从日志占用的磁盘空间，还是新节点加入集群，同步日志的网络消耗来看，日志都不能无限的增长。

  Pbft 采用 检查点（checkpoint） 机制来压缩日志，其本质和 Raft 算法采用快照的形式清理日志是一样的，只是实现的方式不同。

  为每一次操作创建一个集群中稳定检查点，代价是非常昂贵的，Pbft 为常数个操作创建一次稳定检查点，比如每 100 个操作创建一次检查点，而这个检查点就是 checkpoint，当这个 checkpoint 得到集群中多数节点认可以后，就变成了稳定检查点 stable checkpoint。

  当节点 i 生成 checkpoint 后会广播消息 <CHECKPOINT, n, d, i> 其中 n 是最后一次执行的消息序号，d 是 n 执行后的状态机状态的摘要。每个节点收到 2f+1 个相同 n 和 d 的 checkpoint 消息以后，checkpoint 就变成了 stable checkpoint。同时删除本地序号小于等于 n 的消息。

  同时 checkpoint 还有一个提高 水线（water mark） 的作用，当一个 stable checkpoint 被创建的时候，水线 h 被修改为 stable checkpoint 的 n，水线 H 为 h + k 而 k 就是之前用到创建 checkpoint 的那个常数。

视图切换（View-Change）

  在正常流程中，可以看到所有客户端发来的消息 m 都是由主节点 p 广播到集群的，但是当主节点突然宕机，又怎么保证集群的可用性呢？

  view-change 提供了一种当主节点宕机以后依然可以保证集群可用性的机制。view-change 通过计时器来进行切换，避免副本长时间的等待请求。
  当副本收到请求时，就启动一个计时器，如果这个时候刚好有定时器在运行就重置（reset）定时器，但是 主节点 宕机的时候，副本 i 就会在当前 视图 v 中超时，这个时候副本 i 就会触发 view-change 的操作，将视图切换为 v+1。

• 副本 i 会停止接收除了 checkpoint，view-change 和 new view-change 以外的请求，同时广播消息 <VIEW-CHANGE, v+1, n, C, P, i> 的消息到集群。
  1. n 是节点 i 知道的最后一个 stable checkpoint 的消息序号。
  2. C 是节点 i 保存的经过 2f+1 个节点确认 stable checkpoint 消息的集合。
  3. P 是一个保存了 n 之后所有已经达到 prepared 状态消息的集合。
• 当在视图( v+1 )中的主节点 p1 接收到 2f 个有效的将视图变更为 v+1 的消息以后，p1 就会广播一条消息 <NEW-VIEW, v+1, V, Q>
  1. V 是 p1 收到的，包括自己发送的 view-change 的消息集合。
  2. Q 是 PRE-PREPARE 状态的消息集合，但是这个 PRE-PREPARE 消息是从 PREPARE 状态的消息转换过来的。
• 从节点接收到 NEW-VIEW 消息后，校验签名，V 和 Q 中的消息是否合法，验证通过，主节点和副本都 进入视图 v+1。

  当 p1 在接收到 2f+1 个 VIEW-CHANGE 消息以后，可以确定 stable checkpoint 之前的消息在视图切换的过程中不会丢，但是当前检查点之后，下一个检查点之前的已经 PREPARE 可能会被丢弃，在视图切换到 v+1 后，Pbft 会把旧视图中已经 PREPARE 的消息变为 PRE-PREPARE 然后新广播。

• 如果集合 P 为空，广播 <PRE-PREPARE, v+1, n, null>，接收节点就什么也不做。
• 如果集合 P 不为空，广播 <PRE-PREPARE, v+1, n,d>

  总结一下，在 view-change 中最为重要的就是 C，P，Q 三个消息的集合，C 确保了视图变更的时候，stable checkpoint 之前的状态安全。P 确保了视图变更前，已经 PREPARE 的消息的安全。Q 确保了视图变更后 P 集合中的消息安全。回想一下 pre-prepare 和 prepare 阶段最重要的任务是保证，同一个 主节点 发出的请求在同一个 视图（view） 中的顺序是一致的，而在视图切换过程中的 C，P，Q 三个集合就是解决这个问题的。

  集群在运行过程中，可能出现网络抖动、磁盘故障等原因，会导致部分节点的执行速度落后大多数节点，而传统的 PBFT 拜占庭共识算法并没有实现主动恢复的功能，因此需要添加主动恢复的功能才能参与后续的共识流程，主动恢复会索取网络中其他节点的视图，最新的区块高度等信息，更新自身的状态，最终与网络中其他节点的数据保持一致。
  在 Raft 中采用的方式是主节点记录每个跟随者提交的日志编号，发送心跳包时携带额外信息的方式来保持同步，在 Pbft 中采用了 视图协商（NegotiateView） 的机制来保持同步。
  一个节点落后太多，这个时候它收到主节点发来的消息时，对消息 水线（water mark） 的检查会失败，这个时候计时器超时，发送 view-change 的消息，但是由于只有自己发起 view-change 达不到 2f+1 个节点的数量，本来正常运行的节点就退化为一个拜占庭节点，尽管是非主观的原因，为了尽可能保证集群的稳定性，所以加入了 视图协商（NegotiateView） 机制。
  当一个节点多次 view-change 失败就触发 NegotiateView 同步集群数据，流程如下；

• 新增节点 Replica 4 发起 NegotiateView 消息给其他节点；
• 其余节点收到消息以后，返回自己的视图信息，节点 ID，节点总数 N；
• Replica 4 收到 2f+1 个相同的消息后，如果 quorum 个视图编号和自己不同，则同步 view 和 N；
• Replica 4 同步完视图后，发送 RevoeryToCheckpoint 的消息，其中包含自身的 checkpoint 信息；
• 其余节点收到 RevoeryToCheckpoint 后将自身最新的检查点信息返回给 Replica 4;
• Replica 4 收到 quorum 个消息后，更新自己的检查点到最新，更新完成以后向正常节点索要 pset、qset 和 cset 的信息（即 PBFT 算法中 pre-prepare 阶段、prepare 阶段和 commit 阶段的数据）同步至全网最新状态；

  Replica 5 新节点加入的流程如下图所示；

• 新节点启动以后，向网络中其他节点建立连接并且发送 AddNode 消息；
• 当集群中的节点收到 AddNode 消息后，会广播 AgreeAdd 的消息；
• 当一个节点收到 2f+1 个 AgreeAdd 的消息后，会发送 AgreeAdd 的消息给 Replica 5
• Replica 5 会从收到的消息中，挑选一个节点同步数据，具体的过程在主动恢复中有说明，同步完成以后发送 JoinNet
• 当集群中其他节点收到 JoinNet 之后重新计算视图 view，节点总数 N，同时将 PQC 信息封装到 AgreeJoinOrExit 中广播
• 当收到 2f+1 个有效的 AgreeJoinOrExit 后，新的主节点广播 UpdateNet 消息完成新增节点流程

  删除节点的流程和新增节点的过程类似：

##Q&A

Q：为什么 PBFT 算法需要三个阶段？
A：假如简化为两个阶段 pre-prepare 和 prepare，当一个节点 A 收到 2f+1 个相同的 prepare 后执行请求，一部分节点 B 发生 view-change，在 view-change 的过程中是拒收 prepare 消息的，所以这一部分节点的状态机会少执行一个请求，当 view-change 切换成功后重放 prepare 消息，在重放的过程中，节点 A 也完成了 view-change，这个时候 A 就会面临重放的 prepare 已经执行过了，是否需要再次执行？会导致状态机出现二义性。

---

Q：view-change 阶段集群会不可用么？
A：view-change 阶段集群会出现短暂的不可用，一般在实践的时候都会实现一个缓冲区来减少影响，实现参考 以太坊 TXpool 分析。

---

Q：Pbft 算法的时间复杂度？
A：Pbft 算法的时间复杂度 O(n^2)，在 prepare 和 commit 阶段会将消息广播两次，一般而言，Pbft 集群中的节点都不会超过 100。

本文作者是深入浅出区块链共建者清源，欢迎关注清源的博客，不定期分享一些区块链底层技术文章。

深入浅出区块链 - 打造高质量区块链技术博客，学区块链都来这里，关注知乎、微博。