Bulletproofs एक zero knowledge inner product argument हैं, जो एक prover को verifier को यह समझाने में सक्षम बनाते हैं कि उन्होंने एक inner product की सही गणना की है। अर्थात्, prover के पास दो vectors $\mathbf{a} = [a_1, a_2, \dots, a_n]$ और $\mathbf{b} = [b_1, b_2, \dots, b_n]$ हैं और उन्होंने $v = \langle\mathbf{a},\mathbf{b}\rangle=a_1b_1+a_2b_2 + \dots +a_nb_n$ की गणना की है। Prover इच्छानुसार vectors या inner product के परिणाम को छिपा सकता है या प्रकट कर सकता है, लेकिन फिर भी वह verifier को विश्वास दिला सकता है कि उसने गणना ईमानदारी से की है।

Verifier को vectors $\mathbf{a}$, $\mathbf{b}$, और scalar $v$ प्राप्त नहीं होते हैं, बल्कि इन मानों के commitments प्राप्त होते हैं। बहुत मोटे तौर पर, कोई यह सोच सकता है कि verifier को एक “hash” $h$ प्राप्त होता है जहाँ $h = \mathsf{hash}([a_1, a_2, \dots, a_n],[b_1, b_2, \dots, b_n],v)$, फिर एक proof प्राप्त होता है (जिसे हम $\pi$ कहते हैं) कि hash में वास्तव में दो vectors और उनका inner product शामिल है। दूसरे शब्दों में, verifier को $(h, \pi)$ प्राप्त होता है और वह आश्वस्त हो जाता है कि prover ने hashed मानों पर inner product ऑपरेशन सही ढंग से किया है – लेकिन hash के “contents” के बारे में कुछ नहीं जान पाता है।

Bulletproof के verification हिस्से को execute करने के दौरान, verifier hash का पुनर्निर्माण करेगा और इस प्रकार आश्वस्त हो जाएगा कि prover ने inner product का मूल्यांकन वैसा ही किया है जैसा कि दावा किया गया है।

निस्संदेह, input को जाने बिना एक पारंपरिक hash का पुनर्निर्माण करना संभव नहीं है, इसलिए Bulletproofs एक विशेष प्रकार के hash का उपयोग करते हैं जिसे “Pedersen Commitment” कहा जाता है, जो इस ट्यूटोरियल के पहले अध्याय का विषय है। Pedersen Commitments elliptic curves पर आधारित एक विशेष प्रकार का “hash” हैं; Pedersen Commitments का पुनर्निर्माण मूल input को जाने बिना किया जा सकता है।

कुछ इंजीनियर vectors को $a_1b_1+a_2b_2 + \dots +a_nb_n$ के तरीके से संयोजित करने के ऑपरेशन को “dot product” के रूप में पहचानते हैं। तकनीकी रूप से, एक dot product एक Cartesian plane में vectors पर होने वाले ऑपरेशन को संदर्भित करता है, लेकिन inner product मनमाने vectors के लिए ऑपरेशन को संदर्भित करता है। इसलिए, हम इस ऑपरेशन को inner product के रूप में संदर्भित करेंगे। हम एक vector को दर्शाने के लिए $\mathbf{a}$ जैसे बोल्ड अक्षरों का उपयोग करते हैं, एक finite field तत्व को दर्शाने के लिए $v$ जैसे छोटे अक्षरों का उपयोग करते हैं (मोटे तौर पर, modular arithmetic में एक “scalar”), और दो vectors के inner product को दर्शाने के लिए एंगल्ड ब्रैकेट $\langle\mathbf{a},\mathbf{b}\rangle$ का उपयोग करते हैं, जिसका परिणाम हमेशा एक finite field तत्व होता है।

सामान्य रूप से zero knowledge साबित करने के लिए, prover को यह दिखाना होगा कि वे एक arithmetic circuit के लिए एक ऐसा assignment (एक witness) जानते हैं जो circuit के constraints को संतुष्ट करता है। हालाँकि, SNARKs, विशेष रूप से Groth16 मनमाने circuits को स्वीकार नहीं करते हैं – circuits एक विशेष प्रारूप, Rank One Constraint system में होने चाहिए। वहाँ से, R1CS को Lagrange interpolation और polynomial division का उपयोग करके एक Quadratic Arithmetic Program (QAP) में बदल दिया जाता है।

Interpolating polynomials और polynomial division का अतिरिक्त overhead, prover के लिए काम को काफी बढ़ा देता है।

