コンセンサスアルゴリズム徹底比較：Paxos・Raft・PBFT・PoW/PoSの仕組みと実務的選び方

2025年11月18日 最終更新日時 : 2025年11月18日 エバープレイ編集部

コンセンサスアルゴリズムとは何か

コンセンサスアルゴリズム（合意形成アルゴリズム）は、分散システムにおいて複数のノードが単一の値や状態について合意（コンセンサス）を得るための手続きです。中央集権的な仲介者が存在しない、あるいはその故障や悪意に備えたい環境で不可欠な要素であり、分散データベース、分散ロックサービス、ブロックチェーンなどで広く利用されています。

合意形成における基本的性質

  • 安全性（Safety）：合意された値が矛盾しない（異なるノードが異なる値を最終的に決めない）。
  • 生存性・終端性（Liveness / Termination）：要求された条件下で、プロトコルは最終的に合意に到達する。
  • 最小限の正当性（Validity）：合意値は提案された値のうちの一つである。
  • ファイナリティ（Finality）：合意が確定的か確率的か。BFT系は決定的最終性、PoWは確率的最終性を持つ。

ネットワーク・障害モデル

設計するアルゴリズムは、前提とするネットワークの性質と故障モデルに依存します。主な分類は次の通りです。

  • クラッシュ故障（Crash Fault）：ノードが停止するが誤動作はしない。多数決（過半数）を使うアルゴリズムで扱われることが多い。
  • ビザンチン故障（Byzantine Fault）：ノードが任意に悪意ある振る舞いをする可能性。これを扱うにはn ≥ 3f + 1（fは許容するビザンチンノード数）の条件が必要な場合が多い。
  • 同期性の仮定：完全同期、部分同期、非同期。FLP不可能性の結果（非同期ネットワークでの決定的合意は1つの故障があれば不可能）が設計に影響します。

代表的なコンセンサスアルゴリズム（分散システム系）

まずはブロックチェーン以前から存在する、サーバー群やクラスタ向けの古典的アルゴリズムです。

  • Paxos（Leslie Lamport）

    Paxosは、非同期なネットワーク上でクラッシュ故障を前提に安全性を保証する代表的アルゴリズムです。実装は複雑であるため、解説的な「Paxos Made Simple」が有名です。分散ロックサービス（例：GoogleのChubby）での応用が知られています。

  • Raft（Ongaro & Ousterhout）

    RaftはPaxosよりも理解しやすく実装しやすいことを目標に設計され、リーダー選出、ログ複製、メンバーシップ変更を明確に規定します。etcd、Consul、Docker Swarmなどで採用されています。

  • Viewstamped Replication / Zab

    主に分散レプリケーションのためのプロトコル。ZooKeeperのZabやその他のレプリケーションプロトコルがこれらの思想を取り入れています。

ビザンチン耐性（BFT）系アルゴリズム

悪意を持つノードの存在を考慮する場合、BFTアルゴリズムが必要です。

  • PBFT（Practical Byzantine Fault Tolerance）

    Castro と Liskov による1999年のPBFTは、実践的なビザンチン耐性レプリケーションを実現します。許可型（permissioned）ブロックチェーンや分散台帳の基礎として参考にされてきました。一般にn ≥ 3f + 1の条件でf個のビザンチン故障に耐えられます。

  • Tendermint, HotStuff 等

    TendermintはBFTベースのブロック承認エンジンで、Cosmos SDKなどで採用。HotStuffは単純で効率的なBFTコンセンサスで、Facebook系のLibra（Diem）やその他の実装に影響を与えました。

