بررسی پروتکل اجماع استلار (Stellar)

پروتکل اجماع استلار در ابتدا در سال ۲۰۱۵ در وایت پیپری (Whitepaper) به قلم دیوید مازیرس (David Mazières) شرح داده شد. این پروتکل یک «سیستم توافق بیزانسی متحد یا فدرال (Federated)» است که به شبکه‌های غیر متمرکز رایانش و بدون رهبر امکان می‌دهد تا به صورت موثر در مورد تصمیمی به اجماع برسند. شبکه پرداخت استلار برای ارائه سندی همیشگی از تاریخچه تراکنش‌های شبکه به تمام شرکت‌کنندگان، از SCP استفاده می‌کند. در این مقاله، ما پیش‌زمینه‌ای مختصر در این باره ارائه می‌کنیم که اصولا «سیستم توافق» چیست، چه چیزی یک سیستم توافق را «بیزانسی» می‌کند و چرا باید یک سیستم توافق «بیزانسی» را «فدرال» کرد. سپس روش رای‌گیری فدرالی را توضیح می‌دهیم که وایت پیپر SCP شرح داده است و در نهایت به خود SCP خواهیم پرداخت.

0 400

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

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

یک سیستم توافق گروهی از شرکت‌کنندگان را قادر می‌سازد تا به تصمیمی مشابه در مورد چیزی برسند: برای مثال، این که برای ناهار چه چیزی سفارش داده شود.

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

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

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

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

هر سیستم توافقی در یک شبکه رایانشی توزیع‌شده باید متحمل خطا باشد: باید علی رغم وجود اشتباهاتی از جمله سرعت پایین ارتباطات، نودهای بدون واکنش و پیام‌های اشتباه، نتایج منسجمی تولید کند. یک سیستم توافق بیزانسی علاوه بر آن خطاهای «بیزانسی» را نیز تحمل می‌کند: نودهایی که اطلاعات نادرست ارائه می‌کنند، چه به دلیل خطا و چه به دلیل قصد عمدی برای خرابکاری یا به دست آوردن منفعت[۱]. آلیس (Alice)، صاحب یک سکه رمز ارز را در نظر بگیرید که باید بین خرید یک بستنی خوشمزه از باب یا پرداخت آن سکه به کارول برای تسویه یک بدهی یکی را انتخاب کند. شاید آلیس تمایل داشته باشد تا با پرداخت همان سکه به باب و کارول به هر دو هدف برسد. برای این کار او باید کامپیوتر باب را قانع کند که آن سکه هرگز به کارول پرداخت نشده است، و همچنین باید کامپیوتر کارول را متقاعد کند که آن سکه هرگز به باب پرداخت نشده است. یک سیستم توافق بیزانسی می‌تواند به طور موثر چنین کاری را با استفاده از نوعی اکثریت به نام حد نصاب (quorum) غیرممکن سازد. یک نود در چنین شبکه‌ای از پذیرش نسخه‌ای خاص از تاریخچه امتناع می‌کند، تا زمانی که ببیند تعدادی کافی از همتایانش (یک حد نصاب) نیز آماده پذیرش آن هستند. هنگامی که این اتفاق می‌افتد، آن‌ها یک دسته رای‌دهنده را تشکیل داده‌اند که به اندازه کافی برای الزام نودهای باقی‌مانده شبکه به موافقت با تصمیم آن‌ها بزرگ است. شاید آلیس بتواند باعث شود که برخی نودها از طرف او دروغ بگویند، اما اگر شبکه به اندازه کافی بزرگ باشد، تلاش او مغلوب آرای نودهای درستکار خواهد شد.

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

شاید تعیین یک حد نصاب تنها بر اساس دید محدود یک نود واحد در یک شبکه وسیع ناممکن به نظر برسد، اما ممکن است. این حد نصاب حتی می‌تواند در خصوص نتیجه یک رای‌گیری غیر متمرکز اعتماد ایجاد کند. وایت پیپر SCP نحوه انجام این کار را با استفاده از روندی به نام رای‌گیری متحدشده نشان می‌دهد.

