تولید تصادفی توزیع‌شده از طریق توافق تقریبی: پروتکل‌های ناهمگام مقاوم در برابر خطای بیزانس

1 مقدمه

تصادفی‌سازی یک ابزار حیاتی در طراحی سیستم‌های توزیع‌شده است. پایه سکه مشترک که به اعضای سیستم امکان می‌دهد بر روی یک عدد تصادفی غیرقابل پیش‌بینی توافق کنند، به‌طور خاص برای پروتکل‌هایی مانند توافق بیزانس، تولید کلید توزیع‌شده و انتخاب رهبر مفید ثابت شده است. با این حال، پیاده‌سازی یک پروتکل سکه مشترک کاملاً تصادفی در سیستم‌های ناهمگام مستعد خطا به دلیل نتیجه عدم امکان FLP غیرممکن است.

این مقاله دو آرامش از سکه مشترک کامل را معرفی می‌کند: (1) سکه مشترک تقریبی که اعداد تصادفی نزدیک به هم تولید می‌کند، و (2) سکه مشترک مونت‌کارلو که یک عدد تصادفی مشترک با احتمال شکست دلخواه کوچک، اما غیر صفر، تولید می‌کند. پروتکل‌های ما بر روی پایه توافق تقریبی ساخته شده‌اند و تا یک سوم فرآیندهای بیزانس را بدون راه‌اندازی قابل اعتماد یا زیرساخت کلید عمومی تحمل می‌کنند.

2 پیشینه و کارهای مرتبط

3 طراحی پروتکل

4 تحلیل فنی

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  # total processes
        self.f = f  # maximum Byzantine failures
        self.delta = delta  # failure probability
        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 مراجع

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