リップルプロトコルコンセンサスアルゴリズム
Abstract
Mặc dù đã có nhiều thuật toán đồng thuận cho Bài toán các tướng Byzantine, đặc biệt trong bối cảnh hệ thống thanh toán phân tán, nhiều thuật toán vẫn gặp độ trễ cao do yêu cầu tất cả các nút trong mạng phải giao tiếp đồng bộ. Trong công trình này, chúng tôi trình bày một thuật toán đồng thuận mới vượt qua yêu cầu đó bằng cách tận dụng các mạng con được tin cậy tập thể bên trong mạng lớn hơn. Chúng tôi chỉ ra rằng "niềm tin" cần thiết để ngăn chặn tấn công Sybil thực chất không phải là toàn cục, mà là cục bộ theo từng nút trong mạng.
Thuật toán đồng thuận giao thức Ripple (RPCA) được áp dụng vài giây một lần bởi tất cả các nút để duy trì tính đúng đắn và sự nhất quán của mạng. Khi đạt đồng thuận, sổ cái hiện tại được coi là "đã đóng" và trở thành sổ cái đóng gần nhất. Thuật toán này khác biệt ở chỗ đạt đồng thuận với độ trễ thấp trong khi vẫn duy trì các bảo đảm mạnh trước lỗi Byzantine, phù hợp cho các hệ thống thanh toán tài chính thời gian thực.
Abstract
Byzantine Generals Problemに対するいくつかの合意アルゴリズムが存在するが、特に分散型決済システムに関連して、その多くはネットワーク内のすべてのノードが同期的に通信する必要があるという要件に起因する高い遅延の問題を抱えている。本研究では、より大きなネットワーク内で集合的に信頼されたサブネットワークを活用することにより、この要件を回避する新しい合意アルゴリズムを提示する。Sybil攻撃を防止するために必要な「信頼」は、実際にはグローバルなものではなく、ネットワーク内の各ノードに対してローカルであることを示す。
Rippleプロトコル合意アルゴリズム（RPCA）は、ネットワークの正確性と合意を維持するために、すべてのノードによって数秒ごとに適用される。合意に達すると、現在の台帳は「閉鎖」されたとみなされ、最後に閉鎖された台帳（last-closed ledger）となる。このアルゴリズムは、Byzantine障害に対する強力な保証を維持しながら低い遅延で合意を達成するという点で独自であり、リアルタイムの金融決済システムに適している。
Introduction
Một hệ thống thanh toán phân tán phải triển khai thuật toán đồng thuận để xử lý thanh toán chính xác và kịp thời ngay cả khi có tác nhân lỗi hoặc độc hại. Bitcoin đạt đồng thuận bằng proof-of-work, yêu cầu tất cả các nút tiêu tốn tài nguyên tính toán để giải các bài toán mật mã. Dù cách tiếp cận này cung cấp bảo đảm bảo mật mạnh, nó có các hạn chế đáng kể như tiêu thụ năng lượng cao, thông lượng giao dịch thấp và độ trễ xác nhận dài, có thể kéo dài đến một giờ hoặc hơn với giao dịch giá trị cao.
Thuật toán đồng thuận giao thức Ripple đưa ra một cách tiếp cận mới cho đồng thuận phân tán mà không cần proof-of-work. Thay vào đó, các nút trong mạng cùng thống nhất trên các tập giao dịch thông qua cơ chế bỏ phiếu đạt đồng thuận chỉ trong vài giây. Cơ chế này được thiết kế riêng cho yêu cầu của một mạng thanh toán toàn cầu, nơi độ trễ thấp và thông lượng cao là điều kiện bắt buộc để triển khai thực tế.
Đổi mới cốt lõi của RPCA là không yêu cầu mọi nút trong mạng phải đồng ý trực tiếp với nhau. Thay vào đó, mỗi nút duy trì một Unique Node List (UNL) gồm các nút khác mà nó tin rằng sẽ không thông đồng. Miễn là các UNL do các nút chọn có độ chồng lấn đủ lớn và số nút lỗi thấp hơn một ngưỡng nhất định, mạng sẽ đạt đồng thuận. Cách làm này giữ được các bảo đảm bảo mật cần thiết cho hệ thống thanh toán đồng thời rút ngắn độ trễ đồng thuận xuống mức giây thay vì phút hoặc giờ.
Introduction
分散型決済システムは、障害のあるまたは悪意のあるアクターが存在する状況でも、適時に正しく決済を処理するために合意アルゴリズムを実装しなければならない。ビットコインはプルーフ・オブ・ワーク（proof-of-work）を使用して合意を達成しており、これはすべてのノードが暗号パズルを解くために計算リソースを消費することを要求する。このアプローチは強力なセキュリティ保証を提供するが、高いエネルギー消費、低いトランザクションスループット、高額取引では1時間以上に及ぶ可能性がある長い確認遅延など、重大な欠点がある。
Rippleプロトコル合意アルゴリズムは、プルーフ・オブ・ワークを必要としない分散型合意への新しいアプローチを提供する。代わりに、ネットワーク内のノードは数秒で合意を達成する投票プロセスを通じて、トランザクションセットに集合的に同意する。この合意メカニズムは、実用的な展開に低い遅延と高いスループットが不可欠なグローバル決済ネットワークの要件に合わせて特別に設計されている。
RPCAの重要なイノベーションは、ネットワーク内のすべてのノードが互いに同意する必要がないという点である。代わりに、各ノードは共謀しないと信頼する他のノードのUnique Node List（UNL）を維持する。ノードが選択したUNLが十分な重複を持ち、閾値パーセンテージ未満のノードのみが障害を持つ場合、ネットワークは合意に達する。このアプローチは、合意遅延を分や時間ではなく秒単位で測定しながら、決済システムに必要なセキュリティ保証を提供する。
Definition of Consensus
Trong hệ thống phân tán, đồng thuận là quá trình một mạng các nút đi đến thống nhất về một trạng thái chung, bất chấp sự hiện diện của các thành phần lỗi hoặc độc hại. Một thuật toán đồng thuận phải thỏa mãn ba thuộc tính nền tảng: tính đúng đắn (không có hai nút đúng đưa ra quyết định khác nhau), sự nhất trí (mọi nút đúng đều đi đến cùng một quyết định), và tính kết thúc (mọi nút đúng cuối cùng đều đưa ra quyết định). Các thuộc tính này bảo đảm hệ thống phân tán hành xử như thể nó là một nút duy nhất và đáng tin cậy.
Khó khăn của đồng thuận đến từ tính không đáng tin cậy vốn có của hệ thống phân tán. Nút có thể gặp sự cố, thông điệp có thể bị trễ hoặc thất lạc, và nút Byzantine có thể hành xử tùy ý hoặc độc hại. Bài toán các tướng Byzantine, được Lamport, Shostak và Pease hình thức hóa, mô tả đúng thách thức này: làm thế nào một nhóm tiến trình đạt được thống nhất khi một phần có thể bị lỗi và truyền thông không đáng tin cậy?
Các kết quả cổ điển trong tính toán phân tán đặt ra giới hạn nền tảng cho những gì thuật toán đồng thuận có thể đạt được. Kết quả bất khả thi FLP cho thấy không thuật toán tất định nào có thể bảo đảm đồng thuận trong hệ bất đồng bộ nếu chỉ một nút cũng có thể lỗi. Vì vậy, các thuật toán đồng thuận thực tế phải đánh đổi giữa an toàn (không bao giờ đạt đồng thuận sai) và tính sống (luôn tiếp tục tiến triển). Proof-of-work của Bitcoin ưu tiên an toàn hơn tính sống, trong khi RPCA đạt cân bằng phù hợp hơn cho hệ thống thanh toán bằng cách hoàn tất các vòng đồng thuận trong thời gian hữu hạn mà vẫn duy trì bảo đảm an toàn mạnh dưới các giả định lỗi thực tế.
Definition of Consensus
分散システムにおいて、合意とは、障害のあるまたは悪意のある参加者が存在する状況でも、ノードのネットワークが共有状態について合意に達するプロセスを指す。合意アルゴリズムは3つの基本的な性質を満たさなければならない：正確性（2つの正しいノードが異なる決定をしない）、合意（すべての正しいノードが同じ決定に達する）、そして終了（すべての正しいノードが最終的に決定を下す）。これらの性質は、分散システムが単一の信頼できるノードであるかのように動作することを保証する。
合意を達成する上での課題は、分散システムの本質的な不安定性に起因する。ノードがクラッシュする可能性があり、メッセージが遅延または喪失する可能性があり、Byzantineノードは任意にまたは悪意を持って振る舞う可能性がある。Lamport、Shostak、Peaseが定式化したByzantine Generals Problemは、この課題を捉えている：一部が障害を持つ可能性があり、通信が不安定な状況で、プロセスのグループはどのように合意に達することができるのか？
分散コンピューティングの古典的な結果は、合意アルゴリズムが達成できることの根本的な限界を確立している。FLP不可能性結果は、たった1つのノードが障害を起こす可能性がある非同期システムにおいて、いかなる決定論的アルゴリズムも合意を保証できないことを示している。したがって、実用的な合意アルゴリズムは、安全性（誤った合意に決して達しない）と活性（常に進行する）の間でトレードオフを行わなければならない。ビットコインのプルーフ・オブ・ワークは活性よりも安全性を優先するが、RPCAは現実的な障害仮定の下で強力な安全性保証を維持しながら、限られた時間内に合意ラウンドを完了することで、決済システムにより適したバランスを達成している。
Existing Consensus Algorithms
Nhiều thuật toán đồng thuận đã được đề xuất để giải Bài toán các tướng Byzantine trong hệ thống phân tán. Thuật toán Practical Byzantine Fault Tolerance (PBFT), do Castro và Liskov giới thiệu, có thể chịu tối đa f lỗi Byzantine trong hệ gồm 3f+1 nút. PBFT đạt đồng thuận qua nhiều vòng trao đổi thông điệp giữa tất cả các nút, với độ phức tạp truyền thông O(n^2), trong đó n là số nút. Dù PBFT có bảo đảm an toàn mạnh và độ trễ tương đối thấp với mạng nhỏ, nó không mở rộng tốt lên mạng lớn do chi phí truyền thông bậc hai.
Paxos và các biến thể của nó, do Lamport phát triển, đạt đồng thuận trong hệ bất đồng bộ nhưng giả định lỗi sập (crash) thay vì lỗi Byzantine. Paxos vận hành qua các vòng mà bên đề xuất đưa ra giá trị và bên chấp nhận bỏ phiếu. Dù có thể chịu trễ thông điệp tùy ý và lỗi sập tiến trình, Paxos cần thiết kế cẩn thận để xử lý lỗi Byzantine và có thể gặp livelock trong một số tình huống.
Thuật toán đồng thuận proof-of-work của Bitcoin theo một hướng tiếp cận khác về bản chất: làm cho tấn công Byzantine trở nên không khả thi về kinh tế. Các nút cạnh tranh giải bài toán mật mã, nút thắng sẽ đề xuất khối giao dịch tiếp theo. Cách làm này mở rộng được đến quy mô mạng tùy ý và xử lý được lỗi Byzantine, nhưng có nhược điểm nghiêm trọng: tiêu thụ năng lượng rất lớn (ước tính hơn 150 triệu USD mỗi năm cho mạng Bitcoin), độ trễ xác nhận dài (thường 40-60 phút cho giao dịch giá trị cao), và thông lượng hạn chế (khoảng 7 giao dịch mỗi giây). Các hạn chế này khiến proof-of-work không phù hợp với nhiều ứng dụng thanh toán cần quyết toán nhanh và khối lượng giao dịch cao.
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
Thuật toán Đồng thuận Giao thức Ripple (RPCA) bắt đầu khi mỗi máy chủ lấy tất cả các giao dịch hợp lệ mà nó đã thấy nhưng chưa được áp dụng làm giao dịch ứng viên. Các máy chủ sau đó tuân theo một giao thức nhiều vòng, lặp dần để đạt đồng thuận về tập giao dịch sẽ áp dụng cho sổ cái hiện tại. Trong mỗi vòng, máy chủ đưa ra đề xuất gồm các giao dịch mà nó cho rằng nên được đưa vào sổ cái tiếp theo.
Trong mỗi vòng đồng thuận, máy chủ truyền đề xuất của mình đến các máy chủ khác trong Unique Node List (UNL) của nó. Sau đó, máy chủ tính giao dịch nào xuất hiện trong một tỷ lệ ngưỡng của các đề xuất. Ban đầu ngưỡng này là 50%, nghĩa là giao dịch phải xuất hiện trong đề xuất từ ít nhất một nửa UNL của máy chủ thì mới được xét ở vòng sau. Khi đồng thuận tiến qua các vòng liên tiếp, ngưỡng này tăng dần (thường lên 60%, 70% và cuối cùng 80%).
Khi một giao dịch đạt ngưỡng siêu đa số 80% ủng hộ trong UNL của máy chủ, giao dịch đó sẽ được đưa vào đề xuất của máy chủ cho vòng đồng thuận cuối. Tất cả các giao dịch đạt ngưỡng này trên toàn mạng được áp dụng vào sổ cái, sau đó sổ cái được băm và ký bằng mật mã. Sổ cái mới được xác thực này trở thành sổ cái đóng gần nhất, và quy trình bắt đầu lại với tập giao dịch ứng viên tiếp theo.
Quy trình đồng thuận thường hoàn tất trong 5 giây hoặc ít hơn, với phần lớn giao dịch chỉ cần một vòng đồng thuận để đạt ngưỡng siêu đa số. Giao dịch chưa đạt đồng thuận trong một vòng sẽ tiếp tục là ứng viên cho các vòng sau. Thiết kế này bảo đảm mạng liên tục tiến triển trong khi vẫn giữ an toàn mạnh, vì không giao dịch nào có thể được áp dụng vào sổ cái nếu không có sự ủng hộ siêu đa số từ các validator đáng tin cậy.
Ripple Protocol Consensus Algorithm
Rippleプロトコル合意アルゴリズム（RPCA）は、各サーバーがまだ適用されていないすべての有効なトランザクションを候補トランザクションとして収集することから始まる。その後、サーバーは現在の台帳に適用するトランザクションセットについて合意に向けて反復的に作業するマルチラウンドプロトコルに従う。各ラウンドで、サーバーは次の台帳に含めるべきだと考えるトランザクションからなる提案を作成する。
各合意ラウンド中、サーバーは自身のUnique Node List（UNL）内の他のサーバーに提案を伝達する。その後、サーバーはどのトランザクションが閾値パーセンテージ以上の提案に含まれているかを計算する。初期段階ではこの閾値は50%に設定されており、トランザクションが次のラウンドで考慮されるには、サーバーのUNLの少なくとも半分の提案に含まれている必要がある。合意が連続するラウンドを経るにつれ、この閾値は段階的に引き上げられる（通常60%、70%、そして最終的に80%）。
トランザクションがサーバーのUNLにおいて80%の絶対多数支持の閾値を達成すると、そのトランザクションは最終合意ラウンドに対するサーバーの提案に含まれる。ネットワーク全体でこの閾値に達したすべてのトランザクションは台帳に適用され、台帳は暗号学的にハッシュされ署名される。この新たに検証された台帳が最後に閉鎖された台帳となり、次の候補トランザクションセットでプロセスが再び開始される。
合意プロセスは通常5秒以内に完了し、ほとんどのトランザクションは絶対多数の閾値を達成するために1回の合意ラウンドのみを必要とする。1回のラウンドで合意を達成しなかったトランザクションは、後続のラウンドの候補として残る。この設計は、信頼された検証者の絶対多数の支持なしにはいかなるトランザクションも台帳に適用できないため、強力な安全性保証を維持しながらネットワークが継続的に進行することを保証する。
Formal Analysis of Convergence
Tính đúng đắn của RPCA phụ thuộc quyết định vào độ chồng lấn giữa các UNL do các nút khác nhau chọn trong mạng. Gọi UNL_i là unique node list của nút i, và UNL_i ∩ UNL_j là tập các nút xuất hiện trong cả UNL_i và UNL_j. Để mạng duy trì đồng thuận, với mọi cặp nút i và j, giao của hai UNL phải đủ lớn so với kích thước lớn hơn giữa hai UNL đó.
Cụ thể, giao thức bảo đảm an toàn khi |UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5 cho mọi cặp i, j. Điều kiện này bảo đảm rằng ngay cả khi các nút Byzantine cố làm các phần khác nhau của mạng đạt các quyết định đồng thuận khác nhau, phần chồng lấn các nút đáng tin vẫn ngăn được phân nhánh. Nếu điều kiện này đúng và số nút Byzantine trong bất kỳ UNL nào nhỏ hơn 1/5, thì mọi nút đúng sẽ đi đến cùng một quyết định đồng thuận.
Chứng minh hình thức cho thấy rằng nếu hai nút có thể đi đến hai quyết định đồng thuận khác nhau, phải tồn tại một giao dịch T xuất hiện trong sổ cái cuối của một nút nhưng không có trong nút kia. Để điều này xảy ra, T phải đạt 80% ủng hộ trong UNL của nút thứ nhất nhưng dưới 80% trong UNL của nút thứ hai. Tuy nhiên, với yêu cầu chồng lấn và ràng buộc tỷ lệ Byzantine, kịch bản này là bất khả: nếu T đạt 80% trong UNL_i, nó phải đạt ít nhất 60% trong bất kỳ UNL_j nào thỏa điều kiện chồng lấn; và với đủ số vòng đồng thuận, mức này sẽ hội tụ về 80% hoặc bị cả hai nút loại bỏ.
Thuộc tính tính sống, tức đồng thuận cuối cùng sẽ đạt được, đến từ việc ngưỡng đưa vào tăng một cách tất định qua các vòng đồng thuận. Ngay cả khi có nút Byzantine và độ trễ mạng, giao thức vẫn bảo đảm các giao dịch được siêu đa số nút trung thực ủng hộ cuối cùng sẽ được đưa vào, còn các giao dịch không có mức ủng hộ đó sẽ bị loại. Thời gian đồng thuận hữu hạn (thường khoảng 5 giây) mang lại bảo đảm tính sống thực tế phù hợp với các ứng dụng thanh toán.
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) là thành phần cốt lõi của RPCA, tạo nên điểm khác biệt với các thuật toán đồng thuận khác. Mỗi nút trong mạng Ripple duy trì một UNL gồm các nút khác mà nó tin rằng sẽ không thông đồng để gian lận mạng. Điểm then chốt là niềm tin này mang tính cục bộ, không phải toàn cục: các nút khác nhau có thể có UNL khác nhau, và không có yêu cầu phải tồn tại một tập validator thống nhất toàn mạng. Thiết kế này cho phép mạng mở rộng tự nhiên trong khi vẫn giữ tính phi tập trung.
UNL đóng vai trò cơ chế chống tấn công Sybil mà không cần proof-of-work. Trong hệ bỏ phiếu ngây thơ, kẻ tấn công có thể tạo nhiều danh tính giả để giành ảnh hưởng không cân xứng. Bằng cách buộc mỗi nút phải chỉ rõ nó tin nút nào, RPCA bảo đảm việc tạo thêm danh tính không mang lại lợi thế trừ khi các danh tính đó thuyết phục được các nút hiện có thêm chúng vào UNL. Nhờ đó, bài toán kháng Sybil được chuyển từ chi phí tính toán sang quan hệ uy tín và tin cậy.
Để mạng hoạt động đúng, UNL phải được chọn sao cho có độ chồng lấn đủ lớn như đã nêu trong phân tích hình thức. Trong thực tế, điều này có nghĩa là dù mỗi nhà vận hành nút có quyền tự chủ khi chọn UNL, họ vẫn cần bảo đảm danh sách của mình bao gồm các validator cũng được các phần khác của mạng tin cậy. Ripple cung cấp một UNL mặc định gồm các validator do nhiều thực thể vận hành, nhưng nhà vận hành có thể điều chỉnh danh sách này theo đánh giá tin cậy riêng.
Cơ chế UNL cũng tạo ra con đường tự nhiên hướng đến phi tập trung dần theo thời gian. Ở giai đoạn đầu của mạng, tập validator tập trung hơn có thể phù hợp để bảo đảm ổn định và độ tin cậy. Khi mạng trưởng thành và nhiều nhà vận hành đa dạng chứng minh được uy tín, UNL có thể tiến hóa để bao gồm tập validator rộng hơn, tăng khả năng chống chịu và mức độ phi tập trung mà không làm suy giảm các thuộc tính bảo mật.
Unique Node Lists
Unique Node List（UNL）は、RPCAを他の合意アルゴリズムと区別する根本的な構成要素である。Rippleネットワークの各ノードは、ネットワークを欺くために共謀しないと信頼する他のノードからなるUNLを維持する。重要なのは、この信頼がグローバルではなくローカルであるということである：異なるノードは異なるUNLを持つことができ、グローバルに合意された検証者セットは要求されない。この設計により、分散化を維持しながらネットワークが有機的に拡張できる。
UNLは、プルーフ・オブ・ワークなしにSybil攻撃防止メカニズムとして機能する。単純な投票システムでは、攻撃者は不均衡な影響力を得るために多数の偽名ノードを作成できる。各ノードが信頼する他のノードを明示的に選択することを要求することにより、RPCAは、それらのアイデンティティが既存のノードを説得してUNLに追加されない限り、追加のアイデンティティを作成しても何の利点も得られないことを保証する。これにより、Sybil耐性の問題は計算的支出から評判と信頼関係に移行する。
ネットワークが正しく機能するためには、形式的分析で説明したように、UNLが十分な重複を持つように選択されなければならない。実際には、各ノード運営者がUNL選択において自律性を持ちながらも、ネットワークの他の部分でも信頼されている検証者をリストに含めることを保証しなければならないことを意味する。Rippleは多様なエンティティが運営する検証者からなるデフォルトUNLを提供するが、ノード運営者は独自の信頼評価に基づいてこのリストを自由に変更できる。
UNLメカニズムはまた、段階的な分散化への自然な道筋を提供する。ネットワークの初期段階では、安定性と信頼性を確保するために、より集中化された検証者セットが適切かもしれない。ネットワークが成熟し、より多様な運営者がその信頼性を実証するにつれて、UNLはセキュリティ特性を損なうことなく、ネットワークの耐障害性と分散化を高めるより広範な検証者セットを含むように進化できる。
Simulation Code
Để kiểm chứng phân tích lý thuyết của RPCA và đánh giá hiệu năng dưới nhiều điều kiện, các mô phỏng quy mô lớn đã được thực hiện bằng phần mềm mô phỏng tùy biến. Khung mô phỏng mô hình hóa một mạng các nút, mỗi nút duy trì UNL riêng và tham gia giao thức đồng thuận. Mã nguồn triển khai đầy đủ thuật toán RPCA, bao gồm đề xuất giao dịch, các vòng bỏ phiếu với ngưỡng tăng dần và xác thực sổ cái.
Các tham số chính được thay đổi trong mô phỏng gồm kích thước mạng (từ 10 đến 1.000 nút), tỷ lệ nút Byzantine (từ 0% đến 20%), kích thước UNL (thường từ 5 đến 50 nút), và cấu hình topology mạng. Với mỗi cấu hình tham số, nhiều lần chạy mô phỏng được thực hiện với các random seed khác nhau để bảo đảm độ tin cậy thống kê của kết quả. Các mô phỏng theo dõi các chỉ số như độ trễ đồng thuận, xác suất phân nhánh, và thông lượng giao dịch.
Kết quả mô phỏng xác nhận các dự đoán lý thuyết về hội tụ và an toàn. Trong mọi cấu hình mà điều kiện chồng lấn UNL được thỏa và tỷ lệ Byzantine trong mỗi UNL dưới 20%, mạng đạt đồng thuận thành công mà không xảy ra phân nhánh. Độ trễ đồng thuận luôn thấp (thường hoàn tất trong 3-5 giây mô phỏng) bất kể kích thước mạng, cho thấy tính mở rộng của thuật toán. Ngay cả khi 15% nút Byzantine chủ động phá hoại đồng thuận, mạng vẫn giữ được tính đúng đắn miễn là điều kiện chồng lấn UNL được đáp ứng.
Các mô phỏng bổ sung cũng khảo sát các trường hợp biên và kịch bản lỗi, gồm phân vùng mạng, thay đổi đột ngột thành phần UNL, và tấn công phối hợp của các nút Byzantine. Các mô phỏng này cung cấp thêm hiểu biết về độ vững chắc của giao thức và định hình các thực hành tốt nhất được khuyến nghị cho lựa chọn UNL và vận hành mạng. Toàn bộ mã mô phỏng đã được công bố để cho phép kiểm chứng độc lập và nghiên cứu tiếp theo.
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
So với đồng thuận proof-of-work của Bitcoin, RPCA mang lại nhiều lợi thế đáng kể cho các ứng dụng hệ thống thanh toán. Nổi bật nhất là độ trễ đồng thuận giảm từ 40-60 phút (thời gian thường được khuyến nghị cho giao dịch Bitcoin giá trị cao) xuống khoảng 5 giây. Cải thiện này khiến RPCA phù hợp cho điểm bán hàng và các ứng dụng đòi hỏi quyết toán gần như tức thời. Ngoài ra, RPCA yêu cầu tài nguyên tính toán tối thiểu so với proof-of-work, loại bỏ mức tiêu thụ năng lượng khổng lồ gắn với hoạt động đào Bitcoin.
Tuy nhiên, các lợi thế này đi kèm giả định tin cậy khác. Trong khi bảo mật của Bitcoin chỉ dựa trên giả định không có kẻ tấn công nào kiểm soát quá 50% năng lực tính toán toàn mạng, RPCA yêu cầu các nút chọn UNL có độ chồng lấn đủ lớn và số nút Byzantine không vượt ngưỡng trong các UNL đó. Điều này chuyển một phần trách nhiệm sang nhà vận hành nút trong việc đưa ra quyết định tin cậy thận trọng. Trong thực tế, đánh đổi này chấp nhận được trong nhiều bối cảnh thanh toán nơi các tổ chức tham gia vốn đã có quan hệ tin cậy.
Topology mạng và chiến lược chọn UNL ảnh hưởng mạnh đến đặc tính của hệ đồng thuận. Topology tập trung cao, nơi mọi nút cùng dùng chung validator trong UNL, tối đa hóa an toàn nhưng có thể làm giảm tính sống nếu các validator đó không khả dụng. Ngược lại, topology phi tập trung cao với độ chồng lấn UNL thấp có thể cải thiện tính sống nhưng làm tăng rủi ro thất bại đồng thuận nếu chồng lấn trở nên quá thưa. Việc tìm điểm cân bằng tối ưu đòi hỏi cân nhắc kỹ kịch bản triển khai cụ thể và mức chấp nhận rủi ro.
Các hướng nghiên cứu tương lai có thể gồm thuật toán chọn UNL thích nghi tự động duy trì điều kiện chồng lấn trong khi tối đa hóa phi tập trung, cơ chế để nút điều chỉnh UNL động theo hành vi validator quan sát được, và mở rộng thuật toán đồng thuận để chịu được tỷ lệ nút Byzantine cao hơn nữa. Những cải tiến này có thể tiếp tục nâng cao độ vững chắc và phạm vi ứng dụng của RPCA cho các hệ thống thanh toán phân tán quy mô lớn.
Discussion
ビットコインのプルーフ・オブ・ワーク合意と比較して、RPCAは決済システムアプリケーションにいくつかの重要な利点を提供する。最も注目すべきは、合意遅延が40〜60分（高額ビットコイン取引に通常推奨される時間）から約5秒に短縮されることである。この改善により、RPCAはほぼ即時の決済が必要なPOS（販売時点）やその他のアプリケーションに適している。さらに、RPCAはプルーフ・オブ・ワークと比較して最小限の計算リソースしか必要とせず、ビットコインマイニングに伴う膨大なエネルギー消費を排除する。
しかし、これらの利点には異なる信頼仮定が伴う。ビットコインのセキュリティが、いかなる攻撃者もネットワークの計算能力の50%以上を制御しないという仮定のみに依存するのに対し、RPCAはノードが十分な重複を持つUNLを選択し、ByzantineノードがこれらのUNL内で閾値を超えないことを要求する。これにより、慎重な信頼決定を行う責任の一部がノード運営者に移る。実際には、参加機関が既存の信頼関係を持つ多くの決済システムユースケースにおいて、このトレードオフは許容可能である。
ネットワークトポロジーとUNL選択戦略は、合意システムの特性に大きく影響する。すべてのノードがUNLに同じ検証者を含む高度に集中化されたトポロジーは安全性を最大化するが、それらの検証者が利用不可になった場合、活性が低下する可能性がある。逆に、UNLの重複が最小限の高度に分散化されたトポロジーは活性を改善する可能性があるが、重複が疎になりすぎると合意障害のリスクがある。最適なバランスを見つけるには、特定のデプロイメントシナリオとリスク許容度の慎重な考慮が必要である。
将来の研究では、分散化を最大化しながら重複要件を自動的に維持する適応的UNL選択アルゴリズム、観察された検証者の行動に基づいてノードがUNLを動的に調整するメカニズム、そしてさらに高い割合のByzantineノードを許容できる合意アルゴリズムの拡張を探求できる可能性がある。これらの強化により、大規模分散型決済システムに対するRPCAの堅牢性と適用可能性がさらに向上する可能性がある。
Conclusion
Thuật toán Đồng thuận Giao thức Ripple là một bước tiến quan trọng của đồng thuận phân tán cho hệ thống thanh toán. Bằng cách sử dụng các mạng con được tin cậy tập thể thay vì yêu cầu đồng thuận toàn cục giữa mọi nút, RPCA đạt đồng thuận trong vài giây mà vẫn giữ bảo đảm mạnh trước lỗi Byzantine. Phân tích hình thức cho thấy rằng khi UNL được chọn với độ chồng lấn đủ lớn và tỷ lệ nút Byzantine nằm dưới ngưỡng, mạng sẽ đạt đồng thuận đúng mà không phân nhánh.
Ý nghĩa thực tiễn của công trình này vượt ra ngoài mạng thanh toán Ripple. RPCA cho thấy đánh đổi truyền thống giữa độ trễ đồng thuận và bảo đảm bảo mật có thể được vượt qua bằng thiết kế giao thức cẩn thận và việc khai thác quan hệ tin cậy cục bộ. Cách tiếp cận này có thể áp dụng cho các hệ phân tán khác nơi độ trễ thấp là yếu tố then chốt và các bên tham gia có quan hệ tin cậy sẵn có, như thanh toán liên ngân hàng, theo dõi chuỗi cung ứng, và các hạ tầng tài chính khác.
Việc triển khai RPCA trong môi trường sản xuất đã xác nhận đặc tính hiệu năng và độ vững chắc của thuật toán. Mạng Ripple xử lý hàng nghìn giao dịch mỗi giây với độ trễ đồng thuận ổn định 3-5 giây, chứng minh rằng các thuộc tính lý thuyết có thể chuyển hóa hiệu quả thành vận hành thực tế. Khi mạng tiếp tục phát triển và bổ sung thêm validator từ các nhà vận hành đa dạng, nó trở thành ví dụ thực tiễn về cách một hệ đồng thuận phi tập trung có thể duy trì đồng thời bảo mật và hiệu năng ở quy mô lớn.
Conclusion
Rippleプロトコル合意アルゴリズムは、決済システムのための分散型合意における重要な進歩を表している。すべてのノード間のグローバルな合意を要求する代わりに、集合的に信頼されたサブネットワークを活用することにより、RPCAはByzantine障害に対する強力な保証を維持しながら数秒で合意を達成する。形式的分析は、UNLが十分な重複で選択され、Byzantineノードが閾値以下に維持される限り、ネットワークがフォークなしに正しい合意に達することを実証している。
本研究の実用的な意味合いは、Ripple決済ネットワークを超えて広がる。RPCAは、合意遅延とセキュリティ保証の間の従来のトレードオフが、慎重なプロトコル設計とローカルな信頼関係の利用を通じて克服できることを示している。このアプローチは、低い遅延が重要であり参加者が既存の信頼関係を持つ他の分散システム、例えば銀行間決済システム、サプライチェーン追跡、その他の金融インフラアプリケーションに適用可能であると考えられる。
本番システムにおけるRPCAの展開は、アルゴリズムのパフォーマンス特性と堅牢性を検証した。Rippleネットワークは、一貫した3〜5秒の合意遅延で毎秒数千のトランザクションを処理しており、理論的特性が実世界の運用に効果的に反映されることを実証している。ネットワークが進化を続け、多様な運営者からの追加の検証者を組み込むにつれ、分散型合意システムがスケールにおいてセキュリティとパフォーマンスの両方を維持できる方法の実用的な事例を提供している。
References
Lamport, L., Shostak, R., và Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. Công trình nền tảng này đã hình thức hóa bài toán đạt đồng thuận trong hệ phân tán có thành phần lỗi và đặt nền móng lý thuyết cho các hệ chịu lỗi Byzantine.
Castro, M., và Liskov, B. (1999). "Practical Byzantine Fault Tolerance." Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI). Công trình này giới thiệu PBFT, cho thấy chịu lỗi Byzantine có thể đạt được với hiệu năng thực tiễn, dù độ phức tạp truyền thông O(n^2) giới hạn khả năng mở rộng.
Nakamoto, S. (2008). "Bitcoin: A Peer-to-Peer Electronic Cash System." Whitepaper này giới thiệu đồng thuận proof-of-work như lời giải cho bài toán chi tiêu kép trong tiền tệ số, cho phép đồng thuận phi tập trung không cần bên tin cậy nhưng đánh đổi bằng độ trễ cao và tiêu thụ năng lượng lớn.
Lamport, L. (1998). "The Part-Time Parliament." ACM Transactions on Computer Systems, 16(2):133-169. Bài báo này trình bày thuật toán Paxos, đạt đồng thuận trong hệ bất đồng bộ dưới lỗi sập và có ảnh hưởng lớn đến thiết kế các giao thức đồng thuận về sau.
Fischer, M. J., Lynch, N. A., và Paterson, M. S. (1985). "Impossibility of Distributed Consensus with One Faulty Process." Journal of the ACM, 32(2):374-382. Kết quả bất khả thi FLP thiết lập giới hạn cơ bản về những gì thuật toán đồng thuận có thể đạt trong hệ bất đồng bộ, qua đó định hình không gian thiết kế cho các giao thức đồng thuận thực tế.
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不可能性結果は、非同期システムにおいて合意アルゴリズムが達成できることの根本的な限界を確立し、実用的な合意プロトコルの設計空間を形成した。
