ZKVM सर्किट को कैसे डिज़ाइन करें

स्वनिर्धारित गेट

Zkvm सर्किट को डिजाइन करते समय, कई कस्टम गेट निर्धारित किए जाने के कारण, बहुत सारे बाइनरी चयनकर्ता पेश किए जाते हैं।

एक उदाहरण के रूप में (फ़ील्ड) डिवीजन गेट लेते हुए, हम यह सत्यापित करने के लिए एक गेट डिजाइन करने की योजना बनाते हैं कि संबंध q = x/y तीन तत्वों q, x, y के बीच काम करता है।

सुविधा के लिए हम परिपथ स्तर पर फील्ड डिवीजन ऑपरेशन नहीं करेंगे, इसके बजाय, हम निम्नलिखित तार्किक संबंध को सत्यापित करके इसे बनाएंगे:

एक्स * आमंत्रण_y = q

inv_y∗y=1 // सुनिश्चित करें कि y≠0

दोनों तत्वों के बीच एक समान संबंध है। इसलिए, हमारे पास निम्न ट्रेस तालिका है:

बहुपद को परिभाषित करें w_0(x), w_1(x), w_2(x), w_3(x) कॉलम के लिए w_0,w_1,w_2,w_3 फिर विभाजन ऑपरेशन से संबंधित पंक्तियों को संतुष्ट करेगा：

डब्ल्यू_0 (एक्स)। w_3(x) - w_2(x) = 0 w_1(x) । w_3(x) - 1 = 0

यह सुनिश्चित करने के लिए कि उपरोक्त संबंध संबंधित पंक्ति में संतुष्ट हो सकते हैं, सत्यापन को बाधित करने के लिए संबंधित विभाजन बनाने के लिए एक चयनकर्ता की आवश्यकता होती है।

इसलिए, हमने एक नया कॉलम s_{div} = {0,0,...1,...0}$ पेश किया है। जब इसे बहुपद s_{div}(x) में बदल दिया जाता है, तो उपरोक्त समीकरण होगा:

s_{div}(x) ⋅ (w_0(x) ⋅ w_3(x) - w_2(x)) = 0

s_{div}(x) (w_1(x) ⋅ w_3(x) - 1) = 0

संयुक्त चयनकर्ता

ऊपर के उदाहरण से, हम देख सकते हैं कि जब हम एक नया अनुकूलित गेट परिभाषित करते हैं, तो गेट के अनुरूप एक चयनकर्ता कॉलम s* को पेश करने की आवश्यकता होती है।

यदि हम t∗(x) के साथ गेट के संगत बाधा बहुपद का प्रतिनिधित्व करते हैं, तो हम अंत में निम्नलिखित बाधाओं को प्राप्त कर सकते हैं:

s_{जोड़ें}(x) t_{जोड़ें}(x) = 0

s_{div}(x) t_{जोड़ें}(x) = 0

s_{घन}(x) t_{घन}(x) = 0

s_{sqrt}(x) t_{sqrt}(x) = 0

...

प्रूफ जनरेशन के दौरान प्रोवर को सभी बहुपदों के लिए प्रतिबद्धताओं का संचालन करने की आवश्यकता होती है, अधिक से अधिक चयनकर्ता बहुपदों को पेश करने से प्रोवर और सत्यापनकर्ता के कार्यभार में वृद्धि होगी।

इसलिए, चयनकर्ता संख्या को अनुकूलित करना आवश्यक है जबकि निम्नलिखित दो शर्तें पूरी होनी चाहिए:

1. चयनकर्ता बहुपद के अर्थ के लिए कोई नुकसान नहीं है, अर्थात केवल विशिष्ट द्वार का उपयोग किया जा सकता है;

   
   

2. कम चयनकर्ता बहुपद

"प्लोंकी 2: प्लॉन्क और एफआरआई के साथ फास्ट रिकर्सिव तर्क" ( https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ) में, एक अनुकूलन विधि है "बाइनरी-ट्री आधारित चयनकर्ता" , जो चुनिंदा बहुपद की संख्या को घटाकर लॉग (k) कर देता है, और k अनुकूलित गेट की संख्या है।

