“区块链（Blockchain）技术是一种多方维护，通过密码学保证传输和安全，实现一致、难以篡改、防止抵赖的记账技术，称为分布式账本技术。而区块链技术框架中非常重要的一部分是共识机制，是在不可信的分布式环境下实现数据一致性的关键。”

【百度超级链学院】今天为大家奉上一篇超强万字干货，由深受超级链开发者喜爱的“小X姐姐”撰文的“区块链共识机制演进及应用”，带大家一同了解共识机制的发展脉络与未来趋势预测。

本文详细解析了PoW、PoS、PBFT…等主流共识机制各自特点及优劣；也从单一共识向可插拔共识、从链式共识向图式共识、从确定性共识向随机性共识，归纳总结出了共识机制的发展趋势。此外，还有更多的知识点和独家观点等你来发现哦～

概述

1.1 区块链技术2008年11月1日，中本聪发表了《比特币:一种点对点的电子现金系统》[1]一文，阐述了基于P2P网络技术、加密技术、时间戳技术、区块链技术等的电子现金系统的构架理念，标志着比特币的诞生。2009年初，中本聪搭建了以其论文为原型的网络——比特币。区块链技术是比特币网络背后的技术基础，是一种基础设施。区块链作为一种解决不可信分布式环境下能够以较低成本建立信任的计算模式和协作模式，正在悄然改变这个世界。1.2 共识机制由于区块链系统多数采用去中心化的分布式设计，节点是分散在各处，所以必须设计一套完善的制度，以维护系统的运作顺序与公平性，统一区块链的版本，并奖励提供资源维护区块链的使用者，以及惩罚恶意的危害者。这样的制度，必须依赖某种方式来证明，是由谁取得了一个区块链的打包权（或称记帐权），并且可以获取打包这一个区块的奖励；又或者是谁意图进行危害，就会获得一定的惩罚，这就是区块链系统的共识机制[2]。区块链是一个去中心化的分布式系统，在该系统中，所有的节点都是一个全副本，维护着全部的账本数据。这样，当某一个或多个节点故障时，用户可以从其他的节点读取数据。由于系统中有多个副本，如何保证副本之间的一致性是整个分布式系统的理论核心，下面会详细地向大家介绍传统分布式系统和区块链系统副本一致性问题。

传统分布式系统一致性问题

2.1 分布式一致性问题

从传统的集中式单节点结构，演变到分布式多节点结构，碰到的首个问题就是一致性的保障。如何保障副本之间的一致性是整个分布式系统的理论核心。

一致性是指分布式系统中的多个服务节点，给定一系列的操作，在约定协议的保障下，使它们对外界呈现的状态是一致的。换句话说，也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案（Proposal）达成一致。

一致性的要求，在分布式系统中，系统可以达成一致性需要满足以下三个要求：

有限性：达成一致的结果在有限的时间内完成。
约同性：不同节点最终完成决策的结果是相同的。
合法性：决策的结果必须是系统中某个节点提出来的。

一般地，非学术角度，分布式系统一致性主要包括以下三类：

强一致性（Strong）：数据a一旦写入成功，在任意副本任意时刻都能读到a的最新值。
弱一致性（Weak）：写入一个数据a成功后，在数据副本上可能读出来，也可能读不出来。系统不能保证多长时间之后每个副本的数据一定达成一致。
最终一致性（Eventually）：最终一致性是弱一致性的一种特例。写入一个数据a成功后，在其他副本有可能暂时读不到a的最新值，但在某个不一致的时间窗口之后保证最终能读到。不一致性窗口的大小依赖于以下几个因素：交互延迟、系统负载、复制协议的副本数。

2000年，Berkeley大学计算机科学家埃里克·布鲁尔提出了著名的CAP定理，指出对于一个分布式计算机系统，不可能同时满足以下三点[3]：

一致性（Consistency）：所有节点访问同一份最新的数据副本，读操作总是能读取到之前完成的写操作结果，满足这个条件的系统就符合我们前面对强一致性系统的定义。
可用性（Availability）：每次请求都能获取到非错的响应，但是不保证获取的数据为最新数据，读写操作在单台机器发生故障的情况下仍然能够正常执行，不需要等到故障的节点将数据迁移到新的节点。
分区容错性（Partition tolerance）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。

根据定理，分布式系统只能满足三项中的两项而不可能满足全部三项。理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设置为不可用，那么又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。随着系统规模逐渐变大，故障的发生会是一种常态，系统的设计必须要考虑容错（Fault Tolerant）。依据分布式系统的部署环境，容错主要包括两大类：一是可信环境下的分布式容错，即我们通常说的CFT（Crash Fault Tolerant）；二是不可信环境下的分布式容错，即我们通常说的BFT（Byzantine Fault Tolerant）。下面两节会详细向大家介绍一下两类环境下的分布式一致性问题和容错方案。

2.2 可信环境分布式一致性问题

传统的分布式系统中，所有服务器掌握在一个公司或者组织内部，系统没有恶意节点，所有节点都是可信的，这样的分布式系统我们称之为可信环境分布式系统TEDS（Trusted Environment Distributed System）。

可信环境分布式系统容错即CFT，该类系统中，只需要考虑单机故障、磁盘故障等故障恢复场景。可信环境分布式系统的一致性协议有很多，比较著名的包括两阶段提交协议、Paxos协议和Raft协议。2.2.1 两阶段提交协议（2PC）

两阶段提交协议2PC（Two-phase Commit）[4]是指在计算机网络以及数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法。2PC协议只有在所有节点都同意提交事务后才会提交事务[5]。2PC协议包括两类节点，分别是协调者（Coordinator）和参与者（Cohorts），节点间可以进行网络通信。该协议假设所有的节点都采用预写入日志的方式，且日志被写入后会持久化到可靠的存储设备上，这样即使系统故障，也不会丢失日志。该协议同时假设所有的节点不会永久性损坏，即使损坏后也可以恢复。2PC协议主要包括2个阶段：

提交请求阶段：

这个阶段，协调者会向所有参与者询问“是否可以执行提交”操作，同时会开始等待各参与者节点回复。参与着执行协调者的事务操作，将操作信息写入日志。如果参与的事务操作执行成功，则返回“同意”消息，否则回复“终止”消息。

提交执行阶段：

当第一个节点所有参与着都回复“同意”时，协调者会向所有节点发出正式“正式提交”操作请求，参与者节点正式完成操作，并释放整个事务处理期间占用的资源，然后参与者会向协调者发送“完成”消息。协调者收到所有节点反馈“完成后”，事务完成。当第一个阶段有任何一个参与者返回“终止”的消息，或者存在参与着操作超时，则协调者会向所有参与者发出“回滚操作”，协调者收到所有参与者返回“回滚完成”后取消事务。

图一：二阶段（2PC）提交协议

2PC协议在现实分布式系统一般都不采用，主要是由于其有一个显著的缺点，其事务的提交的过程中节点是处于阻塞状态的，及节点在等待其他节点返回时无法响应其他服务。并且如果出现参与者宕机或者无响应时，协调者需要通过超时机制来恢复，系统无法容错且低效。

2.2.2 Paxos协议

Paxos协议是Lamport于1989年的一篇论文[6]首次提出，由于该算法晦涩难懂，直到1998年该论文才得以发表。Lamport后续又发表了相关文章《Paxos Made Simple》和《Fast Paxos》[7][8]，因此大家习惯性地将这类算法称为Paxos算法。

Paxos算法自问世以来就垄断了可信环境分布式一致性算法。众多分布式系统都采用了该算法实现分布式一致性，如Google的Spanner、Chubby、Megastore，还有开源的ZooKeeper等。Paxos协议将系统中节点分为三类：

提议者（Proposer）: Proposer 负责提出提案，包括提案标号和提案内容。
决策者（Acceptor）：参与提案的决策，Acceptor收到提案后会根据情况决策是否要接受提案，若足够多的Acceptor接受提案，则该提案3通过。
决策学习者（Learner）：不参与提案的提出或者决策过程，Proposer收到足够多的Acceptor同意后，会将通过的决议发送给所有的Learner。

Paxos算法主要包括两部分，为决议的达成和决议的发布，其中决议的达成又包括2个阶段，整个过程如下图所示：

图二：Paxos算法

上述图描述了Paxos算法的流程，如下所述：

决议提出与达成：
准备阶段（Prepare）：Proposer选择一个提案标号Proposer ID并将prepare消息发送给Acceptors中的一个多数；Acceptor收到Prepare的消息后，如果提案标号大于它接受的所有历史提案的标号，就回复接受，并承诺不再接受提案标号小于该标号的提案。
批准阶段（Accept）：当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，Acceptor在不违背其他提案的前提下对收到的Propose请求进行Accept处理。Proposer在收到多数节点的accept消息后，提案就已经达成。
决议的发布（Publish）：当提案已经达成后，Proposer会将该提案发送给所有的Learner。

