摘要共识算法是区块链技术的核心要素，也是近年来分布式系统研究的热点.本文系统性地梳理和讨论了区块链发展过程中的32种重要共识算法，介绍了传统分布式一致性算法以及分布式共识领域的里程碑式的重要研究和结论，提出了区块链共识算法的一种基础模型和分类方法，并总结了现有共识算法的发展脉络和若干性能指标，以期为未来共识算法的创新和区块链技术的发展提供参考.
关键词区块链，共识算法，分布式系统，拜占庭容错，P2P网络
共识问题是社会科学和计算机科学等领域的经典问题，已经有很长的研究历史.目前有记载的文献至少可以追溯到1959年，兰德公司和布朗大学的埃德蒙·艾森伯格(EdmundEisenberg)和大卫.盖尔(DavidGale)发表的“Consensusofsubjectiveprobabilities：thepari—mutuelmethod”，主要研究针对某个特定的概率空间，一组个体各自有其主观的概率分布时，如何形成一个共识概率分布的问题【.随后，共识问题逐渐引起了社会学、管理学、经济学、特别是计算机科学等各学科领域的广泛研究兴趣.
计算机科学领域的早期共识研究一般聚焦于分布式一致性，即如何保证分布式系统集群中所有节点的数据完全相同并且能够对某个提案达成一致的问题，是分布式计算的根本问题之一.虽然共识(Consensus)和一致性(Consistency)在很多文献和应用场景中被认为是近似等价和可互换使用的，但二者涵义存在着细微的差别：共识研究侧重于分布式节点达成一致的过程及其算法，而一致性研究则侧重于节点共识过程最终达成的稳定状态;此外，传统分布式一致性研究大多不考虑拜占庭容错问题，即假设不存在恶意篡改和伪造数据的拜占庭节点，因此在很长一段时间里，传统分布式一致性算法的应用场景大多是节点数量有限且相对可信的分布式数据库环境.与之相比，区块链系统的共识算法则必须运行于更为复杂、开放和缺乏信任的互联网环境下，节点数量更多且可能存在恶意拜占庭节点.因此，即使Viewstampedreplication(VR)和Paxos等许多分布式一致性算法早在上世纪8O年代就已经提出，但是如何跨越拜占庭容错这道鸿沟、设计简便易行的分布式共识算法，仍然是分布式计算领域的难题之一.
2008年10月31日，一位化名为“中本聪”的研究者在密码学邮件组中发表了比特币的奠基性论文“Bitcoin：apeer—to—peerelectroniccashsystem”【2J.基于区块链(特别是公有链)的共识研究自此拉开序幕.从分布式计算和共识的角度来看，比特币的根本性贡献在于首次实现和验证了一类实用的、互联网规模的拜占庭容错算法，从而打开了通往区块链新时代的大门.
一般而言，区块链系统的节点具有分布式、自治性、开放可自由进出等特性，因而大多采用对等式网络(Peer—to—peernetwork，P2P网络)来组织散布全球的参与数据验证和记账的节点.P2P网络中的每个节点均地位对等且以扁平式拓扑结构相互连通和交互，不存在任何中心化的特殊节点和层级结构，每个节点均会承担网络路由、验证区块数据、传播区块数据、发现新节点等功能.区块链系统采用特定的经济激励机制来保证分布式系统中所有节点均有动机参与数据区块的生成和验证过程，按照节点实际完成的工作量分配共识过程所产生的数字加密货币，并通过共识算法来选择特定的节点将新区块添加到区块链.以比特币为代表的一系列区块链应用的蓬勃发展，彰显了区块链技术的重要性与应用价值，区块链系统的共识也成为一个新的研究热点[引.
迄今为止，研究者已经在共识相关领域做了大量研究工作，不同领域研究者的侧重点也各不相同.计算机学科通常称为共识算法或者共识协议，管理和经济学科则通常称为共识机制.细究之下，这些提法存在细微的差异：算法一般是一组顺序敏感的指令集且有明确的输入和输出;而协议和机制则大多是一组顺序不敏感的规则集.就区块链领域而言，本文认为比特币和以太坊等可认为是底层协议或机制，其详细规定了系统或平台内部的节点交互规则、数据路由和转发规则、区块构造规则、交易验证规则、账本维护规则等集合;而工作量证明(Proof-ofwork，PoW)、权益证明(Proof-of-stake，PoS)等则是建立在特定协议或机制基础上、可灵活切换的算法，其规定了交易侦听与打包、构造区块、记账人选举、区块传播与验证、主链选择与更新等若干类顺序敏感的指令集合.因此，本文后续叙述均采用共识算法的提法.现有文献研究的共识问题实际上可以分为算法共识和决策共识两个分支，前者致力于研究在特定的网络模型和故障模型前提下，如何在缺乏中央控制和协调的分布式网络中确保一致性，其实质是一种“机器共识”;后者则更为广泛地研究无中心的群体决策中，如何就最优的决策达成一致的问题，例如关于比特币系统扩容【6j问题和分叉问题的社区讨论与路线选择，其实质是“人的共识”.二者的区别在于：前者是机器问的确定性共识，以工程复杂性为主;而后者则是以“人在环路中(Human—inthe—loop)”的复杂系统为特点的不确定性共识，以社会复杂性为主.区块链共识算法研究应属于算法共识分支的子集，而决策共识则大多见于分布式人工智能、多智能体等研究领域.
拜占庭将军问题是分布式共识的基础，也是上述两个研究分支的根源.拜占庭将军问题有两个交互一致性条件，即一致性和正确性.由于大多数情况下，正确性涉及到人的主观价值判断，很难施加到分布式节点上，因此算法共识采用的是“降级的正确性(Degradedcorrectness)，即从“表达的内容是正确的”降级为“正确地表达”，这就导致区块链的拜占庭共识实际上是一种机器共识，其本身等价于分布式一致性+正确表达(不篡改消息).与之相对的是，决策共识可以认为是人的共识，不仅要求一致性，而且要求所有节点相信“表达的内容是正确的”，因而决策共识不仅要求内容的客观一致性，而且还要求其在共识节点间的主观正确性.由此可见，算法共识处理的是客观的二值共识，即对(唯一正确的账本)和错(所有错误的账本)，而决策共识处理的是主观的多值共识，即意见1(及其所属群体)、意见2(及其所属群体)、…、意见Ⅳ(及其所属群体)，各节点最终通过群体问的协调和协作过程收敛到唯一意见(共识)，而此过程可能失败(不收敛).
本文致力于按时间顺序梳理和讨论区块链发展过程中的共识算法，以期为未来共识算法的创新和区块链技术的发展提供参考.本文的后续章节安排如下：首先，简要介绍了分布式共识领域重要的里程碑式的研究和结论，包括两军问题、拜占庭问题和FLP不可能定理，并介绍了传统的分布式一致性算法;然后，提出了区块链共识算法的一种基础模型和分类方法，并对当前主流的区块链共识算法进行了分析;最后，总结了区块链共识算法的发展和研究趋势.
1传统分布式一致性算法
1975年，纽约州立大学石溪分校的阿克云卢(AkkoyunluE.A.)、埃卡纳德汉姆(EkanadhamK.)和胡贝尔(HuberR.V.)在论文“Somecon—straintsandtradeofsinthedesignofnetworkcommunications”中首次提出了计算机领域的两军问题及其无解性证明【711著名的数据库专家吉姆.格雷正式将该问题命名为“两军问题”-8J.两军问题表明，在不可靠的通信链路上试图通过通信达成一致共识是不可能的，这被认为是计算机通信研究中第一个被证明无解的问题.两军问题对计算机通信研究产生了重要的影响，互联网时代最重要的TCP/IP协议中的“三次握手”过程即是为解决两军问题不存在理论解而诞生的简单易行、成本可控的“工程解”.
分布式计算领域的共识问题于1980年由马歇尔·皮斯(MarshallPease)、罗伯特·肖斯塔克(RobertShostak)和莱斯利·兰伯特(LeslieLam—port)提出I9j1该问题主要研究在一组可能存在故障节点、通过点对点消息通信的独立处理器网络中，非故障节点如何能够针对特定值达成一致共识.1982年，作者在另一篇文章中正式将该问题命名为“拜占庭将军问题”【10_，提出了基于口头消息和基于签名消息的两种算法来解决该问题.拜占庭假设是对现实世界的模型化，强调的是由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现的不可预料的行为.此后，分布式共识算法可以分为两类，即拜占庭容错和非拜占庭容错类共识.早期共识算法一般为非拜占庭容错算法，例如广泛应用于分布式数据库的VR和Paxos，目前主要应用于联盟链和私有链;2008年末，比特币等公有链诞生后，拜占庭容错类共识算法才逐渐获得实际应用.需要说明的是，拜占庭将军问题是区块链技术核心思想的根源，直接影响着区块链系统共识算法的设计和实现，因而在区块链技术体系中具有重要意义.
1985年，迈克尔·费合尔(MichaelFisher)、南希·林奇(NancyLynch)和迈克尔·帕特森(MichaelPaterson)共同发表了论文“Impossibil—ityofdistributedconsensuswithonefaultypro—cess”[11J.这篇文章证明：在含有多个确定性进程的异步系统中，只要有一个进程可能发生故障，那么就不存在协议能保证有限时间内使所有进程达成一致.按照作者姓氏的首字母，该定理被命名为FLP不可能定理，是分布式系统领域的经典结论之一，并由此获得了Dijkstra奖.FLP不可能定理同样指出了存在故障进程的异步系统的共识问题不存在有限时间的理论解，因而必须寻找其可行的“工程解”.为此，研究者们只能通过调整问题模型来规避FLP不可能定理，例如牺牲确定性、增加时间等;加密货币则是通过设定网络同步性(或弱同步性)和时间假设来规避FLP不可能性，例如网络节点可以快速同步，且矿工在最优链上投入有限时问和资源等.
早期的共识算法一般也称为分布式一致算法.与目前主流的区块链共识算法相比，分布式一致性算法主要面向分布式数据库操作、且大多不考虑拜占庭容错问题，即假设系统节点只发生宕机和网络故障等非人为问题，而不考虑恶意节点篡改数据等问题.1988年，麻省理工学院的布莱恩·奥奇(BrianM.Oki)和芭芭拉·里斯科夫(BarbaraH.Liskov，著名计算机专家、2008年图灵奖得主)提出了VR一致性算法，采用主机备份(Primary—backup)模式，规定所有数据操作都必须通过主机进行，然后复制到各备份机器以保证一致性【J.1989年，莱斯利·兰伯特fLeslieLamport)在工作论文“Thepart—timeparliament”中提出Paxos算法，由于文章采用了讲故事的叙事风格且内容过于艰深晦涩，直到1998年才通过评审、发表在ACMtransac—tionsoncomputersystems期刊上.Paxos是基于消息传递的一致性算法，主要解决分布式系统如何就某个特定值达成一致的问题.随着分布式共识研究的深人，Paxos算法获得了学术界和工业界的广泛认可，并衍生出Abstractpaxos、Classicpaxos、Byzantinepaxos和Diskpaxos等变种算法，成为解决异步系统共识问题最重要的算法家族【MJ.实际上，Liskove等提出的VR算法本质上也是一类Paxos算法.需要说明的是，VR和Paxos算法均假设系统中不存在拜占庭故障节点，因而是非拜占庭容错的共识算法.除以上共识算法外，获得较多研究关注的早期共识算法还有两阶段提交(Two—phasecommit)算法、三阶段提交(Three—phasecommit)算法、Zab、Zyzzyva、Kafka等，本文限于篇幅不加详述.
2主流区块链共识算法
1993年，美国计算机科学家、哈佛大学教授辛西娅·德沃克(CynthiaDwork)首次提出了工作量证明思想_15J，用来解决垃圾邮件问题.该机制要求邮件发送者必须算出某个数学难题的答案来证明其确实执行了一定程度的计算工作，从而提高垃圾邮件发送者的成本.1997年，英国密码学家亚当·伯克(AdamBack)也独立地提出、并于2002年正式发表了用于哈希现金(Hashcash)的工作量证明机制l16j.哈希现金也是致力于解决垃圾邮件问题，其数学难题是寻找包含邮件接受者地址和当前日期在内的特定数据的SHA一1哈希值，使其至少包含20个前导零.1999年，马库斯·雅各布松(MarkusJakobsson)正式提出了“工作量证明”概念-17_.这些工作为后来中本聪设计比特币的共识机制奠定了基础.
1999年，BarbaraLiskov等提出了实用拜占庭容错算法(PracticalByzantinefaulttolerance，PBFT)[18]，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行.PBFT实际上是Paxos算法的变种，通过改进Paxos算法使其可以处理拜占庭错误，因而也称为Byzantinepaxos算法，可以在保证活性(Live—ness)和安全性(Safety)的前提下提供(n一1)/3的容错性，其中n为节点总数.
2000年，加利福尼亚大学的埃里克·布鲁尔(EricBrewer)教授在ACMSymposiumonPrin—ciplesofDistributedComputing研讨会的特邀报告中提出了一个猜想：分布式系统无法同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partitiontolerance)，最多只能同时满足其中两个.其中，一致性是指分布式系统中的所有数据备份在同一时刻保持同样的值;可用性是指集群中部分节点出现故障时，集群整体是否还能处理客户端的更新请求;分区容忍性则是指是否允许数据分区，不同分区的集群节点之问无法互相通信.
2002年，塞斯.吉尔伯特(SethGilbert)和南希·林奇(NancyLynch)在异步网络模型中证明了这个猜想，使其成为CAP(Consistency，availability，partitiontolerance)定理或布鲁尔定理I1.该定理使得分布式网络研究者不再追求同时满足三个特性的完美设计，而是不得不在其中做出取合，这也为后来的区块链体系结构设计带来了影响和限制.
2008年10月，中本聪发表的比特币创世论文催生了基于区块链的共识算法研究.前文所提到的传统分布式一致性算法大多应用于相对可信的联盟链和私有链，而面向比特币、以太坊等公有链环境则诞生了PoW、PoS等一系列新的拜占庭容错类共识算法.
比特币采用了PoW共识算法来保证比特币网络分布式记账的一致性，这也是最早和迄今为止最安全可靠的公有链共识算法.PoW的核心思想是通过分布式节点的算力竞争来保证数据的一致性和共识的安全性.比特币系统的各节点(即矿工)基于各自的计算机算力相互竞争来共同解决一个求解复杂但是验证容易的SHA256数学难题(即挖矿)，最快解决该难题的节点将获得下一区块的记账权和系统自动生成的比特币奖励.PoW共识在比特币中的应用具有重要意义，其近乎完美地整合了比特币系统的货币发行、流通和市场交换等功能，并保障了系统的安全性和去中心性.然而，PoW共识同时存在着显著的缺陷，其强大算力造成的资源浪费(主要是电力消耗)历来为人们所诟病，而且长达l0分钟的交易确认时问使其相对不适合小额交易的商业应用【3】_
2011年7月，一位名为QuantumMe—chanic的数字货币爱好者在比特币论坛(www.bitcointalk.org)首次提出了权益证明PoS共识算法【2o_.随后，SunnyKing在2012年8月发布的点点币(Peercoin，PPC)中首次实现.PoS由系统中具有最高权益而非最高算力的节点获得记账权，其中权益体现为节点对特定数量货币的所有权，称为币龄或币天数(Coindays).PPC将PoW和PoS两种共识算法结合起来，初期采用PoW挖矿方式以使得Token相对公平地分配给矿工，后期随着挖矿难度增加，系统将主要由PoS共识算法维护.PoS一定程度上解决了PoW算力浪费的问题，并能够缩短达成共识的时间，因而比特币之后的许多竞争币都采用PoS共识算法.
2013年2月，以太坊创始人VitalikButerin在比特币杂志网站详细地介绍了Ripple(瑞波币)及其共识过程的思路.Ripple项目实际上早于比特币，2004年就由瑞安·福格尔(RyanFugger)实现，其初衷是创造一种能够有效支持个人和社区发行自己货币的去中心化货币系统;2014年，大卫·施瓦尔茨(DavidSchwartz)等提出了瑞波协议共识算法(RippleProtocolConsensusAlgo—rithm，RPCA)_21_，该共识算法解决了异步网络节点通讯时的高延迟问题，通过使用集体信任的子网络(Collectively—trustedsubnetworks)，在只需最小化信任和最小连通性的网络环境中实现了低延迟、高鲁棒性的拜占庭容错共识算法.目前，Ripple已经发展为基于区块链技术的全球金融结算网络.
相关期刊推荐：《电脑知识与技术》是由安徽省科技情报学会、中国计算机函授学院主办的一本融知识、技术、信息于一体的电脑类杂志，是全国的专业IT类旬刊刊物，读者对象主要为广大电脑用户、电脑爱好者和各企事业单位计算机技术人员。创刊以来，一直本着普及电脑知识、推广电脑技术、交流经验技巧、促进电脑应用的办刊宗旨，注重杂志质量。
2013年8月，比特股(Bitshares)项目提出了一种新的共识算法，即授权股份证明算法(Delegatedproof-of-stake，DPoS)[22J.DPoS共识的基本思路类似于“董事会决策”，即系统中每个节点可以将其持有的股份权益作为选票授予一个代表，获得票数最多且愿意成为代表的前Ⅳ个节点将进入“董事会”，按照既定的时间表轮流对交易进行打包结算、并且签署(即生产)新区块L31.如果说PoW和PoS共识分别是“算力为王”和“权益为王”的记账方式的话，DPoS则可以认为是“民主集中式”的记账方式，其不仅能够很好地解决PoW浪费能源和联合挖矿对系统的去中心化构成威胁的问题，也能够弥补PoS中拥有记账权益的参与者未必希望参与记账的缺点，其设计者认为DPoS是当时最快速、最高效、最去中心化和最灵活的共识算法.
