Byzantine Generals Problem

تخيّل وحدات عسكرية تحيط بمدينة. عليها الهجوم معًا أو الانسحاب معًا، لأن تفرقها قد يكون كارثيًا. يرسل القائد أوامره، لكن أحد المشاركين قد يخون الآخرين ويخبر كلًّا منهم برواية مختلفة. كيف يضمن المشاركون الموثوقون أن يتصرفوا بالطريقة نفسها؟ ليست هذه رواية معركة تاريخية، بل تجربة فكرية لفهم حواسيب تحتاج إلى سجلات متوافقة. فقد تحتاج عدة خوادم، أي حواسيب تقدّم خدمة مشتركة، إلى الاتفاق على ما إذا كانت دفعة معينة قد عولجت بالفعل. لا يكفي أن يتلقى كل خادم إجابة؛ بل يجب أن تؤدي الإجابات إلى قرار مشترك. [1] [9]

قدّم ليزلي لامبورت وروبرت شوستاك ومارشال بيز الصياغة المعروفة في يوليو 1982، بعد عملهم عام 1980 عن الاتفاق مع وجود أعطال. يمثّل الخائن مكوّنًا لم يعد سلوكه قابلًا للتوقع. فالحاسوب لا يتوقف فقط؛ قد يجيب جارًا إجابة صحيحة وآخر إجابة خاطئة، أو يحذف رسائل، أو يدّعي أنه شاهد شيئًا مختلفًا. وقد يكون السبب هجومًا أو خطأ برمجيًا. يصف العطل البيزنطي ما يراه الآخرون، لا نية الجهاز. ويشير اختصار BFT (Byzantine Fault Tolerance) إلى قدرة النظام على تحمّل هذا السلوك ضمن شروط محددة. [1] [2]

للمشكلة الأصلية شرطان. يطلب IC1 أن يقبل جميع المرؤوسين الموثوقين الأمر نفسه. ويضيف IC2 أنه إذا كان القائد موثوقًا أيضًا، فعليهم قبول الأمر الذي أرسله فعلًا. دون الشرط الثاني، تبدو قاعدة «انسحبوا دائمًا» حلًا، لكنها تتجاهل القائد الصادق. تميّز الأنظمة الحاسوبية بين السلامة، أي منع النتائج المتناقضة، وإمكان إحراز التقدم، أي الوصول إلى نتيجة أصلًا. وتحدد قواعد أخرى أي النتائج مقبول. ولا يثبت توافق السجلات وحده أن المعلومة المدخلة كانت صحيحة في العالم الخارجي. [1] [9]

لنسمّ القائد A ومرؤوسيه B وC. يتلقى C من A أمرًا بالهجوم، لكن B يقول إن القائد أمر بالانسحاب. هل يكذب B أم أرسل القائد أمرين مختلفين؟ دون توقيع يمكن التحقق منه بعد إعادة توجيه الرسالة، قد يعجز C عن التمييز بين الحالتين. وقد يواجه B الغموض نفسه. إذا أطاعا القائد دائمًا، يستطيع A الخائن تقسيمهما؛ وإذا تجاهلاه دائمًا، خالفا الشرط الخاص بالقائد الصادق. لذلك لا توجد في هذه المسألة ذات المشاركين الثلاثة والخائن المحتمل الواحد طريقة بلا توقيعات تنجح دائمًا. المشكلة نقص المعلومات التي تميّز الحالات، لا بطء الحواسيب. [1] [9]

في النموذج التقليدي بلا توقيعات، يتطلب تحمّل m من الخونة المحتملين عددًا لا يقل عن n ≥ 3m+1 من المشاركين؛ أي أربعة لمواجهة خائن واحد. يرمز n إلى العدد الإجمالي للمشاركين، وm إلى أكبر عدد من الخونة يُفترض أن يتحمله النظام. وليس المقصود إضافة صوت وعدّ الأغلبية مرة واحدة. يجعل إجراء OM(m) المشاركين يعيدون نقل ما سمعوه ويقيّمون الرسائل وفق قواعد مشتركة؛ أما الحالة الأساسية OM(0) فتأخذ قيمة القائد أو قيمة بديلة متفقًا عليها. يفترض النموذج مشاركين معروفين واتصالات مباشرة وتسليم الرسائل المرسلة على نحو صحيح ومعرفة المرسل المباشر وإمكان اكتشاف الرسالة الغائبة. إذن «بلا توقيعات» لا تعني «بلا أي تحقق من المصدر». ودون هذه الافتراضات لا يضمن الرقم أربعة شيئًا. [1] [9]

باستخدام توقيع رقمي قابل للتحقق، Digital Signature، يستطيع B أن يري C ما وقّعه القائد فعلًا. ينشئ البرنامج التوقيع بمفتاح خاص، وهو قيمة عددية سرية. ويتحقق الآخرون منه بالمفتاح العام المقابل، دون الحاجة إلى معرفة المفتاح الخاص. لا يستطيع الخائن تغيير أمر مشارك موثوق خفية أو تقليد توقيعه. تنشر خوارزمية الرسائل الموقّعة القيم الموقّعة وتطبّق قاعدة اختيار مشتركة. يزول في هذا النموذج شرط الأغلبية الصادقة المذكور، لكن تبقى افتراضات عدم إمكان تزوير التوقيعات وتسليم الرسائل وتوقيت الجولات. وتبحث دراسة دوليف وسترونغ عام 1983 بصورة أعمق عدد الجولات المطلوبة. حتى التوقيع الصحيح لا يضمن صدق المحتوى أو وصوله في الموعد، ولا يثبت أن المفتاح الخاص لم يُسرق. إنه دليل مصدر رسالة معينة، لا شهادة بأن مرسلها جدير بالثقة في كل شيء. [1] [3]

