यदि हमारे पास एक Pedersen vector commitment $A$ है जिसमें एक vector $\mathbf{a}$ के लिए commitment शामिल है, जैसे $A = a_1G_1 + a_2G_2+\dots + a_nG_n$, तो हम verifier को $\mathbf{a}$ भेजकर यह साबित कर सकते हैं कि हम opening जानते हैं, जो यह जांचेगा कि $A \stackrel{?}= a_1G_1 + \dots + a_nG_n$ है या नहीं। इसके लिए verifier को $n$ elements भेजने की आवश्यकता होती है (यह मानते हुए कि $\mathbf{a}$ की लंबाई $n$ है)।

पिछले अध्याय में, हमने दिखाया था कि इसे zero knowledge के साथ कैसे किया जाए। इस अध्याय में, हम दिखाएंगे कि $n$ elements से कम भेजते हुए opening के ज्ञान को कैसे साबित किया जाए, लेकिन zero knowledge प्रॉपर्टी के बिना।

Motivation

हम यहाँ जो तकनीक विकसित करेंगे वह आकार $\log n$ के proof के साथ एक inner product की वैध गणना को साबित करने के लिए एक महत्वपूर्ण building block होगी, जहाँ $n$ vectors की लंबाई है।

पिछले अध्याय में, हमने दिखाया कि यह कैसे साबित किया जाए कि हमने inner product को सही ढंग से execute किया है, लेकिन vectors या परिणाम को प्रकट किए बिना। हालाँकि, उस step के कारण जहाँ prover $\mathbf{l}_u$ और $\mathbf{r}_u$ भेजता है, proof का आकार $\mathcal{O}(n)$ है।

इस लेख में subroutine proof के आकार को कम करने के लिए महत्वपूर्ण होगा। यह लेख zero knowledge से संबंधित नहीं है क्योंकि पहले चर्चा किए गए algorithm में zero knowledge प्रॉपर्टी होती है। यानी $\mathbf{l}_u$ और $\mathbf{r}_u$ शुरुआत में गुप्त नहीं थे, इसलिए उन्हें obfuscate (छिपाने) करने की कोई आवश्यकता नहीं है।

Problem statement

एक सहमत basis vector $\mathbf{G}=[G_1,\dots,G_n]$ दिए जाने पर, prover verifier को एक Pedersen vector commitment $A$ देता है, जहाँ $A$, $\mathbf{a}$ के लिए एक non-blinding commitment है, यानी $A = \langle[a_1,\dots,a_n],[G_1,\dots,G_n]\rangle$, और वह $n$ terms से कम भेजकर यह साबित करना चाहता है कि वह commitment की opening जानता है, यानी पूरा vector $[a_1,\dots,a_n]$ भेजने के बजाय।

$n$ से छोटा proof

Proof के आकार को छोटा करना तीन insights पर निर्भर करता है:

Insight 1: Inner product $\langle \mathbf{a},\mathbf{b}\rangle$ outer product का diagonal होता है

पहला insight जिसका हम लाभ उठाएंगे वह यह है कि inner product outer product का diagonal होता है। दूसरे शब्दों में, outer product एक तरह से inner product को “समाहित” करता है। 1D vectors के संदर्भ में, outer product एक 2D matrix है जो पहले 1D vector के प्रत्येक element को दूसरे vector के प्रत्येक अन्य element से गुणा करके बनाया जाता है। उदाहरण के लिए:

यह गलत दिशा में उठाया गया कदम लग सकता है क्योंकि outer product की गणना करने के लिए $\mathcal{O}(n^2)$ steps की आवश्यकता होती है। हालाँकि, निम्नलिखित insight से पता चलता है कि $\mathcal{O}(1)$ समय में outer product की अप्रत्यक्ष (indirectly) गणना करना संभव है।

Insight 2: Outer product का योग original vectors के योग के गुणनफल (product) के बराबर होता है

दूसरा observation यह है कि outer product के terms का योग vectors के योग के गुणनफल के बराबर होता है। यानी,

vectors $[a_1,a_2]$ और $[b_1,b_2]$ के हमारे उदाहरण के लिए यह होगा:

Graphically (ग्राफ़िक रूप से), इसे $(a_1 + a_2) \times (b_1 + b_2)$ dimensions वाले आयत (rectangle) के क्षेत्रफल के रूप में देखा जा सकता है, जिसका “क्षेत्रफल” $a_1 \times b_1 + a_1 \times b_2 + a_2 \times b_1 + a_2 \times b_2$ के समान होता है:

हमारे मामले में, $\mathbf{b}$ vector वास्तव में elliptic curve points का basis vector है, इसलिए हम कह रहे हैं कि

ध्यान दें कि हमारा मूल Pedersen commitment

outer product के बॉक्स वाले terms में एम्बेडेड (embedded) है:

इसलिए, vector entries के योग को एक साथ गुणा करके, हम outer product के योग की भी गणना करते हैं।

चूँकि inner product outer product का diagonal होता है, इसलिए हमने vector entries के योग को एक साथ गुणा करके अप्रत्यक्ष रूप से inner product की गणना कर ली है। यह साबित करने के लिए कि हम inner product जानते हैं, हमें यह साबित करने की आवश्यकता है कि हम outer product के उन terms को भी जानते हैं जो inner product का हिस्सा नहीं हैं।

लंबाई $2$ वाले vectors के लिए, आइए outer product के उन हिस्सों को जो inner product का हिस्सा नहीं हैं, off-diagonal product कहें।

नीचे, हम उन terms को $\square$ से चिह्नित करते हैं जो off-diagonal product बनाते हैं और उन terms को $\blacksquare$ से चिह्नित करते हैं जो inner product बनाते हैं:

अब हम औपचारिक रूप से उस identity को बता सकते हैं जिस पर हम आगे चलकर निर्भर रहेंगे। यदि $n=2$ है तो:

यह identity तब भी मान्य होती है जब vectors में से कोई एक elliptic curve points का vector हो (भले ही उनके discrete logs अज्ञात हों)।

उन मामलों के लिए जहाँ $n > 2$ है, एक inner product के ज्ञान को साबित करने का अर्थ है कि prover को verifier को यह विश्वास दिलाना होगा कि वे नीचे दिए गए बैंगनी रंग वाले (purple-shaded) क्षेत्र के “क्षेत्रफल” को जानते हैं।

$n > 2$ होने पर इस जानकारी को संक्षेप (succinctly) में बताना अधिक कठिन है, इसलिए हम इस पर बाद में फिर से विचार करेंगे।

$n = 2$ के मामले में, क्षेत्रफल केवल off-diagonals है।

Insight 3: यदि $n = 1$ है तो inner product outer product के बराबर होता है

एक महत्वपूर्ण corner case वह है जहाँ हमारे पास लंबाई $1$ का एक vector है। उस मामले में, prover केवल verifier को $\mathbf{a}$ (जिसकी लंबाई $1$ है) भेजता है और verifier केवल $\mathbf{a}$ के single element को $\mathbf{G}$ के single element से गुणा करता है।

Algorithm की रूपरेखा (Sketch)

अब हम $n=2$ मामले के लिए एक algorithm का पहला ड्राफ्ट बना सकते हैं जो यह साबित करता है कि हमने $\mathbf{a}$ और $\mathbf{G}$ के inner product की गणना की है, जो यह दिखाने के समतुल्य है कि हम commitment $A$ जानते हैं।

Prover और verifier के बीच का interaction इस प्रकार है:

1. Prover verifier को अपना commitment $A = a_1G_1 + a_2G_2$ भेजता है।
2. Prover $\mathbf{a}$ के सभी terms को जोड़ता है और उसे $a' = a_1 + a_2$ के रूप में verifier को भेजता है (ध्यान दें कि vector के components का योग एक scalar होता है, इसलिए $\mathbf{a}$ के elements को जोड़ने पर scalar $a'$ प्राप्त होता है)। इसके अलावा, prover $\mathbf{a} \otimes \mathbf{G}$ के off-diagonal terms (यानी $R = a_2G_1$, $L = a_1G_2$) की गणना करता है और $L$ और $R$ को verifier को भेजता है।

Graphically, $L$ और $R$ को इस प्रकार देखा जा सकता है:

