基于BIRCH与Hash环的改进PBFT算法

An Improved PBFT Algorithm Based on BIRCH and Hash Ring

摘要

针对实用Byzantine容错共识算法在大规模分布式网络中存在的通信复杂度高、扩展性不足及主节点负载不均衡等问题,提出一种基于使用层次的平衡迭代规约和聚类算法与Hash环数据结构改进的实用Byzantine容错共识算法.该算法通过分布式优化平衡迭代规约和聚类算法,实现网络节点的动态聚类子组织划分,同时结合虚拟节点Hash环机制,解决了子组织内部的负载均衡与任务分配不均问题,并引入全局委员会机制以显著降低全网通信复杂度.实验结果表明:在网络节点规模为256时,该改进算法系统延迟仅为713.4ms,相较于传统实用Byzantine容错算法的系统延迟1895.4ms降低了62.4%,且其时延增长曲线斜率明显小于对比的两种主流改进共识算法;该算法在吞吐量、通信开销和资源占用等指标上均表现出显著优势,在较大规模分布式网络中展现了良好的扩展性和稳定性.该算法显著提升了分布式网络的共识效率,可有效满足互联网行业中复杂业务场景对高性能共识算法的需求,为大规模区块链系统的架构优化提供了重要的理论依据与技术支撑.

Abstract

Aiming at the problems of high communication complexity, poor scalability and unbalanced primary node load in the traditional practical Byzantine fault tolerance consensus algorithm in large-scale distributed networks. This paper proposes an improved practical Byzantine fault tolerance consensus algorithm based on balanced iterative reducing and clustering using hierarchies and hash ring data structure. The algorithm achieves dynamic clustering sub-organization division of network nodes through distributed optimization of the balanced iterative reducing and clustering using hierarchies algorithm. Meanwhile, combined with the virtual node hash ring mechanism, the problems of load balancing and uneven task assignment within sub-organizations are resolved, and a global committee mechanism is also introduced to significantly reduce the communication complexity of the entire network. Experimental results demonstrate that when the network node scale reaches 256, the system delay of the proposed algorithm is only 713.4 ms, which is 62.4% lower than the 1895.4 ms of the traditional practical Byzantine fault tolerance algorithm, and its delay growth curve slope is significantly smaller than those of two other mainstream improved consensus algorithms. The proposed algorithm also exhibits significant advantages in terms of throughput, communication overhead, and resource consumption, demonstrating good scalability and stability in large-scale distributed networks. This research significantly improves the consensus efficiency in distributed networks, effectively meets the requirements of complex business scenarios in the Internet industry for high-performance consensus algorithms, and provides important theoretical basis and technical support for the architecture optimization of large-scale blockchain systems.

关键词

互联网行业 / 区块链 / PBFT算法 / BIRCH算法 / Hash环机制

Key words

internet business / blockchain / PBFT algorithm / BIRCH algorithm / Hash ring mechanism

参考文献

[1] 王森, 李志淮, 贾志鹏. 主节点随机选取的改进PBFT共识算法[J]. 计算机应用与软件, 2022, 39(10):305-312.

[2] (Wang S, Li Z H, Jia Z P. Improved PBFT Consensus Algorithm with Random Primary Node Selection[J]. Computer Applications and Software, 2022, 39(10):305-312.)

[3] 鲍煦, 方宇, 林锋, 等. 基于区块链和HACCP的水产品溯源系统[J]. 江苏大学学报(自然科学版), 2024, 45(5):565-573.

[4] (Bao X, Fang Y, Lin F, et al. Aquatic Product Traceability System Based on Blockchain and HACCP[J]. Journal of Jiangsu University(Natural Science Edition), 2024, 45(5):565-573.)

[5] Zaghloul E, Li T T, Mutka M W, et al. Bitcoin and Blockchain:Security and Privacy[J]. IEEE Internet of Things Journal, 2020, 7(11):10210-10228.

[6] 李帅, 侯瑞春, 陶冶. 基于区块链的服务型制造供应链溯源技术研究[J]. 制造业自动化, 2023, 45(4):201-208.

[7] (Li S, Hou R C, Tao Y. Research on Traceability Technology of Service-Oriented Manufacturing Supply Chain Based on Blockchain[J]. Manufacturing Automation, 2023, 45(4):201-208.)

[8] Al-Bahri M, Ateya A, Muthanna A, et al. Digital Object Architecture for IoT Networks[J]. Intelligent Automation & Soft Computing, 2023, 76(1):97-110.

[9] 李亮, 肖名志, 陈曦. 区块链技术的去中心化新闻检索与聚合架构研究[J]. 计算机工程, 2026, 52(5):303-325.

[10] (Li L, Xiao M Z, Chen X. Decentralized News-Retrieval and Aggregation Architecture Using Blockchain Technology[J]. Computer Engineering, 2026, 52(5):303-325.)

[11] 马超, 宋琛. 计及电力数据安全的智能合约上链方法及防篡改技术研究[J]. 计算机工程, 2024, 50(10):240-254.

[12] (Ma C, Song C. Research on Smart Contract Uplink Method and Tamper Resistance Technology Considering Power Data Security[J]. Computer Engineering, 2024, 50(10):240-254.)

[13] Li H F, Kong Y, Wang X L. Design and Implementation of a Distributed Data Acquisition Function Architecture Based on DOA/Handle Technology[J]. MATEC Web of Conferences, 2021, 336:05018-1-05018-5.

[14] 王日宏, 周航, 徐泉清, 等. 用于联盟链的非拜占庭容错共识算法[J]. 计算机科学, 2021, 48(9):325-331.

[15] (Wang R H, Zhou H, Xu Q Q, et al. Non-Byzantine Fault Tolerant Consensus Algorithm for Consortium Blockchains[J]. Computer Science, 2021, 48(9):325-331.)

[16] 王嘉瑶, 宋翔宇, 朱俊武. 基于精确分类和最优匹配机制微电网交易决策方法[J]. 计算机应用研究, 2024, 41(2):34-41.

[17] (Wang J Y, Song X Y, Zhu J W. Microgrid Trading Decision Method Based on Exact Classification and Optimal Matching Mechanism[J]. Application Research of Computers, 2024, 41(2):34-41.)

[18] Du Z Q, Qu Z, Fu Y F, et al. Multi-strategy-based Leader Election Mechanism for the Raft Algorithm[J]. Concurrency and Computation:Practice and Experience, 2023, 35(22):e7734-1-e7734-15.

[19] Qin L T, Lu H C, Chen Y, et al. Energy-Efficient Blockchain-Enabled User-Centric Mobile Edge Computing[J]. IEEE Transactions on Cognitive Communications and Networking, 2024, 10(3):1452-1466.

[20] 肖珂, 刘颖, 何云华, 等. 基于多链的能源数据链上链下安全检索方案[J]. 计算机工程, 2025, 51(8):238-249.

[21] (Xiao K, Liu Y, He Y H, et al. On-Chain and Off-Chain Secure Retrieval Scheme for Energy Data Based on Multi-chain[J]. Computer Engineering, 2025, 51(8):238-249.)

[22] 卢丽, 孙林夫, 邹益胜. 基于一致性哈希环多主节点的改进实用拜占庭容错算法[J]. 计算机集成制造系统, 2023, 29(1):29-39.

[23] (Lu L, Sun L F, Zou Y S. Improved Practical Byzantine Fault Tolerance Algorithm with Multi-primary Nodes Based on Consistent Hash Ring[J]. Computer Integrated Manufacturing Systems, 2023, 29(1):29-39.)

[24] Tian S B, Bai F H, Shen T, et al. VSSB-Raft:A Secure and Efficient Zero Trust Consensus Algorithm for Blockchain[J]. ACM Transactions on Sensor Networks, 2024, 20(2):1-22.

[25] 平健, 严正, 陈思捷, 等. 基于区块链的分布式能源交易市场信用风险管理方法[J]. 中国电机工程学报, 2019, 39(24):47-55.

[26] (Ping J, Yan Z, Chen S J, et al. Credit Risk Management Method for Distributed Energy Trading Market Based on Blockchain[J]. Proceedings of the Chinese Society for Electrical Engineering, 2019, 39(24):47-55.)

[27] Mao C Y, Golab W, Wong B. Antipaxos:Taking Interactive Consistency to the Next Level[J]. Journal of Parallel and Distributed Computing, 2024, 187:104839-1-104839-10.

[28] 陈润宇, 王伦文, 朱然刚. 基于信誉值投票与随机数选举的PBFT共识算法[J]. 计算机工程, 2022, 48(6):48-55.

[29] (Chen R Y, Wang L W, Zhu R G. PBFT Consensus Algorithm Based on Reputation Voting and Random Number Election[J]. Computer Engineering, 2022, 48(6):48-55.)

[30] 黄子鑫, 党建武, 王阳萍, 等. 基于改进PBFT的区块链工程监理数据共享模型[J]. 无线电工程, 2023, 53(2):58-67.

[31] (Huang Z X, Dang J W, Wang Y P, et al. Blockchain Engineering Supervision Data Sharing Model Based on Improved PBFT[J]. Radio Engineering, 2023, 53(2):58-67.)

[32] Ge L N, Wang J, Zhang G F. Survey of Consensus Algorithms for Proof of Stake in Blockchain[J]. Security and Communication Networks, 2022, 2022:2812526-1-2812526-13.

[33] Jahedi A, Luz M, Rivinius M, et al. MS-RAFT+:High Resolution Multi-scale RAFT[J]. International Journal of Computer Vision, 2024, 132(5):1835-1856.

[34] 方维维, 王子岳, 宋慧丽, 等. 一种面向区块链的优化PBFT共识算法[J]. 北京交通大学学报, 2019, 43(5):62-68.

[35] (Fang W W, Wang Z Y, Song H L, et al. An Optimized PBFT Consensus Algorithm for Blockchain[J]. Journal of Beijing Jiaotong University, 2019, 43(5):62-68.)

[36] 薛腾飞, 傅群超, 王枞, 等. 基于区块链的医疗数据共享模型研究[J]. 自动化学报, 2017, 43(9):73-80.

[37] (Xue T F, Fu Q C, Wang C, et al. Research on Medical Data Sharing Model Based on Blockchain[J]. Acta Automatica Sinica, 2017, 43(9):73-80.)

[38] Zhang Y P, Xu X W, Liu A, et al. Blockchain-Based Trust Mechanism for IoT-Based Smart Manufacturing System[J]. IEEE Transactions on Computational Social Systems, 2019, 6(6):1386-1394.

[39] 吴梦宇, 朱国胜, 吴善超. 基于工作量证明和权益证明改进的区块链共识机制[J]. 计算机应用, 2020, 40(8):110-114.

[40] (Wu M Y, Zhu G S, Wu S C. Improved Blockchain Consensus Mechanism Based on Proof of Work and Proof of Stake[J]. Journal of Computer Applications, 2020, 40(8):110-114.)

[41] 陈子豪, 李强. 基于K-Medoids的改进PBFT共识机制[J]. 计算机科学, 2019, 46(12):107-113.

[42] (Chen Z H, Li Q. Improved PBFT Consensus Mechanism Based on K-Medoids[J]. Computer Science, 2019, 46(12):107-113.)

[43] Ruoti S, Kaiser B, Yerukhimovich A, et al. Blockchain Technology[J]. Communications of the ACM, 2019, 62(1):46-53.

[44] Zhang Y G, Wang W, Shi F Y. Reputation-Based Raft-Poa layered Consensus Protocol Converging UAV Network[J]. Computer Networks, 2024, 240:110170-1-110170-15.

[45] 黄冬艳, 李浪, 陈斌, 等. RBFT:基于Raft集群的Byzantine容错共识机制[J]. 通信学报, 2021, 42(3):213-223.

[46] (Huang D Y, Li L, Chen B, et al. RBFT:Byzantine Fault Tolerant Consensus Mechanism Based on Raft Cluster[J]. Journal on Communications, 2021, 42(3):213-223.)

[47] 史锦山, 李茹. 物联网下的区块链访问控制综述[J]. 软件学报, 2019, 30(6):62-78.

[48] (Shi J S, Li R. Survey on Blockchain Access Control in Internet of Things[J]. Journal of Software, 2019, 30(6):62-78.)

[49] Jin H, Xiao J. Towards Trustworthy Blockchain Systems in the Era of “Internet of Value”:Development,Challenges,and Future Trends[J]. Science China:Information Sciences, 2022, 65(5):250-260.

[50] 王天柱, 李凌, 彭志辰, 等. 基于区块链的可信制造供应链溯源框架设计[J]. 计算机应用研究, 2024, 41(5):34-39.

[51] (Wang T Z, Li L, Peng Z C, et al. Design of Trusted Manufacturing Supply Chain Traceability Framework Based on Blockchain[J]. Application Research of Computers, 2024, 41(5):34-39.)

[52] 杨万龙, 陈琳. 区块链架构下蜂蜜供应链可信监管溯源模型[J]. 计算机应用研究, 2024, 41(3):37-41.

[53] (Yang W L, Chen L. Trusted Supervision and Traceability Model of Honey Supply Chain under Blockchain Architecture[J]. Application Research of Computers, 2024, 41(3):37-41.)

[54] 何泾沙, 张琨, 薛瑞昕, 等. 基于贡献值和难度值的高可靠性区块链共识机制[J]. 计算机学报, 2021, 44(1):165-179.

[55] (He J S, Zhang K, Xue R X, et al. High Reliability Blockchain Consensus Mechanism Based on Contribution Value and Difficulty Value[J]. Chinese Journal of Computers, 2021, 44(1):165-179.)

[56] Gu R W, Huang D Y. A Leadership Transfer Algorithm for the Raft[C]// CCF China Blockchain Conference.Berlin:Springer, 2022:13-30.

基金资助

吉林省科技发展计划项目(20220202036NC)