Survey on Consensus Algorithms of Blockchain

doi:10.3969/j.issn.1671-1122.2019.07.002

Abstract

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

CLC Number:

TP309

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

Figures/Tables 12

References 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	选举后轮流	是	确定性的共识