从分布式一致性算法到区块链共识机制

2022-03-15 18:47:45

引言

分布式一致性是一个很“古典”的话题，即在分布式系统中，如何保证系统内的各个节点之间数据的一致性或能够就某个提案达成一致。这个问题想必对于很多技术同学而言并不陌生，几乎在所有的分布式系统中都会遇到，比如hdfs、mq、zookeeper、kafka、redis、elasticsearch等。然而这个问题却历久弥新，随着分布式网络的蓬勃发展与复杂化，对于该问题解法的探索也一直在进行中。

而近年来，随着区块链技术的兴起，特别是开放网络中的公有链与有权限网络中的联盟链的蓬勃发展，一致性问题再次得到关注，并从新的视角来审视该问题。

本文将从传统的分布式一致性问题说起，再次重温我们需要面对的问题挑战、已有的理论研究、以及相应的一致性算法，并简要分析这些一致性算法的适用性与局限性，以及这些传统一致性算法与崭新的区块链技术的结合。另外，将从区块链中一致性问题的全新视角“人的可信”出发，重点阐述公有链领域中的共识算法与机制。因此，本文围绕“一致性”技术问题，重点从技术视角阐述传统计算机科学中的分布式一致性算法与区块链中的共识机制的关联，以及公有链对于一致性问题的重新思考。

分布式一致性问题的挑战

要清楚理解分布式一致性，首先需要对分布式网络的特性有清晰的认识。那么分布式网络具有哪些特点呢？或者通俗理解，在分布式网络中，可能遇到哪些问题呢？

Crash Fault

故障错误（Crash Fault）很好理解，就是说分布式网络中：

节点或副本可能随时宕机、可能暂停运行但随后又恢复；
网络可能随时中断；
发送的消息可能在传递的过程中丢失，对方一直收不到；
发送的消息可能出现延迟，过了很久对方才能收到；
消息在传递的过程中可能出现乱序；
网络可能出现分化，如中美集群因通信不畅，而导致整体网络分化为中美两个子网络；

这些问题，其实就是我们在分布式环境中最常实际遇到的问题，这些问题实质上都是由于分布式系统中的物理硬件的不可靠、不稳定所带来的必然风险，比如：网络（信道）不可能是永远稳定可靠的、物理机磁盘或CPU等不可能是永远良好的。故障错误可以说是分布式系统中必须考虑并解决的最基本、最常见的一类错误。

Byzantine Fault

上文的故障错误，仍然基于一个很简单的假设：节点要么不正常工作或响应，要么能正常工作或响应，但不能口是心非、阳奉阴违、表里不一，即可以不干事、但不能干坏事。一旦网络中存在作恶节点，可能会随意篡改或伪造数据，那么一致性问题的难度就大幅增加。我们常把这类存在“捣乱者”，可能会篡改或伪造数据或响应信息的错误，称之为拜占庭错误（Byzantine Fault），而前面所说的故障类错误也称之为非拜占庭错误。

拜占庭这一称呼，源于Lamport最初的论文，可以说是分布式领域最复杂、最严格的容错模型。简而言之，n个将军准备一起进攻某个城堡，每个将军都可以选择进攻或是撤退，但所有将军必须行动一致才能成功。各个将军之间相隔很远，不能直接通讯，必须通过信使来传递消息。但是信使并不可靠，信使可能过了很久才送到消息、可能一直也没有把消息送到、甚至可能会故意篡改消息；而将军也并不可靠，里面可能存在叛徒，并不按照提案来行动。显然，这个故事中的信使用来代表分布式网络中的不可靠信道，而将军就是各个不可靠的节点。

拜占庭问题示意图（https://lisk.io/academy/blockchain-basics/how-does-blockchain-work/byzantine-fault-tolerance-explained）

应对风险—Fault Tolerance

如何在充满风险与不确定的分布式网络中，寻找到某种确定性与一致性，使得整个分布式网络输出稳定可靠的一致性结果，就是分布式一致性算法要解决的核心问题。显而易见，解决故障类错误更容易一些，通常把这类一致性算法叫做故障容错算法（Crash Fault Tolerance）或者非拜占庭容错算法。而拜占庭类错误，因为有恶意篡改的可能性存在，复杂性更高、解决难度更大，通常把解决这类问题的算法称作拜占庭容错算法（Byzantine Fault Tolerance）。

那么我们忍不住要问，两类容错算法的界限在哪里？或者说两类错误都在什么样的场景下出现？恶意篡改这种情况真的需要考虑吗？问题的答案可能取决于我们所处的网络环境与业务场景。

CFT

通常而言，如果系统处于可信的内部网络环境中，只需要考虑故障容错（CFT）可能就足够了。比如我们经常见到的公司内的分布式存储、消息队列、分布式服务等各种分布式组件，其实只需要考虑故障容错就足够了。因为公司内整个网络是封闭的，又有多重防火墙的保护，外界很难接入或攻击；各个节点是由公司统一部署的，机器或运行的软件遭到篡改的可能性极小；此时的分布式网络环境相对“单纯”，我们唯一的敌人只是：通信网络与机器硬件。我们需要考虑的是网络的延迟、不稳定，以及机器随时可能出现的宕机、故障。

BFT

而拜占庭类错误(BFT)，是把整个分布式网络放到了更大的环境中去看，除了物理硬件之外，还考虑了一些“人”的因素。毕竟，机器是不会作恶的，作恶的只有人。假如我们所处的分布式网络是较为开放的网络，比如行业内几十上百家公司组成的联盟网络；或者是完全开放的网络，比如任何人都可以随意接入到网络中；而节点机器和上面部署的软件也是由各个公司或个人自己提供和部署的，那么如果利益足够大，很可能会有人对网络中的某个节点发起DDoS攻击、故意篡改软件代码改变其执行逻辑、甚至可能故意篡改磁盘上持久化的数据。显然，我们此时面临的挑战更大了，我们除了要考虑通信网络和机器硬件的不可靠之外，还必须要考虑和应对系统中的“捣乱者”。

不可能三角

这些实践中遇到的问题，也引发了诸多计算科学家进行了非常多的理论研究。这些理论研究对于工程技术人员而言或许过于抽象繁琐，有些甚至是无趣的数学问题，但这些理论对于指导我们解决这些问题意义重大。这些理论相当于是告诉了我们这类问题解法的理论极限，以及哪些方向可以探索、哪些方向是死路一条。站在前人的肩膀上，才不至于花毕生精力去研制“永动机”。这些理论大家应该都有所了解，这里只简单回顾。

FLP impossibility

早在1985年，Fisher、Lynch、Paterson三位科学家就发表了关于分布式一致性问题的不可能定理：在完全异步的分布式网络中，故障容错问题无法被解决。（ We have shown that a natural and important problem of fault-tolerant cooperative computing cannot be solved in a totally asynchronous model of computation. ）说得更直白点：在异步网络中，不可能存在能够容忍节点故障的一致性算法，哪怕只有一个节点故障。并且这里并没有考虑拜占庭错误，而是假设网络非常稳定、所有的消息都能被正确传递、并且仅被传递一次，即便如此都不可能找到能容忍哪怕只有一个节点失效的一致性协议，可见该结论有多强。（ In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliableit delivers all messages correctly and exactly once. ）

当然了，这只是理论上的。它的意义在于告诉我们此类问题的理论极限，并不意味着此类问题在实践中也不可能被“解决”。如果我们愿意放宽限制、做出牺牲，在工程上是可以找到切实可行的解法的。

FLP不可能定理的最大适用前提是异步网络模型。何为同步、异步模型呢？

所谓异步模型，是说从一个节点到另一个节点的消息延迟是有限的，但可能是*的（finite but can be unbounded）。这就意味着如果一个节点没有收到消息，它无法判断消息到底是丢失了，还是只是延迟了。也就是说，我们无法通过超时时间来判断某个节点是否故障。
所谓同步模型，是说消息传递的延迟是有限的，且是有界的。这就意味着我们可以通过经验或采样精确估算消息的最大可能延迟，从而可以通过超时时间来确定消息是否丢失、节点是否故障。

所幸的是，我们所处于的真实的网络世界更接近同步模型，在很多场景上，我们都可以通过经验或采样确定最大超时时间。举个通俗点的例子：你给朋友快递了一本书，朋友过了3天还没收到，此时朋友很难判断到底是快递延迟了，还是快递出问题送丢了。但是如果过了一个月，朋友仍没收到书，基本就可以断定快递送丢了。而背后的推论就是基于经验或统计：通常快递都能在1-2周内送达。显然，异步模型其实是反映了节点间通讯的最差情况、极端情况，异步模型包含了同步模型，即能在异步模型上有效的一致性协议，在同步模型上也同样有效。而同步模型是对异步模型做了修正和约束，从而使得更接近真实世界，也使得在实践中一致性问题有可能得到有效解。

