0 引言
2008年，一位化名为“中本聪”的学者提出了比特币概念[1]，随着比特币的火爆，区块链底层技术越来越受到学者们的重视。比特币系统率先引进了区块链的思想，它是一个去中心化加密数字货币系统的典型代表，并为解决分布式系统一致性问题带来了新的技术思想。此外，区块链技术是在多方无须互信的环境下，通过P2P 网络、密码学和共识算法等技术让系统中所有参与方协作来共同记录维护一个可靠的数据日志的方式。其中，共识算法是区块链技术的核心，它决定了整个系统的高效性、安全性和稳定性。目前，越来越多的实体项目与区块链技术相融合，如何选择与实际场景匹配的一款高效、安全和耗能低的共识算法尤为重要。
1 区块链技术概述
区块链是一个公共账本，是一系列包含交易和信息的数据块以顺序相连的方式组合成的链式数据结构[2]。账本可以记录多方资金的往来情况、物品交换情况等。区块链对数据进行分布式加密存储，融合了共识算法、P2P 网络、密码学等多个领域的成果，具有去中心化、天然互信、数据不可篡改等特点[3]。
2 共识算法概述
在分布式系统中，比较普遍的做法是采用共识算法的计算机算法来实现系统中的节点对某个提案
区块链技术中的共识算法对比研究
卢鑫海
云南财经大学，云南 昆明 650221
摘要：随着比特币的火爆，其底层的区块链技术也成为研究的热点，而共识算法是区块链的核心组成部分。现阶段，越来越多的实体项目与区块链技术相融合，如何选择和设计一款适合不同实际场景的共识算法尤为重要。文章首先分别阐述区块链技术、共识算法，接着详细介绍了7种不同的共识算法，再从去中心化程度、资源消耗、吞吐量和时延等指标对7种算法进行比较，最后分析总结出它们的优缺点。关键词：区块链技术；共识算法；对比指标中图分类号：TP311
或交易达成一致性共识的过程，这主要是因为共识算法对分布式系统内部达成一致性共识起到了关键作用。共识算法是区块链的核心组成部分，确保了账本数据在分布式的节点中达成一致。
1982年，美国计算机科学家莱斯利兰伯特(Leslie Lamport)提出了拜占庭将军问题[4]，该问题最早被用来研究分布式对等网络通信容错问题。拜占庭将军问题指在一个有n 个节点的集群内，有m 个恶意节点的情况下，如果n ≤ 3m ，一个正确的共识不可能达成。恶意节点对系统中数据进行篡改或伪造等，
又称拜占庭错误（Byzantine Fault）节点；将发生宕机、网络异常等现象的节点称为非拜占庭错误（Crash Fault）节点[5]。
3 共识算法分类
常见的共识算法可以分为两类，一类是不能解决网络拜占庭错误，而只针对普通节点错误的CFT （Crash Fault Tolerance）类算法，如：Paxos 算法和Raft 算法；另一类是能够解决网络拜占庭错误的BFT（Byzantine Fault Tolerance）类算法，如：PoW、PoS、DPoS 和PBFT 等算法。
3.1 Paxos
Paxos 算法是由Leslie Lamport 在1998年提出的一种基于消息传递且具有较高容错性的一致性算法[6]，主要解决了节点如何在分布式系统中达成共
作者简介：卢鑫海（1995—），男，汉族，重庆垫江人，硕士，就职于云南财经大学信息学院，主要研究方向为区块链技术、共识算法。
识的问题。Paxos 算法中有提议者（Propor）、决策者（Acceptor）、学习者（Leaner）3种类型
的节点。每个节点可以借条
对应一个或多个角色。提议者负责发起提案；决策者负责对提案进行表决；学习者执行表决过的提案。其中提案包括提案编号和提案值，提案编号保证了提案的可区分性，提案值代表提案本身的内容。
3.2 Raft
由于Paxos 不易理解和难以实现，斯坦福大学的Diego Ongaro 设计出了Raft 算法[7]。Raft 算法是一种用于管理日志一致性算法，其核心思想是一组服务器从相同的初始状态开始，以相同的顺序执行相同的指令操作，最终达到一致的状态。在Raft 算法中，有这3种角色：领导者（Leader）、跟随者（Follower）和候选者（Candidate），它们之间可相互转换。领导者负责接收客户端请求，并向跟随者同步请求日志，当大多数节点同步后告诉跟随者提交日志。跟随者负责响应来自领导者的日志负责请求，响应来自候选者的选举请求消防内容
。候选者负责发起选举。Raft 算法一次选举过程中角色状态转换如图1所示。
图1 Raft 算法角色转换
3.3 PoW
PoW（Pow of Work，工作量证明）最初用来解决垃圾邮件问题[8]，在发送邮寄之前，要求邮件发送
方完成一定程度的计算工作，从而提高发送方的成本以减少发送垃圾邮箱的行为。PoW 算法现在一般用于公有链之中，其中最典型的代表是比特币系统。
在比特币系统中，采用PoW 算法保证所有节点对一个待确认交易集合达成共识，该算法的核心是各节点通过比拼算力寻找一个满足区块哈希值的Nonce 值。第一个计算出来Nonce 值的节点获得记账权，可以创建下一个区块，并获得一定数量的比特币作为奖励，即挖矿奖励。此外，每个节点都要认同当前最长的链作为合法主链并努力延长这条链。
只要按照这样的规则确定主链，整个比特币系统就总会达到最终一致的状态，从而解决了共识过程中可能产生的分叉问题。
3.4 PoS
为了解决PoW 算法导致的能源消耗大和计算资源趋于中心化的问题，在2011年Bitcointalk 论坛上，Quantum Mechainc 提出了PoS（Pow of Stake，权益证明）[9]。权益是指节点拥有的资产，根据节点拥有资产的比例决定区块的记账权，拥有资产比例越高，其拥有记账权的概率就越大。PoS 算法的核心思想是用对资产所有权的证明取代算力竞争。
3.5 DPoS
为了解决POW、POS 中的问题，如效率低、趋于中心化等问题，于是，我国在2013年8月启动了比特股项目（BitShares），提出了DPoS（Delegated Proof of Stake，股权授权证明制）。DPoS 的本质是在PoS 的基础上进行了改良，在PoS 中，拥有权益的节点相当于股东，在DPoS 中，通过股东（又称选民）投票出来的一部分委托人（见证人），再由委托人轮流获得记账权。
3.6 PBFT
PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错算法）Miguel Castro 和 Barbara Liskov 在1999年对拜占庭容错算法进行改进后提出[10]，可以容纳1/3的无效或恶意节点。解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级。
在PBFT 共识算法中，用R 表示共识的节点集合，其中|R |表示系统上有|R |个共识节点，编号依次表示为{0，1，2，…，| R | - 1}，假设系统中的恶意节点数量不超过（| R |-1）/3个。所有节点在一个被称为视图（View）的轮换过程中运作。在某个视图中，一个节点作为主节点，其他的节点作为备份节点。视图是连续编号的整数。主节点的计算公式为p = v mod | R |。
PBFT 算法的共识流程分为5个阶段，如图2所示。
开始
发现Leader 或新的任期
超时，开始选举
Follower
Candidate 超时，重新选举
发现具有更长任期的节点
Leader 得到来自Follower
的多数选票后
1）请求阶段，首先客户端发送消息m 给主节点p 。
2）预准备阶段，在收到客户端的请求后，主节点将准备好的消息转发给所有备份节点。消息的格式是<<PRE-PREPARE,v,n,d>,m>，PRE-PREPARE 标示当前消息所处的协议阶段，
v 标示当前视图编号，n 为主节点广播消息的一个唯一递增序号，d 为m 的消息摘要，m 为客户端发来的消息。
3）准备阶段，备份节点收到预准备消息后，会对消息进行检查，检查通过则进入准备阶段。备份节点向其他所有节点广播准备消息<PREPAREv,n,d,i>，其中i 是本节点的编号，可以将PRE-PREPARE、PREPARE 消息写入自己的消息日志。
4）确认阶段，所有副本节点收到2f +1（包括自己）个一致的PREPARE 消息后，会进入Commit 阶段，并且广播消息< COMMIT, v, n, d, i >给其他所有节点，并将确认消息写入自己的消息日志。
5）回复阶段，所有副本节点收到2f +1（包括自己）个一致的COMMIT 消息后执行m 中包含的操作，执行完毕后发送执行成功的消息给客户端。
3.7 VBFT
VBFT 算法由本体公有链平台推出的一种基于可验证随机函数（VRF）的共识算法。该算法结合了PoS、VRF 和PBFT 的思想，本质上是对PBFT 算法
的改善。在VBFT 算法中，首先基于VRF 在共识网络中依次选取每一轮参与共识的节点集，然后由选出的节点集完成共识。
4 共识算法的对比
区块链中运用不同的共识算法会导致系统的整体性能出现差异。下面，我们从去中心化程度、使用规模、容错性、性能正确教育官网
效率和资源消耗对上述7种共识算法进行比较与总结。
4.1 对比指标
去中心化程度：去中心化不是没有中心，而是由所有节点自由选择中心节点，任何中心节点都是阶段性的，而非永久性的，任何中心节点都不具备中央控制权。在每轮共识中，将记账节点作为中心节点，根据记账节点的选取规则和每轮选取的数量来比较算法去中心化程度的高低。
容错性：指共识算法对系统中发生非拜占庭错误节点的容忍值（Crash Fault Tolerance）和发生拜占庭错误的节点的容忍值（Byzantine Fault Tolerance）。容错性也是算法安全性的参考指标之一。
吞吐量：指单位时间内系统处理交易能力，TPS(Transaction Per Second)是其简称。交易吞吐量越大，表示算法的性能效率越高。
时延：指发起交易提案到交易写入区块所花费的时间，用于衡量网络性能和共识算法的运行效率。
图2 PBFT 算法共识流程
Client
Primary0
Replical1
Replical2
Replical3
transacction
pre-prepare
prepare
commit
reply
时延越低，则交易得到确认的速度越快，同时区块链分叉的可能性越低。
资源消耗：指各节点在达成共识的过程中所需消耗的计算机算力、内存、输入输出和电力等资源。
4.2 对比情况
表1对7种共识算法的各个指标进行了对比，表中n表示系统中节点总数量。
表1 7种共识算法各指标对比
共识算法拜占庭
容错
TPS时延
资源
消耗
去中心
化程度
代表性应用
Paxos0>5000秒级低高GoogleChubby Raft0>5000秒级低高braft
PoW n/2<7
10 min
（bitcion）
高高Bitcion
PoS n/25-10
64s
（Blackcion）
较高较高
Blackcion，
peercion
DPoS n/2>500
3s
（Bitshares）
较低较高
Bitshares，
EOS
PBFT n/3>1000秒级较怎么夸女孩
低较高Hyperledger Fabric
VBFT n/3>3000
5～10 s
（ontology）
较低较高ontology
Paxo人物素描图片
s算法资源消耗低，去中心化程度高，但不允许网络中拜占庭节点的存在，只适实习名称
用于私有链，在公有链和联盟链无法发挥作用。Raft算法是Paxos算法的简单实现，其各方面指标与Paxos相似。PoW算法实现了高度去中心化，允许全网有50%的节点出错。矿工节点的参与条件宽松，但它需要矿工付出大量的计算机算力来争夺记账权，这样会导致比较高的资源消耗。与PoW相比，PoS缩短了共识时间，提高了性能，在一定程度上解决了PoW浪费资源的问题。本质上还是挖矿问题，不具备实际应用价值。相比PoW、PoS算法，DPoS算法大幅减少了共识时间，但投票积极性不高，大多数持有权益的节点缺乏时间、精力、技能去参与投票。PBFT算法具有较高的容错性，可同时容忍非拜占庭错误和拜占庭错误，容忍值均为n/3。但当节点数增加到一定程度时，共识效率就会下降。VBFT算法减小了共识节点的规模，从而提高了算法的抗攻击性和性能效率。
5 结语
共识算法保障了区块链系统去中心化的特点，是当今信息科技领域的研究热点。本文对Paxos、Raft、PoW、PoS、DPoS、PBFT、VBFT 7种区块链共识算法的特点和流程进行了详细介绍，并从去中心化程度、资源消耗、吞吐量和时延等指标进行了对比，总结出各算法的优缺点，有利于我们根据
不同的应用场景选择或设计与之相匹配的共识算法。
参考文献
［1］Nakamoto，S.Bitcoin.A peer-to-peer electronic cash system[J],抽搐是什么原因
Consulted，2008（1）：2645-2652.
［2］袁勇，王飞跃.区块链技术发展现状与展望[J].自动化学报，2016，42（4）：481-494.
［3］何蒲，于戈，张岩峰，等.区块链技术与应用前瞻综述[J].计算机科学，2017，44（4）：1-7，15.
［4］L. Lamport, R. Shostak, M. Pea. The Byzantine generals problem[M]. New York: ACM book，2019，203-226.
［5］陆歌皓，谢莉红，李析禹.区块链共识算法对比研究[J].计算机科学，2020，47（S1）：332-339.
［6］LAMPORT L.Paxos made simple[J].ACM SIGACT News，2001，21（4）：51-58.
［7］ONGARO D,OUSTERHOUTJ K.In arch of an understandable connsus algor ithm[C]//USENI X Annual Technical Conference.2014：305-319.
［8］Han R, Foutris N, Kotlidis C. Demystifying Crypto-Mining: Analysis and Optimizations of memory-hard PoW Algorithms[C].2019 IEEE International Symposium on Performance Anal历史上的张飞
ysis of Systems and Software (ISPASS), Boston, 2019：22-33.
［9］Bentov I , Lee C , Mizrahi A , et al. Proof of Activity: Extending Bitcoin's Proof of Work via Proof of Stake[J]. 2014.42（3）：34-
37.
［10］Miguel Castro,Barbara Liskov. Practical Byzantine fault tolerance[P]. Operating systems design and implementation,1999.
