拜占庭问题（拜占庭问题中,如果叛徒的个数是m个）

本篇文章给大家谈谈拜占庭问题，以及拜占庭问题中,如果叛徒的个数是m个对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、拜占庭问题与共识算法
• 2、易理解的拜占庭将军问题——深入剖析
• 3、拜占庭问题说明了哪个问题的重要性
• 4、如何理解拜占庭将军问题
• 5、拜占庭问题

拜占庭问题与共识算法

“拜占庭将军问题”（Byzantine Generals Problem）是一个经典难题，这个难题是这样描述的：拜占庭是东罗马帝国的首都，它的军队分成多个师，每个师都由一个将军统领。这些将军通过信使进行交流，来达成一个共同作战方案，有些将军可能是叛徒，想故意破坏这个过程，这会造成那些忠诚的将军也无法达成一个统一的作战计划。这个难题在于如何让那些忠诚的将军在这样的情况下达成统一作战方案，而避免那些叛徒对作战方案的误导。

在点对点、分布式的区块链中，常常用拜占庭问题来比喻节点如何达成共识的问题。将军即对应着一个个节点，达成统一作战方案即达成共识，正确的打包与验证区块数据，防止恶意节点（叛徒将军）破坏区块链的运行。

顾名思义，就是能够解决拜占庭问题，使各个节点达成共识，解决共识问题的各种机制也被称为共识算法。在各种各样的共识算法中，又一直存在一个「不可能三角」的难题，这三角是指“安全性”、“去中心化”和“速度”，也就是说难以同时保证速度、安全性和去中心化程度，三者之间往往会顾此失彼。

现在各种共识算法算起来有好几十种，计算机界也一直处于研究阶段，并没有说哪种算法已经完美。

下面盘点一下讲解pBET和POW两种算法，以及它们的“安全性”、“去中心化”和“速度”如何。

实用拜占庭容错是一种较早的共识算法。pBFT的一个原则，就是少数服从多数。节点通过在相互传递有关决策的消息，谁的决策赞同的人数多，就采用谁的。所以在这个系统中，安全性随着诚实节点的数量而增加。诚实节点同意正确的决策，拒绝恶意节点的错误决策，只要恶意节点的数量少于总数的1/3，就能保证达成共识。

达成共识可以简化为四步：

pBFT 使用投票机制以循环方式选举领导节点。

领导者发起决策并将其广播给辅助节点。

所有节点，包括领导节点和辅助节点，都发送响应。

当 ⅔ + 1 个节点发送相同的响应时，该响应被认为是有效的。

如果领导者有恶意行为，它可以被大多数节点删除。

按少数服从多数的原则。那按理来说，只要恶意节点的数量少于1/2就够了啊，那么为什么PBFT算法的容错数量要满足恶意节点的数量少于总数的1/3呢？

因为 PBFT 算法的除了需要支持容错故障节点之外，还需要支持容错作恶节点。假设集群节点数为 N，有问题的节点为 f。有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。那么会产生以下两种极端情况：

（1）这f 个有问题节点既是故障节点，又是作恶节点，那么根据少数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即 f+1 个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识，即总节点数为f+(f+1)=n，也就是说这种情况支持的最大容错节点数量是 (n-1)/2。

（2）故障节点和作恶节点都是不同的节点。那么就会有 f 个作恶节点和 f 个故障节点，当发现节点是作恶节点后，会被集群排除在外，剩下 f 个故障节点，那么根据少数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即 f+1 个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是 f+1 个正常节点，f个故障节点和f个作恶节点，即 3f+1=n。

结合上述两种情况，因此PBFT算法支持的最大容错节点数量是(n-1)/3，即少于1/3。

pBFT的优缺点

pBFT 系统不需要高计算资源或大量能源来运行。pBFT 在节点少的时候可以快速达成共识，因为所有节点都在不断地相互通信。一旦节点就决策达成一致，交易就完成了。

然而，pBFT的缺点也很明显：频繁的通信使它只能在节点数量有限的网络中正常工作。随着每个新节点加入网络，通信开销呈指数增长，响应所需的时间也随之增加。

pBFT 网络也容易受到女巫(Sybil)攻击，女巫就是恶意黑客制造的不同节点，黑客可以控制多个节点，使其超过1/3，那系统将无法达成正确的共识。

从不可能三角的角度来看，由此可见pBFT在节点少的时候速度快，但安全性差，去中心化低；节点多了又会导致速度很慢。

中本聪设计了POW共识机制来解决上面pBFT这个经典共识的可扩展性问题。

