پروتکل اجماع ستاره ای برای اولین بار در شرح داده شد مقاله علمی دیوید مازیر در سال 2015. این یک «سیستم قرارداد فدرال بیزانس» است که به شبکه‌های محاسباتی غیرمتمرکز و بدون رهبر اجازه می‌دهد تا به طور مؤثر در مورد یک تصمیم به اجماع برسند. شبکه پرداخت Stellar از پروتکل اجماع Stellar (SCP) برای حفظ یک سابقه تراکنش ثابت که برای همه شرکت‌کنندگان قابل مشاهده است، استفاده می‌کند.

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

در این مقاله به طور خلاصه توضیح خواهیم داد که «نظام قراردادها» چیست، چه چیزی می تواند آن را «بیزانسی» کند و چرا سیستم بیزانس را «فدرال» می کند. سپس روش رای گیری فدرال توضیح داده شده در مقاله SCP را توضیح خواهیم داد و در نهایت خود پروتکل SCP را توضیح خواهیم داد.

سیستم های توافق نامه

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

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

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

به نظر می رسد راه حل ساده است: رای گیری کنید! اما این تصور گمراه کننده است. چه کسی آراء را جمع آوری و نتایج را گزارش می کند؟ و چرا دیگران باید آنچه او می گوید را باور کنند؟ شاید بتوانیم در ابتدا به رهبری رأی دهید که ما به او اعتماد داریم تا رأی گیری را رهبری کند - اما کسی که رهبری آن را بر عهده خواهد داشت اول با رای دادن؟ اگر نتوانیم بر سر یک رهبر به توافق برسیم چه؟ یا اگر به توافق رسیدیم اما این رهبر در جلسه گیر کرد یا به مرخصی استعلاجی رفت چه؟

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

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

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

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

ممکن است ایجاد حد نصاب از دیدگاه یک گره در یک شبکه گسترده غیرممکن به نظر برسد، اما ممکن است. چنین حد نصابی حتی می تواند نتایج رای گیری غیرمتمرکز را تضمین کند. کاغذ سفید SCP نحوه انجام این کار را با استفاده از رویه ای به نام نشان می دهد با رای فدرال.

برای بی قراری

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

1. گره ها دورهای رای گیری فدرال را در مورد "نامزدها" انجام می دهند. دور رای گیری فدرال به این معنی است:
   • گره به برخی از عبارت ها رأی می دهد، به عنوان مثال، "من مقدار V را پیشنهاد می کنم";
   • گره به صدای همتایان گوش می دهد تا زمانی که صدایی را پیدا کند که بتواند "دریافت" کند.
   • گره به دنبال «نصاب» برای این ادعا است. حد نصاب، نامزد را "تأیید" می کند.
2. هنگامی که یک گره می تواند یک یا چند نامزد را تایید کند، سعی می کند تا "رای گیری" را از طریق چندین دور رای گیری فدرال "آماده کند".
3. هنگامی که یک گره بتواند تأیید کند که برگه رای آماده است، سعی می کند آن را از طریق دورهای بیشتری از رای گیری فدرال انجام دهد.
4. هنگامی که یک گره می تواند تعهد یک برگه رای را تایید کند، می تواند با استفاده از آن به عنوان یک نتیجه اجماع، ارزش آن رای گیری را "بیرونی" کند.

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

رای گیری فدرال

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

حد نصاب ها و برش های حد نصاب

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

تشکیل حد نصاب با قطع حد نصاب شروع می شود. برای هر گره، گره های برش آن اضافه می شود. سپس اصطلاحات برش اضافه می شوند این گره ها و غیره همانطور که ادامه می دهید، گره های بیشتری وجود دارد که نمی توانید آنها را اضافه کنید زیرا قبلاً در برش گنجانده شده اند. زمانی که گره جدیدی برای افزودن وجود نداشته باشد، فرآیند متوقف می‌شود: ما با «بسته شدن گذرا» نصاب نصاب گره اولیه، حد نصابی را تشکیل داده‌ایم.

برای یافتن حد نصاب از یک گره معین ...

... اضافه کردن اعضای برش آن ...

... سپس اعضای برش این گره ها را اضافه می کنیم.

ادامه می دهیم تا زمانی که هیچ گره ای برای افزودن باقی نماند.

هیچ گره ای برای افزودن باقی نمانده است. این حد نصاب است.

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

در هر مرحله فقط یک برش حد نصاب انتخاب کنید.

یک حد نصاب ممکن یا جایگزین...

... برش های دیگر را انتخاب کنید ...

… (در صورت امکان)…

... حد نصاب دیگری ایجاد می کند.

چگونه یک گره می داند که گره های دیگر در کدام برش ها قرار دارند؟ مانند سایر اطلاعات در مورد سایر گره ها: از ارسال هایی که هر گره در هنگام تغییر وضعیت رأی گیری به شبکه ارسال می کند. هر پخش شامل اطلاعاتی در مورد برش های گره ارسال کننده است. کاغذ سفید SCP مکانیسم ارتباطی را مشخص نمی کند. پیاده سازی ها معمولا استفاده می کنند پروتکل شایعات برای پخش تضمینی پیام ها در سراسر شبکه.

به یاد بیاورید که در سیستم قراردادهای بیزانسی غیر فدرال، حد نصاب به عنوان اکثریت همه گره ها تعریف می شود. سیستم توافق بیزانسی از دیدگاه این سوال طراحی شده است: سیستم چند گره ناصادق را می تواند تحمل کند؟ در سیستمی از N گره که برای زنده ماندن از شکست f طراحی شده است، یک گره باید بتواند با دریافت بازخورد از N-f همتایان، پیشرفت کند زیرا f از آنها ممکن است خراب باشد. اما با دریافت پاسخ از همتایان N−f، می‌توانیم فرض کنیم که تمام همتایان f (که گره از آنها پاسخی دریافت نکرده است) در واقع صادق هستند. بنابراین، f از N-f همتایان (که پاسخ از آنها دریافت شد) مخرب هستند. برای اینکه گره ها به یک اجماع برسند، اکثر گره های باقی مانده باید صادق باشند، یعنی باید N−f بزرگتر از 2f یا N> 3f باشد. بنابراین معمولاً سیستمی که برای زنده ماندن از شکست‌های f طراحی شده است، در مجموع دارای N=3f+1 گره و حد نصاب اندازه 2f+1 خواهد بود. هنگامی که یک پروپوزال از آستانه حد نصاب عبور کند، بقیه شبکه متقاعد شده اند که هر پیشنهاد رقیب با شکست مواجه خواهد شد. اینگونه است که شبکه به نتیجه همگرا می شود.

اما در یک سیستم قرارداد فدرال بیزانس، نه تنها اکثریت نمی تواند وجود داشته باشد (زیرا هیچ کس اندازه کل شبکه را نمی داند)، بلکه مفهوم اکثریت کاملاً بی فایده است! اگر عضویت در سیستم باز باشد، آنگاه کسی می‌تواند اکثریت را صرفاً با انجام یک حمله به اصطلاح Sybil به دست آورد: پیوستن مکرر به شبکه در چندین گره. پس چرا می توان بسته شدن برش گذرا نامید حد نصابو چگونه می تواند پیشنهادات رقیب را سرکوب کند؟

از نظر فنی به هیچ وجه! شبکه ای از شش گره را تصور کنید که در آن دو سه قلو در برش های حد نصاب یکدیگر جدا شده اند. ممکن است زیرگروه اول تصمیمی بگیرد که گروه دوم هرگز درباره آن چیزی نشنود و بالعکس. هیچ راهی برای اجماع این شبکه وجود ندارد (مگر اتفاقی).

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

در صورت تلاقی حد نصاب ها در شبکه ...

... سپس هر دو حد نصاب که می توانید ایجاد کنید ...

... همیشه متقاطع خواهد شد.

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

ممکن است انتظار اینکه یک عبور از حد نصاب قابل اعتماد در شبکه ای از گره های مستقل امکان پذیر است غیر منطقی به نظر برسد. اما دو دلیل برای این وجود دارد.

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

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

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

رای گیری، پذیرش و تایید

در یک دور رای گیری فدرال، یک گره به صورت اختیاری شروع به رای دادن به مقدار V می کند. این به معنای پخش پیامی به شبکه است: "من گره N هستم، برش های حد نصاب من Q هستند و من به V رای می دهم." وقتی یک گره به این شکل رای می‌دهد، قول می‌دهد که هرگز علیه V رای نداده و نخواهد داد.

در پخش همتا به همتا، هر گره می بیند که دیگران چگونه رای می دهند. هنگامی که یک گره به اندازه کافی از این پیام ها را جمع آوری کرد، می تواند برش های حد نصاب را ردیابی کند و سعی کند حد نصاب ها را پیدا کند. اگر او حد نصابی از همتایان را دید که به V نیز رای می دهند، می تواند اقدام کند فرزندخواندگی V و این پیام جدید را برای شبکه پخش کنید: "من گره N هستم، نصاب من Q است و V را قبول دارم." پذیرش تضمین قوی تری نسبت به رای دادن ساده دارد. وقتی یک گره به V رای می دهد، هرگز نمی تواند به گزینه های دیگر رأی دهد. اما اگر یک گره V را بپذیرد، هیچ گرهی در شبکه هرگز گزینه دیگر را نمی پذیرد (قضیه 8 در کاغذ سفید SCP این را ثابت می کند).

البته، احتمال زیادی وجود دارد که فوراً نصابی از گره های موافق با V وجود نداشته باشد. گره های دیگر ممکن است به مقادیر دیگری رأی دهند. اما راه دیگری برای حرکت گره از رای گیری ساده به پذیرش وجود دارد. N ممکن است مقدار دیگری را برای W بپذیرد، حتی اگر به آن رای نداده باشد، و حتی اگر حد نصابی برای آن نبیند. برای تصمیم به تغییر رای خود، فقط ببینید مجموعه مسدود کننده گره هایی که W را پذیرفته اند. یک مجموعه مسدود کننده یک گره از هر یک از برش های نصاب N است. همانطور که از نام آن پیداست، می تواند مسدود کردن هر معنای دیگری اگر همه گره‌ها در چنین مجموعه‌ای W را بپذیرند، آنگاه (با قضیه 8) هرگز نمی‌توان حد نصابی را تشکیل داد که مقدار متفاوتی داشته باشد، و بنابراین پذیرش W برای N نیز امن است.

گره N با سه برش حد نصاب.

BDF یک مجموعه مسدود کننده برای N است: شامل یک گره از هر یک از برش های N است.

BE همچنین یک مجموعه مسدود کننده برای N است زیرا E در دو برش N ظاهر می شود.

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

رای گیری فدرال

روند رای گیری، پذیرش و تایید یک دور کامل رای گیری فدراسیونی را تشکیل می دهد. پروتکل اجماع Stellar بسیاری از این دورها را برای ایجاد یک سیستم اجماع کامل ترکیب می کند.

پروتکل اجماع ستاره ای

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

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

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

مقادیری که SCP به دنبال اجماع بر روی آنهاست می‌تواند تاریخچه تراکنش یا سفارش ناهار یا چیز دیگری باشد، اما توجه به این نکته مهم است که اینها مقادیری نیستند که پذیرفته یا تأیید شده‌اند. در عوض، رای گیری فدرال بر اساس اظهاراتی در مورد این ارزش ها.

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

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

بخش‌های زیر نامزدی و رأی‌گیری را با جزئیات بیشتری شرح می‌دهند.

نامزدی

در ابتدای مرحله نامزدی، هر گره می تواند به طور خود به خود یک مقدار برای V انتخاب کند و به عبارت "من V را نامزد می کنم" رای دهد. هدف در این مرحله تأیید نامزدی برخی ارزش ها از طریق رأی گیری فدرال است.

شاید گره های کافی به گزاره های به اندازه کافی متفاوت رأی دهند که هیچ نامزدی نتواند به آستانه پذیرش برسد. بنابراین، علاوه بر پخش آرای نامزدی خود، گره‌ها نامزدهای همتایان خود را منعکس می‌کنند. پژواک به این معنی است که اگر یک گره به نامزدی V رای دهد، اما پیامی از طرف همسایه‌ای که به نامزد W رای می‌دهد را ببیند، اکنون به V و W رای می‌دهد. نامزدهای مختلف SCP شامل مکانیزمی برای تنظیم این آرا است. به طور خلاصه، فرمولی برای تعیین "اولویت" یک همتا از دیدگاه یک گره وجود دارد و فقط آرای گره های دارای اولویت بالا منعکس می شود. طول می کشد، آستانه پایین تر است، بنابراین گره مجموعه ای از همتایان را که آرای آنها را منعکس می کند گسترش می دهد. دیگری، و بالعکس).

از نظر مفهومی، نامزدی موازی است، V و W هر دو آرای فدرال جداگانه هستند، که هر کدام به تنهایی قادر به پذیرش یا تایید هستند. در عمل، پیام های پروتکل SCP این رای های فردی را با هم بسته بندی می کنند.

اگرچه رای دادن به نامزدی V وعده‌ای است که هرگز علیه نامزدی V رای نمی‌دهیم، اما در سطح برنامه - در این مورد SCP - مشخص می‌شود که «علیه» به چه معناست. SCP بیانیه ای را نمی بیند که با رای "I nominate X" مغایرت داشته باشد، یعنی پیام "من مخالف نامزد کردن X هستم" وجود ندارد، بنابراین گره می تواند به تعیین هر مقداری رای دهد. بسیاری از این نامزدها به جایی نمی رسند، اما در نهایت گره می تواند یک یا چند مقدار را بپذیرد یا تأیید کند. هنگامی که یک نامزد تایید شد، او می شود نامزد.

نامزدی SCP با استفاده از رای گیری فدرال. ممکن است مقادیر "B" زیادی وجود داشته باشد که توسط همتایان ارائه شده و توسط گره "بازتاب" شده است.

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

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

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

در حال دویدن

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

مهم است که تشخیص دهیم معانی (به عنوان مثال، سفارش ناهار چگونه باشد: پیتزا یا سالاد)، خبرنامه ها (جفت ضد ارزش) و بیانیه در مورد برگه های رای دور SCP شامل چندین دور رأی گیری فدرال است، به ویژه در مورد عبارات زیر:

• "من حاضرم رای B را انجام دهم" و
• "تعهد رای B را اعلام می کنم"

از منظر یک گره معین، زمانی اجماع حاصل می شود که برگه رأی B را بیابد که می تواند بیانیه «من رای B را متعهد می کنم» تأیید کند (یعنی حد نصابی را برای آن قبول کند). از این مرحله به بعد، می توان بر روی مقدار مشخص شده در B عمل کرد - به عنوان مثال، سفارش این سفارش برای ناهار. نامیده می شود برونی سازی معانی هنگامی که پذیرش برگه رأی تأیید شد، یک گره می تواند مطمئن باشد که هر گره دیگری همان مقدار را بیرونی کرده است یا در آینده این کار را انجام خواهد داد.

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

اصطلاحات «آماده» و «تعهد» به چه معناست؟

یک گره زمانی به انجام یک برگه رای رای می دهد که مطمئن باشد سایر گره ها برگه های رای با مقادیر متفاوت را ارسال نخواهند کرد. متقاعد کردن این هدف از تهیه برنامه است. رای که می گوید "من آماده هستم تا رای B را انجام دهم" وعده ای است که هرگز رای کوچکتر از B را انجام نمی دهم، یعنی با تعداد کمتری (SCP مستلزم آن است که مقادیر در برگه های رای به ترتیب خاصی باشد. بنابراین، خبرنامه کمتر ، اگر N1

چرا "من حاضرم رای B را انجام دهم" به معنای "قول می دهم هرگز رای های کوچکتر از B را انجام ندهم" است؟ زیرا SCP abort را برعکس commit تعریف می کند. رای دادن به تهیه برگه رای شامل رای دادن به رد صلاحیت برخی دیگر از برگه‌های رای نیز می‌شود، و همانطور که قبلاً بحث کردیم، رای دادن به یک چیز وعده‌ای است که هرگز علیه آن رای نمی‌دهیم.

قبل از پخش یک commit، یک گره ابتدا باید یک بولتن پیدا کند که بتواند آن را به عنوان آماده شده تأیید کند. به عبارت دیگر، در مورد موضوع «من آماده انجام رأی B هستم»، احتمالاً در بسیاری از برگه‌های رأی، رأی‌گیری فدرالی انجام می‌دهد تا زمانی که موردی را پیدا کند که حد نصاب را بپذیرد.

برگه های رای برای آماده سازی رای از کجا می آیند؟ ابتدا، گره آماده سازی برای رای دادن به <1,C> را پخش می کند، جایی که C نامزد ترکیبی تولید شده در مرحله نامزدی است. با این حال، حتی پس از آغاز آماده‌سازی برای رای‌گیری، نامزدی ممکن است منجر به این شود که نامزدهای دیگری به برگه‌های رای جدید تبدیل شوند. در همین حال، همتایان می توانند کاندیداهای مختلفی داشته باشند و می توانند یک مجموعه مسدود کننده تشکیل دهند که "من آماده هستم تا رای B2 را انجام دهم" را می پذیرد که گره را نیز متقاعد می کند که آن را بپذیرد. در نهایت، مکانیزمی وجود دارد که در صورت گیرکردن برگه‌های رای فعلی، دورهای جدیدی از رای‌گیری فدرال روی برگه‌های رای جدید با تعداد بیشتری را ایجاد می‌کند.

به محض اینکه گره یک برگه رای B را پیدا کرد که می تواند آن را به عنوان آماده تایید کند، پیام جدیدی را پخش می کند "Commit flet B". این رای به همتایان می گوید که گره هرگز B را رها نمی کند. در واقع، اگر B یک برگه رای باشد ، سپس «تعهد رأی گیری «به معنای رضایت بی قید و شرط برای رأی دادن به آمادگی هر برگه رأی از به <∞، s>. این مقدار اضافی به سایر همتایان کمک می کند تا اگر هنوز در مراحل اولیه پروتکل هستند، با همتای commit عقب بیفتند.

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

اگر پیغام «من یک تعهد را اعلام کرده ام » قابل دریافت یا تایید نیست، یعنی احتمال پذیرفته شدن یا تایید شدن پیام یا - یا، در هر صورت، هر برگه رای با مقدار C، و نه هر برگه دیگری، زیرا گره قبلاً قول داده است هرگز لغو نکند. . تا زمانی که یک گره رای برای یک commit را پخش کند، بسته به اینکه اجماع تا کجا پیش می رود، C یا هیچ خواهد بود. با این حال، این هنوز برای گره برای بیرونی کردن C کافی نیست. برخی از همتایان بیزانسی (که بر اساس مفروضات امنیتی ما کمتر از حد نصاب را تشکیل می دهند) ممکن است به گره دروغ بگویند. پذیرش و سپس تأیید برخی از برگه‌های رأی (یا طیفی از برگه‌های رأی) چیزی است که به گره این اطمینان را می‌دهد تا در نهایت C را بیرونی کند.

رای گیری SCP از طریق رای گیری فدرال. نشان داده نشده است: ممکن است تایمر در هر زمانی خاموش شود و تعداد برگه های رای افزایش یابد (و احتمالاً ترکیب جدیدی از نامزدهای معرفی شده اضافی تولید شود).

و این همه است! هنگامی که شبکه به اجماع رسید، آماده است تا آن را بارها و بارها انجام دهد. در شبکه پرداخت Stellar، این تقریباً هر 5 ثانیه یک بار اتفاق می‌افتد: شاهکاری که به امنیت و بقای تضمین شده توسط SCP نیاز دارد.

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

خواندن بیشتر

• کاغذ سفید SCP اصلی را می توان پیدا کرد اینجاو اینجا پیش نویس مشخصات برای اجرای آن.
• نویسنده اصلی پروتکل SCP، دیوید مازیر، آن را به روشی ساده (اما هنوز فنی) توضیح می دهد. اینجا.
• ممکن است از پیدا نکردن عبارات «ماینینگ» یا «اثبات کار» در این مقاله متعجب شده باشید. SCP از این روش ها استفاده نمی کند، اما برخی دیگر از الگوریتم های اجماع استفاده می کنند. زین ویترسپون در دسترس نوشت مروری بر الگوریتم های اجماع.
• شرح گام به گام یک شبکه ساده که در یک دور کامل SCP به اجماع می رسد.
• برای خوانندگان علاقه مند به پیاده سازی SCP: ببینید کد ++C، استفاده شده توسط شبکه پرداخت Stellar، یا برو کد، که برای درک بهتر SCP نوشتم.

منبع: www.habr.com