小小千想和您聊一聊

当前位置: 首页> 技术分享> 区块链绕不过去的拜占庭将军问题

区块链绕不过去的拜占庭将军问题

  “拜占庭将军问题”维基百科:

  拜占庭将军问题(Byzantine Generals Problem),是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。在分布式计算中,不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有時候,系统中的成员计算机可能出错而发送错误的信息,用于传递信息的通讯网络也可能导致信息损坏,使得网络中不同的成员关于全体协作的策略得出不同结论,从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

  1-THE FIRST STORY-

  第一个拜占庭将军问题的故事

  咱们由《哆啦A梦》动画片开始吧,故事轻松,涉及到的人物角色少,主要是哆啦A梦 / 大熊 / 静香 / 小夫 / 胖虎,这五个小伙伴。

  胖虎体胖腰圆,常常喜欢欺负弱小同学,但他也很怕事,遇到强大的对手立刻就怂。某一天,常常遭到胖虎欺负的其他四个小伙伴,哆啦A梦/大熊/静香/小夫开了一次小型的会议,决定联合起来去找胖虎谈判(下图,他们战斗值联合起来可以让胖虎服软)。他们偷偷的给胖虎扔了一张小纸条,气势汹汹的约胖虎放学后小区小广场见。

  下课铃响起,胖虎悠哉悠哉的走去小广场,其他四位小伙伴计划先各自回家,放下书包,火速去广场集合。刚到家,大熊扔下书包打算去广场,可是突然哆啦A梦说了一句话:小夫那么怕事,万一他不去怎么办?这时,大熊迟疑了,他想,对啊,静香又是个女孩子,万一也不想去,我们去了势必要被胖虎揍一顿,我有点不想去了。于是哆啦A梦和大雄在家里踌躇着,静香和小夫其实也在家里考虑着,都认为大熊胆小,也极可能不会去。就这样,胖虎在小广场上等了一小时也不见其他人。

  这其实就是著名的拜占庭将军问题,分析一下,它有几个特点:1、敌人很强大(胖虎);2、作为弱者的几个人实力均等(以上四个小伙伴);3、明确弱者联合起来可以打败强大的敌人;4、只要有一个弱者退出,合作势必失败。

  首先明确并默念几遍

  拜占庭将军问题的本质:

  如何让众多完全平等的节点针对某一状态达成共识

  2 -THE SECOND STORY-

  第二个拜占庭将军问题的故事

  古老的拜占庭帝国是一个强大的国家,他们常常进攻他国以扩大疆土。这次,他们打算攻打一个也很强大的国家多米诺,采取的战略是兵分十路,包抄多米诺,这样他们才会赢。他们按照地形,每支队伍先驻扎下来做好准备等待进攻时刻。这时问题出现,十支部队如今分开了,只要有一个或多个将军是奸细或有将军临时反叛,到了约定的时间不冲锋陷阵,那么战争就会失败,损失也将极为惨重,只要多米诺国反攻甚至会亡国。

  基于以上的问题,我们需要在行动时达成共识。互联网上,每台计算机都是一个个完全相等的节点,只能靠通信来协调,没有权威背书或信任,是一个急需解决的问题。

  如果把十支部队想象成互联网上十个独立平等的节点,想达成共识即拜占庭将军问题。这个问题的提出时间是1982年,直到2009年,比特币的出现才算解决了这一问题。

  比特币的工作机制,POW(proof of work)工作量证明。工作量证明系统主要特征是众多参与节点需要做一定难度的工作得出一个结果,谁先得出立即全网广播,其他节点很容易通过结果来检查出之前节点是不是做了相应的工作,一旦结果被证明正确,其他节点会把之前节点的结果添加到各自的账单中,为争取下一笔的交易记录做好计算的准备。

  沿用比特币的工作机制,将军A在互联网上先发布了一个消息“进攻”并附上了自己的签名“将军A” ,即【进攻 + 将军A】(这则消息容易被其他将军证实确实是将军A发出的)。

  如果消息发出去,却没有执行的话,将军A在拜占庭帝国会被认为是叛军,他的族人都会被处死,他自己在整个社会也会混不下去。

  将军A的消息被其他节点收到,如果其他将军也打算进攻,则在将军A的消息后面跟上自己的信息,如:【进攻 + 将军B】,以此类推。当此类消息达到十个,他们必将堵上未来,一同发起进攻。

  这时也会出现一种情况,将军A发出消息后,可能会有两个或多个将军同时跟上“进攻+签名”的消息,这时,各个节点会严格按照广播的精确时间进行排序,确保一条链的完整性。

  也有完全同时广播出来的情况,这时就是“分叉”,出现一个分开的两条链,之后,哪条链上添加的账本多(共识多),哪条就成为主链,另一条分叉链就此中断或被部分矿工认可继续添加(如:以太坊和以太坊经典)

  之所以能够达成统一的共识,认可这一账本,最终是因为利益驱使。任何人都可以随时加入比特币这套系统,读取/更新/记录账本,只要解题的速度够快且准确,就可以争取到比特币作为奖励(我们这里只用比特币的工作机制举例);相反,比特币网络中只有拥有超过51%的算力才能破坏网络安全,如果恶搞的话,会浪费自己的大量资源,收益可能并不高于成本。

上一篇:HTML5工具初识之网页编辑器

下一篇:JavaString、StringBuilder、StringBuffer类的区别

视频推荐

MORE > >