ビザンチン障害耐性(BFT, Byzantine Fault Tolerance)とPBFT

1. 概要

A. 定義

ビザンチン障害耐性(Byzantine Fault Tolerance, BFT)とは、分散システムの一部ノードが単に停止するだけでなく任意に誤った・矛盾した・悪意あるメッセージを送る状況(ビザンチン障害)においても、正常ノードが一つの正しい値に合意し、システムが一貫して動作することを保証する能力である。PBFT(Practical Byzantine Fault Tolerance)は、1999年にCastro·Liskovが提案した、部分同期(partial synchrony)仮定のもとで実用的性能によりビザンチン合意を達成した代表的アルゴリズムである。

BFTは分散合意の最も強い形態である。先のPaxos·Raftが扱うクラッシュ障害(Crash Fault)はノードが「死ぬか遅くなるだけで嘘はつかない」という前提を置くが、BFTは「ノードがハッキングされて異なるノードに異なる値を送ったり、偽造署名を試みたり、プロトコルを巧妙に違反しうる」という敵対的障害モデルまで仮定する。そのためBFTは、信頼できない(permissionless·adversarial)環境—公開ブロックチェーン、多者間金融決済網、航空·宇宙制御装置—の安全性を支える中核的基盤技術として定着した。

B. 登場背景と必要性

BFTの理論的ルーツは、1982年にLamport·Shostak·Peaseが定式化したビザンチン将軍問題(Byzantine Generals Problem)である。複数の将軍がそれぞれ部隊を率いて敵の城を包囲し、「攻撃」と「撤退」のいずれかを全員同じように選ばなければならないが、伝令(メッセージ)のみで通信し、一部の将軍は裏切り者で偽の命令を流しうる。このとき忠実な将軍が必ず同じ決定に到達できるかを問う思考実験であり、分散システムにおける「嘘をつくノードが混ざっていても合意が可能か」を抽象化したものである。この論文は、口頭(署名なし)メッセージのみでは裏切り者が1名でもいるには将軍全体が最低3倍以上必要であること、すなわち3f+1条件を数学的に証明した。

この問題が現実で重要な理由は明確である。単純な障害のみを仮定するPaxos·Raft系は、ノード一つが悪意をもって異なるフォロワーに矛盾したログを送る攻撃の前で安全性が崩れる。金融決済、電子投票、航空制御のようにただ一度の誤った合意が致命的な領域では、「ノードは嘘をつかない」という楽観的前提を使えない。特に2008年のビットコイン以降、相互に不信する匿名参加者が中央管理者なしに台帳状態に合意する要求が爆発し、ビザンチン合意は学界の難題から産業界の必須技術へと格上げされた。

ただし初期のBFTアルゴリズムは「理論的には可能だが性能が非現実的」という壁に阻まれていた。PBFTはまさにこの点を打ち破った。完全非同期ではなく部分同期(メッセージ遅延に上限が存在するという弱い仮定)を導入し、メッセージ交換回数を指数から多項式水準へ下げ、実際のファイルシステム(BFS)に適用可能なスループットを実証することで「Practical」の名を得た。

C. BFTが保証する中核的性質

合意(Agreement): すべての誠実なノードは同じ順番に同一の要求を実行する。ビザンチンノードが異なる値を流布しても交差検証で除去される。
全順序(Total Order): 要求がすべての誠実なノードで同一の順序に適用され、複製状態機械の状態が発散しない。
完全性(Integrity): 誠実なクライアントの要求のみが、正確に一度だけ実行される(偽造·再生攻撃の遮断)。
外部一貫性(Linearizability): クライアントの観点でシステムが単一の正しいサーバのように応答する。
活性(Liveness): ネットワークが安定すれば(部分同期)誠実な要求は必ず処理される—ただし安全性に従属して保証される。

2. ビザンチン障害の特性と定足数原理

ビザンチン障害がクラッシュ障害と根本的に異なる点は、障害ノードの行動に制約がないことにある。クラッシュ障害ノードは「応答しない」という唯一の失敗様相のみを示すため、残りのノードは「応答した値は誠実である」と信じられる。一方ビザンチンノードは応答はするがその内容が偽でありうるし、受信者によって異なる値を送る二重行動(equivocation)まで可能である。したがってBFTは「入ってきた値を信じる」代わりに「十分多くのノードが同一に証言した値のみを信じる」多重検証構造を採る。

この構造の中核が3f+1定足数原理である。全ノードN個のうち最大f個がビザンチンのとき安全性を守るにはN ≥ 3f+1でなければならない。直観的に説明すると、合意に必要な定足数は2f+1だが、こうすることで二つを同時に満たす。第一に、ビザンチンノードf個が応答を拒否しても正常ノード2f+1個のうちf+1個で定足数を満たせるため進展(liveness)が保証される。第二に、異なる二つの定足数(各2f+1)はN=3f+1の中で必ずf+1個以上重なり、その共通部分には最低1個以上の誠実なノードが存在するため、矛盾した二つの決定が同時に確定することが根本的に遮断され安全性(safety)が守られる。例えばf=1なら最低4ノード、f=2なら7ノードが必要であり、これはクラッシュ障害の2f+1(f=1で3ノード)より多くの冗長性を要求する。

flowchart TB
    subgraph CFT["クラッシュ障害耐性 (CFT, N=2f+1)"]
      direction TB
      C1["正常ノード"] --- C2["正常ノード"]
      C2 --- C3["沈黙(停止)したノード"]
      CNOTE["仮定: ノードは停止するのみで嘘はつかない"]
    end
    subgraph BFT["ビザンチン障害耐性 (BFT, N=3f+1)"]
      direction TB
      B1["正常ノード"] --- B2["正常ノード"]
      B2 --- B3["正常ノード"]
      B3 --- B4["悪意あるノード(二重行動)"]
      BNOTE["仮定: ノードは偽·矛盾メッセージを送りうる"]
    end
    CFT -->|"脅威モデルの強化"| BFT

上図は、同じf=1に耐えるのにもCFTは3ノード、BFTは4ノードが必要であることを示す。追加された1個の冗長は「嘘の可能性」に備えるコストであり、このためBFTはより強い安全性を提供する代わりにノード数·メッセージコスト·遅延が大きくなる根本的トレードオフを抱えている。産業現場で信頼ドメイン内部(社内データセンター)にはコストの低いCFTを、相互不信環境(公開ブロックチェーン)にはBFTを選ぶ分岐点がここで分かれる。

一方、ビザンチン将軍問題の原論文は、メッセージ認証(署名)の有無が耐障害限界を変えるという重要な洞察を残した。署名なしの口頭メッセージ(oral message)モデルでは、裏切り者が「Aには攻撃、Bには撤退」と言った後それを追跡する方法がなく、3f+1個が必ず必要である。しかしメッセージに偽造不可能なデジタル署名を付ければ、裏切り者が伝達過程で内容を変えると署名が壊れて即座に発覚するため、理論的にはより少ないノードでも合意が可能になる。まさにこのためPBFTをはじめ現代のBFTは例外なくすべてのプロトコルメッセージに署名またはMACを付し、署名はBFTの「嘘検出装置」であると同時に性能ボトルネックにもなる。ただし署名は二重行動(equivocation)—同じ署名者が異なる二つのメッセージにそれぞれ正当な署名を付して送る攻撃—は防げないため、結局3f+1定足数による投票交差検証が依然として中核的安全装置として残る。

BFT設計で必ず区別すべきもう一つの軸は、安全性(Safety)と活性(Liveness)である。安全性は「異なる二つの誠実なノードが同じ順番に異なる値を確定しない」(悪いことは決して起こらない)であり、活性は「要求がいつかは必ず処理される」(良いことは結局起こる)である。FLP不可能性定理により完全非同期環境では両者を同時に決定論的に保証できないため、PBFTは安全性をいかなる場合も犠牲にせず活性のみを部分同期仮定(メッセージ遅延上限の存在)に委ねる設計を採った。すなわちネットワークが極端に不安定であればPBFTは停止することはあっても(活性喪失)決して矛盾した決定は下さない(安全性維持)。この「安全性優先」の哲学は、金融·制御のように誤った合意が致命的な領域でBFTを信頼できるものにする根本原則である。

3. PBFTの3段階合意プロトコル

PBFTはノードをプライマリ(primary, リーダー)とバックアップ(backup)に分け、特定の設定(view)でプライマリが要求の順序を提案するとバックアップがこれを交差検証して確定する。正常動作区間(normal-case)の合意はPre-prepare → Prepare → Commitの3段階メッセージ交換で行われ、各段階は「十分な数のノードが同じ内容を見た」という証拠を累積する。各段階が確保する保証を一目で整理すると次のとおりである。

