Byzantine Fault-Tolerance Consensus Algorithm Based on Perfect Binary Tree Communication

LI Shuzhi; XIONG Weizhi; DENG Xiaohong; WANG Zhiqiang; LIU Hunwen

doi:10.11999/JEIT220798

Volume 45 Issue 7

Jul. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(7): 2484-2493

LI Shuzhi, XIONG Weizhi, DENG Xiaohong, WANG Zhiqiang, LIU Hunwen. Byzantine Fault-Tolerance Consensus Algorithm Based on Perfect Binary Tree Communication[J]. Journal of Electronics & Information Technology, 2023, 45(7): 2484-2493. doi: 10.11999/JEIT220798

Citation:

LI Shuzhi, XIONG Weizhi, DENG Xiaohong, WANG Zhiqiang, LIU Hunwen. Byzantine Fault-Tolerance Consensus Algorithm Based on Perfect Binary Tree Communication[J]. Journal of Electronics & Information Technology, 2023, 45(7): 2484-2493. doi: 10.11999/JEIT220798

Citation:

PDF( 3682 KB)

Byzantine Fault-Tolerance Consensus Algorithm Based on Perfect Binary Tree Communication

doi: 10.11999/JEIT220798

1.
College of Information Science, Jiangxi University of Science and Technology, Ganzhou 341000, China
2.
School of Electronics and Information Engineering, Gannan University of Science and Technology, Ganzhou 341000, China
3.
Key Laboratory of Cloud Computing and Big Data, Ganzhou 341000, China

Funds: The National Natural Science Foundation of China (61762046, 62166019), The Natural Science Foundation of Jiangxi Province (2020BABL202032), The Scientific Research Project of Education Department of Jiangxi Province (GJJ218506, GJJ209412)

Received Date: 2022-06-16
Rev Recd Date: 2022-12-07

Available Online: 2022-12-09

Publish Date: 2023-07-10

Abstract

Abstract

Considering the problems of a predictable primary node, high communication complexity, and lack of punishment mechanism for malicious nodes in Practical Byzantine Fault Tolerance (PBFT) algorithm, a consortium chain Byzantine Fault-Tolerant algorithm based on Perfect Binary Tree communication topology(PBT-BFT) is proposed. In PBT-BFT, a reputation evaluation model is designed to evaluate the behavior of nodes. At the same time, a Reputation-based Verifiable Random Function (R-VRF) is proposed, which makes the probability of random extraction positively correlated with the reputation value, and ensures the fairness and randomness of the lottery for nodes with different reputation values. Then, a perfect binary tree communication topology is designed to reduce the communication complexity to linear complexity, and a rotating primary node and Pipelining are proposed to improve the consensus efficiency. The experimental results show that compared with PBFT, the average throughput is increased by 121.6%, and the average delay is reduced by 73.8%, which can be well applied to the consortium chain of large-scale network nodes.
- Perfect binary tree,
- Communication topology,
- Consensus mechanism,
- Byzantine fault tolerance

FullText(HTML)

References(17)

References

