共计 4629 个字符，预计需要花费 12 分钟才能阅读完成。
共识算法，能够了解为是为了实现分布式一致性协定而产生的一系列流程与规定。当散布在不同地区的节点都依照这套规定进行协商交互之后，最终总能就某个 / 某些问题失去统一的决策，从而实现分布式系统中不同节点的一致性。
起源
晚期的计算机利用大都是单体架构，即单个处理器就可能承接所有的计算工作、读写工作等，那时候的计算机只须要负责将本人收到的工作按序执行、提交并返回即可，因而在那个期间，钻研人员的次要钻研内容是如何将单核处理器的性能优化到极致。然而，随着互联网的呈现与倒退，数据量出现爆发式增长，单靠一个处理器曾经无奈满足惯例的业务需要，分布式系统架构横空出世。
分布式系统简略来说就是一系列处理器 / 节点通过音讯交互的模式协同解决一系列的事务，从而达到横向扩大性能、晋升灾备属性的成果。为了可能达到横向扩大，须要所有节点共享雷同的数据正本，自然而然地也就解决了单点故障的问题。分布式系统极大晋升了单体架构的性能下限，但也不可避免地引入了分布式一致性问题。分布式一致性问题指的是：
在分布式系统中，当某些节点出现异常时，如何保障整个零碎对外的体现依然统一。
这里须要关注 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.
