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

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

arXiv:1802.07242  منتشر شده در 20 فوریه 2018.

 

چکیده

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

 

1. مقدمه

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

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

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

“سودمندی” یک مسئله کمی انتزاعی تر است ، که ما آن را عموماً به عنوان “سودمندی” یک سیستم پرداخت گسترده مطرح می کنیم ، اما در عمل اغلب به تأخیردر سیستم خلاصه می شود. یک سیستم گسترده که هم “درستی” را رعایت می کند و هم “توافق” را اما به طور مثال برای پردازش یک معامله به یک سال زمان نیاز دارد ، بدیهی است که یک سیستم پرداخت ناپایدار است. جنبه های جانبی “سودمندی” ممکن است شامل سطح توان محاسباتی مورد نیاز برای شرکت در فرایندهای صحت و توافق یا عملکرد فنی مورد نیاز یک کاربر نهایی برای جلوگیری از کلاهبرداری در شبکه باشد.

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

در این کار ، ما یک اجرای خاص از یک سیستم پرداخت گسترده را تجزیه و تحلیل می کنیم: پروتکل Ripple. ما بر روی الگوریتم های مورد استفاده برای دستیابی به اهداف فوق یعنی درستی ، توافق و سودمندی تمرکز کرده و نشان می دهیم که همه برآورده می شوند (در آستانه های تحمل لازم و از پیش تعیین شده ، که کاملاً شناخته شده اند). علاوه بر این ، ما کدی را ارائه می دهیم که روند توافق عمومی را با اندازه شبکه ، تعداد کاربران مخرب و تأخیرهای ارسال پیام شبیه سازی می کند.

 

2. تعریف ها ، فرم دادن و کارهای قبلی

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

 

2. 1 اجزای پروتکل Ripple

ما توصیف خود را در مورد شبکه موج دار(Ripple) با تعریف اصطلاحات زیر آغاز می کنیم:

• سرور: سرور هر عنصری است که نرم افزار Ripple Server را اجرا می کند (در مقابل نرم افزار Ripple Client که فقط به کاربر امکان ارسال و دریافت وجه را می دهد) ، که در روند توافق عمومی شرکت می کند.
• دفتر ثبت: دفتر ثبت مقدار ارز در حساب هر کاربر است و نشان دهنده “داده مرجع” شبکه است. دفتر به طور مكرر با معاملاتي كه با موفقيت از طريق توافق عمومی عبور مي كنند به روز مي شود.
• دفتر بسته شده اخیر: آخرین دفتری است که توسط فرآیند توافق عمومی به تأیید رسیده است و بنابراین نمایانگر وضعیت فعلی شبکه است.
• دفتر ثبت باز: دفتر ثبت باز وضعیت فعلی گره است (هر گره دفتر باز خود را حفظ می کند). معاملات آغاز شده توسط کاربران نهایی یک سرور معین بر روی دفتر باز آن سرور اعمال می شوند ، اما معاملات تا زمانی که از فرآیند توافق عمومی عبور نکنند ، نهایی محسوب نمی شوند ، در آن زمان دفتر باز به آخرین دفتر بسته شده تبدیل می شود.
• لیست گره های منحصر به فرد (UNL): هر سرور S ، یک لیست گره منحصر به فرد را حفظ می کند ، که مجموعه ای از سرورهای دیگر است که هنگام تعیین توافق عمومی Sآن را درخواست می کند. فقط آرای سایر اعضای UNL  Sدر هنگام تعیین توافق عمومی (بر خلاف هر گره در شبکه) در نظر گرفته می شود. بنابراین UNL زیرمجموعه ای از شبکه را نشان می دهد که در صورت استفاده جمعی ، توسط سرور ” مورد اعتماد” قرار می گیرد تا در تلاش برای کلاهبرداری از شبکه تبانی نکند. توجه داشته باشید که این تعریف “اعتماد” نیازی به اعتماد هر یک از اعضای UNL ندارد (بخش 3.2 را ببینید).
• پیشنهاد دهنده: هر سرور می تواند تراکنش هایی را که در روند توافق عمومی گنجانده می شوند ، پخش کند ، و هر سرور سعی می کند در هر معامله معتبری هنگام شروع دور توافق عمومی جدید ، شرکت کند. در طی فرآیند توافق عمومی ، فقط پیشنهادات سرورها در UNL یک سرور S توسط S مورد بررسی قرار می گیرد.

