论文部分内容阅读
摘 要： 区块链是一种去掉中心管理结构的通过分布式的节点运行的公共数据库。区块链是从2008年提出，经过多年的发展，近些年来收到社会的特别关注。区块链的项目较多，例如以太坊、Fabric、莱特币和比特币等等。其中热度最高的就是比特币。比特币是区块链最本质和最原始的应用。区块链的共识算法，可以保证区块链中的节点参与共识过程的有效性。本文梳理了各种区块链共识算法（如POW、POS、DPOS和PBFT）的思想，分析各类算法的优点和缺点[1]。
关键词： 区块链;分布式系统;共识算法;拜占庭协议;PoW;PoS
中图分类号： G354.4 文献标识码： A DOI：10.3969/j.issn.1003-6970.2019.04.048
本文著录格式：陈玎乐. 区块链共识算法的比较研究[J]. 软件，2019，40（4）：219221
【Abstract】： Block chain is a public database running through distributed nodes without central management structure， which was put forward in 2008. With years of development， it has received special attention from society in recent years. There are many items of block chain， including Ethernet square， Fabric， Wright coin and Bitcoin， etc. And Bitcoin is the hottest among them， which is the most essential and original application of block chain. Consensus algorithm of block chain can ensure validity of block chain nodes in participating consensus process. The paper combs ideas of various block chain consensus algorithms （such as POW， POS， DPOS and PBFT）， and analyses advantages and disadvantages of these algorithms[1].
【Key words】： Block chain; Distributed system; Consensus algorithms; Byzantine protocol; PoW; PoS
0 引言
区块链（Blockchain）技术是一种去掉中心管理结构的，通过分布式的节点运行的公共数据库。其具有自治性、防篡改性、去中心化和完备可追溯等特点。分布式网络是区块链建立的基础。为了维护系统中的每一个节点，将指定时间内的数据打包整理成一个区块，每一个区块保存前一个区块的哈希信息，保证区块形成连贯的链。所以区块链的本质是数据存储技术。经过多年的区块链的发展，比特币、Fabric、莱特币、BigchainDB和以太坊等项目应运而生，并且受到了广泛的关注。其中最成功的项目是比特币[2]。比特币是近些年最成功的一个分布式的点对点加密货币。其本质就是一种用分布式的数字账本记录商务交易的金融平台。比特币实现了无需第三方担保的电子现金系统，但数字货币面临着两大问题：拜占庭问题[1]和双花[2]（参与运算的节点如何建立统一的账目，如何保证同一笔资金不被用于多个金融交易）。问题的本质，就是在没有第三方中心担保的电子金融系统的环境中，如何保证每个节点对同一数据的认可。为了实现高效、公平、稳定的分布式系统，区快链融合了共识算法，密码学，Merkle trees等多个技术。所以区快连是多个成熟技术的完美融合。这个成熟技术中，共识算法是解决区块链中一致性问题。经过多年的科学研究和商业的发展，共识算法已经发展和演变出多个体系。如何选择合适的算法使区块链的系统达到最优的效果，是设计区块链中重要的环节[3-6]。
1 主流区块链共识算法
共识算法也称为分布式一致算法。这些算法包含Paxos 算法、Zab算法、Kafka算法等等[3]。该算法针对分布式数据库的操作，并且不考虑拜占庭容错问题。综合考虑算法的安全性和实际应用中需求，区块链的公有链 和许可链的共识算法也不一样。在公有链中，例如POS（Proof of Stake）、POW（Proof of Work）[4]等一系列的拜占庭容错类的共识算法被应用起来。
根据打包节点方式、一致性的程度和容错能力等特点，区块链共识算法可以分为多了不同维度的类别。根据打包节点的方式，区块链共识算法分为联盟类、选举类、证明类、随机类等。其中常见的区块链共识算法是选举类。常见的证明类算法包括POW（Proof of Work）和POS（Proof of Stake）。这两种算法不同的是POW证明的点是矿工的算力，而POS 证明的点是参与者占有系统虚拟资源的权益;随机类算法中常見的是通过依赖随机数字选取打包节点的Algorand[6]和PoET3;联盟类算法中的一种以 DPOS[7]为代表的“民主集中式”轮流获得打包权;还有很多混合类的共识算法，类如很多系统采用 PoW+PoS 的共识机制[7]。
2 常用共识算法
2.1 工作量证明算法（Proof of Work） 比特币早期的应用的过程中，其核心的思想是通过各个节点的算力竞争选择打包节点。比特币系统通过分布式系统的各个节点的计算机算力通过互相竞争解决复杂并且验证容易的SHA256数学难题。最快解决问题的节点将获得下一区块的记账权利以及系统生成的比特币奖励。POW在比特币的应用中具有重要的意义。工作量证明机制（Proof of Work）简称POW，简单解释就是做的多获得就多。POW是一种应对抵御服务攻击或者其他滥用的经济对策，其要求发起者进行一定量的运算，该理论是1993年Cymhia Dwork和Moni Naor提出。比特币系统中的每一个节点都时刻进行高强度的复杂运算，获得一个随机数，然后根据这个随机数获取生成区块的机会。因此该系统也需要一定的奖励机制，即代币，生成区块获得定制的代币奖励。Proof of Work高度依赖分布式系统中的各个分点的计算机，计算机的性能越高，POW的性能就越高。与其他共识算法相比，Proof of Work构成的成本较高，但区块生成的效率较低。其性能如表1所示。
2.2 股权证明（Proof of Stake）
为了解决POW算法巨大浪费计算能力的问题，POS（Proof of Stake）共识算法被提出。权益证明机制（POS）是一种 依赖于验证者在网络中的经济利益的公共区块链的共识算法。在基于工作量证明（POW）的区块链中，该算法鼓励解决密码难题的参与的区块，以验证交易的成功并创建新的区块-—简称采矿。在基于权益证明机制（POS）的公共区块链中，验证者循环在下一个区块提出投票和投票，每一位验证者投票的权重取决于该验证者存款的大小——股权。简单来说，股份越多，挖矿越容易;拥有的股份越少，越难产生区块。所以权益证明机制是对工作量证明的升级，根据各个分布式节点拥有的代币动态求出随机数的难度，拥有的代币越多则容易求出[8]。
虽然权益证明机制（POS）算法能在一定程度上降低工作量证明（POW）算法带来的巨大浪费，避免了计算资源的竞争，但其仍然存在一些问题。例如某一用户长时间持有区块链资产，或者持有大比重的区块链资产。如果首次币发行（Initial Coin Offering，简称ICO）最初就持有一定量区块链资产，这样就造成了分配不均，同时对网络中新加入的分布式节点也不公平。但是POS 也没有完全避免计算资源的竞争怪圈，该算法依然浪费一定的计算资源。其优缺点总结如下表所示：
2.3 股权授权证明算法（Delegated Proof of stake）
股份授权证明机制（DPOS，Delegated Proof of stake）又称为“股东代表机制”，将拥有一定数量的代币的每个节点看作为股东，各个节点根据持有的代币的数量做出定量的投票，最后选出定量的节点。这些节点作为代表，轮流生成区块，同时其代表们也会收到等同于一个平均水平的 区块所包含交易费的10%作为报酬[8]。如果一些代表在生成区块的过程中发现了问题，股东将会重新投票，并选取新的代表进行替换[9]。
如果将POW共识算法看作“算力为王”的记账方式，POS共识算法看作“权益为王”的记账方式，那么DPOS就是“民主集中制”的记账方式。该算法不仅有效的解决了POW资源浪费的问题和矿池对去中心化[5]构成的威胁的问题，还能够弥补POS中有记账权益的参与者但没有记账实权的缺点。所以，该算法设计者认为DPOS是当时最高效、最灵活、最快速和去中心化的共识算法。其明显的优缺点如下：
2.4 实用拜占庭容错算法（Practical Byzantine Fault Tolerance）
实用拜占庭容错算法（PBFT，Practical Byzantine Fault Tolerance）是由Liskov和Castro提出一种基于状态机复制的一致性算法[10]。该算法被广泛应用于分布式系统中。在Peer-to-peer networking中，各个分布式节点通过节点间传递的信息达成共识，最终生成区块。但是由于系统、网络等等外在因素影响，使节点间传递的信息损毁或者丢失，导致在进行信息验证时产生错误信息。为了解决该问题，一种信息容错率比较高的解决方案的PBFT 算法应运而生[9]。综合考虑了拜占庭将军问题，该算法依据问题节点的数量验证本次共识是否可信。假设对等网络中节点的总数量为M，问题节点的数量为m，则在本次共识过程中，依据条件：M>=3m是否成立，判断本次共识过程是否有效。PBFT算法优缺点如下表所示：
3 共识算法比较
在第2节介绍完共识算法后，以下列表对其进行比较。从表5中可以发现，POW算法用时最长，但资源消耗最高，但其在研究和商业领域仍然有重要的意义。DPOS算法虽然具有髙效和节能的优点，但是在应对拜占庭容错节点的问题没有POW算法效果好。以下是对常用的四种共识算法机制进行比较[10]。
4 结语
该文对现有的区块链的共识算法进行了总结，并且分别从公有链和许可链具体描述了不同的共识算法。对于公有链，我们介绍了POW、POS和DPOS三种共识算法，并分析了算法的优缺点。针对许可链，我们注重描述了BPFT算法的思想和优缺点。最后针对上述几种算法，分别从资源消耗、中心化程度、吞吐量等进行分析对比。我们充分了解现有共识算法。
参考文献
[1] 张偲. 区块链技术原理?应用及建议[J]. 软件， 2016， 37（11）： 51-54.
[2] 党京， 孙弋. 基于区块链的电子投票系统关键技术的实现[J]. 软件， 2018， 39（11）： 140-144.
[3] 焦英楠， 陈英华. 基于区块链技术的物联网安全研究[J]. 软件， 2018， 39（02）： 88-92.
[4] 潘吉飞， 黄德才. 区块链技术对人工智能的影响[J]. 计算机科学， 2018， 45（S2）： 53-57+70.
[5] Gencer A E， Basu S， Eyal I， et al. Decentralization in Bitcoin and Ethereum Networks[C]//International Conference on Financial Cryptography and Data Security， 2018.
[6] Y. Gilad， R. Hemo， S. Micali， ， et al. Algorand： Scaling byzantine agreements for cryptocurrencies//[C] SOSP. Shanghai， China： ACM， 2017.
[7] Larimer D. Delegated proof-of-stake （dpos）. Bitshare Whitepaper. 2014.
[8] Thompson K. Reflections on trusting trust[C]// Communications of the ACM. 2012： 761-763.
[9] Eyal I， Sirer E G. Majority Is Not Enough： Bitcoin Mining Is Vulnerable[M]//Financial Cryptography and Data Security. Springer Berlin Heidelberg， 2014.
[10] 李靜彧， 李兆森. 基于区块链存证的电子数据真实性探讨[J]. 软件， 2018， 39（06）： 109-112.
关键词： 区块链;分布式系统;共识算法;拜占庭协议;PoW;PoS
中图分类号： G354.4 文献标识码： A DOI：10.3969/j.issn.1003-6970.2019.04.048
本文著录格式：陈玎乐. 区块链共识算法的比较研究[J]. 软件，2019，40（4）：219221
【Abstract】： Block chain is a public database running through distributed nodes without central management structure， which was put forward in 2008. With years of development， it has received special attention from society in recent years. There are many items of block chain， including Ethernet square， Fabric， Wright coin and Bitcoin， etc. And Bitcoin is the hottest among them， which is the most essential and original application of block chain. Consensus algorithm of block chain can ensure validity of block chain nodes in participating consensus process. The paper combs ideas of various block chain consensus algorithms （such as POW， POS， DPOS and PBFT）， and analyses advantages and disadvantages of these algorithms[1].
【Key words】： Block chain; Distributed system; Consensus algorithms; Byzantine protocol; PoW; PoS
0 引言
区块链（Blockchain）技术是一种去掉中心管理结构的，通过分布式的节点运行的公共数据库。其具有自治性、防篡改性、去中心化和完备可追溯等特点。分布式网络是区块链建立的基础。为了维护系统中的每一个节点，将指定时间内的数据打包整理成一个区块，每一个区块保存前一个区块的哈希信息，保证区块形成连贯的链。所以区块链的本质是数据存储技术。经过多年的区块链的发展，比特币、Fabric、莱特币、BigchainDB和以太坊等项目应运而生，并且受到了广泛的关注。其中最成功的项目是比特币[2]。比特币是近些年最成功的一个分布式的点对点加密货币。其本质就是一种用分布式的数字账本记录商务交易的金融平台。比特币实现了无需第三方担保的电子现金系统，但数字货币面临着两大问题：拜占庭问题[1]和双花[2]（参与运算的节点如何建立统一的账目，如何保证同一笔资金不被用于多个金融交易）。问题的本质，就是在没有第三方中心担保的电子金融系统的环境中，如何保证每个节点对同一数据的认可。为了实现高效、公平、稳定的分布式系统，区快链融合了共识算法，密码学，Merkle trees等多个技术。所以区快连是多个成熟技术的完美融合。这个成熟技术中，共识算法是解决区块链中一致性问题。经过多年的科学研究和商业的发展，共识算法已经发展和演变出多个体系。如何选择合适的算法使区块链的系统达到最优的效果，是设计区块链中重要的环节[3-6]。
1 主流区块链共识算法
共识算法也称为分布式一致算法。这些算法包含Paxos 算法、Zab算法、Kafka算法等等[3]。该算法针对分布式数据库的操作，并且不考虑拜占庭容错问题。综合考虑算法的安全性和实际应用中需求，区块链的公有链 和许可链的共识算法也不一样。在公有链中，例如POS（Proof of Stake）、POW（Proof of Work）[4]等一系列的拜占庭容错类的共识算法被应用起来。
根据打包节点方式、一致性的程度和容错能力等特点，区块链共识算法可以分为多了不同维度的类别。根据打包节点的方式，区块链共识算法分为联盟类、选举类、证明类、随机类等。其中常见的区块链共识算法是选举类。常见的证明类算法包括POW（Proof of Work）和POS（Proof of Stake）。这两种算法不同的是POW证明的点是矿工的算力，而POS 证明的点是参与者占有系统虚拟资源的权益;随机类算法中常見的是通过依赖随机数字选取打包节点的Algorand[6]和PoET3;联盟类算法中的一种以 DPOS[7]为代表的“民主集中式”轮流获得打包权;还有很多混合类的共识算法，类如很多系统采用 PoW+PoS 的共识机制[7]。
2 常用共识算法
2.1 工作量证明算法（Proof of Work） 比特币早期的应用的过程中，其核心的思想是通过各个节点的算力竞争选择打包节点。比特币系统通过分布式系统的各个节点的计算机算力通过互相竞争解决复杂并且验证容易的SHA256数学难题。最快解决问题的节点将获得下一区块的记账权利以及系统生成的比特币奖励。POW在比特币的应用中具有重要的意义。工作量证明机制（Proof of Work）简称POW，简单解释就是做的多获得就多。POW是一种应对抵御服务攻击或者其他滥用的经济对策，其要求发起者进行一定量的运算，该理论是1993年Cymhia Dwork和Moni Naor提出。比特币系统中的每一个节点都时刻进行高强度的复杂运算，获得一个随机数，然后根据这个随机数获取生成区块的机会。因此该系统也需要一定的奖励机制，即代币，生成区块获得定制的代币奖励。Proof of Work高度依赖分布式系统中的各个分点的计算机，计算机的性能越高，POW的性能就越高。与其他共识算法相比，Proof of Work构成的成本较高，但区块生成的效率较低。其性能如表1所示。
2.2 股权证明（Proof of Stake）
为了解决POW算法巨大浪费计算能力的问题，POS（Proof of Stake）共识算法被提出。权益证明机制（POS）是一种 依赖于验证者在网络中的经济利益的公共区块链的共识算法。在基于工作量证明（POW）的区块链中，该算法鼓励解决密码难题的参与的区块，以验证交易的成功并创建新的区块-—简称采矿。在基于权益证明机制（POS）的公共区块链中，验证者循环在下一个区块提出投票和投票，每一位验证者投票的权重取决于该验证者存款的大小——股权。简单来说，股份越多，挖矿越容易;拥有的股份越少，越难产生区块。所以权益证明机制是对工作量证明的升级，根据各个分布式节点拥有的代币动态求出随机数的难度，拥有的代币越多则容易求出[8]。
虽然权益证明机制（POS）算法能在一定程度上降低工作量证明（POW）算法带来的巨大浪费，避免了计算资源的竞争，但其仍然存在一些问题。例如某一用户长时间持有区块链资产，或者持有大比重的区块链资产。如果首次币发行（Initial Coin Offering，简称ICO）最初就持有一定量区块链资产，这样就造成了分配不均，同时对网络中新加入的分布式节点也不公平。但是POS 也没有完全避免计算资源的竞争怪圈，该算法依然浪费一定的计算资源。其优缺点总结如下表所示：
2.3 股权授权证明算法（Delegated Proof of stake）
股份授权证明机制（DPOS，Delegated Proof of stake）又称为“股东代表机制”，将拥有一定数量的代币的每个节点看作为股东，各个节点根据持有的代币的数量做出定量的投票，最后选出定量的节点。这些节点作为代表，轮流生成区块，同时其代表们也会收到等同于一个平均水平的 区块所包含交易费的10%作为报酬[8]。如果一些代表在生成区块的过程中发现了问题，股东将会重新投票，并选取新的代表进行替换[9]。
如果将POW共识算法看作“算力为王”的记账方式，POS共识算法看作“权益为王”的记账方式，那么DPOS就是“民主集中制”的记账方式。该算法不仅有效的解决了POW资源浪费的问题和矿池对去中心化[5]构成的威胁的问题，还能够弥补POS中有记账权益的参与者但没有记账实权的缺点。所以，该算法设计者认为DPOS是当时最高效、最灵活、最快速和去中心化的共识算法。其明显的优缺点如下：
2.4 实用拜占庭容错算法（Practical Byzantine Fault Tolerance）
实用拜占庭容错算法（PBFT，Practical Byzantine Fault Tolerance）是由Liskov和Castro提出一种基于状态机复制的一致性算法[10]。该算法被广泛应用于分布式系统中。在Peer-to-peer networking中，各个分布式节点通过节点间传递的信息达成共识，最终生成区块。但是由于系统、网络等等外在因素影响，使节点间传递的信息损毁或者丢失，导致在进行信息验证时产生错误信息。为了解决该问题，一种信息容错率比较高的解决方案的PBFT 算法应运而生[9]。综合考虑了拜占庭将军问题，该算法依据问题节点的数量验证本次共识是否可信。假设对等网络中节点的总数量为M，问题节点的数量为m，则在本次共识过程中，依据条件：M>=3m是否成立，判断本次共识过程是否有效。PBFT算法优缺点如下表所示：
3 共识算法比较
在第2节介绍完共识算法后，以下列表对其进行比较。从表5中可以发现，POW算法用时最长，但资源消耗最高，但其在研究和商业领域仍然有重要的意义。DPOS算法虽然具有髙效和节能的优点，但是在应对拜占庭容错节点的问题没有POW算法效果好。以下是对常用的四种共识算法机制进行比较[10]。
4 结语
该文对现有的区块链的共识算法进行了总结，并且分别从公有链和许可链具体描述了不同的共识算法。对于公有链，我们介绍了POW、POS和DPOS三种共识算法，并分析了算法的优缺点。针对许可链，我们注重描述了BPFT算法的思想和优缺点。最后针对上述几种算法，分别从资源消耗、中心化程度、吞吐量等进行分析对比。我们充分了解现有共识算法。
参考文献
[1] 张偲. 区块链技术原理?应用及建议[J]. 软件， 2016， 37（11）： 51-54.
[2] 党京， 孙弋. 基于区块链的电子投票系统关键技术的实现[J]. 软件， 2018， 39（11）： 140-144.
[3] 焦英楠， 陈英华. 基于区块链技术的物联网安全研究[J]. 软件， 2018， 39（02）： 88-92.
[4] 潘吉飞， 黄德才. 区块链技术对人工智能的影响[J]. 计算机科学， 2018， 45（S2）： 53-57+70.
[5] Gencer A E， Basu S， Eyal I， et al. Decentralization in Bitcoin and Ethereum Networks[C]//International Conference on Financial Cryptography and Data Security， 2018.
[6] Y. Gilad， R. Hemo， S. Micali， ， et al. Algorand： Scaling byzantine agreements for cryptocurrencies//[C] SOSP. Shanghai， China： ACM， 2017.
[7] Larimer D. Delegated proof-of-stake （dpos）. Bitshare Whitepaper. 2014.
[8] Thompson K. Reflections on trusting trust[C]// Communications of the ACM. 2012： 761-763.
[9] Eyal I， Sirer E G. Majority Is Not Enough： Bitcoin Mining Is Vulnerable[M]//Financial Cryptography and Data Security. Springer Berlin Heidelberg， 2014.
[10] 李靜彧， 李兆森. 基于区块链存证的电子数据真实性探讨[J]. 软件， 2018， 39（06）： 109-112.