基于k-means的动态多组织PBFT算法  

Dynamic multi-organizational PBFT algorithm based on k-means

作　　者：杨雨浓 唐凌翔 王洪[2] YANG Yunong;TANG Lingxiang;WANG Hong(College of Computer and Information Science,Chongqing Normal University,Chongqing 401331,P.R.China;Digital Education Engineering Center for Technology and Applied Research,Chongqing Normal University,Chongqing 401331,P.R.China)

机构地区：[1]重庆师范大学计算机与信息科学学院,重庆401331 [2]重庆师范大学数字教育工程与应用研究中心,重庆401331

出　　处：《重庆大学学报》2024年第7期125-139,共15页Journal of Chongqing University

基　　金：重庆市教委科学技术研究项目(KJZD-K202300515)。

摘　　要：联盟区块链系统被广泛用于金融和物流等场景。现有应用于区块链系统的实用拜占庭算法(practical Byzantine fault tolerance,PBFT)存在可扩展性较低及通信成本较高等问题,阻碍了区块链系统在大规模场景中的应用。针对上述问题,提出了一种动态多组织实用拜占庭容错算法(k-means-practical Byzantine fault tolerance,k-PBFT)。通过改进k-means算法,根据节点的时延以及节点间通信距离将节点分为多个自治组织,各组织之间通过组织代表节点进行通信。当新节点加入时,根据其特点将其分配到最合理的组织。同时,引入信誉机制以辨别系统中的诚实节点与恶意节点,从而提高系统的安全性。此外,该算法还引入节点任期机制,使区块链中每个诚实节点都有机会充当组织代表节点或主节点。实验结果表明,与PBFT算法相比,k-PBFT算法通信复杂度降低了75%;当节点数为100时,相比于PBFT算法,时延降低了210 ms,吞吐量提高了100%。在高延迟环境下,相较于基于信誉分组的PBFT改进算法,当节点数为100时,时延降低了20%,吞吐量提高了17%。Federated blockchain systems find widely application in fields such as finance and logistics.However,the practical Byzantine fault tolerance(PBFT)algorithm,commonly applied to these systems,encounters challenges of low scalability and high communication cost,limiting its effectiveness in large-scale scenarios.To address these issues,the k-PBFT consensus algorithm,a dynamic multi-organizational practical Byzantine fault-tolerant algorithm,is proposed.The k-PBFT algorithm leverages an enhanced k-means algorithm to partition nodes into multiple autonomous organizations based on node time delays and communication distances.Each organization communicates through designated representative nodes.When a new node joins,it is assigned to the most suitable organization based on its characteristics.Additionally,the k-PBFT algorithm improves system security by introducing a reputation mechanism to distinguish honest nodes from malicious ones.It also implements a node tenure mechanism,giving honest node in the blockchain the opportunity to serve as representative or master node within an organization.Experimental results show significant improvements over the PBFT algorithm:the k-PBFT algorithm reduces communication complexity by 75%,decreases latency by 210 ms,and increases throughput by 100%with 100 nodes.In high-latency environments,the k-PBFT algorithm reduces latency by 20%and boosts throughput by 17%compared to the improved PBFT algorithm based on reputation grouping with 100 nodes.

关 键 词：区块链 拜占庭容错算法 K-MEANS算法 信誉机制 节点任期机制 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]