万字长文：解读区块链7类共识算法
摘要：本文将对区块链中常见的七类共识算法进行介绍，希望对读者探索区块链有所帮助。
区块链技术起源于比特币，最初是比特币等数字货币的一种底层技术，区块链融合了密码学、组网技术、共识算法、智能合约等多种技术。随着区块链技术的逐渐成熟，其逐渐得到科研机构、政府、金融机构和科技企业的关注。区块链具有匿名、防篡改、可追溯和去中心化等特点。
传统的交易需要一个可信任的第三方作为交易中介，与之相比，区块链技术能够实现交易的去中心化，同时还能保证全网数据的一致性，使得点对点交易成为可能。这需要对交易确认规则进行设计，这一规则就是本节将要介绍的共识算法。共识算法作为区块链技术的核心，对区块链安全、效率等方面有着决定性的作用。
在区块链的应用过程中，共识算法需要解决两个问题：双花问题[1, 2]和拜占庭将军问题[3]。双花问题是指货币在使用过程中重复使用的问题。传统的货币具有实体唯一性，可以通过防伪手段防止双花问题。当前的电子交易也能通过中心的信任机构来解决双花问题。区块链则是通过分布式的节点共同验证交易来解决双花问题。区块链中，一笔交易需要经过足够数量共识节点的验证，在确认无误下对交易进行记录并同步给网络中所有的共识节点。区块链中进行“双花”攻击完成需要付出足够的代价，通过选择共识算法，可以将这一代价扩展到足够大或者使得这一代价超过双花攻击获得的收益。
本文将对区块链中常见的七类共识算法进行介绍，希望对读者探索区块链有所帮助。
1. 工作量证明（PoW）
中本聪在2009年提出的比特币（Bitcoin）是区块链技术最早的应用，其采用PoW作为共识算法，其核心思想是节点间通过哈希算力的竞争来获取记账权和比特币奖励。PoW中，不同节点根据特定信息竞争计算一个数学问题的解，这个数学问题很难求解，但却容易对结果进行验证，最先解决这个数学问题的节点可以创建下一个区块并获得一定数量的币奖励。中本聪在比特币中采用了HashCash[4]机制设计这一数学问题。本节将以比特币采用的PoW算法为例进行说明，PoW的共识步骤如下：
- 节点收集上一个区块产生后全网待确认的交易，将符合条件的交易记入交易内存池，然后更新并计算内存池中交易的Merkle根的值，并将其写入区块头部；
在区块头部填写如表1.1所示的区块版本号、前一区块的哈希值、时间戳、当前目标哈希值和随机数等信息；
表1.1 区块头部信息
- 随机数nonce在0到232之间取值，对区块头部信息进行哈希计算，当哈希值小于或等于目标值时，打包并广播该区块，待其他节点验证后完成记账；
- 一定时间内如果无法计算出符合要求的哈希值，则重复步骤2。如果计算过程中有其他节点完成了计算，则从步骤1重新开始。
比特币产生区块的平均时间为10分钟，想要维持这一速度，就需要根据当前全网的计算能力对目标值（难度）进行调整[5]。难度是对计算产生符合要求的区块困难程度的描述，在计算同一高度区块时，所有节点的难度都是相同的，这也保证了挖矿的公平性。难度与目标值的关系为：
难度值=最大目标值/当前目标值 （1.1）
其中最大目标值和当前目标值都是256位长度，最大目标值是难度为1时的目标值，即2224。假设当前难度为，算力为，当前目标值为，发现新区块的平均计算时间为，则
根据比特币的设计，每产生2016个区块后（约2周）系统会调整一次当前目标值。节点根据前2016个区块的实际生产时间，由公式（1.4）计算出调整后的难度值，如果实际时间生产小于2周，增大难度值；如果实际时间生产大于2周，则减小难度值。根据最长链原则，在不需要节点同步难度信息的情况下，所有节点在一定时间后会得到相同的难度值。
在使用PoW的区块链中，因为网络延迟等原因，当同一高度的两个区块产生的时间接近时，可能会产生分叉。即不同的矿工都计算出了符合要求的某一高度的区块，并得到与其相近节点的确认，全网节点会根据收到区块的时间，在先收到的区块基础上继续挖矿。这种情况下，哪个区块的后续区块先出现，其长度会变得更长，这个区块就被包括进主链，在非主链上挖矿的节点会切换到主链继续挖矿。
PoW共识算法以算力作为竞争记账权的基础，以工作量作为安全性的保障，所有矿工都遵循最长链原则。新产生的区块包含前一个区块的哈希值，现存的所有区块的形成了一条链，链的长度与工作量成正比，所有的节点均信任最长的区块链。如果当某一组织掌握了足够的算力，就可以针对比特币网络发起攻击。当攻击者拥有足够的算力时，能够最先计算出最新的区块，从而掌握最长链。此时比特币主链上的区块大部分由其生成，他可以故意拒绝某些交易的确认和进行双花攻击，这会对比特币网络的可信性造成影响，但这一行为同样会给攻击者带来损失。通过求解一维随机游走问题，可以获得恶意节点攻击成功的概率和算力之间的关系：
图1.1 攻击者算力与攻击成功概率
2. 权益证明（PoS）
随着参与比特币挖矿的人越来越多，PoW的许多问题逐渐显现，例如随着算力竞争迅速加剧，获取代币需要消耗的能源大量增加，记账权也逐渐向聚集了大量算力的“矿池”集中[6-9]。为此，研究者尝试采用新的机制取代工作量证明。PoS的概念在最早的比特币项目中曾被提及，但由于稳健性等原因没被使用。PoS最早的应用是点点币（PPCoin），PoS提出了币龄的概念，币龄是持有的代币与持有时间乘积的累加，计算如公式（1.4）所示。利用币龄竞争取代算力竞争，使区块链的证明不再仅仅依靠工作量，有效地解决了PoW的资源浪费问题。
其中持有时间为某个币距离最近一次在网络上交易的时间，每个节点持有的币龄越长，则其在网络中权益越多，同时币的持有人还会根据币龄来获得一定的收益。点点币的设计中，没有完全脱离工作量证明，PoS机制的记账权的获得同样需要进行简单的哈希计算：
其中proofhash是由权重因子、未消费的产出值和当前时间的模糊和得到的哈希值，同时对每个节点的算力进行了限制，可见币龄与计算的难度成反比。在PoS中，区块链的安全性随着区块链的价值增加而增加，对区块链的攻击需要攻击者积攒大量的币龄，也就是需要对大量数字货币持有足够长的时间，这也大大增加了攻击的难度。与PoW相比，采用PoS的区块链系统可能会面对长程攻击（Long Range Attack）和无利害攻击（Nothing at Stake）。
除了点点币，有许多币也使用了PoS，但在记账权的分配上有着不同的方法。例如，未来币（Nxt）和黑币（BlackCion）结合节点所拥有的权益，使用随机算法分配记账权。以太坊也在逐步采用PoS代替PoW。
3. 委托权益证明（DPoS）
比特币设计之初，希望所有挖矿的参与者使用CPU进行计算，算力与节点匹配，每一个节点都有足够的机会参与到区块链的决策当中。随着技术的发展，使用GPU、FPGA、ASIC等技术的矿机大量出现，算力集中于拥有大量矿机的参与者手中，而普通矿工参与的机会大大减小。
采用DPoS的区块链中，每一个节点都可以根据其拥有的股份权益投票选取代表，整个网络中参与竞选并获得选票最多的n个节点获得记账权，按照预先决定的顺序依次生产区块并因此获得一定的奖励。竞选成功的代表节点需要缴纳一定数量的保证金，而且必须保证在线的时间，如果某时刻应该产生区块的节点没有履行职责，他将会被取消代表资格，系统将继续投票选出一个新的代表来取代他。
DPoS中的所有节点都可以自主选择投票的对象，选举产生的代表按顺序记账，与PoW及PoS相比节省了计算资源，而且共识节点只有确定的有限个，效率也得到了提升。而且每个参与节点都拥有投票的权利，当网络中的节点足够多时，DPoS的安全性和去中心化也得到了保证。
4. 实用拜占庭容错算法（PBFT）
在PBFT算法中，所有节点都在相同的配置下运行，且有一个主节点，其他节点作为备份节点。主节点负责对客户端的请求进行排序，按顺序发送给备份节点。存在视图（View）的概念，在每个视图中，所有节点正常按照处理消息。但当备份节点检查到主节点出现异常，就会触发视图变换（View Change）机制更换下一编号的节点为主节点，进入新的视图。PBFT中客户端发出请求到收到答复的主要流程如图4.1所示[10] [11]，服务器之间交换信息3次，整个过程包含以下五个阶段：
图4.1 PBFT执行流程
目前以PBFT为代表的拜占庭容错算法被许多区块链项目所使用。在联盟链中，PBFT算法最早是被Hyper ledger Fabric项目采用。Hyperledger Fabric在0.6版本中采用了PBFT共识算法，授权和背书的功能集成到了共识节点之中，所有节点都是共识节点，这样的设计导致了节点的负担过于沉重，对TPS和扩展性有很大的影响。1.0之后的版本都对节点的功能进行了分离，节点分成了三个背书节点(Endorser)、排序节点(Orderer)和出块节点(Committer)，对节点的功能进行了分离，一定程度上提高了共识的效率。
Cosmos项目使用的Tendermint[12]算法结合了PBFT和PoS算法，通过代币抵押的方式选出部分共识节点进行BFT的共识，其减弱了异步假设并在PBFT的基础上融入了锁的概念，在部分同步的网络中共识节点能够通过两阶段通信达成共识。系统能够容忍1/3的故障节点，且不会产生分叉。在Tendermint的基础上，Hotstuff[13]将区块链的块链式结构和BFT的每一阶段融合，每阶段节点间对前一区块签名确认与新区块的构建同时进行，使算法在实现上更为简单，Hotstuff还使用了门限签名[14]降低算法的消息复杂度。
5. Paxos与Raft
共识算法是为了保障所存储信息的准确性与一致性而设计的一套机制。在传统的分布式系统中，最常使用的共识算法是基于Paxos的算法。在拜占庭将军问题[3]提出后，Lamport在1990年提出了Paxos算法用于解决特定条件下的系统一致性问题，Lamport于1998年重新整理并发表Paxos的论文[15]并于2001对Paxos进行了重新简述[16]。随后Paxos在一致性算法领域占据统治地位并被许多公司所采用，例如腾讯的Phxpaxos、阿里巴巴的X-Paxos、亚马逊的AWS的DynamoDB和谷歌MegaStore[17]等。这一类算法能够在节点数量有限且相对可信任的情况下，快速完成分布式系统的数据同步，同时能够容忍宕机错误（Crash Fault）。即在传统分布式系统不需要考虑参与节点恶意篡改数据等行为，只需要能够容忍部分节点发生宕机错误即可。但Paxos算法过于理论化，在理解和工程实现上都有着很大的难度。Ongaro等人在2013年发表论文提出Raft算法[18]，Raft与Paxos同样的效果并且更便于工程实现。
Raft中领导者占据绝对主导地位，必须保证服务器节点的绝对安全性，领导者一旦被恶意控制将造成巨大损失。而且交易量受到节点最大吞吐量的限制。目前许多联盟链在不考虑拜占庭容错的情况下，会使用Raft算法来提高共识效率。
6. 结合VRF的共识算法
在现有联盟链共识算法中，如果参与共识的节点数量增加，节点间的通信也会增加，系统的性能也会受到影响。如果从众多候选节点中选取部分节点组成共识组进行共识，减少共识节点的数量，则可以提高系统的性能。但这会降低安全性，而且候选节点中恶意节点的比例越高，选出来的共识组无法正常运行的概率也越高。为了实现从候选节点选出能够正常运行的共识组，并保证系统的高可用性，一方面需要设计合适的随机选举算法，保证选择的随机性，防止恶意节点对系统的攻击。另一方面需要提高候选节点中的诚实节点的比例，增加诚实节点被选进共识组的概率。
当前在公有链往往基于PoS类算法，抵押代币增加共识节点的准入门槛，通过经济学博弈增加恶意节点的作恶成本，然后再在部分通过筛选的节点中通过随机选举算法，从符合条件的候选节点中随机选举部分节点进行共识。
Dodis等人于1999年提出了可验证随机函数（Verifiable Random Functions，VRF）[19]。可验证随机函数是零知识证明的一种应用，即在公私钥体系中，持有私钥的人可以使用私钥和一条已知信息按照特定的规则生成一个随机数，在不泄露私钥的前提下，持有私钥的人能够向其他人证明随机数生成的正确性。VRF可以使用RSA或者椭圆曲线构建，Dodis等人在2002年又提出了基于Diffie-Hellman 困难性问题的可验证随机函数构造方法[20]，目前可验证随机函数在密钥传输领域和区块链领域都有了应用[21]。可验证随机函数的具体流程如下：
在公有链中，VRF已经在一些项目中得到应用，其中VRF多与PoS算法结合，所有想要参与共识的节点质押一定的代币成为候选节点，然后通过VRF从众多候选节点中随机选出部分共识节点。Zilliqa网络的新节点都必须先执行PoW，网络中的现有节点验证新节点的PoW并授权其加入网络。区块链项目Ontology设计的共识算法VBFT将VRF、PoS和BFT算法相结合，通过VRF在众多候选节点中随机选出共识节点并确定共识节点的排列顺序，可以降低恶意分叉对区块链系统的影响，保障了算法的公平性和随机性。图灵奖获得者Micali等人提出的Algorand[22]将PoS和VRF结合，节点可以采用代币质押的方式成为候选节点，然后通过非交互式的VRF算法选择部分节点组成共识委员会，然后由这部分节点执行类似PBFT共识算法，负责交易的快速验证，Algorand可以在节点为诚实节点的情况下保证系统正常运行。Kiayias等人提出的Ouroboros[23]在第二个版本Praos[24]引入了VRF代替伪随机数，进行分片中主节点的选择。以Algorand等算法使用的VRF算法为例，主要的流程如下：
公有链中设计使用的VRF中，节点被选为记账节点的概率往往和其持有的代币正相关。公有链的共识节点范围是无法预先确定的，所有满足代币持有条件的节点都可能成为共识节点，系统需要在数量和参与度都随机的节点中选择部分节点进行共识。而与公有链相比，联盟链参与共识的节点数量有限、节点已知，这种情况下联盟链节点之间可以通过已知的节点列表进行交互，这能有效防止公有链VRF设计时可能遇到的女巫攻击问题。
7. 结合分片技术的公式算法
分片技术是数据库中的一种技术，是将数据库中的数据切成多个部分，然后分别存储在多个服务器中。通过数据的分布式存储，提高服务器的搜索性能。区块链中，分片技术是将交易分配到多个由节点子集组成的共识组中进行确认，最后再将所有结果汇总确认的机制。分片技术在区块链中已经有一些应用，许多区块链设计了自己的分片方案。
Luu等人于2017年提出了Elastico协议，最先将分片技术应用于区块链中[25]。Elastico首先通过PoW算法竞争成为网络中的记账节点。然后按照预先确定的规则，这些节点被分配到不同的分片委员会中。每个分片委员会内部执行PBFT等传统拜占庭容错的共识算法，打包生成交易集合。在超过的节点对该交易集合进行了签名之后，交易集合被提交给共识委员会，共识委员会在验证签名后，最终将所有的交易集合打包成区块并记录在区块链上。
Elastico验证了分片技术在区块链中的可用性。在一定规模内，分片技术可以近乎线性地拓展吞吐量。但Elastico使用了PoW用于选举共识节点,这也导致随机数产生过程及PoW竞争共识节点的时间过长，使得交易延迟很高。而且每个分片内部采用的PBFT算法通讯复杂度较高。当单个分片中节点数量较多时，延迟也很高。
在Elastico的基础上，Kokoris-Kogias等人提出OmniLedger[26]，用加密抽签协议替代了PoW选择验证者分组，然后通过RandHound协议[27]将验证者归入不同分片。OmniLedger。OmniLedger在分片中仍然采用基于PBFT的共识算法作为分片中的共识算法[28]，并引入了Atomix协议处理跨分片的交易，共识过程中节点之间通信复杂度较高。当分片中节点数量增多、跨分片交易增多时，系统TPS会显著下降。
Wang等人在2019年提出了Monoxide[29]。在PoW区块链系统中引入了分片技术，提出了连弩挖矿算法（Chu ko-nu mining algorithm），解决了分片造成的算力分散分散问题，使得每个矿工可以同时在不同的分片进行分片，在不降低安全性的情况下提高了PoW的TPS。
8. 小结
本文对区块链中的共识算法进行了综述性介绍，其中对公有链中基础的共识PoW和联盟链中基础的公式算法PBFT进行了较为详细的分析，然后对目前新出现的较为先进的共识算法进行了介绍，希望对读者探索区块链领域有所帮助。
参考文献
[1]Antonopoulos A M. Mastering Bitcoin: Unlocking Digital Crypto-Currencies[J]. Oreilly Media Inc Usa, 2015.
[2]Karame G O, Androulaki E, Capkun S. Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin.[J]. 2012.
[3]Lamport L, Shostak R, Pease M. The Byzantine Generals Problem[J]. Acm Transactions on Programming Languages & Systems, 1982,4(3):382-401.
[4]Back A. Hashcash - A Denial of Service Counter-Measure: USENIX Technical Conference, 2002[C].
[5]Kraft D. Difficulty control for blockchain-based consensus systems[J]. Peer-to-Peer Networking and Applications, 2016,9(2):397-413.
[6]Andolfatto D. The False Analogy Between Gold and Bitcoin[J].
[7]Alfidi A. The Serious Disadvantages of Bitcoin[J].
[8]Miller A, Juels A, Shi E, et al. Permacoin: Repurposing Bitcoin Work for Data Preservation[J]. 2014:475-490.
[9]Stegaroiu C E. The Advantages And Disadvantages Of Bitcoin Payments In The New Economy[J]. Annals Economy, 2018,1.
[10]范捷, 易乐天, 舒继武. 拜占庭系统技术研究综述[J]. 软件学报, 2013(06):1346-1360.
[11]Castro M, Liskov B. Practical Byzantine fault tolerance: Symposium on Operating Systems Design and Implementation, 1999[C].
[12]Buchman E. Tendermint: Byzantine fault tolerance in the age of blockchains[D]., 2016.
[13]Yin M, Malkhi D, Reiter M K, et al. Hotstuff: Bft consensus with linearity and responsiveness, 2019[C].
[14]Desmedt Y, Frankel Y. Shared generation of authenticators and signatures, 1991[C]. Springer.
[15]Lamport L. The part-time parliament[J]. Acm Transactions on Computer Systems, 1998,16(2):133-169.
[16]Lamport L. Paxos made simple[J]. ACM Sigact News, 2001,32(4):18-25.
[17]Chandra T D, Griesemer R, Redstone J. Paxos made live: An engineering perspective: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, 2007[C].
[18]Ongaro D, Ousterhout J K. In search of an understandable consensus algorithm., 2014[C].
[19]Li W, Andreina S, Bohli J, et al. Securing proof-of-stake blockchain protocols, Oslo, Norway, 2017[C]. Springer Verlag, 2017.
[20]Dodis Y. Efficient Construction of (Distributed) Verifiable Random Functions: International Workshop on Theory & Practice in Public Key Cryptography: Public Key Cryptography, 2002[C].
[21]Melara M S, Blankstein A, Bonneau J, et al. Coniks: Bringing key transparency to end users, Washington, DC, United states, 2015[C]. USENIX Association, 2015.
[22]Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling Byzantine Agreements for Cryptocurrencies, Shanghai, China, 2017[C]. Association for Computing Machinery, Inc, 2018.
[23]Kiayias A, Russell A, David B, et al. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol, 2017[C].
[24]David B, Gaži P, Kiayias A, et al. Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain, 2018[C].
[25]Luu L, Narayanan V, Zheng C, et al. A secure sharding protocol for open blockchains, Vienna, Austria, 2016[C]. Association for Computing Machinery, 2016.
[26]Kokoris-Kogias E, Jovanovic P, Gasser L, et al. OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding, Los Alamitos, CA, USA, 2018[C]. IEEE Computer Society, 2018//.
[27]Syta E, Jovanovic P, Kogias E K, et al. Scalable Bias-Resistant Distributed Randomness, Los Alamitos, CA, USA, 2017[C]. IEEE Computer Society, 2017//.
[28]Kokoris-Kogias E, Jovanovic P, Gailly N, et al. Enhancing bitcoin security and performance with strong consistency via collective signing, Austin, TX, United states, 2016[C]. USENIX Association, 2016.
[29]Wang J, Wang H. Monoxide: Scale out blockchains with asynchronous consensus zones: 16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19), 2019[C].
本文分享自华为云社区《万字长文解读区块链七类共识算法》，原文作者：APTX-486977 。
