الگوریتم تحمل خطای بیزانس چیست و چه کاربردی در بلاک چین دارد؟

تحمل خطای بیزانس (Byzantine Fault Tolerance) یا به‌طور خلاصه BFT، یک الگوریتم در بلاک چین و شبکه‌ های ارز دیجیتال است که آن را بررسی می‌کنیم.

از زمان پیدایش ارز بیت کوین در سال 2008 به عنوان یک سیستم پول الکترونیک همتابه‌همتا تا کنون، رمز ارزهای زیادی مجهز به مکانیزم‌های خاص ساخته شده‌اند. اما ویژگی مشترک تقریبا تمام ارزهای دیجیتال، بلاک چین به‌عنوان عنصر مرکزی در ساختار آن‌هاست. الگوریتم تحمل خطای بیزانس (Byzantine Fault Tolerance) یا به‌طور خلاصه BFT، در پاسخ به مسئله معروف فرماندهان بیزانسی مطرح شد که در این مطلب به بررسی آن می‌پردازیم.

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

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

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

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

مسئله دو فرمانده

این مسئله که در سال 1975 منتشر و در سال 1978 نام‌گذاری شد، سناریویی را تشریح می‌کند که در آن دو فرمانده مشغول حمله به یک دشمن مشترک هستند. فرمانده 1 به عنوان رهبر و فرمانده 2 به عنوان پیرو در نظر گرفته شده است. ارتش هر فرمانده هم به تنهایی برای شکست موفقیت‌آمیز ارتش دشمن کافی نیست، بنابراین این فرماندهان به همکاری و حمله همزمان نیاز دارند. این سناریو ساده به نظر می‌رسد، اما یک مشکل وجود دارد:

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

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

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

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

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

مسئله فرماندهان بیزانسی چیست؟

مسئله فرماندهان بیزانسی که در سال 1982 توسط لمپرت (Lamport)، شوستاک (Shostak) و پیز (Pease) به عنوان یک معضل سه‌گانه منطقی مطرح شد، در واقع نوع کلی‌تر مسئله دو فرمانده با کمی تغییر است.

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

بنابراین، باید الزامات زیر را در نظر گرفت:

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

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

حال مسئله فرماندهان بیزانسی دو فرضیه دارد:

• IC1: تمام ستوان‌های وفادار از دستور یکسان پیروی می‌کنند.
• IC2: اگر ژنرال فرمانده وفادار باشد، تمام ستوان‌های وفادار نیز از دستور وی پیروی می‌کنند.

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

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

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

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

درک این قضیه از نقطه نظر ستوان 2 در تصویر زیر مشخص‌تر است. C را فرمانده و L{i} را ستوان iام در نظر بگیرید:

الگوریتم OM(1): از نقطه نظر ستوان 2، ستوان 3 خائن است.

در این الگوریتم، چند گام برای رسیدن به تصمیم نهایی وجود دارد:

1. فرمانده v (تصمیم خودش) را به تمام ستوان‌ها را می‌فرستد.
2. ستوان1 v را به ستوان2 | ستوان3 x را به ستوان2 می‌فرستد.
3. ستوان2 → اکثریت (v,v,x) == v

بنابراین همانطور که مشخص است، تصمیم نهایی مبتنی بر اکثریت رای L2 ,L1 و L3 خواهد بود.

نکته مهم این است که هدف اصلی، انتخاب تصمیم یکسان توسط اکثریت ستوان‌هاست، نه رسیدن به یک تصمیم خاص.

حال، مسئله خائن بودن خود فرمانده را بررسی می‌کنیم.

الگوریتم OM(1): زمانی که فرمانده خائن است. گام‌ها:

1. فرمانده y ,x و z را به به ترتیب به ستوان 1، 2 و 3 می‌فرستد.
2. ستوان1 x را به ستوان 2 و 3 | ستوان2 y را به ستوان 1 و 3 | ستوان3 z را به ستوان 1 و 2 می‌فرستد.
3. L1 → اکثریت (x,y,x) | L2 → اکثریت (x,y,z) | L3 → اکثریت (x,y,z)

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

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

الگوریتم تحمل خطای بیزانس (BFT) چیست؟

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

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

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

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

تحمل خطای بیزانس و الگوریتم های اجماع در بلاک چین

یک الگوریتم اجماع (Consensus Algorithm) را می‌توان به عنوان مکانیزمی تعریف کرد که یک شبکه بلاک چینی از طریق آن به اجماع می‌رسد. متداول‌ترین نوع این الگوریتم‌ها، اثبات کار (Proof of Work) و اثبات سهام (Proof of Stake) هستند. اما مثال شبکه بیت کوین را در نظر بگیرید.

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

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

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

جمع‌بندی

مسئله فرماندهان بیزانسی یک معضل جذاب است که در نهایت منجر به ظهور سیستم‌های BFT شد. ورای صنعت بلاک چین، برخی از کاربردهای BFT در صنایع هوایی، فضایی و هسته‌ای است.

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

تهیه شده در بیت 24