PBFT 共识算法详解

1 系统模型

1.1 网络

PBFT 工作在异步的分布式系统中，系统中各个节点彼此通过网络连接。 系统运行时，消息的传递允许出现下列情形：

• 不能正确发送
• 延迟
• 重复
• 乱序

1.2 拜占庭错误

系统允许错误节点也就是拜占庭节点表现出任意行为，但是需要附加一个限定条件： 节点失效彼此应相互独立，从而大部分或全部节点不会同时失效。

在有恶意攻击存在的情况下，可以采取类似于下列措施来保证这个限制的成立：

• 各节点运行的服务程序和操作系统的版本尽可能多样化
• 各节点的管理员帐号和密码不同

1.3 消息加密属性

1.3.1 使用加密技术的目的

• 防止身份欺骗、重放攻击
• 监测错误消息

1.3.2 具体使用的加密技术

• 公钥签名：用于验证消息发送者身份，PBFT 中，实际上只用于 view-change 和 new-view 消息，以及出现错误的情况。其他消息都采用下面将会提到的 MAC（消息认证码）进行认证。这是算法设计中提出的一种优化措施，用于提升算法性能。
• MAC：即消息认证码，用于算法正常操作流程中的消息认证
• 消息摘要：用于检测错误消息

1.4 敌手特性

算法限定敌手（adversary）可以：

• 串通拜占庭节点

• 延迟通信或延迟正常节点

同时，敌手不可以：

• 无限延迟正常节点的通信
• 伪造正常节点签名
• 从消息摘要反推原始消息
• 让不同消息产生相同摘要

2 服务属性

2.1 关于副本复制服务

PBFT 算法可用于实现确定性的副本复制服务（Replicated service）。 副本复制服务拥有状态（state）和操作（operation）。 客户端（client）向服务发起请求，以执行操作，并等待响应。 服务由 n 个节点组成。操作可以执行任何计算，只要这些计算始终产生确定性的结果。 节点和客户端如果遵循算法的预定步骤执行操作，则被称为正常节点或客户端。

2.2 关于 Safety 和 Liveness

只要系统中失效节点的个数不超过容错数 ，系统就能提供 safety 和 liveness。

2.2.1 Safety

Safety 是指系统能保证客户端请求的线性一致性（linearizability），即请求按顺序一次一条地被执行。 PBFT 相对于之前的算法如 Rampart 等的一个显著的不同在于，其 Safety 不依赖于同步假设。 算法不需限定客户端一定是正常的，允许其发送不合法的请求，原因是各正常节点可以一致性地监测客户端请求的各种操作。并且算法可以通过权限控制的方式对客户端进行限制。

2.2.2 Liveness

由于算法不依赖于同步提供 Safety，因此必须通过同步假设来提供 Liveness。 这里的同步假设是，客户端的请求最终总能在有限的时间内被系统接收到。 客户端可能会通过多次重传的方式，发送请求到服务，确保其被服务接收到。 PBFT 所依赖的同步假设其实是比较弱的假设，原因是在真实的系统中，网络错误最终总可以修复。

2.3 关于算法弹性

PBFT 的算法弹性（resiliency）是最优的：假定系统中失效节点最大个数为 f，则系统最少只需要 3f+1 个节点就可以保证 Safety 和 Liveness。

简单证明：

考虑最坏的情况，系统有最大数量的失效节点，即 f 个 (总节点数为 n) 。客户端此时可以接收到的回复个数最坏情况是 n-f ，因为失效节点可能都不回复。

但是由于网络延迟等原因，客户端接收到的 n-f 个请求中，实际上有可能包含有失效节点的回复（有可能是错误的），而另外一些正常节点的回复还未及时收到。 这其中，最坏的情况是，n-f 个结果中，有 f 个是失效节点发送的。

按照 PBFT 算法的定义，客户端需要收到 f+1 个相同的回复，才被当作是正确的结果。

因此 n-f 个结果中，除去 f 个失效节点的结果，即 n-f-f >= f+1, 即 n >= 3f+1，因此 3f+1 是最少需要的节点数量。

2.4 关于信息保密性

一般情况下，为确保服务的高效性，不能提供容错的信息保密性。 可能可以使用 secret sharing scheme 来获得操作参数和部分对操作来说透明的状态的保密性。

3 算法主流程

3.1 主流程简介

3.1.1 相关定义

算法是状态机副本复制技术的一种形式：服务被建模为状态机，其状态在分布式系统中的不同副本节点上被复制。每个状态机副本节点保存维护着服务状态，并实现服务的各种操作。

假设所有副本节点个数为 n，算法中，每个节点依次编号为 0, 1, …, n-1

方便起见，假设系统中的副本节点总数为 3f+1。可以有更多数量的节点，但是这不会使算法的弹性更优，只会使系统的性能降低。

系统在称为视图（view）的配置下工作。视图以整数编号，从 0 开始。

在一个具体的视图 v 中，通过 p =v mod n，决定出主节点（primary），而其余节点成为副本节点（backup）。

当主节点失效时，进行视图变更（view change）。视图的编号是连续递增的。

3.1.2 算法主流程简要描述

算法主流程可简要描述如下：

1. 客户端通过向主节点发送请求，以调用服务的操作；
2. 主节点向其他所有副本节点广播该请求；
3. 各节点执行客户请求，同时将回复发送到客户端；
4. 客户端收到 f+1 个来自不同节点的相同的回复后，此回复即为本次请求的结果。

因为算法基于状态机副本复制技术，所以节点需满足两个条件：

• 必须是确定性的，即对于给定的状态，以及给定的参数集合，调用相同的操作后，将始终得到相同的结果。
• 各节点拥有相同的初始状态。

在满足上述两个条件的情况下，算法可以保证系统的 Safety 属性：即使存在失效的节点，各正常副本节点仍可以就不同的请求的执行顺序达成总体的一致。

3.2 算法主流程

接下来详细描述算法主流程。为方便起见，这里省略讨论以下细节：

• 节点因空间不足导致错误，以及如何恢复；
• 类似网络的原因等导致的客户端消息的重传。

另外，假设消息使用公钥签名进行认证，而不是更高效的 MAC 的方式。算法流程的启动从客户端发送请求开始。

3.2.1 客户端操作

客户端操作流程示意图如下：

客户端向其认为的 Primary 节点发送请求：<REQUEST, o, t, c>。其中：

• o 是请求的操作

• t 是时间戳

• c 代表客户端信息

这里省略了消息的签名，包括下文提到的所有消息都应该有发送方的签名，为了讨论方便，作了省略。

相关的几点说明：

• 请求中的时间戳用于保证请求只被执行一次的语义：所有的时间戳都严格排序，即后发送的请求比先发送的请求拥有更高的时间戳。
• 每个副本节点向客户端发送回复时，都会包含当前的视图编号。客户端可以通过该视图编号来确定当前的主节点，并且只向其认为的主节点发送请求。
• 每个副本节点执行完请求后，各自单独地向客户端发送回复，其格式为： <REPLY, v, t, c, i, r> 。其中：
  • v 是当前的视图编号
  • t 是请求发送时对应的时间戳
  • i 是副本节点的编号
  • r 是请求的操作的执行结果

• 客户端等待来自 f+1 个不同副本节点的相同回复，即 t 和 r 要相同。如果客户端等到了 f+1 个相同回复，r 即为请求的结果。 之所以该结果是有效的，是因为错误节点的个数最多为 f 个，因此必然至少有一个正常节点回复了正确结果，此结果就是 r。

• 如果客户端没有及时收到回复，则会将请求广播给所有副本节点。副本节点收到请求后，如果发现已经执行过该请求，就只是将结果重新发送至客户端；否则，它会把请求转发到主节点。如果主节点没有把请求广播给其他节点，则最终会被足够多的副本节点认定为错误节点，从而触发视图变更。

