基于K-medoids的改进PBFT共识机制

doi:10.11896/jsjkx.181002014

摘要/Abstract

摘要： 随着数字货币的普及与发展,区块链技术进入了大众的视野,并被誉为信用历史上第四个里程碑,是未来信用的基石^[1]。但与此同时,区块链技术也面临着共识效率低、算力浪费等问题。文中利用K-medoids聚类算法对参与区块链共识的大规模网络节点根据特征进行聚类与层次划分,再将改进的多中心化实用拜占庭容错算法应用于这种聚类后的分层模型中。另外,为了提升聚类算法在多种场景下对区块链模型中共识节点进行聚类的可控性,对K-medoids算法进行了改进。网络拓扑仿真环境实验表明,当选择了适当的聚类特征评判节点间的相似度时,改进后的算法K-PBFT在1000个网络节点参与共识的场景中相较于传统实用拜占庭容错算法(Practical Byzantine Fault Tolerance,PBFT)算法,单次共识耗时缩短了20%,共识过程的通信次数最佳能够降低3个数量级。结果证明K-PBFT算法优化了较大规模共识节点参与的共识过程,使区块链模型能够适用于更广泛的场景中。

关键词: K-medoids, 聚类算法, 区块链, 实用拜占庭容错算法

Abstract: With the popularization and development of digital currency,the blockchain technology enters the public’s vision,and has been hailed as the fourth milestone in credit history,the cornerstone of future credit^[1].However,blockchain technology is also facing problems such as low efficiency of consensus and waste of computing power.The K-medoids clustering algorithm is used to cluster and hierarchically divide the large scale network nodes participating in the blockchain consensus based on features,and then the improved multi-centered PBFT (Practical Byzantine Fault Tole-rance) consensus algorithm is applied to the clustered model.Moreover,in order to improve the controllability of clustering algorithm to cluster nodes in blockchain model under various scenarios,this paper improved K-medoids algorithm.Simulation results show that when appropriate clustering features are selected to evaluate the similarity between nodes,the improved algorithm K-PBFT reduces the single-consensus time consumption by 20%,and the consensus process communication times can be reduced by three orders of magnitude.The experimental results show that K-PBFT optimizes the consensus process involving large-scale nodes,so that the blockchain technology can be applied to a wider range of application scenarios.

Key words: Blockchain, Clustering algorithm, K-medoids, Practical byzantine fault tolerance

中图分类号:

TP301

陈子豪, 李强. 基于K-medoids的改进PBFT共识机制[J]. 计算机科学, 2019, 46(12): 101-107. https://doi.org/10.11896/jsjkx.181002014

CHEN Zi-hao, LI Qiang. Improved PBFT Consensus Mechanism Based on K-medoids[J]. Computer Science, 2019, 46(12): 101-107. https://doi.org/10.11896/jsjkx.181002014

参考文献

[1]SWAN M.Blockchain:Blueprint for a New Economy[M]. USA:O’Reilly Media Inc,2015:45-68.
[2]中国人民银行.中国人民银行数字货币研讨会召开[OL].http://www.pbc.gov.cn/goutongjiaoliu/113456/113469/3008070/index.html.
[3]YUAN Y,WANG F Y.Blockchain:The State of the Art and Future Trends[J].Acta Automatica Sinica,2016,42(4):481-494.(in Chinese)
袁勇,王飞跃.区块链技术发展现状与展望[J].自动化学报,2016,42(4):481-494.
[4]LAMPORT L,SHOSTAK R,PEASE M.The Byzantine gene- rals problem [J].ACM Transactions on Programming Languages and Systems,1982,4(3):382-401.
[5]Delegated Proof-of-Stake Consensus[EB/OL].[2018-07-10]. https://bitshares.org/technology/delegated-proof-of-stake-con-sensus/.
[6]邹均.区块链技术指南[M].北京:机械工业出版社,2016:109-128.
[7]CASTRO M,LISKOV B.Practical byzantine fault tolerance and proactive recovery[J].Acm Transactions on Computer Systems,2002,20(4):398-461.
[8]ANDROULAKI E,BARGER A,BORTNIKOV V,et al.Hy- perledger fabric:a distributed operating system for permissioned blockchains[C]//Proceedings of the Thirteenth EuroSys Conference.ACM,2018:30.
[9]李明轩.区块链投资人李明轩:区块链通过多中心化机制解决传统互联网问题[EB/OL].http://www.sohu.com/a/271184292_100133330.
[10]YUAN Y,NI X C,ZENG S,et al.Development Status and Prospect of Blockchain Consensus Algorithm[J].Acta Automatica Sinica,2018,44(11):2011-2022.
[11]NI X,ZENG S,HAN X,et al.Organizational management using software-defined robots based on smart contracts[C]//2018 IEEE Intelligent Vehicles Symposium (IV).IEEE,2018:274-279.
[12]WANG S,YUAN Y,WANG X,et al.An overview of smart contract:architecture,applications,and future trends[C]//2018 IEEE Intelligent Vehicles Symposium (IV).IEEE,2018:108-113.
[13]IRVING G,HOLDEN J.How blockchain-timestamped proto- cols could improve the trustworthiness of medical science[J].F1000 Research,2016,5:222.
[14]PAPADOPOULOS G.Blockchain and Digital Payments:An Institutionalist Analysis of Cryptocurrencies[M].Academic Press,2015:153-172.
[15]DADDA L,MACCHETTI M,OWEN J.The design of a high speed ASIC unit for the hash function SHA-256 (384,512)[C]//Proceedings of the conference on Design,Automation and Test in Europe.IEEE Computer Society,2004.
[16]KATZ J,LINDELL Y.Introduction to Modern Cryptography:Principles and Protocols[M].Chapman and Hall/CRC,2014:207.
[17]BRACHA G,TOUEG S.Asynchronous consensus and broad- cast protocols[J].Journal of the Acm,1985,32(4):824-840.
[18]REITER M K.A Secure Group Membership Protocol[J].IEEE Transactions on Software Engineering,1996,22(1):31-42.
[19]MAO D H.Improved Canopy-Kmeans algorithm based on Map- Reduce[J].Computer Engineering and Applications,2012,48(27):22-26.
[20]PATTABIRAMAN V,PARVATHI R,NEDUNCHEZIAN R,et al.A Novel spatial clustering with obstacles and facilitators constraint based on edge detection and k-medoids[C]//International Conference on Computer Technology and Development,2009(ICCTD’09).IEEE,2009:402-406.
[21]MA Q,XIE J Y.K-medoids clustering algorithm based on particle computing [J].Computer Applications,2012,32(7):1973-1977.
[22]ISSARIYAKUL T,HOSSAIN E.Introduction to Network Si- mulator 2 (NS2)[M]//Introduction to Network Simulator NS2.Springer,Boston,MA,2012:21-40.
[23]CALVERT K,EAGAN J,MERUGU S,et al.Extending and enhancing GT-ITM[C]//ACM SIGCOMM Workshop on Models,Methods and TOOLS for Reproducible Network Research.ACM,2003:23-27.

相关文章 15

[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]	柴慧敏, 张勇, 方敏. 基于特征相似度聚类的空中目标分群方法 Aerial Target Grouping Method Based on Feature Similarity Clustering 计算机科学, 2022, 49(9): 70-75. https://doi.org/10.11896/jsjkx.210800203
[3]	李博, 向海昀, 张宇翔, 廖浩德. 面向食品溯源场景的PBFT优化算法应用研究 Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios 计算机科学, 2022, 49(6A): 723-728. https://doi.org/10.11896/jsjkx.210800018
[4]	周航, 姜河, 赵琰, 解相朋. 适用于各单元共识交易的电力区块链系统优化调度研究 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
[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]	毛典辉, 黄晖煜, 赵爽. 符合监管合规性的自动合成新闻检测方法研究 Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance 计算机科学, 2022, 49(6A): 523-530. https://doi.org/10.11896/jsjkx.210300083
[8]	王思明, 谭北海, 余荣. 面向6G可信可靠智能的区块链分片与激励机制 Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence 计算机科学, 2022, 49(6): 32-38. https://doi.org/10.11896/jsjkx.220400004
[9]	孙浩, 毛瀚宇, 张岩峰, 于戈, 徐石成, 何光宇. 区块链跨链技术发展及应用 Development and Application of Blockchain Cross-chain Technology 计算机科学, 2022, 49(5): 287-295. https://doi.org/10.11896/jsjkx.210800132
[10]	阳真, 黄松, 郑长友. 基于区块链与改进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
[11]	任畅, 赵洪, 蒋华. 一种量子安全拜占庭容错共识机制 Quantum Secured-Byzantine Fault Tolerance Blockchain Consensus Mechanism 计算机科学, 2022, 49(5): 333-340. https://doi.org/10.11896/jsjkx.210400154
[12]	冯了了, 丁滟, 刘坤林, 马科林, 常俊胜. 区块链BFT共识算法研究进展 Research Advance on BFT Consensus Algorithms 计算机科学, 2022, 49(4): 329-339. https://doi.org/10.11896/jsjkx.210700011
[13]	王鑫, 周泽宝, 余芸, 陈禹旭, 任昊文, 蒋一波, 孙凌云. 一种面向电能量数据的联邦学习可靠性激励机制 Reliable Incentive Mechanism for Federated Learning of Electric Metering Data 计算机科学, 2022, 49(3): 31-38. https://doi.org/10.11896/jsjkx.210700195
[14]	张潆藜, 马佳利, 刘子昂, 刘新, 周睿. 以太坊Solidity智能合约漏洞检测方法综述 Overview of Vulnerability Detection Methods for Ethereum Solidity Smart Contracts 计算机科学, 2022, 49(3): 52-61. https://doi.org/10.11896/jsjkx.210700004
[15]	杨昕宇, 彭长根, 杨辉, 丁红发. 基于演化博弈的理性拜占庭容错共识算法 Rational PBFT Consensus Algorithm with Evolutionary Game 计算机科学, 2022, 49(3): 360-370. https://doi.org/10.11896/jsjkx.210900110

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed