2025-11-21T20:28:23.433071

OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA

Chen
In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message $\boldsymbol{w}$ with expected $O(n |\boldsymbol{w}|\log n + n^2 \log q)$ communication bits, expected $O(n^2)$ messages, expected $O(\log n)$ rounds, and expected $O(\log n)$ common coins, under optimal resilience $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, $q$ becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^2 \log n)$ communication bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under a relaxed resilience (RR) of $n \geq 5t + 1$. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^3)$ bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under optimal resilience $n \geq 3t + 1$.
academic

OciorMVBA: নিকট-সর্বোত্তম ত্রুটি-মুক্ত অ্যাসিঙ্ক্রোনাস MVBA

মৌলিক তথ্য

  • পেপার আইডি: 2501.00214
  • শিরোনাম: OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA
  • লেখক: Jinyuan Chen
  • শ্রেণীবিভাগ: cs.CR (ক্রিপ্টোগ্রাফি এবং নিরাপত্তা), cs.DC (বিতরণকৃত কম্পিউটিং), cs.IT (তথ্য তত্ত্ব), math.IT (তথ্য তত্ত্ব)
  • প্রকাশনার সময়: ২০২৪ সালের ৩১ ডিসেম্বর (arXiv প্রিপ্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2501.00214

সারসংক্ষেপ

এই পেপারটি একটি ত্রুটি-মুক্ত, তথ্য-তাত্ত্বিক নিরাপদ অ্যাসিঙ্ক্রোনাস বহু-মূল্য যাচাইকরণ বাইজান্টাইন সামঞ্জস্য (MVBA) প্রোটোকল OciorMVBA প্রস্তাব করে। এই প্রোটোকলটি সর্বোত্তম ত্রুটি সহনশীলতা n ≥ 3t + 1 সহ n নোডের নেটওয়ার্কে বার্তা w এর জন্য MVBA সামঞ্জস্য অর্জন করে, যার প্রত্যাশিত O(n|w|log n + n²log q) যোগাযোগ বিট, প্রত্যাশিত O(n²) বার্তা সংখ্যা, প্রত্যাশিত O(log n) রাউন্ড এবং প্রত্যাশিত O(log n) সাধারণ মুদ্রার জটিলতা রয়েছে। অতিরিক্তভাবে, দুটি ভেরিয়েন্ট প্রোটোকল প্রস্তাব করা হয়েছে: OcitorMVBArr যা শিথিল ত্রুটি সহনশীলতা n ≥ 5t + 1 এর অধীনে O(1) রাউন্ড জটিলতা অর্জন করে, এবং হ্যাশ-ভিত্তিক OciorMVBAh যা সর্বোত্তম ত্রুটি সহনশীলতার অধীনে O(1) রাউন্ড জটিলতা অর্জন করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

বহু-মূল্য যাচাইকরণ বাইজান্টাইন সামঞ্জস্য (MVBA) বিতরণকৃত সিস্টেম এবং ক্রিপ্টোগ্রাফির একটি মূল নির্মাণ ব্লক, যা ২০০১ সালে Cachin এবং অন্যদের দ্বারা প্রবর্তিত হয়েছিল। MVBA-তে, বিতরণকৃত নোডগুলি তাদের নিজ নিজ ইনপুট মান প্রস্তাব করে এবং পূর্বনির্ধারিত প্রেডিকেট ফাংশন (বাহ্যিক বৈধতা) সন্তুষ্ট করে এমন একটি মানের উপর সামঞ্জস্য খোঁজে।

গবেষণার গুরুত্ব

  1. তাত্ত্বিক ভিত্তি: Fischer, Lynch এবং Paterson এর যুগান্তকারী কাজ দেখায় যে অ্যাসিঙ্ক্রোনাস পরিবেশে কোনো নির্ধারণীয় MVBA প্রোটোকল বিদ্যমান নেই, তাই যেকোনো অ্যাসিঙ্ক্রোনাস MVBA প্রোটোকলকে অবশ্যই র্যান্ডমনেস প্রবর্তন করতে হবে
  2. ব্যবহারিক চাহিদা: বিতরণকৃত সিস্টেমগুলিকে বাইজান্টাইন ত্রুটির উপস্থিতিতে অ্যাসিঙ্ক্রোনাস নেটওয়ার্কে নির্ভরযোগ্য সামঞ্জস্য অর্জন করতে হবে
  3. নিরাপত্তা প্রয়োজনীয়তা: সাধারণ মুদ্রা ছাড়া ক্রিপ্টোগ্রাফিক অনুমানের উপর নির্ভর না করে তথ্য-তাত্ত্বিক নিরাপত্তা নিশ্চিত করতে হবে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

সারণী I এর তুলনা থেকে দেখা যায় যে বিদ্যমান MVBA প্রোটোকলগুলির নিম্নলিখিত সমস্যা রয়েছে:

  • বেশিরভাগ থ্রেশহোল্ড স্বাক্ষর বা হ্যাশিং এর মতো ক্রিপ্টোগ্রাফিক অনুমানের উপর নির্ভর করে
  • যোগাযোগ জটিলতা বেশি, বিশেষত ক্রিপ্টোগ্রাফিক অনুমান ছাড়াই
  • রাউন্ড জটিলতা এবং সাধারণ মুদ্রা ব্যবহারের দক্ষতা উন্নত করার অবকাশ রয়েছে

মূল অবদান

  1. OciorMVBA প্রোটোকল প্রস্তাব: সর্বোত্তম ত্রুটি সহনশীলতা n ≥ 3t + 1 এর অধীনে নিকট-সর্বোত্তম যোগাযোগ জটিলতা O(n|w|log n + n²log q) অর্জনকারী প্রথম ত্রুটি-মুক্ত, তথ্য-তাত্ত্বিক নিরাপদ অ্যাসিঙ্ক্রোনাস MVBA প্রোটোকল
  2. OciorMVBArr প্রোটোকল ডিজাইন: শিথিল ত্রুটি সহনশীলতা n ≥ 5t + 1 এর অধীনে O(n|w| + n²log n) যোগাযোগ জটিলতা এবং O(1) রাউন্ড জটিলতা অর্জনকারী প্রোটোকল
  3. OciorMVBAh প্রোটোকল নির্মাণ: হ্যাশ-ভিত্তিক প্রোটোকল, সর্বোত্তম ত্রুটি সহনশীলতার অধীনে O(n|w| + n³) যোগাযোগ জটিলতা এবং O(1) রাউন্ড জটিলতা অর্জন করে
  4. নতুন আদিম প্রবর্তন: অ্যাসিঙ্ক্রোনাস পক্ষপাতী বাইনারি বাইজান্টাইন সামঞ্জস্য (ABBBA) এবং অ্যাসিঙ্ক্রোনাস সম্পূর্ণ তথ্য বিচ্ছুরণ (ACID) এর মতো নতুন নির্মাণ ব্লক প্রস্তাব করে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

ইনপুট: প্রতিটি সৎ নোড প্রেডিকেট ফাংশন Predicate(w) = true সন্তুষ্ট করে এমন ইনপুট মান w প্রস্তাব করে আউটপুট: সমস্ত সৎ নোড চূড়ান্তভাবে একই মান w' আউটপুট করে, এবং Predicate(w') = true সীমাবদ্ধতা: সামঞ্জস্য, সমাপ্তি এবং বাহ্যিক বৈধতার তিনটি বৈশিষ্ট্য সন্তুষ্ট করে

