Groth16 समझाया गया

Last updated on Mar 16, 2026

Groth16 एल्गोरिथम एक prover को एक trusted setup में प्राप्त elliptic curve points पर एक quadratic arithmetic program की गणना करने में सक्षम बनाता है, जिसे एक verifier द्वारा जल्दी से चेक किया जा सकता है। यह जाली (forged) proofs को रोकने के लिए trusted setup से auxiliary elliptic curve points का उपयोग करता है।

पूर्व-अपेक्षाएं

यह लेख RareSkills Book of Zero Knowledge Proofs का एक अध्याय है। यह मानकर चला जाता है कि आप पिछले अध्यायों से परिचित हैं।

नोटेशन

हम $\mathbb{G}_1$ elliptic curve group से संबंधित एक elliptic curve point को $[x]_1$ के रूप में और $\mathbb{G}_2$ elliptic curve group से संबंधित एक elliptic curve point को $[x]_2$ के रूप में संदर्भित करते हैं। $[x]_1$ और $[x]_2$ के बीच एक pairing को $[x]_1\bullet[x]_2$ के रूप में दर्शाया जाता है और यह $\mathbb{G}_{12}$ में एक element उत्पन्न करता है। बोल्ड में दिए गए variables जैसे कि $\mathbf{a}$ वेक्टर्स (vectors) हैं, अपर केस बोल्ड अक्षर जैसे कि $\mathbf{L}$ मैट्रिसेस (matrices) हैं, और फील्ड एलिमेंट्स (field elements) (जिन्हें कभी-कभी अनौपचारिक रूप से “scalars” कहा जाता है) लोअर केस अक्षर हैं जैसे कि $d$ । सभी अंकगणितीय संचालन (arithmetic operations) एक finite field में होते हैं जिसकी characteristic elliptic curve group के order के बराबर होती है।

एक Arithmetic Circuit (ZK Circuit) दिए जाने पर, हम इसे एक Rank 1 Constraint System (R1CS) $\mathbf{L}\mathbf{a}\circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$ में परिवर्तित करते हैं, जिसमें मैट्रिसेस का आयाम (dimension) $n$ पंक्तियाँ (rows) और $m$ कॉलम (columns) होता है और एक witness vector $\mathbf{a}$ होता है। फिर, हम मैट्रिसेस के कॉलम को $x$ मानों $[1,2,...,n]$ पर $y$ मानों के रूप में इंटरपोलेट (interpolate) करके R1CS को Quadratic Arithmetic Program (QAP) में बदल सकते हैं। चूँकि $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ में $m$ कॉलम हैं, इसलिए हमारे पास $m$ पॉलीनोमियल्स (polynomials) के तीन सेट होंगे:

\begin{array}{} u_1(x),...,u_m(x) & m \text{ polynomials interpolated on the }m \text{ columns of } \mathbf{L}\\ v_1(x),...,v_m(x)& m \text{ polynomials interpolated on the }m \text{ columns of } \mathbf{R}\\ w_1(x),...,w_m(x)& m \text{ polynomials interpolated on the }m \text{ columns of } \mathbf{O}\\ \end{array}

इससे, हम एक Quadratic Arithmetic Program (QAP) का निर्माण कर सकते हैं:

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

जहाँ

t(x) = (x - 1)(x - 2)\dots(x - n)

और

h(x) = \frac{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) - \sum_{i=1}^m a_iw_i(x)}{t(x)}

यदि कोई तीसरा पक्ष powers of tau सेरेमनी (ceremony) के माध्यम से एक structured reference string (srs) बनाता है, तो prover QAP में sum terms ( $\sum a_if_i(x)$ terms) का मूल्यांकन एक छिपे हुए बिंदु $\tau$ पर कर सकता है। मान लें कि structured reference strings की गणना इस प्रकार की जाती है:

\begin{align*} [\Omega_{n-1}, \Omega_{n-2},\dots,\Omega_2,\Omega_1,G_1] &= [\tau^nG_1,\tau^{n-1}G_1,\dots,\tau G_1,G_1] && \text{srs for } G_1 \\ [\Theta_{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_1,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && \text{srs for } G_2\\ [\Upsilon_{n-2},\Upsilon_{n-3},\dots,\Upsilon_1,\Upsilon_0]&=[\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] && \text{srs for }h(\tau)t(\tau)\\ \end{align*}

हम $f(\tau)$ को inner product के माध्यम से एक structured reference string $[\tau^dG_1,...,\tau^2G_1,\tau G_1,G_1]$ पर मूल्यांकित (evaluated) एक पॉलीनोमियल के रूप में संदर्भित करते हैं:

f(\tau) = \sum_{i=1}^d f_i\Omega_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Omega_d,\Omega_{d-1},...,G_1]\rangle

या $\mathbb{G}_2$ srs के लिए:

f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Theta_d,\Theta_{d-1},...,G_2]\rangle

