فهم أساسيات Blockchain: تحدي الجنرالات البيزنطيين. الجزء 1

تم إعداد ترجمة المقال خاصة لطلاب الدورة التدريبية "High Load Architect" ، التي تبدأ هذا الشهر.

---

Blockchain هو نظام لامركزي يتكون من عدة كيانات تعمل وفقًا لحوافزهم والمعلومات التي لديهم.

عندما يتم بث معاملة جديدة عبر الشبكة ، يمكن للعقد تضمين هذه المعاملة في نسخة من دفتر الأستاذ أو تجاهلها. عندما يقرر معظم المشاركين في الشبكة قبول حالة معينة ، يتم التوصل إلى توافق في الآراء.

تتمثل المشكلة الأساسية في أنظمة الحوسبة الموزعة والمتعددة الوكلاء في تحقيق الموثوقية الكلية للنظام في وجود عدد من العمليات غير الفعالة. في كثير من الأحيان ، يتطلب هذا أن تنسق العمليات فيما بينها بعض القيمة التي ستكون مطلوبة أثناء الحساب.

يتم وصف هذه العمليات على أنها إجماع.

• ماذا يحدث عندما يقرر المشارك عدم اتباع القواعد والتدخل في حالة دفتر الأستاذ الخاص به؟
• ماذا يحدث عندما يكون هناك الكثير من هؤلاء المشاركين في الشبكة ، ولكن ليس الغالبية؟

لكي يكون بروتوكول الإجماع آمنًا ، يجب أن يكون متسامحًا مع الخطأ.

بادئ ذي بدء ، سنتحدث باختصار عن المشكلة غير القابلة للذوبان المتمثلة في جنرالين. ثم ، فكر في مشكلة الجنرالات البيزنطيين وناقش التسامح مع الأخطاء البيزنطية في الأنظمة الموزعة واللامركزية. وفي النهاية ، دعونا نتحدث عن مدى ارتباط كل ذلك بتكنولوجيا blockchain.

مهمة اثنين من الجنرالات

تصف هذه المهمة ، التي نُشرت لأول مرة في عام 1975 وتمت تسميتها عام 1978 ، سيناريو يهاجم فيه جنرالان عدوًا مشتركًا. يعتبر الجنرال الأول القائد ، والثاني هو الأتباع. جيش كل جنرال وحده لا يكفي لهزيمة جيش العدو ، لذلك يحتاجون إلى التعاون والهجوم في نفس الوقت. يبدو هذا السيناريو بسيطًا ، ولكن هناك تحذير واحد:

حتى يتمكنوا من التواصل والاتفاق على الوقت ، يجب أن يرسل الجنرال الأول رسولا عبر معسكر العدو ، وعليه أن يسلم رسالة في وقت بدء الهجوم إلى الجنرال الثاني. ومع ذلك ، فمن المرجح أن يتم القبض على رسول من قبل المعارضين ، ولم يتم تسليم الرسالة. سيؤدي ذلك إلى حقيقة أن جيش الجنرال الأول سيواصل الهجوم ، وسيظل الثاني في مكانه.

حتى إذا تم تسليم الرسالة الأولى ، يجب على الجنرال الثاني تأكيد (ACK (إقرار) ، لاحظ التشابه مع المصافحة الثلاثية في TCP ) التي تلقاها الرسالة ، لذلك فهو يرسل الرسول مرة أخرى ، وبالتالي إعادة إنتاج السيناريو السابق حيث يمكن القبض على رسول . هذا يتدفق إلى ACKs التي لا نهاية لها ، وبسبب هذا ، لا يمكن للجنرالات التوصل إلى اتفاق.

لا توجد وسيلة لضمان الشرط الثاني ، وهو أن كل جنرال واثق تماما من أن الآخر يوافق على خطة الهجوم. سيكون كلا الجنرالات جاهلين دائمًا بما إذا كان الرسول قد وصل إلى رفيقه أم لا.



ثبت أن مهمة الجنرالات غير قابلة للحل.

مهمة الجنرالات البيزنطيين

وصفها في عام 1982 من قبل لامبورت ، شوستاك وبيز ، تحولت نسخة هذه المشكلة إلى تسليط الضوء. إنها تصف السيناريو نفسه ، حيث يجب أن يتفق عدد أكبر من الجنرالات على وقت الهجوم بدلاً من جنرالات. هناك تعقيد إضافي يتمثل في أن جنرالًا واحدًا أو أكثر يمكن أن يكونوا خونة ، أي أنه يمكنهم الكذب بشأن نواياهم (على سبيل المثال ، يقول الجنرال إنه يوافق على الهجوم في الساعة 09:00 ، لكنه لا يفعل ذلك).

يتحول نموذج زعيم الأتباع الموصوف في مهمة الجنرالات إلى تثبيت تابع للقائد. لتحقيق الإجماع هنا ، يجب على القائد وكل مرؤوس الاتفاق على نفس الحل (الهجوم أو التراجع).

ترجمة الصور:

مهمة الجنرالات البيزنطيين. يجب على القائد العام إرسال أمر إلى مرؤوسيه n-1 ، بحيث:

• جميع الجنرالات المرؤوسين المخلصين يطيعون قيادة واحدة.
• إذا كان القائد العام مخلصًا ، فإن جميع مرؤوسيه المخلصين يطيعون أوامره.

بالإضافة إلى النقطة الثانية ، يجب الإشارة إلى حقيقة مثيرة للاهتمام: إذا كان القائد خائناً ، فيجب التوصل إلى توافق في الآراء. ونتيجة لذلك ، فإن جميع المساعدين لديهم أغلبية الأصوات.

تستند خوارزمية الإجماع في هذه الحالة إلى معنى معظم القرارات التي يراها المرؤوسون.

النظرية: بالنسبة إلى أي m ، تصل خوارزمية OM (m) إلى توافق مع أكثر من 3 ملايين من الجنرالات وحد أقصى من الخونة m .

هذا يعني أن الخوارزمية يمكنها الوصول إلى توافق بينما 2/3 من المشاركين صادقون. إذا كان الخونة أكثر من 1/3 ، لم يتم التوصل إلى توافق في الآراء ، لا يمكن للجيوش تنسيق هجماتهم ، ويفوز العدو.

خوارزمية OM (0)

1. يرسل القائد قيمته إلى كل من المرؤوسين.
2. يستخدم كل مرؤوس القيمة التي يتلقاها من القائد ، أو يستخدم القيمة DELAY إذا لم يتلق أي قيمة.

OM الخوارزمية (م) ، م> 0

1. يرسل القائد بأهميته لكل من المرؤوسين.
2. بالنسبة لكل i ، دع vi هي القيمة التي يستلمها المرؤوس من القائد ، أو سيتم استخدام قيمة RESET إذا لم يتلق المرؤوس أي قيمة. يعمل المرؤوس الأول كقائد في خوارزمية OM (م -1) ويرسل قيمة إلى كل من المرؤوسين المتبقين n-2.
3. بالنسبة لكل i ، بشرط أن ji ، اسمحوا vj أن تكون القيمة التي حصل عليها المرؤوس ith من المرؤوس jth في الخطوة (2) (باستخدام OM Algorithm (m-1)) ، أو تستخدم القيمة DISCONNECT إذا لا تحصل على أي معنى. يستخدم العبد ith قيمة الأغلبية (v1 ، ... ، vn-1).

عندما لا يكون هناك = m خونة ، يتبع كل مرؤوس الترتيب. بالنسبة إلى m> 0 ، فإن كل اختيار نهائي لأحد المرؤوسين يبدأ من الجزء الغالب في انتخاب جميع المرؤوسين.
سيكون الأمر أكثر وضوحًا إذا نظرت إلى الموقف من وجهة نظر المرؤوس الثاني - دع C هو القائد ، و L {i} هو المرؤوس الأول.



OM (1): المرؤوس 3 خائن. الموقف من وجهة نظر المرؤوس الثاني.

الخطوات التالية:

1. يرسل القائد الخامس إلى جميع المرؤوسين.
2. L1 يرسل L2 قيمة v أو L3 يرسل L2 قيمة x.
3. L2 ← الأغلبية (v ، v ، x) == v

