আমরা একে অপরকে বিশ্বাস না করলে কি এলোমেলো সংখ্যা তৈরি করা সম্ভব? অংশ 2

হে হাবর!

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

নিবন্ধের এই অংশে, আমরা থ্রেশহোল্ড স্বাক্ষর ব্যবহার করে এমন আরেকটি পদ্ধতির উপর ঘনিষ্ঠভাবে নজর দেব।

ক্রিপ্টোগ্রাফি একটি বিট

থ্রেশহোল্ড স্বাক্ষরগুলি কীভাবে কাজ করে তা বোঝার জন্য, আপনাকে একটু মৌলিক ক্রিপ্টোগ্রাফি বুঝতে হবে। আমরা দুটি ধারণা ব্যবহার করব: স্কেলার, বা সহজভাবে সংখ্যা, যা আমরা ছোট হাতের অক্ষর দ্বারা বোঝাব (x, y) এবং উপবৃত্তাকার বক্ররেখার বিন্দু, যা আমরা বড় অক্ষর দ্বারা বোঝাব।

থ্রেশহোল্ড স্বাক্ষরের মূল বিষয়গুলি বোঝার জন্য, আপনাকে কয়েকটি মৌলিক জিনিস ছাড়া উপবৃত্তাকার বক্ররেখাগুলি কীভাবে কাজ করে তা বোঝার দরকার নেই:

1. একটি উপবৃত্তাকার বক্ররেখার বিন্দুগুলি একটি স্কেলার দ্বারা যোগ এবং গুণ করা যেতে পারে (আমরা স্কেলার দ্বারা গুণকে বোঝাব xG, স্বরলিপি যদিও Gx এছাড়াও প্রায়ই সাহিত্যে ব্যবহৃত হয়)। একটি স্কেলার দ্বারা যোগ এবং গুণের ফলাফল একটি উপবৃত্তাকার বক্ররেখার একটি বিন্দু।

2. বিন্দু মাত্র জানা G এবং একটি স্কেলার সহ এর পণ্য xG গণনা করা যাবে না x.

আমরা একটি বহুপদ ধারণা ব্যবহার করব p(x) ডিগ্রী k-1। বিশেষ করে, আমরা বহুপদগুলির নিম্নলিখিত বৈশিষ্ট্যগুলি ব্যবহার করব: যদি আমরা মানটি জানি p(x) কোন জন্য k বিভিন্ন x (এবং আমাদের কাছে আর কোন তথ্য নেই p(x)), আমরা গণনা করতে পারি p(x) অন্য কারো জন্য x.

এটা আকর্ষণীয় যে কোন বহুপদী জন্য p(x) এবং বক্ররেখার কিছু বিন্দু Gঅর্থ জানা p(x)G কোন জন্য k বিভিন্ন অর্থ x, আমরাও গণনা করতে পারি p(x)G কোন জন্য x.

থ্রেশহোল্ড স্বাক্ষরগুলি কীভাবে কাজ করে এবং এলোমেলো সংখ্যা তৈরি করতে কীভাবে সেগুলি ব্যবহার করতে হয় তার বিশদ খননের জন্য এটি যথেষ্ট তথ্য।

থ্রেশহোল্ড স্বাক্ষরে র্যান্ডম নম্বর জেনারেটর

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

ধরুন এমন একটি বহুপদ আছে p(x) ডিগ্রী k-1 প্রথম অংশগ্রহণকারী কি জানেন পি (1), দ্বিতীয়টি জানে p(2), এবং তাই (n-তা জানে p(n)) আমরা কিছু পূর্বনির্ধারিত বিন্দু জন্য যে অনুমান G সবাই জানে p(x)G সব মান জন্য x. আমরা কল করব p(i) "ব্যক্তিগত উপাদান" iম অংশগ্রহণকারী (কারণ শুধুমাত্র iতম অংশগ্রহণকারী তাকে চেনে), এবং p(i) G "পাবলিক উপাদান" i-তম অংশগ্রহণকারী (কারণ সমস্ত অংশগ্রহণকারীরা তাকে চেনে)। আপনি যেমন মনে রাখবেন, জ্ঞান p(i) G পুনরুদ্ধার করার জন্য যথেষ্ট নয় p(i)।

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

