为什么PBFT需要3个阶段消息？

前言

在面试的时候，很多同学的简历熟悉PBFT共识算法，在现场面试的时候，却只能说个主要逻辑，离完整的算法，还差十万八千里，相似从网络上看了一些文章，就算是熟悉了。当我问“为什么PBFT需要3个阶段消息？2个阶段行不行”时，还没有人能回答出来。

回答这个问题，还要从PBFT要解决的本质问题说起，所以我打算以这样一个思路，为大家回答问题：

• PBFT与拜占庭问题
• 拜占庭节点在网络中的行为
• 什么是3阶段消息
• 3阶段消息解决什么问题
• 为什么不能只有前2个阶段
• 论文使用的2个不变性
• 为什么3个阶段可以达成一致性

PBFT与拜占庭问题

莱斯利·兰波特在其论文[1]中描述了如下拜占庭问题：

一组拜占庭帝国的将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻，或部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中，每位将军都将自己投票进攻还是撤退的信息，通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票，和其他所有将军送来的信息，就可以知道共同的投票结果，而决定行动策略。

问题在于，将军中可能出现叛徒(坏将军)，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。阻止好将军达成一致的形成策略。

摘自：维基百科：拜占庭将军问题，有删改。

很多人喜欢玩狼人杀，我也喜欢，但我玩的很菜，我用狼人杀跟拜占庭将军问题做个类比。

在狼人杀开局的时候，你是好人，并且不知道自己的队友是谁，也不知道狼人是谁，但所有的好人都有一个共同的目的：干死狼人，好人获胜。所以游戏中需要使用技巧和策略，达成目的。

拜占庭将军问题是类似的，好的将军不知道其他将军是好的，还是坏的，但所有好的将军的目的是：行动一致，共同进退。所以，它们也需要策略达成一致。

BFT是一类解决拜占庭将军问题的策略/算法：让非拜占庭节点达成一致的算法。在这类论文中，拜占庭节点指“坏”的将军，非拜占庭节点指“好”的将军。

PBFT是实用拜占庭算法（Practical Byzantine Fault Tolerance）的缩写，该论文与1999年发表，另外2001年又发表了一篇Practical Byzantine Fault Tolerance and Proactive Recovery，让PBFT拥有恢复能力。

PBFT作为解决拜占庭问题的策略：非拜占庭节点不知道哪些是拜占庭节点，哪些是非拜占庭节点，PBFT要让非拜占庭节点达成一致。

拜占庭节点在网络中的行为

拜占庭问题是在分布式对等网络，对通信容错所提出来的。在真实世界中，拜占庭问题是什么样的？

通常使用拜占庭行为，描述拜占庭节点可能的行为，拜占庭行为有：

• 任何不遵守协议的动作
• 恶意代码、节点
• 代码bug
• 网络故障、数据包损坏
• 磁盘崩掉、重复丢失
• 无权限时加入
• …

什么是3阶段消息

3阶段消息是：Pre-prepare、Prepare和Commit。每个消息都会包含数字签名，证明消息的发送者，以及消息类型，下文中会省略。

Pre-prepare消息由主节点发出，包含：

• 当前view：v
• 主节点分配给请求的序号n
• 请求的摘要d
• 请求本身m

务必记牢，m、v、n、d，后面会使用缩写。

Prepare是副本节点收到Pre-prepare消息后，做出的响应，发送给所有副本节点，包含：

• v
• n
• d

Prepared状态：副本i有Pre-prepare消息，且收到2f个有效的Prepare消息。

副本i达到Prepared状态，可以发送Commit消息，Commit消息的内容和Prepare消息内容相同，但消息类型和数字签名是不同的，所以可以区分。

m可以使用d代替，所以Prepare和Commit消息使用d代替m，来节省通信量。

3阶段消息解决什么问题

前面提到，PBFT解决的是拜占庭问题的一致性，即让非拜占庭节点达成一致。更具体的说：让请求m，在view内使用序号n，并且完成执行m，向客户端发送响应。