$f(\tau)$ उपरोक्त अभिव्यक्ति (expression) के लिए एक शॉर्टहैंड है, और यह एक elliptic curve point उत्पन्न करता है। इसका मतलब यह नहीं है कि prover $\tau$ को जानता है।

Prover निम्नलिखित गणना करके trusted setup पर अपने QAP का मूल्यांकन कर सकता है:

\begin{align*} [A]_1 &= \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau) \end{align*}

इस गणना के विवरण हमारे ट्यूटोरियल Quadratic Arithmetic Programs over Elliptic Curves में चर्चा किए गए हैं।

यदि QAP संतुलित (balanced) है, तो निम्नलिखित समीकरण लागू होता है:

[A]_1\bullet[B]_2 \stackrel{?}= [C]_1\bullet G_2

उद्देश्य (Motivation)

केवल $([A]_1, [B]_2, [C]_1)$ को प्रस्तुत करना यह साबित करने के लिए कोई ठोस तर्क नहीं है कि prover $\mathbf{a}$ को जानता है जिससे कि QAP संतुलित हो।

Prover आसानी से $a$ , $b$ , $c$ मानों का आविष्कार कर सकता है जहाँ $ab = c$ हो, और गणना कर सकता है

\begin{align*} [A]_1 &= aG_1\\ [B]_2 &= bG_2\\ [C]_1 &= cG_1 \end{align*}

और उन्हें verifier के सामने elliptic curve points $[A]_1$ , $[B]_2$ , $[C]_1$ के रूप में प्रस्तुत कर सकता है।

इस प्रकार, verifier को यह पता नहीं चल पाता है कि क्या $([A]_1, [B]_2, [C]_1)$ एक संतुष्ट (satisfied) QAP का परिणाम थे या नहीं।

हमें prover को ईमानदार रहने के लिए मजबूर करने की आवश्यकता है, वह भी बिना बहुत अधिक computational overhead जोड़े। इसे पूरा करने वाला पहला एल्गोरिथम “Pinocchio: Nearly Practical Verifiable Computation” था। यह इतना उपयोगी था कि ZCash ने अपने ब्लॉकचेन का पहला संस्करण इसी पर आधारित किया।

हालाँकि, Groth16 इसी काम को बहुत कम चरणों में पूरा करने में सक्षम था, और यह एल्गोरिथम आज भी व्यापक रूप से उपयोग में है, क्योंकि इसके बाद किसी भी एल्गोरिथम ने verification चरण के लिए इतना कुशल एल्गोरिथम तैयार नहीं किया है (यद्यपि अन्य एल्गोरिदम ने trusted setup को हटा दिया है या prover के लिए काम की मात्रा को काफी कम कर दिया है)।

2024 के लिए अपडेट: Cryptology में प्रकाशित एक पेपर जिसका काफी उत्साहपूर्ण शीर्षक “Polymath: Groth16 is not the limit” है, एक ऐसे एल्गोरिथम को प्रदर्शित करता है जिसमें Groth16 की तुलना में कम verifier चरणों की आवश्यकता होती है। हालाँकि, इस लेख को लिखे जाने के समय तक इस एल्गोरिथम का कोई ज्ञात कार्यान्वयन (implementation) नहीं है।

जालसाजी को रोकना भाग 1: $\alpha$ और $\beta$ का परिचय

एक “unsolveable” (न सुलझाया जा सकने वाला) verification फॉर्मूला

मान लीजिए कि हम अपने verification फॉर्मूले को निम्नलिखित में अपडेट करते हैं:

[A]_1 \bullet [B]_2 \stackrel{?}= [D]_{12} + [C]_1\bullet G_2

ध्यान दें कि हम सुविधा के लिए $G_{12}$ समूह के लिए additive notation का उपयोग कर रहे हैं।

यहाँ, $[D]_{12}$ , $G_{12}$ का एक element है और इसका एक अज्ञात discrete logarithm है।

अब हम यह दिखाते हैं कि $[D]_{12}$ के discrete logarithm को जाने बिना, एक verifier के लिए इस समीकरण का हल $([A]_1, [B]_2, [C]_1)$ प्रदान करना असंभव है।

अटैक 1: A और B की जालसाजी (Forging) करना और C प्राप्त करना

मान लीजिए कि prover $[A]₁$ और $[B]₂$ उत्पन्न करने के लिए बेतरतीब ढंग से (randomly) $a’$ और $b’$ का चयन करता है और एक ऐसा मान $[C’]$ प्राप्त करने का प्रयास करता है जो verifier के फॉर्मूले के अनुकूल हो।

[A]_1 \bullet [B]_2 \stackrel{?}= [D]_{12} + [C]_1\bullet G_2

$[A]₁$ और $[B]₂$ के discrete logarithms को जानते हुए, दुर्भावनापूर्ण (malicious) prover निम्नलिखित करके $[C’]$ को हल करने का प्रयास करता है:

\begin{align*}\underbrace{[A]_1\bullet [B]_2 - [D]_{12}}_{\chi_{12}}=[C']_1\bullet G_2\\ [\chi]_{12}=[C']_1\bullet G_2 \end{align*}

अंतिम पंक्ति में prover को $\chi_{12}$ के discrete log के लिए हल करने की आवश्यकता होती है, इसलिए वे $[C']_1$ के लिए एक वैध (valid) discrete log की गणना नहीं कर सकते हैं।

अटैक 2: C की जालसाजी (Forging) करना और A और B प्राप्त करना

यहाँ prover एक यादृच्छिक (random) बिंदु $c'$ चुनता है और $[C']_1$ की गणना करता है। चूँकि वे $c'$ को जानते हैं, इसलिए वे $a'$ और $b'$ के एक ऐसे अनुकूल संयोजन को खोजने का प्रयास कर सकते हैं जहाँ:

\begin{align*}[A]_1 \bullet [B]_2 &\stackrel{?}= \underbrace{[D]_{12} + [C]_1\bullet G_2}_{[\zeta]_{12}}\\ [A]_1 \bullet [B]_2 &\stackrel{?}=[\zeta]_{12} \end{align*}

इसके लिए prover को, $[\zeta]_{12}$ दिए जाने पर, एक ऐसा $[A]₁$ और $[B]₂$ खोजना होगा जो पेयर (pair) होने पर $[\zeta]_{12}$ उत्पन्न करे।

Discrete log समस्या के समान, हम अप्रमाणित क्रिप्टोग्राफ़िक मान्यताओं (cryptographic assumptions) पर भरोसा करते हैं कि यह गणना ( $\mathbb{G}_{12}$ में एक element को $\mathbb{G}_1$ और $\mathbb{G}_2$ element में डिकम्पोज़ (decompose) करना) अव्यावहारिक (infeasible) है। इस मामले में, यह मान्यता कि हम $[\zeta]_{12}$ को $[A]₁$ और $[B]₂$ में डिकम्पोज़ नहीं कर सकते, Bilinear Diffie-Hellman Assumption कहलाती है। इच्छुक पाठक Decisional Diffie-Hellman Assumption पर एक संबंधित चर्चा देख सकते हैं।

(अप्रमाणित का अर्थ अविश्वसनीय नहीं है। यदि आप इस मान्यता को सिद्ध करने या गलत साबित करने का कोई तरीका खोज सकते हैं, तो नाम और पैसा आपका इंतजार कर रहा है! व्यवहार में, $[\zeta]_{12}$ को $[A]₁$ और $[B]₂$ में डिकम्पोज़ करने का कोई ज्ञात तरीका नहीं है और इसे कम्प्यूटेशनल रूप से अव्यावहारिक (computationally infeasible) माना जाता है।)

$\alpha$ और $\beta$ का उपयोग कैसे किया जाता है

व्यवहार में, Groth16 $[D]_{12}$ टर्म का उपयोग नहीं करता है। इसके बजाय, trusted setup दो यादृच्छिक (random) scalars $\alpha$ और $\beta$ उत्पन्न करता है और निम्नलिखित रूप में गणना किए गए elliptic curve points $([\alpha]_1,[\beta]_2)$ प्रकाशित करता है:

\begin{align*} [α]_1 &= α G_1 \\ [β]_2 &= β G_2 \end{align*}

जिसे हमने $[D]_{12}$ के रूप में संदर्भित किया था, वह वास्तव में $[\alpha]_1 \bullet [\beta]_2$ है।

Proving और verification फ़ॉर्मूलों को फिर से प्राप्त करना (Re-deriving)

