The Multi-Leader Consensus Algorithm Based on Improvements to HotStuff

doi:10.3969/j.issn.1671-1122.2023.09.010

Abstract

Abstract:

In response to the performance bottleneck caused by Byzantine fault tolerant (BFT) class consensus algorithm in blockchain, a HotStuff-based on improved multi-principal node consensus algorithm was proposed, namely multi leader HotStuff (MLH) consensus algorithm. The algorithm introduced a coordination phase that was not on the critical path, and combined mechanisms such as intra-round collection of votes and cross-round block submission, so that multiple nodes became master nodes, allowing the algorithm to submit blocks in parallel and improving the computational efficiency of the algorithm. At the same time, the communication complexity within the partition was reduced by combining schemes such as threshold signatures and aggregated signatures, so that the algorithm maintained linear communication complexity after amortization in the case of consecutive view switching. Experimental results verifies that MLH algorithm has a better performance in terms of latency and throughput.

Key words: blockchain, consensus algorithm, HotStuff algorithm, multi-leader, throughput

CLC Number:

TP309

GONG Pengfei, XIE Sijiang, CHENG Andong. The Multi-Leader Consensus Algorithm Based on Improvements to HotStuff[J]. Netinfo Security, 2023, 23(9): 108-117.

Figures/Tables 9

References 27