上面说到，pBFT通过不断广播然后计算节点的消息数，时间花费过长。POW是怎么做的：我不要计算节点数是否超过2/3，我直接选一个节点，按它的决策，其他节点全部同步它的决策。这样就省去在全节点通信然后计算节点数的费时操作。

那么，对于哪个节点来打包区块，那就很重要，万一是恶意节点呢？必须对打包的节点进行要求，哪个节点有权力进行打包呢？那就是解决复杂的数学问题，俗称挖kuang。节点必须花费大量算力和电费来争取某次打包区块的权力。这样的成本就限制了黑客的女巫攻击。

如果打包区块的权力真的被黑客抢到了，那可能会有什么问题？

（1）窃取冰糖橙

黑客能够窃取属于另一个用户，不受她控制的地址里的冰糖橙吗？答案是否定的。即使这一轮是由黑客打包区块链上的下一个区块，她也不可能窃取别人的比特币。这么做的话，黑客需要发起一笔有效的交易来转移比特币到自己的地址。这就要求黑客伪造比特币拥有者的签名，然而如果数字签名机制是安全的，她是无法办到的。只要背后的密码学基础是牢靠的，她就无法轻易窃取比特币。

（2）拒绝服务攻击

让我们来考虑另一种攻击。假设黑客不喜欢叫鲍勃的某个用户，黑客可以决定她不把鲍勃发起的任何交易放进她所提议的区块里。换言之，她拒绝提供服务给鲍勃。尽管这是黑客可以开展的有效的攻击，但幸好这不过是个小问题。如果鲍勃的交易没有被放进黑客所打包的下一个区块，鲍勃只要等到下一个诚实节点发起区块的时候，他的交易记录就会被放进这个区块里。所以这其实也不算是一个有效的攻击。

也就是说，黑客花费重大成本取得的打包，但并不能起到有效的攻击。由于对恶意节点进行惩罚、对诚实节点进行奖励这样的机制下，共识就达成了。

尽管有所改进，POW也引入了其他问题。工作量证明需要所有节点解决复杂的数学问题，这会消耗大量的能源，就是大家所熟知的挖kuang耗费电力。并且解决复杂的数学问题的时间也要求不短，10分钟左右。

从不可能三角的角度来看，POW去中心化高，安全性高，但速度还是慢，但至少已经不会像pBFT那样由于节点多导致花费时间呈指数增长。

共识算法各式各样，冰糖橙的POW并不是真正去解决分布式共识问题，它不能完美的套用到其他场景。但它在货币系统的这个特定场景下解决了冰糖橙的共识问题。POW在冰糖橙里运行得非常好。

易理解的拜占庭将军问题——深入剖析

拜占庭将军问题和两军问题实质是不一样的，不能混为一谈。其中两军问题如下图所示：

两军问题描述：

和拜占庭将军问题有一定的相似性也有不同之处，所以我们必须注意的是：

两军问题的根本问题在于信道的不可靠，也就是信号做不到真正的同步，那么想要做到真正的同步唯一的办法就是量子通信——毕竟遇事不决量子搞定:

到底是一个关于一致性和正确性的算法问题。针对的是忠诚的将军，因为叛徒可以做出任何超出约定的判断。我们就是要在有叛徒的干扰下，找到一个抗干扰的算法。

类似TCP/IP的三次握手，我们也同样的是采用容错机制，通过限制一部分条件最后使得在有叛徒的情况下依然能够得到信息的真实性。

失效说明：

满足以下三个条件的方式称为口头协议：

对于正整数 和 ，当图 是 -正则的是，定义算法 OM(m, p) ：

在算法中，司令官发送一个签名的命令给他的每个副官。然后，每个副官添加他的签名到命令上，并发送给其他副官，收到命令的副官再添加他的签名发送给其他副官......

算法还假定了一个 choice 函数，作用在一个命令的集合上来获得一个单独的命令。 choice 函数需要满足：

例如， choince 函数可以是取有序集合 的中位数。

令 指由将军 签名的命令值 ， 指命令指 由将军 签名后再由将军 签名。令将军 为司令官，每个副官 维护一个命令集 ，包含他收到的被正确签名的命令值。(如果司令官是忠诚的，这个值集的元素不会超过一个)。

书面协议的结论非常令人兴奋，这不是解决了拜占庭将军问题了吗？但请注意我们在A1~A4中实际上是添加了一些条件的，这使得拜占庭将军问题在这些假设下能够解决，但是在实际状况中却会有一些问题。观察A1-A4，我们做了一些在现实中比较难以完成的假设，比如：