另外，即便是在异步网络模型下，FLP也并不意味着一致性永远无法达成，只是说无法保证在有界的时间（in bounded time）内达成。在实践上，如果放宽对bounded time的限制，仍然是有可能找到实践中的解法的。

而根据DLS的研究（http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf ），一致性算法按照网络模型可以分为三大类：

部分同步网络模型（partially synchronous model）中的一致性协议可以容忍最多1/3的任意错误。这里的部分同步模型是指网络延迟是有界的，但是我们无法提前得知。这里的容错也包含了拜占庭类错误。
异步网络模型（asynchronous model）中的确定性协议无法容忍错误。这里的异步模型即是前文所说的网络延迟是*的。该结论其实就是FLP不可能定理的含义，在完全异步网络中的确定性协议不能容忍哪怕只有一个节点的错误。
同步网络模型（synchronous model）可以达到惊人的100%容错，虽然对错误节点超过1/2时的节点行为有限制。这里的同步模型是指网络延迟一定是有界的，即小于某个已知的常数。

从另一个角度来理解，FLP实际上考虑了分布式系统的3个属性：安全(safety)、活性（liveness)、容错：

安全是说系统内各个节点达成的值是一致的、有效的。safety其实是保证系统一致性运行的最低要求，其核心是cannot do something bad，即不能干坏事、不能做错事。
活性是说系统内各个节点最终（在有限时间内）必须能够达成一致，即系统必须能够向前推进，不能永远处于达不成一致的状态。liveness其实是更高要求，意味着不能只是不干坏事，也不能一直不干事，you must do something good，即必须使得整个系统能良好运转下去。
容错是说该协议在有节点故障的情况下也必须能有效。

FLP不可能定理其实意味着在异步网络中，不可能存在同时满足这三者的分布式一致性协议。因为分布式环境中，节点故障几乎是必然的，因此容错是必须要考虑的因素，所以FLP不可能定理就意味着一致性协议在能做到容错的情况下，没办法同时做到安全性与系统活性。通常在实践中，我们可以做出部分牺牲，比如牺牲一部分安全性，意味着系统总能很快达成结论，但结论的可靠性不足；或者牺牲一部分系统活性，意味着系统达成的结论非常可靠，但可能长时间、甚至永远都在争论中，无法达成结论。所幸的是，很多时候现实世界的鲁棒性很强，使一致性协议失效的倒霉事件发生的概率也很可能极低。

FLP不可能定理示意图（https://www.slideshare.net/oryband/the-stellar-blockchain-and-the-story-of-the-federated-consensusblockchain-academy）

另外，FLP并未排除Las Vegas类随机算法，许多一致性算法采用了这种随机性来规避FLP不可能定理对于确定性异步网络的限制。此类非确定性一致性算法涉及Las Vegas规则：网络最终一定能达成一致，但是达成一致所需要的时间可能是*的。此类算法每轮共识决策都有一定的概率，并且系统在T秒内能够达成一致的概率P随着时间T的增加而指数增长并趋近于1。事实上，该方法被许多成功的一致性算法所采用，是在FLP不可能定理笼罩下的安全地带（escape hatch），后面将会讲到比特币的共识机制就是采用了这样的方法。

CAP theorem

众所周知、大名鼎鼎的CAP原理，从另一个维度，简单明了、直截了当地告诉我们：可用性、一致性与网络分区容错性这三者不可能同时实现，而只能实现任意其中的两个。( "Of three properties of shared-data systems (data consistency, system availability and tolerance to network partitions) one can only achieve two at any given time".) CAP与FLP看起来有相似之处，其实二者并不尽相同，二者是从不同的维度思考问题，另外即使是很相似的概念，内涵也并不完全一样。比如：

FLP面对的是分布式一致性问题，而CAP面对的是分布式网络中的数据同步与复制。
FLP是说在异步网络模型中，三者不可能同时实现；而CAP是说在所有场景下，三者都不可能同时实现。
FLP中的liveness强调的是一致性算法的内在属性；而CAP中的availability强调的是一致性算法对外呈现的外在属性。

理论上，只能从CAP三者中选择两者，然而，这种选择的边界并非是非此即彼的（not binary），很多时候混合考虑不同程度的各个因素，结果可能是更好的。（ The whole spectrum in between is useful; mixing different levels of Availability and Consistency usually yields a better result.）

CAP理论示意图（https://www.researchgate.net/figure/Visualization-of-CAP-theorem_fig2_282679529）

在实践中，我们通常需要根据实际业务场景做折中权衡。比如：

传统的关系型数据库如mysql等多采用ACID（atomicity, consistency, isolation and durability）理论，通过同步事务操作保证了强一致性；因节点较少（一般只有主从），可用性也比较一般；网络拓扑较为简单，而弱化了分区容错性。
NoSQL存储系统如hbase等多采用BASE（Basically Available、Soft state、Eventually consistent）理论，通过多节点多副本保证了较高的可用性；另外因节点数增多、网络环境也更复杂，也考虑了网络分区容错性；但一致性较弱，只能保证最终一致性。

ACID与BASE对比（https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf）

当然，这些并不是定论，各个系统都在各自不断的进化完善中，今天的结论明天可能就会被打破。更好的系统一定是不断探索适合自己的场景，找到更佳的平衡点。

分布式一致性算法

面对分布式环境中各种真实、复杂的问题与挑战，基于理论上的指引，各种应对现实问题的解法也被提出。我们这里不探究各类算法的实现细节与具体差异，仅做大体介绍，以便放到更大的维度，从整体上做比较。

Paxos

最大名鼎鼎的分布式一致性算法当属Lamport提出的paxos算法，虽然其复杂性也同样“臭名昭著”。Lamport开创性地提出了一种在工程实践上切实可行的、能够最大程度地保证分布式系统一致性的机制。paxos被广泛应用在诸多分布式系统中，如Chubby、Zookeeper等。在basic paxos（单一法令，即每次仅对一个值进行决策）中有两种角色：proposer可以处理客户端请求、主动提出某个议案值；acceptor被动响应proposer发出的信息、对提案进行投票、持久化存储决策过程中的值和状态。(为简化模型，可以忽略learner角色，不影响模型决策。)

如图所示，共识决策过程采用了两阶段提交：

第1阶段，广播Prepare RPC命令，即找出协议决定的最终值、阻断尚未完成的旧提案；
第2阶段，广播Accept RPC命令，即要求acceptor接受共识协商出的特定值。而multi-paxos是由多个basic paxos实例组成，可以对一系列的值进行决议。

Paxos之所以在实践中可行，其实也做了诸多假设和约束。从处理的问题上来看，Paxos仅能处理故障容错，并不难处理拜占庭错误，所以属于非拜占庭容错算法。从FLP的视角，Paxos做到了故障容错和安全性，但放弃了liveness（safe but not live）,也就是说该算法可能永远无法结束，或者说永远无法达成共识，虽然这种可能性极小。从CAP的视角，Paxos只保证了CP，即做到了分区容错性和一致性，但弱化了可用性。有时为了增强paxos系统的可用性，可以考虑增加learner角色的数目。

即便并不完美，Paxos在实践中仍然是可靠、有效且久经考验的。Paxos本质上是异步系统的分布式一致性协议，并且在该领域具有支配地位。Chubby之父甚至声称世界上只有一种一致性算法，那就是paxos（ there is only one consensus protocol, and that’s Paxos），其他一致性算法都是paxos的broken version。Paxos之所以在实践中有效是因为可能影响paxos系统liveness和可用性的条件并不容易被触发，即便真的出现，所带来的代价也可能并非是难以接受的。

Basic Paxos RPC通信与决策过程（https://ongardie.net/static/raft/userstudy/paxos.pdf）

Raft

有感于Paxos的晦涩难懂，Ongaro在2014年提出了更容易理解的Raft算法。Raft把易于理解、易于工程实现提到了很高的重要级别，甚至是raft的初心和存在理由，因而在不影响功能性的前提下，尽可能多地做了易于理解的精细设计。

Raft算法是leader-based的非对称模型，系统中的任意一个节点在任意时刻，只能处于leader、follower、candidate这3种状态之一。初始状态所有节点都是follower状态，follower想变成leader必须先成为candidate，然后发起选举投票；如果投票不足，则回到follower状态；如果投票过半，则成为leader；成为leader后出现故障，若故障恢复后已有新leader，则自动*，回归follower状态。

Raft还引入了term的概念用于及时识别过期信息，类似于zookeeper中的epoch；term值单向递增，每个term内至多一个leader；若不同term的信息出现冲突，则以term值较大的信息为准。