[1]	NAKAMOTO S. Bitcoin: A peer-to-peer electronic cash system[EB/OL]. https://bitcoin.org/en/bitcoin-paper, 2022.
[2]	陈友荣, 章阳, 陈浩, 等. 面向车联网异构节点的区块链高效一致性共识算法研究[J]. 电子与信息学报, 2022, 44(1): 314–323. doi: 10.11999/JEIT201065 CHEN Yourong, ZHANG Yang, CHEN Hao, et al. Efficient consistency consensus algorithm of blockchain for heterogeneous nodes in the internet of vehicles[J]. Journal of Electronics &Information Technology, 2022, 44(1): 314–323. doi: 10.11999/JEIT201065
[3]	陈友荣, 陈浩, 韩蒙, 等. 基于信用等级划分的医疗数据安全共识算法[J]. 电子与信息学报, 2022, 44(1): 279–287. doi: 10.11999/JEIT200893 CHEN Yourong, CHEN Hao, HAN Meng, et al. Security consensus algorithm of medical data based on credit rating[J]. Journal of Electronics &Information Technology, 2022, 44(1): 279–287. doi: 10.11999/JEIT200893
[4]	邓小鸿, 王智强, 李娟, 等. 主流区块链共识算法对比研究[J]. 计算机应用研究, 2022, 39(1): 1–8. doi: 10.19734/j.issn.1001-3695.2021.06.0210 DENG Xiaohong, WANG Zhiqiang, LI Juan, et al. Comparative research on mainstream blockchain consensus algorithms[J]. Application Research of Computers, 2022, 39(1): 1–8. doi: 10.19734/j.issn.1001-3695.2021.06.0210
[5]	CASTRO M and LISKOV B. Practical Byzantine fault tolerance[C]. The Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, 1999: 173–186.
[6]	黄冬艳, 李浪, 陈斌, 等. RBFT: 基于Raft集群的拜占庭容错共识机制[J]. 通信学报, 2021, 42(3): 209–219. doi: 10.11959/j.issn.1000-436x.2021043 HUANG Dongyan, LI Lang, CHEN Bin, et al. RBFT: A new Byzantine fault-tolerant consensus mechanism based on Raft cluster[J]. Journal on Communications, 2021, 42(3): 209–219. doi: 10.11959/j.issn.1000-436x.2021043
[7]	赖英旭, 薄尊旭, 刘静. 基于改进PBFT算法防御区块链中Sybil攻击的研究[J]. 通信学报, 2020, 41(9): 104–117. doi: 10.11959/j.issn.1000-436x.2020170 LAI Yingxu, BO Zunxu, and LIU Jing. Research on Sybil attack in defense blockchain based on improved PBFT algorithm[J]. Journal on Communications, 2020, 41(9): 104–117. doi: 10.11959/j.issn.1000-436x.2020170
[8]	王日宏, 袁杉杉, 徐泉清, 等. 基于时间权重值的共识算法研究[J]. 计算机应用研究, 2021, 38(11): 3243–3248. doi: 10.19734/j.issn.1001-3695.2021.03.0097 WANG Rihong, YUAN Shanshan, XU Quanqing, et al. Consensus algorithm based on time weight value[J]. Application Research of Computers, 2021, 38(11): 3243–3248. doi: 10.19734/j.issn.1001-3695.2021.03.0097
[9]	ZHAN Yu, WANG Baocang, LU Rongxing, et al. DRBFT: Delegated randomization Byzantine fault tolerance consensus protocol for blockchains[J]. Information Sciences, 2021, 559: 8–21. doi: 10.1016/j.ins.2020.12.077
[10]	LI Y X, QIAO Liang, and LV Zhihan. An optimized byzantine fault tolerance algorithm for consortium blockchain[J]. Peer-to-Peer Networking and Applications, 2021, 14(5): 2826–2839. doi: 10.1007/s12083-021-01103-8
[11]	CHEN Yineng, LI Ming, ZHU Xinghui, et al. An improved algorithm for practical byzantine fault tolerance to large-scale consortium chain[J]. Information Processing & Management, 2022, 59(2): 102884. doi: 10.1016/j.ipm.2022.102884
[12]	TANG Song, WANG Zhiqiang, JIANG Jian, et al. Improved PBFT algorithm for high-frequency trading scenarios of alliance blockchain[J]. Scientific Reports, 2022, 12(1): 4426. doi: 10.1038/s41598-022-08587-1
[13]	MICALI S, RABIN M, and VADHAN S. Verifiable random functions[C]. The 40th Annual Symposium on Foundations of Computer Science, New York, USA, 1999: 120–130.
[14]	GILAD Y, HEMO R, MICALI S, et al. Algorand: Scaling byzantine agreements for cryptocurrencies[C]. The 26th Symposium on Operating Systems Principles, Shanghai, China, 2017: 51–68.
[15]	GOLDBERG S, REYZIN L, PAPADOPOULOS D, et al. Verifiable random functions (VRFs)[EB/OL], https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/11/, 2022.
[16]	ALQAHTANI S and DEMIRBAS M. Bottlenecks in blockchain consensus protocols[C]. 2021 IEEE International Conference on Omni-Layer Intelligent Systems (COINS), Barcelona, Spain, 2021: 1–8.
[17]	YIN Maofan, MALKHI D, REITER M K, et al. HotStuff: BFT consensus with linearity and responsiveness[C]. The 2019 ACM Symposium on Principles of Distributed Computing, Toronto, Canada, 2019: 347–356.