基于树形拓扑网络的实用拜占庭容错共识算法

doi:10.3969/j.issn.0255-8297.2020.01.003

应用科学学报 ›› 2020, Vol. 38 ›› Issue (1): 34-50.doi: 10.3969/j.issn.0255-8297.2020.01.003

基于树形拓扑网络的实用拜占庭容错共识算法

包振山¹, 王凯旋¹, 张文博^1,2

1. 北京工业大学信息学部, 北京 100124;
2. 可信计算北京市重点实验室, 北京 100124

收稿日期:2019-10-31 出版日期:2020-01-31 发布日期:2020-01-19
作者简介:张文博,博士,讲师,研究方向为异构计算、可信计算、区块链技术.E-mail:zhangwenbo@bjut.edu.cn
基金资助:
国家自然科学基金（No.91646201）；国家重点研发计划基金（No.2017YFC0803300）资助

A Practical Byzantine Fault Tolerance Consensus Algorithm Based on Tree Topological Network

BAO Zhenshan¹, WANG Kaixuan¹, ZHANG Wenbo^1,2

1. Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China;
2. Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

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

摘要/Abstract

摘要： 实用拜占庭容错算法在节点数量较多的广域网环境下存在性能瓶颈.为提高该算法的可扩展性，基于树形拓扑网络将全网范围共识拆分为若干子网范围共识；同时引入信誉模型以降低错误节点在共识过程中的影响力，提高系统的安全性、容错性与可靠性.实验结果表明：所提算法的性能明显优于原有算法，表现出良好的可扩展性，可用于大规模许可链系统.

关键词: 许可链, 共识算法, 实用拜占庭容错, 树形拓扑网络, 信誉模型

Abstract: The practical Byzantine fault tolerance (PBFT) algorithm suffers its performance bottleneck in wide-area networks with a large number of nodes. In order to improve the scalability of the algorithm, we propose to divide the whole network consensus into several subnetwork consensus based on tree topology network. At the same time, a reputation model is introduced to reduce the influence of fault nodes in the consensus process and improve the security, fault tolerance and reliability of the system. Experimental results show that the performance of the proposed algorithm is significantly improved comparing with the original one, showing good scalability and applicability to large-scale permissioned blockchain system.

Key words: permissioned blockchain, consensus algorithm, practical Byzantine fault tolerance (PBFT), tree topological network, reputation model

中图分类号:

TP311.13

包振山, 王凯旋, 张文博. 基于树形拓扑网络的实用拜占庭容错共识算法[J]. 应用科学学报, 2020, 38(1): 34-50.

BAO Zhenshan, WANG Kaixuan, ZHANG Wenbo. A Practical Byzantine Fault Tolerance Consensus Algorithm Based on Tree Topological Network[J]. Journal of Applied Sciences, 2020, 38(1): 34-50.

参考文献

[1] 袁勇,王飞跃.区块链技术发展现状与展望[J].自动化学报,2016, 42(4):3-16. Yuan Y, Wang F Y. Current situation and prospect of blockchain technology[J]. Acta Automatica Sinica, 2016, 42(4):3-16.(in Chinese)
[2] 袁勇,倪晓春,曾帅,等.区块链共识算法的发展现状与展望[J].自动化学报, 2018, 44(11):93-104. Yuan Y, Ni X C, Zeng S, et al. Development status and prospect of block chain consensus algorithm[J]. Acta Automatica Sinica, 2018, 44(11):93-104.(in Chinese)
[3] Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3):382-401.
[4] Nakamoto S. Bitcoin:a peer-to-peer electronic cash system[EB/OL].[2019-12-23]. http://bitcoin.org/bitcoin.pdf.
[5] Douceur J R. The sybil attack[C]//International Workshop on Peer-to-Peer Systems, Cambridge, MA, USA, March, 2002:251-260.
[6] Croman K, Decker C, Eyal I, et al. On scaling decentralized blockchains[C]//International Conference on Financial Cryptography and Data Security, Christ Church, Barbados, February 2016:106-125.
[7] Bentov I, Gabizon A, Mizrahi A. Cryptocurrencies without proof of work[C]//International Conference on Financial Cryptography and Data Security, Christ Church, Barbados, February, 2016:142-157.
[8] Larimer D. Delegated proof-of-stake (DPOS)[J]. Bitshare Whitepaper, 2014.
[9] Wood G. Ethereum:a secure decentralised generalised transaction ledger[J]. Ethereum Project Yellow Paper, 2014, 151:1-32.
[10] Lamport L. The part-time parliament[J]. ACM Transactions on Computer Systems, 1998, 16(2):133-169.
[11] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 USENIX Annual Technical Conference, Philadelphia, PA, June, 2014:305-319.
[12] Castro M, Liskov B. Practical Byzantine fault tolerance[C]//Proceedings of the Third Symposium on Operating Systems Design and Implementation, Cambridge, MA, 1999, 99:173-186.
[13] Veronese G S, Correia M, Bessani A N, et al. Efficient Byzantine fault-tolerance[J]. IEEE Transactions on Computers, 2011, 62(1):16-30.
[14] Kapitza R, Behl J, Cachin C, et al. CheapBFT:resource-efficient Byzantine fault tolerance[C]//Proceedings of the 7th ACM European conference on Computer Systems, Bern, Switzerland, April, 2012:295-308.
[15] Liu J, Li W, Karame G O, et al. Scalable Byzantine consensus via hardware-assisted secret sharing[J]. IEEE Transactions on Computers, 2018, 68(1):139-151.
[16] Gueta G G, Abraham I, Grossman S, et al. SBFT:a scalable and decentralized trust infrastructure[C]//201949th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), Portland, OR, USA, June, 2019:568-580.
[17] Distler T, Cachin C, Kapitza R. Resource-efficient Byzantine fault tolerance[J]. IEEE Transactions on Computers, 2015, 65(9):2807-2819.
[18] Jalalzai M M, Busch C, Richard III G. Proteus:a scalable BFT consensus protocol for blockchains[J/OL]. arXiv preprint arXiv, 2019, 1903.04134.
[19] Meng Y, Cao Z, Qu D. A committee-based Byzantine consensus protocol for blockchain[C]//2018 IEEE 9th International Conference on Software Engineering and Service Science (ICSESS), Beijing, China, November, 2018:1-6.
[20] Long J, Wei R. Scalable BFT consensus mechanism through aggregated signature gossip[C]//2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), Seoul, Korea (South), May, 2019:360-367.
[21] Fan X. Scalable practical Byzantine fault tolerance with short-lived signature schemes[C]//Proceedings of the 28th Annual International Conference on Computer Science and Software Engineering, Markham, Ontario, Canada, October, 2018:245-256.
[22] Thai Q T, Yim J C, Yoo T W, et al. Hierarchical Byzantine fault-tolerance protocol for permissioned blockchain systems[J]. The Journal of Supercomputing, 2019, 75(11):7337-7365.
[23] Nawab F, Sadoghi M. Blockplane:a global-scale Byzantizing middleware[C]//2019 IEEE 35th International Conference on Data Engineering (ICDE), Macao, Macao, April, 2019:124-135.
[24] Gai K, Wu Y, Zhu L, et al. Privacy-preserving energy trading using consortium blockchain in smart grid[J]. IEEE Transactions on Industrial Informatics, 2019, 15(6):3548-3558.
[25] Gai K, Wu Y, Zhu L, et al. Permissioned blockchain and edge computing empowered privacypreserving smart grid networks[J]. IEEE Internet of Things Journal, 2019, 6(5):7992-8004.
[26] Zhu L, Wu Y, Gai K, et al. Controllable and trustworthy blockchain-based cloud data management[J]. Future Generation Computer Systems, 2019, 91:527-535.
[27] 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.
[28] Sorensen D. Establishing standards for consensus on blockchains[C]//International Conference on Blockchain, San Diego, CA, USA, June, 2019:18-33.
[29] Dwork C, Lynch N, Stockmeyer L. Consensus in the presence of partial synchrony[J]. Journal of the ACM, 1988, 35(2):288-323.
[30] 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, Vienna, Austria, 2016:31-42.
[31] Xu H, Long Y, Liu Z, et al. Dynamic practical Byzantine fault tolerance[C]//2018 IEEE Conference on Communications and Network Security (CNS), Beijing, China, 2018:1-8.
[32] Androulaki E, Barger A, Bortnikov V, et al. Hyperledger fabric:a distributed operating system for permissioned blockchains[C]//Proceedings of the Thirteenth EuroSys Conference, Porto, Portugal, 2018:30.
[33] Anderson C. Docker[software engineering] [J]. IEEE Software, 2015, 32(3):102-c3.

基于树形拓扑网络的实用拜占庭容错共识算法

A Practical Byzantine Fault Tolerance Consensus Algorithm Based on Tree Topological Network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	何正源, 段田田, 张颖, 张瀚文, 孙毅. 物联网中区块链技术的应用与挑战[J]. 应用科学学报, 2020, 38(1): 22-33.
[2]	王文奇, 潘恒, 潘磊, 关云云. 基于区块链的电子仓单可信存储技术[J]. 应用科学学报, 2020, 38(1): 105-118.
[3]	杨凯，马建峰，杨超. 一种新的无线网状网可信路由[J]. 应用科学学报, 2011, 29(3): 221-227.
[4]	王堃吴蒙. P2P网络中一种可信任的全局信誉模型[J]. 应用科学学报, 2010, 28(3): 237-245.