分散合意とは — Paxos・Raft・PBFT・Nakamoto型合意

分散システムでは、複数のプロセスが同じ出来事を同時に観測することはありません。メッセージは遅れ、順番が入れ替わり、一部の参加者だけが停止し、ときには矛盾する情報が送られてきます。こうしたなかで「ログのこの位置には値Aを置く」といったん決めたなら、正しい参加者が同じ位置に値Bを確定してしまわないようにする。それが分散合意の中心にある仕事です。

ここでいう合意は、すべてのノードが同じ瞬間に同じ画面を映すことでも、参加者全員が賛成票を投じることでもありません。一部のノードが決定をまだ知らなかったり、停止していたりしても、クォーラムどうしが交差することで、矛盾する別の決定だけは起きないようにします。

Paxos、Raft、PBFT、ビットコインはいずれも複数の主体のあいだで順序を扱いますが、互いに置き換えられるアルゴリズムではありません。既知のサーバー群を複製する問題と、誰でも仮名で参加できる公開ネットワークの問題とでは、「一票を誰に与えるか」という出発点から設計が違います。

古典的な一回限りの合意問題は、各プロセスが候補値を持ち、正しいプロセスが一つの値を決める問題として定式化されます。確認する性質は一般に、Agreement（正しい参加者が異なる値を決めない）、Validity（決定値が定められた正当性条件を満たす）、Integrity（同じ参加者が二度決定しない）、Termination（正しい参加者が最終的に決定する）です。Validityの厳密な定義は文献によって異なります。

実際のサービスは、一つの値を決めて終わりではありません。命令をログのスロット1、2、3へ順に置くために、一回の合意を繰り返し、同じ初期状態を持つ決定的な状態機械へ同じ順番で適用します。これが状態機械複製の基本です。

合意とアトミックブロードキャストは密接に対応します。誰もが同じメッセージ集合を同じ順序で配信できれば複製ログを作れますし、各スロットで合意できれば順序付きのブロードキャストを構成できます。ただし、障害からの回復、重複した要求、構成の変更、スナップショット、クライアントへの応答まで含む実システムには、一回限りの定理よりも広い設計が要ります。

合意方式を比べるとき、最初に読むべきなのは処理件数ではなく仮定です。参加者はあらかじめ登録されたサーバーか、誰でも入れる公開の参加者か。障害は停止だけか、嘘や二枚舌まで含むか。通信の遅延に上限はあるか。票は身元、ステーク、計算資源のどれで重み付けするか。決定はその場で覆らなくなるのか、時間とともに覆る確率が下がっていくのか。

「分散型」や「BFT」という一語だけでは、これらの問いに答えられません。保証はアルゴリズムの名前に宿るのではなく、仮定と結論の組み合わせにあります。

完全同期モデルでは、処理速度とメッセージの配送に既知の上限を置けます。完全非同期モデルでは上限を置かないので、応答しない相手が停止したのか、ただ遅いだけなのかを確実には判定できません。部分同期モデルはその中間です。上限は存在するものの事前にはわからない、あるいは未知の時点以降にだけ上限が成立する、と仮定します。

FLPの結果が示すのは、完全非同期・決定的プロトコル・一つのクラッシュ障害という条件でも、すべての許容実行でTerminationを保証できない、ということです。「合意は実現できない」という意味ではありません。実際のプロトコルは、通信が最終的に安定する、リーダーが一定期間生き続ける、乱数を使うといった追加条件のもとで進みます。

多くの実用的な方式は、二つの性質を分けて考えます。ネットワークがどれほど遅くても矛盾する二つの決定を作らないのが安全性、ネットワークが十分に安定したあとに処理が進むのが生存性です。タイムアウトは障害の証明ではなく、リーダーの交代を試すための進行の仕組みにすぎません。

クォーラムの目的は人気を測ることではなく、二つの決定集合を必ず交差させることです。`2f+1` 台のクラッシュ耐性構成で過半数を取ると、どの二つの過半数にも少なくとも一台は共通のノードがあります。その共通ノードが過去に受理した情報を次のラウンドへ運ぶため、同じスロットに別の値が選ばれることを防げます。

ただし、交差する部分がビザンチンノードだけなら、そこで嘘をつかれてしまいます。`3f+1` のレプリカから `2f+1` のクォーラムを取るBFT構成では、二つのクォーラムは少なくとも `f+1` 台で交差します。そのなかには、正しいレプリカが少なくとも一台は含まれます。閾値は、障害モデルと、証明したい性質から導かれます。