दूसरी ओर, Bulletproofs हमें QAP के बिना सीधे R1CS के लिए एक proof बनाने की अनुमति देते हैं। विचार करें कि बाईं ओर निम्नलिखित matrix ऑपरेशन और दाईं ओर inner product गणनाएँ समतुल्य हैं:

दूसरे शब्दों में, एक $n \times m$ matrix को $m$ dimensional vector से गुणा करना $n$ inner products की गणना करने के समान है। इसलिए यदि हम सीधे यह साबित कर सकते हैं कि एक inner product की गणना सही ढंग से की गई थी, तो हमें एक Quadratic Arithmetic Program बनाने के अतिरिक्त चरणों की आवश्यकता नहीं है।

इसके अलावा, Bulletproofs pairings का उपयोग नहीं करते हैं (केवल बुनियादी elliptic curve addition) और इन्हें trusted setup की आवश्यकता नहीं होती है।

Bulletproofs की कमियाँ

Multiplications की संख्या के संदर्भ में proof का आकार logarithmic होता है, ZK-SNARK proof के विपरीत जो कि constant size का होता है।

Bulletproofs की प्राथमिक कमी यह है कि verifier का runtime, circuit के आकार के सन्दर्भ में linear होता है। ऐसा इसलिए है क्योंकि जो काम trusted setup द्वारा पूरा किया गया होता, उसे अब verifier द्वारा किया जाना होता है।

Arithmetic Circuits के बिना ZK

Inner products का एक बड़ा फायदा यह है कि वे कुछ समस्याओं को “सीधे” मॉडल कर सकते हैं – अर्थात – उन्हें एक arithmetic circuit की आवश्यकता नहीं होती है।

उदाहरण के लिए, यह साबित करने के लिए कि एक संख्या $v$, $2^n$ से कम है, यह दिखाकर किया जा सकता है कि $v$ का binary representation $\mathbf{b}$ है, और $\mathbf{b}$ तथा vector $[1,2,4,8,...,2^{n-1}]$ का inner product $v$ है। इसका सीधा सा अर्थ है कि $v < 2^n$। उदाहरण के लिए, यदि 2 की घातों (powers of 2) का vector $[1,2,4,8,16,32,64,128]$ है, तो हम जानते हैं कि $v$ निश्चित रूप से 256 से कम होना चाहिए, उसी कारण से कि एक uint8 255 से बड़े मानों को धारण नहीं कर सकता। लेकिन चूँकि $\mathbf{b}$ छिपा हुआ है, हम $v$ का वास्तविक मान नहीं जानते हैं। इसे एक range proof कहा जाता है क्योंकि हम जानते हैं कि $v$, $[0,255]$ की सीमा (range) में है, बिना उसका वास्तविक मान जाने।

यदि इसके बजाय हम range proof के लिए एक arithmetic circuit बनाते, तो यह काफी बड़ा computational overhead उत्पन्न करता।

NP-Completeness से परिचित पाठकों के लिए, Subset Sum समस्या को सीधे एक inner product argument के साथ मॉडल किया जा सकता है। NP में किसी भी समस्या को एक Subset Sum इंस्टेंस में घटाया (reduced) जा सकता है और इसके समाधान को एक inner product argument से साबित किया जा सकता है। कुछ मामलों में, वह reduction एक arithmetic circuit की तुलना में अधिक कुशल (efficient) हो सकता है।

व्यवहार में Bulletproofs

प्राइवेसी ब्लॉकचेन Monero ऊपर वर्णित range proof का उपयोग यह सुनिश्चित करने के लिए करता है कि ट्रांजैक्शन के input में negative मान न हों (अर्थात् finite field में एक overflow)। ZCash एक PLONKish circuit का उपयोग करते हुए SNARK polynomial commitment के प्रतिस्थापन के रूप में Bulletproofs का उपयोग करता है।

Bulletproofs का linear runtime उन्हें Ethereum मेननेट पर smart contracts में उपयोग के लिए अनुपयुक्त बनाता है। हालाँकि, उन प्रोटोकॉल्स के लिए जिन्हें एक छोटी समस्या के तेज़ proof generation और verification की आवश्यकता होती है – जैसे कि एक range proof, Bulletproofs को हराना मुश्किल है।

Bulletproofs पर RareSkills ZK Book

