区块链共识算法综述*

姜 义, 吕荣镇

(哈尔滨理工大学 测控技术与通信工程学院，黑龙江 哈尔滨 150080)

0 引 言

中本聪在2009年发表的比特币白皮书[1]拉开了区块链发展的序幕。近年来区块链技术的巨大发展为其在更多领域应用提供了可能性。区块链技术的研究与应用都呈现出爆炸性增长的态势，被认为是信息技术领域的第五次颠覆性创新，是人类信用进化史上继血亲信用、贵金属信用、央行纸币信用之后的第四个里程碑[2]。

在对区块链的研究中，共识算法不仅是核心的技术之一，也是分布式网络重要的研究课题，其研究内容包括共识算法和奖励机制。共识算法是区块链技术达成去中心化系统的关键，其作用是使决策高度分散的去中心化系统能够高效且快速的对数据的有效性达成一致。共识中的激励包含代币的发行机制和分配机制，其设计中引入了经济学的设计用于保证参与节点的积极性。

目前发表的文献中，袁勇[3]、蔡晓晴[4]、张亮[5]、何蒲[6]等人分别对区块链技术的基础技术、概念、以及未来的应用方向进行了叙述。该文则对区块链的共识算法进行综述。

1 基于一致性算法的共识机制

在区块链系统中共识机制的目的是使所有的诚实节点获得一致的区块链视图。一致性视图包含两个含义：一致性，即对区块链的每一次更新后，每个节点都能获得相同的视图；有效性，即由任一诚实节点在区块链发布的信息都最终被其它节点承认并记录。而在区块链系统中达成以上两个特性的算法就是一致性算法。本节将对区块链系统中常见的基于一致性算法的共识机制进行介绍。

1.1 PAXOS和RAFT

早期的分布式系统共识中仅考虑对错误节点的容错，其中代表性工作包括Paxos[7]和Raft[8]等一致性协议。这些一致性算法旨在解决如何快速且正确地在集群内部对某个数据的内容达成共识，且保证在可能发生一定异常的情况下不破坏整个系统的一致性。

1.1.1 Paxos

Paxos算法可以使分布式异步网络中存在着二分之一的故障节点或者网络本身出现异常的情况下，网络中信息的传输也能正常的运行。该算法在一定程度上容忍了信息的丢失、延时、乱序以及重复的可能性，该算法拥有的容错能力是2f+1。

Paxos将节点的角色分为三种：提议者Proposer提出议案(Proposal)，提案中包括提案编号(Proposel ID)和提案的值(Value)；Acceptor决策者，用来回复Proposer的提案；收到Proposal后，若获得多数的Acceptor的接受，提案才被允许；Learner决策学习者，不参与决策，只能学习最新达成共识的提案。Paxos算法主要解决了两个问题：一是各节点能够区分当前的提议者和前一个提议者，能够阻止共识被破坏；二是一旦提议达成共识，之后的提议者也必须承认该提议，确保达成一致性。

1.1.2 Raft

Raft算法则是从多副本状态机的角度提出，通过管理多副本状态机的日志复制来实现共识。Raft算法中有三种角色，分别是领导者(Leader)、跟从者(Follower)、候选人(Candidate)。其中领导者主要用于传达客户端的信息，通知跟从者日志的同步，在收到大部分跟从者确认后，提交日志。而跟从者则是接受并持久化日志，在领导者确认之后进行提交。候选人就是节点从跟从者到领导者的中间角色。该算法的容错能力与Paxos算法相同，为2f+1，但是比Paxos更容易理解和实现。

Raft算法的关键问题是领导者选举(Leader Election)和日志同步(Log Replication)。Raft通过心跳触发系统进行领导人的选举。选举过程分为两步：首先跟从者将自己的任期期号加一，并将角色转变为候选者；其次向其他节点发送投票请求，希望跟从者能给其投票。如果某个候选人得票超过半数，就可成为下一任期的领导人。如一段时间内，没有节点获胜，即多个领导者的票数相同，则候选人继续增加任期号，并重启选举。日志同步则是由客户端发送请求给领导者，再由领导者进行发布确保其和其它跟从者之间的状态是一致的。

