引言

在之前的文章中，我们介绍了什么是「拜占庭将军问题」，也了解了原论文中的解决方案。但那些方案只是理论上的解决办法，若真的在现实中使用就会有各种各样的问题。因此在那之后，又提出了一些可在真实生产环境中使用的解决拜占庭将军问题的方法，本文将要介绍的「实用拜占庭容错算法」（Practical Byzantine Fault Tolerance, 简称 PBFT）就是其中一种。

从名称上就可以看出，PBFT 就是冲着可在实际应用中使用而发明的。这篇文章里，我们将详细了解一下 PBFT 算法的相关细节。文章中的多数讨论来自于原始论文，不过这篇文章写得也很不错，给了我一些启发。

系统模型

在介绍 PBFT 的算法步骤之前，我们先了解一下使用 PBFT 算法的分布式系统的概念，和算法对系统的一些要求。

首先，PBFT 对系统内的结点数量是有要求的。与拜占庭将军问题类似，PBFT 要求系统内的结点数量 $n$ 不小于 $3f+1$，其中 $f$ 为「恶意结点」的数量。这里的「恶意结点」可以是故意作恶的结点，也可以是被攻击被控制的结点，甚至是失去响应的结点，总之只要是不正常的，都可以认为是恶意的。

其次，PBFT 将系统内的每个结点分成了两类：主结点和从结点。任一时刻内，只有一个主结点，其它结点都是从结点。但主结点是可以被更换的（更换主结点被称为「域转换」（View Change））。无论是主结点还是从结点，他们都使用状态机机制记录自己的操作。如果各结点的操作是一致的，那么它们的状态机的状态会一直保持一致。

再次，向 PBFT 系统发送请求的端叫做「客户端」。当某个客户端想要向系统发送请求时，一般情况下，它会将请求发给当前的主结点；非一般情况下，它会将请求广播给所有结点。无论哪种情况，客户端都直接从各个结点（包括主结点）接收请求返回的数据。

第四，在论文中，作者假设客户端等待上一个请求完成以后，才会发送下一个请求。也就是说主结点和从结点们在某一时刻只会处理一个请求。这是一种同步发送请求的方式。如果客户端不等上一个请求返回就再次发送请求（即异步发送请求），那么请求的响应顺序可能不会是客户端发送的顺序。

第五，PBFT 中有一个「域」( view )的概念（一般翻译成「视图」，但我觉得「视图」这个词并不能表达原术语的意思，所以我大胆将它翻译成「域」）。某个结点担任主结点的过程，就是一个域。如果担任主结点的结点发生了变化，就是发生了「域转换」(View Change)。域是有编号的，每发生一次域转换，域编号就递增一次。如果将每个结点从 0 开始编号，那么我们可以通过算式 $i = v \, mod \, |R|$ 得到当前主结点的编号 $i$：其中 $v$ 为当前的域编号， $|R|$ 为结点数量。（如果把「域」比作「朝代」，可能会比较好理解一些：一个结点开始担任主结点，表示一个朝代的开始；主结点发生变更时，表示一个朝代的变更，朝代号就是加 1）

最后，PBFT 中各结点通信信息是经过签名的。也就是说，任何一个结点都无法修改别的结点发送的消息，只能原封不动的拷贝、转发或存储。所以可以想象一下， PBFT 算法与介绍拜占庭将军问题的文章中的 $SM$ 算法应该是有相同的地方的。

以上就是 PBFT 系统模型的要点。看完这些你可能似懂非懂，心中有很多疑问题。比如为什么需要 $3f+1$ 个结点？域到底起什么作用？这些问题我们会在后面作解答。这里只需了解这些概念和限制，相信在后面理解算法的过程中，很多问题自然就会消散了。

如果我来发明这个算法…

我发现很多「高大上」的东西，其底层的逻辑通常都很朴素，并没有复杂到像我这样的普通人永远也想不出来的程度。所以我很喜欢在理解了某问题的解决方法以后，再假设我不知道这个方法但仍然遇到了问题，然后把解决方法「自己想出来」。所以这里我决定在文章里来这么一次。

前面我们已经给了应用 PBFT 的系统的一些概念和限制了，总结一下就是：正常情况下，客户端发送请求给主节点，然后等待各个从节点返回数据。而我们要做的是，保证多数节点（无论是主结点还是从结点）返回一致的数据给客户端。

OK，现在就让我们来想象一下这个过程。现在客户端发送数据给主结点了，主结点该怎么办呢？它不但要自己响应这一请求，还要把这一请求发送给所有从结点，让所有从结点进行响应。所以这里主结点做了两件事：一是自己响应客户端的请求；二是将客户端的请求转发给所有从节点。

现在每个从结点都收到了主结点转发的请求，那么从结点们应该开始响应这个请求吗？注意这是一个无法信任某个人的世界，所以从结点们不知道主结点是不是可信，它们不会直接执行收到的请求的。那从结点们该怎么办呢？

答案就是「少数服从多数」：如果从结点可以确定其它大多数从结点收到的请求与自己收到的请求是一样的，那么就可以响应这个请求。所以从结点们一边将自己收到的请求广播给其它从结点，一边收取并记录其它从结点广播过来的请求。当某个从结点收集到了足够多的从结点广播的请求，并且这些请求与自己从主结点那里收到的一致，它就认为主结点是可信的、这个请求是可以响应的。（这一过程与拜占庭将军问题的论文中的 $SM$ 算法很像，具体可参考之前的文章）。

现在收集到足够多的从结点可以确定主结点是可信的，那么它是否可以立即执行这个请求呢（在 $SM$ 算法中确实是立即执行的）？答案是不可以。虽然某个从结点确认了请求是可以响应的，但它并不能确定别的从结点也确认了。所以如果此时立即执行请求，我们并不能保证结点间的状态一致。举个例子，比如可能有某个从结点由于暂时的网络问题，只能向外广播消息，却收不到其它结点的消息。因此这个结点就收不到足够多的其它从结点广播的请求，因而也不会认为这个请求是可以响应的。最终的结果是有的结点响应了这个请求，有的没有响应，无法保证结点间的状态是一致的。

