区块链共识算法研究综述

doi:10.3969/j.issn.1671-1122.2019.07.002

摘要/Abstract

摘要：

共识算法是区块链技术发展的关键,影响着区块链的交易处理能力、可扩展性和安全性,同时也是近年来分布式系统研究的热点。文章对区块链共识算法的最新进展和未来研究方向进行了分析和总结。首先概述了区块链框架,梳理了30年来分布式系统与一致性算法的重要结论和发展脉络,详细总结了现在主流的区块链共识算法并分析比较其性能。在此基础上,文章提出了一种共识算法的通用模型和分类方法,并对新的具有代表性进展的区块链共识算法进行分析和总结,最后对共识算法的研究方向进行展望,以期为未来的共识算法研究和创新提供参考。

关键词: 区块链, 共识算法, 分布式系统, 拜占庭容错, 联盟链

Abstract:

Consensus algorithm is the key to the development of blockchain technology and hasa significant impact on the capability, scalability and security of blockchain. It is also a hotspot of distributed system research in recent years. This paper reviewed the state-of-the-art research progress of the blockchain consensus algorithm, outlined the blockchain framework and clarified the important conclusions of the distributed system and consensus algorithmsinrecent 30 years. We provided a detailed summary and comparison of mainstreamblockchain consensus algorithms, then proposed a general model and classification method of consensus algorithms. In the end, we systematically reviewed new blockchain consensus algorithms and provided an outlook of the research direction in thefuture.

Key words: blockchain, consensus algorithm, distributed system, byzantine fault tolerance, consortium blockchain

中图分类号:

TP309

郑敏, 王虹, 刘洪, 谭冲. 区块链共识算法研究综述[J]. 信息网络安全, 2019, 19(7): 8-24.

Min ZHENG, Hong WANG, Hong LIU, Chong TAN. Survey on Consensus Algorithms of Blockchain[J]. Netinfo Security, 2019, 19(7): 8-24.

图/表 12

图1

图2

图3

图4

表1

图5

表2

表3

表4

图6

表5

表6

参考文献 78

[1]	The Sate Council.the 13th Five-Year Plan for National Informa- tionization[EB/OL]. 2016-12-27.
	国务院.“十三五”国家信息化规划[EB/OL]. .
[2]	NAKAMOTO S.Bitcoin: A Peer-to-Peer Electronic Cash System[EB/OL]. , 2019-1-7.
[3]	YUAN Yong, WANG Fei Yue.Blockchain: the State of the Art and Future Trends[J]. Acta Automatica Sinica, 2016, 42(4): 481-494.
	袁勇,王飞跃.区块链技术发展现状与展望[J].软件学报,2016,42(4):481-494.
[4]	EVANS D S. Economic Aspects of Bitcoin and Other Decentralized Public-Ledger Currency Platforms[EB/OL]. , 2014-1-15.
[5]	VUKOLIĆ M.The Quest for Scalable Blockchain Fabric: Proof-of-Work Vs. BFT Replication[C]// IFIP. International Workshop on Open Problems in Network Security, October 29, 2015, Zurich, Switzerland. Cham: Springer, 2015: 112-125.
[6]	VISA.Annual Report 2017 [EB/OL]. , 2017-12-26.
[7]	LAMPORT L.The Part-Time Parliament[J]. ACM Transactions on Computer Systems, 1998, 16(5): 144-169.
[8]	LAMPORT L.Paxos Made Simple[J]. ACM SIGACT News, 2001, 32(4): 18-25.
[9]	SUNNY K, SCOTT N. PPcoin: Peer-to-Peer Crypto-Currency with Proof-of-Stake[EB/OL]. ,2012-8-19.
[10]	LARIMER D. Delegated Proof of Stake[EB/OL]. , 2018-8-29.
[11]	DONET J A D, PÉREZ-Sola C, HERRERA J J. The Bitcoin P2P Network[C]//Springer. International Conference on Financial Cryptography and Data Security. March 7, 2014, Christ Church, Barbados. Berlin: Springer, 2014: 87-102.
[12]	DEMERS A, GREENE D, HOUSER C, et al.Epidemic Algorithms for Replicated Database Maintenance[J]. ACM SIGOPS Operating Systems Review, 1988, 22(1): 8-32.
[13]	MA Chungguang, AN Jing, BI Wei.et al.Smart Contract in Blockchain[J]. Netinfo Security, 2018, 18(11): 8-17.
	马春光,安婧,毕伟,等.区块链中的智能合约[J].信息网络安全,2018,18(11):8-17.
