3,663 पढाइहरू

कसरी बिनियसले बाइनरी फिल्डहरूको टावरहरूसँग कम्प्युटेशनल जटिलता घटाउँछ

द्वारा Sin7Y3m2024/09/13

धेरै लामो; पढ्नकाे लागि

Ulvetanna (IRREDUCIBLE) टोलीले यो प्रश्नलाई आफ्नो शोध पत्रमा Succinct Arguments over Towers of Binary Fields मा सम्बोधन गर्यो। तिनीहरूले यसलाई आफ्नो परियोजना, बिनियस: एक हार्डवेयर-अप्टिमाइज्ड SNARK मार्फत Rust मा लागू गरे। बिनियसमा, बाइनरी फिल्डहरू क्षेत्र विस्तारका टावरहरू प्रयोग गरेर निर्माण गरिन्छ।

featured image - कसरी बिनियसले बाइनरी फिल्डहरूको टावरहरूसँग कम्प्युटेशनल जटिलता घटाउँछ

कम्प्युटेशनल जटिलता कम गर्नु सधैं ब्लकचेन टेक्नोलोजीको प्राथमिक लक्ष्यहरू मध्ये एक हो। यो प्राप्त गर्न को लागी एक प्रभावकारी दृष्टिकोण गणना क्षेत्र को बिट चौडाई को कम गरेर छ। उदाहरणका लागि, अण्डाकार कर्भहरूमा आधारित SNARKहरूले 256 वा माथिको बिट चौडाइ भएका क्षेत्रहरूमा अंकगणितीय कार्यहरू प्रदर्शन गर्छन्, जबकि STARKहरू 64-बिट गोल्डिलक्स फिल्ड प्रयोग गरेर 31-बिट मर्सेने31 र बेबीबियर क्षेत्रहरूमा विकसित भएका छन्। मोड्युलर सञ्चालनका क्रममा प्राइम नम्बरहरूको दक्षताभन्दा बाहिर, बिट चौडाइमा भएको उल्लेखनीय कमीले Plonky2 लाई यसको पूर्ववर्ती Plonky भन्दा सयौं गुणा छिटो भएको छ। यस ट्र्याजेक्टोरी पछ्याउँदै, कसैले सोच्न सक्छ: के फिल्ड चौडाइ 1 मा सेट गर्न सम्भव छ, विशेष गरी ${\mathbb{F}}_{2}$? Ulvetanna (IRREDUCIBLE) टोलीले यो प्रश्नलाई टावर्स अफ बाइनरी फिल्ड्समा Succinct Arguments शीर्षकको आफ्नो अनुसन्धान पत्रमा सम्बोधन गरेको थियो। [१] , र यसलाई तिनीहरूको परियोजना, बिनियस: एक हार्डवेयर-अप्टिमाइज्ड SNARK मार्फत Rust मा लागू गर्यो। [२] [३] ।

यसको विमोचन पछि, बिनियसले ZK (शून्य-ज्ञान) समुदायमा महत्त्वपूर्ण ध्यान प्राप्त गरेको छ। 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$ बाट, थप र गुणन प्रभावकारी रूपमा लागू गर्न सकिन्छ। बाइनरी विस्तारित क्षेत्र।

बाइनरी क्षेत्रहरूको कार्यान्वयन

Irreducible ले बिनियस [3] को खुला स्रोत रस्ट कार्यान्वयन प्रदान गर्दछ। स्रोत कोडले बाइनरी फिल्डको टावरको लागि पूर्ण कार्यान्वयन र अपरेशनहरू समावेश गर्दछ [8,9,10]।

[८] मा, चित्र १ मा देखाइए अनुसार, कार्यान्वयनले बाइनरी क्षेत्रहरूको लागि सञ्चालनको पूर्ण परिभाषा र बाइनरी क्षेत्रहरूको टावरको निर्माण समावेश गर्दछ। बाइनरी फिल्डहरूको टावर, 128-बिट बाइनरी फिल्ड सम्म समर्थन गर्दै, निम्न रूपमा परिभाषित गरिएको छ: