Bulletproofs ZKP: इनर प्रोडक्ट्स के लिए ज़ीरो नॉलेज और संक्षिप्त प्रमाण

Last updated on Nov 4, 2024

Bulletproofs ZKPs एक prover को लॉगरिदमिक-आकार (logarithmic-sized) के proof के साथ एक inner product के ज्ञान को प्रमाणित करने की अनुमति देते हैं। Bulletproofs को किसी trusted setup की आवश्यकता नहीं होती है।

पिछले अध्यायों में, हमने दिखाया कि vectors या inner product को प्रकट किए बिना inner product के ज्ञान को कैसे प्रमाणित किया जाए, हालांकि इसमें proof का आकार $\mathcal{O}(n)$ था जहाँ $n$ vector की लंबाई है। हमने यह भी दिखाया कि लॉगरिदमिक-आकार के डेटा का उपयोग करके inner product के ज्ञान को कैसे प्रमाणित किया जाए, लेकिन बिना zero knowledge गुण (property) के।

इस अध्याय में, हम Bulletproof ZK एल्गोरिथम को प्रदर्शित करने के लिए इन एल्गोरिथम्स को एक साथ मिलाते हैं।

(यह कार्य ZK Bulletproofs पर आधारित एक श्रृंखला का हिस्सा है।)

समस्या का विवरण

Prover और verifier लंबाई $n$ के दो elliptic curve basis vectors $\mathbf{G}$ और $\mathbf{H}$ और elliptic curve points $Q$ और $B$ पर सहमत होते हैं। इन सभी points के बीच discrete log relationships अज्ञात हैं।

Prover के पास inner product $v$ के साथ vectors $\mathbf{a}$ और $\mathbf{b}$ हैं। Prover $\mathbf{a}$ और $\mathbf{b}$ को $A$ के लिए इस प्रकार commit करता है: $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$ जहाँ $\alpha$ एक blinding term है। Prover $V = \langle\mathbf{a},\mathbf{b}\rangle Q + \gamma B$ को commit करता है।

Prover verifier को $(A, V)$ भेजता है और यह साबित करने का लक्ष्य रखता है कि $\mathbf{a}$ और $\mathbf{b}$ $A$ के लिए committed हैं और उनका inner product $V$ के लिए committed है। Verifier को vectors या inner product के बारे में कुछ पता नहीं चलता है।

Proof का आकार $\mathcal{O}(\log n)$ होना चाहिए।

Bulletproof ZK एल्गोरिथम

Prover रैंडम scalars $\set{\alpha, \beta,\gamma,\tau_1,\tau_2}$ और रैंडम vectors $\set{\mathbf{s}_L,\mathbf{s}_R}$ जनरेट करता है और commitments की गणना करता है:

\begin{align} A &= \langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle+\alpha B\\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle + \langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B\\ V &= vQ + \gamma B \\ \end{align}

Prover vector polynomials तैयार करता है (लेकिन भेजता नहीं है):

\begin{align*} \mathbf{l}(x) &= \mathbf{a} + \mathbf{s}_Lx\\ \mathbf{r}(x) &= \mathbf{b} + \mathbf{s}_Rx\\ t(x)&=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle = \langle\mathbf{a},\mathbf{b}\rangle+(\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle) x+(\langle\mathbf{s}_L,\mathbf{s}_R\rangle)x^2 \end{align*}

$A$ vector polynomial के constant terms के लिए एक commitment है, $S$ linear terms के लिए एक commitment है, और $V$ inner product के लिए एक commitment है।

Prover $t(x)$ के coefficients के लिए commitments इस प्रकार बनाता है:

\begin{align*} T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)Q + \tau_1B\\ T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle Q + \tau_2B \end{align*}

ध्यान दें कि $V$ , $t(x)$ के constant coefficient के लिए एक commitment है, और $T_1$ और $T_2$ क्रमशः $t(x)$ के linear और quadratic coefficients के लिए commitments हैं।

Prover verifier को $(A, S, V, T_1, T_2)$ भेजता है।

Verifier रैंडम वैल्यू $u$ के साथ उत्तर देता है।

फिर prover $u$ पर polynomials का मूल्यांकन (evaluate) करता है और proofs बनाता है कि उनका मूल्यांकन सही ढंग से किया गया था:

\begin{align*} \mathbf{l}_u &= \mathbf{l}(u) = \mathbf{a} + \mathbf{s}_Lu \\ \mathbf{r}_u &= \mathbf{r}(u) = \mathbf{b} + \mathbf{s}_Ru \\ t_u &= t(u) =v + (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)u + \langle\mathbf{s}_L,\mathbf{s}_R\rangle u^2\\ \pi_{lr} &=\alpha+\beta u\\ \pi_t &= \gamma + \tau_1u + \tau_2u^2\\ \end{align*}

