مقدمه ای بر ترجمه وایت پیپر ریپل

الگوریتم جمعی پروتکل ریپل Ripple

چکیده

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

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

۱٫ معرفی

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

در حالی که این مشکلات متنوع است ، ما آنها را در سه دسته اصلی قرار می دهیم: درستی ، توافق و سودمندی.

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

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

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

جنبه های اضافی (سودمندی) ممکن است شامل سطح توان محاسباتی مورد نیاز برای شرکت در درستی و فرآیندهای توافق یا مهارت فنی مورد نیاز کاربر نهایی برای جلوگیری از کلاهبرداری در شبکه باشد. بسیاری از این موضوعات مدت ها قبل از ظهور سیستم های رایانه ای توزیع شده ی مدرن ، از طریق مشکلی موسوم به “مسئله ژنرال های بیزانس” (Byzantine Generals Problem) مورد بررسی قرار گرفته است.

[۲] در این مشکل ، گروهی از ژنرال ها هرکدام بخشی از ارتش را کنترل می کنند و باید با ارسال پیام رسان به یکدیگر ، یک حمله را هماهنگ کنند. از آنجا که ژنرال ها در قلمرویی ناآشنا و خصمانه قرار دارند ، ممکن است پیام رسان ها نتوانند به مقصد خود برسند (دقیقاً همانطور که ممکن است گره های یک شبکه ی توزیع شده خراب شوند ، یا به جای پیام مورد نظر داده های خراب را ارسال کنند).

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

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

در این کار ، ما یک اجرای خاص از یک سیستم پرداخت توزیع شده را تجزیه و تحلیل می کنیم: پروتکل ریپل Ripple

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

علاوه بر این ، ما کدی را ارائه می دهیم که فرایند جمعی را با اندازه ی شبکه پارامتری ، تعدادی کاربر مخرب و تأخیرهای ارسال پیام ، شبیه سازی می کند.

۲ – تعاریف ، رسمی سازی و کارهای قبلی

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

۲٫۱ –  مولفه های پروتکل ریپل  Ripple

توضیحات خود در مورد شبکه ی ریپل ripple را با تعریف شرایط زیر شروع می کنیم:

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

لیست گره های منحصر به فرد  (UNL) Unique Node List:  هر سرور ، لیست گره های منحصر به فردی را حفظ می کند ، که مجموعه ای از سرورهای دیگر است که هنگام تعیین جمعی از آنها پرس و جو می کند.

فقط آراء دیگر اعضای UNL در هنگام تعیین جمعی در نظر گرفته می شود (بر خلاف بقیه گره ها در شبکه).

بنابراین UNL زیرمجموعه ای از شبکه را نشان می دهد که وقتی به صورت جمعی در نظر گرفته می شود ، مورد اعتماد خوانده می شود تا برای جعل این شبکه تبانی نکنند.

توجه داشته باشید که این تعریف “اعتماد” نیازی به اعتماد تک تک اعضای UNL ندارد (به بخش ۳٫۲ مراجعه کنید).

• پیشنهاد دهنده: هر سرور می تواند معاملات را منتشر کند تا در پروسه جمعی گنجانده شود ، و هر سرور سعی می کند با شروع دور جمعی جدید ، یک معامله معتبر را شامل شود. با این حال در طول فرایند جمعی ، تنها پیشنهادات سرورهای UNL سرور s توسط s در نظر گرفته می شود.

۲٫۲ –  رسمی سازی

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

ما مفهوم اعتبار یک معامله را به یک مشکل تصمیم گیری باینری ساده کاهش می دهیم: هر گره باید از اطلاعاتی که با مقدار ۰ یا ۱ دریافت کرده است تصمیم بگیرد.

مانند Attiya ، Dolev  و Gill ،در سال ۱۹۸۴ ، ما فرایند جمعی را طبق سه اصل زیر تعریف می کنیم:

۱ (C1): هر گره بی عیب و نقصی در زمان محدود تصمیم می گیرد

۲ (C2): همه گره های بی عیب و نقص به مقدار تصمیم گیری یکسان می رسند

۳  (C3): 0 و ۱ هر دو مقادیر ممکن برای همه گره های بی عیب و نقص هستند. (صرف نظر از اطلاعات ارائه شده توسط آنها)

۲٫۳ الگوریتم های جمعی موجود : تحقیقات زیادی در مورد الگوریتم هایی انجام شده است که در مواجهه با خطاهای بیزانس به یک توافق جمعی می رسند.

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

یکی از نتایج مهم کار قبلی در مورد الگوریتم های جمعی، نتایج مربوط به فیشر ، لینچ و پترسون ،در سال  ۱۹۸۵ [۴] است که ثابت می کند در موارد ناهمگام ، همیشه امکان بی پایانی برای یک الگوریتم جمعی، حتی با تنها یک فرآیند معیوب وجود دارد. این امر کشف مبتنی بر زمان را ، برای اطمینان از همگرایی (یا حداقل تکرارهای غیر همگرایی) ضروری می کند. ما این اکتشافات مربوط به پروتکل ریپل Ripple را در بخش ۳ شرح خواهیم داد.

قدرت یک الگوریتم جمعی معمولاً از نظر میزان فرایندهای معیوبی که می تواند تحمل کند ، اندازه گیری می شود.

این امر قابل اثبات است که هیچ راه حل خطای ژنرالهای بیزانسی (که در حال حاضر همزمانی و شرکت کنندگان شناخته شده را قبول کرده اند ) نمی تواند بیش از (n−۱)/۳ خطای بیزانس ، یا ۳۳٪ عملکرد مخرب شبکه را تحمل کند[۲]. با این وجود ، این راه حل نیازی به اثبات درستی پیام های ارسال شده بین گره ها (امضاهای دیجیتال) ندارد. اگر ضمانت غیر قابل جعل بودن پیام ها امکان پذیر باشد ، الگوریتم هایی با تحمل خطای بسیار بالاتر در موارد همگام وجود دارند.

چندین الگوریتم با پیچیدگی های بیشتر برای بیزانس جمعی در موارد ناهمگام پیشنهاد شده است. FaB Paxos می تواند خطای بیزانسی به میزان (n−۱)/۵ را در شبکه ای از گره ها تحمل می کند ، و این برار با میزان تحمل ۲۰٪ گره های شبکه است که با یک خرابکاری برخورد می کنند.

Attiya  ، Doyev  و Gill یک الگوریتم فاز برای موراد ناهمزمان را معرفی می کنند ، که می تواند خطاهایی با میزان (n−۱)/۴ یا حداکثر ۲۵ درصد شبکه را تحمل کند. در نهایت ، Alchieri   ،در سال ۲۰۰۸ ، BFT-CUP  را ارائه می دهد ، که حتی در موارد  غیرهمزمان با شرکت کننده های ناشناخته ، با حداکثر حد تحمل  (n−۱)/۳  به بیزانس جمعی میرسند ، اما با محدودیت های اضافی برای  اتصال شبکه های بنیادین.

۲٫۴ اهداف اجماع رسمی

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

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

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

در آخر ما نشان خواهیم داد كه پروتكل ریپل  Ripple در مواجهه با خطاهای (n − ۱) / ۵ می تواند به این اهداف برسد ، كه قوی ترین نتیجه نیست ، اما نشان خواهیم داد كه پروتكل ریپل دارای چندین ویژگی مطلوب دیگر است كه تا حد زیادی موجب افزایش سودمندی آن می شود.

ترجمه توسط تیم دلاریپتو

No views yet