Trusted Setup पर Quadratic Arithmetic Program का मूल्यांकन

Last updated on Jan 5, 2026

एक trusted setup पर Quadratic Arithmetic Program (QAP) को evaluate करने से एक prover को यह साबित करने की अनुमति मिलती है कि QAP संतुष्ट (satisfied) है, वह भी witness को उजागर किए बिना और एक constant sized proof का उपयोग करते हुए।

विशेष रूप से, QAP polynomials का मूल्यांकन एक अज्ञात बिंदु (unknown point) $\tau$ पर किया जाता है। QAP समीकरण (equation)

\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)

संतुलित (balanced) होगा यदि vector $\mathbf{a}$ समीकरण को संतुष्ट करता है, और अन्यथा इसके असंतुलित (unbalanced) होने की अत्यधिक संभावना (overwhelming probability) होगी।

यहाँ दिखाई गई योजना (scheme) एक सुरक्षित ZK Proof नहीं है, लेकिन यह यह दिखाने की दिशा में एक कदम (stepping stone) है कि Groth16 कैसे काम करता है।

एक Concrete Example

इसे थोड़ा कम abstract बनाने के लिए, मान लेते हैं कि Rank 1 Constraint System (R1CS) के matrices $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ में 3 rows और 4 columns हैं।

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

चूँकि हमारे पास 3 rows हैं, इसका मतलब है कि हमारे interpolating polynomials की degree 2 होगी। क्योंकि हमारे पास 4 columns हैं, प्रत्येक matrix से 4 polynomials प्राप्त होंगे (कुल मिलाकर 12 polynomials)।

हमारा QAP होगा

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

Notation और Preliminaries

हम groups $\mathbb{G}_1$ और $\mathbb{G}_2$ में generators elliptic curve points को क्रमशः $G_1$ और $G_2$ के रूप में संदर्भित करते हैं। $\mathbb{G}_1$ में एक element को $[X]_1$ के रूप में दर्शाया जाता है। $\mathbb{G}_2$ में एक element को $[X]_2$ के रूप में दर्शाया जाता है। जहाँ किसी list में indices को संदर्भित करने वाले subscripts के साथ अस्पष्टता (ambiguity) हो सकती है, वहाँ हम कहते हैं कि $X \in \mathbb{G}_1$ या $X \in \mathbb{G}_2$ । दो बिंदुओं के बीच एक elliptic curve pairing को $[X]_1 \bullet [Y]_2$ के रूप में दर्शाया जाता है।

मान लीजिए कि $\mathbf{L}_{(*,j)}$ , $\mathbf{L}$ का $j$ -th column है। हमारे उदाहरण में, rows $(1,2,3)$ होंगी और columns $(1,2,3,4)$ होंगे। मान लीजिए कि $\mathcal{L}(\mathbf{L}_{(*,j)})$ वह polynomial है जो $\mathbf{L}$ के $j$ -th column पर Lagrange interpolation चलाने से प्राप्त होता है, जिसमें $x$ values $(1,2,3)$ का उपयोग किया जाता है और $y$ values, $j$ -th column की values होती हैं।

चूँकि हमारे पास 4 columns हैं, हम $\mathbf{L}$ से चार polynomials प्राप्त करते हैं

\begin{align*} u_1(x) = \mathcal{L}(\mathbf{L}_{(*,1)}) =u_{12}x^2 + u_{11}x+u_{10}\\ u_2(x) = \mathcal{L}(\mathbf{L}_{(*,2)}) =u_{22}x^2 + u_{21}x+u_{20}\\ u_3(x) = \mathcal{L}(\mathbf{L}_{(*,3)}) =u_{32}x^2 + u_{31}x+u_{30}\\ u_4(x) = \mathcal{L}(\mathbf{L}_{(*,4)}) =u_{42}x^2 + u_{41}x+u_{40}\\ \end{align*}

$\mathbf{R}$ से चार polynomials

\begin{align*} v_1(x) = \mathcal{L}(\mathbf{R}_{(*,1)}) =v_{12}x^2 + v_{11}x+v_{10}\\ v_2(x) = \mathcal{L}(\mathbf{R}_{(*,2)}) =v_{22}x^2 + v_{21}x+v_{20}\\ v_3(x) = \mathcal{L}(\mathbf{R}_{(*,3)}) =v_{32}x^2 + v_{31}x+v_{30}\\ v_4(x) = \mathcal{L}(\mathbf{R}_{(*,4)}) =v_{42}x^2 + v_{41}x+v_{40}\\ \end{align*}