3. Verifier अप्रत्यक्ष रूप से $a'G'$ की गणना करके $\mathbf{a} \otimes \mathbf{G}$ की गणना करता है, जहाँ $G' = G_1 + G_2$ है, और जाँचता है कि

Expanded रूप में, उपरोक्त समीकरण है:

ध्यान दें कि उपरोक्त जाँच पहले दी गई identity के समतुल्य है:

Security bug: एकाधिक (multiple) openings

हालाँकि, यहाँ एक security issue है – prover एक ही commitment के लिए कई proofs खोज सकता है। उदाहरण के लिए, prover $L$ को randomly चुन सकता है, फिर गणना कर सकता है:

इसे रोकने के लिए, हम zero knowledge multiplication की अपनी चर्चा से एक समान विचार का फिर से उपयोग करते हैं – prover को अपनी गणना में verifier द्वारा प्रदान की गई randomness $u$ को शामिल करना होगा। उन्हें $u$ प्राप्त करने से पहले (in advance) $L$ और $R$ भी भेजना होगा ताकि $L$ और $R$ को “फायदेमंद” तरीके से नहीं चुना जा सके।

Prover को योग $L + R$ के बजाय $L$ और $R$ को अलग-अलग क्यों भेजना चाहिए, इसका कारण यह है कि prover बिना किसी प्रतिबंध के $L$ और $R$ के बीच value को move करके protocol को हैक करने में सक्षम है। यानी, चूँकि

prover कोई elliptic curve point $S$ चुन सकता है और एक fraudulent (धोखाधड़ी पूर्ण) $L'$ और $R'$ की गणना इस प्रकार कर सकता है:

हमें prover को $L$ और $R$ को अलग रखने के लिए मजबूर करने की आवश्यकता है।

यहाँ updated algorithm है जो इस बग को ठीक करता है:

1. Prover और verifier एक basis vector $[G_1, G_2]$ पर सहमत होते हैं जहाँ points को randomly चुना जाता है और उनके discrete logs अज्ञात होते हैं।

2. Prover $(A, L, R)$ की गणना करता है और verifier को भेजता है:
   

   $$\begin{align*} A &= a_1G_1 + a_2G_2 && \text{// vector commitment we are proving knowledge of}\\ L &= a_1G_2 && \text{// left diagonal term}\\ R &= a_2G_1 && \text{// right diagonal term}\\ \end{align*}$$

3. Verifier एक random scalar $u$ के साथ प्रतिक्रिया देता है।

4. Prover $a'$ की गणना करता है और भेजता है:

5. Verifier, जिसके पास अब $(A, L, R, a', u)$ है, जाँचता है कि:
   
   $$L + u A + u^2R \stackrel{?}= a'(u G_1 + G_2)$$

आंतरिक रूप से (Under the hood) यह है:

जो कि बिल्कुल सही (identically correct) है यदि prover ने $a'$, $L$, और $R$ की सही गणना की है।

ध्यान दें कि verifier ने $u$ को $G_2$ पर apply किया जबकि prover ने $u$ को $a_1$ पर apply किया। इसके कारण original inner product के terms परिणामी (resulting) polynomial के linear coefficients बन जाते हैं।

यह तथ्य कि $L$ और $R$, $u^2$ द्वारा अलग किए गए हैं, जिसे verifier नियंत्रित करता है, एक malicious prover को पहले बताए गए हमले को करने से रोकता है। यानी, prover $R$ से $L$ में value shift नहीं कर सकता है क्योंकि जो value वे shift करते हैं उसे $u^2$ द्वारा scale किया जाना चाहिए, लेकिन prover को $u$ प्राप्त करने से पहले $L$ और $R$ भेजना होगा।

Algorithm की एक वैकल्पिक व्याख्या (alternative interpretation): $n$ के dimension को आधा करना

Verifier केवल एक single गुणा कर रहा है, $a'$ गुना $(uG_1 + G_2)$। भले ही हमने लंबाई $2$ के vectors के साथ शुरुआत की, verifier केवल $n/2=1$ point multiplications करता है।

Operation $a_1 + a_2u$ ने लंबाई $2$ के vector $\mathbf{a}$ को लंबाई $1$ के vector में बदल दिया। इसलिए, prover के vectors और verifier की randomness $u$ दिए जाने पर, prover और verifier दोनों संयुक्त रूप से लंबाई $1$ का एक नया vector बना रहे हैं।

चूँकि दोनों ने original vector को लंबाई $1$ के vector में compress कर दिया है, verifier identity $\langle\mathbf{a}',\mathbf{G}'\rangle=\mathbf{a}'\otimes\mathbf{G}'$ का उपयोग कर सकता है जब $n = 1$ हो। यहाँ, $\mathbf{a}' = a_1 + a_2u$ और $\mathbf{G'} = G_1u + G_2$ है।

Algorithm की सुरक्षा (Security)

Algorithm सारांश

Algorithm के एक त्वरित सारांश (quick summary) के रूप में:

1. Prover verifier को $(A, L, R)$ भेजता है।
2. Verifier $u$ के साथ प्रतिक्रिया देता है।
3. Prover $a'$ की गणना करता है और भेजता है।
4. Verifier जाँचता है कि:

अब आइए देखें कि prover धोखा (cheat) क्यों नहीं दे सकता।

Step 3 पर prover के पास एकमात्र “degree of freedom” $a'$ है।

एक ऐसा $a'$ लाने के लिए जो निम्न को संतुष्ट करे:

prover को $G_1$ और $G_2$ के discrete logs जानने की आवश्यकता है। विशेष रूप से, उन्हें हल करना होगा:

जहाँ

• $l$ और $r$, $L$ और $R$ के discrete logs हैं
• $g_1$ और $g_2$ क्रमशः $G_1$ और $G_2$ के discrete logs हैं, और $a$, $A$ का discrete log है।
• $l$ और $r$ prover को ज्ञात हैं, क्योंकि prover ने step 1 में $L$ और $R$ को produce किया था।

हालाँकि, prover को discrete logs $g_1$ और $g_2$ नहीं पता हैं, इसलिए वे $a'$ की गणना नहीं कर सकते।

Variable $a'$ के केवल दो वैध (valid) समाधान हैं

$a'$ के लिए केवल दो मान वैध हैं जो $L + uA + u^2R = a'(uG_1 + G_2)$ को संतुष्ट करते हैं। ध्यान दें कि समीकरण $L + uA + u^2R$ variable $u$ के संबंध में एक quadratic polynomial बनाता है और $a'(uG_1+G_2)$ एक linear polynomial बनाता है। Schwartz-Zippel Lemma के अनुसार, समीकरण के अधिक से अधिक दो समाधान होते हैं। जब तक field का क्रम (order) $\gg 2$ है, तब तक prover द्वारा ऐसा $a'$ खोजने की संभावना (probability) नगण्य (negligible) है जिसके परिणामस्वरूप $L + uA + u^2R = a'(uG_1 + G_2)$ का एक intersection point प्राप्त हो।

Randomness इंजेक्ट करने के लिए Bulletproofs पेपर का दृष्टिकोण

$a_1$ और $a_2$ को $a_1 + a_2u$ के रूप में एक साथ मिलाने के बजाय, prover उन्हें $a' = a_1u + a_2u^{-1}$ के रूप में मिलाता है और verifier $G' = u^{-1}G_1 + u G_2$ करता है। ध्यान दें कि दो vectors की powers विपरीत क्रम में apply की जाती हैं। जब हम outer product की गणना करते हैं, तो inner product terms में $uu^{-1}$ cancel हो जाएगा:

तार्किक रूप से (Arguably), यह दृष्टिकोण अधिक “cleaner” है इसलिए हम आगे इसी का उपयोग करेंगे।

$\mathsf{fold}(\mathbf{a},x)$ का परिचय

$a_1x + a_2x^{-1}$ की गणना Bulletproofs में इतनी बार होती है कि इसे एक नाम देना सुविधाजनक है, जिसे हम $\mathsf{fold}(\mathbf{a},x)$ कहते हैं। पहला argument $\mathbf{a}$ वह vector है जिसे हम fold कर रहे हैं (जिसकी लंबाई सम (even) होनी चाहिए, यदि नहीं तो हम इसे $0$ के साथ pad करते हैं)। Fold लंबाई $n$ के vector $\mathbf{a}$ को $n/2$ जोड़े (pairs) में विभाजित करता है, और इस प्रकार $n/2$ लंबाई का एक vector देता है:

यदि हम $\mathsf{fold}(\mathbf{a},x^{-1})$ करते हैं तो हमारा मतलब है:

जब $n=2$ होता है, तो $\mathsf{fold}(\mathbf{a},x)$ केवल $a_1x+a_2x^{-1}$ होता है और $\mathsf{fold}(\mathbf{a},x^{-1})=a_1x^{-1}+a_2x$ होता है।

$\mathsf{fold}$ के साथ Algorithm का विवरण

अब हम randomness के लिए Bulletproofs पेपर के दृष्टिकोण का उपयोग करके algorithm को फिर से बताते हैं:

1. Prover $\mathbf{a}$ के लिए अपना commitment $A = a_1G_1 + a_2G_2$ के रूप में verifier को भेजता है, साथ ही $L$ और $R$ भी भेजता है जिसकी गणना इस प्रकार की गई है:
   
   $$\begin{align*} L &= a_1G_2 \\ R &= a_2G_1 \\ \end{align*}$$
2. Verifier एक random scalar $u$ के साथ प्रतिक्रिया देता है।
3. Prover $a'$ की गणना करता है और भेजता है:
   
   $$a' = \mathsf{fold}(\mathbf{a},u) = a_1u + a_2u^{-1}$$
4. Verifier गणना करता है:
   
   $$\begin{align*} P &= a'\cdot\mathsf{fold}(\mathbf{G},u^{-1})= a'\cdot(u^{-1} G_1 + uG_2)\\ P &\stackrel{?} = Lu^2 + A + u^{-2}R \end{align*}$$

यह मानते हुए कि prover ईमानदार था, आंतरिक रूप से (under the hood) अंतिम जाँच इस प्रकार विस्तारित (expand) होती है:

$n > 2$ होने पर मामलों को कैसे handle करें

यह मानते हुए कि array $\mathbf{a}$ की लंबाई सम (even) है (यदि नहीं, तो हम इसे सम लंबाई बनाने के लिए एक zero element जोड़ सकते हैं), हम array को pairwise-partition कर सकते हैं। नीचे एक pairwise-partition का उदाहरण दिया गया है:

इसी तरह, हम $\mathbf{G}$ को pair-wise partition कर सकते हैं।

फिर प्रत्येक sub-pair को पहले बताए गए $n=2$ मामले का उपयोग करके inner product की गणना के उदाहरण (instances) के रूप में माना जा सकता है:

फिर हम यह साबित कर सकते हैं कि हम चार $n=2$ commitments $a_1G_1 + a_2G_2$, $a_3G_3 + a_4G_4$, $a_5G_5 + a_6G_6$, और $a_7G_7 + a_8G_8$ को जानते हैं और यह यह साबित करने के समतुल्य होगा कि हम original commitment की opening को जानते हैं।

हालाँकि, यह हमारे द्वारा साबित किए जा रहे pairs के लिए चार अतिरिक्त $(L, R)$ terms बनाएगा – यानी, prover द्वारा ट्रांसमिट किए जाने वाले डेटा के आकार के संदर्भ में कोई efficiency gain (दक्षता लाभ) नहीं होगा।

Naive समाधान यह होगा कि prover commit करे और भेजे:

Graphically, इसे इस प्रकार देखा जा सकता है:

एक (मुख्य!) optimization के रूप में, हम प्रत्येक जोड़े (pair) से सभी $A_i$, $L_i$ और $R_i$ terms को जोड़कर single points $A$, $L$, $R$ बना देते हैं। दूसरे शब्दों में, prover केवल भेजता है:

वर्णित operation नीचे दिए गए एनीमेशन में दिखाया गया है:

सभी commitments और off-diagonals को एक साथ जोड़ने की सुरक्षा

इस तरह के optimization के साथ एक शुरुआती चिंता यह है कि चूँकि prover अधिक terms को एक साथ जोड़ रहा है, इसलिए एक बेईमान (dishonest) गणना को छिपाने का अधिक अवसर होता है।

अब हम दिखाते हैं कि एक बार जब prover $A$ (और $L$ और $R$) भेज देता है, तो वे केवल एक unique proof ही बना सकते हैं कि वे $A$ की opening को जानते हैं।

ध्यान दें कि $L$ की गणना $L = a_1G_2 + a_3G_4 +a_5G_6+a_7G_8$ के रूप में की जाती है और $R$ की गणना $R = a_2G_1 + a_4G_3 +a_6G_5+a_8G_7$ के रूप में की जाती है। उनमें कोई सामान्य (common) elliptic curve points नहीं हैं। इस प्रकार, prover $L$ से $R$ में “value shift” नहीं कर सकता क्योंकि वे किसी भी points के discrete logs नहीं जानते हैं। प्रभावी रूप से, $L$ basis vector $[G_1, G_3, G_5, G_7]$ पर $[a_2, a_4, a_6, a_8]$ का एक Pedersen vector commitment है। Pedersen vector commitment की security assumption यह है कि prover केवल एक ही संभव vector opening produce कर सकता है। Commitment भेजने के बाद “Shifting values around (मानों को इधर-उधर करने)” का अर्थ होगा कि prover $[a_2, a_4, a_6, a_8]$ के अलावा किसी अन्य vector की गणना कर सकता है जो समान commitment produce करता है। लेकिन यह हमारी इस धारणा (assumption) का खंडन करता है कि एक prover Pedersen commitment के लिए केवल एक single वैध vector ही produce कर सकता है। $R$ के लिए भी ऐसा ही तर्क दिया जा सकता है।

$A$ चार Pedersen commitments (vectors $[a_1, a_2]$, $[a_3, a_4]$, $[a_5, a_6]$, $[a_7, a_8]$ के commitments) का योग है। हालाँकि, यह तथ्य कि कई Pedersen commitments एक साथ जोड़े गए हैं, सुरक्षा के दृष्टिकोण से महत्वहीन (immaterial) है। इससे कोई फर्क नहीं पड़ता कि commitments की गणना अलग से की जाती है और फिर जोड़ी जाती है, या $A$ की गणना $n = 8$ के vector के रूप में की जाती है। इस पर विचार करें कि:

उदाहरण के लिए, prover $a_1G_1$ से $a_2G_1$ में “value shift” कर सकता है।

एकमात्र शेष चिंता यह है कि prover $A$ में $a_1G_1$ से $L$ में $a_2G_1$ तक value shift कर सकता है क्योंकि वे एक common elliptic curve point share करते हैं। हालाँकि, जैसा कि पहले दिखाया गया है, verifier से प्राप्त random $u$ द्वारा इसे रोका जाता है।

इसलिए, एक बार जब prover इस अनुभाग में वर्णित तरीके से गणना किए गए $(A, L, R)$ को भेज देता है, तो वे केवल एक ही संभव opening बना सकते हैं, और इस प्रकार केवल एक ही संभव proof बना सकते हैं।

$n/2$ डेटा भेजते हुए यह साबित करना कि हम $A$ की opening जानते हैं

1. Prover verifier को $A = \langle\mathbf{a},\mathbf{G}\rangle$ भेजता है। Prover $L = a_1G_2 + a_3G_4 + ... a_{n-1}G_n$ और $R = a_2G_1 + a_4G_3 + ... + a_nG_{n-1}$ भी भेजता है।
2. Verifier एक random $u$ भेजता है।
3. Prover $\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)$ की गणना करता है और verifier को $\mathbf{a}'$ भेजता है।
4. Verifier जाँचता है कि $Lu^2 + A + Ru^{-2} \stackrel{?}=\langle\mathbf{a}',\mathsf{fold}(\mathbf{G},u^{-1})\rangle$ है या नहीं।