কিভাবে আমরা একটি এলোমেলো সংখ্যা তৈরি করতে এই ধরনের একটি বহুপদ ব্যবহার করতে পারি? শুরু করার জন্য, আমাদের এমন কিছু স্ট্রিং দরকার যা আগে জেনারেটরে ইনপুট হিসাবে ব্যবহার করা হয়নি। একটি ব্লকচেইনের ক্ষেত্রে, শেষ ব্লকের হ্যাশ h যেমন একটি লাইন জন্য একটি ভাল প্রার্থী. অংশগ্রহণকারীদের ব্যবহার করে একটি র্যান্ডম সংখ্যা তৈরি করতে চান h বীজের মত অংশগ্রহণকারীরা প্রথমে কনভার্ট করে h কোনো পূর্বনির্ধারিত ফাংশন ব্যবহার করে বক্ররেখার একটি বিন্দুতে:

H = scalarToPoint(h)

তারপর প্রতিটি অংশগ্রহণকারী i গণনা করে এবং প্রকাশ করে হাই = p(i)H, তারা কি করতে পারে কারণ তারা জানে p(i) এবং H. প্রকাশ Hআমি অন্যান্য অংশগ্রহণকারীদের ব্যক্তিগত উপাদান পুনরুদ্ধার করার অনুমতি দিই না iতম অংশগ্রহণকারী, এবং তাই এক সেট ব্যক্তিগত উপাদান ব্লক থেকে ব্লক ব্যবহার করা যেতে পারে। সুতরাং, নীচে বর্ণিত ব্যয়বহুল বহুপদী প্রজন্মের অ্যালগরিদম শুধুমাত্র একবার কার্যকর করা দরকার।

যখন k অংশগ্রহণকারীদের ময়নাতদন্ত করা হয়েছিল হাই = p(i)H, সবাই হিসাব করতে পারে Hx = p(x)H সবার জন্য x বহুপদীর সম্পত্তির জন্য ধন্যবাদ যা আমরা শেষ বিভাগে আলোচনা করেছি। এই মুহুর্তে, সমস্ত অংশগ্রহণকারী গণনা করে H0 = p(0)H, এবং এটি ফলস্বরূপ র্যান্ডম সংখ্যা। দয়া করে নোট করুন যে কেউ জানে না p(0), এবং তাই গণনা করার একমাত্র উপায় p(0)H - এই ইন্টারপোলেশন p(x)H, যা তখনই সম্ভব যখন k মান p(i)H পরিচিত কোন ছোট পরিমাণ খোলা p(i)H সম্পর্কে কোন তথ্য প্রদান করে না p(0)H

উপরের জেনারেটরের সমস্ত বৈশিষ্ট্য রয়েছে যা আমরা চাই: আক্রমণকারীরা নিয়ন্ত্রণ করে k-1 জন বা তার কম অংশগ্রহণকারীর উপসংহারে কোন তথ্য বা প্রভাব নেই, যদিও কোনটি k অংশগ্রহণকারীরা ফলাফল সংখ্যা গণনা করতে পারেন, এবং যে কোনো উপসেট k অংশগ্রহণকারীরা সবসময় একই বীজের জন্য একই ফলাফলে আসবে।

একটি সমস্যা আছে যা আমরা সাবধানে উপরে এড়িয়ে গিয়েছি। ইন্টারপোলেশন কাজ করার জন্য, এটা গুরুত্বপূর্ণ যে মান Hi যা প্রতিটি অংশগ্রহণকারী দ্বারা প্রকাশিত হয়েছিল i এটা সত্যিই একই ছিল p(i)H যেহেতু ছাড়া কেউ নেই i-ম অংশগ্রহণকারী জানেন না p(i), ছাড়া কেউ না i-তম অংশগ্রহণকারী তা যাচাই করতে পারে না Hi প্রকৃতপক্ষে সঠিকভাবে গণনা করা হয়েছে, এবং সঠিকতার কোনো ক্রিপ্টোগ্রাফিক প্রমাণ ছাড়াই Hআমি একজন আক্রমণকারী যে কোনো মান প্রকাশ করতে পারেন হাই, এবং নির্বিচারে র্যান্ডম নম্বর জেনারেটরের আউটপুটকে প্রভাবিত করে:

