Introduction

拜占庭将军问题是指，当一群将军（计算机）打算攻打拜占庭王国的城堡（达成一致）时，约定进攻策略（一致内容）的问题。这个问题的前提是，攻下城堡或撤退（达成一致）所需要的将军（节点）数量是小于等于将军中忠诚将军（忠诚节点）的数量的。

拜占庭将军问题实际上是一个分布式系统的一致性问题。解决的核心问题是对叛徒节点的tolerance。

Magical $\frac{1}{3}$

这里介绍一些便于理解的思路

假定节点总数是$n$，作恶节点数为$m$，那么剩下的正确节点数为 $n - m$，意味着只要收到 $n - m$ 个消息且 $n - m > m$ 就能做出决定，但是这 $n - m$ 个消息有可能有 $m$ 个是由作恶节点冒充的（或因网络延迟导致f个恶意节点的消息先被收到），那么正确的消息就是 $n - m - m$ 个，为了多数一致，正确消息必须占多数，也就是 $n - m - m > m$ ，所以N最少是 $3m + 1$ 个。
拜占庭容错算法BFT的33%

Complexity

为何oral massage algorithm的复杂度是$O(N^{m+1})$？

算法

从论文出发来分析一下：

A commanding general must send an order to his $n - 1$ lieutenant generals such that:

IC1: All loyal lieutenants obey the same order.
IC2: If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

这是两个重要的 interactive consistency conditions，满足这些，就认为保持了一致性。

先扔出论文中的几个assumption：

A1. Every message that is sent is delivered correctly.

不考虑丢包

A2. The receiver of a message knows who sent it.

信息来源已知

A3. The absence of a message can be detected.

可以感知哪个将军没有进行决策

A1 和 A2 可以防止叛徒干扰另外两名将军之间的通信，因为根据 A1，不能干扰将军发送的消息，而根据 A2，不能通过引入虚假消息来混淆将军的通信。 A3 防止叛徒试图通过不发送消息来阻止决策。这些假设的实现在论文中的section 6得到阐述。

提出算法的定义：

$OM(m)$: oral massage algorithm when the number of malicious node is $m$.
$v_i$: lieutenants $i$ “obtaining a value” as its command.
$majority(v_1, …, v_{n-1})$: for each lieutenant, its value $v_i$ should equal to the majority of the $(v_1, …, v_{n-1})$ received from other lieutenants.

在正式开始推导之前，再提出两个限制：

choose the majority value among the $v_i$ if it exists, otherwise the default value $RETREAT$;
The median of the $v_i$, assuming that they come from an ordered set.

符合majority多于一半的原则

对于 Algorithm $ OM(0)$：

The commander sends his value to every lieutenant.
Each lieutenant uses the value he receives from the commander, or uses the value RETREAT if he receives no value.

对于 Algorithm $OM(m) , m > 0$：

The commander sends his value to every lieutenant.
For each $i$, let $v_i$ be the value Lieutenant $i$ receives from the commander, or else be $RETREAT$ if he receives no value. Lieutenant $i$ acts as the commander in Algorithm $OM(m - 1)$ to send the value $v_i$ to each of the $n - 2$ other lieutenants.
For each $i$, and each $j \ne i$, let $v_j$ be the value Lieutenant $i$ received from Lieutenant $j$ in step (2) (using Algorithm $OM(m - 1)$), or else $RETREAT$ if he received no such value. Lieutenant $i$ uses the value $majority (v_1,…,v_{n-1} )$.

论文认为这个算法可以解决拜占庭问题

证明

实际上就是证明算法满足互相一致性条件。

**LEMMA 1.** For any $m$ and $k$, Algorithm $OM(m)$ satisfies **IC2** if there are more than $2k + m$ generals and at most $k$ traitors.

如果有多于 $2k+m$ 个将军而且将军中叛徒的数量不多于 $k$ 个，那么算法满足IC2。

当 $m=0$ 时，此时 commander 一定是忠诚的，显然成立。

在引理中，我们有 $n > 2k + m$，所以有 $n - 1 > 2k + (m - 1)$ 。假设 m-1 时成立，当为 m 时，通过归纳法应当也成立。

由于叛徒最多有 $k$ 个，且 $n - 1 > 2k + (m - 1) \geq 2k$，因此 $n - 1$ 名副官中的大多数是忠诚的。因此，对于 $n-1$ 个中的大多数lieutenant $i$，每个忠诚的 lieutenant 都有$v_i = v$，因此他在step 3中获得$majority (v_1,…,v_{n-1})=v$ ，证明IC2。

重头戏来了

THEOREM 1. For any $m$, Algorithm $OM(m)$ satisfies conditions IC1 and IC2 if there are more than $3m$ generals and at most $m$ traitors.

依然使用归纳法证明：

如果没有叛徒，容易得到 $OM(0)$ 满足 IC1 and IC2。假设定理对于 $OM ( m - 1)$ 成立，归纳证明 $O M ( m ), m > 0$ 的情况。
先考虑 commander 忠诚时的情况，使用 lemma1 并使 $k=m$，当 commander 是忠诚的时，IC1实际上就自然被满足了。
考虑 commander 是叛徒的情况，此时，在 $n-1$ 个 lieutenant 中至多有 $m-1$ 个 lieutenant 是叛徒，且 $n-1>3m-1$ ，说明 lieutenant 的数量多于 $3m-1$ 。同时， $3m-1>3(m-1)$，正好符合定理在 $m-1$ 时的情况（假设正确）。也就是说，对于 $n-1$ 的情况，当新的 commander 是叛徒时，可以保证忠诚的 lieutenant 做出了一致的决策；当新的 commander 是忠诚时，可以保证忠诚的 lieutenant 听从忠诚的 commander（做出了一致的决策）。发现了吗，所有忠诚者的决策向量应当是一致的，所以可以推断得到，所有忠诚者的最终决策 $v$ 都是一样的。回到 m 的情况，此时竟然自然地满足了 IC1。

至此，定理得证。