计算机科学 ›› 2021, Vol. 48 ›› Issue (9): 317-323.doi: 10.11896/jsjkx.200600051

• 信息安全 • 上一篇    下一篇

用于联盟链的非拜占庭容错共识算法

王日宏1, 周航1, 徐泉清2, 张立锋1   

  1. 1 青岛理工大学信息与控制工程学院 山东 青岛266520
    2 阿里巴巴达摩院 杭州 310012
  • 收稿日期:2020-06-08 修回日期:2020-09-09 出版日期:2021-09-15 发布日期:2021-09-10
  • 通讯作者: 周航(2275392207@qq.com)
  • 作者简介:rihongw@126.com
  • 基金资助:
    山东省研究生教育创新计划项目(SDYY16023)

Non-byzantine Fault Tolerance Consensus Algorithm for Consortium Blockchain

WANG Ri-hong1, ZHOU Hang1, XU Quan-qing2, ZHANG Li-feng1   

  1. 1 School of Information & Control Engineering,Qingdao University of Technology,Qingdao,Shandong 266520,China
    2 Alibaba DAMO Academy,Hangzhou 310012,China
  • Received:2020-06-08 Revised:2020-09-09 Online:2021-09-15 Published:2021-09-10
  • About author:WANG Ri-hong,born in 1964,professor,master supervisor.His main research interests include blockchain technology and intelligent information processing.
    ZHOU Hang,born in 1995,postgra-duate.Her main research interests include blockcha in technology and so on.
  • Supported by:
    Shandong Graduate Education Innovation Program Project(SDYY16023).

摘要: 随着区块链技术的发展,区块链出现了多种分类,兼顾公有链多中心特点和私有链高性能优势的联盟链成为了我国区块链的发展重心。结合联盟链中存在节点信任的特性,非拜占庭容错共识算法能为联盟链提供更好的性能支持。文中选取Raft共识算法作为研究对象,针对Raft共识算法中Leader节点选举和日志复制过程中的诸多问题,提出了一种可应用于联盟链的非拜占庭容错共识算法——KRaft(Kademlia-Raft)共识算法,该共识算法结合区块链网络层的双层Kademlia路由协议改进了Raft共识算法中的Leader节点选举和日志复制过程。首先,针对Raft共识算法Leader节点选举中存在的多Candidate节点分票和Follower节点增多引发的投票效率问题,KRaft共识算法利用双层Kademlia协议建立的K桶实现了Candidate节点集合内的稳定选举;其次,针对Raft共识算法日志复制过程中Leader节点单节点日志复制过程效率低和节点负载不均的问题,提出了均衡Leader节点负载的多Candidate节点并行日志复制方案,在提升数据吞吐量的同时提升了算法的可拓展性。本地多节点仿真实验的结果表明,KRaft共识算法相较于Raft共识算法,数据吞吐量提升了34.5%,Leader节点选举速度提升了55.6%。

关键词: Kademlia路由协议, Raft共识算法, 共识算法, 联盟链, 区块链

Abstract: As a consortium blockchain with the multi-center characteristics of public blockchain and the high-performance advantages of private blockchain,it has become the center of development of China.Combined with the characteristics of node trust in the consortium blockchain,non-byzantine fault tolerance consensus algorithm can provide better performance support for the consortium blockchain.By selecting Raft consensus algorithm as the research object,focusing on the leader election and log replication process in the Raft consensus algorithm,this paper proposes a non-byzantine fault tolerance consensus algorithm for consortium blockchain—Kraft(Kademlia-Raft) consensus algorithm.It improves the process of Leader election and log replication in the Raft consensus algorithm by combining the two-layer Kademlia routing protocol.First,in view of the problem of voting efficiency caused by the number of Candidate nodes and the increase of Follower nodes in the Raft consensus algorithm,KRaft consensus algorithm uses K-bucket established by the two-layer Kademlia protocol to realize the stable election in the Candidate node set.Se-condly,in view of the low efficiency of the single-node log replication process of the Leader in the log replication process of Raft consensus algorithm and the load balance problem on the nodes,a parallel log replication scheme of multiple Candidate nodes is proposed to equalize the load on the Leader node,so as to improve the data throughput and the scalability of the algorithm at the same time.Finally,the local multi-node simulation experiment shows that the data throughput of KRaft consensus algorithm is increased by 34.5% compared with Raft consensus algorithm,the voting speed of Leader node is increased by 55.6%.

Key words: Blockchain, Consensus algorithm, Consortium blockchain, Kademlia routing protocol, Raft consensus algorithm

中图分类号: 

  • TP393
[1]ONGARO D,OUSTERHOUT J.In search of an understandable consensus algorithm[C]//2014 {USENIX} Annual Technical Conference.2014:305-319.
[2]LU N,ZHANG Y,SHI W,et al.A secure and scalable data integrity auditing scheme based on hyperledger fabric[J].Computers & Security,2020,92:101741.
[3]YUAN Y,WANG F Y.Development status and Prospect ofBlockchain technology[J].Journal of Automation,2016,42(4):481-494.
[4]CROSBY M,PATTANAYAK P,VERMA S,et al.Blockchaintechnology:Beyond bitcoin[J].Applied Innovation,2016,2(6/7/8/9/10):71.
[5]HO C C,WANG K,HSU Y H.A fast consensus algorithm formultiple controllers in software-defined networks[C]//2016 18th International Conference on Advanced Communication Technology (ICACT).IEEE,2016:112-116.
[6]GRAMOLI V.From blockchain consensus back to byzantineconsensus[J].Future Generation Computer Systems,2020,107:760-769.
[7]XIAO Y,ZHANG N,LOU W,et al.A survey of distributedconsensus protocols for blockchain networks[J].IEEE Communications Surveys & Tutorials,2020,22(2):1432-1465.
[8]ALFANDI O,OTOUM S,JARARWEH Y.Blockchain Solution for IoT-based Critical Infrastructures:Byzantine Fault Tolerance[C]//NOMS 2020-2020 IEEE/IFIP Network Operations and Management Symposium.IEEE,2020:1-4.
[9]DE ANGELIS S,ANIELLO L,BALDONI R,et al.PBFT vsproof-of-authority:Applying the CAP theorem to permissioned blockchain[C]//Italian Conference on Cyberseaurity.2017.
[10]HAKKARINEN D,WU P,CHEN Z.Fail-stop failure algo-rithm-based fault tolerance for cholesky decomposition[J].IEEE Transactions on Parallel and Distributed Systems,2014,26(5):1323-1335.
[11]WANG R H,ZHANG L F,XU Q Q,et al.K-Bucket BasedRaft-Like Consensus Algorithm for Permissioned Blockchain[C]//2019 IEEE 25th International Conference on Parallel and Distributed Systems (ICPADS).IEEE,2019:996-999.
[12]WANG R H,ZHANG L F,ZHOU H,et al.A Byzantine fault tolerant Raft algorithm combined with BLS signature[J].Journal of Applied Science,2020,38(1):93-104.
[13]LEE E,YOON Y,LEE G M,et al.Blockchain-based PerfectSharing Project Platform based on the Proof of Atomicity Consensus Algorithm[J].Tehnicki Vjesnik,2020,27(4):1244-1253.
[14]GERGELY A M,CRAINICU B.RandAdminSuite:A New Privacy-Enhancing Solution for Private Blockchains[J].Procedia Manufacturing,2020,46:562-569.
[15]RAO A,LAKSHMINARAYANAN K,SURANA S,et al.Loadbalancing in structured P2P systems[C]//International Work-shop on Peer-to-Peer Systems.Berlin,Heidelberg:Springer,2003:68-79.
[16]WU Y,LI J X.Evolution process of blockchain P2P networkprotocol[J].Application Research of Computer,2019,36(10):2881-2886.
[17]OU Z,HARJULA E,KASSINEN O,et al.Performance evaluation of a Kademlia-based communication-oriented P2P system under churn[J].Computer Networks,2010,54(5):689-705.
[18]ZHENG Z,XIE S,DAI H N,et al.Blockchain challenges and opportunities:A survey[J].International Journal of Web and Grid Services,2018,14(4):352-375.
[19]ZHANG Z,CHOW M Y.Convergence analysis of the incremental cost consensus algorithm under different communication network topologies in a smart grid[J].IEEE Transactions on PowerSystems,2012,27(4):1761-1768.
[1] 王子凯, 朱健, 张伯钧, 胡凯.
区块链与智能合约并行方法研究与实现
Research and Implementation of Parallel Method in Blockchain and Smart Contract
计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[2] 周航, 姜河, 赵琰, 解相朋.
适用于各单元共识交易的电力区块链系统优化调度研究
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
[3] 陈彦冰, 钟超然, 周超然, 薛凌妍, 黄海平.
基于医疗联盟链的跨域认证方案设计
Design of Cross-domain Authentication Scheme Based on Medical Consortium Chain
计算机科学, 2022, 49(6A): 537-543. https://doi.org/10.11896/jsjkx.220200139
[4] 李博, 向海昀, 张宇翔, 廖浩德.
面向食品溯源场景的PBFT优化算法应用研究
Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios
计算机科学, 2022, 49(6A): 723-728. https://doi.org/10.11896/jsjkx.210800018
[5] 傅丽玉, 陆歌皓, 吴义明, 罗娅玲.
区块链技术的研究及其发展综述
Overview of Research and Development of Blockchain Technology
计算机科学, 2022, 49(6A): 447-461. https://doi.org/10.11896/jsjkx.210600214
[6] 高健博, 张家硕, 李青山, 陈钟.
RegLang:一种面向监管的智能合约编程语言
RegLang:A Smart Contract Programming Language for Regulation
计算机科学, 2022, 49(6A): 462-468. https://doi.org/10.11896/jsjkx.210700016
[7] 袁昊男, 王瑞锦, 郑博文, 吴邦彦.
基于Fabric的电子病历跨链可信共享系统设计与实现
Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric
计算机科学, 2022, 49(6A): 490-495. https://doi.org/10.11896/jsjkx.210500063
[8] 毛典辉, 黄晖煜, 赵爽.
符合监管合规性的自动合成新闻检测方法研究
Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance
计算机科学, 2022, 49(6A): 523-530. https://doi.org/10.11896/jsjkx.210300083
[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] 李素, 宋宝燕, 李冬, 王俊陆.
面向金融活动的复合区块链关联事件溯源方法
Composite Blockchain Associated Event Tracing Method for Financial Activities
计算机科学, 2022, 49(3): 346-353. https://doi.org/10.11896/jsjkx.210700068
[15] 杨昕宇, 彭长根, 杨辉, 丁红发.
基于演化博弈的理性拜占庭容错共识算法
Rational PBFT Consensus Algorithm with Evolutionary Game
计算机科学, 2022, 49(3): 360-370. https://doi.org/10.11896/jsjkx.210900110
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!