深度长文丨系统读懂PBFT共识算法

PBFT 是 Practical Byzantine Fault Tolerance 的缩写，意为实用拜占庭容错算法。该算法首次将拜占庭容错算法复杂度从指数级降低到了多项式级，其可以在恶意节点不高于总数 1/3 的情况下同时保证安全性（Safety）和活性（Liveness）。我们假设所有节点的总数为 R ，拜占庭节点数量为 f，下面给出安全性证明：

设想 f 个叛变者和 k 个忠诚者，叛变者故意使坏，可以给出错误的结果，也可以不响应。某个时候 F 个叛变者都不响应，则 k 个忠诚者取多数既能得到正确结果。当 f 个叛变者都给出一个恶意的提案，并且 k 个忠诚者中有 f 个离线时，剩下的 k - f 个忠诚者此时无法分别是否混入了叛变者，仍然要确保取多数能得到正确结果，因此，k - f > f，即 k > 2f 或 R - f > 2f，所以系统整体规模 R 要大于 3f。所以为了能确保达成共识的拜占庭系统节点数至少为 4，此时最多允许出现 1 个拜占庭节点。

PBFT 是一种基于状态机副本复制的算法，每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。PBFT 中所有的副本都在视图（View）的轮换过程中运作，当主节点掉线的时候就启动视图更换过程保证算法的持续运行。

从上面的内容可以看出，PBFT 算法的流程如下：

1.客户端向主节点发送请求；

2.主节点向其他副本广播请求；

3.所有副本执行请求后，将结果返回给客户端；

4.客户端需要等待 2f+1 个不同副本返回相同的结果，作为最终结果。

这里面暗含着的是所有节点都是确定性的和所有节点都从相同的状态开始执行这两个条件。

首先客户端发送了一个请求到主节点，之后经典的三阶段协议（three-phase protocol）就拉开了序幕。

1.预准备阶段

首先，主节点向所有副本节点发送预准备消息。这里面包含有消息序号，视图编号和消息的摘要。需要注意的是预准备消息是不包含请求的，这样做有两个好处，一是压缩消息大小提升传播效率，二是将请求排序与请求传输解耦。

接着副本节点会去验证消息的签名是否正确，视图编号是否一致和消息序号是否满足水线要求。这里就要引出 PBFT 中的水线机制（watermark）。对于消息的序号 n，要求其在水线 h 和 H 之间。水线存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。

2.准备阶段

如果副本节点接受预准备消息，就进入了准备阶段。在准备阶段，每一个节点都向其他节点发送包含自己 ID 的准备消息，同时也接收其他节点的准备消息。对于收到准备消息同样进行合法性检查。验证通过则把这个准备消息写入自己的消息日志中。一个节点集齐至少 2f+1 个验证过的消息才进入准备状态。

3.提交阶段

在提交阶段，每个节点广播 commit 消息告诉其他节点自己已经进入准备状态。如果集齐至少 2f+1 的 commit 消息则说明提案通过。

在经过了三阶段协议之后，每个副本节点都想客户端发送回复，副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。

总结

PBFT 共识算法在 1999 年的时候由 Castro 和 Liskov 正式提出，它在设计时考虑的共识对象是一些相对不大的消息。为了对消息进行排序，PBFT 设计了水线机制，通过 checkpoint 机制移动水线，用以并发地处理多个消息的投票过程。同时， PBFT 只有当某个节点作恶或掉线才触发视图的切换，主节点的更换。这是因为视图的切换过程也是需要共识的，这一过程非常耗时，因此 PBFT 不能接受频繁的视图变更。再加上为了配合水位机制，视图切换的消息都相对普通消息要大得多。因为以上原因，PBFT 的设计非常复杂，效率不高。

然而，随着技术的发展，区块链技术的诞生轻松的化解掉了 PBFT 在设计上的一些问题。 在区块链中，每一个消息（区块）前后相继，用于并发处理的水位机制毫无用处，因此水线机制以及为此服务的 checkpoint 机制就没有存在的意义了。没有了水线机制和 checkpoint，阻碍视图切换的就只剩下视图切换的共识过程了，而这一点又被区块链本身作为共识账本的特点给简化掉了。如果节点的切换通过链上的数据来达成共识，那么原本需要经过在线共识的过程又省掉了。

因此大量的区块链项目都使用了改进的 PBFT 用作共识算法，作为拜占庭容错的代表的 PBFT 也在不断地优化的过程中焕发出了新的生机。除了PBFT共识算法以外，不少优秀的区块链项目自行研发除了更加创新的共识算法，比如DPOW共识算法。此共识算法由UENC公链首创，极大地提升了去中心化网络下的交易性能。

—-

编译者/作者：通证时代Time

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。