那怎么办呢？既然无法确定别的结点是否确认了这个消息是可响应的，那就确定一下呗。所以从结点需要多做一步，从结点此时并不马上响应请求，而是给所有其它结点广播一条消息：「我认可了某某请求」。然后它开始等待其它从结点的同样的消息。如果某从结点发现大多数结点都发出了这样一条消息，它就确定大多数结点认可这一请求是可以响应的（而不像刚才那样只知道自己认可是可响应的，别人是否认可它不知道）。所以现在它可以愉快的执行并响应这一请求。如果所有正常的结点都这样做，那么所有正常的结点都知道自己可以响应这一请求，也知道其他多数结点也同意响应这个请求，那么最后大多结点的状态在响应完这个请求后，仍然是一致的。

稍微总结一下这一过程，你会发现各结点先是做了两步：第一步是广播「认可当前请求」的消息、并从其它结点那接收同样的消息；第二步是广播「我认可了某某请求」的消息、并从其它结点那接收同样的消息。然后当接收到多数结点发送的「我认可了某某请求」消息时，才真正执行和响应请求。

这就是我能想像出来的保证多数结点状态一致的过程，也是白话版的 PBFT 算法的主要过程。当然刚才描述的这个过程仍有不少问题需要解决（比如当前主结点是恶意的怎么办？再比如即使收到了大多数结点发送的「我认可了某某请求」、但因为一些原因仍未执行请求怎么办？），但主要的流程就是刚才描述的那样，其它问题只不过是对一些异常状态的处理而已。

其实各结点「两步走」的想法，和建立 TCP 连接的「三次握手」是非常相似的：虽然我能确定对方是正常的，但我确定不了对方对我的看法（对方是否认为我是正常的），所以只得再增加一步，以完成这一确定。

说完了我自己的朴素的 PBFT 的逻辑，下面我们就来看看真正的 PBFT 是什么样子的。

PBFT 算法

下面我们就来看看真正的 PBFT 算法是什么样子的。我们首先了解一下在正常情况下，PBFT 是如何执行的；然后介绍一下检查点（checkpoint）的概念；最后学习一下异常发生时的域转换（View Changes）的逻辑，和主结点不响应这种异常情况的处理方法。（其实检查点不算是 PBFT 的一个重点的概念，并且也很好理解。但要想理解域转换，就需要先理解检查点的概）

正常情况下的流程

这一小节里我们来了解一下在正常情况下 PBFT 算法的流程。但在这之前，我们需要先介绍一下后面用到的一些符号的意义。

首先，我们在文章的开头提到过，PBFT 系统中各结点的消息是经过签名的，所以在下面的描述中，我们使用 ${\langle m \rangle}_{\sigma_i}$ 代表由结点 $i$ 签名的消息 $m$；使用 $D(m)$ 或 $d$ 代表消息 $m$ 哈希。

其次，前面也说过，在 PBFT 中每一个域都有一个编号，后面我们记为 $v$。当发生域转换时，$v$ 会递增加 1。每个结点也有一个编号，一般记为 $i$，结点的编号从 0 开始，直至结点总数 $|R| - 1$。所以我们可以使用 $i = v \, mod \, |R|$ 来计算当前哪个结点是主结点。

PBFT 的核心是三个阶段：pre-prepare、prepare、commit。所以这里我们先单独介绍一下这三个阶段，然后再看一下整体的正常流程。

PBFT 三阶段

PBFT 的三个阶段按执行顺序是 pre-prepare 阶段、 prepare 阶段、 commit 阶段。pre-prepare 阶段起始于主结点收到客户端的请求以后。下面我们详细了解一下每个阶段的细节。小节的最后我们会放上原始论文中的示意图，在经过说明之后，这个示意图会更加容易明白。

pre-prepare

主结点收到客户端发送的请求之后，开始 pre-prepare 阶段。首先主结点 $p$ 为收到的请求分配一个序号，记为 $n$（$n$ 必须未被分配给其它请求，且比最近一次的请求的序号大）。然后广播消息 $\langle \langle PRE$-${PREPARE, v, n, d \rangle}_{\sigma_p}, m \rangle$ 给所有从结点。其 $m$ 为结点收到的客户端请求； $v$ 代表当前的域编号（view number）；$n$ 为刚才分配给 $m$ 的序号；$d$ 为 $m$ 的哈希值。

注意这里的参与签名的 $\langle PRE$-$PREPARE \rangle$ 消息中，并不包含 $m$ 本身。这是因为一方面 $\langle PRE$-$PREPARE \rangle$ 消息可能在域转换时还会被用到，而那时并不需要重新发送 $m$ 本身；另一方面，将 $m$ 与 $\langle PRE$-$PREPARE \rangle$ 消息分开，可以更方便针对某些情况做优化，比如在 $m$ 较大时使用更好的方式发送 $m$ 本身。

当从结点收到 $\langle PRE$-$PREPARE \rangle$ 消息后，会对其进行验证，满足以下条件才会通过验证：

$m$ 的签名和 $\langle PRE$-$PREPARE \rangle$ 消息的签名都是正确的，且 $\langle PRE$-$PREPARE \rangle$ 消息中的 $d$ 确是 $m$ 的哈希
从结点当前的域编号与 $\langle PRE$-$PREPARE \rangle$ 消息中的一致，都为 $v$
从结点之前没收到过相同的 $\langle PRE$-$PREPARE \rangle$ 消息
$\langle PRE$-$PREPARE \rangle$ 消息中的 $n$ 在区间 $[h, H]$ 内

最后一条可以避免恶意的主结点滥用序号值，比如将序号值设置得非常大。我们在介绍 checkpoint 时会说明如何设置 $h$ 和 $H$ 的值。

prepare

