引言：美东时间2月14日，也就是情人节那天，美国众议院召开第二次区块链听证会，主题为“超越比特币：区块链技术新兴应用”，有人认为这意味着关于区块链技术大规模应用的“美国共识”正在形成，包括拥抱技术、不要封杀、区块链必须开放等等，这是超越于区块链技术层面的“共识机制”。那今天，我们就从区块链技术层面的共识算法说起，这可谓是区块链的灵魂。
区块链系统首先是分布式系统，分布式领域最为基础的问题就是一致性问题。
所谓一致性，是指对于分布式系统中的多个节点，给定一系列操作，在约定协议的保障下，它们对处理结果达成认同。分布式环境里要求多点数据是一致的，即数据要完整、要同步。通常数据库中存在的“脏数据”就属于数据缺乏一致性的表现，而在分布式系统中常出现的不一致情况是读写数据时缺乏一致性，比如一个节点写操作之后没有对与其有数据冗余的另一个节点进行数据更新，这样读取另一个节点时就会出现数据不一致问题。有限状态机是有限个状态以及在这些状态之间的转移和动作等行为的数学模型，其特点是状态总数有限，任一时刻只处于一种状态中，某种条件下，会从一种状态转变到另一种状态。从有限状态机的角度来看一致性，也即各个节点构成相同的有限状态机，给定相同的初始状态和输入序列，保证在处理过程中每个环节的结果都相同。
如果分布式系统能够实现一致性，对外就可以呈现出一个完美的、可扩展的“虚拟节点”，这也是分布式系统希望实现的最终目标。 区块链系统由非常多的分散节点组成，对于加入区块链的新内容，大多数节点必须达成一致才能成功写入，这种共识机制保证了网络安全，让篡改内容变得非常困难。
一致性与共识之间是结果和手段的关系
人们常常把一致性与共识混为一谈，实际上一致性描述的是结果状态，共识则是一种手段。一致性一般是指分布式系统中多个副本对外呈现的数据的状态，共识则描述了分布式系统中多个节点之间，对某个状态达成一致结果的过程。 要保障系统满足不同程度的一致性，往往需要共识算法来达成。共识算法解决的是对某个提案达成一致意见的过程，这里的提案可以指任何能达成一致的信息。
FLP不可能原理是共识算法的理论界限
1985年，Fischer、Lynch和Patterson提出了FLP不可能原理，它是分布式领域里的测不准原理，指的是在网络可靠，但允许节点失效的最小化异步模型中，不存在一个可以解决一致性问题的确定性共识算法。这里的异步与同步相对，指的是系统中各节点可能存在较大的时钟差异，同时消息传输时间和各节点处理消息的时间可能都是任意长的，这样就无法判断某个消息迟迟未被响应到底是哪里出了问题。
利用CAP之不可能三角用一方面的妥协保证另一方面
2000年7月，加州大学伯克利分校的Eric Brewer提出CAP猜想，2年后麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP，之后其正式成为分布式计算领域的公认定理。分布式计算系统不可能同时确保以下三个特性：C（一致性）、A（可用性）和P（分区容错性）。区块链系统中使用共识算法优先保证整个系统的容错能力。
拜占庭将军问题是允许少数节点作恶时达成一致性的问题
1982年，Leslie Lamport等提出一个用来解释一致性问题的虚构模型——拜占庭将军问题，这是一个在不可靠的环境中建立一个可靠系统的问题。拜占庭是古代东罗马帝国的首都，想要进攻一个强大的敌国，为此派出了10支军队去包围它。敌国的军事力量足以抵御5支拜占庭军队的同时袭击。因此任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。由于地域广大，守卫边境的将军们需要通过信使来传递消息，达成进攻意向及进攻时间的共识。但将军并非都是忠诚的，其中可能有叛徒存在，叛徒可能擅自变更进攻意向或者进攻时间，故意干扰共识的达成。在这种情况下，如何保证忠诚的将军们能达成行动上的一致性，赢取战斗？这就是拜占庭将军问题。 从1982年到1999年，都无人能够真正创造一个可以解决拜占庭将军问题的系统。
共识算法分CFT和BFT两大类，BFT又分为确定性算法和概率算法
在传统的数据库和分布式系统领域，对数据一致性的研究已经非常多，但在区块链出现之前，很少有系统有上万个节点要同步，同时在传统的分布式网络中，各个节点也不会因为贪图利益故意伪造信息，很多情况下是由于网络的原因而掉线或发送错误消息。因此，可根据要解决的问题是普通错误还是拜占庭将军问题，将共识算法分为CFT（Crash Fault Tolerance）和BFT（Byzantine Fault Tolerance），CFT已有一些经典的解决算法，包括Paxos、Raft及其变种等，其中Paxos算法1990年由Leslie Lamport提出，被广泛应用于Google的Chubby Lock中，而Chubby Lock后面则被应用于Google的核心设计Bigtable中。而BFT则是在区块链系统中常用的共识算法，分为PBFT（Practical Byzantine Fault Tolerance）为代表的确定性系列算法和工作量证明（PoW）为代表的概率算法。对于确定性算法，一旦达成对某个结果的共识就不可逆转，即共识是最终结果；而对于概率性算法，共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，成为事实上的最终结果。
确定性算法PBFT降低了算法复杂度，适合联盟链
1999年，Castro和Liskov在论文中提出PBFT算法，解决了以往拜占庭问题的解决方案复杂度过高的缺点，将算法复杂度从指数级降到多项式级。PBFT算法中，如果有超过2/3的节点正常，整个系统就能正常工作，其特点有三，一是共识各节点由业务的参与方或监管方组成，安全性与稳定性由业务相关方保证。二是共识的时延基本达到商用实时处理的要求。三是共识效率高，可满足高频交易量的需求。 非常适合联盟链的应用场景。但其前提仍是依靠法定多数，一个节点一票，少数服从多数，这在开放生态的公有链中，存在很大的问题。
概率算法PoW通过引入激励机制和随机性提供解决新思路
对PoW最简单的理解就是按劳分配、多劳多得，其协议如下，首先向所有节点广播新的交易，每个节点把收到的交易放进区块中，每一轮中通过解出数学题找到随机数的方式决定胜出的节点，由它广播其所保有的区块，其他节点在验证区块中所有交易正确无误后接受该区块，其他节点将该区块的哈希值放入下一个它们创建的区块中，表示承认这个区块的正确性。节点们总是以最长的链为合法的链，并努力去延长这条链。
可以说区块链系统是技术和人性的结合，引入激励机制让节点维护一致性。为了更容易理解，可以参考我们熟悉的市场经济，市场经济是一个典型的去中心化系统，参与市场经济的每个主体都在遵守商业规则的基础上，按照实现自己利益最大化的原则行事，同时在客观上推动了整个市场的繁荣，这就是凯恩斯所说的“看不见的手”；而PoW则构造了一个以竞争-记账-奖励为核心的正向循环的经济系统，解决了去中心化记账问题，每个节点只需根据自身利益行事，出于“自私”（得到奖励）的目的进行记账权的竞争，最终造就了保护系统安全的庞大算力。在拜占庭问题中，决定下一步的行动计划，不能像在中心化系统中，由权威大的做决定，因此引入了随机性，即争夺决定权，谁的计算力强，谁就可以做决定（记账）。此外，拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案，因为提案成本很低；并且难以完成最终一致性的确认，极易被干扰。PoW算法对此做了两点改进：一是增加提案成本，限制一段时间内网络中的提案数；二是放宽对最终一致性确认的需求，约定好大家都确认并沿着已知的最长链进行拓展。系统的最终确认是概率意义上的。对于公有链来说，PoW应该是最优算法。
更进一步，想要改变一个系统，上策就是寻求形成共识，构建利益共同体
共识机制在区块链中实现了更有弹性的协作方式。最近流行的Token经济学其核心也就是形成利益共同体，合作共赢。它可以解决市场交易成本问题，其设计的核心理念，是把原来系统中分散的交易成本集约起来，用技术手段把收益分到系统中每个参与者，使系统整体摩擦力不断下降，从而使Token内在价值不断上升。通过设计合理的Token机制，调动参与者的积极性，从而形成良好的生态组织，不论其服务于哪个领域，最终一起构建了区块链的生命体（就像阿西莫夫笔下的盖娅一样），本质上是协同进化，构建更强大的利益共同体。再往远了说，对于人类社会这个更大的组织系统来说也是一样，有句话叫“团结就是力量”，真正的团结应该是在某种共识的基础上，一个系统里所有人各自的小目标和系统的大目标达成了一致。比如说，中国共产党在抗战时团结一切力量，就是通过形成抗击日本侵略者这个共识；而习总书记提出的共同构建人类命运共同体，也是一个更高层次的共识，最符合全球人类的愿望和根本利益。
来源：公众号（智能之河）