Verification फॉर्मूले $[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1\bullet[\beta]_2 + [C]_1\bullet G_2$ को “सुलझाने योग्य (solvable)” बनाने के लिए, हमें $\alpha$ और $\beta$ को शामिल करने के लिए अपने QAP फॉर्मूले को बदलना होगा।

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

अब विचार करें कि क्या होगा यदि हम समीकरण के बाईं ओर $\theta$ और $\eta$ टर्म्स को जोड़ दें:

\left(\boxed{\theta}+\sum_{i=1}^m a_iu_i(x)\right)\left(\boxed{\eta} +\sum_{i=1}^m a_iv_i(x)\right) =

=\boxed{\theta\eta} + \boxed{\theta}\sum_{i=1}^m a_iv_i(x) + \boxed{\eta}\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)

हम मूल QAP परिभाषा का उपयोग करके सबसे दाएँ टर्म्स को प्रतिस्थापित (substitute) कर सकते हैं:

=\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}

=\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}

अब हम निम्नलिखित परिभाषा के साथ एक “विस्तारित (expanded)” QAP पेश कर सकते हैं:

\left(\theta+\sum_{i=1}^m a_iu_i(x)\right)\left(\eta +\sum_{i=1}^m a_iv_i(x)\right) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

हम आगे क्या करने जा रहे हैं, इसकी एक झलक के रूप में: यदि हम $\theta$ को $[\alpha]_1$ से और $\eta$ को $[\beta]_2$ से बदल दें, तो हमें पहले का अपडेटेड verification फॉर्मूला मिलता है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2

जहाँ

\underbrace{\left([\alpha]_1+\sum_{i=1}^m a_iu_i(\tau)\right)}_{[A]_1}\underbrace{\left([\beta]_2 +\sum_{i=1}^m a_iv_i(\tau)\right)}_{[B]_2} =[\alpha]_1\bullet[\beta]_2 + \underbrace{\left(\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau)\right)}_{[C]_1} \bullet G_2

Prover $\tau$ , $\alpha$ , या $\beta$ को जाने बिना $[A]_1$ और $[B]_2$ की गणना कर सकता है। Structured reference string (powers of $\tau$ ) और elliptic curve points $([α]_1,[β]_2)$ दिए जाने पर, prover $[A]_1$ और $[B]_2$ की गणना इस प्रकार करता है:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ \end{align*}

यहाँ, $a_iu_i(\tau)$ का मतलब यह नहीं है कि prover $\tau$ को जानता है। Prover $i=1,2,\dots,m$ के लिए $u_i(\tau)$ की गणना करने हेतु structure reference string $[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1]$ का उपयोग कर रहा है, और $[B]_2$ के लिए $G_2$ srs का उपयोग कर रहा है।

हालाँकि, वर्तमान में $\alpha$ और $\beta$ को जाने बिना $[C]_1$ की गणना करना संभव नहीं है। Prover $[\alpha]_1$ को $\sum a_iu_i(\tau)$ के साथ और $[\beta]_2$ को $\sum a_iv_i(\tau)$ के साथ पेयर (pair) नहीं कर सकता क्योंकि इससे एक $\mathbb{G}_{12}$ बिंदु बन जाएगा, जबकि prover को $[C]_1$ के लिए एक $\mathbb{G}_1$ बिंदु की आवश्यकता होती है।

इसके बजाय, trusted setup को विस्तारित QAP के समस्याग्रस्त $C$ टर्म के लिए $m$ पॉलीनोमियल्स की पूर्व-गणना (precompute) करने की आवश्यकता होती है।

\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau)

कुछ बीजगणितीय हेरफेर (algebraic manipulation) के साथ, हम sum terms को एक एकल (single) sum में जोड़ते हैं:

=\sum_{i=1}^m (\alpha a_iv_i(\tau)+\beta a_iu_i(\tau) + a_iw_i(\tau))

और $a_i$ को फैक्टर आउट (factor out) करते हैं:

=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}

Trusted setup ऊपर दिए गए बॉक्स वाले टर्म से $\tau$ पर मूल्यांकित $m$ पॉलीनोमियल्स बना सकता है, और prover sum की गणना करने के लिए उसका उपयोग कर सकता है। सटीक विवरण अगले अनुभाग में दिखाए गए हैं।

अब तक के एल्गोरिथम का सारांश

Trusted setup के चरण

ठोस रूप में, trusted setup निम्नलिखित की गणना करता है:

\begin{align*} \alpha,\beta,\tau &\leftarrow \text{random scalars}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\\ [\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] &\leftarrow \text{srs for }h(\tau)t(\tau)\\ [\Psi_1]_1 &= (\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau))G_1\\ [\Psi_2]_1 &= (\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau))G_1\\ &\vdots\\ [\Psi_m]_1 &= (\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau))G_1\\ \end{align*}

Trusted setup प्रकाशित करता है:

([\alpha]_1,[\beta]_2,\text{srs}_{G_1},\text{srs}_{G_2},\text{srs for }h(\tau)t(\tau),[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)

Prover के चरण

Prover गणना करता है:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\ \end{align*}

ध्यान दें कि हमने “समस्याग्रस्त (problematic)” पॉलीनोमियल

=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}

(जिसमें $\alpha$ और $\beta$ शामिल थे) को निम्नलिखित से बदल दिया है:

\sum_{i=1}^m a_i[\Psi_i]_1

Verifier के चरण

Verifier गणना करता है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2

पब्लिक इनपुट्स (Public inputs) का समर्थन करना

अब तक का verifier फॉर्मूला पब्लिक इनपुट्स का समर्थन नहीं करता है, अर्थात् witness के एक हिस्से को सार्वजनिक (public) बनाना।

परंपरानुसार, witness के सार्वजनिक हिस्से वेक्टर $\mathbf{a}$ के पहले $\ell$ एलिमेंट्स होते हैं। उन एलिमेंट्स को सार्वजनिक बनाने के लिए, prover बस उन्हें उजागर (reveal) करता है:

[a_1, a_2, \dots, a_\ell]

Verifier को यह जांचने के लिए कि वे मान वास्तव में उपयोग किए गए थे, verifier को कुछ ऐसी गणनाएँ करनी होंगी जो मूल रूप से prover कर रहा था।

विशेष रूप से, prover गणना करता है:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\ \end{align*}

ध्यान दें कि केवल $[C]_1$ की गणना बदली है – prover केवल $a_i$ और $\Psi_i$ टर्म्स का उपयोग $\ell + 1$ से $m$ तक करता है।

Verifier sum के पहले $\ell$ टर्म्स की गणना करता है:

[X]_1=\sum_{i=1}^\ell a_i\Psi_i

और verification समीकरण है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet G_2 + [C]_1\bullet G_2

भाग 2: $\gamma$ या $\delta$ के साथ पब्लिक इनपुट्स को प्राइवेट इनपुट्स से अलग करना

$i\leq\ell$ के लिए $\Psi_i$ का दुरुपयोग करके proofs की जालसाजी करना

ऊपर दिए गए समीकरण में यह मान्यता है कि prover $[C]_1$ की गणना करने के लिए केवल $\Psi_{\ell+1}$ से $\Psi_m$ तक का उपयोग कर रहा है, लेकिन किसी बेईमान (dishonest) prover को $[C]_1$ की गणना करने के लिए $\Psi_1$ से $\Psi_{\ell}$ का उपयोग करने से कोई नहीं रोकता, जिससे एक जाली proof बन सकता है।

उदाहरण के लिए, यहाँ हमारा वर्तमान verification समीकरण है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + \sum_{i=1}^\ell a_i\Psi_i + [C]_1\bullet G_2

यदि हम C टर्म को अंदर से विस्तार (expand) करें, तो हमें निम्नलिखित मिलता है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + \sum_{i=1}^\ell a_i\Psi_i + \underbrace{\left(\sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\right)}_C \bullet G_2

उदाहरण के लिए मान लीजिए कि $\mathbf{a} = [1,2,3,4,5]$ और $\ell=3$ है। उस मामले में, witness का सार्वजनिक (public) हिस्सा $[1,2,3]$ है और निजी (private) हिस्सा $[4,5]$ है।