如果某个从结点验证通过了某条 $\langle PRE$-$PREPARE \rangle$ 消息，那么它将进入 prepare 阶段，并广播消息 ${\langle PREPARE, v, n, d, i \rangle}_{\sigma_i}$。（如果 $\langle PRE$-$PREPARE \rangle$ 消息验证不通过，就忽略它，什么也不做）

在从结点发出 $\langle PREPARE \rangle$ 消息的同时，它也会接收别人广播过来的 $\langle PREPARE \rangle$ 消息，并对其进行验证。满足以下条件才会通过验证：

$\langle PREPARE \rangle$ 消息的签名是正确的
从结点当前的域编号与 $\langle PREPARE \rangle$ 消息中的一致，都为 $v$
$\langle PREPARE \rangle$ 消息中的 $n$ 在区间 $[h, H]$ 内

这里我们需要定义一个函数 $prepared(m, v, n, i)$：如果某结点 $i$ 验证通过了以下数据：
a. $m$ 本身
b. 关于 $m$ 的 $\langle PRE$-$PREPARE, v, n, d \rangle$ 消息
c. $2f$ 条其它结点（不包含自己）发送过来的、与 $\langle PRE$-$PREPARE \rangle$ 消息相匹配的 $\langle PREPARE \rangle$ 消息（匹配的定义是，它们的 $v$、$n$ 以及 $m$ 的哈希 $d$ 是完全一样的）
我们就定义 $prepared(m, v, n, i)$ 的值为 $true$，否则为 $false$。

commit

如果对于某个结点 $i$ ，$prepared(m, v, n, d, i)$ 为 $true$，那么这个结点将进入commit 阶段，并广播消息 ${\langle COMMIT, v, n, i \rangle}_{\sigma_i}$ 。

类似于 prepare 阶段，从结点发送 $\langle COMMIT \rangle$ 消息的同时，也会接收别的结点广播过来的 $\langle COMMIT \rangle$ 消息，并对其进行验证。满足以下条件才会通过验证：

$\langle COMMIT \rangle$ 消息的签名是正确的
从结点当前的域编号与 $\langle COMMIT \rangle$ 消息中的一致，都为 $v$
$\langle COMMIT \rangle$ 消息中的 $n$ 在区间 $[h, H]$ 内

类似于 prepare 阶段，我们这里也要定义一个函数 $committed$-$local(m, v, n, d, i)$：如果某结点 $i$ 满足以下条件：
a. $prepared(m, v, n, d, i)$ 的值为 $true$
b. 验证通过了 $2f$ 条其它结点（不包括自己）发送过来的、与 $\langle PREPARE\rangle$ 消息相匹配的 $\langle COMMIT\rangle$ 消息（匹配的定义是，它们的$v$、$n$ 以及 $m$ 的哈希 $d$ 是完全一样的）
我们就定义 $committed$-$local(m, v, n, i)$ 为 $true$，否则为 $false$。

如果某结点 $i$ 的 $committed$-$local(m, v, n, d, i)$ 为 $true$，那么它就可以响应请求 $m$、将结果更新到自己的状态机中、并返回结果给客户端了。

下面就是原始论文中使用的三阶段的示意图，其中 0 是主结点，3号是恶意结点不对请求进行响应（我一开始看这个图是有些懵的，但明白了整个过程以后再看，就很清楚了）：

正常情况下的完整流程

介绍完了最核心的三阶段，我们将其放在整个 PBFT 的流程中，看一下在不出意外的正常情况下，PBFT 的完整流程：

客户端向主结点发起请求，记为 ${\langle REQUEST, o, t, c \rangle}_{\sigma_c}$。
其中 $o$ 代表客户端请求的操作( operation )；$t$ 代表时间戳；$c$ 为客户端自己的标识。这里通过 $t$ 来保证同一请求只会被发送和处理一次：如果主结点收到两个完全一样的请求，它将丢弃重复的请求；如果同一操作需要先后执行两次，客户端应该先后构造两个请求，且这两个请求的时间戳是不一样的。
主结点收到请求后，立即启动三阶段的共识过程，让所有从结点参与请求的处理。
三阶段的共识过程就是我们前面介绍的 pre-prepare、prepare、commit。
三阶段执行完成后，如果对于某一结点 $i$， $committed$-$local(m, v, n, d, i)$ 的值为 $true$，则结点开始执行请求 $m$。执行成功后更改自己本地状态机的状态，并将结点直接返回给客户端。
针对同一请求，如果客户端收到了 $f+1$ 个相同的返回结果，那么它就把这个结点作为最终的结果。

这就是 PBFT 在正常情况下的完整流程。

在第 3 步中，你可能会有疑问，虽然对于结点 $i$， $committed$-$local(m, v, n, d, i)$ 为 $true$，即结点 $i$ 确实可以响应 $m$ 了，但结点 $i$ 如何确定其它结点的 $committed$-$local$ 为 $true$ 了呢？如果大多数其它结点的 $committed$-$local$ 不为 $true$，它们就不会响应 $m$，那么结点 $i$ 的状态岂不是与其它结点的状态不一致了吗？

确实，在第 3 步中，某个正常结点的 $committed$-$local$ 为 $true$，并不真正代表其它所有正常结点的 $committed$-$local$ 都为 $true$，但这其实是一种特殊情况，而不是正常情况。正常情况下，某结点发送了 $\langle COMMIT \rangle$ 消息且验证通过了 $2f$ 条其它结点发送的 $\langle COMMIT \rangle$ 消息（因而它的 $committed$-$local$ 为 $true$），其它正常结点应该也可以接收到 $2f$ 条 $\langle COMMIT \rangle$ 消息、因而也可以达到 $committed$-$local$ 为 $true$ 的状态。

这一小节里我们并没有讨论「特殊情况」下的解决方法（所以小节的名字才叫「正常情况下的完整流程」）。那么要解决刚才的疑问中的特殊情况（包括其它特殊情况，比如主结点是恶意的），需要靠后面的小节介绍的域转换才行。

检查点（ checkpoints )