हम पाठक के लिए यह अभ्यास (exercise) के रूप में छोड़ते हैं कि वह एक उदाहरण पर काम करके जाँचे कि क्या अंतिम सत्यापन जाँच (verification check) बीजगणितीय रूप से (algebraically) समान है यदि prover ईमानदार था। हम $n=4$ जैसे छोटे उदाहरण का उपयोग करने का सुझाव देते हैं।

$\mathsf{fold}$ की एक और व्याख्या (interpretation)

$P$ basis vector $\mathbf{G}$ के संबंध में original vector $\mathbf{a}$ के लिए एक commitment है। $L$ pairwise outer products के left off-diagonals से बने vector के लिए एक commitment है और $R$ pairwise outer products के right off-diagonals के components के लिए एक commitment है।

योग $Lu^2 + P + Ru^{-2}$ स्वयं basis $\mathsf{fold}(\mathbf{G}, u^{-1})$ पर vector $\mathsf{fold}(\mathbf{a},u)$ का एक vector commitment है, जिसका आकार $n/2$ है।

हम नीचे graphically इस संबंध को दिखाते हैं:

$n/2$ आकार के commitment की opening को जानने का प्रमाण देने के लिए, हम बस $n/2$ आकार का vector भेज सकते हैं, जो इस मामले में $\mathsf{fold}(\mathbf{a},u)$ है।

