区块链共识算法研究综述

靳世雄 ,张潇丹,葛敬国 ,史洪彬,孙 毅 ,李 鸣 ,林业明 ,姚忠将

1中国科学院大学网络空间安全学院 北京 中国 100049

2中国科学院信息工程研究所 北京 中国 100093

3中国科学院计算技术研究所 北京 中国 100190

4中国电子技术标准化研究院 北京 中国 100007

1 引言

2008年,“中本聪”发表《Bitcoin: A Peer-to-Peer Electronic Cash System》[1],详细描述了去中心化的数字货币[2]交易账本的概念和技术细节; 2009年,比特币系统正式发布; 随后,比特币系统的底层技术——区块链技术进入大众视野。

区块链是一种去中心化、不可篡改、可追溯的分布式数据库系统[3]。区块链系统中底层网络采用对等式网络(P2P网络)组织各个独立的网络节点。P2P网络是扁平式的拓扑结构,网络中的每个节点地位对等,不存在任何中心化的特殊节点和层级结构。因此区块链具备去中心化的特点,系统中各节点相互独立,具备相同的功能,存储同样的信息,相互监督;与传统分布式数据库不同,各个节点独立存储完整的数据,任何组织或个人无法完全控制所有数据,只拥有本地数据的控制权,任何单个节点对本地数据的修改不会对整个区块链产生影响,因此区块链具备难以篡改性; 区块链把数据分成不同的区块,每一个区块头都包含前一个区块的哈希摘要信息,如图1所示,前后顺连形成一条链,因此区块链具备可溯性。总体来说,区块链融合了经济学的博弈论[4]、计算机科学等多种技术,比如P2P网络协议[5],块链结构、共识算法、非对称加密[6-8]、激励机制等,解决了数据可信问题。在无需借助可信第三方的情况下,实现互不信任的多方对等可信的价值传输。

图1 区块链示意图Figure 1 The diagram of blockchain

共识算法是区块链系统中的核心机制,旨在解决系统中各分布式节点数据一致性[9]的问题。在分布式对等网络中,不同节点通过交换信息达成共识,而网络中可能存在恶意节点篡改或伪造数据,或者通信网络也可能导致传输信息出错,从而影响节点间共识的达成,破坏分布式系统的一致性。这个问题于 1982年由 Leslie Lamport、Robert Shostak和Marshall Pease正式建模为“拜占庭将军问题”[10]。传统的分布式系统共识算法大多不考虑拜占庭容错问题,仅考虑网络延时或部分节点出现故障无法响应的情况下,非故障节点如何实现分布式系统的数据一致性。区块链系统运行在更为开放并且缺乏信任的网络环境中,节点数量众多且可能存在恶意节点,因此区块链系统的共识算法设计必须考虑“拜占庭将军问题”。

1985年,由 Michael Fisher、Nancy Lynch 和Michael Paterson共同提出并证明了在分布式系统共识算法的设计中起到重要指导作用的“FLP不可能定理”[11]。该定理指出: 在网络可靠的异步通信系统中,当存在节点故障(即使只有一个)的情况下,不存在协议能保证在有限时间内使系统达成一致。“FLP不可能定理”指出了在可能存在节点失效的分布式异步通信系统中,理论上不存在能使系统在有限时间内达成一致的共识算法。因而研究者们通过调整问题模型来规避“FLP不可能定理”从而寻找工程上可行的共识算法,比如比特币系统中通过假定网络为弱同步性,即网络节点间可以快速同步,以及矿工在一个区块上投入有限的时间等来规避“FLP不可能定理”。

通过调整问题模型规避“FLP不可能定理”,使得共识算法存在“工程解”。2000年,Eric Brewer在一次研讨会的报告中提出了一个猜想: 分布式系统无法同时满足一致性 (Consistency)、可用性(Availability)和分区容忍性(Partition Tolerance),最多只能同时满足其中两个特性,如图2所示。该猜想于2002年被Seth Gilbert和Nancy Lynch在异步网络模型证明,被命名为“CAP定理”[12]。一致性是指分布式系统中所有节点在同一时刻持有同样的数据信息; 可用性是指系统处于服务状态,当客户端发出请求,服务端能在有效的时间内返回结果; 分区容忍性是指允许网络中部分节点不与其他节点通信,即允许网络发生分区(不同区域之间的节点不能建立通信)。“CAP定理”指出即使可以设计出工程上可行的共识算法,这个共识算法也无法完美地做到同时满足一致性、可用性和分区容忍性。该定理的提出为共识算法的设计提供了指导性的原则,使研究者不再追求能同时满足三个特性的共识算法。比如比特币系统的工作量证明(Proof of Work,PoW)共识算法不支持分区容忍性(要求全网节点参与竞争、验证、最后达成共识),同时尽可能满足一致性和可用性。比特币系统首次真正实现了互联网规模的分布式系统的拜占庭容错类共识算法,并且该系统的稳定运行也验证了此类共识算法的可行性。

图2 CAP定理Figure 2 CAP Theorem

迄今为止,研究者已经在共识领域做了大量研究工作,从传统的分布式共识算法,到受 PoW 共识算法启发后涌现的大量应用于区块链系统的共识算法,这些共识算法试图从不同角度解决区块链发展中的问题。本文所做工作: 深入调研并分析区块链共识算法及演化历程; 基于区块链共识算法的共识过程,提出共识算法的分类模型,并对各类型中的代表性共识算法进行详细分析; 从去中心化、可扩展性、安全性、一致性、可用性、分区容忍性六个层面建立区块链共识算法的评价指标体系,并对典型的共识算法进行对比分析,给出各类算法综合性的性能评价。通过对共识算法进行分类以及评价指标体系的建立,期望对未来共识算法的创新提供参考。

本文的后续章节安排如下: 第二节梳理了当前区块链共识算法的演化历程,并展示这些共识算法的发展脉络; 第三节提出区块链共识算法的分类模型,在此基础上,对各类中代表性的共识算法进行详细分析; 第四节提出区块链共识算法的评价指标体系,并对代表性的共识算法进行对比分析,给出各类算法综合性的性能评价。最后第五节对全文进行总结。

2 共识算法的发展

分布式共识算法是分布式计算领域的核心问题,很多研究者为促进其发展做了大量工作[13]。本节按照时间顺序给出共识算法的发展简史,并梳理出这些共识算法的演进关系,如图3所示,箭头方向代表演进方向,比如共识算法A指向B,则代表算法B借鉴算法A; 多个算法比如A和B共同指向C,则代表算法C同时借鉴A和B。

图3 共识算法汇总Figure 3 Summary of consensus algorithms

1982 年,由 Leslie Lamport、Robert Shostak、Marshall Pease正式提出“拜占庭将军问题” ,并给出了基于口头消息和签名消息的解决方案,开创了拜占庭容错类算法的先河。从此,分布式系统共识算法被分为拜占庭容错类算法和非拜占庭容错类算法。由于拜占庭容错类算法(Byzantine Fault Tolerance,BFT)的高复杂度,BFT类算法一直未得到实际应用,直到1999 年,Barbara Liskov 等提出了实用拜占庭容错算法(Practical Byzantine Fault Tolerance,PBFT)[14],将原始拜占庭容错算法的复杂度由指数级降低到多项式级,将拜占庭容错类算法真正引入工程领域。

1988年提出的Viewstamped Replication(VR)一致性算法[15]和1989年提出的Paxos算法[16-18]开创了非拜占庭容错类算法的先河; 基于 Paxos算法,之后出现了多种 Paxos变种算法[19-21]; 除此之外,还有两阶段提交算法(Two-Phase Commit)[22]、三阶段提交算法 (Three-Phase Commit)[23]、Zyzzyva[24]、Zab[25]、Kafka[26]以及2013年提出的Paxos算法简化版——Raft算法[27]。以上这些算法都是非拜占庭容错类算法。

2008年,“中本聪”发表的比特币论文开启了区块链共识算法研究的先河。比特币系统的工作量证明共识算法(Proof of Work,PoW)以基于工作量证明的方式[28-30]开创性地解决了互联网规模的分布式系统拜占庭容错问题。PoW 的核心思想是通过算力竞争达成共识保证数据的一致性,同时保证了比特币系统的安全性和去中心化程度,但同时也带来了电力资源的大量消耗; 2011年权益证明机制(Proof of Stake,PoS)[31]被提出,一定程度上解决了 PoW 电力资源消耗的问题; 2013年提出瑞波共识算法[32],通过使用集体信任的子网络 (Collectively-Trusted Subnetworks),实现了低延迟、高鲁棒性的拜占庭容错共识算法,成功应用于基于区块链技术的金融结算网络; 之后基于Ripple协议,结合BFT算法提出的恒星共识协议[33]是第一个可证明安全的共识协议;同年超级账本锯齿湖项目(Hyperledger Sawtooth)中提出的法定人数投票共识算法(Quorum Voting)旨在确定立即交易的状态; 授权股份证明机制(Delegated Proof-of-Stake,DPoS)[34]也于2013年提出,引入“民主集中式”的共识准则,提升了PoS的可扩展性,但21个超级节点的引入一定程度上降低了去中心化程度; 除此之外,Sleepy Consenus[35]、Ouroboros[36]等共识算法中也应用了节点的权益; 2014年提出的结合PoS和PBFT的Tendermint[37]共识算法以及之后基于Tendermint的改进方案HoneyBadger[38],旨在解决原PoS面临的“无利害关系”问题(Nothing at Stake); 同年提出的Tangaroa共识算法[39]结合PBFT对Raft算法进行改进,继承了Raft算法的简洁易理解特点,同时具有拜占庭容错能力; 之后受 Tangaroa启发演变而来的Scalable BFT算法[40]相比Tangaroa具有更好的性能; 2014—2017年还相继出现了权益流通证明(Proof of Stake Velocity,PoSV)[41]、空间证明(Proof of Space,PoS)[42]、燃烧证明(Proof of Burn,PoB)[43]、活动证明(Proof of Activity,PoA)[44]、消逝时间证明(Proof of Elapsed Time,PoET)[45]、幸运证明(Proof of Luck,PoL)[46]、有用工作证明(Proof of Useful Work,PoUW)[47]等、权威证明(Proof of Authority,PoA)[48]等,以不同的竞争方式替代PoW中的算力竞争以及基于PoW和PoS的二跳(2-hop)算法等解决PoW中的资源消耗和安全问题; 2015年以太坊中提出 Casper协议[49],在PoS中引入权益抵押; 2016年,国内NEO[50]基于 PBFT和 PoS提出授权拜占庭容错(Delegated Byzantine Fault Tolerance,DBFT)共识算法[51],解决了PoW和PoS中的最终一致性问题; 同年,由图灵奖得主Micali提出的AlgoRand共识算法[52],利用密码抽签算法随机选择部分节点参与共识过程,被认为是适用于公链的高可扩展性共识算法; 此外,比特币网络扩展协议 Bitcoin-NG[53],基于 Bitcoin-NG的改进方案 Byzcoin[54]、基于分片技术的共识协议Elastico[55]、以及基于 Elastico和 Byzcoin提出的ByzCoinX方案[56],这些方案从不同的角度提升区块链系统的可扩展性; 2018年也出现了一些代表性的共识算法: 3月 OCE(Ontology Consensus Engine,OCE)项目[57]中应用的可验证拜占庭容错算法(Verifiable Byzantine Fault Tolerance,VBFT)共识算法[58],结合了 PoS、BFT和可验证的随机函数(Verifiable Random Function,VRF)[59]; 5月,康奈尔大学教授EMin Gun Sirer发布了基于 PoW和BFT的共识协议族Snowflake to Avalanche 共识算法[60],简单、高效且安全; 8月,以太坊的创始人 Vitalik Buterin 发表“99% Fault Tolerant Consensus”共识算法[61],仅需要1%的诚实节点就能保障区块链系统的正常运行; 11月,YEE 项目[62]发布的基于知识推理的Tetris共识算法[62],是一种具备最终一致性的高效共识算法。

