R1CS से एक Zero Knowledge Proof बनाना

Last updated on Oct 31, 2024

Rank 1 Constraint System के रूप में एन्कोड किए गए arithmetic circuit को देखते हुए, witness होने का एक ZK-proof बनाना संभव है, भले ही यह संक्षिप्त (succinct) न हो। यह लेख वर्णन करता है कि इसे कैसे पूरा किया जाए।

R1CS के लिए एक zero knowledge proof, witness vector को finite field elliptic curve points में परिवर्तित करके और प्रत्येक पंक्ति (row) के लिए Hadamard product को bilinear pairing से बदलकर पूरा किया जाता है।

एक Rank 1 Constraint System को देखते हुए जहाँ प्रत्येक मैट्रिक्स में $n$ पंक्तियाँ (rows) और $m$ कॉलम (columns) हैं, हम इसे इस प्रकार लिखते हैं:

\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}

जहाँ $\mathbf{L}$ , $\mathbf{R}$ , $\mathbf{O}$ ऐसे मैट्रिक्स हैं जिनमें $n$ पंक्तियाँ और $m$ कॉलम हैं, और $\mathbf{a}$ witness vector है (जिसमें arithmetic circuit के प्रत्येक सिग्नल के लिए एक satisfying assignment होता है)। वेक्टर $\mathbf{a}$ में 1 कॉलम और $m$ पंक्तियाँ हैं और $\circ$ element-wise multiplication (Hadamard product) है।

विस्तारित (expanded) रूप में, यह ऐसा दिखता है:

\left[ \begin{array}{ccc} l_{1,1} & \cdots & l_{1,m} \\ \vdots & \ddots & \vdots \\ l_{n,1} & \cdots & l_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right] \circ \left[ \begin{array}{ccc} r_{1,1} & \cdots & r_{1,m} \\ \vdots & \ddots & \vdots \\ r_{n,1} & \cdots & r_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right] = \left[ \begin{array}{ccc} o_{1,1} & \cdots & o_{1,m} \\ \vdots & \ddots & \vdots \\ o_{n,1} & \cdots & o_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right]

= \left[ \begin{array}{ccc} a_1 l_{1,1} + \cdots + a_m l_{1,m} \\ \vdots \\ a_1 l_{n,1} + \cdots + a_m l_{n,m} \end{array} \right] \circ \left[ \begin{array}{ccc} a_1 r_{1,1} + \cdots + a_m r_{1,m} \\ \vdots \\ a_1 r_{n,1} + \cdots + a_m r_{n,m} \end{array} \right] = \left[ \begin{array}{ccc} a_1 o_{1,1} + \cdots + a_m o_{1,m} \\ \vdots \\ a_1 o_{n,1} + \cdots + a_m o_{n,m} \end{array} \right]

= \left[ \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \end{array} \right] \circ \left[ \begin{array}{ccc} \sum_{i=1}^m a_i r_{1,i} \\ \sum_{i=1}^m a_i r_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i r_{n,i} \end{array} \right] = \left[ \begin{array}{ccc} \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i o_{n,i} \end{array} \right]

= \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \sum_{i=1}^m a_i r_{1,i} = \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \sum_{i=1}^m a_i r_{2,i} = \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \sum_{i=1}^m a_i r_{n,i} = \sum_{i=1}^m a_i o_{n,i} \end{array}

इस सेटअप में, हम एक verifier को साबित कर सकते हैं कि हमारे पास एक witness vector $\mathbf{a}$ है जो R1CS को संतुष्ट करता है, बस उन्हें वेक्टर $\mathbf{a}$ देकर। लेकिन इसमें स्पष्ट खामी यह है कि यह एक zero knowledge proof नहीं है!

R1CS के लिए Zero knowledge proof एल्गोरिदम

यदि हम witness vector की प्रत्येक प्रविष्टि (entry) को $G_1$ या $G_2$ से गुणा करके “एन्क्रिप्ट (encrypt)” करते हैं, तो भी गणित ठीक से काम करेगा!

इसे समझने के लिए, मान लें कि यदि हम यह मैट्रिक्स गुणा करते हैं:

\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4 \\ 5 \end{bmatrix} = \begin{bmatrix} 14 \\ 32 \end{bmatrix}

और साथ ही:

\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4G_1 \\ 5G_1 \end{bmatrix} = \begin{bmatrix} 14G_1 \\ 32G_1 \end{bmatrix}

दूसरे मैट्रिक्स गुणा में दो elliptic curve points के discrete logs का मान वही है जो पहले मैट्रिक्स गुणा के तत्वों (elements) का है।

दूसरे शब्दों में, हर बार जब हम कॉलम वेक्टर को स्क्वायर मैट्रिक्स की एक पंक्ति से गुणा करते हैं, तो हम दो elliptic curve point multiplications और एक elliptic curve addition करते हैं।

Elliptic curves के लिए नोटेशन (Notation)

हम कहते हैं कि $[aG_1]_1$ एक $\mathbb{G}_1$ elliptic curve point है जो फ़ील्ड एलिमेंट $a$ को $G_1$ से गुणा करके बनाया गया है। हम कहते हैं कि $[aG_2]_2$ एक $\mathbb{G}_2$ elliptic curve point है जो $a$ को जनरेटर $G_2$ से गुणा करके उत्पन्न किया गया है। Discrete log problem के कारण, हम $[aG_1]_1$ या $[aG_2]_2$ दिए जाने पर $a$ नहीं निकाल सकते। $A \in \mathbb{G}_1$ और $B \in \mathbb{G}_2$ point दिए जाने पर, हम कहते हैं कि दो points की pairing $A\bullet B$ है।

Prover के कदम (Steps)

आइए अपने $\mathbf{a}$ वेक्टर को एन्क्रिप्ट करें, जिसके लिए प्रत्येक प्रविष्टि को जनरेटर पॉइंट $G_1$ से गुणा करके elliptic curve point $[a_iG_1]_1$ तैयार किया जाएगा।

मैट्रिक्स $\mathbf{L}$ के लिए, हम निम्नलिखित कार्य कर रहे हैं:

\left[ \begin{array}{ccc} l_{1,1} & \cdots & l_{1,m} \\ \vdots & \ddots & \vdots \\ l_{n,1} & \cdots & l_{n,m} \end{array} \right] \left[ \begin{array}{c} [a_1 G_1]_1 \\ \vdots \\ [a_m G_1]_1 \end{array} \right] = \left[ \begin{array}{ccc} l_{1,1}[a_1 G_1]_1 & + \cdots + & l_{1,m}[a_m G_1]_1 \\ \vdots & \ddots & \vdots \\ l_{n,1}[a_1 G_1]_1 & + \cdots + & l_{n,m}[a_m G_1]_1 \end{array} \right] = \left[ \begin{array}{c} \sum_{i=1}^m l_{1,i}[a_i G_1]_1 \\ \sum_{i=1}^m l_{2,i}[a_i G_1]_1 \\ \vdots \\ \sum_{i=1}^m l_{n,i}[a_i G_1]_1 \end{array} \right]

Hadamard product के elliptic curve pairings की सूची बनने के अनुमान में, हम $\mathbf{a}$ वेक्टर को एन्क्रिप्ट करने के लिए $G_2$ points का भी उपयोग कर सकते हैं ताकि verifier pairing कर सके।

\left[ \begin{array}{ccc} r_{1,1} & \cdots & r_{1,m} \\ \vdots & \ddots & \vdots \\ r_{n,1} & \cdots & r_{n,m} \end{array} \right] \left[ \begin{array}{c} [a_1 G_2]_2 \\ \vdots \\ [a_m G_2]_2 \end{array} \right] = \left[ \begin{array}{ccc} r_{1,1}[a_1 G_2]_2 & + \cdots + & r_{1,m}[a_m G_2]_2 \\ \vdots & \ddots & \vdots \\ r_{n,1}[a_1 G_2]_2 & + \cdots + & r_{n,m}[a_m G_2]_2 \end{array} \right] = \left[ \begin{array}{c} \sum_{i=1}^m r_{1,i}[a_i G_2]_2 \\ \sum_{i=1}^m r_{2,i}[a_i G_2]_2 \\ \vdots \\ \sum_{i=1}^m r_{n,i}[a_i G_2]_2 \end{array} \right]