2.2.3 Raft协议Raft也是一种可信环境分布式一致性算法[9]。相比于Paxos算法，Raft更加容易理解和容易实现，他强化了领导人的概念，将整个分布式一致性问题抽象成了两大阶段，领导人选举（Leader Election）和日志复制（Log Replication）。Raft协议中每个节点可能会处于三种状态：

领导者状态（Leader）：Leader负责处理客户端的请求并将事务同步给Follwer。
跟从者（Follower）：接受Leader的更新事务请求，并写入本地的日志文件。
候选状态（Candidate）: 当Follower一段时间内没有接收到Leader的心跳，会认为Leader不可用，此时副本会进入Candidate状态，并开始新一轮选主，直到新的主被选择出来。

其状态转换图如下所示：

图三：Raft选主

第一个阶段选出主后，会进入第二个阶段Log replication，这个阶段Leader就开始处理客户端的请求，每一个请求包含一个被副本状态机执行的命令。Leader将该命令作为一个新的记录追加在日志结尾。同时调用其他节点的追加记录的接口，将操作同步给其他副本。如果某个Follower宕机、运行地很慢或者网络丢包，那么Leader会一直重试直到副本与与Leader状态一致。

2.3 不可信环境分布式一致性问题

当一个分布式系统中节点的维护方不属于某个公司单独所有，节点的参与方的利益互不相同时，就可能会出现节点不遵循规则，对系统实施作恶，这样的环境就是一个不可信的环境。其中作恶的节点我们叫做拜占庭节点（Byzantine node），这样环境下的分布式系统我们称之为UTEDS（Untrusted Environment Distributed System）

不可信环境分布式系统容错即BFT（Byzantine-Fault-Tolerant），该类系统中，我们需要允许部分节点作恶、欺骗或者伪造消息。不可信环境分布式系统一致性算法典型的有BFT、PBFT和SBFT。下节会向大家介绍一下著名的拜占庭问题及相应算法。区块链系统是一个不可性环境的分布式系统，自2008年比特币系统创建以来，一批又一批的学者和科创团队投入该领域分布式一致性问题的研究，创新性地引入了激励以及博弈的思想来促使系统达成一致。经典的算法有PoW、PoS、DAG、VRF等，这些内容将在下一章进行详细地介绍。

2.3.1 拜占庭将军问题及算法

拜占庭问题是由Lamport于1982年[10]提出的分布式对等网络通信的容错问题。在分布式系统中，所有节点通过通信交换达成共识，按照相同的策略协同。但是系统中有时存在节点由于各种原因，发送错误的信息到网络中，从而破坏系统的一致性。

拜占庭问题的原始描述是：N个将军被分隔在不同的地方，诚实的将军希望通过某种协议达成命令的一致。但是其中一些背叛的将军会通过发送错误的消息阻挠的诚实的将军达成一致。Lamport证明了在将军总数大于3f，背叛者为f或者更少时，忠诚的将军可以达成命令上的一致。拜占庭问题的证明:证明前，首先看3个概念[11]：

仲裁（Quorum）：只作出一次决策至少需要的得到的同意的票数。
活跃度（Liveness）：是指在共识决策的过程中保持活跃的节点，不能出现卡死或者无响应的状态。
安全性（Safty）: 是指执行过共识算法后，节点能够达成一致。

证明过程如下，假设系统中共有N个节点，f个拜占庭节点，仲裁组节点为Q。

那么要满足Liveness，则Q<=N-f，如果Q>N-f，那么f个拜占庭节点都作恶时，算法无法继续运行。
为了满足Safety，则需要满足2Q-N>f，即任意两个仲裁组的交集一定要有非拜占庭节点；
则 N+f<2Q<=2N-2f 且N>3f；
当N=3f+1时，Q>=2f + 1;

根据以上证明，可以得出在一个拜占庭将军问题中，总节点为N的环境下，最多只能f个拜占庭节点，且N>=3f+1。

2.3.2 PBFT

传统的BFT算法复杂度太高，Castro和Liskov于1999年提出了PBFT（Practical Byzantine Fault Tolerance）实用拜占庭容错算法[12]，该算法能够实现拜占庭容错，同时能够大大提升拜占庭容错的效率。

