리플 프로토콜 합의 알고리즘
Abstract
虽然存在多种针对Byzantine Generals Problem的共识算法，特别是与分布式支付系统相关的算法，但其中许多都因网络中所有节点需要同步通信的要求而导致高延迟问题。在本研究中，我们提出了一种新颖的共识算法，通过利用更大网络内的集体信任子网络来规避这一要求。我们证明，防止Sybil攻击所需的"信任"实际上不是全局性的，而是网络中每个节点的局部性的。
Ripple协议共识算法（RPCA）由所有节点每隔几秒应用一次，以维护网络的正确性和一致性。一旦达成共识，当前账本被视为"关闭"，成为最后关闭的账本（last-closed ledger）。该算法的独特之处在于，它在维持对Byzantine故障的强大保障的同时实现了低延迟共识，使其适用于实时金融结算系统。
Abstract
Byzantine Generals Problem에 대한 여러 합의 알고리즘이 존재하지만, 특히 분산 결제 시스템과 관련하여 많은 알고리즘이 네트워크 내 모든 노드가 동기적으로 통신해야 하는 요구사항으로 인해 높은 지연 시간 문제를 겪고 있다. 본 연구에서는 더 큰 네트워크 내에서 집합적으로 신뢰할 수 있는 하위 네트워크를 활용하여 이 요구사항을 우회하는 새로운 합의 알고리즘을 제시한다. Sybil 공격을 방지하기 위해 필요한 "신뢰"가 실제로는 전역적인 것이 아니라 네트워크 내 각 노드에 대해 지역적임을 보여준다.
Ripple 프로토콜 합의 알고리즘(RPCA)은 네트워크의 정확성과 합의를 유지하기 위해 모든 노드에 의해 수 초마다 적용된다. 합의에 도달하면 현재 원장은 "폐쇄"된 것으로 간주되며 마지막으로 폐쇄된 원장(last-closed ledger)이 된다. 이 알고리즘은 Byzantine 장애에 대한 강력한 보장을 유지하면서 낮은 지연 시간으로 합의를 달성한다는 점에서 독특하며, 실시간 금융 결제 시스템에 적합하다.
Introduction
分布式支付系统必须实现共识算法，以便在存在故障或恶意行为者的情况下及时正确地处理支付。比特币通过工作量证明（proof-of-work）来达成共识，这要求所有节点消耗计算资源来解决密码学难题。虽然这种方法提供了强大的安全保障，但它存在显著的缺点，包括高能耗、低交易吞吐量以及对于高价值交易可能延长至一小时或更长时间的确认延迟。
Ripple协议共识算法提供了一种不需要工作量证明的分布式共识新方法。取而代之的是，网络中的节点通过在几秒内达成共识的投票过程来集体同意交易集合。这种共识机制专门为全球支付网络的需求而设计，在这些网络中，低延迟和高吞吐量对于实际部署至关重要。
RPCA的关键创新在于它不要求网络中的所有节点彼此达成一致。相反，每个节点维护一个唯一节点列表（Unique Node List, UNL），其中包含它信任不会串通的其他节点。只要节点选择的UNL具有足够的重叠，且故障节点低于阈值百分比，网络就会达成共识。这种方法在以秒而非分钟或小时来衡量共识延迟的同时，提供了支付系统所需的安全保障。
Introduction
분산 결제 시스템은 결함이 있거나 악의적인 행위자가 존재하는 상황에서도 적시에 올바르게 결제를 처리하기 위해 합의 알고리즘을 구현해야 한다. 비트코인은 작업 증명(proof-of-work)을 사용하여 합의를 달성하며, 이는 모든 노드가 암호화 퍼즐을 풀기 위해 계산 자원을 소비하도록 요구한다. 이 접근 방식은 강력한 보안 보장을 제공하지만 높은 에너지 소비, 낮은 트랜잭션 처리량, 그리고 고가치 트랜잭션의 경우 1시간 이상까지 늘어날 수 있는 긴 확인 지연 시간을 포함한 상당한 단점이 있다.
Ripple 프로토콜 합의 알고리즘은 작업 증명을 필요로 하지 않는 분산 합의에 대한 새로운 접근 방식을 제공한다. 대신, 네트워크의 노드들은 수 초 내에 합의를 달성하는 투표 과정을 통해 트랜잭션 집합에 대해 집단적으로 동의한다. 이 합의 메커니즘은 실질적인 배포를 위해 낮은 지연 시간과 높은 처리량이 필수적인 글로벌 결제 네트워크의 요구사항에 맞춰 특별히 설계되었다.
RPCA의 핵심 혁신은 네트워크의 모든 노드가 서로 동의할 필요가 없다는 점이다. 대신, 각 노드는 공모하지 않을 것으로 신뢰하는 다른 노드들의 고유 노드 목록(Unique Node List, UNL)을 유지한다. 노드들이 선택한 UNL이 충분한 중첩을 가지고 있고, 임계값 비율 미만의 노드만 결함이 있다면 네트워크는 합의에 도달할 것이다. 이 접근 방식은 합의 지연 시간을 분이나 시간이 아닌 초 단위로 측정하면서 결제 시스템에 필요한 보안 보장을 제공한다.
Definition of Consensus
在分布式系统中，共识是指即使存在故障或恶意参与者，节点网络也能就共享状态达成一致的过程。共识算法必须满足三个基本属性：正确性（没有两个正确的节点做出不同的决定）、一致性（所有正确的节点达成相同的决定）和终止性（所有正确的节点最终都会做出决定）。这些属性确保分布式系统表现得如同一个单一的、可靠的节点。
达成共识的挑战源于分布式系统固有的不可靠性。节点可能崩溃，消息可能延迟或丢失，Byzantine节点可能任意或恶意地行为。Lamport、Shostak和Pease形式化的Byzantine Generals Problem捕捉了这一挑战：当一部分进程可能存在故障且通信不可靠时，一组进程如何能够达成一致？
分布式计算的经典结果确立了共识算法所能达到的基本限制。FLP不可能性结果表明，如果即使一个节点可能失败，在异步系统中没有确定性算法可以保证达成共识。因此，实用的共识算法必须在安全性（永远不会达成错误的共识）和活性（始终保持进展）之间做出权衡。比特币的工作量证明优先考虑安全性而非活性，而RPCA通过在有限时间内完成共识轮次，同时在现实的故障假设下维持强大的安全性保障，从而实现了更适合支付系统的平衡。
Definition of Consensus
분산 시스템에서 합의란 결함이 있거나 악의적인 참가자가 존재하는 상황에서도 노드 네트워크가 공유 상태에 대한 동의에 도달하는 과정을 말한다. 합의 알고리즘은 세 가지 기본 속성을 만족해야 한다: 정확성(두 개의 올바른 노드가 서로 다르게 결정하지 않음), 동의(모든 올바른 노드가 동일한 결정에 도달함), 그리고 종료(모든 올바른 노드가 결국 결정을 내림). 이러한 속성은 분산 시스템이 단일의 신뢰할 수 있는 노드처럼 동작하도록 보장한다.
합의를 달성하는 데 있어서의 도전은 분산 시스템의 본질적인 불안정성에서 비롯된다. 노드가 충돌할 수 있고, 메시지가 지연되거나 손실될 수 있으며, Byzantine 노드는 임의적으로 또는 악의적으로 행동할 수 있다. Lamport, Shostak, Pease가 공식화한 Byzantine Generals Problem은 이 도전을 포착한다: 일부가 결함이 있을 수 있고 통신이 불안정한 상황에서 프로세스 그룹이 어떻게 합의에 도달할 수 있는가?
분산 컴퓨팅의 고전적 결과들은 합의 알고리즘이 달성할 수 있는 것의 근본적 한계를 확립한다. FLP 불가능성 결과는 단 하나의 노드만 실패할 수 있는 비동기 시스템에서도 어떤 결정론적 알고리즘도 합의를 보장할 수 없음을 보여준다. 따라서 실용적인 합의 알고리즘은 안전성(잘못된 합의에 절대 도달하지 않음)과 활성(항상 진행함) 사이에서 절충해야 한다. 비트코인의 작업 증명은 활성보다 안전성을 우선시하는 반면, RPCA는 현실적인 결함 가정 하에서 강력한 안전성 보장을 유지하면서 제한된 시간 내에 합의 라운드를 완료함으로써 결제 시스템에 더 적합한 균형을 달성한다.
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笔交易）。这些限制使得工作量证明不适合许多需要快速结算和高交易量的支付系统应用。
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
Ripple协议共识算法（RPCA）从每个服务器收集所有尚未应用的有效交易作为候选交易开始。然后服务器遵循多轮协议，迭代地就当前账本应用的交易集达成一致。在每一轮中，服务器提出它们认为应该包含在下一个账本中的交易提案。
在每个共识轮次中，服务器将其提案传达给唯一节点列表（UNL）中的其他服务器。然后服务器计算哪些交易出现在阈值百分比以上的提案中。最初，该阈值设置为50%，意味着交易必须出现在服务器UNL中至少一半的提案中才能被考虑进入下一轮。随着共识通过连续轮次的推进，该阈值逐步提高（通常到60%、70%，最终到80%）。
当一笔交易在服务器的UNL中达到80%的绝对多数支持阈值时，它将被包含在该服务器最终共识轮次的提案中。网络中所有达到该阈值的交易被应用到账本上，账本随后被加密哈希和签名。这个新验证的账本成为最后关闭的账本，流程以下一组候选交易重新开始。
共识过程通常在5秒或更短时间内完成，大多数交易只需要一个共识轮次即可达到绝对多数阈值。在一轮中未达成共识的交易仍作为后续轮次的候选。这种设计确保网络持续推进，同时维持强大的安全性保障，因为没有任何交易可以在没有受信任验证者绝对多数支持的情况下被应用到账本上。
Ripple Protocol Consensus Algorithm
Ripple 프로토콜 합의 알고리즘(RPCA)은 각 서버가 아직 적용되지 않은 유효한 트랜잭션을 모두 후보 트랜잭션으로 수집하는 것으로 시작한다. 그런 다음 서버들은 현재 원장에 적용할 트랜잭션 집합에 대한 합의를 향해 반복적으로 작업하는 다중 라운드 프로토콜을 따른다. 각 라운드에서 서버들은 다음 원장에 포함되어야 한다고 생각하는 트랜잭션으로 구성된 제안을 만든다.
각 합의 라운드 동안 서버들은 자신의 고유 노드 목록(UNL)에 있는 다른 서버들에게 제안을 전달한다. 그런 다음 서버들은 어떤 트랜잭션이 임계값 비율 이상의 제안에 나타나는지 계산한다. 처음에 이 임계값은 50%로 설정되며, 이는 트랜잭션이 다음 라운드에서 고려되려면 서버 UNL의 최소 절반 이상의 제안에 나타나야 함을 의미한다. 합의가 연속적인 라운드를 거치면서 이 임계값은 점진적으로 증가한다(일반적으로 60%, 70%, 그리고 최종적으로 80%).
트랜잭션이 서버의 UNL에서 80%의 절대다수 지지 임계값을 달성하면, 해당 트랜잭션은 최종 합의 라운드에 대한 서버의 제안에 포함된다. 네트워크 전체에서 이 임계값에 도달한 모든 트랜잭션은 원장에 적용되고, 원장은 암호화 해시되고 서명된다. 이 새로 검증된 원장이 마지막으로 폐쇄된 원장이 되며, 다음 후보 트랜잭션 집합으로 프로세스가 다시 시작된다.
합의 과정은 일반적으로 5초 이내에 완료되며, 대부분의 트랜잭션은 절대다수 임계값을 달성하기 위해 단 한 번의 합의 라운드만 필요로 한다. 한 라운드에서 합의를 달성하지 못한 트랜잭션은 후속 라운드의 후보로 남는다. 이 설계는 신뢰할 수 있는 검증자들의 절대다수 지지 없이는 어떤 트랜잭션도 원장에 적용될 수 없으므로 강력한 안전성 보장을 유지하면서 네트워크가 지속적으로 진행되도록 보장한다.
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中Byzantine节点少于1/5，则所有正确节点将达成相同的共识决定。
形式化证明通过证明如果两个节点可以达成不同的共识决定，则必定存在某笔交易T出现在一个节点的最终账本中但不在另一个节点的账本中来进行。要发生这种情况，T必须在第一个节点的UNL中获得80%的支持，但在第二个节点的UNL中获得不到80%的支持。然而，考虑到重叠要求和对Byzantine节点的约束，可以证明这种情况是不可能的：如果T在UNL_i中获得80%的支持，它必须在满足重叠条件的任何UNL_j中至少获得60%的支持，经过足够的共识轮次，这将收敛到80%或被两个节点都拒绝。
活性属性——共识最终会达成——来自于包含阈值通过共识轮次确定性地增加这一观察。即使在存在Byzantine节点和网络延迟的情况下，协议也确保由诚实节点绝对多数支持的交易最终会被包含，而缺乏此类支持的交易将被排除。共识的有限时间（通常5秒）为支付系统应用提供了实用的活性保障。
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
唯一节点列表（UNL）是RPCA区别于其他共识算法的基本组件。Ripple网络中的每个节点维护一个UNL，包含它信任不会串通欺骗网络的其他节点。关键的是，这种信任是局部的而非全局的：不同的节点可以有不同的UNL，不需要全局统一的验证者集合。这种设计允许网络在保持去中心化的同时有机地扩展。
UNL作为一种无需工作量证明的Sybil攻击防御机制。在简单的投票系统中，攻击者可以创建许多假名节点以获得不成比例的影响力。通过要求每个节点明确选择它信任的其他节点，RPCA确保创建额外的身份不会带来任何优势，除非这些身份能够说服现有节点将其添加到UNL中。这将Sybil抵抗的问题从计算支出转移到了声誉和信任关系上。
为使网络正确运行，UNL必须按照形式化分析中所述选择具有足够重叠的列表。在实践中，这意味着虽然每个节点运营者在选择UNL方面拥有自主权，但必须确保其列表中包含网络其他部分也信任的验证者。Ripple提供了一个由多元化实体运营的验证者组成的默认UNL，但节点运营者可以根据自己的信任评估自由修改此列表。
UNL机制还提供了一条通向渐进式去中心化的自然路径。在网络的早期阶段，更集中的验证者集合可能更适合确保稳定性和可靠性。随着网络的成熟和更多多元化运营者证明其可信度，UNL可以演变为包含更广泛的验证者集合，在不损害安全属性的情况下增强网络的韧性和去中心化程度。
Unique Node Lists
고유 노드 목록(UNL)은 RPCA를 다른 합의 알고리즘과 구별하는 근본적인 구성 요소이다. Ripple 네트워크의 각 노드는 네트워크를 속이기 위해 공모하지 않을 것으로 신뢰하는 다른 노드들로 구성된 UNL을 유지한다. 중요한 점은 이 신뢰가 전역적이 아닌 지역적이라는 것이다: 서로 다른 노드가 서로 다른 UNL을 가질 수 있으며, 전역적으로 합의된 검증자 집합을 요구하지 않는다. 이 설계는 탈중앙화를 유지하면서 네트워크가 유기적으로 확장될 수 있게 한다.
UNL은 작업 증명 없이 Sybil 공격 방지 메커니즘 역할을 한다. 순진한 투표 시스템에서 공격자는 불균형적인 영향력을 얻기 위해 많은 가명 노드를 생성할 수 있다. 각 노드가 신뢰하는 다른 노드를 명시적으로 선택하도록 요구함으로써, RPCA는 해당 신원이 기존 노드를 설득하여 UNL에 추가될 수 없는 한, 추가 신원을 생성하는 것이 아무런 이점을 제공하지 않도록 보장한다. 이것은 Sybil 저항의 문제를 계산적 지출에서 평판과 신뢰 관계로 전환시킨다.
네트워크가 올바르게 기능하기 위해서는 형식적 분석에서 설명한 것처럼 UNL이 충분한 중첩을 갖도록 선택되어야 한다. 실제로 이것은 각 노드 운영자가 UNL 선택에 자율성을 가지면서도 네트워크의 다른 부분에서도 신뢰하는 검증자를 포함하도록 보장해야 함을 의미한다. Ripple은 다양한 주체가 운영하는 검증자로 구성된 기본 UNL을 제공하지만, 노드 운영자는 자체 신뢰 평가에 따라 이 목록을 자유롭게 수정할 수 있다.
UNL 메커니즘은 또한 점진적 탈중앙화를 향한 자연스러운 경로를 제공한다. 네트워크 초기 단계에서는 안정성과 신뢰성을 보장하기 위해 보다 중앙화된 검증자 집합이 적절할 수 있다. 네트워크가 성숙하고 더 다양한 운영자들이 신뢰성을 입증함에 따라, UNL은 보안 속성을 타협하지 않으면서 네트워크의 회복력과 탈중앙화를 높이는 더 넓은 검증자 집합을 포함하도록 진화할 수 있다.
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选择和网络运营的推荐最佳实践提供了参考。完整的模拟代码已公开发布，以便进行独立验证和进一步研究。
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
与比特币的工作量证明共识相比，RPCA为支付系统应用提供了几个显著优势。最值得注意的是，共识延迟从40-60分钟（高价值比特币交易通常建议的时间）减少到约5秒。这一改进使RPCA适用于需要近乎即时结算的销售点和其他应用。此外，RPCA与工作量证明相比所需的计算资源极少，消除了与比特币挖矿相关的大量能源消耗。
然而，这些优势伴随着不同的信任假设。比特币的安全性仅依赖于没有攻击者控制网络计算能力50%以上的假设，而RPCA要求节点选择具有足够重叠的UNL，并且Byzantine节点不超过这些UNL内的阈值。这将部分做出审慎信任决策的责任转移给了节点运营者。在实践中，对于参与机构拥有现有信任关系的许多支付系统用例，这种权衡是可以接受的。
网络拓扑和UNL选择策略显著影响共识系统的属性。所有节点在UNL中包含相同验证者的高度集中化拓扑最大化了安全性，但如果这些验证者不可用，可能会降低活性。相反，UNL重叠最小的高度去中心化拓扑可能改善活性，但如果重叠变得过于稀疏，则存在共识失败的风险。找到最佳平衡需要仔细考虑特定的部署场景和风险承受能力。
未来的研究可以探索在最大化去中心化的同时自动维护重叠要求的自适应UNL选择算法、节点根据观察到的验证者行为动态调整UNL的机制，以及可以容忍更高比例Byzantine节点的共识算法扩展。这些增强可以进一步提高RPCA在大规模分布式支付系统中的鲁棒性和适用性。
Discussion
비트코인의 작업 증명 합의와 비교하여, RPCA는 결제 시스템 응용에 여러 가지 중요한 이점을 제공한다. 가장 주목할 만한 것은 합의 지연 시간이 40-60분(고가치 비트코인 트랜잭션에 일반적으로 권장되는 시간)에서 약 5초로 단축된다는 점이다. 이 개선으로 RPCA는 즉각적인 결제가 필요한 판매 시점(POS) 및 기타 응용에 적합해진다. 또한 RPCA는 작업 증명에 비해 최소한의 계산 자원을 필요로 하여, 비트코인 채굴과 관련된 막대한 에너지 소비를 제거한다.
그러나 이러한 장점에는 다른 신뢰 가정이 수반된다. 비트코인의 보안이 어떤 공격자도 네트워크 계산 능력의 50% 이상을 통제하지 못한다는 가정에만 의존하는 반면, RPCA는 노드들이 충분한 중첩을 가진 UNL을 선택하고 Byzantine 노드가 이 UNL 내에서 임계값을 초과하지 않을 것을 요구한다. 이것은 노드 운영자에게 신중한 신뢰 결정을 내릴 일부 책임을 전가한다. 실제로 이 절충은 참여 기관이 기존의 신뢰 관계를 가진 많은 결제 시스템 사용 사례에서 수용 가능하다.
네트워크 토폴로지와 UNL 선택 전략은 합의 시스템의 속성에 상당한 영향을 미친다. 모든 노드가 UNL에 동일한 검증자를 포함하는 고도로 중앙화된 토폴로지는 안전성을 최대화하지만, 해당 검증자가 사용 불가능해지면 활성이 감소할 수 있다. 반대로, 최소한의 UNL 중첩을 가진 고도로 탈중앙화된 토폴로지는 활성을 개선할 수 있지만, 중첩이 너무 희박해지면 합의 실패의 위험이 있다. 최적의 균형을 찾으려면 특정 배포 시나리오와 위험 허용 범위를 신중하게 고려해야 한다.
향후 연구는 탈중앙화를 최대화하면서 중첩 요구사항을 자동으로 유지하는 적응적 UNL 선택 알고리즘, 관찰된 검증자 행동에 기반하여 노드가 동적으로 UNL을 조정하는 메커니즘, 그리고 더 높은 비율의 Byzantine 노드를 허용할 수 있는 합의 알고리즘의 확장을 탐구할 수 있다. 이러한 개선은 대규모 분산 결제 시스템에 대한 RPCA의 견고성과 적용 가능성을 더욱 향상시킬 수 있다.
Conclusion
Ripple协议共识算法代表了支付系统分布式共识的重要进步。通过利用集体信任的子网络而非要求所有节点之间的全局一致，RPCA在维持对Byzantine故障的强大保障的同时，在几秒内达成共识。形式化分析表明，只要UNL以足够的重叠选择且Byzantine节点保持在阈值以下，网络将达成正确的共识而不会出现分叉。
本研究的实际意义超越了Ripple支付网络。RPCA表明，共识延迟与安全保障之间的传统权衡可以通过精心的协议设计和局部信任关系的使用来克服。这种方法可能适用于其他低延迟至关重要且参与者拥有现有信任关系的分布式系统，如银行间结算系统、供应链跟踪以及其他金融基础设施应用。
RPCA在生产系统中的部署验证了算法的性能特征和鲁棒性。Ripple网络以一致的3-5秒共识延迟处理每秒数千笔交易，证明了理论属性有效地转化为实际运营。随着网络继续演进并纳入来自多元化运营者的额外验证者，它提供了一个去中心化共识系统如何在规模上同时维持安全性和性能的实际案例。
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. 这篇开创性论文形式化了在具有故障组件的分布式系统中达成共识的问题，并建立了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不可能性结果确立了异步系统中共识算法所能达到的基本限制，塑造了实用共识协议的设计空间。
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 불가능성 결과는 비동기 시스템에서 합의 알고리즘이 달성할 수 있는 것의 근본적 한계를 확립하여, 실용적인 합의 프로토콜의 설계 공간을 형성하였다.
