一种结合BLS签名的可拜占庭容错Raft算法

doi:10.3969/j.issn.0255-8297.2020.01.007

应用科学学报 ›› 2020, Vol. 38 ›› Issue (1): 93-104.doi: 10.3969/j.issn.0255-8297.2020.01.007

一种结合BLS签名的可拜占庭容错Raft算法

王日宏¹, 张立锋¹, 周航¹, 徐泉清²

1. 青岛理工大学信息与控制工程学院, 山东青岛 266520;
2. 蚂蚁金服, 杭州 310012

收稿日期:2019-11-01 出版日期:2020-01-31 发布日期:2020-01-19
作者简介:张立锋,硕士生,研究方向为区块链.E-mail:zhanglifeng1994@gmail.com
基金资助:
山东省研究生教育创新计划项目基金（No.SDYY16023）资助

A Byzantine Fault Tolerance Raft Algorithm Combines with BLS Signature

WANG Rihong¹, ZHANG Lifeng¹, ZHOU Hang¹, XU Quanqing²

1. School of Information and Control Engineering, Qingdao University of Technology, Qingdao 266520, Shandong Province, China;
2. Ant Financial Services Group, Hangzhou 310012, China

Received:2019-11-01 Online:2020-01-31 Published:2020-01-19

摘要/Abstract

摘要： 针对Raft算法中的拜占庭容错问题，提出结合BLS签名的拜占庭容错（RaftByzantine fault tolerance，RBFT）算法.首先，利用BLS签名实现阈值签名，将投票过程转化为阈值签名过程，并将该过程与Raft算法的AppendEntries消息和RequestVote消息结合，尽可能地减弱容错过程对共识效率的影响；其次，通过增量哈希引入安全状态，保证了日志的不可篡改性；接着引入客户端对Leader节点的动态监控，以避免拜占庭Leader节点消极反馈的发生，进一步保证了算法的活性；最后，由本地多节点仿真实验表明：RBFT算法有效提升了数据吞吐量和可拓展性，并降低了交易延迟.

关键词: Raft算法, BLS签名, 拜占庭容错方法, 安全状态

Abstract: Aiming at the problem of Byzantine fault tolerance (BFT) in the Raft algorithm, a Raft Byzantine fault tolerance (RBFT) algorithm combined with BLS signature is proposed. First, it uses BLS signatures to implement threshold signatures, converts the voting process into a threshold signature process, and combines this process with the Raft algorithm's AppendEntries message and RequestVote message to minimize the impact of the fault-tolerant process on consensus efficiency. Second, it introduces a safe status through the incremental Hash value to ensure the log's tamper-resistibility. Then it provides dynamical monitoring on the leader node so as to avoid the possible negative feedback of Byzantine leader and ensure the liveness of the algorithm. Finally, local multi-node simulation experiments show that the RBFT algorithm could improve the throughput and scalability, and reduce the latency of transactions effectively.

Key words: Raft algorithm, BLS signature, Byzantine fault tolerance (BFT) algorithm, safe status

中图分类号:

TP301

王日宏, 张立锋, 周航, 徐泉清. 一种结合BLS签名的可拜占庭容错Raft算法[J]. 应用科学学报, 2020, 38(1): 93-104.

WANG Rihong, ZHANG Lifeng, ZHOU Hang, XU Quanqing. A Byzantine Fault Tolerance Raft Algorithm Combines with BLS Signature[J]. Journal of Applied Sciences, 2020, 38(1): 93-104.

参考文献