इस ऑपरेशन के बाद, हमारे पास $G_1$ में elliptic curve points का एक सिंगल कॉलम है जो $\mathbf{L}\mathbf{a}$ के गुणा से उत्पन्न हुआ है और $\mathbf{R}\mathbf{a}$ से $G_2$ points का एक सिंगल कॉलम है।

इसका सरल (naive) अगला कदम $\mathbf{a}$ वेक्टर को $G_{12}$ points के साथ एन्क्रिप्ट करना होगा ताकि verifier $\mathbf{L}\mathbf{a}$ के परिणाम को $\mathbf{R}\mathbf{a}$ के साथ pair कर सके यह देखने के लिए कि क्या यह $\mathbf{O}\mathbf{a}$ के बराबर है। लेकिन $G_{12}$ points बहुत बड़े होते हैं, इसलिए हम चाहेंगे कि verifier $G_1$ में $\mathbf{O}\mathbf{a}$ elliptic curve points को pair करे और फिर प्रत्येक प्रविष्टि को $G_2$ point के साथ pair करे। $G_2$ point के साथ pairing करना, एक तरह से “एक से गुणा करना” है लेकिन यह $G_1$ point को $G_{12}$ point में बदल देता है।

Prover फिर $G_1$ वेक्टर और $G_2$ वेक्टर verifier को सौंप देता है।

Verification का कदम

इस प्रकार, verification कदम बन जाता है:

\left[ \begin{array}{c} \sum_{i=1}^m l_{i,1}[a_i G_1]_1 \\ \sum_{i=1}^m l_{i,1}[a_i G_1]_1 \\ \vdots \\ \sum_{i=1}^m l_{i,1}[a_i G_1]_1 \end{array} \right] \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \left[ \begin{array}{c} \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \\ \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \\ \vdots \\ \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \end{array} \right] \stackrel{?}{=} \left[ \begin{array}{c} \sum_{i=1}^m o_{i,1}[a_i G_1]_1 \\ \sum_{i=1}^m o_{i,1}[a_i G_1]_1 \\ \vdots \\ \sum_{i=1}^m o_{i,1}[a_i G_1]_1 \end{array} \right] \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \left[ \begin{array}{c} G_2 \\ G_2 \\ \vdots \\ G_2 \end{array} \right]

= \begin{array}{c} \sum_{i=1}^m l_{i,1}[a_i G_1]_1\bullet \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \\ \sum_{i=1}^m l_{i,2}[a_i G_1]_1\bullet \sum_{i=1}^m r_{i,2}[a_i G_2]_2 \\ \vdots \\ \sum_{i=1}^m l_{i,n}[a_i G_1]_1\bullet \sum_{i=1}^m r_{i,n}[a_i G_2]_2 \end{array} \stackrel{?}{=} \begin{array}{c} \sum_{i=1}^m o_{i,1}[a_i G_1]_1\bullet G_2 \\ \sum_{i=1}^m o_{i,2}[a_i G_1]_1\bullet G_2 \\ \vdots \\ \sum_{i=1}^m o_{i,n}[a_i G_1]_1 \bullet G_2 \end{array}

$G_{12}$ तत्वों (elements) के उपरोक्त वेक्टर तभी और केवल तभी element-wise बराबर होंगे जब prover ने एक वैध (valid) witness प्रदान किया हो।

खैर, लगभग। हम अगले अनुभाग में उस पर चर्चा करेंगे।

सबसे पहले हमें एक महत्वपूर्ण इम्प्लीमेंटेशन विवरण का उल्लेख करने की आवश्यकता है:

Public inputs

यदि हमारा नॉलेज क्लेम “मुझे $x$ पता है ताकि $x³ + 5x + 5 = y$ जहाँ $y = 155$ ” है, तो हमारा witness vector संभवतः निम्नलिखित जैसा दिखेगा:

[1, y, x, v]

जहाँ $v = x^2$ है। इस स्थिति में, हमें $[1, y]$ को पब्लिक (public) करने की आवश्यकता है। इसे पूरा करने के लिए, हम बस witness के पहले दो तत्वों को एन्क्रिप्ट नहीं करते हैं। Verifier पब्लिक आउटपुट्स की जाँच करेगा, फिर पब्लिक इनपुट्स को $G_1$ या $G_2$ पॉइंट से गुणा करके एन्क्रिप्ट करेगा ताकि verification फॉर्मूला न बदले।