PBFT是一种基于副本状态机复制的算法。将不可信环境一致性达成分成3个阶段，分别是预准备、准备和确认。如下图所示：

图四：PBFT算法

上图中对于每个请求的处理过程如下：

请求（request）：客户端c向服务器0发起一个请求；
预准备阶段（pre-prepare）：该阶段，服务器0分配一个整数n给收到的请求，并将消息广播给所有的副本节点，同时将消息添加到日志的结尾，消息格式为，其中v表示发送消息的视图、m表示客户端发送的消息，d表示消息的摘要。副本收到消息后会进行消息的签名验证、消息摘要验证、视图验证和水平线验证，验证通过的消息予以接收。
准备阶段（prepare）：当副本接受了消息时，就会进入prepare阶段，这个阶段，副本会广播消息，同时将预准备消息和准备消息写入日志。当所有正常节点对统一视图v的请求序号n达成一致时，会进入确认阶段。
确认（commit）：该阶段，副本会广播。其他副本会进行消息验证和确认，当确认后，会将消息写入日志。
返回（Reply）：对客户端C进行反馈。

PBFT能够有效地实现拜占庭容错，且由于其将容错分为明确的3个阶段，工程上更容易实现。但是他有个比较大的缺点是系统中的节点规模不能很大，因为系统中的每个节点都要频繁地和其他说有节点进行通信，当系统节点规模太大后，系统将无法运行。

2.3.3 SBFT

为了优化PBFT在扩展上的不足，业界也在不断地进行探索。2018年GG Gueta提出SBFT（Scalable Byzantine Fault Tolerance）[13]，旨在提高BFT的扩展性。SBFT主要从以下四点进行了优化：

降低通信：通过使用收集器，副本将消息发送给收集器，收集器将消息广播给所有节点，同时通过使用阈值前面，将收集器消息大小从线性减少到常量;
添加快速路径：在所有副本都非故障且同步的时候，SBFT使用一种乐观的快速路径；
将客户端通信从f+1 减到1：SBFT通过添加一个使用收集器聚合执行阈值签名的阶段，并给每个客户端发送一个带签名的消息，从而将每个客户端的线性成本降低为一条消息；
通过冗余服务器进行快速路径；

SBFT在算法的流程如下图所示：

图五：原理图消息流

客户端向主服务器发送操作请求；
主服务器收集客户端请求，创建决策块，并将此块作为预准备消息转发给副本；
副本使用σ(3f+c+1)-阈值签名对决策块进行签名，并将签名共享消息发送给C-收集器；
每个C-收集器收集共享签名，并为决策块创建一个简洁的完全提交证明，并将其发送回副本，这种单消息提交证明具有固定的大小开销，包含单个签名，并且足以副本提交；
一旦副本接受到提交证明，它会提交决策区块，并启动执行协议；
当副本在提交决策区块前，他需要完成序列块的执行，并对新的状态进行阈值签名，然后将其发送给E-收集器；
每个E-收集器收集签名，并创建决策块的完整证明，然后，它向副本发送一个证书，表明状态是持久的，向客户机发送一个证书，表明其操作已被执行完毕。

目前SBFT已经实现了最大209个节点的测试网络。相比于PBFT，在扩展性上提高了2倍。

2.3.4全球部署不可信环境

一般的公链系统，如比特币、以太坊节点数都超过了1W个。在这样的系统中PBFT和SBFT都无法很好地工作，这样大规模的不可信环境下的分布式一致性问题近10年来也是区块链系统的一个研究热点。区块链创造性地引入了激励的机制和博弈的思想来促使大规模不可信环境中的节点达成一致，下面一章将详细介绍比较著名的共识协议，包括PoW、PoS、DAG、VRF，并会简要介绍一下使用该共识的应用。

区块链共识机制及其应用

共识机制是区块链系统各节点达成一致的协议，对交易的进行合法性和一致性确认。早期的区块链系统采用PoW（Proof of work），后续随着区块链的发展、出现了PoS（Proof of Stake）、DAG等一系列的算法。下面这个图直观地向大家展示了各个共识协议的使用应用。后续各小节会详细进行介绍各个协议，并对其优缺点进行简要介绍。

图六：共识协议应用项目

3.1PoW（Proof of work）