本节按照时间顺序列出各共识算法,这些共识算法包括传统的分布式共识算法和区块链中应用的共识算法,并梳理出这些共识算法之间的演进关系。第三节将对在区块链中应用的共识算法建立分类模型并描述每类中代表性的算法。

3 共识算法分类

为了对现有的共识算法有更清晰的理解,本节对共识算法的共识过程进行建模,并从共识过程的角度对当前主流的算法进行分类,并详细阐述各类型中的典型共识算法。

算法的共识过程总体上分为三个阶段,如图 4所示: 创建区块、验证区块,提交区块。根据共识协议,从参与共识过程的节点中选择主节点创建新区块(定义主节点为每轮共识过程中产生有效区块的节点); 然后新区块交由其他参与共识的节点进行独立验证; 通过验证的新区块会被节点提交到本地区块链中,达成对最新高度区块的共识; 至此完成共识,开启下一轮共识过程。

图4 共识过程及分类模型Figure 4 The basic consensus process and classification model

共识算法的分类方式有很多,比如在性能层面:从数据一致性的角度将共识算法分为强一致性共识算法、弱一致性(最终一致性)共识算法; 从拜占庭容错的角度将共识算法分为拜占庭容错共识算法、非拜占庭容错共识算法。在应用层面: 可以将共识算法分为适用于公链、联盟链、私链的共识算法。本节从共识过程出发,按照主节点的产生方式将共识算法分为竞争类、选举类、随机类以及其他类型。竞争类: 所有参与共识的节点通过参与特定的竞争方式,在竞争中获胜的节点成为主节点。竞争类共识算法以PoW为代表,还有权益证明、空间证明等等。选举类: 所有节点通过投票的方式选择出部分节点参与共识过程,这些被选择的节点依次轮流成为主节点。选举类共识算法以区块链中应用的传统 BFT类共识算法为代表,比如PBFT、DBFT等。随机类:通过设计特定的随机算法从参与共识的节点中随机选择节点作为主节点。竞争类共识算法以 PoET、Algorand、Ouroboros为代表。以下部分,从共识过程角度对各类中的代表算法进行详细分析。

3.1 竞争类

PoW 共识算法在比特币项目中的成功运用,激发了一系列通过资源、能力、名誉、权益等证明方式来竞争成为主节点的共识算法。比如Peercoin项[63]目中的权益证明(Proof of Stake,PoS)、Parity项目[64]中的权威证明(Proof of Authority,PoA)、Burstcoin项目[65]中的空间证明(Proof of Sapce,PoSpace)、GoChain项目[66]中的信誉证明(Proof of Reputation,PoR)等[67]。从命名方式的角度,这些共识算法应该被称为证明类算法,但从主节点的选择方式角度,相同时间内完成证明最多的节点才成为主节点,因此把这些共识算法归纳为竞争类更为合理。竞争类共识算法在每一轮主节点的选择中,会设置一个竞争成功的标准,最先达到标准的共识节点成为主节点。竞争类算法的共识过程如图 5所示。本小节对典型的PoW、PoS、PoSpace进行详细分析,帮助理解竞争类共识算法。

3.1.1 PoW

PoW 共识算法中,所有参与共识的节点通过消耗算力解决数学难题来竞争成为主节点,由最先解决数学难题的节点成为主节点。在比特币系统中,中本聪采用安全散列算法,将数学难题设计为对区块头信息的双SHA256哈希运算,即:

其中F为双 SHA256哈希运算函数[68],T是目标哈希值,BlockHeader为区块头信息,其中包含Nonce字段,求解合适的Nonce字段使得对完整BlockHeader的哈希运算结果满足目标值要求。

共识过程如图 5所示,第一步全网节点接收并转发交易信息,将接收到的交易信息打包进新区块,然后全网所有节点基于本节点打包的新区块设置区块头中的Nonce字段,计算整个区块头信息的哈希值,使其满足目标值的要求; 率先完成计算工作的节点成为主节点,并将自己的区块广播给其余节点;第二步,未竞争成功的其余节点在接收到新区块后,放弃计算本地新区块,并对接收到的新区块进行验证; 第三步,节点在验证通过新区块后,将其添加到本地区块链,所有节点达成对最新高度区块的共识。

图5 竞争类算法共识过程Figure 5 The consensus process of competition classification algorithms

由于安全散列算法的单向不可逆性,使得 PoW算法难计算易验证。从CPU到GPU再到ASIC矿机,随着算力不断增强,越能快速求解满足条件的Nonce字段值,竞争为主节点的概率也就越大。

PoW 计算密集型属性防止了恶意节点冒充多个节点来实施恶意攻击篡改交易数据等,保障了区块链的安全; 同时带来的一个明显缺点就是耗费大量资源; 另外随着整个网络新区块产生难度的增加,出于成本和收益的博弈,部分亏损的小算力节点会退出比特币系统,整个网络的新区块的生成趋向于算力高的节点,中心化程度增加。Eyal等[69]提出PoW共识还存在自私挖矿攻击的风险,自私挖矿的收益比例大于其在全网的算力比例,促使理性的节点加入自私挖矿矿池,算力集中之后进一步增加 51%攻击的风险。