इस व्याख्या का उपयोग करते हुए, algorithm निम्नलिखित कार्य कर रहा है:

1. Prover $A = \langle\mathbf{a},\mathbf{G}\rangle$, $L$, और $R$ भेजता है।
2. Verifier $u$ भेजता है।
3. अब verifier के पास basis vector $\mathsf{fold}(\mathbf{G},u^{-1})$ के संबंध में एक commitment $A' = Lu^2 + A + Ru^{-2}$ है।
4. Prover $\mathbf{a}' =\mathsf{fold}(\mathbf{a}, u)$ भेजकर यह साबित करता है कि वे $A'$ की opening जानते हैं।

Verification गति (speed) की सीमाएँ

चूँकि verifier को $\mathsf{fold}(\mathbf{G}, u^{-1})$ की गणना करने की आवश्यकता होती है, इसलिए पूरे $\mathbf{G}$ vector पर iterate करने की आवश्यकता होगी, जिसमें $\mathcal{O}(n)$ समय लगेगा। हालाँकि proof का आकार मूल (original) vectors से छोटा हो सकता है, लेकिन proof को verify करने में अभी भी linear time लगेगा।

सारांश (Summary)

हमने दिखाया है कि कैसे prover केवल $n/2$ elements ($\mathbf{a}$ folded) भेजते हुए यह दिखा सकता है कि वे एक Pedersen vector commitment $A$ की opening जानते हैं।

