The Byzantine Generals Problem

闲扯

之前挖下的坑还没有填完，但在此之前，由于各种原因，我决定先写些有关拜占庭将军问题的东西。

拜占庭将军问题是可信计算中的一个非常经典的问题，这个名称我估计是源于Lamport对古罗马的莫名情愫。关于历史的问题，我不懂就不逼逼了。

Problem Description

拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划。然而，这些将军中有叛徒。叛徒试图扰乱计划的制定。

因此，能够解决该问题的正确算法必须保证如下两点：

  1. 所有忠诚的将军能够达成相同的行动计划。
  2. 少数的叛徒不能使忠诚的将军做出错误的计划。

What is a bad plan?

事实上，我们很难定义什么样的计划是错误的，但是我们可以提出更高的要求来保证计划是正确的。
作如下假设：

  1. 所有的将军根据占据独立作出判断，不失一般性，此处将判断简化为 attack/retreat 二者之一。
  2. 用 w(i) 表示第i个将军作出的判断。
    1. 如果第i个将军是忠诚的，那么他发出的表示自己意见的消息都如下：“我是i，我认为应该w(i)”。
    2. 如果第i个将军是叛徒，那么他可以给不同的将军发送表达不同意愿的消息。
  3. 每个将军可以转述别人的消息，如：“我是i，j告诉我说他认为应该w’(j)”。
    1. 同样的道理，忠诚的将军在转述的时候也不说谎。
    2. 叛徒则可以随意造谣。
  4. 最后每个将军根据接收到的消息猜测所有人的判断，最后得到一个判断矩阵V，其中$V_{ij}$表示将军i认为将军j的判断。
    1. 第i个将军只具有V中第i行信息的读写权限，因此最后的决定完全取决于该行向量。
    2. 当i将军收到“我是j，我认为该w’(j)”这样的消息的时候，他并不能直接将$V_{ij}$置为w’(j)，因为j有可能是叛徒。
  5. 所有忠诚将军在得到最终V中对应的行向量之后，有统一的函数来将其映射为最终决定。

在上述假设的基础上，我们认为一个正确的算法最终能够使 V 满足如下条件：

  1. 对于任意两个都是忠诚的将军，设为m和n，其在V中对应的行向量（第m行和第n行）完全相同，从而推出所有忠将的决定相同。
  2. 对于任意两个忠诚的将军，m&n，$V_{ij} = w(j)$，也就是说忠诚将军的意志不被曲解。

如果满足这两个条件，那么最终达到的忠将之间的一致决定我们认为就是正确的。

Interactive Consistency Conditions

上述要求有一个等价形式。描述如下：

  • n个将军，其中有一个统帅c，n-1个副官l.
  • 统帅下达命令，副官则只能传达命令。

算法需要满足：

  1. IC1: 所有忠诚的副官都执行相同的命令。
  2. IC2: 如果统帅是忠诚的，那么所有忠诚的副官都执行统帅下达的命令。

其实就是将之前的V拆成不同的列，在决定第i列时，将军i作为统帅，其余将军作为副官。
本文之后所说的拜占庭将军问题，都是采用这样的简化模型。

Impossibility Results

拜占庭将军问题在如下情况无解：

  • 不小于1/3的将军是叛徒。

Proof of 1 traitor in 3 generals

首先证明3个将军中有1个是叛徒时，无法解决。假设：

  • 副官1是忠诚的。
  • 副官1收到来自统帅的消息attack，来自副官2转述的消息retreat.

则有以下两种情形。

byz

副官1无法分辨哪一方的消息为假，但是如果是图1的情形，我们要求满足IC2，于是他只能选择相信统帅，执行attack; 同理，如果副官2也是忠将，也就是图2的情形，那么他也只能选择相信统帅，执行retreat. 于是两个忠诚的副官执行了不同的命令，违背了IC1.

Proof of the rest

反证法，假设“m个叛徒，且总将军数不大于3m”时问题（下面简称为m-3m问题）有解，我们试图用这个解来构造上边1个叛徒3个将军问题（下面简称为1-3问题）的解，从而导出矛盾。

