“区块链（Blockchain）技术是一种多方维护，通过密码学保证传输和安全，实现一致、难以篡改、防止抵赖的记账技术，称为分布式账本技术。而区块链技术框架中非常重要的一部分是 共识机制，是在不可信的分布式环境下实现数据一致性的关键。”
【百度超级链学院】今天为大家奉上一篇 超强万字干货，由深受超级链开发者喜爱的“小X姐姐”撰文的“ 区块链共识机制演进及应用”，带大家一同了解共识机制的发展脉络与未来趋势预测。
本文详细解析了PoW、PoS、PBFT…等主流共识机制各自特点及优劣；也从单一共识向可插拔共识、从链式共识向图式共识、从确定性共识向随机性共识，归纳总结出了共识机制的发展趋势。此外，还有更多的知识点和观点等你来发现哦～
2008年11月1日，中本聪发表了《比特币:一种点对点的电子现金系统》[1]一文，阐述了基于P2P网络技术、加密技术、时间戳技术、区块链技术等的电子现金系统的构架理念，标志着比特币的诞生。2009年初，中本聪搭建了以其论文为原型的网络——比特币。区块链技术是比特币网络背后的技术基础，是一种基础设施。区块链作为一种解决不可信分布式环境下能够以较低成本建立信任的计算模式和协作模式，正在悄然改变这个世界。
由于区块链系统多数采用去中心化的分布式设计，节点是分散在各处，所以必须设计一套完善的制度，以维护系统的运作顺序与公平性，统一区块链的版本，并奖励提供资源维护区块链的使用者，以及惩罚恶意的危害者。这样的制度，必须依赖某种方式来证明，是由谁取得了一���区块链的打包权（或称记帐权），并且可以获取打包这一个区块的奖励；又或者是谁意图进行危害，就会获得一定的惩罚，这就是区块链系统的共识机制[2]。
区块链是一个去中心化的分布式系统，在该系统中，所有的节点都是一个全副本，维护着全部的账本数据。这样，当某一个或多个节点故障时，用户可以从其他的节点读取数据。由于系统中有多个副本，如何保证副本之间的一致性是整个分布式系统的理论核心，下面会详细地向大家介绍传统分布式系统和区块链系统副本一致性问题。
从传统的集中式单节点结构，演变到分布式多节点结构，碰到的问题就是一致性的保障。如何保障副本之间的一致性是整个分布式系统的理论核心。
一致性是指分布式系统中的多个服务节点，给定一系列的操作，在约定协议的保障下，使它们对外界呈现的状态是一致的。换句话说，也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案（Proposal）达成一致。
一致性的要求，在分布式系统中，系统可以达成一致性需要满足以下三个要求：
有限性：达成一致的结果在有限的时间内完成。
约同性：不同节点最终完成决策的结果是相同的。
合法性：决策的结果必须是系统中某个节点提出来的。
一般地，非学术角度，分布式系统一致性主要包括以下三类：
强一致性（Strong）：数据a一旦写入成功，在任意副本任意时刻都能读到a的最新值。
弱一致性（Weak）：写入一个数据a成功后，在数据副本上可能读出来，也可能读不出来。系统不能保证多长时间之后每个副本的数据一定达成一致。
最终一致性（Eventually）：最终一致性是弱一致性的一种特例。写入一个数据a成功后，在其他副本有可能暂时读不到a的最新值，但在某个不一致的时间窗口之后保证最终能读到。不一致性窗口的大小依赖于以下几个因素：交互延迟、系统负载、复制协议的副本数。
一致性（Consistency）：所有节点访问同一份最新的数据副本，读操作总是能读取到之前完成的写操作结果，满足这个条件的系统就符合我们前面对强一致性系统的定义。
可用性（Availability）：每次请求都能获取到非错的响应，但是不保证获取的数据为最新数据，读写操作在单台机器发生故障的情况下仍然能够正常执行，不需要等到故障的节点将数据迁移到新的节点。
分区容错性（Partition tolerance）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。
传统的分布式系统中，所有服务器掌握在一个公司或者组织内部，系统没有恶意节点，所有节点都是可信的，这样的分布式系统我们称之为可信环境分布式系统TEDS（Trusted Environment Distributed System）。 可信环境分布式系统容错即CFT，该类系统中，只需要考虑单机故障、磁盘故障等故障恢复场景。 可信环境分布式系统的一致性协议有很多，比较著名的包括两阶段提交协议、Paxos协议和Raft协议。
提交请求阶段：
提交执行阶段：
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算法的流程，如下所述：
决议提出与达成：
准备阶段（Prepare）：Proposer选择一个提案标号Proposer ID并将prepare消息发送给Acceptors中的一个多数；Acceptor收到Prepare的消息后，如果提案标号大于它接受的所有历史提案的标号，就回复接受，并承诺不再接受提案标号小于该标号的提案。
批准阶段（Accept）：当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，Acceptor在不违背其他提案的前提下对收到的Propose请求进行Accept处理。Proposer在收到多数节点的accept消息后，提案就已经达成。
决议的发布（Publish）：当提案已经达成后，Proposer会将该提案发送给所有的Learner。
领导者状态（Leader）：Leader负责处理客户端的请求并将事务同步给Follwer。
跟从者（Follower）：接受Leader的更新事务请求，并写入本地的日志文件。
候选状态（Candidate）: 当Follower一段时间内没有接收到Leader的心跳，会认为Leader不可用，此时副本会进入Candidate状态，并开始新一轮选主，直到新的主被选择出来。
其状态转换图如下所示：
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;
2.3.2 PBFT
传统的BFT算法复杂度太高，Castro和Liskov于1999年提出了PBFT（Practical Byzantine Fault Tolerance）实用拜占庭容错算法[12]，该算法能够实现拜占庭容错，同时能够大大提升拜占庭容错的效率。 PBFT是一种基于副本状态机复制的算法。将不可信环境一致性达成分成3个阶段，分别是预准备、准备和确认。如下图所示：请求（request）：客户端c向服务器0发起一个请求；
预准备阶段（pre-prepare）：该阶段，服务器0分配一个整数n给收到的请求，并将消息广播给所有的副本节点，同时将消息添加到日志的结尾，消息格式为，其中v表示发送消息的视图、m表示客户端发送的消息，d表示消息的摘要。副本收到消息后会进行消息的签名验证、消息摘要验证、视图验证和水平线验证，验证通过的消息予以接收。
准备阶段（prepare）：当副本接受了消息时，就会进入prepare阶段，这个阶段，副本会广播消息，同时将预准备消息和准备消息写入日志。当所有正常节点对统一视图v的请求序号n达成一致时，会进入确认阶段。
确认（commit）：该阶段，副本会广播。其他副本会进行消息验证和确认，当确认后，会将消息写入日志。
返回（Reply）：对客户端C进行反馈。
PBFT能够有效地实现拜占庭容错，且由于其将容错分为明确的3个阶段，工程上更容易实现。但是他有个比较大的缺点是系统中的节点规模不能很大，因为系统中的每个节点都要频繁地和其他说有节点进行通信，当系统节点规模太大后，系统将无法运行。
降低通信：通过使用收集器，副本将消息发送给收集器，收集器将消息广播给所有节点，同时通过使用阈值前面，将收集器消息大小从线性减少到常量;
添加快速路径：在所有副本都非故障且同步的时候，SBFT使用一种乐观的快速路径；
将客户端通信从f+1 减到1：SBFT通过添加一个使用收集器聚合执行阈值签名的阶段，并给每个客户端发送一个带签名的消息，从而将每个客户端的线性成本降低为一条消息；
通过冗余服务器进行快速路径；
客户端向主服务器发送操作请求；
主服务器收集客户端请求，创建决策块，并将此块作为预准备消息转发给副本；
副本使用σ(3f+c+1)-阈值签名对决策块进行签名，并将签名共享消息发送给C-收集器；
每个C-收集器收集共享签名，并为决策块创建一个简洁的完全提交证明，并将其发送回副本，这种单消息提交证明具有固定的大小开销，包含单个签名，并且足以副本提交；
一旦副本接受到提交证明，它会提交决策区块，并启动执行协议；
当副本在提交决策区块前，他需要完成序列块的执行，并对新的状态进行阈值签名，然后将其发送给E-收集器；
每个E-收集器收集签名，并创建决策块的完整证明，然后，它向副本发送一个证书，表明状态是持久的，向客户机发送一个证书，表明其操作已被执行完毕。
目前SBFT已经实现了最大209个节点的测试网络。相比于PBFT，在扩展性上提高了2倍。
一般的公链系统，如比特币、以太坊节点数都超过了1W个。在这样的系统中PBFT和SBFT都无法很好地工作，这样大规模的不可信环境下的分布式一致性问题近10年来也是区块链系统的一个研究热点。区块链创造性地引入了激励的机制和博弈的思想来促使大规模不可信环境中的节点达成一致，下面一章将详细介绍比较著名的共识协议，包括PoW、PoS、DAG、VRF，并会简要介绍一下使用该共识的应用。
共识机制是区块链系统各节点达成一致的协议，对交易的进行合法性和一致性确认。早期的区块链系统采用PoW（Proof of work），后续随着区块链的发展、出现了PoS（Proof of Stake）、DAG等一系列的算法。下面这个图直观地向大家展示了各个共识协议的使用应用。后续各小节会详细进行介绍各个协议，并对其优缺点进行简要介绍。
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努力使其满足工作证明时，在不进行重做的情况下，区块无法被改变。由于后面的区块会连接到前一个区块，如下图六所示，修改一个块，需要将后面所有块的工作量都重做一遍。
2011年Quantum Mechanic[15]首次提出了PoS算法。在基于PoS的加密货币中，下一个区块的创建者是通过随机选择和财富或币龄（即股份）的各种组合来选择的。PoS必须有定义任何区块下一个有效区块的方法，不能仅仅按照账户余额，这样会造成富有的人越富有。PoS的发展主要经历了3个阶段，第一阶段是以Peercoin为代表的的基于币龄的PoS，第二个阶段是以黑币为代表的基于币数的PoS，第三阶段是像EOS、XuperChain这样为代表的DPoS。
hash计算: 执行PoS最安全的方式是让尽可能多的节点在线。参与的节点越多，发生51%攻击的可能性越低，实际网络中通过这些节点确认事务的时间越快。因此，黑币取消了hash计算公式中币龄参数，新系统计算谜题的公式变成如下：
改变权益修正因子：为了减少预计算攻击的可能性，权重修正因子在每一次修正因子间歇时都会改变，以便对将要用来下一个权益累积证明的时间戳的计算结果进行更好的模糊处理。
区块时间戳规则：通过修改区块的时间戳以更好地使用PoS。预期的出块时间从最初的60s增加到粒度匹配的时间。假设节点有一个外部时间，假设节点时间与系统共识时间偏离太多，这个节点将被孤立。区块时间戳的修改规则如下：
通过上述的优化，黑币将可能的攻击降到最小，并能够显著提升节点的在线率。使得PoS在进一步扩大节点范围的同时能够有效地降低系统风险，提高系统的安全性。
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加原子钟的方式来修正节点间的时间同步问题。
交易速度快：DAG 的并行化结构和blockless的设计会提高系统的效率，交易速度大大提升。
无需挖矿：由于不需要区块打包，故无需挖矿；
无手续费：由于blockless的项目中没有矿工进行区块打包，所以不需要付手续费给矿工。
对于不同的Input,Output的值是随机的，但是均匀地分布在值域范围内。
对于相同的Input，他的Output是一定是相同的。
VRF的过程主要包括四个步骤：
VRFgen：随机生成密钥，生成一对非对称加密密钥（一对公私钥）；
VRFval：生成随机数输出；
VRFproof：随机数输出的零知识证明；
VRFver：其他节点收到输入和零知识证明后，结合生成随机数的节点的公私钥，对随机数进行验证。
验证加密排序的伪代码如下所示，通过相同的结构验证用户是否被选中，函数返回所选子用户的数量，若没有选出用户，则返回0。
Alogrand通过VRF实现了矿工选择的不可预测性，实现了区块链的去中心化；并且每个区块随机产生，不需要竞争出块，提升了系统的扩展性；PoW、PoS当恶意节点积攒到一定数量时就可以控制网络，一般地是通过博弈的方式来实现网络稳定性和安全性保障，Alogrand随机产生区块生产者，所以即使是恶意节点，也无法随意控制网络。
自从2018年中本聪发布比特币以来，区块链系统已经经历了10年的发展。共识算法的发展也进入了百花齐放的时期。纵观区块链共识协议的发展过程，主要体现以下几大趋势。
早期的区块链系统，一般采取单一的共识机制，比如BTC的PoW、Peercoin的PoS等、EOS的DPoS等。
在当前的技术背景下，没有哪一种共识机制是完美无缺的，每一种共识机制都有其优点和缺点，不同的应用场景可能需要不同共识机制。在区块链解决方案中，应该实现兼容多种共识算法，在实际业务落地中有选择性的使用一种最合适的共识机制，甚至整个网络具备让开发者自定义共识机制的能力。未来可插拔的共识机制可能是未来发展的主要方向。
百度超级链XuperChain实现了可插拔共识机制，目前已经支持Pow，DPoS，Pool和Raft等共识，同时还允许用户通过该可插拔共识框架定义符合其业务特征的共识机制。
Hyperledger的 Fabric也实现了可插拔的共识机制，目前支持的共识Solo、Kafka、SBFT。
一般地，区块链是一种链式结构，区块只能沿着一条链生长，效率较低。随着共识的发展，有人提出使用DAG的方式，所谓DAG就是有向无环图。基于这种思想，可以有很多新的方式，比如可以并发地进行区块打包，从而提高区块链的扩展能力。 除了前面提到的IOTA和Byteball使用了基于DAG的共识协议。图灵奖得主、清华大学交叉信息研究院院长姚期智参与创立的区块链项目 Conflux也是基于DAG的思想，Conflux的理念设计容许不同区块同时生成，并运用基于有向无环图（directed acyclic graph, DAG）概念的排序算法来避免分叉的问题，先決定所有区块的整体排序，再決定衍生的交易排序。
前面所述的共识，为了提高区块链系统的吞吐能力，一定程度上降低了其去中心化的程度，一定程度上降低了系统的安全性。Alogrand项目出现，使得共识由确定性向随机性发展，在该共识中，很多节点都具有潜在的控制权，下一个矿工的是由加密排序函数随机产生，在这种变化下，事实上虽然只有少数节点参与共识，但是由于参与共识的节点在系统中游走，无法提前预测，从而实现系统的安全性。 除了上面提到的Alogrand使用了基于VRF的共识协议，Difinity和TASchain也都使用了基于VRF的共识机制，未来该趋势上相信会有更多适用于工业级的共识协议诞生。
本文从分布式一致性问题切入，分别讨论了可信环境分布式系统和不可信环境分布式系统的一致性问题。在可信环境分布式系统一致性问题中，介绍了经典的2PC、Paxos和Raft协议。在不可信环境分布式系统一致性问题中，介绍了拜占庭教军问题及PBFT算法，并介绍了公链环境下新型一致性协议（即区块链共识协议）及应用，主要包括PoW、PoS、DAG和VRF。最后本文总结了区块链的发展趋势，主要体现三大趋势，从单一共识向可插拔共识、从链式共识向图式共识、从确定性共识向随机性共识。 区块链是一个不可信环境分布式系统，区块链共识是不可信环境分布式系统一致性的一个重要的研究方向。近年来，区块链共识也百花齐放，各种改进算法争相被提出。本文讨论的共识算法只是其中的一个子集。 未来，随着区块链技术的进一步发展，尤其是伴随着底层账本结构的进一步优化，势必会涌现出更多的新兴的共识算法，本文提到的IOTA的基于DAG的共识只是其中一种。同时，随着技术的进一步深入，区块链共识的评估标准也一定会进一步规范。
[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.
本文已被收录在 《区块链应用蓝皮书： 中国区块链应用发展研究报告（2019）》技术篇中，该书由人民网人民创投区块链研究院策划编撰，社会科学文献出版社出版发行。
本蓝皮书通过大量一线调研和数据分析，系统深入地对我国区块链的核心技术创新进展、行业应用发展状况以及产业与市场的基本发展情况进行了全面梳理，总结出区块链的应用发展特点、产业发展特征以及我国区块链技术及应用的挑战与发展机遇。
原文链接：https://xuperchain.baidu.com/n/news/4222c17c8af084352f2f930f35d75f91
| 修改日期 | 修改人 | 备注 |
| 2022-06-09 17:43:22[当前版本] | 尹紫娟 | 更新数据 |
| 2022-06-09 13:15:42 | 尹紫娟 | 更新数据 |
| 2022-06-09 12:57:58 | 尹紫娟 | 更新数据 |
| 2020-04-01 15:37:55 | 潘昊 | 格式调整 |
| 附件类型 |
|
|
|
|
JPG
PNG