基于信誉值投票与随机数选举的PBFT共识算法

doi:10.19678/j.issn.1000-3428.0063904

摘要/Abstract

摘要： 实用拜占庭容错（PBFT）算法在Raft和Paxos共识算法的基础上，解决了分布式系统中恶意节点向其他节点发送错误消息以扰乱系统正常运行的问题，但PBFT算法由于主节点选举随意导致共识效率低下，而现有PBFT改进算法普遍通信复杂度较高且容易出现系统集中化趋势。针对上述问题，提出一种基于信誉值投票与随机数选举的RN-VPBFT共识算法。通过增设监督节点，实现权力分散和信息中转，保证系统安全运行。在投票确定初始信誉值的过程中，引入随机参数使得满足条件的节点均有机会当选主节点，缓解系统集中化趋势。建立节点动态信誉模型，区分系统中的诚实节点与恶意节点，简化共识算法的一致性协议，降低算法通信复杂度。实验结果表明，与PBFT算法和基于信誉投票的PBFT改进算法相比，RN-VPBFT算法将通信复杂度由O（N²）降至O（N），并且所有诚实节点的信誉值之差仅为0.02，具有更低的通信复杂度及更好的去中心化特性。

关键词: 区块链, 共识算法, 实用拜占庭容错算法, 信誉值投票, 随机数选举

Abstract: Compared with Raft and Paxos, the original consensus algorithm, i.e., the Practical Byzantine Fault Tolerant(PBFT) algorithm, is mainly aimed at malicious nodes in a distributed system used to send error messages to other nodes, disturbing the normal operation of the entire system.This algorithm fundamentally solves the Byzantine problem of the system.However, the PBFT algorithm itself has the problem of a low consensus efficiency caused by an arbitrary primary node election.Meanwhile, existing improved algorithms generally have problems of a high communication complexity and centralization tendency.Aiming at these problems, an improved consensus algorithm, RN-VPBFT, is proposed based on reputation value voting and random number election.First, by adding supervision nodes, the algorithm realizes a decentralization of rights and an information transfer and ensures the safe operation of the system.A random parameter is then introduced during the process of voting to determine the initial reputation value, and thus the reputation value is no longer the only criterion for selecting the master node.All nodes that meet certain conditions have an equal chance to be selected as the master node.This can reduce the trend of system centralization.Finally, the algorithm establishes the dynamic reputation model of the nodes to distinguish between honest and malicious nodes in the system, simplify the consistency protocol of the consensus algorithm, and reduce the communication complexity of the entire algorithm.Experimental results show that, compared with the original PBFT algorithm and the existing improved PBFT algorithm based on reputation voting, the RN-VPBFT algorithm can reduce the communication complexity from O(N²) to O(N).The final difference in reputation of all honesty nodes is only 0.02, which is almost negligible.Therefore, the proposed algorithm has a lower communication complexity and better decentralization.

Key words: blockchain, consensus algorithm, Practical Byzantine Fault Tolerant(PBFT) algorithm, reputation value voting, random number election

中图分类号:

TP311

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

CHEN Runyu, WANG Lunwen, ZHU Rangang. PBFT Consensus Algorithm Based on Reputation Value Voting and Random Number Election[J]. Computer Engineering, 2022, 48(6): 42-49,56.

https://www.ecice06.com/CN/Y2022/V48/I6/42

图/表 15

20220618112839

20220618112843

20220618112847

20220618112850

20220618112854

20220618112858

20220618112902

20220618112906

20220618112910

20220618112913

20220618112917

20220618112921

20220618112925

20220618112929

20220618112934

参考文献

