深入区块链技术（三）｜共识算法与分布式共识算法

在上一篇文章中，我们介绍了区块链的第一个核心技术P2P网络。 今天我们再深入一点，简单介绍一下共识算法和分布式共识算法。

区块链首先是一个分布式系统，那么我们先从这个概念说起。 为了便于理解，我们可以想象如下场景：

假设全国有11个村，其中一个村每年过年都要办庙会，其他村的人都要来参加。

因为举办庙会可以带来巨大的经济效益，所以举办庙会的权利需要争夺。 其中A、B村居民多，经济实力强，大家一致同意，通过投票结果从这两个村中选出举办庙会的权利。

由于村与村之间距离较远，信息只能通过信鸽传递，信鸽无法覆盖所有村，需要部分村作为中转站。

为了让自己支持的村获得主办权，各个村都会采取各种手段，比如延迟发送结果、篡改其他人的投票结果、假装自己没有收到结果等等。

这是一个典型的分布式系统，可以看作是区块链系统的缩小版。 那么，这个分布式系统会遇到哪些问题呢？

一、分布式系统面临的问题

显然比特币的共识算法是，这个系统面临的第一个问题就是必须在有限的时间内达成共识，即谁拥有最终的主办权。 我们称之为可终止性。 同时，必须保证收到的选票是这11个村给的，不能来自其他渠道。 这就是合法性。 最后，最重要也是最基本的一点是，每个村发给其他村的信息必须是一致的，即如果我支持A，那么其他10个村都应该收到“我支持A”，而不是5个村认为我支持 A 而其他 5 个村庄认为我支持 B。我们称之为一致性。

哪些情况会导致一致性被破坏？

1. 非恶意信息传递错误。 例如，信鸽在送信的过程中中途死亡，信鸽迷路，寄错目的地，信件受潮，信息模糊，收件人不在家，信鸽飞得很慢，以及消息被延迟等等。对应到分布式系统，面临的问题有消息丢包，网络拥塞，消息延迟，消息内容失真，节点下线等等。

2、人为恶意篡改消息。 比如故意投不同村不一致的票比特币的共识算法是，中继村篡改发送的选票等。对应一个分布式系统，消息被伪造，系统遇到中间人攻击等。

这种人为恶意篡改消息的过程在系统中也称为拜占庭错误。 如果系统能够容忍这种错误并且仍然达成最终共识，我们称这样的系统为拜占庭容错系统。

对于非恶意的信息传输错误，已经有很多更好的解决方案，不在本文讨论范围之内。 我们要关注的是如何解决人为恶意篡改消息的问题，这就引出了我们的共识算法和分布式共识算法。

2.关于分布式系统的定理

在介绍具体算法之前，我们先介绍一下两个分布式系统的定理，做个铺垫。

FLP 不可能定理：即使网络通信是完全可靠的，也不存在可以解决所有拜占庭错误的通用共识算法。

CAP定理：在设计分布式系统的过程中，一致性、可用性、分区容忍度三点不能同时满足。 只能选择满足第二个，削弱剩下的一个。

从CAP定理，我们可以延伸出两个概念：严格一致性和最终一致性。 前者是指系统在约定时间内始终保持一致性的状态； 后者意味着系统不需要一直保持一致性，而只需要在约定的时间结束时达到一致性。

在工程实现中，严格一致性很难做到，即使做到了，性能也比较低。 因此，人们通常会在时间上妥协（即削弱一致性）。 在区块链中，设置了更长的时间来让系统达到最终的一致性。

这也符合我们对比特币和以太坊的观察。 在比特币和以太坊中，区块链侧重于高可用性和分区容错性，弱化了一致性，每秒可以处理的交易数比较少。

同样，在 EOS 中，由于记账节点数量减少到 21 个，分区容忍度不再是需要满足的指标。 因此，EOS 提高了一致性时间约束，即节点每秒可以处理的交易数量大幅增加。

3. 共识算法和分布式共识算法

共识算法其实就是分布式系统的共识过程的算法。 为了区分区块链中常用的算法和经典的分布式共识算法，我们使用不同的名称。 即共识算法是指区块链中常用的算法，后者是指经典的共识算法。

经典分布式共识算法

经典的分布式共识算法可以分为两类。 一类不提供拜占庭容错，常见的有Raft算法和Paxos算法。

Raft 算法主要依靠强领导者来实现一致性。 使用该算法的系统的吞吐量基本上就是leader的吞吐量。 该系统的弱点在于过于中心化，难以抵御恶意的单点攻击。 . Paxos算法比较复杂，可以针对不同的场景提供不同类型的共识算法，包括强领导者类型、弱领导者类型等。 关于这些算法不是本文的重点。

另一种类型提供拜占庭容错，通常是实用拜占庭容错 (PBFT)。 PBFT 的本质是一个有限状态机，需要所有节点共同维护一个状态，并采取一致的动作。 PBFT更适合联盟链等对性能要求较高的场景。 HyperLedger 中的 Fabric 框架默认使用 PBFT 的修改版本。

区块链共识算法

区块链采用的算法更贴合实际情况。 主要思想是大大增加攻击者的攻击成本，使攻击收益远小于攻击成本，从经济角度避免攻击情况。

区块链中的共识算法是目前工业上成熟的PoW（Proof of Work），另外两种比较成熟的是PoS（Proof of Stake）和DPoS（Proxy Proof of Stake）。 此外，还有一些变体算法和某些货币单独使用的算法，如PoC（概念证明）、PoE（存在证明）和Ripple共识算法。

在使用PoW算法的情况下，系统的容错率为50%，即允许50%的节点恶意作弊。 在 PBFT 中，容错率只有 33%。 至于其他PoX算法，或多或少延续了PoW的设计理念。 关于PoW、PoS和DPoS算法，后面会单独一篇文章介绍。

总结

今天我们简单介绍了分布式系统面临的三大问题，分布式系统中的两个重要定理，以及经典的分布式共识算法和区块链常用的共识算法。 来源被整理出来。