O Algoritmo de Consenso do Protocolo Ripple
Abstract
Obwohl mehrere Konsensalgorithmen fur das Problem der Byzantinischen Generale existieren, insbesondere in Bezug auf verteilte Zahlungssysteme, leiden viele unter hoher Latenz, die durch die Anforderung verursacht wird, dass alle Knoten im Netzwerk synchron kommunizieren mussen. In dieser Arbeit prasentieren wir einen neuartigen Konsensalgorithmus, der diese Anforderung umgeht, indem er kollektiv vertrauenswurdige Subnetzwerke innerhalb des grosseren Netzwerks nutzt. Wir zeigen, dass das "Vertrauen", das zur Verhinderung von Sybil-Angriffen erforderlich ist, tatsachlich nicht global ist, sondern lokal fur jeden Knoten im Netzwerk.
Der Konsensalgorithmus des Ripple-Protokolls (RPCA) wird alle paar Sekunden von allen Knoten angewendet, um die Korrektheit und Ubereinstimmung des Netzwerks aufrechtzuerhalten. Sobald ein Konsens erreicht ist, gilt das aktuelle Ledger als "geschlossen" und wird zum letzten geschlossenen Ledger. Dieser Algorithmus ist einzigartig, da er Konsens mit niedriger Latenz erreicht und gleichzeitig starke Garantien gegen byzantinische Ausfalle bietet, was ihn fur Echtzeit-Finanzabrechnungssysteme geeignet macht.
Abstract
Embora existam vários algoritmos de consenso para o Byzantine Generals Problem, especificamente no que diz respeito a sistemas de pagamento distribuídos, muitos sofrem de alta latência induzida pelo requisito de que todos os nós dentro da rede se comuniquem de forma síncrona. Neste trabalho, apresentamos um algoritmo de consenso inovador que contorna esse requisito ao utilizar sub-redes coletivamente confiáveis dentro da rede maior. Mostramos que a "confiança" necessária para prevenir ataques Sybil não é, de fato, global, mas sim local a cada nó na rede.
O algoritmo de consenso do protocolo Ripple (RPCA) é aplicado a cada poucos segundos por todos os nós, a fim de manter a correção e o acordo da rede. Uma vez alcançado o consenso, o livro-razão atual é considerado "fechado" e se torna o último livro-razão fechado (last-closed ledger). Este algoritmo é único no sentido de que alcança consenso com baixa latência enquanto mantém fortes garantias contra falhas Byzantine, tornando-o adequado para sistemas de liquidação financeira em tempo real.
Introduction
Ein verteiltes Zahlungssystem muss einen Konsensalgorithmus implementieren, um Zahlungen korrekt und zeitnah zu verarbeiten, selbst bei Vorhandensein fehlerhafter oder boswilliger Akteure. Bitcoin erreicht Konsens durch Proof-of-Work, bei dem alle Knoten Rechenressourcen aufwenden mussen, um kryptografische Ratsel zu losen. Obwohl dieser Ansatz starke Sicherheitsgarantien bietet, leidet er unter erheblichen Nachteilen, darunter hoher Energieverbrauch, geringer Transaktionsdurchsatz und lange Bestatigungs-Latenzen, die bei hochwertigen Transaktionen eine Stunde oder mehr betragen konnen.
Der Konsensalgorithmus des Ripple-Protokolls bietet einen neuen Ansatz fur verteilten Konsens, der kein Proof-of-Work erfordert. Stattdessen einigen sich die Knoten im Netzwerk durch einen Abstimmungsprozess kollektiv auf Transaktionssatze, der Konsens innerhalb von Sekunden erreicht. Dieser Konsensmechanismus ist speziell fur die Anforderungen eines globalen Zahlungsnetzwerks konzipiert, bei dem niedrige Latenz und hoher Durchsatz fur den praktischen Einsatz unerlasslich sind.
Die wichtigste Innovation des RPCA besteht darin, dass nicht alle Knoten im Netzwerk miteinander ubereinstimmen mussen. Stattdessen pflegt jeder Knoten eine Unique Node List (UNL) anderer Knoten, denen er vertraut, nicht zu kolludieren. Solange die von den Knoten gewahlten UNLs ausreichende Uberlappung aufweisen und weniger als ein Schwellenwertprozentsatz der Knoten fehlerhaft ist, wird das Netzwerk Konsens erreichen. Dieser Ansatz bietet die fur ein Zahlungssystem erforderlichen Sicherheitsgarantien bei einer Konsenslatenz, die in Sekunden statt in Minuten oder Stunden gemessen wird.
Introduction
Um sistema de pagamento distribuído deve implementar um algoritmo de consenso para processar pagamentos corretamente e de maneira oportuna, mesmo na presença de atores defeituosos ou maliciosos. O Bitcoin alcança consenso usando prova de trabalho (proof-of-work), que exige que todos os nós gastem recursos computacionais resolvendo quebra-cabeças criptográficos. Embora essa abordagem forneça fortes garantias de segurança, ela sofre de desvantagens significativas, incluindo alto consumo de energia, baixa taxa de transferência de transações e longas latências de confirmação que podem se estender a uma hora ou mais para transações de alto valor.
O algoritmo de consenso do protocolo Ripple fornece uma nova abordagem para o consenso distribuído que não requer prova de trabalho. Em vez disso, os nós na rede concordam coletivamente sobre conjuntos de transações através de um processo de votação que alcança consenso em questão de segundos. Este mecanismo de consenso é projetado especificamente para os requisitos de uma rede de pagamentos global, onde baixa latência e alta taxa de transferência são essenciais para a implantação prática.
A inovação-chave no RPCA é que ele não exige que todos os nós na rede concordem entre si. Em vez disso, cada nó mantém uma Lista de Nós Únicos (Unique Node List, UNL) de outros nós em que confia para não conspirar. Desde que as UNLs escolhidas pelos nós tenham sobreposição suficiente e menos de uma porcentagem limite de nós sejam defeituosos, a rede alcançará consenso. Esta abordagem fornece as garantias de segurança necessárias para um sistema de pagamento enquanto alcança latência de consenso medida em segundos em vez de minutos ou horas.
Definition of Consensus
In verteilten Systemen bezieht sich Konsens auf den Prozess, durch den ein Netzwerk von Knoten trotz fehlerhafter oder boswilliger Teilnehmer eine Einigung uber einen gemeinsamen Zustand erzielt. Ein Konsensalgorithmus muss drei grundlegende Eigenschaften erfullen: Korrektheit (keine zwei korrekten Knoten entscheiden unterschiedlich), Ubereinstimmung (alle korrekten Knoten treffen die gleiche Entscheidung) und Terminierung (alle korrekten Knoten entscheiden sich schliesslich). Diese Eigenschaften stellen sicher, dass sich das verteilte System verhalt, als ware es ein einzelner, zuverlassiger Knoten.
Die Herausforderung bei der Erreichung von Konsens ergibt sich aus der inharenten Unzuverlassigkeit verteilter Systeme. Knoten konnen absturzen, Nachrichten konnen verzogert werden oder verloren gehen, und byzantinische Knoten konnen sich beliebig oder boswillig verhalten. Das Problem der Byzantinischen Generale, formalisiert von Lamport, Shostak und Pease, erfasst diese Herausforderung: Wie kann eine Gruppe von Prozessen eine Einigung erzielen, wenn ein Teil fehlerhaft sein kann und die Kommunikation unzuverlassig ist?
Klassische Ergebnisse der verteilten Informatik legen fundamentale Grenzen fest, was Konsensalgorithmen erreichen konnen. Das FLP-Unmoglichkeitsergebnis zeigt, dass kein deterministischer Algorithmus Konsens in einem asynchronen System garantieren kann, wenn auch nur ein einziger Knoten ausfallen kann. Praktische Konsensalgorithmen mussen daher Kompromisse zwischen Sicherheit (niemals einen falschen Konsens erreichen) und Lebendigkeit (immer Fortschritte machen) eingehen. Bitcoins Proof-of-Work priorisiert Sicherheit uber Lebendigkeit, wahrend RPCA ein fur Zahlungssysteme besser geeignetes Gleichgewicht erreicht, indem es Konsensrunden in begrenzter Zeit abschliesst und gleichzeitig starke Sicherheitsgarantien unter realistischen Fehlerannahmen aufrechterhalt.
Definition of Consensus
Em sistemas distribuídos, consenso refere-se ao processo pelo qual uma rede de nós chega a um acordo sobre um estado compartilhado, apesar da presença de participantes defeituosos ou maliciosos. Um algoritmo de consenso deve satisfazer três propriedades fundamentais: correção (nenhum par de nós corretos decide de forma diferente), acordo (todos os nós corretos alcançam a mesma decisão) e terminação (todos os nós corretos eventualmente decidem). Essas propriedades garantem que o sistema distribuído se comporte como se fosse um nó único e confiável.
O desafio em alcançar o consenso decorre da inerente falta de confiabilidade dos sistemas distribuídos. Os nós podem falhar, as mensagens podem ser atrasadas ou perdidas, e os nós Byzantine podem se comportar de forma arbitrária ou maliciosa. O Byzantine Generals Problem, formalizado por Lamport, Shostak e Pease, captura esse desafio: como um grupo de processos pode chegar a um acordo quando alguma fração pode ser defeituosa e quando a comunicação não é confiável?
Os resultados clássicos em computação distribuída estabelecem limites fundamentais sobre o que os algoritmos de consenso podem alcançar. O resultado de impossibilidade FLP mostra que nenhum algoritmo determinístico pode garantir o consenso em um sistema assíncrono se mesmo um único nó puder falhar. Os algoritmos de consenso práticos devem, portanto, fazer compensações entre segurança (nunca alcançar um consenso incorreto) e vivacidade (sempre progredir). A prova de trabalho do Bitcoin prioriza a segurança sobre a vivacidade, enquanto o RPCA alcança um equilíbrio mais adequado para sistemas de pagamento ao completar rodadas de consenso em tempo limitado enquanto mantém fortes garantias de segurança sob suposições realistas de falha.
Existing Consensus Algorithms
Mehrere Konsensalgorithmen wurden vorgeschlagen, um das Problem der Byzantinischen Generale in verteilten Systemen zu losen. Der Practical Byzantine Fault Tolerance (PBFT) Algorithmus, eingefuhrt von Castro und Liskov, kann bis zu f byzantinische Fehler in einem System von 3f+1 Knoten tolerieren. PBFT erreicht Konsens durch mehrere Runden des Nachrichtenaustauschs zwischen allen Knoten mit einer Kommunikationskomplexitat von O(n^2), wobei n die Anzahl der Knoten ist. Wahrend PBFT starke Sicherheitsgarantien und relativ niedrige Latenz fur kleine Netzwerke bietet, skaliert er aufgrund des quadratischen Kommunikationsaufwands nicht gut fur grosse Netzwerke.
Paxos und seine Varianten, entwickelt von Lamport, ermoglichen Konsens in asynchronen Systemen, setzen jedoch Absturzfehler statt byzantinischer Fehler voraus. Paxos erreicht Konsens durch eine Reihe von Runden, in denen Vorschlagende Werte vorschlagen und Akzeptoren daruber abstimmen. Wahrend Paxos beliebige Nachrichtenverzogerungen und Prozessabsturze tolerieren kann, erfordert es sorgfaltige Entwicklung fur den Umgang mit byzantinischen Fehlern und kann in bestimmten Szenarien unter Livelock leiden.
Bitcoins Proof-of-Work-Konsensalgorithmus verfolgt einen grundlegend anderen Ansatz, indem er byzantinische Angriffe wirtschaftlich undurchfuhrbar macht. Knoten konkurrieren darum, kryptografische Ratsel zu losen, wobei der Gewinner den nachsten Transaktionsblock vorschlagt. Wahrend dieser Ansatz auf beliebige Netzwerkgrossen skaliert und byzantinische Fehler behandelt, hat er schwerwiegende Nachteile: massiver Energieverbrauch (geschatzt auf uber 150 Millionen Dollar pro Jahr fur das Bitcoin-Netzwerk), lange Bestatigungs-Latenzen (oft 40-60 Minuten fur hochwertige Transaktionen) und begrenzter Durchsatz (ungefahr 7 Transaktionen pro Sekunde). Diese Einschrankungen machen Proof-of-Work fur viele Zahlungssystemanwendungen ungeeignet, die eine schnelle Abwicklung und hohe Transaktionsvolumen erfordern.
Existing Consensus Algorithms
Vários algoritmos de consenso foram propostos para resolver o Byzantine Generals Problem em sistemas distribuídos. O algoritmo de Practical Byzantine Fault Tolerance (PBFT), introduzido por Castro e Liskov, pode tolerar até f falhas Byzantine em um sistema de 3f+1 nós. O PBFT alcança consenso através de múltiplas rodadas de troca de mensagens entre todos os nós, com complexidade de comunicação de O(n^2), onde n é o número de nós. Embora o PBFT forneça fortes garantias de segurança e latência relativamente baixa para redes pequenas, ele não escala bem para redes grandes devido à sobrecarga de comunicação quadrática.
O Paxos e suas variantes, desenvolvidos por Lamport, fornecem consenso em sistemas assíncronos, mas assumem falhas por crash em vez de falhas Byzantine. O Paxos alcança consenso através de uma série de rodadas nas quais proponentes sugerem valores e aceitadores votam neles. Embora o Paxos possa tolerar atrasos arbitrários de mensagens e falhas de processos, ele requer engenharia cuidadosa para lidar com falhas Byzantine e pode sofrer de livelock em certos cenários.
O algoritmo de consenso por prova de trabalho do Bitcoin adota uma abordagem fundamentalmente diferente ao tornar os ataques Byzantine economicamente inviáveis. Os nós competem para resolver quebra-cabeças criptográficos, e o vencedor propõe o próximo bloco de transações. Embora essa abordagem escale para tamanhos de rede arbitrários e lide com falhas Byzantine, ela tem graves desvantagens: consumo massivo de energia (estimado em mais de 150 milhões de dólares por ano para a rede Bitcoin), longas latências de confirmação (frequentemente 40-60 minutos para transações de alto valor) e taxa de transferência limitada (aproximadamente 7 transações por segundo). Essas limitações tornam a prova de trabalho inadequada para muitas aplicações de sistemas de pagamento que exigem liquidação rápida e altos volumes de transações.
Ripple Protocol Consensus Algorithm
Der Konsensalgorithmus des Ripple-Protokolls (RPCA) beginnt damit, dass jeder Server alle gultigen Transaktionen, die er gesehen hat und die noch nicht angewendet wurden, als Kandidatentransaktionen nimmt. Die Server folgen dann einem Mehrrundenprotokoll, in dem sie iterativ auf eine Einigung uber einen Satz von Transaktionen hinarbeiten, die auf das aktuelle Ledger angewendet werden sollen. In jeder Runde machen die Server Vorschlage, die aus den Transaktionen bestehen, von denen sie glauben, dass sie in das nachste Ledger aufgenommen werden sollten.
Wahrend jeder Konsensrunde kommunizieren die Server ihre Vorschlage an andere Server in ihrer Unique Node List (UNL). Die Server berechnen dann, welche Transaktionen in einem Schwellenwertprozentsatz der Vorschlage erscheinen. Anfanglich wird dieser Schwellenwert auf 50 % gesetzt, was bedeutet, dass eine Transaktion in Vorschlagen von mindestens der Halfte der UNL eines Servers erscheinen muss, um fur die nachste Runde berucksichtigt zu werden. Wahrend der Konsens durch aufeinanderfolgende Runden fortschreitet, erhoht sich dieser Schwellenwert schrittweise (typischerweise auf 60 %, 70 % und schliesslich 80 %).
Wenn eine Transaktion den Supermajority-Schwellenwert von 80 % Unterstutzung in der UNL eines Servers erreicht, wird sie in den Vorschlag dieses Servers fur die finale Konsensrunde aufgenommen. Alle Transaktionen, die diesen Schwellenwert im gesamten Netzwerk erreichen, werden auf das Ledger angewendet, das dann kryptografisch gehasht und signiert wird. Dieses neu validierte Ledger wird zum letzten geschlossenen Ledger, und der Prozess beginnt mit dem nachsten Satz von Kandidatentransaktionen von vorne.
Der Konsensprozess wird typischerweise in 5 Sekunden oder weniger abgeschlossen, wobei die meisten Transaktionen nur eine einzige Konsensrunde benotigen, um den Supermajority-Schwellenwert zu erreichen. Transaktionen, die in einer Runde keinen Konsens erreichen, bleiben Kandidaten fur nachfolgende Runden. Dieses Design stellt sicher, dass das Netzwerk kontinuierlich Fortschritte macht und gleichzeitig starke Sicherheitsgarantien aufrechterhalt, da keine Transaktion auf das Ledger angewendet werden kann, ohne die Unterstutzung einer Supermajority vertrauenswurdiger Validatoren.
Ripple Protocol Consensus Algorithm
O Algoritmo de Consenso do Protocolo Ripple (RPCA) começa com cada servidor coletando todas as transações válidas que viu e que ainda não foram aplicadas como transações candidatas. Os servidores então seguem um protocolo de múltiplas rodadas onde trabalham iterativamente em direção a um acordo sobre um conjunto de transações para aplicar ao livro-razão atual. Em cada rodada, os servidores fazem propostas consistindo nas transações que acreditam que devem ser incluídas no próximo livro-razão.
Durante cada rodada de consenso, os servidores comunicam suas propostas a outros servidores em sua Lista de Nós Únicos (UNL). Os servidores então calculam quais transações aparecem em uma porcentagem limite de propostas. Inicialmente, esse limite é definido em 50%, significando que uma transação deve aparecer em propostas de pelo menos metade da UNL de um servidor para ser considerada na próxima rodada. À medida que o consenso progride através de rodadas sucessivas, esse limite aumenta incrementalmente (tipicamente para 60%, 70% e finalmente 80%).
Quando uma transação alcança o limite de supermaioria de 80% de apoio na UNL de um servidor, ela é incluída na proposta desse servidor para a rodada final de consenso. Todas as transações que alcançam esse limite em toda a rede são aplicadas ao livro-razão, que é então criptograficamente hashado e assinado. Este livro-razão recém-validado se torna o último livro-razão fechado, e o processo recomeça com o próximo conjunto de transações candidatas.
O processo de consenso tipicamente se completa em 5 segundos ou menos, com a maioria das transações exigindo apenas uma rodada de consenso para alcançar o limite de supermaioria. As transações que não alcançam consenso em uma rodada permanecem como candidatas para rodadas subsequentes. Este design garante que a rede progrida continuamente enquanto mantém fortes garantias de segurança, já que nenhuma transação pode ser aplicada ao livro-razão sem o apoio de supermaioria dos validadores confiáveis.
Formal Analysis of Convergence
Die Korrektheit von RPCA hangt entscheidend von der Uberlappung zwischen den UNLs ab, die von verschiedenen Knoten im Netzwerk gewahlt werden. Sei UNL_i die Unique Node List des Knotens i, und sei UNL_i ∩ UNL_j die Menge der Knoten, die sowohl in UNL_i als auch in UNL_j erscheinen. Damit das Netzwerk den Konsens aufrechterhalt, fordern wir, dass fur zwei beliebige Knoten i und j die Schnittmenge ihrer UNLs im Verhaltnis zur maximalen Grosse einer der beiden UNLs ausreichend gross sein muss.
Genauer gesagt garantiert das Protokoll Sicherheit, wenn |UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5 fur alle Knotenpaare i und j gilt. Diese Bedingung stellt sicher, dass selbst wenn byzantinische Knoten versuchen, verschiedene Teile des Netzwerks zu unterschiedlichen Konsensentscheidungen zu bringen, die Uberlappung vertrauenswurdiger Knoten einen Fork verhindert. Wenn diese Bedingung erfullt ist und weniger als 1/5 der Knoten in jeder UNL byzantinisch sind, werden alle korrekten Knoten zur gleichen Konsensentscheidung gelangen.
Der formale Beweis erfolgt durch den Nachweis, dass wenn zwei Knoten zu unterschiedlichen Konsensentscheidungen gelangen konnten, eine Transaktion T existieren musste, die im endgultigen Ledger eines Knotens erscheint, aber nicht im anderen. Damit dies eintritt, musste T 80 % Unterstutzung in der UNL des ersten Knotens, aber weniger als 80 % Unterstutzung in der UNL des zweiten Knotens erreicht haben. Angesichts der Uberlappungsanforderung und der Beschrankung byzantinischer Knoten kann jedoch gezeigt werden, dass dieses Szenario unmoglich ist: Wenn T 80 % Unterstutzung in UNL_i erreicht, muss sie mindestens 60 % Unterstutzung in jeder UNL_j erreichen, die die Uberlappungsbedingung erfullt, und mit ausreichend Konsensrunden wird dies zu 80 % konvergieren oder von beiden Knoten abgelehnt werden.
Die Lebendigkeitseigenschaft -- dass Konsens schliesslich erreicht wird -- folgt aus der Beobachtung, dass der Schwellenwert fur die Aufnahme durch die Konsensrunden deterministisch ansteigt. Selbst bei Vorhandensein byzantinischer Knoten und Netzwerkverzogerungen stellt das Protokoll sicher, dass Transaktionen, die von einer Supermajority ehrlicher Knoten unterstutzt werden, schliesslich aufgenommen werden, wahrend Transaktionen ohne solche Unterstutzung ausgeschlossen werden. Die begrenzte Zeit fur den Konsens (typischerweise 5 Sekunden) bietet praktische Lebendigkeitsgarantien, die fur Zahlungssystemanwendungen geeignet sind.
Formal Analysis of Convergence
A correção do RPCA depende criticamente da sobreposição entre as UNLs escolhidas por diferentes nós na rede. Seja UNL_i a lista de nós únicos do nó i, e seja UNL_i ∩ UNL_j o conjunto de nós que aparecem tanto em UNL_i quanto em UNL_j. Para que a rede mantenha o consenso, exigimos que para quaisquer dois nós i e j, a interseção de suas UNLs seja suficientemente grande em relação ao tamanho máximo de qualquer uma das UNLs.
Especificamente, o protocolo garante segurança quando |UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5 para todos os pares de nós i e j. Esta condição garante que mesmo se os nós Byzantine tentarem fazer com que diferentes partes da rede cheguem a diferentes decisões de consenso, a sobreposição em nós confiáveis previne uma bifurcação. Se esta condição for mantida e menos de 1/5 dos nós em qualquer UNL forem Byzantine, então todos os nós corretos chegarão à mesma decisão de consenso.
A prova formal prossegue mostrando que se dois nós pudessem chegar a diferentes decisões de consenso, deve existir alguma transação T que aparece no livro-razão final de um nó mas não no do outro. Para que isso ocorra, T deve ter alcançado 80% de apoio na UNL do primeiro nó mas menos de 80% de apoio na UNL do segundo nó. No entanto, dado o requisito de sobreposição e a restrição sobre nós Byzantine, pode-se mostrar que este cenário é impossível: se T alcançar 80% de apoio em UNL_i, deve alcançar pelo menos 60% de apoio em qualquer UNL_j que satisfaça a condição de sobreposição, e com rodadas suficientes de consenso, isso convergirá para 80% ou será rejeitado por ambos os nós.
A propriedade de vivacidade -- que o consenso eventualmente será alcançado -- segue da observação de que o limite para inclusão aumenta deterministicamente ao longo das rodadas de consenso. Mesmo na presença de nós Byzantine e atrasos de rede, o protocolo garante que as transações apoiadas por uma supermaioria de nós honestos eventualmente serão incluídas, enquanto as transações que carecem de tal apoio serão excluídas. O tempo limitado para consenso (tipicamente 5 segundos) fornece garantias práticas de vivacidade adequadas para aplicações de sistemas de pagamento.
Unique Node Lists
Die Unique Node List (UNL) ist eine grundlegende Komponente von RPCA, die es von anderen Konsensalgorithmen unterscheidet. Jeder Knoten im Ripple-Netzwerk pflegt eine UNL, die aus anderen Knoten besteht, denen er vertraut, das Netzwerk nicht durch Absprachen zu betrugen. Entscheidend ist, dass dieses Vertrauen lokal und nicht global ist: Verschiedene Knoten konnen unterschiedliche UNLs haben, und es gibt keine Anforderung fur eine global vereinbarte Menge von Validatoren. Dieses Design ermoglicht es dem Netzwerk, organisch zu wachsen und gleichzeitig die Dezentralisierung aufrechtzuerhalten.
Die UNL dient als Sybil-Angriffs-Praventionsmechanismus ohne Proof-of-Work. In einem naiven Abstimmungssystem konnte ein Angreifer viele pseudonyme Knoten erstellen, um unverhaltnismassigen Einfluss zu erlangen. Indem jeder Knoten explizit wahlen muss, welchen anderen Knoten er vertraut, stellt RPCA sicher, dass die Erstellung zusatzlicher Identitaten keinen Vorteil bietet, es sei denn, diese Identitaten konnen bestehende Knoten davon uberzeugen, sie zu ihren UNLs hinzuzufugen. Dies verlagert das Problem der Sybil-Resistenz von der Rechenausgabe auf Reputation und Vertrauensbeziehungen.
Damit das Netzwerk korrekt funktioniert, mussen UNLs so gewahlt werden, dass sie ausreichende Uberlappung aufweisen, wie in der formalen Analyse beschrieben. In der Praxis bedeutet dies, dass jeder Knotenbetreiber zwar Autonomie bei der Auswahl seiner UNL hat, aber sicherstellen muss, dass seine Liste Validatoren enthalt, die auch von anderen Teilen des Netzwerks vertraut werden. Ripple stellt eine Standard-UNL bereit, die aus Validatoren besteht, die von verschiedenen Einrichtungen betrieben werden, aber Knotenbetreiber konnen diese Liste nach ihrer eigenen Vertrauensbewertung anpassen.
Der UNL-Mechanismus bietet auch einen naturlichen Weg zur progressiven Dezentralisierung. In den fruhen Phasen des Netzwerks kann eine zentralisiertere Menge von Validatoren angemessen sein, um Stabilitat und Zuverlassigkeit zu gewahrleisten. Wenn das Netzwerk reift und vielfaltiger Betreiber ihre Vertrauenswurdigkeit unter Beweis stellen, konnen die UNLs weiterentwickelt werden, um eine breitere Menge von Validatoren einzuschliessen, was die Widerstandsfahigkeit und Dezentralisierung des Netzwerks erhoht, ohne seine Sicherheitseigenschaften zu gefahrden.
Unique Node Lists
A Lista de Nós Únicos (UNL) é um componente fundamental do RPCA que o distingue de outros algoritmos de consenso. Cada nó na rede Ripple mantém uma UNL consistindo de outros nós em que confia para não conspirar para fraudar a rede. Criticamente, esta confiança é local em vez de global: diferentes nós podem ter diferentes UNLs, e não há requisito de um conjunto de validadores globalmente acordado. Este design permite que a rede escale organicamente enquanto mantém a descentralização.
A UNL serve como mecanismo de prevenção de ataques Sybil sem exigir prova de trabalho. Em um sistema de votação ingênuo, um atacante poderia criar muitos nós pseudônimos para obter influência desproporcional. Ao exigir que cada nó escolha explicitamente em quais outros nós confia, o RPCA garante que a criação de identidades adicionais não fornece nenhuma vantagem a menos que essas identidades possam convencer os nós existentes a adicioná-las às suas UNLs. Isso desloca o problema da resistência Sybil do gasto computacional para relacionamentos de reputação e confiança.
Para que a rede funcione corretamente, as UNLs devem ser escolhidas de modo que tenham sobreposição suficiente, conforme descrito na análise formal. Na prática, isso significa que embora cada operador de nó tenha autonomia na seleção de sua UNL, deve garantir que sua lista inclua validadores que também são confiados por outras partes da rede. O Ripple fornece uma UNL padrão consistindo de validadores operados por entidades diversas, mas os operadores de nós são livres para modificar esta lista com base em sua própria avaliação de confiança.
O mecanismo UNL também fornece um caminho natural em direção à descentralização progressiva. Nos estágios iniciais da rede, um conjunto mais centralizado de validadores pode ser apropriado para garantir estabilidade e confiabilidade. À medida que a rede amadurece e mais operadores diversos demonstram sua confiabilidade, as UNLs podem evoluir para incluir um conjunto mais amplo de validadores, aumentando a resiliência e descentralização da rede sem comprometer suas propriedades de segurança.
Simulation Code
Um die theoretische Analyse von RPCA zu validieren und seine Leistung unter verschiedenen Bedingungen zu bewerten, wurden umfangreiche Simulationen mit eigens entwickelter Simulationssoftware durchgefuhrt. Das Simulationsframework modelliert ein Netzwerk von Knoten, von denen jeder seine eigene UNL pflegt und am Konsensprotokoll teilnimmt. Der Code implementiert den vollstandigen RPCA-Algorithmus, einschliesslich Transaktionsvorschlagen, Abstimmungsrunden mit steigenden Schwellenwerten und Ledger-Validierung.
Wesentliche in den Simulationen variierte Parameter umfassen die Netzwerkgrosse (von 10 bis 1.000 Knoten), den Prozentsatz byzantinischer Knoten (von 0 % bis 20 %), die UNL-Grosse (typischerweise zwischen 5 und 50 Knoten) und Netzwerktopologie-Konfigurationen. Fur jede Parameterkonfiguration wurden mehrere Simulationslaufe mit verschiedenen Zufallsstartwerten durchgefuhrt, um die statistische Validitat der Ergebnisse sicherzustellen. Die Simulationen verfolgten Metriken wie Konsenslatenz, Fork-Wahrscheinlichkeit und Transaktionsdurchsatz.
Die Simulationsergebnisse bestatigen die theoretischen Vorhersagen bezuglich Konvergenz und Sicherheit. In allen Konfigurationen, in denen die UNL-Uberlappungsbedingung erfullt war und byzantinische Knoten weniger als 20 % jeder UNL ausmachten, erreichte das Netzwerk erfolgreich Konsens ohne Forks. Die Konsenslatenz blieb durchgehend niedrig (typischerweise in 3-5 simulierten Sekunden abgeschlossen), unabhangig von der Netzwerkgrosse, was die Skalierbarkeit des Algorithmus demonstriert. Selbst bei 15 % byzantinischer Knoten, die aktiv versuchten, den Konsens zu storen, behielt das Netzwerk die Korrektheit bei, solange die UNL-Uberlappungsanforderung erfullt war.
Zusatzliche Simulationen untersuchten Grenzfalle und Ausfallszenarien, einschliesslich Netzwerkpartitionen, plotzlicher Anderungen der UNL-Zusammensetzung und koordinierter Angriffe durch byzantinische Knoten. Diese Simulationen lieferten Erkenntnisse uber die Robustheit des Protokolls und informierten empfohlene Best Practices fur die UNL-Auswahl und den Netzwerkbetrieb. Der vollstandige Simulationscode wurde verfugbar gemacht, um unabhangige Uberprufung und weitere Forschung zu ermoglichen.
Simulation Code
Para validar a análise teórica do RPCA e avaliar seu desempenho sob várias condições, simulações extensas foram conduzidas usando software de simulação personalizado. O framework de simulação modela uma rede de nós, cada um mantendo sua própria UNL e participando do protocolo de consenso. O código implementa o algoritmo RPCA completo, incluindo proposta de transações, rodadas de votação com limites crescentes e validação do livro-razão.
Os parâmetros-chave variados nas simulações incluem tamanho da rede (variando de 10 a 1.000 nós), a porcentagem de nós Byzantine (de 0% a 20%), tamanho da UNL (tipicamente entre 5 e 50 nós) e configurações de topologia de rede. Para cada configuração de parâmetros, múltiplas execuções de simulação foram conduzidas com diferentes sementes aleatórias para garantir a validade estatística dos resultados. As simulações rastrearam métricas incluindo latência de consenso, probabilidade de bifurcação e taxa de transferência de transações.
Os resultados da simulação confirmam as previsões teóricas sobre convergência e segurança. Em todas as configurações onde a condição de sobreposição de UNL foi satisfeita e os nós Byzantine compreendiam menos de 20% de cada UNL, a rede alcançou consenso com sucesso sem bifurcações. A latência de consenso permaneceu consistentemente baixa (tipicamente completando em 3-5 segundos simulados) independentemente do tamanho da rede, demonstrando a escalabilidade do algoritmo. Mesmo com 15% de nós Byzantine tentando ativamente interromper o consenso, a rede manteve a correção desde que o requisito de sobreposição de UNL fosse atendido.
Simulações adicionais exploraram casos extremos e cenários de falha, incluindo partições de rede, mudanças repentinas na composição da UNL e ataques coordenados por nós Byzantine. Essas simulações forneceram insights sobre a robustez do protocolo e informaram as melhores práticas recomendadas para seleção de UNL e operação de rede. O código de simulação completo foi disponibilizado para permitir verificação independente e pesquisa adicional.
Discussion
Im Vergleich zu Bitcoins Proof-of-Work-Konsens bietet RPCA mehrere bedeutende Vorteile fur Zahlungssystemanwendungen. Am bemerkenswertesten ist, dass die Konsenslatenz von 40-60 Minuten (der typischerweise fur hochwertige Bitcoin-Transaktionen empfohlene Zeitraum) auf etwa 5 Sekunden reduziert wird. Diese Verbesserung macht RPCA geeignet fur Point-of-Sale und andere Anwendungen, bei denen eine nahezu sofortige Abwicklung erforderlich ist. Daruber hinaus benotigt RPCA im Vergleich zu Proof-of-Work minimale Rechenressourcen, wodurch der massive Energieverbrauch des Bitcoin-Minings entfallt.
Diese Vorteile gehen jedoch mit anderen Vertrauensannahmen einher. Wahrend Bitcoins Sicherheit nur auf der Annahme beruht, dass kein Angreifer mehr als 50 % der Rechenleistung des Netzwerks kontrolliert, erfordert RPCA, dass Knoten UNLs mit ausreichender Uberlappung wahlen und dass byzantinische Knoten den Schwellenwert innerhalb dieser UNLs nicht uberschreiten. Dies ubertragt einen Teil der Verantwortung auf die Knotenbetreiber, umsichtige Vertrauensentscheidungen zu treffen. In der Praxis ist dieser Kompromiss fur viele Zahlungssystem-Anwendungsfalle akzeptabel, in denen die teilnehmenden Institutionen bestehende Vertrauensbeziehungen haben.
Die Netzwerktopologie und die UNL-Auswahlstrategie wirken sich erheblich auf die Eigenschaften des Konsenssystems aus. Eine stark zentralisierte Topologie, bei der alle Knoten dieselben Validatoren in ihre UNLs aufnehmen, maximiert die Sicherheit, kann aber die Lebendigkeit verringern, wenn diese Validatoren nicht verfugbar werden. Umgekehrt kann eine stark dezentralisierte Topologie mit minimaler UNL-Uberlappung die Lebendigkeit verbessern, birgt aber das Risiko von Konsensfehlern, wenn die Uberlappung zu gering wird. Das Finden des optimalen Gleichgewichts erfordert eine sorgfaltige Berucksichtigung des spezifischen Einsatzszenarios und der Risikotoleranz.
Zukunftige Arbeiten konnten adaptive UNL-Auswahlalgorithmen untersuchen, die die Uberlappungsanforderungen automatisch aufrechterhalten und gleichzeitig die Dezentralisierung maximieren, Mechanismen fur Knoten, um ihre UNLs dynamisch basierend auf dem beobachteten Validatorverhalten anzupassen, und Erweiterungen des Konsensalgorithmus, die noch hohere Prozentsatze byzantinischer Knoten tolerieren konnten. Diese Verbesserungen konnten die Robustheit und Anwendbarkeit von RPCA fur grosse verteilte Zahlungssysteme weiter verbessern.
Discussion
Comparado ao consenso por prova de trabalho do Bitcoin, o RPCA oferece várias vantagens significativas para aplicações de sistemas de pagamento. Mais notavelmente, a latência de consenso é reduzida de 40-60 minutos (o tempo tipicamente recomendado para transações Bitcoin de alto valor) para aproximadamente 5 segundos. Esta melhoria torna o RPCA adequado para ponto de venda e outras aplicações onde a liquidação quase instantânea é necessária. Além disso, o RPCA requer recursos computacionais mínimos em comparação com a prova de trabalho, eliminando o consumo massivo de energia associado à mineração de Bitcoin.
No entanto, essas vantagens vêm com diferentes suposições de confiança. Enquanto a segurança do Bitcoin depende apenas da suposição de que nenhum atacante controla mais de 50% do poder computacional da rede, o RPCA exige que os nós escolham UNLs com sobreposição suficiente e que os nós Byzantine não excedam o limite dentro dessas UNLs. Isso transfere alguma responsabilidade para os operadores de nós para tomar decisões de confiança prudentes. Na prática, essa compensação é aceitável para muitos casos de uso de sistemas de pagamento onde as instituições participantes têm relacionamentos de confiança existentes.
A topologia de rede e a estratégia de seleção de UNL impactam significativamente as propriedades do sistema de consenso. Uma topologia altamente centralizada onde todos os nós incluem os mesmos validadores em suas UNLs maximiza a segurança, mas pode reduzir a vivacidade se esses validadores ficarem indisponíveis. Por outro lado, uma topologia altamente descentralizada com sobreposição mínima de UNL pode melhorar a vivacidade, mas poderia arriscar falhas de consenso se a sobreposição se tornar muito esparsa. Encontrar o equilíbrio ideal requer consideração cuidadosa do cenário de implantação específico e da tolerância ao risco.
Trabalhos futuros poderiam explorar algoritmos adaptativos de seleção de UNL que mantenham automaticamente os requisitos de sobreposição enquanto maximizam a descentralização, mecanismos para que os nós ajustem dinamicamente suas UNLs com base no comportamento observado dos validadores, e extensões ao algoritmo de consenso que possam tolerar porcentagens ainda mais altas de nós Byzantine. Essas melhorias poderiam aumentar ainda mais a robustez e aplicabilidade do RPCA para sistemas de pagamento distribuídos em larga escala.
Conclusion
Der Konsensalgorithmus des Ripple-Protokolls stellt einen bedeutenden Fortschritt im verteilten Konsens fur Zahlungssysteme dar. Durch die Nutzung kollektiv vertrauenswurdiger Subnetzwerke anstelle der Anforderung einer globalen Ubereinstimmung aller Knoten erreicht RPCA Konsens in Sekundenschnelle bei gleichzeitiger Aufrechterhaltung starker Garantien gegen byzantinische Ausfalle. Die formale Analyse zeigt, dass das Netzwerk korrekten Konsens ohne Forks erreicht, solange UNLs mit ausreichender Uberlappung gewahlt werden und byzantinische Knoten unter dem Schwellenwert bleiben.
Die praktischen Implikationen dieser Arbeit gehen uber das Ripple-Zahlungsnetzwerk hinaus. RPCA demonstriert, dass der traditionelle Kompromiss zwischen Konsenslatenz und Sicherheitsgarantien durch sorgfaltiges Protokolldesign und die Nutzung lokaler Vertrauensbeziehungen uberwunden werden kann. Dieser Ansatz kann sich als anwendbar auf andere verteilte Systeme erweisen, in denen niedrige Latenz entscheidend ist und Teilnehmer bestehende Vertrauensbeziehungen haben, wie beispielsweise Interbanken-Abrechnungssysteme, Lieferkettenverfolgung und andere Anwendungen der Finanzinfrastruktur.
Der Einsatz von RPCA in Produktionssystemen hat die Leistungsmerkmale und die Robustheit des Algorithmus validiert. Das Ripple-Netzwerk verarbeitet Tausende von Transaktionen pro Sekunde mit einer konstanten Konsenslatenz von 3-5 Sekunden und demonstriert damit, dass sich die theoretischen Eigenschaften effektiv in den realen Betrieb ubertragen. Wahrend das Netzwerk sich weiterentwickelt und zusatzliche Validatoren von verschiedenen Betreibern einbezieht, liefert es ein praktisches Beispiel dafur, wie ein dezentralisiertes Konsenssystem sowohl Sicherheit als auch Leistung im grossen Massstab aufrechterhalten kann.
Conclusion
O Algoritmo de Consenso do Protocolo Ripple representa um avanço significativo no consenso distribuído para sistemas de pagamento. Ao utilizar sub-redes coletivamente confiáveis em vez de exigir acordo global entre todos os nós, o RPCA alcança consenso em questão de segundos enquanto mantém fortes garantias contra falhas Byzantine. A análise formal demonstra que desde que as UNLs sejam escolhidas com sobreposição suficiente e os nós Byzantine permaneçam abaixo do limite, a rede alcançará consenso correto sem bifurcações.
As implicações práticas deste trabalho se estendem além da rede de pagamentos Ripple. O RPCA demonstra que a compensação tradicional entre latência de consenso e garantias de segurança pode ser superada através de design cuidadoso do protocolo e do uso de relacionamentos de confiança locais. Esta abordagem pode se mostrar aplicável a outros sistemas distribuídos onde a baixa latência é crítica e os participantes têm relacionamentos de confiança existentes, como sistemas de liquidação interbancária, rastreamento de cadeia de suprimentos e outras aplicações de infraestrutura financeira.
A implantação do RPCA em sistemas de produção validou as características de desempenho e robustez do algoritmo. A rede Ripple processa milhares de transações por segundo com latência de consenso consistente de 3-5 segundos, demonstrando que as propriedades teóricas se traduzem efetivamente para a operação no mundo real. À medida que a rede continua a evoluir e incorporar validadores adicionais de operadores diversos, ela fornece um exemplo prático de como um sistema de consenso descentralizado pode manter tanto a segurança quanto o desempenho em escala.
References
Lamport, L., Shostak, R., und Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. Diese bahnbrechende Arbeit formalisierte das Problem der Konsensfindung in verteilten Systemen mit fehlerhaften Komponenten und legte die theoretische Grundlage fur byzantinisch fehlertolerante Systeme.
Castro, M., und Liskov, B. (1999). "Practical Byzantine Fault Tolerance." Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI). Diese Arbeit fuhrte PBFT ein und zeigte, dass byzantinische Fehlertoleranz mit praktischer Leistung erreicht werden kann, allerdings mit einer Kommunikationskomplexitat von O(n^2), die die Skalierbarkeit einschrankt.
Nakamoto, S. (2008). "Bitcoin: A Peer-to-Peer Electronic Cash System." Dieses Whitepaper fuhrte den Proof-of-Work-Konsens als Losung fur das Double-Spending-Problem bei digitaler Wahrung ein und ermoglichte dezentralen Konsens ohne vertrauenswurdige Parteien auf Kosten hoher Latenz und Energieverbrauchs.
Lamport, L. (1998). "The Part-Time Parliament." ACM Transactions on Computer Systems, 16(2):133-169. Diese Arbeit prasentierte den Paxos-Algorithmus, der Konsens in asynchronen Systemen unter Absturzfehlern erreicht und nachfolgende Konsensprotokollentwurfe beeinflusste.
Fischer, M. J., Lynch, N. A., und Paterson, M. S. (1985). "Impossibility of Distributed Consensus with One Faulty Process." Journal of the ACM, 32(2):374-382. Das FLP-Unmoglichkeitsergebnis etablierte fundamentale Grenzen dessen, was Konsensalgorithmen in asynchronen Systemen erreichen konnen, und pragte den Designraum fur praktische Konsensprotokolle.
References
Lamport, L., Shostak, R., and Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. Este artigo seminal formalizou o problema de alcançar consenso em sistemas distribuídos com componentes defeituosos e estabeleceu a base teórica para sistemas 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). Este trabalho introduziu o PBFT, demonstrando que a Byzantine fault tolerance poderia ser alcançada com desempenho prático, embora com complexidade de comunicação O(n^2) limitando a escalabilidade.
Nakamoto, S. (2008). "Bitcoin: A Peer-to-Peer Electronic Cash System." Este whitepaper introduziu o consenso por prova de trabalho como solução para o problema do gasto duplo em moeda digital, permitindo consenso descentralizado sem partes confiáveis ao custo de alta latência e consumo de energia.
Lamport, L. (1998). "The Part-Time Parliament." ACM Transactions on Computer Systems, 16(2):133-169. Este artigo apresentou o algoritmo Paxos, que alcança consenso em sistemas assíncronos sob falhas por crash, influenciando designs subsequentes de protocolos de consenso.
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. O resultado de impossibilidade FLP estabeleceu limites fundamentais sobre o que os algoritmos de consenso podem alcançar em sistemas assíncronos, moldando o espaço de design para protocolos de consenso práticos.
