Protocols for Univariate Sumcheck

यहाँ मैल्कम मोहम्मद के शोध पत्र "Protocols for Univariate Sumcheck" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र Succinct Non-Interactive Arguments of Knowledge (SNARKs) के डिज़ाइन में एक मौलिक विषमता (asymmetry) को संबोधित करता है। SNARK सिस्टम डेटा को एनकोड करने के तरीके के आधार पर सामान्यतः दो श्रेणियों में आते हैं:

• Multilinear Systems: ये डेटा वेक्टर्स के Multilinear Extensions (mlex) का उपयोग करते हैं। ये आमतौर पर मानक multivariate sumcheck protocol (LFKF) का उपयोग करते हैं, जो उत्कृष्ट प्रवर (prover) दक्षता (रैखिक समय) प्रदान करता है, लेकिन इसके लिए $O(m)$ राउंड की परस्पर क्रिया (interaction) की आवश्यकता होती है, जिससे यह बैंडविड्थ-भारी और वेरीिफायर के लिए कम अनुकूल हो जाता है।
• Univariate Systems: ये रूट्स ऑफ यूनिटी (roots of unity) पर Univariate Extensions (unex) का उपयोग करते हैं। ये आमतौर पर Aurora protocol का उपयोग करते हैं, जो एक सिंगल-राउंड समचेक है। हालाँकि, मानक यूनिवेरिएट समचेक अक्सर अपने मल्टीवेरिएट समकक्षों की तुलना में उच्च प्रवर जटिलता (quasilinear या उससे अधिक) से ग्रस्त होते हैं।

मुख्य प्रश्न: क्या एक linear-time univariate sumcheck protocol का निर्माण करना संभव है जो मल्टीवेरिएट समचेक की प्रवर दक्षता (prover efficiency) से मेल खाता हो और साथ ही यूनिवेरिएट सिस्टम की राउंड-दक्षता (या कम से कम लचीलापन) को बनाए रखता हो?

मौजूदा "adaptors" जो मल्टीवेरिएट बहुपदों को यूनिवेरिएट में मैप करते हैं (जैसे, Gemini, Caulk, Zeromorph), मौजूद हैं, लेकिन उनमें से कई क्वैसिलिनियर (quasilinear) प्रवर समय से ग्रस्त हैं, उनके लिए जटिल बेसिस ट्रांसलेशन (values-to-coefficients) की आवश्यकता होती है, या वे त्रुटिपूर्ण प्रोटोकॉल (विशेष रूप से DGM प्रोटोकॉल) पर निर्भर करते हैं।

2. कार्यप्रणाली (Methodology)

लेखक इस अंतर को पाटने के लिए तीन संभावित दृष्टिकोण प्रस्तावित करते हैं, जिनका लक्ष्य यूनिवेरिएट समचेक समस्याओं को कुशल मल्टीवेरिएट तकनीकों या प्रत्यक्ष रैखिक-समय रिडक्शन (linear-time reductions) में बदलना है।

A. Multilinear को Univariate में बदलना (Section 3)

पहला दृष्टिकोण यूनिवेरिएट एक्सटेंशन बहुपद (unex) को एक ऑरेकल (oracle) के रूप में मानता है और इसके संगत मल्टीलिनियर एक्सटेंशन (mlex) के बारे में कथनों को सिद्ध करता है।

• तंत्र (Mechanism): शोध पत्र Protocol 2 पेश करता है, जो एक रिकर्सिव फोल्डिंग प्रोटोकॉल है। यह रूट्स ऑफ यूनिटी के आधार पर यूनिवेरिएट बहुपद $f$ को "स्क्वायर" ($f_{sq}$) और "नॉन-स्क्वायर" ($f_{no}$) घटकों में विभाजित करता है।
• मुख्य अंतर्दृष्टि (Key Insight): एक सामान्यीकृत लैग्रेंज इंटरपोलेशन फॉर्मूला का उपयोग करते हुए, प्रवर इन घटकों के लिए ऑरेकल भेजता है। वेरीिफायर एक यादृच्छिक बिंदु (random point) पर निरंतरता (consistency) की जाँच करता है। यह जटिल बेसिस ट्रांसलेशन के बिना सीधे mlex प्रतिनिधित्व पर मानक मल्टीवेरिएट समचेक प्रोटोकॉल चलाने की अनुमति देता है।
• जटिलता: यह $O(2^m)$ रैखिक प्रवर समय और $O(m)$ वेरीिफायर समय प्राप्त करता है।

B. DGM सुधार के माध्यम से प्रत्यक्ष Univariate Sumcheck (Section 4.1 & 4.2)

यह शोध पत्र ड्रेक, गैबिसन और मेकलर (DGM) द्वारा प्रस्तावित एक पूर्व प्रोटोकॉल का विश्लेषण करता है, जिसने यूनिवेरिएट डोमेन आइडेंटिटी को जेमिनी प्रोटोकॉल में बदलने का प्रयास किया था।

• त्रुटि की पहचान (Flaw Identification): लेखक मूल DGM प्रोटोकॉल में एक महत्वपूर्ण दोष की पहचान करते हैं: प्रस्तावित बहुपद पहचान (पेपर में समीकरण 3) विफल हो जाती है क्योंकि दोनों पक्षों के बहुपदों की डिग्री मेल नहीं खाती है, जिससे प्रोटोकॉल न तो पूर्ण (complete) है और न ही सुदृढ़ (sound)।
• सुधार (Correction): लेखक Protocol 3 प्रस्तावित करते हैं, जो एक सुधारा गया संस्करण है। यह सुनिश्चित करने के लिए अतिरिक्त जाँच पेश करता है कि बहुपदों के "इवन/ओड" (even/odd) भागों और मूल बहुपद के बीच डिग्री सीमा और निरंतरता बनी रहे।
• परिणाम: सुधारा गया यह प्रोटोकॉल सफलतापूर्वक यूनिवेरिएट समचेक को जेमिनी में बदल देता है, लेकिन अतिरिक्त ऑरेकल और फील्ड एलिमेंट्स के कारण यह प्रत्यक्ष दृष्टिकोण की तुलना में कम कुशल रहता है।

C. Gemini में प्रत्यक्ष रिडक्शन (Section 4.3)

सबसे महत्वपूर्ण योगदान Protocol 4 है, जो एक सीधा रैखिक-समय यूनिवेरिएट समचेक है जो DGM के मध्यवर्ती "डोमेन आइडेंटिटी" चरण से बचता है।

• तंत्र (Mechanism): यह प्रोटोकॉल इस अवलोकन का लाभ उठाता है कि रूट्स ऑफ यूनिटी पर एक यूनिवेरिएट बहुपद का मूल्यांकन करना, विशिष्ट बिंदुओं पर इसके मल्टीलिनियर एक्सटेंशन के मूल्यांकन के समान है जो इन रूट्स से व्युत्पन्न होते हैं।
  • विशेष रूप से, $f(w^i) = \text{mlin}[f](w^i, w^{2i}, \dots, w^{2^{m-1}i})$।
• प्रक्रिया: प्रवर एक राउंड बहुपद $p_1(y)$ भेजता है जो आधे डोमेन पर योग (sum) का प्रतिनिधित्व करता है। वेरीिफायर $p_1(1) + p_1(-1) = s$ की जाँच करता है। इसके बाद दावा एक छोटे यूनिवेरिएट समचेक में बदल जाता है जिसमें $r_1 w^i, w^{2i}, \dots$ पर मूल्यांकित बहुपदों का उपयोग किया जाता है।
• दक्षता: यह प्रोटोकॉल अनिवार्य रूप से मानक मल्टीवेरिएट समचेक की दक्षता की नकल करता है, जिसमें किसी जटिल बेसिस ट्रांसलेशन ओवरहेड की आवश्यकता नहीं होती है।

D. राउंड रिडक्शन (Sections 3.3 & 4.3)

शोध पत्र यह प्रदर्शित करता है कि कैसे इंटरैक्शन राउंड्स को $m$ से घटाकर $\log(m)$ या यहाँ तक कि $O(\sqrt{m})$ तक कम किया जा सकता है।

• रणनीति: इन प्रोटोकॉल को $k$ राउंड के बाद "अर्ली-स्टॉप" (early-stop) किया जा सकता है। शेष छोटे यूनिवेरिएट दावे को Aurora जैसे सिंगल-राउंड प्रोटोकॉल द्वारा संभाला जाता है।
• लाभ: पिछले कार्यों (जैसे, HybridPlonk) के विपरीत, यह दृष्टिकोण बेसिस ट्रांसलेशन चरणों (कोएफिशिएंट और इवैल्यूएशन रूपों के बीच रूपांतरण) के बिना काम करता है क्योंकि बूलियन हाइपरक्यूब और रूट्स ऑफ यूनिटी के बीच का मैपिंग स्वाभाविक रूप से संरक्षित रहता है।

3. मुख्य योगदान (Key Contributions)