প্রথম অংশগ্রহণকারীর দ্বারা প্রেরিত H_1 এর বিভিন্ন মান বিভিন্ন H_0 ফলাফলের দিকে নিয়ে যায়

সঠিকতা প্রমাণ করার অন্তত দুটি উপায় আছে Hi, আমরা বহুপদীর প্রজন্ম বিশ্লেষণ করার পরে সেগুলি বিবেচনা করব।

বহুপদ প্রজন্ম

শেষ বিভাগে আমরা ধরে নিয়েছিলাম যে আমাদের এমন একটি বহুপদ আছে p(x) ডিগ্রী k-১ যে অংশগ্রহণকারী i তিনি জানেন p(i), এবং অন্য কেউ এই মান সম্পর্কে কোন তথ্য নেই. পরবর্তী বিভাগে আমাদের কিছু পূর্বনির্ধারিত পয়েন্টের জন্যও এটির প্রয়োজন হবে G সবাই জানত p(x)G সবার জন্য x.

এই বিভাগে আমরা অনুমান করব যে প্রতিটি অংশগ্রহণকারীর স্থানীয়ভাবে কিছু ব্যক্তিগত কী আছে একাদশ, যাতে সবাই সংশ্লিষ্ট পাবলিক কী জানে Xi.

একটি সম্ভাব্য বহুপদী প্রজন্মের প্রোটোকল নিম্নরূপ:

1. প্রতিটি অংশগ্রহণকারী i স্থানীয়ভাবে একটি নির্বিচারে বহুপদ তৈরি করে pi(x) ডিগ্রি k-1। তারপর তারা প্রতিটি অংশগ্রহণকারীকে পাঠায় j অর্থ pi(j), পাবলিক কী দিয়ে এনক্রিপ্ট করা এক্সজে. এইভাবে শুধুমাত্র i-ম и j-ম অংশগ্রহণকারী জানেন pi(j)। অংশগ্রহণকারী i এছাড়াও প্রকাশ্যে ঘোষণা pi(j)G সবার জন্য j থেকে 1 থেকে k সমেত।

2. সমস্ত অংশগ্রহণকারীরা বেছে নিতে কিছু ঐক্যমত্য ব্যবহার করে k অংশগ্রহণকারীদের বহুপদ ব্যবহার করা হবে। যেহেতু কিছু অংশগ্রহণকারী অফলাইনে থাকতে পারে, আমরা সবাই পর্যন্ত অপেক্ষা করতে পারি না n অংশগ্রহণকারীরা বহুপদ প্রকাশ করবে। এই ধাপের ফলাফল একটি সেট Z অন্তত গঠিত k ধাপে বহুপদ তৈরি করা হয়েছে (1).

3. অংশগ্রহণকারীরা নিশ্চিত করে যে তারা যে মানগুলি জানে তা নিশ্চিত করে pi(j) সর্বজনীনভাবে ঘোষিত অনুরূপ pi(j)G এই ধাপে পরে Z শুধুমাত্র বহুপদ যার জন্য ব্যক্তিগতভাবে প্রেরণ করা হয় pi(j) সর্বজনীনভাবে ঘোষিত অনুরূপ pi(j)G

4. প্রতিটি অংশগ্রহণকারী j এর ব্যক্তিগত উপাদান গণনা করে p(j) একটি যোগফল হিসাবে pi(j) সবার জন্য i в Z. প্রতিটি অংশগ্রহণকারী সমস্ত মান গণনা করে p(x)G একটি যোগফল হিসাবে pi(x)G সবার জন্য i в Z.

মনে রাখবেন যে p(x)- এটা সত্যিই একটি বহুপদ k-1, কারণ এটি ব্যক্তির যোগফল pi(x), যার প্রতিটি ডিগ্রীর বহুপদী k-1। তারপর, প্রতিটি অংশগ্রহণকারীর সময় যে নোট করুন j তিনি জানেন p(j), তাদের কোন তথ্য নেই p(x) থেকে x ≠ j. প্রকৃতপক্ষে, এই মান গণনা করার জন্য, তাদের সবকিছু জানতে হবে pi(x), এবং যতক্ষণ অংশগ্রহণকারী j অন্তত একটি নির্বাচিত বহুপদ জানে না, তাদের কাছে পর্যাপ্ত তথ্য নেই p(x)।