3.1.2 PoS

Peercoin项目[63]中实现的 PoS共识算法是为了降低算力的消耗。PoS延续了PoW算法的竞争理念,只不过相对于PoW中Nonce字段的大搜索空间而言,PoS将搜索空间限制在一个计算量可接受的范围;除此外,PoS中还引入了“币龄”作为权益,即:

其中,Coinage是“币龄”,Coin为持有的货币,Age为持续持有的时间。通过减小搜索空间以及引入“币龄”,PoS将数学问题设计为:

其中F为双SHA256哈希运算函数;BlockHeader为区块头信息,其中包含Timestamp字段,取值范围是上一个区块时间和当前时间之间,远小于 PoW 中Nonce字段的搜索空间大小;Weight是用于竞争所消耗的“币龄”权重,T是目标哈希值,与PoW中的T相同。

PoS的共识过程与PoW一致,唯一不同是解决的数学问题不同,其余过程均如图5所示。

与PoW相比,PoS的数学问题中自变量的搜索空间减小,同时不等式右侧引入“币龄”权重,对于同一T,在每轮竞争中所投入的“币龄”越多,权重越大,竞争中获胜的概率也越大。

PoS将算力竞争转化为权益竞争,不仅节约算力,权益的引入也能够防止节点发动恶意攻击; 同时促使所有节点有责任维护区块链的安全稳定运行以保障自身权益; PoS虽然降低了算力资源的消耗,但是没有解决中心化程度增强的问题,新区块的生成趋向于权益高的节点。PoS中需要拥有超全网一半的权益发动 51%攻击,但其成本高于拥有超全网一半的算力[70],另外创建区块需要消耗权益,使得PoS持续进行 51%攻击的难度增加,一定程度上降低了安全风险[31]。

3.1.3 PoSpace

Burstcoin项目[65]中的共识算法为 PoSpace,基于存储空间的竞争机制。在PoSpace中节点分为普通节点和校验节点两种角色。普通节点下载特定序列的数据块(由节点用户公钥决定)占据硬盘空间参与主节点的竞争,校验节点存储普通节点的部分存储信息以便验证普通节点。

在每轮创建新区块的竞争中,校验节点向普通节点发起“挑战”,“挑战”为普通节点所存储数据块的某种随机组合。普通节点根据“挑战”信息,生成对应组合数据的哈希摘要,由校验节点验证哈希值是否正确,验证通过则说明普通节点确实存储了相应的数据。PoSpace中定义了一个质量函数作为竞争指标:

其中,hash为普通节点被验证通过的哈希值,S为数据占用存储空间的大小。在每轮竞争中,质量函数结果最小的节点获胜。

PoSpace的共识过程第一步通过占用存储空间加入网络,然后对“挑战”得到的哈希结果计算质量函数,质量函数结果最小的节点成为主节点,将区块广播给其余未竞争成功的节点; 第二步其余节点对接收到的新区块进行验证,验证通过后进入第三步将新区块提交到本地区块链,达成对最新高度区块的共识。从质量函数的定义可以看出,数据占用空间S越大,质量函数值越小,获胜的概率越大。

PoSpace共识算法使用存储空间代替计算,节约电力资源; 同时该共识协议下,节点初次接入网络时确定存储空间大小,之后不能扩容,防止了 PoW共识算法中“矿池”(将不同节点的算力集合成一个大的算力节点)的出现,一定程度上避免了中心化程度增强的问题,同时降低了安全风险。

3.2 选举类

除了竞争方式选择主节点外,也可以通过选举的方式选择主节点。所有节点投票选择,根据投票结果,有的共识算法是产生一个主节点集合,由这些节点依次轮流成为主节点; 有的共识算法是只产生一个主节点负责创建区块,下一轮重新投票。选举类的共识过程如图6所示,第一步是选出信任节点集合,信任节点依次轮流作为主节点; 第二步是区块验证,区块验证方式分类两大类,一类与竞争类算法相似,主节点广播区块到其余节点进行验证,一类是主节点的区块经过三轮 BFT类的投票过程进行验证; 第三步是节点提交通过验证的区块,达成共识状态。本节选择授权股份证明算法(DPoS)、实用拜占庭容错算法(PBFT)、授权拜占庭容错算法(DBFT)进行描述,帮助理解选举类的共识算法。

图6 选举类算法共识过程Figure 6 The consensus process of delegation classification algorithms

3.2.1 DPoS

EOS项目[71]中实现的DPoS共识算法旨在解决PoS中主节点的产生趋向于高权益节点的问题,同时提高了PoS的共识效率。

DPoS在PoS中引入选举机制。DPoS将节点分为普通节点和信任节点两种角色。普通节点可以投票选择信任节点或者被投票成为信任节点。在DPoS中,节点消耗权益作为投票权,根据权益的加权结果产生最受信任的N个节点成为信任节点集合D{D1,… ,DN},每个信任节点Di,i=1→N依次被赋予固定的期限(比如 2秒)成为主节点,授权时间结束后,创建权依次交由下一个信任节点。信任节点集合D循环结束之后,重新选举调整D,恶意节点将在下轮选举中失去其他节点的信任。

共识过程仅由信任节点集合D中所有节点参与,当下被授权的信任节点Di创建新区块后广播到其余信任节点Dj≠i进行验证,在验证成功后将区块添加到本地,达成对最新高度区块的共识。

