Abstract: Compared with Raft and Paxos, the original consensus algorithm, i.e., the Practical Byzantine Fault Tolerant(PBFT) algorithm, is mainly aimed at malicious nodes in a distributed system used to send error messages to other nodes, disturbing the normal operation of the entire system.This algorithm fundamentally solves the Byzantine problem of the system.However, the PBFT algorithm itself has the problem of a low consensus efficiency caused by an arbitrary primary node election.Meanwhile, existing improved algorithms generally have problems of a high communication complexity and centralization tendency.Aiming at these problems, an improved consensus algorithm, RN-VPBFT, is proposed based on reputation value voting and random number election.First, by adding supervision nodes, the algorithm realizes a decentralization of rights and an information transfer and ensures the safe operation of the system.A random parameter is then introduced during the process of voting to determine the initial reputation value, and thus the reputation value is no longer the only criterion for selecting the master node.All nodes that meet certain conditions have an equal chance to be selected as the master node.This can reduce the trend of system centralization.Finally, the algorithm establishes the dynamic reputation model of the nodes to distinguish between honest and malicious nodes in the system, simplify the consistency protocol of the consensus algorithm, and reduce the communication complexity of the entire algorithm.Experimental results show that, compared with the original PBFT algorithm and the existing improved PBFT algorithm based on reputation voting, the RN-VPBFT algorithm can reduce the communication complexity from O(N²) to O(N).The final difference in reputation of all honesty nodes is only 0.02, which is almost negligible.Therefore, the proposed algorithm has a lower communication complexity and better decentralization.

Key words: blockchain, consensus algorithm, Practical Byzantine Fault Tolerant(PBFT) algorithm, reputation value voting, random number election

摘要： 实用拜占庭容错（PBFT）算法在Raft和Paxos共识算法的基础上，解决了分布式系统中恶意节点向其他节点发送错误消息以扰乱系统正常运行的问题，但PBFT算法由于主节点选举随意导致共识效率低下，而现有PBFT改进算法普遍通信复杂度较高且容易出现系统集中化趋势。针对上述问题，提出一种基于信誉值投票与随机数选举的RN-VPBFT共识算法。通过增设监督节点，实现权力分散和信息中转，保证系统安全运行。在投票确定初始信誉值的过程中，引入随机参数使得满足条件的节点均有机会当选主节点，缓解系统集中化趋势。建立节点动态信誉模型，区分系统中的诚实节点与恶意节点，简化共识算法的一致性协议，降低算法通信复杂度。实验结果表明，与PBFT算法和基于信誉投票的PBFT改进算法相比，RN-VPBFT算法将通信复杂度由O（N²）降至O（N），并且所有诚实节点的信誉值之差仅为0.02，具有更低的通信复杂度及更好的去中心化特性。

关键词: 区块链, 共识算法, 实用拜占庭容错算法, 信誉值投票, 随机数选举

CLC Number: 

• TP311