拜占庭问题说明了哪个问题的重要性

拜占庭问题说明了通信中基本问题的重要性。拜占庭将军问题，是由莱斯利兰伯特提出的点对点通信中的基本问题，含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。

如何理解拜占庭将军问题

关于拜占庭将军问题，一个简易的非正式描述如下：

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。

这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。

基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。

他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。

他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。

困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。

在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗 。

这就是著名的拜占庭将军问题。

应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。

Lamport已经证明了在消息可能丢失的不可靠信道上试通过消息传递的方式达到一致性是不可能的。

所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题的，并在这个前提下，去做一致性和容错性相关研究。

拜占庭问题

拜占庭帝国即中世纪的土耳其，拥有巨大的财富，周围10个邻邦垂诞已久，但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。

然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。

于是每一方都小心行事，不敢轻易相信邻国。这就是拜占庭将军问题。

在拜占庭问题中，最重要的point就是： 所有将军如何达成一致攻打拜占庭的共识 ，这当中，可能出现的情况举例如下：

用一个模型解释一下：

假设只有3个人，A、B、C，三人中如果其中一个是叛徒。当A发出进攻命令时，B如果是叛徒，他可能告诉C，他收到的是“撤退”的命令。这时C收到一个“进攻”，一个“撤退“，于是C被信息迷惑，而无所适从。

如果A是叛徒。他告诉B“进攻”，告诉C“撤退”。当C告诉B，他收到“撤退”命令时，B由于收到了司令“进攻”的命令，而无法与C保持一致。

正由于上述原因，在只有三个角色的系统中，只要有一个是叛徒，即叛徒数等于1/3，拜占庭问题便不可解。

可以看得出， 只要叛徒的数量大于或等于1/3，拜占庭问题不可解

从技术上理解， 拜占庭将军问题是分布式系统容错性问题 。加密货币建立在P2P网络之上，是典型的分布式系统，类比一下， 将军就是P2P网络中的节点，信使就是节点之间的通信，进攻还是撤退的决定就是需要达成的共识 。 如果某台独立的节点计算机拓机、掉线或攻击网络搞破坏，整个系统就要停止运行，那这样的系统将非常脆弱，所以容许部分节点出错或搞破坏而不影响整个系统运行是必要的 ， 这就需要算法理论上的支撑，保证分布式系统在一定量的错误节点存在的情况下，仍然保持一致性和可用性 。

而且，拜占庭将军与两军问题不同，前者假定信差没有问题，只是将军出现了叛变等问题；后者研究信差的通信问题。

终极解决方案到了——

如果 10个将军中的几个同时发起消息，势必会造成系统的混乱，造成各说各的攻击时间方案，行动难以一致 。

谁都可以发起进攻的信息，但由谁来发出呢？中本聪巧妙地在个系统加入了 发送信息的成本 ，即：

它加入的 成本就是”工作量“ —— 节点必须完成一个计算工作才能向各城邦传播消息 ，当然，谁第一个完成工作，谁才能传播消息。（这也是 工作量证明机制的意义：以检验结果的方式证明你过去所做过了多少工作 ）

这种加密技术——非对称加密，完全可以解决古代难以解决的签名问题：

中本聪在设计比特币时，它采用了一种工作量证明机制叫哈希现金，在一个交易块这要找到一个随机数，计算机只能用穷举法来找到这个随机数，可以说，能不能找到全靠运气，所以对于各个节点来说，这个世界上，只有随机才是真正的公平，实现随机的最好办法是使用数学，所有的将军在寻找共识的过程，借助了大家都认可的数学逻辑。

当然了， 凭什么要义务进行计算工作，那么肯定要有一个激励机制 ：比特币的奖励机制是每打包一个块，目前是奖励25个比特币，而拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。

在这个分布式网络里：

每个将军都有一份实时与其他将军同步的消息账本 。

账本里有每个将军的签名都是可以验证身份的。 如果有哪些消息不一致，可以知道消息不一致的是哪些将军 。

尽管有消息不一致的，只要超过半数同意进攻，少数服从多数，共识达成（只要大多数是好人，那么就可以实现共识）。

区块链上的共识机制主要解决 由谁来构造区块 ，以及 如何维护区块链统一 的问题。

拜占庭容错问题需要解决的也同样是 谁来发起信息 ，如何 实现信息的统一同步 的问题。

注：区块链学习新人，若有不正确的地方，望指出

拜占庭问题的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于拜占庭问题中,如果叛徒的个数是m个、拜占庭问题的信息别忘了在本站进行查找喔。