अंतिम समीकरण इस प्रकार होगा:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+3\Psi_3)\bullet G2 + \underbrace{(4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2

हालाँकि, prover को सार्वजनिक witness का एक वैध (valid) हिस्सा [1,2,0] बनाने और शून्य किए गए सार्वजनिक हिस्से को गणना के निजी हिस्से में ले जाने से कोई नहीं रोकता, जैसा कि नीचे दिया गया है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+\boxed{0\Psi_3})\bullet G2 + \underbrace{(\boxed{3\Psi_3}+4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2

ऊपर दिया गया समीकरण वैध (valid) है, लेकिन यह आवश्यक नहीं है कि witness मूल constraints को संतुष्ट करता हो।

इसलिए, हमें prover को $[C]_1$ की गणना के भाग के रूप में $\Psi_1$ से $\Psi_{\ell}$ का उपयोग करने से रोकना होगा।

$\gamma$ और/या $\delta$ का परिचय

उपरोक्त समस्या से बचने के लिए, trusted setup एक नया scalar : $\gamma$ या $\delta$ पेश करता है ताकि $\Psi_{\ell+1}$ से $\Psi_m$ तक को $\Psi_1$ से $\Psi_{\ell}$ से अलग करने के लिए बाध्य किया जा सके। ऐसा करने के लिए, trusted setup निजी टर्म्स (जो $[C]_1$ बनाते हैं) को $\delta$ से और/या सार्वजनिक टर्म्स (जो $[X]_1$ बनाते हैं, वह sum जिसकी verifier गणना करता है) को $\gamma$ से विभाजित (divide) करता है (अर्थात् modular inverse से गुणा करता है)।

चूँकि $h(\tau)t(\tau)$ टर्म $[C]_1$ में सन्निहित (embedded) है, इसलिए उन टर्म्स को भी $\delta$ से विभाजित करने की आवश्यकता है। यदि $\delta$ और $\gamma$ दोनों में से किसी एक का अज्ञात discrete logarithm है, तो पहले वर्णित जालसाजी के साथ-साथ अन्य संभावित तरीकों से बचा जा सकता है। इस विधि का उपयोग Zcash के Sapling-आधारित trusted setups में किया गया था जहाँ $\gamma$ को केवल $G_2$ पर छोड़ दिया जाता है और $\delta$ को अभी भी बाद के trusted setup चरणों में $G_2$ से एक यादृच्छिक (random) मान में अपडेट किया जाता है।

\begin{align*} \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{random scalars}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow \text{srs for }h(\tau)t(\tau)\\ \\ &\text{public portion of the witness}\\ [\Psi_1]_1 &= \frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\ [\Psi_2]_1 &= \frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{private portion of the witness}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+2}(\tau)}{\delta}G_1\\ &\vdots\\ [\Psi_{m}]_1 &= \frac{\alpha v_{m}(\tau) + \beta u_{m}(\tau) + w_{m}(\tau)}{\delta}G_1\\ \end{align*}

Trusted setup प्रकाशित करता है:

([\alpha]_1,[\beta]_2,[\gamma]_2,[\delta]_2,\text{srs}_{G_1},\text{srs}_{G_2},\text{srs for }h(\tau)t(\tau),[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)

Prover के चरण पहले के समान ही हैं:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\ \end{align*}

और verifier के चरणों में अब denominators को रद्द (cancel out) करने के लिए $[\gamma]_2$ और/या $[\delta]_2$ द्वारा pairing शामिल है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2

भाग 3: True zero knowledge लागू करना: r और s

हमारी योजना (scheme) अभी पूरी तरह से zero knowledge नहीं है। यदि कोई हमलावर हमारे witness vector का अनुमान लगाने में सक्षम है (जो कि संभव है यदि वैध (valid) इनपुट की केवल एक छोटी श्रृंखला हो, उदा. privileged addresses से गुप्त मतदान), तो वे अपने बनाए गए proof की तुलना मूल proof से करके सत्यापित कर सकते हैं कि उनका अनुमान सही है।

एक साधारण उदाहरण के रूप में, मान लें कि हमारा दावा है कि $x_1$ और $x_2$ दोनों या तो $0$ हैं या $1$ हैं। संबंधित arithmetic circuit इस प्रकार होगा:

\begin{align*} x_1 (x_1 - 1) = 0\\ x_2 (x_2 - 1) = 0 \end{align*}

हमलावर को यह पता लगाने के लिए केवल चार संयोजनों (combinations) का अनुमान लगाने की आवश्यकता है कि witness क्या है। अर्थात्, वे एक witness का अनुमान लगाते हैं, एक proof उत्पन्न करते हैं, और देखते हैं कि क्या उनका उत्तर मूल proof से मेल खाता है।

अनुमान लगाने से रोकने के लिए, prover को अपने proof में “salt” (यादच्छिक डेटा) मिलाना होगा, और salt को समायोजित करने के लिए verification समीकरण को संशोधित करने की आवश्यकता होगी।

Prover दो यादृच्छिक (random) field elements $r$ और $s$ को सैंपल करता है और उन्हें $A$ और $B$ में जोड़ता है ताकि witness का अनुमान न लगाया जा सके – एक हमलावर को witness और salts $r$ तथा $s$ दोनों का अनुमान लगाना होगा:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau) + r[\delta]_1\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau) + s[\delta]_2\\ [B]_1 &= [\beta]_1 + \sum_{i=1}^m a_iv_i(\tau) + s[\delta]_1\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau) + As+Br-rs[\delta]_1\\ \end{align*}

