区块链共识算法综述

doi:10.11896/jsjkx.241100140

摘要/Abstract

摘要： 共识算法是区块链的核心支撑技术,本质上是分布式系统各节点就特定数据达成一致性的问题。目前,共识算法存在的最大瓶颈是通信复杂性带来的延迟和吞吐量对区块链性能产生的影响。据此,在系统综述共识技术发展脉络的基础上,分析了基于轮次(Basic-Round,BR)的DAG(Directed Acyclic Graph)分类标准,深入研究了BR-DAG共识算法的核心原理、共识过程,重点阐述了BR-DAG类共识算法降低网络通信延迟、提升共识收敛速度以及提高交易吞吐量的问题。进一步总结了BBCA-Chain等前沿共识算法的研究现状、存在的问题及发展趋势。此外,根据既定的分类标准,提出综合评价体系对各类共识算法在吞吐量、延迟等性能维度上进行对比分析。最后,讨论了目前共识算法面临的挑战,提出未来研究可以围绕BR-DAG和Rho-calculate构建基于消息交互传递的并发计算模型。通过形式化验证的方式,实现高吞吐量、低延迟并且稳健的共识算法。

关键词: 共识算法, 区块链, 拜占庭容错, BBCA-chain, Rho-calculate

Abstract: The consensus algorithm is a critical technological cornerstone of blockchain,facilitating consistency among nodes within a distributed system concerning specific data.The primary bottleneck in current consensus algorithms lies in the impact of communication complexity on blockchain performance,specifically in terms of latency and throughput.To address these challenges,this paper presents a comprehensive analysis the development of consensus technology,with a particular focus on the Basic-Round(BR)-based Directed Acyclic Graph(DAG) classification criterion.The present study aims to analyse the core principles of the BR-DAG consensus algorithm and the consensus process.The objective of this analysis is to mitigate the inherent limitations of BR-DAG consensus algorithms by reducing network communication latency,enhancing convergence speed,and increasing transaction throughput.This study offers an extensive review of the current state of research,existing challenges,and emerging trends in advanced consensus algorithms,with a specific emphasis on BBCA-Chain.Furthermore,we propose a robust evaluation framework designed to facilitate the comparative analysis of various consensus algorithms based on throughput,latency,and other performance dimensions,aligned with established classification criteria.Finally,it discusses the prevailing challenges faced by consensus algorithms and proposes future research directions that should focus on BR-DAG and Rho-calculate.This includes the development of concurrent computation models based on message interaction delivery and the formal verification of consensus algorithm correctness.To achieve a high-throughput,low-latency,and robust consensus algorithm,formal verification methods can be employed.

Key words: Consensus algorithm, Blockchain, Byzantine fault tolerance, BBCA-Chain, Rho-calculate

中图分类号:

TP309

周凯, 陈福, 鲁添元, 曹怀虎. 区块链共识算法综述[J]. 计算机科学, 2025, 52(11): 255-269. https://doi.org/10.11896/jsjkx.241100140

ZHOU Kai, CHEN Fu, LU Tianyuan, CAO Huaihu. Review of Blockchain Consensus Algorithm[J]. Computer Science, 2025, 52(11): 255-269. https://doi.org/10.11896/jsjkx.241100140

参考文献