एक दुर्भावनापूर्ण (malicious) prover से निपटना।

चूँकि वेक्टर एन्क्रिप्टेड होते हैं, verifier तुरंत यह नहीं जान सकता कि क्या $\mathbb{G}₁$ points का वेक्टर उन्हीं मानों (values) को एन्क्रिप्ट करता है जिन्हें $\mathbb{G}₂$ points का वेक्टर करता है।

अर्थात, prover $\mathbf{a}G_1$ और $\mathbf{a}G_2$ प्रदान कर रहा है। चूँकि verifier को points के वेक्टर के discrete logs नहीं पता हैं, तो verifier को कैसे पता चलेगा कि $\mathbb{G}₁$ points के वेक्टर के discrete logs वही हैं जो $\mathbb{G}₂$ points के वेक्टर के हैं?

Verifier (उन्हें जाने बिना) discrete logs की समानता की जाँच कर सकता है, जिसके लिए वह points के दोनों वेक्टर्स को विपरीत (opposite) जनरेटर के वेक्टर के साथ pair करता है और यह देखता है कि परिणामी $\mathbb{G}_{12}$ points बराबर हैं या नहीं। विशेष रूप से:

\begin{bmatrix} a_1G_1 \\ a_2G_1 \\ \vdots \\ a_mG_1 \end{bmatrix} \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \begin{bmatrix} G_2 \\ G_2 \\ \vdots \\ G_2 \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} a_1G_2 \\ a_2G_2 \\ \vdots \\ a_mG_2 \end{bmatrix} \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \begin{bmatrix} G_1 \\ G_1 \\ \vdots \\ G_1 \end{bmatrix}

यह एल्गोरिदम मुख्य रूप से एकेडमिक (academic) है

यह एल्गोरिदम verifier के लिए बहुत अक्षम (inefficient) है। यदि R1CS में मैट्रिक्स बड़े हैं (और दिलचस्प एल्गोरिदम के लिए, वे होंगे), तो verifier को बहुत सारी pairings और elliptic curve additions करने होंगे। Elliptic curve addition काफी तेज़ है, लेकिन elliptic curve pairings धीमी हैं (और Ethereum पर बहुत अधिक गैस खर्च होती है)।

हालाँकि, यह देखना अच्छा है कि इस स्तर पर, zero knowledge proofs संभव हैं, और यदि आपको elliptic curve operations की अच्छी समझ है (और आप अपना मैट्रिक्स अंकगणित नहीं भूले हैं), तो उन्हें समझना मुश्किल नहीं है।

इस तकनीक को पूरी तरह से zero knowledge बनाना

जैसा कि यह अभी है, हमारे witness vector को डिक्रिप्ट (decrypt) नहीं किया जा सकता है, हालाँकि इसका अनुमान लगाया जा सकता है। यदि कोई हमलावर (कोई व्यक्ति जो अनएन्क्रिप्टेड witness को खोजने की कोशिश कर रहा है) witness का एक शिक्षित अनुमान (educated guess) लगाने के लिए कुछ सहायक (auxiliary) जानकारी का उपयोग करता है, तो वे अपने अनुमानित witness vector को elliptic curve point generators से गुणा करके और यह देखकर कि क्या परिणाम prover के witness vectors के समान है, अपने काम की जाँच कर सकते हैं।

हम Groth16 के अपने कवरेज में witness का अनुमान लगाने से बचाव करना सीखेंगे।

इसके अलावा, ध्यान रखें कि वास्तविक दुनिया में कोई भी वर्णित एल्गोरिदम नहीं करता है, क्योंकि यह बहुत अक्षम है। हालाँकि, यदि आप इसे लागू (implement) करते हैं, तो यह आपको सार्थक elliptic curve arithmetic को लागू करने का अभ्यास करने और एक कार्यात्मक एंड-टू-एंड (लगभग) zero knowledge proof बनाने में मदद करेगा।

आप Obront द्वारा वर्णित एल्गोरिदम का एक उदाहरण इम्प्लीमेंटेशन इस रेपो (repo) में देख सकते हैं।

RareSkills के साथ और जानें

यह सामग्री हमारे Zero Knowledge Course से है।

मूल रूप से 26 अगस्त, 2023 को प्रकाशित