ビットコインは、登録済みノードの頭数でクォーラムを作りません。誰でもノードの識別情報をいくらでも作れるからです。競合する有効なチェーンの選択を累積Proof of Workで重み付けし、身元の数ではなく希少な計算資源を履歴の提案に結び付けます。これは過半数クォーラムを単純に置き換えたものではなく、別の参加モデルです。

Paxosは、既知のアクセプタ集合のもとでクラッシュ障害に耐えながら、一つの値を安全に選ぶためのプロトコルです。プロポーザは、一意に順序づけられる提案番号を使います。Phase 1では、これより小さい提案番号は今後受け付けないという約束をアクセプタに求め、あわせて、すでに受理された値のうち提案番号が最大のものを集めます。

Phase 2では、Phase 1で受理済みの値が見つかればそのうち提案番号が最大の値を、見つからなければ新しい値を提案します。アクセプタの過半数が受理した値が、選ばれた値です。この制約があるため、別のプロポーザがあとからより大きい提案番号で進んでも、同じインスタンスで異なる値が選ばれることはありません。

Basic Paxosが選ぶのは一つの値です。Multi-Paxosは各ログスロットにPaxosを適用し、安定したリーダーのもとでPhase 1を再利用しながら複製ログを進めます。`2f+1` のアクセプタなら `f` 台のクラッシュに耐えられますが、通信できる過半数を失うと、安全性を壊さないまま停止します。

Paxosは二相コミットの別名ではありません。2PCは参加者全員がトランザクションをコミットするかどうかを調整する仕組みで、コーディネータが故障すると処理が止まったままになり得ます。Paxosは候補値のうち一つを選ぶ合意です。両者を組み合わせたトランザクション処理はあり得ますが、解こうとしている問題の定義そのものが違います。また、通常のPaxosは、任意の嘘をつくビザンチン型のアクセプタを扱いません。

Raftは、Multi-Paxosと同等の結果を生むクラッシュ耐性のある複製ログを、理解しやすさを設計目標にして整理した方式です。サーバーはフォロワー・候補者・リーダーのいずれかになり、時間を単調に増える任期へ区切ります。フォロワーはハートビートが届かなくなると候補者になり、同じ任期で過半数の票を得た一台だけがリーダーになります。

リーダーはログのエントリをAppendEntries RPCで複製します。中心にあるのは次の性質です。同じインデックスと任期を持つエントリが二つのログにあれば、それ以前も一致するというLog Matching。コミット済みのエントリが将来のリーダーにも残るLeader Completeness。同じインデックスに異なる命令を適用しないState Machine Safetyです。

リーダーは、現在の任期のエントリが過半数に保存されたことを確認してからコミットを進めます。未コミットのエントリは新しいリーダーに上書きされることがありますが、コミット済みのエントリは選出時の安全な制約によって保たれます。メンバーシップの変更では、移行中に新旧構成のクォーラムが交差するjoint consensusを用います。

ランダム化した選挙タイムアウトは票の割れを減らして進行を助けますが、それでRaftがビザンチン障害に耐えられるようになるわけではありません。悪意あるサーバーが相手ごとに異なるログを故意に送り分けるようなモデルは、通常のRaftの保証の外側にあります。

ビザンチン障害には、停止だけでなく、相手ごとに異なる値を送る二枚舌、メッセージの改変、プロトコルからの任意の逸脱まで含まれます。悪意ある攻撃者だけでなく、侵害、ソフトウェアの不具合、データの破損も、この強いモデルに収められます。

1982年のByzantine Generals論文では、署名のない口頭メッセージで `m` 人の裏切り者に耐えるには、少なくとも `3m+1` 人の将軍が必要だと示されました。偽造できない署名を仮定すると条件は変わります。ただし「署名があれば公開ネットワークの合意が完成する」わけではありません。誰の公開鍵をレプリカとして数えるのかという、メンバーシップの問題が残ります。

PBFTは、既知で認証された `3f+1` 台のレプリカにより、最大 `f` 台のビザンチン障害のもとで決定的な状態機械複製を行います。プライマリのpre-prepare、レプリカのprepare、commitを通じて、`2f+1` 台ぶんの証明を集めます。クライアントは同じ結果を返す `f+1` の応答を受け取り、そのうち少なくとも一つが正しいレプリカから来ていることを確かめます。

PBFTの安全性はメッセージの遅延に依存しませんが、生存性のほうは、正しいノードとメッセージが無期限には遅れないという弱い同期の仮定を必要とします。また `3f+1` という閾値は、レプリカの故障が互いに独立であることと、メンバーシップが既知であることを前提にしています。一人が際限なく識別情報を作れる環境では、その前提を別の仕組みで確立しなければなりません。

