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

doi:10.11896/jsjkx.210700011

Abstract

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

CLC Number:

TP311

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.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Research Advance on BFT Consensus Algorithms

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0

[1]	LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[2]	WANG Zi-kai, ZHU Jian, ZHANG Bo-jun, HU Kai. Research and Implementation of Parallel Method in Blockchain and Smart Contract [J]. Computer Science, 2022, 49(9): 312-317.
[3]	WANG Can, LIU Yong-jian, XIE Qing, MA Yan-chun. Anchor Free Object Detection Algorithm Based on Soft Label and Sample Weight Optimization [J]. Computer Science, 2022, 49(8): 157-164.
[4]	CHEN Jun, HE Qing, LI Shou-yu. Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor [J]. Computer Science, 2022, 49(8): 237-246.
[5]	LI Qi-ye, XING Hong-jie. KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion [J]. Computer Science, 2022, 49(8): 267-272.
[6]	WANG Bing, WU Hong-liang, NIU Xin-zheng. Robot Path Planning Based on Improved Potential Field Method [J]. Computer Science, 2022, 49(7): 196-203.
[7]	TANG Feng, FENG Xiang, YU Hui-qun. Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation [J]. Computer Science, 2022, 49(7): 254-262.
[8]	ZHAO Dong-mei, WU Ya-xing, ZHANG Hong-bin. Network Security Situation Prediction Based on IPSO-BiLSTM [J]. Computer Science, 2022, 49(7): 357-362.
[9]	LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Clustered Federated Learning Methods Based on DBSCAN Clustering [J]. Computer Science, 2022, 49(6A): 232-237.
[10]	CHEN Jun-wu, YU Hua-shan. Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs [J]. Computer Science, 2022, 49(6A): 594-600.
[11]	LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[12]	FAN Xing-ze, YU Mei. Coverage Optimization of WSN Based on Improved Grey Wolf Optimizer [J]. Computer Science, 2022, 49(6A): 628-631.
[13]	ZHU Xu-hui, SHEN Guo-jiao, XIA Ping-fan, NI Zhi-wei. Model Based on Spirally Evolution Glowworm Swarm Optimization and Back Propagation Neural Network and Its Application in PPP Financing Risk Prediction [J]. Computer Science, 2022, 49(6A): 667-674.
[14]	WANG Xian-fang, ZHANG Liang, ZHANG Ning. Evolutionary Game Analysis of WeChat Health Information Quality Optimization Based on Prospect Theory [J]. Computer Science, 2022, 49(6A): 694-704.
[15]	LI Bo, XIANG Hai-yun, ZHANG Yu-xiang, LIAO Hao-de. Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios [J]. Computer Science, 2022, 49(6A): 723-728.