拜占庭将军问题

一个拜占庭军队有 n 个将军, 其中一个主官领导, 其余 n-1 个副官, 主官发出消息给副官, 要求:

• 每个将军要么是忠诚的, 要么是叛徒.
• 一个有两种命令: 进攻/撤退.
• 所有的将军通过接收和传递消息(进攻/撤退)通信.
• 所有的忠诚的将军最后要达成共识: 一起进攻或者一起撤退.

结论: 当 \(n<=3m\) 时, 无法达成共识, \(n>3m\) 时存在达成共识的构造算法.

很早就见过这个问题, 不过由于大部分版本的证明很容易让人误解, 所以一直没有理解证明. 最近读了一遍原论文: The Byzantine Generals Problem, 条理非常清楚, 终于弄懂了证明. 让我很吃惊的是, 这篇 paper 是发在 TOPLAS(PL/System)上而不是 Theory 相关的期刊上的, 可见"好的工作"既有应用价值也有坚实的理论基础.

由于使用参数不同可能造成误导, 用代码描述算法流程更清楚一些:

"""
Byzantine Generals Problem, Oral Message(OM) Algorithm
Author: expye(Zihao Ye)
Format: 
  pos 0:        commander
  pos 1-n:  generals
"""
import numpy as np
from collections import Counter

generals = []
votes_list = {}
votes = {}
nodes = []
n = 10
m = k = 3

def general(flag):
  def truthful(input):
    return input
  def traitor(input):
    return input if np.random.rand() < 0.5 else 1 - input
  return truthful if flag else traitor

def majority(lst):
  c = Counter(lst)
  return c.most_common()[0][0]

def propagate(parents, command, n, m):
  if m > 0:
    current = parents[-1]
    for i in range(n):
      if not i in parents:
        propagate(parents + [i], generals[current](command), n, m - 1)
  return nodes.append((tuple(parents), command, m))

def gather(reversed_nodes):
  for parents, command, m in reversed_nodes[:-1]:
    current = parents[-1]
    votes[parents] = generals[current](command) if m == 0 else
        generals[current](majority(votes_list[parents] + [command]))
    if len(parents) > 1:
      j = tuple(list(parents)[: -2] + [current])
      if not j in votes_list:
        votes_list[j] = []
      votes_list[j].append(votes[parents])

if __name__ == '__main__':
  pos = np.random.choice(n, k)
  is_truthful = np.ones(n)
  is_truthful[pos] = 0
  is_truthful = list(is_truthful)
  for i in range(n):
    generals.append(general(is_truthful[i]))

  propagate([0], 1, n, m + 1)
  gather(sorted(nodes, key = lambda tup: tup[2]))

  print 't' if is_truthful[0] else 'f'
  for i in range(1, n):
    print 't' if is_truthful[i] else 'f',
  print

  for i in range(1, n):
    print votes[(0, i)], 
  print

用 DFS 递归下去(BFS 也可以), 然后逆 BFS 序收集回来, 时间复杂度为 \(O(n^m)\).

两个性质:

1. (IC1): 所有忠诚的将军遵从同意指令(可能是假的)
2. (IC2): 若司令是忠诚的, 所有忠诚的将军遵从他的指令.

性质 2 一般的协议很容易满足, 比较厉害的一点是性质 1.

定理:

1. \(n > 2k + m\) , 至多 \(k\) 个 traitor, \(OM(m)\) 满足 IC2.
2. \(n > 3m\) , 至多 \(m\) 个 traitor, \(OM(m)\) 满足 IC1, IC2.

定理 1 比较 trivial; 定理 2 的 IC2 部分直接带入定理 1 即可, IC1 部分可以用图示来说明: 前向实箭头表示正向传播, 可以欺骗; 反向虚箭头表示反向收集, 指向自己本人, 欺骗与否都只影响自己的判断. 那么由递归的 IC1 可得, 连向所有诚实的将军的反向同色虚箭头均携带相同的值, 因此他们会做出同样的决策. Q.E.D.

可以证明当 \(n<=3m\) 时是无法达成共识的, 过程非常精妙, \(m=1\) 的情况可以用这张图来说明: ²

假设每个节点初始时携带有一个信息 1(相当于主官做了第一轮广播), 其中处于两个状态的节点代表是不诚实的节点, 不带 prime 的节点向外发送 1, 带 prime 的节点向外发送 0.

• 在 case 1 中, \(A,B\) 分别收到:

• 在 case 2 中, \(B',C'\) 分别收到:

• 在 case 3 中, \(A, C'\) 分别收到:

注意到:

1. case 1 中 \(A,B\) 必须达成共识, 而 \(A\) 无法区分 case 1 和 case 3, 所以在 case 1 和 case 3 中, \(A\) 会做出相同决策.
2. case 2 中 \(A,C\) 必须达成共识, 而 \(C'\) 无法区分 case 2 和 case 3, 所以在 case 2 和 case 3 中, \(C'\) 会做出相同决策.

因此 \(A, B, B', C'\) 均会做出相同决策, 这种情况是平凡的.

证明可以推广至 \(m>1\) 的情形:

前提: 设 \(n=3m\) 时好人可以达成共识.

假设 \(n=3m\) , 将 \(n\) 个节点分为三组 \(S_A, S_B, S_C\) , 假设每组由一个总的处理器控制, 分别为 \(A,B,C\) , 所有节点之间互相传递的消息都经过相应组的总处理器, 总处理器的输出结果为该组达成的共识. 假设 \(A\) 由坏人控制, 那么由前提得 \(S_B, S_C\) 可以达成共识. 此时 \(B,C\) 达成了共识, 与 \(n=3\) 时的结论矛盾.

Dolev-Strong 是一类基于签名机制的拜占庭算法, 它并不需要满足 \(n>3m\) 的限制.

思路是, 每个节点在收到信息并发送时, 用自己的私钥签名在最后附上, 协议假设每个用户的公钥都是 common knowledge. 这样便杜绝了坏人修改信息的可能(否则可以通过签名得知).

具体流程如下:

算法需要 \(m+1\) 轮结束, 因为需要保证收到的消息至少经过了一个诚实的节点.