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

01合意は「全員一致」の別名ではない

• 分散システムでは、複数のプロセスが同じ出来事を同時には観測しません。メッセージは遅れ、順番が入れ替わり、一部の参加者だけが停止し、場合によっては矛盾する情報を送ります。その中で「ログのこの位置には値Aを置く」と一度決めたなら、正しい参加者が同じ位置へ値Bを確定しないようにするのが分散合意の中心です。
• ここでいう合意は、全ノードが同時刻に同じ画面を表示することでも、参加者全員が賛成票を投じることでもありません。方式によっては一部のノードが決定をまだ知らず、停止していても、quorumが交差することで矛盾する別決定だけを防ぎます。
• Paxos、Raft、PBFT、Bitcoinはいずれも複数主体の順序を扱いますが、交換可能なアルゴリズムではありません。既知のサーバー群を複製する問題と、誰でも仮名で参加できる公開ネットワークの問題では、「一票を誰に与えるか」から設計が異なります。

02一回の決定から複製ログへ

• 古典的な一回限りのconsensus problemは、各プロセスが候補値を持ち、正しいプロセスが一つの値を決める問題として定式化されます。一般に確認する性質は、Agreement（正しい参加者が異なる値を決めない）、Validity（決定値が定められた正当性条件を満たす）、Integrity（同じ参加者が二度決定しない）、Termination（正しい参加者が最終的に決定する）です。文献ごとにValidityの厳密な定義は異なります。
• 実サービスは一つの値だけで終わりません。命令をログのslot 1、2、3へ順番に置くため、一回の合意を繰り返し、同じ初期状態を持つ決定的な状態機械へ同じ順番で適用します。これがreplicated state machineの基本です。
• 合意とatomic broadcastは密接に対応します。誰もが同じメッセージ集合を同じ順序で配信できれば複製ログを作れ、各slotで合意できれば順序付きbroadcastを構成できます。ただし、障害回復、重複要求、再構成、snapshot、client応答まで含む実システムは、一回の定理より広い設計を必要とします。

03方式名より先に仮定を読む

• 合意方式を比較するとき、最初に読むべきなのは処理件数ではなく仮定です。参加者は事前に登録されたサーバーか、公開参加者か。障害は停止だけか、嘘やequivocationまで含むか。通信遅延に上限はあるか。票は身元、stake、計算資源のどれで重み付けされるか。決定は即時に覆らなくなるか、時間とともに覆る確率が下がるか。

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

04Safetyは時間から切り離し、Livenessは時間へ戻る

• 完全同期モデルでは、処理速度とメッセージ配送に既知の上限を置けます。完全非同期モデルでは上限を置かず、応答しない相手が停止したのか、ただ遅いのかを確実には判定できません。部分同期モデルはその中間で、上限は存在するが事前には不明、または未知の時点以降にだけ上限が成立すると仮定します。
• FLP結果が示すのは、完全非同期・決定的プロトコル・一つのcrash faultという条件でも、すべての許容実行でTerminationを保証できないことです。「合意は実現できない」という意味ではありません。実プロトコルは、通信が最終的に安定する、leaderが一定期間生きる、乱数を使う、といった追加条件で進行します。
• 多くの実用方式は、ネットワークがどれほど遅くても矛盾する二決定を作らないSafetyと、ネットワークが十分安定した後に処理が進むLivenessを分けます。timeoutは故障の証明ではなく、leader交代を試すための進行機構です。

05Quorum intersection — 多数決の本当の役割

• quorumの目的は人気を測ることではなく、二つの決定集合を必ず交差させることです。`2f+1` 台のcrash-tolerant構成で過半数を取ると、どの二つの過半数にも少なくとも一台の共通ノードがあります。その共通ノードが過去の受理情報を次のroundへ運ぶことで、別の値が同じslotへ選ばれることを防ぎます。
• ただし、交差点がByzantine nodeだけなら嘘をつけます。`3f+1` replicasから`2f+1`のquorumを取るBFT構成では、二つのquorumは少なくとも`f+1`台で交差し、その中に少なくとも一台の正しいreplicaが含まれます。閾値は故障モデルと証明したい性質から導かれます。
• Bitcoinは登録済みノードの頭数でquorumを作りません。誰でも多数のnode identityを作れるためです。競合する有効チェーンの選択を累積Proof of Workで重み付けし、身元の数ではなく希少な計算資源を履歴提案へ結び付けます。これは過半数quorumの単純な置き換えではなく、異なる参加モデルです。

06Paxos — 過半数が一度選んだ値を守る

• Paxosは既知のacceptor集合でcrash faultに耐え、一つの値を安全に選ぶためのプロトコルです。proposerは一意に順序付けられるballot numberを使います。Phase 1でacceptorへpromiseを求め、より小さいballotを今後受け付けない約束と、すでに受理した中で最大ballotの値を集めます。
• Phase 2では、Phase 1で受理済みの値が見つかればその中で最大ballotの値を、なければ新しい値を提案します。acceptorの過半数が受理した値はchosenです。この制約により、別のproposerが後からより大きいballotで進んでも、同じinstanceで異なる値を選べません。
• Basic Paxosが選ぶのは一つの値です。Multi-Paxosは各log slotへPaxosを適用し、安定したleaderの下でPhase 1を再利用して複製ログを進めます。`2f+1` acceptorsなら`f` crashesに耐えられますが、通信可能な過半数を失えばSafetyを壊さず停止します。
• Paxosはtwo-phase commitの別名ではありません。2PCは参加者全員のtransaction commitを調整し、coordinator故障でblockし得ます。Paxosは候補値のうち一つを選ぶ合意であり、両者を組み合わせたtransaction systemはあり得ても問題定義は別です。また、通常のPaxosは任意の嘘をつくByzantine acceptorを扱いません。

07Raft — Leader、term、logを明示する

• RaftはMulti-Paxosと同等の結果を生むcrash-tolerantな複製ログを、理解しやすさを設計目標として整理した方式です。serverはfollower、candidate、leaderのいずれかになり、時間を単調増加するtermへ分けます。followerがheartbeatを受けないとcandidateになり、同じtermで過半数の票を得た一台だけがleaderになります。
• leaderはlog entryをAppendEntries RPCで複製します。同じindexとtermを持つentryが二つのlogにあれば、それ以前も同じであるというLog Matching、commit済みentryが将来のleaderにも残るLeader Completeness、同じindexへ異なる命令を適用しないState Machine Safetyが中心です。
• leaderは現在termのentryが過半数へ保存されたことを確認してcommitを進めます。未commit entryは新leaderによって上書きされ得ますが、commit済みentryは安全な選挙制約によって保存されます。membership変更では、新旧構成のquorumが移行中に交差するjoint consensusを用います。
• randomized election timeoutはsplit voteを減らして進行を助けますが、RaftをByzantine tolerantにはしません。悪意あるserverが異なるlogを故意に送り分けるモデルは通常のRaftの保証外です。

08Byzantine agreementとPBFT — 嘘をつくreplicaを含める

• Byzantine faultは、停止だけでなく、相手ごとに異なる値を送るequivocation、message改変、protocolからの任意の逸脱を含みます。悪意ある攻撃者だけでなく、侵害、software bug、破損もこの強いモデルへ含められます。
• 1982年のByzantine Generals論文では、署名のないoral messagesで`m` traitorsに耐えるには少なくとも`3m+1` generalsが必要と示されました。偽造不能な署名を仮定すると条件は変わります。ただし「署名があれば公開ネットワークの合意が完成する」わけではありません。誰の公開鍵をreplicaとして数えるかというmembership問題が残ります。
• PBFTは既知で認証された`3f+1` replicasにより、最大`f` Byzantine faultsの下で決定的な状態機械複製を行います。primaryのpre-prepare、replicasのprepare、commitを通じ、`2f+1`の証明を集めます。clientは同じ結果を返す`f+1` repliesを得て、少なくとも一つが正しいreplica由来だと確認します。
• PBFTのSafetyはmessage delayに依存しませんが、Livenessは正しいnodeとmessageが無期限には遅延しないという弱い同期仮定を必要とします。また`3f+1`という閾値は、独立したreplica故障と既知membershipを前提にします。一人が無制限にidentityを作れる環境では、その前提を別の仕組みで確立しなければなりません。

09Nakamoto型合意 — 公開参加を資源で重み付けする

• Bitcoin白書は「Nakamoto consensus」という語を使っていません。後世にそう呼ばれる設計は、P2P broadcast、各nodeによるrule validation、Proof of Workによるblock提案、競合時のchain selection、報酬を一つに組み合わせたものです。
• マイナーはblock headerのhashがtarget以下になるnonce等を探索します。成功はhashpowerに比例する確率的なleader electionとして働きます。白書の「one-CPU-one-vote」はIPや仮名の頭数ではなく計算資源で重み付けするという説明であり、ASICが中心の現在は「hashpower加重」と読む方が正確です。
• 複数の有効blockがほぼ同時に見つかると、一時的なforkが生じます。各full nodeは、自分が検証した有効blockだけを対象に、再作成が最も困難な、すなわち累積Proof of Workが最大のchainへ収束します。単にblock数が多いchainでも、無効なchainでもありません。
• 形式研究では、Bitcoin backboneの性質をcommon prefix、chain quality、chain growthなどで記述し、その上にtransactionのpersistenceとlivenessを持つledgerを構成します。Garay、Kiayias、Leonardosは、元の提案をそのまま一般的なByzantine Agreementの解とは扱わず、追加protocolとhashpower・network synchronyの仮定を明示しました。Bitcoinは古典BAと同じ問題を同じ保証で解くのではありません。

10Finality — 決まったことと、深く埋まったこと

• finalityは「もう覆らない」を何によって定義するかです。Paxosでは、あるinstanceで値が一度chosenになると、同じinstanceで別の値はchosenになりません。ただし、その事実をすべてのlearnerが直ちに知るとは限りません。Raftでもcommit済みentryと、まだleaderのlocal logにしかないentryを区別します。
• PBFTではfault threshold内でcommit certificateを得た命令に決定的finalityがあります。Bitcoinでは、先端の競合が通常動作として許され、後続blockが増えるほどreorganizationの確率が低下します。confirmation数は確率的な安全余裕であり、どの件数にも絶対不可逆を保証するprotocol定数はありません。

• 「決定的」と「速い」、「確率的」と「危険」は同義ではありません。決定的方式もquorumを失えば停止し、確率的方式も十分な深さと分散したhashpowerの下で高い実用安全性を持ちます。用途ごとに停止リスクとreorgリスクを比較します。

11Bitcoinでは誰が何に合意するのか

• Bitcoinでは、すべてのnodeが明示的な投票messageを交換して同時に決定するわけではありません。walletはtransactionを作って署名し、peerへbroadcastします。full nodeはtransactionとblockをconsensus rulesに照らして独立検証し、マイナーは有効transactionから候補blockを作り、Proof of Workを競います。
• マイナーが担うのは、候補履歴の提案と順序付け、chainを書き換えるcostの形成です。マイナーが十分なProof of Workを付けても、発行上限を超えるcoinbase、無効なsignature、二重使用などを含むblockはfull nodeに拒否されます。hashpowerは無効を有効へ変える票ではありません。
• full nodeが実行するconsensus rulesと、競合する有効履歴を収束させるconsensus mechanismは区別すると理解しやすくなります。利用者、取引所、merchantなどのeconomic actorsは、どのsoftwareとrulesを受け入れるかを自ら選びます。protocol変更は単純なnode countやminer pollだけで自動決定されません。
• Bitcoinの合意対象は「世界の真実」一般ではなく、規則に従うtransactionの有効性と、有効block履歴のうちどれを現在のbest chainとして扱うかです。価格、法的所有権、現実世界の出来事の正しさまではchain単独で決めません。

12四方式を同じ物差しで読む

• 最適な方式を一列に順位付けすることはできません。データセンター内で既知serverのcrashに耐えたいならPaxosやRaftの仮定が合い、既知replicaの任意動作まで扱うならBFTが候補になります。中央membership管理なしで公開台帳を維持するBitcoinは、追加costと確率的finalityを受け入れて別の問題を解きます。
• 設計を読む最後の問いは、「何を信頼しなくてよくなったか」だけでなく「代わりに何を仮定したか」です。quorumの独立性、鍵とmembership、leaderの安定、network伝播、hashpower分布、利用者のrule validation。合意は信頼を消す魔法ではなく、検証可能な仮定へ分解する技術です。