ビザンチン障害耐性（BFT）と 3f+1 の理由

ビザンチン故障とは何か

分散合意（/devops/flp-impossibility/）で扱う故障モデルには段階があります。最も弱いのがクラッシュ故障で、ノードはただ止まるだけ、止まる前に嘘はつきません。これに対しビザンチン故障は、ノードが任意の振る舞いをすることを許す最も強い故障モデルです。乗っ取られたノードは黙るだけでなく、偽の値を送り、メッセージを改竄し、さらに厄介なことに相手ごとに矛盾した値を送る（AにはX、BにはYと言う）こともできます。

名前は Lamport らの「ビザンチン将軍問題」（1982）に由来します。包囲した複数の将軍が攻撃か撤退かを合意したいが、一部の将軍は裏切り者で、伝令に偽情報を流す——というたとえです。

クラッシュ耐性とBFTは別物

クラッシュ故障なら、止まったノードは単に「無言」になるだけなので、生き残った過半数（n≥2f+1） で合意できます。RaftやPaxosはこの世界の住人です。しかしビザンチン故障では「無言」ではなく「積極的に嘘をつく」ため、過半数では足りません。必要なのは n≥3f+1 です。

なぜ過半数では足りないのか

直観をまず掴みます。f 台が嘘をつけるとき、過半数決（n≥2f+1）が破れる状況を考えます。n=3, f=1 とすると、3台中1台が裏切り者です。残り正直な2台が異なる初期値（片方は0、片方は1）を持つと、裏切り者は0派には「自分も0だ」、1派には「自分も1だ」と矛盾した証言をできます。すると0派から見れば2対1で0、1派から見れば2対1で1となり、両陣営が別々の値を確定してしまいます。安全性（同一値への合意）が壊れるのです。投票数を数えるだけでは、矛盾証言を見抜けません。

3f+1 を定足数の交差から導く

本質は定足数（quorum）の交差にあります。BFTプロトコルは「ある決定が成立した」と判断するために、一定数 q 台以上の賛同（定足数）を集めます。ここで満たすべき2つの条件を立てます。

条件	要求	理由
可用性	n - f 台で定足数を満たせる	f 台が応答しなくても前進できる必要がある（q ≤ n - f）
安全性	2つの定足数の重複に正直ノードが1台以上残る	矛盾する2決定が同時に成立しないため

定足数を q とします。2つの定足数 A と B が重なるノード数は、包除原理から最低 2q - n 台です。この重複には裏切り者が最大 f 台紛れ込みうるので、正直なノードが1台以上重なるには次が要ります。

2q - n  >  f        … 重複から偽証 f 台を除いても1台残る

一方、可用性から q ≤ n - f（落ちている f 台を当てにできない）。この2式を連立します。q ≤ n - f を上式へ代入すると 2(n - f) - n > f、整理して n > 3f、すなわち n ≥ 3f+1。定足数 q は両式を同時に満たす最小値として q = 2f+1 となります。

2f+1 という定足数の意味

n=3f+1 のとき定足数は q=2f+1。任意の2つの定足数（各 2f+1 台）は、3f+1 台中で最低 (2f+1)+(2f+1)-(3f+1) = f+1 台で重なります。この f+1 台の重複に裏切り者が最大 f 台いても、必ず正直なノードが少なくとも1台残る。この1台が2つの決定の橋渡しとなり、矛盾した確定を防ぎます。

これが「過半数（n/2 超）では足りず、3分の2超が要る」という有名な比率の根拠です。n≥3f+1 は同期前提を置かない非同期BFTでの理論下限であり、PBFTはこれを達成します。

PBFT の3フェーズ

PBFT（Practical Byzantine Fault Tolerance, Castro–Liskov 1999）は、部分同期を仮定してこの下限で実用的に動く最初のプロトコルです。1つのプライマリ（リーダー）と複数のバックアップからなり、クライアントの要求を以下の3フェーズで確定します。

フェーズ	送信者→受信者	成立条件	目的
pre-prepare	プライマリ→全バックアップ	—	要求に連番（シーケンス番号）を割り当て順序を提案
prepare	各ノード→全ノード	2f+1 票で prepared	「この連番にこの要求」という割り当てに全員が合意（順序の固定）
commit	各ノード→全ノード	2f+1 票で committed	十分多数が prepared に達したと相互確認し実行を確定

なぜ2フェーズ（prepare／commit）の投票が要るのか。prepare だけでは、ある正直ノードが prepared に達した事実を他のノードも知っている保証がありません。プライマリ交代（ビューチェンジ）が起きたとき、新プライマリが「すでに確定済みの順序」を取りこぼすと矛盾が生じます。commit フェーズは「2f+1 台が prepared を見届けた」ことを定足数で固め、ビューを跨いでも順序が保存されることを保証します。各フェーズが 2f+1 の定足数を要求するのは、前節の交差性をそのまま使っているからです。

試験・面接での要点

「BFTは n≥3f+1、クラッシュ耐性は n≥2f+1」をペアで覚えるのが定番です。違いの源泉は「無言の故障（票が減るだけ）」か「偽証する故障（票を捏造しうる）」か。さらにビザンチン故障ではメッセージ署名が前提で、改竄や成りすましを暗号で防げないと、3f+1 でも安全性は保てません。

メッセージ複雑度とブロックチェーンへの系譜

PBFTの弱点は通信量です。prepare と commit は全ノードが全ノードへ送る all-to-all なので、ノード数 n に対し1合意あたり O(n^2) 通のメッセージが飛びます。数十ノードなら実用的でも、数百を超えると急速に重くなり、これがブロックチェーンでの大規模化を阻みました。

それでもPBFTの骨格——3分の2超の定足数と多段投票による安全性——は、許可型（permissioned）ブロックチェーンの合意へ直接受け継がれます。整合性モデル（/devops/consistency-models/）の言葉で言えば、これらは即時の最終確定（ファイナリティ）を与える強整合な合意です。

プロトコル	PBFTからの進化	耐性
Tendermint / CometBFT	ラウンドベースで連鎖的に確定。Cosmos系の合意エンジン	n≥3f+1
HotStuff	閾値署名でフェーズを集約し O(n) 通へ。リーダー交代も線形化	n≥3f+1
Casper FFG	Ethereum のファイナリティ層。2/3超の検証者でブロックを確定	ステーク量で 1/3 未満の悪意を許容

HotStuff は 閾値署名（多数の署名を1つに集約）でメッセージ複雑度を O(n^2) から O(n) へ下げ、PBFTの実用上の壁を破りました。Diem（旧Libra）や多くの近代BFTチェーンの基盤です。一方、ビットコインの Nakamoto合意 は系譜が異なり、3f+1 の定足数ではなく最長チェーン規則と計算量で多数派を表現します。確率的な確定（確認数を重ねるほど覆りにくい）であり、PBFT系の即時ファイナリティとは対照的です。耐性も「ハッシュレートの過半数」を握られると崩れる、いわゆる51%攻撃が境界になります。

どちらを選ぶかは確定性の要件で決まる

PBFT/HotStuff系は即座に覆らない確定を与える代わりにノード数のスケールに弱く、Nakamoto系は巨大スケールに強い代わりに確定は確率的です。可用性の数理（/devops/reliability-math/）と同じく、ここでも「何を犠牲にして何を取るか」のトレードオフが設計の核心になります。

まとめ

ビザンチン故障は嘘・改竄・矛盾証言を含む任意の振る舞い。クラッシュ耐性（n≥2f+1）では守れない。
f 台の偽証に耐えるには n≥3f+1。根拠は定足数の交差で、定足数 2f+1 の2つは f+1 台で重なり、偽証 f 台を引いても正直ノードが1台残る。
PBFT は pre-prepare／prepare／commit の3フェーズと 2f+1 定足数で、ビューを跨いでも順序を保存し安全性を担保する。
メッセージ複雑度 O(n^2) が壁となり、HotStuff は閾値署名で O(n) 化。Tendermint・Casper などブロックチェーンBFTへ系譜が続く。Nakamoto合意は別系統で、確率的ファイナリティを取る。

ビザンチン障害耐性（BFT）と 3f+1 の理由

ビザンチン故障とは何か

なぜ過半数では足りないのか

3f+1 を定足数の交差から導く

PBFT の3フェーズ

メッセージ複雑度とブロックチェーンへの系譜

まとめ

ビザンチン障害耐性（BFT）と 3f+1 の理由を実務で読む

解決すること

比較で見る軸

導入後に効く点

先に潰すリスク

判断チェックリスト

次に確認する観点