\( \def\vector#1{\boldsymbol{#1}} \)

ビザンチン合意問題

Takami Torao #Byzantine #PBFT
  • このエントリーをはてなブックマークに追加

概要

ビザンチン合意問題 (Byzantine agreement problem; ビザンチン将軍問題) は分散システムにおけるサブシステム間の合意の困難さを表す例として挙げられる想定問題である。城壁に囲まれた都市を複数の部隊で攻撃することを想定する。作戦を遂行するためには将軍と城壁を取り囲んでいる各部隊の指揮官たちがその時々の作戦に合意しなければならない。しかし、以下の状況を考慮することによって問題が複雑化する。

  • 部隊は互いに遠く離れているため司令官たちがコミュニケーションをとるには伝令員を走らせる必要がある。
  • 一部の指揮官は攻撃や撤退を望んで命令を改ざんしたり握りつぶすかもしれない。
  • 一部の指揮官はうっかり次の部隊に伝え忘れたり別の伝令書を届けてしまうかも知れない。
  • 寝返りや作戦妨害をもくろむ指揮官や伝令員が紛れ込んでいて命令書をすり替えるかも知れない。
  • 伝令員が敵の弓矢に倒れたり、伝令を放棄して逃げ出してしまうかもしれない。
Byzantine Generals' Problem
Fig 1. Byzantine Generals' Problem

裏切り者の司令官は不正のためであればどのような行動も取りうるだろう。分散合意アルゴリズムがビザンチン問題耐性を持つかは以下の条件を保証できるかに依存する。

  1. 正しい指揮官は全員が同じ命令に従う。
  2. 少数の裏切り司令官は正しい司令官に不正な命令を遂行させることができない。

アルゴリズムは裏切り者の行動に関係なく条件 1. を保証する必要がある。また、正しい司令官は単に作戦命令の内容を検証するだけではなくではなく、合意のための過程も検証すべきである。

分散システムにおいては、全てのノードがある一連のルールの元で動作するよう設計し、各ノードはトランザクションを自分のデータベースに追加する前に多数のノードでトランザクション検証が正しく行われたことを検証しなければならない。現実的な実装方法として分散システムのネットワークは伝令員を走らせるより遙かに低コストでメッセージを伝達することができるため富豪的なアプローチを取ることは可能である。

ビザンチン合意

ビザンチン耐性を持つ分散合意アルゴリズムは以下の特性を持たなければならない。

\(n\) 個のプロセス \(P_0, P_1, \ldots, P_{n-1}\) がそれぞれ状態 \(s_i \in \{0,1\}\) を持つとする。1) 故障していないプロセス \(P_0\) が初期状態 \(s_0 = s \in \{0,1\}\) をとるとき、2) アルゴリズムの終了時に全ての故障していないプロセスが \(s_i = s\) の状態をとる。

合意可能条件

非同期のネットワーク環境では正常なノードであっても応答が遅れたり応答できないケースを想定しなければならない。全てのプロセス数を \(n\)、ビザンチン故障プロセス数を \(f\) としたとき、正常だが応答できなかったノードが \(f\) 個発生したとしても \(f\) 個のビザンチン故障プロセスによる不正な合意に到達させないためには、応答できた正常なプロセス数が \(f\) より多く存在しなければならない。つまり応答遅延とビザンチン障害を考慮した合意条件は以下のように表すことができる。\[ n - f_{\it byzantine} - f_{\it noreply} \gt f_{\it byzantine} \] これは一般的に以下のように表される。\[ \begin{eqnarray} n \ge 3f + 1 \label{n3f1} \end{eqnarray} \] 言い換えると、ビザンチン耐性を持った分散合意には \(n\) 個のノード中に少なくとも正常なノードが \(2f + 1\) 個存在しなければならない。また、ノードごとの応答に対して同じ結果が \(f+1\) 個集まった時点でその結果を合意とみなして良いとも言える。

いくつかの例を考えてみよう。正常なプロセスが 🍎 を提案しビザンチン故障プロセスが 🍇 を提案すると仮定する (bivalent)。このとき、全体のコンセンサスは 🍎 で合意するか、または合意に到達できず却下するか (却下に合意するか) のどちらかの状態となる必要がある。

  1. \(n=7\), \(f=2\) 構成においてビザンチン障害が 2 プロセスあり、正常な 5 プロセスのうち 2 プロセスが応答できなかった。このとき提案は (🍎×3, 🍇×2) となり \(f+1=3\) 個集まった 🍎 で合意する。
  2. \(n=7\), \(f=2\) 構成においてビザンチン障害が 2 プロセスあり、正常な 5 プロセスのうち 3 プロセスが応答できなかった。このとき提案は (🍎×2, 🍇×2) となり、どちらも \(f+1=3\) 個を満たさないため却下で合意する。
  3. \(n=7\), \(f=2\) 構成において実際のビザンチン障害が 3 プロセスあり、正常な 4 プロセスのうち 2 プロセスが応答できなかった。このとき提案は (🍎×2, 🍇×3) となり \(f+1=3\) 個集まった 🍇 で合意する。
  4. \(n=7\), \(f=2\) 構成において実際のビザンチン障害が 3 プロセスあり、正常な 4 プロセス全てが正しく応答した。このとき、提案は最終的に (🍎×4, 🍇×3) となるが、通常はパフォーマンスを考慮して先に \(f+1\) を満たした方で合意する。つまり提案の到達タイミングによってプロセスごとに合意値が異なる可能性がある。

