Byzantine Generals Problem

نشر Lamport وShostak وPease الاستعارة في ACM TOPLAS في يوليو 1982 لشرح الاتساق التفاعلي للأنظمة المنسوخة. على جنرالات منفصلين اختيار خطة واحدة، بينما يستطيع الخائن إرسال أقوال مختلفة لكل متلقٍ. العطل البيزنطي أشد من التوقف: قد يكذب المكوّن أو يناقض نفسه أو يحذف الرسائل أو يبدو صحيحًا لبعض النظام فقط. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

تفصل الورقة بين IC1: ينفذ كل الملازمين المخلصين الأمر نفسه، وIC2: إن كان القائد مخلصًا ينفذون أمره. تقابلها حديثًا خصائص الاتفاق أو السلامة، والصلاحية، والإنهاء أو الحيوية. لا معنى للضمان دون تحديد نموذج الشبكة والتوثيق والعدد الأقصى للأعطال. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

في نموذج الرسائل الشفهية يُعرف المرسل المباشر ويُكتشف الغياب ويتصل كل زوج، لكن الخائن قد يرسل قيمًا مختلفة. يعيد OM(m) تمرير القيم تكراريًا ثم يطبق أغلبية حتمية. تحمل m عمليات بيزنطية يتطلب 3m+1 مشاركًا على الأقل، أي أكثر من الثلثين مخلصين. لا يستطيع ثلاثة تحمل خائن لأن المخلص لا يميز القائد الكاذب من الزميل الكاذب. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]

تكشف التوقيعات غير القابلة للتزوير التناقض وتمنع تعديل أمر وقعه مشارك مخلص. يمرر الخوارزم القيم الموقعة الجديدة ويختار حتميًا من المجموعة. تحت الفرضيات المثالية يمكن تحمل أي عدد من الخونة. لكن التوقيع يثبت المصدر لا صدق المحتوى أو وصوله في الوقت أو سلامة مفتاح مخترق؛ وقد شدد Dolev وStrong حدود الجولات لاحقًا. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]

تعتمد إمكانية ضمان التقدم على التوقيت. تبين نتيجة Fischer–Lynch–Paterson لعام 1985 أن نظام رسائل حتميًا غير متزامن بالكامل قد يملك تنفيذًا مسموحًا لا ينهي الإجماع حتى مع عملية واحدة فقط قد تتوقف. لا تقول FLP إن الأنظمة الفعلية لا تتفق أبدًا. يتطلب ضمان التقدم افتراضات إضافية، مثل حدود زمنية تسري في النهاية أو كاشف أعطال بخصائص محددة، أو الانتقال إلى بروتوكول عشوائي. تعيين قائد وحده لا يكفي. وقد يتوقف بروتوكول آمن عن إتمام العمليات خلال انقسام طويل للشبكة. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]

يحوّل PBFT الذي قدمه ميغيل كاسترو وباربرا ليسكوف عام 1999 الاتفاق البيزنطي إلى آلة حالات مكررة. يتحمل التكوين الأساسي n = 3f+1 عددًا قدره f من النسخ البيزنطية. تشمل حالة الاستعداد رسالة pre-prepare من النسخة الرئيسية و2f من رسائل prepare المتطابقة؛ ويتطلب الإقرار المحلي الاستعداد و2f+1 من رسائل commit المتطابقة. تمنع تقاطعات الأنصبة وقواعد تغيير العرض الإقرارات المتناقضة. يعالج التوثيق والأرقام التسلسلية ونقاط التحقق وتغييرات العرض التزوير وإعادة الإرسال ونمو السجل والقائد المعطل. تختلف مجموعة النسخ المعروفة والنهائية الحتمية عن شبكة Proof of Work المفتوحة. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]

لا يشغّل Bitcoin خوارزمية OM أو PBFT ولا يعدّ العقد ذات الهويات المسماة. يزن Proof of Work المقاوم لهجمات Sybil السجلات المتنافسة بالعمل المتراكم؛ ويرفض كل Full Node مستقلًا الكتل المخالفة لقواعد الإجماع ويتبع السلسلة الصالحة ذات أكبر عمل تراكمي. التفرعات المؤقتة متوقعة. في ظل افتراضات تفوق العمل النزيه والاتصال، ينخفض احتمال إعادة الكتابة مع عمق التأكيدات، لكنه ليس استحالة رياضية للعكس. يصوغ نموذج Bitcoin Backbone البادئة المشتركة ونمو السلسلة وجودتها مع تحديد حصة عمل المهاجم وظروف الشبكة صراحة. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]

القول إن Bitcoin حل مشكلة الجنرالات البيزنطيين اختصار يخفي تغير النموذج. يبدأ الاتفاق الكلاسيكي بمجموعة ثابتة ذات هويات معروفة وحد أعطال f؛ ويسمح Bitcoin بمشاركين متغيرين ذوي أسماء مستعارة وبمورد خارجي نادر. لا تزال ضماناته تتطلب افتراضات محددة عن تسليم الرسائل. يحد Proof of Work من تأثير هويات Sybil، لكنه لا يمنع هجمات العزل أو الرقابة أو التعدين الأناني أو أخطاء البرمجيات أو إعادة التنظيم بأغلبية معدل التجزئة. يجب أن يحدد نموذج التهديد المهاجم والتوقيت والعضوية والنهائية؛ ولا يكفي وصف BFT وحده. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]