अंतिम verification फॉर्मूला प्राप्त करने के लिए, आइए अस्थायी रूप से इस बात को अनदेखा कर दें कि हम ग्रीक अक्षर वाले टर्म्स के discrete logs को नहीं जानते हैं, और verification समीकरण $AB$ के बाएँ पक्ष (left-hand-side) की गणना करें:

\underbrace{\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)}_A \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)}_B

टर्म्स का विस्तार (expanding) करने पर हमें मिलता है:

\alpha\beta+\alpha\sum_{i=1}^m a_iv_i(x)+\alpha s\delta + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)+\sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta

हम $C$ के लिए मूल टर्म्स का चयन कर सकते हैं:

\alpha\beta+\boxed{\alpha\sum_{i=1}^m a_iv_i(x)}+\alpha s\delta + \boxed{\beta\sum_{i=1}^m a_iu_i(x)} + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+\sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta

और नए टर्म्स को दाईं ओर छोड़ते हुए, उन्हें बाईं ओर मिला सकते हैं:

\alpha\beta + \boxed{\alpha\sum_{i=1}^m a_iv_i(x) + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+ \underline{\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta}

हम $As\delta$ और $Br\delta$ के संदर्भ में लिखने के लिए रेखांकित (underlined) टर्म्स को निम्नानुसार पुनर्व्यवस्थित करते हैं। हम $r\delta s\delta$ को $rs\delta^2 + rs\delta^2 - rs\delta^2$ में भी विभाजित (split) करते हैं:

=\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2 + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2 - rs\delta^2

$s$ और $r$ टर्म्स को एक साथ समूहित (Group) करें:

=\left(\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2\right) + \left(r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2\right) - rs\delta^2

$s\delta$ और $r\delta$ को फैक्टर आउट (Factor out) करें:

=\underbrace{\left(\alpha+ \sum_{i=1}^m a_iu_i(x) + r\delta\right)s\delta}_{As\delta} + \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)r\delta}_{Br\delta} - rs\delta^2

$A$ और $B$ को प्रतिस्थापित (Substitute) करें:

=As\delta + Br\delta - rs\delta^2

तो हमारा अंतिम समीकरण है:

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\sum_{i=1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2

अब हम इसे सार्वजनिक (public) और निजी (private) हिस्सों में विभाजित करते हैं:

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\underbrace{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}_\text{public} + \underbrace{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2}_\text{private}

हम चाहते हैं कि सार्वजनिक हिस्सा और निजी हिस्सा क्रमशः $\gamma$ और $\delta$ द्वारा अलग किए जाएं:

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As\delta + Br\delta - rs\delta^2

$\delta$ कुछ टर्म्स के लिए रद्द (cancel) हो जाता है:

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\left(\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\right)

अब हम इस समीकरण को verifier और prover के हिस्सों में अलग करते हैं। बॉक्स वाले टर्म्स verifier का हिस्सा हैं, और underbrace वाले टर्म्स वे हैं जो prover प्रदान करता है:

\underbrace{(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)}_{[A]_1}\underbrace{(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)}_{[B]_2}=\boxed{\alpha\beta}+\boxed{\gamma}\boxed{\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma}} + \boxed{\delta}\underbrace{\left(\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\right)}_{[C]_1}

Groth16 Proof एल्गोरिथम

अब हम शुरू से अंत तक (end-to-end) Groth16 एल्गोरिथम दिखाने के लिए तैयार हैं। Trusted setup और verification चरण पिछले उदाहरण से अपरिवर्तित रहते हैं जहाँ हमने $\gamma$ और $\delta$ को शामिल किया था। $r$ और $s$ को शामिल करने के लिए केवल prover की गणना बदलती है।

Trusted Setup

\begin{align*} \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{random scalars}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow \text{srs for }h(\tau)t(\tau)\\ \\ &\text{public portion of the witness}\\ [\Psi_1]_1 &= \frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\ [\Psi_2]_1 &= \frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{private portion of the witness}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+2}(\tau)}{\delta}G_1\\ &\vdots\\ [\Psi_{m}]_1 &= \frac{\alpha v_{m}(\tau) + \beta u_{m}(\tau) + w_{m}(\tau)}{\delta}G_1\\ \end{align*}

