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

doi:10.3778/j.issn.1673-9418.2112077

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (6): 1214-1242.DOI: 10.3778/j.issn.1673-9418.2112077

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP309.7

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

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.

图/表 22

图1 区块链共识基础模型

Fig.1 Blockchain consensus base model

图2 两军问题示意图

Fig.2 Two-army problem pattern

图3 三个将军中一个是叛徒

Fig.3 One of three generals is a traitor

图4 PBFT协议运行示意图

Fig.4 PBFT protocol communication pattern

图5 CAP定理的属性取舍

Fig.5 Attribute trade-off of CAP theorem

图6 Paxos算法运行过程描述

Fig.6 Description of running process of Paxos algorithm

表1 经典共识算法

Table 1 Classical consensus algorithm

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

图7 比特币系统中PoW共识算法的实现流程

Fig.7 Realization process of PoW consensus algorithm in bitcoin system

图8 以太坊Ethash共识算法的实现流程

Fig.8 Realization process of Ethash consensus algorithm in Ethereum system

图9 Ethash算法中区块、种子、缓存和数据集之间的关系

Fig.9 Relationship among block, seed, cache, and dataset in Ethash algorithm

图10 Bitcoin-NG共识算法示意图

Fig.10 Schematic diagram of Bitcoin-NG consensus algorithm

表2 PoW及其改进算法

Table 2 PoW and its improved algorithms

名称	年份	能耗	出块速度	分叉	算力分布
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	无	分散

图11 Ouroboros共识算法的执行流程

Fig.11 Implementation process of Ouroboros consensus algorithm

表3 典型PoS共识算法的性能比较

Table 3 Preformance comparison of typical PoS consensus algorithms

名称	年份	安全性	出块速度	分叉	去中心化
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	分叉	去中心化

图12 Casper FFG共识算法流程示意图

Fig.12 Flow diagram of Casper FFG consensus algorithm

表4 组成投票消息的4条信息

Table 4 Four pieces of information that makes up voting message

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

图13 2-hop区块链结构

Fig.13 2-hop blockchain structure

表5 典型PoW+PoS共识算法的性能比较

Table 5 Performance comparison of typical PoW+PoS consensus algorithms

名称	年份	主要解决问题	典型应用
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

图14 Chainspace共识算法流程示意图

Fig.14 Flow diagram of Chainspace consensus algorithm

图15 PeerCensus共识算法组成示意图

Fig.15 Schematic diagram of PeerCensus consensus algorithm

图16 OmniLedger共识算法总体架构

Fig.16 Overall architecture of OmniLedger consensus algorithm

表6 典型PoW/PoS+BFT/PBFT共识算法的性能比较

Table 6 Performance comparison of typical PoW/PoS+BFT/PBFT consensus algorithms

算法名称	年份	核心算法	分片类型	通信模型	应用场景
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	单一分片	异步	公有链

参考文献 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.

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

Survey on Blockchain Consensus Algorithms and Application

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 22

参考文献 106

相关文章 12

编辑推荐

Metrics

[1]	刘同来, 章子凯, 武继刚. 面向医疗图像协同分析的系统模型及访问控制[J]. 计算机科学与探索, 2022, 16(8): 1779-1791.
[2]	熊啸, 李雷孝, 高静, 高昊昱, 杜金泽, 郑岳, 牛铁铭. 区块链在车联网数据共享领域的研究进展[J]. 计算机科学与探索, 2022, 16(5): 1008-1024.
[3]	韩刚, 吕英泽, 罗维, 王嘉乾. 重大疫情患者隐私数据保护方案研究[J]. 计算机科学与探索, 2022, 16(2): 359-371.
[4]	樊星, 牛保宁. 区块链应用下的新型区块链布隆过滤器[J]. 计算机科学与探索, 2021, 15(10): 1921-1929.
[5]	周健，孙丽艳，付明. 抗货币失效的区块链钱包保护协议研究[J]. 计算机科学与探索, 2020, 14(12): 2039-2049.
[6]	郑良汉，何亨，童潜，杨湘，陈享. 云环境中的多授权机构访问控制方案[J]. 计算机科学与探索, 2020, 14(11): 1865-1878.
[7]	王群，李馥娟，王振力，梁广俊，徐杰. 区块链原理及关键技术[J]. 计算机科学与探索, 2020, 14(10): 1621-1643.
[8]	赵守月，葛洪伟. MEPaxos：低延迟的共识算法[J]. 计算机科学与探索, 2019, 13(5): 866-874.
[9]	贾大宇，信俊昌，王之琼，郭薇，王国仁. 区块链的存储容量可扩展模型[J]. 计算机科学与探索, 2018, 12(4): 525-535.
[10]	李舟军，张江霄，冯春辉，隋春荣. 电子现金协议研究综述[J]. 计算机科学与探索, 2017, 11(11): 1701-1712.
[11]	周爽，鲍玉斌，王志刚，冷芳玲，于戈，邓超，郭磊涛. BHP：面向BSP模型的负载均衡Hash图数据划分[J]. 计算机科学与探索, 2014, 8(1): 40-50.
[12]	李影1+ ,黄罡2 ,刘天成1 ,杨杰1 ,刘钊2 . 迈向管理服务化[J]. 计算机科学与探索, 2008, 2(4): 346-355.