The Byzantine Generals Problem (BGP)

TL;DR

Oral Message

• 如果結點間fully connected，需要滿足 $n > 3k$ ($k$為有問題節點)才能處理BGP。
• 如果節點間不是fully connected，如果有 $k$個問題節點，則要求圖為$3k$ $regular$ (regular graph)。

Signed Message

• 如果節點間fully connected，需要滿足 $n >= k$才能處理BGP。
• 如果節點間不是fully connected，需要滿足$n >= k + d -1$ ($d$為graph diameter)。

Motivation

The Byzantine Generals Problem是分散式環境中，如果存在malfunctioning的節點，該怎麼保證剩下的節點，能正常的運作並取得consensus的問題。

The Byzantine Generals Problem

BGP要處理的是，當分散式系統中存在malfunctioning的節點，正常的節點(loyal general)仍然能正常運作，並且達成共識。

我們使用 $v(i)$代表 $i$的value，正常運作且達成共識的條件是：

• 任兩個 loyal general使用相同的 $v(i)$
• 如果 $i$是 loyal general，則$v(i)$是 $i$提出的value

BGP根據傳送訊息的方式，還可以分為：

• Oral message: 訊息無法驗證，例如malfunctioning可以宣稱它從** commander **收到attack offer，但其實是retreat
• Signed message: 訊息被sender signed過，可以保證malfunctioning node不能串改它收到的訊息內容。

Oral message相比 Signed message更難，因為無法驗證訊息，所以需要更多的loyal general和更多的訊息傳遞來形成共識。

3-Generals Problem

3-Generals Problem是系統中只存在3m個node，且被證明在oral message的條件下，如果存在一個m以上的malfunctioning node，3-generalss problem沒有解。

Oral Message

Fully connected

如果系統中所有的node都可以直接傳訊息給其他node，也就是整個系統fully connected的情況下，要處理BGP至少需要$n > 3k$ ($k$為malfunction node)。

可以利用反證法來證明，假設存在一個演算法可以使 $n <= 3k$的情況下處理BGP，我們假設3個node的BGP，我們把每個node視為m個 3-Generals Problem的node，因為存在一個malfunctioning node，所以轉換過去也是m個malfunctioning node，因此我們可以把BGP reduce成 3-Generals Problem，如果BGP有解，則代表3-Generals Problem有解，但這跟我們所知矛盾，因此不存在 $n <= 3k$的解。

用 $OM(k)$代表演算法要處理的 malfunctioning node數目

1. 當 $k = 0$，$commander$ 送訊息給其他node，其他node使用收到的訊息或是沒收到就用default。
2. 當 $k > 0$：

• commander送 value給其他node
• 當 $i$ 收到 commander來的value，它把$v_i$傳給它和commander以外的node，並執行 $OM(k-1)$
• 當 $i$ 從非commander的其他node $j$ 收到 $v_j$，它做 $majority(v_1,...,v_{n-1})$

lemma 1

在證明 $om(k)$ work之前，先證明一個lemma: 對任何一個 m & k, $OM(k)$ 在 $n > 2m+k$ 的情況下滿足條件2。

證明如下： 在step2的時候， 除了commander以外的n-1個node會apply $OM(k-1)$，而我們知道 $n > 2k+m$，所以可以得到 $n-1 > 2k + (m-1) >= 2k$，因為只有$k$個malfunctioning node，所以loyal general是majority，因此條件2可以被滿足。

proof

從上面的lemma，當$m = k$的時候可以用數學歸納法來證明此演算法，當 $n > 3m$的時候，$OM(m)$ 可以處理BGP。當m=0的時候，沒有malfunctioning node所以 $m = 0$ 成立。

我們假設 $m - 1$的時候使演算法也成立，嘗試證明$m$的時候也成立。假設 commander是loyal，則條件1,2都可以被滿足，因此要證明當commander 是malfunctioning node的時候，也能滿足條件1&2。

當commander 是malfunctioning node，代表其他只剩下$m - 1$個 malfunctioning node，而因為 $n > 3m$，所以至少還有 $3m - 1$個node，而$3m-1 > 3(m-1)$，因此我們可以可以使用 $OM(m-1)$來遞迴處理，而$m-1$已經被證明可行，所以我們$m$也可行，故得證。

Not Fully Connected

如果系統中不是所有node都跟其他node有連接，也就是整個graph不是fully connected，要處理BGP還需要一個額外條件，就是graph是一個$p-regular$的 graph。

延伸 $OM(k)$至，$OM(k, p)$ （$p$為regular的數目），要證明 $OM(k, 3k)$ 可以處理BGP。

lemma 2

對任何一個 $m > 0$且$p >= 2k + m$，$OM(m, p)$滿足條件2。

證明： 當 $m = 1$，此式子為$p >= 2k+1$，因為我們有 $p$條到目的的path，因為只有 $k$個malfunctioning node且$p >= 2k+1$，因此有半數以上的path是由loyal general組成，所以loyal commander的value會是majority，故滿足條件2。

當 $m > 1$，由上明顯可知在 $m > 1$的情況下，$p >= 2k+m$ 一定是majority，所以也滿足條件2。

proof

由上可知當$k = m$且$p = 3m$，滿足lemma 2，如果commander是loyal則滿足條件1，因此我們只需要證明當commander是malfunctioning node也滿足條件1。

當 $m = 1$，我們可以很快的畫圖知道，loyal general的node傳遞的傳遞的訊息不經過commander，所以它們可以達成共識，當$m > 1$，因為 $p >= 3m$，扣掉commander以後， $p - 1 >=$ $3(m-1)$，所以此式可以遞迴到 $m = 1$，故得證。

Signed Message

Signed message有兩個特徵：

1. 可以識別是由哪個node發出的訊息，且malfunctioning node不能偽裝成loyal general node。
2. malfunctioning node可以偽裝成另外一個malfunctioning node

假設 $0$是commander，當node $i$收到 offer $v$，它會copy以後再把$v$sign過，然後傳給其他還沒收到過的node。舉例來說，假設$i$收到 $v:0:...:j$，因為$v$已經被node $0...j$ signed，所以 $i$會signed然後把$v:0:...:j:i$傳給不在上面的節點。

Fully Connected

當graph是fully connected，我們演算法$SM(k)$可以解決$k$個malfunctioning node以下的 BGP

proof

當commander是loyal general，因為malfunctioning node無法偽裝成loyal general，所以他offer的value必定可以被其他人使用且形成共識。

當commander是malfunctioning node，因為loyal general node是majority且會互相傳遞訊息，所以它們會知道commander是malfunctioning node並形成共識。

Not Fully Connected

如果有 $m$個 malfunctioning node且graph的diameter為$d$，則需要$n >= m+d-1$。

proof

當loyal general nodes是connected，則我們在$n-2$個node裡面必定會存在至少一個loyal general，所以是 $SM(n-2)$。

當loyal general nodes不是connected，但是有部分(subgraph)的loyal general node 是connected，在$m+d-1$的路徑上，並定至少經過一個loyal general node，所以可以知道commander不是loyal並形成共識。