SNARK प्रदर्शन को मापना: फ्रंटएंड, बैकएंड और भविष्य

एक SNARK (संक्षिप्त गैर-संवादात्मक ज्ञान का तर्क) ब्लॉकचेन स्केलेबिलिटी (जैसे, L2 रोलअप) और गोपनीयता के लिए एक महत्वपूर्ण क्रिप्टोग्राफ़िक आदिम खोज अनुप्रयोग है। SNARKs किसी को अविश्वसनीय सत्यापनकर्ता साबित करने देते हैं V (उदाहरण के लिए, एथेरियम ब्लॉकचेन) कि वे कुछ डेटा जानते हैं (जैसे, वैध लेनदेन का एक बैच)। इसे साबित करने का एक भोला तरीका यह होगा कि डेटा को भेजा जाए V, जो फिर सीधे इसकी वैधता की जांच कर सकता है। एक SNARK वही हासिल करता है, लेकिन बेहतर लागत के साथ V. विशेष रूप से, एक SNARK प्रूफ डेटा को शामिल करने वाले भोले से छोटा होना चाहिए। (अधिक विवरण के लिए, मेरी पाठ्यपुस्तक का प्रारूप देखें, सबूत, तर्क और शून्य ज्ञान. SNARKs के परिचय के लिए, देखें सारा मिकलेजॉन्स प्रदर्शन a16z क्रिप्टो पर ग्रीष्मकालीन अनुसंधान श्रृंखला.)

SNARK के लिए सत्यापन लागत भिन्न हो सकती है, लेकिन अच्छी तरह से समझी जाती है और अक्सर काफी अच्छी होती है। उदाहरण के लिए, प्लोनके सबूत लागत के बारे में 290,000 गैस इथेरियम पर सत्यापित करने के लिए, जबकि स्टार्कवेयर के प्रमाणों की कीमत लगभग 5 मिलियन गैस थी। SNARK संभावित रूप से ब्लॉकचेन के बाहर भी विविध सेटिंग्स में लागू होते हैं - उदाहरण के लिए तेज़ लेकिन अविश्वसनीय के उपयोग को सक्षम करना सर्वर और हार्डवेयर. 

लेकिन क्योंकि SNARK सत्यापन आम तौर पर सस्ता है, प्रयोज्यता के मुख्य निर्धारक SNARK कहावत की लागत हैं P. इस पोस्ट में, मैं समझाता हूं कि इन लागतों का अनुमान कैसे लगाया जाए, यह निर्धारित करने के लिए कि कब SNARK का उपयोग करना उचित है, और भविष्य में SNARK कैसे बेहतर हो सकते हैं। यह ध्यान देने योग्य है कि यह एक तेजी से आगे बढ़ने वाला स्थान है, और इस पोस्ट में चर्चा की गई कई परियोजनाएं सक्रिय रूप से अपने प्रदर्शन में सुधार कर रही हैं।

लेकिन पहले: SNARK कैसे तैनात किए जाते हैं

SNARK परिनियोजन में एक डेवलपर आमतौर पर एक कंप्यूटर प्रोग्राम लिखता है ψ जो डेटा इनपुट के रूप में लेता है w कि कहावत जानने का दावा करती है (w के लिए खड़ा है गवाह), और जाँचता है कि w यह सही है। उदाहरण के लिए, रोलअप में, प्रोग्राम जाँच करेगा कि सभी लेन-देन in w डिजिटल रूप से हस्ताक्षरित हैं, किसी भी खाते की शेष राशि शून्य से नीचे गिरने का कारण न बनें, इत्यादि। कार्यक्रम ψ फिर a . के माध्यम से खिलाया जाता है SNARK दृश्यपटल जो इसे एक ऐसे प्रारूप में संकलित करता है जो SNARK प्रौद्योगिकी के अनुप्रयोग के लिए अधिक अनुकूल है। इस SNARK के अनुकूल प्रारूप को an . कहा जाता है मध्यवर्ती प्रतिनिधित्व (आईआर)। 

आम तौर पर, आईआर किसी प्रकार का सर्किट-संतुष्टि उदाहरण है जो बराबर है . इसका मतलब है कि सर्किट C डेटा इनपुट के रूप में लेता है w, साथ ही कुछ अतिरिक्त इनपुट जिन्हें आमतौर पर "गैर-नियतात्मक सलाह" कहा जाता है, और चलता है ψ on w. सलाह इनपुट का उपयोग मदद करने के लिए किया जाता है C रन ψ, रखते हुए C छोटा। उदाहरण के लिए, हर बार ψ दो संख्याओं को विभाजित करता है x और y, भागफल q और शेष r को सलाह के रूप में प्रदान किया जा सकता है C, तथा C बस इसे चेक कर सकते हैं x = qy + r. यह चेक बनाने से कम खर्चीला है C गणना करने के लिए एक विभाजन एल्गोरिथ्म चलाएँ q और r शुरुवात से।

अंत में, सर्किट-संतुष्टि के लिए एक SNARK लागू किया जाता है C। इसे कहते हैं स्नैक बैकएंड. कुछ अत्यधिक संरचित समस्याओं जैसे के लिए मैट्रिक्स गुणन, संकल्प, तथा कई ग्राफ समस्याएं, ज्ञात SNARK मौजूद हैं जो इस फ्रंटएंड/बैकएंड प्रतिमान से बचते हैं और इस तरह एक बहुत तेज कहावत प्राप्त करते हैं। लेकिन इस पोस्ट का फोकस सामान्य प्रयोजन वाले SNARKs पर है।

