PBFT徹底解説：ビザンチン障害耐性を実現する実用的合意アルゴリズムと派生プロトコルの全体像
エバープレイ編集部はじめに
PBFT（Practical Byzantine Fault Tolerance）は、分散システムにおけるビザンチン故障（任意の悪意ある／誤動作をするノード）に耐える実用的な合意（コンセンサス）アルゴリズムの代表例です。Miguel Castro と Barbara Liskov による1999年の論文で提案されて以来、分散データベースやパーミッションド（許可型）ブロックチェーンなど、信頼できない可能性のある複数ノードで一貫した状態を保つ用途で広く研究・応用されてきました。
基本的な考え方と前提条件
ビザンチン障害モデル：ノード（レプリカ）は任意の挙動をする可能性がある（メッセージの偽造、矛盾したメッセージ送信、無応答など）。PBFT はこのモデル下での耐障害性を扱います。
耐故障数 f と総ノード数 n：PBFT は n ≥ 3f + 1 の条件のもとで f 個のビザンチン故障に耐えます。つまり 3f+1 台以上のレプリカを用意することで、安全性（Safety）を確保します。
通信モデル：PBFT は安全性は非同期通信モデル（メッセージ遅延が任意に発生しても安全性は保たれる）で保証し、ライブネス（進行性）は「部分同期性（eventual synchrony）」の下で保証します。これは FLP 不可能性（完全非同期下での待機ゼロの合意は不可能）を踏まえた現実的な仮定です。
認証：レプリカ間やクライアントとの通信はメッセージ認証（MAC）やデジタル署名で保護されます。元論文では性能向上のために MAC を多用し、必要に応じて署名を使う設計が示されています。
PBFT の全体構造（ステートマシンレプリケーション）
PBFT はステートマシンレプリケーション（SMR：同じ入力を同じ順序で各レプリカに適用して状態を一致させる手法）として設計されています。システムは「プライマリ（リーダー）」と「バックアップ」レプリカ（残り）に分かれ、クライアントからのリクエストをプライマリが順序付けして他のレプリカに伝搬します。
主要メッセージフロー：3段階の通常パス
クライアント → プライマリ：クライアントはリクエスト（例：操作の内容とタイムスタンプ）をプライマリに送る。
プライマリ → 全レプリカ（PRE-PREPARE）：プライマリはリクエストにシーケンス番号を割り当て、PRE-PREPARE メッセージを全レプリカにブロードキャストする。
各レプリカ → 全レプリカ（PREPARE）：各レプリカは PRE-PREPARE を検証し、正しければ PREPARE メッセージを全員に送る。
準備完了（prepared）状態：あるレプリカが同一ビュー（同じリーダー）・同一シーケンス番号について、自身の PREPARE と他の 2f PREPARE（合計 2f+1）を受け取ると「prepared」となる。
各レプリカ → 全レプリカ（COMMIT）：prepared 状態に達したレプリカは COMMIT を送信する。
コミット（commit）と実行：あるレプリカが同一ビュー・同一シーケンス番号について 2f+1 の COMMIT メッセージ（自身を含む）を受け取ると、そのリクエストを実行して状態を更新し、クライアントに実行結果を返信する。
クライアントの完了判定：クライアントは異なるレプリカから f+1 個の同一の返信を受け取ると、結果を正当と見なして完了と判断する（f 個まで悪意のある返信が混じっても少なくとも 1 つは正当なレプリカ由来であるため）。
閾値や理由の説明（なぜ 3f+1、2f+1 などか）
これらの閾値は、ビザンチン故障が混入しても正当な多数の意見が一致することを保証するための数学的条件に由来します。例えば、ある決定に関して「正しい」レプリカが互いに交わる（common intersection）ことを確保するため、2f+1 のコミット集合を用いることで任意の二つの正当集合は少なくとも f+1 個で交わり、そこには常に少なくとも 1 つの正当なレプリカが含まれます。これが合意の安全性を支えます。
チェックポイントとログの整理
PBFT は無制限にログを延ばすとメモリや処理が肥大化するため、チェックポイント機構を用いて状態を区切ります。各レプリカは一定シーケンスごとにチェックポイントを作り、2f+1 の一致したチェックポイントを受け取るとそのチェックポイント以前のログを「安定」と見なし破棄（ガベージコレクション）できます。ビュー変更時の状態転送（state transfer）もチェックポイントを使って効率化します。
ビュー変更（プライマリ交代）
プライマリが不正や遅延を起こして進行が止まった場合、PBFT はビュー変更プロトコルで新しいプライマリに交代します。新しいプライマリは 2f+1 個の VIEW-CHANGE メッセージを集めて、それまでのコミット済み・準備済みログから正しい最新状態を選び直し、新ビュー（new-view）をブロードキャストして処理を再開します。ビュー変更の正当性を保つためにも多数の証拠（2f+1）が必要です。
安全性とライブネス
安全性（Safety）：PBFT は、任意の時点で正しいレプリカ同士が異なる順序で実行することがないように保証します。これには 3f+1 の条件とメッセージ閾値が必要です。
ライブネス（Liveness）：PBFT のライブネス（すなわちクライアントの要求が最終的に実行されること）は、ネットワークが十分に良くなり（部分同期性が成立する）プライマリが正常であるなどの条件下で保証されます。完全非同期モデルでは FLP の理論からどの合意アルゴリズムも進行不能になる可能性があるため、PBFT は「最悪時でも安全」を重視しつつ「良い時には必ず進行する」という妥協を取っています。
性能・スケーラビリティ上の考察
メッセージ複雑度：通常パスではレプリカ間の全方位ブロードキャストが発生するため、メッセージ数は O(n^2)（実用的には (3f+1)^2 に近い）になり、ノード数が増えると通信オーバーヘッドが急増します。
最適化手法：要求のバッチング（複数リクエストをまとめて一つのシーケンス番号で処理）、MAC の多用（署名より高速）、部分的な署名集約や閾値署名の導入などでスループット改善が図られます。
実運用での限界：ノード数が数十〜数百に達するスケールでは標準 PBFT は非効率になりやすく、そのために設計を変えた派生プロトコルやレイヤー分離（例えば委任・シャーディング）を行うことが多いです。
派生プロトコルと近年の研究動向
Zyzzyva：クライアントをより積極的に利用した「楽観的」パスで低レイテンシを狙う手法。
Tendermint：ブロックチェーン向けに PBFT 的な考えを取り入れたプロトコルで、特にパーミッションドチェーンで広く使われています。
HotStuff：リーダー主導のシンプル化、線形の通信量を目指した設計で、Facebook（Libra/Diem）系の取り組みで採用例があり、以後の BFT ブロックチェーン設計に大きな影響を与えました。
HoneyBadgerBFT：完全非同期かつ耐帯域変動が大きい環境での高スループットを目指した設計（暗号的手法を多用）。
BFT-SMaRt 等：実用実装と運用を重視したライブラリやフレームワーク群も多数存在します。
実際の適用例
PBFT やその派生は、特に「参加ノードが事前に知られている（パーミッションド）環境」で採用されることが多いです。企業間の共同台帳や Consortium ブロックチェーン、分散データベースのレプリケーションレイヤー等で利用され、決済・記録の改ざん耐性と高速な承認を両立する選択肢として評価されています。一方で、パブリックな大規模（数千ノード）の環境ではスケーラビリティの観点から PoW/PoS 型の設計や、より軽量な BFT 派生が採用される場合が多いです。
運用上の注意点と落とし穴
動的メンバーシップ：標準 PBFT は静的なノード集合を想定しているため、ノードの追加・削除を安全に行うには別途プロトコルや設計が必要です。
DoS 攻撃やネットワーク分断：ビザンチン攻撃に加えて、ネットワーク攻撃による遅延や分断に対する脆弱性を考慮する必要があります。
鍵管理：MAC や署名に用いる鍵の管理が甘いと認証の前提が崩れるため、鍵配布・回転の運用が重要です。
実装の複雑性：ビュー変更や状態転送、ログ整理などの実装が煩雑になりやすく、バグが安全性を破るリスクがあるため検証・コードレビューが不可欠です。
まとめ
PBFT は「ビザンチン故障に対する実用的な合意アルゴリズム」として、非同期下での安全性と、部分同期性の下でのライブネスを両立する設計哲学を示しました。実装・運用次第で高性能を発揮しますが、ノード数や動的メンバー管理、ネットワークの現実的な振る舞いを考慮すると、用途に応じて PBFT 本体、あるいは HotStuff や Tendermint、HoneyBadger といった派生・改良プロトコルを選ぶ必要があります。特にブロックチェーンや分散台帳の分野では PBFT の影響が色濃く残っており、現在も多くの研究・実装が続いています。
参考文献
- Miguel Castro and Barbara Liskov, "Practical Byzantine Fault Tolerance", OSDI 1999 (論文 PDF)
- Maofan Yin et al., "HotStuff: BFT Consensus in the Lens of Blockchain", OSDI 2019 (論文 PDF)
- Jae Kwon and Ethan Buchman, "Tendermint: Consensus without Mining"（Tendermint 白書）
- Andrew Miller et al., "The Honey Badger of BFT Protocols"（アーキテクチャ論文、2016）
- Hyperledger Fabric ドキュメント - Consensus （アーキテクチャとコンセンサスの説明）
投稿者プロフィール
