Improved Consensus Algorithm Based on HotStuff and Multi-Ary Trees

doi:10.3969/j.issn.1671-1122.2025.09.012

Abstract

Abstract:

This paper presented an improved consensus algorithm based on HotStuff and multi-ary trees to address the issues of high communication complexity, poor scalability, and leader censorship in Byzantine fault-tolerant consensus protocols for blockchain. This algorithm introduced BLS signature into the signature mechanism to achieve aggregation verification, significantly reducing message overhead. Using multi-ary trees structure to achieve load balancing and improved the parallelism of block processing. By optimizing the voting and submission stages through pipeline technology, consensus latency had been reduced, and adopted an active leadership rotation strategy to address the system performance degradation caused by malicious or inefficient leaders. The results show that with a total of 100 system nodes, this algorithm consensus algorithm achieves a throughput five times higher than the traditional HotStuff consensus algorithm. Moreover, when round-trip time increases from 50ms to 400ms, throughput only decreases by 9% and still maintained high stability. Meanwhile, in various network environments, this algorithm exhibits lower transaction confirmation latency. Therefore, this algorithm has significant advantages in reducing communication complexity, enhancing fault tolerance, and improving performance, providing reference for the design and application of high-performance blockchain systems.

Key words: blockchain, consensus algorithm, HotStuff, multi-ary trees

CLC Number:

TP309

YANG Jianxin, WANG Xiaoding, LIN Hui. Improved Consensus Algorithm Based on HotStuff and Multi-Ary Trees[J]. Netinfo Security, 2025, 25(9): 1447-1455.

Figures/Tables 7

References 18

[1]	CACHIN C. Architecture of the Hyperledger Blockchain Fabric[EB/OL]. (2016-06-23)[2024-06-10]. https://docslib.org/doc/9496711/architecture-of-the-hyperledger-blockchain-fabric.
[2]	BROWN R G. The Corda Platform: An Introduction[EB/OL]. (2018-05-10)[2024-06-10]. https://www.semanticscholar.org/paper/The-Corda-Platform-%3A-An-Introduction/8f0bb6825f4af8a708187959d62cadd6b6e424f2.
[3]	CASTRO M, LISKOV B. Practical Byzantine Fault Tolerance[C]// ACM. The Third Symposium on Operating Systems Design and Implementation (OSDI’99). New York: ACM, 1999: 173-186.
[4]	BESSANI A, SOUSA J, ALCHIERI E E P. State Machine Replication for the Masses with BFT-SMART[C]// IEEE. 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. New York: IEEE, 2014: 355-362.
[5]	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.
[6]	KOGIAS E K, JOVANOVIC P, GAILLY N, et al. Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing[C]// USENIX. 25th USENIX Security Symposium (USENIX Security 16). Berkley: USENIX, 2016: 279-296.
[7]	LUU L, NARAYANAN V, ZHENG Chaodong, et al. A Secure Sharding Protocol for Open Blockchains[C]// ACM. The 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 17-30.
[8]	KOKORIS-KOGIAS E, JOVANOVIC P, GASSER L, et al. OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding[C]// IEEE. 2018 IEEE Symposium on Security and Privacy. New York: IEEE, 2018: 583-598.
[9]	BONEH D, LYNN B, SHACHAM H. Short Signatures from the Weil Pairing[C]// Springer. 2001 Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2001: 514-532.
[10]	JALALZAI M M, NIU Jianyu, FENG Chen, et al. Fast-HotStuff: A Fast and Resilient HotStuff Protocol[EB/OL]. (2023-08-25)[2024-06-10]. https://doi.org/10.1109/TDSC.2023.3308848.
[11]	CHANDRA T D, TOUEG S. Unreliable Failure Detectors for Asynchronous Systems (Preliminary Version)[C]// ACM. The Tenth Annual ACM Symposium on Principles of Distributed Computing (PODC’91). New York: ACM, 1991: 325-340.
[12]	GELASHVILI R, KOKORIS-KOGIAS L, SONNINO A, et al. Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback[C]// Springer. The 26th Financial Cryptography and Data Security. Heidelberg: Springer, 2022: 296-315.
[13]	LI Qinan, XUE Zhihao, ZHANG Xuejun. Improved Fast-HotStuff Blockchian Consensus Algorithm[J]. Computer Engineering, 2021, 47(8): 14-21. doi: 10.19678/j.issn.1000-3428.0060847
	李启南, 薛志浩, 张学军. 改进Fast-HotStuff区块链共识算法[J]. 计算机工程, 2021, 47(8): 14-21. doi: 10.19678/j.issn.1000-3428.0060847
[14]	SUI Xiao, DUAN Sisi, ZHANG Haibin. Marlin: Two-Phase BFT with Linearity[C]// IEEE. 2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). New York: IEEE, 2022: 54-66.
[15]	BROWN D R L. Sec2:Recommended Elliptic Curve Domain Parameters[EB/OL]. (2010-01-27)[2024-06-10]. https://www.secg.org/sec2-v2.pdf.
[16]	LIU Jintao, SHEN Limin. TRBFT Consensus Algorithm Based on Threshold Signature and Reputation Grouping[J]. Journal of Nanjing Normal University (Engineering and Technology Edition), 2023, 23(4): 10-18.
	刘金涛, 沈丽敏. 基于门限签名及信誉分组的TRBFT共识算法[J]. 南京师范大学学报(工程技术版), 2023, 23(4): 10-18.
[17]	SYTA E, TAMAS I, VISHER D, et al. Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning[C]// IEEE. 2016 IEEE Symposium on Security and Privacy. New York: IEEE, 2016: 526-545.
[18]	AJTAI M. The Complexity of the Pigeonhole Principle[J]. Combinatorica, 1994, 14(4): 417-433.