在介绍域转换之前，我们首先要介绍一下 checkpoint 的概念。一般情况下，每个结点需要保存所有的历史数据和状态机的每个历史状态，以便在需要的时候可以复查。但随着系统运行的时间越来越长，数据就会越来越多，最终肯定有存不下的情况。所以我们需要一种机制，可以放心的丢弃以前的历史数据，又不致于影响系统的运行和结点间的信任。

原始论文中给出的解决方法就是检查点（checkpoints）机制。所谓「检查点」，其实就是某一时刻结点状态机的状态。系统中的每个结点都会按相同的时期间隔（比如每隔 100 个请求序号）将状态机的状态创建为检查点。

如果某结点自顾自的创建的一个检查点，那么这个检查点是没有可信度的，只有它自己才相信这个检查点的正确性。因此如果一个结点想要创建一个别人都信服的检查点，除了创建检查点本身，还要创建这个检查点的「证明」，这个证明说明了大多数结点都认可了这个检查点。一个有证明的检查点，被称为「稳定检查点」（stable checkpoint）。只有稳定检查点之前的历史数据，才是可以放心删除的。

那么如何创建稳定检查点呢？假设一个结点 $i$ 最新处理的请求序号为 $n$，此时状态机的状态的哈希值为 $d$。它想在此时创建一个稳定的检查点，那么它将创建并广播消息 ${\langle CHECKPOINT, n, d, i \rangle}_{\sigma_i}$ 。同时它将收集其它结点广播的 $CHECKPOINT$ 消息，如果它收到 $2f$ 条不同结点广播出来的、序号为 $n$、状态哈希为 $d$ 的 $CHECKPOINT$ 消息，那么它就创建了一个稳定检查点，这 $2f+1$ 条消息（包含自己的消息）就是这个稳定检查点的证明。

前面我们也提到了一个区间 $[h, H]$ ，这个区间主要是为了防止恶意主结点滥用序号值。但我们没提过如何设置 $h$ 和 $H$ 的值。有了稳定检查点，这两个值就好设置了。论文中提出可以将 $h$ 设置为当前最新的稳定检查点的序号值，而 $H$ 设置一个相对较大的值，保证正常情况下在创建下一个稳定检查点时，其序号值也不会超过 $H$。比如，如果系统正常情况下每隔 100 个请求序号就创建一个检查点，那么 $H$ 可以设置为 200。

了解了检查点的概念，下面我们再来看看域转换时会发生什么。

域转换（View Changes）

前面我们提到过，所谓「域」，就是某个结点作为主结点的整个过程（就像中国古代「朝代」的概念）。每个域都有一个编号。每当主结点发生一次变换，域编号就递增加 1，这个过程也就是所谓的「域转换」。可以看到，其实域转换主要是主结点的变换。

为什么要设计「域」这个概念呢？这主要是为了保持整个系统的「活性」（liveness）。前面我们说过， PBFT 的系统模型就是主结点、从结点的模式，这种模式严重依赖主结点的正确性：如果主结点是正常的，那么它会给客户端请求分配正确的序号，然后将正确的 $\langle PRE$-$PREPARE\rangle$ 消息广播给所有从结点，各结点才能最终达成一致共识；如果主结点是恶意的，它就可能给各从结点发送各不相同的 $\langle PRE$-$PREPARE \rangle$ 消息，那么从结点肯定无法达成共识。可见如果没有机制可以将这样的恶意主结点换掉，那么不管有多少个正常的从结点，这个系统依然是废的，永远无法处理任何请求。所以在设计 PBFT 更换主结点的能力时，作者定义了「域」的概念，并将更换主结点的过程定义为「域转换」。

那么什么时候会发生域转换呢？其实任何会发生异常的地方，都有可能导致发生域转换，总结下来，主要有以下情况可能会发生异常：

从结点发送 $\langle PREPARE \rangle$ 消息后，在一定时间内没有收到 $2f$ 条其它结点广播的同样的 $\langle PREPARE \rangle$ 消息。
从结点发送 $\langle COMMIT \rangle$ 消息以后，在一定时间内没有收到 $2f$ 条其它结点广播的同样的 $\langle COMMIT \rangle$ 消息。
主结点不响应客户端的请求。

上面三种情况总结起来，其实都是「超时」（第三种情况其实是主结点不响应的情况，我们会在下一小节详细讨论）。可以说任何该发生却没有发生的情况，都会引起域转换。

下面我们来看看如何进行域转换。对于任一结点 $i$，假设它当前的域编号是 $v$。如果发生了前面提到的超时情况，则结点 $i$ 就会发起域转换，具体步骤如下：

