تحمل خطای بیزانس ( Byzantine fault tolerance ) چیست؟

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

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

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

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

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

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

مشکل دو ژنرال

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

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

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

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

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

بنابراین می‌گوییم مشکل دو ژنرال حل‌نشدنی است.

مشکل ژانرال‌های بیزانس

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

در این سناریو به جای رهبر و پیرو، فرمانده و نایب داریم. در این روش برای رسیدن به اجماع، فرمانده و همه‌ی نواب او باید بر سر یک تصمیم به توافق برسند.

در مسئله‌ی ژنرال‌های بیزانس، ژنرال فرمانده باید برای n-1 نایب خود دستور بفرستد به صورتی که:

IC1. همه‌ی نواب وفادار از یک دستور مشابه اطاعت کنند.

IC2. اگر فرمانده وفادار باشد، همه‌ی نواب وفادار از دستور ارسالی او اطاعت می‌کنند.

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

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

قاعده: الگوریتم (OM(m به ازای هر m به اجماع می‌رسد اگر بیش از ۳m ژانرال و حداکثر m خائن وجود داشته باشد.

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

الگوریتم (OM(0

(۱) فرمانده تصمیم خود را برای همه‌ی نوابش می‌فرستد.

(۲) هر نایب از خبری که از طرف فرمانده به دستش می‌رسد استفاده می‌کند، یا اگر خبری به دستش نرسد، موضع عقب‌نشینی یا RETREAT را در نظر می‌گیرد.

الگوریتم OM(m), m>0

(۱) فرمانده تصمیم خود را برای همه‌ی نوابش می‌فرستد.

(۲) vi برای هرi همان خبری است که نایبi از طرف فرمانده دریافت می‌کند. اگر هیچ خبری به دست نایب نرسد موضع RETREAT در نظر گرفته می‌شود. در الگوریتم (OM(m-1، نایت i به عنوان فرمانده‌ای عمل می‌کند که خبر vi را به n-2 نایب دیگر می‌فرستد.

(۳) به ازای هر i و هر j ≠ i، vi همان خبری است که نایب i در مرحله (۲) از طرف نایب j دریافت می‌کند. اگر خبری به او نرسد، موضع RETREAT در نظر گرفته می‌شود. نایب i از ارزش اکثریت (v1,…vn-1) استفاده می‌کند.

اگر m=0 باشد، هیچ نایب خائنی وجود ندارد و همه از دستور پیروی می‌کنند. اگر m>0 باشد، تصمیم نهاییِ هر نایب برابر تصمیم اکثریت نواب است.

تصویر زیر مثالی از دیدگاه نایب دوم یا Lieutentant 2 است. در این مثال C فرمانده و {L{i نیز نایب i می‌باشد:

(OM(1: نایب ۳ خائن است (از دیدگاه نایب ۲)

مراحل:

۱. فرمانده v را برای همه‌ی نواب می‌فرستد.

۲. نایب اول v را به نایب دوم، و نایب سوم x را به نایب دوم می‌فرستد.

۳. از دیدگاه نایب دوم، اکثریت (v== (v,v,x

تصمیم نهایی رای اکثریتی است که از نواب اول و دوم و سوم به دست می‌آید و در نتیجه اجماع حاصل می‌شود.

ذکر این نکته حائز اهمیت است که هدف اکثریت نواب نه رسیدن به یک تصمیم خاص بلکه رسیدن به تصمیمی مشترک است.

حالا بگذارید فرض کنیم فرمانده خائن باشد:

(OM(1: فرمانده خائن است.

مراحل:

۱. فرمانده x,y,z را به نواب اول و دوم و سوم می‌فرستد.

۲. نایب اول x را به نواب دوم و سوم، نایب دوم y را به نواب اول و سوم، و نایب سوم z را به نواب اول و دوم می‌فرستد.

۳. از دیدگاه نایب اول اکثریت (x,y,z)، از دیدگاه نایب دوم اکثریت (x,y,z)، از دیدگاه نایب سوم اکثریت (x,y,z)

هر سه نایب به جواب مشترکی می‌رسند و اجماع حاصل می‌شود. توجه داشته باشید که حتی اگر x,y,z با هم متفاوت باشند، مقدار اکثریت (x,y,z) برای هر سه نایب برابر است. اگر x,y,z دستورات کاملا متفاوتی باشند، می‌توانیم فرض کنیم که هر نایب به صورت پیشفرض به سراغ گزینه RETREAT می‌رود.

تحمل خطای بیزانس

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

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

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

این مباحث چه ربطی به بلاک چین دارد؟

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

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

یکی از دستاوردهای بیت کوین این بود که از پروتکل اثبات کار به عنوان راهکاری مبتنی بر احتمال برای حل مشکل ژنرال‌های بیزانس استفاده می‌کرد. این روش در مقاله‌ معروف ساتوشی ناکاموتو تشریح شد.

منبع