OciorMVBA প্রোটোকল আর্কিটেকচার

সামগ্রিক ডিজাইন

OciorMVBA একটি পুনরাবৃত্তিমূলক প্রোটোকল, যার প্রধান উপাদানগুলি অন্তর্ভুক্ত করে:

  • RMVBA(ID, p): পুনরাবৃত্তিমূলক MVBA প্রোটোকল
  • SHMDM: শক্তিশালী সৎ বহুমত বিতরণকৃত মাল্টিকাস্ট
  • OciorRBA: নির্ভরযোগ্য বাইজান্টাইন সামঞ্জস্য
  • ABBBA: অ্যাসিঙ্ক্রোনাস পক্ষপাতী বাইনারি বাইজান্টাইন সামঞ্জস্য
  • ABBA: অ্যাসিঙ্ক্রোনাস বাইনারি বাইজান্টাইন সামঞ্জস্য

মূল অ্যালগরিদম প্রবাহ

  1. নেটওয়ার্ক বিভাজন: নেটওয়ার্ক Sp কে দুটি অসংযুক্ত উপসেট S2p এবং S2p+1 এ বিভক্ত করুন
  2. পুনরাবৃত্তিমূলক আহ্বান: সাব-নেটওয়ার্কে সমান্তরালভাবে RMVBA সাব-প্রোটোকল সম্পাদন করুন
  3. বার্তা প্রচার: SHMDM প্রোটোকলের মাধ্যমে সাব-প্রোটোকলের আউটপুট প্রচার করুন
  4. সামঞ্জস্য পরীক্ষা: OciorRBA ব্যবহার করে বার্তার নির্ভরযোগ্যতা যাচাই করুন
  5. নির্বাচন প্রক্রিয়া: অর্ডার করা নির্বাচন এবং ABBBA/ABBA প্রোটোকলের মাধ্যমে চূড়ান্ত আউটপুট নির্ধারণ করুন

মূল প্রযুক্তিগত বিবরণ

Ready-Finish-Confirm প্রক্রিয়া:

ধাপ ১: সাব-প্রোটোকল আউটপুট → SHMDM প্রচার
ধাপ ২: SHMDM আউটপুট → OciorRBA যাচাইকরণ
ধাপ ৩: OciorRBA আউটপুট vi=1 → Iready[θ]=1 সেট করুন, READY বার্তা পাঠান
ধাপ ৪: পর্যাপ্ত READY বার্তা পান → Ifinish[θ]=1 সেট করুন, FINISH বার্তা পাঠান  
ধাপ ৫: পর্যাপ্ত FINISH বার্তা পান → Iconfirm[θ]=1 সেট করুন

ABBBA প্রোটোকল:

  • ইনপুট: বাইনারি জোড় (a1, a2)
  • পক্ষপাতী বৈধতা: যদি t+1 টি সৎ নোড a2=1 ইনপুট করে, তবে 1 আউটপুট করুন
  • পক্ষপাতী সম্পূর্ণতা: যদি 1 আউটপুট করা হয়, তবে কমপক্ষে একটি সৎ নোড a1=1 বা a2=1 ইনপুট করেছে

OciorRBA প্রোটোকল ডিজাইন

COOL এবং OciorCOOL প্রোটোকলের উপর ভিত্তি করে সম্প্রসারিত, তিনটি পর্যায় অন্তর্ভুক্ত করে:

  1. পর্যায় ১: প্রতীক বিনিময় এবং লিঙ্ক সূচক আপডেট
  2. পর্যায় ২: সাফল্য সূচক প্রক্রিয়াকরণ
  3. পর্যায় ৩: অনলাইন ত্রুটি সংশোধন এবং বার্তা পুনর্নির্মাণ

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. পুনরাবৃত্তিমূলক আর্কিটেকচার: নেটওয়ার্ক বিভাজন এবং পুনরাবৃত্তিমূলক আহ্বানের মাধ্যমে লগারিদমিক রাউন্ড জটিলতা অর্জন করুন
  2. পক্ষপাতী সামঞ্জস্য: ABBBA প্রোটোকল নির্দিষ্ট শর্তে দ্রুত সমাপ্তি প্রদান করে
  3. অনলাইন ত্রুটি সংশোধন: Reed-Solomon কোড বা Expander কোড ব্যবহার করে দক্ষ ত্রুটি সংশোধন বাস্তবায়ন করুন
  4. ক্রিপ্টোগ্রাফিক অনুমান ছাড়াই: সাধারণ মুদ্রা ছাড়া অন্য কোনো ক্রিপ্টোগ্রাফিক আদিমের উপর নির্ভর করবেন না