[1]NAKAMOTO S.Bitcoin:A peer-to-peer electronic cash system[EB/OL].https://bitcoin.org/bitcoin.pdf?kuid=5e3c690d-b96e-4fb7-a9cd-c3119e61fe99-1743128278.
[2]ROLIM J,MUELLER F,ZOMAYA Y.Parallel and Distributed Processing[J].Lecture Notes in Computer Science,1993,5(3):217-221.
[3]GRAY J.The transaction concept:Virtues and limitations[C]//VLDB.1981:144-154.
[4]SHAO Q F,ZHANG S,ZHU Y C,et al.Overview of Enterprise Blockchain Technology[J].Journal of Software,2019,30(9):2571-2592.
[5]LAMPORT L,SHOSTAK R,PEASE M.The Byzantine Gene-rals Problem[J].ACM Transactions on Programming Languages and Systems,1982,4(3):382-401.
[6]HAN X,YUAN Y,WANG F Y.Security Problems on Block-chain:The State of the Art and Future Trends[J].Acta Automatica Sinica,2019,45(1):206-225.
[7]WANG Q,LI F J,NI X L,et al.Survey on Blockchain Consensus Algorithms and Application[J].Journal of Frontiers of Computer Science & Technology,2022,16(6):1214-1242.
[8]FISCHER M J,LYNCH N A,PATERSON M.Impossibility of distributed consensus with one faulty process[J].Journal of the ACM,1985,32(2):374-382.
[9]DWORK C,NAOR M.Pricing via processing or combatting junk mail[C]//Advances in Cryptology—CRYPTO'92.Berlin:Springer,1993:139-147.
[10]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.
[11]LAMPORT L.The Part-Time Parliament[J].ACM Transac-tions on Computer Systems,1998,16(2):133-169.
[12]ONGARO D,OUSTERHOUT J.In search of an understandable consensus algorithm[C]//2014 USENIX Annual Technical Conference(USENIX ATC 14).2014:305-319.
[13]LIN L S,ZHENG H Q,SU S,et al.An On-Chain SecurityMechanism Against DeFi Price Manipulation Attacks[J].Journal of Computer Research and Development,2025,62(2):443-457.
[14]DAMAŠEVIČIUS R,MISRA S,MASKELIŪNAS R,et al.Convergence of blockchain and Internet of Things:integration,security,and use cases[J].Frontiers of Information Technology & Electronic Engineering,2024,25(10):1295-1321.
[15]SHEN M,CHE Z,ZHU L H,Anonymity in Blockchain Digital Currency Transactions:Protection And Confrontation[J].Chinese Journal of Computers,2023,46(1):125-146.
[16]LI J ,YUAN Y,WANG F Y.Blockchain-based Digital Currency:The State of the Art and Future Trends[J].Acta Automatica Sinica,2021,47(4):715-729.
[17]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.
[18]LIU Y Z,LIU J W,ZHANG Z Y,et al.Overview on Blockchain Consensus Mechanisms[J].Journal of Cryptology,2019,6(4):395-432.
[19]FU X,WANG H,SHI P.A survey of Blockchain consensus algorithms:mechanism,design and applications[J].Science China Information Sciences,2021,64:1-15.
[20]GAO Z F,ZHENG J L,TANG S Y,et al.State-of-the-art Survey of Consensus Mechanisms on DAG-based Distributed Led-ger[J].Journal of Software,2019,31(4):1124-1142.
[21]WANG Q,YU J S,CHEN S P,et al.SoK:DAG-based blockchain systems[J].ACM Computing Surveys,2023,55(12):1-38.
[22]GĄGOL A,LES′NIAK D,STRASZAK D,et al.Aleph:Efficient atomic broadcast in asynchronous networks with byzantine nodes[C]//Proceedings of the 1st ACM Conference on Advances in Financial Technologies.2019:214-218.
[23]KEIDAR I,KOKORIS-KOGIAS E,NAOR O,et al.All youneed is dag[C]//Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing.2021:165-175.
[24]DANEZIS G,KOKORIS-KOGIAS L,SONNINO A,et al.Narwhal and tusk:a dag-based mempool and efficient bft consensus[C]//Proceedings of the Seventeenth European Conference on Computer Systems.2022:34-50.
[25]SPIEGELMAN,A,NEIL G,ALBERTO S et al.Bullshark:Dag bft protocols made practical[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security.2022:2705-2718.
[26]MALKHI D,STATHAKOPOULOU D,YIN M F.BBCA-CHAIN:One-Message,Low Latency BFT Consensus on a DAG [J].arXiv:2310.06335,2023.
[27]SHRESTHA N,SHROTHRIUM R,KATE A,et al.Sailfish:Towards Improving Latency of DAG-based BFT[C]//2025 IEEE Symposium on Security and Privacy(SP).IEEE,2025:1928-1946.
[28]FENG B M,WANG S X,ZHANG J Q.Progress in Cryptoeconomics Research[J].Economic Perspective,2023(11):125-140.
[29]YUAN X Z.Consensus game and consensus equilibrium inblockchain ecology[J].Operations Research Transactions,2024,28(3):1-26.
[30]XIA Q,DOU W S,GUO K W,et al.Survey on Blockchain Consensus Protocol[J].Journal of Software,2021,32(2):277-299.
[31]YUAN Y,NI X C,ZENG S.Blockchain Consensus Algorithms:The State of the Art and Future Trends[J].Acta Automatica Sinica,2018,44(11):2011-2022.
[32]LAMPORT L.The part-time parliament[J].ACM Transactions on Computer Systems,1998,16(2):133-169.
[33]YI X C,WEI H F,HUANG Y,et al.TPaxos Consensus Protocol in PaxosStore:Derivation,Specification,and Refinement[J].Journal of Software,2020,31(8):2336-2361.
[34]BURROWS M.The Chubby lock service for loosely-coupled distributed systems[C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation.USENIX Association,2006:335-350.
[35]ONGARO D,OUSTERHOUT J.In search of an understandable consensus algorithm[C]//Proceedings of the 2014 USENIX Annual Technical Conference.2014:305-319.
[36]GE N,HE Y K,ZHAI S M,et al.Formal Verification of Consensus Protocols:Survey and Perspective[J].Journal of Software,2022,34(11):4989-5007.
[37]WANG D,DOU W S,GAO Y,et al.Raft Protocol TestingBased on TLA+ Formal Specification[J].Journal of Software,2024,35(12):5363-5381.
[38]HAN S C,ZHU X R,ZHANG X X.Optimized scalable Byzantine fault tolerance algorithm[J].Chinese Journal on Internet of Things,2020,4(2):18-25.
[39]ZHANG X,ZHONG W,YANG C,et al,BFT Consensus Algorithms[C]//2023 IEEE 10th International Conference on Cyber Security and Cloud Computing.2023:434-439.
[40]XU J,WANG C,JIA X.A survey of blockchain consensus protocols[J].ACM Computing Surveys,2023,55(13):1-35.
[41]DWORK C,NAOR M.Pricing via processing or combatting junk mail[C]//Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology.1992:139-147.
[42]BACK A.Hashcash－a denial of service counter-measure[EB/OL].http://www.hashcash.org/papers/hashcash.pdf.
[43]JAKOBSSON M,JUELS A.Proofs of work and bread pudding protocols[C]//Secure Information Networks.1999:258-272.
[44]YI L,LU X Y,TANG K,et al.Overview on consensus algo-rithms of blockchain [J].Electronic Design Engineering,2024,32(6):161-170.
[45]WU Y,LI J X.Evolution process of blockchain consensus algorithm[J].Application Research of Computers,2020,37(7):2097-2103.
[46]MECHANIC Q,Proof of stake[EB/OL].https://en.bitcoin.it/wiki/ Proof of Stake.
[47]KING S,NADAL S M.PPcoin:Peer-to-peer crypto-currency with proof-of-stake [EB/OL].https://www.semanticscholar.org/paper/PPCoin%3A-Peer-to-Peer-Crypto-Currency-with-King-Nadal/0db38d32069f3341d34c35085dc009a85ba13c13.
[48]NXT Generation of Cryptocurrency.NXT whitepaper[EB/OL].[2024-03-27].https://nxtdocs.jelurida.com/Nxt_Whitepaper.
[49]QIN B,QIAO X.Development and Security of Blockchain Consensus Mechanism[J].ZTE Technology Journal,2018,24(6):8-12.
[50]ZHU J M,ZHANG Q N,GAO S.Research Progress of Blockchain Key Technologies and Their Application[J].Journal of Taiyuan University of Technology,2020,51(3):321-330.
[51]DUONG T,FAN L,ZHOU H S.2-hop blockchain:combining proof-of-work and proof-of-stake securely [EB/OL].(2023-09-30).https://eprint.iacr.org/2016/716.
[52]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.
[53]BUTERIN V,REIJSBERGEN D,LEONARDOS S,et al.Incentives in Ethereum's hybrid casper protocol[C]//2019 IEEE International Conference on Blockchain and Cryptocurrency.2019:236-244.
[54]FU X,WANG H M,SHI P C,et al.Jointgraph:A DAG-based efficient consensus algorithm for consortium blockchains[J].Software:Practice and Experience,2021,51(10):1987-1999.
[55]CASTRO M,LISKOV B.Practical Byzantine fault tolerance[C]//Proceedings of the 3rd Symposium on Operating Systems Design and Implementation.1999:173-186.
[56]YANG,J,JIA Z H,SU R G,et al.Improved fault-tolerant consensus based on the PBFT algorithm[C]//IEEE Access,2022,10:30274-30283.
[57]FANG W W,WANG Z Y,SONG H L,et al.An optimizedPBFT consensus algorithm for blockchain[J].Journal of Beijing Jiaotong University,2019,43(5):58-64.
[58]ZHANG Z W,WANG G R,XU J L,et al.Survey on Data Ma-nagement in Blockchain Systems[J].Journal of Software,2020,31(9):2903-2925.
[59]BESSANI A,SOUSA J,ALCHIERI E E P.State machine replication for the masses with BFT-SMART[C]//2014 44th An-nual IEEE/IFIP International Conference on Dependable Systems and Networks.IEEE,2014:355-362.
[60]ZHANG G,JACOBSEN H A.Prosecutor:An efficient BFTconsensus algorithm with behavior-aware penalization against Byzantine attacks[C]//Proceedings of the 22nd International Middleware Conference.2021:52-63.
[61]GUETA G G,ABRAHAM I,GROSSMAN S,et al.SBFT:A scalable and decentralized trust infrastructure[C]//2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks(DSN).IEEE,2019:568-580.
[62]KOTLA R,ALVISI L,DAHLIN M,et al.Zyzzyva:speculative byzantine fault tolerance[C]//Proceedings of twenty-first ACM SIGOPS Symposium on Operating Systems Principles.2007:45-58.
[63]CHENG A D,XIE S J,LIU A,et al.Efficient Quantum-secure Byzantine Fault Tolerance Consensus Mechanism Based on HotStuff[J].Computer Science,2024,51(8):429-439.
[64]YIN M,MALKHI D,REITER M K,et al.HotStuff:BFT consensus with linearity and responsiveness [C]//Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing.2019:347-356.
[65]GARAY J,KIAYIAS A,LEONARDOS N.The bitcoin back-bone protocol:Analysis and applications[J].Journal of the ACM,2024,71(4):1-49.
[66]DENG X H,WANG Z Q,LI K T,et al.ACT-BFT:Byzantine Fault Tolerant Consensus Mechanism Based on Adaptive Communication Topology[J].Journal of Computer Engineering & Applications,2023,59(21):267.
[67]ZHANG G R,PAN F,MAO Y H,et al.Reaching consensus in the byzantine empire:A comprehensive review of bft consensus algorithms[J].ACM Computing Surveys,2024,56(5):1-41.
[68]BAUDET M,CHING A,CHURSIN A,et al.State machine replication in the libra blockchain[C]//Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation.2020:633-649
[69]ZHANG G,JACOBSEN H A.Prosecutor:An efficient BFTconsensus algorithm with behavior-aware penalization against Byzantine attacks[C]//Proceedings of the 22nd International Middleware Conference.2021:52-63.
[70]SUN Z X,ZHANG X,XIANG F,et al.Survey of Storage Scalability on Blockchain[J].Journal of Software,2020,32(1):1-20.
[71]SHI J,ZHANG A,BAI X Y,et al.Survey on Performance Optimization Technologies of Distributed Ledger System[J].Journal of Software,2022,34(10):4607-4635.
[72]LERNER S D.DagCoin:A cryptocurrency without blocks [EB/OL].(2024-03-11).https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf.
[73]POPOV S.The Tangle [EB/OL].(2018-04-30) [2024-04-25].https://assets.ctfassets.net/r1dr6vzfxhev/2t4uxvsIqk0EUau6g2sw0g/45eae33637ca92f85dd9f4a3a218e1ec/iota1_4_3.pdf.
[74]CHURYUMOV A.Byteball:A decentralized system for storage and transfer of value [EB/OL].[2024-09-30].https://byteball.org/Byteball.pdf.
[75]BAIRD L.The swirlds hashgraph consensus algorithm:Fair,fast,byzantine fault tolerance:Swirlds Tech Reports:SWIRLDS-TR-2016-01[R].2016:9-11.
[76]ZHAO G S,ZHANG H,WANG J.A Mobile Crowdsensing Data Security Delivery ModelBased on Tangle Network[J].Journal of Electronics & Information Technology,2020,42(4):965-971.
[77]DONG Z,ZHENG E,CHOON Y,et al.Dagbench:A performance evaluation framework for dag distributed ledgers[C]//2019 IEEE 12th International Conference on Cloud Computing(CLOUD).IEEE,2019:264-271.
[78]LU X F,JIANG C,WANG P.A Survey on Consensus Algorithms of Blockchain Based on DAG[C]//Proceedings of the 2024 6th Blockchain and Internet of Things Conference(BIOTC'24).2024:50.
[79]ZHANG,Y Q,LEI G,KE W.A high-throughput DAG-based blockchain protocol[C]//Third International Conference on Signal Image Processing and Communication.2023:533-540.
[80]MALKHI D,SZALACHOWSKI P.Maximal extractable value protection on a dag[J].arXiv:2208.00940,2022.
[81]SPIEGELMAN A,ARUN B,GELASHVILI R,et al.Shoal:Improving dag-bft latency and robustness [EB/OL].(2023-06-05) [2024-07-24]. https://arxiv.org/abs/2306.03058.
[82]MILLER A,XIA Y,CROMAN K,et al.The honey badger of BFT protocols[C]//Proceedings of the 2016ACM SIGSAC Conference on Computer and Communications Security.2016:31-42.
[83]ARUN B,LI Z,SURI-PAYER F,et al.Shoal++:HighThroughput DAG BFT Can Be Fast! [J].arXiv:2405.20488,2024.
[84]SPIEGELMAN A,GIRIDHARAN N,SONNINO A,et al.Bullshark:the partially synchronous version[J].arXiv:2209.05633,2022.
[85]BUCHMAN E.Tendermint:Byzantine fault tolerance in the age of blockchains[D].Guelph:University of Guelph,2016.
[86]LIU F Y,ZHANG J F.Multiple-index Comprehensive Regression Scoring[J].Journal of Applied Statistics and Management,2014,33(3):408-415.
[87]YU X F,FU D.Multiple-index comprehensive evaluation methods[J].Statistics and Decision,2004(11):119-121.
[88]TAN P L,WANG R S,ZENG W H.Overview of BlockchainConsensus Algorithms[J].Computer Science,2023,50(S1):691-702.
[89]LIU Q Y,WU X N,Review on the Weighting Methods of Indexes in the Multi-Factor Evaluation[J].Knowledge Management Forum,2017,2(6):500-510.
[90]CHEN F,YANG J H,YANG Y,et al.A Study on Network Service Behavior Verification with Process Algebra and Its Application[J].Chinese Journal of Computers,2011,34(9):1660-1668.
[91]MEREDITH L G,RADESTOCK M.A reflective higher-order calculus[J].Electronic Notes in Theoretical Computer Science,2005,141(5):49-67.
[92]MILNER R.Communicating and mobile systems:the pi calculus[M].Cambridge:Cambridge University Press,1999.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed