计算机科学 ›› 2022, Vol. 49 ›› Issue (3): 360-370.doi: 10.11896/jsjkx.210900110

• 信息安全 • 上一篇    

基于演化博弈的理性拜占庭容错共识算法

杨昕宇1,3, 彭长根1,2,3, 杨辉1, 丁红发4   

  1. 1 贵州大学数学与统计学院公共大数据国家重点实验室 贵阳550025
    2 贵州大学计算机科学与技术学院 贵阳550025
    3 贵州大学密码学与数据安全研究所 贵阳550025
    4 贵州财经大学信息学院 贵阳550025
  • 收稿日期:2021-09-13 修回日期:2022-01-05 出版日期:2022-03-15 发布日期:2022-03-15
  • 通讯作者: 丁红发(hongfa.ding@foxmail.com)
  • 作者简介:(yxiny__gzu@163.com)
  • 基金资助:
    国家自然科学基金(U1836205);贵州省科技计划基金(黔科合平台人才[2020]5017);贵州省教育厅自然科学项目(黔教合KY字[2021]140);贵州大学培育项目([2019]56);贵州大学人才引进科研项目([2020]61)

Rational PBFT Consensus Algorithm with Evolutionary Game

YANG Xin-yu1,3, PENG Chang-gen1,2,3, YANG Hui1, DING Hong-fa4   

  1. 1 College of Mathematics and Statistics,State Key Laboratory of Public Big Data,Guizhou University,Guiyang 550025,China
    2 College of Computer Science and Technology,Guizhou University,Guiyang 550025,China
    3 Institute of Cryptography and Data Security,Guizhou University,Guiyang 550025,China
    4 College of Information,Guizhou University of Finance and Economics,Guiyang 550025,China
  • Received:2021-09-13 Revised:2022-01-05 Online:2022-03-15 Published:2022-03-15
  • About author:YANG Xin-yu,born in 1998,master student.His main research interests include consensus mechanism and game theory.
    DING Hong-fa,born in 1988,Ph.D,associate professor.His main research interests include privacy protection and data security.
  • Supported by:
    Natural Science Foundation of China(U1836205),Science and Technology Program of Guizhou Province(Qian-Science-Contract-Platform-Talent[2020]5017),Natural Science Fundation of Guizhou Provincial Education Department(Qian-Education-Contact-KY[2021]140),Cultivation Project of Guizhou University([2019]56) and Research Project of Guizhou University for TalentIntroduction([2020]61).

摘要: 拜占庭容错算法(byzantine fault-tolerant)是保证区块链等分布式系统能够达成一致性的重要算法,其性能影响着系统的安全性和稳定性。针对现有共识算法存在效率低下和缺少激励机制等问题,提出了一种基于演化博弈的理性实用拜占庭容错共识算法。首先,通过引入信誉机制来确定节点在共识过程中的可信任度,以信誉值为理性节点共识积极性的依据,基于信誉对共识节点进行划分,采用节点网络分片化的共识方式来提升共识效率;其次,针对共识过程中节点之间链路动态性对信誉值产生的影响建立演化博弈模型,并分析证明信誉稳定策略的存在性,设计基于信誉稳定策略的激励机制,以提升共识节点参与共识的积极性。实验结果表明,所提共识算法可提升40%的吞吐量,且在共识过程中对节点所设计的信誉演化博弈模型有快速收敛的效果。

关键词: 共识算法, 激励机制, 区块链, 信誉机制, 演化博弈

Abstract: Byzantine fault-tolerant algorithm is vital to ensure the distributed system such as blockchain reaching consistency.The performance of algorithm affects the security and stability of the system.In view of the low efficiency and lack of incentive mechanism of existing consensus algorithms,a rational practical Byzantine fault-tolerant consensus algorithm with evolutionary game is proposed.Firstly,the trustworthiness of nodes in the consensus process is determined by node trust evaluation,the reputation value is used as the basis for the consensus enthusiasm of rational nodes,consensus nodes are divided based on reputation value,and the consensus method of node network fragmentation is adopted to improve consensus efficiency;secondly,the evolutionary game model is established for the impact of link dynamics between nodes in the consensus process on the reputation value,and based on the existence of the reputation stabilization strategy,an incentive mechanism based on reputation value rewards is designed to enhance the enthusiasm of consensus nodes to participate in consensus.Simulation results show that the consensus algorithm has a throughput increase of 40%,and the reputation evolution game model designed for nodes has a rapid convergence effect in the consensus process.

Key words: Blockchain, Consensus algorithm, Evolutionary game, Incentive mechanism, Reputation mechanism

中图分类号: 

  • O225