[14]	TSCHORSCH F, SCHEUERMANN B.Bitcoin and Beyond: A Technical Survey on Decentralized Digital Currencies[J]. IEEE Communications Surveys & Tutorials, 2016, 18(3): 2084-2123.
[15]	LAMPORT L, SHOSTAK R, PEASE M.The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.
[16]	FAN Jie, YI Le Tian, SHU Ji Wu.Research on the Technologies of Byzantine System[J]. Journal of Software, 2013, 24(6): 1346-1360.
	范捷,易乐天,舒继武.拜占庭系统技术研究综述[J].软件学报,2013,24(6):1346-1360.
[17]	FISCHER M J, LYNCH N A, PATERSON M S.Impossibility of Distributed Consensus with One Faulty Process[J]. Journal of the ACM, 1985, 32(2): 374-382.
[18]	GILBERT S, LYNCH N.Brewer’s Conjecture and the Feasibility of Consistent Available Partition-Tolerant Web Services[J]. ACM SIGACT News, 2002, 33(2): 51-59.
[19]	LAMPORt L.Proving the Correctness of Multiprocess Programs[J]. IEEE Transactions on Software Engineering, 1977, 3(2): 125-143.
[20]	OKI B M, LISKOV B H.Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems[C]// ACM. the Seventh Annual ACM Symposium on Principles of distributed computing. August 15-17, 1988, Toronto, Ontario, Canada. NewYork: ACM, 1988: 8-17.
[21]	LAMPORT L. My Writings [EB/OL]. , 2019-3-11
[22]	CHANDRA T D, GRIESEMER R, REDSTONE J.Paxos made live: An engineering perspective[C]// ACM. the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, August 12-15, 2007, Portland, Oregon, USA. NewYork: ACM, 2007: 398-407.
[23]	LAMPORT L, MASSA M.Cheap paxos[C]//IEEE. International Conference on Dependable Systems and Networks, June 28-July 1, 2004, Florence, Italy. New York: IEEE, 2004: 307-314.
[24]	LAMPSON B W.How to Build a Highly Available System Using Consensus[C]//Springer. International Workshop on Distributed Algorithms, October 9-11, 1996, Bologna, Italy. Berlin, Heidelberg: Springer, 1996: 1-17.
[25]	ONGARO D, OUSTERHOUT J K.In Search of an Understand-able Consensus Algorithm[C]//USENIX. USENIX Annual Technical Conference, June 19-20, 2014, Philadelphia, PA, USA. Berkeley: USENIX Association, 2014: 305-319.
[26]	CASTRO M, LISKOV B.Practical Byzantine Fault Tolerance[C]//USENIX. Proceedings of the Third Symposium on Operating Systems Design and Implementation, February 22-25, 1999, New Orleans, Louisiana, USA. Berkeley: USENIX Association, 1999: 173-186.
[27]	CASTROM, LISKOV B.Practical Byzantine Fault Tolerance and Proactive Recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002, 20(4): 398-461.
[28]	GARAY J A, MOSES Y.Fully Polynomial Byzantine Agreement for Processors in Rounds[J]. SIAM Journal on Computing, 1998, 27(1): 247-290.
[29]	MALKHI D, REITER M.Unreliable Intrusion Detection in Distributed Computations[C]//IEEE. Proceedings 10th Computer Security Foundations Workshop, June 10-12, 1997, Rockport, MA, USA. New York: IEEE, 1997: 116-124.
[30]	SCHNEIDER F B.Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial[J]. ACM Computing Surveys (CSUR), 1990, 22(4): 299-319.
[31]	Abd-El-Malek M, Ganger G R, Goodson G R, et al. Fault-scalable Byzantine Fault-tolerant Services[J]. ACM SIGOPS Operating Systems Review, 2005, 39(5): 59-74.
[32]	COWLING J, MYERS D, LISKOV B, et al.HQ replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance[C]//USENIX. Proceedings of the 7th Symposium on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006: 177-190.
[33]	KOTLA R, ALVISI L, DAHLIN M, et al.Zyzava: Speculative Byzantine Fault Tolerance[J]. SIGOPS Oper. Syst. Rev, 2007, 41(6): 45-58.
[34]	SHOKER A, BAHSOUN J P, YABANDEH M.Improving Independence of Failures in BFT[C]//IEEE. 2013 IEEE 12th International Symposium on Network Computing and Applications. August 22-24, 2013, Cambridge, MA, USA. New York: IEEE, 2013: 227-234.
[35]	AUBLIN P L, MOKHTAR S B, QUÉMA V. Rbft: Redundant byzantine fault tolerance[C]//IEEE. 2013 IEEE 33rd International Conference on Distributed Computing Systems, July 8-11, 2013, Philadelphia, PA, USA. New York: IEEE, 2013: 297-306.
[36]	COPELAND C, ZHONG H. Tangaroa: A Byzantine Fault Tolerant Raft[EB/OL]. .
[37]	MILLER A, XIA Y, CROMAN K, et al.The Honey Badger of BFT Protocols[C]//ACM. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,October 24-28, 2016, Vienna, Austria. New York: ACM, 2016: 31-42.
[38]	BACK A. Hashcash-a Denial of Service Counter-Measure[EB/OL]. , 2002-8-1.
[39]	ANDROULAKI E, BARGER A, BORTNIKOV V, et al. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains[EB/OL]., 2018-4-17.
[40]	COURTOIS N T, EMIRDAG P, NAGY D A.Could Bitcoin Transactions be 100x Faster?[C]//IEEE. 2014 11th International Conference on Security and Cryptography (SECRYPT). August 28-30, 2014, Vienna, Austria. New York: IEEE, 2014: 1-6.
[41]	Rosenfeld M.Analysis of Hashrate-Based Double Spending[J]. arXiv preprint arXiv: 1402. 2009, 2014.
[42]	O’DWYER K J, MALONE D. Bitcoin Mining and Its Energy Footprint[C]//IET. 25th IET Irish Signals & Systems Conference 2014 and 2014 China-Ireland International Conference on Information and Communications Technologies (ISSC 2014/CIICT 2014), June 26-27, 2013, Limerick, Ireland. London: IET, 2014: 280-285.
[43]	EYAL I, GENCER A E, SIRER E G, et al.Bitcoin-Ng: A Scalable Blockchain Protocol[C]//USENIX. Proceedings of the 13th USENIX Conference on Networked Systems Design and Implementation, March 16-18, 2016, Santa Clara, CA. Berkeley: USENIX Association, 2016: 45-59.
[44]	BACK A, CORALLO M, DASHJR L, et al. Enabling Blockchain Innovations with Pegged Sidechains [EB/OL]. , 2014-10-22.
[45]	Empowering Light Nodes in Blockchains with Block Summari-zation [C]//IEEE. 2018 9th IFIP International Conference on New Technologies, Mobility and Security (NTMS).February 26-28, 2018, Paris, France. New York: IEEE. 2018: 1-5.
[46]	WANG Xing, WENG Jian, ZHANG Yue, et al. Blaockchain System for Creating Digital Assets Based on Reputation Value[J]. Netinfo Security, 2018, 18(5): 59-65.
	王醒,翁健,张悦,等.基于信誉值创建数字资产的区块链系统[J].信息网络安全,2018,18(5):59-65.
[47]	CROMAN K, DECKER C, EYAL I, et al.On Scaling Decentralized Blockchains[C]//International Conference on Financial Cryptography and Data Security, February 26, 2016, Christ Church, Barbados Berlin: Springer, 2016: 106-125.
[48]	LUU L, NARAYANAN V, ZHENG C, et al.A Secure Sharding Protocol for Open Blockchains[C]//ACM. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, New York: ACM, 2016: 17-30.
[49]	BALL M, ROSEN A, SABIN M, et al. Proofs of Useful Work[EB/OL]. , 2017-5-15.
[50]	KING S. Primecoin: Cryptocurrency with Prime Number Proof-of-Work [EB/OL]. .
[51]	JUELS A, BURTON S. KALISKI J.Pors: Proofs of Retrievability for Large Files[C]//ACM. Proceedings of the 14th ACM conference on Computer and communications security, July 7 -12, Alexandria, Virginia, USA. New York: ACM, 2007: 584-597.
[52]	MILLER A, JUELS A, SHI E, et al.Permacoin: Repurposing Bitcoin Work for Data Preservation[C]//IEEE. 2014 IEEE Symposium on Security and Privacy (SP), May 18-21, 2014, San Jose, CA, USA. New York: IEEE, 2014: 475-490.
[53]	BIRYUKOV A, KHOVRATOVICH D. Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem [EB/OL]. , 2016-10-27.
[54]	WAGNER D.A Generalized Birthday Problem[C]//Springer. Annual International Cryptology Conference, August 18-22, 2002, Santa Barbara, California, USA. Berlin: Springer, 2002: 288-304.
[55]	WOOD G.Ethereum: A Secure Decentralised Generalised Transaction Ledger[J]. Ethereum project yellow paper, 2014, 151: 1-32.
[56]	HANKE T, Movahedi M, Williams D.Dfinity Technology Overview Series,Consensus System[EB/OL].arXiv preprint arXiv:1805.04548, 2018-5-11.
[57]	PASS R, SHI E.Fruitchains: A Fair Blockchain[C]//ACM. Proceedings of the ACM Symposium on Principles of Distributed Computing, July 25-27, 2017, Washington, DC, USA. New York: ACM, 2017: 315-324.
[58]	KWON J.Tendermint: Consensus without Mining[EB/OL]., 2019-4-19.
[59]	GILAD Y, HEMO R, MICALI S, et al.Algorand: Scaling Byzantine Agreements for Cryptocurrencies[C]//ACM. Proceedings of the 26th Symposium on Operating Systems Principles, October 28, 2017, Shanghai, China. New York: ACM, 2017: 51-68.
[60]	BUTERIN V, GRIFFITH V. Casper the Friendly Finality Gadget[EB/OL]., 2017-10-15.
[61]	KIAYIAS A, RUSSELL A, DAVID B, et al.Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol[C]// Springer. 37th Annual International Cryptology Conference Annual International Cryptology Conference, August 20-24, 2017, Santa Barbara, CA, USA. Cham: Springer, 2017: 357-388.
[62]	CHEN L, XU L, SHAH N, et al.On Security Analysis of Proof-of-Elapsed-Time (PoET)[C]//Springer. 19thInternational Symposium on Stabilization, Safety, and Security of Distributed Systems, November 5-8, 2017, Boston, MA, USA. Cham: Springer, 2017: 282-297.
[63]	MILUTINOVIC M, HE W, WU H, et al.Proof of Luck: An Efficient Blockchain Consensus Protocol[C]//ACM. Proceedings of the 1st Workshop on System Software for Trusted Execution, December 12-16, 2016, Trento, Italy. New York: ACM, 2016: 1-6.
[64]	MCKEEN F, ALEXANDROVICH I, BERENZON A, et al.Innovative Instructions and Software Model for Isolated Execution[EB/OL]., 2013-4-14.
[65]	SCHNEIDER F B.Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial[J]. ACM Computing Surveys, 1990, 22(4): 299-319.
[66]	LARIMER D. Steem: an Incentivized,Blockchain-Based,Public Content Platform [EB/OL]. , 2018-7-15.
[67]	LARIMER D. Eos. Io Technical White Paper V2[EB/OL]. , 2018-4-28.
[68]	ZHANG E.A Byzantine Fault Tolerance Algorithm for Blockchain[EB/OL]. , 2019-1-7.
[69]	VUKOLIĆ M.Rethinking Permissioned Blockchains[C]// ACM. Proceedings of the ACM Workshop on Blockchain, Cryptocurrencies and Contracts, April 2, 2017, Abu Dhabi, United Arab Emirates. New York: ACM, 2017: 3-7.
[70]	SCHWARTZ D, YOUNGS N, BRITTO A. The Ripple Protocol Consensus Algorithm[EB/OL]. , 2014-5-12.
[71]	CHASE B, MACBROUGH E. Analysis of the XRP Ledger Consensus Protocol[EB/OL]. , 2018-2-15.
[72]	SOUSA J, BESSANI A, VUKOLIC M.A Byzantine Fault-Tolerant Ordering Service for the Hyperledger Fabric Blockchain Platform[C]//IEEE. 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), June 25-28, 2018, Luxembourg City, Luxembourg. New York: IEEE, 2018: 51-58.
[73]	HUNT P, KONAR M, JUNQUEIRA F P, et al.Zookeeper: Wait-Free Coordination for Internet-Scale Systems[EB/OL]., 2019-1-7.
[74]	MURATOV F, LEBEDEV A, IUSHKEVICH N, et al.Yac: BFT Consensus Algorithm for Blockchain[J].arXiv: 1809. 00554.
[75]	MARTINO W. Kadena The First Scalable,HighPerformance Private Blockchain[EB/OL]., 2016-8-24.
[76]	MAZIERES D.The Stellar Consensus Protocol: A Federated Model for Internet Level Consensus[EB/OL]., 2015-7-14.
[77]	CHAIN. Federated Consensus Protocol[EB/OL]., 2019-1-7.
[78]	HAN Xuan, LIU Yamin.Research on the Consensus Mechanisms of Blockchain Technology[J]. Netinfo Security, 2017, 17(9): 147-152.
	韩璇,刘亚敏.区块链技术中的共识机制研究[J].信息网络安全,2017,17(9):147-152.

算法	提出时间	容错类型	应用
VR	1988	CFT	Berkeley DB
Paxos	1990	CFT	Chubby
PBFT	1999	BFT (容错率<1/3)	Hyperledger v0.6
Query/Update	2005	BFT (容错率<1/5)	—
Hybrid/Quorum	2006	BFT (容错率<1/3)	—
Zyzzava	2007	BFT (容错率<1/3)	—
OBFT	2013	BFT (容错率<1/3)	—
RBFT	2013	BFT (容错率<1/3)	Hyperledger Indy
Raft	2014	CFT	etcd
Tangaroa	2014	BFT (容错率<1/3)	—
HoneyBadger BFT	2016	BFT (容错率<1/3)	POA Network

共识算法	PoW	PoS	DPoS	PBFT
容错率	50%	50%	50%	33%
出块时间	>500s	<100s	<100s	<10s
吞吐量(TPS)	<10	<1000	>1000	<2000
可扩展性	强	强	强	弱

共识算法	核心思想	优点	缺点
PoW	拥有最高算力的节点易获得新区块的记账权和区块奖励,再由全网节点验证区块的正确性	算法简单,可操作性强,节点自由加入或者退出,可扩展性强	严重浪费电力等资源,依赖专业挖矿硬件资源,算力集中在几大矿场之间,有中心化风险且效率低下,交易吞吐量小
PoS	拥有最高权益的节点易获得新区块的记账权和区块奖励,再由全网节点验证区块的正确性	降低了PoW机制算力的浪费,节点不再依赖专业挖矿硬件资源,节点自由加入或者退出,可扩展性强	需要完善解决PoS机制存在的“无利害关系”问题,吞吐量小,一些平台手续费高
DPoS	由拥有权益的节点选出前N个超级节点作为新区块的记账节点,这些受理人轮流获得记账权和区块奖励	高吞吐量,更快地确认时间,降低能源损耗,节省了区块确认时间,减少了交易延迟,吞吐量得到极大提高,节点自由加入或者退出,可扩展性强	超级节点投票麻烦,投票期间需要锁定代币,不利于激发普通节点参与,固定数量超级节点的竞选规则令人担忧,去中心化的实现存在争议
PBFT	主节点排序请求,从节点响应请求,多数节点响应结果为最终结果	共识结果的一致性和正确性程度高,确认时间快	算法复杂度较高,通信量大;当节点数量过多时,运行效率较低