结点 $i$ 暂时停止接收和处理消息（除了 $\langle CHECKPOINT \rangle$、$\langle VIEW$-$CHANGE \rangle$、$\langle NEW$-$VIEW \rangle$ 三种消息），并广播消息 $\langle VIEW$-${CHANGE, v+1, n, C, P, i \rangle}_{\sigma_i}$ 。
　其中 $n$ 是结点 $i$ 最新的稳定检查点的请求序号；$C$ 是 $n$ 对应的稳定检查点的证明（$2f+1$ 条 $\langle CHECKPOINT \rangle$ 消息）；$P$ 是一个集合，集合中的每一项为某结点 $i$ 中序号大于 $n$ 且处于 $prepared$ 状态的请求的信息 $P_m$。这里 $P_m$ 其实就是 $m$ 对应的 $\langle PRE$-$PREPARE\rangle$ 消息和 $2f$ 条相匹配的 $\langle PREPARE\rangle$ 消息。
当域编号为 $v+1$ 的主结点 $p$（此时它其实还不是主结点）收到 $2f$ 条步骤 1 中发送的 $\langle VIEW$-$CHANGE \rangle$ 消息，则它广播一条消息 $\langle NEW$-${VIEW, v+1, V, O \rangle}_{\sigma_p}$ 给所有其它结点。
　其中 $V$ 是新主结点 $p$ 收到的 $2f+1$ 条（包括自己的）$\langle VIEW$-$CHANGE \rangle$ 消息的集合；$O$ 是一些 $\langle PRE$-$PREPARE \rangle$ 消息的集合。集合 $O$ 是这样计算出来的：
1. 主结点 $p$ 计算出一个请求的序号范围。其中最小值我们记为 $min$-$s$，它的值为 $V$ 中所有稳定检查点的请求序号的最大值；最小值我们记为 $max$-$s$，它的值为 $V$ 中所有处于 $prepared$ 状态的请求的序号的最大值。
2. 主结点 $p$ 使用新的域编号 $v+1$ 为每一个序号位于 $[min$-$s, max$-$s]$ 范围内的请求创建一个 $PRE$-$PREPARE$ 消息，并将其加入到集合 $O$ 中。创建 $\langle PRE$-$PREPARE \rangle$ 消息时，假设当前的序号为 $n$，有两种情况：
  　　(1). 序号 $n$ 对应的请求信息存在于集合 $P$ 中。此时主结点 $p$ 创建如下消息：$\langle PRE$-${PREPARE, v+1, n, d \rangle}_{\sigma_p}$。其中 $d$ 是集合 $V$ 中序号为 $n$ 且域编号最大的 $\langle PRE$-$PREPARE \rangle$ 消息对应的请求的哈希。
  　　(2). 序号 $n$ 对应的请求信息不在 $P$ 中，这表明此消息已被成功处理。此时主结点 $p$ 创建如下消息：$\langle PRE$-${PREPARE, v+1, n, d^{null} \rangle}{\sigma_p}$。其中 $d^{null}$ 是一个特定的、空请求的哈希。（空请求在系统内的处理方式和正常请求一样，但它的操作为「无操作」，不会改变状态机的状态）
对于新的主结点 $p$，在它发送 $NEW$-$VIEW$ 后，就正常进入 $v+1$ 域。对于其它从结点，在收到 $v+1$ 域的 $\langle NEW$-$\rangle VIEW$ 消息后，会首先检查这个消息的正确性。如果正确，才会正式进入域 $v+1$。然后无论是主结点还是从结点，都会像前面描述的正常流程一样，开始处理集合 $O$ 中的所有 $\langle PRE$-$PREPARE \rangle$ 消息。
　从结点通过检查 $\langle NEW$-$VIEW \rangle$ 的签名、集合 $V$ 和集合 $O$ 是否正确，来判断 $\langle NEW$-$VIEW \rangle$ 消息是否正确（检查集合 $O$ 的方法与创建的方法一样）。
　另外，如果各结点发现自己的最新稳定检查点落后于集合 $V$ 中的最新稳定检查点，那么它也会保存集合 $V$ 中的最新检查点，并将其作为自己最新的检查点，丢弃旧的数据。或者如果发现自己缺少请求 $m$ 本身的数据（还记得请求数据和 $\langle PRE$-$PREPARE \rangle$ 不是放在一起传输的吗），它可以从别的结点那里获取到 $m$ 数据。

经过这三步以后，域转换就完成了，从这之后所有结点就进入了新的域时代了。

主结点不响应

前面我们提到了域转换发生的条件，其中一条就是主结点不响应客户端请求的情况。试想如果一个主结点是恶意的，但它不是通过给不同从结点发送不同消息来作恶，而是不响应客户端的请求、不将请求发送给其它从结点。如果没有一种机制来应对这种情况，那么从结点永远也不知道客户端曾经发送过请求，也就永远不会发起域转换，这个系统也就永远瘫痪了。

处理这种情况需要客户端的配合。如果客户端发现自己发出的请求没有或很少有结点返回数据，那么客户端可以认为主结点不响应。这时客户端就会将请求广播给所有从结点。每个从结点从客户端那直接收到 $\langle REQUEST \rangle$ 请求后，并不会马上处理，而是将请求转发给主结点，并等待与这个请求对应的、主结点发送的 $\langle PRE$-$PREPARE \rangle$ 消息。如果在一定时间内没有收到主结点的 $\langle PRE$-$PREPARE \rangle$ 消息，那么从结点就认为主结点没有响应，从而发送 $\langle VIEW$-$CHANGE \rangle$ 消息，提议进行域转换；如果有足够多（$2f+1$）个结点提议进行域转换，就会真正进入域转换，从而将不响应的主结点换掉。

（原论文中并没有讨论在主结点不响应时、进入域转换流程后，客户端当初广播给所有结点的请求是如何被处理的。依算法的情况来看，这个请求应该是被忽略了。客户端在发现仍然没有结点返回请求后，需要再次广播请求，直到结点们域转换完成，且换到了一个正常的结点当主结点）

关键问题分析

前面我们详细的说明了 PBFT 算法的流程，但也只是说明了流程，很少提到为什么要这样做。这一小节里，我们就针对一些关键问题，聊一聊「为什么」。

三阶段的作用

其实 PBFT 的整个流程还是非常容易理解的（我个人认为比「拜占庭将军问题」论文里给出的方法好理解多了），但我看完这个算法的第一个反应是：为什么要分三个阶段呢？一个阶段不行吗？两个阶段不行吗？

其实我们在之前的小节「如果我来发明这个算法」里已经提到过三阶段的原因了，但这里我们要说得更正式一些。

首先再次提一下我自己的认识。pre-prepare 阶段，是主结点分发请求给所有从结点的阶段，这个过程必不可少，也很好理解。prepare 阶段，是各从结点「商量」达成一致的阶段，大家把自己的收到的消息公布出来，看看自己是不是属于「大多数」，如果是，理论上讲其实就可以放心的响应请求啦。commit 阶段，是确定别人的 prepare 阶段是否成功的阶段，这样就可以避免自己通过了 prepare 阶段响应了请求，而别人并没有通过 prepare 阶段、也就没有响应请求，从而造成了状态不一致的状况。

这是我对三阶段中每阶段的作用的理解。若以原论文的描述为准，我感觉这些理解都不是很「正式」（但我自己觉得也没有错）下面我们看看原论文中的说法。