Pre-prepare: プライマリが順番(n)を提案 → 「このviewでn番の位置の要求」候補を固定。
Prepare(2f+1を収集): 同じview·順番に異なる要求がpreparedされえないことを保証(同一view内の順序合意)。
Commit(2f+1を収集): 決定がview交替後も保持されることを保証(view間の確定性) → 実行·応答。

A. Pre-prepare(事前準備). クライアント要求を受けたプライマリはその要求に順番(sequence number) nを付与し、現在のview v·要求ダイジェストとともに署名してすべてのバックアップにブロードキャストする。この段階の目的は「このviewでn番の位置にはこの要求が入る」という順序提案を固定することである。バックアップは署名·view·順番範囲の有効性を検証して受け入れる。プライマリが悪意的であっても次段階の交差検証が矛盾を除去する。

B. Prepare(準備). Pre-prepareを受け入れた各バックアップは同一の⟨v, n, ダイジェスト⟩に対するPrepareメッセージを自らの署名とともにすべてのノードにブロードキャストする。あるノードが自分自身を含めて2f+1個の一致するPrepare(異なるノードが署名した)を集めると「prepared状態」に至る。この条件が成立すれば、誠実なノード間で同じview·同じ順番に異なる要求がpreparedされえないことが保証される。すなわちPrepare段階は「順序に対する一次合意」を確保するが、viewが変わってもこの決定が生き残るかはまだ保証しない。

C. Commit(確定). preparedに到達したノードはCommitメッセージを同じく全体にブロードキャストし、2f+1個の一致するCommitを集めると「committed-local」状態となり、要求を複製状態機械に実行(execute)した後クライアントに応答する。クライアントは異なるノードからf+1個の同一応答を受け取ると結果を信頼する(f+1のうち最低1個は誠実だから)。Commit段階が追加で必要な理由は、Prepareのみではview交替(view change)時に決定が覆されうるからである。Commitは「この決定はviewが変わっても保持される」という確定性を付与する。

sequenceDiagram
    participant C as クライアント
    participant P as プライマリ(ノード0)
    participant B1 as バックアップ1
    participant B2 as バックアップ2
    participant B3 as バックアップ3(障害可能)
    C->>P: 要求(request)
    Note over P,B3: 1) Pre-prepare段階
    P->>B1: Pre-prepare(v,n,ダイジェスト)
    P->>B2: Pre-prepare(v,n,ダイジェスト)
    P->>B3: Pre-prepare(v,n,ダイジェスト)
    Note over P,B3: 2) Prepare段階 (2f+1を収集)
    B1->>P: Prepare
    B1->>B2: Prepare
    B2->>P: Prepare
    B2->>B1: Prepare
    Note over P,B3: 3) Commit段階 (2f+1を収集)
    P->>B1: Commit
    B1->>B2: Commit
    B2->>P: Commit
    Note over P,B2: committed-local到達 → 実行
    P-->>C: 応答
    B1-->>C: 応答
    B2-->>C: 応答(同一f+1個受信時に信頼)

D. チェックポイントとガベージコレクション. 合意が累積すると各ノードが保管するメッセージログが無限に大きくなるため、PBFTは一定の順番ごとにチェックポイント(checkpoint)を作って状態スナップショットを共有し、それ以前のログを安全に廃棄する。2f+1個のノードが同一状態ダイジェストに署名した安定チェックポイント(stable checkpoint)が確保されると、その地点までの決定は覆せない事実として固まりメモリが回収される。チェックポイントは単なる性能最適化ではなく、view change時に「どこから引き継ぐか」の基準点となる安全性の構成要素でもある。

プライマリが応答しないか誤った順序を強要すると、バックアップはタイマー満了後にビューチェンジ(View Change)を発動する。2f+1個のノードがビューチェンジに同意すると次のプライマリ(v+1基準のノード)が選出され、直前までprepared·committedされた要求を新プライマリが証拠(prepared証明)とともに引き継ぎ、すでに確定した決定が失われないよう保証する。このメカニズムのおかげでPBFTは悪意あるプライマリ一つが全体の進展を永久に止められない。ただし正常区間の合意がO(N²)のメッセージ複雑度を持ち(すべてのノードが互いにPrepare·Commitを交換)、ノード数が数十を超えると拡張性が急激に落ちる限界がある。

4. 合意モデルの比較と適用事例

実務で「どの合意を使うか」は性能数値ではなく信頼仮定から出発する設計決定である。同じ分散合意でも前提する障害モデルが異なれば必要なノード数·メッセージ量·確定性の性格がまるごと変わるからである。以下では三つの代表モデルを比較するが、数値そのものよりその数値がなぜそう決まるかに焦点を置く。

BFTを正しく使うにはクラッシュ障害合意、そして公開ブロックチェーンの確率的合意(PoW)との違いを明確に理解しなければならない。下表は中核的差異を比較するが、各差異がなぜ生じるかが重要である。CFTがBFTよりノードと遅延が少ないのは「嘘をつくノードを仮定しない」からであり、PoWがBFTより参加者拡張性が大きい代わりに確定性(finality)が確率的なのは投票の代わりにハッシュ競争で合意を置き換えたからである。

区分	クラッシュ障害(Paxos/Raft)	PBFT(決定論的BFT)	PoW(確率的BFT)
障害モデル	停止·遅延のみ	任意·悪意(嘘)	任意·悪意(開放型)
耐障害限界	f < N/2 (N=2f+1)	f < N/3 (N=3f+1)	ハッシュパワー < 50%
確定性	即時(決定的)	即時(決定的)	確率的(確認数の累積)
メッセージ複雑度	O(N)	O(N²)	低い(ブロードキャスト)
ノード拡張性	数~数十	数十(限界が明確)	数千~数万
代表的適用	etcd·ZooKeeper	Hyperledger Fabric·Zilliqa	Bitcoin·初期Ethereum

定足数計算を小さな数値で具体化すると差異が明確になる。公開ブロックチェーンのようにN=100ノードで運用するとき、BFTは最大f=33個(100 ≥ 3×33+1)の悪意あるノードに耐えられ、すべての決定に最低67個(2f+1)の署名投票が必要である。一方CFTなら同じ100ノードでf=49個の停止障害に耐えられ耐障害「比率」はより高いが、これは「悪意あるノードがない」という強い前提の上でのみ成立する。すなわちBFTはより少ない比率(1/3未満)の障害のみに耐える代わりに、その障害が嘘を含む任意の行動であっても安全性を守るという質的優位を提供する。設計者は「どれだけ多くの障害に耐えるか」ではなく「どんな種類の障害に耐えるべきか」をまず問わねばならない。

具体的な事例として、許可型(permissioned)ブロックチェーンであるHyperledger Fabricは参加機関数が限定的で身元が確認されるため、PBFT系(またはRaft)オーダラーを使って即時確定性と高いスループットを得る。一方公開型のビットコインは匿名参加者が数万に及びO(N²)投票が不可能なためPoWを採り、その代償としてブロックが覆される確率が時間とともに指数的に減少する「確率的確定性」を受け入れた。一方、航空分野ではボーイング777の飛行制御コンピュータが三重多数決(ビザンチン耐性)構造でセンサ·演算障害に備えるなど、BFT概念はブロックチェーン以前から安全必須(safety-critical)システムに実際に適用されてきた。このように「参加者数·信頼仮定·要求確定性」という三つの軸がどの合意を使うかを決める。

5. 深化 — 拡張型BFTと最新動向

PBFTのO(N²)ボトルネックは過去10数年間BFT研究の最大の課題であり、ブロックチェーンの台頭とともにこれを克服する次世代BFTが噴出した。第一に、Tendermint(現CometBFT)はPBFTを単純化してリーダー交替を毎ブロックローテーションし、即時確定性を提供し、Cosmosエコシステムの多数のチェーンがこれを合意エンジンとして採択した。第二に、HotStuff(2019)はメッセージ複雑度をO(N)に下げ、すべての段階をリーダー中心の線形通信に再構成し、リーダー交替コストまで線形化した。HotStuffはMetaが推進したLibra/DiemのLibraBFT(DiemBFT)やAptos·Flowなどに継承され、現代の持分証明(PoS)チェーンの事実上の標準設計となった。

代表的な次世代BFT系を整理すると次のとおりである。

Tendermint / CometBFT: PBFT単純化 + 毎ブロックリーダーローテーション、即時確定性。Cosmos·Binance Chainなど採択。
HotStuff / DiemBFT: 線形通信(O(N))とリーダー交替の線形化、パイプライニングでスループット向上。Aptos·Flow·Diem継承。
Casper FFG + Gasper: 持分証明と結合した委員会サンプリングBFT、スラッシングで悪意行動を抑制。Ethereum PoS。
HoneyBadgerBFT / DAGベース(Narwhal·Bullshark): タイムアウト仮定のない非同期BFT、ネットワーク攻撃にも活性を維持。

