A Complexity-Theoretic Approach to Proofs of Space

तकनीकी सारांश: स्पेस के प्रमाणों (Proofs of Space) के लिए एक जटिलता-सैद्धांतिक दृष्टिकोण

समस्या विवरण
स्पेस के प्रमाण (Proofs of Space - PoS), जिन्हें डिज़िएम्बोव्स्कीकी और अन्य [DFKP15] द्वारा पेश किया गया था, दो-चरणीय प्रोटोकॉल हैं जो एक प्रूवर (Prover) को एक कुशल वेरीफायर (Verifier) को यह समझाने की अनुमति देते हैं कि उसने एक महत्वपूर्ण मात्रा में स्थायी मेमोरी आवंटित की है। प्रोटोकॉल में एक इनिशियलाइज़ेशन चरण (लंबी अवधि) शामिल है जहाँ प्रूवर डेटा संग्रहीत करता है, और एक निष्पादन चरण (छोटी अवधि) शामिल है जहाँ वेरीफायर प्रूवर को चुनौती देता है कि वह सिद्ध करे कि डेटा अभी भी संग्रहीत है।

मौजूदा PoS प्रोटोकॉल की एक महत्वपूर्ण सीमा यह है कि उनके सुरक्षा प्रमाण भारी रूप से रैंडम ओरकल मॉडल (Random Oracle Model - ROM) या अधोमुखी (ad hoc) क्रिप्टोग्राफिक धारणाओं पर निर्भर करते हैं। विशेष रूप से, वे रैंडम ओरकल प्रश्नों की समवर्ती असंपीड्यता (incompressibility) और निष्कर्षण क्षमता (extractibility) पर निर्भर करते हैं। अब तक, ऐसी कोई रचना ज्ञात नहीं है जो केवल मानक क्रिप्टोग्राफिक धारणाओं के आधार पर प्लेन मॉडल (बिना रैंडम ओरकल के) में सुरक्षित हो। क्रिप्टोग्राफिक हैश फ़ंक्शंस के संबंध में ऐसी स्पष्ट, विखंडनीय (falsifiable) धारणाओं का अभाव है जो इन रचनाओं की प्रमाणित सुरक्षा के लिए पर्याप्त हों।

कार्यप्रणाली और ढांचा
यह शोध पत्र डेरैंडमाइजेशन धारणाओं (derandomization assumptions) को क्रिप्टोग्राफिक धारणाओं के साथ जोड़कर प्लेन मॉडल में PoS के निर्माण के लिए एक प्राथमिक ढांचा प्रस्तुत करता है। मुख्य अंतर्दृष्टि यह है कि एक PoS के लिए एक स्ट्रिंग $\sigma$ की आवश्यकता होती है जो विरोधाभासी रूप से एक संक्षिप्त विवरण (पर्याप्त समय $T$ मिलने पर) से संपीड़ित (compressible) भी है और किसी थोड़े छोटे विवरण से (कम समय $t$ के भीतर) असंपीडित (incompressible) भी है।

लेखक इसे कंप्यूटेशनल डेप्थ (computational depth) की जटिलता-सैद्धांतिक अवधारणा (जिसे एंट्यून्स एट अल. [AFvMV06] द्वारा पेश किया गया था) का उपयोग करके औपचारिक रूप देते हैं। वे एक ऐसे फलन $f$ की खोज करते हैं जिसमें उच्च कंप्यूटेशनल डेप्थ हो:

1. लंबे समय की संपीड़्यता (Long-time compressibility): $f(x)$ को एक संक्षिप्त सीड $x$ से समय $T$ में कंप्यूट किया जा सकता है।
2. छोटे समय की असंपीड्यता (Short-time incompressibility): $x$ दिए जाने पर भी, $f(x)$ को किसी भी छोटे विवरण से समय $t$ के भीतर पुनर्गठित नहीं किया जा सकता है।

निर्माण तीन चरणों में आगे बढ़ता है:

1. उच्च-डेप्थ वाले फलनों का निर्माण:
   लेखक नॉन-डिटरमिनिस्टिक डिस्टिंग्विशर्स (nondeterministic distinguishers) के विरुद्ध सीड-एक्सटेंडिंग प्रूडो-रैंडम जनरेटर्स (PRGs) का उपयोग करते हैं। इस धारणा के तहत कि $E = \text{DTIME}[2^{O(n)}]$ को घातांकीय आकार के नॉन-डिटरमिनिस्टिक सर्किट्स की आवश्यकता है (एक मानक धारणा जिसका उपयोग $\text{AM} = \text{NP}$ दिखाने के लिए किया जाता है), वे ऐसे PRGs का निर्माण करते हैं जो नॉन-डिटरमिनिस्टिक सर्किट्स के लिए कठिन हैं।

• अत्यधिक संभावना (Overwhelming probability) के साथ असंपीड्यता प्राप्त करने के लिए, वे नॉन-डिटरमिनिस्टिक डिस्टिंग्विशर्स के विरुद्ध मल्टीप्लिकेटिव PRGs का उपयोग करते हैं। ये नगण्य घटनाओं की संभावना को संरक्षित करते हैं, जिससे यह सुनिश्चित होता है कि PRG का आउटपुट अत्यधिक संभावना के साथ असंपीडित रहता है।
• अनुमानित असंपीड्यता (हैमिंग डिस्टेंस त्रुटियों के प्रति लचीलापन) को संभालने के लिए, वे PRG को लिस्ट-डिकोडेबल एरर-करेक्टिंग कोड्स (ECC) के साथ संयोजित करते हैं। यह सुनिश्चित करता है कि भले ही एक एडवर्सरी (adversary) $f(x)$ के करीब एक स्ट्रिंग को पुनः प्राप्त कर ले, मूल स्ट्रिंग असंपीडित बनी रहती है।

2. एक्सट्रैक्शन लेम्मा (The Extraction Lemma):
   एक केंद्रीय तकनीकी योगदान एक्सट्रैक्शन लेम्मा (लेम्मा 11) है। यह बताता है कि यदि एक प्रूवर एक छोटा स्टेट $S$ बनाए रख सकता है और गैर-नगण्य संभावना के साथ सत्यापन चुनौतियों का सफलतापूर्वक उत्तर दे सकता है, तो अंतर्निहित स्ट्रिंग $y = f(x)$ लगभग संपीड़ित है।

• लेम्मा एक हिटिंग सेट जनरेटर (HSG) का उपयोग करता है ताकि नियत रूप से "उपयोगी" चुनौती इंडेक्स का एक सेट चुना जा सके जो संग्रहीत स्ट्रिंग के एक बड़े हिस्से को कवर करता है।
• यह एक एक्सट्रैक्टर को समय $t$ के भीतर प्रूवर के छोटे स्टेट से $y$ के अधिकांश बिट्स को पुनः प्राप्त करने की अनुमति देता है, जो $f$ की मानी गई असंपीड्यता का खंडन करता है।

3. प्रोटोकॉल इंस्टेंशिएशन (Protocol Instantiation):
   इस ढांचे को दो विशिष्ट PoS प्रोटोकॉल में स्थापित किया गया है, जो अपनी क्रिप्टोग्राफिक धारणाओं और स्टोरेज ओवरहेड में भिन्न होते हैं:

• निर्माण 1 (SNARG-आधारित): $P$ के लिए एक सेमी-यूनिवर्सल नॉन-इंटरैक्टिव आर्गुमेंट (SNARG) का उपयोग करता है। प्रूवर $f(x)$ का मर्केल रूट (Merkle root) और एक संक्षिप्त प्रमाण संग्रहीत करता है कि रूट $f(x)$ के अनुरूप है। यह $P$ के लिए SNARGs के अस्तित्व पर निर्भर करता है (एक मजबूत धारणा) लेकिन ईमानदार प्रूवर के लिए लगभग इष्टतम स्टोरेज ($N$ बिट्स) प्रदान करता है।
• निर्माण 2 (Kilian-आधारित): PCPs और कोलिजन-रेसिस्टेंट हैश फंक्शन्स (CRHF) पर आधारित किलियन के इंटरैक्टिव आर्गुमेंट सिस्टम का उपयोग करता है। प्रूवर को $f(x)$ की गणना का PCP स्ट्रिंग संग्रहीत करना पड़ता है, जिससे ईमानदार स्टोरेज की आवश्यकता अधिक ($N + \tilde{O}(T)$) हो जाती है, लेकिन यह कमजोर क्रिप्टोग्राफिक धारणाओं (CRHF + डैरांडमाइजेशन) पर निर्भर करता है।

मुख्य परिणाम
यह शोध पत्र (अनौपचारिक रूप से) निम्नलिखित प्रमेय स्थापित करता है:

