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

مشكلة الجنرالين

مشكلة الجنرالين هي حالة خاصة لمشكلة الجنرالات البيزنطيين. تم اقتراح المشكلة وإثباتها على عدم قابلية الحل لأول مرة من قبل EA Akkoyunlu و K.Ekanadham و R.V. Huber في ورقتهم عام 1975 "بعض القيود والمقايضات في تصميم اتصالات الشبكة". في عام 1978 ، أطلق جيم جراي رسميا على هذه المشكلة اسم "مشكلة الجنرالات" في كتابه "ملاحظات حول أنظمة تشغيل قاعدة البيانات". في الأصل ، تم استخدامه لتحليل قضايا تحقيق توافق في الآراء من خلال التواصل عبر رابط اتصال غير موثوق. يستخدم الآن بشكل شائع لتوضيح قضايا الاتساق وتوافق الآراء في الأنظمة الموزعة.

تعريف المشكلة:
جيشان من البلد A، يقود كل منهما جنرال، يستعدان لمهاجمة جيش من البلد B. يحاصر جيش بلد B في وادٍ، مع جيشي A موجودين على التلال على جانبي الوادي. ومع ذلك، الطريق الوحيد بين جيشي A يمر عبر الوادي. جيش B أقوى من أي من جيشي A بشكل فردي، ولكن إذا هاجم الجيشان A معًا، يمكنهما هزيمة جيش B.
مشكلة: هل يمكن إيجاد خوارزمية تُتيح لجنرالي جيشي أن يتفقا على هجوم متزامن؟ قد تتضمن الخوارزمية إرسال واستقبال الرسائل.
الحل: مشكلة الجنرالات الكلاسيكية غير قابلة للحل. لا يوجد بروتوكول يمكن أن يضمن أن جيشي A سينسقان هجومهما بنجاح. ومع ذلك ، في الأنظمة العملية ، يمكن معالجة المشكلات بشكل موثوق نسبيا ، مثل آلية "المصافحة الثلاثية" في بروتوكول TCP.

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

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

الحل: إذا كان عدد الجنرالات (العقد) في نظام بيزنطي هو Z وكان عدد الجنرالات غير الموثوقة (الخائنة) هو X، فإنه يمكن فقط عندما يكون Z ≥ 3X + 1 أن بروتوكول تحمل العطل البيزنطي (BFT) يضمن استقرار النظام.
في الأنظمة العملية ، تُصنف الفشل الناتج عن جعل العقد غير مستجيبة باسم "أخطاء الانهيار" ، في حين تُصنف العقد التي تزور أو تتلاعب بالرسائل باسم "أخطاء بيزنطية".

تصنيف خوارزمية التوافق

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

خوارزميات عدم تحمل الأخطاء البيزنطية

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

خوارزميات تحمل الخطأ البيزنطية

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