برای عجول‌ها

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

  1. نودها چند مرحله رای‌گیری فدرال برای انتخاب «نامزدها» را برگزار می‌کنند. یک دور رای‌گیری فدرال به این معنی است:
    • یک نود رایی را برای گزاره‌ای مانند «من مقدار V را نامزد می‌کنم» صادر می‌کند؛
    • نود رای سایر همتایان خود را بررسی می‌کند تا موردی را بیابد که بتواند به آن «متعهد شود»؛
    • نود به دنبال «حد نصابی» می‌گردد که آن‌ها نیز به آن گزاره متعهد می‌شوند. این فرایند «گزاره» را تایید می‌کند.
  2. به محض اینکه نودی بتواند یک یا چند نامزد را تایید کند، تلاش برای «آماده‌سازی» «تعرفه» از طریق رای‌گیری‌های فدرال بیشتر را آغاز می‌کند.
  3. به محض اینکه نودی بتواند تأیید کند که یک تعرفه آماده است، تلاش برای «متعهد شدن» (commit) به تعرفه از طریق برگزاری مراحل بیشتری از رای‌گیری فدرال را آغاز می‌کند.
  4. هنگامی که نودی بتواند تأیید کند که تعرفه‌ای تعهد شده است، می‌تواند مقدار موجود در آن تعرفه را «برونی‌سازی» کرده و از آن به عنوان نتیجه اجماع استفاده کند.

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

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

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

حد نصاب‌ها و تکه حد نصاب‌ها

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

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

بررسی پروتکل اجماع استلار (Stellar)

برای یافتن یک حد نصاب از یک نود…

بررسی پروتکل اجماع استلار (Stellar)

… اعضای تکه حد نصاب آن را اضافه کنید…

بررسی پروتکل اجماع استلار (Stellar)

… سپس اعضای آن تکه‌های آن نودها را اضافه کنید.

بررسی پروتکل اجماع استلار (Stellar)

تا زمانی ادامه دهید که هیچ نودی برای اضافه کردن وجود نداشته باشد.

بررسی پروتکل اجماع استلار (Stellar)

بررسی پروتکل اجماع استلار (Stellar)

نودی برای اضافه کردن باقی نمانده است. این یک حد نصاب است.

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

بررسی پروتکل اجماع استلار (Stellar)

در هر گام تنها یک تکه حد نصاب انتخاب کنید.

بررسی پروتکل اجماع استلار (Stellar)

بررسی پروتکل اجماع استلار (Stellar)

بررسی پروتکل اجماع استلار (Stellar)

یک حد نصاب ممکن. به شکل جایگزین…

بررسی پروتکل اجماع استلار (Stellar)

… انتخاب تکه‌های گوناگون…

بررسی پروتکل اجماع استلار (Stellar)

بررسی پروتکل اجماع استلار (Stellar)

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

بررسی پروتکل اجماع استلار (Stellar)

… یک حد نصاب متفاوت تولید می‌کند.

یک نود چگونه اعضای تکه حد نصاب‌های نودهای دیگر را تشخیص می‌دهد؟ به همان صورت که هر چیز دیگری را در مورد نودهای دیگر می‌داند: از اطلاعاتی که هر نود زمانی که وضعیت رای‌دهی آن تغییر می‌کند در شبکه می‌پراکند. اطلاعات پراکنده‌شده هر نود شامل جزئیات تکه حد نصاب نود ارسال کننده است.[۲]

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

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

از لحاظ فنی، هیچ چیز! شبکه‌ای را تصور کنید که از آلیس، باب، کارول (Carol)، دیو (Dave)، السی (Elsie) و فرانک (Frank) تشکیل شده است. آلیس باب و کارول را در تکه حد نصاب خود دارد. باب آلیس و کارول و کارول آلیس و باب را دارد. در همین حال، دیو، السی و فرانک همگی یکدیگر را در تکه حد نصاب‌های خود دارند. زیرگروه آلیس-باب-کارول می‌تواند تصمیمی بگیرد که زیرگروه دیو-السی-فرانک هرگز در مورد آن نخواهد شنید و بالعکس. در این شبکه هیچ راهی برای نیل به یک اجماع (به جز به شکل تصادفی) وجود ندارد.

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

بررسی پروتکل اجماع استلار (Stellar)

اگر شبکه دارای «تقاطع حد نصاب» باشد…

بررسی پروتکل اجماع استلار (Stellar)

… سپس هر دو حد نصاب ممکن …

بررسی پروتکل اجماع استلار (Stellar)

… همواره همپوشانی خواهند داشت

بررسی پروتکل اجماع استلار (Stellar)

بررسی پروتکل اجماع استلار (Stellar)

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

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

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

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

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

رای‌دهی،‌ پذیرش و تأیید

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

یک نود از روی پیام‌های پراکنده شده همتایان خود می‌بیند که آن‌ها چگونه رای می‌دهند. هنگامی که نود تعدادی کافی از این پیام‌ها را جمع کند، می‌تواند تکه حد نصاب‌های موجود در آن‌ها را بررسی کند تا حد نصاب‌ها را بیابد. اگر بتواند حد نصابی از همتایان را ببیند که آن‌ها نیز همگی به V رای داده‌اند، سپس می‌تواند به مرحله پذیرشV وارد شود و این پیام جدید را در شبکه می‌پراکند. («من نود N هستم، تکه حد نصاب‌های من Q هستند، و من V را می‌پذیرم ») پذیرش تضمینی قوی‌تر نسبت به رای‌دهی ارائه می‌دهد. هنگامی که نودی به V رای می‌دهد، هرگز نمی‌تواند به غیر V رای دهد. اما زمانی که نودی V را می‌پذیرد، هیچ نودی در شبکه هرگز غیر V را نمی‌پذیرد. (نظریه ۸ در وایت پیپر SCP این را اثبات می‌کند.)

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

بررسی پروتکل اجماع استلار (Stellar)

یک نود، N، با سه تکه حد نصاب.

بررسی پروتکل اجماع استلار (Stellar)

B-D-F یک مجموعه مسدودکننده برای N است: این مجموعه شامل یک نود از هر یک از تکه‌های N است.

بررسی پروتکل اجماع استلار (Stellar)

B-E نیز یک همچنین مجموعه مسدودکننده برای N است، چرا که E در دو تکه N حضور دارد.

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

بررسی پروتکل اجماع استلار (Stellar)

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

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

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

دو ویژگی مهم یک سیستم اجماع عبارت‌اند از: امنیت و زنده بودن. یک الگوریتم اجماع زمانی «امن» است که هرگز نتواند برای شرکت‌کنندگان مختلف نتایج مختلفی تولید کند. (نسخه‌ای که باب از تاریخچه در اختیار دارد هرگز با نسخه کارول در تناقض نخواهد بود.) در همین حال، «زنده بودن» به این معنا است که الگوریتم هرگز در تولید نتیجه ناتوان نخواهد بود؛ به این معنی که گیر نخواهد کرد.

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

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

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

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

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

بخش زیر معرفی نامزد و رای‌دهی را به تفصیل شرح می‌دهد.

معرفی نامزد

در ابتدای مرحله معرفی نامزد، ممکن است هر نود خود به خود یک مقدار V را انتخاب کرده و به گزاره «من V را نامزد می‌کنم» رای دهد.[۵] در این مرحله هدف تایید معرفی مقداری به عنوان نامزد از طریق رای‌گیری متحدشده است.

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

با وجود این رای به معرفی V به عنوان نامزد وعده‌ای برای هرگز رای ندادن به ضرر V است، لایه اپلیکیشن روی رای‌گیری فدرال ( در این مورد SCP) باید «به ضرر» را تعریف کند. SCP گزاره‌ای را تعریف نمی‌کند که با یک رای «من X را نامزد می‌کنم» متناقض باشد (گزاره «من نامزدی X را رد می‌کنم» وجود ندارد)، بنابراین یک نود می‌تواند به نامزدی هر تعداد مقدار که می‌خواهد رای دهد. شاید بسیاری از این نامزدی‌ها به جایی نرسند، اما در نهایت یک یا چند آن مقدار وجود خواهند داشت که نودی آن‌ها را قبول یا تأیید می‌کند. هنگامی که یک نامزد تایید شود، کاندیدا نامیده می‌شود.

بررسی پروتکل اجماع استلار (Stellar)

نامزدی SCP با استفاده از رای‌گیری فدرال. ممکن است مقادیر «B» زیادی توسط همتایان نامزد شده و توسط نود «بازگو» شود.

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

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

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

رای‌دهی

یک تعرفه جفت است: <مقدار،شمارنده> ، که در آن شمارنده یک عدد صحیح است که از ۱ شروع می‌شود و مقدار، کاندیدایی از مرحله نامزد کردن است. این کاندیدا می‌تواند کاندیدای خود نود یا کاندیدای همتای دیگری باشد که نود پذیرفته است. به طور کلی، در رای‌دهی مکررا تلاش می‌شود تا با انجام رای‌گیری‌های فدرال بسیار در مورد گزاره‌هایی درباره تعرفه‌ها، شبکه به اجماعی در خصوص کاندیدایی در تعرفه‌ای برسد. شمارنده‌ها در تعرفه‌ها تلاش‌های انجام شده را دنبال می‌کنند و تعرفه‌های دارند اعداد شمارنده بالاتر بر تعرفه‌های دارای اعداد شمارنده پایین‌تر اولویت دارند. اگر به نظر برسد که <مقدار،شمارنده> تعرفه گیر کرده است، یک رای‌گیری جدید با تعرفه <counter+1,value> آغاز می‌شود.

تفاوت قائل شدن بین مقادیر (به عنوان مثال، این که سفارش ناهار چه باشد، پیتزا یا سالاد)، تعرفه‌ها (یک جفت مقدار-شمارنده)، و گزاره‌ها در مورد تعرفه‌ها مهم است. یک مرحله SCP شامل چندین مرحله رای‌گیری فدرال بر سر چنین گزاره‌هایی، به ویژه این موارد است:

  • «من آماده‌ام متعهد به تعرفه B شوم»، و
  • «من به تعرفه B متعهد می‌شوم.»

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

اگرچه به صورت مفهومی، رای‌گیری‌های فدرال بسیاری بر سر گزاره‌هایی در مورد تعرفه‌های گوناگون زیادی انجام می‌شود، اما تعداد پیام‌های پروتکل به مراتب کمتری رد و بدل می‌شوند، چرا که هریک محتوی طیفی از تعرفه‌ها هستند. بنابراین یک پیام واحد بنابراین وضعیت بسیاری از آرای فدرال به صورت یکجا پیش می‌برد، به عنوان مثال: «من می‌پذیرم که تعرفه‌های محدوده <min,V> تا <max,V> تعهد شده‌اند.»

«آمادگی» و «تعهد» به چه معنا هستند؟

نود زمانی به تعهد به تعرفه‌ای رای می‌دهد که متقاعد شده باشد نودهای دیگر متعهد به تعرفه‌هایی با مقادیر متفاوت نمی‌شوند. متقاعد شدن به این موضوع، هدف گزاره آماده‌سازی است. رایی که می‌گوید «من آماده‌ام تا متعهد به تعرفه B شوم» وعده هرگز متعهد نشدن به تعرفه‌ای کمتر از B است؛ یعنی تعرفه‌ای که عدد شمارنده آن کمتر است. [۶]گفته می‌شود که آن تعرفه‌های کوچکتر توسط رای آماده‌سازی‌ «لغو» (aborted) شده و B (prepared) «آماده» می‌شود.

چرا «من آماده‌ام تا متعهد به تعرفه B شوم» به این معنی است که «من قول می‌دهم که هرگز متهعد به تعرفه‌ای کمتر از B نشوم» ؟ به این دلیل که SCP «لغو» را متضاد «تعهد» تعریف می‌کند. رای به آماده‌سازی یک تعرفه به طور ضمنی همچنین به معنای رای به لغو سایر تعرفه‌ها است، و همانطور که پیش‌تر گفتیم، رای به چیزی به معنی این وعده است که هرگز خلاف آن رای داده نمی‌شود.

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

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

هنگامی که نود یک تعرفه B را بیابد که بتواند آماده بودن آن را تایید کند، رایی جدید برای «من متعهد به تعرفه B می‌شوم» را صادر می‌کند. این رای به همتایان می‌گوید که نود هرگز B را لغو نخواهد کرد. در حقیقت، اگر B تعرفه <N,C> باشد، سپس «من متعهد به تعرفه <N,C> می‌شوم» به طور ضمنی همچنین به معنی رای به آماده‌سازی تمام تعرفه‌ها از <N,C> تا <∞,C> است. این مفهوم اضافی به سایر نودهایی که این پیام را دریافت می‌کنند کمک می‌کند تا اگر هنوز در مراحل اولیه پروتکل هستند خود را برسانند.

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

اگر «من متعهد به <N,C> می‌شوم» پذیرفتنی یا قابل تایید نباشد، شاید بتوان <N+1,C> یا <N+2,C> را پذیرفت و تایید کرد؛ یا در هر صورت، تعرفه‌ای حاوی C و نه مقداری دیگر، چرا که نود وعده داده است که هرگز <N,C> را لغو نکند. وقتی که زمان صدور رای تعهد نود فرا رسد، تا جایی که به اجماع مربوط می‌شود رای آن یا C یا ناتوانی در رای‌دهی خواهد بود. با این حال، این هنوز برای برونی‌سازی C توسط نود کافی نیست. برخی از همتایان بیزانسی (که بر اساس فرضیات ایمنی ما تعداد آن‌ها کمتر از حد نصاب است)، ممکن است به نود دروغ گفته باشند. پذیرش و سپس تأیید یک نود (یا طیفی از تعرفه‌ها) آن چیزی است که به نود برای در نهایت برونی‌سازی C اطمینان می‌بخشد.

بررسی پروتکل اجماع استلار (Stellar)

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

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

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

ته‌نویس‌ها

  1. تحمل خطای «بیزانسی» (توانایی اعتماد به تصمیم گروه حتی زمانی که شاید برخی از اعضای گروه دروغ بگویند یا به هر صورت از قوانین تصمیم‌گیری تبعیت نکنند) بر اساس حکایتی از ژنرال‌های امپراتوری بیزانس نامگذاری شده است که سعی در هماهنگ کردن یک حمله داشتند. آنتونی استیونس (Anthony Stevens) شرح خوبی از آن نوشته است.
  2. وایت‌پیپر SCP یک سازوکار ارتباطی را تعیین نمی‌کند. پیاده‌سازی‌ها عموما از یک پروتکل خبرچینی استفاده می‌کنند تا اطمینان حاصل کنند که پیام‌ها در سراسر شبکه منتظر می‌شوند.
  3. یک سیستم توافق بیزانسی بر اساس این سوال طراحی می‌شود که: سیستم باید چند نود خرابکار را تحمل کند؟ در مجموعه‌ای از N نود که باید f ناکامی را تحمل کنند، نود باید بتواند پس از شنیدن از N-f همتا به کار خود ادامه دهد، چرا که ممکن است f تعداد از آن‌ها دچار مشکل شده باشند. با این حال، پس از دریافت پاسخ از N-f همتا، ممکن است همه همتایان باقیمانده (که نود از آن‌ها خبری ندارد) صادق باشند و تا f همتا از N-f همتا (که نود از آن‌ها پاسخ دریافت کرده است) خرابکار باشند. برای اطمینان از اینکه نودها همه به یک نتیجه می‌رسند، اکثریت N-f نودی که نود از آن‌ها پاسخ دریافت می‌کند باید صادق باشند، یعنی به N-f> 2f یا N> 3f نیاز داریم. بنابراین عموما سیستمی که طوری طراحی شده است تا f ناکامی را تحمل کند در مجموع N = 3f +1 نود داشته و حد نصاب آن ۲f +1 خواهد بود.
  4. تضمین‌های امنیت و زنده بودن SCP مشروط به محدودیت‌های نظری هستند. طراحی SCP یک تضمین بسیار قوی ایمنی را با یک تضمین کمی ضعیف‌تر زنده بودن معاوضه کرده است: با داشتن محدودیت زمانی کافی، به احتمال زیاد اجماع به دست خواهد آمد.
  5. در طول معرفی نامزد، همه آرای همتایان توسط یک نود بازگو نمی‌شوند، چرا که این کار منجر به داشتن تعداد بسیار زیادی از نامزدها خواهد شد. SCP شامل سازوکاری برای کاستن از آرای بازگو شده است. به طور خلاصه، فرمولی برای تعیین «اولویت» یک همتا از منظر یک نود وجود دارد، و تنها آرای نودهای دارای اولویت بالا بازگو خواهند شد. هر چه معرفی نامزد بیشتر طول بکشد، حد آستانه پایین‌تر خواهد رفت، بنابراین نود مجموعه همتایانی را که رای آن‌ها را بازگو می‌کند گسترش می‌دهد. یکی از ورودی‌های فرمول اولویت شماره اسلات است، بنابراین ممکن است همتای اولویت بالای یک اسلات برای نود دیگر اولویت کمی داشته باشد و بالعکس.
  6. SCP الزام می‌کند که مقادیر تعرفه‌ها به نوعی ترتیب داشته باشند. بنابراین اگر N1<N2 تعرفه <N1,V1> از <N2,V2> کمتر است، اما اگر V1<V2 باشد N1=N2 خواهد بود.

    منبع

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

ارسال پاسخ

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