जैसा कि हम देखेंगे, SNARK बैकएंड की प्रोवर लागत बढ़ती है Cकी आकार। रखना C छोटा चुनौतीपूर्ण हो सकता है, क्योंकि सर्किट एक अत्यंत सीमित प्रारूप है जिसमें एक संगणना व्यक्त की जाती है। वे शामिल हैं द्वार, द्वारा जुड़ा हुआ है तारों. प्रत्येक द्वार g कुछ मूल्यों को खिलाया जाता है और लागू होता है a बहुत उन मूल्यों के लिए सरल कार्य। परिणाम तब से निकलने वाले तारों के माध्यम से "डाउनस्ट्रीम" गेट्स में फीड किया जाता है g.

SNARK मापनीयता: वास्तव में कितना समय लगता है?

मुख्य प्रश्न यह है कि SNARK कहावत को केवल पुन: निष्पादित करने के सापेक्ष कितना अधिक समय लगता है ψ डेटा पर? उत्तर है कहावत उपरि SNARK के सापेक्ष प्रत्यक्ष गवाह जाँच. बाद की अभिव्यक्ति इस तथ्य को संदर्भित करती है कि, भोले प्रमाण में जिसमें P भेजता w सेवा मेरे V, V चेक के wक्रियान्वित करने की वैधता ψ उस पर. 

प्रोवर ओवरहेड को "फ्रंटएंड ओवरहेड" और "बैकएंड ओवरहेड" में तोड़ने में मददगार है। यदि सर्किट का मूल्यांकन C गेट-बाय-गेट है F दौड़ने से कई गुना महंगा ψ, तो हम कहते हैं कि फ्रंटएंड ओवरहेड है F. यदि बैकएंड प्रोवर को लागू कर रहे हैं C is B मूल्यांकन से कई गुना अधिक महंगा C गेट-बाय-गेट, तो हम कहते हैं कि बैकएंड ओवरहेड है B. कुल प्रोवर ओवरहेड है उत्पाद, F·B. यह गुणक उपरि पर्याप्त हो सकता है, भले ही F और B व्यक्तिगत रूप से विनम्र हैं। 

अभ्यास में, F और B दोनों लगभग 1000 या उससे अधिक हो सकते हैं। इसका मतलब है कि प्रत्यक्ष गवाह जाँच के सापेक्ष कुल प्रोवर ओवरहेड 1 मिलियन से 10 मिलियन या उससे अधिक हो सकता है। एक प्रोग्राम जो लैपटॉप पर सिर्फ एक सेकंड के लिए चलता है, आसानी से एक SNARK प्रोवर की ओर ले जा सकता है जिसमें दसियों या सैकड़ों दिनों की गणना समय (एकल-थ्रेडेड) की आवश्यकता होती है। सौभाग्य से, यह काम आम तौर पर अलग-अलग विस्तार (SNARK के आधार पर) के समानांतर है। 

संक्षेप में, यदि आप आज किसी एप्लिकेशन में SNARK का उपयोग करना चाहते हैं, तो तीन चीजों में से एक का सही होना आवश्यक है:

1. प्रत्यक्ष गवाह जाँच एक लैपटॉप पर एक सेकंड से भी कम समय लेता है।
2. प्रत्यक्ष गवाह जाँच एक सर्किट में प्रतिनिधित्व के लिए विशेष रूप से उत्तरदायी है, इसलिए फ्रंटएंड ओवरहेड छोटा है।
3. आप SNARK कहावत के समाप्त होने के लिए दिनों की प्रतीक्षा करने के लिए तैयार हैं, और/या विशाल समानांतर गणना संसाधनों के लिए भुगतान करने के लिए तैयार हैं।

Tवह इस पोस्ट के बाकी हिस्सों में बताता है कि फ्रंटएंड और बैकएंड ओवरहेड्स कहां से आते हैं, और मैं उन्हें अलग-अलग SNARKs के लिए कैसे अनुमान लगाता हूं। फिर हम सुधार की संभावनाओं की ओर मुड़ेंगे। 

फ्रंटएंड और बैकएंड को अलग करना

बैकएंड से फ्रंटएंड को पूरी तरह से अलग करना चुनौतीपूर्ण हो सकता है क्योंकि विभिन्न बैकएंड विभिन्न प्रकार के सर्किट का समर्थन करते हैं। इसलिए, बैकएंड के आधार पर फ्रंटएंड भिन्न हो सकते हैं जिसके साथ वे इंटरफ़ेस की अपेक्षा करते हैं।

SNARK बैकएंड आमतौर पर तथाकथित अंकगणितीय सर्किट का समर्थन करते हैं, जिसका अर्थ है कि सर्किट के इनपुट कुछ परिमित क्षेत्र के तत्व हैं, और यह कि सर्किट के द्वार दो क्षेत्र तत्वों के जोड़ और गुणा करते हैं। ये सर्किट मोटे तौर पर सीधी रेखा के कंप्यूटर प्रोग्राम (कोई शाखाएं, सशर्त बयान, और इसी तरह) से मेल खाते हैं जो प्रकृति में बीजगणितीय हैं - यानी, उनका आदिम डेटा प्रकार फ़ील्ड तत्व है। 