通过基于权益的民主投票产生信任节点集合,每个节点都可以参与到信任节点的选择上,Di轮流作为主节点,避免了主节点的产生趋向于高权益节点的问题,但选举的信任节点全权负责创建区块,这在一定程度上降低了去中心化程度; 同时仅由D{D1,… ,DN}进行验证,使得共识效率得到提升;另外,区块的产生不需要消耗算力,相对于PoS更加节省能耗。

3.2.2 PBFT

Fabric v0.6.0[72]中实现了PBFT共识算法。该共识算法从全网节点选择一个主节点负责创建区块,然后经过三阶段投票达成共识: 预准备阶段,准备阶段,提交阶段。如图7所示,主要过程如下:

预准备阶段: 从全网选择一个主节点; 每个节点把客户端发来的交易信息向全网广播,主节点收集所有交易信息,创建新区块并向全网广播;

准备阶段: 每个节点在收到主节点发送的区块信息后,从预准备阶段进入到准备阶段,节点对区块进行验证,验证通过后向其他节点广播一条准备消息;

提交阶段: 节点在向全网广播准备消息之后进入提交阶段,如果节点收到超过2/3节点的准备消息,就向全网广播一条提交消息; 如果一个节点收到超过2/3节点的提交消息,即可提交新区块到本地区块链,达成对最新高度区块的共识。

PBFT中无权益的抵押或竞争资源的消耗,使得恶意节点的成本降低,PBFT通过三阶段的投票机制排除恶意节点对共识的影响,提供不超过1/3总节点数量的容错能力,但O(N2) 的通信复杂度使得系统性能随着网络规模的增加而下降。

图7 PBFT三阶段示意图Figure 7 The three-phase process diagram of PBFT

3.2.3 DBFT

NEO项目[50]中提出DBFT算法。DBFT改进自PBFT算法,PBFT算法共识过程需要全部节点的参与,且需要通过3轮网络请求确认来达成共识,网络通信复杂度为O(N2),N为全网节点的数量,可扩展性差,随着网络规模增加,难以快速达成一致。NEO的解决方案是投票选取出部分节点参与共识,由此减少网络通信消耗、提高可扩展性、同时提升交易处理速度。

DBFT共识过程: 所有节点投票选举记账节点集合(记账节点即信任节点,此处为了遵从原算法的描述),记账节点集合完成共识过程,其余节点为非记账节点,不参与共识过程,只采纳最终的共识结果。接下来由记账节点集合中选举出议长(议长即负责创建区块的主节点),其他记账节点为议员; 在每轮共识中,议长提出新区块,由议员进行确认并广播确认结果; 当节点收到超过 2/3记账人节点发送的确认消息后,则在本地添加区块,即对最新高度的区块达成共识; 之后重新选择议长,开启新一轮共识过程。

DBFT将共识过程的参与范围缩小为选举出来的记账节点集合,虽然通信复杂度依然为O(N2),但是缩小了共识节点网络规模,减少达成共识的通信成本。安全性上,DBFT被证明在恶意节点少于总节点数量1/3的情况下也可能导致网络分叉[73]。DBFT 2.0中[74]通过增加commit阶段,避免出现分叉,并增加两种状态恢复机制,使得离线共识节点可以更快地从异常情况中恢复,虽然提升了 DBFT算法的可靠性,但安全性依然没有得到彻底解决,目前仍在完善。

3.3 随机类

除竞争、选举外,也可以通过随机方式选择主节点。对于随机方式,可以设计随机函数使得每个节点成为主节点的概率与节点所持有的某种资源成比例,也可以设计随机函数使得每个节点成为主节点的概率相等。随机类的共识过程与竞争类共识过程相似,如图 5所示,只是第一步通过随机算法随机选择主节点。本节描述衔尾蛇(Ouroboros)、消逝时间证明(PoET)两个共识算法,帮助理解随机类的共识算法。

3.3.1 Ouroboros

Cardano项目[75]中Ouroboros共识算法的核心思想是根据节点权益大小,随机地选出主节点,节点权益越大被选中的概率越大。

如图8所示,Ouroboros共识算法将时间分段划分,一个时间段称为一个epoch; 以epoch为周期,每个epoch中划分多个时间slot; 每个slot时间期限内,由随机算法随机选择主节点,该随机算法在数学上证明是不可被预知的。

其中,S为权益持有者候选人集合,ρ为随机种子,slj表示该epoch中第j个slot,Si∈S表示主节点。该随机算法从候选人集合S为每个slot选择主节点。在整个epoch周期中,S和ρ不变,直到周期结束之后,产生新的ρ,更新S,开启下一个epoch周期。

图8 Ouroboros示意图Figure 8 The diagram of Ouroboros

每个节点根据当前epoch的种子ρ,执行随机函数F获得当前slot主节点; 若是自己,则打包交易,创建区块; 否则等待主节点出块并广播,对接收到的区块进行验证,如果长时间未收到(超出一个slot的时间)则认为当前slot无区块产生; 在当前epoch中不断重复这个过程直到这个epoch中的所有slot结束。

与选举类相似,随机产生主节点的方式也会减少资源的消耗; 但不同于选举类中主节点的产生需要节点之间网络通信进行投票,随机类使用随机算法产生主节点的方式无需网络通信,缩短了共识时间,提高了共识效率,增强可扩展性。Aggelos Kiayias等[76]对Ouroboros的安全性给出了严密的证明,并提出了全新的奖励机制防止自私挖矿攻击。

3.3.2 PoET

PoET虽然从名字看像是竞争类的共识算法,但本质上是通过随机时间长短来选择主节点。

基于Intel CPU的SGX(Software Guard Extensions)技术,Intel在超级账本的锯齿湖项目中提出并实现了PoET共识算法。在这种机制下,每个节点等待一定的随机时间,该随机时间满足预定的概率分布函数F,最先结束等待时间的节点成为主节点。