পরীক্ষামূলক সেটআপ

তাত্ত্বিক বিশ্লেষণ কাঠামো

পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ পরিচালনা করে, নিম্নলিখিত উপায়ে প্রোটোকল বৈশিষ্ট্য যাচাই করে:

জটিলতা বিশ্লেষণ:

  • যোগাযোগ জটিলতা: পুনরাবৃত্তিমূলক সম্পর্ক বিশ্লেষণ
  • রাউন্ড জটিলতা: নেটওয়ার্ক গাছের গভীরতা বিশ্লেষণ
  • বার্তা জটিলতা: প্রোটোকল ইন্টারঅ্যাকশন সংখ্যা পরিসংখ্যান

নিরাপত্তা প্রমাণ:

  • সামঞ্জস্য: Lemma 3 এর মাধ্যমে প্রমাণিত
  • সমাপ্তি: নেটওয়ার্ক চেইন বিশ্লেষণের মাধ্যমে (Lemma 2, 4)
  • বাহ্যিক বৈধতা: প্রেডিকেট যাচাইকরণের মাধ্যমে নিশ্চিত

তুলনা মানদণ্ড

বিদ্যমান MVBA প্রোটোকলের সাথে তুলনা, অন্তর্ভুক্ত করে:

  • Cachin et al. 1 - থ্রেশহোল্ড স্বাক্ষর ভিত্তিক
  • Abraham et al. 8 - অপ্টিমাইজড থ্রেশহোল্ড স্বাক্ষর স্কিম
  • Dumbo-MVBA 9 - দক্ষ থ্রেশহোল্ড স্বাক্ষর প্রোটোকল
  • Duan et al. 10 - হ্যাশিং এবং ক্রিপ্টোগ্রাফিক অনুমান ছাড়াই ভিত্তিক প্রোটোকল

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

OciorMVBA কর্মক্ষমতা:

  • যোগাযোগ জটিলতা: O(n|w|log n + n²log q) বিট
  • বার্তা জটিলতা: O(n²)
  • রাউন্ড জটিলতা: O(log n)
  • সাধারণ মুদ্রা: O(log n)

OciorMVBArr কর্মক্ষমতা (n ≥ 5t + 1):

  • যোগাযোগ জটিলতা: O(n|w| + n²log n) বিট
  • রাউন্ড জটিলতা: O(1)
  • সাধারণ মুদ্রা: O(1)

OciorMVBAh কর্মক্ষমতা:

  • যোগাযোগ জটিলতা: O(n|w| + n³) বিট
  • রাউন্ড জটিলতা: O(1)
  • সাধারণ মুদ্রা: O(1)

জটিলতা বিশ্লেষণ

পুনরাবৃত্তিমূলক সম্পর্কের মাধ্যমে:

fTB(ñp) = β1ñp|w| + β2ñp²log q + fTB(⌊ñp/2⌋) + fTB(⌈ñp/2⌉)

মোট যোগাযোগ জটিলতা O(n|w|log n + n²log q) প্রমাণিত হয়েছে।

প্রোটোকল সঠিকতা

একাধিক লেম্মার মাধ্যমে প্রমাণিত যে প্রোটোকল MVBA এর তিনটি মূল বৈশিষ্ট্য সন্তুষ্ট করে:

  • উপপাদ্য ১: সামঞ্জস্য এবং সমাপ্তি
  • উপপাদ্য ২: বাহ্যিক বৈধতা
  • উপপাদ্য ৩: যোগাযোগ এবং রাউন্ড জটিলতা

সম্পর্কিত কাজ

MVBA প্রোটোকল বিকাশ

  1. প্রাথমিক কাজ: Cachin এবং অন্যরা প্রথম MVBA ধারণা প্রবর্তন করেছেন
  2. স্বাক্ষর-ভিত্তিক পদ্ধতি: Abraham এবং অন্যরা, Dumbo-MVBA ইত্যাদি থ্রেশহোল্ড স্বাক্ষর-ভিত্তিক প্রোটোকল অপ্টিমাইজ করেছেন
  3. স্বাক্ষর-মুক্ত পদ্ধতি: Duan এবং অন্যরা হ্যাশিং-ভিত্তিক স্বাক্ষর-মুক্ত প্রোটোকল প্রস্তাব করেছেন
  4. তথ্য-তাত্ত্বিক নিরাপত্তা: এই পেপারটি সর্বোত্তম ত্রুটি সহনশীলতার অধীনে নিকট-সর্বোত্তম কর্মক্ষমতা অর্জনকারী প্রথম তথ্য-তাত্ত্বিক নিরাপদ প্রোটোকল

প্রযুক্তিগত ভিত্তি

  • COOL/OciorCOOL প্রোটোকল: UA এবং HMDM আদিম প্রদান করে
  • ত্রুটি সংশোধন কোড তত্ত্ব: Reed-Solomon কোড এবং Expander কোডের প্রয়োগ
  • বাইজান্টাইন সামঞ্জস্য: Pease, Shostak, Lamport এর ক্লাসিক কাজ থেকে বিকশিত

উপসংহার এবং আলোচনা

প্রধান সিদ্ধান্ত

  1. সর্বোত্তম ত্রুটি সহনশীলতা n ≥ 3t + 1 এর অধীনে, প্রথম নিকট-সর্বোত্তম ত্রুটি-মুক্ত, তথ্য-তাত্ত্বিক নিরাপদ অ্যাসিঙ্ক্রোনাস MVBA প্রোটোকল বাস্তবায়িত হয়েছে
  2. ত্রুটি সহনশীলতা শিথিল করে বা হ্যাশিং অনুমান প্রবর্তন করে, ধ্রুবক রাউন্ড জটিলতা অর্জন করা যায়
  3. পুনরাবৃত্তিমূলক ডিজাইন এবং পক্ষপাতী সামঞ্জস্য প্রক্রিয়া উচ্চ দক্ষতা অর্জনের চাবিকাঠি

সীমাবদ্ধতা

  1. ধ্রুবক ফ্যাক্টর: যদিও渐近 জটিলতা সর্বোত্তম, ধ্রুবক ফ্যাক্টর বড় হতে পারে
  2. সাধারণ মুদ্রা নির্ভরতা: এখনও O(log n) সাধারণ মুদ্রা প্রয়োজন
  3. নেটওয়ার্ক বিভাজন: পুনরাবৃত্তিমূলক বিভাজন বাস্তব নেটওয়ার্কে অতিরিক্ত ওভারহেড প্রবর্তন করতে পারে
  4. ত্রুটি সংশোধন কোড নির্বাচন: কর্মক্ষমতা ত্রুটি সংশোধন কোডের বর্ণমালা আকার q এর উপর নির্ভর করে

ভবিষ্যত দিকনির্দেশনা

  1. ধ্রুবক অপ্টিমাইজেশন: প্রোটোকলে ধ্রুবক ফ্যাক্টর হ্রাস করুন
  2. সাধারণ মুদ্রা দক্ষতা: সাধারণ মুদ্রার ব্যবহার আরও হ্রাস করুন
  3. বাস্তব বাস্তবায়ন: দক্ষ বাস্তব বাস্তবায়ন বিকাশ করুন এবং কর্মক্ষমতা মূল্যায়ন পরিচালনা করুন
  4. প্রয়োগ সম্প্রসারণ: প্রোটোকলটি নির্দিষ্ট বিতরণকৃত সিস্টেমে প্রয়োগ করুন

গভীর মূল্যায়ন

সুবিধা

  1. তাত্ত্বিক অগ্রগতি: তথ্য-তাত্ত্বিক নিরাপত্তা সেটিংয়ে নিকট-সর্বোত্তম যোগাযোগ জটিলতা অর্জন করেছে
  2. চতুর ডিজাইন: পুনরাবৃত্তিমূলক আর্কিটেকচার এবং পক্ষপাতী সামঞ্জস্যের সমন্বয় অত্যন্ত উদ্ভাবনী
  3. কঠোর বিশ্লেষণ: সম্পূর্ণ সঠিকতা প্রমাণ এবং জটিলতা বিশ্লেষণ প্রদান করেছে
  4. ব্যবহারিক মূল্য: বিভিন্ন প্রয়োগ পরিস্থিতির জন্য একাধিক ভেরিয়েন্ট প্রদান করে

অপূর্ণতা

  1. পরীক্ষামূলক যাচাইকরণের অভাব: পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ, বাস্তব বাস্তবায়ন এবং কর্মক্ষমতা পরীক্ষার অভাব
  2. ধ্রুবক জটিলতা: যদিও渐近 সর্বোত্তম, বাস্তব ধ্রুবক ব্যবহারযোগ্যতা প্রভাবিত করতে পারে
  3. অনুমান শর্ত: সাধারণ মুদ্রা অনুমান বাস্তব সিস্টেমে বাস্তবায়ন করা কঠিন হতে পারে
  4. পঠনযোগ্যতা: প্রোটোকল বর্ণনা জটিল, বোঝা এবং বাস্তবায়ন কঠিন

প্রভাব

  1. তাত্ত্বিক অবদান: MVBA ক্ষেত্রে নতুন তাত্ত্বিক মানদণ্ড প্রদান করেছে
  2. প্রযুক্তিগত অনুপ্রেরণা: পুনরাবৃত্তিমূলক ডিজাইন চিন্তাভাবনা অন্যান্য বিতরণকৃত প্রোটোকলের ডিজাইনকে অনুপ্রাণিত করতে পারে
  3. ব্যবহারিক সম্ভাবনা: নিরাপত্তার প্রতি অত্যন্ত দাবিদার পরিস্থিতিতে প্রয়োগের মূল্য রয়েছে
  4. গবেষণা দিকনির্দেশনা: পরবর্তী MVBA প্রোটোকল অপ্টিমাইজেশনের জন্য নতুন চিন্তাভাবনা প্রদান করেছে

প্রযোজ্য পরিস্থিতি

  1. উচ্চ নিরাপত্তা প্রয়োজনীয়তা: তথ্য-তাত্ত্বিক নিরাপত্তা গ্যারান্টি প্রয়োজন এমন গুরুত্বপূর্ণ সিস্টেম
  2. বড় আকারের নেটওয়ার্ক: নোডের সংখ্যা বেশি এমন বিতরণকৃত সিস্টেম
  3. অ্যাসিঙ্ক্রোনাস পরিবেশ: নেটওয়ার্ক বিলম্ব অপ্রত্যাশিত এমন পরিবেশ
  4. ত্রুটি সহনশীল সিস্টেম: বাইজান্টাইন ত্রুটি সহন করতে হয় এমন সিস্টেম

সংদর্ভ

পেপারটি ১৭টি সম্পর্কিত সংদর্ভ উদ্ধৃত করেছে, প্রধানত অন্তর্ভুক্ত করে:

  • 1 Cachin et al. - MVBA এর যুগান্তকারী কাজ
  • 5-7 Chen - COOL এবং OciorCOOL প্রোটোকল সিরিজ
  • 8-12 সাম্প্রতিক MVBA প্রোটোকলের গুরুত্বপূর্ণ অগ্রগতি
  • 13-15 ত্রুটি সংশোধন কোড তত্ত্বের ভিত্তি
  • 17 Li-Chen এর অ্যাসিঙ্ক্রোনাস বাইজান্টাইন সামঞ্জস্য প্রোটোকল