1993年，Pow[14]思想首次被Cynthia Dwork在论文《Pricing via Processing or Combatting Junk Mail》中被提出。该算法用于解决垃圾邮件的问题，要求邮件发送者需要计算某个数学难题以此来提高邮件发送的成本，从而减少垃圾邮件。

2008年中本聪发表了文章[1]标志着区块链的诞生，次年初，全球第一个区块链系统比特币诞生。比特币采用的是PoW共识算法来保证分布式网络记账的一致性，这是迄今为止最为安全的公链共识算法。在比特币网络中所有节点都可以参与竞争挖矿。如果想要生成一个区块并写入账本中，则需要成为网络中最先解出比特币网络中的工作量证明谜题的节点。在比特币中，PoW算法致力于寻找一个值，使得它SHA256的hash值以若干个0开始。随着0的个数的增加，算出目标hash值的工作量耗费会呈指数上升，但是可以只通过一次hash运算就可以验证谜题。求解谜题的公式如下：

通过修改block中的nonce值，直到算出的block的hash值符合0的个数的要求。一旦CPU努力使其满足工作证明时，在不进行重做的情况下，区块无法被改变。由于后面的区块会连接到前一个区块，如下图六所示，修改一个块，需要将后面所有块的工作量都重做一遍。

图七：区块链式结构示意图

PoW解决了群体决策中的确定代表问题。如果绝大数的是基于IP的投票，那么任何能够分配多个IP的人都可能破坏它。PoW强调One-CPU-One-Vote。大多数决策是采用最长链的方法，因为这表明工作量投入的最大，如果绝大数节点都是善良的，那么诚实链会长成最快的链，超过任何竞争的链。攻击者如果想改变一个区块，那么需要修改该块后所有区块，并且能够长成最长的诚实链，比特币网络在设计的时候考虑了博弈的思想，生产一个合法的区块需要付出金钱代价，这使得攻击者需要掌握足够的算力才能发起攻击，掌握足够的算力是非常昂贵的，这使得发起攻击很难获利。为了避免硬件加速等因素导致区块打包过快，PoW会依据出块的时间调整打包区块的难度。如果生成速度太快，难度就会增加。PoW算法是唯一一个被成功验证的公链算法，安全性最高。PoW算法的缺点主要有两点，一是能耗大，需要消耗巨大的电力。二是效率低，比特币平均10分钟才打包一个区块，系统的吞吐低，而且也无法盲目地通过缩短出块时间或者增加区块大小来提高系统吞吐，缩短出块时间会导致生成区块速度太快，而分叉很多，会造成系统频繁回滚从而降低性能，目前比特币的区块大小在1M左右，增大区块大小，可能会导致区块在网络中传播的效率降低。

3.2 PoS（Proof of stake）

2011年Quantum Mechanic[15]首次提出了PoS算法。在基于PoS的加密货币中，下一个区块的创建者是通过随机选择和财富或币龄（即股份）的各种组合来选择的。PoS必须有定义任何区块下一个有效区块的方法，不能仅仅按照账户余额，这样会造成富有的人越富有。PoS的发展主要经历了3个阶段，第一阶段是以Peercoin为代表的的基于币龄的PoS，第二个阶段是以黑币为代表的基于币数的PoS，第三阶段是像EOS、XuperChain这样为代表的DPoS。

3.2.1基于币龄的 PoS

Peercoin是Sunny King, Scott Nadal于2012年从中本聪所创造的BTC衍生出来的一种P2P的电子密码货币[16]，以PoS取代PoW来维护网络安全,是基于币龄(coin age)并由通过与BTC类似的由每个节点散列运算产生的,只是其搜索空间被限制了。

币龄(Coin age)，定义为货币的持有时间段，假设a收到10币，并持有了5天，那么就说明了a积攒了50币龄。一笔交易所消耗的币龄可被视为PoS的一种形式。PoS下生成区块如下图所示：

图八：PoS CoinStake的结构

这种新型区块里PoS是一种特殊的交易称利息币(coinstake)，类似于BTC中的coinbase。在利息币(coinstake) 交易中,区块持有人可以消耗他的币龄获得利息,同时获得为网络产生一个区块和用PoS造币的优先权。利息币的第一个输入被称为核心(Kernel),需要符合某一Hash目标协议。PoS区块的产生具有随机性，这一过程与PoW相似。但有一个重要的区别在于, PoS的随机散列运算是在的搜索空间比PoW小，在hash/未消费钱包的输出*秒,而不是象PoW那样在无限制的空间里寻找,因此无需大量的能源消耗。其生成区块可以用下面这个公式表示：

