共识算法的简单理解（二）

我们来介绍联盟链中最经典的一种算法——拜占庭容错算法（Practical Byzantine Fault Tolerance，PBFT）。

算法的提出主要是为了解决拜占庭将军问题。什么是拜占庭将军问题呢？首先介绍拜占庭，拜占庭位于现在土耳其的伊斯坦布尔，是古代东罗马帝国的首都，君士坦丁堡、拜占庭、伊斯坦布尔，都是这一个地方。同一个地方有这么多名字，可见这个地方的重要性，历史上一直是战争、宗教的中心。

罗马帝国国土辽阔，为了达到防御目的，每块地都驻扎一支由将军统领的军队，军队与军队之间都距离比较远，将军与将军之间只能依靠信差传递信息。 在战争出现的时候，拜占庭军队所有将军必需达成一致，才能最终决定是否去攻打敌人的阵营。但是，在军队内有可能出现叛徒或间谍，左右将军的决策，受影响的将军多了的话，会最终影响将军们的集体决策。

在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致意见的问题，就是拜占庭将军问题。

当然现在我们都知道，Leslie Lamport 与另外两人在 1982 年发表的论文《The Byzantine Generals Problem 》提出了拜占庭将军问题求解的证明，在背叛者数量为 n 的情况下，只要将军总数大于 3n，忠诚的将军就可以达成一致意见。

注意这里说的是忠诚的将军达成一致意见，假始这些忠诚的将军仍然能通过少数服从多数的方式来决定他们的战略，便称达到了拜占庭容错。举例，有一个将军出现问题，将军总数是 3 的情况下，剩余两个忠诚的将军有可能出现意见向左的情况，所以将军总数是 4 的情况下才能够实现容错。

我们放到分布式系统中理解：

1. 如果 n 个有问题节点既是故障节点，又是作恶节点，那么根据少数服从多数的原则，系统中正常节点只需要比 n 个节点再多一个节点，即 n+1 个节点，好节点的数量就会比故障节点数量多，那么系统就能达成共识（节点总数 2n+1），也就是说这种情况支持的最大容错节点数量是（n-1）/2。

2. 如果故障节点和作恶节点都是不同的节点。那么就会有 n 个问题节点和 n 个故障节点，当发现节点是问题节点后，会被系统记录并排除在外，剩下 n 个故障节点，那么根据少数服从多数的原则，系统里正常节点只需要比 n 个节点再多一个节点，即 n+1 个节点，好节点的数量就会比故障节点数量多，那么系统就能达成共识。所以，所有类型的节点数量加起来就是 n+1 个正确节点，n 个故障节点和 n 个问题节点，即 3n+1，这种情况下支持的最大容错节点数量是 n。

PBFT 算法的基本流程主要有以下四步：

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

2. 主节点广播请求给其它节点，节点执行 PBFT 算法的三阶段（pre-prepare、prepare、commit）共识流程。

3. 节点处理完三阶段流程后，返回消息给客户端。

4. 客户端收到来自 n+1 个节点的相同消息后，代表共识已经正确完成。

为什么收到 n+1 个节点的相同消息后就代表共识已经正确完成？从上一小节的推导里可知，无论是最好的情况还是最坏的情况，如果客户端收到 n+1 个节点的相同消息，那么就代表有足够多的正确节点已全部达成共识并处理完毕了。

下一讲，我们来继续探讨三阶段共识流程这一 PBFT 算法核心内容。