Abstract: Since Practical Byzantine Fault Tolerance （PBFT） consensus algorithm applied to consortium blockchain has the problems of insufficient scalability and high communication overhead， an improved practical Byzantine fault tolerance consensus algorithm based on Raft algorithm named K-RPBFT （K-medoids Raft based Practical Byzantine Fault Tolerance） was proposed. Firstly， blockchain was sharded based on K-medoids clustering algorithm， all nodes were divided into multiple node clusters and each node cluster constituted to a single shard， so that global consensus was improved to hierarchical multi-center consensus. Secondly， the consus between the cluster central nodes of each shard was performed by adopting PBFT algorithm， and the improved Raft algorithm based on supervision nodes was used for intra-shard consensus. The supervision mechanism in each shard gave a certain ability of Byzantine fault tolerance to Raft algorithm and improved the security of the algorithm. Experimental analysis shows that compared with PBFT algorithm， K-RPBFT algorithm greatly reduces the communication overhead and consensus latency， improves the consensus efficiency and throughput while having Byzantine fault tolerance ability， and has good scalability and dynamics， so that the consortium blockchain can be applied to a wider range of fields.

Key words: blockchain, consensus algorithm, Practical Byzantine Fault Tolerance (PBFT), Raft algorithm, K-medoids clustering algorithm

摘要： 针对应用于联盟链的实用拜占庭容错（PBFT）共识算法可扩展性不足、通信开销大等问题，提出了一种基于Raft算法改进的实用拜占庭容错共识算法K-RPBFT。首先，将区块链分片，使用K-medoids聚类算法将所有节点划分为多个节点簇，每个节点簇构成一个分片，从而将全局共识改进为分层次的多中心共识；然后，每个分片的聚类中心节点之间使用PBFT算法进行共识，而在分片内部使用基于监督节点改进的Raft算法进行共识。K-RPBFT算法的片内监督机制赋予了Raft算法一定的拜占庭容错能力，并提升了算法的安全性。实验分析表明，相较于PBFT算法，K-RPBFT算法在具备拜占庭容错能力的同时能够大幅降低共识的通信开销与共识时延，提升共识效率与吞吐量，并且具有良好的可扩展性与动态性，使联盟链能够应用于更广泛的场景中。

关键词: 区块链, 共识算法, 实用拜占庭容错, Raft算法, K中心点聚类算法