Raft还采用了心跳包和超时时间，leader为了保持自己的权威，必须不停地向集群中的其他节点发送心跳包；一旦某个follow在超过了指定时间（election timeout）仍没有收到心跳包，则就认为leader已经挂掉，自己进入candidate状态，开始竞选leader。

不难发现，raft的leader选举是通过heartbeat和随机timeout时间来实现的；而日志复制（log replication）阶段是以强leadership来实现的：leader接收client的command，append到自身log中，并将log复制到其他follower；而raft对安全性的保证是通过只有leader可以决定是否commit来实现的。

详细的竞选、复制等过程，这里不再赘述，有兴趣的同学可以参考笔者之前的文章（https://yq.aliyun.com/articles/675031 ）。值得一提的是，raft中的leader选举过程和leader任期内的正常运作过程都比较简单，复杂的其实是leader的变更过程。

然而，虽然raft的原理机制与paxos不尽相同，但二者所解决的问题，以及所采取的折中权衡策略，可以认为是类似的。也就是说raft仍然只能解决故障错误，仍然强调了故障容错与安全性、一致性，弱化了liveness和可用性。

Raft协议概览（https://ongardie.net/static/raft/userstudy/raft.pdf）

PBFT

自从1982年Lamport提出拜占庭将军问题之后，虽然有诸多关于拜占庭容错解决方案的讨论，但长期以来，此类问题的解决方案都效率低下、运行缓慢、复杂度过高，直到1999年Castro和Liskov提出实用拜占庭容错算法（Practical Byzantine Fault Tolerance），首次将此类算法的复杂度从指数级降到了多项式级，TPS可以达到几千，也使得节点故意作恶类问题在实践中找到了可行的解法。可以证明，如果系统内作恶节点数目不超过总节点数目的1/3，PBFT算法就能生效。

在PBFT中，所有的节点被顺序编号，其中1个是leader，其余的都是backup。系统内的所有节点间都互相通讯，依据多数原则达成一致。PBFT中的每轮共识都被称为一个view，而在不同的view之间，leader都会发生变化；如果超过给定的时间，leader没有广播出消息，则leader就会通过view change协议被替换掉。通过这种replica timeout机制，保证了crashed或malicious leader会被检测出来，从而通过重新选举新的leader，而进入到新的view中。

如图所示，从客户端发起请求到收到回复结果，可以分为5个阶段，而共识过程采用了3阶段协议。下面简要叙述5个阶段的大致过程：

发起：客户端（client c）向集群发起服务请求m；
pre-prepare阶段：leader节点（replica 0）验证请求消息m的有效性，并在其view内为该请求m分配序列号n，并向所有backup节点（replica 1-3）广播关于该分配的pre-prepare消息；
prepare阶段：backup节点验证请求消息m的有效性，并接受序列号n。若该节点同意该分配方案，则向其他所有节点广播出相应的prepare消息；这一阶段其实是要求所有replica达成全局一致的顺序。
commit阶段：所有节点（包含主备）一旦收到来自集群的同意分配消息，则向其他所有节点广播出commit消息；这一阶段，所有replica已经对顺序达成一致，并对收到请求已做确认。
执行并返回：节点收到来自集群的commit消息后，执行请求m，并返回消息给客户端；客户端等到接收到来自f+1个不同节点的相同回复，则认为请求已成功执行；其中f表示集群中潜在故障节点的最大数目。这里所有节点都向client直接返回消息也是为了避免主节点在请求期间出问题。

PBFT算法正常运作过程（http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf）

PBFT基于异步网络模型做到了安全性，但需要依赖消息超时时间来做周期性的同步。因为采用了leader-based方案，消息同步过程很快，也做到了完全的顺序写入。但是leader的重新选举过程很困难，某些恶意leader可以在临近timeout窗口期时才发送消息，这样会导致系统严重缓慢。而利用这一不利特点，可以攻击网络使正确的leader看起来也出问题，从而导致无穷无尽的leader选举过程。

PBFT与Paxos、Raft相比，所能处理应对的问题更为完备，除了能应对故障崩溃类错误之外，还能处理存在“捣乱者”的恶意篡改类拜占庭错误。然而，从所采取的折中权衡策略来看，PBFT仍然与Paxos、Raft很类似。从FLP的视角来看，PBFT同样更关注容错性和安全性，而弱化了liveness。从CAP的角度，PBFT同样强调网络分区容错与一致性，而弱化了可用性。

即便如此，只要故障或作恶节点不超过总节点数的1/3，PBFT在实践中还是有效可行的。而拜占庭容错算法（BFT）也不止PBFT一种，BFT类算法也在不断进化，如Lamport就提出过改进版的Paxos算法BFT Paxos以处理拜占庭错误，近来也有人结合PBFT与Raft提出了 BFT Raft 算法。但从问题领域与原理机制上来说，仍然与原有的思路和框架较为类似，不再一一赘述。

适用场景

从Paxos、Raft到PBFT，再到目前层出不穷的Paxos变种、Raft变种、BFT类混合新算法，分布式一致性算法在不断发展、完善、进化。甚至各大公司也在结合自己的业务实际，研发各种适合自己场景的分布式一致性算法。这些算法虽然并不完美，但都在适合自己场景的业务实践中发挥着重大作用。那么这些算法的适用场景到底是什么？自身又有哪些局限性呢？

对于Paxos、Raft这类非BFT算法而言，只能处理机器硬件故障，而无法处理存在作恶节点的情况。显然，这类非BFT算法只能运行在非常可信的网络环境中，比如公司内部网络中，在这样的较为封闭的网络中，访问需要严格授权，从而保证各个节点的身份是已知的、可信的，基本排除了节点作恶的可能性，这类算法才能有效运行。

而BFT类算法，对于网络环境的要求不再那么苛刻，即使存在作恶节点，只要作恶节点数目不超过总节点数的1/3，整个系统依然是安全的。但问题就在于，你怎么知道网络中到底有多少作恶节点？作恶节点占总节点的比例到底有多高？显然，如果网络的接入是需要权限控制的，那么这个问题就相对容易解决。比如10家业务关联公司组成的联盟网络，只有这10家授权的公司才能访问，即便里面有个别公司（少于3家）蓄意作恶、妄图篡改数据，整个系统仍然是安全可靠的。在这种permissoned网络中，隐含着对于网络中可能作恶节点数目的预估，即便真的作恶了，也能方便快速地定位出其真实身份，间接提高了网络的安全性。

局限性

然而，在permissonless（开放权限、无权限控制）的公有网络中，BFT类算法很可能会有问题。因为，如果分布式网络是开放的，谁都能进进出出，而接入网络系统的成本又很低，那么没人知道网络中到底可能有多少作恶节点，即便真有作恶，也很难定位出真实身份。比如，一种比较典型的女巫攻击（Sybil attack）场景，作恶者可以通过大量伪造身份来控制集群中的大量节点，从而控制整个分布式网络。

另外，BFT类算法最大的局限性还在于仅能协调少量的节点，如几个到几十个，若节点数目成千上万，整个系统的性能将会非常低下，甚至可能无法达成共识，从而影响系统的liveness和可用性。想必大家已经注意到，在PBFT的三阶段协议中，都需要多点广播（multicast）：在pre-prepare阶段，主节点向所有备节点广播；在prepare节点，备节点向其他所有节点广播；在commit阶段，各个节点向其他所有节点广播。由此可见，通讯次数的数量级是节点数目的平方，当节点数目庞大时，这种两两广播的机制将会是灾难，系统几乎不可能在较短时间内达成一致。

综上可知，这些传统的分布式一致性算法，无论是Paxos、Raft，还是PBFT，通常适用于存在权限控制的、节点数目较少的、较为可信的分布式网络环境中。

在联盟链中的应用

事实上，这些传统的一致性算法在区块链时代也焕发了新的活力，得到了进一步的认识和使用。在网络环境较为可信的联盟链场景中，这些一致性算法得到了大量的应用。联盟链因如下特点而被业内看好其应用前景：

接入需授权：联盟链并不完全对外开放，一般只有几家或几十家企业组成，只有经过授权的公司或组织才能加入到网络中，并且一般是实名认证参与。
数据保护：联盟链信息数据并不完全对外开放，而只有授权方可见。这对于保护行业或公司的数据安全比较重要，如跨境转账中的交易信息等对于银行业至关重要、链上税务系统中的税务信息也很敏感。
可监管：联盟链中一般可以设立监管观察节点，对于敏感信息进行审计与监管，满足合法性要求。

