区块链BFT共识算法研究进展

doi:10.11896/jsjkx.210700011

摘要/Abstract

摘要： 自2008年比特币问世后,区块链逐渐成为学术界的研究热点,共识算法作为区块链的关键技术,受到了越来越多研究者的重视。由于区块链运行环境复杂多变,容易在系统中引入拜占庭节点,因此区块链拜占庭容错共识算法是必须要攻克的难关。文中系统地总结了区块链拜占庭容错共识算法的研究进展,以期为未来共识算法的创新提供参考。首先,梳理了现有的区块链拜占庭容错共识算法的四大派别,引出了BFT共识算法;其次,回顾了经典BFT共识算法PBFT中的几个重要临界值及其正确性证明;再次,提出了BFT共识算法具有去中心化、效能、安全性和容错率ntg 四大优化目标;然后,基于共识轮次、共识节点个数、底层硬件、通信模式或加密算法、出错概率等维度,归纳出BFT共识算法的5种优化思路;最后,对10种经典BFT共识算法进行了详细分析与性能对比。

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

Abstract: Since the advent of Bitcoin in 2008, blockchain has gradually become a research hotspot in academia.As the key technology of blockchain, consensus algorithm has also attracted more attention from researchers.It's easy to introduce Byzantine fault nodes in blockchain system because of its complex and variable runtime, so the blockchain Byzantine fault tolerant consensus algorithm is a difficulty that must be overcome.This paper systematically summarizes the research progress of the blockchain Byzantine fault tolerant consensus algorithm, in order to provide a reference for the innovation of consensus algorithms in the future.Firstly, sorting out the four major factions of the existing blockchain Byzantine fault tolerant consensus algorithms and introducing the BFT consensus algorithm.Secondly, reviewing several important values in the classic PBFT algorithm and its correctness proof.Thirdly, putting forward the four optimization goals of the BFT consensus algorithm:decentralization, efficiency, fault tolerance rate and security.Then, based on the dimensions of consensus rounds, number of consensus nodes, underlying hardware, communication mode or encryption algorithm, probability of fault nodes, five optimization ideas of BFT consensus algorithm are summarized.Finally, analysising 10 classic BFT consensus algorithms in detail and making performance comparison.

Key words: BFT, Blockchain, Byzantine fault tolerant, Consensus algorithm, Distributed system, Optimization, PBFT

中图分类号:

TP311

冯了了, 丁滟, 刘坤林, 马科林, 常俊胜. 区块链BFT共识算法研究进展[J]. 计算机科学, 2022, 49(4): 329-339. https://doi.org/10.11896/jsjkx.210700011

FENG Liao-liao, DING Yan, LIU Kun-lin, MA Ke-lin, CHANG Jun-sheng. Research Advance on BFT Consensus Algorithms[J]. Computer Science, 2022, 49(4): 329-339. https://doi.org/10.11896/jsjkx.210700011

参考文献

[1] OKI B M,LISKOV B H.Viewstamped replication:A new primary copy method to support highly-available distributed systems[C]//Proceedings of the Seventh Annual ACM Symposium on Principles of distributed Computing.1988:8-17.
[2] LAMPORT L.Paxos made simple[J].ACM Sigact News,2001,32(4):18-25.
[3] PEASE M,SHOSTAK R,LAMPORT L.Reaching agreement in the presence of faults[J].Journal of the ACM (JACM),1980,27(2):228-234.
[4] CASTRO M,LISKOV B.Practical byzantine fault tolerance[C]//OSDI.1999,99(1999):173-186.
[5] KWON J.Tendermint:consensus without mining[EB/OL].(2021-11-04) [2022-2-11].https://tendermint.com/static/docs/tendermint.pdf.
[6] COPELAND C,ZHONG H.Tangaroa:a byzantine fault tolerant raft[EB/OL].(2014-12-15) [2021-05-30].https://www.scs.stanford.edu/14au-cs244b/labs/projects/copeland_zhong.pdf.
[7] MARTINO W.The first scalable,high performance privateblockchain[EB/OL](2017-04-20)[2022-02-11]https://blockchainlab.com/pdf/Kadena-ConsensusWhitePaper-Aug2016.pdf.
[8] NAKAMOTO S.Bitcoin:A peer-to-peer electronic cash system[EB/OL].https://www.debr.io/article/21260.pdf.
[9] KIAYIAS A,RUSSELL A,DAVID B,et al.Ouroboros:A pro-vably secure proof-of-stake blockchain protocol[C]// Annual International Cryptology Conference.Cham:Springer,2017:357-388.
[10] ZHONG Z S.An Improvement on Blockchain-Based PoS Consensus Algorithm[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2021,38(4):36-41.
[11] ATENIESE G,BONACINA I,FAONIO A,et al.Proofs ofspace:When space is of the essence[C]//International Confe-rence on Security and Cryptography for Networks.Cham:Springer,2014:538-557.
[12] BALL M,ROSEN A,SABIN M,et al.Proofs of Useful Work[EB/OL].(2021-02-27) [2021-05-30].https://eprint.iacr.org/2017/203.pdf.
[13] YUAN Y,NI X,ZENG S,et al.Blockchain consensus algo-rithms:the state of the art and future trends[J].Acta Automa-tica Sinica,2018,44(11):2011-2022.
[14] SCHWARTZ D,YOUNGS N,BRITTO A.The Ripple Protocol Consensus Algorithm[EB/OL].https://ripple.com/files/ripple_consensus_whitepaper.pdf.
[15] MAZIERES D.The stellar consensus protocol:A federatedmodel for internet-level consensus[J].Stellar Development Foundation,2015,32:1-45.
[16] CHURYUMOV A.Byteball:A decentralized system for storage and transfer of value [EB/OL].https://byteball.org/Byteball.pdf.
[17] ROCKET T.Snowflake to avalanche:A novel metastable con-sensus protocol family for cryptocurrencies [EB/OL].http://knowen-production.s3.amazonaws.com/uploads/attachment/file/1922/Snowflake%2Bto%2BAvalanche%2B-%2BA%2BNovel%2BMetastable%2BConsensus%2BProtocol%2BFamily.pdf.
[18] CHEN J W,XIAN X B,YANG Z G,et al.Improving the practical Byzantine fault-tolerant consensus algorithm with BLS aggregate signature[J/OL].https://doi.org/10.19734/j.issn.1001-3695.2020.12.0403.
[19] POPOV S.The tangle[EB/OL].http://www.descryptions.com/Iota.pdf.
[20] LI C,LI P,ZHOU D,et al.Scaling nakamoto consensus to thousands of transactions per second[EB/OL].https://arxiv.org/pdf/1805.03870.pdf.
[21] HOPKINS A L,LALA J H,SMITH T,et al.The evolution of fault tolerant computing at the Charles Stark Draper Laboratory,1955-85[M]//The Evolution of Fault-Tolerant Computing.Vienna:Springer,1987:121-140.
[22] DRISCOLL K,PAPADOPOULIS G,NELSON S,et al.Multi-microprocessor flight control system[C]//Proceedings of the IEEE/AIAA 5th Digital Avionics Systems Conference,Institute of Electrical and Electronic Engineers.New York,NY.1983:11.
[23] WENSLEY J H,LAMPORT L,GOLDBERG J,et al.SIFT:Design and analysis of a fault-tolerant computer for aircraft control[J].Proceedings of the IEEE,1978,66(10):1240-1255.
[24] FU X,WANG H,SHI P.A survey of Blockchain consensus algorithms:mechanism,design and applications[J].Science China Information Sciences,2021,64(2):1-15.
[25] WANG Q,YU J,PENG Z,et al.Security Analysis on dBFTprotocol of NEO[C]//International Conference on Financial Cryptography and Data Security.Cham:Springer,2020:20-31.
[26] LUU L,NARAYANAN V,ZHENG C,et al.A secure sharding protocol for open blockchains[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.2016:17-30.
[27] KOKORIS-KOGIAS E,JOVANOVIC P,GASSER L,et al.Omniledger:A secure,scale-out,decentralized ledger via sharding[C]//2018 IEEE Symposium on Security and Privacy (SP).IEEE,2018:583-598.
[28] MILLER A,JUELS A,SHI E,et al.Permacoin:Repurposingbitcoin work for data preservation[C]//2014 IEEE Symposium on Security and Privacy.IEEE,2014:475-490.
[29] PARK S,PIETRZAK K,ALWEN J,et al.Spacemint:A cryptocurrency based on proofs of space[C]//International Confe-rence on Financial Cryptography and Data Security.Berlin:Springer,2018:480-499.
[30] XIANG F,HUAIMIN W,PEICHANG S.Proof of previoustransactions (PoPT):An efficient approach to consensus for JCLedger[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2019,51(4):2415-2424.
[31] WANG H Y,GUO K X,PAN Q Q.Byzantine fault-tolerant consensus algorithm based on voting mechanism[J].Journal of Computer Application,2019,39(6):1766-1771.
[32] HANKE T,MOVAHEDI M,WILLIAMS D.Dfinity technology overview series,consensus system[J].arXiv:1805.04548,2018.
[33] THE ONTOLOGY TEAM.Ontology Launches VBFT,a Next-Generation Consensus Mechanism,Becoming one of the First VRF-Based Public Chains[EB/OL].https://medium.com/on-tologynetwork/ontology-launches-vbft-a-next-generation-con-sensus-mechanism-becoming-one-of-the-first-vrf-based-91f782308db4.
[34] GILAD Y,HEMO R,MICALI S,et al.Algorand:Scaling byzantine agreements for cryptocurrencies[C]//Proceedings of the 26th Symposium on Operating Systems Principles.2017:51-68.
[35] SUN H F,ZHANG W F,WANG X M.Byzantine fault-tolerant consensus algorithm for anti-adaptive attack based on threshold and ring signature[J/OL].Acta Automatica Sinica[2021-05-30].https://kns.cnki.net/kcms/detail/11.2109.TP.20210308.1350.001.html.
[36] GUETA G G,ABRAHAM I,GROSSMAN S,et al.Sbft:a sca-lable and decentralized trust infrastructure[C]//2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN).IEEE,2019:568-580.
[37] YIN M,MALKHI D,REITER M K,et al.Hotstuff:Bft consen-sus with linearity and responsiveness[C]//Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing.2019:347-356.
[38] JALALZAI M M,NIU J,FENG C,et al.Fast-Hotstuff:a fast and resilient hotstuff protocol[EB/OL].(2021-10-04) [2022-02-11].https://arxiv.org/pdf/2010.11454.pdf.
[39] LI Q,XUE Z,ZHANG X.Improved Fast-HotStuff BlockchianConsensus Algorithm[J].Computer Engineering,2021,47(8):14-21.
[40] ZHANG S J,CAI J,CHEN Z H,et al.Byzantine consensus algorithm based on Gossip protocol[J].Computer Science,2018,45(2):20-24.
[41] ZHANG Q W,WANG Z Q,ZHANG Y Q.Research on trustcollection consensus algorithm based on Gossip protocol[J].Computer Science,2020,47(S1):391-394.
[42] CHUN B G,MANIATIS P,SHENKER S,et al.Attested append-only memory:Making adversaries stick to their word[J].ACM SIGOPS Operating Systems Review,2007,41(6):189-204.
[43] VERONESE G S,CORREIA M,BESSANI A N,et al.Efficient byzantine fault-tolerance[J].IEEE Transactions on Computers,2011,62(1):16-30.
[44] KAPITZA R,BEHL J,CACHIN C,et al.CheapBFT:Resource-efficient Byzantine fault tolerance[C]//Proceedings of the 7th ACM European Conference on Computer Systems.2012:295-308.
[45] LIU J,LI W,KARAME G O,et al.Scalable byzantine consensus via hardware-assisted secret sharing[J].IEEE Transactions on Computers,2018,68(1):139-151.
[46] 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.
[47] DISTLER T,CACHIN C,KAPITZA R.Resource-efficient By-zantine fault tolerance[J].IEEE Transactions on Computers,2015,65(9):2807-2819.
[48] WANG R H,ZHANG L F,XU Q Q,et al.Byzantine fault-tole-rant consensus algorithm that can be applied to the alliance chain[J].Application Research of Computers,2020,37(11):3382-3386.
[49] TIM F.Ethereum’s Casper protocol explained in simple terms[EB/OL].https://www.finder.com/ethereum-casper.
[50] DAVID B,GAŽI P,KIAYIAS A,et al.Ouroboros praos:Anadaptively-secure,semi-synchronous proof-of-stake blockchain[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Cham:Springer,2018:66-98.
[51] GOODMAN L M.Tezos:A self-amending crypto-ledger position paper[EB/OL].(2014-08-03) [2021-05-30].https://icohoo.com/pdf/position_paper.pdf.
[52] MILLER A,XIA Y,CROMAN K,et al.The honey badger of BFT protocols[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.2016:31-42.
[53] HUANG D Y,LI L,CHEN B,et al.RBFT:Byzantine fault-to-lerant consensus mechanism based on Raft cluster[J].Journal of Communications,2021,42(3):209-219.
[54] CHEN Z H,LI Q.Improved PBFT consensus mechanism based on K-medoids[J].Computer Science,2019,46(12):101-107.

相关文章 15

[1]	鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于分层抽样优化的面向异构客户端的联邦学习 Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients 计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263
[2]	王子凯, 朱健, 张伯钧, 胡凯. 区块链与智能合约并行方法研究与实现 Research and Implementation of Parallel Method in Blockchain and Smart Contract 计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[3]	王灿, 刘永坚, 解庆, 马艳春. 基于软标签和样本权重优化的Anchor Free目标检测算法 Anchor Free Object Detection Algorithm Based on Soft Label and Sample Weight Optimization 计算机科学, 2022, 49(8): 157-164. https://doi.org/10.11896/jsjkx.210600240
[4]	陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[5]	李其烨, 邢红杰. 基于最大相关熵的KPCA异常检测方法 KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion 计算机科学, 2022, 49(8): 267-272. https://doi.org/10.11896/jsjkx.210700175
[6]	王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[7]	唐枫, 冯翔, 虞慧群. 基于自适应知识迁移与资源分配的多任务协同优化算法 Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation 计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184
[8]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[9]	赵冬梅, 吴亚星, 张红斌. 基于IPSO-BiLSTM的网络安全态势预测 Network Security Situation Prediction Based on IPSO-BiLSTM 计算机科学, 2022, 49(7): 357-362. https://doi.org/10.11896/jsjkx.210900103
[10]	鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于DBSCAN聚类的集群联邦学习方法 Clustered Federated Learning Methods Based on DBSCAN Clustering 计算机科学, 2022, 49(6A): 232-237. https://doi.org/10.11896/jsjkx.211100059
[11]	傅丽玉, 陆歌皓, 吴义明, 罗娅玲. 区块链技术的研究及其发展综述 Overview of Research and Development of Blockchain Technology 计算机科学, 2022, 49(6A): 447-461. https://doi.org/10.11896/jsjkx.210600214
[12]	高健博, 张家硕, 李青山, 陈钟. RegLang:一种面向监管的智能合约编程语言 RegLang:A Smart Contract Programming Language for Regulation 计算机科学, 2022, 49(6A): 462-468. https://doi.org/10.11896/jsjkx.210700016
[13]	毛典辉, 黄晖煜, 赵爽. 符合监管合规性的自动合成新闻检测方法研究 Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance 计算机科学, 2022, 49(6A): 523-530. https://doi.org/10.11896/jsjkx.210300083
[14]	周航, 姜河, 赵琰, 解相朋. 适用于各单元共识交易的电力区块链系统优化调度研究 Study on Optimal Scheduling of Power Blockchain System for Consensus Transaction ofEach Unit 计算机科学, 2022, 49(6A): 771-776. https://doi.org/10.11896/jsjkx.210600241
[15]	陆浩松, 胡勇华, 王书盈, 周新莲, 李慧祥. 向量DSP的混合资源启发式循环展开因子选择方法研究 Study on Hybrid Resource Heuristic Loop Unrolling Factor Selection Method Based on Vector DSP 计算机科学, 2022, 49(6A): 777-783. https://doi.org/10.11896/jsjkx.210400146

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed