拜占庭将军算法

基于投票机制的拜占庭容错共识算法作者：王海勇郭凯璇潘启青来源：《计算机应用》2019年第06期摘要：针对现有的区块链中实用拜占庭容错（PBFT）共识算法、基于动态授权的拜占庭容错（DDBFT）共识算法、联盟拜占庭容错（CBFT）共识算法普遍存在能耗高、效率低、扩展性差等问题，通过引入投票机制，提出了基于投票机制的拜占庭容错（VPBFT）共识算法。

首先，以PBFT算法为基础，将网络中的节点划分为四类具有不同职责的节点。

其次，算法中的投票节点具有投票和评分权，监督生产节点诚实可靠地生产数据块;生产有效的数据块的生产节点优先进入下一轮，候选节点能够被选为生产节点，而普通节点则能够成为投票节点或候选节点。

最后，不同类型的节点之间具有一定的数量关系，能够在不同类型节点的数目或网络中的节点总数发生变化时动态调整参数，从而使得算法适应动态网络。

通过性能仿真分析可知，VPBFT算法相较于PBFT、 DDBFT、CBFT等共识算法，具有低能耗、低时延、高容错性和高动态性。

关键词：区块链;拜占庭容错;投票机制;共识算法;数据块中图分类号： TP301.6文献标志码：AAbstract： Focusing on the problems of high energy consumption， low efficiency and poor scalability of Practical Byzantine Fault Tolerance （PBFT） consensus algorithm， Dynamic authorized Byzantine Fault Tolerance （DDBFT） consensus algorithm and Consortium Byzantine Fault Tolerance （CBFT） consensus algorithm existed in the blockchain， Practical Byzantine Fault Tolerant consensus algorithm based on Voting （VPBFT） was proposed by introducing voting mechanism. Firstly， based on PBFT algorithm， the nodes in the network were divided into four types of nodes with different responsibility. Secondly， the voting nodes in the algorithm had voting and scoring rights to supervise the production nodes to produce data blocks honestly and reliably，the production nodes producing valid data blocks had priority to be selected into next turn， while the candidate nodes were able to be voted as production nodes， and the ordinary nodes were able to be voted as production nodes or candidate nodes. Finally， different types of nodes had a certain quantity relationship between themselves， which means the parameters were able to be dynamically adjusted when the number of different types of nodes or the total number of nodes in the network changed， so that the algorithm was able to adapt to the dynamic network. Through performance simulation analysis， the proposed VPBFT algorithm has low energy consumption， short delay，high fault tolerance and high dynamicity compared with consensus algorithms such as PBFT，DDBFT and CBFT.Key words： blockchain; Byzantine Fault Tolerance （BFT）; voting mechanism; consensus algorithm; data block0 引言自2008年“一種完全通过点对点技术实现的电子现金货币”（即比特币）[1]被提出起，区块链技术正一步一步地得到重视。

共识算法的作用
共识算法的作用主要是确保分布式系统中的节点在进行某些操作时达
成一致。

在分布式系统中，可能有多个节点在同时对系统进行操作，
而这些节点之间的通信存在延迟、不可靠和不同步等问题，因此可能
会导致系统数据的不一致性。

共识算法旨在解决这些问题，确保系统
所有节点对某个特定的操作所达成的结论是一致的，从而保持数据的
完整性。

共识算法的应用范围非常广泛，例如在区块链技术中，共识算法被用
来解决“双花”问题，即同一笔数字货币被同时花费的问题。

在这种
情况下，共识算法可以使所有节点都同意一笔交易是否有效，从而避
免了“双花”问题的产生。

此外，共识算法还被广泛应用于分布式数据库系统、分布式文件系统、分布式存储系统、云计算平台等各种分布式应用领域。

例如，在分布
式数据库系统中，共识算法可以确保多个节点对某个关系型数据库的
修改操作是一致的，从而避免了数据冲突和损坏的问题。

在实际应用中，共识算法往往包括多种不同的实现方式，例如拜占庭
将军问题算法、Raft算法、Paxos算法等。

每一种实现方式都有其独
特的优势和适用场景，需要根据具体应用场景的需求来选择不同的算
法。

总之，共识算法是保障分布式系统中数据一致性的关键技术之一，其应用范围非常广泛，已经成为了分布式计算领域不可或缺的一部分。

2022年5月25日第6卷第10期现代信息科技Modern Information TechnologyMay.2022 Vol.6 No.1016基于信誉值的实用拜占庭容错改进算法研究王启河（华北电力大学 控制与计算机工程学院，河北 保定 071003）摘 要：共识问题是区块链中的核心问题，针对联盟链常用的实用拜占庭容错算法（PBFT ）中主节点选取随意、网络通信量大、公平性较低等问题，提出一种基于信誉值的PBFT 改进算法。

首先改变信誉值主节点选取方式，然后优化共识流程，节点的累计信誉作为判断达成共识的条件。

达成共识时没有参与共识过程的节点或恶意节点的信誉值降低，降低的信誉值均分给成功参与共识的节点。

经过多次共识后，故障或恶意节点对共识的影响变小，提高了算法的公平性。

关键词：联盟链；实用拜占庭容错算法；共识机制；信誉值；公平性中图分类号：TP311.5文献标识码：A文章编号：2096-4706（2022）10-0016-05Research on Improved Algorithm of Practical Byzantine Fault Tolerance Based onReputation ValueWANG Qihe(School of Control and Computer Engineering, North China Electric Power University, Baoding 071003, China)Abstract: The consensus problem is the core problem in the blockchain. In view of the problems of arbitrary master node selection, large amount of network communication and low fairness of the Practical Byzantine Fault Tolerance (PBFT), which is commonly used in coalition chains, an improved algorithm of PBFT based on reputation value is proposed. Firstly, it changes the selection mode of reputation value master node. Then the consensus process is optimized, and the accumulated reputation of nodes is used as a condition to judge reaching consensus. The reputation value of nodes that do not participate in the consensus process or malicious nodes is reduced when consensus is reached, and the reduced reputation value is equally distributed to the nodes that successfully participate in consensus. After multiple consensus, the impact of the fault or malicious node on the consensus becomes small and the fairness of the algorithm is improved.Keywords: coalition chain; practical Byzantine fault tolerant algorithm; consensus mechanism; reputation value; fairness0 引 言近2008年中本聪[1]提出一种点对点的电子现金系统即比特币，使得区块链底层技术得到了社会广泛关注。

2021‑03‑10计算机应用,Journal of Computer Applications 2021,41(3):756-762ISSN 1001‑9081CODEN JYIIDU http ：//检测型的联盟区块链共识算法d -PBFT刘宇1，2，朱朝阳2，3，李金泽1，2，劳源基1，2，覃团发1，2*（1.广西大学计算机与电子信息学院，南宁530004；2.广西多媒体通信与网络技术重点实验室（广西大学），南宁530004；3.华南理工大学电子与信息学院，广州510641）（∗通信作者电子邮箱tfqin@ ）摘要：联盟区块链通常都会采用严格的身份准入机制，但然而该机制不能完全保证联盟网络中不会混入拜占庭恶意节点，也不能担保现有的联盟成员节点一定不会被第三方敌手劫持利用。

针对这类问题，提出了一种能够监控节点状态的检测型实用拜占庭容错（d -PBFT ）共识算法。

首先，选举主节点并校验主节点的其状态，以保证选举出来的主节点从未有过作恶历史；然后，经历“预准备—准备—提交”的共识三阶段过程，尝试来完成客户端提交的共识请求；最后，会根据三阶段完成的情况对主节点的状态进行评估，将有故障或作恶行为的主节点标记出来，并将作恶的主节点加入到隔离区等待处理。

该算法在容忍一定数量拜占庭节点的基础上还能随时监控各个节点的状态，并对恶意节点能够进行隔离，从而降低恶意节点对整个联盟系统的不良影响。

实验结果表明，采用d -PBFT 算法的网络拥有较高的吞吐量和较低的共识时延，并且在联盟网络中有拜占庭节点的情况下相较原实用拜占庭容错（PBFT ）算法的共识生成量提升了26.1%。

d -PBFT 算法不仅提高了联盟网络的健壮性，还进一步提升了网络的吞吐量。

关键词：联盟区块链；拜占庭错误；节点监控；检测型实用拜占庭容错共识算法；吞吐量中图分类号：TP311文献标志码：Ad -PBFT ：detection consensus algorithm for alliance blockchainLIU Yu 1，2，ZHU Chaoyang 2，3，LI Jinze 1，2，LAO Yuanji 1，2，QIN Tuanfa 1，2*（1.School of Computer ，Electronics and Information ，Guangxi University ，Nanning Guangxi 530004，China ；2.Guangxi Key Laboratory of Multimedia Communications and Network Technology （Guangxi University ），Nanning Guangxi 530004，China ；3.School of Electronic and Information Engineering ，South China University of Technology ，Guangzhou Guangdong 510641，China ）Abstract:There is an identity authentication mechanism in alliance blockchain ，but even by using the mechanism ，Byzantine malicious nodes still exist in the network ，and the member nodes in the alliance may be controlled and utilized bythe third -party enemies.To solve these problems ，a detection -Practical Byzantine Fault Tolerance （d -PBFT ）consensus algorithm that can monitor the node states was proposed.Firstly ，the primary node was elected and the its state was checked to ensure that the elected primary node never be malicious before.Secondly ，the consensus request submitted by the client was executed through the three -stage consensus process “pre -prepare -prepare -commit ”.Finally ，the primary node state was assessed according to the three -stage achievement state.If primary node was unstable or malicious ，it would be marked ，and the malicious node would be added to the quarantine to wait for processing.In this algorithm ，based on tolerating a specific number of Byzantine nodes ，every node state was monitored all the time and the malicious nods would be isolated.Inthis case ，the bad impact of malicious nodes on the alliance would be reduced.Experimental results show that the network with d -PBFT algorithm has high throughput and low consensus delay ，and the consensus generation amount of the algorithm is 26.1%more than that of Practical Byzantine Fault Tolerance （PBFT ）algorithm when alliance network includes Byzantinenodes.The d -PBFT algorithm not only improves the robustness of alliance network ，but also improves the network throughput.Key words:alliance blockchain;Byzantine error;node monitoring;detection -Practical Byzantine Fault Tolerance (d -PBFT)consensus algorithm;throughput0引言在用户的信息安全方面，为了保证用户数据的完整性和隐私性，本文将区块链技术应用到其中。

目录1. 共识算法的分类 (1)1.1. 概率一致性算法 (1)1.2. 绝对一致性算法 (2)2. 区块链项目中常用的共识算法 (2)2.1. 工作量证明（Proof-of-Work, PoW） (2)2.2. 权益证明（Proof of Stake, PoS） (4)2.3. 权益授权证明(DPoS) (5)2.4. 实用拜占庭容错(PBFT) (6)2.5. PoW + PoS (7)3. 小结 (7)1. 共识算法的分类共识算法解决的是对某个提案（Proposal），大家达成一致意见的过程。

根据要解决的问题是普通错误还是拜占庭将军问题，将共识算法分为CFT（Crash Fault Tolerance）和BFT（Byzantine Fault Tolerance）。

CFT已有一些经典的解决算法，包括Paxos、Raft及其变种等。

在传统的分布式网络中，各个节点也不会因为贪图利益故意伪造信息，很多情况下是由于网络的原因而掉线或发送错误消息。

因此传统分布式系统中均使用CFT类共识算法。

而BFT则是在区块链系统中常用的共识算法。

根据算法采取的策略，BFT类算法可以被分为两大类，即概率一致性算法和绝对一致性算法。

回顾CAP 原理，两类算法的区别在于对可用性和一致性之间的平衡：概率一致性算法保证了系统的可用性而牺牲了系统的一致性，绝对一致性算法则与之相反，保证了系统的一致性而牺牲了系统的可用性。

1.1. 概率一致性算法概率一致性算法指在不同分布式节点之间，有较大概率保证节点间数据达到一致，但仍存在一定概率使得某些节点间数据不一致。

对于某一个数据点而言，数据在节点间不一致的概率会随时间的推移逐渐降低至趋近于零，从而最终达到一致性。

例如工作量证明算法（Proof of Work, PoW）、权益证明算法（Proof of Stake, PoS）和委托权益证明算法（Delegated Proof of Stake, DPoS）都属于概率一致性算法。

共识算法（Consensus Algorithm）是分布式计算领域中的一个重要概念，用于确保分布式系统中的各个节点之间就某个共同的状态或值达成一致。

共识算法的目标是解决分布式系统中的数据一致性和节点故障恢复等问题。

以下是共识算法的基本概念：一致性：共识算法的核心目标是确保在分布式系统中的所有节点之间达成一致的数据状态。

这意味着无论发生什么情况，系统的不同节点都应该能够就某个值或状态达成一致意见。

容错性：共识算法需要考虑分布式系统中可能出现的节点故障、网络分区和消息丢失等问题。

因此，它通常包括容错机制，以确保即使某些节点出现问题，系统仍能够继续正常运行。

提供一致性服务：共识算法通常作为底层基础设施，为上层应用程序提供一致性服务。

这包括分布式数据库、分布式存储系统和区块链等应用。

协议：共识算法通常涉及节点之间的通信和协作，以达成共识。

它们通常包括通信协议、消息传递、投票过程和决策算法等组成部分。

安全性：共识算法需要确保系统的安全性，包括防止恶意节点的攻击、数据篡改和拜占庭故障等问题。

因此，安全性是共识算法的一个关键考虑因素。

性能：共识算法也需要考虑性能因素，以确保在达成共识时不会对系统的吞吐量和延迟产生过大的影响。

几种常见的共识算法包括：Paxos：一种经典的共识算法，用于分布式系统中的一致性问题。

Raft：一种相对简单的共识算法，旨在提供更好的可理解性。

拜占庭容错共识：用于处理拜占庭故障的共识算法，如拜占庭将军问题。

区块链共识算法：用于区块链技术中的共识，包括工作证明（Proof of Work，PoW）和权益证明（Proof of Stake，PoS）等。

共识算法在分布式系统和区块链技术中扮演着重要角色，它们帮助确保数据一致性、系统安全性和可靠性，从而支持分布式应用的开发和部署。

不同的共识算法适用于不同的场景和需求。

区块链共识算法总结（PBFT，Raft，PoW，PoS，DPoS，Ripple）⽬录正⽂ 近⼏天对区块链中⼏种常见的共识机制（PBFT，Raft，PoW，PoS，DPoS，Ripple）进⾏了总结。

尽量使⽤简单易懂语⾔，篇幅较⼤，想了解的可以只读每个算法介绍中前边的原理。

本篇⽂章主要参考《区块链技术指南》，⾸先表⽰感谢！ ---Begin--- 区块链架构是⼀种分布式的架构。

其部署模式有公共链、联盟链、私有链三种，对应的是去中⼼化分布式系统、部分去中⼼化分布式系统和弱中⼼分布式系统。

在分布式系统中，多个主机通过异步通信⽅式组成⽹络集群。

在这样的⼀个异步系统中，需要主机之间进⾏状态复制，以保证每个主机达成⼀致的状态共识。

然⽽，异步系统中，可能出现⽆法通信的故障主机，⽽主机的性能可能下降，⽹络可能拥塞，这些可能导致错误信息在系统内传播。

因此需要在默认不可靠的异步⽹络中定义容错协议，以确保各主机达成安全可靠的状态共识。

所谓共识，简单理解就是指⼤家都达成⼀致的意思。

其实在现实⽣活中，有很多需要达成共识的场景，⽐如开会讨论，双⽅或多⽅签订⼀份合作协议等。

⽽在区块链系统中，每个节点必须要做的事情就是让⾃⼰的账本跟其他节点的账本保持⼀致。

如果是在传统的软件结构中，这⼏乎就不是问题，因为有⼀个中⼼服务器存在，也就是所谓的主库，其他的从库向主库看齐就⾏了。

在实际⽣活中，很多事情⼈们也都是按照这种思路来的，⽐如企业⽼板发布⼀个通知，员⼯照着做。

但是区块链是⼀个分布式的对等⽹络结构，在这个结构中没有哪个节点是“⽼⼤”，⼀切都要商量着来。

所以在区块链系统中，如何让每个节点通过⼀个规则将各⾃的数据保持⼀致是⼀个很核⼼的问题，这个问题的解决⽅案就是制定⼀套共识算法，实现不同账本节点上的账本数据的⼀致性和正确性。

这就需要借鉴已有的在分布式系统中实现状态共识的算法，确定⽹络中选择记账节点的机制，以及如何保障账本数据在全⽹中形成正确、⼀致的共识。