리플 프로토콜 합의 알고리즘
Abstract
Bien que plusieurs algorithmes de consensus existent pour le Probleme des Generaux Byzantins, en particulier en ce qui concerne les systemes de paiement distribues, beaucoup souffrent d'une latence elevee induite par l'exigence que tous les noeuds du reseau communiquent de maniere synchrone. Dans ce travail, nous presentons un nouvel algorithme de consensus qui contourne cette exigence en utilisant des sous-reseaux collectivement fiables au sein du reseau plus large. Nous montrons que la "confiance" requise pour prevenir les attaques Sybil n'est en fait pas globale, mais plutot locale a chaque noeud du reseau.
L'algorithme de consensus du protocole Ripple (RPCA) est applique toutes les quelques secondes par tous les noeuds, afin de maintenir la correction et l'accord du reseau. Une fois le consensus atteint, le ledger actuel est considere comme "ferme" et devient le dernier ledger ferme. Cet algorithme est unique en ce qu'il atteint le consensus avec une faible latence tout en maintenant de fortes garanties contre les defaillances byzantines, ce qui le rend adapte aux systemes de reglement financier en temps reel.
Abstract
Byzantine Generals Problem에 대한 여러 합의 알고리즘이 존재하지만, 특히 분산 결제 시스템과 관련하여 많은 알고리즘이 네트워크 내 모든 노드가 동기적으로 통신해야 하는 요구사항으로 인해 높은 지연 시간 문제를 겪고 있다. 본 연구에서는 더 큰 네트워크 내에서 집합적으로 신뢰할 수 있는 하위 네트워크를 활용하여 이 요구사항을 우회하는 새로운 합의 알고리즘을 제시한다. Sybil 공격을 방지하기 위해 필요한 "신뢰"가 실제로는 전역적인 것이 아니라 네트워크 내 각 노드에 대해 지역적임을 보여준다.
Ripple 프로토콜 합의 알고리즘(RPCA)은 네트워크의 정확성과 합의를 유지하기 위해 모든 노드에 의해 수 초마다 적용된다. 합의에 도달하면 현재 원장은 "폐쇄"된 것으로 간주되며 마지막으로 폐쇄된 원장(last-closed ledger)이 된다. 이 알고리즘은 Byzantine 장애에 대한 강력한 보장을 유지하면서 낮은 지연 시간으로 합의를 달성한다는 점에서 독특하며, 실시간 금융 결제 시스템에 적합하다.
Introduction
Un systeme de paiement distribue doit implementer un algorithme de consensus pour traiter correctement les paiements en temps opportun, meme en presence d'acteurs defaillants ou malveillants. Bitcoin atteint le consensus en utilisant la preuve de travail (proof-of-work), qui exige que tous les noeuds depensent des ressources de calcul pour resoudre des puzzles cryptographiques. Bien que cette approche fournisse de solides garanties de securite, elle souffre d'inconvenients importants, notamment une consommation energetique elevee, un faible debit de transactions et de longues latences de confirmation pouvant s'etendre a une heure ou plus pour les transactions de grande valeur.
L'algorithme de consensus du protocole Ripple propose une nouvelle approche du consensus distribue qui ne necessite pas de preuve de travail. Au lieu de cela, les noeuds du reseau s'accordent collectivement sur des ensembles de transactions par un processus de vote qui atteint le consensus en quelques secondes. Ce mecanisme de consensus est specifiquement concu pour les exigences d'un reseau de paiement mondial, ou une faible latence et un debit eleve sont essentiels pour un deploiement pratique.
L'innovation cle du RPCA est qu'il ne necessite pas que tous les noeuds du reseau s'accordent entre eux. Au lieu de cela, chaque noeud maintient une Liste de Noeuds Uniques (Unique Node List, UNL) d'autres noeuds en lesquels il a confiance pour ne pas s'entendre. Tant que les UNL choisies par les noeuds ont un chevauchement suffisant et que moins d'un pourcentage seuil de noeuds sont defaillants, le reseau atteindra le consensus. Cette approche fournit les garanties de securite necessaires a un systeme de paiement tout en atteignant une latence de consensus mesuree en secondes plutot qu'en minutes ou en heures.
Introduction
분산 결제 시스템은 결함이 있거나 악의적인 행위자가 존재하는 상황에서도 적시에 올바르게 결제를 처리하기 위해 합의 알고리즘을 구현해야 한다. 비트코인은 작업 증명(proof-of-work)을 사용하여 합의를 달성하며, 이는 모든 노드가 암호화 퍼즐을 풀기 위해 계산 자원을 소비하도록 요구한다. 이 접근 방식은 강력한 보안 보장을 제공하지만 높은 에너지 소비, 낮은 트랜잭션 처리량, 그리고 고가치 트랜잭션의 경우 1시간 이상까지 늘어날 수 있는 긴 확인 지연 시간을 포함한 상당한 단점이 있다.
Ripple 프로토콜 합의 알고리즘은 작업 증명을 필요로 하지 않는 분산 합의에 대한 새로운 접근 방식을 제공한다. 대신, 네트워크의 노드들은 수 초 내에 합의를 달성하는 투표 과정을 통해 트랜잭션 집합에 대해 집단적으로 동의한다. 이 합의 메커니즘은 실질적인 배포를 위해 낮은 지연 시간과 높은 처리량이 필수적인 글로벌 결제 네트워크의 요구사항에 맞춰 특별히 설계되었다.
RPCA의 핵심 혁신은 네트워크의 모든 노드가 서로 동의할 필요가 없다는 점이다. 대신, 각 노드는 공모하지 않을 것으로 신뢰하는 다른 노드들의 고유 노드 목록(Unique Node List, UNL)을 유지한다. 노드들이 선택한 UNL이 충분한 중첩을 가지고 있고, 임계값 비율 미만의 노드만 결함이 있다면 네트워크는 합의에 도달할 것이다. 이 접근 방식은 합의 지연 시간을 분이나 시간이 아닌 초 단위로 측정하면서 결제 시스템에 필요한 보안 보장을 제공한다.
Definition of Consensus
Dans les systemes distribues, le consensus designe le processus par lequel un reseau de noeuds parvient a un accord sur un etat partage, malgre la presence de participants defaillants ou malveillants. Un algorithme de consensus doit satisfaire trois proprietes fondamentales : la correction (deux noeuds corrects ne prennent pas de decisions differentes), l'accord (tous les noeuds corrects parviennent a la meme decision) et la terminaison (tous les noeuds corrects finissent par prendre une decision). Ces proprietes garantissent que le systeme distribue se comporte comme s'il s'agissait d'un noeud unique et fiable.
Le defi pour atteindre le consensus provient de la non-fiabilite inherente des systemes distribues. Les noeuds peuvent tomber en panne, les messages peuvent etre retardes ou perdus, et les noeuds byzantins peuvent se comporter de maniere arbitraire ou malveillante. Le Probleme des Generaux Byzantins, formalise par Lamport, Shostak et Pease, capture ce defi : comment un groupe de processus peut-il parvenir a un accord lorsqu'une fraction d'entre eux peut etre defaillante et que la communication n'est pas fiable ?
Les resultats classiques en informatique distribuee etablissent des limites fondamentales sur ce que les algorithmes de consensus peuvent realiser. Le resultat d'impossibilite FLP montre qu'aucun algorithme deterministe ne peut garantir le consensus dans un systeme asynchrone si meme un seul noeud peut echouer. Les algorithmes de consensus pratiques doivent donc faire des compromis entre la surete (ne jamais atteindre un consensus incorrect) et la vivacite (toujours progresser). La preuve de travail de Bitcoin privilegie la surete par rapport a la vivacite, tandis que le RPCA atteint un equilibre plus adapte aux systemes de paiement en completant les tours de consensus en temps borne tout en maintenant de fortes garanties de surete sous des hypotheses de pannes realistes.
Definition of Consensus
분산 시스템에서 합의란 결함이 있거나 악의적인 참가자가 존재하는 상황에서도 노드 네트워크가 공유 상태에 대한 동의에 도달하는 과정을 말한다. 합의 알고리즘은 세 가지 기본 속성을 만족해야 한다: 정확성(두 개의 올바른 노드가 서로 다르게 결정하지 않음), 동의(모든 올바른 노드가 동일한 결정에 도달함), 그리고 종료(모든 올바른 노드가 결국 결정을 내림). 이러한 속성은 분산 시스템이 단일의 신뢰할 수 있는 노드처럼 동작하도록 보장한다.
합의를 달성하는 데 있어서의 도전은 분산 시스템의 본질적인 불안정성에서 비롯된다. 노드가 충돌할 수 있고, 메시지가 지연되거나 손실될 수 있으며, Byzantine 노드는 임의적으로 또는 악의적으로 행동할 수 있다. Lamport, Shostak, Pease가 공식화한 Byzantine Generals Problem은 이 도전을 포착한다: 일부가 결함이 있을 수 있고 통신이 불안정한 상황에서 프로세스 그룹이 어떻게 합의에 도달할 수 있는가?
분산 컴퓨팅의 고전적 결과들은 합의 알고리즘이 달성할 수 있는 것의 근본적 한계를 확립한다. FLP 불가능성 결과는 단 하나의 노드만 실패할 수 있는 비동기 시스템에서도 어떤 결정론적 알고리즘도 합의를 보장할 수 없음을 보여준다. 따라서 실용적인 합의 알고리즘은 안전성(잘못된 합의에 절대 도달하지 않음)과 활성(항상 진행함) 사이에서 절충해야 한다. 비트코인의 작업 증명은 활성보다 안전성을 우선시하는 반면, RPCA는 현실적인 결함 가정 하에서 강력한 안전성 보장을 유지하면서 제한된 시간 내에 합의 라운드를 완료함으로써 결제 시스템에 더 적합한 균형을 달성한다.
Existing Consensus Algorithms
Plusieurs algorithmes de consensus ont ete proposes pour resoudre le Probleme des Generaux Byzantins dans les systemes distribues. L'algorithme Practical Byzantine Fault Tolerance (PBFT), introduit par Castro et Liskov, peut tolerer jusqu'a f fautes byzantines dans un systeme de 3f+1 noeuds. PBFT atteint le consensus par plusieurs tours d'echange de messages entre tous les noeuds, avec une complexite de communication de O(n^2), ou n est le nombre de noeuds. Bien que PBFT fournisse de solides garanties de surete et une latence relativement faible pour les petits reseaux, il ne s'adapte pas bien aux grands reseaux en raison de la surcharge de communication quadratique.
Paxos et ses variantes, developpes par Lamport, fournissent un consensus dans les systemes asynchrones mais supposent des defaillances par arret plutot que des fautes byzantines. Paxos atteint le consensus par une serie de tours au cours desquels les proposants suggerent des valeurs et les accepteurs votent. Bien que Paxos puisse tolerer des retards de messages arbitraires et des arrets de processus, il necessite une ingenierie soigneuse pour gerer les defaillances byzantines et peut souffrir de livelock dans certains scenarios.
L'algorithme de consensus proof-of-work de Bitcoin adopte une approche fondamentalement differente en rendant les attaques byzantines economiquement irrealisables. Les noeuds rivalisent pour resoudre des puzzles cryptographiques, le gagnant proposant le prochain bloc de transactions. Bien que cette approche s'adapte a des reseaux de taille arbitraire et gere les fautes byzantines, elle presente de serieux inconvenients : une consommation d'energie massive (estimee a plus de 150 millions de dollars par an pour le reseau Bitcoin), de longues latences de confirmation (souvent 40-60 minutes pour les transactions de grande valeur) et un debit limite (environ 7 transactions par seconde). Ces limitations rendent le proof-of-work inadapte a de nombreuses applications de systemes de paiement necessitant un reglement rapide et des volumes de transactions eleves.
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
L'algorithme de consensus du protocole Ripple (RPCA) commence par chaque serveur prenant toutes les transactions valides qu'il a vues et qui n'ont pas encore ete appliquees comme transactions candidates. Les serveurs suivent ensuite un protocole multi-tours ou ils travaillent iterativement vers un accord sur un ensemble de transactions a appliquer au ledger actuel. A chaque tour, les serveurs font des propositions consistant en les transactions qu'ils estiment devoir etre incluses dans le prochain ledger.
Pendant chaque tour de consensus, les serveurs communiquent leurs propositions aux autres serveurs de leur Unique Node List (UNL). Les serveurs calculent ensuite quelles transactions apparaissent dans un pourcentage seuil des propositions. Initialement, ce seuil est fixe a 50 %, ce qui signifie qu'une transaction doit apparaitre dans les propositions d'au moins la moitie de l'UNL d'un serveur pour etre consideree pour le tour suivant. Au fur et a mesure que le consensus progresse a travers les tours successifs, ce seuil augmente progressivement (typiquement a 60 %, 70 %, et finalement 80 %).
Lorsqu'une transaction atteint le seuil de supermajority de 80 % de soutien dans l'UNL d'un serveur, elle est incluse dans la proposition de ce serveur pour le tour de consensus final. Toutes les transactions qui atteignent ce seuil a travers le reseau sont appliquees au ledger, qui est ensuite hache cryptographiquement et signe. Ce ledger nouvellement valide devient le dernier ledger ferme, et le processus recommence avec le prochain ensemble de transactions candidates.
Le processus de consensus se termine generalement en 5 secondes ou moins, la plupart des transactions ne necessitant qu'un seul tour de consensus pour atteindre le seuil de supermajority. Les transactions qui n'atteignent pas le consensus en un tour restent candidates pour les tours suivants. Cette conception garantit que le reseau progresse continuellement tout en maintenant de fortes garanties de surete, car aucune transaction ne peut etre appliquee au ledger sans le soutien d'une supermajority de validateurs de confiance.
Ripple Protocol Consensus Algorithm
Ripple 프로토콜 합의 알고리즘(RPCA)은 각 서버가 아직 적용되지 않은 유효한 트랜잭션을 모두 후보 트랜잭션으로 수집하는 것으로 시작한다. 그런 다음 서버들은 현재 원장에 적용할 트랜잭션 집합에 대한 합의를 향해 반복적으로 작업하는 다중 라운드 프로토콜을 따른다. 각 라운드에서 서버들은 다음 원장에 포함되어야 한다고 생각하는 트랜잭션으로 구성된 제안을 만든다.
각 합의 라운드 동안 서버들은 자신의 고유 노드 목록(UNL)에 있는 다른 서버들에게 제안을 전달한다. 그런 다음 서버들은 어떤 트랜잭션이 임계값 비율 이상의 제안에 나타나는지 계산한다. 처음에 이 임계값은 50%로 설정되며, 이는 트랜잭션이 다음 라운드에서 고려되려면 서버 UNL의 최소 절반 이상의 제안에 나타나야 함을 의미한다. 합의가 연속적인 라운드를 거치면서 이 임계값은 점진적으로 증가한다(일반적으로 60%, 70%, 그리고 최종적으로 80%).
트랜잭션이 서버의 UNL에서 80%의 절대다수 지지 임계값을 달성하면, 해당 트랜잭션은 최종 합의 라운드에 대한 서버의 제안에 포함된다. 네트워크 전체에서 이 임계값에 도달한 모든 트랜잭션은 원장에 적용되고, 원장은 암호화 해시되고 서명된다. 이 새로 검증된 원장이 마지막으로 폐쇄된 원장이 되며, 다음 후보 트랜잭션 집합으로 프로세스가 다시 시작된다.
합의 과정은 일반적으로 5초 이내에 완료되며, 대부분의 트랜잭션은 절대다수 임계값을 달성하기 위해 단 한 번의 합의 라운드만 필요로 한다. 한 라운드에서 합의를 달성하지 못한 트랜잭션은 후속 라운드의 후보로 남는다. 이 설계는 신뢰할 수 있는 검증자들의 절대다수 지지 없이는 어떤 트랜잭션도 원장에 적용될 수 없으므로 강력한 안전성 보장을 유지하면서 네트워크가 지속적으로 진행되도록 보장한다.
Formal Analysis of Convergence
La correction du RPCA depend de maniere critique du chevauchement entre les UNL choisies par les differents noeuds du reseau. Soit UNL_i la liste de noeuds uniques du noeud i, et soit UNL_i ∩ UNL_j l'ensemble des noeuds qui apparaissent a la fois dans UNL_i et UNL_j. Pour que le reseau maintienne le consensus, nous exigeons que pour deux noeuds quelconques i et j, l'intersection de leurs UNL soit suffisamment grande par rapport a la taille maximale de l'une ou l'autre UNL.
Specifiquement, le protocole garantit la surete lorsque |UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5 pour toutes les paires de noeuds i et j. Cette condition garantit que meme si des noeuds byzantins tentent de faire en sorte que differentes parties du reseau atteignent des decisions de consensus differentes, le chevauchement des noeuds de confiance empeche une bifurcation (fork). Si cette condition est remplie et que moins de 1/5 des noeuds dans une UNL sont byzantins, alors tous les noeuds corrects atteindront la meme decision de consensus.
La preuve formelle procede en montrant que si deux noeuds pouvaient atteindre des decisions de consensus differentes, il devrait exister une transaction T qui apparait dans le ledger final d'un noeud mais pas dans celui de l'autre. Pour que cela se produise, T devrait avoir obtenu 80 % de soutien dans l'UNL du premier noeud mais moins de 80 % de soutien dans l'UNL du second noeud. Cependant, etant donne l'exigence de chevauchement et la contrainte sur les noeuds byzantins, on peut montrer que ce scenario est impossible : si T atteint 80 % de soutien dans UNL_i, elle doit atteindre au moins 60 % de soutien dans toute UNL_j qui satisfait la condition de chevauchement, et avec suffisamment de tours de consensus, cela convergera vers 80 % ou sera rejete par les deux noeuds.
La propriete de vivacite -- que le consensus sera finalement atteint -- decoule de l'observation que le seuil d'inclusion augmente de maniere deterministe a travers les tours de consensus. Meme en presence de noeuds byzantins et de retards reseau, le protocole garantit que les transactions soutenues par une supermajority de noeuds honnetes seront finalement incluses, tandis que les transactions manquant d'un tel soutien seront exclues. Le temps borne pour le consensus (typiquement 5 secondes) fournit des garanties pratiques de vivacite adaptees aux applications de systemes de paiement.
Formal Analysis of Convergence
RPCA의 정확성은 네트워크 내 서로 다른 노드들이 선택한 UNL 간의 중첩에 결정적으로 의존한다. UNL_i를 노드 i의 고유 노드 목록이라 하고, UNL_i ∩ UNL_j를 UNL_i와 UNL_j 양쪽에 나타나는 노드 집합이라 하자. 네트워크가 합의를 유지하기 위해서는 임의의 두 노드 i와 j에 대해, 그들의 UNL의 교집합이 어느 쪽 UNL의 최대 크기에 비해 충분히 커야 한다.
구체적으로, 프로토콜은 모든 노드 쌍 i와 j에 대해 |UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5일 때 안전성을 보장한다. 이 조건은 Byzantine 노드가 네트워크의 다른 부분들이 서로 다른 합의 결정에 도달하게 하려고 시도하더라도, 신뢰 노드의 중첩이 포크를 방지하도록 보장한다. 이 조건이 성립하고 어떤 UNL에서든 1/5 미만의 노드가 Byzantine이면, 모든 올바른 노드는 동일한 합의 결정에 도달할 것이다.
형식적 증명은 두 노드가 서로 다른 합의 결정에 도달할 수 있다면, 한 노드의 최종 원장에는 나타나지만 다른 노드에는 나타나지 않는 어떤 트랜잭션 T가 존재해야 함을 보여줌으로써 진행된다. 이것이 발생하려면, T가 첫 번째 노드의 UNL에서 80%의 지지를 달성했지만 두 번째 노드의 UNL에서는 80% 미만의 지지를 받아야 한다. 그러나 중첩 요구사항과 Byzantine 노드에 대한 제약을 고려하면, 이 시나리오가 불가능함을 보일 수 있다: T가 UNL_i에서 80%의 지지를 달성하면, 중첩 조건을 만족하는 어떤 UNL_j에서도 최소 60%의 지지를 달성해야 하며, 충분한 합의 라운드를 거치면 80%로 수렴하거나 양쪽 노드에 의해 거부될 것이다.
활성 속성 -- 합의가 결국 도달된다는 것 -- 은 포함을 위한 임계값이 합의 라운드를 통해 결정론적으로 증가한다는 관찰에서 따른다. Byzantine 노드와 네트워크 지연이 존재하더라도, 프로토콜은 정직한 노드의 절대다수가 지지하는 트랜잭션은 결국 포함되고, 그러한 지지가 부족한 트랜잭션은 제외되도록 보장한다. 합의에 대한 제한된 시간(일반적으로 5초)은 결제 시스템 응용에 적합한 실용적인 활성 보장을 제공한다.
Unique Node Lists
La Liste de Noeuds Uniques (Unique Node List, UNL) est un composant fondamental du RPCA qui le distingue des autres algorithmes de consensus. Chaque noeud du reseau Ripple maintient une UNL composee d'autres noeuds en lesquels il a confiance pour ne pas s'entendre afin de frauder le reseau. De maniere critique, cette confiance est locale plutot que globale : differents noeuds peuvent avoir differentes UNL, et il n'y a aucune exigence d'un ensemble de validateurs convenu globalement. Cette conception permet au reseau de se developper organiquement tout en maintenant la decentralisation.
L'UNL sert de mecanisme de prevention des attaques Sybil sans necessiter de preuve de travail. Dans un systeme de vote naif, un attaquant pourrait creer de nombreux noeuds pseudonymes pour obtenir une influence disproportionnee. En exigeant que chaque noeud choisisse explicitement les autres noeuds en lesquels il a confiance, le RPCA garantit que la creation d'identites supplementaires ne procure aucun avantage a moins que ces identites ne puissent convaincre les noeuds existants de les ajouter a leurs UNL. Cela deplace le probleme de la resistance Sybil de la depense de calcul vers les relations de reputation et de confiance.
Pour que le reseau fonctionne correctement, les UNL doivent etre choisies de maniere a avoir un chevauchement suffisant, comme decrit dans l'analyse formelle. En pratique, cela signifie que bien que chaque operateur de noeud ait une autonomie dans la selection de son UNL, il doit s'assurer que sa liste inclut des validateurs qui sont egalement approuves par d'autres parties du reseau. Ripple fournit une UNL par defaut composee de validateurs operes par des entites diverses, mais les operateurs de noeuds sont libres de modifier cette liste en fonction de leur propre evaluation de confiance.
Le mecanisme UNL fournit egalement une voie naturelle vers une decentralisation progressive. Dans les premieres etapes du reseau, un ensemble plus centralise de validateurs peut etre approprie pour assurer la stabilite et la fiabilite. A mesure que le reseau murit et que des operateurs plus divers demontrent leur fiabilite, les UNL peuvent evoluer pour inclure un ensemble plus large de validateurs, augmentant la resilience et la decentralisation du reseau sans compromettre ses proprietes de securite.
Unique Node Lists
고유 노드 목록(UNL)은 RPCA를 다른 합의 알고리즘과 구별하는 근본적인 구성 요소이다. Ripple 네트워크의 각 노드는 네트워크를 속이기 위해 공모하지 않을 것으로 신뢰하는 다른 노드들로 구성된 UNL을 유지한다. 중요한 점은 이 신뢰가 전역적이 아닌 지역적이라는 것이다: 서로 다른 노드가 서로 다른 UNL을 가질 수 있으며, 전역적으로 합의된 검증자 집합을 요구하지 않는다. 이 설계는 탈중앙화를 유지하면서 네트워크가 유기적으로 확장될 수 있게 한다.
UNL은 작업 증명 없이 Sybil 공격 방지 메커니즘 역할을 한다. 순진한 투표 시스템에서 공격자는 불균형적인 영향력을 얻기 위해 많은 가명 노드를 생성할 수 있다. 각 노드가 신뢰하는 다른 노드를 명시적으로 선택하도록 요구함으로써, RPCA는 해당 신원이 기존 노드를 설득하여 UNL에 추가될 수 없는 한, 추가 신원을 생성하는 것이 아무런 이점을 제공하지 않도록 보장한다. 이것은 Sybil 저항의 문제를 계산적 지출에서 평판과 신뢰 관계로 전환시킨다.
네트워크가 올바르게 기능하기 위해서는 형식적 분석에서 설명한 것처럼 UNL이 충분한 중첩을 갖도록 선택되어야 한다. 실제로 이것은 각 노드 운영자가 UNL 선택에 자율성을 가지면서도 네트워크의 다른 부분에서도 신뢰하는 검증자를 포함하도록 보장해야 함을 의미한다. Ripple은 다양한 주체가 운영하는 검증자로 구성된 기본 UNL을 제공하지만, 노드 운영자는 자체 신뢰 평가에 따라 이 목록을 자유롭게 수정할 수 있다.
UNL 메커니즘은 또한 점진적 탈중앙화를 향한 자연스러운 경로를 제공한다. 네트워크 초기 단계에서는 안정성과 신뢰성을 보장하기 위해 보다 중앙화된 검증자 집합이 적절할 수 있다. 네트워크가 성숙하고 더 다양한 운영자들이 신뢰성을 입증함에 따라, UNL은 보안 속성을 타협하지 않으면서 네트워크의 회복력과 탈중앙화를 높이는 더 넓은 검증자 집합을 포함하도록 진화할 수 있다.
Simulation Code
Pour valider l'analyse theorique du RPCA et evaluer ses performances dans diverses conditions, des simulations approfondies ont ete menees a l'aide d'un logiciel de simulation sur mesure. Le cadre de simulation modelise un reseau de noeuds, chacun maintenant sa propre UNL et participant au protocole de consensus. Le code implemente l'algorithme RPCA complet, incluant la proposition de transactions, les tours de vote avec des seuils croissants et la validation du ledger.
Les parametres cles varies dans les simulations comprennent la taille du reseau (allant de 10 a 1 000 noeuds), le pourcentage de noeuds byzantins (de 0 % a 20 %), la taille de l'UNL (typiquement entre 5 et 50 noeuds) et les configurations de topologie reseau. Pour chaque configuration de parametres, plusieurs executions de simulation ont ete menees avec differentes graines aleatoires afin d'assurer la validite statistique des resultats. Les simulations ont suivi des metriques incluant la latence du consensus, la probabilite de bifurcation (fork) et le debit de transactions.
Les resultats de simulation confirment les predictions theoriques concernant la convergence et la surete. Dans toutes les configurations ou la condition de chevauchement de l'UNL etait satisfaite et ou les noeuds byzantins representaient moins de 20 % de chaque UNL, le reseau a atteint le consensus avec succes sans bifurcation. La latence du consensus est restee constamment faible (se terminant typiquement en 3-5 secondes simulees) independamment de la taille du reseau, demontrant la scalabilite de l'algorithme. Meme avec 15 % de noeuds byzantins tentant activement de perturber le consensus, le reseau a maintenu la correction tant que l'exigence de chevauchement de l'UNL etait respectee.
Des simulations supplementaires ont explore des cas limites et des scenarios de defaillance, incluant des partitions reseau, des changements soudains dans la composition de l'UNL et des attaques coordonnees par des noeuds byzantins. Ces simulations ont fourni des informations sur la robustesse du protocole et ont eclaire les meilleures pratiques recommandees pour la selection de l'UNL et l'exploitation du reseau. Le code de simulation complet a ete mis a disposition pour permettre la verification independante et la recherche approfondie.
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
Compare au consensus proof-of-work de Bitcoin, le RPCA offre plusieurs avantages significatifs pour les applications de systemes de paiement. Plus remarquablement, la latence du consensus est reduite de 40-60 minutes (le temps typiquement recommande pour les transactions Bitcoin de grande valeur) a environ 5 secondes. Cette amelioration rend le RPCA adapte aux points de vente et autres applications ou un reglement quasi instantane est requis. De plus, le RPCA necessite des ressources de calcul minimales par rapport au proof-of-work, eliminant la consommation massive d'energie associee au minage de Bitcoin.
Cependant, ces avantages s'accompagnent d'hypotheses de confiance differentes. Alors que la securite de Bitcoin repose uniquement sur l'hypothese qu'aucun attaquant ne controle plus de 50 % de la puissance de calcul du reseau, le RPCA exige que les noeuds choisissent des UNL avec un chevauchement suffisant et que les noeuds byzantins ne depassent pas le seuil au sein de ces UNL. Cela transfere une certaine responsabilite aux operateurs de noeuds pour prendre des decisions de confiance prudentes. En pratique, ce compromis est acceptable pour de nombreux cas d'utilisation de systemes de paiement ou les institutions participantes ont des relations de confiance existantes.
La topologie du reseau et la strategie de selection de l'UNL ont un impact significatif sur les proprietes du systeme de consensus. Une topologie hautement centralisee ou tous les noeuds incluent les memes validateurs dans leurs UNL maximise la surete mais peut reduire la vivacite si ces validateurs deviennent indisponibles. Inversement, une topologie hautement decentralisee avec un chevauchement minimal de l'UNL peut ameliorer la vivacite mais risque des echecs de consensus si le chevauchement devient trop faible. Trouver l'equilibre optimal necessite une consideration attentive du scenario de deploiement specifique et de la tolerance au risque.
Les travaux futurs pourraient explorer des algorithmes de selection UNL adaptatifs qui maintiennent automatiquement les exigences de chevauchement tout en maximisant la decentralisation, des mecanismes permettant aux noeuds d'ajuster dynamiquement leurs UNL en fonction du comportement observe des validateurs, et des extensions de l'algorithme de consensus qui pourraient tolerer des pourcentages encore plus eleves de noeuds byzantins. Ces ameliorations pourraient renforcer davantage la robustesse et l'applicabilite du RPCA pour les systemes de paiement distribues a grande echelle.
Discussion
비트코인의 작업 증명 합의와 비교하여, RPCA는 결제 시스템 응용에 여러 가지 중요한 이점을 제공한다. 가장 주목할 만한 것은 합의 지연 시간이 40-60분(고가치 비트코인 트랜잭션에 일반적으로 권장되는 시간)에서 약 5초로 단축된다는 점이다. 이 개선으로 RPCA는 즉각적인 결제가 필요한 판매 시점(POS) 및 기타 응용에 적합해진다. 또한 RPCA는 작업 증명에 비해 최소한의 계산 자원을 필요로 하여, 비트코인 채굴과 관련된 막대한 에너지 소비를 제거한다.
그러나 이러한 장점에는 다른 신뢰 가정이 수반된다. 비트코인의 보안이 어떤 공격자도 네트워크 계산 능력의 50% 이상을 통제하지 못한다는 가정에만 의존하는 반면, RPCA는 노드들이 충분한 중첩을 가진 UNL을 선택하고 Byzantine 노드가 이 UNL 내에서 임계값을 초과하지 않을 것을 요구한다. 이것은 노드 운영자에게 신중한 신뢰 결정을 내릴 일부 책임을 전가한다. 실제로 이 절충은 참여 기관이 기존의 신뢰 관계를 가진 많은 결제 시스템 사용 사례에서 수용 가능하다.
네트워크 토폴로지와 UNL 선택 전략은 합의 시스템의 속성에 상당한 영향을 미친다. 모든 노드가 UNL에 동일한 검증자를 포함하는 고도로 중앙화된 토폴로지는 안전성을 최대화하지만, 해당 검증자가 사용 불가능해지면 활성이 감소할 수 있다. 반대로, 최소한의 UNL 중첩을 가진 고도로 탈중앙화된 토폴로지는 활성을 개선할 수 있지만, 중첩이 너무 희박해지면 합의 실패의 위험이 있다. 최적의 균형을 찾으려면 특정 배포 시나리오와 위험 허용 범위를 신중하게 고려해야 한다.
향후 연구는 탈중앙화를 최대화하면서 중첩 요구사항을 자동으로 유지하는 적응적 UNL 선택 알고리즘, 관찰된 검증자 행동에 기반하여 노드가 동적으로 UNL을 조정하는 메커니즘, 그리고 더 높은 비율의 Byzantine 노드를 허용할 수 있는 합의 알고리즘의 확장을 탐구할 수 있다. 이러한 개선은 대규모 분산 결제 시스템에 대한 RPCA의 견고성과 적용 가능성을 더욱 향상시킬 수 있다.
Conclusion
L'algorithme de consensus du protocole Ripple represente une avancee significative dans le consensus distribue pour les systemes de paiement. En utilisant des sous-reseaux collectivement fiables plutot que d'exiger un accord global entre tous les noeuds, le RPCA atteint le consensus en quelques secondes tout en maintenant de fortes garanties contre les defaillances byzantines. L'analyse formelle demontre que tant que les UNL sont choisies avec un chevauchement suffisant et que les noeuds byzantins restent en dessous du seuil, le reseau atteindra un consensus correct sans bifurcation.
Les implications pratiques de ce travail s'etendent au-dela du reseau de paiement Ripple. Le RPCA demontre que le compromis traditionnel entre latence du consensus et garanties de securite peut etre surmonte par une conception de protocole soignee et l'utilisation de relations de confiance locales. Cette approche peut s'averer applicable a d'autres systemes distribues ou une faible latence est critique et ou les participants ont des relations de confiance existantes, tels que les systemes de reglement interbancaires, le suivi de la chaine d'approvisionnement et d'autres applications d'infrastructure financiere.
Le deploiement du RPCA dans les systemes de production a valide les caracteristiques de performance et la robustesse de l'algorithme. Le reseau Ripple traite des milliers de transactions par seconde avec une latence de consensus constante de 3-5 secondes, demontrant que les proprietes theoriques se traduisent efficacement en fonctionnement reel. A mesure que le reseau continue d'evoluer et d'incorporer des validateurs supplementaires d'operateurs divers, il fournit un exemple pratique de la facon dont un systeme de consensus decentralise peut maintenir a la fois la securite et la performance a grande echelle.
Conclusion
Ripple 프로토콜 합의 알고리즘은 결제 시스템을 위한 분산 합의에서 중요한 발전을 나타낸다. 모든 노드 간의 전역적 합의를 요구하는 대신 집합적으로 신뢰할 수 있는 하위 네트워크를 활용함으로써, RPCA는 Byzantine 장애에 대한 강력한 보장을 유지하면서 수 초 만에 합의를 달성한다. 형식적 분석은 UNL이 충분한 중첩으로 선택되고 Byzantine 노드가 임계값 이하로 유지되는 한, 네트워크가 포크 없이 올바른 합의에 도달할 것임을 입증한다.
이 연구의 실질적인 시사점은 Ripple 결제 네트워크를 넘어 확장된다. RPCA는 합의 지연 시간과 보안 보장 사이의 전통적인 절충이 신중한 프로토콜 설계와 지역적 신뢰 관계의 사용을 통해 극복될 수 있음을 보여준다. 이 접근 방식은 낮은 지연 시간이 중요하고 참가자들이 기존의 신뢰 관계를 가진 다른 분산 시스템, 예를 들어 은행 간 결제 시스템, 공급망 추적, 기타 금융 인프라 응용에 적용 가능할 수 있다.
프로덕션 시스템에서 RPCA의 배포는 알고리즘의 성능 특성과 견고성을 검증하였다. Ripple 네트워크는 일관된 3-5초의 합의 지연 시간으로 초당 수천 건의 트랜잭션을 처리하며, 이론적 속성이 실제 운영에 효과적으로 번역됨을 입증한다. 네트워크가 계속 발전하고 다양한 운영자의 추가 검증자를 통합함에 따라, 탈중앙화된 합의 시스템이 대규모에서 보안과 성능을 모두 유지할 수 있는 방법의 실용적인 사례를 제공한다.
References
Lamport, L., Shostak, R., et Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. Cet article fondateur a formalise le probleme d'atteindre le consensus dans les systemes distribues avec des composants defaillants et a etabli les fondements theoriques des systemes tolerants aux fautes byzantines.
Castro, M., et Liskov, B. (1999). "Practical Byzantine Fault Tolerance." Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI). Ce travail a introduit PBFT, demontrant que la tolerance aux fautes byzantines pouvait etre atteinte avec des performances pratiques, bien qu'avec une complexite de communication O(n^2) limitant la scalabilite.
Nakamoto, S. (2008). "Bitcoin: A Peer-to-Peer Electronic Cash System." Ce livre blanc a introduit le consensus par preuve de travail comme solution au probleme de la double depense dans la monnaie numerique, permettant un consensus decentralise sans parties de confiance au prix d'une latence elevee et d'une consommation energetique importante.
Lamport, L. (1998). "The Part-Time Parliament." ACM Transactions on Computer Systems, 16(2):133-169. Cet article a presente l'algorithme Paxos, qui atteint le consensus dans les systemes asynchrones sous des defaillances par arret, influencant les conceptions de protocoles de consensus ulterieures.
Fischer, M. J., Lynch, N. A., et Paterson, M. S. (1985). "Impossibility of Distributed Consensus with One Faulty Process." Journal of the ACM, 32(2):374-382. Le resultat d'impossibilite FLP a etabli des limites fondamentales sur ce que les algorithmes de consensus peuvent realiser dans les systemes asynchrones, faconnant l'espace de conception des protocoles de consensus pratiques.
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 불가능성 결과는 비동기 시스템에서 합의 알고리즘이 달성할 수 있는 것의 근본적 한계를 확립하여, 실용적인 합의 프로토콜의 설계 공간을 형성하였다.