算法名称	设计基础	设计目标	谜题特性	网络实现
Bitcoin-NG	两种类型的区块	提高吞吐量	PoW谜题	无
Elastico	分片技术	增强扩展性	PoW谜题	无
PoUW^[50]	寻找坎宁安链	将算力用在有用方面	顺序搜寻	质数币
Proof of Retrievability	梅克尔树上文档碎片	分布式存储	两阶段挑战	永久币
Equihash	广义生日悖论	抵抗ASIC矿机	Memory-hard	Zcash
Ethash	DAG	抵抗ASIC矿机,提高区块生成速度	Memory-hard	以太坊

算法名称	虚拟挖矿	混合算法	模拟领导者选举	最长链规则	算法特性
PoS（Peercoin）	是	PoW?PoS	权益竞争	是	权益代替算力竞争
Tendermint	是	PoS?BFT	可证的随机函数	是	确定性共识
Algorand	是	PoS?BFT	可证的随机函数	是	在同步时可保证安全性和活性
Casper FFG	否	PoS?BFT	PoW哈希解谜竞争	是	验证者集合借助BFT算法
Ouroboros	是	PoS	掷硬币协议	是	严格安全性保障
Proof of Luck/Elapsed Time	是	否	Intel-SGX执行的可信任随机函数	是	无资源消耗
BFT-DPoS	是	PoS?BFT	选举后轮流	是	确定性的共识