paxos算法_共识算法（8） —— PBFT 算法详解

本文翻译自：伊利诺伊大学厄巴纳-香槟分校助理教授 Ling Ren 开设的讨论课：CS598 Consensus Algorithm

参考论文：

前言

上一节中我们介绍了经典的Paxos算法。我们知道在节点只可能出现故障错误的情况下，可以实用Paxos算法来解决共识问题。但是如果节点不仅仅可能会宕机，还可能会发送错误的消息呢？实用拜占庭容错算法（PBFT）就是Paxos算法的拜占庭错误的扩展。

我们将逐步改善Paxos算法，最终形成PBFT算法，使之在拜占庭错误的环境下也依然可以使用。

拜占庭错误节点数量

在故障错误下我们知道 n > 2f，而在部分同步的拜占庭错误环境下，n > 3f。这是因为：

1. 在部分同步算法中，节点接收到 n - f 条消息之后必须要做出决策，否则，如果有f个节点发生故障，将不满足存活性的条件
2. 在拜占庭错误环境下，节点可能收到的假消息数量 f 一定要小于真消息数量。因此消息数量必须大于 2f
3. n-f > 2f ，n > 3f

在本文中我们确定 n = 3f+1

身份验证

接下来一步，我们要验证消息的正确性。首先我们要确定消息的发送者一定是来源于某个特定节点，而不是由其他节点伪造。

在此我们引入签名机制，在消息中加入该节点特有的签名。例如：当某个节点收到了 2f + 1 个消息，它可以得知这些消息的签名都是来自 2f + 1 个不同节点，此外我们可以知道这些节点是谁。

从 Paxos 到 PBFT

我们说 PBFT 是 Paxos 算法的一种改进，理由是这两种算法的问题设定和环境设定除了错误类型之外完全一致。因此我们将从 Paxos 开始，讨论出现拜占庭错误的情况下会有哪些情况会导致 Paxos 失败，随后逐步改进，最终形成我们的 PBFT 算法

上图为原本的 paxos 算法。我们在安全性证明中提到，如果有节点提交了v，那么至少有f+1 个节点锁定了值v。然而在拜占庭错误中这个断言是不成立的：节点可能假装锁定并且发送投票 vote，而在status的信息中只包含上一轮锁定的值和view。

因此我们在这里需要扩大收到vote的数量，让收到的所有 status 消息中至少有一个诚实节点在上一轮锁定了已经提交的值。

这样就万事大吉了吗？我们再列举另外几种拜占庭节点可以胡作非为的可能性。

1. 如果拜占庭节点在 status 消息中给出一个根本不存在的锁定值，而且
   非常高，那么leader会以为这个是最新的值并且发送该值的提议
2. 如果拜占庭节点是假的 leader， 并且发送假的 proposal 给节点们
3. 如果拜占庭节点是假的 leader， 并且发送假的 success 消息 （致命！因为所有节点收到success 之后都会commit）

我们需要验证这个节点发的proposal 和 success，status 消息都是真实可信的，因此我们在消息签名的基础上再增加了 backup 的概念：把收到的签名消息收集起来再转发，证明自己收到了这些消息

1. 证明 success 消息合法：每收到一个投票消息，便把收到的消息和签名一起存在缓存中，在发送的时候带上其中 2f+1 个消息+签名（记为 ）,用以证明自己确实收到了2f+1 个投票
2. 证明 status 消息合法：在 锁定值之前增加一轮投票（见下图）：leader 在该轮收集到 2f+1 个投票消息后，一并转发给其他节点；节点在收到这些投票消息后将它存在缓存中，并且在 status消息中带上这些消息+签名，用以证明自己确实可以锁定这些值
3. 证明 propose 消息合法：在 propose 中带上收到的 2f+1 个status消息中的 2f+1 个消息+签名（一共为
   个签名），用以证明这个 propose 消息是收到足够的status之后发出的

总结

该算法与原来的PBFT有一点小小的不同：运用签名减少了消息收发的总数量，增加了验证签名的计算量（可以忽略不计，因为分布式系统的主要瓶颈在于IO而非计算）

PBFT算法被广泛运用与各种区块链底层协议中，但是针对不同的情况该算法会有一些低性能的瓶颈，下一章我们将介绍PBFT算法的几种不同的改进