其他节点进行验证,通过两种方式验证节点确实等待了一定的随机时间。第一,产生区块的同时在SGX的协助下产生一个等待时间的证明 ,随同区块一起广播给其他节点进行区块验证以及等待时间验证; 第二,应用概率统计测试来检验节点的等待时间是否符合预定的概率分布F。

PoET共识算法将信任依托于硬件,使得区块链系统不必耗费大量算力,实现了“一CPU一票”的公平性。每个节点成为主节点的概率相等,但不能排除用户通过增加CPU资源提高出块概率,从而使中心化程度增强。PoET面临硬件安全造成的单点故障风险,恶意节点只需攻破一台SGX就可以控制出块权。

3.4 其他类

3.4.1 Ripple

Ripple联盟链[77]项目中提出并实现了RPCA共识算法。RPCA中引入了一个新的概念: 独立节点列表(Unique Node List,UNL)。这是一份“信任”列表,这里的“信任”指的是节点相信这个列表里的节点不会联合起来作恶,不需要相信这个列表里的每一个节点。每个节点维护自己的UNL,各个节点的UNL相互独立,可能相同也可能不同。

共识过程如下:

1.共识开始之前,每个节点接受所有的交易,放到本地的“交易候选集”;

2.每个节点把自己UNL列表中的节点各自维护的“交易候选集”合并到自己本地,然后以UNL为单位对每笔交易进行投票;

3.当UNL中超过一定数量比例的节点都认为某笔交易正确的时候,这笔交易进入第4步; 没有达到要求的交易要么被丢弃,要么继续被留在“交易候选集”中等待下一轮共识过程开始后重新被投票;

4.共识过程的最后一步,对于第 3步中通过的交易,如果在这一步UNL中超过80%的节点都认为该笔交易正确,则这笔交易满足共识要求。所有满足这一要求的交易被添加进账本。

RPCA共识算法能够容忍不超过 20%数量的拜占庭错误节点即可保证区块链系统的可用性; 对于一致性而言,该共识算法对节点的UNL选择有如下要求:

图9 连接性示意图Figure 9 The diagram of connectivity

3.4.2 分片共识算法

当前区块链面临的一大问题是交易性能低。竞争类和随机类共识算法中系统性能等价于单节点性能,选举类共识算法由于O(n2)的通信复杂度会使得随着节点数量的增加整体的交易性能下降。分片技术中,全网节点划分为不同的分组(委员会),每个分组并行处理不同的交易集。其关键技术在于设计合理的分片方式以及解决分片交易的原子性问题。Elastico[55]是第一个基于分片技术的拜占庭容错公链方案,之后出现众多改进方案,比如OmniLedger[56]、RapidChain[78]等。

以Elastico为例说明分片技术方案。Elastico周期性地共识区块,每个周期内,节点执行以下操作:

1.身份获取和委员会分配: 每个节点产生一个身份信息,身份信息由公钥、IP地址和一个PoW难题解组成,PoW 难题解是为了防止恶意节点伪造多个身份信息,之后根据身份信息将节点划分到不同的委员会;

2.委员会内部节点发现: Elastico通过建立“目录服务委员会”,节点可以高效地与同一委员会内部的其他成员建立通信连接;

3.委员会内部共识: 委员会内部运行 PBFT共识算法对交易集达成共识,将共识结果发送到“共识委员会”;

4.最终共识: “共识委员会”接受其他委员会的共识结果并重新打包交易,运行PBFT共识算法达成最终共识并向全网广播;

5.产生随机数: “共识委员会”产生一组随机数,用于下一周期中节点重新构建身份信息。

分片技术通过并行处理提升系统性能,使其随着全网节点数量的增多而线性提升; 另外每个节点只存储部分数据,减少了节点数据存储压力。Elastico中也存在一些问题,比如没有解决原子性交换问题,当分片拒绝某笔跨片交易后,原分片中的交易资产被永远锁定。

3.4.3 基于DAG共识算法

除了分片技术外,也可以通过有向无环图(Directed Acyclic Graph,DAG)的结构提升区块链系统的交易性能,基于 DAG的加密货币项目有Obyte[79](Byteball)、DagCoin[80]、IOTA[81]等。DAG中的每个单元代表用户发起的一笔交易,每一条从子单元指向父单元的有向边代表一种验证关系,即用户创建交易的时候需要对先前的交易单元进行验证,将验证有效的交易单元的哈希值包含到自己的交易数据结构中,则当前的交易单元称为子交易,被验证的交易称为当前交易的父交易,每笔交易可以有多个父交易,每个交易也可以有多个子交易,这样交易单元构成有向无环图的结构,如图10所示。

图10 基于DAG共识数据存储图示Figure 10 The diagram of data unit stored based on DAG

以Obyte为例展示基于DAG模式的交易过程:

1.创建交易: 当用户需要发起交易时,创建一个交易单元,按照交易单元数据结构填充对应的内容,包括消息类型、签名、以及一个或多个先前交易单元的哈希值;

2.广播交易: 交易创建完成后,将交易单元向全网广播;

3.验证交易: 其他节点接收交易,之后发起交易时会选择验证当前交易是否有效。

Obyte系统中选择12个可信的“证人”节点,这些节点发起的交易按照先后顺序连接成为一条主链,如图10中按顺序编号的链为主链,出现双花交易时,根据交易单元与主链中交易单元的关系选择有效交易[80]。

从以上的过程中,可以看出 DAG模式中,没有矿工和区块,节省了交易费以及产生主节点打包区块的时间,交易得到及时确认。这种异步并发处理交易的模式使得DAG具有高可扩展性,但高并发情形下可能短时间内出现数据不一致的问题,不适合强一致性的场景。

