التوزيع العشوائي من خلال الاتفاق التقريبي: بروتوكولات بيزنطية متسامحة مع الأعطال في الأنظمة غير المتزامنة

1 المقدمة

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

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

2 الخلفية والأعمال ذات الصلة

2.1 البدائيات المشتركة للعملة

يجب أن يفي بروتوكول العملة المشتركة المثالية بثلاث خصائص:

الإنهاء: كل عملية صحيحة تخرج في النهاية بقيمة ما
الاتفاق: لا تخرج عمليتان صحيحتان بقيم مختلفتين
العشوائية: يجب أن تكون قيمة الخرج موزعة بشكل موحد على المجال D، |D| ≥ 2

التنفيذات السابقة إما تفترض أنظمة متزامنة أو شبه متزامنة مع إعداد موثوق. يركز عملنا على الأنظمة غير المتزامنة دون مثل هذه الافتراضات.

2.2 الاتفاق التقريبي

يسمح الاتفاق التقريبي للعمليات باتخاذ قرار بقيم قريبة من بعضها البعض ضمن تسامح محدد مسبقًا ε. يمكن التعبير عن دالة التقارب كالتالي:

$v_i^{r+1} = \frac{\sum_{j \in S} v_j^r}{|S|}$ حيث $S$ هي مجموعة القيم المستلمة ضمن النطاق المقبول

تشكل هذه البدائية الأساس لتنفيذنا للعملة المشتركة التقريبية.

3 تصميم البروتوكول

3.1 العملة المشتركة التقريبية

يضمن بروتوكول العملة المشتركة التقريبية الخاص بنا أن جميع العمليات الصحيحة تخرج بقيم ضمن مسافة ε من بعضها البعض بعد k جولة. يتقارب البروتوكول بسرعة أسية مع عدد الجولات:

$\epsilon_k \leq \epsilon_0 \cdot \alpha^k$ حيث $\alpha < 1$ هو معدل التقارب

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

3.2 العملة المشتركة مونت كارلو

تضمن العملة المشتركة مونت كارلو الاتفاق باحتمالية 1-δ لأي δ > 0 صغيرة بشكل تعسفي. تتناقص احتمالية الفشل بشكل أسي مع عدد الجولات:

$P[\text{failure}] \leq e^{-\beta k}$ لثابت ما $\beta > 0$

يجمع هذا البروتوكول بين الاتفاق التقريبي والتقنيات التشفيرية لتحقيق الخصائص المرغوبة دون إعداد موثوق.

4 التحليل التقني

4.1 الأسس الرياضية

يعتمد أمان بروتوكولاتنا على خصائص تقارب الاتفاق التقريبي في وجود أعطال بيزنطية. لنظام به n عملية و f < n/3 أعطال بيزنطية، نثبت:

$\lim_{k \to \infty} \max_{i,j \in \text{correct}} |v_i^k - v_j^k| = 0$

يعتمد معدل التقارب على طوبولوجيا الشبكة ودالة الاتفاق المحددة المستخدمة.

4.2 تحليل الأمان

بروتوكولاتنا مقاومة ضد الخصوم البيزنطيين التكيفيين الذين يتحكمون في ما يصل إلى f < n/3 عملية. تتبع براهين الأمان نموذج المحاكاة، موضحة أنه لا يمكن لأي بيئة التمييز بين البروتوكول الحقيقي والوظيفة المثالية.

5 النتائج التجريبية

قيمنا بروتوكولاتنا في شبكات غير متزامنة محاكاة بأعداد متفاوتة من العمليات (n = 10 إلى 100) ومعدلات الأعطال البيزنطية (f < n/3). تظهر النتائج:

تقارب أسي للاتفاق خلال 5-10 جولات للمعاملات النموذجية
تعقيد اتصال O(n³log n) للاتفاق البيزنطي الثنائي
تحسن كبير عن حلول O(n⁴) السابقة

يوضح الكود الزائف التالي جولة الاتفاق التقريبي الأساسية:

function ApproximateAgreementRound(value, round):
    broadcast("PROPOSE", value, round)
    received = wait_for_messages(n - f, round)
    valid_values = filter_within_range(received, value - ε, value + ε)
    new_value = median(valid_values)  // or average for continuous domains
    return new_value

6 تفاصيل التنفيذ

يستخدم تنفيذنا البدائيات التشفيرية القياسية بما في ذلك دوال الهاش والتوقيعات الرقمية. هيكل الخوارزمية الأساسي:

class MonteCarloCommonCoin:
    def __init__(self, n, f, delta):
        self.n = n  # إجمالي العمليات
        self.f = f  # الحد الأقصى للأعطال البيزنطية
        self.delta = delta  # احتمالية الفشل
        self.round = 0
        
    def generate_coin(self):
        while True:
            self.round += 1
            estimate = self.approximate_agreement_round()
            if self.consensus_achieved(estimate):
                return self.finalize_output(estimate)
            if self.round > self.required_rounds():
                return self.fallback_output()

7 التطبيقات والاتجاهات المستقبلية

التطبيقات الحالية:

الاتفاق البيزنطي بتعقيد اتصال O(n³log n)
مشكلة المجموعات الفرعية العشوائية المتقاطعة باستخدام العملة المشتركة التقريبية مع رموز جراي
انتخاب القائد في أنظمة البلوكشين بدون إذن

اتجاهات البحث المستقبلية:

تكييف البروتوكولات للتشفير المقاوم للكم
التوسع لإعدادات العضوية الديناميكية
التحسين لظروف الشبكة الواقعية مع تزامن جزئي
التكامل مع بنى البلوكشين المجزأة

8 المراجع

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM.
Rabin, M. O. (1983). Randomized Byzantine generals. Symposium on Foundations of Computer Science.
Cachin, C., Kursawe, K., & Shoup, V. (2000). Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. PODC.
Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. (2016). The honey badger of BFT protocols. CCS.
Abraham, I., Malkhi, D., & Spiegelman, A. (2019). Asymptotically optimal validated asynchronous Byzantine agreement. PODC.

التحليل الأصلي

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

يمثل تحقيق المؤلفين لتعقيد اتصال O(n³log n) للاتفاق البيزنطي الثنائي تحسنًا كبيرًا عن حلول O(n⁴) السابقة. يتماشى هذا التقدم مع الاتجاهات في بحث الأنظمة الموزعة القابلة للتطوير، حيث يعد تقليل عبء الاتصال أمرًا بالغ الأهمية للنشر العملي. دفعت مخاوف الكفاءة المماثلة التطورات في مجالات أخرى، مثل تحسين شبكات الخصومة التوليدية (GANs) في التعلم الآلي، حيث أظهر CycleGAN كيف يمكن جعل المفاهيم النظرية عملية من خلال التصميم الخوارزمي الدقيق.

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

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

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

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