拜占庭将军问题（三）——书面协议区块链

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

文章图片

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

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

注意，我们并没有对叛徒的签名进行限制，也就是说一个叛徒的签名可以被其他叛徒伪造，进而叛徒可以进行串谋作恶。
引入了签名消息之后，三将军问题也就不在成立了。现在给出一个算法，在任意数量将军中有***m***个叛徒的情况。
SM(m) 算法在算法中，司令官发送一个签名的命令给他的每个副官。然后，每个副官添加他的签名到命令上，并发送给其他副官，收到命令的副官再添加他的签名发送给其他副官…
算法还假定了一个choice函数，作用在一个命令的集合上来获得一个单独的命令。choice函数需要满足：

如果命令集合VVV只包含一个元素vvv，那么choince(V)=vchoince(V)=vchoince(V)=v.

如果命令集是?\emptyset?，那么choince(?)=RETREATchoince(\emptyset)=RETREATchoince(?)=RETREAT.

例如，choince函数可以是取有序集合VVV的中位数。
在下面的算法中，令x:ix:ix:i指由将军iii签名的命令值xxx，v:j:iv:j:iv:j:i指命令指vvv由将军jjj签名后再由将军iii签名。令将军000为司令官，每个副官iii维护一个命令集ViV_iVi?，包含他收到的被正确签名的命令值。(如果司令官是忠诚的，这个值集的元素不会超过一个)。

Algorithm SM(m)
初始化 Vi=?V_i = \emptysetVi?=?
(1) 司令官签名并发送他的命令给每个副官；
(2) 对于每个iii:

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

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

(B) 如果副官iii接收到形如v:0:j1:...:jkv:0:j_1:...:j_kv:0:j1?:...:jk?的消息，且vvv不在ViV_iVi?中，那么:

(i) 他将vvv添加到ViV_iVi?中;
(ii) 如果k< mk< mk

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

注意，在第二步中，副官iii将忽略任意值已经在ViV_iVi?出现的消息。通过对kkk的归纳，对于每个副官序列j1,...,jkj_1, ..., j_kj1?,...,jk?, 且k< mk< mk 举例： m=1, n=3 下图描述了当将军是叛徒时，发送消息的情况：

文章图片

在第(1)步，司令发送发送“attack”给副官1并发送“retreat”给副官2；
在第(2)步，每个副官将收到两个命令值，即V1=V2={" attack" ," retreat" }V_1=V_2=\{" attack" , " retreat" \}V1?=V2?={"attack","retreat"}。
在第(3)步，两个忠诚的副官执行choice(Vi)choice(V_i)choice(Vi?)得到的结果也是一样的。
因此，当司令叛徒时，算法满足条件IC1。
当司令是忠诚的时，叛徒副官无法篡改司令的命令，因此忠诚的副官的行动值集ViV_iVi?只有一个元素，即司令发送的命令。
因此，SM(m)算法满足条件IC1和IC2**。
证明下面证明算法的正确性：

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

证明：首先证明条件IC2。如果司令是忠诚的，那么在第(1)步中，他发送签名的命令v:0v:0v:0给每个副官。在第(2)(A)步中，每个忠诚的将军收到命令vvv。而且，因为叛徒无法篡改将军的命令成v′:0v' :0v′:0，所以忠诚的副官不会在第(2)步中收到其他值因此每个忠诚的副官将按照司令的命令vvv行动。条件IC2得证。
当司令是忠诚的时，条件IC1包含在条件IC2中，因此，下面仅需证明当将军是叛徒时，条件IC1成立。
如果两个忠诚的副官iii和jjj在第(2)步中收到的行动值集ViV_iVi?和VjV_jVj?相同，那么他们会采取相同的命令。因此，证明条件IC1，等于证明如果副官iii在第(2)步中将值vvv放入其值集ViV_iVi?中，那么，副官jjj也会将vvv放入其值集VjV_jVj?。
如果副官iii在第(2)(A)步收到命令vvv，那么他会在第(2)(A)(ii)步将其发送出去，因此副官jjj也会受到值vvv。
如果副官iii在第(2)(B)步将一个命令vvv添加到ViV_iVi?中，那么他肯定收到了形如v:0:j1:...:jkv:0:j_1:...:j_kv:0:j1?:...:jk?的消息。如果jjj是j1:...:jkj_1:...:j_kj1?:...:jk?中的一个，那个副官jjj肯定也已经收到命令值vvv。否则，讨论两种情况：

k< mk< mk
k=mk=mk=m。在这种情况下，因为司令是叛徒，那么副官中至多有m?1m-1m?1个叛徒，因此在j1:...:jmj_1:...:j_mj1?:...:jm?中至少有一个副官是忠诚的，这个忠诚的副官肯定将指令vvv发给了副官jjj，因此，副官jjj拥有指令vvv。

结论得证。
小结在本篇文章中，介绍了当将军之间传输不能篡改的签名消息时，拜占庭将军问题的算法SM(m)，算法能够处理在n个将军中至多有m个叛徒的情况(n≥mn\geq mn≥m)。
口头协议和书面协议都假设了将军之间是能够直接通信的，后续的文章中将介绍不是所有将军都能直接通信的情况下拜占庭将军问题的解法。

【拜占庭将军问题（三）——书面协议】Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401. ??