Quantum Byzantine agreement
বাইজেন্টাইন ফল্ট সহনশীল প্রোটোকলগুলি এমন অ্যালগরিদম যা বিতরণকৃত অ্যালগরিদমগুলিতে নির্বিচারে ধরণের ব্যর্থতার জন্য শক্তিশালী। বাইজেন্টাইন চুক্তি প্রটোকল এই কাজের একটি অপরিহার্য অংশ। বাইজেন্টাইন প্রটোকলের ধ্রুবক-সময়ের কোয়ান্টাম সংস্করণটি নীচে বর্ণনা করা হয়েছে। পরিচয় বাইজেন্টাইন চুক্তি প্রটোকল হল ডিস্ট্রিবিউটেড কম্পিউটিং-এর একটি প্রটোকল। 1982 সালে ল্যাম্পোর্ট, শোস্তাক এবং পিজ দ্বারা প্রণীত একটি সমস্যা থেকে এর নাম নেওয়া হয়েছে, যা নিজেই একটি ঐতিহাসিক সমস্যার উল্লেখ। বাইজেন্টাইন সেনাবাহিনীকে বিভিন্ন বিভাগে বিভক্ত করা হয়েছিল এবং প্রতিটি বিভাগের নেতৃত্বে একজন জেনারেল ছিলেন যার নিম্নলিখিত বৈশিষ্ট্যগুলি ছিলঃ প্রতিটি জেনারেল হয় বাইজেন্টাইন রাষ্ট্রের প্রতি অনুগত অথবা বিশ্বাসঘাতক। সমস্ত জেনারেল বার্তা পাঠানোর এবং গ্রহণ করার মাধ্যমে যোগাযোগ করেন। শুধুমাত্র দুটি আদেশ রয়েছেঃ আক্রমণ এবং পশ্চাদপসরণ। সমস্ত অনুগত জেনারেলদের একই কর্মপরিকল্পনায় একমত হওয়া উচিতঃ আক্রমণ বা পশ্চাদপসরণ। খারাপ জেনারেলদের একটি ছোট রৈখিক ভগ্নাংশ প্রোটোকল ব্যর্থ হওয়ার কারণ হওয়া উচিত নয় (একটি ভগ্নাংশের চেয়ে কম)। (অসম্ভব ফলাফলের প্রমাণের জন্য দেখুন)। সমস্যাটি সাধারণত একজন কমান্ডিং জেনারেল এবং অনুগত লেফটেন্যান্টের আকারে সমতুল্যভাবে পুনরাবৃত্তি করা হয় যেখানে জেনারেল হয় অনুগত বা বিশ্বাসঘাতক এবং নিম্নলিখিত সম্পত্তি সহ লেফটেন্যান্টদের ক্ষেত্রেও একই। সমস্ত অনুগত লেফটেন্যান্ট একই আদেশ পালন করে। যদি কমান্ডিং জেনারেল অনুগত হন, তবে সমস্ত অনুগত লেফটেন্যান্টরা তাঁর পাঠানো আদেশ মেনে চলেন। কমান্ডিং জেনারেল সহ একটি কঠোরভাবে কম ভগ্নাংশ বিশ্বাসঘাতক। বাইজেন্টাইন ব্যর্থতা এবং স্থিতিস্থাপকতা একটি অ্যালগরিদম বা প্রোটোকলের ব্যর্থতাগুলিকে তিনটি প্রধান প্রকারে শ্রেণীবদ্ধ করা যেতে পারেঃ অ্যালগরিদমের আরেকটি কার্যকর পদক্ষেপ গ্রহণে ব্যর্থতাঃ এটিকে সাধারণত "ফেল স্টপ" ফল্ট হিসাবে উল্লেখ করা হয়। সঠিকভাবে কার্যকর করতে এলোমেলো ব্যর্থতাঃ এটিকে "র্যান্ডম ফল্ট" বা "র্যান্ডম বাইজেন্টাইন" ফল্ট বলা হয়। একটি নির্বিচারে ব্যর্থতা যেখানে অ্যালগরিদম ধাপগুলি সঠিকভাবে কার্যকর করতে ব্যর্থ হয় (সাধারণত কোনও প্রতিপক্ষের দ্বারা পুরো অ্যালগরিদমকে ব্যর্থ করার জন্য চতুর উপায়ে) যা পূর্ববর্তী দুই ধরনের ত্রুটিগুলিকেও অন্তর্ভুক্ত করে; এটিকে "বাইজেন্টাইন ফল্ট" বলা হয়। একটি বাইজেন্টাইন স্থিতিস্থাপক বা বাইজেন্টাইন ফল্ট সহনশীল প্রোটোকল বা অ্যালগরিদম এমন একটি অ্যালগরিদম যা উপরে উল্লিখিত সমস্ত ধরণের ব্যর্থতার জন্য শক্তিশালী। উদাহরণস্বরূপ, একাধিক অপ্রয়োজনীয় প্রসেসর সহ একটি স্পেস শাটল দেওয়া হলে, প্রসেসরগুলি যদি পরস্পরবিরোধী তথ্য দেয়, তবে কোন প্রসেসর বা প্রসেসরের সেটগুলি বিশ্বাস করা উচিত? সমাধানটি বাইজেন্টাইন ফল্ট সহনশীল প্রোটোকল হিসাবে প্রণয়ন করা যেতে পারে। অ্যালগরিদমের স্কেচ আমরা এখানে অ্যাসিঙ্ক্রোনাস অ্যালগরিদমটি স্কেচ করব অ্যালগরিদমটি দুটি পর্যায়ে কাজ করেঃ ফেজ 1 (কমিউনিকেশন ফেজ): সমস্ত বার্তা এই রাউন্ডে পাঠানো এবং গ্রহণ করা হয়। একটি মুদ্রা উল্টানোর প্রটোকল এমন একটি পদ্ধতি যা দুটি পক্ষ এ এবং বি-কে একটি নির্দিষ্ট বস্তু জেতার জন্য একটি মুদ্রা টস করার অনুমতি দেয় যা একে অপরকে বিশ্বাস করে না। দুই ধরনের মুদ্রা উল্টানোর প্রোটোকল রয়েছে দুর্বল মুদ্রা উল্টানোর প্রোটোকলঃ দুই খেলোয়াড় এ এবং বি প্রাথমিকভাবে কোনও ইনপুট ছাড়াই শুরু করে এবং তাদের কিছু মূল্য গণনা করতে হবে এবং যে কাউকে প্রতারণার জন্য অভিযুক্ত করতে সক্ষম হতে হবে। প্রোটোকল সফল হয় যদি এ এবং বি ফলাফলের উপর একমত হয়। ফলাফল 0 কে এ বিজয়ী এবং 1 কে বি বিজয়ী হিসাবে সংজ্ঞায়িত করা হয়। প্রোটোকলের নিম্নলিখিত বৈশিষ্ট্যগুলি রয়েছেঃ যদি উভয় খেলোয়াড় সৎ হয় (তারা প্রোটোকল অনুসরণ করে), তবে তারা প্রোটোকলের ফলাফলের সাথে একমত হয়। যদি খেলোয়াড়দের মধ্যে একজন সৎ হয় (অর্থাৎ, অন্য খেলোয়াড় তার স্থানীয় গণনায় প্রোটোকল থেকে নির্বিচারে বিচ্যুত হতে পারে), তবে অন্য পক্ষ সর্বাধিক সম্ভাবনার সাথে জয়ী হয়। অন্য কথায়, যদি বি অসৎ হয়, তাহলে, এবং যদি এ অসৎ হয়, তাহলে। একটি শক্তিশালী মুদ্রা উল্টানোর প্রটোকলঃ একটি শক্তিশালী মুদ্রা উল্টানোর প্রটোকলে, লক্ষ্য হল একটি এলোমেলো বিট তৈরি করা যা কোনও নির্দিষ্ট মান 0 বা 1 থেকে দূরে পক্ষপাতদুষ্ট। স্পষ্টতই, পক্ষপাতের সাথে যে কোনও শক্তিশালী মুদ্রা উল্টানোর প্রটোকল একই পক্ষপাতের সাথে দুর্বল মুদ্রা উল্টানোর দিকে পরিচালিত করে। যাচাইযোগ্য গোপন ভাগাভাগি একটি যাচাইযোগ্য গোপন ভাগাভাগি প্রোটোকলঃ এ (এন, কে) গোপন ভাগাভাগি প্রোটোকল এন খেলোয়াড়দের একটি সেটকে একটি গোপন ভাগ করে নেওয়ার অনুমতি দেয়, যাতে কেবল কে বা তার বেশি খেলোয়াড়ের কোরাম গোপনটি আবিষ্কার করতে পারে। যে খেলোয়াড় গোপনীয়তা ভাগ করে নেয় (গোপন টুকরোগুলি বিতরণ করে) তাকে সাধারণত ব্যবসায়ী হিসাবে উল্লেখ করা হয়। একটি যাচাইযোগ্য গোপন শেয়ারিং প্রোটোকল একটি মৌলিক গোপন শেয়ারিং প্রোটোকল থেকে আলাদা যে খেলোয়াড়রা যাচাই করতে পারে যে তাদের শেয়ারগুলি কোনও দূষিত ব্যবসায়ীর উপস্থিতিতেও সামঞ্জস্যপূর্ণ। খেলোয়াড় রাউন্ড 1-এর জন্য ফেল-স্টপ প্রোটোকল কোয়ান্টাম কয়েন ফ্লিপ কিউবিটগুলিতে জিএইচজেড অবস্থা তৈরি করে এবং এক অংশ রেখে থ কিউবিটকে থ খেলোয়াড়ের কাছে পাঠায় কিউডিটগুলিতে অবস্থা তৈরি করুন (একাধিক কিউবিটের সামঞ্জস্যপূর্ণ কোয়ান্টাম-কম্পিউটিং উপাদান), 1 এবং এর মধ্যে সংখ্যার সমান সুপারপজিশন। সমস্ত খেলোয়াড়ের মধ্যে কুদিত বিতরণ করুন সমস্ত খেলোয়াড়ের কাছ থেকে কোয়ান্টাম বার্তা গ্রহণ করুন এবং পরবর্তী যোগাযোগ রাউন্ডের জন্য অপেক্ষা করুন, এইভাবে প্রতিপক্ষকে কোন বার্তাটি প্রেরণ করা হয়েছিল তা বেছে নিতে বাধ্য করে। দ্বিতীয় পর্যায়ঃ প্রথম পর্যায়ে প্রাপ্ত সমস্ত কিউবিট পরিমাপ করুন (স্ট্যান্ডার্ড বেসে)। সর্বোচ্চ লিডার ভ্যালু (নির্বিচারে টাই ভেঙে যাওয়া) সহ খেলোয়াড়কে রাউন্ডের "লিডার" হিসাবে নির্বাচন করুন। নেতার মুদ্রা স্ট্যান্ডার্ড বেসে পরিমাপ করুন। কোয়ান্টাম কয়েনফ্লিপ প্রোটোকলের আউটপুট নির্ধারণ করুনঃ = নেতার মুদ্রার পরিমাপের ফলাফল। বাইজেন্টাইন প্রটোকল একটি এলোমেলো মুদ্রা তৈরি করার জন্য প্রতিটি খেলোয়াড়কে [0, এন-1] পরিসরে একটি পূর্ণসংখ্যা বরাদ্দ করা হয় এবং প্রতিটি খেলোয়াড়কে তার নিজস্ব এলোমেলো আইডি বেছে নেওয়ার অনুমতি দেওয়া হয় না কারণ প্রতিটি খেলোয়াড় প্রতিটি অন্য খেলোয়াড়ের জন্য একটি এলোমেলো সংখ্যা নির্বাচন করে এবং একটি যাচাইযোগ্য গোপন ভাগ করে নেওয়ার স্কিম ব্যবহার করে এটি বিতরণ করে। এই পর্বের শেষে খেলোয়াড়রা একমত হয় যে কোন গোপনীয়তাগুলি সঠিকভাবে ভাগ করা হয়েছিল, তারপরে গোপনীয়তাগুলি খোলা হয় এবং প্রতিটি খেলোয়াড়কে মান বরাদ্দ করা হয় যার জন্য ব্যক্তিগত তথ্য চ্যানেলগুলির প্রয়োজন হয় তাই আমরা এলোমেলো গোপনীয়তাগুলি সুপারপজিশন দ্বারা প্রতিস্থাপন করি। যেখানে কোয়ান্টাম ভেরিফায়েবল সিক্রেট শেয়ারিং প্রোটোকল (কিউভিএসএস) ব্যবহার করে রাষ্ট্রকে এনকোড করা হয়। আমরা রাজ্যকে ভাগ করতে পারি না কারণ খারাপ খেলোয়াড়রা রাজ্যকে ভেঙে দিতে পারে। খারাপ খেলোয়াড়দের তা করা থেকে বিরত রাখতে আমরা কোয়ান্টাম ভেরিফায়েবল সিক্রেট শেয়ারিং (কিউভিএসএস) ব্যবহার করে রাষ্ট্রকে এনকোড করি এবং প্রতিটি খেলোয়াড়কে তাদের গোপন অংশ পাঠাই। এখানে আবার যাচাইকরণের জন্য বাইজেন্টাইন চুক্তি প্রয়োজন, তবে গ্রেড-কাস্ট প্রোটোকল দ্বারা চুক্তিটি প্রতিস্থাপন করাই যথেষ্ট। গ্রেড-কাস্ট প্রোটোকল একটি গ্রেড-কাস্ট প্রোটোকলের নিম্নলিখিত বৈশিষ্ট্যগুলি রয়েছে যা অনানুষ্ঠানিকভাবে সংজ্ঞাগুলি ব্যবহার করে, একটি শ্রেণীবদ্ধ সম্প্রচার প্রোটোকল হল "ডিলার" (যিনি সম্প্রচার করেন) নামে একটি মনোনীত খেলোয়াড়ের সাথে এমন একটি প্রোটোকল যাতেঃ ডিলার যদি ভাল হয় তবে সমস্ত খেলোয়াড় একই বার্তা পাবেন। এমনকি ব্যবসায়ী খারাপ হলেও, যদি কোনও ভাল খেলোয়াড় বার্তাটি গ্রহণ করে, তবে সমস্ত ভাল খেলোয়াড় একই বার্তা পায় (তবে তারা এটি গ্রহণ করতে পারে বা নাও করতে পারে)। একটি প্রোটোকল পি-কে শ্রেণীবদ্ধ সম্প্রচার অর্জন বলা হয় যদি, প্রোটোকলের শুরুতে, একজন মনোনীত খেলোয়াড় ডি (ব্যবসায়ী নামে পরিচিত) একটি মান ভি ধারণ করে এবং প্রোটোকলের শেষে, প্রতিটি খেলোয়াড় একটি জোড়া এমনভাবে আউটপুট দেয় যাতে নিম্নলিখিত বৈশিষ্ট্যগুলি ধরে থাকেঃ যদি ডি সৎ হয়, তবে প্রতিটি সৎ খেলোয়াড়ের জন্য = ভি এবং = 2। যে কোনও দুই সৎ খেলোয়াড়ের জন্য। (ধারাবাহিকতা) যে কোনও দুই সৎ খেলোয়াড়ের জন্য এবং, যদি এবং, তাহলে। কিউভিএসএস প্রটোকলের যাচাইকরণ পর্যায়ে নিশ্চিত করা হয় যে একজন ভাল ডিলারের জন্য সঠিক অবস্থা এনকোড করা হবে এবং যে কোনও, সম্ভবত ত্রুটিপূর্ণ ডিলারের জন্য, পুনরুদ্ধারের পর্যায়ে কিছু নির্দিষ্ট অবস্থা পুনরুদ্ধার করা হবে। আমরা লক্ষ্য করছি যে আমাদের বাইজেন্টাইন কোয়ান্টাম কয়েন ফ্লিপ প্রোটোকলের উদ্দেশ্যে পুনরুদ্ধারের পর্যায়টি অনেক সহজ। প্রতিটি খেলোয়াড় কিউভিএসএস-এ তার অংশ পরিমাপ করে এবং অন্যান্য সমস্ত খেলোয়াড়দের কাছে শাস্ত্রীয় মূল্য পাঠায়। যাচাইকরণ পর্যায়টি উচ্চ সম্ভাবনার সাথে গ্যারান্টি দেয় যে, ত্রুটিপূর্ণ খেলোয়াড়দের উপস্থিতিতে সমস্ত ভাল খেলোয়াড় একই শাস্ত্রীয় মান পুনরুদ্ধার করবে (যা একই মান যা এনকোডেড অবস্থার সরাসরি পরিমাপের ফলে হবে)। মন্তব্য 2007 সালে, বাইজেন্টাইন চুক্তির জন্য একটি কোয়ান্টাম প্রোটোকল পরীক্ষামূলকভাবে একটি চার-ফোটন মেরুকরণ-আবদ্ধ অবস্থা ব্যবহার করে প্রদর্শিত হয়েছিল। এটি দেখায় যে শাস্ত্রীয় বাইজেন্টাইন চুক্তি প্রোটোকলের কোয়ান্টাম বাস্তবায়ন প্রকৃতপক্ষে সম্ভবপর। তথ্যসূত্র কোয়ান্টাম তথ্য বিজ্ঞান ক্রিপ্টোগ্রাফি বিতরণকৃত কম্পিউটিং সমস্যা ত্রুটি সহনশীলতা প্রকৌশল ব্যর্থতা গণনার তত্ত্ব