अगले अध्याय में, हम दिखाएंगे कि इस algorithm को recursively कैसे apply किया जाए ताकि prover केवल $\mathcal{O}(\log n)$ elements भेजे।

Exercise: इस अध्याय में वर्णित algorithm को implement करें। निम्नलिखित कोड को शुरुआती बिंदु (starting point) के रूप में उपयोग करें:

Copy
from py_ecc.bn128 import G1, multiply, add, FQ, eq, Z1
from py_ecc.bn128 import curve_order as p
import numpy as np
from functools import reduce
import random

def random_element():
    return random.randint(0, p)

def add_points(*points):
    return reduce(add, points, Z1)

# if points = G1, G2, G3, G4 and scalars = a,b,c,d vector_commit returns
# aG1 + bG2 + cG3 + dG4
def vector_commit(points, scalars):
    return reduce(add, [multiply(P, i) for P, i in zip(points, scalars)], Z1)

# these EC points have unknown discrete logs:
G_vec = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
     (FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
     (FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
     (FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]

# return a folded vector of length n/2 for scalars
def fold(scalar_vec, u):
    pass
    # your code here

# return a folded vector of length n/2 for points
def fold_points(point_vec, u):
    pass
    # your code here

# return L, R as a tuple
def compute_secondary_diagonal(G_vec, a):
    pass
    # your code here

a = [9,45,23,42]

# prover commits
A = vector_commit(G_vec, a)
L, R = compute_secondary_diagonal(G_vec, a)

# verifier computes randomness
u = random_element()

# prover computes fold(a)
aprime = fold(a, u)

# verifier computes fold(G)
Gprime = fold_points(G_vec, pow(u, -1, p))

# verification check
assert eq(vector_commit(Gprime, aprime), add_points(multiply(L, pow(u, 2, p)), A, multiply(R, pow(u, -2, p)))), "invalid proof"
assert len(Gprime) == len(a) // 2 and len(aprime) == len(a) // 2, "proof must be size n/2"