अधिकांश बैकएंड वास्तव में अंकगणितीय सर्किट के सामान्यीकरण का समर्थन करते हैं जिन्हें अक्सर रैंक -1 बाधा संतुष्टि (R1CS) उदाहरण कहा जाता है। के उल्लेखनीय अपवाद के साथ ग्रोथ16 और इसके पूर्ववर्ती, इन SNARKs को अन्य IR का भी समर्थन करने के लिए बनाया जा सकता है। उदाहरण के लिए, स्टार्कवेयर बीजीय मध्यवर्ती प्रतिनिधित्व (एआईआर) नामक किसी चीज़ का उपयोग करता है, जो कि एक धारणा के समान है जिसे कहा जाता है प्लोनकिश अंकगणित जिसे PlonK और अन्य बैकएंड द्वारा समर्थित किया जा सकता है। अधिक सामान्य IR का समर्थन करने के लिए कुछ बैकएंड की क्षमता उन IR का उत्पादन करने वाले फ़्रंटएंड के ऊपरी हिस्से को कम कर सकती है। 

बैकएंड उन परिमित क्षेत्रों के संदर्भ में भी भिन्न होते हैं जिनका वे मूल रूप से समर्थन करते हैं। मैं इस पर आगे अगले भाग में चर्चा करूंगा।

फ़्रंटएंड के लिए विभिन्न दृष्टिकोण

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

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

उदाहरण के लिए, StarkWare's काहिरा एक बहुत ही सीमित असेंबली भाषा है जिसमें असेंबली निर्देश मोटे तौर पर एक परिमित क्षेत्र में जोड़ और गुणा की अनुमति देता है, फ़ंक्शन कॉल करता है, और एक अपरिवर्तनीय (यानी, राइट-वन) मेमोरी को पढ़ता और लिखता है। काहिरा वीएम एक वॉन न्यूमैन वास्तुकला है, जिसका अर्थ है कि फ्रंटएंड द्वारा निर्मित सर्किट अनिवार्य रूप से काहिरा कार्यक्रम को सार्वजनिक इनपुट के रूप में लेते हैं और गवाह पर कार्यक्रम को "चलाते हैं"। काहिरा भाषा ट्यूरिंग कम्प्लीट है - अपने सीमित निर्देश सेट के बावजूद, यह अधिक मानक आर्किटेक्चर का अनुकरण कर सकती है, हालांकि ऐसा करना महंगा हो सकता है। काहिरा फ्रंटएंड काहिरा के कार्यक्रमों को क्रियान्वित करता है T आदिम निर्देश जिसे "डिग्री-" कहा जाता है2 के साथ आकाशवाणी T पंक्तियों और के बारे में 50 कॉलम।" क्या बिल्कुल इसका मतलब इस पद के लिए महत्वपूर्ण नहीं है, लेकिन जहां तक ​​SNARK नीतिवचन का संबंध है, यह प्रत्येक के लिए 50 और 100 द्वारों के बीच सर्किट से मेल खाता है T काहिरा सीपीयू के कदम। 

आरआईएससी जीरो काहिरा के लिए एक समान दृष्टिकोण लेता है, लेकिन आभासी मशीन तथाकथित होने के साथ आरआईएससी-वी वास्तुकला, एक समृद्ध सॉफ्टवेयर पारिस्थितिकी तंत्र के साथ एक ओपन-सोर्स आर्किटेक्चर जो लोकप्रियता में बढ़ रहा है। एक बहुत ही सरल निर्देश सेट के रूप में, एक कुशल SNARK फ्रंटएंड को डिजाइन करना जो इसका समर्थन करता है, अपेक्षाकृत ट्रैक्टेबल हो सकता है (कम से कम जटिल आर्किटेक्चर जैसे x86 या ARM के सापेक्ष)। मई तक, आरआईएससी जीरो कार्यक्रम बदल रहा है को क्रियान्वित T डिग्री -5 एआईआर के साथ आदिम आरआईएससी-वी निर्देश 3T पंक्तियाँ और 160 स्तंभ। यह कम से कम के साथ सर्किट से मेल खाता है 500 RISC-V CPU के प्रति चरण गेट। निकट भविष्य में और सुधार की उम्मीद है।

विभिन्न zkEVM प्रोजेक्ट्स (जैसे, zkSync 2.0, स्क्रॉल, पॉलीगॉन का zkEVM) वर्चुअल मशीन को एथेरियम वर्चुअल मशीन (duh) मानते हैं। प्रत्येक ईवीएम निर्देश को एक समान "गैजेट" (यानी, निर्देश को लागू करने वाला एक अनुकूलित सर्किट) में बदलने की प्रक्रिया सरल काहिरा और आरआईएससी-वी आर्किटेक्चर की तुलना में काफी अधिक शामिल है। इसके लिए और अन्य कारणों से, कुछ zkEVM प्रोजेक्ट्स ईवीएम निर्देश सेट को सीधे लागू नहीं कर रहे हैं बल्कि सर्किट में बदलने से पहले उच्च स्तरीय सॉलिडिटी प्रोग्राम को अन्य असेंबली भाषाओं में संकलित कर रहे हैं। इन परियोजनाओं के निष्पादन परिणाम लंबित हैं।

"सीपीयू एमुलेटर" प्रोजेक्ट जैसे आरआईएससी-वी और काहिरा एक एकल सर्किट का उत्पादन करते हैं जो संबंधित असेंबली भाषा में सभी कार्यक्रमों को संभाल सकता है। वैकल्पिक दृष्टिकोण "एएसआईसी-जैसे" हैं, जो विभिन्न कार्यक्रमों के लिए अलग-अलग सर्किट तैयार करते हैं। यह ASIC जैसा दृष्टिकोण कुछ कार्यक्रमों के लिए छोटे सर्किट उत्पन्न कर सकता है, खासकर जब असेंबली निर्देश जो प्रोग्राम प्रत्येक टाइमस्टेप पर निष्पादित करता है, प्रोग्राम के इनपुट पर निर्भर नहीं करता है। उदाहरण के लिए, यह संभावित रूप से सीधे-रेखा वाले कार्यक्रमों जैसे कि भोले मैट्रिक्स गुणन के लिए पूरी तरह से फ्रंटएंड ओवरहेड से बच सकता है। लेकिन ASIC का दृष्टिकोण भी अत्यधिक सीमित लगता है; जहां तक ​​​​मुझे पता है, यह ज्ञात नहीं है कि पूर्व निर्धारित पुनरावृत्ति सीमाओं के बिना लूप का समर्थन करने के लिए इसका उपयोग कैसे किया जाए। 

फ्रंटएंड ओवरहेड का अंतिम घटक इस तथ्य से आता है कि सभी SNARK सर्किट का उपयोग करते हैं जो परिमित क्षेत्रों में संचालित होते हैं। आपके लैपटॉप पर सीपीयू एक मशीन निर्देश के साथ दो पूर्णांकों को गुणा या जोड़ सकता है। यदि एक फ्रंटएंड एक बड़ी पर्याप्त विशेषता के क्षेत्र में एक सर्किट को आउटपुट करता है, तो यह अनिवार्य रूप से संबंधित फ़ील्ड ऑपरेशन के माध्यम से उस गुणन या जोड़ को अनुकरण कर सकता है। हालांकि, वास्तविक सीपीयू पर फील्ड ऑपरेशन को लागू करने के लिए आमतौर पर कई मशीन निर्देशों की आवश्यकता होती है (हालांकि कुछ आधुनिक प्रोसेसर के पास कुछ क्षेत्रों के लिए मूल समर्थन होता है)। 

कुछ SNARK बैकएंड दूसरों की तुलना में अधिक लचीले फ़ील्ड विकल्प सक्षम करते हैं। उदाहरण के लिए, यदि बैकएंड क्रिप्टोग्राफ़िक समूह का उपयोग करता है G, सर्किट के क्षेत्र को तत्वों की संख्या से मेल खाना चाहिए G, जो सीमित हो सकता है। इसके अलावा, सभी फ़ील्ड व्यावहारिक FFT एल्गोरिदम का समर्थन नहीं करते हैं। 

केवल एक कार्यान्वित SNARK है, हिम्मत हार जाना, जो मूल रूप से मनमाने (काफी बड़े) क्षेत्रों पर संगणना का समर्थन करता है। इसके साथ वंशज, अन्य SNARKs द्वारा समर्थित क्षेत्रों में भी इसका सबसे तेज़ ज्ञात ठोस प्रोवर प्रदर्शन है, लेकिन इसके प्रमाण वर्तमान में कई ब्लॉकचेन अनुप्रयोगों के लिए बहुत बड़े हैं। हाल ही में किया गया कार्य प्रूफ़ के आकार में सुधार करना चाहता है, लेकिन कहावत अस्वाभाविक रूप से धीमी है और वहाँ प्रकट होने के लिए बाधाओं व्यावहारिकता को।

कुछ परियोजनाओं ने विशेष रूप से तेज़ अंकगणित वाले क्षेत्रों में काम करना चुना है। उदाहरण के लिए, प्लोंकी2 और अन्य विशेषता वाले क्षेत्र का उपयोग करते हैं 2⁶⁴ - 2³² +1 क्योंकि इस क्षेत्र में अंकगणित को कम संरचित क्षेत्रों की तुलना में कई गुना तेजी से लागू किया जा सकता है। हालांकि, इस तरह की एक छोटी सी विशेषता का उपयोग करने से क्षेत्र संचालन के माध्यम से पूर्णांक अंकगणित का कुशलतापूर्वक प्रतिनिधित्व करने में चुनौतियों का सामना करना पड़ सकता है (उदाहरण के लिए, दो 32-बिट अहस्ताक्षरित पूर्णांक गुणा करने से फ़ील्ड विशेषता से अधिक परिणाम मिल सकता है)। 

 लेकिन कोई बात नहीं, सभी लोकप्रिय SNARKs के लिए आज 128 बिट सुरक्षा (सत्यापन लागत में उल्लेखनीय वृद्धि के बिना) प्राप्त करने के लिए, उन्हें 2 से बड़े आकार के क्षेत्र में काम करना होगा¹²⁸. जहां तक ​​​​मैं बता सकता हूं, इसका मतलब है कि प्रत्येक फील्ड ऑपरेशन के लिए कम से कम दस 64-बिट मशीन गुणन की आवश्यकता होगी, और काफी अधिक जोड़ और बिटवाइज ऑपरेशन। इसलिए, परिमित क्षेत्रों पर काम करने वाले सर्किट की आवश्यकता के कारण कम से कम परिमाण के अग्रभाग ओवरहेड के क्रम में कारक होना चाहिए। 

संक्षेप में, मौजूदा फ्रंटएंड जो वर्चुअल मशीन एब्स्ट्रैक्शन का उपयोग करते हैं, वर्चुअल मशीन के प्रति चरण 100x से 1000x गेट्स के साथ सर्किट का उत्पादन करते हैं, और संभवतः अधिक जटिल वर्चुअल मशीनों के लिए अधिक। उसके ऊपर, परिमित क्षेत्र अंकगणित आधुनिक प्रोसेसर पर समान निर्देशों की तुलना में कम से कम 10x धीमा है (संभावित अपवादों के साथ यदि प्रोसेसर में कुछ क्षेत्रों के लिए अंतर्निहित समर्थन है)। एक "एएसआईसी फ्रंटएंड दृष्टिकोण" इनमें से कुछ ओवरहेड्स को कम कर सकता है लेकिन वर्तमान में उन कार्यक्रमों के प्रकार में सीमित है जो इसका समर्थन कर सकते हैं।

बैकएंड बाधाएं क्या हैं?

सर्किट-संतुष्टि के लिए SNARKs को आमतौर पर एक सूचना-सैद्धांतिक रूप से सुरक्षित प्रोटोकॉल के संयोजन से डिज़ाइन किया जाता है, जिसे "एक" कहा जाता है।बहुपद IOP"एक क्रिप्टोग्राफ़िक प्रोटोकॉल के साथ जिसे" कहा जाता हैबहुपद प्रतिबद्धता योजना।" ज्यादातर मामलों में, नीतिवचन के लिए ठोस बाधा बहुपद प्रतिबद्धता योजना है। विशेष रूप से, इन SNARKs में एक या एक से अधिक बहुपदों के लिए क्रिप्टोग्राफ़िक रूप से प्रतिबद्ध कहावत है, जिनकी डिग्री (कम से कम) है |C|, सर्किट में फाटकों की संख्या C. 

बदले में, बहुपद प्रतिबद्धता योजना के भीतर ठोस अड़चन इस्तेमाल की गई योजना और सर्किट के आकार पर निर्भर करेगी। लेकिन यह हमेशा निम्नलिखित तीन कार्यों में से एक होगा: एफएफटी की गणना, क्रिप्टोग्राफ़िक समूह में घातांक, या मर्कल-हैशिंग. मर्कल-हैशिंग आमतौर पर केवल तभी एक अड़चन है जब सर्किट छोटा होता है, इसलिए हम इस पर आगे चर्चा नहीं करेंगे। 

असतत लॉग पर आधारित बहुपद प्रतिबद्धताएं

क्रिप्टोग्राफ़िक समूह में असतत लघुगणक समस्या की कठोरता के आधार पर बहुपद प्रतिबद्धताओं में G (केजेडजी, बुलेटप्रूफ, हलकी नाव, तथा हायरैक्स-प्रतिबद्ध), कहावत को गणना करनी होगी a पेडरसन वेक्टर प्रतिबद्धता बहुपद के गुणांकों के लिए। इसमें बहुपद की डिग्री के बराबर आकार का एक बहु-घातांक शामिल है। SNARKs में, यह डिग्री आमतौर पर आकार होती है |C| सर्किट की C.

भोलेपन से किया गया, आकार का एक बहु-घातांक |C| लगभग 1.5 . की आवश्यकता है·|C|·लॉग इन |G| ≈ 400·|C| समूह संचालन, जहां |G| समूह में तत्वों की संख्या को दर्शाता है G. हालांकि, एक दृष्टिकोण है, जिसे पिपेन्जर का एल्गोरिदम कहा जाता है, जो इसे मोटे तौर पर लॉग के कारक से कम कर सकता है |C|. बड़े सर्किट के लिए (कहते हैं, |C| मैं 225), यह लॉग |C| कारक ठोस रूप से 25 या अधिक हो सकता है, यानी बड़े सर्किट के लिए, हम उम्मीद करते हैं कि पेडर्सन वेक्टर प्रतिबद्धता 10 से थोड़ा अधिक के साथ गणना योग्य हो सकती है·|C| समूह संचालन। बदले में प्रत्येक समूह ऑपरेशन एक सीमित क्षेत्र संचालन की तुलना में लगभग 10x धीमा (एक बहुत ही मोटे बॉलपार्क के रूप में) होता है। इन बहुपद प्रतिबद्धताओं का उपयोग करने वाले SNARK उतने ही महंगे हैं P लगभग 100 . के रूप में·|C| क्षेत्र संचालन। 

दुर्भाग्य से, मौजूदा SNARK के ऊपर 100x कारक के शीर्ष पर अतिरिक्त ओवरहेड्स हैं। उदाहरण के लिए:

• संयमीके नीतिवचन, जो Hyrax बहुपद प्रतिबद्धता का उपयोग करता है, को करना है |C|^½ प्रत्येक आकार के कई बहु-घातांक |C|^½, पिपेन्जर के एल्गोरिथम से स्पीडअप को लगभग दो के कारक से कमजोर करना। 
• In ग्रोथ16, P एक जोड़ी-अनुकूल समूह पर काम करना चाहिए, जिसका संचालन आमतौर पर उन समूहों की तुलना में कम से कम 2x धीमा होता है जो अनुकूल नहीं हैं। P 3 के बजाय 1 बहु-घातांक भी करना चाहिए। संयुक्त, इसके परिणामस्वरूप कम से कम एक अतिरिक्त कारक -6 100 के सापेक्ष धीमा हो जाता है·|C| ऊपर अनुमान। 
• मार्लिन और प्लोनके युग्मों की भी आवश्यकता होती है, और उनके प्रोवर्स 3 से अधिक बहुपदों के लिए प्रतिबद्ध होते हैं। 
• किसी भी SNARK के लिए जो उपयोग करता है बुलेटप्रूफ (जैसे, Halo2, जो मोटे तौर पर PlonK है, लेकिन KZG बहुपद प्रतिबद्धताओं के बजाय बुलेटप्रूफ के साथ), नीतिवचन को प्रतिबद्धता योजना के "उद्घाटन" चरण के दौरान लघुगणकीय रूप से कई बहु-घातांकों की गणना करनी होती है, और यह बड़े पैमाने पर किसी भी पिपेंजर स्पीडअप को मिटा देता है। 