पहले, prover $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$ ट्रांसमिट करता था ताकि verifier यह जांच सके कि:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A + Su &\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle + \pi_{lr} B\\ t_u Q &\stackrel{?}{=} V + T_1 u + T_2 u^2 - \pi_t B\\ \end{align*}

लेकिन यह vectors $\mathbf{l}_u$ और $\mathbf{r}_u$ के कारण आकार में linear होगा। इसके बजाय, prover $\mathbf{l}_u$ और $\mathbf{r}_u$ को इस प्रकार commit करता है:

C=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{H}\rangle

और $(C, t_u, \pi_{lr}, \pi_t)$ भेजता है।

हम पहले दो verifier चेक्स को इस प्रकार पुनर्व्यवस्थित (re-arrange) कर सकते हैं:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A + Su -\pi_{lr}B&\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle\\ \end{align*}

ध्यान दें कि यदि हम $P = A + Su -\pi_{lr}B$ सेट करते हैं, तो यह ठीक वैसी ही समस्या (problem statement) है जैसे यह साबित करना कि $P$ basis vectors $\mathbf{G}$ और $\mathbf{H}$ के संदर्भ में दो vectors $\mathbf{l}_u$ और $\mathbf{r}_u$ के commitments रखता है, और यह कि $\mathbf{l}_u$ और $\mathbf{r}_u$ का inner product $t_u$ है। इसलिए, हम $P$ पर ओपन होने वाले commitment के ज्ञान के लॉगरिदमिक-आकार के proof का पुन: उपयोग कर सकते हैं।

इस proof के लिए, हमें गोपनीयता (secrecy) की आवश्यकता नहीं है क्योंकि पिछले एल्गोरिथम में $\mathbf{l}_u$ और $\mathbf{r}_u$ को वैसे भी सार्वजनिक कर दिया गया था।

अब जब verifier के पास सभी आवश्यक डेटा है, तो prover एक interactive proof में भाग लेता है ताकि यह साबित किया जा सके कि $C$ में $\mathbf{l}_u$ और $\mathbf{r}_u$ के commitments हैं और उनका inner product $t_u$ है:

\texttt{prove_commitments_log}(C + t_uQ, \mathbf{G}, \mathbf{H}, Q, \mathbf{l}_u, \mathbf{r}_u)

वह सबरूटीन (subroutine) यह साबित करेगा कि $t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ और $C\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle$ , बिना $\mathbf{l}_u$ और $\mathbf{r}_u$ को भेजे। यह केवल लॉगरिदमिक-आकार का डेटा भी भेजता है। ध्यान दें कि पिछले अध्याय का रिकर्सिव एल्गोरिथम (recursive algorithm) $P = \langle \mathbf{a}, \mathbf{G} \rangle + \langle \mathbf{b}, \mathbf{H} \rangle + \langle\mathbf{a},\mathbf{b}\rangle Q$ commitment का उपयोग करता है, इसलिए verifier को स्वयं “ $Q$ हिस्सा” जोड़ना होगा। अब verifier आश्वस्त हो सकता है कि:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ C&\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle\\ \end{align*}

अंत में, verifier जांचता है कि:

\begin{align*} C&\stackrel{?}=A + Su-\pi_{lr}B\\ t_u Q &\stackrel{?}{=} V + T_1 u + T_2 u^2 - \pi_t B \end{align*}

याद रखें कि $A$ और $S$ क्रमशः vector polynomials $\mathbf{l}(x)$ और $\mathbf{r}(x)$ के constant और linear terms के लिए commitments हैं। पहली जांच यह सुनिश्चित करती है कि $C$ के लिए कमिट किए गए vectors $u$ पर उन polynomials के evaluations हैं।

दूसरी जांच यह सुनिश्चित करने के लिए है कि coefficients $V$ , $T_1$ , और $T_2$ के commitments को देखते हुए $t(u)$ का मूल्यांकन सही ढंग से किया गया था।

Fiat Shamir Transform के माध्यम से Non-interactivity

व्यवहार में, इस एल्गोरिथम को Fiat Shamir Transform के माध्यम से non-interactive बनाया जाता है। Verifier से रैंडमनेस (randomness) माँगने के बजाय, prover अब तक ट्रांसमिट किए गए सभी डेटा को जोड़कर (concatenating) और उसे हैश (hash) करके रैंडमनेस जनरेट करता है। फिर verifier यह सुनिश्चित करने के लिए डेटा को फिर से हैश करता है कि prover ने रैंडमनेस सही ढंग से जनरेट की है।

यह महत्वपूर्ण है कि हैश में सभी पिछले डेटा ट्रांसमिशन शामिल हों, अन्यथा कार्यान्वयन (implementation) में frozen heart vulnerability आ सकती है।

अगला कदम

व्यवहार में, व्यावहारिक रुचि की समस्याओं में कई inner products शामिल होते हैं। उदाहरण के लिए, एक Rank 1 Constraint System:

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

वास्तव में $3n$ inner products (उदाहरण के लिए $\mathbf{a}$ को $L$ की $n$ पंक्तियों से गुणा करना और इसी तरह $R$ और $O$ के लिए) और एक एकल Hadamard product है। इसलिए, कई inner products को एक में मिलाने के लिए कुछ गणितीय ट्रिक्स जानना उपयोगी होगा ताकि हमें $3n$ Bulletproofs न भेजने पड़ें। हम यह सीखेंगे कि इसे रैंडम लीनियर कॉम्बिनेशन्स (random linear combinations) पर हमारे आगामी अध्याय में कैसे प्राप्त किया जाए।

इसके अलावा, कुछ उपयोगी समस्याओं को सीधे एक inner product के रूप में एन्कोड किया जा सकता है, विशेष रूप से range proof या subset sum समस्या। उन स्थितियों में, हम समस्या को arithmetic circuit के रूप में एन्कोड करने को छोड़ सकते हैं और इसे सीधे inner product के रूप में एन्कोड कर सकते हैं। अपने inner product प्रतिनिधित्व (representation) के लचीलेपन (flexibility) को बढ़ाने के साथ-साथ random linear combinations को समझने के लिए आधार तैयार करने के लिए, हम अगले अध्याय में कुछ inner product बीजगणित (algebra) सीखेंगे।

अभ्यास: यह साबित करने के लिए पिछले अभ्यासों को मिलाएं कि $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$ जहाँ $\mathbf{a}$ और $\mathbf{b}$ 4 की लंबाई वाले vectors हैं। आपका proof succinct और zero knowledge दोनों होना चाहिए। सरलता के लिए एक interactive proof बनाएं। अभ्यासों के लिए इस रिपॉजिटरी का संदर्भ लें।

Last updated on Nov 4, 2024

(यह कार्य ZK Bulletproofs पर आधारित एक श्रृंखला का हिस्सा है।)

समस्या का विवरण

Proof का आकार $\mathcal{O}(\log n)$ होना चाहिए।

Bulletproof ZK एल्गोरिथम

\begin{align} A &= \langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle+\alpha B\\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle + \langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B\\ V &= vQ + \gamma B \\ \end{align}

Prover vector polynomials तैयार करता है (लेकिन भेजता नहीं है):

\begin{align*} \mathbf{l}(x) &= \mathbf{a} + \mathbf{s}_Lx\\ \mathbf{r}(x) &= \mathbf{b} + \mathbf{s}_Rx\\ t(x)&=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle = \langle\mathbf{a},\mathbf{b}\rangle+(\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle) x+(\langle\mathbf{s}_L,\mathbf{s}_R\rangle)x^2 \end{align*}

Prover $t(x)$ के coefficients के लिए commitments इस प्रकार बनाता है:

\begin{align*} T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)Q + \tau_1B\\ T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle Q + \tau_2B \end{align*}

Prover verifier को $(A, S, V, T_1, T_2)$ भेजता है।

Verifier रैंडम वैल्यू $u$ के साथ उत्तर देता है।

\begin{align*} \mathbf{l}_u &= \mathbf{l}(u) = \mathbf{a} + \mathbf{s}_Lu \\ \mathbf{r}_u &= \mathbf{r}(u) = \mathbf{b} + \mathbf{s}_Ru \\ t_u &= t(u) =v + (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)u + \langle\mathbf{s}_L,\mathbf{s}_R\rangle u^2\\ \pi_{lr} &=\alpha+\beta u\\ \pi_t &= \gamma + \tau_1u + \tau_2u^2\\ \end{align*}

पहले, prover $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$ ट्रांसमिट करता था ताकि verifier यह जांच सके कि:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A + Su &\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle + \pi_{lr} B\\ t_u Q &\stackrel{?}{=} V + T_1 u + T_2 u^2 - \pi_t B\\ \end{align*}

C=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{H}\rangle

और $(C, t_u, \pi_{lr}, \pi_t)$ भेजता है।

हम पहले दो verifier चेक्स को इस प्रकार पुनर्व्यवस्थित (re-arrange) कर सकते हैं:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A + Su -\pi_{lr}B&\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle\\ \end{align*}

\texttt{prove_commitments_log}(C + t_uQ, \mathbf{G}, \mathbf{H}, Q, \mathbf{l}_u, \mathbf{r}_u)

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ C&\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle\\ \end{align*}

अंत में, verifier जांचता है कि:

\begin{align*} C&\stackrel{?}=A + Su-\pi_{lr}B\\ t_u Q &\stackrel{?}{=} V + T_1 u + T_2 u^2 - \pi_t B \end{align*}

Fiat Shamir Transform के माध्यम से Non-interactivity

अगला कदम

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