1. Linear-Time Univariate Sumcheck: शोध पत्र पहले ठोस, रैखिक-समय यूनिवेरिएट समचेक प्रोटोकॉल (Protocol 2 और Protocol 4) प्रदान करता है जो मौजूदा यूनिवेरिएट SNARKs के साथ संगत हैं।
2. DGM का सुधार: शोध पत्र औपचारिक रूप से DGM प्रोटोकॉल की साउंडनेस/कम्प्लीटनेस खामियों की पहचान करता है और उन्हें ठीक करता है, जिससे जेमिनी एडैप्टर के साथ इसके संबंध को स्पष्ट किया जाता है।
3. Protocol 4 (Direct Reduction): एक नया, अत्यधिक कुशल प्रोटोकॉल पेश करता है जो मध्यवर्ती "डोमेन आइडेंटिटी" चरणों के बिना यूनिवेरिएट समचेक को सीधे मल्टीवेरिएट इवैल्यूएशन में बदल देता है, जो DGM और एडैप्टर-आधारित दृष्टिकोणों से बेहतर प्रदर्शन करता है।
4. बिना ओवरहेड के राउंड रिडक्शन: यह प्रदर्शित करता है कि ये प्रोटोकॉल बेसिस ट्रांसलेशन के ओवरहेड के बिना $\log m$ या $\sqrt{m}$ राउंड तक राउंड रिडक्शन का समर्थन करते हैं, जो उन्हें कुछ कॉन्फ़िगरेशन के लिए HybridPlonk से बेहतर बनाता है।
5. व्यापक विश्लेषण: यह विभिन्न कॉन्फ़िगरेशन का एक विस्तृत तुलनात्मक विश्लेषण (तालिका 2) प्रस्तुत करता है, जो दिखाता है कि नए प्रोटोकॉल यूनिवेरिएट सिस्टम को वह प्रवर दक्षता प्राप्त करने की अनुमति देते हैं जो पहले मल्टीलिनियर सिस्टम के लिए आरक्षित थी।

4. परिणाम और प्रदर्शन (Results and Performance)

शोध पत्र विभिन्न कॉन्फ़िगरेशन का तुलनात्मक विश्लेषण (तालिका 2) प्रस्तुत करता है:

• प्रवर समय (Prover Time): प्रस्तावित प्रोटोकॉल (विशेष रूप से Protocol 4 + Gemini) रैखिक प्रवर समय $O(d^2 2^m)$ प्राप्त करते हैं, जो मानक मल्टीवेरिएट समचेक की दक्षता से मेल खाता है। यह पिछले यूनिवेरिएट एडैप्टर्स के क्वैसिलिनियर समय की तुलना में एक महत्वपूर्ण सुधार है।
• संचार (Communication): Protocol 4 में $O(dm)$फील्ड एलिमेंट्स और$O(m)$ ऑरेकल भेजे जाते हैं। हालांकि यह सिंगल-राउंड Aurora प्रोटोकॉल की तुलना में थोड़ा अधिक है, फिर भी यह मल्टीवेरिएट दृष्टिकोणों के प्रतिस्पर्धी है।
• राउंड्स (Rounds):
  • मानक निष्पादन: $m$ राउंड।
  • राउंड रिडक्शन के साथ: इसे $\log(m)$ राउंड (टेल के लिए Aurora का उपयोग करके) या $O(\sqrt{m})$ राउंड (एक सामान्यीकृत इनवर्स क्रोनेकर मैप का उपयोग करके) तक कम किया जा सकता है।
• वेरीिफायर जटिलता: यह कम रहती है, जो आमतौर पर राउंड रिडक्शन रणनीति के आधार पर $O(m)$ या $O(\log m)$ होती है।

5. महत्व (Significance)

यह कार्य SNARK निर्माण के भविष्य के लिए महत्वपूर्ण है क्योंकि यह यूनिवेरिएट सिस्टम में प्रवर दक्षता और राउंड दक्षता के बीच के समझौते (trade-off) को समाप्त करता है।

• एकीकरण (Unification): यह यूनिवेरिएट-आधारित SNARKs (जो अपनी सरलता और सिंगल-राउंड वेरिफिकेशन के लिए पसंद किए जाते हैं) को भारी बेसिस ट्रांसलेशन लागत के बिना अत्यधिक कुशल मल्टीवेरिएट समचेक तकनीकों का उपयोग करने की अनुमति देता है।
• व्यावहारिकता: DGM प्रोटोकॉल को ठीक करके और Protocol 4 पेश करके, शोध पत्र डेवलपर्स के लिए, जो अगली पीढ़ी के zk-SNARKs बना रहे हैं, कार्यान्वयन योग्य और कुशल समाधान प्रदान करता है।
• लचीलापन: प्रवर गति से समझौता किए बिना राउंड की संख्या को ट्यून करने (रैखिक से लॉगरिदमिक या स्क्वायर-रूट तक) की क्षमता, सिस्टम डिजाइनरों को विशिष्ट हार्डवेयर या नेटवर्क बाधाओं के लिए अनुकूलित करने हेतु नए विकल्प देती है।

संक्षेप में, यह शोध पत्र सिद्ध करता है कि उपयुक्त रिडक्शन और एडैप्टर को जोड़कर रैखिक-समय यूनिवेरिएट समचेक सामान्य रूप से प्राप्त करने योग्य है, जो प्रभावी रूप से "दोनों दुनियाओं का सर्वश्रेष्ठ" (मल्टीलिनियर दक्षता और यूनिवेरिएट राउंड-फ्रेंडलीनेस) SNARK परिदृश्य में लाता है।