拜占庭将军问题

Table of Contents

定义

拜占庭共识: 解决有坏人的情况下好人如何达成共识, 是分布式计算领域的一个重要问题。

完整陈述

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

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

结论: 假设叛徒的数量是 \(m\) ,当 \(n \leq 3m\) 时, 无法达成共识, \(n>3m\) 时存在达成共识的构造算法.

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

算法

以下算法我们称为 OM (Oral Message) 算法,是一个递归式的消息传播算法,执行 \(m\) 轮的 OM 算法叫做 \(OM(m)\) 。 具体流程如下

  • 在前向传播过程中,对于每条从根出发的消息传播路径 \(p := g_0 \rightarrow g_1 \rightarrow \cdots g_i\) , 将军 \(g_i\) 把自己当作主官,将它得到的命令发送给不在 \(p\) 中的所有其它将军,进行 \(m\) 轮。
  • 在后向收集过程中,每个将军 \(g\) 取其“在前向传播过程中接收到司令的命令” 和 “在下一层中以 \(g\) 结尾的路径做出的决策” 的众数作为每条路径的决策。

最后我们取第一层每个将军的决策做为最终决策。算法图示如下:

2017-04-17-22-13-21.jpg

前向实箭头表示正向传播,不忠诚的将军可以发送虚假消息(比如给不同的将军发送不同消息);反向虚箭头表示反向收集,指向自己本人。 同一个将军在不同路径下有不同的决策,同一个将军在同一层可以出现多次(前缀不同)。

模拟代码如下:

"""
Byzantine Generals Problem, Oral Message(OM) Algorithm
Author: expye(Zihao Ye)
"""
from typing import List, Tuple
import argparse
import numpy as np
from collections import Counter


def majority(lst: List):
    """Note that we should output the same value for [0, 0, 1, 1] and [1, 1, 0, 0]"""
    c = Counter(sorted(lst))
    return c.most_common()[0][0]


class General:
    def __init__(self, truthful: bool) -> None:
        self._truthful = truthful

    def __call__(self, input):
        """If truthful, always output input, otherwise output random value."""
        if self._truthful:
            return input
        else:
            return np.random.randint(2)


class OralMessage:
    def __init__(self, generals: List[General], n: int, k: int) -> None:
        """
        Parameters
        ----------
        generals : List[General]
            The general list.
        n : int
            Number of generals.
        k : int
            Number of traitors.
        """
        self.generals = generals
        self.n = n
        self.k = k
        # record traces: (path, command, remaining number of rounds)
        self.trace = []
        self.received = {}  # received commands of each path started from root
        self.vote = {}      # final vote of each path

    def propagate(self, ancestors: Tuple[int], command: bool, m: int):
        """
        Regard current node as commander, propagate message for $m$ rounds, and collect traces.

        Parameters
        ----------
        ancestors : Tuple[int]
            The message passing path from root to current node.
        command : bool
            The command current node received.
        m : int
            The remaining number of rounds.
        """
        self.trace.append((ancestors, command, m))  # collect traces.
        if m > 0:  # not in the last round
            commander = ancestors[-1]
            for i in range(self.n):
                if not i in ancestors:  # send messages to other generals
                    self.propagate(ancestors + (i,),
                                   self.generals[commander](command), m - 1)

    def gather(self, ordered_trace: List[Tuple[Tuple[int], bool, int]]):
        """
        Back propagation and take majority of received commands of each path as its vote.

        Parameters
        ----------
        ordered_traces : List[Tuple[Tuple[int], bool, int]]
            Collected traces sorted by topological order.
        """
        for ancestors, command, m in ordered_trace[:-1]:
            commander = ancestors[-1]
            if m == 0:  # in the last round, take the command received in forward phase.
                vote = self.generals[commander](command)
            # take majority of received (in forward/backward phase) commands
            else:
                vote = self.generals[commander](
                    majority(self.received[ancestors] + [command]))
            self.vote[ancestors] = vote
            if len(ancestors) > 1:  # update received commands for m-1 level paths
                j = ancestors[: -2] + (commander,)
                if not j in self.received:
                    self.received[j] = []
                self.received[j].append(vote)


