什么是拜占庭将军问题

什么是拜占庭将军问题问题描述

什么是拜占庭将军问题_aicoin_图1

9个将军带领9支军队,打一场攻城战役。假设每个将军都能独立根据眼前战况做出两种判断:进攻撤退,要求(或者最终目的是)如何让这9个将军的命令一致的(一致性,即共识)?要么一起进攻,要么一起撤退(每个将军之间也是互不信任的,也有消灭对方的动机)

最简单的策略即:投票(上图中的红色箭头和绿色箭头为每个将军做出的判断),超过半数支持某个决定,那么所有9个将军一定执行这个决定。如上图,5个将军决定进攻,4个将军决定撤退,那么所有将军都会下令:进攻!

这种策略需要每个将军把自己的判断通过一种途径(途中灰色箭头)传递到所有其他将军处。相对的,每个将军只有在收到了所有投票结果后,才会下令。如上面的例子,所有将军得到投票:4进攻5撤退,才下令撤退

什么是拜占庭将军问题_aicoin_图2

这个投票策略的最大问题:假设出现了叛徒,如上图所示,会出现两种情况

【1】对自己位置的战场情况进行错误广播(比如他这个地方优势很大,但是投票给撤退)

【2】可以选择靠给不同的将军送去不同的消息破坏整体决定的一致性(导致左边四个将军选择撤退,右边四个将军选择进攻)

问题总结

此时总结一下,拜占庭问题的问题倒是是什么:

所有将军如何才能达成共识去攻打(或撤退)城堡

根据相关的研究,得出一个【一般性的结论】:如果叛徒的数量大于或等于三分之一 ,那么拜占庭问题不可解,这个三分之一也被称为拜占庭容错,三模冗余是完全无法容错的(也就是说无解,不可能保持一致性)

解释方法使用副官模型即可

推广到计算机系统内,【将军】类比为【计算机】,而计算机因为物理或被感染等其他原因造成的【运行异常】就是【叛徒】,其实整个问题也是为了保证分布式系统的一致性可用性

传统解决方案

在区块链之前,有两种解决方案:口头协议(又称为拜占庭容错算法)和书面协议。

通常来说,大多数分布式系统使用的是书面协议确保一致性,中心机构背书。其中有实用拜占庭容错算法(PBFT)最为有名。采用PBFT方法,本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息,通信代价是非常高的。通常采用PBFT算法,节点间的通信复杂度是节点数的平方级的

区块链解决方案

我们知道,区块链最强的地方就在于它的一致性,同时这正是拜占庭问题的核心

案例拆解

我们先假设你已经完全了解了比特币区块链的运行原理,那么我们一步一步建立一个场景看一看区块链是如何解决拜占庭将军问题?

我们先假设信道一定是可靠的,传令兵死亡之类的事情我们不考虑,毕竟在一个非常复杂的网络中,还可以通过多条的方式连接任意两个节点,可靠性还是值得相信。主要破坏一致性的还是心怀不轨的【间谍】,或者总结为:如何防止【间谍】对整体决策(进攻还是撤退)进行破坏?

我们按照区块链模型构造一个下图所示的系统

什么是拜占庭将军问题_aicoin_图3

每个将军本地都存储一份【记录】:记录所有将军的决定,比如“1:1”代表1号将军决定进攻

然后构造以下协议内容:

使用数字签名保证身份可可信

所有将军参与挖矿,国王以保证战役胜利为缘由,出资,奖励每一个挖到新区块俩的将军

每一个将军当本地维护的最新确认【记录】中包含了所有1-9号将军的决定后,正式做出自己的决定

在这个案例中,抛弃了代币的设定,因为不存在交易行为,而是由国王出资(保证战争不被间谍影响,我认为国王应该愿意出这笔钱)。在拜占庭时期,因为没有网络,构造上述这样的系统,是完全不可能的。而现在网络链路速度,效率越来越高,让区块链解决一致性问题得以解决

这里就引出了现在区块链的核心问题:应用场景与代价博弈。你要解决的痛点,到底值不值得这样的花费呢?无论是算力消耗,还是资源消耗,亦或是类似于上述案例中的国王出资(区块链代币价值为负数?),都是一种【代价】。完全的信任是不存在的,只有当造假(走捷径获得利润)的成本远远高于得到的利润,才能取得信任(一致性)

必须强调,在传统的拜占庭问题构造的情景中,只能是一个例子,这个应用情景是完全没有没有必要使用区块链来解决的!

总结

互联网技术的存在,让传输过程中,基本没有延迟(或说延迟很小可以基本忽略),解决了通讯延迟的问题

区块链使用链型数据结构+算力互相制约使得作假的成本随着时间的加长呈指数上升解决了一致性问题。当然非对称秘钥部分的密码学,解决了身份确认问题

至少这个系统解决的问题不仅仅是金融领域,去中心化银行系统的问题所在,交易,其实只是其中很小的一部分

极客网企业会员

免责声明:本网站内容主要来自原创、合作伙伴供稿和第三方自媒体作者投稿,凡在本网站出现的信息,均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性,但不保证有关资料的准确性及可靠性,读者在使用前请进一步核实,并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏,概不负任何法律责任。任何单位或个人认为本网站中的网页或链接内容可能涉嫌侵犯其知识产权或存在不实内容时,应及时向本网站提出书面权利通知或不实情况说明,并提供身份证明、权属证明及详细侵权或不实情况证明。本网站在收到上述法律文件后,将会依法尽快联系相关文章源头核实,沟通删除相关内容或断开相关链接。

2018-03-31
什么是拜占庭将军问题
本文带你了解拜占庭将军问题

长按扫码 阅读全文