3,663 পড়া

কিভাবে বিনিয়াস বাইনারি ফিল্ডের টাওয়ারের সাথে কম্পিউটেশনাল জটিলতা হ্রাস করে

দ্বারা Sin7Y3m2024/09/13

অতিদীর্ঘ; পড়তে

উলভেটান্না (অপ্রত্যাশিত) দলটি তাদের গবেষণা পত্রে এই প্রশ্নটিকে সম্বোধন করেছে যার শিরোনাম রয়েছে সুসিক্ট আর্গুমেন্টস ওভার বাইনারি ফিল্ডস। তারা তাদের প্রকল্প, বিনিয়াস: একটি হার্ডওয়্যার-অপ্টিমাইজড SNARK এর মাধ্যমে এটিকে মরিচা-এ বাস্তবায়ন করেছে। বিনিয়াসে, বাইনারি ক্ষেত্রগুলি ফিল্ড এক্সটেনশনের টাওয়ার ব্যবহার করে তৈরি করা হয়।

featured image - কিভাবে বিনিয়াস বাইনারি ফিল্ডের টাওয়ারের সাথে কম্পিউটেশনাল জটিলতা হ্রাস করে

গণনাগত জটিলতা হ্রাস করা সর্বদা ব্লকচেইন প্রযুক্তির প্রাথমিক লক্ষ্যগুলির মধ্যে একটি। এটি অর্জনের একটি কার্যকর পদ্ধতি হল গণনা ক্ষেত্রের বিট প্রস্থ হ্রাস করা। উদাহরণস্বরূপ, উপবৃত্তাকার বক্ররেখার উপর ভিত্তি করে SNARKগুলি 256 বা তার বেশি বিট প্রস্থের ক্ষেত্রে গাণিতিক ক্রিয়াকলাপ সম্পাদন করে, যখন STARKগুলি 64-বিট গোল্ডিলক্স ক্ষেত্র ব্যবহার করে 31-বিট মার্সেন 31 এবং বেবিবিয়ার ক্ষেত্রগুলিতে বিবর্তিত হয়েছে। মডুলার ক্রিয়াকলাপের সময় মৌলিক সংখ্যার দক্ষতার বাইরে, বিট প্রস্থে উল্লেখযোগ্য হ্রাস প্লনকি2 এর পূর্বসূরি প্লঙ্কির চেয়ে শতগুণ দ্রুততর হয়েছে। এই ট্র্যাজেক্টোরি অনুসরণ করে, কেউ ভাবতে পারে: ক্ষেত্রের প্রস্থ 1 এ সেট করা কি সম্ভব, বিশেষ করে ${\mathbb{F}}_{2}$? উলভেটান্না (অপ্রত্যাশিত) দলটি তাদের গবেষণামূলক প্রবন্ধে এই প্রশ্নটি সম্বোধন করেছে যার শিরোনাম ছিল বাইনারি ফিল্ডের টাওয়ারের উপর সংক্ষিপ্ত আর্গুমেন্টস। [১] , এবং এটি তাদের প্রকল্প, বিনিয়াস: একটি হার্ডওয়্যার-অপ্টিমাইজড SNARK-এর সাথে Rust-এ বাস্তবায়ন করেছে [২] [৩] .

মুক্তির পর থেকে, বিনিয়াস জেডকে (জিরো-নলেজ) সম্প্রদায়ে উল্লেখযোগ্য মনোযোগ অর্জন করেছে। LambdaClass টিম বেশ কিছু প্রযুক্তিগত বিশ্লেষণ প্রদান করেছে [4][5][6], এবং Vitalik Buterin একটি আরো সহজলভ্য ব্যাখ্যা প্রদান করেছেন [৭] . এই নিবন্ধে, আমরা প্রযুক্তিগত এবং বাস্তবায়ন উভয় দৃষ্টিকোণ থেকে বাইনারি ফিল্ডের টাওয়ারগুলিতে ফোকাস করে বিনিয়াসের ভিত্তিগুলি অন্বেষণ করব।

বাইনারি ক্ষেত্র

বিনিয়াসের বাস্তবায়ন বাইনারি ফিল্ডের উপর ভিত্তি করে। বিনিয়াসে, বাইনারি ক্ষেত্রগুলি ফিল্ড এক্সটেনশনের টাওয়ার ব্যবহার করে তৈরি করা হয়।

সবচেয়ে সহজ বাইনারি ক্ষেত্র হল ${{\mathbb{F}}{2}}$ , যেটিতে মাত্র দুটি উপাদান রয়েছে ${0,1}$ , ক্রিয়াকলাপ সম্পাদিত মডুলো 2 সহ: সংযোজন বিটওয়াইজ XOR এর সাথে মিলে যায়, এবং গুণন বিটওয়াইজের সাথে মিলে যায় এবং $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ বেছে নিয়ে, আমরা ${{\mathbb{F}}_{{2^{2}}}}$ ক্ষেত্রটি গঠন করতে পারি। ${{\mathbb{F}}_{{2^{2}}}}$ , যেখানে উপাদানগুলি সর্বাধিক 1 ডিগ্রির বহুপদীর অবশিষ্টাংশ, $r(x) = ax + b$ (with $a, b \in {0, 1}$ )।

ক্ষেত্র প্রসারিত করার একটি পদ্ধতির মধ্যে অপরিবর্তনীয় বহুপদ ব্যবহার করে অবশিষ্টাংশ নেওয়া জড়িত, বিনিয়াস আরও দক্ষ পদ্ধতি ব্যবহার করে: টাওয়ার এক্সটেনশনের ভিত্তি হিসাবে মাল্টিলিনিয়ার ল্যাগ্রেঞ্জ বহুপদীর ব্যবহার। এই পদ্ধতিটি পুনরাবৃত্ত ক্ষেত্র এক্সটেনশনের জন্য অনুমতি দেয়, যেখানে প্রতিটি এক্সটেনশন ক্ষেত্র পূর্ববর্তীটির মধ্যে নেস্ট করা হয়।

টাওয়ার এক্সটেনশনের সুনির্দিষ্ট বাস্তবায়ন নিম্নরূপ: প্রথম, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; তারপর, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; এরপরে, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

ফিল্ড এক্সটেনশনগুলির নির্মাণ প্রক্রিয়া থেকে, এটা স্পষ্ট যে এক্সটেনশনগুলি নিম্নলিখিত সম্পর্কগুলিকে সন্তুষ্ট করে: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ $k \ge 0$ এর জন্য, ক্ষেত্রের এক্সটেনশনটিকে একটি রিংয়ের সরাসরি আকারেও প্রকাশ করা যেতে পারে: ${{\tau }{k}}={{{\mathbb{F}}{2}}[{{x}{0,}}\ldots ,{{x}{k-1}}]}/{\left( x_{0}^{2}+{{x}{0}}+1,\ldots ,x{k-1}^{2}+{{x}{k-2}}{{x}{k-1}}+1 \right)}$.

এই বাস্তবায়নের উপর ভিত্তি করে, নিম্নরূপ বিভিন্ন এক্সটেনশন প্রাপ্ত করা যেতে পারে:

${{\tau }_{0}}=\left{ 0,1 \right}$
${{\tau }{1}}=\left{ 0+0{{x}{0}},1+0{{x}{0}},0+1{{x}{0}},1+1{{x}{0}} \right}$, or ${{\tau }{1}}=\left{ {{\tau }{0}},0+1{{x}{0}},1+1{{x}_{0}} \right}$
$${{\tau }{2}}=\left{ \begin{align} & 0+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},1+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},0+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}}, \ & 1+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}x \ \end{align} \right}$$, Or ${{\tau }{2}}=\left{ {{\tau }{1}},0+0{{x}{0}}+1{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}{{x}{1}} \right}$

বর্ধিত ক্ষেত্রের মধ্যে থাকা উপাদানগুলি থেকে এটি স্পষ্ট যে একটি উপাদান ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ ${{\tau }{k}}$ থেকে প্রাপ্ত, এটি দুটি অংশের সমষ্টিতে পচে যেতে পারে: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . উদাহরণস্বরূপ, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ ।

পুনরাবৃত্তিমূলকভাবে পচন ধরে, আমরা অবশেষে প্রকাশ করতে পারি: $$1100101010001111=1+{{x}{0}}+{{x}{2}}+{{x}{2}}{{x}{1}}+{{x}{3}}+{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{2}}{{x}{3}}+{{x}{1}}{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{1}}{{x}{2}}{{x}{3}}$$

উপরন্তু, $k > 0$ -এর জন্য, যেহেতু $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , যোগ এবং গুণন দক্ষতার সাথে প্রয়োগ করা যেতে পারে বাইনারি বর্ধিত ক্ষেত্র।

বাইনারি ক্ষেত্র বাস্তবায়ন

ইরিডুসিবল বিনিয়াসের ওপেন সোর্স রাস্ট বাস্তবায়ন প্রদান করে [3]। সোর্স কোডে টাওয়ার অফ বাইনারি ফিল্ডস [8,9,10] এর জন্য সম্পূর্ণ বাস্তবায়ন এবং ক্রিয়াকলাপ অন্তর্ভুক্ত রয়েছে।

[৮], চিত্র 1-এ দেখানো হিসাবে, বাস্তবায়নে বাইনারি ক্ষেত্রগুলির জন্য ক্রিয়াকলাপের সম্পূর্ণ সংজ্ঞা এবং বাইনারি ক্ষেত্রগুলির টাওয়ার নির্মাণ অন্তর্ভুক্ত রয়েছে। বাইনারি ক্ষেত্রগুলির টাওয়ার, একটি 128-বিট বাইনারি ক্ষেত্র পর্যন্ত সমর্থন করে, নিম্নরূপ সংজ্ঞায়িত করা হয়েছে: