PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错）由Miguel Castro和Barbara Liskov于1999年首次提出。PBFT算法的目标是在存在最多f个拜占庭故障节点的情况下，仍然能够实现分布式系统的一致性。这个有一个重要的概念——拜占庭容错。拜占庭容错（Byzantine Fault Tolerance，BFT）是分布式计算领域中的一个重要概念，指的是在存在恶意节点（拜占庭节点）的情况下，仍能够保持分布式系统的正确性和一致性。
"拜占庭"一词最早来源于古代拜占庭帝国（Byzantine Empire），是一个位于今天的土耳其伊斯坦布尔的城市，曾是罗马帝国的东部延伸。计算机领域借用的"拜占庭"来自分布式领域的拜占庭将军问题，其描述如下：在一个军队中，有多个将军（Generals）希望协调一个共同的行动，比如进攻或撤退。这些将军通过发送消息来达成共识，但有些将军可能是拜占庭（恶意）的，它们可以发送虚假的消息，试图破坏协调。问题的关键是如何让所有忠诚的将军在不受恶意将军干扰的情况下达成一致的行动决策。
拜占庭将军问题的难点在于，当存在恶意将军发送虚假消息时，忠诚将军需要能够判断哪些消息是正确的，以便做出正确的决策。解决这个问题需要设计一种拜占庭容错的共识算法，使得系统能够在最多f个拜占庭将军的情况下依然能够达成共识，其中f是拜占庭将军的数量。下面算法部分将会对f的取值进行论证。
拜占庭容错算法需要满足以下两个条件：
-
一致性条件（Consistency）：至少有一个忠诚节点提议一个值，那么所有忠诚节点都会接受这个值。
-
合法性条件（Validity）：如果提议的值是一个有效的值（不是恶意节点发送的虚假值），那么只要有一个忠诚节点接受了这个值，其他忠诚节点也会接受。
PBFT只是拜占庭容错的一种实现，像 HoneyBadgerBFT、Tendermint等也都是其不同的实现。这些算法通过在节点之间进行多轮通信、投票和验证等方式，确保系统能够在拜占庭节点的存在下依然保持正确性和一致性。
PBFT(Practical Byzantine Fault Tolerance)共识算法可以在少数节点作恶(如伪造消息)场景中达成共识，它采用签名、签名验证、哈希等密码学算法确保消息传递过程中的防篡改性、防伪造性、不可抵赖性，并优化了前人工作，将拜占庭容错算法复杂度从指数级降低到多项式级别。当存在 f 个拜占庭故障节点(节点可能会不响应请求，也可能错误响应请求)时必须保证存在至少 3f+1 个副本数量，这样才能保证在异步系统中提供安全性和活性。这么多数量的副本是需要的，由于 f 个副本有可能失效而不发回响应，所以在同 n-f 个节点通讯后系统必须做出正确判断（由于前面假设的条件是最多f个故障节点，所以这f个节点可能会不发送消息，所以我们只需要接收到n-f个节点的响应就需要做出判断，而不能一直等待所有节点都响应）。但是，有可能 f 个未及时响应的节点都是好节点，f 个坏节点依然发送了相反的请求。尽管如此，系统仍旧需要好节点的返回数量大于坏节点的返回数量，即 n-f-f>f，因此得到 n>3f。
所有的副本在一个被称为视图（View）的轮换过程（succession of configuration）中运作。在某个视图中，一个副本作为主节点（primary），其他的副本作为备份（backups）。视图是连续编号的整数。**主节点由公式 p = v mod |R | 计算得到，**这里 v 是视图编号，p 是副本编号，|R | 是副本集合的个数。当主节点失效的时候就需要启动视图更换（view change）过程。Viewstamped Replication 算法和 Paxos 算法就是使用类似方法解决良性容错的。
重要概念:
- View： 节点运行过程中, 全网络的配置 (configuration) 是在不断变化的. 比方说现在的配置是 A 节点是主节点, 其余节点都是从节点, 那么一段时间后, 这个配置可能改变为 B 节点为主节点, 其余从节点。 **我们将每一次的配置状态称为一个 View。**整个网络就是不断在不同的 View 之间切换的. 记当前 View 的编号为 v, 编号为 p = v % n 的节点就作为主节点, 其余作为从节点。当主节点失效时, 进行 View 的切换。
PBFT 算法如下： 1. 客户端向主节点发送请求调用服务操作 ；2. 主节点通过广播将请求发送给其他副本； 3. 所有副本都执行请求并将结果发回客户端； 4. 客户端需要等待 f+1 个不同副本节点发回相同的结果，作为整个操作的最终结果。
同所有的状态机副本复制技术一样，PBFT 对每个副本节点提出了两个限定条件：（1）所有节点必须是确定性的。也就是说，在给定状态和参数相同的情况下，操作执行的结果必须相同；（2）所有节点必须从相同的状态开始执行。在这两个限定条件下，即使失效的副本节点存在，PBFT 算法对所有非失效副本节点的请求执行总顺序达成一致，从而保证安全性。
客户端 c 向主节点发送 <REQUEST,o,t,c> 请求执行状态机操作 o，这里时间戳 t 用来保证客户端请求只会执行一次。客户端 c 发出请求的时间戳是全序排列的，后续发出的请求比早先发出的请求拥有更高的时间戳。例如，请求发起时的本地时钟值可以作为时间戳。
每个由副本节点发给客户端的消息都包含了当前的视图编号，使得客户端能够跟踪视图编号，从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求，然后主节点自动将该请求向所有备份节点进行广播。
副本发给客户端的响应为 <REPLY,v,t,c,i,r>，v 是视图编号，t 是时间戳，i 是副本的编号，r 是请求执行的结果。
客户端等待 f+1 个从不同副本得到的同样响应，同样响应需要保证签名正确，并且具有同样的时间戳 t 和执行结果 r。这样客户端才能把 r 作为正确的执行结果，因为失效的副本节点不超过 f 个，所以 f+1 个副本的一致响应必定能够保证结果是正确有效的。
如果客户端没有在有限时间内收到回复，请求将向所有副本节点进行广播。如果请求已经在副本节点处理过了，副本就向客户端重发一遍执行结果。如果请求没有在副本节点处理过，该副本节点将把请求转发给主节点。如果主节点没有将该请求进行广播，那么就有认为主节点失效，如果有足够多的副本节点认为主节点失效，则会触发一次视图变更。
每个副本节点的状态都包含了:
- 服务的整体状态
- 副本节点上的消息日志 (message log) 包含了该副本节点接受 (accepted) 的消息
- 当前视图编号 v。
下图展示了在没有发生主节点失效的情况下算法的正常执行流程，其中副本 0 是主节点，副本 3 是失效节点，而 C 是客户端。
当主节点 p 收到客户端的请求 m，主节点将该请求向所有副本节点进行广播，然后展开一个三阶段协议（three-phase protocol）。在这里，如果请求太多, 主节点会将请求 buffer 起来稍后再处理。
三阶段包括预准备（pre-prepare）、准备 (prepare) 和确认 (commit) 这三个阶段。pre-prepare 和 prepare 两个阶段用对同一个视图中的 requests 进行排序（即使对请求进行排序的主节点失效了），prepare 和 commit 两个阶段用来确保在不同的 view 之间的 requests 是严格排序的。
在预准备阶段，主节点 (primary) 分配一个序列号 n 给 request，然后向所有副节点发送 PRE-PREPARE 消息，PRE-PREPARE 消息的格式为<<PRE-PREPARE,v,n,d>,m>（在某些资料中是<PRE-PREPARE,v,n,d,sig>（比较符合工程），其中sig是节点消息摘要签名），这里 v 是视图编号，m 是客户端发送的请求消息，d 是请求消息 m 的摘要。
请求 m 本身是不包含在预准备的消息里面的，这样就能使预准备消息足够小，因为预准备消息的目的是作为一种证明，确定该请求是在视图 v 中被赋予了序号 n，从而在视图变更的过程中可以追索。另外一个层面，将 "将排序的协议" 和 "广播请求的协议" 进行解耦，有利于对消息传输的效率进行深度优化。
只有满足以下条件，各个 副本节点才会接受一个 PRE-PREPARE 消息：
- 请求和 pre-prepare 消息的签名都正确, d 是 m 的 digest
- 当前视图编号是 v。
- 该副本节点从未在视图 v 中接受过序号为 n 但是摘要 d 不同的消息 m。
- 编号 n 在下限 h 和上限 H 之间. (这是为了避免坏的主节点通过设置一个超大的 n 来穷尽编号)
如果副本节点 i 接受了预准备消息 <<PRE-PREPARE,v,n,d>,m>，则进入准备阶段。在准备阶段的同时，该节点向所有副本发送准备消息 <PREPARE,v,n,d,i>，并且将 PRE-PREPARE 消息和 PREPARE 消息写入自己的消息日志。副本节点若不接受 pre-prepare 消息就什么都不做。
包括主节点在内的所有副本节点在收到PREPARE消息之后，对
- 1.消息的签名是否正确，
- 2.视图编号 v 是否一致，
- 3.消息序号 n 是否满限制
这三个条件进行验证，如果验证通过则把这个准备消息写入消息日志中。
当且仅当节点 i 将如下消息插入到 message log 后, 我们才认为节点进入准备完毕状态, 记做 prepared(m, v, n, i).
- 请求 m
- 针对 m, v, n 的 pre-prepare 消息
- 2f 个来自不同从节点 (只有副本节点) 的对应于 pre-prepare 的
prepare消息(算上自己的那个 prepare 消息).
如何验证对应关系? 通过视图编号 v、消息序号 n 和摘要 d。
为啥要 2f 个? 因为 prepare 消息主节点不参与发送, 这样全网 3f+1 个节点减去主节点和恶意节点总共 (f+1) 个, 剩下的是 2f 个节点。
预准备阶段和准备阶段**确保所有正常节点对同一个视图中的请求排序达成一致。**接下去是对这个结论的形式化证明：如果 prepared(m,v,n,i) 为真，则 prepared(m',v,n,j) 必不成立 (i 和 j 表示副本编号，i 可以等于 j)，这就意味着至少 f+1 个正常节点在视图 v 的预准备或者准备阶段发送了序号为 n 的消息 m。
证明：
反证法：假如有 prepared(m,v,n,i) 为真且 prepared(m',v,n,j) 也为真，那么可以又接受 prepared 的条件可以看出，有 f+1 个好节点（包括他本身）发出了 prepare 消息接受 m，另有 f+1 个好节点发出了 prepare 接受 m', 这样好节点为 2f+2 但是 N=3f+1, 好节点只有 N-f=2f+1 个，有矛盾。
当 prepared(m,v,n,i) 条件为真的时候，副本 i 将 **<COMMIT,v,n,D(m),i >** 向其他副本节点广播，于是就进入了确认阶段。每个副本接受确认消息的条件是：
- 1.签名正确；
- 2.消息的视图编号与节点的当前视图编号一致；
- 3.消息的序号 n 满足水线条件，在 h 和 H 之间。
一旦确认消息的接受条件满足了，则该副本节点将确认消息写入消息日志中。（补充：需要将针对某个请求的所有接受的消息写入日志，这个日志可以是在内存中的）。
我们定义 committed(m,v,n) (不带节点编号 i 表示是一个整体状态) 为真得条件为：
- 任意 f+1 个好节点进入
prepared(m,v,n,i)为真的时候；
committed-local(m,v,n,i) 为真的条件为：
prepared(m,v,n,i)为真，并且 i 已经接受了 2f+1 个 commit 消息（包括自身在内）和与之对应一致的 pre-prepare 消息。commit 与 pre-prepare 消息一致的条件是具有相同的视图编号 v、消息序号 n 和消息摘要 d。
commit 阶段保证了以下这个不变式（invariant）：对某个好节点 i 来说，如果 committed-local(m,v,n,i) 为真则 committed(m,v,n) 也为真。(也就是说只要有一个好节点到了 committed-local 状态则整体就达到了 committed 状态)。
**证明：**某个好节点 i 达到 committed-local 说明其至少接收了 2f+1 个节点的 commit 消息，所以至少有 f+1 个好节点的 commit 消息。好节点发送 commit 需要保证是已经进入 prepared 状态才行。这样就至少有 f+1 个好节点进入了 prepared 状态，也意味着整体进入了 committed 状态。
这个不变式和视图变更协议保证了所有正常节点对本地确认的请求的序号达成一致，即使这些请求在每个节点的确认处于不同的视图。更进一步地讲，只要有一个好节点到达 committed 状态，那么至少有 f+1 个好节点也会到达 committed 状态。
每个副本节点 i 在 committed-local(m,v,n,i) 为真之后执行 m 的请求，并且 i 的状态反映了所有编号小于 n 的请求依次顺序执行。这就确保了所有正常节点以同样的顺序执行所有请求，这样就保证了算法的正确性（safety）。在完成请求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。
我们不依赖于消息的顺序传递，因此某个副本节点可能乱序确认请求。因为每个副本节点在请求执行之前已经将预准备、准备和确认这三个消息记录到了日志中，这样乱序就不成问题了。
为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少 f+1 个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了（例如故障恢复），这就需要通过传输部分或者全部服务状态实现该副本节点的同步。因此，副本节点同样需要证明状态的正确性。
在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如 100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作检查点（checkpoint），并且将具有证明的检查点称作稳定检查点（stable checkpoint）。
副本节点保存了服务状态的多个逻辑拷贝，包括最新的稳定检查点，零个或者多个非稳定的检查点，以及一个当前状态。写时复制技术可以被用来减少存储额外状态拷贝的空间开销。
检查点的正确性证明的生成过程如下：当副本节点 i 生成一个检查点后，向其他副本节点广播检查点消息 <CHECKPOINT,n,d,i>，这里 n 是最近一个影响状态的请求序号，d 是状态的摘要。每个副本节点都默默地在各自的日志中收集并记录其他节点发过来的检查点消息，直到收到来自 2f+1 个不同副本节点的具有相同序号 n 和摘要 d 的检查点消息。这 2f+1 个消息就是这个检查点的正确性证明。
具有证明的检查点成为稳定检查点，然后副本节点就可以将所有序号小于等于 n 的预准备、准备和确认消息从日志中删除。同时也可以将之前的检查点和检查点消息一并删除。
检查点协议可以用来更新水线（watermark）的高低值（h 和 H），这两个高低值限定了可以被接受的消息。水线的低值 h 与最近稳定检查点的序列号相同，而水线的高值 H=h+k，k 需要足够大才能使副本不至于为了等待稳定检查点而停顿。加入检查点每 100 个请求产生一次，k 的取值可以是 200。
view-change 存在的意义: 主节点坏掉了, 更换 view(即更换主节点 primary), 以此来保证全网的 liveness. 使用计时器的超时机制触发 view-change。
视图变更可以由从节点 timeout 触发，以防止从节点无期限地等待请求的执行（在工程上或者在实际运行当中，长时间没有pre-prepare是常见的，因此一般会通过心跳来进行探测保活，所以也不一定非得要用定时器）。从节点等待一个请求，就是该节点接收到一个有效请求，但是还没有执行它。当从节点接收到一个请求但是计时器还未运行，那么它就启动计时器；当它不再等待请求的执行就把计时器停止，但是当它等待其他请求执行的时候再次启动计时器。
当计时器超时的时候，会触发 view-change，使 v 变为 v+1，并停止服务（除了接收 checkpoint, view-change, and new-view messages）并广播 <VIEW-CHANGE,v+1，n，C，P，i> 消息到所有节点（n 为最近的一个 stable checkpoint 对应的请求号，C 表示 2f+1 个有效的 checkpoint 的证明，P 是一个包含若干个 Pm 的集合. 其中 Pm 的定义: 对于编号大于 n 且已经在节点 i 写入prepared 的消息 m, Pm 包含一个合法的 pre-prepare 消息 (不包括对应的 client message) 和 2f 个对应的, 由不同节点签名的 prepare 消息 (v, n, D(m) 要一样)）。
View v+1 的主节点 p 接收到 2f 个来自不同其他节点的 view-change 消息后, 就广播 **<NEW-VIEW, v+1, V, O>**_sigma_p 到所有节点. V : 集合 {p 接收到的 view-change 消息, p 发送(或者应该发送) 的对于 v+1 的 view-change 消息} ，O: 一个包含若干 pre-prepare 消息的集合 (不顺带请求), 包含如下内容:
- 主节点从 V 中找到
- min-s, 即最近一次 stable checkpoint 的编号.
- V 中所有 prepare 消息的最大的编号 max-s.
- 对 min-s 和 max-s 之间的每个编号 n, 主节点创建一个新的 pre-prepare 消息, 用于 View v+1。两种情况:
- V 中的某个编号为 n 的 view-change 消息, 其 P 集合不为空. 这种情况下, 主节点创建一个新的 pre-prepare 消息 <PRE-PREPARE, v+1, n, d>_sigma_p
- 其 P 集合为空. 主节点创建一个新的 pre-prepare 消息
<PRE-PREPARE, v+1, n, d^null>_sigma_p, 其中 d^null 是一个特殊的 null 请求的 digest. 该操作什么都不做.
然后, 主节点将 O 中的信息插入到 log 中. 如果 min-s 大于它最近一个 checkpoint 的编号, 主节点要计算编号为 min-s 的 checkpoint 的 proof, 并将其插入到 log 中, 然后按照上述进行垃圾回收. 至此, 主节点正式进入 View v+1, 可以接受关于 v+1 的消息。
如果从节点接受的 new-view 消息满足如下条件
- 签名合法
- V 中的 view-change 消息合法.
- O 合法 (算法类似于主节点创建 O 的算法)
从节点会将这些消息加入到 log 中 (跟上一段的主节点操作一样), 然后对于 O 中的每一个 pre-prepare 消息, 广播对应的 prepare 消息到所有节点并插入 log, 正是进入 View v+1.
Practical Byzantine Fault Tolerance - Miguel Castro and Barbara Liskov