其实仔细琢磨一下 PBFT，就会发现只要正常结点间执行请求的顺序是一致的，它们的状态就能保持一致。因此保持请求的执行顺序的一致性就很重要。而保持一致性的关键，是序号不会被重复使用，即如果某些正常结点认为请求 $m$ 的序号是 $n$，那么其它正常结点就必须不能认为另一个请求 $m^\prime$ 的序号是 $n$。pre-prepare 和 prepare 阶段的作用，就是在同一域内保证了这一点。比如说，在域 $v$ 中，某一个或多个正常结点使用序号 $n$ 来执行请求 $m$，即 $prepared(m, v, n, i)$ 为 $true$；那么可以确定，其它的正常结点一定不会使用序号 $n$ 来执行另一个不同的请求 $m^\prime$。

为什么可以这么肯定呢？为了证明，我们先假设这种情况会发生，即存在一些正常结点 $j$ 使用序号 $n$ 执行另一个不同的请求 $m^\prime$，即 $prepared(m^\prime, v, n, j)$ 为 $true$。根据我们前面了解的 PBFT 三阶段的算法，$prepared$ 为 $true$ 代表有 $2f+1$ 个结点对某一消息的序号进行了相同的确认。这就是说，$prepared(m, v, n, i)$ 为 $true$ 代表有 $2f+1$ 个结点确认了 $m$ 的序号是 $n$；$prepared(m^\prime, v, n, j)$ 为 $true$ 代表有 $2f+1$ 个结点确认了 $m^\prime$ 的序号是 $n$。而结点的总数量为 $3f+1$，那么必定有 $f+1$ 个结点对这两种情况都进行了确认。恶意结点最多有 $f$ 个，那么对两种情况都进行了确认的 $f+1$ 个结点中，至少有 1 个是正常结点，而这是不可能的。所以假设不成立，肯定不会存在其它正常结点使用序号 $n$ 执行另一个不同的请求 $m^\prime$ 的情况。

但是正如我们所说，pre-prepare 和 prepare 仅能保证在同一域内请求顺序的共识。并不能保证跨域的情况下所有结点对请求的顺序仍能达成共识。假如某结点 $i$ 的 $prepared$ 函数为 $true$ 后立即执行了请求（即没有 commit 阶段），但其它结点的 $prepared$ 函数并不是 $true$，因而它们发起了域转换，那么结果是虽然结点 $i$ 也被迫转到了新的域，但只有它使用序号 $n$ 执行了请求 $m$ ；对于新主结点来说，序号 $n$ 可能还是未被分配的，所以当有新的请求时，新主结点就可能会将序号 $n$ 分配给新的请求，结果就是仍然出现了我们刚才讨论的问题，即结点 $i$ 使用序号 $n$ 执行了请求 $m$，但其它结点却使用序号 $n$ 执行了新的请求 $m^\prime$。

这里你可能会说，域转换时会将 $prepared$ 为 $true$ 的请求 $m$ 及序号 $n$ 放到 $\langle VIEW$-$CHANGE \rangle$ 中啊，这样根据前面讲的域转换的流程，新的主结点就会将这个消息的 $\langle PRE$-$PREPARE \rangle$ 消息再广播一遍，从而使这个请求再次正常执行一遍整个流程，序号 $n$ 也不会被复用了。但这里执行了请求 $m$ 的结点 $i$ 并没有发送 $\langle VIEW$-$CHANGE \rangle$ 消息，它是被迫进行域转换的，而其它主动提议域转换的结点的 $m$ 的 $prepared$ 函数并不为 $true$，因此 $\langle VIEW$-$CHANGE \rangle$ 消息中并不会包含请求 $m$ 及序号 $n$ 等信息。

所以为了避免上面说的情况，需要加上 commit 阶段。commit 阶段和域转换算法一起，保证了达到了 $committed$-$local$ 条件的请求，即使在发生域转换以后，在新的域里各结点依然能对消息的顺序达成共识。还是考虑刚才的情况，在结点 $i$ 内，$committed$-$local(m, v, n, i)$ 为 $true$ ，然后结点 $i$ 执行了这个请求。但此时其它结点 $committed$-$local$ 并不是 $true$（因而肯定还没有执行这个请求），而是超时发起了域转换。只要发起域转换的结点中至少有一个结点的 $prepared(m, v, n, i)$ 为 $true$，那么 $\langle NEW$-$VIEW \rangle$ 中肯定包含了消息 $m$ 和序号 $n$ 的 $\langle PRE$-$PREPARE \rangle$ 消息，因而在新的域里面会再次使用序号 $n$ 执行一遍关于请求 $m$ 的正常流程，此时除了刚才结点 $i$ 之外的结点就会仍然使用序号 $n$ 执行请求 $m$，从而达到与结点 $i$ 一致的状态（虽然不在一个域中）。

我们如何能确定发起域转换的结点中至少有一个结点 $prepared(m, v, n, i)$ 为 $true$ 呢？一方面，结点 $i$ 的 $committed$-$local(m, v, n, i)$ 已经是 $true$，也就是说它肯定收到了至少 $2f$ 条其它结点的 $\langle COMMIT \rangle$ 消息，这也说明至少有 $2f$ 个结点的 $prepared$ 为 $true$。另一方面，如果域转换想要成功，必定至少有 $2f$ 个结点主动发送 $\langle VIEW$-$CHANGE \rangle$ 消息。总结点数量为 $3f+1$，所以 $2f$ 个 $prepared$ 为 $true$ 的结点和 $2f$ 个发送 $\langle VIEW$-$CHANGE \rangle$ 消息的结点中，必须有重合的。也就是说，肯定有结点它的 $prepared$ 为 $true$ 并且发送了 $\langle VIEW$-$CHANGE\rangle$ 消息。

以上就是三阶段的作用的分析。总得来说，pre-prepare 和 prepare 阶段保证了在同一域内请求的执行顺序；commit 阶段和域转换规则保证了在不同域内，请求的执行顺序仍然是不变的。

