拜占庭将军问题(三)——书面协议

在上篇文章中,对口头消息算法OM(m)进行了阐述,OM(m)算法能够处理在大于3m个将军中至多存在m个叛徒的拜占庭将军问题。Leslie的论文1中,对将军之间发送不可篡改的签名消息的情况进行分析,阐述书面协议算法SM(m)

拜占庭将军问题(三)——书面协议

假设

为了限制叛徒发送的消息,从而使拜占庭将军问题更加简单。一种方法是让每位将军发送不可伪造的签名消息。更准确的来说,在假设A1-A3的基础上添加如下假设:

A4 (a) 忠诚将军的签名不能被伪造,并且任何针对他签名消息的篡改都能被检测到;
(b) 任何将军都可以验证将军签名的真实性

注意,我们并没有对叛徒的签名进行限制,也就是说一个叛徒的签名可以被其他叛徒伪造,进而叛徒可以进行串谋作恶。

引入了签名消息之后,三将军问题也就不在成立了。现在给出一个算法,在任意数量将军中有m个叛徒的情况。

SM(m) 算法

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

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

  1. 如果命令集合V只包含一个元素v,那么choince(V)=v.
  2. 如果命令集是,那么choince()=RETREAT.

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

在下面的算法中,令x:i指由将军i签名的命令值xv:j:i指命令指v由将军j签名后再由将军i签名。令将军0为司令官,每个副官i维护一个命令集Vi,包含他收到的被正确签名的命令值。(如果司令官是忠诚的,这个值集的元素不会超过一个)。

Algorithm SM(m)

初始化 Vi=

(1) 司令官签名并发送他的命令给每个副官;
(2) 对于每个i:

(A) 如果副官i从司令官接收到一个v:0形式的消息,并且他还没有接收到过任何命令,那么:

(i) 令Vi={v};
(ii) 发送v:0:i给每个其他的副官。

(B) 如果副官i接收到形如v:0:j1:...:jk的消息,且v不在Vi中,那么:

(i) 他将v添加到Vi中;
(ii) 如果k<m,那么他发送消息v:0:j1:...:jk:i给不同于j1:...:jk的每个副官。

(3) 对于每个副官i: 当副官i不再接收到消息,他将遵从choice(Vi)行动。

注意,在第二步中,副官i将忽略任意值已经在Vi出现的消息。通过对k的归纳,对于每个副官序列j1,...,jk, 且k<m,每个副官至多收到一条v:0:j1:...:jk消息。在第(3)步中可以使用超时来判断没有消息再回到来。

举例: m=1, n=3

下图描述了当将军是叛徒时,发送消息的情况:

拜占庭将军问题(三)——书面协议

在第(1)步,司令发送发送“attack”给副官1并发送“retreat”给副官2;
在第(2)步,每个副官将收到两个命令值,即V1=V2={"attack","retreat"}
在第(3)步,两个忠诚的副官执行choice(Vi)得到的结果也是一样的。

因此,当司令叛徒时,算法满足条件IC1

当司令是忠诚的时,叛徒副官无法篡改司令的命令,因此忠诚的副官的行动值集Vi只有一个元素,即司令发送的命令。

因此,SM(m)算法满足条件IC1IC2

证明

下面证明算法的正确性:

定理 2:对于任意m,当将军中至多有m个叛徒时,算法SM(m)能解决拜占庭将军问题。

证明: 首先证明条件IC2。如果司令是忠诚的,那么在第(1)步中,他发送签名的命令v:0给每个副官。在第(2)(A)步中,每个忠诚的将军收到命令v。而且,因为叛徒无法篡改将军的命令成v:0,所以忠诚的副官不会在第(2)步中收到其他值因此每个忠诚的副官将按照司令的命令v行动。条件IC2得证。

当司令是忠诚的时,条件IC1包含在条件IC2中,因此,下面仅需证明当将军是叛徒时,条件IC1成立。

如果两个忠诚的副官ij在第(2)步中收到的行动值集ViVj相同,那么他们会采取相同的命令。因此,证明条件IC1,等于证明如果副官i在第(2)步中将值v放入其值集Vi中,那么,副官j也会将v放入其值集Vj

如果副官i在第(2)(A)步收到命令v,那么他会在第(2)(A)(ii)步将其发送出去,因此副官j也会受到值v

如果副官i在第(2)(B)步将一个命令v添加到Vi中,那么他肯定收到了形如v:0:j1:...:jk的消息。如果jj1:...:jk中的一个,那个副官j肯定也已经收到命令值v。否则,讨论两种情况:

  1. k<m。在这种情况下,副官i会发送v:0:j1:...:jk:i消息给副官j,因此副官j会收到指令v
  2. k=m。在这种情况下,因为司令是叛徒,那么副官中至多有m1个叛徒,因此在j1:...:jm中至少有一个副官是忠诚的,这个忠诚的副官肯定将指令v发给了副官j,因此,副官j拥有指令v

结论得证。

小结

在本篇文章中,介绍了当将军之间传输不能篡改的签名消息时,拜占庭将军问题的算法SM(m),算法能够处理在n个将军中至多有m个叛徒的情况(nm)。

口头协议和书面协议都假设了将军之间是能够直接通信的,后续的文章中将介绍不是所有将军都能直接通信的情况下拜占庭将军问题的解法。


  1. Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.