リップルプロトコルコンセンサスアルゴリズム

Abstract

Byzantine Generals Problemに対するいくつかの合意アルゴリズムが存在するが、特に分散型決済システムに関連して、その多くはネットワーク内のすべてのノードが同期的に通信する必要があるという要件に起因する高い遅延の問題を抱えている。本研究では、より大きなネットワーク内で集合的に信頼されたサブネットワークを活用することにより、この要件を回避する新しい合意アルゴリズムを提示する。Sybil攻撃を防止するために必要な「信頼」は、実際にはグローバルなものではなく、ネットワーク内の各ノードに対してローカルであることを示す。

Rippleプロトコル合意アルゴリズム（RPCA）は、ネットワークの正確性と合意を維持するために、すべてのノードによって数秒ごとに適用される。合意に達すると、現在の台帳は「閉鎖」されたとみなされ、最後に閉鎖された台帳（last-closed ledger）となる。このアルゴリズムは、Byzantine障害に対する強力な保証を維持しながら低い遅延で合意を達成するという点で独自であり、リアルタイムの金融決済システムに適している。

Introduction

分散型決済システムは、障害のあるまたは悪意のあるアクターが存在する状況でも、適時に正しく決済を処理するために合意アルゴリズムを実装しなければならない。ビットコインはプルーフ・オブ・ワーク（proof-of-work）を使用して合意を達成しており、これはすべてのノードが暗号パズルを解くために計算リソースを消費することを要求する。このアプローチは強力なセキュリティ保証を提供するが、高いエネルギー消費、低いトランザクションスループット、高額取引では1時間以上に及ぶ可能性がある長い確認遅延など、重大な欠点がある。

Rippleプロトコル合意アルゴリズムは、プルーフ・オブ・ワークを必要としない分散型合意への新しいアプローチを提供する。代わりに、ネットワーク内のノードは数秒で合意を達成する投票プロセスを通じて、トランザクションセットに集合的に同意する。この合意メカニズムは、実用的な展開に低い遅延と高いスループットが不可欠なグローバル決済ネットワークの要件に合わせて特別に設計されている。

RPCAの重要なイノベーションは、ネットワーク内のすべてのノードが互いに同意する必要がないという点である。代わりに、各ノードは共謀しないと信頼する他のノードのUnique Node List（UNL）を維持する。ノードが選択したUNLが十分な重複を持ち、閾値パーセンテージ未満のノードのみが障害を持つ場合、ネットワークは合意に達する。このアプローチは、合意遅延を分や時間ではなく秒単位で測定しながら、決済システムに必要なセキュリティ保証を提供する。

Definition of Consensus

分散システムにおいて、合意とは、障害のあるまたは悪意のある参加者が存在する状況でも、ノードのネットワークが共有状態について合意に達するプロセスを指す。合意アルゴリズムは3つの基本的な性質を満たさなければならない：正確性（2つの正しいノードが異なる決定をしない）、合意（すべての正しいノードが同じ決定に達する）、そして終了（すべての正しいノードが最終的に決定を下す）。これらの性質は、分散システムが単一の信頼できるノードであるかのように動作することを保証する。

合意を達成する上での課題は、分散システムの本質的な不安定性に起因する。ノードがクラッシュする可能性があり、メッセージが遅延または喪失する可能性があり、Byzantineノードは任意にまたは悪意を持って振る舞う可能性がある。Lamport、Shostak、Peaseが定式化したByzantine Generals Problemは、この課題を捉えている：一部が障害を持つ可能性があり、通信が不安定な状況で、プロセスのグループはどのように合意に達することができるのか？

分散コンピューティングの古典的な結果は、合意アルゴリズムが達成できることの根本的な限界を確立している。FLP不可能性結果は、たった1つのノードが障害を起こす可能性がある非同期システムにおいて、いかなる決定論的アルゴリズムも合意を保証できないことを示している。したがって、実用的な合意アルゴリズムは、安全性（誤った合意に決して達しない）と活性（常に進行する）の間でトレードオフを行わなければならない。ビットコインのプルーフ・オブ・ワークは活性よりも安全性を優先するが、RPCAは現実的な障害仮定の下で強力な安全性保証を維持しながら、限られた時間内に合意ラウンドを完了することで、決済システムにより適したバランスを達成している。

Existing Consensus Algorithms

分散システムにおけるByzantine Generals Problemを解決するために、いくつかの合意アルゴリズムが提案されている。CastroとLiskovが導入したPractical Byzantine Fault Tolerance（PBFT）アルゴリズムは、3f+1個のノードからなるシステムにおいて最大f個のByzantine障害を許容できる。PBFTはすべてのノード間での複数ラウンドのメッセージ交換を通じて合意を達成し、通信計算量はO(n^2)である（nはノード数）。PBFTは強力な安全性保証と小規模ネットワークでの比較的低い遅延を提供するが、二次的な通信オーバーヘッドのため大規模ネットワークへの拡張性に課題がある。