相信经过上面一段详细的说明，读者对三个阶段的作用会有更加深刻的认识。

安全性（Safety）和活性（Liveness）

之前我们在讨论 PBFT 的各个方面时，其实已经涉及到安全性和活性的问题，但没有特意指出这俩特性。在这一小节里，我们再将安全性和活性相关的问题讨论一遍。

我们先说安全性。安全性是指系统内所有正常结点可以达成「正确的一致性」，而不会受内部恶意结点的干扰。「正确的一致性」是我自己发明的，这里不仅指达成一致的决定，而且这个决定需要是客户端的原始请求。比如客户端请求计算 10 的平方，那么各正常结点必须计算 10 的平方，而不是每个结点收到多个数值（如 10, 20, 30, …）然后计算这些数值的平均值（或中位数）的平方（拜占庭将军问题中的 $SM$ 算法就可能会再现这种情况）。对于后一种情况，虽然每个结点最终参加计算的值和结果都是一致的，但并不是原来客户端的请求。

由于 PBFT 系统中的所有消息都有签名，我们不用担心客户端的请求被篡改。所以只要每个正常的结点能拿到客户端的请求并只执行原始的请求，就不必担心刚才提到的后一种情况。需要重点关注的仍是如何达成一致。可以确定，只要所有正常的结点始终以同样的顺序处理请求，那么这些正常结点的状态始终是一致的，也就是达成一致了。因而总得来说，就可以保证安全性。那算法是如何保证所有正常结点以相同的顺序处理请求呢？正是前面我们刚才讨论的三阶段和域转换的作用：pre-prepare 和 prepare 可以保证在同一域内请求的执行顺序达成一致；commit 阶段和域转换规则可以保证在不同域内这一执行顺序也不会发生改变。详细信息上一小节已作了详细的说明，这里不再重复了。因此可以说，签名机制和整个 PBFT 的算法设计提供了安全性。

不过论文中也提到一点，就是这里的安全性仅仅是指系统内部的安全性，它只能使系统内的恶意结点无法干扰正常的工作，但并不能阻止外部如客户端作恶（比如向整个系统写入垃圾数据）。

我们再来说说活性。前面说过，所谓活性就是整个系统持续处理请求的能力。如果主结点是一个恶意结点，而没有机制可以更换这个主结点，那么这个系统就没有活性。前面我们介绍过，域转换其实就是更改主结点，因此可以说，PBFT 中的活性主要是由域转换机制保证的。具体的域转换规则前面已经详细介绍过，这里不再重复。但这里我们要说一下保证活性的三个细节。

第一个细节，就是要避免频繁地进行域转换。这主要是通过线性增加超时时间来完成的。比如一个结点在开始处理一个请求时，它设置一个时长为 $T_1$ 的计时器，如果计时器超时仍没有完成这个请求的 commit 阶段，那么除了发起域转换，它还会把 $T_1$ 设置得更大一些（比如 $2T_1$），以保证下次可以容忍更久的请求处理时间（当然也需要在请求处理得比较快的时候减小 $T_1$，或设置 $T_1$ 的最大值，防止超时时间无限增大）；再比如一个结点为了更新到域 $v+1$ 而发送 $\langle VIEW$-$CHANGE \rangle$ 消息后，设置一个时长为 $T_2$ 的计时器，如果计时器超时仍没有收到 $\langle NEW$-$VIEW \rangle$ 消息，那么这个结点可以再次为更新到域 $v+2$ 而发送 $\langle VIEW$-$CHANGE \rangle$ 消息，并这次计时器的时间间隔会设置得更大，比如 $2T_2$。

第二个细节，如果一个结点累计收到了超过（包含） $f+1$ 条域编号比结点自己当前域编号大的 $\langle VIEW$-$CHANGE \rangle$ 消息，那么该结点需要立即使用这些消息中的域编号最小的编号，重新发送一遍 $\langle VIEW$-$CHANGE \rangle$ 消息。这样有助于及时的进入到新的域中。（原因如下：假设某结点 $i$ 收到了 $f+1$ 个其它结点的 $\langle VIEW$-$CHANGE \rangle$ 消息，说明至少有一个正常结点发现了异常并发起了域转换。但若结点 $i$ 非常等待自己发现异常（比如共识三阶段的超时）才去发起域转换，会多浪费一些时间。反正已经可以确认有正常结点发现异常了，不如直接跟随马上发起域转换。）

第三个细节是自然而然的，即除了恶意的主结点，其它恶意结点无法强制频繁地进行域转换。因为域转换算法规定需要有 $2f+1$ 个结点发送 $\langle VIEW$-$CHANGE \rangle$ 消息才可能进行域转换，而系统中最多有 $f$ 个恶意结点，显然达不到域转换成功的要求（事实上，只要发送 $\langle VIEW$-$CHANGE \rangle$ 消息的结点数量小于（不包含） $f+1$ ，就肯定不会进行域转换；但超过或等于 $f+1$ 个结点发送 $\langle VIEW$-$CHANGE \rangle$ 消息，就肯定会进行域转换。因为这 $f+1$ 个结点中，必定至少有一个正常结点，而一个正常结点一旦发送了 $\langle VIEW$-$CHANGE \rangle$ 消息，就不会处理其它消息。这会导致其它正常处理请求的结点因无法收到 $2f$ 条 $\langle PREPARE \rangle$ 或 $\langle COMMIT \rangle$ 消息而超时，从而也发起域转换）。虽然恶意主结点可以通过不响应或发送错误消息强制发起域转换，但因为最多只有 $f$ 个恶意结点，所以最多连续强迫系统发生 $f$ 次域转换，这是可以接受的。

PBFT 与 $SM$ 算法的比较

这一小节里我们将 PBFT 与拜占庭将军问题的文章中的 $SM$ 算法放在一起，进行一下比较，从而可以更加深刻的理解这两种算法。

