レッスン0 — BFT 問題をゼロから

問い

午前 3 時。30 ノードの chain で、1 バリデータが矛盾する 2 つのブロックに同時に署名した。他のバリデータは両方に投票している。Chain は split-brain。まず何を見にいくか？ なぜこれが起こりうるのか — コンセンサスがそもそもどんな故障を生き延びるための仕組みなのか — のメンタルモデルがなければ、次の 8 時間を当てずっぽうで過ごすことになる。

注: このコースのコードブロックは「実行可能な最小例」と「概念説明の抜粋」が混在する。... や todo!() を含むブロックは概念スニペット（コンパイル不要）。

原理（最小モデル）

• 3 つの性質は条件なしには同時に満たせない。 Safety（split-brain にならない）、Validity（誰も提案していない値を勝手に決めない）、Liveness（いつかは決定する）。特に「完全非同期 + 故障あり」では 3 つを同時に得ることはできない（FLP）。コンセンサス研究の分野全体が、どのユースケースに対してどのトレードオフなら許容できるかを見極めることに費やされてきた。
• 故障モードは crash / omission / partition / Byzantine の 4 つ。 Byzantine が最難（嘘をつくノード、A と ¬A 両方に署名）。Crash + omission は相対的に扱いやすい。
• 3f+1 ルール。 f 個の Byzantine を許容するには常に 3f+1 ノードが必要。数学的に厳密な結果（Lamport-Pease-Shostak 1982）であって設計選択ではない。
• FLP 不可能性（1985）。 完全非同期 + 1 crash で、決定論的プロトコルは safety と liveness を同時に保証できない。実プロトコルは「タイムアウト」「ランダム性」「view change」のいずれかで脱出する。

具体例

n=4, f=1  →  3f+1=4 を満たす（境界）
n=7, f=2  →  3f+1=7 を満たす（境界）
n=10, f=3 →  3f+1=10 を満たす（境界）

quorum 算術: quorum サイズ q、ノード総数 n。2 quorum は 2q−n ノードで重なる。重なりに 1 つの正直ノードが必要 → 2q − n > f → q > 2f → q ≥ 2f+1。代入で 2(2f+1) − n > f → n > 3f → n ≥ 3f+1。

各プロトコルが選ぶ妥協:

失敗例（誤解）

「Bitcoin は絶対に停止しない」「Bitcoin は BFT である」— 両方とも技術的には間違い だが、間違い方が違う。Bitcoin は safety を確率的にしか保証しない（reorg がいつでも起こりうる）。BFT は safety を絶対保証する代わりに liveness を諦める。「Bitcoin は最高、何も犠牲にしない」は典型的な混乱。

🛑 予測。 3 ノード A、B、C が単一の値に合意しなければならない。どこで何がうまくいかなくなり得るか？ 異なる故障モードを 4 つ列挙。（「ネットワークが遅い」だけではない。答え: ① crash → ノードが落ちる、② omission → メッセージが選択的に落ちる、③ partition → ネットワークが分断、④ Byzantine → ノードが嘘をつく / 矛盾する票に署名。）

ステップで組み立てる

Step 1: Safety / Validity / Liveness を 1 文ずつ言える

• Safety: A が x を決め、B が y を決めたら、x = y
• Validity: 「42」について誰も話していないのに、勝手に「42」で合意できない
• Liveness: 有限時間内に決定がなされる

Step 2: 4 故障モードを 1 例で覚える

• Crash → 電源リセット
• Omission → パケットロス、検閲
• Partition → 海底ケーブル切断
• Byzantine → 鍵侵害、バグ

Step 3: 3f+1 の代数を紙にスケッチ

quorum 重なり > f → q ≥ 2f+1 → n ≥ 3f+1。3f では不可 の理由まで言えるようにする。

Step 4: FLP 脱出経路を 3 つ言える

• タイムアウト（同期仮定）
• ランダム性（確率的 finality）
• View change（一時的に liveness を諦める）

実プロトコルはどれも少なくとも 1 つの脱出経路を使っている。Tendermint = タイムアウト + view change。Bitcoin = ランダム性。Ethereum PoS = 両方。

答え合わせ

• 3 ノード A/B/C の故障モード: crash / omission / partition / Byzantine の 4 つ列挙できれば OK。
• f = ? @ Ethereum: ~100 万バリデータなら f < 333,333。「Byzantine」 = 「報酬で買収された / 侵害された / その両方によってプロトコルに反する動きをするバリデータ」。
• Bitcoin が犠牲にしているもの: safety（確率的 finality）。chain weight ベースなので最長 chain ルールが勝ち、reorg が起きうる。これが 3f+1 ルールの反例にならないのは、Bitcoin が そもそも BFT を主張していない から。

合格基準

• 4 故障モードを即答できる（crash / omission / partition / Byzantine）。
• 3f+1 ルールの代数（quorum 重なり > f）を 1 分で紙に書ける。
• FLP の意味と 3 脱出経路を言える。
• 「Ethereum は両方使う」「Bitcoin はランダム性のみ」「Tendermint はタイムアウト + view change」の対応が頭に入っている。

まとめ（3行）

• Safety / Validity / Liveness は同時に満たせない — 必ずトレードオフ。
• 3f+1 は数学的結果（Lamport-Pease-Shostak 1982）。f Byzantine を許容するには quorum 重なり > f が必要。
• FLP 不可能性は実プロトコルでは「タイムアウト / ランダム性 / view change」のいずれかで回避する。