if __name__ == '__main__':
    parser = argparse.ArgumentParser("Byzantine generals simulator.")
    parser.add_argument('--n', '-n', type=int, help='number of generals')
    parser.add_argument('--m', '-m', type=int, help='number of runs')
    parser.add_argument('--k', '-k', type=int, help='number of traitors')
    args = parser.parse_args()
    traitors = np.random.choice(args.n, args.k)
    is_truthful = np.ones(args.n, dtype=np.int32)
    is_truthful[traitors] = 0
    generals = []
    for i in range(args.n):
        generals.append(General(is_truthful[i]))

    om = OralMessage(generals, args.n, args.k)
    om.propagate((0,), 1, args.m + 1)
    om.gather(sorted(om.trace, key=lambda _: _[2]))

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

    for i in range(1, args.n):
        print(om.vote[(0, i)], end='')
    print()


"""
example: python byzantine.py -n 10 -k 3 -m 3
output:
t
tttftttff
111011101

The commander is a loyal general, and all loyal generals made the same decision: 1.
"""

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

性质及证明

两个性质:

  1. (IC1): 所有忠诚的将军遵从相同命令
  2. (IC2): 若司令是忠诚的, 所有忠诚的将军遵从他的命令.

定理:

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

定理 1

对 \(m\) 使用归纳:

  1. \(m=0\) 时,没有后向收集过程,每个将军 \(g\) 受司令直接指挥,如果 \(g\) 是忠诚的,将遵从司令的命令。
  2. \(m>0\) 时,消息从司令 \(c\) 发到每个将军 \(g_i\) 之后,每个将军 \(g_i\) 将以自己为司令,在子树上进行 \(OM(m-1)\) 算法。由于 \(n-1>2k+m-1\) ,由归纳假设得 \(IC2(n-1, k, m-1)\) 是成立的。因此在后向收集过程中,对于每个忠诚的将军,至少有 \(n - k - 1\) 个接收到的指令跟 \(c\) 发送过来的指令是一致的 (一个来自 \(l\) ,至少 \(n - k - 2\) 个来自后向收集)。由前提 \(n > 2k + m\) ,可知 \(n - k - 1 > k + m - 1 \geq k\) ,求众数即可达成共识。

定理 2

定理 2 的 IC2 部分直接带入定理 1 即可, IC1 部分同样对 \(m\) 使用归纳:

  1. \(m=0\) 时,没有叛徒,所有将军都会遵从司令的命令。
  2. \(m>0\) 时
    1. 如果司令是忠诚的,那么由IC2,所有忠诚的将军将遵从司令的命令。
    2. 司令不忠诚,那么由归纳假设 \(IC1(n-1, m-1)\) 和 \(IC2(n-1, k-1, m-1)\) ,后向收集时所有忠诚将军将得到一样的指令列表,可以达成共识。

下界 1

\(n \leq 3m\)

可以证明当 \(n\leq3m\) 时是无法达成共识的, 过程非常精妙, \(m=1\) 的情况可以用这张图来说明: 2017-07-11-01-49-28.png 2

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

  • 在 case 1 中, \(A,B\) 分别收到:
\ A B
from A 1 1
from B 1 1
from C 0 1
  • 在 case 2 中, \(B',C'\) 分别收到:
\ B' C'
from A 0 1
from B' 0 0
from C' 0 0
  • 在 case 3 中, \(A, C'\) 分别收到:
\ A C'
from A 1 1
from B 1 0
from C' 0 0

注意到:

  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 算法

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

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

具体流程如下: 2017-07-11-02-23-10.png

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

参考文献

Footnotes:

1

Update in 2017.07, after Prof. Elaine Shi's class.

Author: expye(Zihao Ye)

Email: expye@outlook.com

Date: 2017-04-17

Last modified: 2021-10-25 Mon 21:58

Licensed under CC BY-NC 4.0