本节建立了共识算法的分类模型,将共识算法分为四类: 竞争类、选举类、随机类和其他类型; 每种类型中描述典型的算法共识过程,帮助更好地理解各共识算法及分类模型。在此基础上,第四节从六个维度建立共识算法的评价指标,并对各类型算法进行对比分析,给出各类算法在不同性能上的表现。

4 评价体系

以太坊项目中,Vitalik Buterin提出区块链DSS猜想[61]: 区块链系统中不能从去中心化(Decentralization)、安全性(Security)和可扩展性(Scalability)三个方面同时做到提升。区块链的去中心化是指网络的控制权分散到整个网络,而不是被少数用户集中控制。既要保证用户公平地参与网络,即使得参与用户的收益比例与资源投入比例尽可能相近[82],同时防止网络的控制权被少数用户控制,网络的控制权越分散,即各用户创建区块的权利越平均,网络的去中心化程度越高。区块链系统中面临的安全性问题主要有密码学安全性、网络安全性、数据安全性、共识算法安全性等,比如比特币系统的51%算力攻击,即恶意节点的算力超过全网一半的算力时,这些恶意节点就可以联合起来对比特币系统强行分叉,通过删除或修改交易信息构造新区块取代原来的正常交易数据,实现双重支付等,破坏比特币系统的安全性。区块链的可扩展性指区块链系统处理高业务量的能力。区块链可扩展性主要面临以下三点挑战[83]: (1)分布式系统的网络延迟,区块链系统节点间网络距离以及网络环境无法控制,所以在网络延迟上比传统的分布式系统受到更大的限制。(2)区块链的一致性,区块链要维护节点间的一致性需要大量节点的确认。一般来说,越是强的一致性确认计算开销也会越大,同时系统规模越大达成一致的成本也越高。(3)节点性能限制,比如PoW这类共识算法本身就会消耗大量的计算资源,在效率上存在一定限制。同时随着区块链数据量的不断累加,要想达到较高的交易率,极大的数据量对于节点的吞吐量有很高的需求。

在比特币和以太坊中,出于去中心化和安全性的考虑,系统中每笔交易都需要全网节点广播,全网节点验证,并且每个新区块的创建都需要全网节点共同竞争,提升去中心化程度和安全性; 共识过程需要全网节点的参与,使得共识过程中网络通信复杂度增高,系统处理性能低效,限制了系统的可扩展性。EOS项目中采用的DPoS共识算法,采用21个超级节点参与共识过程,这些被认为可信的超级节点按照顺序创建区块,提升了区块链系统的性能,可扩展性得到提升,但是降低了区块链去中心化程度。

DSS猜想仅是Vitalik Buterin用来解构区块链性能问题的方式,理论上并不严谨和完整,但依然给区块链共识算法的研究者们提供了一个性能研究的切入点。

本节将从去中心化、可扩展性、安全性、一致性、可用性、分区容忍性六个方面建立共识算法的评价指标体系。去中心化要求所有的节点具有相等的地位,在共识算法中即要求所有节点能够参与共识过程且每个用户出块的权利越平均,网络的控制权越分散,去中心化程度越高。进一步将去中心化细化为共识节点数量、主节点选择方式、共识节点权重三个指标,综合这三个指标建立去中心化程度指标。共识节点数量描述的是全网节点都参与共识过程还是部分节点参与共识过程; 主节点的选择方式描述主节点是通过竞争、选举或随机的方式产生; 共识节点权重描述在每轮共识过程中,共识节点成为主节点的概率是否相等。可扩展性方面,系统处理高业务量的能力越强,可扩展性越强。处理高业务量的能力主要受到单个节点的性能和网络通信成本等因素的影响。进一步将可扩展性分为资源消耗、通信复杂度两个指标,综合这两个指标对可扩展性程度进行评价。资源消耗是指共识过程对计算、存储、网络等资源的消耗程度,资源消耗限制单个节点的性能; 通信复杂度是指共识算法的网络通信复杂度,旨在刻画网络通信成本(N代表共识节点数量)。共识算法的安全性主要受到容错能力、对恶意节点的处理能力、潜在的攻击方式种类及数量、攻击难易程度、以及遭受安全攻击后的恢复能力等因素的影响。进一步将安全性细化为容错度、节点可控性、攻击多样性、攻击成本、安全恢复性,综合这五个指标评估共识算法安全性。容错度是指共识算法保证区块链系统达成共识所能接受的拜占庭恶意节点(或算力等)在全网中的最大占比; 节点可控性是指共识算法是否具有排除恶意节点参与共识过程的能力; 攻击多样性是指共识算法可能面临的攻击方式的种类及数量,种类及数量越多,则潜在的安全风险越高,目前区块链共识算法可能面临的安全攻击主要包括:针对安全性假设的攻击、影响可扩展性的攻击和针对激励机制的攻击等; 攻击成本是指恶意节点发动安全攻击所消耗的代价,代价越高,发动攻击的难度越大; 安全恢复性是指区块链受到安全攻击后,使数据恢复到攻击发生之前安全状态的能力,进行硬分叉的可能性越高,安全恢复性越强。去中心化程度、可扩展性和安全性是从DSS猜想的三个特性评价共识算法,接下来从“CAP定理”的一致性、可用性和分区容忍性三个特性评价共识算法。进一步将一致性层面分为分叉可能性、最终一致性。分叉可能性是指区块链产生分叉的概率大小; 最终一致性是指各节点的数据是否在有限时间内达成一致,综合这两个角度刻画共识算法的一致性程度。可用性指标描述系统是否一直处于服务状态; 分区容忍性指系统是否允许部分节点不与其他节点通信。