其实 PBFT 与 $SM$ 有一定的相似性，但 PBFT 更进一步，考虑和解决了很多现实的问题，所以才可以应用于实际环境中。下面我们先聊聊它们之间的共同点，再看看 PBFT 比 $SM$ 「更进一步」在哪些地方。

共同点

相比起不同点，PBFT 与 $SM$ 的共同点较少，我认为主要在两个方面：一是系统模型相同，都是主从结构；二是从结点拿到主结点消息后，都会进行「沟通」与汇总。

首先在$SM$ 算法中，有一个司令官，其它人都是副官，接受并执行司令官的命令；而 PBFT 算法中，也分主结点和从结点，从结点也接受主结点的消息并执行。这一点上，它们是一样的。

其次在两种算法中，所有副官（从结点）收到司令官（主结点）的消息后，都不会着急着去立刻执行，而是将自己收到的消息广播给其它结点，并接收其它结点广播的消息。这就像一个沟通的过程：我告诉别人我收到了什么消息，别人也告诉我他收到了什么消息。最终每个结点会在这些消息的基础上汇总一个结果。这一过程在 PBFT 中并不那么明显，但 prepare 阶段本质上也是这么一个过程。

我觉得在相同点上，两种算法主要就是这两方面的相同，这两方面也都是基础。下面我们来看看在这两个基础之上的不同，这些不同点也是让 PBFT 的应用性强于 $SM$ 的地方。

不同点

由于 PBFT 与 $SM$ 的不同点稍多且需要较多的说明，因此我们分小节来看这些不同点。

「一致性」与「正确的一致性」

在 $SM$ 算法中只要求一致性，即只要最终所有副官能达成一致的结果就可以了，至于这个结果是什么并不关心。比如如果司令官是叛徒，他给有的副官发送「进攻」、给有的副官发送「撤退」，只要最终忠诚的副官们行动一致，就算是正确的，不管是「一致进攻」还是「一致撤退」。

但这在 PBFT 中是不行的。在 PBFT 中，客户端请求什么，所有结点就计算什么。如果从结点们发现彼此请求的数据不一致，它们就拒绝执行，而不是像 $SM$ 那样取一个中间状态去执行。这就是通过对 $\langle PRE$-$PREPARE\rangle$ 消息的检验和必须收到 $2f$ 条 $\langle PREPARE \rangle$ 消息这两方面来保证的。

外部可识别正确结果

在 $SM$ 中，最终所有副官的行动肯定是一致的。但作为一个外部成员，却无法知道哪些人的行动是可信的。比如存在 5 个将军，其中只有 2 个是忠诚的，3 个是叛徒。并且司令官是忠诚的。因此在发送命令时，忠诚的司令官给每个人发送了「进攻」的命令。根据 $SM$ 算法，另一个忠诚的副官肯定也会执行「进攻」。但另外 3 个叛徒的行为就不一定了，他们可能都执行的是「撤退」。那么在一个外人看来，你该相信哪个行动是正确的呢？

PBFT 中的客户端其实就相当于这样一个「外人」。但与 $SM$ 不同的是，在 PBFT 中客户端是能够知道哪些结果是正确的。这是它们之间很大的不同。

那么 PBFT 是如何做到这一点的呢？其实主要是结点数量的差别。

仔细研究 $SM$ 算法就会发现，虽然 $f+2$ 个结点也可以让正常结点（哪怕只有 2 个）达成一致，但外部（比如客户端）并不知道哪个结点的结果是正确的，正如刚才的例子显示的，如果 $f>=2$ 且 $f$ 个结点的结果是一致的（但是错误的），那么外部（比如客户端）是无法确定应该相信哪个结果的。比如若客户端根据「数量最多的结果就是正确的」的原则，那么它就会采用 $f$ 个恶意结点返回的结果。这显然是不对的。因此在 PBFT 中，除了要求正确的结点达成一致外，还要有数量上的优势，让客户端知道应该采用谁的结果。所以 PBFT 要求 $3f+1$ 个结点。由于只有 $f$ 个恶意结点，那么客户端只要收到 $f+1$ 个相同的结果，就可以认为这是正常的结果。

既然只要有数量上的优势就可以，为什么 $2f+1$ 个结点不行呢？根据 PBFT 论文中的描述，PBFT 可以用于存在恶意结点的情况，那么除了有 $f$ 个恶意结点，还可能有 $f$ 个正确结点「临时出点状况」，比如网络偶尔故障，因此 $3f+1$ 个结点可以最大程序的确保整个系统正常运行。

（事实上我对论文中这个解释是有点疑问的。客户端只要 $f+1$ 个结点返回一样的结果，就可以认为这个结果就是正确的结果。但在系统内部处理请求的时候，每个结点仍然需要等待 $2f$ 条 $\langle PREPARE \rangle$ 和 $\langle COMMIT \rangle$，因此只要有 1 个正常结点「临时出点状况」，出状况其间请求是无法处理的。所以这难道不是要求所有正常结点都不能出状况吗？）

那么 $4f+1$ 个结点行不行呢？也不是不可以，只是这么多结点拖慢整个系统处理请求的速度，却没带来其它额外好处。

活性

是否考虑了活性，是 $SM$ 与 PBFT 非常明显也是非常重要的区别。PBFT 考虑到了活性问题，所以它是「实用的」；而 $SM$ 根据没有考虑更换司令官的问题，因而也就无法在实际应用中使用。

总结

PBFT 是一个比较重要的共识算法，是许多其它共识算法的基础。在这篇文章里，我们详细介绍了 PBFT 的相关知识，包括主从模式，pre-prepare / prepare / commit 三阶段及其作用，域和域转换等。pre-prepare 和 prepare 阶段让所有正常结点对请求的处理顺序达成一致；而 commit 和域转换规则保证了在发生域转换时，也能保持这个处理顺序。

限于作者水平，文章中难免有错误的地方，如果发现感谢您能不吝指正。

实用拜占庭容错算法（PBFT）

引言