1.2 BTF类

1.2.1 PBTF

实用拜占庭容错算法(PBFT)[9]出现，使得拜占庭协议的运行复杂度从指数级别降低到多项式级别，保证了算法的活性和安全性以及3f+1的容错能力。该算法首次提出在异步网络环境下使用状态副本复制协议，并实现了一种拜占庭容错的分布式文件系统。 PBFT算法中节点都是副本(Replica)，在同一个视图中有一个副本作为领导者(Primary)，其余的副本则作为备份(Backup)。该共识机制主要有两个部分，其中一个是有五个步骤达成共识：请求(Request)、预准备(Pre-Prepare)、准备(Prepare)、提交(Commit)、回复(Reply)。如果领导节点出现故障或者错误的时候，导致了数据无法处理，就需要启动视图转换。这个过程被称为视图转换(View-Change)。

1.2.2 HotStuff

HotStuff[10]算法由Abraham，Gueta和Malkhi提出，该算法以传统BFT共识算法为基础实现了Pipeline BFT共识模式，将原先需要两轮通信才能达成共识写入链中的方式，改成了先将区块上链。只要一个区块后面产生了三个连续区块，那么就说明该区块经过了三轮投票确认，就可以最终确认该提前上链区块成功出块了。这种方式使得系统的响应特性大幅度提高了。HotStuff网络模型为部分同步网络，容错能力为n=3f+1。

HotStuff在PBFT的基础上做了较多改进。其一将PBFT网状通信网络拓扑换成星形通信网络拓扑，降低了系统通信的复杂度。HotStuff只依靠主节点进行消息的发送和处理，再把结果传送给其他节点。其二将视图切换流程和正常流程合并，采用线性视图转换(Linear View Change，LVC)降低切换视图的复杂度。此外HotStuff引入了门限签名和流水化处理。引入门限签名的目的是为了减少共识协议中的签名的个数，在其三阶段确认中，对消息门限签名并发送给主节点即为投票。这两个改进大幅度提高了共识的效率。

1.2.3 LibraBFT

LibraBFT算法被称为另一种HotStuff的共识算法。LibraBFT基于HotStuff设计并保留了HotStuff的流水线的设计，但在投票时节点仅将投票发给领导者，而不是发给其他节点。LibraBFT还使用了HotStuff无法使用的广播形式，LibraBFT在以下情况中要求非领导者节点执行广播：节点定期使用广播进行状态的同步；当网络出现问题或者领导节点故障时，节点会向其他节点发送消息超时。此外在LibraBFT中还添加了现实考量的机制，引入了“代”的概念，允许了共识节点交换以及增加了一些奖惩机制。

1.2.4 SBFT

可扩展拜占庭容错协议(Scalable Byzantine Fault Tolerance, SBFT)由Golan Gueta等人[11]提出，是对拜占庭容错算法(PBFT)的一种扩展，其主要解决了BFT的去中心化和可扩展性问题。相比于PBFT适用于少数节点的情况，SBFT能够使200个节点高效的达成共识。此外还有其它一些改进。首先采用相互确认的方式来确认区块，而SBFT则是采用收集器的线性通信模式。每个节点不需要再将信息发给复制节点，而是发给收集器，再由收集器进行广播。其次SBFT采用了快速共识的机制，只要节点没有发现错误并且使用门限签名将消息长度降低到常数。其容错能力是3f+1。

1.2.5 Honey Badger BFT

传统的PBFT是一种弱同步网络的共识算法，但是这种算法受到网络的延时的影响非常大。Honey Badger BFT[12]则是一种异步网络的BFT算法，其对网络的依赖很低，效率比PBFT提高很多。Honey Badger BFT的容错能力n=3f+1。Honey Badger BFT是针对异步网络，采用原子广播协议设计的共识算法，其核心是Reliable Broadcast (RBC)广播协议。RBC广播协议使用纠删错算法降低节点间的数据传输量，并通过BA算法形成一致的交易列表。该算法在网络节点少的情况下性能不如PBFT；但在网络节点较多时，Honey Badger BFT算法的性能不会下降，而PBFT性能会显著下降。