第三に、持分証明(PoS)自体がBFTと結合して拡張性問題を回避する。イーサリアムのCasper FFGとGasperは数十万の検証者から無作為に委員会を選んでBFT投票を行い、持分(ステーク)を担保に悪意ある行為にスラッシング(slashing)罰則を課し、経済的コストでビザンチン行動を抑制する。これは「暗号学的投票(BFT) + 経済的誘因(ステーク)」を結合したハイブリッドであり、伝統的BFTのノード数限界を検証者サンプリングで突破した事例である。第四に、完全非同期ネットワークでも安全·活性を保証するHoneyBadgerBFTのような非同期BFTが登場し、タイムアウト仮定なしでも動作する堅牢な合意が研究されている。この流れは「信頼なしの大規模参加」と「即時確定性」を同時に追求するWeb3·CBDC(中央銀行デジタル通貨)設計で特に重要に扱われる。

6. 考慮事項および示唆点 (技術士の観点)

脅威モデルに合わせた合意選択: 信頼ドメイン内部(社内クラスタ、etcd)にはコストの低いCFT(Raft)を、相互不信·開放環境(コンソーシアム·公開ブロックチェーン)にはBFTを選ばねばならない。過度なBFT適用は不要なノード·遅延コストを、不足したCFT適用は致命的な安全性崩壊をもたらすため、設計初期に障害モデルを明示的に文書化することが中核的なガバナンス課題である。
拡張性-確定性のトレードオフ: PBFTのO(N²)特性上、ノードが数十を超えるとスループットが急落する。大規模が必要なら HotStuff(O(N))系や委員会サンプリング(検証者サブセット投票)で通信量を減らすが、サンプリングは安全性が確率的に弱まりうるため委員会サイズ·再選出周期を定量的に検証せねばならない。
鍵管理と署名性能: BFTはすべてのメッセージにデジタル署名·MACを要求するため、鍵漏洩がすなわちビザンチンノード化を意味する。HSM·閾値署名(threshold signature)·鍵ローテーションで署名鍵を保護し、BLS集約署名などで検証コストを相殺する設計が運用安定性を左右する。
ネットワーク仮定と活性保証: PBFTの活性は部分同期(遅延上限の存在)に依存するため、持続的なネットワーク攻撃(遅延·分割)は進展を止めうる。DDoS防御·多重経路·ビューチェンジタイマーのチューニングで活性を防御し、完全非同期耐性が必要ならHoneyBadgerBFT系を検討する。
経済的誘因との結合展望: PoSベースのBFTではスラッシング·報酬設計が安全性の一部となる。暗号学的安全装置のみならず経済的インセンティブまで含めたメカニズムデザインでビザンチン行動を抑制することがCBDC·分散型金融の必須能力となる見込みであり、技術士は暗号·分散·経済メカニズムを包括する統合設計の観点を備えねばならない。
段階的導入と検証戦略: BFT全面導入前に、カオスエンジニアリング(Chaos Engineering)·障害注入でビューチェンジ·悪意あるプライマリのシナリオを再現して安全性·活性を定量検証し、ノード地理的分散·クロックスキュー·署名スループットのボトルネックを事前に測定せねばならない。特に「正常区間では速いが攻撃区間で遅延が急増する」BFT特性上、平常時の性能ではなく最悪区間(worst-case)遅延を基準に容量を算定する保守的設計が安定運用の鍵である。

参考資料

Lamport, Shostak, Pease, "The Byzantine Generals Problem", ACM TOPLAS, 1982. https://lamport.azurewebsites.net/pubs/byz.pdf
Castro, Liskov, "Practical Byzantine Fault Tolerance", OSDI, 1999. https://pmg.csail.mit.edu/papers/osdi99.pdf
Yin et al., "HotStuff: BFT Consensus with Linearity and Responsiveness", PODC, 2019. https://arxiv.org/abs/1803.05069
Buchman, "Tendermint: Byzantine Fault Tolerance in the Age of Blockchains", 2016. https://tendermint.com/

一言まとめ: BFTはノードが嘘·矛盾メッセージを送る敵対的環境においてもN≥3f+1定足数と多重交差検証で合意を守る最も強い耐障害技術であり、PBFTのPre-prepare·Prepare·Commitの3段階とビューチェンジがその実用的原型として、今日HotStuff·PoSへ拡張されブロックチェーン·CBDC信頼の基盤となっている。