এটি সম্পূর্ণ বহুপদী প্রজন্মের প্রক্রিয়া যা শেষ বিভাগে প্রয়োজন ছিল। উপরের ধাপ 1, 2 এবং 4 এর মোটামুটি সুস্পষ্ট বাস্তবায়ন রয়েছে। কিন্তু ধাপ 3 এত তুচ্ছ নয়।

বিশেষ করে, আমাদের এনক্রিপ্ট করা প্রমাণ করতে সক্ষম হতে হবে pi(j) সত্যিই প্রকাশিতগুলির সাথে মিলে যায়৷ pi(j)G এটা প্রমাণ করতে না পারলে হামলাকারী i পরিবর্তে আবর্জনা পাঠাতে পারে pi(j) অংশগ্রহণকারীকে j, এবং অংশগ্রহণকারী j প্রকৃত অর্থ পেতে সক্ষম হবে না pi(j), এবং এর ব্যক্তিগত উপাদান গণনা করতে সক্ষম হবে না.

একটি ক্রিপ্টোগ্রাফিক প্রোটোকল রয়েছে যা আপনাকে একটি অতিরিক্ত বার্তা তৈরি করতে দেয় প্রমাণi(j), যেমন কোনো অংশগ্রহণকারীর, কিছু মান আছে e, а также প্রমাণী(জ) и pi(j)G, স্থানীয়ভাবে তা যাচাই করতে পারে e - এটা সত্যিই pi(j), অংশগ্রহণকারীর কী দিয়ে এনক্রিপ্ট করা j. দুর্ভাগ্যবশত, এই ধরনের প্রমাণের আকার অবিশ্বাস্যভাবে বড়, এবং এটি প্রকাশ করা প্রয়োজন O(nk) এই উদ্দেশ্যে এই ধরনের প্রমাণ ব্যবহার করা যাবে না.

সেটা প্রমাণ করার বদলে pi(j) অনুরূপ pi(j)G আমরা বহুপদী প্রজন্মের প্রোটোকলে একটি দীর্ঘ সময় বরাদ্দ করতে পারি, যার সময় সমস্ত অংশগ্রহণকারীরা প্রাপ্ত এনক্রিপ্ট করা পরীক্ষা করে pi(j), এবং যদি ডিক্রিপ্ট করা বার্তা জনসাধারণের সাথে সঙ্গতিপূর্ণ না হয় pi(j)G, তারা একটি ক্রিপ্টোগ্রাফিক প্রমাণ প্রকাশ করে যে তারা প্রাপ্ত এনক্রিপ্ট করা বার্তাটি ভুল। বার্তাটি প্রমাণ করুন না অনুরূপ পাই(জি) এটা মেলে প্রমাণ করার চেয়ে অনেক সহজ। এটি উল্লেখ করা উচিত যে এর জন্য প্রতিটি অংশগ্রহণকারীকে এই ধরনের প্রমাণ তৈরি করার জন্য বরাদ্দকৃত সময়ের মধ্যে অন্তত একবার অনলাইনে উপস্থিত হতে হবে এবং এই ধারণার উপর নির্ভর করে যে যদি তারা এই ধরনের প্রমাণ প্রকাশ করে, তবে এটি একই বরাদ্দকৃত সময়ে অন্য সকল অংশগ্রহণকারীদের কাছে পৌঁছাবে।

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

H_i এর সঠিকতার প্রমাণ

শেষ যে অংশটি আলোচনা করা বাকি আছে তা হল প্রকাশের সঠিকতা কীভাবে প্রমাণ করা যায় Hআমি, যথা হাই = p(i)H, খোলা ছাড়া p(i)।

আমাদের যে মান মনে রাখা যাক H, G, p(i) G সর্বজনীন এবং সবার কাছে পরিচিত। অপারেশন গ্রহণ p(i) জানা p(i) G и G বিযুক্ত লগারিদম বলা হয়, বা dlog, এবং আমরা প্রমাণ করতে চাই যে:

dlog(p(i)G, G) = dlog(Hi, H)

প্রকাশ ছাড়াই p(i). যেমন প্রমাণের জন্য নির্মাণ বিদ্যমান, উদাহরণস্বরূপ Schnorr প্রোটোকল.

এই নকশা সঙ্গে, প্রতিটি অংশগ্রহণকারী, বরাবর Hi নকশা অনুযায়ী সঠিকতার প্রমাণ পাঠায়।

একবার একটি এলোমেলো সংখ্যা তৈরি হয়ে গেলে, এটি প্রায়শই যারা এটি তৈরি করেছে তাদের ব্যতীত অন্যান্য অংশগ্রহণকারীদের দ্বারা ব্যবহার করা প্রয়োজন৷ এই ধরনের অংশগ্রহণকারীদের, নম্বর সহ, সবাইকে পাঠাতে হবে Hi এবং সম্পর্কিত প্রমাণ।

একজন অনুসন্ধিৎসু পাঠক জিজ্ঞাসা করতে পারেন: যেহেতু চূড়ান্ত র্যান্ডম সংখ্যা H0, এবং পি(0)জি - এটি সর্বজনীন তথ্য, কেন আমাদের প্রতিটি ব্যক্তির জন্য প্রমাণ দরকার Hআমি, কেন তার পরিবর্তে প্রমাণ পাঠান না

dlog(p(0)G, G) = dlog(H0, H)

সমস্যা হল যে এই ধরনের প্রমাণ Schnorr প্রোটোকল ব্যবহার করে তৈরি করা যাবে না কারণ কেউ মান জানে না পি (0), প্রমাণ তৈরি করার জন্য প্রয়োজনীয়, এবং আরও কী, পুরো র্যান্ডম নম্বর জেনারেটরটি এই সত্যের উপর ভিত্তি করে যে এই মানটি কেউ জানে না। তাই সব মান থাকা আবশ্যক Hi এবং সঠিকতা প্রমাণ করার জন্য তাদের পৃথক প্রমাণ H0.

যাইহোক, যদি উপবৃত্তাকার বক্ররেখার বিন্দুতে কিছু ক্রিয়াকলাপ থাকে যা শব্দার্থগতভাবে গুণের অনুরূপ, সঠিকতার প্রমাণ H0 তুচ্ছ হবে, আমরা কেবল তা নিশ্চিত করব

Hএক্সএনএমএক্স × G = p(0)G × H

যদি নির্বাচিত বক্ররেখা সমর্থন করে উপবৃত্তাকার বক্ররেখা জোড়া, এই প্রমাণ কাজ করে. এক্ষেত্রে H0 শুধুমাত্র একটি এলোমেলো নম্বর জেনারেটরের আউটপুট নয়, যা জানে এমন যেকোনো অংশগ্রহণকারী দ্বারা যাচাই করা যেতে পারে জি, এইচ и p(0)জি. এইচ0 বার্তাটিতে একটি স্বাক্ষর যা একটি বীজ হিসাবে ব্যবহৃত হয়েছিল, এটি নিশ্চিত করে k и n অংশগ্রহণকারীরা এই বার্তায় স্বাক্ষর করেছেন। এইভাবে, যদি বীজ - তারপর ব্লকচেইন প্রোটোকলের ব্লকের হ্যাশ H0 একটি ব্লকে একটি বহু-স্বাক্ষর এবং একটি খুব ভাল র্যান্ডম সংখ্যা উভয়ই৷

উপসংহার ইন

এই নিবন্ধটি একটি প্রযুক্তিগত ব্লগ সিরিজের অংশ NEAR. NEAR হল একটি ব্লকচেইন প্রোটোকল এবং প্ল্যাটফর্ম যা বিকেন্দ্রীকৃত অ্যাপ্লিকেশনগুলিকে বিকাশের সহজে এবং শেষ ব্যবহারকারীদের জন্য সহজে ব্যবহারের উপর জোর দেয়।

প্রোটোকল কোড খোলা আছে, আমাদের বাস্তবায়ন মরিচা লেখা আছে, এটি পাওয়া যাবে এখানে.

NEAR-এর বিকাশ কেমন তা আপনি দেখতে পারেন এবং অনলাইন IDE-তে পরীক্ষা করতে পারেন৷ এখানে.

আপনি এখানে রাশিয়ান সব খবর অনুসরণ করতে পারেন টেলিগ্রাম গ্রুপ এবং ইন ভিকন্টাক্টে গ্রুপ, এবং সরকারিভাবে ইংরেজিতে টুইটার.

Ыскор!

উত্স: www.habr.com