[1] NAKAMOTO S.A peer-to-peer electronic cash system[EB/OL].[2022-01-17].http://bitcoins.info/bitcoin.pdf.
[2] 袁勇, 王飞跃.区块链技术发展现状与展望[J].自动化学报, 2016, 42(4):481-494. YUAN Y, WANG F Y.Blockchain:the state of the art and future trends[J].Acta Automatica Sinica, 2016, 42(4):481-494.(in Chinese)
[3] WANG H, QIN H, ZHAO M H, et al.Blockchain-based fair payment smart contract for public cloud storage auditing[J].Information Sciences, 2020, 519:348-362.
[4] GAO F, ZHU L H, SHEN M, et al.A blockchain-based privacy-preserving payment mechanism for vehicle-to-grid networks[J].IEEE Network, 2018, 32(6):184-192.
[5] 张亮, 刘百祥, 张如意, 等.区块链技术综述[J].计算机工程, 2019, 45(5):1-12. ZHANG L, LIU B X, ZHANG R Y, et al.Overview of blockchain technology[J].Computer Engineering, 2019, 45(5):1-12.(in Chinese)
[6] 王志铧, 柳平增, 宋成宝, 等.基于区块链的农产品柔性可信溯源系统研究[J].计算机工程, 2020, 46(12):313-320. WANG Z H, LIU P Z, SONG C B, et al.Research on flexible and reliable blockchain-based traceability system for agricultural products[J].Computer Engineering, 2020, 46(12):313-320.(in Chinese)
[7] 刘懿中, 刘建伟, 张宗洋, 等.区块链共识机制研究综述[J].密码学报, 2019, 6(4):395-432. LIU Y Z, LIU J W, ZHANG Z Y, et al.Overview on blockchain consensus mechanisms[J].Journal of Cryptologic Research, 2019, 6(4):395-432.(in Chinese)
[8] JAKOBSSON M, JUELS A.Proofs of work and bread pudding protocols(extended abstract)[M].Berlin, Germany:Springer, 1999.
[9] 谭敏生, 杨杰, 丁琳, 等.区块链共识机制综述[J].计算机工程, 2020, 46(12):1-11. TAN M S, YANG J, DING L, et al.Review of consensus mechanism of blockchain[J].Computer Engineering, 2020, 46(12):1-11.(in Chinese)
[10] 范捷, 易乐天, 舒继武.拜占庭系统技术研究综述[J].软件学报, 2013, 24(6):1346-1360. FAN J, YI L T, SHU J W.Research on the technologies of Byzantine system[J].Journal of Software, 2013, 24(6):1346-1360.(in Chinese)
[11] CASTRO M, LISKOV B.Practical Byzantine fault tolerance[EB/OL].[2022-01-17].https://www.researchgate.net/publication/2437947_Practical_Byzantine_Fault_Tolerance.
[12] 吴晓彤, 柳平增.基于备选投票机制的低时延PBFT改进研究[J].计算机工程, 2021, 47(7):117-125, 134. WU X T, LIU P Z.Delay optimization for PBFT based on alternative voting mechanism[J].Computer Engineering, 2021, 47(7):117-125, 134.(in Chinese)
[13] ZHENG X D, FENG W L.Research on practical Byzantine fault tolerant consensus algorithm based on blockchain[EB/OL].[2022-01-17].httpss://iopscience.iop.org/article/10.1088/1742-6596/1802/3/032022/pdf.
[14] LAMPORT L, SHOSTAK R, PEASE M.The Byzantine generals problem[J].ACM Transactions on Programming Languages and Systems, 1982, 4(3):382-401.
[15] WANG Y H, CAI S B, LIN C L, et al.Study of blockchain's consensus mechanism based on credit[J].IEEE Access, 2019, 7:10224-10231.
[16] ZHU S C, ZHANG Z Y, CHEN L Q, et al.A PBFT consensus scheme with reputation value voting based on dynamic clustering[M].Berlin, Germany:Springer, 2020.
[17] ZHANG Z J, ZHU D L, FAN W.QPBFT:practical Byzantine fault tolerance consensus algorithm based on quantified-role[C]//Proceedings of IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications.Washington D.C., USA:IEEE Press, 2021:991-997.
[18] ZHENG X D, FENG W L, HUANG M X, et al.Optimization of PBFT algorithm based on improved C4.5[J].Mathematical Problems in Engineering, 2021(2):1-7.
[19] GAO S, YU T Y, ZHU J M, et al.T-PBFT:an EigenTrust-based practical Byzantine fault tolerance consensus algorithm[J].China Communications, 2019, 16(12):111-123.
[20] TONG W, DONG X W, ZHENG J W.Trust-PBFT:a PeerTrust-based practical Byzantine consensus algorithm[C]//Proceedings of International Conference on Networking and Network Applications.Washington D.C., USA:IEEE Press, 2019:344-349.
[21] WANG H Y, GUO K X.Byzantine fault tolerant algorithm based on vote[C]//Proceedings of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.Berlin, Germany:Springer, 2019:190-196.
[22] 方维维, 王子岳, 宋慧丽, 等.一种面向区块链的优化PBFT共识算法[J].北京交通大学学报, 2019, 43(5):58-64. 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):58-64.(in Chinese)
[23] 王壹铭, 初剑峰, 王永军, 等.基于有向无环图的高效区块链共识算法[J].吉林大学学报(理学版), 2020, 58(5):1167-1172. WANG Y M, CHU J F, WANG Y J, et al.Efficient blockchain consensus algorithm based on directed acyclic graph[J].Journal of Jilin University(Science Edition), 2020, 58(5):1167-1172.(in Chinese)
[24] CHEN L, XU L, SHAH N, et al.On security analysis of Proof-of-Elapsed-Time(PoET)[C]//Proceedings of International Symposium on Stabilization, Safety, and Security of Distributed Systems.Berlin, Germany:Springer, 2017:282-297.
[25] 王海勇, 郭凯璇, 潘启青.基于投票机制的拜占庭容错共识算法[J].计算机应用, 2019, 39(6):1766-1771. WANG H Y, GUO K X, PAN Q Q.Byzantine fault tolerance consensus algorithm based on voting mechanism[J].Journal of Computer Applications, 2019, 39(6):1766-1771.(in Chinese)

选择文件类型/文献管理软件名称

选择包含的内容