以下基于评价指标体系,从6个方面对各类算法进行对比分析,如图11所示。去中心化程度方面,竞争类全网节点全部参与共识过程,但是每个节点成为主节点的概率不等,与节点拥有的竞争资源有关,这就造成在实际区块链系统中部分拥有大量竞争资源的节点垄断了主节点。选举类算法各节点投票选择主节点,之后仅由选定的节点创建区块,比如EOS中选出21个超级节点轮流负责创建区块,这在一定程度上降低了去中心化程度。Ripple算法每个节点维护一个信任节点列表,各节点地位相等,去中心化程度高。可扩展性方面,竞争类共识算法属于资源消耗型,单个节点的性能受到很大限制,因此性能效率偏低,处理大规模业务量能力差,可扩展性程度低; 选举类共识算法虽然共识过程不需要消耗大量资源,单个节点性能得到提升,但是通信复杂度高,且随着网络规模增加,通信成本会限制可扩展性的提升,但相比竞争类共识算法,可扩展性得到提升; 随机类共识算法共识过程即不需要消耗大量资源,网络通信复杂度也没有选举类算法高,可扩展性比选举类更好; Ripple算法通过将全网节点分为多个共识组提高了可扩展性。安全性方面,竞争类共识算法容错度高于部分其他类算法,选举类算法对节点的可控性强,发现恶意节点之后可以在下一轮主节点的选举过程中将其排除,竞争类算法面临的攻击多样性高,以 PoW 为例,安全性假设层面存在51%攻击、日蚀攻击[84]等,可扩展性层面存在粉尘攻击、空块攻击等; 激励层面存在自私挖矿攻击[69]、扣块攻击[85]等,三个层面均面临潜在的安全攻击,攻击多样性相对较高。选举类和随机类算法也存在一定的安全攻击,但针对这两类算法的安全攻击方式相对较少,相比于以PoW为代表的竞争类算法,其攻击多样性相对较低。从攻击成本角度,相比选举类和随机类,竞争类算法中由恶意节点发动较强破坏性安全攻击的成本较高,比如 PoS中发动51%攻击,需要控制超过全网一半的权益,发动安全攻击的难度较大。从安全恢复性角度,选举类算法由选择的少数节点维护共识,通过硬分叉进行安全恢复的能力强于竞争类和随机类算法。实际中,采用PoW算法的比特币已经发生过数次大规模的硬分叉,说明竞争类算法也具有一定的安全恢复能力。一致性方面,竞争类算法由于网络延时的存在,可能出现在短时间间隔内出现多个达到竞争标准的节点,因此有分叉的可能性,不具有最终一致性; 对于选举类和随机类,算法在同一时间只产生一个主节点,因此没有分叉的可能性,具有最终一致性; Ripple算法在满足连接性要求的情况下,也不会产生分叉。一致性方面,与竞争类共识算法相比,选举类、随机类和 Ripple算法具有强一致性。对于可用性和分区容忍性两个角度,四大类共识算法均具有高可用性,不支持分区容忍性,满足“CAP定理”。综上所述,可以看出四大类算法在一致性、可用性和分区容忍性层面都致力于满足一致性和可用性,牺牲了分区容忍性,满足“CAP定理”; 与“CAP定理”只能满足其中两个特性不同,“DSS猜想”是指去中心化程度、可扩展性、安全性三个层面的性能无法同时得到提升。竞争类算法具有更高的安全性,在安全性不如竞争类的情况下,随机类和 Ripple算法提升了去中心化程度和可扩展性。因此,网络环境更为复杂的公链中多采用竞争类算法,比如规模最大的公链比特币采用PoW,以太坊拟采用PoS; 而联盟链则多采用选举类、随机类和其他类的共识算法,比如Hyperledger Fabric中采用PBFT算法,Hyperledger Sawtooth中采用的PoET算法,Ripple联盟链中采用的Ripple共识算法。

图11 共识算法评价指标Figure 11 The evaluating indicators of consensus algorithms

本节从去中心化、可扩展性、安全性、一致性、可用性、分区容忍性六个方面建立了共识算法的评价体系并完成了初步的定性分析。Garay等[86]提出比特币骨干协议,并对比特币的一致性(Persistence)和可用性(Liveness,也称活性)进行定量分析。该协议中提出公共前缀和链质量两种特性,并得出一定算力约束条件下这两个特性的概率大小,进而量化比特币的一致性和可用性,分析得出在网络同步速率大于出块速率且恶意节点的算力严格小于全网算力50%的条件下,比特币具有高一致性和可用性。比特币骨干协议分析、抽象比特币协议,提取关键元素、提出并证明新特性,并通过重新实现比特币,借助新特性来证明比特币的相关特性,这种分析方法为后续对共识算法评价指标体系设计对应的定量分析方法提供了有效参考。

5 总结与展望

共识算法是区块链系统的核心机制之一,获得了研究人员和产业界的广泛关注。近年来区块链项目中涌现出各种共识算法,但缺乏完整技术分类和统一评价体系。本文深入分析区块链共识算法,从共识过程本身出发,提出了共识算法的分类模型,按照主节点的产生方式将共识算法分为竞争类、选举类、随机类及其他类型,并剖析了每种类型中代表性共识算法的共识过程及其优劣势; 同时从去中心化、可扩展性、安全性、一致性、可用性、分区容忍性六个方面建立了一套共识算法的评价指标体系,在此基础上,对各类共识算法进行初步的对比分析。

后续的研究重点将在此评价指标体系和评价分析的基础上,结合区块链的应用场景,借鉴比特币骨干协议等的分析方法,针对共识算法设计对应的评测方法,进一步开展科学化分析,给出区块链共识算法在应用场景中的定量评价,为不同的应用场景选择合适的共识算法提供参考。