2. のケースでは、正常だが応答できないプロセス数が \(f\) を超えたとしても、式 (\(\ref{n3f1}\)) が満たされる限り、正常なプロセスは却下で合意する (🍇 で合意することはない)。また 3. および 4. のケースでは \(f\) を超えるビザンチン故障プロセスが含まれているため 🍇 で合意することが可能となる。

このように、ビザンチン故障プロセスの数が \(f\) までは正常なプロセスの提案に合意するか、最悪でも合意は却下されるが、実際に存在するビザンチン故障プロセスの数が \(f\) を超えていた場合は深刻な状態不整合 (safety の違反) が発生しうる。

証明

以下では説明を簡単にするために \(P_0\) を提案役とし \(P_1\) の視点で記述している。

定理1 : 故障プロセス数を \(f\) とすると、\(n=3\), \(f=1\) の場合にビザンチン合意問題を解くアルゴリズムは存在しない。

提案者 \(P_0\) と他の \(P_1, P_2\) という 3 つのプロセスにおいて、\(P_1\) は \(P_0, P_1\) のどちらか、あるいは両方に故障が発生しているか分からないと仮定する。

1. \(P_1\) は \(P_0\) から 0 を受信したとしても、\(P_0\) がビザンチン故障プロセスで \(P_1\) 以外に 1 を送信している可能性があるため、0 に合意してよいかを判断することができない。合意のために \(P_1\) は \(P_0\) 以外のプロセス (この場合 \(P_1\) しかない) が何を受信したかを知る必要がある。
2. 故障プロセスが存在しない場合、\(P_0 \to P_2\) が 0 を受信したことを \(P_2\) から教われば \(P_1\) は 0 に合意することができる。
3. 故障プロセスが存在する場合、\(P_0\) から受信した 0 と \(P_0 \to P_2\) の 1 で矛盾する。しかし \(P_0\) と \(P_2\) のどちらが故障しているかが分からないため、\(P_1\) は 0 と 1 のどちらに合意して良いか 判断することができない

上記は \(P_2\) が沈黙するケースでも同じである。電子署名を使用して \(P_i \xrightarrow{x} P_j\) を改ざんできないようにすることは可能だが、故障プロセスによる沈黙のケースを防ぐことはできない。

\(n=3\) 構成において \(f=1\) の故障プロセスの存在により \(P_1\) は \(P_0\) と \(P_1\) のどちらにも従うことができず、例えば固定値のような値を採用することもできないことは明かだろう。

さらに、\(f=2\) のケースではビザンチンプロセスによる合意の乗っ取りが可能となる。

4. \(P_0\) と \(P_2\) が故障プロセスであった場合、ビザンチンプロセスによる判断の乗っ取りが可能であり \(P_1\) の合意は正しくない

以上の説明を使用して \(n \gt 3\) のケースで同様の定理を導くことができる。

定理2 : \(n \le 3f\) の場合にビザンチン合意問題を解くアルゴリズムは存在しない。

\(n \le 3f\) を満たす任意の \((n, f)\) に対して \(n\) 個のプロセス \(P_0, P_1, \ldots, P_{n-1}\) を以下の 3 つの集合 \(\vector{P}'_0, \vector{P}'_1, \vector{P}'_2\) に分ける。\[ \left\{ \begin{array}{ccl} \vector{P}'_0 & = & \{P_0, P_3, \ldots\} \\ \vector{P}'_1 & = & \{P_1, P_4, \ldots\} \\ \vector{P}'_2 & = & \{P_2, P_5, \ldots\} \end{array} \right. \]

それぞれのプロセス集合は、自分以外のプロセス集合が合意した値に対して内包する \(|\vector{P}'_i| \le f\) 個のプロセスが合意した結果を以てそれぞれのプロセス集合がある値に合意するためには、いずれか一つの

それぞれのプロセス集合を \(n=3\), \(f=1\) として定理 1 とする。この仮定の下では \(n=3\), \(f=1\) の各プロセス \(P'_0, P'_1, P'_2\) は合意可能なアルゴリズム \(\mathcal{A}_{3,1}\) が存在する。それぞれのプロセスが \(\vector{V}_0, \vector{V}_1, \vector{V}_2\) のプロセス集合を生成して、それらの間でアルゴリズム \(\mathcal{A}_{}\) を実行する。

ここで \(|\vector{P}'_i| \le f\) である。合意可能なアルゴリズム \(\mathcal{A}_{n,f}\) が存在すると仮定する。

pBFT シミュレーション

Proposer プロセスの提案で全ての正常なプロセスが合意できるかのシミュレーション。\(n\) を全てのプロセス数、\(f\) を故障しているプロセス数とする。

Loading...
# pre-prepare prepare commit