हमारा Bulletproofs का वॉकथ्रू मूल Bulletproofs paper पर आधारित है। यह पेपर बहुत अच्छी तरह से व्यवस्थित है, लेकिन यह अत्यंत गहन (dense) है क्योंकि यह पेशेवर क्रिप्टोग्राफी शोधकर्ताओं (cryptography researchers) को लक्षित करता है और यह मानकर चलता है कि पाठक के पास अच्छी खासी background knowledge है। Bulletproof ट्यूटोरियल्स का हमारा संग्रह काफी हद तक इस पेपर का एक ऐसे संस्करण में अनुवाद है जिसे सीनियर web3 डेवलपर्स समझ सकें। हम उन पूर्वापेक्षाओं (prerequisites) के लिए पूरे ट्यूटोरियल बनाते हैं जिनके बारे में पेपर परोक्ष रूप से मान लेता है कि वे पाठक को पता होंगे।

हमेशा की तरह, हम एल्गोरिथम का एक सहज मानसिक मॉडल (intuitive mental model) प्रदान करने का प्रयास करते हैं, न कि केवल एल्गोरिथम द्वारा उठाए गए कदमों को दोहराते हैं। जहाँ उपयुक्त होता है, स्पष्टीकरण को अधिक प्रभावी बनाने के लिए हम गणितीय एनिमेशन (mathematical animations) शामिल करते हैं। हर कीमत पर, हम अत्यधिक सरलीकरण (oversimplification) से बचते हैं ताकि आपको यह पूरी समझ (intuition) मिल सके कि एल्गोरिथम का प्रत्येक चरण क्या पूरा करता है।

इस कार्य को पढ़ना

हम यह मानकर चलते हैं कि पाठक ने हमारी ZK Book के पहले नौ अध्यायों को पढ़ और समझ लिया है। Groth16 या अन्य ZK एल्गोरिदम से परिचित होने की अपेक्षा नहीं की जाती है।

हम इसके साथ “fill in the blank” Python कोडिंग अभ्यास शामिल करते हैं ताकि आप जो सीखते हैं उसका अभ्यास कर सकें।

सही पूर्वापेक्षाओं (prerequisites) वाले पाठक के लिए, थोड़े से अनुशासन के साथ, दो सप्ताह तक प्रतिदिन तीन घंटे से अधिक समय न निकालकर, खरोंच से (from scratch) Bulletproofs एल्गोरिथम को कोड करना संभव है। Bulletproofs का यह विवेचन अत्यधिक मदद (hand-holding) के बिना ऐसा करने की रूपरेखा प्रदान करता है।

Bulletproofs एक अर्थ में SNARKs से “सरल” हैं, इसलिए वे ZK के क्षेत्र को समझने में आत्मविश्वास बनाने का एक शानदार तरीका हैं।

विषय सूची

अध्याय 2 Pedersen Commitment का परिचय देता है, जो Bulletproofs का मूलभूत आधार (foundational building block) है। अध्याय 3-5 दिखाते हैं कि zero knowledge के साथ एक inner product proof कैसे पूरा किया जाए, लेकिन succinctness के बिना (proof का आकार $\mathcal{O}(n)$ है जहाँ $n$ vectors का आकार है)। अध्याय 6-7 दिखाते हैं कि बिना ZK के inner product के ज्ञान को कैसे साबित किया जाए, लेकिन $n$ में एक logarithmic proof आकार के साथ। अध्याय 8 मुख्य Bulletproofs एल्गोरिथम दिखाता है। अध्याय 9 और 10 अध्याय 11 के लिए पूर्वापेक्षाएँ (prerequisites) हैं जहाँ हम दिखाते हैं कि एक arithmetic circuit के उपयोग के बिना एक range proof कैसे बनाया जाए।

