技术 | 分布式系统的共识算法与容错·下篇（福利在文末）

在上一篇文章中，我们介绍了三种主要的共识算法。 今天的文章从比较这三种共识算法开始。

一、典型共识算法比较

现在让我们详细了解一下 Paxos。 其实对于Paxos来说，这个理论（或原理）就是经典的纯异步模型非拜占庭问题的基本算法。

图1

传统分布式系统中几乎所有的算法都是Paxos的变种，或者派生自Paxos，主要就是这样一个过程（图1）。

首先，根据前文提到的FLP定理，从理论上讲，不可能有一个确定的共识算法，但在实际工程中，往往有很多前提或假设可以使用。 通过这些假设，我们可以得到一个Leader。 正是因为在实际工程中有Leader这个前提条件比特币共识算法比特币共识算法，Paxos算法才能在实际工作中正常合理的工作。

也就是说，在这个共识开始的时候，每个节点都有自己不同的提案。 共识结束后，所有人都同意leader的提议，即完成了共识的预期目标。

图 2

在拜占庭问题下，PBFT是目前可以实现功能性的算法，其复杂度为多项式级别。 达成共识的过程可以类比，比上一个要复杂。 之所以这么复杂，是因为恶意节点多。 为了消除这些恶意节点的影响，每个节点都必须广播自己的消息。 通过这种大量的沟通成本，获得最终共识的一致性。

因此，Paxos与PBFT的区别在于后者（指PBFT）的通信量明显增加。 前者的通信量可以看作是N的复杂度，而后者的通信量是

的复杂性。

图 3

最后看一下典型的POW算法。 它牺牲了强一致性，采用了最终一致性，在这个前提下简化了节点间的通信。

在最初的Leader选举阶段，每个矿工都会默认成为Leader。 然后看谁先挖矿，先挖矿的矿工会广播自己挖矿的消息，然后这个区块就会按照Gossip协议传遍全网。 当其他节点收到新区块时，会停止自己的挖矿过程，然后验证收到的新区块是否正确。 如果正确，他将根据新区块继续向前挖区块。 每个人都可以看到整个过程。

前两种算法的一致性是通过多数决策，而在 POW 中，是一种经济激励，让所有矿工的行动保持一致。

比如对于矿工来说，如果在别人广播新区块的基础上继续挖区块，此时获得的经济收益远远大于不顾别人挖出正确区块所获得的收益。

因此，Paxos和PBFT通过确定性多数原则实现一致性，而post-POW通过经济博弈原理实现一致性。

为什么这些算法的性能会有如此大的差异？

大家可以想一下，性能取决于它的运算过程，而在运算过程中，PBFT的复杂度是

，Paxos复杂度为N，我们将Paxos N与POW进行比较，然后进行分析。

图 4

在这两种简化模型下，可以清楚地看到，随着节点数量的增加，传统共识算法的性能会迅速下降，而对于 POW 来说，可以保证相对恒定的出块速度。

所以图4基本可以说明，如果要做公链，实现真正的去中心化，运行几万甚至几十万节点，那么目前看来，POW可能是最好的选择。

但是如果你想像EOS一样选择少量的超级节点，可以选择使用PBFT等算法来实现。 以PBFT为例，如果不真正优化中间信息传播过程，原则上是没有用的。 该方法适用于数万甚至更大的节点。

2. 共识算法容错性分析

一个系统必然会出现故障，甚至肯定会有恶意节点。 区块链的容错功能和传统算法一样，更重要的是如何抵御各种攻击。 对于Paxos算法，它可以容忍超过一半（超过50%），即崩溃最多的节点不超过50%。

关于拜占庭，80年代有一篇经典论文（The Byzantine Generals Problem）。 论文中对此进行了详细分析。 拜占庭模型有两种解决方案。 在口头协议的方式下，最多只能提供总数的三分之一。 容错性，那么对于书面约定，所有忠诚节点在保持共同一致动作的前提下，可以有任意数量的叛徒节点。

论文下载地址：

~luca/cs174/byzantine.pdf

前面说过，Paxos的容错率上限是50%，拜占庭的容错率上限是1/3。 那么是不是可以结合我们的一些实际工程应用，在我们的特定场景下获得更高的容错率呢？

其实这是可以的，那么在什么情况下才能达到更高的容错率呢？

以太坊的创始人提出了一个解决方案，引入了一些先决条件：

通过引入这四个条件，“即使只有一个忠诚节点，在强同步条件下也能做到99%的容错”。

但是这里特别重要的是，如果前四个条件，比如强同步条件不满足，所有观察者都是恶意或者被攻击，或者延迟选择算法不能正常工作，门限共识算法就不能正常工作。 运行，如果不满足这些条件，整个系统最终会恢复到Paxos的50%容错和Byzantium的33%容错。

3. 共识算法的应用

在传统的分布式应用中，主要是基于Paxos和Paxos的各种变体，比如Raft，在Zookeeper等应用广泛的系统中都会使用到。

在区块链场景下，目前的公链主要是基于POW和POW的变种，比如POS和DPOS，实现完全去中心化的超大规模网络。

对于联盟链，它的节点数可以是几十个。 在这种情况下，可能会使用传统的共识算法，例如 PBFT 和基于 PBFT 的变体，这些算法可能会达到数十个甚至数百个节点。 是可以的，但是如果要实现几万个节点的共识网络，在功能上是不可能的。

对于私有链来说，应用场景更可控，所以可以选择的共识算法范围也比较广，比如可以使用Raft、Paxos。