الگوریتم توافقی پروتکل ریپل (Ripple)

با اینکه الگوریتم‌‌های توافقی زیادی برای مشکل عمومی بیزانتین (Byzantine) وجود دارند که اختصاصا به سیستم‌‌های پرداخت توزیعی مربوط می‌‌شوند، افراد زیادی از رکود ایجاد شده به وسیله این نیاز که تمام نودهای درون شبکه باید به صورت همزمان با هم در ارتباط باشند، ضرر می‌‌کنند.
در این فعالیت، ما الگوریتم توافقی جدیدی ارائه می‌‌کنیم که این نیازها را با استفاده از تحت شبکه‌‌های مطمئن در شبکه‌‌ای بزرگ‌تر برطرف می‌‌کند. ما نشان می‌‌دهیم که اعتماد مورد نیاز این تحت شبکه ها در حقیقت حداقل است و می‌‌توان آن را با انتخاب اصولی اعضای نود باز هم کاهش داد. به علاوه ما نشان می‌‌دهیم که اتصال حداقلی برای حفظ توافق در کل شبکه نیاز است. نتیجه یک الگوریتم توافقی با رکود پایین است که همچنان قدرت مقابل اختلالات بیزانتین را حفظ می‌‌کند. ما این الگوریتم را در تجسم آن در پروتکل ریپل ارائه می‌‌کنیم.

0 94

الگوریتم توافقی پروتکل ریپل

1- مقدمه

در سال‌‌های اخیر علاقه و تحقیق در سیستم‌‌های توافقی توزیعی به طرز قابل توجهی افزایش یافته و تمرکز اصلی بر روی شبکه‌‌های پرداخت توزیعی بنا شده است. چنین شبکه‌‌هایی تراکنش‌‌های سریع و کم‌‌هزینه که توسط یک منبع متمرکز کنترل نمی‌‌شوند را ممکن می‌‌کنند. در حالی‌‌که مزایای اقتصادی و بازگشت چنین سیستمی، مستلزم انجام تحقیقات بیشتر هم می‌‌باشد، این فعالیت بیشتر بر روی چالش‌‌های فنی که پیش روی سیستم‌‌های پرداخت توزیعی وجود دارد متمرکز شده است. با اینکه این مشکلات متنوع هستند، ما آن‌‌ها را به سه دسته اصلی طبقه بندی می‌‌کنیم: صحت، توافق، سودمندی.

منظور ما از صحت این است که این موضوع برای توانایی یک سیستم توزیعی در تمایز بین تراکنش صحیح و دارای تقلب ضروری می‌‌باشد. در تنظیمات معتبر سنتی، این موضوع از طریق اعتماد بین شرکت‌‌ها و امضاهای رمزنگاری شده که تراکنش را تضمین می‌‌کند صورت می‌‌گیرد. اما در سیستم‌‌های توزیعی چنین اعتمادی وجود ندارد زیرا ممکن است هویت هیچ کدام از اعضای شبکه مشخص نباشد. بنابراین، باید روش‌‌های جایگزین دیگری برای موضوع صحت به کار گرفته شود.

توافق به مشکل نگهداری یک واقعیت جهانی در مواجهه با سیستم حسابداری غیرمتمرکز مربوط می‌‌شود. در حالیکه این مشکل به مشکل صحت شباهت زیادی دارد، تفاوت آن‌‌ها بین این واقعیت است که یک کاربر مخرب شبکه ممکن است نتواند تراکنش تقلبی ایجاد کند، اما ممکن است بتواند چند تراکنش صحیح بدون ارتباط با یکدیگر ایجاد کرده و با ترکیب آن ها، یک حرکت فریب‌‌آمیز ترتیب دهد. به عنوان مثال یک کاربر مخرب ممکن است با سرمایه کافی برای یک خرید، دو خرید همزمان و جدا از هم انجام دهد.

بنابراین هر تراکنش به خودی خود صحیح است اما اگر به صورت همزمان و به گونه ای که شبکه توزیعی آن را به صورت کلی تشخیص ندهد صورت بگیرد، مشکل واضحی ایجاد خواهد شد که معمولا آن را با عبارت “مشکل دو هزینه ای” نامگذاری می‌‌کنند. بنابراین مشکل توافق را می‌‌توان به عنوان نیازی که فقط یک مجموعه تراکنش جهانی در شبکه وجود دارد خلاصه کرد.

سودمندی مشکل نسبتا کوچکتری می‌‌باشد و ما آن را به عنوان “مفید بودن” سیستم پرداخت توزیعی تعریف می‌‌کنیم اما در عمل معمولا به رکود سیستم خلاصه می‌‌شود. یک سیستم توزیعی که از نظر صحت و توافق مشکلی نداشته اما نیازمند یک سال دیگر برای پردازش تراکنش‌‌ها باشد، قطعا یک سیستم غیرقابل‌‌اعتماد خواهد بود. جنبه‌‌های اضافی سودمندی ممکن است شامل سطوحی از نیروی رایانشی لازم برای شرکت در پروسه‌‌های توافق و صحت یا کیفیت فنی لازم برای یک کاربر نهایی در اجتناب از فریب در شبکه باشد.

بسیاری از این مسائل خیلی قبل‌‌تر از ظهور سیستم‌‌های توزیع کامپیوتری مورد بررسی قرار گرفته‌‌ و با عبارت “مشکل ژنرال بیزانتین” نامگذاری شده‌‌اند . در این مشکل، گروهی از ژنرال ها هر کدام بخشی از ارتش را کنترل می‌‌کنند و باید در حمله و ارسال پیام‌‌رسان‌‌ها به یکدیگر هماهنگ باشند. از آنجایی که ژنرال‌‌ها در محدوده ناآشنا و متعلق به دشمن حضور دارند، شاید پیام‌‌رسان‌‌ها به مقصد خود نرسند (دقیقا مثل نودها در یک شبکه توزیعی که ممکن است با مشکل مواجه شوند یا به جای پیام مورد نظر، داده های خرابی ارسال کنند). یک جنبه اضافی از این مشکل این است که برخی ژنرال‌‌ها ممکن است خائن باشند یا علیه هم توطئه کنند و پیام‌‌ها به صورت غلط دریافت شوند. در این حالت ژنرال های وفادار محکوم به انجام خطا هستند (دقیقا مثل اعضای مخرب سیستم توزیعی که ممکن است بخواهند سیستم را مجبور به پذیرش تراکنش های فریب آمیز کنند یا بخواهند نسخه های مختلفی از تراکنش های صحیح را ایجاد کنند که سبب وقوع مشکل دو هزینه ای شود). بنابراین یک سیستم پرداخت توزیعی باید از نظر مواجهه با اختلالات استاندارد و همچنین این مشکل بیزانتنین مقاوم باشد، از چند منبع در شبکه منشا بگیرد و با کمک این منابع هماهنگی خود را صورت دهد.

در فعالیت فعلی ما یک پیاده‌‌سازی سیستم پرداخت مشخص را بررسی می‌‌کنیم؛ پروتکل ریپل. ما روی الگوریتم‌‌هایی تمرکز می‌‌کنیم که به منظور اهداف صحت، توافق و سودمندی نوشته شده اند و نشان می‌‌دهیم که تمامی آن‌‌ها محقق شده اند (در آستانه‌‌های تحمل و ضروری که به خوبی مشخص هستند). به علاوه ما کدی را فراهم می کنیم که پروسه توافقی با اندازه شبکه قابل پارامتری شدن (parameterizable)، تعداد کاربران مخرب و رکودهای ارسال پیام را شبیه‌‌سازی می‌‌کنند.

1. تعاریف، رسمی‌‌سازی و کارهای قبلی

ما با تعریف اجزای پروتکل ریپل آغاز می‌‌کنیم. به منظور اثبات صحت، توافق و ویژگی‌‌های سودمندی ما ابتدا این ویژگی‌‌ها را به درون قواعد کلی وارد می‌‌کنیم. این ویژگی‌‌ها وقتی که همراه با یکدیگر قرار می‌‌گیرند، مفهوم توافق را شکل می‌‌دهند: وضعیتی که کدام نود شبکه به توافق صحیح می‌‌رسند. سپس ما برخی از نتایج قبلی مرتبط با الگوریتم‌‌های توافقی را برجسته کرده و نهایتا اهداف توافقی برای پروتکل ریپل در چارچوب رسمی خود را بیان می‌‌کنیم.

1.1 اجزای پروتکل ریپل

ما با توصیف شبکه ریپل و تعریف واژه‌‌های زیر شروع می‌‌کنیم:

  • سرور: سرور نهاد مجری نرم افزار ریپل سرور است که در پروسه توافقی شرکت می‌‌کند (بر خلاف نرم افزار مشتری ریپل که فقط به کاربر اجازه ارسال و دریافت سرمایه را می‌‌دهد).
  • لجر: لجر یا دفتر کل تاریخچه‌‌ای از میزان ارز در هر حساب کاربری بوده و نمایانگر “حقیقت بنیادی” شبکه است. لجر مکررا با تراکنش‌‌هایی که با موفقیت از پروسه توافقی عبور می‌‌کنند به‌‌روز می‌‌شود.
  • لجر آخرین (Last-Closed): لجر آخرین، جدیدترین لجری است که در پروسه توافقی به تصویب رسیده و بنابراین بیانگر وضعیت فعلی شبکه می‌‌باشد.
  • لجر باز: لجر باز وضعیت عملیاتی فعلی یک نود است (هر نود لجر باز خود را حفظ می کند). تراکنش‌‌های آغاز شده به وسیله کاربر نهایی از یک سرور در لجر باز همان سرور به کار گرفته می‌‌شوند اما تراکنش‌‌ها تا زمانی که از درون پروسه توافقی عبور نکرده‌‌اند، نهایی نیستند و فقط در این زمان است که لجر آخرین ایجاد می‌‌شود.
  • لیست منحصر به فرد نود (UNL): هر سرور، S، یک لیست منحصر به فرد نود را حفظ می‌‌کند که مجموعه‌‌ای از دیگر سرورها می باشد که صف های S در هنگام توافق دارند. فقط آرای دیگر اعضای UNL از s در هنگام تعیین توافق در نظر گرفته می‌‌شود (بر خلاف هر نود در شبکه). بنابراین UNL نمایانگر مجموعه‌‌ای از شبکه است که به صورت مجموعه‌‌ای در نظر گرفته می‌‌شود و به وسیله s تایید اعتبار شده تا در تلاش برای فریب شبکه دستخوش تغییر نشود. توجه داشته باشید که مفهوم اعتبار نیازمند تک تک اعضای UNL نیست (بخش 3.2 را ببینید).
  • پیشنهاد کننده: تمام سرورها می توانند تراکنش‌‌ها را پخش کرده تا شامل پروسه توافقی شوند و هر سرور تلاش می‌‌کند تا وقتی که یک دور توافقی جدید آغاز می‌‌شود، هر تراکنش معتبر را در بر بگیرد. هر چند طی پروسه توافقی، فقط پیشنهادهای سرور در UNL یک سرور s توسط s در نظر گرفته می‌‌شود.

1.2 رسمی‌‌سازی (Formalization)

ما از واژه غیر معیوب برای نودهایی در شبکه استفاده می‌‌کنیم که بدون ایراد فعالیت می‌‌کنند. در عوض یک نود معیوب نودی است که دستخوش ایرادات شده و ممکن است درست (به واسطه خرابی داده ها، خطاهای پیاده‌‌سازی و غیره) یا مخرب (ایرادهای بیزانتین) باشد. ما مفهوم تایید اعتبار یک تراکنش را به یک مشکل تصمیم‌‌گیری باینری ساده تبدیل می‌‌کنیم: هر نود باید از اطلاعاتی که با مقادیر 0 و 1 به آن داده می‌‌شود تصمیم‌‌گیری کند.

همانند چیزی که در تحقیقات آتیا، دولف و گیل در سال 1984 آمده، ما توافق را بر اساس این سه اصل تعریف می‌‌کنیم:

1- (C1): هر نود غیر معیوب در زمان محدودی تصمیم می‌‌گیرد.

2- (C2): تمام نودهای غیر معیوب به مقادیر مشابه تصمیم‌‌گیری می‌‌رسند.

3- (C3): صفر  و یک برای تمام نودهای غیر معیوب، مقادیری ممکن ‌‌هستند. (این موضوع راه حلی جزیی در تمام نودهایی را حذف می‌‌کند که صرف نظر از اطلاعاتشان بین 0 یا 1 تصمیم گیری می‌‌کنند).

1.3 الگوریتم‌‌های توافقی موجود

تحقیقاتی بر روی الگوریتم‌‌هایی که در مواجهه با ایرادهای بیزانتین به توافق می‌‌رسند صورت گرفته است. این فعالیت‌‌های قبلی شامل گسترش مواردی که تمام شرکت کنندگان درون شبکه از قبل نمی‌‌دانستند می‌‌شد و در این موارد پیام‌‌ها بدون هماهنگی ارسال می‌‌شود (هیچ محدودیتی در میزان زمانی که هر نود برای رسیدن به توافق می خواهد وجود ندارد) و همچنین توصیفی برای تفاوت بین توافق ضعیف و قوی وجود دارد.

یک نتیجه مرتبط با فعالیت قبلی بر روی الگوریتم‌‌های توافقی این است که فیشر، لینچ و پترسون در سال 1985 اثبات می‌‌کنند در مورد ناهماهنگی، بی پایانی همیشه برای یک الگوریتم توافقی ممکن خواهد بود، حتی اگر یک پروسه معیوب وجود داشته باشد. این موضوع ضرورت بحث مبتنی بر زمان را مشخص می‌‌کند تا از همگرایی تضمین حاصل شود (یا حداقل بازگویی مکرر ناهمگرایی). ما این بحث ها را برای پروتکل ریپل در بخش 3 توصیف می‌‌کنیم.

قدرت یک الگوریتم توافقی معمولا به عنوان کسری از پروسه‌‌های معیوب که می‌‌تواند تحمل کند اندازه‌‌گیری می‌‌شود. قابل اثبات است که هیچ راه حلی برای مشکل ژنرال های بیزانتین نمی‌‌تواند بیش از n-1)/3) عیب بیزانتین یا 33 درصد کل فعالیت مخرب شبکه را تحمل کند. هر چند این راه حل نیازمند صحت قابل تایید پیام‌‌های دریافت‌‌شده بین نودها نمی‌‌باشد (امضاهای دیجیتالی). اگر یک تضمین روی پیام های غیر قابل جعل ممکن باشد، الگوریتم ها با تحمل خطای بسیار بالاتری از نظر هماهنگی فعالیت می‌‌کنند.

الگوریتم‌‌های فراوانی با پیچیدگی بالاتر برای توافق بیزانتین در موارد ناهماهنگ ارائه شده است.و FaB Paxos تعداد n−1)/5) اختلال در یک شبکه ای با n نود را تحمل خواهد کرد که مساوی با 20 درصد کل نودهای درون شبکه می‌‌باشد. آتیا، دویف و گیل یک الگوریتم فازی برای موارد ناهماهنگ معرفی می‌‌کنند که می‌‌تواند تعداد (n−1)/4 اختلال یا 25 درصد کل شبکه را تحمل کند. در نهایت آلچیری و همکاران در سال 2008 ، BFT-CUP را معرفی می‌‌کنند که حتی با وجود شرکت‌‌کنندگان نامشخص و محدوده حداکثری از تعداد n-1)/3) اختلال، به توافق بیزانتین در موارد ناهماهنگ می‌‌رسد. اما محدودیت‌‌های اضافی در اتصال با شبکه زیرین آن وجود خواهد داشت.

1.4 اهداف توافقی رسمی

هدف ما در این کار نشان دادن این موضوع است که الگوریتم توافق به وسیله پروتکل ریپل در هر لجر آخرین به توافق خواهد رسید (حتی اگر توافق جز کوچکی از کل تراکنش ها باشد) و توافق جزیی حتی در مواجهه با اختلالات بیزانتین، فقط با احتمال مشخصی حاصل خواهد شد.

از آنجایی که هر نود درون شبکه فقط روی پیشنهادات نودهای معتبر رای می‌‌دهد (نودهای دیگر در UNL خودشان) و هر نود ممکن است UNLهای متفاوتی داشته باشد، ما نشان می‌‌دهیم که صرف نظر از عضویت UNL، فقط یک توافق در بین تمام نودها حاصل خواهد شد. همچنین این هدف با عنوان جلوگیری از منشعب‌‌شدن در شبکه شناخته می‌‌شود: شرایطی که در آن 2 مجموعه گسسته از نودها به صورت مجزا به توافق می‌‌رسند و 2 لجر آخرین به وسیله نودها در هر مجموعه نود مشاهده می‌‌شود.

در آخر ما نشان خواهیم داد که پروتکل ریپل در مواجهه با تعداد n− 1)/5) اختلال می‌‌تواند به این اهداف برسد که این موضوع مهمترین نتیجه ما نیست اما همچنین نشان خواهیم داد که پروتکل ریپل، ویژگی‌‌های مطلوب دیگری هم دارد که باعث بهبود سودمندی آن می‌‌شود.

2. الگوریتم توافقی ریپل

الگوریتم توافقی پروتکل ریپل (RPCA) هر ثانیه توسط تمام نودها به کار گرفته می‌‌شود تا صحت و توافق شبکه حفظ شود. وقتی که توافق حاصل شد، لجر فعلی به عنوان بسته شده در نظر گرفته و تبدیل به لجر آخرین می‌‌شود. با فرض اینکه الگوریتم توافقی موفقیت آمیز باشد و هیچ انشعابی در شبکه وجود نداشته باشد، لجر آخرین که از سوی تمام نودهای درون شبکه حفظ می‌‌شود، یکسان خواهد بود.

2.1 تعریف

RPCA در چند مرحله فعالیت می‌‌کند. در هر مرحله:

  • در ابتدا هر سرور تمام تراکنش‌‌های معتبر قبل از آغاز مرحله توافقی که تا به حال به کار گرفته نشده را صورت می‌‌دهد (این موضوع شاید شامل تراکنش‌‌های آغاز شده از سوی کاربران نهایی سرور، تراکنش‌‌های پروسه توافق قبلی و غیره شود) و آن ها را به صورت عمومی و لیستی تبدیل می‌‌کند که با نام “مجموعه داوطلب” شناخته می‌‌شود.
  • سپس هر سرور مجموعه‌‌های داوطلب را در UNL خودش ترکیب می‌‌کند و روی صحت تمام تراکنش‌‌ها رای می‌‌دهد.
  • تراکنش‌‌هایی که بیش از حداقل درصد رای های “بله” را دریافت کنند به مرحله بعدی می‌‌روند اما تراکنش‌‌هایی که رای کافی دریافت نکنند یا حذف و یا به مجموعه داوطلب آغازین در لجر بعدی وارد می‌‌شوند.
  • مرحله نهایی توافق نیازمند حداقل 80 درصد موافقت UNL سرور بر روی یک تراکنش می‌‌باشد. تمام تراکنش‌‌هایی که به این نیاز برسند به لجر اضافه می‌‌شوند و این لجر بسته و به جدیدترین لجر آخرین تبدیل می‌‌شود.

2.3 صحت

با توجه به میزان حداکثری اختلالات بیزانتین، برای رسیدن به صحت باید نشان داد که تایید یک تراکنش فریب‌‌آمیز طی توافق غیرممکن خواهد بود، مگر اینکه تعداد نودهای معیوب بیشتر از حد تحمل باشد. سپس اثبات صحت RCPA مطرح می‌‌شود: از آنجایی که یک تراکنش فقط زمانی تایید می‌‌شود که 80 درصد یک سرور UNL با آن موافق باشد، تا زمانی که این 80 درصد UNL درست باشد، هیچ تراکنش فریب‌‌آمیزی تایید نخواهد شد. بنابراین برای یک UNL با n نود در شبکه، پروتکل توافقی صحت را حفظ خواهد کرد، اگر:

f ≤ (n−1)/5   (1

که در آن f تعداد اختلالات بیزانتین می‌‌باشد. در حقیقت حتی در مواجهه با تعداد n−1)/5+1) اختلال بیزانتین، از نظر فنی صحت همچنان حفظ می‌‌شود. پروسه توافقی مختل خواهد شد اما هنوز هم تایید یک تراکنش فریب‌‌آمیز غیرممکن نخواهد بود. همچنین تعداد 4n+1)/5) اختلال بیزانتین برای تایید یک تراکنش غلط لازم خواهد بود. ما این محدوده دوم را محدوده‌‌ای برای صحت ضعیف و محدوده اول را محدوده‌‌ای برای صحت قوی می‌‌نامیم.

باید در نظر داشت که تمام تراکنش‌‌های فریب‌‌آمیز، خطرناک نیستند، حتی اگر طی توافق تایید شوند. برای مثال اگر یک کاربر سرمایه های دو هزینه ای را در دو تراکنش صورت دهد و حتی اگر هر دو تراکنش هم در پروسه توافق تایید شوند، بعد از اینکه تراکنش اول اضافه شد تراکنش دومی با خطا مواجه خواهد شد زیرا سرمایه‌‌ها دیگر در دسترس نیستند. این قدرت به واسطه این موضوع است که تراکنش‌‌ها به صورت قطعی اضافه می‌‌شوند و این که توافق، تمام نودهای درون شبکه را با قوانین قطعی به مجموعه مشابهی از تراکنش‌‌ها اضافه می‌‌کند.

برای یک تحلیل نسبتا متفاوت، فرض کنیم احتمال هر نود برای تبانی و ورود به یک فعالیت فریب‌‌آمیز Pc باشد، سپس احتمال صحت اینگونه خواهد شد:

2)

الگوریتم توافقی ریپل

این احتمال بیانگر این موضوع است که اندازه فعالیت فریب آمیز همچنان زیر آستانه اختلال بیزانتین باقی خواهد ماند و با Pc مشخص می‌‌شود. از آنجایی که احتمال یک توزیع دوجمله ای است، مقادیر بالاتر از 20 درصد Pc نتیجه ای فریب آمیز بزرگ‌تر از 20 درصد شبکه در بر خواهند داشت و پروسه توافق را ناموفق می‌‌کنند. در عمل، یک UNL به صورت تصادفی انتخاب نمی‌‌شود بلکه با قصد به حداقل رساندن Pc صورت می‌‌گیرد. از آنجایی که نودها مستقل نیستند و از نظر رمزنگاری قابل تشخیص می‌‌باشند، انتخاب یک UNL از نودهای دارای ترکیبی از قاره ها، ملت ها، صعنت ها، ایدئولوژی ها و غیره سبب تولید مقادیر پایینتر از 20 درصد Pc می‌‌شود.

به عنوان مثال احتمال لیگ ضد رسوایی و کلیسای تعمید دهنده وستبرو (Anti-Defamation League and the Westboro Baptist Church) برای فریب شبکه قطعا بسیار بسیار پایینتر از 20 درصد است. حتی اگر UNL، Pc نسبتا بزرگی داشته باشد، مثلا 15 درصد، احتمال صحت حتی با وجود 200 نود در UNL بسیار بالا خواهد بود، چیزی در حدود 97.8 درصد.

یک ارائه گرافیکی از نحوه احتمال مقیاس های صحت به عنوان عملکردی از اندازه UNL برای مقادیر متفاوت Pc در شکل 1 به تصویر کشیده شده‌‌است. توجه داشته باشید که محور عمودی نمایانگر احتمال فریب در توافق می‌‌باشد و بنابراین مقادیر پایینتر احتمال بالاتری از موفقیت توافق را نشان می‌‌دهند. همانطور که در تصویر می‌‌توان مشاهده کرد، حتی با یک Pc به بزرگی 10 درصد، اگر UNL از 100 نود عبور کند، احتمال اینکه توافق ناموفق شود بسیار پایین می‌‌آید.

3.3 توافق

برای رسیدن به نیازهای توافقی باید نشان داد که تمام نودهای غیرمعیوب صرف نظر از UNLهایشان، به توافق در مجموعه مشابهی از تراکنش‌‌ها می‌‌رسند. از آنجایی که UNL ممکن است ها برای هر سرور متفاوت باشد، توافق به صورت همیشگی توسط اثبات صحت، قطعی نیست. به عنوان مثال اگر هیچ محدودیتی بر روی عضویت UNL وجود نداشته باشد و اندازه UNL هم بزرگ‌‌تر از 0.2∗ntotal نباشد (ntotal تعداد نودهای کل شبکه است)، در این صورت یک انشعاب ممکن خواهد بود. این موضوع با یک مثال ساده در تصویر 2 آمده است: دو گروه را در گراف UNL فرض کنید، هر کدام ∗ntotal هستند. منظور ما از گروه، مجموعه‌‌ای از نودها است که هر UNL نود، دقیقا مشابه همان مجموعه نودها عمل می‌‌کند. به خاطر اینکه 2 گروه هیچ عضو مشترکی ندارند، برای هر کدام از آن ها رسیدن به یک توافق صحیح و مستقل از یکدیگر ممکن خواهد بود. اگر اتصال دو گروه از 0.2 ∗ntotalبیشتر باشد، انشعاب دیگر ممکن نیست و اختلاف بین دو گروه ممکن است از توافق جلوگیری کند زیرا که رسیدن به 80 درصد آستانه توافق ضروری می‌‌باشد.

الگوریتم توافقی پروتکل ریپل (Ripple)

تصویر2. مثالی از اتصال مورد نیاز برای جلوگیری از انشعاب بین دو گروه UNL

حد بالایی اتصال مورد نیاز برای اثبات اینگونه خواهد بود:

1

UNLi UNLj| ≥ -max(|UNLi|,|UNLj|)∀i, j (3) 5|

این حد بالایی، ساختار گروه مانندی از UNL ها را در نظر می‌‌گیرد، یعنی نودها مجموعه‌‌ای از UNL‌‌ها را شکل می‌‌دهند و دیگر نودها در این مجموعه‌‌ها حضور دارند. این حد بالایی تضمین می‌‌کند که هیچ دو گروهی نتوانند در تراکنش‌‌های متضاد به توافق برسند، زیرا رسیدن به 80 درصد آستانه مورد نیاز برای توافق غیرممکن می‌‌شود. یک حد محکم‌‌تر زمانی ممکن خواهد بود که گوشه‌‌های غیرمستقیم بین UNL‌‌ها هم محاسبه شود. به عنوان مثال اگر ساختار شبکه گروه مانند نباشد، به واسطه درگیری بیشتر UNL های تمام نودها، رسیدن به انشعاب سخت تر می‌‌شود.

در نظر داشتن این موضوع که هیچ فرضی درباره ماهیت نودهای متقاطع وجود ندارد، جالب خواهد بود. عبور دو UNL از یکدیگر ممکن است شامل نودهای معیوب شود اما تا زمانی که اندازه تقاطع بزرگ‌تر از حد مورد نیاز برای تضمین توافق و تعداد کلی نودهای معیوب، کمتر از حد مورد نیاز برای رسیدن به صحت قوی باشد، صحت و توافق حاصل خواهد شد. می توان اینگونه گفت که توافق فقط به اندازه تقاطع‌‌های نود و نه به اندازه تقاطع نودهای غیرمعیوب وابسته است.

3.4 سودمندی

در حالیکه بسیاری از اجزای سودمندی ذهنی هستند، یکی از آن ها همگرایی می‌‌باشد: همان مفهومی که می‌‌گوید پروسه توافقی در زمان محدود به پایان خواهد رسید.

الگوریتم توافقی پروتکل ریپل (Ripple)

تصویر 1. احتمال فریب برای خنثی کردن توافق به عنوان عملکردی از اندازه UNL، برای مقادیر مختلف Pc، احتمال اینکه هر عضو UNL تصمیم به تبانی با دیگران بگیرد، وجود دارد. در اینجا مقادیر پایینتر نمایانگر احتمالا بالاتر موفقیت توافق می‌‌باشد.

3.4.1 همگرایی

ما همگرایی را به عنوان نقطه‌‌ای که در آن RPCA با صحت بالا در لجر به توافق می‌‌رسد تعریف کردیم و این لجر، همان لجر آخرین می‌‌باشد. توجه داشته باشید در حالیکه صحت ضعیف همچنان بیانگر همگرایی الگوریتم می‌‌باشد، همگرایی فقط در موارد جزیی بوده، همانگونه که طرح C3 نقض شده است و هیچ تراکنشی دیگر تایید نخواهد شد. با توجه به نتایج بالا ما می دانیم که صحت قوی همیشه در مواجهه با تعداد (n−1)/5 اختلال بیزانتین قابل دسترسی است. ضمن این که فقط یک توافق در کل شبکه حاصل خواهد شد تا شرایط اتصال UNL محقق شود (معادله 3). تمام مواردی که باقی مانده برای این است که نشان دهد وقتی هر دوی این شرایط محقق شوند، توافق در زمان محدود حاصل می‌‌شود.

از آنجایی که الگوریتم توافقی به خودی خود قطعی است و تعداد مشخصی مرحله دارد، t، پیش از توافق پایان می‌‌یابد و مجموعه فعلی تراکنش‌‌ها، تایید شده یا تایید نشده اعلام می‌‌شوند (حتی اگر در این نقطه هیچ تراکنشی بیش از 80 درصد توافق مورد نیاز را نداشته باشد و توافق فقط توافقی جزیی باشد)، فاکتور محدود کننده برای پایان یافتن الگوریتم، نهفتگی ارتباط بین نودها خواهد بود. به منظور محدود کردن این میزان، زمان پاسخ نودها بررسی می‌‌شود و نودهایی که نهفتگی آن ها بیشتر از حد b رشد کند از کل UNL ها حذف می‌‌شوند. در حالی‌‌که این موضوع تضمین می‌‌کند که توافق با حد بالاتری از tb متوقف خواهد شد، باید بدانیم حدودهایی که برای صحت و توافق توصیف شده اند باید توسط آخرین UNL محقق شوند، زیرا نودهایی که لازم بوده، افت کرده اند. اگر شرایط نگهداری شده برای UNL‌‌های آغازی در تمام نودها به کار گرفته شود اما برخی از نودها به واسطه نهفتگی از شبکه حذف شوند، تضمین‌‌های صحت و توافق به صورت اتوماتیک نگه داشته می‌‌شوند اما باید توسط مجموعه‌‌ای جدید از UNL‌‌ها محقق شوند.

3.4.2 روش‌‌ها و مسائل ذهنی

همانطور که بالاتر توضیح داده شد، یک حد نهفته ذهنی در تمام نودهای دورن شبکه ریپل قرار داده شده تا از همگرایی الگوریتم توافقی اطمینان حاصل شود. به علاوه، روش‌‌ها و مسائل ذهنی دیگری هم وجود دارند که به RPCA سودمندی اضافه می‌‌کنند.

  • پنجره اجباری 2 ثانیه‌‌ای برای تمام نودها وجود دارد تا مجموعه داوطلب نخستین خود در هر مرحله از توافق را ارائه کنند. در حالیکه این موضوع حد پایین‌‌تری از 2 ثانیه به هر مرحله از توافق وارد می‌‌کند، این موضوع از اینکه تمام نودهای با نهفتگی مناسب، قابلیت شرکت در پروسه توافقی را خواهند داشت، اطمینان حاصل می کند.
  • زمانی که آرا برای هر مرحله از توافق در لجر ثبت شد، نودها را می‌‌توان به خاطر رفتارهای مخرب و معمول از شبکه حذف کرد. این موارد نودهایی که به هر تراکنش رای “نه” می دهند و نودهایی که همیشه تراکنش‌‌های غیرمعتبر به توافق ارائه می کنند را شامل می‌‌شود.
  • یک UNL پیش فرض برای تمام کاربران فراهم می‌‌شود که برای حداقل کردن Pc انتخاب شده است و در بخش 3.2 توضیح داده شد. در حالیکه کاربران می‌‌توانند UNL‌‌های شخصی خود را انتخاب کنند، این لیست پیش فرض از نودها تضمین می‌‌کند که حتی تمام کاربران ساده هم در پروسه‌‌ای توافقی شرکت خواهند کرد که صحت و توافق را با احتمال بالا محقق خواهد کرد.
  • یک الگوریتم شناسایی مجزا هم برای اجتناب از انشعاب در شبکه به کار گرفته می‌‌شود. در حالی‌‌که الگوریتم توافقی تایید می‌‌کند که تراکنش‌‌های روی آخرین لجر صحیح هستند، احتمال وجود بیش از یک لجر آخرین در بخش‌‌های مختلف شبکه با اتصال ضعیف را ممنوع نمی‌‌کند. برای تلاش و مشخص کردن رخداد یک جدایی، هر نود اندازه اعضای فعال UNL خود را بررسی می‌‌کند. اگر این اندازه ناگهان از حد آستانه مشخصی پایین‌‌تر آید، ممکن است یک جدایی رخ داده باشد. به منظور جلوگیری از یک مثبت کاذب هنگامی که بخش بزرگی از UNL موقتا نهفته شده، نودها می‌‌توانند اعتبار جزیی منتشر کنند که در این حالت آن ها تراکنش ها را پردازش نمی‌‌کنند، بلکه اعلام می‌‌کنند همچنان در پروسه توافقی شرکت دارند، دقیقا بر عکس پروسه مختلف توافقی که در یک تحت شبکه منقطع رخ می‌‌دهد.
  • در حالی‌‌که به کار گرفتن RPCA در یک مرحله از توافق ممکن خواهد بود، سودمندی را می‌‌توان از مراحل مختلفی به دست آورد و قبل از رسیدن به مرحله پایانی با 80 درصد نیازها، هر مرحله درصد در حال افزایشی از توافق حداقلی مورد نیاز را خواهد داشت. این مراحل شناسایی نودهای نهفته را زمانی ممکن می‌‌سازند که نودهای کمی، وضعیت دشوار نرخ تراکنش شبکه را ایجاد می‌‌کنند. این نودها قادر خواهند بود تا در ابتدا طی مراحل با نیاز پایین ادامه دهند اما سپس عقب می‌‌افتند و با افزایش آستانه مشخص می‌‌شوند. یکی از مراحل توافق، ممکن است موردی باشد که تراکنش های کمی از 80 درصد آستانه عبور کرده و این موضوع ادامه آرام و پایین آمدن نرخ تراکنش کل شبکه را نشان می‌‌دهد.

4. کد شبیه سازی

کد شبیه سازی ارائه شده، بیانگر مرحله‌‌ای از RPCA می‌‌باشد که ویژگی‌‌های قابل پارامتری شدن دارد (تعداد نودهای درون شبکه، نودهای مخرب، نهفتگی پیام‌‌ها و غیره). شبیه ساز در اختلاف کامل آغاز می‌‌کند (نصف نودهای شبکه در ابتدا “بله” و نصف دیگر “نه” می‌‌گویند)، سپس با پروسه توافق ادامه می‌‌دهد، در هر مرحله تعداد آرای بله یا نه در شبکه مشخص می‌‌شود و نودها بر اساس این آرای اعضای UNL تنظیم می‌‌شوند. هنگامی که 80 درصد آستانه محقق شد، توافق حاصل می‌‌شود. ما به خوانندگان توصیه می‌‌کنیم که مقادیر متفاوتی از تعریف در آغاز “Sim.cpp” را امتحان کرده تا با پروسه توافقی تحت شرایط مختلف آشنا شوند.

5- بحث

ما RPCA را توصیف کرده‌‌ایم که شرایط صحت، توافق و سودمندی که قبلتر توضیح دادیم را مشخص می‌‌کند. نتیجه این است که پروتکل ریپل می‌‌تواند تراکنش‌‌های معتبر و ایمنی را در چند ثانیه پردازش کند: مدت زمان مورد نیاز برای تکمیل یک مرحله توافق. این تراکنش‌‌ها قطعا حدود توصیف شده در بخش 3 را تضمین می‌‌کنند که البته اگرچه مهم‌‌ترین موضوعات برای توافق ناهماهنگ بیزانتین نیستند، همگرایی و انعطاف‌‌پذیری سریع در عضویت درون شبکه را ممکن می‌‌سازند. وقتی شرایط را جمع‌‌بندی می‌‌کنیم، این کیفیت‌‌ها به شبکه ریپل اجازه می‌‌دهند تا به عنوان یک شبکه پرداخت کم‌‌هزینه و سریع با امنیت مطلوب و ویژگی‌‌های معتبر فعالیت کند.

در حالی‌‌که ما نشان داده‌‌ایم پروتکل ریپل قطعا هنگام محقق شدن معادله‌‌های 1 و 3 ایمن می‌‌باشد، باید در نظر داشت که این حدها حداکثری هستند و در عمل شبکه باید تحت شرایط بسیار آرام تری ایمنی داشته باشد. همچنین بسیار مهم است که بدانیم رسیدن به این حدها برای خود RPCA دائمی نیست و مدیریت UNL‌‌های کل کاربران را می‌‌طلبد. UNL پیش‌‌فرضی که برای کل کابران ارائه شده در حال حاضر کافی می‌‌باشد اما تغییرات کاربری به UNL باید با دانش نسبت به حدهای بالایی صورت بگیرد. به علاوه به برخی بررسی های ساختار شبکه جهانی نیاز است تا از محقق شدن حد در معادله 3 و اینکه توافق همیشه عملی می‌‌شود، تضمین حاصل شود.

ما باور داریم که RPCA یک قدم قابل توجه رو به جلو در سیستم‌‌های پرداخت توزیعی می‌‌باشد، زیرا نهفتگی پایین، انواع مختلفی از تراکنش های مالی که قبلا با روش‌‌های توافقی با نهفتگی بالاتر، سخت یا غیرممکن بوده اند، را ممکن می‌‌سازد.

6- سپاسگزاری‌‌ها

ریپل‌‌لبز مایل است از تمام افرادی که در توسعه الگوریتم توافقی پروتکل ریپل دخیل بوده‌‌اند تشکر کند. مخصوصا آرتور بریتو به خاطر فعالیتش بر روی مجموعه‌‌های تراکنشی، جد مک کیلب برای مقوله توافقی پروتکل ریپل اصلی و دیوید شوارتس برای فعالیتش روی جنبه اختلال در توافق. ریپل‌‌لبز همچنین می‌‌خواهد از نوح یانگز بابت تلاش‌‌هایش در آماده‌‌سازی و بازبینی این مقاله تشکر کند.

 

 

شاید از این مطالب هم خوشتان بیاید.

ارسال پاسخ

آدرس ایمیل شما منتشر نخواهد شد.