什么是共识？（理论篇）

共识算法，可以理解为是为了实现分布式一致性协议而产生的一系列流程与规则。当分布在不同地域的节点都按照这套规则进行协商交互之后，最终总能就某个/某些问题得到一致的决策，从而实现分布式系统中不同节点的一致性。

起源

早期的计算机应用大都是单体架构，即单个处理器就能够承接所有的计算任务、读写任务等，那时候的计算机只需要负责将自己收到的任务按序执行、提交并返回即可，因此在那个时期，研究人员的主要研究内容是如何将单核处理器的性能优化到极致。然而，随着互联网的出现与发展，数据量呈现爆发式增长，单靠一个处理器已经无法满足常规的业务需求，分布式系统架构横空出世。

分布式系统简单来说就是一系列处理器/节点通过消息交互的形式协同处理一系列的事务，从而达到横向扩展性能、提升灾备属性的效果。为了能够达到横向扩展，需要所有节点共享相同的数据副本，自然而然地也就解决了单点故障的问题。分布式系统极大提升了单体架构的性能上限，但也不可避免地引入了分布式一致性问题。分布式一致性问题指的是：

在分布式系统中，当某些节点出现异常时，如何保证整个系统对外的表现仍然一致。

这里需要关注 3 个词语，即“某些”、“异常”以及“一致”。

• 一致：分布式一致性大致分为强一致性、弱一致性、最终一致性，由于各个分类涉及的细节较多，本文不做过多赘述。

• 异常：在分布式系统中，不同节点通常分布在不同的地域，因此同一时间不同节点的状态可能不受控。节点可能出现一些良性错误，例如宕机、网络延迟/断开等；也可能出现一些恶意错误，例如伪造消息、向不同节点发送不同的投票等。良性错误通常是由于机器/网络故障导致的节点暂时不在线，通过人为介入是可以恢复到宕机之前的状态的，因此不会对整个系统的安全性造成威胁；而恶意错误也就是我们通常所说的拜占庭错误，则可能由于某些节点的恶意攻击导致整个集群出现不可预估的崩溃。

• 某些：为了应对上述两种不同类型的错误（非拜占庭错误与拜占庭错误），我们需要设计不同的协议来解决/容忍有限量的错误。通常来说，非拜占庭容错的共识算法能够容忍不超过 1/2 的节点出现良性错误；拜占庭容错的共识算法能够容忍不超过 1/3 的节点出现良性/恶意错误。

分布式系统的一致性问题早在上世纪七八十年代就开始了研究，奠定了非常扎实的理论基础，不过在后来相当长的一段时间内理论研究几乎停滞。直到近年来，区块链系统的出现又促进了分布式一致性问题研究的蓬勃发展。本文将分别介绍分布式领域内一些非常重要的模型假设/定理/理论等。随后，将从传统分布式一致性算法与典型区块链共识算法的角度剖析共识算法的发展历程。

网络模型

分布式系统建立在许多通过网络连接或者其他方式进行消息通信的节点之上，而网络通信的不确定性会限制共识算法的设计。通信模型定义了不同消息延迟对于分布式系统的限制能力。总的来说，一共存在三种类型的通信模型，分别是同步模型、异步模型与部分同步模型。

（1） 同步模型（Synchronous model）

在同步模型中，所有节点之间的消息通信都存在一个已知的延迟上界，并且不同节点处理事务的相对速度差值有一个已知上界。同步模型是一个非常理想的通信模型，在现实生活中几乎不可见，但是在分布式系统的理论研究中却发挥着及其重要的作用，许多早期的分布式一致性算法都是在同步网络假设下设计的。

（2） 异步模型（Asynchronous model）

在异步模型中，上述的假设上界都不存在，因此异步模型比较符合现实的互联网环境。异步与同步相比，是一种更通用的情况。一个适用于异步系统的算法，也能被用于同步系统，但是反过来并不成立。在异步模型中设计一个正确的共识算法已经被证明是不可能的。

（3） 部分同步模型（Partial Synchronous model）

部分同步模型是界于同步模型与异步模型之间的一种通信模型，于 1988 年由 Dwork, Lynch 等人在论文[1]中提出。该模型中假设存在一个全局稳定时钟 GST（Global Stabilization Time），在 GST 之前整个系统可能处于异步状态，但是在 GST 之后，整个系统可以恢复到同步状态。部分同步模型的时序假设比较贴合现实世界中对共识算法的需求，即共识总是可以在同步状态下完成，然而一旦网络出现问题，共识可能会进入一段时间的阻塞，直至网络恢复正常。

拜占庭将军问题

1982 年，Leslie Lamport、Robert Shostak 和 Marshall Pease 三位科学家发表了一篇论文[2]，提出了著名的拜占庭将军问题。拜占庭将军问题首次假设了分布式系统中存在恶意节点的情况，并给出了在同步网络模型下的解法（虽然在此之前，同步模型与异步模型还没有明确的定义）。在拜占庭将军问题中，节点不止会出现宕机或者断网等良性错误，还有可能出现任意情况的拜占庭错误，例如硬件或者软件故障导致的节点不按程序逻辑运行，甚至于节点程序被人恶意操纵等等。总之，拜占庭错误更加贴近于实际生活中面临的故障模型，同时它也是分布式系统中最难解决的故障模型。

根据是否容忍拜占庭错误，我们可以将共识算法分为两类：

• CFT 类共识算法：仅能够容忍宕机、网络延迟/断开等良性错误的共识算法

• BFT 类共识算法：除了能够容忍上述错误，还能够容忍任意类型的恶意攻击的共识算法

FLP 不可能定理

1985 年，Fischer、Lynch 和 Patterson 三位科学家发表了论文[3]，提出了著名的 FLP 不可能定理。作为分布式系统领域内最重要的定理之一，它给出了一个非常重要结论：在一个异步通信网络中，只要存在一个故障节点，那么就不存在一种完美的共识算法可以正确的终止。

FLP 的出现，从理论的角度告诉人们可以不用再想方设法地去设计一个异步网络中始终能够达成一致的共识算法。因此，后续的共识算法设计中通常会在某些方面做出妥协，例如网络假设不再是异步模型而是选择部分同步模型，即允许存在一定时间的异步网络状态，该期间无法达成共识，但是只要网络恢复到同步状态，就可以立即完成共识，这样虽然对于系统的活性有一定的影响，但是只要能够保证系统的安全性，依然是一个可接受的共识算法。

CAP 理论

2000 年，加州大学伯克利分校的 Eric Brewer 教授在 ACM PODC 会议上提出 CAP 猜想。2 年后，麻省理工学院的 Seth Gilbert 和 Nancy Lynch 从理论上证明了 CAP。此后，CAP 理论正式成为分布式领域的公认定理：一个分布式系统最多只能同时满足如下三种特性中的两种：

• 一致性（Consistency）

• 可用性（Availability）

• 分区容错性（Partition tolerance）

在分布式系统尤其是区块链系统中，营造一个高可用甚至永远不会出错的网络环境需要付出高昂的代价。因此一般来说，区块链系统必须满足分区容错性这一特质。那么对于区块链系统来说，就只能在一致性与可用性之间做出权衡与让步。例如大型公链系统中有成千上万的节点运行在世界的各个角落中，因此几乎不可能设计出一个强一致的共识算法保证所有节点同时对外提供一致的读写服务。PoW 算法是通过牺牲强一致性，退而求其次地满足最终一致性、可用性与分区容错性。尽管 PoW 网络随时有分叉的可能性，即已经上链的区块有可能被回退掉，但是随着时间的推移，靠前的区块得到越来越多的确认，那么其被回退的可能性就越来越低，以至于达到一种几乎不可能被回退的最终一致性。在此期间，每一个节点都可以正常的对外提供读写服务。

总结

通过前人的研究，我们已经能够大致理解了一个共识算法能够正确运转的条件：即在一个传统的分布式系统中，一个实用的共识算法需要能够安全地运行在部分同步网络模型中。其实，早期分布式一致性算法的研究大都集中在非拜占庭的部分同步网络模型环境下，例如经典的 Paxos、ViewStamped Replication、ZAB 等。直到 PBFT 算法的提出，才出现了第一个可实用的拜占庭容错共识算法原型。上述这些算法本身已经能够非常好地解决一致性的问题，因此在相当长的一段时间内，都没有新型共识算法被提出。但是近年来，随着人们对于共识算法可理解性、易实现性、吞吐量等要求的不断提高，涌现出了非常多优秀的共识算法，例如 CFT 类的 RAFT、BFT 类的 HotStuff 等。

在区块链系统或者说比特币出现之前，已经有非常多的应用从单数据中心单数据库模式转变成了多地多中心的分布式数据库模式，然而此类的应用通常还是部署在同一个机构/公司内部服务器上。与此不同的是，在区块链这样一个承载着价值传输的分布式系统上，节点可能分布在全球各地，并且不受任何单一的机构/组织控制，因此区块链共识算法必须要考虑到恶意节点的存在，保证区块链上的价值不会被恶意节点操纵，即区块链共识算法是需要容忍拜占庭错误的。而为了能够应对拜占庭攻击，不同的区块链系统走上了不同的道路。

在公有链中，常见的选择是通过工作量证明算法（PoW）来防止拜占庭攻击，由于每次竞争出块权都需要解决一个非常复杂的数学难题，因此在这第一步就已经阻挡了绝大多数的攻击者；其次，每一个新构造出来的区块都必须经过其他矿工节点的验证，因此不可能在区块中包含非法/重复的交易；而如果想要伪造一条包含非法交易的链，除非攻击者掌握全世界范围内超过 50%的算力，这显然是不可能的，即便存在这样一条链，一旦被发现有非法交易存在必然会导致该链信誉的下降从而导致巨量的损失，这对于攻击者来说显然也是不合算的。最终，上述的规则会引导所有尝试出块的节点都到一条“正确的最长链”上竞争，因为这样做才是利益最大化的选择。

在联盟链中，常见的选择是通过理论完备的 BFT 共识算法来防止拜占庭攻击。由于联盟链的共识节点通常由参与方机构管理，因此准入门槛本身就比较高；其次，联盟链中的共识缺乏经济激励，因此需要通过更强的理论来进行约束。然而完全按照一个共识算法的原型来实现的话，依旧会存在一些问题。例如，传统 PBFT 算法中主节点是固定的，如果能够控制主节点，即便不让它打包非法交易，也可以控制它偏向性地打包某些账户的交易，从而导致其他账户的交易被阻塞而无法上链。因此，在应用 BFT 共识算法的过程中，还需要为区块链特性加上一些特殊的功能，例如选择不可预测的主节点，为节点加上信誉值从而通过信誉值来选择主节点等。

敬请期待下篇《什么是共识（生活篇）》

对于共识算法有兴趣的小伙伴，可以添加小助手桔子（18458407117）加入技术交流群，欢迎您和我们共享观点，共论区块链的无限未来～

作者简介

端豪

趣链科技基础平台部共识算法研究小组

参考文献

[1] Dwork C, Lynch N, Stockmeyer L. Consensus in the presence of partial synchrony[J]. Journal of the ACM (JACM), 1988, 35(2): 288-323.

[2] Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.

[3] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process[J]. Journal of the ACM (JACM), 1985, 32(2): 374-382.