基于投票机制的拜占庭容错共识算法

doi:10.11772/j.issn.1001-9081.2018102049

计算机应用 ›› 2019, Vol. 39 ›› Issue (6): 1766-1771.DOI: 10.11772/j.issn.1001-9081.2018102049

基于投票机制的拜占庭容错共识算法

王海勇¹, 郭凯璇², 潘启青²

1. 南京邮电大学计算机学院, 南京 210003;
2. 南京邮电大学物联网学院, 南京 210003

收稿日期:2018-10-10 修回日期:2018-12-19 出版日期:2019-06-10 发布日期:2019-06-17
通讯作者: 郭凯璇
作者简介:王海勇(1979-),男,江苏南京人,副研究员,博士,主要研究方向:计算机网络与安全、信息网络;郭凯璇(1991-),女,山东枣庄人,硕士研究生,主要研究方向:区块链、共识算法、物联网;潘启青(1994-),女,江苏南京人,硕士研究生,主要研究方向:区块链、物联网。
基金资助:
江苏省教育信息化研究资助重点课题（20172105）；江苏省现代教育技术研究2017年度智慧校园专项课题（2017-R-59518）；南京邮电大学教学改革重点项目（JG06717JX66）；南京邮电大学校园信息化创新项目（NYXX217002，NYXX217004）；赛尔网络下一代互联网技术创新项目（NGII20180620）。

Byzantine fault tolerance consensus algorithm based on voting mechanism

WANG Haiyong¹, GUO Kaixuan², PAN Qiqing²

1. School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China;
2. School of Internet of Things, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China

Received:2018-10-10 Revised:2018-12-19 Online:2019-06-10 Published:2019-06-17
Supported by:
This work is partially supported by the Key Project of Education Informatization Research of Jiangsu Province (20172105), the Special Project of 2017 Smart Campus of Jiangsu Modern Educational Technology Research (2017-R-59518), the Teaching Reform Project of Nanjing University of Posts and Telecommunications (JG06717JX66), the Campus Informatization Innovation Project of Nanjing University of Posts and Telecommunications (NYXX217002, NYXX217004), the CERNET Innovation Project (NGII20180620).

摘要/Abstract

摘要： 针对现有的区块链中实用拜占庭容错（PBFT）共识算法、基于动态授权的拜占庭容错（DDBFT）共识算法、联盟拜占庭容错（CBFT）共识算法普遍存在能耗高、效率低、扩展性差等问题，通过引入投票机制，提出了基于投票机制的拜占庭容错（VPBFT）共识算法。首先，以PBFT算法为基础，将网络中的节点划分为四类具有不同职责的节点。其次，算法中的投票节点具有投票和评分权，监督生产节点诚实可靠地生产数据块；生产有效的数据块的生产节点优先进入下一轮，候选节点能够被选为生产节点，而普通节点则能够成为投票节点或候选节点。最后，不同类型的节点之间具有一定的数量关系，能够在不同类型节点的数目或网络中的节点总数发生变化时动态调整参数，从而使得算法适应动态网络。通过性能仿真分析可知，VPBFT算法相较于PBFT、DDBFT、CBFT等共识算法，具有低能耗、低时延、高容错性和高动态性。

关键词: 区块链, 拜占庭容错, 投票机制, 共识算法, 数据块

Abstract: Focusing on the problems of high energy consumption, low efficiency and poor scalability of Practical Byzantine Fault Tolerance (PBFT) consensus algorithm, Dynamic authorized Byzantine Fault Tolerance (DDBFT) consensus algorithm and Consortium Byzantine Fault Tolerance (CBFT) consensus algorithm existed in the blockchain, Practical Byzantine Fault Tolerant consensus algorithm based on Voting (VPBFT) was proposed by introducing voting mechanism. Firstly, based on PBFT algorithm, the nodes in the network were divided into four types of nodes with different responsibility. Secondly, the voting nodes in the algorithm had voting and scoring rights to supervise the production nodes to produce data blocks honestly and reliably, the production nodes producing valid data blocks had priority to be selected into next turn, while the candidate nodes were able to be voted as production nodes, and the ordinary nodes were able to be voted as production nodes or candidate nodes. Finally, different types of nodes had a certain quantity relationship between themselves, which means the parameters were able to be dynamically adjusted when the number of different types of nodes or the total number of nodes in the network changed, so that the algorithm was able to adapt to the dynamic network. Through performance simulation analysis, the proposed VPBFT algorithm has low energy consumption, short delay, high fault tolerance and high dynamicity compared with consensus algorithms such as PBFT, DDBFT and CBFT.

Key words: blockchain, Byzantine Fault Tolerance (BFT), voting mechanism, consensus algorithm, data block

中图分类号:

TP301.6

王海勇, 郭凯璇, 潘启青. 基于投票机制的拜占庭容错共识算法[J]. 计算机应用, 2019, 39(6): 1766-1771.

WANG Haiyong, GUO Kaixuan, PAN Qiqing. Byzantine fault tolerance consensus algorithm based on voting mechanism[J]. Journal of Computer Applications, 2019, 39(6): 1766-1771.

参考文献