为什么不能只有前2个阶段消息

这个问题的等价问题是：为什么Pre-prepare和Prepare消息，不能让非拜占庭节点达成一致？

Pre-prepare消息的目的是，主节点为请求m，分配了视图v和序号n，让至少f+1个非拜占庭节点对这个分配组合<m, v, n>达成一致，并且不存在<m', v, n>，即不存在有2个消息使用同一个v和n的情况。

Prepared状态可以证明非拜占庭节点在只有请求m使用<v, n>上达成一致。主节点本身是认可<m, v, n>的，所以副本只需要收集2f个Prepare消息，而不是2f+1个Prepare消息，就可以计算出至少f个副本节点是非拜占庭节点，它们认可m使用<v, n>，并且没有另外1个消息可以使用<v, n>。

既然1个<v, n>只能对应1个请求m了，达到Prepared状态后，副本i执行请求m，不就达成一致了么？

并不能。Prepared是一个局部视角，不是全局一致，即副本i看到了非拜占庭节点认可了<m, v, n>，但整个系统包含3f+1个节点，异步的系统中，存在丢包、延时、拜占庭节点故意向部分节点发送Prepare等拜占庭行文，副本i无法确定，其他副本也达到Prepared状态。如果少于f个副本成为Prepared状态，然后执行了请求m，系统就出现了不一致。

所以，前2个阶段的消息，并不能让非拜占庭节点达成一致。

如果你了解2PC或者Paxos，我相信可以更容易理解上面的描述。2PC或Paxos，第一步只是用来锁定资源，第2步才是真正去Do Action。把Pre-prepare和Prepare理解为第一步，资源是<v, n>，只有第一步是达不成一致性的。

2个不变性

PBFT的论文提到了2个不变性，这2个不变性，用来证明PBFT如何让非拜占庭节点达成一致性。

第1个不变性，它是由Pre-prepare和Prepare消息所共同确保的不变性：非拜占庭节点在同一个view内对请求的序号达成共识。关于这个不变性，已经在为什么不能只有前2个阶段消息中论述过。

介绍第2个不变性之前，需要介绍2个定义。

• committed-local：副本i已经是Prepared状态，并且收到了2f+1个Commit消息。
• committed：至少f+1个非拜占庭节点已经是Prepared状态。

第2个不变性，如果副本i是committed-local，那么一定存在committed。

2f+1个Commit消息，去掉最多f个拜占庭节点伪造的消息，得出至少f+1个非拜占庭节点发送了Commit消息，即至少f+1个非拜占庭节点是Prepared状态。所以第2个不变性成立。

为什么3个阶段消息可以达成一致性

committed意味着有f+1个非拜占庭节点可以执行请求，而committed-local意味着，副本i看到了有f+1个非拜占庭节点可以执行请求，f+1个非拜占庭节点执行请求，也就达成了，让非拜占庭节点一致。

虽然我前面使用了2PC和Paxos做类比，但不意味着PBFT的Commit阶段就相当于，2PC和Paxos的第2步。因为2PC和Paxos处理的CFT场景，不存在拜占庭节点，它们的主节点充当了统计功能，统计有多少节点完成了第一步。PBFT中节点是存在拜占庭节点的，主节点并不是可靠(信)的，不能依赖主节点统计是否有f+1个非拜占庭节点达成了Prepared，而是每个节点各自统计，committed-local让节点看到了，系统一定可以达成一致，才去执行请求。

总结

本文介绍了2个阶段消息是无法达成一致的原因，而为什么3阶段消息可以。最核心的还是要理解好，PBFT解决了什么问题，以及它是如何解决的。

PBFT解决的是在拜占庭环境下，如何提供一致性，以及如何持续的提供一致性的问题。本文只介绍了如何提供一致性，没有提如何持续提供一致性，即PBFT的可用性。现在，不妨思考一下，View Change是如何保证切换时一致性的，是否也需要2个不变性的支持呢？