Lamportが開発したPaxosとその変種は、非同期システムにおいて合意を提供するが、Byzantine障害ではなくクラッシュ障害を仮定している。Paxosは、提案者が値を提案し受諾者が投票する一連のラウンドを通じて合意を達成する。Paxosは任意のメッセージ遅延とプロセスクラッシュを許容できるが、Byzantine障害を処理するには慎重なエンジニアリングが必要であり、特定のシナリオではライブロック（livelock）が発生する可能性がある。

ビットコインのプルーフ・オブ・ワーク合意アルゴリズムは、Byzantine攻撃を経済的に不可能にするという根本的に異なるアプローチを取っている。ノードは暗号パズルを解くために競争し、勝者が次のトランザクションブロックを提案する。このアプローチは任意のネットワークサイズに拡張でき、Byzantine障害を処理するが、深刻な欠点がある：膨大なエネルギー消費（ビットコインネットワークで年間1億5千万ドル以上と推定）、長い確認遅延（高額取引では40〜60分であることが多い）、そして限られたスループット（毎秒約7トランザクション）。これらの制限により、プルーフ・オブ・ワークは迅速な決済と高いトランザクション量を必要とする多くの決済システムアプリケーションには不適切である。

Ripple Protocol Consensus Algorithm

Rippleプロトコル合意アルゴリズム（RPCA）は、各サーバーがまだ適用されていないすべての有効なトランザクションを候補トランザクションとして収集することから始まる。その後、サーバーは現在の台帳に適用するトランザクションセットについて合意に向けて反復的に作業するマルチラウンドプロトコルに従う。各ラウンドで、サーバーは次の台帳に含めるべきだと考えるトランザクションからなる提案を作成する。

各合意ラウンド中、サーバーは自身のUnique Node List（UNL）内の他のサーバーに提案を伝達する。その後、サーバーはどのトランザクションが閾値パーセンテージ以上の提案に含まれているかを計算する。初期段階ではこの閾値は50%に設定されており、トランザクションが次のラウンドで考慮されるには、サーバーのUNLの少なくとも半分の提案に含まれている必要がある。合意が連続するラウンドを経るにつれ、この閾値は段階的に引き上げられる（通常60%、70%、そして最終的に80%）。

トランザクションがサーバーのUNLにおいて80%の絶対多数支持の閾値を達成すると、そのトランザクションは最終合意ラウンドに対するサーバーの提案に含まれる。ネットワーク全体でこの閾値に達したすべてのトランザクションは台帳に適用され、台帳は暗号学的にハッシュされ署名される。この新たに検証された台帳が最後に閉鎖された台帳となり、次の候補トランザクションセットでプロセスが再び開始される。

合意プロセスは通常5秒以内に完了し、ほとんどのトランザクションは絶対多数の閾値を達成するために1回の合意ラウンドのみを必要とする。1回のラウンドで合意を達成しなかったトランザクションは、後続のラウンドの候補として残る。この設計は、信頼された検証者の絶対多数の支持なしにはいかなるトランザクションも台帳に適用できないため、強力な安全性保証を維持しながらネットワークが継続的に進行することを保証する。

Formal Analysis of Convergence

RPCAの正確性は、ネットワーク内の異なるノードが選択したUNL間の重複に決定的に依存する。UNL_iをノードiのUnique Node Listとし、UNL_i ∩ UNL_jをUNL_iとUNL_jの両方に含まれるノードの集合とする。ネットワークが合意を維持するためには、任意の2つのノードiとjに対して、それらのUNLの共通部分がいずれかのUNLの最大サイズに対して十分に大きい必要がある。

具体的には、プロトコルはすべてのノードペアiとjに対して|UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5である場合に安全性を保証する。この条件は、Byzantineノードがネットワークの異なる部分に異なる合意決定をさせようとしても、信頼ノードの重複がフォークを防止することを保証する。この条件が成立し、いずれのUNLにおいてもByzantineノードが1/5未満であれば、すべての正しいノードは同じ合意決定に達する。

形式的証明は、2つのノードが異なる合意決定に達する可能性がある場合、一方のノードの最終台帳には含まれるがもう一方には含まれないトランザクションTが存在しなければならないことを示すことによって進む。これが発生するためには、Tが最初のノードのUNLで80%の支持を達成しているが、2番目のノードのUNLでは80%未満の支持しか得ていない必要がある。しかし、重複要件とByzantineノードの制約を考慮すると、このシナリオは不可能であることが示される：TがUNL_iで80%の支持を達成した場合、重複条件を満たすいかなるUNL_jでも少なくとも60%の支持を達成しなければならず、十分な合意ラウンドを経れば80%に収束するか、両方のノードによって拒否される。

活性の性質——合意が最終的に達成されること——は、包含のための閾値が合意ラウンドを通じて決定論的に増加するという観察から導かれる。Byzantineノードとネットワーク遅延が存在しても、プロトコルは誠実なノードの絶対多数が支持するトランザクションが最終的に含まれ、そのような支持を欠くトランザクションが除外されることを保証する。合意のための限られた時間（通常5秒）は、決済システムアプリケーションに適した実用的な活性保証を提供する。

Unique Node Lists

Unique Node List（UNL）は、RPCAを他の合意アルゴリズムと区別する根本的な構成要素である。Rippleネットワークの各ノードは、ネットワークを欺くために共謀しないと信頼する他のノードからなるUNLを維持する。重要なのは、この信頼がグローバルではなくローカルであるということである：異なるノードは異なるUNLを持つことができ、グローバルに合意された検証者セットは要求されない。この設計により、分散化を維持しながらネットワークが有機的に拡張できる。

UNLは、プルーフ・オブ・ワークなしにSybil攻撃防止メカニズムとして機能する。単純な投票システムでは、攻撃者は不均衡な影響力を得るために多数の偽名ノードを作成できる。各ノードが信頼する他のノードを明示的に選択することを要求することにより、RPCAは、それらのアイデンティティが既存のノードを説得してUNLに追加されない限り、追加のアイデンティティを作成しても何の利点も得られないことを保証する。これにより、Sybil耐性の問題は計算的支出から評判と信頼関係に移行する。

ネットワークが正しく機能するためには、形式的分析で説明したように、UNLが十分な重複を持つように選択されなければならない。実際には、各ノード運営者がUNL選択において自律性を持ちながらも、ネットワークの他の部分でも信頼されている検証者をリストに含めることを保証しなければならないことを意味する。Rippleは多様なエンティティが運営する検証者からなるデフォルトUNLを提供するが、ノード運営者は独自の信頼評価に基づいてこのリストを自由に変更できる。

UNLメカニズムはまた、段階的な分散化への自然な道筋を提供する。ネットワークの初期段階では、安定性と信頼性を確保するために、より集中化された検証者セットが適切かもしれない。ネットワークが成熟し、より多様な運営者がその信頼性を実証するにつれて、UNLはセキュリティ特性を損なうことなく、ネットワークの耐障害性と分散化を高めるより広範な検証者セットを含むように進化できる。

Simulation Code

RPCAの理論的分析を検証し、さまざまな条件下でのパフォーマンスを評価するために、カスタムビルドのシミュレーションソフトウェアを使用して大規模なシミュレーションが実施された。シミュレーションフレームワークは、それぞれ独自のUNLを維持し合意プロトコルに参加するノードのネットワークをモデル化する。コードは、トランザクション提案、閾値が増加する投票ラウンド、台帳検証を含む完全なRPCAアルゴリズムを実装している。

シミュレーションで変更された主要なパラメータには、ネットワークサイズ（10から1,000ノード）、Byzantineノードの割合（0%から20%）、UNLサイズ（通常5から50ノード）、およびネットワークトポロジー構成が含まれる。各パラメータ構成に対して、結果の統計的妥当性を確保するために異なるランダムシードを使用して複数のシミュレーション実行が行われた。シミュレーションは合意遅延、フォーク確率、トランザクションスループットを含むメトリクスを追跡した。

シミュレーション結果は、収束と安全性に関する理論的予測を確認している。UNL重複条件が満たされ、Byzantineノードが各UNLの20%未満であるすべての構成において、ネットワークはフォークなしに正常に合意に達した。合意遅延はネットワークサイズに関係なく一貫して低く維持され（通常3〜5秒のシミュレーション時間内に完了）、アルゴリズムのスケーラビリティを実証した。合意を妨害しようと積極的に試みる15%のByzantineノードが存在しても、UNL重複要件が満たされている限り、ネットワークは正確性を維持した。

追加のシミュレーションは、ネットワーク分割、UNL構成の突然の変更、Byzantineノードによる協調攻撃を含むエッジケースと障害シナリオを探索した。これらのシミュレーションはプロトコルの堅牢性に関する洞察を提供し、UNL選択とネットワーク運用に関する推奨ベストプラクティスの策定に寄与した。独立した検証とさらなる研究を可能にするため、完全なシミュレーションコードが公開されている。

Discussion

ビットコインのプルーフ・オブ・ワーク合意と比較して、RPCAは決済システムアプリケーションにいくつかの重要な利点を提供する。最も注目すべきは、合意遅延が40〜60分（高額ビットコイン取引に通常推奨される時間）から約5秒に短縮されることである。この改善により、RPCAはほぼ即時の決済が必要なPOS（販売時点）やその他のアプリケーションに適している。さらに、RPCAはプルーフ・オブ・ワークと比較して最小限の計算リソースしか必要とせず、ビットコインマイニングに伴う膨大なエネルギー消費を排除する。

しかし、これらの利点には異なる信頼仮定が伴う。ビットコインのセキュリティが、いかなる攻撃者もネットワークの計算能力の50%以上を制御しないという仮定のみに依存するのに対し、RPCAはノードが十分な重複を持つUNLを選択し、ByzantineノードがこれらのUNL内で閾値を超えないことを要求する。これにより、慎重な信頼決定を行う責任の一部がノード運営者に移る。実際には、参加機関が既存の信頼関係を持つ多くの決済システムユースケースにおいて、このトレードオフは許容可能である。

ネットワークトポロジーとUNL選択戦略は、合意システムの特性に大きく影響する。すべてのノードがUNLに同じ検証者を含む高度に集中化されたトポロジーは安全性を最大化するが、それらの検証者が利用不可になった場合、活性が低下する可能性がある。逆に、UNLの重複が最小限の高度に分散化されたトポロジーは活性を改善する可能性があるが、重複が疎になりすぎると合意障害のリスクがある。最適なバランスを見つけるには、特定のデプロイメントシナリオとリスク許容度の慎重な考慮が必要である。

将来の研究では、分散化を最大化しながら重複要件を自動的に維持する適応的UNL選択アルゴリズム、観察された検証者の行動に基づいてノードがUNLを動的に調整するメカニズム、そしてさらに高い割合のByzantineノードを許容できる合意アルゴリズムの拡張を探求できる可能性がある。これらの強化により、大規模分散型決済システムに対するRPCAの堅牢性と適用可能性がさらに向上する可能性がある。

Conclusion

Rippleプロトコル合意アルゴリズムは、決済システムのための分散型合意における重要な進歩を表している。すべてのノード間のグローバルな合意を要求する代わりに、集合的に信頼されたサブネットワークを活用することにより、RPCAはByzantine障害に対する強力な保証を維持しながら数秒で合意を達成する。形式的分析は、UNLが十分な重複で選択され、Byzantineノードが閾値以下に維持される限り、ネットワークがフォークなしに正しい合意に達することを実証している。

本研究の実用的な意味合いは、Ripple決済ネットワークを超えて広がる。RPCAは、合意遅延とセキュリティ保証の間の従来のトレードオフが、慎重なプロトコル設計とローカルな信頼関係の利用を通じて克服できることを示している。このアプローチは、低い遅延が重要であり参加者が既存の信頼関係を持つ他の分散システム、例えば銀行間決済システム、サプライチェーン追跡、その他の金融インフラアプリケーションに適用可能であると考えられる。

本番システムにおけるRPCAの展開は、アルゴリズムのパフォーマンス特性と堅牢性を検証した。Rippleネットワークは、一貫した3〜5秒の合意遅延で毎秒数千のトランザクションを処理しており、理論的特性が実世界の運用に効果的に反映されることを実証している。ネットワークが進化を続け、多様な運営者からの追加の検証者を組み込むにつれ、分散型合意システムがスケールにおいてセキュリティとパフォーマンスの両方を維持できる方法の実用的な事例を提供している。

References

Lamport, L., Shostak, R., and Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. この画期的な論文は、障害のあるコンポーネントを持つ分散システムにおいて合意に達する問題を定式化し、Byzantine fault-tolerantシステムの理論的基盤を確立した。

Castro, M., and Liskov, B. (1999). "Practical Byzantine Fault Tolerance." Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI). この研究はPBFTを導入し、Byzantine fault toleranceが実用的なパフォーマンスで達成できることを実証したが、O(n^2)の通信計算量がスケーラビリティを制限した。

Nakamoto, S. (2008). "Bitcoin: A Peer-to-Peer Electronic Cash System." このホワイトペーパーは、デジタル通貨における二重支出問題の解決策としてプルーフ・オブ・ワーク合意を導入し、高い遅延とエネルギー消費を代償として、信頼できる当事者なしに分散型合意を可能にした。

Lamport, L. (1998). "The Part-Time Parliament." ACM Transactions on Computer Systems, 16(2):133-169. この論文は、クラッシュ障害の下で非同期システムにおいて合意を達成するPaxosアルゴリズムを提示し、その後の合意プロトコル設計に影響を与えた。

Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). "Impossibility of Distributed Consensus with One Faulty Process." Journal of the ACM, 32(2):374-382. FLP不可能性結果は、非同期システムにおいて合意アルゴリズムが達成できることの根本的な限界を確立し、実用的な合意プロトコルの設計空間を形成した。