حين لا يرد خادم، لا يعرف الآخرون إن كان قد توقف أم أن اتصاله بطيء جدًا. تحدد نتيجة FLP، التي نشرها مايكل فيشر ونانسي لينش ومايكل باترسون عام 1985، هذه المعضلة بدقة. المقصود بالعملية هنا برنامج قيد التشغيل. والإجراء الحتمي يختار الخطوة التالية نفسها عند تطابق الحالة والمدخلات؛ ولا يختارها عشوائيًا. في نظام غير متزامن تمامًا، لا يُعرف حد أعلى لتأخر الرسائل، لا يضمن إجراء حتمي إتمام الاتفاق في كل تنفيذ مسموح إذا أمكن حتى لعملية واحدة أن تتوقف بسبب عطل. وينطبق ذلك مع تسليم موثوق لا حد معلومًا لتأخره. لا تعني النتيجة أن الاتفاق لا يحدث أبدًا. تضيف الأنظمة العملية افتراضات زمنية أو كاشف أعطال مناسبًا أو العشوائية. وعند انقسام الشبكة قد يكون الانتظار أكثر أمانًا من تأكيد نتيجتين متعارضتين. [4] [13] [8]

وصف ميغيل كاسترو وباربرا ليسكوف عام 1999 بروتوكول Practical Byzantine Fault Tolerance، أو PBFT، لخدمة تعمل على عدة نسخ معروفة. هذه النسخ تشغّل الخدمة على خوادم مختلفة وتعالج الطلبات نفسها باستمرار. ليست ملفات نسخ احتياطي محفوظة للاستخدام لاحقًا. يتحمل التكوين الأساسي n = 3f+1 عددًا قدره f من النسخ المعطوبة. من أربعة خوادم يمكن لواحد أن يتصرف بيزنطيًا؛ وتتداخل مجموعتان من ثلاثة خوادم في اثنين على الأقل، أحدهما موثوق على الأقل. تسمى مجموعة الموافقات المطلوبة نصابًا. لكن التداخل وحده لا يكفي: قواعد المراحل وتغيير القائد مهمة أيضًا. بدقة أكبر، تتطلب حالة prepared الطلب ورسالة pre-prepare و2f من رسائل prepare المتطابقة من نسخ مختلفة غير النسخة الرئيسية. ويتطلب التأكيد المحلي أيضًا 2f+1 من رسائل commit، وقد تشمل رسالة النسخة نفسها. تعالج مصادقة المصدر والأرقام التسلسلية ونقاط التحقق التزوير والتكرار والنمو غير المحدود للسجل. لا تعتمد السلامة على حدود زمنية، لكن استمرار التقدم يحتاج إلى شروط إضافية للتأخير. [5] [10] [11] [12]

لا يملك Bitcoin قائمة خوادم مغلقة محددة سلفًا. لو حصل كل حساب جديد على صوت، لأمكن المهاجم صنع أغلبية؛ وهذا هو Sybil Attack. لذلك يربط Proof of Work إنتاج الكتل بالعمل الحاسوبي. الكتلة مجموعة معاملات تُضاف إلى السجل المشترك. ترفض Full Node، وهي حاسوب يشغّل برنامجًا يتحقق من القواعد بصورة مستقلة، الكتل غير الصالحة أولًا، ثم تتبع الفرع الصالح صاحب أكبر عمل متراكم. لا يشغّل Bitcoin خوارزمية OM ولا PBFT؛ التفرعات المؤقتة جزء من عمله. ومع حصة كافية من القدرة الصادقة واتصال مناسب، تقلل التأكيدات الإضافية خطر إعادة كتابة التاريخ، لكنها لا تمنح عدم قابلية مطلقة للعكس. تبحث دراسات Bitcoin Backbone هذه الشروط: توافق السجلات ونمو السلسلة ونسبة الكتل التي يستطيع المشاركون الصادقون إنتاجها. [6] [7]

عند سماع «تحقق الشبكة إجماعًا»، ابحث عن إجابات محددة: من يحق له المشاركة، وماذا يتحكم فيه المهاجم، وكم قد تتأخر الرسائل، ومتى يمكن أن يتغير القرار؟ حتى Proof of Work لا يزيل كل المشكلات. يعزل Eclipse Attack عقدة عن أقران صادقين، وتستبعد الرقابة معاملات، ويقوم Selfish Mining على حجب كتل جرى تعدينها. وتبقى أخطاء البرمجيات وإمكان إعادة كتابة جزء من التاريخ عند امتلاك المهاجم قوة كافية. ومع ذلك، حتى أغلبية القدرة الحاسوبية لا تُجبر Full Node تعمل بصورة صحيحة على قبول كتلة تخالف قواعدها. تفيد حكاية الجنرالات لأنها تعلّمنا فحص شروط الاتفاق بدل الثقة باسم التقنية وحده. [6] [7] [8]