ブロックチェーンで用いられる代表的なアルゴリズム

  • Proof of Work（PoW）

    ビットコインで採用された方式。計算作業（ハッシュ計算）によってブロック作成権を競います。確率的最終性を持ち、51%攻撃等のリスクがあります。高い電力消費と低いスループットが課題です。

  • Proof of Stake（PoS）

    ステーク（保有量）に基づいてブロック提案者を選ぶ方法。Ethereumの「The Merge」以降はPoSへ移行しました。長期攻撃（long-range）やスラッシングポリシーなど設計上の注意点があります。

  • Delegated Proof of Stake（DPoS）

    EOSやTRONなどで使われる、投票で代表を選びその代表がブロックを作る方式。高いスループットが期待できる反面、中央集権化の懸念があります。

  • Proof of Authority（PoA）

    事前に許可されたノードのみがブロックを生成できる方式。許可型ネットワークに適しており、パフォーマンスは良いが参加の開放性は低い。

性能とスケーラビリティ、トレードオフ

コンセンサス選択はトレードオフの連続です。主な評価軸は次の通りです。

  • レイテンシ（合意にかかる時間）：低いほうが応答性が良い。BFT系やPoS系は高速に処理できることが多い。
  • スループット（TPS）：1秒あたり処理できる取引数。許可型BFTやDPoSは高いスループットを狙える。
  • セキュリティ（耐障害性）：ビザンチン耐性、Sybil耐性（PoW/PoSでは経済的コストによる耐性）など。
  • 最終性：確定的（即座に確定）か確率的（後に分岐が起きる可能性がある）か。
  • スケーラビリティ：ノード数が増えたときの通信オーバーヘッド。全ノード間で認証・投票を行うBFTは大規模化が難しい。

攻撃や脅威

  • 51%攻撃：PoWや一部PoSで過半数の算力やステークを掌握されると不正な履歴書換えが可能。
  • Sybil攻撃：多数の偽ノードを用いて投票を支配する攻撃。許可型では参加管理で軽減、無許可型ではPoW/PoSが抑止力。
  • Eclipse攻撃：特定ノードのネットワークビューを隔離し誤情報を与える攻撃。
  • Long-range / Reorg 攻撃：長期間にわたるステークの移動やチェーンの再編成を狙う攻撃（主にPoSで議論される）。
  • 自己利得行為（Selfish Mining）：採掘者がブロックを隠蔽して戦略的にチェーンを延ばす行為。

アルゴリズム選定の実務的ガイドライン

  • 用途が許可型で、参加者が限定される場合：PBFT、Tendermint、HotStuffなどのBFTベースが高性能で現実的。
  • 公共の無許可型ネットワークで分散性を重視する場合：PoW（高い分散性）かPoS（電力効率、スケーラビリティ）を検討。
  • クラスタ管理やレプリケーション（データベース、サービス）では：RaftやPaxosが堅牢で実装成熟度が高い。
  • スケーラビリティ優先だが信頼できる代表を置ける場合：DPoSやPoAを検討。
  • 設計時にはネットワーク同期性、ノード数、故障想定（クラッシュ/ビザンチン）を明確にする。

実装上の注意点

  • ログの永続化やフォールトトレランス設定（スナップショット、ログ圧縮）は実運用で必須。
  • ネットワークの遅延やパーティションを想定したタイムアウト設計。FLP不可能性を踏まえ、部分同期モデルや乱数化を利用する。
  • 監視とメトリクス（合意遅延、再試行回数、投票メッセージ量）を整備して性能劣化を検知する。
  • セキュリティ対策（鍵管理、ノード認証、DoS保護）を合わせて設計する。

まとめ

コンセンサスアルゴリズムは「どのような環境で」「どのような脅威モデルを想定し」「何を重視するか」によって最適解が大きく変わります。Paxos/Raftのようなクラスタ向け、PBFTやTendermintのようなビザンチン耐性型、PoW/PoSのような無許可型ブロックチェーン向け——それぞれメリットと限界があり、設計者は最終性、パフォーマンス、スケーラビリティ、経済的インセンティブや運用コストを天秤にかけて選択する必要があります。

参考文献

カテゴリー
IT
前の記事
ハッシュチェーンとは？仕組み・OTP・ログ改ざん検出への活用法と実装上の注意点New!!
2025年11月18日
次の記事
スマートコントラクト完全ガイド：仕組み・代表チェーン・ユースケースと実務向けセキュリティ対策New!!
2025年11月18日