संक्षेप में, पेडर्सन वेक्टर प्रतिबद्धताओं का उपयोग करने वाले ज्ञात SNARKs का बैकएंड ओवरहेड कम से कम 200x और 1000x या अधिक तक होता है। 

अन्य बहुपद प्रतिबद्धताएं

अन्य बहुपद प्रतिबद्धताओं का उपयोग करने वाले SNARK के लिए (जैसे मुफ़्त और लिगेरो-कमिट), अड़चन यह है कि कहावत को बड़े एफएफटी करने की जरूरत है। उदाहरण के लिए, काहिरा द्वारा निर्मित डिग्री-2 एआईआर में (51 कॉलम और . के साथ) T पंक्तियाँ, काहिरा सीपीयू का एक प्रति चरण), स्टार्कवेयर का तैनात कहावत कम से कम 2 एफएफटी प्रति कॉलम, लंबाई के बीच करता है 16 ·T और 32 ·T. स्थिरांक 16 और 32 स्टार्कवेयर द्वारा निर्धारित एफआरआई के आंतरिक मापदंडों पर निर्भर करता है और इसे कम किया जा सकता है - लेकिन सत्यापन लागत में वृद्धि की कीमत पर। 

आशावादी रूप से, लंबाई 32 . का एक FFT·T लगभग 64 . लेता है·T·लॉग(32T) क्षेत्र गुणन। इसका मतलब यह है कि के अपेक्षाकृत छोटे मूल्यों के लिए भी T (जैसे, T ≥ 2²⁰), प्रति कॉलम क्षेत्र संचालन की संख्या कम से कम 64 . है·25·T= 1600·T. तो बैकएंड ओवरहेड कम से कम हजारों में प्रतीत होता है। इसके अलावा, यह संभव है कि बड़े एफएफटी क्षेत्र संचालन की तुलना में मेमोरी बैंडविड्थ द्वारा और भी अधिक बाधा उत्पन्न कर रहे हैं। 

कुछ संदर्भों में, बड़े एफएफटी करने वाले SNARK के बैकएंड ओवरहेड को प्रूफ एग्रीगेशन नामक तकनीक से कम किया जा सकता है। रोलअप के लिए, इसका मतलब यह होगा कि P (रोलअप सेवा) लेन-देन के एक बड़े बैच को 10 छोटे बैचों में विभाजित करता है। प्रत्येक छोटे बैच के लिए i, P एक SNARK सबूत पैदा करता है πi बैच की वैधता के बारे में। परंतु P इन सबूतों को एथेरियम पर पोस्ट नहीं करता है, क्योंकि इससे गैस की लागत में लगभग 10 गुना वृद्धि होगी। इसके बजाय, SNARK को फिर से लागू किया जाता है, इस बार एक प्रमाण प्रस्तुत करने के लिए π यह स्थापित करना P जानता है π₁ ...,π₁₀. यानी साक्षी है कि P जानने का दावा है दस प्रमाण₁,…, π₁₀, और प्रत्यक्ष गवाह जाँच प्रत्येक सबूत के लिए SNARK सत्यापन प्रक्रिया लागू करती है। यह एकल प्रमाण π इथेरियम पर पोस्ट किया गया है। 

बहुपद प्रतिबद्धताओं जैसे कि एफआरआई और लिगेरो-प्रतिबद्धता में, के बीच एक मजबूत तनाव है P समय और V लागत, आंतरिक मापदंडों के साथ एक घुंडी के रूप में कार्य करती है जो एक के लिए दूसरे का व्यापार कर सकती है। तब से π₁ ,…, π₁₀ एथेरियम पर पोस्ट नहीं किए गए हैं, नॉब को ट्यून किया जा सकता है इसलिए ये सबूत बड़े हैं, और उनका उत्पादन तेज है। केवल SNARK के अंतिम आवेदन में, कुल करने के लिए π₁ ,…, π₁₀ एक ही प्रमाण में π, क्या एक छोटा सा सबूत सुनिश्चित करने के लिए प्रतिबद्धता योजना को कॉन्फ़िगर करने की आवश्यकता है। 

स्टार्कवेयर प्रूफ एग्रीगेशन को तैनात करने की योजना बना रहा है सिर पर. यह भी इस तरह की परियोजनाओं का फोकस है प्लोंकी2.

SNARK मापनीयता के लिए अन्य अड़चनें क्या हैं?

इस पोस्ट ने कहावत पर ध्यान केंद्रित किया है पहर, लेकिन अन्य कहावत लागतें भी मापनीयता अड़चनें हो सकती हैं। उदाहरण के लिए, कई SNARK बैकएंड के लिए प्रोवर को प्रत्येक गेट के लिए कई फ़ील्ड तत्वों को स्टोर करने की आवश्यकता होती है C, और यह अंतरिक्ष लागत बहुत बड़ी हो सकती है। उदाहरण के लिए, एक कार्यक्रम ψ लैपटॉप पर एक सेकंड में चलने से आधुनिक प्रोसेसर पर शायद एक अरब आदिम ऑपरेशन हो सकते हैं। जैसा कि हमने देखा है, सामान्य तौर पर किसी को उम्मीद करनी चाहिए C इस तरह के ऑपरेशन के लिए 100 से अधिक फाटकों की आवश्यकता होती है। इसका मतलब है कि 100 बिलियन गेट्स, जो कि SNARK पर निर्भर करता है, का अर्थ दसियों या सैकड़ों टेराबाइट्स के लिए जगह हो सकता है। P. 

