1. 链一财经首页
  2. 资讯

拜占庭将军问题OM算法详解

关于“拜占庭将军问题”的背景以及介绍这里老猫就不提了,前面几篇文章讲的也很详细了。今天这里还是直接开门见山说算法。

下面的这个截图是从Lamport发表的论文中截取的: 

拜占庭将军问题OM算法详解

对于这个英文算法,老猫知道你们肯定看不懂。知你们者,非老猫是也。接下来给你们详细讲讲。  

(1) 在第一轮 将军会把消息发送给所有的副官,第i个副官收到的记为 Vi。如 1(这里代表的是攻击)

(2) 在第二轮里面,Li(即第i个副官)会怀疑将军发来的消息Vi是对还是错,于是他会问其余的副官。这样他就会得到剩下的(n-2)个副官的值。 i从1到n-1,所以每个副官都会得到剩余的n-2个副官手里的Vi。在这一步骤里,忠诚的副官j会直接将自己的 Vj发送给其它人。叛徒则会发假消息。 

在n=7,m=2的时候 如果将军是忠臣的话,那么在第二轮忠诚的副官确实已经可以判断出要做的决定,因为他们会收到(1 1 1 0 0 )再加上将军发来的1就是 1 1 1 1 0 0 但是这个算法是递归的所有必须要到第三轮。并且如果将军是个叛徒的话,那么第二轮有情形是做不出决定的。 

这里对进入第三轮的解释是,如L1收到其它L2~L6发来的Vj, 但是他要怀疑准确性,比如L1会想L2发给自己是否是正确的呢?那么就进入第三轮进行投票

(3)在第三轮里面,接着(2)中后面的问题。L1会依次询问L3,L4,L5,L6 ,问他们上一轮L2给他们发了什么,然后L1会得到在(2)中 L2->L3, L2->L4,L2->L5, L2->L6的值 这样再结合自己的L2->L1的值,从这5个里面用majority函数投出决定得到L2发给自己的消息值。依次再进行L3,L4,L5,L6在第二轮中发给自己的消息的确认。 

这样L1就完成了第二轮的确认。之后L1再从第一步中将军发给自己的vi和第二轮中确定的5个值中投出自己的决定。 

其余的L2,L3.等等也进行同样的步骤。 

其实算法还是挺复杂的,老猫也是花了很长时间,查了很多资料才搞懂的。知道你们可能还是看不懂。再看看下面的图解吧。

拜占庭将军问题OM算法详解

这里需要注意的是:Lamport提出的容错的两个条件。

IC1:即所有的忠诚的副官要遵守同一个命令,即达成一致; 

IC2:假如将军是忠诚的,那么每一个忠诚的副官都应该按照将军的意思行事。 

这里将军是叛徒,所以只要满足IC1条件即可。同时L6也是叛徒会干扰L1-L5。 

Step1 : C给L1~L6 依次发 A R A R A x  (A,R代表攻击和撤退,这里因为C是叛徒,所以可以随便发给L1-L5消息,这里只是一个例子,可以用其他的值,只要最后满足IC1就可以)

step2:以L1为例,L1会怀疑将军发给自己的消息的真假,于是他会问L2-L6的人他们收的消息是什么。所以L1收到:2R  3A   4R   5A   6A(即L2发给L1的是R,L3发给L1的是A以此类推)

同理L2-L6收到消息如下图:

拜占庭将军问题OM算法详解

Step3:其实在第三步中 L1会依次确认在step2中, L2~L6发给自己的信息. 例如确认L2时会问L3-L6,在Step2中L2发给你们了什么,最后得到 R,R,R,A(因为L6这时候肯定又说谎) 

再结合自己的R,L1确定在Step2中收到L2发来的是R,之后又确认了L3-L6。大家可以自己在草稿纸上画出。  

其实因为L1-L5都是忠诚,他们不会在Step2中撒谎,所以只需投票L6即可 ,(A R A R A )是L6发给L1-L5的信息,最后投出发的是A,将A修改到step2中L1-L5收到的,信息中其余的信息可以不用改。 

最后得到L1-L5均是4个A,2个R。以L1为例=R  A  R  A  A  A  

即L1~L5达成了一致。所以他们最后的行动是A,攻击。

好了,今天的算法讲解就到这里了,后面有时间老猫还会给你们讲讲拜占庭将军问题的签名算法。

大家对今天内容有什么疑问都可以留言提出来,老猫会一一解答。

声明:币圈有风险,投资需谨慎,本文纯属个人观点,不作任何投资意见;

根据国家《关于防范代币发行融资风险的公告》,大家应警惕代币发行融资与交易的风险隐患。

本文来自LIANYI转载,不代表链一财经立场,转载请联系原作者。

发表评论

登录后才能评论

联系我们

微信:kkyves

邮件:kefu@lianyi.com

时间:7x24,节假日bu休息

QR code