Trusted setup प्रकाशित करता है:

([\alpha]_1,[\beta]_1[\beta]_2,[\gamma]_2,[\delta]_1[\delta]_2,\text{srs}_{G_1},\text{srs}_{G_2},\text{srs for }h(\tau)t(\tau),[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)

Prover के चरण

Prover के पास एक witness $\mathbf{a}$ है और वह यादृच्छिक (random) scalars $r$ और $s$ उत्पन्न करता है।

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)+r[\delta]_1\\ [B]_1 &= [\beta]_1 + \sum_{i=1}^m a_iv_i(\tau)+s[\delta]_1\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)+s[\delta]_2\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)+[A]_1s+[B]_1r-rs[\delta]_1\\ \end{align*}

Prover $([A]_1, [B]_2, [C]_1, [a_1,...,a_\ell])$ प्रकाशित करता है।

Verifier के चरण

Verifier जांच करता है:

\begin{align*} [X]_1&=\sum_{i=1}^\ell a_i\Psi_i\\ [A]_1\bullet[B]_2 &\stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2 \end{align*}

Solidity में Groth16 का सत्यापन (Verifying)

इस बिंदु पर, आपके पास Solidity में proof verification कोड को समझने के लिए पर्याप्त ज्ञान है। यहाँ Tornado Cash का proof verification कोड दिया गया है। पाठक को source code को ध्यान से पढ़ने के लिए प्रोत्साहित किया जाता है। यदि पाठक Solidity असेंबली प्रोग्रामिंग के साथ सहज है, तो इस source code को समझना मुश्किल नहीं होगा क्योंकि वेरिएबल नाम इस लेख में दिए गए नामों के अनुरूप हैं।

Solana पर Groth16 के लिए लाइब्रेरी सपोर्ट भी उपलब्ध है।

ध्यान देने योग्य सुरक्षा मुद्दे (Security Issues)

Groth16 Malleable (परिवर्तनशील) है

Groth16 proofs malleable होते हैं। एक वैध (valid) proof

$([A]_1, [B]_2, [C]_1)$ दिए जाने पर, एक हमलावर $[A]_1$ और $[B]_2$ के बिंदु निषेध (point negation) की गणना कर सकता है और $([A']_1, [B']_2, [C]_1)$ के रूप में एक नया proof प्रस्तुत कर सकता है जहाँ $[A']_1 = \mathsf{neg}([A]_1)$ और $[B']_2 = \mathsf{neg}([B]_2)$ है।

यह देखने के लिए कि $[A]_1\bullet[B]_2 = [A']_1\bullet[B']_2$ कैसे होता है, निम्नलिखित कोड पर विचार करें:

from py_ecc.bn128 import G1, G2, multiply, neg, eq, pairing

# chosen arbitrarily
x = 10
y = 100
A = multiply(G1, x)
B = multiply(G2, y)

A_p = neg(A)
B_p = neg(B)

assert eq(pairing(B, A), pairing(B_p, A_p))

सहज रूप में (Intuitively), हमलावर $A$ और $B$ को $-1$ से गुणा कर रहा है, और pairing में $(-1)\times(-1)$ खुद को रद्द (cancel) कर देता है।

अतः, यदि verification फॉर्मूला इसे स्वीकार करता है:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2

तो यह इसे भी स्वीकार करेगा:

\mathsf{neg}([A]_1)\bullet\mathsf{neg}([B]_2) \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2

इस हमले से बचाव का वर्णन अगले अनुभाग में किया गया है।

आप इस लेख में इस हमले का एक proof of concept देख सकते हैं।

Prover एक ही witness के लिए असीमित संख्या में proofs बना सकता है

यह अपने आप में कोई “सुरक्षा मुद्दा” नहीं है – Zero Knowledge प्राप्त करने के लिए यह आवश्यक है। हालाँकि, एप्लिकेशन को यह ट्रैक करने के लिए एक तंत्र (mechanism) की आवश्यकता होती है कि कौन से तथ्य पहले ही साबित हो चुके हैं और इसे प्राप्त करने के लिए proof की विशिष्टता (uniqueness) पर निर्भर नहीं रहा जा सकता है।

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

इस तरह की सामग्री को निःशुल्क प्रकाशित करने की हमारी क्षमता हमारे छात्रों के निरंतर समर्थन पर निर्भर करती है। हमारे Zero Knowledge Bootcamp, Web3 Bootcamps के लिए साइन अप करने, या RareTalent पर नौकरी पाने पर विचार करें।

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