在接下的流程讨论中，假定客户端等待一个请求完成后，才发送下一个请求。但是，算法允许客户端异步地发送请求，并且可以保证不同请求按顺序执行。

3.2.2 三阶段协议

主节点收到客户端请求后，将启动三阶段协议，也就是算法接下来的流程。

这三阶段是 pre-prepare，prepare 和 commit。

前两阶段，即 pre-prepare 和 prepare 用于保证当前视图中请求被排好序，而后两阶段 prepare 和 commit 保证请求在视图变更后，仍旧是排好序的。

---

3.2.2.1 pre-prepare 阶段

pre-prepare 阶段流程示意图如下：

pre-prepare 阶段中，主节点组装预准备消息，同时把客户端请求附加在其后：<<PRE-PREPARE, v, n, d>, m>，其中：

• v 是当前视图编号，指当前消息当前在哪个视图中被编号和发送
• m 是客户端的请求消息
• n 是主节点给 m 分配的一个序号（sequence number）
• d 是 m 的摘要。

注意：请求 m 并没有放在预准备消息中，这样可以使预准备消息变得更简短。有两个好处：

1. 降低通信的负载：在视图变更时，由于各节点收到的预准备消息会被用来证明一个特定的请求确实在特定的视图中被赋予了一个序号，较简短的预准备消息将使数据传输量更少。
2. 有助于传输优化：算法运行中，一方面需要向各节点发送客户端请求，另一方面需要传输协议消息以实现对客户请求的排序。通过对这两者解耦，可以实现对较小的协议消息的传输以及对应于较大的请求的大消息的传输分别进行优化。

每个副本节点接收到预准备消息后，会进行如下校验，如果条件都满足的话，就接受该消息，否则什么也不做：

• 客户端请求和预准备消息的签名都正确；d 和 m 的消息摘要一致；
• 当前节点的当前视图是 v；
• 当前节点未曾接受另外一条预准备消息，其包含的视图编号和消息序号都和本条消息相同，但对应的是不同的客户端请求；
• 预准备消息中的序号 n 位于低水线 h 和高水线 H 之间。这是为了防止恶意主节点随意地选择序号来耗尽序号空间，例如故意选择一个非常大的序号。

如果副本节点接受预准备消息，接下来就进入 prepare 阶段，如下节所示。

---

3.2.2.2 prepare 阶段

prepare 阶段流程示意图如下：

在 prepare 阶段，节点会组装并广播准备消息给其他所有副本节点，同时把预准备和准备消息写入到本地消息日志中。

准备消息格式如下： <PREPARE, v, n, d, i>。其中：

• i 为节点编号

  其余参数和预准备消息中的含义相同。

副本节点（包括主节点）收到其他节点发送过来的准备消息时，会进行校验，如果消息满足下列条件，则会接受准备消息，并写入消息日志中：

• 签名正确
• 其视图编号和节点的当前视图编号相同
• 消息中的序号在 h 和 H 之间

对于一个副本节点 i 来说，如果其消息日志中包含如下消息：

• 客户端请求 m
• 在视图 v 中将 m 分配序号 n 的预准备消息
• 2f 个由不同的副本节点发送的、和预准备消息相匹配的准备消息（匹配是指有相同的视图编号、请求序号，以及消息摘要）

我们就称 prepared (m, v, n, i) 为 true。

算法的预准备和准备阶段用于保证所有的正常副本节点就同一视图中的所有请求的顺序达成一致。具体来说，这两阶段能确保以下不变式：

• 如果 prepared (m, v, n, i) 为 true，则对任意一个正常的副本节点 j (包含 i) 来说，prepared (m’, v, n, j) 肯定为 false（这里 m’ 是不同于 m 的一个请求）。

简单证明：

因为 prepared (m, v, n, i) 为 true，而错误节点最多为 f 个，所以至少有 f 个正常节点发送了准备消息，再加上主节点，这样至少有 f+1 个节点已经就 m 在视图 v 中被编号为 n 达成了一致。

