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