Survey on Blockchain Consensus Algorithms and Application

doi:10.3778/j.issn.1673-9418.2112077

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (6): 1214-1242.DOI: 10.3778/j.issn.1673-9418.2112077

• Surveys and Frontiers • Previous Articles Next Articles

Survey on Blockchain Consensus Algorithms and Application

WANG Qun¹^,², LI Fujuan¹^,⁺(), NI Xueli¹^,², XIA Lingling¹, WANG Zhenli¹, LIANG Guangjun¹^,²

1. Department of Computer Information and Cybersecurity, Jiangsu Police Institute, Nanjing 210031, China
2. Jiangsu Electronic Data Forensics and Analysis Engineering Research Center, Nanjing 210031, China

Received:2021-12-20 Revised:2022-02-14 Online:2022-06-01 Published:2022-06-20
About author:WANG Qun, born in 1971, Ph.D., professor, member of CCF. His research interests include information security, computer network architecture and protocols.
LI Fujuan, born in 1974, M.S., professor. Her research interests include computer network technology and application and information security.
NI Xueli, born in 1990, M.S., lecturer. Her research interests include digital forensics and cyberspace security.
XIA Lingling, born in 1988, Ph.D., associate professor, member of Jiangsu Cyberspace Security Association. Her research interests include network security technology, spreading dynamics of complex networks, web crawler technology and data mining.
WANG Zhenli, born in 1977, Ph.D., associate professor. His research interests include blockchain technology and applications.
LIANG Guangjun, born in 1982, Ph.D., lecturer. His research interests include digital forensics and cyberspace security.
Supported by:
National Natural Science Foundation of China(61802155);Natural Science Research Major Project of Jiangsu Province(20KJA520004);Project of Excellent Scientific and Technological Innovation Team of Jiangsu Universities;Key Disciplines Project of Jiangsu Province in the 14th Five-Year Plan: Public Security Technology and Cyberspace Security;Public Security Technology and Cyberspace Security, and the Social Science Fund of Jiangsu Province(21MLD012)

区块链共识算法及应用研究

王群¹^,², 李馥娟¹^,⁺(), 倪雪莉¹^,², 夏玲玲¹, 王振力¹, 梁广俊¹^,²

1. 江苏警官学院计算机信息与网络安全系,南京 210031
2. 江苏省电子数据取证分析工程研究中心,南京 210031

通讯作者: + E-mail: lfj@jspi.edu.cn
作者简介:王群（1971—）,男,甘肃天水人,博士,教授,CCF会员,主要研究方向为信息安全、计算机网络体系结构与协议。
李馥娟（1974—）,女,陕西西安人,硕士,教授,主要研究方向为计算机网络技术与应用、信息安全。
倪雪莉（1990—）,女,江苏南通人,硕士,讲师,主要研究方向为电子数据取证、网络空间安全。
夏玲玲（1988—）,女,江苏射阳人,博士,副教授,江苏省网络空间安全学会会员,主要研究方向为网络安全、复杂网络传播动力学、网络爬虫、数据挖掘。
王振力（1977—）,男,安徽寿县人,博士,副教授,主要研究方向为区块链技术与应用。
梁广俊（1982—）,男,安徽芜湖人,博士,讲师,主要研究方向为电子数据取证、网络空间安全。
基金资助:
国家自然科学基金(61802155);江苏省高校自然科学研究重大项目(20KJA520004);江苏省高校优秀科技创新团队项目;公安技术、网络空间安全“十四五”江苏省重点学科项目;江苏省社会科学基金项目研究成果(21MLD012)

Abstract

Abstract:

The consensus algorithm, as the core technology of blockchain, provides mechanism support and guarantee for the realization of functions such as decentralization, openness, autonomy, information tamperability and anonymous traceability, and realizes efficient achievement of strong and final consistency in distributed system. The consensus algorithms are divided into the previous classical distributed consensus algorithms and the subsequent blockchain consensus algorithms by taking the emergence of bitcoin as the time node. On this basis, the consensus algorithms are further classified according to the implementation principle, the typical algorithms are selected, and then the discussion is focused on decentralization, scalability, security, consistency and so on. Firstly, a general model of blockchain consensus algorithm is proposed, and the basic definition of consensus algorithm is given. Secondly, while introducing the characteristics of the classical distributed consensus algorithms, the distributed consistency algorithms and their improvements such as the two armed forces problem, the Byzantine generals problem, the FLP impossibility theorem, the CAP theorem and Paxos algorithm are studied, and then the execution process and functional characteristics of the algorithm are analyzed. Thirdly, the blockchain consensus algorithms are divided into POW consensus algorithm, POS consensus algorithm, POW+POS hybrid consensus algorithm and POW/POS+BFT/PBFT hybrid consensus algorithm according to different implementation principles and application scenarios. The algorithm flow is given respectively after selecting representative algorithms in each category, and then the specific application scenarios are deeply analyzed. Finally, the research hotspots and development directions of blockchain consensus algorithms in performance and scalability, incentive mechanism, security and privacy, parallel processing and so on are pointed out.

Key words: blockchain, consensus algorithms, distributed systems, Byzantine fault tolerance

摘要：

作为区块链核心技术的共识算法,为区块链的去中心化、开放自治、信息不可篡改、匿名溯源等功能的实现提供了机制支撑和保障,实现了分布式系统中强一致性和最终一致性的高效达成。以比特币出现为时间节点,将共识算法分为之前的经典分布式共识算法和之后的区块链共识算法,在此基础上根据算法的实现原理对共识算法又进一步分类,并选择其中的典型算法,重点从去中心化、可扩展性、安全性、一致性等方面进行了讨论。首先,提出了区块链共识算法的一般模型,给出了共识算法的基本定义。其次,在介绍经典分布式共识算法特点的同时,研究了两军问题、拜占庭将军问题、FLP不可能性定理、CAP定理和Paxos等分布式一致性算法及其改进,分析了算法的执行流程和功能特征。再次,对于区块链共识算法,根据实现原理和应用场景的不同,将其分为PoW共识算法、PoS共识算法、PoW+PoS混合共识算法和PoW/PoS+BFT/PBFT混合共识算法,在每一类中选择了具有代表性的算法后分别给出了算法流程,并结合具体应用场景进行了深入分析。最后,指出了区块链共识算法在性能与可扩展性、激励机制、安全与隐私、并行处理等方面的研究热点和发展方向。

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

CLC Number:

TP309.7

WANG Qun, LI Fujuan, NI Xueli, XIA Lingling, WANG Zhenli, LIANG Guangjun. Survey on Blockchain Consensus Algorithms and Application[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(6): 1214-1242.

王群, 李馥娟, 倪雪莉, 夏玲玲, 王振力, 梁广俊. 区块链共识算法及应用研究[J]. 计算机科学与探索, 2022, 16(6): 1214-1242.

Figures/Tables 22

References 106

[1]	王群, 李馥娟, 王振力, 等. 区块链原理及关键技术[J]. 计算机科学与探索, 2020, 14(10): 1621-1643.
	WANG Q, LI F J, WANG Z L, et al. Principle and core technology of blockchain[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1621-1643.
[2]	MIRAZ M H. Blockchain: technology fundamentals of the trust machine[EB/OL]. (2017-12-23)[2021-07-12]. https://www.legalanalytics.law.cuhk.edu.hk/post/2017/12/23/blockchain-technology-fundamentals-of-the-trust-machine .
[3]	FANTI G, VISWANATH P. Anonymity properties of the bitcoin P2P network[J]. arXiv:1703.08761, 2017.
[4]	NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash system[EB/OL]. (2018-06-10)[2021-07-13]. https://bitcoin.org/ bitcoin.pdf
[5]	袁勇, 倪晓春, 曾帅, 等. 区块链共识算法的发展现状与展望[J]. 自动化学报, 2018, 44(11): 2011-2022.
	YUAN Y, NI X C, ZENG S, et al. Blockchain consensus algorithms: the state of the art and future trends[J]. Acta Automatica Sinica, 2018, 44(11): 2011-2022.
[6]	刘懿中, 刘建伟, 张宗洋, 等. 区块链共识机制研究综述[J]. 密码学报, 2019, 6(4): 395-432.
	LIU Y Z, LIU J W, ZHANG Z Y, et al. Overview on blockchain consensus mechanisms[J]. Journal of Cryptologic Research, 2019, 6(4): 395-432.
[7]	夏清, 窦文生, 郭凯文, 等. 区块链共识协议综述[J]. 软件学报, 2021, 32(2): 277-299.
	XIA Q, DOU W S, GUO K W, et al. Survey on blockchain consensus protocol[J]. Journal of Software, 2021, 32(2): 277-299.
[8]	靳世雄, 张潇丹, 葛敬国, 等. 区块链共识算法研究综述[J]. 信息安全学报, 2021, 6(2): 85-100.
	JIN S X, ZHANG X D, GE J G, et al. Overview of blockchain consensus algorithm[J]. Journal of Cyber Security, 2021, 6(2): 85-100.
[9]	NGUYEN G T, KIM K. A survey about consensus algorithms used in blockchain[J]. Journal of Information Processing Systems, 2018, 14(1): 101-128.
[10]	YIU N. An overview of forks and coordination in blockchain development[J]. arXiv: 2102.10006, 2021.
[11]	LASHKARI B, MUSILEK P. A comprehensive review of blockchain consensus mechanisms[J]. IEEE Access, 2021, 9(3): 43620-43652. DOI URL
[12]	BOURAGA S. A taxonomy of blockchain consensus protocols: a survey and classification framework-ScienceDirect[J]. Expert Systems with Applications, 2021, 168: 114384. DOI URL
[13]	LAMPORT L. How to make a multiprocessor computer that correctly executes multiprocess programs[J]. IEEE Transactions on Computers, 1979, 28(9): 690-691.
[14]	KRISHNA S, EMMI M, ENEA C, et al. Verifying visibility-based weak consistency[C]// LNCS 12075: Proceedings of the 29th European Symposium on Programming, Dublin, Apr 25-30, 2020. Cham: Springer, 2020: 280-307.
[15]	MA Z F. Handbook of blockchain technology development[M]. Beijing: Tsinghua University Press, 2021.
	马兆丰. 区块链技术开发指南[M]. 北京: 清华大学出版社, 2021.
[16]	HERRERA-JOANCOMARTÍ J. Research and challenges on bitcoin anonymity[C]// LNCS 8872: Proceedings of the 9th International Workshop on Data Privacy Management, Autonomous Spontaneous Security, and Security Assurance, Wroclaw, Sep 10-11, 2014. Cham: Springer, 2015: 3-16.
[17]	BADARI A, CHAUDHURY A. An overview of bitcoin and ethereum white-papers, forks, and prices[EB/OL]. (2021-05-11)[2021-08-10]. https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3841827 .
[18]	CACHIN C. Architecture of the hyperledger blockchain fabric[EB/OL]. (2016-01-01)[2021-08-16]. https://www.zurich. ibm.com/dccl/papers/cachin_dccl.pdf
[19]	ABRAHAM I, MALKHI D, NAYAK K, et al. Solida: a blockchain protocol based on reconfigurable Byzantine consensus[C]// Proceedings of the 21st International Conference on Principles of Distributed Systems, Lisbon, Dec 18-20, 2017: 25.
[20]	MANEAS A, CHONDROS N, DIAMANTOPOULOS P, et al. On achieving interactive consistency in real-world distributed systems[J]. Journal of Parallel and Distributed Computing, 2021, 147: 220-235. DOI URL
[21]	AKKOYUNLU E A, EKANADHAM K, HUBER R V. Some constraints and tradeoffs in the design of network communications[J]. ACM SIGOPS Operating Systems Review, 1975, 9(5): 67-74. DOI URL
[22]	LAMPORT L, SHOSTAK R, PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401. DOI URL
[23]	COWLING J, MYERS D S, LISKOV B, et al. HQ Replication: a hybrid quorum protocol for Byzantine fault tolerance[C]// Proceedings of the 7th Symposium on Operating Systems Design and Implementation, Seattle, Nov 6-8, 2003. New Orleans: USENIX Association, 2003: 177-190.
[24]	LAMPORT L. The part-time parliament[J]. ACM Transactions on Computer Systems, 1998, 16(2): 133-169. DOI URL
[25]	OKI B M, LISKOV B H. Viewstamped replication: a new primary copy method to support highly-available distributed systems[C]// Proceedings of the 7th Annual Conference on Principles of Distributed Computing, Toronto, Aug 15-17, 1988. New York: ACM, 1988: 8-17.
[26]	FAZLALI M, EFTEKHAR S M, DEHSHIBI M M, et al. Raft consensus algorithm: an effective substitute for Paxos in high throughput P2P-based systems[J]. arXiv: 1911.01231, 2019.
[27]	CASTRO M, LISKOV B. Practical Byzantine fault tolerance[C]// Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation, New Orleans, Feb 22-25, 1999. New Orleans: USENIX Association, 1999: 173-186.
[28]	THAI Q T, YIM J C, YOO T W, et al. Hierarchical Byzantine fault-tolerance protocol for permissioned blockchain systems[J]. The Journal of Supercomputing, 2019, 75(11): 7337-7365. DOI URL
[29]	CASTRO M, LISKOV B. Practical Byzantine fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems, 2002, 20(4): 398-461. DOI URL
[30]	JEHL L. Quorum selection for Byzantine fault tolerance[C]// Proceedings of the 39th International Conference on Distributed Computing Systems, Dallas, Jul 7-10, 2019. Piscataway: IEEE, 2019: 2168-2177.
[31]	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. DOI URL
[32]	WANG Y G. Blockchain BFT protocol for complete asynchronous networks[J]. arXiv: 2005.04309, 2020.
[33]	MUÑOZ-ESCOÍ F D, DE JUAN-MARÍN R, GARCÍA-ESCRIVÁ J R, et al. CAP theorem: revision of its related consistency models[J]. The Computer Journal, 2019, 62(6): 943-960. DOI URL
[34]	KLEPPMANN M. A critique of the CAP theorem[J]. arXiv:1509.05393, 2015.
[35]	En-Tan-Mo. En-Tan-Mo science[EB/OL]. (2019-11-27) [2021-08-10]. http://www.entanmo.com/docs/ETM%20Science_en-GB.pdf
[36]	HAN R, FOUTRIS N, KOTSELIDIS C. Demystifying crypto-mining: analysis and optimizations of memory-hard POW algorithms[C]// Proceedings of the 2019 IEEE International Symposium on Performance Analysis of Systems and Software, Madison, Mar 24-26, 2019. Piscataway: IEEE, 2019: 22-33.
[37]	JIANG X J, LIU X F. CryptoKitties transaction network analysis: the rise and fall of the first blockchain game mania[J]. Frontiers in Physics, 2021, 9: 631665. DOI URL
[38]	GARCÍA-PÉREZ Á, GOTSMAN A, MESHMAN Y, et al. Paxos consensus, deconstructed and abstracted[C]// LNCS 10801: Proceedings of the 27th European Symposium on Programming, Thessaloniki, Apr 14-20, 2018. Cham: Springer, 2018: 912-939.
[39]	LAMPORT L. Paxos made simple[J]. ACM SIGACT News, 2001, 32(4): 18-25.
[40]	LAMPORT L. Fastpaxos[J]. Distributed Computing, 2006, 19(2): 79-103. DOI URL
[41]	BURROWS M. The Chubby lock service for loosely-coupled distributed systems[C]// Proceedings of the 7th Symposium on Operating Systems Design and Implementation, Seattle, Nov 6-8, 2006. New Orleans: USENIX Association, 2006: 335-350.
[42]	KRZYZANOWSKI P. Google chubby[EB/OL]. (2021-03-01)[2021-07-12]. https://people.cs.rutgers.edu/-pxk/417/notes/chubby.html .
[43]	ISARD M. Autopilot: automatic data center management[J]. ACM SIGOPS Operating Systems Review, 2007, 41(2): 60-67. DOI URL
[44]	ZHENG J J, LIN Q, XU J T, et al. Paxos store: high- availability storage made practical in wechat[J]. Proceedings of the VLDB Endowment, 2017, 10(12): 1730-1741. DOI URL
[45]	HUANG D Y, MA X L, ZHANG S L. Performance analysis of the raft consensus algorithm for private blockchains[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 50(1): 172-181. DOI URL
[46]	HUNT P, KONAR M, JUNQEIRA F, et al. Zookeeper: wait-free coordination for internet-scale systems[C]// Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, Boston, Jun 23-25, 2010. New Orleans: USENIX Association, 2010: 11-25.
[47]	etcd. A distributed, reliable key-value store for the most critical data of a distributed system[EB/OL]. (2021-06-15)[2021-07-15]. https://etcd.io/ .
[48]	JAKOBSSON M, JUELS A. Proofs of work and bread pudding protocols[C]//Proceedings of the IFIP TC6/TC 11 Joint Working Conference on Secure Information Networks:Communications and Multimedia Security, Netherlands, Sep 20-21, 1999. Boston: Kluwer Academic Publishers, 1999: 258-272.
[49]	BACK A. Hashcash—a denial of service counter-measure[EB/OL]. (2002-08-01)[2021-08-30]. http://www.hashcash.org/papers/hashcash.pdf
[50]	WAHAB A, MEHMOOD W. Survey of consensus protocols[J]. arXiv: 1810.03357, 2018.
[51]	CONTI M, KUMAR E S, LAL C, et al. A survey on security and privacy issues of bitcoin[J]. IEEE Communications Surveys & Tutorials, 2018, 20(4): 3416-3452.
[52]	MUKHERJEE P, PRADHAN C. Blockchain 1.0 to Blockchain 4.0—the evolutionary transformation of blockchain technology[EB/OL]. (2021-05-01)[2021-09-01]. https://www. researchgate.net/publication/351263701_Blockchain_10_to_ Blockchain_40-The_Evolutionary_Transformation_of_Blockchain_Technology .
[53]	CHERNET H F, JILLEDI S K. A next-generation smart contract and decentralized blockchain platform: a case study on ethiopia[J]. Journal of Business Analytics and Data Visualization, 2020, 1(1): 28-34.
[54]	BRÜNJES L, GABBAY M J. UTxO- vs account-based smart contract blockchain programming paradigms[C]// LNCS 12478: Proceedings of the 9th International Symposium on Leveraging Applications of Formal Methods, Rhodes, Oct 20-30, 2020. Cham: Springer, 2020: 73-88.
[55]	BENCIC F M, ZARKO I P. Distributed ledger technology: blockchain compared to directed acyclic graph[C]// Proceedings of the 38th IEEE International Conference on Distributed Computing Systems, Vienna, Jul 2-6, 2018. Washington: IEEE Computer Society, 2018: 1569-1570.
[56]	Ethereum WiKi. ethash[EB/OL]. (2020-11-06)[2021-09-02]. https://eth.wiki/en/concepts/ethash/ethash .
[57]	TRADING C. X11 mining calculator[EB/OL]. (2020-07-21)[2021-09-02]. https://www2.ict.ufvjm.edu.br/index.php/2020/ 07/21/x11-mining-calculator/ .
[58]	PADMAVATHI M, SURESH R M. Secure P2P intelligent network transaction using litecoin[J]. Mobile Networks & Applications, 2019, 24(2): 318-326.
[59]	DASH. What is dash?[EB/OL]. (2021-06-03)[2021-09-01]. https://dashplatform.readme.io/docs/introduction-what-is-dash .
[60]	SOMPOLINSKY Y, ZOHAR A. Secure high-rate transaction processing in bitcoin[C]// LNCS 8975: Proceedings of the 2015 International Conference on Financial Cryptography and Data Security, San Juan, Jan 26-30, 2015. Cham: Springer, 2015: 507-527.
[61]	EYAL I, GENCER A E, SIRER E G, et al. Bitcoin-NG: a scalable blockchain protocol[J]. arXiv:1510.02037, 2015.
[62]	EYAL I, SIRER E G. Majority is not enough: bitcoin mining is vulnerable[J]. Communication of the ACM, 2018, 61(7): 95-102.
[63]	KOKORIS-KOGIAS E, JOVANOVIC P, GAILLY N, et al. Enhancing bitcoin security and performance with strong consistency via collective signing[C]// Proceedings of the 25th USENIX Security Symposium, Austin, Aug 10-12, 2016. New Orleans: USENIX Association, 2016: 279-296.
[64]	LUU L, NARAYANAN V, ZHENG C D, et al. A secure sharding protocol for open blockchains[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Oct 24-28, 2016. New York: ACM, 2016: 17-30.
[65]	KOKORIS-KOGIAS E, JOVANOVIC P, GASSER L, et al. OmniLedger:a secure, scale-out, decentralized ledger via sharding[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy, San Fransisco, May 20-23, 2018. Washington: IEEE Computer Society, 2018: 583-598.
[66]	PASS R, SHI E. FruitChains: a fair blockchain[C]// Procee-dings of the 2017 ACM Symposium on Principles of Distributed Computing, Washington, Jul 25-27, 2017. New York: ACM, 2017: 315-324.
[67]	LI C X, LI P L, ZHOU D, et al. Scaling nakamoto consensus to thousands of transactions per second[J]. arXiv:1805. 03870v4, 2018.
[68]	LASLA N, ALSAHAN L, ABDALLAH M, et al. Green-PoW: an energy-efficient blockchain proof-of-work consensus algorithm[J]. arXiv: 2007.04086, 2020.
[69]	KARA M, LAOUID A, ALSHAIKH M, et al. A compute and wait in PoW (CW-PoW) consensus algorithm for preserving energy consumption[J]. Applied Sciences, 2021, 11(15): 6750. DOI URL
[70]	QU X D, WANG S L, HU Q, et al. Proof of federated learning: a novel energy-recycling consensus algorithm[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(8): 2074-8085. DOI URL
[71]	MECHANIC Q. Proof of stake[EB/OL]. (2011-07-11)[2021-09-13]. https://bitcointalk.org/index.php?topic=27787 .
[72]	KING S, NADAL S. PPCoin: peer-to-peer crypto-currency with proof-of-stake[EB/OL]. (2012-08-19)[2021-09-05]. https://www.peercoin.net/assets/paper/peercoin-paper.pdf
[73]	Nxt community. Nxt whitepaper[EB/OL]. (2014-07-12) [2021-09-30]. https://www.jelurida.com/sites/default/files/NxtWhitepaper.pdf
[74]	VASIN P. BlackCoin’s proof-of-stake protocol v2[EB/OL]. [2021-09-30]. https://blackcoin.org/blackcoin-pos-protocol-v2-whitepaper.pdf
[75]	SCHUH F, LARIMER D, CRYPTONOMEX, et al. BitShare 2.0: financial smart contract platform[EB/OL]. (2015-11-01)[2021-10-02]. http://docs.bitshares.eu/_downloads/ bitshares-financial-platform.pdf
[76]	Bitshares. What is bitShares?[EB/OL]. (2019-01-01) [2021-10-02]. https://how.bitshares.works/en/master/technology/what_bitshares.html .
[77]	Steem. Steem: an incentivized, blockchain-based, public content platform[EB/OL]. (2019-06-01)[2021-10-02]. https://www.steem.com/steem-whitepaper.pdf
[78]	EOSIO. What is EOS?[EB/OL]. [2021-10-02]. https://eos.io/eos-public-blockchain/ .
[79]	KIAYIAS A, RUSSELL A, DAVID B, et al. Ouroboros: a provably secure proof-of-stake blockchain protocol[C]// LNCS 10401: Proceedings of the 37th Annual International Cryptology Conference Advances in Cryptology, Santa Barbara, Aug 20-24, 2017. Cham: Springer, 2017: 357-388.
[80]	GAŽI P, KIAYIAS A, ZINDROS D. Proof-of-stake sidechains[C]// Proceedings of the 2019 IEEE Symposium on Security and Privacy, San Francisco, May 19-23, 2019. Piscataway: IEEE, 2019: 139-156.
[81]	HALEVI S, HAZAY C, POLYCHRONIADOU A, et al. Round-optimal secure multi-party computation[J]. Journal of Cryptology, 2021, 34(3): 1-63. DOI URL
[82]	JZNBAZ S, ASGHARI R, BAGHERPOUR B, et al. A fast non-interactive publicly verifiable secret sharing scheme[C]// Proceedings of the 17th International ISC Conference on Information Security and Cryptology, Tehran, Sep 9-10, 2020. Piscataway: IEEE, 2020: 7-13.
[83]	ROTHBLUM R D, SEALFON A, SOTIRAKI K. Toward non-interactive zero-knowledge proofs for NP from LWE[J]. Journal of Cryptology, 2021, 34(1): 472-503.
[84]	DAVID B, GAŽI P, KIAYIAS A, et al. Ouroboros Praos:an adaptively-secure, semi-synchronous proof-of-stake blockchain[C]// LNCS 10821: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Apr 29-May 3, 2018. Cham: Springer, 2018: 66-98.
[85]	GANESH C, ORLANDI C, TSCHUDI D. Proof-of-stake protocols for privacy-aware blockchains[C]// Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, May 19-23, 2019. Cham: Springer, 2019: 690-719.
[86]	BADERTSCHER C, GAŽI P, KIAYIAS A, et al. Ouroboros Genesis: composable proof-of-stake blockchains with dynamic availability[C]// Proceedings of the 2018 ACM SIGSAC Conference, Toronto, Oct 15-19, 2018. New York: ACM, 2018: 913-930.
[87]	DEIRMENTZOGLOU E, PAPAKYRIAKOPOULOS G, PATSAKIS C. A survey on long-range attacks for proof of stake protocols[J]. IEEE Access, 2019(7): 28712-28725.
[88]	DAIAN P, PASS R, SHI E. Snow White: robustly reconfigurable consensus and applications to provably secure proof of stake[C]// LNCS 11598: Proceedings of the 23rd International Conference on Financial Cryptography and Data Security, Frigate Bay, Feb 18-22, 2019. Cham: Springer, 2019: 23-41.
[89]	REN L. Proof of stake velocity: building the social currency of the digital age[EB/OL](2018-04-10)[2021-10-15]. https://assets.coss.io/documents/whitepapers/reddcoin.pdf
[90]	BENTOV I, LEE C, MIZRAHI A, et al. Proof of activity: extending bitcoin’s proof of work via proof of stake[J]. ACM SIGMETRICS Performance Evaluation Review, 2014, 42(3): 34-37. DOI URL
[91]	BUTERIN V, GRIFFITH V. Casper the friendly finality gadget[J]. arXiv:1710.09437v4, 2017.
[92]	ORLICKI J I. Fair proof-of-stake using VDF+VRF consensus[J]. arXiv: 2008.10189v2, 2020.
[93]	BUTERIN V, HERNANDEZ D, KAMPHERFNER T, et al. Combining GHOST and casper[J]. arXiv: 2003.03052, 2020.
[94]	DUONG T, FAN L, KATZ J, et al. 2-hop Blockchain: combining proof-of-work and proof-of-stake securely[C]// LNCS 12309: Proceedings of the 25th European Symposium on Research in Computer Security, Guildford, Sep 14-18, 2020. Cham: Springer, 2020: 697-712.
[95]	KARANTIAS K, KIAYIAS A, ZINDROS D. Proof-of-burn[C]// LNCS 12059: Proceedings of the 24th International Conference on Financial Cryptography and Data Security 2020, Kota Kinabalu, Feb 10-14, 2020. Cham: Sprin-ger, 2020: 523-540.
[96]	ABRAHAM I, MALKHI D, NAYAK K, et al. Solida: a blockchain protocol based on reconfigurable Byzantine consensus[J]. arXiv:1612.02916v2, 2016.
[97]	PASS R, SHI E. Hybrid consensus: efficient consensus in the permissionless model[C]// Proceedings of the 31st International Symposium on Distributed Computing, Vienna, Oct 16-20, 2017. Leibniz: Zentrum für Informatik, 2017: 39.
[98]	AI-BASSAM M, SONNINO A, BANO S, et al. Chainspace: a sharded smart contracts platform[J]. arXiv:1708.03778, 2017.
[99]	ZAMANI M, MOVAHEDI M, BAYKOVA M, et al. RapidChain: scaling blockchain via full sharding[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, Oct 15-19, 2018. New York: ACM, 2018: 931-948.
[100]	DECKER C, SEIDEL J, WATTENHOFER R. Bitcoin meets strong consistency[J]. arXiv:1412.7935, 2014.
[101]	KOKORIS-KOGIAS E, JOVANOVIC P, GASSER L, et al. OmniLedger:a secure, scale-out, decentralized ledger via sharding[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy, San Francisco, May 20-24, 2018. Washington: IEEE Computer Society, 2018: 583-598.
[102]	SYTA E, JOVANOVIC P, KOKORIS-KOGIAS E, et al. Scalable bias-resistant distributed randomness[C]// Proceedings of the 2017 IEEE Symposium on Security and Privacy, San Jose, May 22-26, 2017. Washington: IEEE Computer Society, 2017: 444-460.
[103]	WANG J P, WANG H. Monoxide: scale out blockchains with asynchronous consensus zones[C]// Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation, Boston, Feb 26-28, 2019. New Orleans: USENIX Association, 2019: 95-112.
[104]	GILAD Y, HEMO R, MICALI S, et al. Algorand: scaling Byzantine agreements for cryptocurrencies[C]// Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, Oct 28-31, 2017. New York: ACM, 2017: 51-68.
[105]	WANG Q, LI R J, CHEN S P, et al. Formal security analysis on dBFT protocol of NEO[C]// Proceedings of the 24th International Conference on Financial Cryptography and Data Security, Kota Kinabalu, Feb 10-14, 2020. Cham: Springer, 2020: 20-31.
[106]	王晨旭, 程加成, 桑新欣, 等. 区块链数据隐私保护: 研究现状与展望[J]. 计算机研究与发展, 2021, 58(10): 2099-2119.
	WANG C X, CHENG J C, SANG X X, et al. Data privacy-preserving for blockchain: state of the art and trends[J]. Journal of Computer Research and Development, 2021, 58(10): 2099-2119.

名称	年份	拜占庭容错	节点是否可靠	链路是否可靠	通信模型
两军问题^[21]	1975	否	是	否	不限
拜占庭将军问题^[22]	1982	是（<1/3)	否	是	部分同步
FLP^[31]	1985	否	允许1个失败	是	异步
CAP^[33-34]	2019	是（≥1/3)	是	否	异步
Paxos^[24]	1998	否	是	是	部分同步

名称	年份	拜占庭容错	节点是否可靠	链路是否可靠	通信模型
两军问题^[21]	1975	否	是	否	不限
拜占庭将军问题^[22]	1982	是（<1/3)	否	是	部分同步
FLP^[31]	1985	否	允许1个失败	是	异步
CAP^[33-34]	2019	是（≥1/3)	是	否	异步
Paxos^[24]	1998	否	是	是	部分同步

名称	年份	能耗	出块速度	分叉	算力分布
PoW^[48]	1999	高	10 min	有	集中
Ethash^[56]	2014	较高	15 s	易	分散
Bitcoin-NG^[61]	2015	较低	主块10 min、微块10 s	易	较集中
ByzCoin^[63]	2016	较低	区块1 MB时约1/100 s	易	较集中
ByzCoinX^[65]	2018	较低	—	无	较集中
FruitChains^[66]	2017	低	—	—	分散
Conflux^[67]	2018	低	<1/6 000 s	无	分散

名称	年份	能耗	出块速度	分叉	算力分布
PoW^[48]	1999	高	10 min	有	集中
Ethash^[56]	2014	较高	15 s	易	分散
Bitcoin-NG^[61]	2015	较低	主块10 min、微块10 s	易	较集中
ByzCoin^[63]	2016	较低	区块1 MB时约1/100 s	易	较集中
ByzCoinX^[65]	2018	较低	—	无	较集中
FruitChains^[66]	2017	低	—	—	分散
Conflux^[67]	2018	低	<1/6 000 s	无	分散

名称	年份	安全性	出块速度	分叉	去中心化
DPoS^[75]	2014	较弱	0.5 s（EOS)	短期分叉	部分中心化
Ouroboros^[79]	2017	较强	20 s（ADA)	无	中心化
Ouroboros Praos^[84]	2018	强	<20 s	无	中心化
Ouroboros Genesis^[86]	2018	更强	<20 s	无	中心化
Snow White^[88]	2016	强	<20 s	分叉	去中心化

Survey on Blockchain Consensus Algorithms and Application

区块链共识算法及应用研究

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 22

References 106

Related Articles 9

Recommended Articles

Metrics

字段名	描述
s	已经被确认的检查点（checkpoint）区块
t	目标确认检查点区块
h(s)	已确认检查点的高度
h(t)	目标确认检查点的高度

名称	年份	主要解决问题	典型应用
PoSV^[89]	2014	屯积币龄	Reddcoin
PoA^[90]	2014	持币者不积极参与挖矿	Decred
Casper FFG^[91]	2017	无利害关系攻击、长程攻击	Ethereum2.0
2-hop^[94]	2020	51%算力（PoW）或权益（PoS）攻击	—
PoB^[95]	2020	屯积代币	Slimcoin

算法名称	年份	核心算法	分片类型	通信模型	应用场景
Solida^[96]	2016	PoW+BFT	单一分片	异步	公有链
Hybrid consensus^[97]	2017	PoW+BFT	单一分片	异步	公有链
Chainspace^[98]	2017	PoW+BFT	多分片	异步	联盟链
RapidChain^[99]	2018	PoW+BFT	多分片	部分同步	公有链
PeerCensus^[100]	2014	PoW+PBFT	单一分片	部分同步	公有链
ByzCoin^[63]	2016	PoW+PBFT	单一分片	部分同步	公有链
OmniLedger^[101]	2018	PoW+PBFT	多分片	同步	联盟链/ 公有链
ELASTICO^[64]	2016	PoW+PBFT	多分片	同步	联盟链/ 公有链
Monoxide^[103]	2019	PoW+PBFT	多分片	同步	联盟链/ 公有链
Algorand^[104]	2017	PoS+BFT	单一分片	部分同步	公有链
dBFT^[105]	2020	PoS+BFT	单一分片	异步	公有链

[1]	LIU Tonglai, ZHANG Zikai, WU Jigang. System Model and Access Control Schemes for Medical Image Collaborative Analysis [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(8): 1779-1791.
[2]	XIONG Xiao, LI Leixiao, GAO Jing, GAO Haoyu, DU Jinze, ZHENG Yue, NIU Tieming. Research Progress of Blockchain in Internet of Vehicles Data Sharing [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(5): 1008-1024.
[3]	HAN Gang, LYU Yingze, LUO Wei, WANG Jiaqian. Privacy Data Protection Scheme for Patients with Major Outbreaks [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 359-371.
[4]	FAN Xing, NIU Baoning. BBF: Bloom Filter Variant for Blockchain [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 1921-1929.
[5]	ZHOU Jian, SUN Liyan, FU Ming. Research on Wallet Protection Against Currency Failure in Blockchain [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(12): 2039-2049.
[6]	ZHENG Lianghan, HE Heng, TONG Qian, YANG Xiang, CHEN Xiang. Multi-authority Access Control Scheme in Cloud Environment [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(11): 1865-1878.
[7]	WANG Qun, LI Fujuan, WANG Zhenli, LIANG Guangjun, XU Jie. Principle and Core Technology of Blockchain [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1621-1643.
[8]	JIA Dayu, XIN Junchang, WANG Zhiqiong, GUO Wei, WANG Guoren. Storage Capacity Scalable Model for Blockchain [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(4): 525-535.
[9]	LI Zhoujun, ZHANG Jiangxiao, FENG Chunhui, SUI Chunrong. Survey on E-Cash Scheme [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(11): 1701-1712.