Peercion对可以参与挖矿的币龄做了限制，大于30天的币才可以参与挖矿，币龄越大、币数越多的节点越容易挖出下一个区块。然而一旦一个币用来挖出一个区块，它的币龄就会归零，需要等到30天以上才能再进行挖矿。此外为了避免币龄太老的节点控制网络，币龄最大不会超过90天。基于币龄的PoS算法，相比于PoW更加环保，且由于挖矿不完全依赖与CPU，使得系统内在的安全系数提升，黑客无法通过系统外的力量进行攻击。但是由于Peercoin中仅允许币天大于30天的币才可以参与挖矿，所以导致节点的在线率特别低。很多节点会等待快要到币龄才开启节点。

3.2.2 基于币数的PoS

前面提到的基于币龄的PoS有几个潜在的安全风险，币龄会被恶意利用已发起双花攻击。而且，由于币龄的存在，诚实节点会通过定期开启节点的方式来积攒币龄。为了进一步提供PoS系统的安全性，提升节点的在线时长。2014年Pavel Vasin提出了黑币，其PoS算法也被称为PoS2.0[17]。相比于以往的PoS，黑币的PoS协议变化主要有四点，如下所示：

hash计算: 执行PoS最安全的方式是让尽可能多的节点在线。参与的节点越多，发生51%攻击的可能性越低，实际网络中通过这些节点确认事务的时间越快。因此，黑币取消了hash计算公式中币龄参数，新系统计算谜题的公式变成如下：

改变权益修正因子：为了减少预计算攻击的可能性，权重修正因子在每一次修正因子间歇时都会改变，以便对将要用来下一个权益累积证明的时间戳的计算结果进行更好的模糊处理。
区块时间戳规则：通过修改区块的时间戳以更好地使用PoS。预期的出块时间从最初的60s增加到粒度匹配的时间。假设节点有一个外部时间，假设节点时间与系统共识时间偏离太多，这个节点将被孤立。区块时间戳的修改规则如下：

图九：区块时间修正规则

hash函数：黑币采用SHA256d算法，SHA256d是将SHA256算2遍，这种算法如下所示，

通过上述的优化，黑币将可能的攻击降到最小，并能够显著提升节点的在线率。使得PoS在进一步扩大节点范围的同时能够有效地降低系统风险，提高系统的安全性。

3.2.3 DPoS

DPoS是2014年4月由Bitshares 的首席开发者 Dan Larimer提出的一种基于代理人机制的PoS算法[18]。DPoS算法一般每隔预设时间长度（一个区块周期）选择N个候选区块生成节点，确定各候选区块生成节点的区块生成顺序，并将一个区块生成周期所需的区块生成时间均分为N个时间段，再按照区块生成顺序将各时间段分配给各候选区块生成节点。各个候选区块生成节点会按照预设的顺序协同出块；所以DPoS算法主要包括两个阶段，第一阶段是候选人的选举，第二个阶段是轮值。第一阶段是候选人选举，在该阶段，用户可以给候选人进行投票，候选人一般地可以通过提名的方式限制在指定范围内，也可以不进行限制。每到一定的时间系统会进行矿工选举，得票高的节点当选为下一轮的矿工。第二阶段是轮值阶段，在该阶段，第一阶段选出的节点会按照既定的顺序轮流出块，协同出块。DPoS和上述的共识协议相比大幅缩短了打包区块的时间，大大增加了系统的处理能力，交易确认时间降低到秒级。百度的超级链实现了一种改进的DPoS[19]，XuperChain 自主研发实现了一套 DPoS 共识，我们称之为 TDPoS。依据这种算法，全网持有通证的人都可以给候选人投票。TDPoS 的参数包括每轮的 proposer 个数、出块间隔、节点每轮出块个数等，在创建平行链的时候可以指定，也可以通过提案机制升级。例如，如果配置的参数为每轮21个节点、出块间隔为3s、每个节点每轮出块个数为 200 个，则每轮的时间为 3.5h。传统的DPoS依赖于相对同步的网络，TDPoS创造性地引入GPS加原子钟的方式来修正节点间的时间同步问题。

3.3DAG（Directed Acyclic Graphs）

DAG第一次被提出与区块链结合是在Nxt社区，为的是解决区块链的效率问题。DAG是一种图状的区块链。由于其独特区块结构，DAG内在地支持高可扩展性，得到了广泛的应用。