1. Bulletproofs का परिचय (यह अध्याय)
2. Pedersen Commitments Pedersen Commitments वही हैं जिन्हें हमने इस लेख की शुरुआत में “hash” कहा था। हालाँकि, वे पारंपरिक hash functions की तुलना में अधिक composable हैं, क्योंकि वे additively homomorphic हैं। अर्थात्, हम $A$ के लिए 2 और $B$ के लिए 5 commit कर सकते हैं और $A + B$ के लिए 7 को “प्रकट” (reveal) कर सकते हैं।
3. Polynomial Commitments via Pedersen Commitments एक polynomial के गुणांकों (coefficients) के Pedersen commitments बनाकर, हम यह साबित कर सकते हैं कि हमने 1) एक polynomial के लिए commit किया है और 2) मूल polynomial को प्रकट किए बिना इसका सही ढंग से मूल्यांकन किया है।
4. Zero Knowledge Multiplication हम यह सत्यापित कर सकते हैं कि दो polynomials को 1) उन्हें commit करके, 2) उनका मूल्यांकन करके, और 3) यह जाँच कर कि पहले दो के मूल्यांकन (evaluations) गुणा होकर तीसरा बनाते हैं, सही ढंग से गुणा किया गया था। Polynomials को (zero knowledge के साथ) एक साथ गुणा करने की एक योजना होने से, हमें मुफ्त में scalar multiplication भी मिल जाता है।
5. Inner Product Arguments चूँकि अब हमारे पास multiplication के लिए zero knowledge proofs करने का तंत्र है, तो inner product के लिए zero knowledge proofs का समर्थन करने के लिए यह केवल एक छोटा सा बदलाव है। विशेष रूप से, हम scalar coefficient polynomials को “vector polynomials” में बदलते हैं और गुणांकों (coefficients) के लिए scalar commitments के बजाय vector commitments करते हैं। हम “vector polynomial inner product” के एक ऑपरेशन को भी परिभाषित करते हैं जो हमें inner product argument को पूरा करने में सक्षम बनाता है। जबकि यह zero knowledge है, यह argument अभी तक succinct नहीं है।
6. Succinct Inner Product Arguments आम तौर पर, यह साबित करने के लिए कि आपने $n$ लंबाई के दो vectors के साथ एक inner product की सही गणना की है, आपको $2n$ तत्वों (अर्थात् दोनों vectors) को भेजने की आवश्यकता होगी। यह अध्याय केवल $n$ तत्वों को भेजने की एक चतुर तरकीब (clever trick) दिखाता है।
7. Logarithmic-Sized Proofs of Knowledge for Inner Products यह अध्याय अध्याय 6 में वर्णित एल्गोरिदम का पुनरावर्ती (recursively) उपयोग यह साबित करने के लिए करता है कि हमने $n$ आकार के दो vectors के inner product की सही गणना की है, जिसमें proof का आकार केवल $\mathcal{O}(n)$ डेटा है।
8. Bulletproof ZKP: the algorithm end-to-end हम Bulletproof तैयार करने के लिए अध्याय 5 में zero knowledge inner product argument को अध्याय 7 में succint inner product के साथ मिलाते हैं। इस बिंदु पर, पिछले अभ्यासों को मिलाकर एल्गोरिदम को स्वयं कोड करने के लिए आपके पास पर्याप्त ज्ञान है।
9. Inner Product Algebra यह अध्याय inner products को एक साथ जोड़ने के लिए विभिन्न बीजीय सर्वसमिकाओं (algebraic identities) का परिचय देता है और साबित करता है, जो Bulletproof range proof सीखते समय उपयोगी होंगी।
10. Random Linear Combinations दो (या अधिक) inner products के लिए दो (या अधिक) proofs बनाने के बजाय, हम random linear combination तरकीब का उपयोग करके कई inner products के लिए एक ही proof बना सकते हैं।
11. Range Proofs एक range proof इस बात का proof है कि एक committed मान एक निश्चित सीमा (range) में स्थित है। Bulletproofs समस्या को arithmetize किए बिना इसे सीधे पूरा कर सकते हैं। Bulletproofs range proofs साबित करते हैं कि एक संख्या को 2 की घातों (powers of 2) के एक vector $[1,2,4,...,2^{n-1}]$ और एक binary vector के inner product के रूप में एन्कोड किया जा सकता है, लेकिन वे यह प्रकट नहीं करते हैं कि कौन से bits वन (one) हैं या ज़ीरो (zero)।

हम अनुशंसा करते हैं कि आप this Bulletproofs ZK repo को fork करें और पढ़ते समय अभ्यास करें, ताकि आप जो सीखते हैं उसका तुरंत अभ्यास कर सकें।

आभार

Henry de Valence, Cathie Yun और Oleg Andreev द्वारा documentation of the Rust Bulletproofs crate के उत्कृष्ट प्रलेखन (documentation) ने वहाँ मददगार संकेत प्रदान किए जहाँ पेपर स्पष्ट नहीं था और हम कभी-कभी उनके नोटेशन (notation) का उपयोग करते हैं, जो कुछ मामलों में मूल पेपर में नोटेशन की तुलना में अधिक सहज है। पाठक Bulletproofs पर एक वैकल्पिक दृष्टिकोण के रूप में उस संसाधन को उपयोगी पा सकते हैं।