[1] Baird L. The Swirlds hashgraph consensus algorithm:fair, fast, Byzantine fault tolerance[R]. Swirlds-TR-2016-01, 2016.
[2] Swan M. Blockchain:blueprint for a new economy[M]. O0Reilly Media, Inc., 2015.
[3] Oki B M, Liskov B H. Viewstamped replication:a new primary copy method to support highly-available distributed systems[C]//Proceedings of the seventh annual ACM Symposium on Principles of Distributed Computing, 1988:8-17.
[4] Lamport L. The part-time parliament[J]. ACM Transactions on Computer Systems, 1998, 16(2):133-169.
[5] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014{USENIX}Annual Technical Conference ({USENIX}{ATC}14), 2014:305-319.
[6] Morgan J. Quorum:a permissioned implementation of Ethereum supporting data privacy[EB/OL].[2016-09]. https://github.com/jpmorganchase/quorumdocs/raw/master/Blockchain_QuorumHyperledger_20160922.pdf.
[7] Cowling J, Myers D, Liskov B, et al. HQ replication:a hybrid quorum protocol for Byzantine fault tolerance[C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation, 2006:177-190.
[8] Kotla R, Alvisi L, Dahlin M, et al. Zyzzyva:speculative Byzantine fault tolerance[C]//ACM SIGOPS Operating Systems Review, 2007:45-58.
[9] Hendricks J, Sinnamohideen S, Ganger G R, et al. Zzyzx:scalable fault tolerance through byzantine locking[C]//2010 IEEE/IFIP International Conference on Dependable Systems&Networks (DSN), 2010:363-372.
[10] Veronese G S, Correia M, Bessani A N, et al. Spin one's wheels Byzantine fault tolerance with a spinning primary[C]//28th IEEE International Symposium on Reliable Distributed Systems, 2009:135-144.
[11] Chun B G, Maniatis P, Shenker S, et al. Attested append-only memory:making adversaries stick to their word[C]//ACM SIGOPS Operating Systems Review, 2007:189-204.
[12] Veronese G S, Correia M, Bessani A N, et al. Efficient Byzantine fault-tolerance[J]. IEEE Transactions on Computers, 2011, 62(1):16-30.
[13] Kwon J. Tendermint:consensus without mining[EB/OL]. https://tendermint.com/static/docs/tendermint.pdf
[14] Larimer D. Delegated proof-of-stake (DPoS)[R/OL]. Bitshare Whitepaper. 2014. https://whitepaper.io/document/388/bitshares-whitepaper
[15] Ahmed S. A scalable Byzantine fault tolerant secure domain name system[D]. Cambridge:Massachusetts:Massachusetts Institute of Technology, 2001.
[16] Kim Y, Jo J Y. Dynamically adjusting the mining capacity in cryptocurrency with binary blockchain[J]. International Journal of Networked and Distributed Computing, 2018, 6(1):43.
[17] Miller A, Xia Y, Croman K, et al. The honey badger of BFT protocols[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016:31-42.
[18] Kurosawa K. Advances in cryptology[C]//ASIACRYPT 2007:13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2-6, 2007.[S.l.]:Springer, 2007:4833-4839.
[19] Fox A, Brewer E A. Harvest, yield, and scalable tolerant systems[C]//Proceedings of the Seventh Workshop on Hot Topics in Operating Systems, 1999:174-178.
[20] Kokoris-kogias E, Jovanovic P, Gasser L, et al. Omniledger:a secure, scale-out, decentralized ledger via sharding[C]//2018 IEEE Symposium on Security and Privacy (SP), 2018:583-598.
[21] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process[R]. Massachusetts Inst of Tech Cambridge lab for Computer Science, 1982.
[22] Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11):612-613.
[23] Cachin C, Guerraoui R, Rodrigues L. Introduction to reliable and secure distributed programming[M].[S.l.]:Springer Science&Business Media, 2011.

一种结合BLS签名的可拜占庭容错Raft算法

A Byzantine Fault Tolerance Raft Algorithm Combines with BLS Signature

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	叶旸, 张雪凡, 刘源, 王臣, 黄庆. 基于智能可穿戴设备的乐音对比算法[J]. 应用科学学报, 2017, 35(6): 706-716.
[2]	杨绍文, 闫光辉, 李雷, 张海涛. 基于活跃点的社区跟踪算法[J]. 应用科学学报, 2017, 35(5): 602-611.
[3]	姜长泓, 张永恒, 王盛慧. 基于改进粒子群优化算法的PID控制器参数优化[J]. 应用科学学报, 2017, 35(5): 667-674.
[4]	李军华, 刘群芳. 基于稀疏A*算法与文化算法的无人机动态航迹规划[J]. 应用科学学报, 2017, 35(1): 128-138.
[5]	高洪元1，曹金龙2. 认知无线电中的量子蛙跳频谱分配[J]. 应用科学学报, 2014, 32(1): 19-26.
[6]	闫春钢1;2，汪明新1;2，刘关俊1;2. 有界Petri 网进程表达式与活性的关系[J]. 应用科学学报, 2012, 30(4): 387-390.
[7]	郎利影，夏飞佳. 人脸识别中的零范数稀疏编码[J]. 应用科学学报, 2012, 30(3): 281-286.
[8]	杜航原，郝燕玲，赵玉新，陈立娟. Cholesky 分解在协方差矩阵恢复中的使用[J]. 应用科学学报, 2012, 30(2): 187-193.
[9]	徐庆征，王磊，何宝民，王娜. 基于当前最优解的反向差分进化算法求解函数优化问题[J]. 应用科学学报, 2011, 29(3): 308-315.
[10]	梅蓉，吴庆宪，姜长生. 超混沌系统滑模自适应同步控制及其在保密通信中的应用[J]. 应用科学学报, 2010, 28(2): 115-122.
[11]	胡越黎;计慧杰. 短期电力负荷预测的模糊神经网络方法[J]. 应用科学学报, 2009, 27(1): 79-83 .
[12]	侯静, 宋安平, 王卓, 张武, 李园园, 李亦学. 图形聚类算法的代谢网络模块化分析[J]. 应用科学学报, 2006, 24(6): 588-592.
[13]	陈政洪, 郁松年. 一个基于QR分解的并行原-对偶内点算法[J]. 应用科学学报, 2004, 22(4): 549-552.
[14]	业宁, 梁作鹏, 董逸生. 基于蚁群算法的Web站点导航[J]. 应用科学学报, 2003, 21(4): 357-361.
[15]	宋爱波, 庄晓青, 何洁月, 业宁, 董逸生. 图书馆大规模日志数据的快速聚类[J]. 应用科学学报, 2003, 21(3): 284-288.