因此，如果 prepared (m’, v, n, j) 为 true，意味着上述 f+1 个节点中至少有一个节点发送了两个相互矛盾的预准备或准备消息，也就是说，这些消息拥有相同的视图编号和序号，但是对应着不同的请求消息。

但这是不可能的，因为该节点是正常节点，因此 prepared (m’, v, n, j) 一定为 false。

对于副本节点 i 来说，prepared (m, v, n, i) 变为 true，则其将进入 commit 阶段，如下节所示。

---

3.2.2.3 commit 阶段

commit 阶段流程示意图如下：

节点进入 commit 阶段时，副本节点 i 将向其他所有副本节点广播确认消息：<COMMIT, v, n, D(m), i>，其中：

• D(m)是 m 的消息摘要

  其余参数和预准备消息和准备消息中的含义相同。

对于副本节点来说，当其收到其他节点发来的确认消息的时候，如果消息满足下列条件，则节点则会接受确认消息并写入本地的日志消息中：

• 签名正确；
• 消息中的视图编号等于当前节点的视图编号；
• 消息中的请求序号在 h 和 H 之间。

对于副本节点 i 来说，如果：

• prepared (m, v, n, i) 为 true
• 并且已经接受了 2f+1 个来自不同节点的、和 m 对应的预准备消息相匹配（匹配是指它们有相同的视图编号、消息序号，以及消息摘要）的确认消息（可能包含它自己的）

我们称 committed-local (m, v, n, i) 为 true。

另外，如果至少存在 f+1 个节点，对于其中每一个节点 i 来说，prepared (m, v, n, i) 为 true，我们则称 committed (m, v, n) 为 true。

commit 阶段能保证以下不变式：

• 如果对某个副本节点来说，committed-local (m, v, n, i) 为 true，则 committed (m, v, n) s 也为 true。

上述不变式和视图变更协议一起能够保证：

• 所有正常节点能够就所有本地确认的请求的序号达成一致，即使这些请求是在不同的视图中确认的。

另外，该不变式也能保证：任何一个请求如果在一个副本节点被确认，那么它最终也会被至少 f+1 个副本节点确认。

对于任何一个副本节点 i 来说，如果 committed-local (m, v, n, i) 为 true，i 的状态反映了所有序号小于 n 的请求顺序执行的结果。此时，它就可以执行 m 所请求的操作。这就保证了所有的正常节点，按相同的顺序执行请求，从而保证算法的安全性。在执行了请求的操作后，每个节点单独地给客户端发送回复。对于同样内容的请求，节点会忽略那些时间戳更早的，以保证请求只被执行一次。

此外，算法并不要求消息按顺序投递，因此，节点可以乱序确认请求。这样做没有问题，因为算法只在一个请求对应的预准备、准备和确认消息都收集完全时才会执行该请求。

以下是 f=1，即拜占庭节点数为 1 ，总节点数为 4 时，PBFT 算法的运行示意图：

容错证明：

• 设系统节点数为 n ，其中拜占庭节点数为 f ，系统需要根据节点发来的消息做判断。
• 为了共识正常进行，在收到 n-f 个消息时，就应该进行处理，因为可能有 f 个节点根本不发送消息。
• 根据收到的 n-f 个消息做判断，判断的原则至少 f+1 个相同结果。
• 但最坏情况下，收到的 n-f 个消息中可能有 f 个假消息（由于网络延迟等原因，未收到的是 f 个正常节点的消息）
• 在此情况下仍能正确共识，应保证：n - f - f >= f + 1, 即 f <= (n-1) / 3

---

垃圾回收

为保证安全性（safety），需要保证：

1. 对于每个请求来说，在被至少 f+1 个正常节点执行之前，所有相关的消息都必须记录在消息日志中
2. 如果一条请求被执行，节点能够在视图变更中向其他节点证明这一点

另外，如果某个副本节点缺失的一些消息正好已经被所有正常节点删除，则需要通过传输部分或全部的服务状态来使节点状态更新到最新。因此，节点需要某种方式来证明状态的正确性。

如果每执行一次操作，都生成一个状态证明，代价将会很大。因此可以每执行一定数量的请求后生成一次状态证明，例如：只要节点序号是某个值比如 100 的整数倍时，就生成一次，此时称这个状态为检查点 checkpoint 。如果一个检查点带有相应的证明，我们则称其为稳定检查点 stable checkpoint 。

checkpoint 就是当前节点处理的最新请求序号。stable checkpoint 就是大部分节点 （2f+1） 已经共识完成的最大请求序号。

stable checkpoint 的作用：就是减少内存的占用。

稳定检查点的生成过程：

1. 副本节点 i 生成一个检查点之后，会组装检查点消息，并全网广播给其他所有副本节点，检查点消息格式： <CHECKPOINT, n, d, i>，n 指的是生成目前最新状态的最后一条执行请求的序号，d 是当前服务状态的摘要。
2. 每个副本节点等待并收集 2f+1 个来自其它副本节点的检查点消息（有可能包括自己的），这些消息有相同的序号 n 和摘要 d。这 2f+1 个检查点消息就是该检查点的正确性证明。

一旦一个检查点成为稳定检查点后，节点将从本地消息日志中删除所有序号小于或等于 n 的请求所对应的预准备、准备和确认消息。同时，会删除所有更早的检查点和对应的检查点消息。

检查点的生成协议可以用来移动低水线 h 和高水线 H

高低水线：

• h 的值就是最新稳定检查点所对应的稳定消息序号；
• 高水线 H = h+k，这里 k 要设置足够大，至少要大于检查点的生成周期，比如说：假如每隔 100 条请求生成检查点，k 就可以取 200。

例子：

如果 B 当前的 checkpoint 已经为 1134，而A的 checkpoint 还是 1039 ，假如有新请求给 B 处理时，B会选择等待

等到 A 节点也处理到和 B 差不多的请求编号时，比如 A 也处理到 1112 了，这时会有一个机制更新所有节点的 stabel checkpoint

比如可以把 stabel checkpoint 设置成 1100 ，于是 B 又可以处理新的请求了，如果 L 保持100 不变，这时的高水位就会变成 1100+100=1200 了。

视图变更

PBFT 算法运行过程中，如果主节点失效了，为了保持系统的活性（liveness），就需要用到视图变更协议。

view-change 会有三个阶段，分别是 view-change ， view-change-ack 和 new-view 阶段。

从节点认为主节点有问题时，会向其它节点发送 view-change 消息，当前存活的节点编号最小的节点将成为新的主节点。

当新的主节点收到 2f 个其它节点的 view-change 消息，则证明有足够多人的节点认为主节点有问题，于是就会向其它节点广播 New-view 消息。

注意：从节点不会发起 new-view 事件。

对于主节点，发送 new-view 消息后会继续执行上个视图未处理完的请求，从 pre-prepare 阶段开始。其它节点验证 new-view 消息通过后，就会处理主节点发来的 pre-prepare 消息，这时执行的过程就是前面描述的 PBFT 过程。到这时，正式进入 v+1 （视图编号加1）的时代了。

视图变更过程中，节点将不再接受其他任何类型的消息，只接受 checkpoint, view-change, 和 new-view 消息。

视图变更过程

1. 节点检查到 timer 超期会停止接受消息并多播一个 view-change 消息 <VIEW-CHANGE,v+1,n,C,P,i> 给所有的replica。

   消息中的各字段含义：

   • v+1：要变更到的目标视图编号；
   • n：对应于节点已知的、最新的检查点 s 的请求序号；
   • C：包含 2f+1 个检查点消息<CHECKPOINT,n,d,i>的集合。这些检查点消息用于证明稳定检查点 s 的正确性；
   • P：由 Pm 构成，m 是所有大于 n 的消息的序列号，集合 Pm 是由在 i 中达成 prepared 状态的消息的集合，Pm 的内容包括关于 m 的 pre-prepare 消息和 2f 个 prepare 消息。