और $\mathbf{O}$ से चार polynomials

\begin{align*} w_1(x) = \mathcal{L}(\mathbf{O}_{(*,1)}) =w_{12}x^2 + w_{11}x+w_{10}\\ w_2(x) = \mathcal{L}(\mathbf{O}_{(*,2)}) =w_{22}x^2 + w_{21}x+w_{20}\\ w_3(x) = \mathcal{L}(\mathbf{O}_{(*,3)}) =w_{32}x^2 + w_{31}x+w_{30}\\ w_4(x) = \mathcal{L}(\mathbf{O}_{(*,4)}) =w_{42}x^2 + w_{41}x+w_{40}\\ \end{align*}

एक polynomial $p_{ij}$ का अर्थ है $i$ -th polynomial और $j$ -th coefficient (power)। उदाहरण के लिए, $j=2$ का अर्थ है $x^2$ से जुड़ा coefficient।

हमारे उदाहरण के लिए QAP है

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

जहाँ $t(x) = (x - 1)(x - 2)(x - 3)$ और $h(x)$ है

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

R1CS के आकार के संबंध में QAP में polynomials की degrees

सामान्य स्थिति (general case) में polynomials की degrees के बारे में कुछ अवलोकन (observations):

$u(x)$ और $v(x)$ की degree अधिकतम $n - 1$ तक हो सकती है क्योंकि वे $n$ points को interpolate करते हैं, जहाँ $n$ , R1CS में rows की संख्या है।
$w(x)$ की degree कम से कम 0 हो सकती है यदि polynomials का योग $\sum_{i=0}^m a_iw_i(x)$ जुड़कर शून्य (zero) polynomial बन जाता है, अर्थात्, coefficients एक-दूसरे को योगात्मक (additively) रूप से cancel कर देते हैं।
परिभाषा के अनुसार $t(x)$ की degree $n$ होती है।
polynomials को गुणा करने पर उनकी degrees आपस में जुड़ जाती हैं, और polynomials को विभाजित करने पर उनकी degrees घट जाती हैं।

इसलिए, h(x) अधिकतम $n - 2$ होगा क्योंकि

\underbrace{n - 1}_{ \deg{u(x)}} + \underbrace{n - 1}_{\deg{v(x)}} - \underbrace{n}_{\deg{t(x)}} = n - 2

Terms का विस्तार (Expanding)

यदि हम अपने पिछले उदाहरण से sums का विस्तार करते हैं, तो हमें निम्नलिखित प्राप्त होता है

\begin{align*} \sum_{i=1}^4 a_iu_i(x) &= a_1(u_{12}x^2 + u_{11}x+u_{10}) + a_2(u_{22}x^2 + u_{21}x+u_{20}) + a_3(u_{32}x^2 + u_{31}x+u_{30}) + a_4(u_{42}x^2 + u_{41}x+u_{40})\\ &= (a_1u_{12}+a_2u_{22}+a_3u_{32}+a_4u_{42})x^2 + (a_1u_{11}+a_2u_{21}+a_3u_{31}+a_4u_{41})x + (a_1u_{10}+a_2u_{20}+a_3u_{30}+a_4u_{40})\\ &=u_{2a}x^2+u_{1a}x+u_{0a}\\ \sum_{i=1}^4 a_iv_i(x) &= a_1(v_{12}x^2 + v_{11}x+v_{10}) + a_2(v_{22}x^2 + v_{21}x+v_{20}) + a_3(v_{32}x^2 + v_{31}x+v_{30}) + a_4(v_{42}x^2 + v_{41}x+v_{40})\\ &= (a_1v_{12}+a_2v_{22}+a_3v_{32}+a_4v_{42})x^2 + (a_1v_{11}+a_2v_{21}+a_3v_{31}+a_4v_{41})x + (a_1v_{10}+a_2v_{20}+a_3v_{30}+a_4v_{40})\\ &=v_{2a}x^2+v_{1a}x+v_{0a}\\ \sum_{i=1}^4 a_iw_i(x) &= a_1(w_{12}x^2 + w_{11}x+w_{10}) + a_2(w_{22}x^2 + w_{21}x+w_{20}) + a_3(w_{32}x^2 + w_{31}x+w_{30}) + a_4(w_{42}x^2 + w_{41}x+w_{40})\\ &= (a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2 + (a_1w_{11}+a_2w_{21}+a_3w_{31}+a_4w_{41})x + (a_1w_{10}+a_2w_{20}+a_3w_{30}+a_4w_{40})\\ &=w_{2a}x^2+w_{1a}x+w_{0a}\\ \end{align*}

इनमें से प्रत्येक मामले में, चूँकि हम 4 degree 2 वाले polynomials को जोड़ रहे हैं, हमें एक degree 2 वाला polynomial प्राप्त होता है।

सामान्य रूप में, expression $\sum_{i=1}^m a_ip_i(x)$ एक ऐसा polynomial उत्पन्न करता है जिसकी अधिकतम power $p(x)$ के समान होती है (यह कम भी हो सकती है, यदि उदाहरण के लिए $(a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2$ जुड़कर 0 हो जाए)। सुविधा के लिए, हमने coefficients $p_{ia}$ को पेश किया है जहाँ $i$ coefficient की power है और $_a$ का अर्थ है कि हमने polynomials को witness $\mathbf{a}$ के साथ मिला दिया है।

इस प्रकार polynomials को reduce करने के बाद polynomials यहाँ दिए गए हैं:

\begin{align*} \sum_{i=1}^4 a_iu_i(x) &= u_{2a}x^2+u_{1a}x+u_{0a}\\ \sum_{i=1}^4 a_iv_i(x) &= v_{2a}x^2+v_{1a}x+v_{0a}\\ \sum_{i=1}^4 a_iw_i(x) &= w_{2a}x^2+w_{1a}x+w_{0a}\\ \end{align*}

एक QAP के साथ trusted setup को Combine करना

अब हम polynomials को evaluate करने के लिए trusted setup से structured reference string को लागू कर सकते हैं।

अर्थात्, दी गई एक structured reference string

[\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], \space\Omega_i \in \mathbb{G}_1, \space\Theta_i \in \mathbb{G}_2

जिसकी trusted setup में इस प्रकार गणना (computed) की गई थी

\begin{align*} [\Omega_2, \Omega_1, G_1] &= [\tau^2G_1, \tau G_1, G_1], \space\Omega_i \in \mathbb{G}_1\\ [\Theta_2, \Theta_1, G_2] &= [\tau^2G_2, \tau G_2, G_2], \space\Theta_i \in \mathbb{G}_2 \end{align*}

हम गणना कर सकते हैं

\begin{align*} [A]_1 &=\sum_{i=1}^4 a_iu_i(\tau) = \langle[u_{2a}, u_{1a}, u_{0a}],[\Omega_2, \Omega_1, G_1]\rangle\\ [B]_2 &=\sum_{i=1}^4 a_iv_i(\tau) = \langle[v_{2a}, v_{1a}, v_{0a}],[\Theta_2, \Theta_1, G_2]\rangle\\ [C]_1 &=\sum_{i=1}^4 a_iw_i(\tau) = \langle[v_{2a}, v_{1a}, v_{0a}],[\Omega_2, \Omega_1, G_1]\rangle \\ \end{align*}

यहाँ, $u_i(\tau), v_i(\tau), w_i(\tau)$ का अर्थ है कि polynomials का मूल्यांकन trusted setup में $\tau$ से उत्पन्न structured reference string का उपयोग करके किया गया था, इसका अर्थ यह नहीं है कि “ $\tau$ को डालें और polynomials को evaluate करें”। चूँकि trusted setup के बाद $\tau$ को नष्ट कर दिया गया था, इसलिए $\tau$ का मान (value) अज्ञात है।

हमने srs का उपयोग करके अधिकांश QAP की गणना कर ली है, लेकिन हमने अभी तक $h(x)t(x)$ की गणना नहीं की है:

\underbrace{\sum_{i=1}^m a_iu_i(x)}_{[A]_1}\underbrace{\sum_{i=1}^m a_iv_i(x)}_{[B]_2} = \underbrace{\sum_{i=1}^m a_iw_i(x)}_{[C]_1} + \underbrace{h(x)t(x)}_{??}

$h(x)t(x)$ की गणना करना (Computing)

याद करें कि $t(x)$ की degree 3 (आमतौर पर $n$ ) है और $h(x)$ की degree 1 (आमतौर पर $n - 2$ ) है। यदि हम इन्हें एक साथ गुणा करते हैं, तो हमें अधिकतम degree 3 वाला polynomial मिल सकता है, जो कि powers of tau ceremony द्वारा प्रदान किए जाने वाले से अधिक है। इसके बजाय, $h(x)t(x)$ के लिए एक structured reference string प्रदान करने के लिए powers of tau ceremony को समायोजित (adjusted) किया जाना चाहिए।

जो व्यक्ति trusted setup कर रहा है उसे $t(x)$ पता होता है, यह बस $(x - 1)(x - 2)...(x - n)$ होता है। हालाँकि, $h(x)$ एक ऐसा polynomial है जिसकी गणना prover द्वारा की जाती है और यह $\mathbf{a}$ के मानों के आधार पर बदलता है, इसलिए इसे trusted setup के दौरान जाना नहीं जा सकता है।

ध्यान दें कि हम $h(\tau)$ और $t(\tau)$ को अलग-अलग (एक structured reference string का उपयोग करके) evaluate नहीं कर सकते और फिर उन्हें एक साथ pair नहीं कर सकते। इससे $\mathbb{G}_1$ element प्राप्त नहीं होगा जिसकी हमें आवश्यकता है।

Polynomial products के लिए SRS

ध्यान दें कि निम्नलिखित सभी computations का परिणाम समान मान (value) ही होता है:

Polynomial $h(x)t(x)$ का $u$ पर मूल्यांकन, या $(h(x)t(x))(u)$
$h(u)$ को $t(u)$ से गुणा किया गया, या $h(u)t(u)$ ( $h$ का $u$ पर मूल्यांकन और $t$ का $u$ पर मूल्यांकन)
$h(x)$ को evaluation $t(u)$ से गुणा किया गया, फिर $u$ पर evaluate किया गया, यानी $(h(x)t(u))(u)$

हम $h(\tau)t(\tau)$ की गणना करने के लिए तीसरी विधि का उपयोग करेंगे। मान लीजिए, व्यापकता को खोए बिना (without loss of generality), कि $h(x)$ $3x^2 + 6x + 2$ है और $t(u) = 4$ है। तो computation होगी

h(x)t(u) = (3x^2 + 6x + 2) \cdot 4 = 12x^2 + 24x + 8

यदि हम $u$ को $12x^2 + 24x + 8$ में डालते हैं, तो वह $h(u)t(u)$ होगा।

हालाँकि, इस polynomial को $\tau$ पर evaluate करने के लिए prover को $\tau$ पता होना आवश्यक होगा। यहाँ मुख्य अंतर्दृष्टि (key insight) यह है कि उपरोक्त computation को इस प्रकार संरचित किया जा सकता है:

h(u)t(u) = \langle[3, 6, 2], [4u^2, 4u, 4]\rangle=12u^2+24u+8

यदि trusted setup $[4u^2, 4u, 4]$ प्रदान करता है, और prover $[3, 6, 2]$ प्रदान करता है, तो prover $u$ को जाने बिना $h(u)t(u)$ की गणना कर सकता है, क्योंकि $u$ से जुड़ी कोई भी चीज़ inner product के right vector में है।

$h(\tau)t(\tau)$ के लिए Structured reference string

$h(\tau)t(\tau)$ के लिए एक structured reference string बनाने के लिए, हम $\tau$ की क्रमिक powers (successive powers) से गुणा किए गए $t(\tau)$ के $n - 1$ evaluations बनाते हैं।

[\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0] = [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, ..., \tau t(\tau)G_1, t(\tau)G_1]

(थोड़ा भ्रमित करने वाली बात यह है कि degree $k$ वाले एक polynomial में $k+1$ terms होते हैं, इसलिए हम degree $k - 2$ वाले एक polynomial के लिए $k - 1$ evaluations उत्पन्न करते हैं। ध्यान दें कि Upsilon ${n-1}$ से शुरू होता है और 0 पर समाप्त होता है)।

यहाँ, $n$ , R1CS में rows की संख्या है, और हमने स्थापित किया है कि $h$ की degree $n - 2$ से अधिक नहीं हो सकती।

$h(\tau)t(\tau)$ की गणना के लिए structured reference string का उपयोग करने के लिए, prover यह करता है:

h(\tau)t(\tau) = \langle[h_{n-2}, h_{n-3}, ..., h_1, h_0], [\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0] \rangle

एक Trusted Setup पर QAP को Evaluate करना

अब हम सब कुछ एक साथ जोड़ते हैं। मान लीजिए कि हमारे पास $n$ rows और $m$ columns वाले matrices के साथ एक R1CS है। इससे, हम इसे QAP में बदलने के लिए Lagrange interpolation लागू कर सकते हैं

\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)

Sum terms में से प्रत्येक $n - 1$ degree वाला एक polynomial उत्पन्न करेगा (एक Lagrange polynomial की degree उसके द्वारा interpolate किए जाने वाले points की संख्या से एक कम होती है), और $h(x)$ polynomial की degree अधिकतम $n - 2$ होगी, तथा $t(x)$ की degree $n$ होगी।

एक trusted setup एक random field element $\tau$ उत्पन्न करता है और गणना करता है:

\begin{align*} [\Omega_{n-1},\Omega_{n-2},..., \Omega_1, G_1] &= [\tau^{n-1}G_1, \tau^{n-2}G_1,\dots, \tau G_1, G_1]\\ [\Theta_{n-1}, \Theta_{n-2}, ..., \Theta_1, G_2] &= [\tau^{n-1}G_2, \tau^{n-2}G_2,\dots, \tau G_2, G_2]\\ [\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0] &= [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, ..., \tau t(\tau)G_1, t(\tau)G_1] \end{align*}

ध्यान दें कि QAP में polynomials को समायोजित (accommodate) करने के लिए structured reference strings में पर्याप्त terms होने चाहिए।

फिर trusted setup $\tau$ को नष्ट कर देता है और structured reference strings को publish करता है:

([\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], [\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0])

Prover, QAP के components को इस प्रकार evaluate करता है:

\underbrace{\sum_{i=1}^m a_iu_i(x)}_{A}\underbrace{\sum_{i=1}^m a_iv_i(x)}_B = \underbrace{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}_{C}

\begin{align*} [A]_1 &=\sum_{i=1}^m a_iu_i(\tau) = \langle[u_{{n-1}a}, u_{{n-2}a}, \dots, u_{1a}, u_{0a}],[\Omega_{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle\\ [B]_2 &=\sum_{i=1}^m a_iv_i(\tau) = \langle[v_{{n-1}a}, v_{{n-2}a}, \dots, v_{1a}, v_{0a}],[\Theta_{n-1}, \Theta_{n-2}, \dots, \Theta_1, G_2]\rangle\\ [C]_1 &=\sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau) = \langle[w_{{n-1}a}, w_{{n-2}a}, \dots, w_{1a}, w_{0a}],[\Omega_{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle \\ &+\langle[h_{n-2}, h_{n-3}, \dots, h_1, h_0], [\Upsilon_{n-2}, \Upsilon_{n-3}, \dots, \Upsilon_1, \Upsilon_0] \rangle\\ \end{align*}

Prover $([A]_1, [B]_2, [C]_1)$ को publish करता है और verifier जाँच सकता है कि

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

यदि witness $\mathbf{a}$ QAP को संतुष्ट करता है, तो उपरोक्त समीकरण संतुलित (balanced) हो जाएगा। लेकिन समीकरण का संतुलित होना यह सुनिश्चित नहीं करता है कि prover एक संतुष्ट करने वाले $\mathbf{a}$ को जानता है क्योंकि prover arbitrary elliptic curve points publish कर सकता है और verifier को यह नहीं पता होता कि वे वास्तव में QAP से प्राप्त हुए हैं या नहीं।

Proof बहुत छोटा होता है

ध्यान दें कि proof में केवल तीन elliptic curve points होते हैं। यदि एक $\mathbb{G}_1$ element का आकार 64 bytes है, और एक $\mathbb{G}_2$ element का आकार 128 bytes है, तो proof केवल 256 bytes का होता है। यह R1CS के आकार के बावजूद सत्य है!

R1CS जितना बड़ा होगा, prover का काम उतना ही अधिक होगा, लेकिन verifier का काम constant रहता है।

इस समस्या का समाधान Groth16 protocol पर अगले अध्याय में वर्णित है।

Groth16 में proof अभी भी constant आकार का रहता है, जैसा कि Proof नामक struct पर Tornado Cash के source code में देखा जा सकता है।

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