将m-3m问题中的将军尽可能均匀地分成3份（目的是使3份处于等价地位，无法通过数量进行区分），因为叛徒的数量至少有三分之一，所以一定有一种分法使得某一组中全为叛徒。在这样的分配方式下，让这3组将军扮演1-3问题中的角色。进行如下模拟：

  • 如果统帅不是叛徒，如上图1，则全为叛徒的那组扮演l2，统帅所在那组扮演c，其余扮演l1.
  • 如果统帅为叛徒，如上图2，则令统帅被分到全叛徒组，且该组扮演c，其余两组分别扮演l1和l2.
  • 扮演c的非统帅将军发送 “he said xxx”，这里的xxx与统帅发出的真实指令（同目标）相同。
  • 所有被分在非全叛徒组的叛徒都不表现为叛徒。
  • 组内成员互不通信，组间通信方式采取1-3问题中对应组角色之间的消息。

对于每个忠将，由于他处于忠诚的组，组中的每个将军的行为都是忠诚的，他知道其余的组员会获得跟他完全一样的消息，所以组内的通信不会带来任何附加消息，因此可以忽略。于是模拟出的1-3问题的消息全集构成了原本m-3m问题的消息全集。

根据假设，m-3m问题可解，根据解的IC1和IC2性质，可以推出模拟的1-3问题也有对应解，从而得到矛盾。

Oral Message Algorithm

如果通信的信道满足：

  1. A1: 所有消息被准确送达。
  2. A2: 消息的接收者知道送信人的身份。
  3. A3: 消息的丢失可以被检测（timeout机制）。

那么当叛徒数量小于1/3时，问题有解，下面，用递归的方式给出算法 OM(m).

首先，令majority函数返回一个向量中的众数，如果attack数量与retreat一样多，选择retreat.

  • OM(0) （适用于0个叛徒时）
    1. c发送命令给所有的l.
    2. 每个l采用他从c收到的消息作为行动，如果没有收到消息，则执行retreat.
  • OM(m) （适用于m个叛徒）
    1. c发送命令给所有的l.
    2. 假设v(i)为第i个l收到的来自c的命令（默认retreat），他以OM(m-1)算法中c的角色向其余n-2个l发送消息：”c told me to v’(i)”.
      1. 如果第i个l为忠将，则v’(i) = v(i).
      2. 如果为叛徒，则v’(i)可视消息目标变化而变化。
    3. 通过n-1次算法OM(m-1)，每个忠将确认所有的l“声称从c处获得的消息”。即每个忠将得到一个消息向量V，其中第i个是该l对”c told me to v’(i)”中v’(i)的判断v’’(i)，然后他将执行majority(V).

OM(1)如下图，此处由于信道的A2性质省略了”c told me to”的消息字样，但是当m更大时，两个l之间会有多条层次不同的消息，要注意区别。

byz

Proof of algorithm OM(m)

Lemma1: 对于任意的m和k，如果有多于2k+m个将军，且最多k个叛徒，则OM(m)满足IC2.

Proof: 对m作归纳：

  • m = 0时，所有l采用盲从的策略，必然满足IC2.
  • 设m = m’-1时成立。
  • 考虑OM(m’)的第2步，采用了n-1次OM(m’-1)算法，算法作用于n-1个将军，由于 $n-1 > 2k + (m’-1)$，归纳假设可知，
    对任意i，如果第i个l忠诚，那么在他发出的 “c told me to v’(i)”的问题上，所有其它的忠诚的l判断出的 v’’(i) = v’(i) = v(i) （第一个等号根据IC2，第二个等号根据i忠诚）。
  • 由于 $n-1 > 2k + (m’-1) \geq 2k$，于是n-1个l中多数为忠诚，那么当c为忠时，他会给所有l发送同样的v，其中多数忠诚的l转发了相同的v，且被正确理解。于是任意忠的l所判断出的V中，多数为v，即 majority(V) = v，也就是IC2的要求。

Theorem1: 对任意m，最多m个叛徒，至少3m+1个将军时，OM(m)满足IC1和IC2.

Proof: 对m作归纳：

  • m = 0时，结论显然。
  • m = m’-1时成立。
  • 令k = m’，利用Lemma1，可以证明OM(m’)满足IC2.
  • 只需证明IC1，也就是说，当c为叛徒时，所有忠的l还能够达成一致的决定。
    1. 此时n-1个l中最多有m-1个叛徒，$n-1 > 3m’-1 > 3(m’-1)$，于是归纳假设可得，每个被执行的OM(m’-1)算法也满足IC1.
    2. 也就是说，即使第i个l是叛徒，他所发出的”c told me to v’(i)”的消息在所有忠的l中被统一解读为v’’(i) (可能不等于v(i))，换句话说，所有忠的l可以得到完全一样的V.
    3. 作用在相同的函数majority上，必然得到相同的结果，于是IC1也成立。

Signed Messages Algorithm

