基于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: Practical byzantine fault tolerance, K-medoids, Blockchain, Clustering algorithm

中图分类号:

TP301

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

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

参考文献 23

[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]	张煜, 陆亿红, 黄德才. 基于密度峰值的加权犹豫模糊聚类算法[J]. 计算机科学, 2021, 48(1): 145-151.
[2]	张艳梅, 楼胤成. 基于深度神经网络的庞氏骗局合约检测方法[J]. 计算机科学, 2021, 48(1): 273-279.
[3]	邵炜晖, 王宁, 韩传峰, 许维胜. 基于区块链的一体化应急应战机制[J]. 计算机科学, 2021, 48(1): 287-294.
[4]	李莹, 于亚新, 张宏宇, 李振国. 基于TBchain区块链的高可信云存储模型[J]. 计算机科学, 2020, 47(9): 330-338.
[5]	徐守坤, 倪楚涵, 吉晨晨, 李宁. 基于YOLOv3的施工场景安全帽佩戴的图像描述[J]. 计算机科学, 2020, 47(8): 233-240.
[6]	刘帅, 甘国华, 刘明熹, 房勇, 汪寿阳. 一种基于拓扑结构及分配机制设计的多子块激励共识机制[J]. 计算机科学, 2020, 47(7): 268-277.
[7]	陆歌皓, 谢莉红, 李析禹. 区块链共识算法对比研究[J]. 计算机科学, 2020, 47(6A): 332-339.
[8]	洪小玲, 万虎, 肖晓, 孙浩祥. 基于区块链的制造联盟系统[J]. 计算机科学, 2020, 47(6A): 369-374.
[9]	林旭丹, 鲍士兼, 赵立昕, 赵成林. 基于Hyperledger Fabric的汽车供应链系统的方案设计与性能分析[J]. 计算机科学, 2020, 47(6A): 546-551.
[10]	可雨憬, 敬茂华, 郑涵尹. 区块链技术在信托行业的应用研究[J]. 计算机科学, 2020, 47(6A): 591-595.
[11]	任仪. 基于区块链与人工智能的网络多服务器SIP信息加密系统设计[J]. 计算机科学, 2020, 47(6A): 634-638.
[12]	张启明, 陆建华, 李守智, 徐建栋. 基于区块链构建新型企业客户服务技术平台[J]. 计算机科学, 2020, 47(6A): 639-642.
[13]	叶少杰, 汪小益, 徐才巢, 孙建伶. BitXHub:基于侧链中继的异构区块链互操作平台[J]. 计算机科学, 2020, 47(6): 294-302.
[14]	谢英英, 石涧, 黄硕康, 雷凯. 面向5G的命名数据网络物联网研究综述[J]. 计算机科学, 2020, 47(4): 217-225.
[15]	王辉, 刘玉祥, 曹顺湘, 周明明. 融入区块链技术的医疗数据存储机制[J]. 计算机科学, 2020, 47(4): 285-291.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed