论文地址:http://pmg.csail.mit.edu/papers/osdi99.pdf PBFT 是 Practical Byzantine Fault Tolerance 的缩写，意为实用拜占庭容错算法。该算法是 Miguel Castro (卡斯特罗) 和 Barbara Liskov（利斯科夫）在 1999 年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在 1999 年的操作系统设计与实现国际会议上（OSDI99）。没错，这个 Loskov 就是提出著名的里氏替换原则（LSP）的人，2008 年图灵奖得主。

摘要部分

OSDI99 这篇论文描述了一种副本复制（replication）算法解决拜占庭容错问题。作者认为拜占庭容错算法将会变得更加重要，因为恶意攻击和软件错误的发生将会越来越多，并且导致失效的节点产生任意行为。（拜占庭节点的任意行为有可能误导其他副本节点产生更大的危害，而不仅仅是宕机失去响应。）而早期的拜占庭容错算法或者基于同步系统的假设，或者由于性能太低而不能在实际系统中运作。这篇论文中描述的算法是实用的，因为该算法可以工作在异步环境中，并且通过优化在早期算法的基础上把响应性能提升了一个数量级以上。作者使用这个算法实现了拜占庭容错的网络文件系统（NFS），性能测试证明了该系统仅比无副本复制的标准 NFS 慢了 3%。

1. 概要介绍

这篇论文提出解决拜占庭容错的状态机副本复制（state machine replication）算法。这个算法在保证活性和安全性（liveness & safety）的前提下提供了 (n-1)/3 的容错性。从 Lamport 教授在 1982 年提出拜占庭问题开始，已经有一大堆算法去解决拜占庭容错了。PBFT 在之上进行了优化使得能够应用在实际场景，在只读操作中只使用 1 次消息往返（message round trip），在只写操作中只使用 2 次消息往返，并且在正常操作中使用了消息验证编码（Message Authentication Code, 简称 MAC），而造成妖艳贱货性能低下的公钥加密（public-key cryptography）只在发生失效的情况下使用（viewchange and new-view messages）。作者不仅提出算法，而且使用这个算法实现了一个拜占庭容错的 NFS 服务。 作者列举一下这边论文的贡献：

1）首次提出在异步网络环境下使用状态机副本复制协议 2）使用多种优化使性能显著提升 3）实现了一种拜占庭容错的分布式文件系统 4）为副本复制的性能损耗提供试验数据支持

2. 系统模型

系统假设为异步分布式的，通过网络传输的消息可能丢失、延迟、重复或者乱序。作者假设节点的失效必须是独立发生的，也就是说代码、操作系统和管理员密码这些东西在各个节点上是不一样的。

作者使用了加密技术来防止欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（其实就是 RSA 算法）、消息验证编码（MAC）和无碰撞哈希函数生成的消息摘要（message digest）。使用 m 表示消息，mi 表示由节点 i 签名的消息，D(m) 表示消息 m 的摘要。按照惯例，只对消息的摘要签名，并且附在消息文本的后面。并且假设所有的节点都知道其他节点的公钥以进行签名验证。

系统允许攻击者可以操纵多个失效节点、延迟通讯、甚至延迟正确节点。但是不能无限期地延迟正确的节点，并且算力有限不能破解加密算法。例如，不能伪造正确节点的有效签名，不能从摘要数据反向计算出消息内容，或者找到两个有同样摘要的消息。 message digests:https://www.techopedia.com/definition/4024/message-digest

可以理解为 checksum, 对文件内容进行 hash, 如果文件内容被修改则 hash 改变, 用以验证文件是否损坏 / 被修改. MD5, SHA 等算法都可以用作生成 message digest 的算法)

Cryptographic hash function

密码学中将输入数据作为 message, 输出数据, 即 hash value, 记做 message digest = 消息摘要. 仅对 message digest 进行签名, 而不是对整个 message 进行签名. 什么是签名 非对称加密中使用私钥对消息 + 自己的身份进行加密, 外部节点使用公钥进行解密, 可以看到加密方的身份, 即为签名

3. 服务属性

这部分描述了副本复制服务的特性

论文算法实现的是一个具有确定性的副本复制服务，这个服务包括了一个状态（state）和多个操作（operations）。这些操作不仅能够进行简单读写，而且能够基于状态和操作参数进行任意确定性的计算。客户端向副本复制服务发起请求来执行操作，并且阻塞以等待回复。副本复制服务由 n 个节点组成。

针对安全性

算法在失效节点数量不超过（n-1)/3 的情况下同时保证安全性和活性（safety & liveness）。安全性是指副本复制服务满足线性一致性（linearizability）, 就像中心化系统一样原子化执行操作。安全性要求失效副本的数量不超过上限，但是对客户端失效的数量和是否与副本串谋不做限制。系统通过访问控制来限制失效客户端可能造成的破坏，审核客户端并阻止客户端发起无权执行的操作。同时，服务可以提供操作来改变一个客户端的访问权限。因为算法保证了权限撤销操作可以被所有客户端观察到，这种方法可以提供强大的机制从失效的客户端攻击中恢复。

针对活性

算法不依赖同步提供安全性，因此必须依靠同步提供活性。否则，这个算法就可以被用来在异步系统中实现共识，而这是不可能的（由 Fischer1985 的论文证明）。本文的算法保证活性，即所有客户端最终都会收到针对他们请求的回复，只要失效副本的数量不超过（n-1)/3，并且延迟 delay(t) 不会无限增长。这个 delay(t) 表示 t 时刻发出的消息到它被目标最终接收的时间间隔，假设发送者持续重传直到消息被接收。这时一个相当弱的同步假设，因为在真实系统中网络失效最终都会被修复。但是这就规避了 Fischer1985 提出的异步系统无法达成共识的问题。

下面这段话是关键

本文的算法是最优的：当存在 f 个失效节点时必须保证存在至少 3f+1 个副本数量，这样才能保证在异步系统中提供安全性和活性。这么多数量的副本是需要的，因为在同 n-f 个节点通讯后系统必须做出正确判断，由于 f 个副本有可能失效而不发回响应。但是，有可能 f 个失效的节点是好节点，f 个坏节点依然发送请求。尽管如此，系统仍旧需要好节点的返回数量大于坏节点的返回数量，即 n-2f>f，因此得到 n>3f。

算法不能解决信息保密的问题，失效的副本有可能将信息泄露给攻击者。在一般情况下不可能提供信息保密，因为服务操作需要使用参数和服务状态处理任意的计算，所有的副本都需要这些信息来有效执行操作。当然，还是有可能在存在恶意副本的情况下通过秘密分享模式（secret sharing scheme）来实现私密性，因为参数和部分状态对服务操作来说是不可见的。 推理 由于有 f 个坏节点, 它们可能完全不回复消息, 所以我们要确保客户端只要接收到 n-f 个消息就足以做出判断. 不能依赖于更多的信息, 否则等待永不回复坏节点就意味着 liveness 被破坏. 考虑一个最差的情况: 那 f 个还未回复的节点是好节点, 收到的 n-f 个消息中有 f 个坏节点消息. 那么接到的好节点的消息实际上是 n-2f 个, 坏节点消息是 f 个. 根据少数服从多数, 需要 n-2f>f, 即 n>3f. 综上, 全网总节点数 n 至少是 3f+1 才能确保安全性和 Liveness.

4. 算法

PBFT 是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母 R 表示，使用 0 到 | R|-1 的整数表示每一个副本。为了描述方便，假设 | R|=3f+1，这里 f 是有可能失效的副本的最大个数。尽管可以存在多于 3f+1 个副本，但是额外的副本除了降低性能之外不能提高可靠性。

所有的副本在一个被称为视图（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 算法对所有非失效副本节点的请求执行总顺序达成一致，从而保证安全性。

接下去描述简化版本的 PBFT 算法，忽略磁盘空间不足和消息重传等细节内容。并且，本文假设消息验证过程是通过数字签名方法实现的，而不是更加高效的基于消息验证编码（MAC）的方法。

4.1 客户端

客户端 c 向主节点发送 请求执行状态机操作 o，这里时间戳 t 用来保证客户端请求只会执行一次。客户端 c 发出请求的时间戳是全序排列的，后续发出的请求比早先发出的请求拥有更高的时间戳。例如，请求发起时的本地时钟值可以作为时间戳。