[1]CASTRO M,LISKOV B.Practical Byzantine Fault Tolerance[C]//Proceedings of the Third Symposium on Operating Systems Design and Implementation.New York:ACM Press,1999:173-186.
[2]SUKHWANI H,MARTÍNEZ J M,CHANG X L,et al.Performance Modeling of PBFT Consensus Process for Permissioned Blockchain Network (Hyperledger Fabric)[C]//2017 IEEE 36th Symposium on Reliable Distributed Systems.NJ:IEEE Press,2017:253-255.
[3]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.
[4]LI Y X,WANG Z,FAN J,et al.An Extensible Consensus Algorithm Based on PBFT[C]//2019 International Conference on Cyber-Enabled Distributed Computing and Knowledge Disco-very.NJ:IEEE Press,2019:17-23.
[5]NWEBONYI F N,MARTINS R,CORREIA M E.Reputation based Approach for Improved Fairness and Robustness in P2P Protocols[J].Peer-to-Peer Networking and Applications,2019,12(4):951-968.
[6]GAYVORONSKAYA T M.Blockchain:Hype Or Innovation[M]//Springer International Publishing AG.Berlin:Springer,2021:1-14.
[7]BOU A J,EI S R,KAMBHAMPATY K,et al.PermissionlessReputation-based Consensus Algorithm for Blockchain[J].Internet Technology Letters,2020,3(3):7-12.
[8]ZHU S C,ZHANG Z Y,CHEN L Q,et al.A PBFT Consensus Scheme with Reputation Value Voting based on Dynamic Clustering[C]//International Conference on Security and Privacy in Digital Economy.Singapore:Springer,2020:336-354.
[9]LIU Z Y,LUONG N C,WANG W B,et al.A Survey on Blockchain:A Game Theoretical Perspective[J].IEEE Access,2019,7(4):47615-47643.
[10]LI W Y,FENG C L,ZHANG L,et al.A Scalable Multi-layer PBFT Consensus for Blockchain[J].IEEE Transactions on Pa-rallel and Distributed Systems,2020,32(5):1146-1160.
[11]XU X L,ZHU D W,YANG X X,et al.Concurrent Practical Byzantine Fault Tolerance for Integration of Blockchain and Supply Chain[J].ACM Transactions on Internet Technology,2021,21(1):1-17.
[12]LEI K,ZHANG Q C,XU L M,et al.Reputation-based Byzantine Fault Tolerance for Consortium Block-chain[C]//2018 IEEE 24th International Conference on Parallel and Distributed Systems.NJ:IEEE Press,2018:604-611.
[13]BIRYUKOV A,FEHER D.ReCon:Sybil-resistant Consensusfrom Reputation[J].Pervasive and Mobile Computing,2020,61(1):1-29.
[14]CHEN P,HAN D Z,WENG T H,et al.A Novel ByzantineFault Tolerance Consensus for Green IoT with Intelligence based on Reinforcement[J].Journal of Information Security and Applications,2021,59(6):131-139.
[15]LIA Y X,BO Z X,LIU J.Research on Sybil Attack in Defense Blockchain based on Improved PBFT Algorithm[J].Journal on Communications,2020,41(9):104-117.
[16]YU J S,KOZHAYA D,DECOUCHANT J,et al.Repucoin:Your Reputation is Your Power[J].IEEE Transactions on Computers,2019,68(8):1225-1237.
[17]BOU A J,EI S R,DEMERJIAN J.Permissionless Proof-of-Re-putation-X:A Hybrid Reputation-based Consensus Algorithm for Permissionless Blockchains[J].Transactions on Emerging Telecommunications Technologies,2021,32(1):383-410.
[18]MANSHAEI M H,JADLIWALA M,MAITI A,et al.A Game-Theoretic Analysis of Shard-based Permissionless Blockchains[J].IEEE Access,2018,6(12):78100-78112.
[19]TIAN Y L,PENG C G,MA J F,et al.Game-Theoretic Mechanism for Cryptographic Protocol[J].Journal of Computer Research and Development,2014,51(2):344-352.
[20]DING H F,PENG C G,TIAN Y L,et al.Privacy Risk Adaptive Access Control Model via Evolutionary Game[J].Journal on Communications,2019,40(12):9-20.
[21]SANDHOLM W H.Population Games and Evolutionary Dy-namics[M]//Massachusetts Institute of Technology MIT Press.London:The MIT Press,2010:119-140.
[22]LI S J,SU W L.The Research of Reputation Incentive Mechanism of P2P Network File Sharing System[J].International Journal of Information and Computer Security,2018,10(2/3):149-169.
[23]RANJBAR-SAHRAEI B,BOU A H,BLOEMBERGEN D,et al.Evolution of Cooperation in Arbitrary Complex Networks[C]//Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems.New York:ACM Press,2014:677-684.
[24]HARTMAN P.A Lemma in The Theory of Structural Stability of Differential Equations[J].Proceedings of the American Ma-thematical Society,1960,11(4):610-620.
[25]WANG E K,LIANG Z D,CHEN C M,et al.PoRX:A Reputation Incentive Scheme for Blockchain Consensus of IioT[J].Future Generation Computer Systems,2020,102(1):140-151.
[26]MALKHI D,NAYAK K,REN L.Flexible Byzantine Fault To-lerance[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security.New York:ACM Press,2019:1041-1053.
[1] 傅彦铭, 朱杰夫, 蒋侃, 黄保华, 孟庆文, 周兴.
移动众包中基于多约束工人择优的激励机制研究
Incentive Mechanism Based on Multi-constrained Worker Selection in Mobile Crowdsourcing
计算机科学, 2022, 49(9): 275-282. https://doi.org/10.11896/jsjkx.210700129
[2] 王子凯, 朱健, 张伯钧, 胡凯.
区块链与智能合约并行方法研究与实现
Research and Implementation of Parallel Method in Blockchain and Smart Contract
计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[3] 傅丽玉, 陆歌皓, 吴义明, 罗娅玲.
区块链技术的研究及其发展综述
Overview of Research and Development of Blockchain Technology
计算机科学, 2022, 49(6A): 447-461. https://doi.org/10.11896/jsjkx.210600214
[4] 高健博, 张家硕, 李青山, 陈钟.
RegLang:一种面向监管的智能合约编程语言
RegLang:A Smart Contract Programming Language for Regulation
计算机科学, 2022, 49(6A): 462-468. https://doi.org/10.11896/jsjkx.210700016
[5] 毛典辉, 黄晖煜, 赵爽.
符合监管合规性的自动合成新闻检测方法研究
Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance
计算机科学, 2022, 49(6A): 523-530. https://doi.org/10.11896/jsjkx.210300083
[6] 王显芳, 张亮, 张宁.
基于前景理论的微信健康信息质量三方博弈分析
Evolutionary Game Analysis of WeChat Health Information Quality Optimization Based on Prospect Theory
计算机科学, 2022, 49(6A): 694-704. https://doi.org/10.11896/jsjkx.210900186
[7] 李博, 向海昀, 张宇翔, 廖浩德.
面向食品溯源场景的PBFT优化算法应用研究
Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios
计算机科学, 2022, 49(6A): 723-728. https://doi.org/10.11896/jsjkx.210800018
[8] 周航, 姜河, 赵琰, 解相朋.
适用于各单元共识交易的电力区块链系统优化调度研究
Study on Optimal Scheduling of Power Blockchain System for Consensus Transaction ofEach Unit
计算机科学, 2022, 49(6A): 771-776. https://doi.org/10.11896/jsjkx.210600241
[9] 王思明, 谭北海, 余荣.
面向6G可信可靠智能的区块链分片与激励机制
Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence
计算机科学, 2022, 49(6): 32-38. https://doi.org/10.11896/jsjkx.220400004
[10] 孙浩, 毛瀚宇, 张岩峰, 于戈, 徐石成, 何光宇.
区块链跨链技术发展及应用
Development and Application of Blockchain Cross-chain Technology
计算机科学, 2022, 49(5): 287-295. https://doi.org/10.11896/jsjkx.210800132
[11] 阳真, 黄松, 郑长友.
基于区块链与改进CP-ABE的众测知识产权保护技术研究
Study on Crowdsourced Testing Intellectual Property Protection Technology Based on Blockchain and Improved CP-ABE
计算机科学, 2022, 49(5): 325-332. https://doi.org/10.11896/jsjkx.210900075
[12] 任畅, 赵洪, 蒋华.
一种量子安全拜占庭容错共识机制
Quantum Secured-Byzantine Fault Tolerance Blockchain Consensus Mechanism
计算机科学, 2022, 49(5): 333-340. https://doi.org/10.11896/jsjkx.210400154
[13] 冯了了, 丁滟, 刘坤林, 马科林, 常俊胜.
区块链BFT共识算法研究进展
Research Advance on BFT Consensus Algorithms
计算机科学, 2022, 49(4): 329-339. https://doi.org/10.11896/jsjkx.210700011
[14] 杜辉, 李卓, 陈昕.
基于在线双边拍卖的分层联邦学习激励机制
Incentive Mechanism for Hierarchical Federated Learning Based on Online Double Auction
计算机科学, 2022, 49(3): 23-30. https://doi.org/10.11896/jsjkx.210800051
[15] 王鑫, 周泽宝, 余芸, 陈禹旭, 任昊文, 蒋一波, 孙凌云.
一种面向电能量数据的联邦学习可靠性激励机制
Reliable Incentive Mechanism for Federated Learning of Electric Metering Data
计算机科学, 2022, 49(3): 31-38. https://doi.org/10.11896/jsjkx.210700195
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!