通过给消息进行签名来简化问题。在A1-A3的基础上加入如下假设：

  • A4: 忠将的签名不能被伪造，无法对“被他签名认证的消息”进行篡改。
  • A5: 所有人可以识别任何一个将军的签名。

为了解决问题，引入新的函数：choice(V)，它的输入为一组决定，输出为一个决定，且满足：

  • 如果V只包含一个元素v，则 choice(V) = v.
  • choice(empty set) = retreat.

引入如下记号：

  • $x:j$ 表示值x被将军i签名。
  • $v:j:i$ 表示值v首先被将军j签名，然后$v:j$作为整体被将军i签名。
  • 每个将军i记录一个集合V(i)，包含所有他收到的签名合法的消息值。

在这样的假设下，给出算法SM(m):

  1. c发送签名了的消息v给所有l.
    • 若c为叛徒，则v可视目标而定，且可以选择只给部分的l发送消息。
  2. 对于每个i：
    1. 如果i从c收到消息$v:0$，并且V(i)为空，则令 V(i)={v}，且他将发送$v:0:i$给其他所有l.
    2. 如果i收到消息$v:0:j_i:…:j_k$，并且v不在V(i)中，则将v添加到V(i)，如果 $k < m$，则他将发送$v:0:j_i:…:j_k:i$给所有除了$j_i…j_k$之外的l.
    • 如果i为叛徒，则他可以选择部分l转发消息，或者完全不转发，但是他无法更改已经被c签名的消息（根据A4）。
  3. 对每个i，当他不再接收消息，他将执行choice(V(i)).

byz

接下来，证明该算法SM(m)在最多只有m个叛徒时满足IC1，IC2.

Proof of algorithm SM(m)

Theorem2: SM(m)在最多m个叛徒时解决拜占庭将军问题。

Proof:

  • 注意如果c为忠，则对于步骤2，根据A4，叛徒并不能修改v的值，于是所有的V(i)将只包含一个值v，IC2被满足。
  • 如果c为叛徒，我们只需证明对于忠的副官i和j，最后得到的V(i) = V(j).
    1. 对于V(i)中的任意元素v，假设2中添加时对应的消息为$v:0:j_1:…:j_k$，如果j在$j_1…j_k$中，则v已被添加如V(j).
    2. j不在$j_1…j_k$中，分两种情况：
      1. $k < m$, 则i在接收到该消息后将会向j转发，于是v会出现在V(j)中。
      2. $k = m$，由于最多只有m个叛徒，c是叛徒，所以$j_1…j_k$中至少有一个忠诚的，他会将消息转发给j.
    3. 综上所述，V(i) = V(j)，于是IC1满足。

Missing Communication Paths

以上算法均假设将军两两之间均可通信，但是现实中的情形往往不是如此。将将军视为节点，能够通信的两个将军之间连线，则
当所形成的图非完全图时，是否有办法解决拜占庭将军问题呢？

首先引入概念regular-set，如果一个节点集合$\{i_1, …, i_p\}$满足如下条件，就说它是一个regular-set.

  1. 集合中的每个元素都与i相连。
  2. 对于任意不同于i的节点k，和1-p中的下表j，存在一条路径 $p_{j,k}$ 从 $i_j$ 到k，且不经过i；所有这样的路径 $p_{j,k}$ 除了k以外没有其它相同的节点。

如果一个图被成为p-regular的，则它满足：

  1. 每个节点的邻居集合形成一个regular-set.
  2. 每个节点的度为p.

下左图给出了一个3-regular非完全图的例子，右边则为一个反例。

byz

Algorithm OM(m, p)

改进OM算法，使之能够解决3m-regular拓扑下的拜占庭将军问题。改进后的算法OM(m, p)如下：

  1. 选择c的一个邻居集合N，N的大小为p，且N为regular-set.
  2. c将他的消息v发送给N中的每个l.
  3. 对N中的每个i，副官i从c处接收到v(i)消息（默认为retreat），i将”c told me to v’(i)”以如下方式发送给任意其它副官k：
    1. m = 1, 则沿路径$p_{i,k}$发送，消息内容被直接信任。
    2. m > 1, 则他以统帅的角色使用OM(m-1, p-1)算法发送，新的通信关系图为将原本的c从原图G中移除所得。
    3. 当i为忠时v’(i) = v(i)，否则v’(i)视k不同可以有不同选择。
  4. 类似于OM(m)算法的第3步，每个N中的将军对步骤3中收到的所有”c told me to xxx”消息的值作判断，最后得出向量V，执行majority(V).

注意到3中执行OM(m-1, p-1)算法时需要在新的统帅的邻居集合中选取大小为p-1的regular-set，因此要使算法能够持续进行，需要保证原图G为p-regular的。
因此我们可以规定，OM(m, p)算法只在G为p-regular时有定义。

Proof of algorithm OM(m, p)

类似于OM(m)的证明，需要如下引理：

Lemma2: 对于任意的$m > 0, k \geq 0, p \geq 2k + m$，如果最多k个叛徒，则OM(m, p)满足IC2.

Proof: 对m作归纳:

  • m = 1时，若c为忠，则所有的v(i) = v，考虑某个忠的副官i，他收到的步骤3中的消息均来自不相交的路径（regular-set的要求），这样的消息有$p \geq 2k+1$个，而叛徒最多不超过k，于是，一半以上的路径是全忠的（鸽巢定理）。于是i最终的V中有超过一半的值为v，majority(V) = v，IC2满足。
  • 假设m = m’-1时满足。
  • m = m’时，如果c为忠，所有v(i) = v, 考虑某个忠的副官i，他收到的步骤3中的p个消息中，一半以上来自忠的l（p > 2k），归纳假设，步骤3中忠的l发出的消息”c told me to v”不会被曲解，即i最终的V中，一半以上为v，IC2满足。

Theorem3: 对任意的$m > 0, p \geq 3m$，最多m个叛徒时，算法OM(m, p)(有定义意味着G为p-regular)能够满足IC1, IC2, i.e. 可以解决拜占庭将军问题。

Proof:

  • 根据Lemma2，令k=m，可得IC2满足，只需证明IC1，即c为叛徒的情况下，所有忠将的行为依然保持一致。为此我们只需证明所有忠将在步骤4中的V全等。
  • m = 1时，最多一个叛徒，于是就是c，其余所有l为忠，根据算法步骤3中的情况1，所有的l收到同样的$V = \{v(i)\}$，IC1满足。
  • 与OM(m)的证明类似，对m作归纳可得结论，这里不再赘述。

OM(m, p)需要G至少为3m-regular，这是一个非常苛刻的要求，当总将军数为3m+1时，G必为完全图。因此这样的扩展算法并不是很有效。

Extension of algorithm SM

扩展算法SM时，不需要对G作非常苛刻的假设，事实上只需满足：

  • 所有忠将构成的子图是连通的。

这被称为 weakest connectivity hypothesis，因为当它不满足时，拜占庭将军问题不可解，理由如下：

  1. 如果c忠，且某个l与c之间通信必须经过一个叛徒，则无法保证该l会执行c发出的指令（考虑叛徒不作任何转发）。
  2. 如果某两个l为忠，且他们之间通信必须经过一个叛徒，则无法保证他们会得到相同的判断（考虑c为叛徒，c给两个忠的l发不同消息，且其余叛徒不进行任何转发）。

对SM算法的修改十分简单，只需在每一步发消息时去掉无法接收的部分即可。

接下去证明如下定理：

Theorem4: 对任意的m和d，如果最多m个叛徒，且所有忠将构成的子图具有直径d（最小的d使得任意两节点可以通过某长度不超过d的路径相连），则算法SM(m + d -1)满足IC1, IC2, i.e. 解决了拜占庭将军问题。

Proof:

  • 与Theorem2的证明类似，若c忠，则c发出的消息全为v，且不能被篡改，由于联通，每个忠的i可以收到合法的v，且V(i) = {v}，IC2满足。
  • 若c为叛徒，只需证明对于任意两个忠的i，j，如果i收到合法消息$v’:0:j_1:…:j_k$, 则j也能收到值为v’的合法消息，即V(i) = V(j).
    1. j在$j_1…j_k$中，则j已然收到，结论显然。
    2. $k < m$，则i将继续转发该消息，i与j之间有一条长度不超过d的忠路径，因此总条数为 $k + d < m + d $，不超过$m + d -1$，因而可以正确传达。
    3. $k \geq m$，则由于c为叛徒，最多m个叛徒，j1-jm中至少有一个忠，则在消息传递到他时，他会继续转发消息，该消息经过长度不超过d的忠路径之后必然能够到达j，结论成立。

可以想见算法SM改更加具有实用价值。

Conclusion

拜占庭将军问题可以很容易的同构到可信系统，其中出错的程序可能导致意想不到的结果，因此可被视作叛徒。算法OM和SM都能够用于解决这类问题，但是其通信开销巨大，然而在不作其它假设的前提下，这样的开销是必须的。

Reference

  • Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982): 382-401.