在当前阶段，联盟链不失为快速落地、解决行业痛点的不错选择，也是对区块链后续发展的积极探索。因为联盟链需要授权才能参与，这其实相当于已经提前建立了相当程度的信任，网络环境较为可信，网络中的恶意行为和攻击行为发生的可能性都非常低，并且即便发生也很容易快速追责。因此在这样的场景下，传统的一致性算法也可以得到应用。比如：

HyperLedger Fabric(https://www.hyperledger.org/projects/fabric ) 在v1.0中可以使用Solo和Kafka pubsub系统来实现ordering；在v1.4版本也引入了Raft算法（https://hyperledger-fabric.readthedocs.io/en/release-1.4/orderer/ordering_service.html ）；目前这些均是CFT类算法，而raft的引入主要也是为后期支持BFT类算法铺平道路（ Raft is the first step toward Fabric’s development of a byzantine fault tolerant (BFT) ordering service. As we’ll see, some decisions in the development of Raft were driven by this. ）。
R3 Corda(https://www.r3.com/corda-platform/ )也采用了可插拔式的共识算法设计，不仅可以选择高速度、高可信环境的Raft算法，也可以选择低速度、低可信环境的BFT类算法（https://docs.corda.net/key-concepts-notaries.html ）。
以太坊企业联盟EEA(https://entethalliance.org/ )也支持BFT类算法、Raft算法，以及PoET算法（https://entethalliance.org/wp-content/uploads/2018/05/EEA-TS-0001-0-v1.00-EEA-Enterprise-Ethereum-Specification-R1.pdf ）。
蚂蚁区块链BaaS平台（https://tech.antfin.com/blockchain )也采用了PBFT算法。

Permissionless网络的挑战

那么我们忍不住要问，如果网络是完全开放的、无需权限许可的（permissionless），谁都可以随时进出，那么整个系统还能在有限的时间内达成一致吗？如果网络中的节点数目不再是几十个，而是一万个，那么又该如何协调这些数量庞大的节点呢？

在回答这些问题之前，其实更应该反问：为什么需要网络是完全开放、无需许可的？什么场景会需要一万个节点？这到底是伪需求，还是真实存在的场景？这个问题的答案直接关系到区块链中公有链的存在意义，而要回答这个问题，我们需要回到分布式系统的初心和目的。

去中心化的意义

我们为什么需要分布式系统？显然，这个问题不难回答，通常的理解，分布式系统可以增强容错能力（Fault tolerance)，毕竟系统依赖众多不同的节点，而众多节点同时失败的可能性远低于一个节点发生故障的可能性；另外，分布式系统还可以抵御攻击（Attack resistance），毕竟攻击或摧毁众多节点的难度远大于攻击单点的难度。

然而，以上这些依然是局限在物理硬件的维度，都是用来降低机器物理硬件发生故障的可能性，而没有考虑“人”的因素。如果一个系统足够重要，比如电子货币系统等，除了考虑机器故障之外，更多需要考虑的是人的因素。部署节点的人会不会故意作恶呢？如何防止系统内不同节点间的腐败串通呢？

如下图所示，以太坊创始人Vitalik Buterin曾经深入地探讨过去中心化的含义。如果说传统的分布式系统做到了architectural decentralization（系统有多少物理机器构成？系统能够容忍最多多少台机器同时故障？），考虑的是fault tolerance和attack resistance；那么现在我们需要考虑的是如何做到political decentralization，如何能够collusion resistance? 到底有多少人或组织最终控制了系统内的节点？如何防止这些人之间的腐败串通？如果说传统的分布式系统考虑的问题是网络或机器硬件的可信，那现在我们想考虑的是“人的可信”：是否存在这样的技术手段来防范人的作恶？如何确保重要网络中的大部分节点不被一个人或一个组织恶意控制？

去中心化的三个维度（https://medium.com/@VitalikButerin/the-meaning-of-decentralization-a0c92b76a274）

值得一提的是，这个问题的必要性依然充满争议，很多人根本不曾想过、或者认为根本没有必要考虑人的腐败串通，也可能认为对于这个问题技术也无能为力，毕竟这与我们生活的真实世界相去甚远。我们生活在一个中心化平台拥有极高声誉、提供信用背书、控制一切规则流程的世界，比如极少有人担心银行会故意做假账，侵吞你在银行的资产，毕竟大家普遍认为银行是值得信赖的。如果认为银行都不可信，那很可能一切商业活动都无法开展。

然而，我们只是“假设”银行是可信的，在“信任”与“怀疑”之间，我们只是*选择了信任，毕竟不信任银行，商业活动无法开展，经济也将停滞。然而实际上，并没有切实可行的措施来向所有人“证明”银行是可信的。

如果你认为这个问题是必要的、有意义的，那么能否找到一种解决方案，可以让这个世界变得更可信，让你不再需要“*相信”某个陌生人，而是提供一种“证明”，足以确保与你交易的某个陌生人是可信的？Don’t Trust, Please Verify. 你不需要相信我，你也不必相信我，你只需要去验证我。

如果要解决这个问题，所有人的身份应该是对等的，每个人都可以平等、*地参与决策过程，每个人都可以*地进出“议会”，这事实上是一种技术上的democracy，隐含的技术要素是：网络必须是permissonless的，谁都可以随时加入随时离开；节点之间必须是对等的，可以直接通讯；无任何中间人，无任何中心权威存在，完全的点对点（peer to peer）；每个节点都有希望成为记账者。

因为网络无权限控制，完全的开放、透明、*，所以参与的节点数目很可能非常众多，节点作恶的可能性也很高。那如何在这种permissionless的、节点数目众多、存在较大作恶可能的分布式网络环境中，通过某种机制协调节点间的行为，保证整个系统的一致性呢？显然，如前所述的一致性算法并不能做到这一点，我们需要寻求新的解法。

另外，去中心化可能是区块链领域最充满争议的词汇。一些人认为去中心化是区块链的价值观和公有链的灵魂与存在前提，应该尽可能地保证系统的去中心化程度；而另一些人认为完全的去中心化过于理想、不太可能实现，应该结合实际场景，在兼顾效率的情况下考虑弱中心化或多中心化。这里抛开价值判断，单纯从技术角度理性分析，去中心化程度越高确实系统的安全性会越高，所以在公有链的系统设计中确实应该尽可能地保证系统的去中心化程度。不过，结合Vitalik Buterin对于去中心化含义的诠释，在追求去中心化的过程中，我们不应该停留在单纯的表面上看起来的去中心化，而应该综合考虑去中心化的各个维度，结合实际情况，做出必要的trade-off。

PoW

对开放网络中的分布式一致性问题比较创新的解法当属比特币中的Proof-of-work（PoW、工作量证明）机制。

不得不提的Bitcoin

2008年10月31日，中本聪发表了比特币白皮书《Bitcoin: A Peer-to-Peer Electronic Cash System》，天才般地为此类问题提供了创造性的解决思路，使得协调复杂网络环境中的成千上万节点成为可能。事实上，中本聪并不是为了解决这个技术问题而发表了比特币白皮书。相反，中本聪想象的更加宏大，他创造性地发明了比特币这种完全点对点的电子现金系统，以消除传统支付中需要依赖的可信第三方中间人，而在实现的过程中恰好依赖并解决了开放网络中众多节点间的一致性问题。也可以说，比特币所解决的最核心问题是点对点网络中电子货币的双花问题。然而，比特币的实现机制绝不仅仅是分布式网络技术问题，还结合了密码学、经济学、博弈论等思想，并以一种非确定性的概率方式实现了节点间的一致性。因此，单纯地称为算法已不太能准确表达其含义，可能叫作共识机制（consensus mechanism）更为恰当，因为其实现的确依赖了一整套的完整策略与制度。这里我们不过多阐述比特币的思想意义与实现细节，而仅聚焦在其共识机制的实现上。

比特币实际上是电子签名链，币的owner可以通过对前一个交易的哈希值和下一个owner的公钥进行签名，并将签名添加到币的末尾，从而实现转账。接受者通过校验签名来验证币的owner构成的链。然而，问题是币的接受者没有办法确保币的owner没有进行双花（double-spend），即有可能某个币的owner将同一个币先后转给了两个人。因此我们需要一种机制来让接收者确保币的前一个owner并没有在此之前将币转给其他人，为了确保这一点，唯一的办法就是让所有人知晓所有的交易。而在无可信第三方的情况下，想实现这一点，所有的交易必须广播给所有人。因此我们需要一个系统，其中的所有参与者对他们接收币的顺序达成一致，形成唯一的顺序记录历史。不难发现，这其实就是分布式一致性问题。

而比特币提供的方案就是需要一个由所有节点组成的时间戳服务器（timestamp server），时间戳服务器可以对交易区块的哈希加盖时间戳，并将该哈希广播出去。每一个时间戳都在其哈希中包含了前一个时间戳，从而形成一条链，而每一个新的时间戳都是对其之前所有时间戳的确保与强化。为了在点对点的网络中实现分布式的时间戳服务器，比特币采用了工作量证明机制（proof-of-work，PoW）。PoW涉及在做哈希运算时，需要寻找某个值，使得总体哈希值的开头前几位都为零，而所需要的平均工作量随着零位数目的增多而指数增加。另外，该哈希没有任何规律，为了保证开头前几位为零，只能通过暴力的方法不断地随机试错。一旦消耗了足够的CPU的算力，找到了符合条件的哈希值，则该区块就无法变更，除非再耗费CPU重做一遍。

另外，PoW也解决了大多数决策问题。在比特币中，最长的那条链就代表了大多数的决策。因为如果诚实的节点控制了大部分的算力，则诚实的链就会快速增长并超过其他链。如果想篡改某个过去的区块，攻击者必须重做相应的区块和其后面所有区块的PoW任务，然后追赶并赶超诚实的节点。这种难度是非常巨大的，从数学上不难证明，随着后续节点数目的增多，较慢的攻击者想追赶上来的概率指数下降，一般认为经过6个区块之后，想追赶上来几乎是不可能的。另外，PoW任务的难度并不是固定的，而是用移动平均的方法动态调整的，这主要是考虑到硬件运算速率的提高和挖矿人数的增减变化，算的快就加大难度、算的慢就减小难度，通过动态调节难度使得比特币的出块时间大致稳定在10分钟左右。

整个网络的运行过程如下：

新交易广播到所有节点。
每个节点都将收到的交易打包到一个区块内。
每个节点都为该区块不断尝试改变nonce，做PoW任务，以使得该区块的哈希符合指定条件。
一旦某个节点完成了PoW任务，则它将该区块广播给其他所有节点。
其他节点收到该区块后，验证区块内交易的有效性，验证通过则接受该区块。
节点如何表达自己接受了该区块呢？那就在添加下一个区块的时候，将该已接受区块的哈希值作为下一个区块的前一个哈希值（previous hash）。

比特币交易过程（https://www.giottus.com/Bitcoin）

关于交易、挖矿等细节，这里不过多阐述，有兴趣的同学可以参考笔者之前的入门介绍文章（https://www.atatech.org/articles/126343 ）。简而言之，在比特币中总是以最长链的信息为准，若某个节点发现了比自己更长的链会自动切换到最长的链工作。

我们忍不住要问，既然PoW成本如此之高，那如何激励大家贡献算力、成为节点，以保证整个比特币网络的安全呢？比特币中提供了两种激励策略：

挖出某个区块的节点会得到一定量的比特币，这其实也是比特币唯一的发行机制（一级市场），所有的比特币都只能通过挖矿的形式被挖出然后进入流通领域；
矿工处理交易信息可以得到一定量的手续费，这其实是存量比特币的流通（二级市场），而当比特币的2100万枚被完全挖出后，激励策略就只能依靠手续费这种方式了。

这些激励策略也隐含地鼓励了节点保持诚实，若某个贪婪的攻击者真的拥有了过半的CPU算力，他不得不做出选择：到底是篡改交易记录，把他已经花出去的比特币再转回来呢？还是老老实实地挖矿赚钱新币和手续费呢？很可能，老老实实地挖矿是更有利的，毕竟能赚到的币比其他所有节点加起来都要多；而破坏比特币体系也将会破坏自身财富的有效性，毕竟若比特币不再可靠，其价值也会迅速崩溃。这里多提一点，攻击者并不像一般人想象的那样可以为所欲为、任意篡改或伪造交易记录，他能做的只可能是将其最近花出去的比特币偷回来。

PoW为什么有效？

比特币在没有任何组织或团体维护的情况下，仅仅依靠社区志愿者自发维护，稳定运行了10年之久，期间从未发生过重大问题，这不能不说是个奇迹，也足以证明了比特币背后共识机制的有效性。我们忍不住要问，为什么比特币能够做到？为什么比特币背后的共识机制能够如此有效？bitnodes数据显示目前比特币节点数目超过1万（比特币节点类型较多，不同口径数量可能不一致，这里仅考虑全节点）。为什么比特币能够在permissionless的网络环境中，协调上万的节点保持一致性？

笔者粗浅的认为，可能有以下几个原因：

有效的激励策略：通过激励策略有效地激励了更多节点参与到比特币的点对点网络中，节点越多比特币网络越安全。
PoW：挖矿出块需要消耗CPU算力，人为地制造障碍、增加成本，提高了攻击者的作恶成本。
博弈论思想：激励策略也考虑了博弈平衡，理性节点保持诚实的收益更大。
通讯效率：比特币节点间的通讯效率并不低效，大家可能注意到其中也涉及到了交易和区块的广播，不过这种广播并非是两两广播，而是由某个节点（发生交易或算出PoW的节点）将信息广播到其他所有节点。另外，交易广播并不要求触达所有节点，只要有许多节点接受，不久之后就会被打包。2014年也有Miller等人（Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin）严格证明，消息复杂度并不随网络大小而增大，而是一个常数。另外，区块广播也容许消息丢失，若某个节点未收到某个区块，则当它接收到下个区块时，会意识到自己遗漏了上个区块，而主动向其他节点请求该区块。
概率性的一致性：相比其他一致性算法，比特币的共识机制最特别的是不再追求确定性的一致性，而是追求概率性的一致性。当某个区块刚被挖出的时候，其包含的交易信息并非被所有节点最终确认、其包含的数据并非是最终一致性的结果，还是有可能被攻击者篡改的；但是随着后续节点数目的增多，这种被篡改的可能性指数下降，最终一致性的概率显著增大；一旦后续节点超过6个（也就是经过约60分钟），这种一致性就可以被认为是确定的、最终的。

显然，比特币的共识机制不再拘泥于分布式算法层面，而是包含了更多经济学、博弈论、概率论等思想，因此可能叫作共识机制更为恰当。不过，我们仍然可以将比特币的PoW共识机制放到一致性问题的框架内来思考，从FLP和CAP的角度来看：

比特币最大程度地考虑了故障容错和网络分区容错，这也是对网络openness的必要要求，因为开放网络环境极其复杂，谁都可以随时进出，节点遍布全球各地，机器故障、网络分化、系统攻击随时可能发生，容错是必须需要考虑应对的。而利用PoW机制，比特币不仅做到了故障容错，而且结合密码学非对称加密技术，也可以做到拜占庭容错，抵御恶意篡改与攻击。
比特币尽可能地保证了liveness和availability，比特币的出块时间总是在10分钟左右，这也就意味着系统总可以在10分钟内达成一致；比特币网络十年来不曾瘫痪，从这个角度来讲确实将可用性做到了极致。然而，我们必须指出，比特币的可用性与我们通常理解的互联网领域的可用性是有很大差异的。互联网领域的系统可用性，不仅要求系统稳定运行不宕机，还对服务体验如响应时间有明确要求。如果你用支付宝转账，不是随时可转、3秒到账，而是告诉你系统繁忙，需要等待10分钟、甚至30分钟，这显然会被认为服务不可用。然而，这一现象在比特币中一直在发生，比特币每10分钟一个区块，而区块大小只有1M，装不下太多交易，若同一时间交易过多，只能一直等待，直到能被下一个区块打包进去，所以经常可能需要等待20分钟、30分钟、甚至更久。从这一角度对比来看，其实比特币网络放宽了对响应时间的要求，做到了比较基本的可用性：读的可用性极高，而写的可用性很低。
比特币对于safety和consistency，不再追求确定性，而是采用了概率性的保障，基本可以认为保证了最终安全性和最终一致性，只不过这里的“最终”依然是有时间条件的、基于概率的。比如，如果我刚刚给你转账了一个比特币，没人敢说这个结果是确定的、最终的，但是随着时间的推移，不断有新的区块被挖出，我转账的交易信息也会被更多的节点确认、被更多的后续区块强化，这一结果确定性的概率不断增大，一旦过了足够的时间（如1个小时），我们从概率角度可以认为结果被篡改的可能性极低，系统达成最终一致性的概率极高，从实践上就可以认为系统保证了最终的一致性。

综合来看，不难看出，比特币的PoW共识机制在FLP和CAP的限制下，做到了比较好的折中权衡，在实践中确实提供了开放复杂网络中分布式一致性问题的可行解法，比特币近十年来的稳定可靠运行也有力地证明了这一点。

另外，比特币的PoW算法也被Miller等人（https://socrates1024.s3.amazonaws.com/consensus.pdf ：Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin）严谨地分析并证明：

比特币网络可以看作是由近似无穷节点组成的，每个节点贡献一小部分算力，并且相应地每个节点都有较小概率可以创造区块。
PoW算法依赖于同步网络模型。在该模型中，若网络延迟为0，则算法可以容忍50%错误；而以目前真实观测的网络延迟来看，比特币可以容忍49.5%的错误；若网络延迟等于区块时间（即10分钟），则只能容忍33%的错误；若网络延迟接近无穷，则算法的容错也趋近于0。
比特币PoW算法具有扩展性（scalable），这是因为共识时间和消息复杂度都与网络大小（网络中的节点数目）无关，而只与错误节点的相应算力有关，可以认为是一个无量纲常数。

可见，PoW算法不仅在实践中可靠，在理论上也能经受考验。PoW算法采用了同步模型与随机概率来规避FLP的确定性异步模型不可能定理。而PoW独立于网络大小的可扩展性，与PBFT算法O(n2)复杂度相比优势巨大：节点越多，系统效率并未降低，而系统却更安全。

PoW到底是什么？

我们忍不住要问，PoW机制到底有何神奇之处呢？

其实，大家可能也意识到了，PoW的思想并不高深，事实上也并非是中本聪首创。早在1993年这一思想就被提出用于对抗垃圾邮件(Pricing via Processing or Combatting Junk Mail)，但直到中本聪创造比特币之前，这一思想都尚未得到广泛应用。PoW思想的精髓就在于故意制造障碍、增加参与者的成本，以尽量降低参与者的恶意企图。比如要求请求者做些额外的工作以检测DDoS攻击、垃圾邮件等，也比如最常见的登录网站需要输入验证码，也是为了增加登录成本，防止网站被攻击。这类任务最核心的特征是非对称：对于服务请求者来说，完成任务必须有一定难度；而对服务提供者来说，验证任务必须很简单快速。对于比特币PoW而言，显然符合非对称性：不断试错，寻找使哈希符合条件的nonce（随机数）需要消耗大量算力，而验证寻找到的nonce是否符合条件只需要做一次简单的哈希运算验证即可。

比特币的PoW本质上是one-CPU-one-vote，一个CPU投一票。为什么选择CPU，而不是IP地址呢？这仍然是基于任务难度考虑，若是one-IP-one-vote，则系统可以被拥有大量IP地址的人（如ip供应商）轻易控制。相对而言，至少在当时（尚未出现ASIC和FPGA）CPU仍然是比较昂贵的硬件，想拥有大量的算力（CPU+电力）并不容易。当然，这其实也隐含地为比特币的价值提供了现实锚定：虚拟的货币体系通过算力找到了现实物理世界的价值锚定，虽然在很多人看来这种算力的消耗是毫无意义、浪费能源的。

也有很多人提出如何降低比特币的挖矿成本，当然这种思考尝试有其积极意义，这种工作量证明的成本需要适宜：难度过大、成本过高确实浪费能源较多，不过比特币网络的安全性也得到了提高；难度过小、成本过低则会起不到防攻击的目的，进而也会降低比特币网络的安全性。这其实是一个需要做tradeoff的问题，也是一个偏主观的价值判断，取决于大众对比特币的认识和定位。价值判断总是充满了主观偏见，目前对于比特币的争论如此之大，其实也正是因为社会大众尚未达成共识，尚未构建出对于比特币未来共同一致的想象。

简言之，比特币的PoW是一整套的机制，包含了技术上的权衡、经济和博弈的考量，这一整套的策略和机制共同保障了比特币网络的安全可靠。

PoW机制的局限性

凡事没有完美，PoW机制也不可例外地存在局限，其实从大家对比特币的诸多批评也可见一二，通常地大家认为PoW机制存在以下局限性：

成本过高、浪费能源：大家对比特币浪费能源的批评声不绝于耳，digiconomist数据显示，比特币的全年电力消耗基本与新西兰相当，也相当于澳大利亚用电量的1/5；而每笔比特币转账交易的成本是每10万笔visa转账交易的3倍。虽然有时候这种对比有失公允（比特币交易即清算，而visa除交易成本之外还有额外的清算成本），也有不少人并不以为然。前文也提到这其实也是一种主观价值判断，但这毕竟是一种声音，有时候也是切实的痛点，比如恐怕没人愿意用比特币买杯咖啡，毕竟手续费可能会比咖啡还贵。而罪魁祸首当然是PoW机制所需要的CPU算力消耗，因此不断有人尝试改进，甚至提出新的解决思路。
效率低下：大家习惯了互联网的便捷，习惯了秒级到账和百万级别的TPS，对于比特币交易动辄需要等待几十分钟，每秒钟仅能支持7笔交易，显然不太满意。虽然这种对比也并不公正，毕竟银行系统后台只有几个机房、最多百台机器，并且交易只进入到了其中某台机器，事后的清算环节才保证了最终一致性；而比特币无任何单点，协调的是上万台机器，并且交易即清算。不过这种效率的低下也确实是事实，也不断有人尝试改进，如把比特币每个区块的size limit调大，让其每个区块能打包更多的交易，bitcoin cash就是这么干的；再如把比特币的出块时间改小，让其更快出块，litecoin就是这么干的。但即便如此，PoW为了保证网络安全性而要求的巨大的工作量证明成本，也注定了网络的效率很难有质的提升。
中心化风险：随着ASIC和FPGA等特制挖矿芯片的出现，普通个人PC想挖出比特币几乎是天方夜谭。挖矿越来越集中到有实力研发芯片的巨头企业上，而矿池（为了平滑收益大量节点组成联盟共同挖矿、平分收益）的出现也加剧了这一趋势。另外，对比特币block size limit的调大，也会导致运行比特币全节点需要庞大的存储空间，以至于无法在普通PC上运行，而只能运行在特制的大型计算机上。这些中心化的倾向无疑都会损害比特币网络的安全性，毕竟由全世界各个角落的普通PC构成的比特币网络的安全性远远高于由几个巨头公司直接或间接控制的比特币网络。虽然这一问题的争议更大，仁者见仁，但仍然有很多人在尝试寻求新的解决思路。

PoS

在这些新的解决思路中，无疑最引人注目的就是Proof-of-stake（PoS、权益证明），同样面对开放复杂网络中的一致性问题，提出了全新的解决方案。

基本思想

2011年在bitcointalk论坛一个名为QuantumMechanic的用户率先提出了proof-of-stake的思想（https://bitcointalk.org/index.php?topic=27787.0 ），而后不断发展完善，得到越来越多人的信赖。

PoS的基本思想大致如下：

所有节点不再同时竞争挖矿，而是每次仅有1个节点做验证者：在比特币网络中，所有节点都需要做PoW任务，也就是说都需要做复杂的哈希运算而消耗大量CPU算力，而只有最先找到答案的节点才能获得奖励。这种所有节点间的同时竞争挖矿无疑需要消耗大量资源，那么是否可以每次只有一个节点工作呢？如果可以，那怎么选定这个幸运儿呢？PoS中不再需要挖矿，不再有miner，而是每次只需要选出一个节点作为validator去验证区块的有效性。如果某个节点被选为validator来验证下一个区块，它将验证该区块内的所有交易是否有效。如果所有交易都验证有效，则该节点对该区块进行签名，并添加到区块链上。作为回报，该validator将会收到这些交易相关的交易费用。显然，在PoS中每次共识只有一个节点付出了劳动，且该劳动非常轻松，从而达到了节约资源的目的。
想成为validator必须提供保证金：为了防止validator作恶，想成为validator必须提前往指定账户存入代币作为保证金或抵押担保金，一旦被发现作恶，则保证金即会被罚没，而诚实工作将会得到激励。显然，只要作恶带来的收益不超过保证金额度，节点就会老老实实地保持诚实。
被选为validator并不是完全随机的，而是被选定概率与提供的保证金金额成正比：例如Alice提供100个币的保证金，而Bob提供500个币的保证金，则Bob被随机选为validator从而产出下一个区块的概率是Alice的5倍。这其实就类似于股份制公司，按照出资比例来划分发言权、最终受益权等，大股东出资多、承担责任大、相应的回报也大。

PoW与PoS对比图（https://hackernoon.com/consensus-mechanisms-explained-pow-vs-pos-89951c66ae10）

不难发现，PoS也是采用了经济和博弈的思想，通过激励策略和惩罚机制来确保了网络的安全可靠。

PoS为什么有效？

PoS协议仍然符合传统的拜占庭容错算法研究的结论。目前围绕PoS的研究可以分为两条主线：一条围绕同步网络模型、一条围绕部分异步网络模型。而基于链的PoS算法几乎总是依赖于同步网络模型，并且其有效性与安全性可以像PoW算法一样被严格证明（https://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf ）。

另外，从CAP的角度来看，基于链的PoS算法与PoW算法类似，也是尽可能地做到了容错性，另外在可用性与一致性之间，更多地保证了可用性。

如果说传统的一致性算法（Paxos、Raft和PBFT）实现的是确定性的最终性(finality)或一致性，那么PoS与PoW类似，转而寻求概率性的最终一致性。从传统CAP的视角，这其实是对一致性的弱化，然而从实践可行性的视角来看，也是一种全新的思维和突破。

而从PoS的设计策略来看，也可以分为两大阵营（https://arxiv.org/pdf/1710.09437.pdf ）：

一类是如前所述的chain-based PoS，主要是模仿PoW机制，通过伪随机地把区块创造权分配给stakeholders来模拟挖矿过程，典型代表如PeerCoin、Blackcoin等。其安全性与有效性可以参考类比pow来看。
另一类是BFT based PoS，基于近30年来的BFT类一致性算法研究。基于BFT算法来设计PoS的思想最初在Tendermint中提出，以太坊2.0中的Casper也遵从了这一传统并做了一些修改完善。这类PoS的安全性与有效性可以参考BFT类算法来看，如可以从数学上证明，只要协议参与者的2/3以上节点都诚实地遵照协议，不管网络延迟有多大，算法都能保证最终状态不会出现冲突区块。不过此类算法也并不完美，特别是针对51%攻击问题，也尚未完全解决，目前该领域仍然处于开放探索阶段。

PoS的争论

PoS的思想并不复杂，而其中比较容易被诟病的恰恰就是这种与现实世界类似的按出资比例获取收益的制度。大家对现实世界的马太效应已经非常警惕，这种制度显然容易带来富者越富、穷者越穷的结果：拥有更多代币的人，将会有更多机会成为validator，从而参与网络并获得更多收益。

然而，对这一问题的看法争议很大，很多人提出了完全不同的看法，认为PoS相比PoW更公平、更有助于对抗中心化趋势。理由主要是：PoW挖矿依赖现实世界的物理硬件和电力资源，而这很容易带来规模经济（Economies of scale）优势。购买10000台矿机的公司相比购买1台矿机的个人更有议价权，甚至可以自主研发成本更低的矿机；而拥有10000台矿机的矿场，对电费的议价权也更高，甚至可以搬迁到电费便宜的国家和地区的电站旁边，甚至可以自建成本更低的电站。由此带来的后果就是越庞大的组织的综合挖矿成本越低，而这正是现实世界真实已经发生的事实。相比之下，PoS不需要依赖现实硬件，不存在规模经济优势，在不考虑价格操纵的情况下，买1个币的价格和买10000个币的价格是线性增加的，从这个角度理解，PoS可能更公平，更有助于去中心化。

对PoS的另一个担忧是其安全性，毕竟PoS不再像PoW那样做复杂的CPU运算以证明自己。在PoW中，若想发动攻击，需要控制51%的算力（近来也有研究发现只需25%算力即有可能攻击成功），这也就意味着需要拥有大部分的矿机和算力资源。而在PoS中，若想控制整个体系，需要拥有51%的代币。究竟哪个更安全？其实也不太好讲，不过可以从现实世界的例子来看，如果比特币算法切换为PoS，则控制比特币体系需要大约比特币市值的一半，大概是400~1600亿美金（比特币价格区间5000~20000美金），显然这一数字远远高于矿机成本，想拥有这么大资金量发动攻击几乎是不可能的，从这个角度来讲，PoS可能更安全。

除此之外，PoS因为部署成本很低（对硬件要求很低），在真实世界中会导致代币非常容易分叉，从而产生一堆山寨币，而PoW不存在这个问题。因为PoW依赖硬件挖矿，若想把比特币的某个参数改改，这很容易；但真想跑起来，则需要大量算力的支持，需要争取大量miner的支持，比如bitcoin cash从bitcoin中分叉出来就历经波折。而PoS完全没这个顾虑，随便某个人都可以下载开源代码、随意改下，拉几个节点就可以声称自己创造了一种全新的代币，比如从EOS（代币名）中可以轻易分叉出几十上百个山寨兄弟币，每个都声称自己很独特。这确实是事实，不过也不太容易说孰好孰坏。

PoS的改进优化

PoS机制中最关键的当属下一个区块validator或creator的选择机制，究竟谁来做这个幸运儿？前文所说的根据账户资金按比例按概率选择其实是最简单的一种方式，这种方式确实容易导致有钱人获得一劳永逸的收益，从而损害网络中其他参与者的积极性。目前有很多种思路来改善这一问题，其中比较有意思的是coin age-based方法，在选择creator的时候，除了考虑资金量，还会考虑coin age（币龄）。所谓的coin age指的是币在某个账户上的停留时间，比如1个币转入指定账户经过10天，可以认为币龄是10，而每次币发生变动币龄都会从0开始重新计算。通过这样，可以限制大资金量节点频繁成为creator，比如可以设定币龄达到30才有机会成为creator，而成为creator之后币龄立即清零。这其实是限制了大参与者的利益，为其他中小参与者提供了更多的参与机会。

基于PoS改进的比较有名的方案当属Delegated Proof-of-Stake（DPoS），其中采用了代理人委托机制。在DPoS中不再是所有节点都有可能成为creator，而是节点间相互投票，只有得票最高的一些节点才可能参与区块创造过程。具体如下：

代理人的职责包含保证自身节点持续运行、收集交易信息并打包到区块中、签名验证并广播区块、解决网络中可能存在的一致性问题。
对于大多数DPoS链来说，网络中的所有持币人（token holders）都可以向代理人投票，且投票权与持币数量成正比。用户也可以不直接投票，而把投票权委托给其他人来代表他们投票。
投票是动态的、可变的，意味着某个代理人随时可能被选进来或选出去。而一旦某个代理人被发现作恶或欺诈，就将失去收入和名誉，这就起到了激励代理人保持诚实、保证网络安全的目的。代理人可以将收到的区块奖励按比例分给向他投票的用户（这其实相当于贿选，在有些方案中不被允许）。
不像传统的PoS，代理人不再需要持有大量的代币，而是必须相互竞争从持币者那里争取投票。
DPoS限制了交易区块的验证者人数，这相当于牺牲了一定程度的去中心化，但却带来了效率的提升，因为网络达成共识所需的工作量大幅降低。

DPoS选举validator/witness过程（https://www.nichanank.com/blog/2018/6/4/consensus-algorithms-pos-dpos）

不难发现，DPoS通过引入投票机制，尽可能地保证了节点的广泛参与；而对validator数目的限制（一般是21-101个），尽可能地提高了系统的运行效率。虽然充满很大争议，DPoS仍然不失为一种可行的解法，越来越多的区块链系统也在尝试对其进行改进和探索。

在公有链中的应用

在公有链中，众多项目都采用了PoS机制，比较有名的有：

以太坊（Ethereum：https://www.ethereum.org/ ）：目前阶段以太坊仍然采用的是PoW挖矿机制，不过作为以太坊的创始人和公有链领域的领军人物Vitalik Buterin对于PoS机制显然更为青睐，也多次阐述过PoS的设计哲学（https://medium.com/@VitalikButerin/a-proof-of-stake-design-philosophy-506585978d51 ），以及PoS相比PoW的优势（https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ#what-are-the-benefits-of-proof-of-stake-as-opposed-to-proof-of-work ）。目前以太坊正在开发基于PoS的Casper协议（https://arxiv.org/pdf/1710.09437.pdf ），预计将于今年下半年发布，这种从PoW到PoS的转变也标志着以太坊进入2.0时代。如下图所示，在以太坊2.0 phase0阶段，将会发布采用Casper协议的PoS beacon chain，作为coordination layer(https://github.com/ethereum/wiki/wiki/Sharding-roadmap )。

以太坊2.0 layers和phases(https://docs.ethhub.io/ethereum-roadmap/ethereum-2.0/eth-2.0-phases/)

EOS(https://eos.io/ )：作为DPoS思想的提出者Daniel Larimer发起了EOS公有链项目，其中众多节点会一起竞争，期望成为拥有记账权的21个Supernodes中的其中一员。这种类似现实世界议会制度的设计引起了非常大的争议，而超级节点的竞选也可能蕴含着巨大的商业利益，这些都已经超越了技术讨论的范畴，在此不做过多讨论。

Proof of X?

其实，PoS机制的兴起除了其本身具备的低成本、高效率、去中心化等特点之外，还在于它打开了一扇新的大门——基于博弈论机制来设计如何降低中心化风险的一系列技术，如何预防中心化垄断巨头的形成，以及在已有巨头的情况下如何防范它们损害网络（ Proof of stake opens the door to a wider array of techniques that use game-theoretic mechanism design in order to better discourage centralized cartels from forming and, if they do form, from acting in ways that are harmful to the network）。

而随着近年来区块链（特别是公有链）的蓬勃发展，其他各种Proof of机制也层出不穷。从这里面的诸多机制中都可以看到PoS思想的影子，即如何从经济角度和博弈视角来设计制度尽可能地保证去中心化、安全性与高效率。下面对这些机制做简要说明：

Leased Proof of Stake:持币量非常低的众多节点可以将代币出租给其他节点，从而形成合力，增加成为validator的几率；而一旦选举胜出得到奖励，则按比例分配手续费，其实与矿池的思想比较类似。
Proof of Elapsed Time:所有节点都必须等待一定的时间才能成为记账者，而等待时间是完全随机的。而要想保证公平，核心的两个问题是：如何保证等待时间确实是完全随机的？如何保证某个节点真的等待了指定的时间？目前的解法依赖于Intel的特殊CPU硬件Intel SGX 系统，目前通常也仅能应用在permissioned网络环境中，如前所述的以太坊企业联盟EEA中。
Proof of Activity:PoA同时结合了PoW和PoS的思想。在PoA中，起始过程与PoW类似，仍然是miners间竞争解题挖矿，只不过所挖的区块仅仅包含头信息和矿工地址。而一旦区块被挖出，则系统自动切换成PoS模式，区块头信息指向一个随机的持币者（stakeholder），由该持币者来验证该pre-mined区块。
Proof of Importance:有感于PoS机制倾向于鼓励人持币而不是流通、也容易导致富者越富的问题，PoI在计算节点对系统的重要性上吸纳了更多的维度：除了考虑币的数量、币在账户上的停留时间之外，还考虑了交易对手（与其他账户的净交易越多分数越高）以及最近30天交易数目和大小（交易越频繁、数额越大分数越高）。
Proof of Capacity:也称作Proof of Space，思想与PoW类似，只是不再以CPU算力为衡量标准，而是以存储空间来衡量。
Proof of Burn:矿工必须烧毁一定量的代币，即将一定量的代币转入eater address(黑洞地址，只进不出，即私钥未知的地址)，以此来证明自己。本质上与PoW的思想接近，只是工作量证明消耗了算力资源，而PoB直接消耗了代币本身。
Proof of Weight:PoWeight是在PoS考虑代币量的基础之上，增加考虑了更多的权重因子。比如FileCoin（IPFS分布式文件系统上的代币）考虑了你拥有的IPFS数据大小；其他的一些权重因子也包含但不限于Proof-of-Spacetime、Proof-of-Reputation等。

一致性算法概览（https://101blockchains.com/consensus-algorithms-blockchain/）

不难发现，虽然这些Proof-of机制层出不穷、不尽相同，但其要解决的核心本质问题是相同的，即：让谁来成为能够记账的幸运儿？这些Proof-of机制只不过是采取了各种不同的策略来制定游戏规则，让各个节点尽可能公平地证明自己，从中公平地选出幸运儿。所有这些策略，包括基于CPU算力、持有代币数量、存储空间大小、随机等待时间、销毁代币数量、节点活跃度、节点贡献度等，都是在特定的场景下对于开放网络中一致性问题的探索。

一切关乎信任

从PoW到PoS，再到Proof of "Everything you can think"，对于permissionless网络中的一致性问题一直在探索中。“一致性”的内涵也在发生变化，从传统的如何防范网络与机器硬件的故障，保证网络节点间的数据一致性，到开放网络中，如何防范网络中人的作恶，保证网络中节点数据间的真实一致。可以说是从硬件的可信，迈进了“人的可信”，公有链技术也被视为“信任的机器”。不过显然，人的可信问题过于复杂，甚至也超越了单纯的技术范畴。目前阶段所能做到的也远远未能保证“人的可信”，更多的仍停留在人对于机器的信任、人对于“协议”的信任。不过可喜的是，我们终于迈出了这一步，开始直面这个棘手的问题，探索创新性的解法。

信任的机器（https://www.economist.com/leaders/2015/10/31/the-trust-machine）

总结

这个世界充满了不确定性，计算机科学也一样。从计算机出现开始，我们就不得不面对机器硬件的不确定性：意外故障可能带来的问题。从互联网兴起开始，我们就不得不面对网络的不确定性：通讯消息可能的延迟、乱序、丢失。而应对不确定性问题最自然的解法就是冗余，通过大量节点来实现系统整体的安全性，避免单点故障，增强容错能力和抵御攻击的能力。正是基于此，才带来了大型分布式网络的蓬勃发展，而如何在不确定的网络和节点间寻找到某种确定性，协调众多节点间的一致性，正是分布式一致性算法需要解决的问题。能够应对故障类错误的CFT算法包括最经典的Paxos算法和更简单的Raft算法，可以在网络中正常节点超过一半的情况下保证算法的有效性。这类算法通常应用在环境可信的封闭网络中，协调几个到几十个节点间的一致性，如公司内部的分布式存储、分布式服务协议、分布式消息系统等。另外，也可以应用于由少数机构组成的需要授权才能访问的联盟链网络中。

然而，不确定的不止是网络与机器本身，还有控制网络中各个节点的人的行为。如何在可能存在捣乱者恶意篡改数据或攻击网络的情况下，保证分布式网络的一致性，正是拜占庭容错类算法BFT需要考虑的问题。BFT类算法中最常见的就是PBFT算法，可以在网络中正常节点超过1/3的情况下保证算法的有效性。即便如此，PBFT对于网络中恶意行为的应对能力仍然是有限的，另外其性能也会随着网络中节点数目的增多而显著下降。这些局限性也导致PBFT算法仅能用于环境较为可信的、有权限控制的网络中，协调几个到几十个节点间的一致性，比如联盟链场景中。

而在无权限控制的permissionless开放网络中，不确定性更加严峻，特别是网络节点背后的人的行为的不确定性。如何防止网络中的控制人之间通过腐败串通组成寡头，从而控制网络中的过半节点，达到控制、损害、攻击网络的目的，即是开放网络需要考虑的问题。从这一角度看，开放网络中的一致性还隐含了安全性的前提：即不仅要求节点间能够达成共识，还要求该共识确实是由节点众多控制人真实表达而形成的。而为了达到这种一致性与安全性，不仅需要实现物理硬件节点在结构上的decentralization，还需要尽可能地保证节点背后实际控制人的decentralization。为了实现这一点，需要保证任何人都可以随时部署运行网络协议而成为网络中的节点、可以随时进出网络；节点之间点对点通讯，无任何中心化控制节点；节点的角色是完全对等的，按照规则有公平的可能性参与记账。而如何协调开放网络中数量庞大的上万个节点间的行为，保证网络的一致性与安全性，即是公有链共识机制要解决的问题。其中，最典型的当属比特币首创的基于工作量证明的PoW共识机制，以及随后兴起的基于权益证明的PoS共识机制。这些共识机制不再局限于技术上的一致性本身，而是更多地引入了经济学和博弈论的思想，从经济和博弈的角度尽可能保证网络的一致性与安全性。

从传统的封闭分布式网络环境中的一致性，到有权限控制的联盟链场景中的一致性，再到无权限控制的公有链开放网络环境中的共识机制，面对的问题越来越复杂，应对的挑战也越来越严峻。从单纯的技术视角来看，其中对于consensus的研究是一脉相承的，这些一致性算法或共识机制同样也都受到传统分布式一致性理论研究中FLP impossibility和CAP theorem的制约。Paxos、Raft和PBFT都强调了fault tolerance与safety/consistency，而弱化了liveness与availability。而PoW与PoS则采用了全新的视角来考虑该问题，尽可能地保证了fault tolerance，以及liveness与availability，放弃了对于安全性与一致性确定性的追求，而仅仅以概率性的方式追求最终的safety与consistency。

另外，对于consensus的思考，也在不断深入，从单纯的节点间的数据一致性，到强调节点背后的人之间的共识与认同；从保证网络与硬件的可信，到尽可能地确保组成网络的节点背后的人的可信。虽然人与人之间的可信非常复杂，也超越了单纯的技术范畴，可喜的是我们已经走在路上，而目前在该领域正在进行的创新性的积极探索，也必将让世界变得更加可信。

注：本文篇幅较长、写作时间跨度较长、本人水平也有限，所参考资料可能有疏漏或个人理解偏差，欢迎大家指正、讨论、交流、建议，后续将进行更新。

码农公寓

引言