从根本上说，任何区块链系统都具有线性结构，因为区块是依次添加到链中的。这使得相比于并行向链中添加区块，线性区块链在本质上是非常缓慢的。但是对于DAG而言，每个区块和交易只需数个前期区块得到确认，就可以并行地添加到区块和交易中。所以DAG在扩展性上给人以很大的想象空间。IOTA和Byteball项目都使用了基于DAG的区块链应用，进一步地，他们提出了Blockless无区块的概念，让每一个事务直接参与维护全网的交易顺序。这样交易发起后直接跳过了打包的阶段，直接融入全网，达到blockless的目的，同时由于省去了打包的时间，效率会进一步地提升。基于DAG的共识主要有以下几个优点：

交易速度快：DAG 的并行化结构和blockless的设计会提高系统的效率，交易速度大大提升。
无需挖矿：由于不需要区块打包，故无需挖矿；
无手续费：由于blockless的项目中没有矿工进行区块打包，所以不需要付手续费给矿工。

3.4VRF（Verifiable Random Function）

2016年, 图灵奖得主、MIT 教授Sivio Micali提出了一种称为 Algorand的快速拜占庭容错共识算法[20][21]。该算法是基于VRF，利用密码抽签技术选择共识过程的验证者和领导者, 并通过其设计的BA* 拜占庭容错协议对新区块达成共识. Algorand只需要极小的计算量且不易分叉, 被认为是实现区块链去中心化、可延展性和安全性不可能三角的区块链项目。

VRF是可验证随机数，所谓的可验证的随机数可以看做一个随机预言机，可以通过任意一个输入获得一个随机数输出，主要有两点：

对于不同的Input,Output的值是随机的，但是均匀地分布在值域范围内。
对于相同的Input，他的Output是一定是相同的。

VRF的过程主要包括四个步骤：

VRFgen：随机生成密钥，生成一对非对称加密密钥（一对公私钥）；
VRFval：生成随机数输出；
VRFproof：随机数输出的零知识证明；
VRFver：其他节点收到输入和零知识证明后，结合生成随机数的节点的公私钥，对随机数进行验证。

通过VRF，Alogrand实现了加密排序，排序需要一个角色参数，这样不同的用户可能选择不同的角色，例如，用户可能被选为区块生产者，也可以被选为委员会成员。Alogrand通过一个阈值来确定每个角色选择的用户数。加密排序算法如下所示：图十：加密排序算法

验证加密排序的伪代码如下所示，通过相同的结构验证用户是否被选中，函数返回所选子用户的数量，若没有选出用户，则返回0。

图十一：验证加密排序

Alogrand通过VRF实现了矿工选择的不可预测性，实现了区块链的去中心化；并且每个区块随机产生，不需要竞争出块，提升了系统的扩展性；PoW、PoS当恶意节点积攒到一定数量时就可以控制网络，一般地是通过博弈的方式来实现网络稳定性和安全性保障，Alogrand随机产生区块生产者，所以即使是恶意节点，也无法随意控制网络。

区块链共识机制发展趋势

自从2018年中本聪发布比特币以来，区块链系统已经经历了10年的发展。共识算法的发展也进入了百花齐放的时期。纵观区块链共识协议的发展过程，主要体现以下几大趋势。

4.1 从单一共识到可插拔共识

早期的区块链系统，一般采取单一的共识机制，比如BTC的PoW、Peercoin的PoS等、EOS的DPoS等。

在当前的技术背景下，没有哪一种共识机制是完美无缺的，每一种共识机制都有其优点和缺点，不同的应用场景可能需要不同共识机制。在区块链解决方案中，应该实现兼容多种共识算法，在实际业务落地中有选择性的使用一种最合适的共识机制，甚至整个网络具备让开发者自定义共识机制的能力。未来可插拔的共识机制可能是未来发展的主要方向。

百度超级链XuperChain实现了可插拔共识机制，目前已经支持Pow，DPoS，Pool和Raft等共识，同时还允许用户通过该可插拔共识框架定义符合其业务特征的共识机制。

Hyperledger的 Fabric也实现了可插拔的共识机制，目前支持的共识Solo、Kafka、SBFT。

4.2 从链式共识到图式共识