ビットコインの白書は「Nakamoto consensus」という語を使っていません。後にそう呼ばれるようになった設計は、いくつかの部品を一つに組み合わせたものです。P2Pのブロードキャスト、各ノードによる規則の検証、Proof of Workによるブロックの提案、競合したときのチェーン選択、そして報酬です。

マイナーは、ブロックヘッダーのハッシュがターゲット以下になるナンスなどを探索します。成功は、ハッシュパワーに比例した確率的なリーダー選出として働きます。白書の「one-CPU-one-vote」は、IPアドレスや仮名の頭数ではなく計算資源で重み付けするという説明です。ASICが中心の現在は「ハッシュパワー加重」と読むほうが正確です。

有効なブロックが複数ほぼ同時に見つかると、一時的なフォークが生じます。各フルノードは、自分が検証した有効なブロックだけを対象に、作り直すのが最も難しいチェーン、すなわち累積Proof of Workが最大のチェーンへ収束します。単にブロック数が多いチェーンでもなければ、無効なチェーンでもありません。

形式的な研究では、Bitcoin backboneの性質をcommon prefix、chain quality、chain growthなどで記述します。その上に、トランザクションの永続性と生存性を持つ台帳を構成します。Garay、Kiayias、Leonardosは、元の提案をそのまま一般的なByzantine Agreementの解としては扱いませんでした。追加のプロトコルと、ハッシュパワーやネットワークの同期についての仮定を明示しています。ビットコインは、古典的なBAと同じ問題を同じ保証で解いているのではありません。

ファイナリティとは、「もう覆らない」を何によって定義するかという問題です。Paxosでは、あるインスタンスで値がいったん選ばれると、同じインスタンスで別の値が選ばれることはありません。ただし、その事実をすべてのラーナーがただちに知るとは限りません。Raftでも、コミット済みのエントリと、まだリーダーの手元のログにしかないエントリを区別します。

PBFTでは、障害の許容範囲内でコミット証明を得た命令に、決定的なファイナリティがあります。ビットコインでは、チェーン先端での競合が通常の動作として許され、後続のブロックが増えるほど再編成の確率が下がります。承認数は確率的な安全余裕であり、どの承認数であっても、絶対に覆らないことを保証するプロトコル上の定数はありません。

「決定的」と「速い」、「確率的」と「危険」は同義ではありません。決定的な方式もクォーラムを失えば停止しますし、確率的な方式も、十分な深さと分散したハッシュパワーのもとでは実用上の高い安全性を持ちます。用途ごとに、停止するリスクと再編成のリスクを比べることになります。

ビットコインでは、すべてのノードが明示的な投票メッセージを交換して同時に決定するわけではありません。ウォレットはトランザクションを作って署名し、ピアへブロードキャストします。フルノードは、トランザクションとブロックを合意規則に照らして独立に検証します。マイナーは有効なトランザクションから候補ブロックを作り、Proof of Workを競います。

マイナーが担うのは、候補となる履歴の提案と順序づけ、そしてチェーンを書き換えるコストの形成です。マイナーが十分なProof of Workを付けても、発行上限を超えるコインベース、無効な署名、二重使用などを含むブロックは、フルノードに拒否されます。ハッシュパワーは、無効なものを有効に変える票ではありません。

フルノードが実行する合意規則と、競合する有効な履歴を一つに収束させる合意メカニズムは、分けて考えると理解しやすくなります。利用者、取引所、加盟店といった経済的な担い手は、どのソフトウェアとどの規則を受け入れるかを自ら選びます。プロトコルの変更は、ノードの数の単純な集計やマイナーの投票だけで自動的に決まるものではありません。

ビットコインが合意する対象は「世界の真実」一般ではありません。規則に従うトランザクションが有効かどうかと、有効なブロック履歴のうちどれを現在のベストチェーンとして扱うかです。価格や法的な所有権、現実世界の出来事の正しさまでは、チェーン単独では決められません。

最適な方式を一列に順位づけすることはできません。データセンター内で既知のサーバーのクラッシュに耐えたいなら、PaxosやRaftの仮定が合います。既知のレプリカの任意の振る舞いまで扱うなら、BFTが候補になります。中央のメンバーシップ管理なしで公開台帳を維持するビットコインは、追加のコストと確率的なファイナリティを受け入れて、別の問題を解いています。

設計を読むときの最後の問いは、「何を信頼しなくてよくなったか」だけでなく「代わりに何を仮定したか」です。クォーラムの独立性、鍵とメンバーシップ、リーダーの安定、ネットワークでの伝播、ハッシュパワーの分布、利用者による規則の検証。合意は信頼を消す魔法ではなく、信頼を検証できる仮定へ分解する技術です。