【分布式共识三】拜占庭将军问题----书面协议

书面协议 Lamport在文中提出,之所以会出现在口头传达中的那些错误是因为一些叛徒可以说谎,这里通过签名就是为了防止说谎。在签名算法中加了两个条件: 即A4(a)忠诚将军的签名是不...

书面协议

Lamport在文中提出,之所以会出现在口头传达中的那些错误是因为一些叛徒可以说谎,这里通过签名就是为了防止说谎。在签名算法中加了两个条件:

attachments-2017-07-2N5LVMYS5969aa26c8b15.png

A4a)忠诚将军的签名是不能伪造的,内容修改可检测。(即 即使是叛徒也要原封不动的签了名将消息转发出去)

b)任何人都可以识别将军的签名,叛徒可以伪造叛徒司令的签名。(后半句是论文中的后半部分规定的)。

而且这里Lamport规定,每条消息只可以复制,然后加上自己的姓名再发出去。 

下面是具体的算法:

attachments-2017-07-pKhBzsEu5969aa3b8460e.png

attachments-2017-07-CtNLzfij5969aa4f8469e.png

对于这个算法要说的是:

1. 初始化中的 Vi 类似于一个集合,表示的是第i个将军收到的命令,比如 Vi= {Attack} 之所以说是个集合是因为Vi里面不会有重复的命令出现。这在算法步骤(2)的(B) 部分描述的很清楚。

在算法步骤(1)中将军将签了自己姓名的消息广播发给所有副官。注意这里发的格式是 V:0V是命令,0代表自己的身份。

2. 算法步骤(2)(A)中,每个副官将收到的消息 V:0  把命令V放入自己的命令集合Vi(因为初始的时候他们的命令集合都是空的,所以不存在重复问题) 然后他们将命令拷贝,然后加上自己的签名 ,得到消息: V:0:i   然后再发给其他的副官。

在算法步骤(2)(B)中因为副官也会收到别的副官发来的消息v:0:1:...:jk. 此时i会判断v在不在自己的命令集合中,如果不存在的话将v加入Vi,并在k的情况下将信息签名,继续发出去。

在这里有几点是需要注意的。

A 如果将军是忠诚的话,那么因为忠诚将军的签名是不可以改的,所以所有的命令都只是V,只是消息的签名不一样罢了,那么副官将不会将重复的命令再加入Vi,所以这就是lamport在论文中提到的如果将军是忠臣的话,那么每个副官只会保存a single order 。这里之所以提到这个是后面的证明需要用到。

B)为什么说当k的时候才会发送呢,这是因为每条信息只需要被复制m+1就可以了(这里将将军署名的时候也算是一次签名,可以发现每签名1次就是一个复制),超过m就没必要了。之所以有这样的规定会面会有证明,即只需要复制m+1此所有的忠臣就可以达成

一致。还有就是这里的下标k,并不是代表一个副官的id号,而是被签名的多少次,例如 v:0:j3; 这条消息,k是等于1(因为除了将军以外只被签名了一次)的而不是3.

3. 算法步骤(3),当一个副官不会再收到任何的消息时就会执行choice函数。这里不再收到,lamport规定是超过一个时间不再收到就认为不再收到了。这里的choice函数,lamport没做具体的实现,只是认为,当Vi中只有一个命令时就得出这个命令。当ViVj是相等的时候choice执行的结果是一样的,即他们可以达成一致,这个只会在将军是叛徒的时候才会出现,这样的话就满足了IC1条件。

当第三步结束,就可以得出一致命令了。

 

下面我们看看lamport是怎么证明只需要m+1次复制就可以了。

attachments-2017-07-GYUl1lrP5969aa6ea8013.png

证明的总体思路是:

情形(一)如果将军是忠诚的话,就像我们在讨论算法的时候提到的,所有忠臣的副官只可能是收到a single order然后经过 choice函数得到的是将军的命令,所以满足IC2

情形(二)这里假如将军是个叛徒。证明的总体思路是只需要证ViVj是相同的集合就可以了。即只需要证明如果在step2i将命令v放入Vi时,j也会将命令v放入Vj

下面我们来证这个:

因为i要是想将v命令放入Vi,肯定会收到一个消息,V:0:j1:j2:...jk。那么下面就讨论:

1)如果j属于j1~jk中的一个,那么他既然在消息上签了名,那么肯定也收到了消息v,所以在这种情况下是满足的。

2)如果j不属于j1~jk中的一个的话,再讨论k的范围:

a.如果k那么i肯定会签上自己的姓名,将消息转发给所有的副官当然这里面肯定会有副官j(根据算法B中的ii),那么j要么在命令集vj中没有v的情况下将他保存,要么在已经有的情况下置之不理,但是无论是哪种情况,都会保证,VjVi一致。

b. 如果k=m.此时i不会转发此消息。但是因为只有m个叛徒,又将军是叛徒,那么这m+1个复制里面就肯定有1个是忠臣,而忠臣会不修改消息直接将叛徒将军的消息v传给所有的副官,当然包括 j 所以在此情况下也是可以保证的。

现在用个实例来证明:

n=4,m=2必须要经过m+1轮复制才可以完成容错(或者说是交换)

 

 

实例证明:n=4,m=2,r=m+1时(r=3 复制的轮数)可容错

1,当将军,L3是叛徒

attachments-2017-07-zkrUTpxW5969ac159f04b.png

step1R1={x:0} R2={y:0} R3={0:0}

step2k=01 x:0:1 发给2,32 y:0:2 发给1,33 z1:0:3 发给1,将 z2:0:3 发给2。得到:

R1={x:0;y:0:2;z1:0:3} R2={y:0;x:0:1; z2:0:3} R3={0:0;x:0:1;y:0:2} 

step3k=1,k进行下一轮复制。1 z1:0:3:1发给2,32z2:0:3:2发给1,3。得到:

R1={x:0;y:0:2;z1:0:3; z2:0:3:2} R2={y:0;x:0:1; z1:0:3; z2:0:3:1} k=2算法执行choice函数。

 

 

书面协议的本质就是引入了签名系统,这使得所有消息都可追本溯源。这一优势,大大节省了成本,他化解了口头协议中1/3要求,只要采用了书面协议,忠诚的将军就可以达到一致(实现IC1IC2)。这个效果是惊人的,相较之下口头协议则明显有一些缺陷。

书面协议的结论非常令人兴奋,这不是解决了拜占庭将军问题了吗?但请注意我们在A1~A4中实际上是添加了一些条件的,这使得拜占庭将军问题在这些假设下能够解决,但是在实际状况中却会有一些问题。观察A1~A4,我们做了一些在现实中比较难以完成的假设,比如没考虑传输信息的延迟时间,书面协议的签名体系难以实现,而且签名消息记录的保存难以摆脱一个中心化机构而独立存在。


下一篇:【分布式共识四】POW共识算法 

上一篇:【分布式共识二】拜占庭将军问题----口头协议

你可能感兴趣的文章

相关问题

4 条评论

请先 登录 后评论
不写代码的码农
吴寿鹤

36 篇文章

作家榜 »

  1. 社区运营-小以 626 文章
  2. 社区运营-小链 243 文章
  3. 涂晶 82 文章
  4. 于中阳Mercina-zy 79 文章
  5. 李晓琼 44 文章
  6. 兄弟连区块链培训 42 文章
  7. 吴寿鹤 36 文章
  8. John-smith 25 文章