يتم اتخاذ القرار النهائي بأغلبية أصوات L1 و L2 و L3 ونتيجة لذلك تم التوصل إلى توافق في الآراء.

من المهم أن تتذكر أن الهدف هو أن يختار معظم المرؤوسين نفس الحل ، بدلاً من حل معين.

دعونا ننظر في القضية عندما يكون القائد خائنا.



OM (1): القائد خائن.

الخطوات التالية:

1. يرسل القائد L1 ، L2 ، L3 قيم x ، y ، z ، على التوالي ؛
2. L1 يرسل قيمة x إلى العبيد L2، L3 | L2 يرسل L1 ، L3 قيمة y | يرسل L3 L1 ، L2 قيمة z ؛
3. L1 ← الأغلبية (س ، ص ، ض) | L2 ← معظم (س ، ص ، ض) | L3 ← الأغلبية (س ، ص ، ض)

لديهم جميعا نفس القيمة ، لذلك تم التوصل إلى توافق في الآراء. لاحظ أنه حتى لو كانت قيم x و y و z مختلفة ، فإن قيمة الأغلبية (x و y و z) هي نفسها لكل المرؤوسين الثلاثة. إذا كانت x ، y ، z هي طلبات مختلفة تمامًا ، يمكننا افتراض أنها ستعمل وفقًا للخطة الافتراضية - إعادة تعيين.

للنظر في مقاربة عملية لمثال أكثر تعقيدًا مع 7 جنرالات و 3 خونة ، أقترح عليك قراءة هذه المقالة .

خطأ البيزنطي التسامح

التسامح مع الأخطاء البيزنطية هو خاصية تحدد النظام الذي يتيح فئة من الإخفاقات التي تنتمي إلى مهمة الجنرالات البيزنطيين. الفشل البيزنطي هو أكثر أنواع الفشل تعقيدًا. لا تتضمن أي قيود ولا تضع أي افتراضات حول السلوك الذي قد تكون للعقدة (على سبيل المثال ، يمكن للعقدة توليد أي بيانات تعسفية ، مما يمثل مشاركًا صادقا).

الأخطاء البيزنطية هي الأصعب في الإصلاح. هناك حاجة إلى التسامح مع الأخطاء البيزنطية في أنظمة محركات الطائرات ، وفي محطات الطاقة النووية وفي أي نظام تقريبًا تعتمد أفعاله على نتائج عدد كبير من أجهزة الاستشعار. حتى SpaceX ترى أنه مطلب محتمل لأنظمتها .

تتوافق الخوارزمية المذكورة في القسم السابق مع التسامح مع الخطأ البيزنطي حتى يتجاوز عدد الخونة ثلث جميع الجنرالات. هناك خيارات أخرى لتسهيل هذه المهمة ، بما في ذلك استخدام التوقيعات الرقمية أو فرض قيود على الاتصال بين الأقران.

كيف يرتبط كل هذا بـ blockchain؟

Blockchain هي دفاتر لا مركزية ، بحكم تعريفها ، لا تخضع لسيطرة السلطة المركزية. نظرًا للقيم المخزنة فيها ، يتمتع المهاجمون بحافز اقتصادي جيد لمحاولة بدء الخطأ. ومع ذلك ، فإن التسامح مع الخطأ البيزنطي ، وبالتالي ، حل المشكلة العامة البيزنطية لكتلة سلسلة المفاتيح هي ببساطة ضرورية.

في حالة عدم وجود تسامح مع الأخطاء البيزنطية ، يمكن للنظير إرسال معاملات كاذبة ونشرها ، مما يلغي تمامًا موثوقية blockchain. ومما زاد الطين بلة ، لا توجد سلطة مركزية يمكن أن تتحمل المسؤولية وإصلاح الضرر.

عندما تم اختراع البيتكوين ، كان هناك تقدم كبير يتمثل في استخدام دليل على الحل الاحتمالي لمشكلة الجنرالات البيزنطيين. وقد وصفها ساتوشي ناكاموتو بالتفصيل في هذه الرسالة الإلكترونية .

استنتاج

في هذه المقالة ، درسنا بعض المفاهيم الأساسية للإجماع في الأنظمة الموزعة.