एक अन्य उदाहरण: कई लोकप्रिय SNARK (जैसे, प्लोनके, मार्लिन, ग्रोथ16) एक संरचित "सिद्ध कुंजी" उत्पन्न करने के लिए एक जटिल "विश्वसनीय सेटअप समारोह" की आवश्यकता होती है। जिसे प्रोवर द्वारा संग्रहित किया जाना चाहिए। जहाँ तक मुझे पता है, ऐसा सबसे बड़ा समारोह लगभग 2 . के साथ सर्किट का समर्थन करने में सक्षम एक सिद्ध कुंजी उत्पन्न की²⁸≈250 मिलियन गेट। साबित करने वाली कुंजी कई दर्जन गीगाबाइट आकार की है। 

ऐसे संदर्भों में जहां सबूत एकत्रीकरण संभव है, इन बाधाओं को काफी हद तक कम किया जा सकता है। 

आगे देख रहे हैं: अधिक स्केलेबल SNARKs के लिए संभावनाएं

दोनों फ़्रंटएंड और बैकएंड ओवरहेड्स परिमाण के तीन क्रम या अधिक हो सकते हैं। क्या हम निकट भविष्य में इनमें काफी कमी आने की उम्मीद कर सकते हैं? 

मुझे लगता है कि हम करेंगे - एक बिंदु तक। सबसे पहले, आज का सबसे तेज़ बैकएंड (जैसे, संयमी और हिम्मत हार जाना, और अन्य SNARKs जो संयोजन करते हैं सम-चेक प्रोटोकॉल बहुपद प्रतिबद्धताओं के साथ) के बड़े प्रमाण हैं - आमतौर पर सर्किट के आकार में वर्गमूल - इसलिए लोग वास्तव में उनका उपयोग नहीं कर रहे हैं। मुझे उम्मीद है कि निकट भविष्य में छोटे-सबूत SNARK के साथ गहराई-एक रचना के माध्यम से प्रूफ आकार और सत्यापनकर्ता समय को सार्थक रूप से कम किया जाएगा। सबूत एकत्रीकरण के समान, इसका मतलब है कि एक कहावत पहले एक SNARK सबूत उत्पन्न करेगी π "फास्ट-प्रोवर, लार्ज-प्रूफ" SNARK के साथ, लेकिन भेजें नहीं π सेवा मेरे V। बल्कि, P एक सबूत तैयार करने के लिए एक छोटे-सबूत SNARK का उपयोग करेगा π' कि यह जानता है π, और भेज दें π' सेवा मेरे V. यह SNARKs के बैकएंड ओवरहेड्स के परिमाण के क्रम को कम कर सकता है जो आज लोकप्रिय हैं। 

दूसरा, हार्डवेयर त्वरण मदद कर सकता है। एक बहुत ही सामान्य नियम यह है कि GPU CPU पर 10x स्पीडअप खरीद सकते हैं, और ASICs GPU पर 10x स्पीडअप खरीद सकते हैं। हालाँकि, इस मोर्चे पर मेरी तीन चिंताएँ हैं। सबसे पहले, बड़े एफएफटी को फील्ड ऑपरेशंस के बजाय मेमोरी बैंडविड्थ द्वारा बाधित किया जा सकता है, इसलिए एसएनएआरके जो ऐसे एफएफटी करते हैं, विशेष हार्डवेयर से सीमित स्पीडअप देख सकते हैं। दूसरा, जबकि यह पोस्ट बहुपद प्रतिबद्धता अड़चन पर केंद्रित है, कई SNARK को अन्य कार्यों को करने के लिए कहावत की आवश्यकता होती है जो केवल थोड़े कम खर्चीले होते हैं। तो बहुपद प्रतिबद्धता बाधा को तोड़ना (उदाहरण के लिए, बहु-घातांक को गति देना असतत-लॉग-आधारित SNARKs में) एक नया अड़चन ऑपरेशन छोड़ सकता है जो पुराने से बहुत बेहतर नहीं है। (उदाहरण के लिए, ग्रोथ16, मार्लिन, और प्लॉनके सहित SNARK में बहु-घातांक के अलावा कहावत FFTs भी है।) अंत में, सबसे कुशल SNARK की ओर ले जाने वाले क्षेत्र और अण्डाकार वक्र कुछ समय के लिए विकसित होते रह सकते हैं, और यह ASIC- आधारित प्रोवर त्वरण के लिए चुनौतियां पैदा कर सकता है।

फ्रंटएंड पर, हम तेजी से पा सकते हैं कि काहिरा, आरआईएससी ज़ीरो, जेडकेईवीएम, और अन्य जैसी परियोजनाओं का "सीपीयू एमुलेटर" दृष्टिकोण वास्तव में सीपीयू निर्देश सेट की जटिलता के साथ (प्रदर्शन के मामले में) काफी अच्छा है। वास्तव में, यह विभिन्न zkEVM परियोजनाओं की आशा है। इसका मतलब यह हो सकता है कि, जबकि फ़्रंटएंड ओवरहेड परिमाण के तीन क्रम या अधिक रहता है, फ़्रंटएंड VMs का समर्थन करने का प्रबंधन करता है जो वास्तविक CPU आर्किटेक्चर से तेजी से मेल खाता है। एक काउंटरवेलिंग चिंता यह है कि फ्रंटएंड जटिल हो सकते हैं और ऑडिट करना मुश्किल हो सकता है, क्योंकि हाथ से कोडित गैजेट तेजी से जटिल निर्देशों को लागू करते हैं। औपचारिक सत्यापन विधियां इस चिंता को दूर करने में महत्वपूर्ण भूमिका निभाएंगी। 

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