2. 新视图中的新主节点将收集来自其他副本节点的 view-change 消息。当其收集到 2f 个有效的 对应新视图 v+1 的 view-change 消息后，将组装并广播 new-view 消息 <NEW-VIEW,v+1,V,O>。

   消息中的各字段含义：

   • V：有效的 对应于新视图 v+1 的 2f+1 个 view-change 消息（包括主节点自己组装的）的集合；

   • O：pre-prepare状态的消息的集合

     • O 的确定：

       1）根据 V 中各条 view-change 消息中包含的 pre-prepare 和 prepare 消息，主节点先找到最新的稳定检查点，将其对应的消息序号赋值给 min-s;

       2）然后从所有 prepare 消息中找到最大的那个消息序号，将其赋值给 max-s;

       3）然后，对于 min-s 和 max-s 之间的每一个消息序号 n， 主节点为其组装位于视图 v+1 上的 pre-prepare 消息。每条消息会有两种情况:

       ​ a) 存在 view-change 消息， 其 P 集合中存在一个 Pm 包含的 prepare 消息中包含对应序号为n的消息，则组装 <PRE-PREPARE, v+1, n, d>；

       ​ 其中，d 是 V 中特定请求消息的摘要，并且该请求在 V 中的一个最新视图上的 pre-prepare 消息中被分配了序号 n 。

       ​ b) V 中不存在和 n 对应的 prepare 消息。此时主节点模拟一个特殊的空请求（null request）组装 <PRE-PREPARE, v+1, n, D(null)>;

       ​ 其中，D (null) 为空请求的摘要。空请求和其他请求一样进行三阶段协议，但是其执行就是一个空操作（noop）。

3. 主节点广播 new-view 消息后，也会把 O 中的消息写入本地消息日志中。同时，如果主节点本地的最新稳定检查点的消息序号落后于 min-s 的话，则会将 min-s 对应的检查点消息写入消息日志，并按之前介绍的垃圾回收机制删除所有的历史消息。
4. 此时，主节点正式变更到新视图 v+1， 开始接收消息。
5. 每个副本节点收到针对 v+1 视图的 new-view 消息后，会进行校验，是否满足以下条件：
   • 签名正确；
   • 其中包含的 view-change 消息是针对 v+1 视图，并且有效；
   • 集合 O 中的信息正确、有效。

之后，在新的视图中，针对所有序号位于 min-s 和 max-s 之间的请求，系统会重新运行三阶段协议。只不过对于每一个副本节点来说，如果当前确认的请求之前已经执行过的话，节点就不再执行该请求。

视图变更完成。

可以这样理解，在新的 view 中，节点是在上一轮 view 中各个节点的 prepared 状态基础上进行共识流程的。

发生view转换时，需要的保证的是：如果视图转换之前的消息 m 被分配了序号 n , 并且达到了 prepared 状态，那么在视图转换之后，该消息也必须被分配序号 n (safety特性)。因为达到 prepared 状态以后，就有可能存在某个节点 commit-local。要保证对于 m 的commit-local，在视图转换之后，其他节点的commit-local 依然是一样的序号。

视图变更中节点的信息同步

视图变更时，由于 new-view 消息中并不包含原始的客户端请求，因此副本节点可能缺失某条客户端请求 m ，或者某个稳定检查点。

此时节点可以从其他副本节点同步缺失的信息。例如，假如节点 i 缺失某个稳定检查点 s ，这个检查点在 V 中可以找到相应的证明，也就是 对应的 checkpoint 消息。由于总共有 2f+1 个这样的消息，而错误节点最多 f 个，因此至少有 f+1 个正常节点发送过这样的消息。因此，可以从这些正常节点获取到对应的检查点状态。

算法优化

减少系统通信量

可以采用三种方法减少系统通信量：

1. 向客户端发送回复的消息摘要，而不是回复的原始内容。

   客户端指定一个特定的副本节点，从该节点接收完整的回复内容，而只从其他所有节点处接收回复的摘要。通过判读摘要与回复的一致性以及对回复计数，可以确保接收到正确的回复。如果客户端接收不到正确结果，就会按正常流程重新请求系统，并接收不同节点的完整回复。

2. 请求在副本节点 prepared 后，节点即试探性地执行请求，并发送结果。客户端只要收到 2f+1 个匹配的结果，就可以确保该结果的正确性。

   也就是说，该请求最终会确认（至少 f+1 个正常副本节点的本地确认）。如果客户端无法得到正确结果，就重新发送请求，系统执行正常流程。一个被试探性执行的请求，有可能在视图变更过程中被中断，并被替换为一个空请求。此时，已经执行过请求的节点可以通过 new-view 消息中的最新的稳定检查点或本地的检查点来更新状态（取决于哪个序号更大）。

3. 针对只读操作，客户端将请求广播到每一个副本节点。各节点判断请求确实为只读且满足条件后，直接执行请求，并发送回复到客户端。客户端收到 2f+1 个相同的回复，即为正确结果；否则客户端之前设置的重发请求定时器将触发超时，使得客户端重发请求，系统执行正常流程。

   这种优化的前提条件是，副本节点在执行请求之前，需确保之前所有请求都已确认，并且被执行。

加快消息验证速度

使用公钥签名的方式验证消息存在如下不足：

• 类似于 RSA 这样的签名算法，签名速度比较慢；

• 其他公钥密码系统，如椭圆曲线公钥密码系统，虽然签名更快，但是验签更慢。

PBFT 算法实际上在正常流程中采用 MAC (Message Authentication Code，消息验证码) 认证消息，因为它具有如下优点，使得算法相对于之前的算法性能提升了一个数量级以上：

• MAC 计算速度快；

• 通过适当优化，可以减少其长度；

• 通过对 authenticator（vector of MAC）的使用，可以使验证时间为常量，而生成时间只随着节点数量线性增长。

具体来说，PBFT 算法中使用 MAC 和公钥签名的具体场景是：

• 所有正常操作流程中使用 MAC 验证消息；

• 视图变更中的消息：view-change, new-view，以及出现错误时，使用公钥签名。这些场景的出现频率相对较低，从而对算法的性能影响较小。

为什么不能是两阶段

• Prepared 状态可以证明在节点 i 看来非拜占庭节点在只有请求 m 使用<v, n>上达成一致。

• Prepared 是一个局部视角，不是全局一致，即副本 i 看到了非拜占庭节点认可了<m, v, n>，副本 i 无法确定，其他副本也达到Prepared状态。
• 如果只有少数副本成为 Prepared 状态，然后执行了请求 m，系统就出现了不一致。

现在我们假设，如果共识只有两个阶段，节点 A 中某个序号 n 对应的消息 m 收到了来自其他 2f 个节点的 prepare 消息，进入 prepared 状态，因为没有commit 阶段，节点 A 直接执行 m 并向 client 发送 REPLY。此时网络中只有少数节点跟 A 一样对消息 m 达到 prepared 状态，其他节点仍然在等待足够的 prepare 消息。 这时节点们发现已经很久没有收到主节点发来的消息了，所以他们将本地的消息打包，广播了一条 view change 消息。根据原文，view change 过程中节点是无法接收到与 view change 无关的消息的，自然也无法接收prepare。 当新视图中主节点准备生成 V 时，它或许可以发现某个序号 n 只在少数节点中达到了 prepared 状态，它可以选择忽略，将其他 2f+1 个节点的 P 打包进 V 里，由此生成 O 并广播。这样新视图里 n 对应的将是一个空消息。当然主节点可以做得更绝，它可以发出 <n，m’> 的 pre-prepare 消息，这样不明就里的其他节点就会被欺骗，最后对 m’ 达成共识。 到这一步可以发现，如果没有 commit 阶段，两个视图中 n 可能对应不同的消息 m 和 m’，这就违背了 PBFT 设计的原则，因为 PBFT 要求即使是跨视图，n 与 m 的匹配也应该是唯一的。

• PBFT 中 prepare 阶段的算法效果 ( prepared, local view ) 在 prepare 阶段，在算法正常进行时，每一个合法的节点都将接收到至少2/3的投票数，我们将“一个节点接收到至少2/3的投票数”称为事件 A，显然至少2/3节点都发生了事件 A，但是节点之间不知道彼此之间是否发生了事件 A；

• PBFT 中 commit 阶段的算法效果 ( commit-local, local view ) 在 commit 阶段，每一个节点都会将自己发生了事件 A 的消息广播给其他节点，并收集其他节点关于事件 A 的广播，我们把“收集到至少2/3节点广播事件 A ”称作事件 B，此时，每一个节点都知道至少有2/3节点都发生了事件 A，但是不确定其他节点是否知道事件 B。

• PBFT 中 reply 阶段的算法效果 ( commited, global-view ) 在 reply 阶段，每一个节点都将事件 B 返回给 client，此时 client 只要收集到至少2/3节点的事件 B 的广播时，就可以判断，系统已经对该 proposal 形成共识，因为事件 B 表示“至少2/3节点都知道有至少2/3节点对proposal进行了投票”，将“收集到至少2/3节点的事件B的广播”称作事件C。

Raft 与 PBFT 的对比

对比点	Raft	PBFT
适用环境	私链	联盟链
算法通信复杂度	O(N)	O(N^2)
容错	崩溃容错，故障节点 f <= (n-1) / 2	拜占庭容错，拜占庭节点 f <= (n-1) / 3
流程对比	1. leader 选举（谁快谁当）2. 共识过程 3. 重选 leader机制	1. leader 选举（按编号轮询）2.共识过程 3. 重选 leader 机制

复杂度分析：

• 对于 Raft 算法，核心共识过程是日志复制这个过程，这个过程分两个阶段，一个是日志记录，一个是提交数据。

  两个过程都只需要领导者发送消息给跟随者节点，跟随者节点返回消息给领导者节点即可完成，跟随者节点之间是无需沟通的。

  所以如果集群总节点数为 n，日志记录阶段通信次数为 n-1，提交数据阶段通信次数也为 n-1，总通信次数为 2n-2，因此 Raft 算法复杂度为 O(N) 。

• 对于 PBFT 算法，核心过程有三个阶段，分别是 pre-prepare （预准备）阶段，prepare （准备）阶段和 commit （提交）阶段。

  对于 pre-prepare 阶段，主节点广播 pre-prepare 消息给其它节点即可，因此通信次数为 n-1 ；

  对于 prepare 阶段，每个节点如果同意请求后，都需要向其它节点再 广播 prepare 消息，所以总的通信次数为 n*(n-1)，即 n^2-n ；

  对于 commit 阶段，每个节点如果达到 prepared 状态后，都需要向其它节点广播 commit 消息，所以总的通信次数也为 n*(n-1) ，即 n^2-n 。

  所以总通信次数为 (n-1) + (n^2-n) + (n^2-n) ，即 2n^2-n-1 ，因此 PBFT 算法复杂度为 O(N^2) 。

流程的对比上，对于 leader 选举这块， Raft 算法本质是谁快谁当选，而 PBFT 算法是按编号依次轮流做主节点。对于共识过程和重选 leader 机制这块，为了更形象的描述这两个算法，接下来会把 Raft 和 PBFT 的共识过程比喻成一个团队是如何执行命令的过程，从这个角度去理解 Raft 算法和 PBFT 的区别。

一个团队一定会有一个老大和普通成员。对于 Raft 算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新老大呢？只有当老大挂了才重选老大。

对于 PBFT 算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人 （2f+1） 都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。