• प्रमेय 1: यह मानते हुए कि $E$ को घातांकीय आकार के नॉन-डिटरमिनिस्टिक सर्किट्स के लिए कठिन माना जाता है, ऐसी स्पष्ट फलन मौजूद हैं जो समय-$t$ के लिए $N - O(\rho N \log(1/\rho))$ आकार तक असंपीडित हैं।
• प्रमेय 2 (SNARG इंस्टेंशिएशन): यह मानते हुए कि $E$ को घातांकीय आकार के नॉन-डिटरमिनिस्टिक सर्किट्स के लिए कठिन माना जाता है, वन-वे फंक्शन्स और $P$ के लिए एक सेमी-यूनिवर्सल SNARG, एक ऐसा PoS मौजूद है जहाँ ईमानदार प्रूवर $N$ बिट्स संग्रहीत करता है, और यह योजना $(1-o(1))N$ बिट्स का उपयोग करने वाले किसी भी प्रूवर के विरुद्ध सुरक्षित है।
• प्रमेय 3 (CRHF इंस्टेंशिएशन): यह मानते हुए कि $E$ को घातांकीय आकार के नॉन-डिटरमिनिस्टिक सर्किट्स के लिए कठिन माना जाता है और कोलिजन-रेसिस्टेंट हैश फंक्शन्स मौजूद हैं, एक ऐसा PoS मौजूद है जहाँ ईमानदार प्रूवर $N$ बिट्स संग्रहीत करता है, और यह $N^{1/c}$ बिट्स (किसी स्थिरांक $c$ के लिए) का उपयोग करने वाले किसी भी प्रूवर के विरुद्ध सुरक्षित है।

महत्व और दावे
लेखक इस बात पर जोर देते हैं कि उनका कार्य प्लेन मॉडल में PoS के लिए एक शैक्षणिक रूप से स्वच्छ, जेनेरिक व्यवहार्यता (pedagogically clean, generic feasibility) परिणाम प्रदान करता है।

• ROM बाधा को तोड़ना: वे प्रदर्शित करते हैं कि बिना रैंडम ओरकल के, मानक डैरांडमाइजेशन धारणाओं (नॉन-डिटरमिनिस्टिक सर्किट्स के विरुद्ध $E$ की कठिनाई) को मानक क्रिप्टोग्राफिक प्रिमिटिव्स के साथ जोड़कर PoS का निर्माण किया जा सकता है।
• ट्रेड-ऑफ (Trade-offs): शोध पत्र क्रिप्टोग्राफिक धारणाओं और स्टोरेज दक्षता के बीच के ट्रेड-ऑफ को उजागर करता है। SNARG-आधारित दृष्टिकोण ईमानदार प्रूवर के स्टोरेज को न्यूनतम करता है लेकिन इसके लिए मजबूत धारणाओं की आवश्यकता होती है। Kilian-आधारित दृष्टिकोण कमजोर धारणाओं (CRHF) का उपयोग करता है लेकिन ईमानदार प्रूवर को $f(x)$ की गणना का PCP संग्रहीत करने की आवश्यकता होती है, जिससे स्टोरेज काफी बढ़ जाता है।
• सीमाएँ: लेखक स्पष्ट रूप से कहते हैं कि उनका ध्यान सैद्धांतिक व्यवहार्यता पर है, न कि परिष्कृत थ्रेट मॉडल्स या व्यावहारिक प्रोटोकॉल पर। वे उल्लेख करते हैं कि हालांकि उनका ढांचा PoS प्रदान करता है, लेकिन इन विचारों को मेमोरी-हार्ड फंक्शन्स (MHFs) (एक संबंधित वस्तु जो अक्सर ROM-आधारित PoS से प्राप्त होती है) के निर्माण के लिए अनुकूलित करना तुरंत स्पष्ट नहीं है। इसके अतिरिक्त, वे स्वीकार करते हैं कि कंपोज़िशन (एक एकल प्रूवर का कई वेरीफायर के साथ इंटरैक्ट करना) को संभालने के लिए यह सुनिश्चित करने हेतु और कार्य की आवश्यकता है कि स्टोरेज लागत का एमोर्टाइजेशन (amortize) न हो।

संक्षेप में, यह कार्य जटिलता सिद्धांत और क्रिप्टोग्राफिक प्रोटोकॉल के बीच के अंतर को पाटता है, यह दिखाते हुए कि 'कठिनाई' (hardness) जिसे 'स्पेस के प्रमाण' (Proofs of Space) के लिए आवश्यक माना जाता है, उसे हेयुरिस्टिक रैंडम ओरकल मॉडल के बजाय मौलिक डैरांडमाइजेशन धारणाओं से प्राप्त किया जा सकता है।