2 基于证明的共识机制

2.1工作量证明

基于工作量证明(Proof of Work)的共识算法是各个节点通过竞争优先计算出随机数来决定记账权，以此来保障数据的一致性问题。工作量证明由Dwork和Naor[13]为了反垃圾邮件而提出，其原理为在邮件发送之前，发送方需要完成一定的计算量来获得邮件发送的权力。比特币网络是工作量证明共识算法第一次运用在大规模非授权网络中。

2.1.1 比特币

作为最典型的工作量证明的代表，比特币系统的节点允许随意进入或者退出。各节点的工作主要是通过计算一个复杂的SHA256数学难题来争夺记账的权利。该难题通过区块预先设定的随机数，各节点通过哈希函数不断的计算出一个小于该数的数，即称为挖矿。只有第一时间被发现并通过校验的区块才会被所有节点计入区块链中。而解题的过程是困难的，需要强大的算力进行暴力计算；但是校验的过程十分方便，容易很快的达成共识。因为使用了基于工作量证明的共识，比特币节点获得奖励的概率和其拥有的算力成正比，算力越高越容易拿到奖励。而随着算力增加，解题的速度加快，也会产生过多的分叉。而挖矿难度如果过高就会导致系统的性能下降，交易的吞吐量也会为之降低，所以需要不断的修正难度系数。

PoW的共识系统中，通过奖励矿工和缴纳交易费来确保了安全性。如果某个恶意节点试图破坏区块链，则它需要超过总节点的51%的算力，即称为51%攻击。而发动此类攻击的代价是非常昂贵的，并不符合攻击者的利益需求。但是随着比特币系统的不断庞大，解题的难度不断上升，独立矿工的盈利的可能性越来越低，所以一些矿工组织起来形成了矿池来提高获取记账权的概率。目前算力排名前五的矿池的总算力已经占比50%以上[14]，这对系统的安全性和公平性有着很大的威胁。由于区块大小和生成间隔的限制，导致产生区块的时间过长。而单纯的提高区块的容量又会导致网络发生拥塞。如果缩短区块生成时间，就会造成更多的分叉，也会导致双花等安全问题。

2.1.2 Bitcoin-NG

Bitcoin-NG是由Eyal等人[15]所提出的改进版PoW共识机制。该算法提出了首领选择(Leader Election)和交易序列化(Transaction Serialization)。它将时间划分为段，在每个时间段都有个领导者，该领导者有资格序列化交易。该方案极大提高了吞吐量。Bitcoin-NG是序列化交易的区块链共识算法，和比特币的共识算法很相似，但是该算法会生成两种不同的区块：首领区块和微区块。与比特币相比，首领区块多了包含微区块的公钥，而微区块中则多了一个对应首领区块的私钥。相比于首领区块，微区块的产生并不需要经过挖矿，领导节点的可以快速高效的生成微区块。除此以外，系统通过一个专门的账目记录“毒药交易”来防止分叉。后来的领导者节点可以对毒药交易进行举报，如果成功就能使恶意节点的酬金无效，举报者能获得奖励。同时因为最长链的原则，Bitcoin-NG引入了区块重量的概念，并且只有关键区块才有重量，微区块没有。所以Bitcoin-NG中只有最重且最长的链才是主链。

2.1.3 Byzcoin

Byzcoin[16]是基于强共识协议的加密货币，Byzcoin建立在成熟的实用拜占庭容错算法之上引入联名签名方案来减小PBFT轮次的开销和轻量级客户端校验交易请求的开销。Byzcoin和Bitcoin-NG一样，区块链是由关键区块和微区块组成，通过PoW机制选出领导区块。但是Byzcoin则引入了拜占庭容错算法，可以在不信任的网络中建立信任，同时完成即时的、不可逆的交易。Byzcoin交易的特点主要是其微区块的确认需要共识小组联合签名来验证，只有大多数矿工同意才能通过，这防止了双花攻击。Byzcoin算法相对于Bitcoin-NG在吞吐量有所提升且降低了交易延迟。

