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 Qun1,2, LI Fujuan1,+(), NI Xueli1,2, XIA Lingling1, WANG Zhenli1, LIANG Guangjun1,2   

  1. 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,2, 李馥娟1,+(), 倪雪莉1,2, 夏玲玲1, 王振力1, 梁广俊1,2   

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

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: