리플 프로토콜 합의 알고리즘
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.
Abstract
Byzantine Generals Problem에 대한 여러 합의 알고리즘이 존재하지만, 특히 분산 결제 시스템과 관련하여 많은 알고리즘이 네트워크 내 모든 노드가 동기적으로 통신해야 하는 요구사항으로 인해 높은 지연 시간 문제를 겪고 있다. 본 연구에서는 더 큰 네트워크 내에서 집합적으로 신뢰할 수 있는 하위 네트워크를 활용하여 이 요구사항을 우회하는 새로운 합의 알고리즘을 제시한다. Sybil 공격을 방지하기 위해 필요한 "신뢰"가 실제로는 전역적인 것이 아니라 네트워크 내 각 노드에 대해 지역적임을 보여준다.
Ripple 프로토콜 합의 알고리즘(RPCA)은 네트워크의 정확성과 합의를 유지하기 위해 모든 노드에 의해 수 초마다 적용된다. 합의에 도달하면 현재 원장은 "폐쇄"된 것으로 간주되며 마지막으로 폐쇄된 원장(last-closed ledger)이 된다. 이 알고리즘은 Byzantine 장애에 대한 강력한 보장을 유지하면서 낮은 지연 시간으로 합의를 달성한다는 점에서 독특하며, 실시간 금융 결제 시스템에 적합하다.
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.
Introduction
분산 결제 시스템은 결함이 있거나 악의적인 행위자가 존재하는 상황에서도 적시에 올바르게 결제를 처리하기 위해 합의 알고리즘을 구현해야 한다. 비트코인은 작업 증명(proof-of-work)을 사용하여 합의를 달성하며, 이는 모든 노드가 암호화 퍼즐을 풀기 위해 계산 자원을 소비하도록 요구한다. 이 접근 방식은 강력한 보안 보장을 제공하지만 높은 에너지 소비, 낮은 트랜잭션 처리량, 그리고 고가치 트랜잭션의 경우 1시간 이상까지 늘어날 수 있는 긴 확인 지연 시간을 포함한 상당한 단점이 있다.
Ripple 프로토콜 합의 알고리즘은 작업 증명을 필요로 하지 않는 분산 합의에 대한 새로운 접근 방식을 제공한다. 대신, 네트워크의 노드들은 수 초 내에 합의를 달성하는 투표 과정을 통해 트랜잭션 집합에 대해 집단적으로 동의한다. 이 합의 메커니즘은 실질적인 배포를 위해 낮은 지연 시간과 높은 처리량이 필수적인 글로벌 결제 네트워크의 요구사항에 맞춰 특별히 설계되었다.
RPCA의 핵심 혁신은 네트워크의 모든 노드가 서로 동의할 필요가 없다는 점이다. 대신, 각 노드는 공모하지 않을 것으로 신뢰하는 다른 노드들의 고유 노드 목록(Unique Node List, UNL)을 유지한다. 노드들이 선택한 UNL이 충분한 중첩을 가지고 있고, 임계값 비율 미만의 노드만 결함이 있다면 네트워크는 합의에 도달할 것이다. 이 접근 방식은 합의 지연 시간을 분이나 시간이 아닌 초 단위로 측정하면서 결제 시스템에 필요한 보안 보장을 제공한다.
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.
Definition of Consensus
분산 시스템에서 합의란 결함이 있거나 악의적인 참가자가 존재하는 상황에서도 노드 네트워크가 공유 상태에 대한 동의에 도달하는 과정을 말한다. 합의 알고리즘은 세 가지 기본 속성을 만족해야 한다: 정확성(두 개의 올바른 노드가 서로 다르게 결정하지 않음), 동의(모든 올바른 노드가 동일한 결정에 도달함), 그리고 종료(모든 올바른 노드가 결국 결정을 내림). 이러한 속성은 분산 시스템이 단일의 신뢰할 수 있는 노드처럼 동작하도록 보장한다.
합의를 달성하는 데 있어서의 도전은 분산 시스템의 본질적인 불안정성에서 비롯된다. 노드가 충돌할 수 있고, 메시지가 지연되거나 손실될 수 있으며, Byzantine 노드는 임의적으로 또는 악의적으로 행동할 수 있다. Lamport, Shostak, Pease가 공식화한 Byzantine Generals Problem은 이 도전을 포착한다: 일부가 결함이 있을 수 있고 통신이 불안정한 상황에서 프로세스 그룹이 어떻게 합의에 도달할 수 있는가?
분산 컴퓨팅의 고전적 결과들은 합의 알고리즘이 달성할 수 있는 것의 근본적 한계를 확립한다. FLP 불가능성 결과는 단 하나의 노드만 실패할 수 있는 비동기 시스템에서도 어떤 결정론적 알고리즘도 합의를 보장할 수 없음을 보여준다. 따라서 실용적인 합의 알고리즘은 안전성(잘못된 합의에 절대 도달하지 않음)과 활성(항상 진행함) 사이에서 절충해야 한다. 비트코인의 작업 증명은 활성보다 안전성을 우선시하는 반면, RPCA는 현실적인 결함 가정 하에서 강력한 안전성 보장을 유지하면서 제한된 시간 내에 합의 라운드를 완료함으로써 결제 시스템에 더 적합한 균형을 달성한다.
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.
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
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.
Ripple Protocol Consensus Algorithm
Ripple 프로토콜 합의 알고리즘(RPCA)은 각 서버가 아직 적용되지 않은 유효한 트랜잭션을 모두 후보 트랜잭션으로 수집하는 것으로 시작한다. 그런 다음 서버들은 현재 원장에 적용할 트랜잭션 집합에 대한 합의를 향해 반복적으로 작업하는 다중 라운드 프로토콜을 따른다. 각 라운드에서 서버들은 다음 원장에 포함되어야 한다고 생각하는 트랜잭션으로 구성된 제안을 만든다.
각 합의 라운드 동안 서버들은 자신의 고유 노드 목록(UNL)에 있는 다른 서버들에게 제안을 전달한다. 그런 다음 서버들은 어떤 트랜잭션이 임계값 비율 이상의 제안에 나타나는지 계산한다. 처음에 이 임계값은 50%로 설정되며, 이는 트랜잭션이 다음 라운드에서 고려되려면 서버 UNL의 최소 절반 이상의 제안에 나타나야 함을 의미한다. 합의가 연속적인 라운드를 거치면서 이 임계값은 점진적으로 증가한다(일반적으로 60%, 70%, 그리고 최종적으로 80%).
트랜잭션이 서버의 UNL에서 80%의 절대다수 지지 임계값을 달성하면, 해당 트랜잭션은 최종 합의 라운드에 대한 서버의 제안에 포함된다. 네트워크 전체에서 이 임계값에 도달한 모든 트랜잭션은 원장에 적용되고, 원장은 암호화 해시되고 서명된다. 이 새로 검증된 원장이 마지막으로 폐쇄된 원장이 되며, 다음 후보 트랜잭션 집합으로 프로세스가 다시 시작된다.
합의 과정은 일반적으로 5초 이내에 완료되며, 대부분의 트랜잭션은 절대다수 임계값을 달성하기 위해 단 한 번의 합의 라운드만 필요로 한다. 한 라운드에서 합의를 달성하지 못한 트랜잭션은 후속 라운드의 후보로 남는다. 이 설계는 신뢰할 수 있는 검증자들의 절대다수 지지 없이는 어떤 트랜잭션도 원장에 적용될 수 없으므로 강력한 안전성 보장을 유지하면서 네트워크가 지속적으로 진행되도록 보장한다.
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.
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
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.
Unique Node Lists
고유 노드 목록(UNL)은 RPCA를 다른 합의 알고리즘과 구별하는 근본적인 구성 요소이다. Ripple 네트워크의 각 노드는 네트워크를 속이기 위해 공모하지 않을 것으로 신뢰하는 다른 노드들로 구성된 UNL을 유지한다. 중요한 점은 이 신뢰가 전역적이 아닌 지역적이라는 것이다: 서로 다른 노드가 서로 다른 UNL을 가질 수 있으며, 전역적으로 합의된 검증자 집합을 요구하지 않는다. 이 설계는 탈중앙화를 유지하면서 네트워크가 유기적으로 확장될 수 있게 한다.
UNL은 작업 증명 없이 Sybil 공격 방지 메커니즘 역할을 한다. 순진한 투표 시스템에서 공격자는 불균형적인 영향력을 얻기 위해 많은 가명 노드를 생성할 수 있다. 각 노드가 신뢰하는 다른 노드를 명시적으로 선택하도록 요구함으로써, RPCA는 해당 신원이 기존 노드를 설득하여 UNL에 추가될 수 없는 한, 추가 신원을 생성하는 것이 아무런 이점을 제공하지 않도록 보장한다. 이것은 Sybil 저항의 문제를 계산적 지출에서 평판과 신뢰 관계로 전환시킨다.
네트워크가 올바르게 기능하기 위해서는 형식적 분석에서 설명한 것처럼 UNL이 충분한 중첩을 갖도록 선택되어야 한다. 실제로 이것은 각 노드 운영자가 UNL 선택에 자율성을 가지면서도 네트워크의 다른 부분에서도 신뢰하는 검증자를 포함하도록 보장해야 함을 의미한다. Ripple은 다양한 주체가 운영하는 검증자로 구성된 기본 UNL을 제공하지만, 노드 운영자는 자체 신뢰 평가에 따라 이 목록을 자유롭게 수정할 수 있다.
UNL 메커니즘은 또한 점진적 탈중앙화를 향한 자연스러운 경로를 제공한다. 네트워크 초기 단계에서는 안정성과 신뢰성을 보장하기 위해 보다 중앙화된 검증자 집합이 적절할 수 있다. 네트워크가 성숙하고 더 다양한 운영자들이 신뢰성을 입증함에 따라, UNL은 보안 속성을 타협하지 않으면서 네트워크의 회복력과 탈중앙화를 높이는 더 넓은 검증자 집합을 포함하도록 진화할 수 있다.
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.
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
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.
Discussion
비트코인의 작업 증명 합의와 비교하여, RPCA는 결제 시스템 응용에 여러 가지 중요한 이점을 제공한다. 가장 주목할 만한 것은 합의 지연 시간이 40-60분(고가치 비트코인 트랜잭션에 일반적으로 권장되는 시간)에서 약 5초로 단축된다는 점이다. 이 개선으로 RPCA는 즉각적인 결제가 필요한 판매 시점(POS) 및 기타 응용에 적합해진다. 또한 RPCA는 작업 증명에 비해 최소한의 계산 자원을 필요로 하여, 비트코인 채굴과 관련된 막대한 에너지 소비를 제거한다.
그러나 이러한 장점에는 다른 신뢰 가정이 수반된다. 비트코인의 보안이 어떤 공격자도 네트워크 계산 능력의 50% 이상을 통제하지 못한다는 가정에만 의존하는 반면, RPCA는 노드들이 충분한 중첩을 가진 UNL을 선택하고 Byzantine 노드가 이 UNL 내에서 임계값을 초과하지 않을 것을 요구한다. 이것은 노드 운영자에게 신중한 신뢰 결정을 내릴 일부 책임을 전가한다. 실제로 이 절충은 참여 기관이 기존의 신뢰 관계를 가진 많은 결제 시스템 사용 사례에서 수용 가능하다.
네트워크 토폴로지와 UNL 선택 전략은 합의 시스템의 속성에 상당한 영향을 미친다. 모든 노드가 UNL에 동일한 검증자를 포함하는 고도로 중앙화된 토폴로지는 안전성을 최대화하지만, 해당 검증자가 사용 불가능해지면 활성이 감소할 수 있다. 반대로, 최소한의 UNL 중첩을 가진 고도로 탈중앙화된 토폴로지는 활성을 개선할 수 있지만, 중첩이 너무 희박해지면 합의 실패의 위험이 있다. 최적의 균형을 찾으려면 특정 배포 시나리오와 위험 허용 범위를 신중하게 고려해야 한다.
향후 연구는 탈중앙화를 최대화하면서 중첩 요구사항을 자동으로 유지하는 적응적 UNL 선택 알고리즘, 관찰된 검증자 행동에 기반하여 노드가 동적으로 UNL을 조정하는 메커니즘, 그리고 더 높은 비율의 Byzantine 노드를 허용할 수 있는 합의 알고리즘의 확장을 탐구할 수 있다. 이러한 개선은 대규모 분산 결제 시스템에 대한 RPCA의 견고성과 적용 가능성을 더욱 향상시킬 수 있다.
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.
Conclusion
Ripple 프로토콜 합의 알고리즘은 결제 시스템을 위한 분산 합의에서 중요한 발전을 나타낸다. 모든 노드 간의 전역적 합의를 요구하는 대신 집합적으로 신뢰할 수 있는 하위 네트워크를 활용함으로써, RPCA는 Byzantine 장애에 대한 강력한 보장을 유지하면서 수 초 만에 합의를 달성한다. 형식적 분석은 UNL이 충분한 중첩으로 선택되고 Byzantine 노드가 임계값 이하로 유지되는 한, 네트워크가 포크 없이 올바른 합의에 도달할 것임을 입증한다.
이 연구의 실질적인 시사점은 Ripple 결제 네트워크를 넘어 확장된다. RPCA는 합의 지연 시간과 보안 보장 사이의 전통적인 절충이 신중한 프로토콜 설계와 지역적 신뢰 관계의 사용을 통해 극복될 수 있음을 보여준다. 이 접근 방식은 낮은 지연 시간이 중요하고 참가자들이 기존의 신뢰 관계를 가진 다른 분산 시스템, 예를 들어 은행 간 결제 시스템, 공급망 추적, 기타 금융 인프라 응용에 적용 가능할 수 있다.
프로덕션 시스템에서 RPCA의 배포는 알고리즘의 성능 특성과 견고성을 검증하였다. Ripple 네트워크는 일관된 3-5초의 합의 지연 시간으로 초당 수천 건의 트랜잭션을 처리하며, 이론적 속성이 실제 운영에 효과적으로 번역됨을 입증한다. 네트워크가 계속 발전하고 다양한 운영자의 추가 검증자를 통합함에 따라, 탈중앙화된 합의 시스템이 대규모에서 보안과 성능을 모두 유지할 수 있는 방법의 실용적인 사례를 제공한다.
References
Lamport, L., Shostak, R., and Pease, M. (1982). "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, 4(3):382-401. 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.
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 불가능성 결과는 비동기 시스템에서 합의 알고리즘이 달성할 수 있는 것의 근본적 한계를 확립하여, 실용적인 합의 프로토콜의 설계 공간을 형성하였다.
