আনুমানিক সম্মতি থেকে বিতরণকৃত র্যান্ডমনেস: অ্যাসিঙ্ক্রোনাস বাইজেন্টাইন ফল্ট-টলারেন্ট প্রোটোকল

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 মন্টে কার্লো কমন কয়েন

মন্টে কার্লো কমন কয়েন নির্বিচারে ছোট δ > 0 এর জন্য 1-δ সম্ভাব্যতা সহ সম্মতি নিশ্চিত করে। ব্যর্থতার সম্ভাবনা রাউন্ড সংখ্যার সাথে সূচকীয়ভাবে হ্রাস পায়:

$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⁴) সমাধানের উপর একটি substancial উন্নতি প্রতিনিধিত্ব করে। এই অগ্রগতি স্কেলযোগ্য বিতরণকৃত সিস্টেম গবেষণায় প্রবণতাগুলির সাথে সামঞ্জস্যপূর্ণ, যেখানে ব্যবহারিক স্থাপনার জন্য কমিউনিকেশন ওভারহেড হ্রাস করা অত্যন্ত গুরুত্বপূর্ণ। অনুরূপ দক্ষতা উদ্বেগগুলি মেশিন লার্নিংয়ে জেনারেটিভ অ্যাডভারসারিয়াল নেটওয়ার্ক (GANs) এর উন্নয়নে চালিত করেছে, যেখানে CycleGAN প্রদর্শন করেছিল কিভাবে সতর্ক অ্যালগরিদমিক ডিজাইনের মাধ্যমে তাত্ত্বিক ধারণাগুলিকে ব্যবহারিক করা যেতে পারে।

ইন্টারসেক্টিং র্যান্ডম সাবসেটস সমস্যা সমাধানের জন্য গ্রে কোডের সাথে আনুমানিক সম্মতির সংমিশ্রণ বিশেষভাবে উদ্ভাবনী। এই পদ্ধতিটি প্রদর্শন করে কিভাবে ক্লাসিক্যাল কম্পিউটার সায়েন্স ধারণাগুলিকে আধুনিক বিতরণকৃত সিস্টেম চ্যালেঞ্জের জন্য পুনরায় ব্যবহার করা যেতে পারে। এই কৌশলটি বিতরণকৃত স্টোরেজ সিস্টেমে কোডিং থিওরি অ্যাপ্লিকেশনের সাথে মিল রয়েছে, যেখানে দক্ষ ডেটা বিতরণ এবং পুনরুদ্ধার নির্দিষ্ট ইন্টারসেকশন বৈশিষ্ট্য সহ গাণিতিক কাঠামোর উপর নির্ভর করে।

একটি নিরাপত্তা দৃষ্টিকোণ থেকে, বিশ্বস্ত সেটআপ বা PKI ছাড়াই অ্যাডাপ্টিভ বাইজেন্টাইন অ্যাডভারসারির বিরুদ্ধে স্থিতিস্থাপকতা উল্লেখযোগ্য। এটি বর্তমান বিকেন্দ্রীকৃত সিস্টেমগুলির প্রবণতাগুলির সাথে সামঞ্জস্যপূর্ণ যা ট্রাস্ট মিনিমাইজেশনকে অগ্রাধিকার দেয়। এই পদ্ধতিটি জিরো-নলেজ প্রুফ সিস্টেমের সাথে দার্শনিক মিল ভাগ করে, যেখানে ক্রিপ্টোগ্রাফিক কৌশলগুলি অন্তর্নিহিত ডেটা প্রকাশ না করে বা বিশ্বস্ত কর্তৃপক্ষের উপর নির্ভর না করে যাচাইকরণ সক্ষম করে।

প্রোটোকলগুলিতে প্রদর্শিত সূচকীয় কনভার্জেন্স রেট আলোচিত তাৎক্ষণিক ব্যবহারের ক্ষেত্রগুলির বাইরে সম্ভাব্য অ্যাপ্লিকেশনগুলি সুপারিশ করে। অনুরূপ কনভার্জেন্স বৈশিষ্ট্যগুলি অপ্টিমাইজেশন অ্যালগরিদম এবং মেশিন লার্নিংয়ে মূল্যবান বলে প্রমাণিত হয়েছে, যেখানে সম্মতিতে দ্রুত কনভার্জেন্স দক্ষ বিতরণকৃত গণনা সক্ষম করে। MIT-এর কম্পিউটার সায়েন্স এবং আর্টিফিশিয়াল ইন্টেলিজেন্স ল্যাবরেটরির মতো প্রতিষ্ঠান থেকে গবেষণায় উল্লেখিত হিসাবে, এই ধরনের বৈশিষ্ট্যগুলি সম্পদ সীমাবদ্ধতা সহ এজ কম্পিউটিং পরিবেশে বিশেষভাবে মূল্যবান।

ভবিষ্যতের কাজ হোমোমরফিক এনক্রিপশন এবং সিকিউর মাল্টি-পার্টি কম্পিউটেশনের সাথে সংযোগগুলি অন্বেষণ করতে পারে, যেখানে বিতরণকৃত র্যান্ডমনেস জেনারেশন একটি গুরুত্বপূর্ণ ভূমিকা পালন করে। এই গবেষণাপত্রে উন্নত কৌশলগুলি ফেডারেটেড লার্নিং সিস্টেমেও অ্যাপ্লিকেশন খুঁজে পেতে পারে, যেখানে কেন্দ্রীয় কর্তৃপক্ষ ছাড়াই বিতরণকৃত নোড জুড়ে র্যান্ডমনেস সমন্বয় করা এই গবেষণায় সমাধান করা চ্যালেঞ্জগুলির অনুরূপ চ্যালেঞ্জ উপস্থাপন করে।