一般地，区块链是一种链式结构，区块只能沿着一条链生长，效率较低。随着共识的发展，有人提出使用DAG的方式，所谓DAG就是有向无环图。基于这种思想，可以有很多新的方式，比如可以并发地进行区块打包，从而提高区块链的扩展能力。除了前面提到的IOTA和Byteball使用了基于DAG的共识协议。图灵奖得主、清华大学交叉信息研究院院长姚期智参与创立的区块链项目 Conflux也是基于DAG的思想，Conflux的理念设计容许不同区块同时生成，并运用基于有向无环图（directed acyclic graph, DAG）概念的排序算法来避免分叉的问题，先決定所有区块的整体排序，再決定衍生的交易排序。

4.3 从确定性共识到随机共识

前面所述的共识，为了提高区块链系统的吞吐能力，一定程度上降低了其去中心化的程度，一定程度上降低了系统的安全性。Alogrand项目出现，使得共识由确定性向随机性发展，在该共识中，很多节点都具有潜在的控制权，下一个矿工的是由加密排序函数随机产生，在这种变化下，事实上虽然只有少数节点参与共识，但是由于参与共识的节点在系统中游走，无法提前预测，从而实现系统的安全性。除了上面提到的Alogrand使用了基于VRF的共识协议，Difinity和TASchain也都使用了基于VRF的共识机制，未来该趋势上相信会有更多适用于工业级的共识协议诞生。

总结与展望

本文从分布式一致性问题切入，分别讨论了可信环境分布式系统和不可信环境分布式系统的一致性问题。在可信环境分布式系统一致性问题中，介绍了经典的2PC、Paxos和Raft协议。在不可信环境分布式系统一致性问题中，介绍了拜占庭教军问题及PBFT算法，并介绍了公链环境下新型一致性协议（即区块链共识协议）及应用，主要包括PoW、PoS、DAG和VRF。最后本文总结了区块链的发展趋势，主要体现三大趋势，从单一共识向可插拔共识、从链式共识向图式共识、从确定性共识向随机性共识。区块链是一个不可信环境分布式系统，区块链共识是不可信环境分布式系统一致性的一个重要的研究方向。近年来，区块链共识也百花齐放，各种改进算法争相被提出。本文讨论的共识算法只是其中的一个子集。未来，随着区块链技术的进一步发展，尤其是伴随着底层账本结构的进一步优化，势必会涌现出更多的新兴的共识算法，本文提到的IOTA的基于DAG的共识只是其中一种。同时，随着技术的进一步深入，区块链共识的评估标准也一定会进一步规范。

参考资料

[1].SatoshiNakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System,2008.[2].wikipedia,https://zh.m.wikipedia.org/zh-hans/%E5%85%B1%E8%AD%98%E6%A9%9F%E5%88%B6,2008.[3].wikipedia,https://en.wikipedia.org/wiki/CAP_theorem,2010.[4].wikipedia,https://en.wikipedia.org/wiki/Two-phase_commit_protocol,2004.[5].exploredatabase,http://www.exploredatabase.com/2014/07/two-phase-commit-protocol-in-pictures.html,2014.[6].LeslieLamport, The Part-Time Parliament, 2000,[7].LeslieLamport, Paxos Made Simple, 2001.[8].LeslieLamport, Fast Paxos, 2006.[9].DiegoOngaro, John Ousterhout, In Search of an Understandable Consensus Algorithm,2014.[10].LeslieLamport, The Byzatine Generals Problem, 1982.[11].MICHAEL J.FISCHER, NANCY A. LYNCH, Impossibility of Distributed Consensus with One FaultyProcess, 1985.[12].MiguelCastro,Barbara Liskov, Practical Byzantine Fault Tolerance, 1999.[13]. GG Gueta, SBFT:a Scalable and Decentralized Trust Infrastructure, 2019.[14].CynthiaDwork, Pricing via Processing or Combatting Junk Mail.[15].bitcoin, https://en.bitcoin.it/wiki/Proof_of_Stake,2012.[16].peercoin,https://docs.peercoin.net/#/proof-of-stake, 2012.[17].PavelVasin, BlackCoin’s Proof-of-Stake Protocol v2, 2014[18].bitshares,http://docs.bitshares.org/bitshares/dpos.html.[19].谭待，肖伟等, 百度区块链白皮书V1.0, 2018.[20].SilvioMicali, Michael Rabin,Salil Vadhan, Verifiable Random Functions, 1999.[21].Jing Chen,Silvio Micali, ALGORAND, 2017.