Halo2 पेपर में, zcash टीम ने एक नई अनुकूलन विधि को सामने रखा है, जो बहुपद की एक छोटी संख्या का एहसास कर सकती है (बाधा बहुपद t∗(x) और बाधा बहुपद max_degree के लिए निर्धारित मापदंडों के साथ सहसंबंध में)।

इसे आसानी से समझने के लिए, आइए एक सरल उदाहरण लेते हैं (एक विशिष्ट एल्गोरिदम के लिए, कृपया चयनकर्ता संयोजन - हेलो 2 बुक देखें)

हम देख सकते हैं कि हमने 4 प्रकार के कस्टमाइज़्ड गेट्स के लिए 4 चयनकर्ता कॉलम सेट किए हैं, जो कि हम उपरोक्त की तरह नहीं चाहते हैं।

इसलिए, इससे प्रोवर और वेरिफायर का काम का बोझ बढ़ जाएगा। यहां हम एक नया कॉलम q परिभाषित करते हैं, जो संतोषजनक है:

यदि हम चयनकर्ताओं s_{add} के लिए एक सेट {s_{add}, s_{div}, s_{cube}, s_{sqrt}} (जिसे डिसजॉइंट कहा जाता है, यानी संभावित पंक्तियों के बीच कोई सामान्य बिंदु नहीं है) को परिभाषित करते हैं। , s_{div}, s_{cube}, s_{sqrt} तो कॉलम q की परिभाषा के आधार पर, हमारे पास है:

यहां, कॉलम q के आधार पर एक नया चयनकर्ता बहुपद रूप परिभाषित करें, और संख्या k चयनकर्ता बहुपद के लिए, हमारे पास है:

उदाहरण के लिए, बाधा के लिए: s_add t_add(x) = 0, इसमें फिर से लिखा जा सकता है:

उपरोक्त सूत्र में विस्तार किया जा सकता है:

समूह

फिर, वास्तविक मूल्य आंकड़ा प्राप्त होता है:

यह देखा जा सकता है कि यह वही काम करता है जो मूल चयनकर्ता करता है। इसलिए, बाधाओं के लिए:

s_{जोड़ें}(x) t_{जोड़ें}(x) = 0

s_{div}(x) t_{जोड़ें}(x) = 0

s_{घन}(x) t_{घन}(x) = 0

s_{sqrt}(x) t_{sqrt}(x) = 0

...

हम बाधाओं को फिर से लिख सकते हैं:

उपरोक्त बाधाओं के लिए, हमें केवल बहुपद q(x) के प्रति वचनबद्धता का संचालन करने की आवश्यकता है। लेकिन यह ध्यान देने योग्य है कि, इस पद्धति ने बाधा की डिग्री भी बढ़ा दी है।

अब तक, हमने ऊपर बताए गए दो बिंदुओं को हासिल किया है:

1. चयनकर्ता बहुपद के अर्थ के लिए कोई नुकसान नहीं है, अर्थात केवल विशिष्ट द्वार का उपयोग किया जा सकता है;

   
   

2. कम चयनकर्ता बहुपद

बेशक, प्रोटोकॉल में सीमित डिग्री की सीमाएं हैं, इसलिए संयोजन में भाग लेने वाले चयनकर्ता संख्या सीमित है, यानी, एकल संयुक्त चयनकर्ता की संख्या डिग्री के सीमा मूल्य और बाधा बहुपद टी की अधिकतम_डिग्री पर निर्भर करती है। (एक्स)।

इसलिए, अधिक संयुक्त स्तंभों की आवश्यकता है, और वैसे भी, संख्या अभी भी मूल की तुलना में बहुत छोटी है।

अधिक मामलों को संभालने और एल्गोरिथम विवरण के लिए, कृपया चयनकर्ता संयोजन - हेलो 2 बुक देखें।

संदर्भ

1. "हेलो 2 बुक",

   https://zcash.github.io/halo2/design/implementation/selector-combining.html

   
   

2. पॉलीगॉन ज़ीरो टीम, "प्लोंकी 2: प्लॉन्क और एफआरआई के साथ फास्ट रिकर्सिव तर्क", https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf , एक्सेस किया गया: 2022-02-06