2.2 فرم دادن

ما از اصطلاح “بی عیب” برای اشاره به گره هایی در شبکه استفاده می کنیم که رفتار صادقانه و بدون خطایی دارند. برعکس ، گره معیوب گره ای است که خطا یا ارور می دهد که این خطا ممکن است صادق (به دلیل خرابی داده ها ، خطاهای پیاده سازی و غیره) یا مخرب (خطاهای بیزانس) باشد. مفهوم اعتبار سنجی یک معامله را به یک مسئله ساده تصمیم گیری باینری(دوگانه) تقلیل می دهیم: هر گره باید از اطلاعاتی که در مورد ارزش 0 یا 1 داده شده تصمیم بگیرد.

مانند Attiya ، Dolev و Gill [3] ما نیز توافق عمومی را بر اساس سهبدیهی زیر بیان می کنیم:

1. (C1): هر گره غیر معیوب در زمان مشخص یک تصمیمی می گیرد.
2. (C2): همه گره های غیر معیوب به مقدار تصمیم یکسانی می رسند.
3. (C3): 0 و 1 هر دو مقدارهای ممکن برای همه گره های غیر معیوب هستند. (این کار راه حل بی فایده را که در آن همه گره ها بدون توجه به اطلاعات ارائه شده 0 یا 1 را انتخاب می کنند حذف می کند).

 

• الگوریتم های توافق عمومی موجود

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

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

قدرت الگوریتم توافق عمومی معمولاً بر اساس کسری از فرایندهای معیوب قابل تحمل اندازه گیری می شود. قابل اثبات است که هیچ راه حلی برای مسئله ژنرال های بیزانتین (که همگام بودن و شرکت کنندگان شناخته شده را در نظر می گیرد) نمی تواند بیش از (n!1)/3  خطای بیزانتین ، یا 33٪ از شبکه را با سوء عمل تحمل کند [2]. با این حال ، این راه حل به اصالت واقعی پیام های ارسالی بین گره ها (امضاهای دیجیتالی) نیاز ندارد. اگر تضمینی در مورد غیرقابل فرار بودن پیام ها امکان پذیر باشد ، الگوریتم هایی با تحمل خطای بسیار بالاتر در حالت همزمان وجود دارند.

چندین الگوریتم با پیچیدگی بیشتر در رابطه با مورد ناهمزمانی برای توافق عمومی بیزانتین ارائه شده است. FaB Paxos [5] مقدار  (n!1)/5 خرابی بیزانتین را در شبکه ای از n گره تحمل می کند ، که میزان تحمل آن تا 20٪ از گره های شبکه است که به طور شرورانه تبانی می کنند. Attiya ، Doyev وGill [3] یک الگوریتم فاز برای مورد ناهمزمانی معرفی می کنند که می تواند (n!1)/4 خرابی یا تا 25٪ از شبکه را تحمل کند. سرانجام ، Alchieri و همکاران ، 2008 [6] BFT-CUP را ارائه می دهند ، که در مورد ناهمزمانی حتی با شرکت کنندگان ناشناخته ، با حداکثر حد تحمل (n!1)/3 شکست ، اما با محدودیت های اضافی در اتصال به شبکه اصلی به توافق عمومی بیزانتین می رسد.

4.2 اهداف رسمی توافق عمومی

هدف ما در این کار این است که نشان دهیم الگوریتم توافق عمومی استفاده شده توسط پروتکل Ripple در هر یک از دفاتر ثبت نزدیک به توافق عمومی می رسد (حتی اگر توافق عمومی مورد نظر، توافق عمومی پیش پا افتاده تمام معاملات رد شده باشد) ، و توافق های عمومی پیش پا افتاده حتی در برابر شکست های بیزانتین تنها با یک احتمال شناخته شده قابل دستیابی هستند.

از آنجا که هر گره در شبکه فقط به پیشنهادات یک مجموعه معتبر از گره ها رأی می دهد (گره های دیگر در UNL آن) ، و از آنجا که هر گره ممکن است UNL متفاوت داشته باشد ، ما همچنین نشان می دهیم که فقط یک توافق در بین همه گره ها حاصل خواهد شد ، صرف نظر از عضویت در UNL این هدف همچنین به عنوان جلوگیری از ایجاد “چنگال” در شبکه شناخته می شود: وضعیتی که در آن دو مجموعه جداگانه از گره ها به طور مستقل به توافق عمومی می رسند و دو دفتر ثبت بسته شده اخیر توسط گره ها در هر مجموعه گره مشاهده می شود. سرانجام ما نشان خواهیم داد که پروتکل Ripple می تواند در مقابله با مشکلات (n!1)/5 به این اهداف دست یابد ، که قوی ترین نتیجه در میان راهکار ها نیست ، اما همچنین نشان خواهیم داد که پروتکل Ripple دارای چندین ویژگی مطلوب دیگر است که تا حد زیادی کاربرد آن را افزایش می دهد.

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

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

• تعاریف

RPCA در دور های مختلف همچنان پیش می رود که در هر دور:

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

2.3درستی

برای دستیابی به “درستی” ، با توجه به مقدار حداکثر شکست های بیزانتین ، باید گفت که تایید یک معامله متقلبانه در حین توافق عمومی امکان پذیر نیست ، مگر اینکه تعداد گره های معیوب از آن حد تحمل تجاوز کنند. پس از آن اثبات درستی RPCA مستقیماً دنبال می شود: از آنجا که یک معامله فقط درصورت موافقت 80٪ UNL سرور با آن تایید می شود ، تا زمانی که 80٪ UNL صادق باشد ، هیچ معامله جعلی تأیید نمی شود. بنابراین برای یک گره UNL با تعداد n گره در شبکه ، پروتکل توافق عمومی “درستی” را تا زمانی حفظ می کند که:

f < (n!1)/5

که در اینجا f تعداد شکست های بیزانتین است. در حقیقت ، حتی در برابر (n!1)/5+1 شکست بیزانیتن، “درستی” هنوز از نظر فنی حفظ می شود. روند توافق عمومی ناموفق خواهد بود ، اما هنوز هم قادر به تایید یک معامله متقلبانه نخواهد بود. در واقع برای تایید یک معامله نادرست میزان (4n+1)/5 شکست بیزانتین لازم است. ما این مورد دوم را مقید به “درستی” ضعیف و اولی را مقید به “درستی” قوی می دانیم.

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

برای یک تجزیه و تحلیل کمی متفاوت ، بگذاریدPc  را احتمال اینکه هر گره تصمیم به تبانی و پیوستن به یک کارتل شیطانی داشته باشد ، فرض کنیم. سپس احتمال “درستی” توسطp*  مشخص  می شود ، یعنی:

(3)

این احتمال نشان دهنده این امر محتمل است که با توجه به Pc اندازه کارتل شیطانی پایینتر از حداکثر آستانه شکست های بیزانتین باقی خواهد ماند. از آنجا که این احتمال یک توزیع دوجمله ای است ، مقادیر pc بیشتر از 20٪ منجر به کارتل های بزرگتر از 20٪ از شبکه می شود و روند توافق عمومی را خنثی می کند. در عمل ، یک UNL به طور تصادفی انتخاب نمی شود ، بلکه با هدف به حداقل رساندن Pc انجام می شود. از آنجا که گره ها ناشناس نیستند بلکه از نظر رمزنگاری قابل شناسایی هستند ، با انتخاب یک UNL از گره ها از مخلوطی از قاره ها ، کشورها ، صنایع ، ایدئولوژی ها و غیره می توان مقادیر Pc بسیار کمتر از 20٪ تولید کرد. بعنوان نمونه ، احتمال اینکه اتحادیه ضد افترا و کلیسای وستبورو باپتیست برای کلاهبرداری از شبکه تبانی کنند ، بسیار  بسیار کمتر از 20٪ است. حتی اگر UNL دارای یک Pc نسبتاً بزرگ باشد ، مثلاً 15٪ ، احتمال درستی حتی با وجود تنها 200 گره در UNL بسیار زیاد است: 97.8٪.

یک نمای گرافیکی از چگونگی احتمال مقیاس های نادرستی به عنوان تابعی از اندازه UNL برای مقادیر مختلف pc در شکل 1 نشان داده شده است. توجه داشته باشید که در اینجا محور عمودی نشان دهنده احتمال خنثی شدن توافق عمومی توسط یک کارتل شرور است و بنابراین مقادیر پایین در این نما نشان دهنده احتمال بیشتر موفقیت توافق عمومی است. همانطور که در تصویر مشاهده می شود ، حتی با وجود یکPc  به اندازه 10٪ ، هنگامی که UNL از 100 گره فراتر می رود، احتمال خنثی شدن سریع توافق عمومی بسیار کم می شود.

• توافق

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

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

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

 

 

یک حد بالا در اتصال برای اثبات توافق مورد نیاز است که به صورت زیر شرح داده می شود:

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

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

4.3 سودمندی

در حالی که بسیاری از مولفه های سودمندی درونی هستند ، اما چیزی که قابل اثبات است همگرایی است: اینکه روند توافق عمومی در زمان محدود خاتمه یابد.

1.4.3 همگرایی

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

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

2.4.3ابتکارات و روش ها

همانطور که در بالا ذکر شد ، یک حد تاخیر ابتکاری برای تضمین همگرایی الگوریتم توافق عمومی در همه گره های شبکه Ripple اعمال می شود. علاوه بر این ، چند روش ابتکاری و روش های دیگر وجود دارند که سودمندی RPCA را فراهم می کنند.

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

 

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

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

5. بحث

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

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

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

 

6. تقدیر و تشکر

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

 

 

 

7. منابع

[1] ناکاموتو ، ساتوشی. “بیت کوین: سیستم نقدی الکترونیکی نظیر به نظیر”. مشاوره 1.2012 (2008): 28.

[2] لمپورت ، لسلی ، رابرت شوستاک و مارشال پی. “مسئله ژنرالهای بیزانس”. معاملات ACM در زبانها و سیستمهای برنامه نویسی (TOPLAS) 4.3 (1982): 382-401.

[3] اتیا ، سی ، دی دولوف و جی گیل. “توافقنامه بیزانتین ناهمزمان”. Proc. سوم. سمپوزیوم سالیانه ACM در اصول محاسبات توزیع شده. 1984

[4] فیشر ، مایکل جی ، نانسی ا. لینچ و مایکل اس. پترسون. “عدم امکان توافق توزیع شده با یک فرآیند معیوب.” مجله ACM (JACM) 32.2 (1985): 374-382.

[5] مارتین ، J-P ، و لورنزو آلوسی. “توافق عمومی بیزانتین سریع”. معاملات قابل اعتماد و امن ، معاملات IEEE در 3.3 (2006): 202-215.

[6] Alchieri ، Eduardo AP ، و دیگران. “اجماع بیزانس با شرکت کنندگان ناشناخته.” اصول سیستم های توزیع شده اسپرینگر برلین هایدلبرگ ، 2008- 22-28.