摘要：本文将对区块链中常见的七类共识算法进行介绍，心愿对读者摸索区块链有所帮忙。
区块链技术起源于比特币，最后是比特币等数字货币的一种底层技术，区块链交融了密码学、组网技术、共识算法、智能合约等多种技术。随着区块链技术的逐步成熟，其逐步失去科研机构、政府、金融机构和科技企业的关注。区块链具备匿名、防篡改、可追溯和去中心化等特点。
传统的交易须要一个可信赖的第三方作为交易中介，与之相比，区块链技术可能实现交易的去中心化，同时还能保障全网数据的一致性，使得点对点交易成为可能。这须要对交易确认规定进行设计，这一规定就是本节将要介绍的共识算法。共识算法作为区块链技术的外围，对区块链平安、效率等方面有着决定性的作用。
在区块链的利用过程中，共识算法须要解决两个问题：双花问题 [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。
点击关注，第一工夫理解华为云陈腐技术~