Byzantine Algorithm for Collaborative Optimization of Recommendation Reputation Model and Cluster Analysis

doi:10.3778/j.issn.1002-8331.2310-0150

Abstract

Abstract: A modified Byzantine fault-tolerant algorithm based on recommendation reputation model and clustering analysis is proposed to address the issues of random selection of main nodes, communication complexity, and high consensus delay in traditional PBFT (practical Byzantine fault tolerance) consensus algorithm. Firstly, based on the recommendation reputation model, the global trust value of nodes is calculated using the transaction behavior between nodes. On this basis, using global trust values to divide nodes into consensus nodes, non consensus nodes, and main group nodes, and making the node with the highest global trust value the main node can greatly reduce the probability of malicious nodes becoming the main node, thereby improving the efficiency of the system. Finally, after each round of consensus, the consensus nodes are clustered and divided based on their characteristics, further updating the global trust value of the nodes. Through simulation experiment analysis, it is found that the improved TK-PBFT algorithm reduces consensus latency by 25%, reduces communication overhead costs by more than 50%, and has higher throughput.

Key words: consensus algorithm, practical Byzantium, reputation model, blockchain

摘要： 针对传统PBFT（practical Byzantine fault tolerance）共识算法主节点随机选择、通信复杂度和共识时延高等问题，提出了一种基于推荐信誉模型和聚类分析的改进拜占庭容错算法。根据推荐信誉模型，利用节点之间的交易行为计算出节点的全局信任值。在此基础上，利用全局信任值将节点划分为共识节点，非共识节点以及主组节点，并使全局信任值最高的节点成为主节点，可以大大降低恶意节点成为主节点的概率，从而提高了系统的效率。在每一轮共识结束后，对共识节点根据其特征进行聚类划分，进一步更新节点的全局信任值。通过仿真实验分析得出，改进后的TK-PBFT算法的共识时延降低了25%，通信开销成本减少超过50%，且具有更高的吞吐量。

关键词: 共识算法, 实用拜占庭, 信誉模型, 区块链

LI Heji, WANG Chuanhua, XU Xin. Byzantine Algorithm for Collaborative Optimization of Recommendation Reputation Model and Cluster Analysis[J]. Computer Engineering and Applications, 2024, 60(24): 282-290.

李合计, 王传华, 徐欣. 推荐信誉模型与聚类分析协同优化的拜占庭算法[J]. 计算机工程与应用, 2024, 60(24): 282-290.

References

[1] 袁勇, 王飞跃. 区块链技术发展现状与展望[J]. 自动化学报, 2016, 42(4): 481-494.
YUAN Y, WANG F Y. Blockchain: the state of the art and future trends[J]. Acta Automatica Sinica, 2016, 42(4): 481-494.
[2] ALMESHAL T A, ALHOGAIL A A. Blockchain for businesses: a scoping review of suitability evaluations frameworks[J]. IEEE Access, 2021, 9(1): 155425-155442.
[3] 杨婷, 庞晓琼, 陈文俊, 等. 区块链环境下支持隐私保护的数字权限管理[J]. 计算机工程与应用, 2020, 56(23): 109-115.
YANG T, PANG X Q, CHEN W J, et al. Digital rights management supporting privacy protection in blockchain environment[J]. Computer Engineering and Applications, 2020, 56(23): 109-115.
[4] MIGUEL C, BARBARA L. Practical Byzantine fault tolerance[C]//Proceedings of the 3rd Symposium on Operating Systems Design and Implementation. Berkeley: USENIX Association, 1999: 173-186.
[5] 袁勇, 倪晓春, 曾帅, 等. 区块链共识算法的发展现状与展望[J]. 自动化学报, 2018, 44(11): 2011-2022.
YUAN Y, NI X C, ZENG S, et al. Blockchain consensus algorithms: the state of the art and future trends[J]. Acta Automatica Sinica, 2018, 44(11): 2011-2022.
[6] JAKOBSSON M, JUELS A. Proofs of work and bread pudding protocols[C]//Proceedings of Secure Information Networks: Communications and Multimedia Security IFIP TC6/TC11 Joint Working Conference on Communications and Multimedia Security (CMS’99), Leuven, Belgium, September 20-21, 1999. Boston, MA: Springer US, 1999: 258-272.
[7] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm[C]//Proceedings of 2014 USENIX Annual Technical Conference (USENIX ATC 14), 2014: 305-319.
[8] LAMPORT L. The part-time parliament[J]. ACM Transactions on Computer Systems (TOCS), 2019, 16(2): 133-169.
[9] GAO S, YU T, ZHU J, et al. T-PBFT: an EigenTrust-based practical Byzantine fault tolerance consensus algorithm[J]. China Communications, 2019, 16(12): 111-123.
[10] 唐宏, 刘双, 酒英豪, 等. 实用拜占庭容错算法的改进研究[J]. 计算机工程与应用, 2022, 58(9): 144-150.
TANG H, LIU S, JIU Y H, et al. Improved study of practical Byzantine fault-tolerant algorithm[J]. Computer Engineering and Applications, 2022, 58(9): 144-150.
[11] 赖英旭, 薄尊旭, 刘静. 基于改进PBFT算法防御区块链中sybil攻击的研究[J]. 通信学报, 2020, 41(9): 104-117.
LAI Y X, BO Z X, LIU J. Research on sybil attack in defense blockchain based on improved PBFT algorithm[J]. Journal on Communications, 2020, 41(9): 104-117.
[12] 吴晓彤, 柳平增. 基于备选投票机制的低时延PBFT改进研究[J]. 计算机工程, 2021, 47(7): 117-125.
WU X T, LIU P Z. Delay optimization for PBFT based on alternative voting mechanism[J]. Computer Engineering, 2021, 47(7): 117-125.
[13] BRACHA G, TOUEG S. Asynchronous consensus and broadcast protocols[J]. Journal of the ACM (JACM), 1985, 32(4): 824-840.
[14] KAMVAR S D, SCHLOSSER M T, GARCIA-MOLINA H. The eigentrust algorithm for reputation management in p2p networks[C]//Proceedings of the 12th International Conference on World Wide Web, 2003: 640-651.
[15] 毛典辉. 基于MapReduce的Canopy-Kmeans改进算法[J]. 计算机工程与应用, 2012, 48(27): 22-26.
MAO D H. Improved Canopy-Kmeans algorithm based on MapReduce[J]. Computer Engineering and Applications, 2012, 48(27): 22-26.
[16] PELLEG D, MOORE A. Accelerating exact k-means algorithms with geometric reasoning[C]//Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999: 277-281.
[17] JIANG W, WU X, SONG M, et al. Improved PBFT algorithm based on comprehensive evaluation model[J]. Applied Sciences, 2023, 13(2): 1117-1132.
[18] 季钰翔, 黄建华, 王喆, 等. 基于信任度匹配的改进PBFT共识算法[J]. 计算机科学, 2021, 48(2): 303-310.
JI Y X, HUANG J H, WANG Z, et al. Improved PBFT consensus algorithm based on trust matching[J]. Computer Science, 2021, 48(2): 303-310.