每个由副本节点发给客户端的消息都包含了当前的视图编号，使得客户端能够跟踪视图编号，从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求，然后主节点自动将该请求向所有备份节点进行广播。

副本发给客户端的响应为 ，v 是视图编号，t 是时间戳，i 是副本的编号，r 是请求执行的结果。

客户端等待 f+1 个从不同副本得到的同样响应，同样响应需要保证签名正确，并且具有同样的时间戳 t 和执行结果 r。这样客户端才能把 r 作为正确的执行结果，因为失效的副本节点不超过 f 个，所以 f+1 个副本的一致响应必定能够保证结果是正确有效的。

如果客户端没有在有限时间内收到回复，请求将向所有副本节点进行广播。如果请求已经在副本节点处理过了，副本就向客户端重发一遍执行结果。如果请求没有在副本节点处理过，该副本节点将把请求转发给主节点。如果主节点没有将该请求进行广播，那么就有认为主节点失效，如果有足够多的副本节点认为主节点失效，则会触发一次视图变更。

本文假设客户端会等待上一个请求完成才会发起下一个请求，但是只要能够保证请求顺序，可以允许请求是异步的。

4.2 PBFT 算法主线流程（正常情况）

每个副本节点的状态都包含了:

• 服务的整体状态
• 副本节点上的消息日志 (message log) 包含了该副本节点接受 (accepted) 的消息
• 当前视图编号 v。

请求开始

当主节点 p 收到客户端的请求 m，主节点将该请求向所有副本节点进行广播，然后展开一个三阶段协议（three-phase protocol）。在这里，如果请求太多, 主节点会将请求 buffer 起来稍后再处理。

三阶段协议

我们重点讨论预准备（pre-prepare）、准备 (prepare) 和确认 (commit) 这三个阶段。pre-prepare 和 prepare 两个阶段用对同一个视图中的 requests 进行排序（即使对请求进行排序的主节点失效了），prepare 和 commit 两个阶段用来确保在不同的 view 之间的 requests 是严格排序的。

预准备阶段

在预准备阶段，主节点 (primary) 分配一个序列号 n 给 request，然后向所有 backup node 发送 PRE-PREPARE 消息，PRE-PREPARE 消息的格式为<,m>，这里 v 是视图编号，m 是客户端发送的请求消息，d 是请求消息 m 的摘要。

请求 m 本身是不包含在预准备的消息里面的，这样就能使预准备消息足够小，因为预准备消息的目的是作为一种证明，确定该请求是在视图 v 中被赋予了序号 n，从而在视图变更的过程中可以追索。另外一个层面，将 “将排序的协议” 和“广播请求的协议”进行解耦，有利于对消息传输的效率进行深度优化。

只有满足以下条件，各个 backup node 才会接受一个 PRE-PREPARE 消息：

1. 请求和 pre-prepare 消息的签名都正确, d 是 m 的 digest
2. 当前视图编号是 v。
3. 该备份节点从未在视图 v 中接受过序号为 n 但是摘要 d 不同的消息 m。
4. 编号 n 在下限 h 和上限 H 之间. (这是为了避免坏的主节点通过设置一个超大的 n 来穷尽编号)

进入准备阶段

如果备份节点 i 接受了预准备消息 <,m>，则进入准备阶段。在准备阶段的同时，该节点向所有 backup node 发送准备消息 < PREPARE,v,n,d,i>，并且将 PRE-PREPARE 消息和 PREPARE 消息写入自己的消息日志。backup node 若不接受 pre-prepare 消息就什么都不做。

接受准备消息需要满足的条件

包括主节点在内的所有副本节点在收到准备消息之后，1、对消息的签名是否正确，2、视图编号 v 是否一致，3 消息序号 n 是否满限制这三个条件进行验证，如果验证通过则把这个准备消息写入消息日志中。

准备阶段完成的标志

当且仅当节点 i 将如下消息插入到 message log 后, 我们才认为节点进入准备完毕状态, 记做 prepared(m, v, n, i).

• 请求 m
• 针对 m, v, n 的 pre-prepare 消息
• 2f 个来自不同从节点 (只有 backup) 的对应于 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 && committed-local

我们定义 committed(m,v,n) 为真得条件为：任意 f+1 个好节点进入 prepared(m,v,n,i) 为真的时候；(不带节点编号 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）。在完成请求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。

我们不依赖于消息的顺序传递，因此某个副本节点可能乱序确认请求。因为每个副本节点在请求执行之前已经将预准备、准备和确认这三个消息记录到了日志中，这样乱序就不成问题了。

下图展示了在没有发生主节点失效的情况下算法的正常执行流程，其中副本 0 是主节点，副本 3 是失效节点，而 C 是客户端。

PBFT算法流程

4.3 垃圾回收 = 为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少 f+1 个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了（例如故障恢复），这就需要通过传输部分或者全部服务状态实现该副本节点的同步。因此，副本节点同样需要证明状态的正确性。

在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如 100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作检查点（checkpoint），并且将具有证明的检查点称作稳定检查点（stable checkpoint）。

副本节点保存了服务状态的多个逻辑拷贝，包括最新的稳定检查点，零个或者多个非稳定的检查点，以及一个当前状态。写时复制技术可以被用来减少存储额外状态拷贝的空间开销。

检查点的正确性证明的生成过程如下：当副本节点 i 生成一个检查点后，向其他副本节点广播检查点消息 ，这里 n 是最近一个影响状态的请求序号，d 是状态的摘要。每个副本节点都默默地在各自的日志中收集并记录其他节点发过来的检查点消息，直到收到来自 2f+1 个不同副本节点的具有相同序号 n 和摘要 d 的检查点消息。这 2f+1 个消息就是这个检查点的正确性证明。

具有证明的检查点成为稳定检查点，然后副本节点就可以将所有序号小于等于 n 的预准备、准备和确认消息从日志中删除。同时也可以将之前的检查点和检查点消息一并删除。

检查点协议可以用来更新水线（watermark）的高低值（h 和 H），这两个高低值限定了可以被接受的消息。水线的低值 h 与最近稳定检查点的序列号相同，而水线的高值 H=h+k，k 需要足够大才能使副本不至于为了等待稳定检查点而停顿。加入检查点每 100 个请求产生一次，k 的取值可以是 200。

4.4 view-change 视图变更

view-change 存在的意义: 主节点坏掉了, 更换 view(即更换主节点 primary), 以此来保证全网的 liveness. 使用计时器的超时机制触发 view-change。

从节点触发 View Change

视图变更可以由从节点 timeout 触发，以防止从节点无期限地等待请求的执行。从节点等待一个请求，就是该节点接收到一个有效请求，但是还没有执行它。当从节点接收到一个请求但是计时器还未运行，那么它就启动计时器；当它不再等待请求的执行就把计时器停止，但是当它等待其他请求执行的时候再次情动计时器。

从节点广播 View Change

当计时器超时的时候，会触发 view-change，使 v 变为 v+1，并停止服务（除了接收 checkpoint, view-change, and new-view messages）并广播 消息到所有节点（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 消息后, 就广播 _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 消息 _sigma_p
• 其 P 集合为空. 主节点创建一个新的 pre-prepare 消息 _sigma_p, 其中 d^null 是一个特殊的 null 请求的 digest. 该操作什么都不做.

然后, 主节点将 O 中的信息插入到 log 中. 如果 min-s 大于它最近一个 checkpoint 的编号, 主节点要计算编号为 min-s 的 checkpoint 的 proof, 并将其插入到 log 中, 然后按照 4.3 中所讲进行垃圾回收. 至此, 主节点正式进入 View v+1, 可以接受关于 v+1 的消息.

从节点接受新的主节点

如果从节点接受的 new-view 消息满足如下条件

• 签名合法
• V 中的 view-change 消息合法.
• O 合法 (算法类似于主节点创建 O 的算法)

从节点会将这些消息加入到 log 中 (跟上一段的主节点操作一样), 然后对于 O 中的每一个 pre-prepare 消息, 广播对应的 prepare 消息到所有节点并插入 log, 正是进入 View v+1.