共计 5053 个字符，预计需要花费 13 分钟才能阅读完成。
—— Part1 共识的分类 ——
从晚期的分布式一致性算法的迟缓倒退到现如今区块链共识的百花齐放，共识算法的倒退曾经走过了四十年左右的时光。不同的共识算法的侧重点不同，因而它们所面临的问题、环境也不一样。本文将从如下几个不同角度对共识算法进行分类：
▲容错类型
依据是否容忍拜占庭谬误，能够将共识算法分为两类。
1）拜占庭容错共识算法：PBFT、PoW、PoS、DPoS
2）非拜占庭容错共识算法：Paxos、Raft
是否容忍拜占庭标记着该算法是否可能利用到低信赖的网络当中。通常来说，私有链环境中必须应用拜占庭容错算法，而联盟链中能够依据联盟参与方之间的信赖水平进行抉择。
▲算法确定性
依据算法的确定性，能够将共识算法分为两类。
1）确定性共识算法：Paxos、Raft、PBFT
2）概率性共识算法：PoW、局部 PoS
确定性共识指的是共识决策一旦达成，就不存在回退的可能性，这一类通常是传统的分布式一致性算法及其改良版本。而概率性指的是曾经达成的共识决策在将来有肯定的概率会被回退，尽管这个概率随着工夫的推移会趋于为 0，这一类通常是利用在私有链上的区块链共识算法。
▲选主策略
依据选主的策略，能够将共识算法分为两类。
1）选举类共识算法：Raft、PBFT
2）证实类共识算法：PoW、PoS
选举类共识指的是通过投票抉择出块节点，同一个节点能够间断多轮作为出块节点存在，这一类通常是传统的分布式一致性算法及其改良版本。证实类共识算法指的是出块节点须要通过某种形式证实本人具备某种能力，从而取得出块权，这一类的共识算法通常每一轮的出块节点都不雷同，从而保障了出块权的公平性，通常利用在私有链上。
—— Part2 非拜占庭容错共识算法 ——
Paxos
Paxos 是第一个异步网络模型下可能保障正确性且容错的共识算法。在此之前，FLP 明确指出在异步网络模型中，只有存在节点故障，就不可能存在一个可终止的共识算法。因而 Paxos 也做出了肯定的就义：Paxos 就义了肯定的活性从而保障了零碎的安全性，即在零碎处于异步状态时暂停共识的推动，只有有半数以上的节点复原至同步状态之后，就能够推动共识，实现终止。
在 Paxos 中，会存在一个或者多个节点同时想要竞选成为协调者（也叫做提案者 Proposer），而每一轮共识最终只会选出一个 Proposer 进行最终提案值的抉择。Proposer 提出一个决策值，并收集其余参与者节点（也叫做接受者 Acceptor）的投票。最终，Proposer 会发表选定的最终决策值。如果可能达成一个最终决策的话，该决策值会被传递到对此感兴趣的节点（也叫做学习者 Learner）中。能够看出，Paxos 是一个保障了公平性的算法，即所有节点都能够竞选成为 Proposer，没有哪个节点领有非凡的权力。
图 1.Basic Paxos 共识流程
Paxos 在肯定水平上给出了一种异步网络下分布式一致性问题的解决范式，然而它自身的算法过于艰涩难懂，以至于 Lamport 自己也在 Paxos 发表之后又写了一篇论文 [1] 来从新解释 Paxos 的流程。同时，一个 Paxos 算法的正确实现也被证实是十分有难度的挑战，有趣味的读者也能够浏览 Google 的实际论文 [2] 来了解实现过程中的一些衡量与考量。
Raft
Paxos 诚然是一个十分有影响力的共识算法，能够说奠定了分布式一致性算法的根底，然而因为其难以了解以及实现难度十分之大，想要实现一个残缺的 Paxos 算法十分的艰难。因而，呈现了十分多的 Paxos 变体，其中最驰名的当属 Raft 共识算法。
Raft 是一种用来治理日志复制的一致性算法，旨在易于了解。它具备了 Paxos 的容错性和性能，不同之处在于它将一致性问题合成为绝对独立的三子问题，别离是领导选取（leader election），日志复制（log replication）和安全性（safety）。这使得 Raft 更好了解并且更容易利用到理论零碎的建设中。
在 Raft 中，每一个节点肯定会处于以下三种状态中的一个：Leader(主节点)、Candidate（候选节点）、Follower（从节点）。在失常状况下，只有一个节点是 Leader，剩下的节点是 Follower。Leader 负责解决所有来自客户端的申请（如果一个客户端与 Follower 进行通信，Follower 会将信息转发给 Leader），生成日志数据（对应在区块链中即负责打包）并播送给 Follower 节点。Follower 是被动的：他们不会被动发送任何申请，只能单向接管从 Leader 发来的日志数据。Candidate 是在选举下一任 Leader 的过程中呈现的过渡状态，任何一个节点在发现主节点故障之后都能够成为 Candidate 并竞选成为 Leader。
Raft 算法将工夫划分成为任意不同长度的 term（任期）。任期用间断的数字进行示意。每一个任期的开始都是一次选举。如果一个 Candidate 博得了选举，它就会在该任期的剩余时间负责 Leader。在某些状况下，选票会被瓜分，有可能没有选出 Leader，那么，另一个任期将会开始，并且立即开始下一次选举。
每一台服务器都存储着一个数字作为以后任期的编号，这个数字枯燥递增。当节点之间进行通信时，会互相交换以后任期号，若一个节点的以后任期号比其它节点的小，则会更新为较大的任期号。如果一个 Candidate 或者 Leader 意识到它的任期号过期了，就会立即转换为 Follower 状态。当一个节点收到过期任期号的申请，就会间接回绝这次申请。
图 2.Raft 共识流程
总结
Paxos 和 Raft 都是故障容错（Crash Fault Tolerance）共识，是非拜占庭问题的容错技术。非拜占庭是指分布式的零碎中存在故障 (crash fault)，但不存在歹意(corrupt) 节点的场景 (即可能音讯失落或反复，但无谬误音讯) 下的共识达成问题，是分布式共识畛域最为常见的问题。相比拟于 Paxos，Raft 更为简洁，同时能够保障等同的容错能力和性能。
—— Part3 概率性共识算法 ——
PoW
工作量证实（Proof of Work，PoW）最早在 1993 年由 Cynthia Dwork 与 Moni Naor 在学术论文 [3] 中提及，并于同年由 Markus Jakobsson 与 Ari Juels 正式提出了“工作量证实”这个概念[4]。起初，PoW 次要用于避免垃圾邮件的产生。2008 年，PoW 作为共识算法利用在比特币零碎中。PoW 有以下 3 个根本属性：
1）数学难题：PoW 共识算法设计了一个数学难题（Mathematical Puzzle），要求节点在生成新区块之前，须要耗费肯定的计算资源能力取得难题的解，从而将区块播送到网络，并且其余节点能够轻易验证这个解的有效性。
2）哈希算法：哈希算法（Hash Algorithm）是一种可能把任意长度的输出变换成固定长度的输入的算法，可被记为 y = hash(x)，不同的输出 x 失去的输入 y 各不相同。除此之外，在已知 x 时能够疾速计算失去 y，然而在已知 y 的状况下，通常只能通过穷举法能力逆推出 x。因为哈希算法具备正向疾速、逆向艰难的个性，常应用哈希算法来设计 PoW 的数学难题。
3）生成区块：在一轮区块生成中，零碎通过对输入值设定条件来调整数学问题的难度值，节点在胜利解出问题并通过验证上链后，将会取得相应的处分。
在生成新的区块之前，PoW 会预设目标值，要求出块节点计算出的哈希值小于该目标值，以此来示意 PoW 的难度。为了生成区块并取得处分，出块节点首先收集一组交易打包成一个区块，并开始尝试解决数学问题进行出块。
在此期间，出块节点须要生成随机数，同以后区块数据与前一个区块的哈希进行多轮哈希运算，计算以后区块的哈希值：
直到以后区块哈希满足条件：
此时的 nonce 即为本次数学问题的答案，出块节点将以后区块的哈希、nonce 值、前一个区块的哈希作为区块头部数据退出以后区块，如图 3 所示。而后将该区块播送到区块链网络中，期待验证通过后，出块节点就能够取到相应的处分。
图 3.PoW 区块构造示意
PoS
后面提到的工作量证实共识算法，就是通过算力来抢夺“领导者”的资格，然而工作量证实过程中的大量资源节约，导致其很难被更大规模的利用承受。对此，有人开始尝试间接应用“股权（Stake）”作为规范进行“领导者”资格的竞选，并随之产生了权利证实（Proof of Stake，PoS）共识算法。
PoS 的思维来源于社会：一个人领有的股份量越多，其取得的股息和分成就会越高。如果区块链零碎也采纳这种办法进行保护，不须要过多的资源耗费，也可能使得区块链资产有天然的通胀。节点通过投入一定量的通证参加共识，依据通证持有状况取得打包新区块的权力并取得处分。目前，以太坊也有转向 PoS 的以太坊 2.0 打算。
为了形容通证持有状况，PoS 共识算法引入了“币龄”的概念。币龄（Coin-age）示意节点持有局部通证的时长，当节点将通证作为“股份”投入后，这部分通证就开始积攒币龄，币龄的计算形式如下：
在应用了这部分通证后，无论是用来进行区块生成或者简略的交易，这部分通证对应的币龄将被销毁。在最后的 PoS 共识算法中，币龄是进行评判的重要规范，节点在区块生成时所应用的币龄越高就越容易产生区块，这能够在肯定水平上制约短期投机行为。
PoS 共识算法在进行区块生成时，将同时思考币龄与哈希运算难度，使得节点只须要耗费很少的计算资源就能够实现区块生成。
DPoS
委托权利证实（Delegated Proof of Stake，DPoS）共识算法 [5] 中，选举人通过选举产生代表，由代表进行间接的区块产生，选举人通过选举代表人间接行使竞争出块的权力。委托权利证实共识算法，实际上就是通过一系列提拔规定对候选人进行制约，并制订一套投票规定。一般参与者通过投票的形式从候选者中提拔出委托人，并由委托人进行出块，不满足要求的委托人将会被勾销权限，并从新选举产生新的委托人。
DPoS 保留了肯定的中心化个性，因而可能保障高效率的交易吞吐，速率能够比肩常见的中心化机构，例如 Visa、Mastercard 等。在该算法中，去中心化的个性次要体现在对于生成区块的权力可控。即股东通过投票，抉择本人信赖的代表节点，并由代表节点进行区块链数据的保护。
—— Part4 总结 ——
上述提到的共识算法大多用于公链场景，比方比特币，以太坊等，因为公链场景下节点规模宏大，因而较难采纳确定性的分布式一致性算法。PoW 通过工作量证实的形式来达到较高的安全性以及去中心化水平，相较于 PoW，PoS 就义了肯定的安全性来升高能源消耗，而 DPoS 以更为激进的形式，选举出较少节点来晋升共识效率。
在企业级场景下，节点数量不会十分多，然而对于交易吞吐量以及最终确定性要求较高，因而罕用联盟链形式来进行建设，从而满足企业级需要。在理论利用场景中，因为拜占庭容错问题，常会应用 PBFT 及其变体拜占庭容错类共识算法。
对「共识专栏」感兴趣的小伙伴，增加小助手桔子（18458407117）退出技术交换群，直面大咖一对一问答～
作者简介
袁超
趣链科技根底平台部共识算法钻研小组
参考文献
[1] Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.
[2] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.
[3] Dwork C, Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992: 139-147.
[4] Jakobsson M, Juels A. Proofs of work and bread pudding protocols[M]//Secure Information Networks. Springer, Boston, MA, 1999: 258-272.
[5] Delegated Proof of Stake https://github.com/dacplaypro…
