Der Konsensalgorithmus des Ripple-Protokolls
Abstract
Хотя существует несколько алгоритмов консенсуса для задачи Византийских генералов, в частности применительно к распределенным платежным системам, многие из них страдают от высокой задержки, вызванной необходимостью синхронного взаимодействия всех узлов сети. В данной работе мы представляем новый алгоритм консенсуса, который обходит это требование, используя коллективно доверенные подсети внутри более крупной сети. Мы показываем, что "доверие", необходимое для предотвращения атак Сивиллы (Sybil), на самом деле не является глобальным, а локальным для каждого узла сети.
Алгоритм консенсуса протокола Ripple (RPCA) применяется каждые несколько секунд всеми узлами для поддержания корректности и согласованности сети. После достижения консенсуса текущий леджер считается "закрытым" и становится последним закрытым леджером. Этот алгоритм уникален тем, что достигает консенсуса с низкой задержкой, сохраняя при этом надежные гарантии против византийских отказов, что делает его пригодным для систем финансовых расчетов в реальном времени.
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.
Introduction
Распределенная платежная система должна реализовывать алгоритм консенсуса для корректной и своевременной обработки платежей даже при наличии неисправных или злонамеренных участников. Bitcoin достигает консенсуса с помощью доказательства работы (proof-of-work), которое требует от всех узлов затрачивать вычислительные ресурсы на решение криптографических задач. Хотя этот подход обеспечивает надежные гарантии безопасности, он имеет существенные недостатки, включая высокое энергопотребление, низкую пропускную способность транзакций и длительные задержки подтверждения, которые могут достигать часа и более для транзакций высокой стоимости.
Алгоритм консенсуса протокола Ripple предлагает новый подход к распределенному консенсусу, не требующий доказательства работы. Вместо этого узлы сети коллективно согласовывают наборы транзакций посредством процесса голосования, который достигает консенсуса за считанные секунды. Этот механизм консенсуса разработан специально для требований глобальной платежной сети, где низкая задержка и высокая пропускная способность необходимы для практического развертывания.
Ключевое нововведение RPCA заключается в том, что он не требует согласия всех узлов сети друг с другом. Вместо этого каждый узел ведет Уникальный список узлов (Unique Node List, UNL) других узлов, которым он доверяет в том, что они не вступят в сговор. Пока выбранные узлами UNL имеют достаточное пересечение и менее порогового процента узлов являются неисправными, сеть достигнет консенсуса. Этот подход обеспечивает гарантии безопасности, необходимые для платежной системы, при этом достигая задержки консенсуса, измеряемой в секундах, а не в минутах или часах.
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.
Definition of Consensus
В распределенных системах консенсус означает процесс, посредством которого сеть узлов приходит к согласию относительно общего состояния, несмотря на наличие неисправных или злонамеренных участников. Алгоритм консенсуса должен удовлетворять трем фундаментальным свойствам: корректность (никакие два правильных узла не принимают разных решений), согласие (все правильные узлы приходят к одному решению) и завершение (все правильные узлы в конечном итоге принимают решение). Эти свойства обеспечивают поведение распределенной системы так, как если бы она была единым надежным узлом.
Сложность достижения консенсуса обусловлена присущей ненадежностью распределенных систем. Узлы могут выходить из строя, сообщения могут задерживаться или теряться, а византийские узлы могут вести себя произвольно или злонамеренно. Задача Византийских генералов, формализованная Лэмпортом, Шостаком и Пизом, отражает эту проблему: как группа процессов может достичь согласия, когда некоторая доля может быть неисправной, а связь ненадежна?
Классические результаты в области распределенных вычислений устанавливают фундаментальные пределы того, чего могут достичь алгоритмы консенсуса. Результат невозможности FLP показывает, что ни один детерминированный алгоритм не может гарантировать консенсус в асинхронной системе, если хотя бы один узел может отказать. Поэтому практические алгоритмы консенсуса должны идти на компромисс между безопасностью (никогда не достигать неверного консенсуса) и живучестью (всегда продвигаться вперед). Proof-of-work Bitcoin отдает приоритет безопасности над живучестью, тогда как RPCA достигает баланса, более подходящего для платежных систем, завершая раунды консенсуса за ограниченное время при сохранении надежных гарантий безопасности в рамках реалистичных предположений о сбоях.
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.
Existing Consensus Algorithms
Для решения задачи Византийских генералов в распределенных системах было предложено несколько алгоритмов консенсуса. Алгоритм Practical Byzantine Fault Tolerance (PBFT), представленный Кастро и Лисков, может допускать до f византийских сбоев в системе из 3f+1 узлов. PBFT достигает консенсуса через несколько раундов обмена сообщениями между всеми узлами со сложностью коммуникации O(n^2), где n -- количество узлов. Хотя PBFT обеспечивает надежные гарантии безопасности и относительно низкую задержку для небольших сетей, он плохо масштабируется для больших сетей из-за квадратичных накладных расходов на коммуникацию.
Paxos и его варианты, разработанные Лэмпортом, обеспечивают консенсус в асинхронных системах, но предполагают отказы по сбою, а не византийские отказы. Paxos достигает консенсуса через серию раундов, в которых предлагающие узлы выдвигают значения, а принимающие узлы голосуют за них. Хотя Paxos может допускать произвольные задержки сообщений и отказы процессов, он требует тщательной инженерии для обработки византийских отказов и может страдать от livelock в определенных сценариях.
Алгоритм консенсуса proof-of-work Bitcoin использует принципиально иной подход, делая византийские атаки экономически нецелесообразными. Узлы соревнуются в решении криптографических задач, при этом победитель предлагает следующий блок транзакций. Хотя этот подход масштабируется до произвольных размеров сети и справляется с византийскими отказами, он имеет серьезные недостатки: огромное потребление энергии (оценивается более чем в 150 миллионов долларов в год для сети Bitcoin), длительные задержки подтверждения (часто 40-60 минут для транзакций высокой стоимости) и ограниченная пропускная способность (приблизительно 7 транзакций в секунду). Эти ограничения делают proof-of-work непригодным для многих приложений платежных систем, требующих быстрого расчета и больших объемов транзакций.
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.
Ripple Protocol Consensus Algorithm
Алгоритм консенсуса протокола Ripple (RPCA) начинается с того, что каждый сервер берет все действительные транзакции, которые он видел и которые еще не были применены, в качестве транзакций-кандидатов. Затем серверы следуют многораундовому протоколу, в котором они итеративно работают над достижением согласия относительно набора транзакций, которые должны быть применены к текущему леджеру. В каждом раунде серверы делают предложения, состоящие из транзакций, которые, по их мнению, должны быть включены в следующий леджер.
В ходе каждого раунда консенсуса серверы передают свои предложения другим серверам из своего Уникального списка узлов (Unique Node List, UNL). Затем серверы вычисляют, какие транзакции появляются в пороговом проценте предложений. Изначально этот порог установлен на уровне 50%, что означает, что транзакция должна появиться в предложениях как минимум половины UNL сервера, чтобы быть рассмотренной в следующем раунде. По мере продвижения консенсуса через последовательные раунды этот порог увеличивается поэтапно (обычно до 60%, 70% и, наконец, 80%).
Когда транзакция достигает порога квалифицированного большинства в 80% поддержки в UNL сервера, она включается в предложение этого сервера для финального раунда консенсуса. Все транзакции, достигшие этого порога по всей сети, применяются к леджеру, который затем криптографически хешируется и подписывается. Этот вновь подтвержденный леджер становится последним закрытым леджером, и процесс начинается заново с новым набором транзакций-кандидатов.
Процесс консенсуса обычно завершается за 5 секунд или менее, при этом большинству транзакций требуется только один раунд консенсуса для достижения порога квалифицированного большинства. Транзакции, не достигшие консенсуса за один раунд, остаются кандидатами для последующих раундов. Такая конструкция обеспечивает непрерывный прогресс сети при сохранении надежных гарантий безопасности, поскольку ни одна транзакция не может быть применена к леджеру без поддержки квалифицированного большинства доверенных валидаторов.
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.
Formal Analysis of Convergence
Корректность RPCA критически зависит от пересечения между UNL, выбранными различными узлами сети. Пусть UNL_i обозначает уникальный список узлов узла i, а UNL_i ∩ UNL_j представляет множество узлов, которые присутствуют как в UNL_i, так и в UNL_j. Для того чтобы сеть поддерживала консенсус, мы требуем, чтобы для любых двух узлов i и j пересечение их UNL было достаточно большим относительно максимального размера любого из UNL.
В частности, протокол гарантирует безопасность, когда |UNL_i ∩ UNL_j| / max(|UNL_i|, |UNL_j|) 1/5 для всех пар узлов i и j. Это условие обеспечивает, что даже если византийские узлы попытаются привести различные части сети к различным решениям консенсуса, пересечение доверенных узлов предотвращает форк. Если это условие выполняется и менее 1/5 узлов в любом UNL являются византийскими, то все корректные узлы придут к одному и тому же решению консенсуса.
Формальное доказательство проводится путем демонстрации того, что если бы два узла могли прийти к различным решениям консенсуса, должна была бы существовать транзакция T, которая присутствует в финальном леджере одного узла, но не другого. Для этого T должна была бы получить 80% поддержки в UNL первого узла, но менее 80% поддержки в UNL второго узла. Однако, учитывая требование пересечения и ограничение на византийские узлы, можно показать, что этот сценарий невозможен: если T достигает 80% поддержки в UNL_i, она должна достичь как минимум 60% поддержки в любом UNL_j, удовлетворяющем условию пересечения, и при достаточном количестве раундов консенсуса это сойдется к 80% или будет отклонено обоими узлами.
Свойство живучести -- что консенсус в конечном итоге будет достигнут -- следует из наблюдения, что порог включения детерминированно возрастает через раунды консенсуса. Даже при наличии византийских узлов и сетевых задержек протокол обеспечивает, что транзакции, поддержанные квалифицированным большинством честных узлов, в конечном итоге будут включены, тогда как транзакции без такой поддержки будут исключены. Ограниченное время для консенсуса (обычно 5 секунд) обеспечивает практические гарантии живучести, подходящие для приложений платежных систем.
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.
Unique Node Lists
Уникальный список узлов (Unique Node List, UNL) является фундаментальным компонентом RPCA, который отличает его от других алгоритмов консенсуса. Каждый узел в сети Ripple ведет UNL, состоящий из других узлов, которым он доверяет в том, что они не вступят в сговор для обмана сети. Критически важно, что это доверие является локальным, а не глобальным: разные узлы могут иметь разные UNL, и нет требования глобально согласованного набора валидаторов. Такая конструкция позволяет сети масштабироваться органически при сохранении децентрализации.
UNL служит механизмом предотвращения атак Сивиллы (Sybil) без необходимости доказательства работы. В наивной системе голосования злоумышленник мог бы создать множество псевдонимных узлов для получения непропорционального влияния. Требуя от каждого узла явного выбора тех узлов, которым он доверяет, RPCA гарантирует, что создание дополнительных идентичностей не дает преимущества, если только эти идентичности не смогут убедить существующие узлы добавить их в свои UNL. Это переносит проблему устойчивости к атакам Сивиллы с вычислительных затрат на репутацию и доверительные отношения.
Для корректного функционирования сети UNL должны быть выбраны таким образом, чтобы иметь достаточное пересечение, как описано в формальном анализе. На практике это означает, что хотя каждый оператор узла имеет автономию в выборе своего UNL, он должен обеспечить, чтобы его список включал валидаторов, которым также доверяют другие части сети. Ripple предоставляет UNL по умолчанию, состоящий из валидаторов, управляемых разнообразными организациями, но операторы узлов вольны модифицировать этот список на основе собственной оценки доверия.
Механизм UNL также обеспечивает естественный путь к прогрессивной децентрализации. На ранних этапах сети более централизованный набор валидаторов может быть уместен для обеспечения стабильности и надежности. По мере созревания сети и демонстрации своей надежности разнообразными операторами UNL могут эволюционировать, включая более широкий набор валидаторов, увеличивая устойчивость и децентрализацию сети без ущерба для ее свойств безопасности.
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.
Simulation Code
Для валидации теоретического анализа RPCA и оценки его производительности в различных условиях были проведены обширные симуляции с использованием специально разработанного программного обеспечения для моделирования. Среда моделирования представляет сеть узлов, каждый из которых ведет собственный UNL и участвует в протоколе консенсуса. Код реализует полный алгоритм RPCA, включая предложение транзакций, раунды голосования с возрастающими порогами и валидацию леджера.
Ключевые параметры, варьировавшиеся в симуляциях, включают размер сети (от 10 до 1 000 узлов), процент византийских узлов (от 0% до 20%), размер UNL (обычно от 5 до 50 узлов) и конфигурации топологии сети. Для каждой конфигурации параметров было проведено несколько запусков симуляции с различными случайными начальными значениями для обеспечения статистической достоверности результатов. В симуляциях отслеживались такие метрики, как задержка консенсуса, вероятность форка и пропускная способность транзакций.
Результаты моделирования подтверждают теоретические предсказания относительно сходимости и безопасности. Во всех конфигурациях, где условие пересечения UNL было выполнено и византийские узлы составляли менее 20% каждого UNL, сеть успешно достигала консенсуса без форков. Задержка консенсуса оставалась стабильно низкой (обычно завершаясь за 3-5 смоделированных секунд) независимо от размера сети, демонстрируя масштабируемость алгоритма. Даже при 15% византийских узлов, активно пытающихся нарушить консенсус, сеть сохраняла корректность при выполнении требования пересечения UNL.
Дополнительные симуляции исследовали граничные случаи и сценарии отказов, включая разделение сети, внезапные изменения состава UNL и координированные атаки византийских узлов. Эти симуляции предоставили информацию о надежности протокола и определили рекомендуемые лучшие практики для выбора UNL и эксплуатации сети. Полный код моделирования был предоставлен для независимой верификации и дальнейших исследований.
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.
Discussion
По сравнению с консенсусом proof-of-work Bitcoin, RPCA предлагает несколько значительных преимуществ для приложений платежных систем. Наиболее примечательно, что задержка консенсуса сокращается с 40-60 минут (время, обычно рекомендуемое для высокостоимостных транзакций Bitcoin) до примерно 5 секунд. Это улучшение делает RPCA пригодным для точек продаж и других приложений, где требуется практически мгновенный расчет. Кроме того, RPCA требует минимальных вычислительных ресурсов по сравнению с proof-of-work, устраняя огромное потребление энергии, связанное с майнингом Bitcoin.
Однако эти преимущества сопряжены с иными предположениями о доверии. В то время как безопасность Bitcoin основывается только на предположении, что ни один злоумышленник не контролирует более 50% вычислительной мощности сети, RPCA требует, чтобы узлы выбирали UNL с достаточным пересечением и чтобы византийские узлы не превышали порог в этих UNL. Это перекладывает часть ответственности на операторов узлов за принятие разумных решений о доверии. На практике этот компромисс приемлем для многих случаев использования платежных систем, где участвующие учреждения имеют существующие доверительные отношения.
Топология сети и стратегия выбора UNL существенно влияют на свойства системы консенсуса. Высокоцентрализованная топология, при которой все узлы включают одних и тех же валидаторов в свои UNL, максимизирует безопасность, но может снизить живучесть, если эти валидаторы станут недоступными. И наоборот, высокодецентрализованная топология с минимальным пересечением UNL может улучшить живучесть, но рискует привести к сбоям консенсуса, если пересечение станет слишком малым. Нахождение оптимального баланса требует тщательного рассмотрения конкретного сценария развертывания и допустимого уровня риска.
Будущие работы могут исследовать адаптивные алгоритмы выбора UNL, которые автоматически поддерживают требования пересечения при максимизации децентрализации, механизмы для динамической корректировки UNL узлами на основе наблюдаемого поведения валидаторов и расширения алгоритма консенсуса, которые могли бы допускать еще более высокие доли византийских узлов. Эти улучшения могут дополнительно повысить надежность и применимость RPCA для крупномасштабных распределенных платежных систем.
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.
Conclusion
Алгоритм консенсуса протокола Ripple представляет собой значительное достижение в области распределенного консенсуса для платежных систем. Используя коллективно доверенные подсети вместо требования глобального согласия между всеми узлами, RPCA достигает консенсуса за считанные секунды, сохраняя при этом надежные гарантии против византийских отказов. Формальный анализ демонстрирует, что при условии выбора UNL с достаточным пересечением и нахождении византийских узлов ниже порогового значения сеть достигнет корректного консенсуса без форков.
Практические последствия этой работы выходят за рамки платежной сети Ripple. RPCA демонстрирует, что традиционный компромисс между задержкой консенсуса и гарантиями безопасности может быть преодолен посредством тщательного проектирования протокола и использования локальных доверительных отношений. Этот подход может оказаться применимым к другим распределенным системам, где критически важна низкая задержка и участники имеют существующие доверительные отношения, таким как системы межбанковских расчетов, отслеживание цепочек поставок и другие приложения финансовой инфраструктуры.
Развертывание RPCA в производственных системах подтвердило характеристики производительности и надежность алгоритма. Сеть Ripple обрабатывает тысячи транзакций в секунду со стабильной задержкой консенсуса 3-5 секунд, демонстрируя, что теоретические свойства эффективно переносятся на реальную эксплуатацию. По мере дальнейшего развития сети и включения дополнительных валидаторов от разнообразных операторов она служит практическим примером того, как децентрализованная система консенсуса может поддерживать как безопасность, так и производительность в масштабе.
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.
References
Lamport, L., Shostak, R., and Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. Эта основополагающая статья формализовала проблему достижения консенсуса в распределенных системах с неисправными компонентами и заложила теоретическую основу для византийски отказоустойчивых систем.
Castro, M., and Liskov, B. (1999). "Practical Byzantine Fault Tolerance." Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI). Эта работа представила PBFT, продемонстрировав, что византийская отказоустойчивость может быть достигнута с практической производительностью, хотя со сложностью коммуникации 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 установил фундаментальные пределы того, чего алгоритмы консенсуса могут достичь в асинхронных системах, определив пространство проектирования для практических протоколов консенсуса.
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.