[1] NAKAMOTO S. Bitcoin:a peer-to-peer electronic cash system[EB/OL].[2018-08-18]. https://www.audible.com/pd/Bitcoin-A-Peer-to-Peer-Electronic-Cash-System-Audiobook/B077T5SCP2.
[2] 长铗,韩锋.区块链:从数字货币到信用社会[M].北京:中信出版社,2016:54-63.(CHANG J, HAN F. Blockchain:from Digital Currency to Credit Society[M]. Beijing:CITIC Press, 2016:54-63.)
[3] BRACHA G, TOUEG S. Asynchronous consensus and broadcast protocols[J]. Journal of the ACM, 1985,32(4):824-840.
[4] LAMPORT L, SHOSTAK R, PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages & Systems, 1982, 4(3):382-401.
[5] 李剑锋.基于拜占庭容错机制的区块链共识算法研究与应用[D].郑州:郑州大学,2018:14-15,31-56.(LI J F. Research and application of blockchain consensus algorithm based on Byzantine fault tolerance mechanism[D]. Zhengzhou:Zhengzhou University, 2018:14-15, 31-56.)
[6] LAMPORT L. The part-time parliament[J]. ACM Transactions on Computing Surveys, 1998, 16(2):133-169.
[7] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm[C]//ATC14:Proceedings of the 2014 USENIX Annual Technical Conference. Berkeley, CA:USENIX Association, 2014:305-319.
[8] REITER M K. A secure group membership protocol[J]. IEEE Transactions on Software Engineering, 1996, 22(1):31-42.
[9] ANDROUTSELLIS-THEOTOKIS S, SPINELLIS D, et al. A survey of peer-to-peer content distribution technologies[J]. ACM Transactions on Computing Surveys, 2004, 36(4):335-371.
[10] 刘肖飞.基于动态授权的拜占庭容错共识算法的区块链性能改进研究[D].杭州:浙江大学,2017:41-67.(LIU X F. Research on performance improvement of blockchain based on dynamic authorized Byzantine fault tolerance consensus algorithm[D]. Hangzhou:Zhejiang University, 2017:41-67.)
[11] JDON.分布式系统Paxos算法[EB/OL].[2018-08-18]. https://www.jdon.com/artichect/paxos.html.(JDON.Distributed system Paxos algorithm[EB/OL].[2018-08-18]. https://www.jdon.com/artichect/paxos.html.)
[12] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm (extended version)[EB/OL].[2018-08-18]. https://raft.github.io/raft.pdf.
[13] CASTRO M, LISKOV B. Practical Byzantine fault tolerance[C]//Proceeding of the 1999 Third Symposium on Operating Systems Design and Implementation. Berkeley, CA:USENIX association, 1999:173-186.
[14] LI K, LI H, HOU H, et al. Proof of vote:a high-performance consensus protocol based on vote mechanism & consortium blockchain[C]//Proceedings of the 2017 IEEE International Conference on High Performance Computing and Communications, IEEE International Conference on Smart City, IEEE International Conference on Data Science and Systems. Piscataway, NJ:IEEE, 2017:466-473.
[15] DWORK C, NAOR M. Pricing via processing, or, combating junk mail[C]//Proceedings of the 199312th Annual International Cryptology Conference, LNCS 1328. Berlin:Springer, 1993:139-147.

基于投票机制的拜占庭容错共识算法

Byzantine fault tolerance consensus algorithm based on voting mechanism

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	葛纪红, 沈韬. 基于区块链的能源数据访问控制方法[J]. 计算机应用, 2021, 41(9): 2615-2622.
[2]	申玉民, 王金龙, 胡殿凯, 刘星宇. 基于区块链的建筑信息模型图纸多人协同创作系统[J]. 计算机应用, 2021, 41(8): 2338-2345.
[3]	杨龙海, 王学渊, 蒋和松. 改进SM2签名方法的区块链数字签名方案[J]. 计算机应用, 2021, 41(7): 1983-1988.
[4]	陈葳葳, 曹利, 顾翔. 基于区块链的车联网电子取证模型[J]. 计算机应用, 2021, 41(7): 1989-1995.
[5]	卿欣艺, 陈玉玲, 周正强, 涂园超, 李涛. 基于中国剩余定理的区块链存储扩展模型[J]. 计算机应用, 2021, 41(7): 1977-1982.
[6]	李蓓, 张问银, 王九如, 赵伟, 王海峰. 基于区块链的密封式投标拍卖方案[J]. 计算机应用, 2021, 41(4): 999-1004.
[7]	田志宏, 赵金东. 面向物联网的区块链共识机制综述[J]. 计算机应用, 2021, 41(4): 917-929.
[8]	张学旺, 殷梓杰, 冯家琦, 叶财金, 付康. 基于区块链与可信计算的数据交易方案[J]. 计算机应用, 2021, 41(4): 939-944.
[9]	张国潮, 唐华云, 陈建海, 沈睿, 何钦铭, 黄步添. 基于区块链的数字音乐版权管理系统[J]. 计算机应用, 2021, 41(4): 945-955.
[10]	刘宏宇, 梁秀波, 吴俊涵. 基于Kubernetes的Fabric链码管理及高可用技术[J]. 计算机应用, 2021, 41(4): 956-962.
[11]	刘宇, 朱朝阳, 李金泽, 劳源基, 覃团发. 检测型的联盟区块链共识算法d-PBFT[J]. 计算机应用, 2021, 41(3): 756-762.
[12]	高昊昱, 李雷孝, 林浩, 李杰, 邓丹, 李少旭. 区块链在数据完整性保护领域的研究与应用进展[J]. 计算机应用, 2021, 41(3): 745-755.
[13]	罗长银, 陈学斌, 马春地, 王君宇. 面向区块链的在线联邦增量学习算法[J]. 计算机应用, 2021, 41(2): 363-371.
[14]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[15]	周翔, 翟俊海, 黄雅婕, 申瑞彩, 侯璎真. 基于随机森林和投票机制的大数据样例选择算法[J]. 计算机应用, 2021, 41(1): 74-80.