विटालिक ब्यूटिरिन के माध्यम से विटालिक ब्यूटिरिन ब्लॉग
यह इस पोस्ट का दर्पण है https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
यह लेखों की श्रृंखला का तीसरा भाग है जिसमें बताया गया है कि zk-SNARKs के पीछे की तकनीक कैसे काम करती है; पर पिछले लेख द्विघात अंकगणित कार्यक्रम और अंडाकार वक्र जोड़ी पढ़ना आवश्यक है, और यह लेख दोनों अवधारणाओं का ज्ञान ग्रहण करेगा। zk-SNARKs क्या हैं और वे क्या करते हैं, इसका बुनियादी ज्ञान भी माना जाता है। यह सभी देखें क्रिश्चियन रीटविस्नर का लेख यहाँ एक अन्य तकनीकी परिचय के लिए.
पिछले लेखों में, हमने द्विघात अंकगणित कार्यक्रम पेश किया था, जो बहुपद समीकरण के साथ किसी भी कम्प्यूटेशनल समस्या का प्रतिनिधित्व करने का एक तरीका है जो गणितीय चालबाज़ी के विभिन्न रूपों के लिए अधिक उत्तरदायी है। हमने अण्डाकार वक्र युग्म भी प्रस्तुत किए हैं, जो एक-तरफ़ा होमोमोर्फिक एन्क्रिप्शन के बहुत सीमित रूप की अनुमति देते हैं जो आपको समानता की जाँच करने की सुविधा देता है। अब, हम वहीं से शुरू करने जा रहे हैं जहां हमने छोड़ा था, और कुछ अन्य गणितीय युक्तियों के साथ अण्डाकार वक्र युग्मों का उपयोग करेंगे, ताकि एक कहावत यह साबित कर सके कि वे किसी विशेष क्यूएपी के लिए एक समाधान जानते हैं, इसके बारे में कुछ भी बताए बिना। वास्तविक समाधान.
यह लेख पर ध्यान केंद्रित करेगा पिनोच्चियो प्रोटोकॉल 2013 से पार्नो, जेंट्री, हॉवेल और रेकोवा द्वारा (अक्सर PGHR13 कहा जाता है); बुनियादी तंत्र में कुछ भिन्नताएँ हैं, इसलिए व्यवहार में लागू की गई zk-SNARK योजना थोड़ी अलग तरह से काम कर सकती है, लेकिन मूल सिद्धांत सामान्य तौर पर वही रहेंगे।
आरंभ करने के लिए, आइए हम उस तंत्र की सुरक्षा में अंतर्निहित प्रमुख क्रिप्टोग्राफ़िक धारणा पर जाएं जिसका हम उपयोग करने जा रहे हैं: *ज्ञान-का-प्रतिपादक* मान्यता।
मूल रूप से, यदि आपको अंक � और � की एक जोड़ी मिलती है, जहां �⋅�=�, और आपको एक बिंदु � मिलता है, तो �� के साथ आना संभव नहीं है जब तक � को किसी तरह से � से "व्युत्पन्न" न किया जाए। क्या आप जानते हैं कि। यह सहज रूप से स्पष्ट प्रतीत हो सकता है, लेकिन यह धारणा वास्तव में किसी अन्य धारणा (उदाहरण के लिए असतत लॉग कठोरता) से प्राप्त नहीं की जा सकती है जिसका उपयोग हम आमतौर पर अण्डाकार वक्र-आधारित प्रोटोकॉल की सुरक्षा साबित करते समय करते हैं, और इसलिए zk-SNARKs वास्तव में कुछ हद तक आराम करते हैं आम तौर पर अण्डाकार वक्र क्रिप्टोग्राफी की तुलना में कमजोर नींव - हालांकि यह अभी भी इतना मजबूत है कि अधिकांश क्रिप्टोग्राफर इससे सहमत हैं।
अब आइए जानें कि इसका उपयोग कैसे किया जा सकता है। माना कि बिंदुओं का एक जोड़ा (�,�) आसमान से गिरता है, जहां �⋅�=� है, लेकिन कोई नहीं जानता कि � का मान क्या है। अब, मान लीजिए कि मैं बिंदुओं (�,�) की एक जोड़ी लेकर आता हूं जहां �⋅�=�। फिर, KoE धारणा का तात्पर्य यह है कि अंकों की जोड़ी बनाने का एकमात्र तरीका मैं � और � लेकर, और दोनों को कुछ कारक r से गुणा कर सकता था। जिसे मैं व्यक्तिगत रूप से जानता हूं. यह भी ध्यान दें कि अण्डाकार वक्र युग्मों के जादू के लिए धन्यवाद, यह जाँच रहा है कि �=�⋅� वास्तव में जानने की आवश्यकता नहीं है � - इसके बजाय, आप बस यह जांच सकते हैं कि �(�,�)=�(�,�) है या नहीं।
आइए कुछ और दिलचस्प करें. मान लीजिए कि हमारे पास आसमान से गिरने वाले बिंदुओं के दस जोड़े हैं: (�1, �1),(2, 2)…(�10, 10)। सभी मामलों में, ��⋅�=��. मान लीजिए कि मैं आपको बिंदुओं (�,�) की एक जोड़ी प्रदान करता हूं जहां �⋅�=�। अब आप क्या जानते हैं? आप जानते हैं कि � कुछ रैखिक संयोजन �1⋅�1+�2⋅�2+…+�10⋅�10 है, जहां मैं गुणांक �1, 2… 10 जानता हूं। यानी, ऐसे बिंदुओं (�,�) के युग्म पर पहुंचने का एकमात्र तरीका �1, 2… 10 के कुछ गुणज लेना और उन्हें एक साथ जोड़ना है, और �1, 2… के साथ समान गणना करना है। �10.
ध्यान दें कि, �1...10 अंक के किसी भी विशिष्ट सेट को देखते हुए, जिसके लिए आप रैखिक संयोजनों की जांच करना चाहते हैं, आप वास्तव में यह जाने बिना कि � क्या है, और यदि आप जानते हैं कि क्या है, साथ में �1...10 अंक नहीं बना सकते हैं। � तो आप एक जोड़ी (�,�) बना सकते हैं जहां �⋅�=� जो कुछ भी आप चाहते हैं उसके लिए, एक रैखिक संयोजन बनाने की जहमत उठाए बिना। इसलिए, इसे कार्यान्वित करने के लिए यह बिल्कुल जरूरी है कि जो कोई भी उन बिंदुओं को बनाता है वह भरोसेमंद है और वास्तव में दस बिंदुओं को बनाने के बाद हटा देता है। यहीं से "विश्वसनीय सेटअप" की अवधारणा आती है.
याद रखें कि QAP का समाधान बहुपदों (�,�,�) का एक सेट है, जैसे कि �(�)⋅�(�)−�(�)=(�)⋅�(�), जहां:
- � बहुपदों के एक सेट का एक रैखिक संयोजन है {�1…��}
- � समान गुणांकों के साथ {�1...��} का रैखिक संयोजन है
- � समान गुणांकों के साथ {�1...��} का एक रैखिक संयोजन है
सेट {�1…��},{�1…��} और {�1…��} और बहुपद � समस्या कथन का हिस्सा हैं।
हालाँकि, अधिकांश वास्तविक दुनिया के मामलों में, �,� और � बहुत बड़े हैं; हैश फ़ंक्शन जैसी हजारों सर्किट गेट वाली किसी चीज़ के लिए, बहुपद (और रैखिक संयोजनों के लिए कारक) में कई हज़ार पद हो सकते हैं। इसलिए, सूचक द्वारा सीधे रैखिक संयोजन प्रदान करने के बजाय, हम उस युक्ति का उपयोग करने जा रहे हैं जिसे हमने ऊपर प्रस्तुत किया है ताकि सूक्त यह साबित कर सके कि वे कुछ प्रदान कर रहे हैं जो एक रैखिक संयोजन है, लेकिन कुछ और प्रकट किए बिना।
आपने देखा होगा कि उपरोक्त युक्ति अण्डाकार वक्र बिंदुओं पर काम करती है, बहुपदों पर नहीं। इसलिए, वास्तव में क्या होता है कि हम विश्वसनीय सेटअप में निम्नलिखित मान जोड़ते हैं:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
आप t को एक "गुप्त बिंदु" के रूप में सोच सकते हैं जिस पर बहुपद का मूल्यांकन किया जाता है। � एक "जनरेटर" है (कुछ यादृच्छिक अण्डाकार वक्र बिंदु जो प्रोटोकॉल के भाग के रूप में निर्दिष्ट है) और �, �, � और � "विषाक्त अपशिष्ट" हैं, संख्याएं जिन्हें निश्चित रूप से हर कीमत पर हटाया जाना चाहिए, अन्यथा जिसके पास ये हैं वह नकली सबूत बना सकेगा। अब, यदि कोई आपको अंकों का एक जोड़ा �, � इस तरह देता है कि �⋅��=� (अनुस्मारक: हमें इसे जांचने के लिए �� की आवश्यकता नहीं है, क्योंकि हम एक युग्म जांच कर सकते हैं), तो आप जानते हैं कि वे क्या हैं हम आपको � पर मूल्यांकित बहुपदों का एक रैखिक संयोजन दे रहे हैं।
इसलिए, अब तक कहावत को यह देना होगा:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
ध्यान दें कि इन मूल्यों की गणना करने के लिए कहावत को वास्तव में जानने की आवश्यकता नहीं है (और जानना भी नहीं चाहिए!) �,�,� या �; बल्कि, प्रोवर को इन मानों की गणना केवल उन बिंदुओं से करने में सक्षम होना चाहिए जिन्हें हम विश्वसनीय सेटअप में जोड़ रहे हैं।
अगला कदम यह सुनिश्चित करना है कि सभी तीन रैखिक संयोजनों में समान गुणांक हों। यह हम विश्वसनीय सेटअप में मानों का एक और सेट जोड़कर कर सकते हैं: �⋅(��(�)+��(�)+��(�))⋅�, जहां � एक अन्य संख्या है जिसे "विषाक्त" माना जाना चाहिए अपशिष्ट" और विश्वसनीय सेटअप पूरा होते ही त्याग दिया जाता है। फिर हम समान गुणांक वाले इन मानों के साथ एक रेखीय संयोजन बना सकते हैं, और यह सत्यापित करने के लिए ऊपर दी गई समान युग्मन चाल का उपयोग कर सकते हैं कि यह मान प्रदान किए गए �+�+� से मेल खाता है।
अंततः, हमें यह सिद्ध करना होगा कि �⋅�−�=�⋅�। हम इसे एक बार फिर युग्मन जांच के साथ करते हैं:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
जहाँ �ℎ=�⋅�(�). यदि इस समीकरण और �⋅�−�=�⋅� के बीच का संबंध आपके लिए समझ में नहीं आता है, तो वापस जाएं और पढ़ें जोड़ियों पर लेख.
हमने ऊपर देखा कि �,� और � को अण्डाकार वक्र बिंदुओं में कैसे परिवर्तित किया जाए; � सिर्फ जनरेटर है (यानी संख्या एक के बराबर अण्डाकार वक्र बिंदु)। हम विश्वसनीय सेटअप में �⋅�(�) जोड़ सकते हैं। � कठिन है; � सिर्फ एक बहुपद है, और प्रत्येक व्यक्तिगत QAP समाधान के लिए इसके गुणांक क्या होंगे, इसके बारे में हम समय से पहले बहुत कम भविष्यवाणी करते हैं। इसलिए, हमें विश्वसनीय सेटअप में और अधिक डेटा जोड़ने की आवश्यकता है; विशेष रूप से अनुक्रम:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4...
Zcash विश्वसनीय सेटअप में, यहाँ अनुक्रम लगभग 2 मिलियन तक चला जाता है; आपको यह सुनिश्चित करने के लिए � की कितनी शक्तियों की आवश्यकता है कि आप हमेशा �(�) की गणना करने में सक्षम होंगे, कम से कम उस विशिष्ट QAP उदाहरण के लिए जिसकी वे परवाह करते हैं। और इसके साथ ही, अंतिम जांच करने के लिए सत्यापनकर्ता सत्यापनकर्ता को सारी जानकारी प्रदान कर सकता है।
एक और विवरण है जिस पर हमें चर्चा करने की आवश्यकता है। अधिकांश समय हम केवल संक्षेप में यह सिद्ध नहीं करना चाहते कि किसी विशिष्ट समस्या का कोई समाधान मौजूद है; बल्कि, हम या तो कुछ विशिष्ट समाधान की शुद्धता को साबित करना चाहते हैं (उदाहरण के लिए यह साबित करना कि यदि आप "गाय" शब्द लेते हैं और SHA3 ने इसे एक लाख बार हैश किया है, तो अंतिम परिणाम 0x73064fe5 से शुरू होता है), या यदि आप प्रतिबंधित करते हैं तो एक समाधान मौजूद है कुछ पैरामीटर. उदाहरण के लिए, एक क्रिप्टोकरेंसी इन्स्टेन्शियेशन में जहां लेनदेन राशि और खाते की शेष राशि एन्क्रिप्ट की जाती है, आप यह साबित करना चाहते हैं कि आप कुछ डिक्रिप्शन कुंजी k जानते हैं जैसे:
decrypt(old_balance, k) >= decrypt(tx_value, k)decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
एन्क्रिप्टेड old_balance, tx_value और new_balance सार्वजनिक रूप से निर्दिष्ट किया जाना चाहिए, क्योंकि वे विशिष्ट मूल्य हैं जिन्हें हम उस विशेष समय पर सत्यापित करना चाहते हैं; केवल डिक्रिप्शन कुंजी छिपाई जानी चाहिए। "कस्टम सत्यापन कुंजी" बनाने के लिए प्रोटोकॉल में कुछ मामूली संशोधन की आवश्यकता होती है जो इनपुट पर कुछ विशिष्ट प्रतिबंध से मेल खाती है।
अब थोड़ा पीछे चलते हैं. सबसे पहले, यहां बेन के सौजन्य से सत्यापन एल्गोरिदम पूरी तरह से है सैसन, ट्रोमर, विर्ज़ा और चिएसा:
पहली पंक्ति पैरामीट्रिज़ेशन से संबंधित है; अनिवार्य रूप से, आप इसके कार्य को "कस्टम सत्यापन कुंजी" बनाने के रूप में सोच सकते हैं समस्या के विशिष्ट उदाहरण के लिए जहां कुछ तर्क निर्दिष्ट हैं। दूसरी पंक्ति �,� और � के लिए रैखिक संयोजन जांच है; तीसरी पंक्ति यह जांचती है कि रैखिक संयोजनों में समान गुणांक हैं, और चौथी पंक्ति उत्पाद जांच है �⋅�−�=�⋅�।
कुल मिलाकर, सत्यापन प्रक्रिया कुछ अण्डाकार वक्र गुणन (प्रत्येक "सार्वजनिक" इनपुट चर के लिए एक) और पांच युग्मन जांच है, जिनमें से एक में अतिरिक्त युग्मन गुणन शामिल है। प्रमाण में आठ अण्डाकार वक्र बिंदु शामिल हैं: �(�), �(�) और �(�) के लिए प्रत्येक बिंदु की एक जोड़ी, �⋅(�(�)+�(�)+�(�) के लिए एक बिंदु �� )), और �(�) के लिए एक बिंदु �ℎ। इनमें से सात बिंदु �वक्र पर हैं (प्रत्येक 32 बाइट्स, क्योंकि आप �निर्देशांक को एक बिट में संपीड़ित कर सकते हैं), और Zcash कार्यान्वयन में एक बिंदु (�) �2 (64) में मुड़े हुए वक्र पर है बाइट्स), इसलिए प्रमाण का कुल आकार ~288 बाइट्स है।
प्रमाण बनाने के दो कम्प्यूटेशनल रूप से सबसे कठिन भाग हैं:
- � प्राप्त करने के लिए (�⋅�−�)/� को विभाजित करना (एल्गोरिदम पर आधारित) फास्ट फूरियर ट्रांसफॉर्म इसे उप-द्विघात समय में कर सकते हैं, लेकिन यह अभी भी काफी कम्प्यूटेशनल रूप से गहन है)
- �(�), �(�), �(�) और �(�) मान और उनके संगत जोड़े बनाने के लिए अण्डाकार वक्र गुणन और जोड़ बनाना
प्रमाण बनाना इतना कठिन होने का मूल कारण यह तथ्य है कि मूल गणना में एक एकल बाइनरी लॉजिक गेट एक ऑपरेशन में बदल जाता है जिसे क्रिप्टोग्राफ़िक रूप से अण्डाकार वक्र संचालन के माध्यम से संसाधित किया जाना चाहिए यदि हम इससे शून्य-ज्ञान प्रमाण बना रहे हैं . यह तथ्य, तेज फूरियर परिवर्तनों की सुपरलाइनरिटी के साथ, इसका मतलब है कि Zcash लेनदेन के लिए प्रमाण निर्माण में ~20-40 सेकंड लगते हैं।
एक और बहुत ही महत्वपूर्ण प्रश्न यह है: क्या हम विश्वसनीय सेटअप को थोड़ा कम... कम भरोसेमंद बनाने का प्रयास कर सकते हैं? दुर्भाग्य से हम इसे पूरी तरह से भरोसेमंद नहीं बना सकते; KoE धारणा स्वयं यह जाने बिना कि � क्या है, स्वतंत्र जोड़े (��,��⋅�) बनाने से रोकती है। हालाँकि, हम -ऑफ़-मल्टीपार्टी कंप्यूटेशन का उपयोग करके सुरक्षा को काफी हद तक बढ़ा सकते हैं - यानी, पार्टियों के बीच विश्वसनीय सेटअप का निर्माण इस तरह से करें कि जब तक कम से कम एक प्रतिभागी ने अपना जहरीला कचरा हटा दिया हो तब तक आप ठीक हैं .
यह समझने के लिए कि आप यह कैसे करेंगे, यहां मौजूदा सेट (�,�⋅�,�⋅�2,�⋅�3...) लेने और अपने स्वयं के रहस्य को "जोड़ने" के लिए एक सरल एल्गोरिदम है ताकि आपको धोखा देने के लिए अपने रहस्य और पिछले रहस्य (या रहस्यों के पिछले सेट) दोनों की आवश्यकता हो।
आउटपुट सेट बस है:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3...
ध्यान दें कि आप केवल मूल सेट और एस को जानते हुए इस सेट का उत्पादन कर सकते हैं, और नया सेट पुराने सेट की तरह ही काम करता है, सिवाय इसके कि अब � के बजाय "विषाक्त अपशिष्ट" के रूप में उपयोग किया जाए। जब तक आप और वह व्यक्ति (या लोग) जिसने पिछला सेट बनाया था, दोनों आपके जहरीले कचरे को हटाने और बाद में मिलीभगत करने में असफल नहीं होते, सेट "सुरक्षित" है।
संपूर्ण विश्वसनीय सेटअप के लिए ऐसा करना थोड़ा कठिन है, क्योंकि इसमें कई मान शामिल हैं, और एल्गोरिदम को पार्टियों के बीच कई राउंड में करना पड़ता है। यह देखने के लिए सक्रिय अनुसंधान का एक क्षेत्र है कि क्या मल्टी-पार्टी गणना एल्गोरिदम को और अधिक सरल बनाया जा सकता है और इसे कम राउंड की आवश्यकता के लिए बनाया जा सकता है या अधिक समानांतर बनाया जा सकता है, क्योंकि जितना अधिक आप ऐसा कर सकते हैं उतना ही अधिक पार्टियों को विश्वसनीय सेटअप प्रक्रिया में शामिल करना संभव हो जाता है। . यह देखना उचित है कि छह प्रतिभागियों के बीच एक विश्वसनीय सेटअप, जो सभी एक-दूसरे को जानते हैं और एक-दूसरे के साथ काम करते हैं, कुछ लोगों को असहज कर सकता है, लेकिन हजारों प्रतिभागियों के साथ एक विश्वसनीय सेटअप बिना किसी भरोसे के लगभग अप्रभेद्य होगा - और यदि आप वास्तव में भ्रमित हैं , आप स्वयं इसमें शामिल हो सकते हैं और सेटअप प्रक्रिया में भाग ले सकते हैं, और सुनिश्चित करें कि आपने व्यक्तिगत रूप से अपना मान हटा दिया है।
सक्रिय अनुसंधान का एक अन्य क्षेत्र अन्य दृष्टिकोणों का उपयोग है जो समान लक्ष्य को प्राप्त करने के लिए युग्मों और समान विश्वसनीय सेटअप प्रतिमान का उपयोग नहीं करते हैं; देखना एली बेन सैसन की हालिया प्रस्तुति एक विकल्प के लिए (हालाँकि सावधान रहें, यह कम से कम गणितीय रूप से उतना ही जटिल है जितना SNARKs हैं!)
समीक्षा के लिए एरियल गैबिज़ोन और क्रिश्चियन रीटविस्नर को विशेष धन्यवाद।
- एसईओ संचालित सामग्री और पीआर वितरण। आज ही प्रवर्धित हो जाओ।
- प्लेटोडेटा.नेटवर्क वर्टिकल जेनरेटिव एआई। स्वयं को शक्तिवान बनाएं। यहां पहुंचें।
- प्लेटोआईस्ट्रीम। Web3 इंटेलिजेंस। ज्ञान प्रवर्धित। यहां पहुंचें।
- प्लेटोईएसजी. कार्बन, क्लीनटेक, ऊर्जा, पर्यावरण, सौर, कचरा प्रबंधन। यहां पहुंचें।
- प्लेटोहेल्थ। बायोटेक और क्लिनिकल परीक्षण इंटेलिजेंस। यहां पहुंचें।
- BlockOffsets. पर्यावरणीय ऑफसेट स्वामित्व का आधुनिकीकरण। यहां पहुंचें।
- स्रोत: प्लेटो डेटा इंटेलिजेंस।