[1]	LAMPORT L, SHOSTAK R, PEASE M. The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 2019, 4(3): 382-401. doi: 10.1145/357172.357176 URL
[2]	CASTRO M, LISKOV B. Practical Byzantine Fault Tolerance[C]// ACM. The Third Symposium on Operating Systems Design and Implementation. New York: ACM, 1999: 173-186.
[3]	BUCHMAN E, KWON J, MILOSEVIC Z. The Latest Gossip on BFT Consensus[EB/OL]. (2018-07-13)[2023-01-13]. https://arxiv.org/abs/1807.04938.
[4]	YIN Maofan, MALKHI D, REITER M K, et al. HotStuff: BFT Consensus with Linearity and Responsiveness[C]// ACM. The 2019 ACM Symposium on Principles of Distributed Computing. New York: ACM, 2019: 347-356.
[5]	CHAN B Y, SHI E. Streamlet: Textbook Streamlined Blockchains[C]// ACM. The 2nd ACM Conference on Advances in Financial Technologies. New York: ACM, 2020: 1-11.
[6]	JALALZAI M M, NIU Jianyu, FENG Chen, et al. Fast-Hotstuff: A Fast and Resilient Hotstuff Protocol[EB/OL]. (2020-10-22)[2023-01-13]. https://arxiv.org/abs/2010.11454.
[7]	GUETA G G, ABRAHAM I, GROSSMAN S, et al. SBFT: A Scalable and Decentralized Trust Infrastructure[C]// IEEE. 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). New York: IEEE, 2019: 568-580.
[8]	BUCHMAN E. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains[D]. Guelph: University of Guelph, 2016.
[9]	BUTERIN V, GRIFFITH V. Casper the Friendly Finality Gadget[EB/OL]. (2017-10-25)[2023-01-13]. https://arxiv.org/abs/1710.09437.
[10]	SHI E. Streamlined Blockchains: A Simple and Elegant Approach (A Tutorial and Survey)[C]// Springer. ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2019: 3-17.
[11]	ZHANG Baochen, KONG Lanju, LI Qingzhong, et al. EB-BFT: An Elastic Batched BFT Consensus Protocol in Blockchain[J]. Future Generation Computer Systems, 2023(139): 267-279.
[12]	LIU Yuan, AI Zhengpeng, TIAN Mengmeng, et al. DSBFT: A Delegation Based Scalable Byzantine False Tolerance Consensus Mechanism[C]// Springer. International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2020). Berlin: Springer, 2020: 426-440.
[13]	ABSPOEL M, ATTEMA T, RAMBAUD M. Malicious Security Comes for Free in Consensus with Leaders[C]// ACM. The 2021 ACM Symposium on Principles of Distributed Computing(PODC’21). New York: ACM, 2020: 195-198.
[14]	GELASHVILI R, KOKORIS-KOGIAS L, SONNINO A, et al. Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback[C]// Springer. Financial Cryptography and Data Security:26th International Conference. Berlin: Springer, 2022: 296-315.
[15]	GIRIDHARAN N, HOWARD H, ABRAHAM I, et al. No-Commit Proofs: Defeating Livelock in BFT[EB/OL]. (2021-09-28)[2023-01-13]. https://eprint.iacr.org/2021/1308.pdf.
[16]	ALQAHTANI S, DEMIRBAS M. Bottlenecks in Blockchain Consensus Protocols[C]// IEEE. 2021 IEEE International Conference on Omni-Layer Intelligent Systems (COINS). New York: IEEE, 2021: 1-8.
[17]	GAI Fangyu, FARAHBAKHSH A, NIU Jianyu, et al. Dissecting the Performance of Chained-BFT[C]// IEEE. 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). New York: IEEE, 2021: 595-606.
[18]	AILIJIANG A, CHARAPKO A, DEMIRBAS M. Dissecting the Performance of Strongly-Consistent Replication Protocols[C]// ACM. The 2019 International Conference on Management of Data. New York: ACM, 2019: 1696-1710.
[19]	YANG Yin. LinBFT: Linear-Communication Byzantine Fault Tolerance for Public Blockchains[EB/OL]. (2018-07-05)[2023-01-13]. https://arxiv.org/abs/1807.01829v1.
[20]	STATHAKOPOULOU C, DAVID T, VUKOLIC M. Mir-BFT: High-Throughput BFT for Blockchains[EB/OL]. (2019-06-13)[2023-01-13]. https://arxiv.org/abs/1906.05552.
[21]	AVARIKIOTI Z, HEIMBACH L, SCHMID R, et al. FnF-BFT: Exploring Performance Limits of BFT Protocols[EB/OL]. (2020-09-04)[2023-01-13]. https://arxiv.org/abs/2009.02235.
[22]	GUPTA S, HELLINGS J, SADOGHI M. RCC: Resilient Concurrent Consensus for High-Throughput Secure Transaction Processing[C]// IEEE. 2021 IEEE 37th International Conference on Data Engineering (ICDE). New York: IEEE, 2021: 1392-1403.
[23]	BARCELONA C S. Mencius: Building Efficient Replicated State Machines for WANs[C]// USENIX. 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08). Berlin: USENIX, 2008: 369-384.
[24]	BONEH D, LYNN B, SHACHAM H. Short Signatures from the Weil Pairing[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2001). Berlin: Springer, 2001: 514-532.
[25]	CACHIN C, SHOUP V. Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using[C]// ACM. The 19th ACM Symposium on Principles of Distributed Computing. New York: ACM, 2000: 1-26.
[26]	SHOUP V. Practical Threshold Signatures[C]// Springer. EUROCRYPT 2000:International Conference on the Theory and Application of Cryptographic Techniques Bruges. Berlin:Springer, 2000: 207-220.
[27]	KAKLAMANIS I, YANG Lei, ALIZADEH M. Coded Broadcast for Scalable Leader-Based BFT Consensus[C]// ACM. 2022 ACM SIGSAC Conference on Computer and Communications Security(CCS’22). New York: ACM, 2022: 3375-3377.

算法	通信复杂度	连续视图切换的通信复杂度
PBFT	$O({{n}^{2}})$	$O({{n}^{4}})$
Mir-BFT	$O({{n}^{2}})$	$O({{n}^{4}})$
Tendermint	$O({{n}^{2}})$	$O({{n}^{3}})$
HotStuff	$O(n)$	$O({{n}^{2}})$
MLH	$O(n)$	$O(n)$