***

जस्टिन थेलेर is जॉर्ज टाउन विश्वविद्यालय में एक एसोसिएट प्रोफेसर। जॉर्ज टाउन में शामिल होने से पहले, उन्होंने न्यूयॉर्क में याहू लैब्स में एक रिसर्च साइंटिस्ट के रूप में दो साल बिताए, इससे पहले वे एक रिसर्च फेलो थे। कम्प्यूटिंग के सिद्धांत के लिए सिमंस संस्थान यूसी बर्कले में। 

***

आभार: मैं आभारी हूँ ऐलेना बर्गर इस पोस्ट के विषय को प्रस्तावित करने के लिए, और करने के लिए अरासु अरुण, जोसेफ बोनौ, तथा सैम रैग्सडेल अंतर्दृष्टिपूर्ण टिप्पणियों के लिए। मेरे संपादक को भी विशेष धन्यवाद, टिम सुलिवान.

***

यहां व्यक्त किए गए विचार व्यक्तिगत एएच कैपिटल मैनेजमेंट, एलएलसी ("a16z") कर्मियों के हैं जिन्हें उद्धृत किया गया है और यह a16z या इसके सहयोगियों के विचार नहीं हैं। यहां निहित कुछ जानकारी तृतीय-पक्ष स्रोतों से प्राप्त की गई है, जिसमें a16z द्वारा प्रबंधित निधियों की पोर्टफोलियो कंपनियों से भी शामिल है। जबकि विश्वसनीय माने जाने वाले स्रोतों से लिया गया, a16z ने स्वतंत्र रूप से ऐसी जानकारी को सत्यापित नहीं किया है और किसी भी स्थिति के लिए सूचना की स्थायी सटीकता या इसकी उपयुक्तता के बारे में कोई प्रतिनिधित्व नहीं करता है। इसके अतिरिक्त, इस सामग्री में तृतीय-पक्ष विज्ञापन शामिल हो सकते हैं; a16z ने ऐसे विज्ञापनों की समीक्षा नहीं की है और उनमें निहित किसी भी विज्ञापन सामग्री का समर्थन नहीं करता है।

यह सामग्री केवल सूचना के उद्देश्यों के लिए प्रदान की जाती है, और कानूनी, व्यापार, निवेश या कर सलाह के रूप में इस पर भरोसा नहीं किया जाना चाहिए। आपको उन मामलों में अपने स्वयं के सलाहकारों से परामर्श लेना चाहिए। किसी भी प्रतिभूति या डिजिटल संपत्ति के संदर्भ केवल दृष्टांत उद्देश्यों के लिए हैं, और निवेश सलाहकार सेवाएं प्रदान करने के लिए एक निवेश अनुशंसा या प्रस्ताव का गठन नहीं करते हैं। इसके अलावा, यह सामग्री किसी भी निवेशक या संभावित निवेशकों द्वारा उपयोग के लिए निर्देशित नहीं है और न ही इसका इरादा है, और किसी भी परिस्थिति में a16z द्वारा प्रबंधित किसी भी फंड में निवेश करने का निर्णय लेते समय इस पर भरोसा नहीं किया जा सकता है। (a16z फंड में निवेश करने की पेशकश केवल निजी प्लेसमेंट मेमोरेंडम, सब्सक्रिप्शन एग्रीमेंट, और ऐसे किसी भी फंड के अन्य प्रासंगिक दस्तावेज द्वारा की जाएगी और इसे पूरी तरह से पढ़ा जाना चाहिए।) किसी भी निवेश या पोर्टफोलियो कंपनियों का उल्लेख, संदर्भित, या वर्णित a16z द्वारा प्रबंधित वाहनों में सभी निवेशों के प्रतिनिधि नहीं हैं, और इस बात का कोई आश्वासन नहीं दिया जा सकता है कि निवेश लाभदायक होगा या भविष्य में किए गए अन्य निवेशों में समान विशेषताएं या परिणाम होंगे। आंद्रेसेन होरोविट्ज़ द्वारा प्रबंधित निधियों द्वारा किए गए निवेशों की सूची (उन निवेशों को छोड़कर जिनके लिए जारीकर्ता ने सार्वजनिक रूप से कारोबार की गई डिजिटल संपत्ति में सार्वजनिक रूप से और साथ ही अघोषित निवेशों का खुलासा करने के लिए a16z की अनुमति नहीं दी है) https://a16z.com/investments पर उपलब्ध है। /.

इसमें दिए गए चार्ट और ग्राफ़ केवल सूचना के उद्देश्यों के लिए हैं और निवेश का कोई भी निर्णय लेते समय उन पर भरोसा नहीं किया जाना चाहिए। पूर्व प्रदर्शन भविष्य के परिणाम का संकेत नहीं है। सामग्री केवल इंगित तिथि के अनुसार बोलती है। इन सामग्रियों में व्यक्त किए गए किसी भी अनुमान, अनुमान, पूर्वानुमान, लक्ष्य, संभावनाएं और/या राय बिना किसी सूचना के परिवर्तन के अधीन हैं और दूसरों द्वारा व्यक्त की गई राय के विपरीत या भिन्न हो सकते हैं। अतिरिक्त महत्वपूर्ण जानकारी के लिए कृपया https://a16z.com/disclosures देखें।