除了上述的一些PoW算法的改进，还有一些研究人员通过修改一致性协议来提升算法的性能，例如以太坊采用GHOST协议提升吞吐量时保证了区块链的安全性。另一些研究者则采用DAG数据结构来改进区块链的性能，例如Spectre[17]和Hashgraph[18]。

2.1.4 性能分析

基于工作量证明的共识算法主要面临以下几个问题：

51%攻击[19]：51%攻击是PoW算法最致命的弱点。一旦有矿工或矿池的算力能够超过总算力的51%，就可以发动攻击。发动攻击者可以通过阻止交易被确认，或者不给其他矿工挖矿，只允许自己发送的交易被确认来进行攻击。但是该攻击成本比较大，而且收益低于成本。

自私挖矿(Selfish Mining)[20]：Ittay Eyal等人提出的自私挖矿攻击揭示了比特币网络中的一个漏洞，即恶意节点发现新区块，然后将新发现的区块保持为私有并在其后面添加更多的新区块。当其他节点挖掘到该区块时，恶意节点就将之前挖掘的区块公布出去，成为主链中的最长链并被其他节点所承认成为主链。自私挖矿是让恶意节点以牺牲所有诚实节点的利益为代价牟取暴利。

日蚀攻击(Eclipse Attack)[21-22]：日蚀攻击主要是攻击区块链中的节点而不是整个网络。在比特币系统中每个网络节点能最多和117个节点连接，而日蚀攻击则是将该节点的输入切断，隔离到正常的区块链网络之外。

2.2 权益证明

PoS(Proof of Stake)权益证明机制，是共识机制的一种，又称股权证明机制。简单来说就是依据持有代币的数量和时间，给相应的利息。这样拥有更多权益的节点更会去维护区块链的安全，以此达成共识。Sunny King和Scott Nadal[23]设计的点点币，首次将PoS算法应用于实际的工程中，一定程度上减少了工作量证明算法所造成的算力浪费和能源消耗。“权益证明”共识的优点是不需要像PoW算法那样庞大的计算能力，而是以投入的代币为资本确定出块权。但仅通过投入代币的数量来确定伪造者将会为较富有的用户带来好处，如不加以限制将削弱区块链的去中心化特性。“基于币龄的选择” 和“随机块选择”则是为了解决该问题所设计的两个较优秀的方案。

“基于币龄的选择”系统根据将自己的股份保留的时间来确定下一位出块者。系统计算由节点拥有的代币数量乘以持有代币的时间，将该乘积作为选择出块者的依据。按照这种方式，货币持有越久，被选作下一个出块者的机会就越高，越能获得奖励。但是一旦用户伪造了区块，系统便会取消其出块的权利至少30天[24]。为了防止少量用户控制网络并使区块链更加安全，该方案将货币的寿命设置为不超过90天。此外用户不能被分配为出块者的时间越长，其成为下一个出块者的机会就越大。因此，该方案的设计可以促进区块系统的公平性并促进区块系统的成长。防止拥有更多代币的钱包总是在“权益证明”系统中获得奖励的第二种机制称为“随机区块选择”。此实现基于最低哈希值和股份大小的组合选择新的出块者，该机制进一步加强了权益证明公平性。

PoS算法面临的最重要的问题是如何在不消耗资源的情况下达到PoW算法的安全性能。权益证明的主流协议中分别是：Tendermint和Casper the Friendly Gadget(CFFG)。

2.2.1 Tendermint

Tendermint[25]算法基于投票机制进行工作，其设置一组验证节点并形成一个表用于轮换领导者。领导节点进行全网监听并收集信息，最后将内容写入一个区块中并全网广播；通过全网投票超过三分之二节点同意后，新区块就能写入区块链中。如果出现领导节点宕机或者网络延迟，则该轮次所在区块为空，不写入任何内容。除此以外Tendermint引入了一种锁机制，即使节点在预提交后突然中断导致而无法收到最终结果，在下一轮中这些节点仍然会继续上一轮的投票，最终与正常节点的区块一致。该算法需要三分之二以上的验证者存在，才能保证运行的正常，所以其区块链永远不会产生分叉。

2.2.2 Casper the Friendly Gadget

CFFG[26]是基于链的权益证明和基于拜占庭容错的PoS算法的一个共同体，是Tendermint核心算法的一种倾向于活跃性而非安全性环境下的改编。CFFG可以看作是覆盖在以太坊上的PoW协议的PoS算法，旨在使其从PoW算法向PoS算法进行过渡。以太坊作为区块链技术2.0版本，从出现以来就备受关注。以太坊的共识机制是融合了PoW和PoS算法的技术，在其目前的发展阶段中仍然使用的是PoW的共识算法。

CFFG是以保守的方式将以太坊从PoW的模式过渡到PoS的模式，其最终的版本可能会结合CFFG和CTFG的优势，向着一个完善的PoS共识机制演化。其算法相比于PoW算法消耗大量的算法来获取记账权不同。节点是通过自身拥有的ETH来成为以太坊中的验证节点，将自身的ETH提交来获取最终确认区块的权利。CFFG采用问责的方式来确保无利害攻击的危害，问责意味着对作恶或者不作为的惩罚将高于奖励。CFFG共识中最重要的就是有检查点的存在，在每增加50个区块时就需要对其进行最终确定。这被称之为检查，而50个区块被称为周期。Casper在每个周期发送投票消息来触发这个处理过程。

CFFG最终化区块主要分为两步：第一步是超过三分之二的节点在第一个周期对区块一进行投票检查；第二步是超过三分之二的节点在第二周期的时候，对区块二进行投票检查，并最终化其父区块。只有区块被最终确认后验证节点才能获得奖励，如果出现区块分叉，那么保证金最少会被降低三分之一。CFFG算法安全性的最大保证是需要在三分之二验证者一起保证区块才能达成一致，协同作恶的可能性很低，如果进行串谋有可能导致自己受益的降低。

2.2.3 委托权益证明

委托权益证明(Delegated Proofs of Stake)[27]的机制类似于股份制有限公司，通过资产占比来进行投票，节点为了自身利益的最大化会选择相对可靠的节点。各个节点投票选举出社区可信度较高的节点作为共识过程的决定者，选中的决定者轮流作为出块节点。如果出块节点在委任期间未按要求生产区块则会被除名，并从新进行选举。DPoS算法要求随机指定节点的出块顺序且每个周期都将顺序打乱。由于该共识机制不需要竞争出块者，在处理能力得到提升的同时舍弃了一部分的去中心化特性。

2.2.4 性能分析

无利害攻击(Nothing at Stake)[28]：该攻击主要是在区块链出现分叉时，出块节点可以在不受任何损失的情况下同时为多个分叉出块，从而获得所有可能到利益。而PoS算法则不同，恶意节点自身利益不会被损害。所以在链产生分叉时，可以同时在两个链上都进行挖矿，从而利益达到最大化。

长程攻击(Long Range Attack)[25]：长程攻击的本质就是恶意节点通过创建一条从创世区块开始的分叉，并通过获取一些在历史上某个时刻控制了超过51%的股权的账户的私钥，来试图欺骗一些新的节点相信这条链的合法性。由于区块链网络是弱主观性的，网络中有新的节点或者长期离线的节点重新加入网络时，是需要有节点为其提供创世区块的，但他们并不能分辨该链是否为主链，比较容易受到欺骗。

2.3 其他证明共识算法

2.3.1 燃烧证明

燃烧证明[29]本质上是指矿工将虚拟货币发送到一个无法使用但可被公众验证的虚拟地址，通过该方式销毁虚拟货币来证明节点对网络的投入，并以此来竞争生成区块的权利。销毁货币的过程代表了类似PoW算法中挖矿的能力。节点销毁的货币越多，说明其拥有的算力也越大，被选为出块者的成功率越高。燃烧证明背后的想法是通过燃烧一种加密货币，甚至可以是本国货币，来表明自己愿意更长期的投资而愿意承受短期的损失。所以该证明鼓励长期参与，从而获得网络的稳定性以及货币价格的稳定，有助于公平和分散的方式确定加密货币的分布。于PoW共识类似，燃烧证明共识存在着资源的浪费，也会造成卡特尔的产生并导致富有的矿工更富有。

2.3.2 活跃度证明

活跃度证明(PoA)[30]通常被称为工作量证明和权益证明的混合体。但是PoA算法能够改进网络拓扑，保证一定量的在线节点，而且能量损耗也比PoW减少很多。

活跃度证明(PoA)算法有两种节点分别是：矿工和参与节点，其中参与节点不需要一定在线。PoA的区块由矿工构造，并由区块选出N个币的所有者，将参与后续的校验和生成。后续的参与者的选举由所拥有的币的多少数量决定，而且这些参与者必须得满足在线的要求，这就是PoA活跃证明的由来。PoA的机制与PoW类似，当矿工发现新的区块，他们将选择n个活动节点来广播该区块。n-1个节点验证新区块并对其进行签名，第n个节点除了需要验证和签名以外，还需要将该区块封装并广播该区块。本次过程中，构造新区块的矿工以外，其他参与者也能得到一部分的激励，来保证其一直维持在在线状态。网络通过控制参与者的激励分成比例来控制参与者人数。

2.3.3 空间证明

空间证明(Proof of Spaces, PoSpace)[31]指的是通过用户付出的硬盘空间来竞争出块权利。PoSpace中有两种节点，分别是验证者和证明者。证明者是普通节点只存储区块链的信息，而验证者不仅有存储区块信息，还有一些证明者的信息。PoSpace通过一个特殊函数来选取出块者，存储空间越大对应函数的数字越小。由于付出空间是一次性的，此后的作恶成本变的很低。在竞争出块权时，PoSpace通过计算从主链出发的所有区块的函数值之和来判断，哪个支链上的函数值之和最小，则哪条分叉为主链。在此基础上，为了强调越早的区块所占的比重越高，可增加一个削减函数对早期的区块函数值进行缩减。

2.3.4 权益速度证明

权益速度证明(Proofs of Stake Velocity)[32]是在权益证明的基础上进行优化，促进网络节点的积极参与。在传统的PoS中随着时间的推移，已持有的货币会呈线性积累币龄，这导致了一些长期离线节点的币龄也获得增长，而网络却无法获得其提供的安全性。所以PoSV引入了一种非线性的货币时效功能，在该功能中，交易后的前几天和几周积累的币龄比后几周要快，与长期离线的节点相比，活跃在网络上的节点可多获得奖励。

2.3.5 贡献量证明

贡献量证明(Proofs of Contribution)[33]是对比特币协议的一种扩展，在不改变比特币数据结构的条件下，设定不同地址不同的挖矿难度，并引入黑名单配合实现共识中的惩罚机制。

除了上述的一些证明算法以外，还有幸运证明(Proof of Luck)、融入知识证明的工作量证明(Entangled Proof of Work and Knowledge)、有益工作证明(Proof of Useful Work)等一些类算法。

3 结 论

不同的共识机制都有自己适合的区块链应用场景，证明类算法适合全球性节点的公有链。由于互联网范围内巨大数量的不信任节点的存在，越开放的系统为了能达成共识需要付出更大的代价。证明类算法中，工作量证明类共识算法适用于加密货币类应用，而权益证明类算法则适用于一般性的区块链。而经典的Paxos和Raft算法适合私有链，在节点数量不多时能够高效率的达到共识。拜占庭容错算法则适合只有少量节点的联盟链。在设计区块链系统时宜根据不同的需求采用不同的共识算法，也可以将现有的算法进行融合，设计出最佳的共识机制。