रेंज प्रूफ

Last updated on Nov 20, 2024

इनर प्रोडक्ट आर्गुमेंट्स के संदर्भ में एक रेंज प्रूफ (range proof) यह प्रमाण है कि स्केलर $v$ को $V$ पर कमिट किया गया है और $v$ किसी गैर-ऋणात्मक पूर्णांक $n$ के लिए $2^n$ से कम है।

यह लेख दिखाता है कि Bulletproofs पेपर इस तरह का प्रमाण कैसे बनाता है। इसका उच्च-स्तरीय विचार यह है कि यदि हम यह साबित कर सकें कि एक वेक्टर $\mathbf{a}_L$ में केवल एक और शून्य (ones and zeros) हैं और $\mathbf{a}_L$ , $v$ का बाइनरी रिप्रजेंटेशन है, तो $v$ निश्चित रूप से $2^n$ से कम होना चाहिए। यह यह कहने के समान है कि 8 बिट अनसाइन्ड इंटीजर (unsigned integer) में फिट होने वाली संख्या 256 से कम होनी चाहिए।

रेंज प्रूफ के लिए Bulletproofs का उपयोग करने का फायदा यह है कि बिना arithmetic circuit की आवश्यकता के सीधे रेंज प्रूफ का निर्माण किया जा सकता है।

Monero uses Bulletproof Range Proofs (यहाँ प्रस्तुत एल्गोरिथम) यह सुनिश्चित करने के लिए कि ट्रांज़ैक्शन का योग ऋणात्मक नहीं है (एक finite field में, ऋणात्मक संख्याएँ वे तत्व हैं जो $p/2$ से अधिक हैं क्योंकि वे $p/2$ से कम या उसके बराबर के तत्वों के एडिटिव इन्वर्स (additive inverses) हैं जहाँ $p$ फील्ड ऑर्डर है)।

यह लेख ZK Bulletproofs पर एक श्रृंखला का हिस्सा है।

Notation

$\mathbf{0}^n$ सभी शून्य वाला एक $n$ डायमेंशनल वेक्टर है।

$\mathbf{1}^n$ सभी एक (ones) वाला एक $n$ डायमेंशनल वेक्टर है।

$\mathbf{2}^n$ एक $n$ डायमेंशनल वेक्टर $[1,2,4,8,...,2^{n-1}]$ है।

$\mathbf{y}^n$ एक $n$ डायमेंशनल वेक्टर $[1, y, y^2, y^3, ..., y^{n-1}]$ है।

$\mathbf{y}^{-n}$ एक $n$ डायमेंशनल वेक्टर $[1, y^{-1}, y^{-2}, ..., y^{-(n-1)}]$ है।

ध्यान दें कि $\mathbf{y}^n\circ\mathbf{y}^{-n}=\mathbf{1}^n$ है।

Range proof overview

यह साबित करने के लिए कि $V$ एक ऐसे स्केलर का कमिटमेंट है जिसका मान $2^n$ से कम है, निम्नलिखित साबित करने की आवश्यकता है:

$\mathbf{a}_L$ बाइनरी है (केवल $0$ और $1$ मान रखता है)।
इनर प्रोडक्ट $\langle \mathbf{a}_L,\mathbf{2}^n\rangle=v$ है।

दूसरे बिंदु को साबित करना आसान है, हम एक सामान्य इनर प्रोडक्ट प्रूफ करते हैं और फिर प्रकट करते हैं कि $\mathbf{2}^n$ कमिटमेंट के वेक्टर्स में से एक है – या वेरिफायर (verifier) से स्वयं $\mathbf{2}^n$ का कमिटमेंट बनाने के लिए कहते हैं। हालांकि, बिना एरिथमेटिक सर्किट के यह साबित करने के लिए कि $\mathbf{a}_L$ बाइनरी है, कुछ अलजेब्रिक ट्रिक्स (algebraic tricks) की आवश्यकता होती है।

Four useful tricks

Bulletproofs पेपर स्पष्ट रूप से चार अलजेब्रिक ट्रिक्स का उपयोग करता है जिन्हें सीधे रेंज प्रूफ एल्गोरिथम देखने से पहले स्पष्ट रूप से समझना सबसे अच्छा है।

1. Proving $\mathbf{a}_L$ is binary

यह कथन कि $\mathbf{a}_L$ बाइनरी है, निम्नलिखित दो दावों के समतुल्य है:

$\mathbf{a}_R = \mathbf{a}_L-\mathbf{1}^n$
$\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n$

उदाहरण के लिए, यदि $\mathbf{a}_L = [1,0,0,1]$ है तो $\mathbf{a}_R=[0,-1,-1,0]$ होगा।

इस मामले में, $\mathbf{a}_L \circ\mathbf{a}_R=\mathbf{0}^n$ है क्योंकि

[1,0,0,1] \circ [0,-1,-1,0] = [0,0,0,0] = \mathbf{0}^n

अब एक ऐसे मामले पर विचार करें जहाँ $\mathbf{a}_L$ बाइनरी नहीं है, उदाहरण के लिए $[2, 1, 0, 0]$ । $\mathbf{a}_R$ , $[1,0,-1,-1]$ होगा। $\mathbf{a}_L$ और $\mathbf{a}_R$ का हैडामर्ड प्रोडक्ट (Hadamard product) $[2,0,0,0] \neq \mathbf{0}^n$ होगा।

अधिक सामान्यतः, यदि $\mathbf{a}_L$ में कोई गैर-बाइनरी प्रविष्टि है, तो उस प्रविष्टि से $1$ घटाया जाएगा, और $\mathbf{a}_R$ में परिणामी प्रविष्टि गैर-शून्य होगी। जब हैडामर्ड प्रोडक्ट की गणना की जाती है, तो उस विशेष इंडेक्स पर, $\mathbf{a}_L$ और $\mathbf{a}_R$ दोनों गैर-शून्य होंगे और प्रोडक्ट गैर-शून्य होगा, जिसका अर्थ है $\mathbf{a}_L \circ \mathbf{a}_R \neq \mathbf{0}^n$ ।

हालांकि, यदि $\mathbf{a}_L$ में एक विशेष प्रविष्टि $1$ है, तो उस इंडेक्स पर $\mathbf{a}_R$ , $0$ होगा ताकि उस इंडेक्स पर हैडामर्ड प्रोडक्ट भी शून्य हो जाए।

अंत में, यदि $\mathbf{a}_L$ में एक विशेष प्रविष्टि $0$ है, तो उस इंडेक्स पर $\mathbf{a}_R$ , $-1$ होगा और उनका एलिमेंट-वाइज़ प्रोडक्ट उस इंडेक्स पर भी शून्य ही रहेगा।

इसलिए, यदि $\mathbf{a}_L$ बाइनरी है और $\mathbf{a}_R$ की गणना $\mathbf{a}_R = \mathbf{a}_L-\mathbf{1}$ के रूप में की जाती है, तो $\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n$ होगा।

2. Proving a vector is all zero

मान लीजिए कि हम यह साबित करना चाहते हैं कि पेडरसन कमिटमेंट (Pedersen commitment) $A$ एक शून्य वेक्टर रखता है। हम पेडरसन कमिटमेंट $A = \langle\mathbf{a},\mathbf{G}\rangle + \alpha B$ बनाते हैं और एक वेरिफायर को यह साबित करना चाहते हैं कि $\mathbf{a}=\mathbf{0}^n$ है।

ऐसा लग सकता है कि केवल ब्लाइंडिंग टर्म (blinding term) $\alpha$ भेजना पर्याप्त है, लेकिन हमारे समाधान को अधिक कंपोजेबल (composable) बनाने के लिए, हम ब्लाइंडिंग टर्म को प्रकट नहीं करना चाहते हैं क्योंकि यह हमारे द्वारा बनाए गए अन्य कमिटमेंट्स को प्रभावित कर सकता है।

इसके बजाय, प्रूवर (prover) $A$ को वेरिफायर को भेजता है, और वेरिफायर रैंडम मानों से भरे एक वेक्टर $\mathbf{r}$ के साथ प्रतिक्रिया देता है। प्रूवर को अब यह साबित करना होगा कि

\langle\mathbf{a},\mathbf{r}\rangle = 0

ध्यान दें कि यह एक प्रॉबेबिलिस्टिक टेस्ट (probabilistic test) है। यह नगण्य संभावना (negligible probability) के साथ संभव है कि $\mathbf{a}\neq\mathbf{0}^n$ के लिए $\langle\mathbf{a},\mathbf{r}\rangle=0$ हो, लेकिन प्रूवर के लिए ऐसा $\mathbf{a}$ बनाना संभव नहीं है क्योंकि वे पहले से नहीं जानते कि $\mathbf{r}$ क्या होगा।

हालांकि, $\mathbf{r}$ को ट्रांसमिट करने के लिए $\mathcal{O}(n)$ कम्युनिकेशन ओवरहेड की आवश्यकता होती है, इसलिए वेरिफायर केवल एक सिंगल रैंडम एलिमेंट $y$ भेजता है और प्रूवर $\mathbf{y}^n$ की गणना करता है और $\mathbf{y}^n$ का उपयोग रैंडम वेक्टर के रूप में करता है।

तब, प्रूवर साबित करता है कि $\langle\mathbf{a},\mathbf{y}^n\rangle=0$ है।

3. Proving an inner product is of the form $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle$ where $y$ is chosen by the verifier and the prover computes $\mathbf{y}^n$

हमारे पास अभी तक यह साबित करने का कोई तंत्र नहीं है कि $\mathbf{a}_L\circ\mathbf{a}_R=\mathbf{0}^n$ , क्योंकि यह एक हैडामर्ड प्रोडक्ट है, इनर प्रोडक्ट नहीं। हालांकि, यह कहना कि वेक्टर $\mathbf{a}_L\circ\mathbf{a}_R$ पूरी तरह से $\mathbf{0}^n$ है, यह कहने के समान है कि $\langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=0$ है। इनर प्रोडक्ट नियमों के अनुसार, हम $\mathbf{a}_R$ को इनर प्रोडक्ट के दूसरी तरफ ले जा सकते हैं और अब हमारे पास $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=0$ है।

वेरिफायर को $\mathbf{a}_L$ और $\mathbf{a}_R$ के कमिटमेंट्स प्राप्त होंगे, न कि $\mathbf{a}_R\circ\mathbf{y}^n$ के। यह वेरिफायर पर निर्भर करेगा कि वह $\mathbf{a}_R\circ\mathbf{y}^n$ का एक कमिटमेंट बनाए ताकि उन्हें यकीन हो जाए कि प्रूवर ने इनर प्रोडक्ट में दूसरे वेक्टर के रूप में $\mathbf{a}_R\circ\mathbf{y}^n$ का उपयोग किया है।

हम जिस मुख्य ट्रिक पर निर्भर करते हैं वह यह है कि प्रूवर अपने वेक्टर्स को कमिट करने के लिए बेसिस वेक्टर्स (basis vectors) $\mathbf{G}$ और $\mathbf{H}$ का उपयोग करता है, लेकिन वेरिफायर $\mathbf{G}$ और $\mathbf{H}\circ\mathbf{y}^{-n}$ का उपयोग करता है।

जब प्रूवर मूल्यांकन $\mathbf{r}_u$ भेजता है, तो प्रूवर को यह सुनिश्चित करना होगा कि $\mathbf{y}^n$ टर्म्स वेरिफायर के बेसिस वेक्टर $\mathbf{y}^{-n}\circ\mathbf{H}$ में $\mathbf{y}^{-n}$ के साथ रद्द (cancel) हो जाएंगे।

विशेष रूप से, प्रूवर निम्नलिखित कमिटमेंट्स का निर्माण करता है:

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

और वेरिफायर को $(A, S)$ भेजता है। $V$ को कमिट करके भेजने की कोई आवश्यकता नहीं है क्योंकि इस मामले में यह शून्य है।

प्रूवर के पॉलिनॉमियल्स (polynomials) होंगे:

\begin{align*} \mathbf{l}(x)&=\mathbf{a}_L + \mathbf{s}_Lx\\ \mathbf{r}(x)&=\mathbf{a}_R\circ\mathbf{y}^n + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x \end{align*}

महत्वपूर्ण रूप से, प्रूवर ने $\mathbf{s}_R$ को $\mathbf{y}^n$ से हैडामर्ड गुणा किया है। पहले, $\mathbf{r}(x)$ की गणना $\mathbf{r}(x)=\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{s}_Rx$ (बिना $\mathbf{y}^n\circ\mathbf{s}_R$ के) के रूप में की जाती थी। यह बाद में सभी $\mathbf{y}^n$ टर्म्स को रद्द करने की अनुमति देगा जब वेरिफायर कमिटमेंट $\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle$ की गणना करेगा। आंतरिक रूप से (Under the hood), $\mathbf{r}_u$ , $(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n$ है, इसलिए जब वेरिफायर $\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle$ की गणना करेगा तो $\mathbf{y}^n$ रद्द हो जाएगा, यानी:

\begin{align*} &\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle\\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{y}^n\circ\mathbf{y}^{-n}\circ\mathbf{H}\rangle\\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{1}^n\circ\mathbf{H}\rangle\\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{H}\rangle \end{align*}

हालांकि, प्रूवर अभी तक $\mathbf{l}(x)$ या $\mathbf{r}(x)$ की गणना नहीं कर सकता है क्योंकि वेरिफायर ने अभी तक $y$ नहीं भेजा है। इसलिए, $(A, S)$ प्राप्त करने के बाद वेरिफायर $y$ भेजता है और प्रूवर $\mathbf{y}^n$ की गणना करता है और पॉलिनॉमियल $t(x)$ की गणना करता है:

t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle=\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle+t_1x+t_2x^2

जहाँ

\begin{align*} t_1&=\langle\mathbf{a}_L,\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle\\ t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y} ^n\rangle \end{align*}

प्रूवर कोएफिशिएंट्स $t_1$ और $t_2$ पर कमिट करता है:

\begin{align*} T_1&=t_1G+\tau_1B\\ T_2&=t_2G+\tau_2B \end{align*}

और $(T_1, T_2)$ वेरिफायर को भेजता है। वेरिफायर $u$ के साथ प्रतिक्रिया देता है और प्रूवर वेक्टर पॉलिनॉमियल्स $\mathbf{l}(x)$ और $\mathbf{r}(x)$ का मूल्यांकन करता है:

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

ध्यान दें कि $\pi_t$ में केवल $t_1$ और $t_2$ के ब्लाइंडिंग टर्म्स शामिल हैं। पिछले इम्प्लीमेंटेशन में, $\pi_t$ की गणना $\gamma + \tau_1u+\tau_2u^2$ के रूप में की गई थी, जहाँ $\gamma$ , $V$ के लिए ब्लाइंडिंग टर्म है, जो पॉलिनॉमियल $t(x)$ का कांस्टेंट कोएफिशिएंट भी है।

कोई ब्लाइंडिंग टर्म $\gamma$ नहीं है क्योंकि $V$ के लिए कोई कमिटमेंट नहीं है, यानी $v$ गुप्त नहीं है – यह $0$ है। प्रूवर $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$ भेजता है और वेरिफायर यह जांचता है कि:

\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{y}^{-n}\circ\mathbf{H}\rangle+\pi_{lr}B\\ t_uG&\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B\\ \end{align*}

पहला महत्वपूर्ण अंतर यह है कि $\mathbf{r}_u$ का कमिटमेंट पहले चर्चा किए गए कारणों से $\mathbf{H}$ के बजाय बेसिस वेक्टर $\mathbf{y}^{-n}\circ\mathbf{H}$ के संबंध में किया जाता है।

दूसरा, $t_uG\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B$ में कोई कांस्टेंट कमिटमेंट नहीं है। आम तौर पर, समीकरण $t_uG\stackrel{?}{=} \boxed{V}+T_1 u + T_2 u^2 - \pi_t B$ होता है, लेकिन इस मामले में $V$ , $0$ का कमिटमेंट है।

सामान्य रूप से, यदि $V$ में ऐसे मान शामिल हैं जो वेरिफायर को ज्ञात हैं, तो वेरिफायर $V$ के कमिटमेंट का निर्माण कर सकता है जैसा कि हम अगले अनुभाग में दिखाएंगे।

4. Proving an inner product when an additive public constant is involved

जैसा कि ऊपर के अनुभाग में संकेत दिया गया है, वेरिफायर कमिटमेंट्स का पुनर्निर्माण कर सकता है यदि वेरिफायर अंडरलाइंग (underlying) वेक्टर को जानता है।

उदाहरण के लिए, मान लीजिए कि हम यह साबित कर रहे हैं कि

$\langle\mathbf{a}_L + \mathbf{j},\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}\rangle=vz$

जहाँ $\mathbf{j}$ और $\mathbf{k}$ वेरिफायर को ज्ञात वेक्टर्स हैं और $z$ एक स्केलर है जो वेरिफायर को पहले से ज्ञात है। $\mathbf{y}^n$ के विपरीत, ये वेक्टर्स और स्केलर प्रमाण शुरू होने से पहले ही ज्ञात होते हैं। ध्यान दें कि इस उदाहरण में $\mathbf{k}$ को $\mathbf{y}^n$ से हैडामर्ड गुणा नहीं किया गया है।

प्रूवर हमेशा की तरह केवल गुप्त मानों $\mathbf{a}_L$ , $\mathbf{a}_R$ और $v$ पर कमिट करता है:

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

हमेशा की तरह, पॉलिनॉमियल्स $\mathbf{l}(x)$ और $\mathbf{r}(x)$ ऐसे हैं कि कांस्टेंट टर्म मूल इनर प्रोडक्ट का वेक्टर है और लीनियर टर्म्स $\mathbf{s}_L$ और $\mathbf{s}_R$ हैं। वेरिफायर से $y$ प्राप्त करने पर, प्रूवर $\mathbf{y}^n$ की गणना करता है और $\mathbf{l}(x)$ और $\mathbf{r}(x)$ बनाता है लेकिन उनका मूल्यांकन नहीं करता है:

\begin{align*} \mathbf{l}(x)&=\underbrace{\mathbf{a}_L + \mathbf{j}}_\text{left vector} + \mathbf{s}_Lx\\ \mathbf{r}(x)&=\underbrace{\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}}_\text{right vector} + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x \end{align*}

ध्यान दें कि $\mathbf{k}$ को $\mathbf{y}^n$ के साथ हैडामर्ड गुणा नहीं किया गया है, लेकिन लीनियर टर्म $\mathbf{s}_R$ के साथ किया गया है। हम बाद में दिखाएंगे कि वेरिफायर इसे कैसे हैंडल करता है।

अभी के लिए, हम $t(x)$ की गणना इस प्रकार करते हैं:

t(x)=vz+t_1x+t_2x^2

जहाँ

\begin{align*} t_1&=\langle\mathbf{a}_L+\mathbf{j},\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}\rangle\\ t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y} ^n\rangle \end{align*}

ध्यान दें कि $t(x)$ में कांस्टेंट टर्म $vz$ है न कि $v$ । कमिटमेंट्स की गणना इस प्रकार की जाती है:

\begin{align*} T_1 &= t_1G+\tau_1B\\ T_2 &= t_2G+\tau_2B\\ \end{align*}

और इन्हें वेरिफायर को भेजा जाता है जो फिर रैंडम मान $u$ भेजता है।

प्रूवर गणना करता है:

\begin{align*} \mathbf{l}_u&= \mathbf{a}_L\circ\mathbf{y}^n+\mathbf{j}+(\mathbf{s}_L\circ\mathbf{y}^n)u\\ \mathbf{r}_u&= \mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}+\mathbf{s}_Ru\\ t_u&=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ \pi_{lr}&=\alpha + \beta u\\ \pi_t&=vz+\tau_1u+\tau_2u^2 \end{align*}

ध्यान दें कि $\pi_t$ में कांस्टेंट टर्म $\gamma z$ है। प्रूवर $(\mathbf{l}_u,\mathbf{r}_u,t_u,\pi_{lr},\pi_t)$ भेजता है। अंत में, वेरिफायर गणना करता है:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A+Su+\underbrace{\langle\mathbf{j,\mathbf{G}}\rangle}_{\text{commitment to } \mathbf{j} \text{ in } \mathbf{l}(x)}+\underbrace{\langle\mathbf{k},\mathbf{y}^{-n}\circ\mathbf{H}\rangle}_{\text{commitment to } \mathbf{k} \text{ in } \mathbf{r}(x)}&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle+\pi_{lr}B\\ t_uG&\stackrel{?}{=} Vz+ T_1 u + T_2 u^2 - \pi_t B\\ \end{align*}

$\mathbf{l}_u$ और $\mathbf{r}_u$ में क्रमशः $\mathbf{j}$ और $\mathbf{k}$ शामिल हैं, लेकिन $A$ और $S$ में नहीं। इसलिए, वेरिफायर उन वेक्टर्स के लिए कमिटमेंट्स की गणना करता है और उन्हें कमिटमेंट्स $A$ और $S$ में जोड़ता है। $\mathbf{k}$ के मामले में, बेसिस वेक्टर $\mathbf{y}^{-n}\circ\mathbf{H}$ , $\mathbf{k}$ को $\mathbf{k}\circ\mathbf{y}^{-n}$ बना देगा, इसलिए कमिटमेंट की गणना $\mathbf{y}^{-n}\circ\mathbf{H}$ के संबंध में की जानी चाहिए। अंत में, ब्लाइंडिंग टर्म $\pi_t$ में $vz$ शामिल है लेकिन $V$ में $z$ शामिल नहीं है। इसलिए, प्रूवर को $V$ को $z$ से गुणा करना होगा।

$\langle\mathbf{j},\mathbf{G}\rangle$ , $\langle\mathbf{k},\mathbf{y}^n\circ\mathbf{H}\rangle$ और $Vz$ की गणना करके, वेरिफायर सुनिश्चित हो सकता है कि इनर प्रोडक्ट गणना में वास्तव में वे टर्म्स शामिल थे।

Range proof

यह साबित करने के लिए कि $V$ एक मान है जो $2^n$ से कम है, हमें तीन चीजें साबित करनी होंगी:

इनर प्रोडक्ट $\langle \mathbf{a}_L,\mathbf{2}^n\rangle = V$ , यानी $\mathbf{a}_L$ , $v$ का बाइनरी रिप्रजेंटेशन है
$\mathbf{a}_R=\mathbf{a}_L-\mathbf{1}$
$\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}$

अंतिम दो दावे सीधे इनर प्रोडक्ट के रूप में नहीं हैं। हालांकि, इसे प्राप्त करने के लिए हम उन्हें थोड़ा संशोधित कर सकते हैं। हम वास्तव में यह कह रहे हैं कि वेक्टर्स:

$\mathbf{a}_R - \mathbf{a}_L+\mathbf{1}$
$\mathbf{a}_L\circ\mathbf{a}_R$

दोनों $\mathbf{0}^n$ हैं। यह साबित करने के लिए कि वे शून्य हैं, हम पिछले अनुभाग की ट्रिक का उपयोग कर सकते हैं। अर्थात, प्रूवर को यह स्थापित करने की आवश्यकता है कि

\langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}

और

\langle \mathbf{a}_R - \mathbf{a}_L+\mathbf{1},\mathbf{y}^n\rangle=\mathbf{0}

जहाँ $\mathbf{y}^n$ वेरिफायर द्वारा भेजे गए $y$ मान से प्राप्त रैंडम वेक्टर है।

मूल बुलेटप्रूफ्स (Bulletproofs) पेपर पहले दावे को थोड़ा इस प्रकार संशोधित करता है ताकि हम पिछले अनुभाग में तीसरी ट्रिक का उपयोग कर सकें:

\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}

इसलिए, प्रूवर को स्थापित करने के लिए तीन इनर प्रोडक्ट्स हैं:

$\langle \mathbf{a}_L,\mathbf{2}^n\rangle = v$
$\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}^n$
$\langle\mathbf{a}_L -\mathbf{1}^n- \mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}^n$

Combining three inner products into one

इन तीन इनर प्रोडक्ट्स को वेरिफायर द्वारा प्रदान किए गए रैंडमनेस $z$ के साथ एक रैंडम लीनियर कॉम्बिनेशन का उपयोग करके एक में मिलाया जा सकता है।

z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z^1 \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + z^0\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v + z^1\cdot\mathbf{0}^n+z^0\cdot\mathbf{0}^n

z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v

कुछ भारी इनर प्रोडक्ट अलजेब्रा के साथ, हम सभी इनर प्रोडक्ट्स को इस प्रकार मिला सकते हैं। हम परिशिष्ट (appendix) में डेरिवेशन दिखाते हैं।

\left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + (z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle

नीचे बॉक्स किए गए टर्म्स में वेरिफायर को ज्ञात मान होते हैं, इसलिए हम स्पष्ट रूप से उन मानों की जांच करने के लिए अपने वेरिफिकेशन एल्गोरिथम का निर्माण करेंगे। अर्थात, वेरिफायर बॉक्स किए गए टर्म्स में मानों के लिए कमिटमेंट्स की गणना करेगा, न कि प्रूवर:

\left\langle \mathbf{a_L} - \boxed{z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{(z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle}

जगह बचाने के लिए, Bulletproofs पेपर टर्म $(z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle$ को $\delta(y,z)$ के रूप में संदर्भित करता है, इसलिए इनर प्रोडक्ट को इस प्रकार लिखा जा सकता है:

\left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z)

ध्यान दें कि $\delta(y,z)$ एक ऐसा मान है जिसकी गणना वेरिफायर कर सकता है।

Range Proof Algorithm

प्रूवर $v$ और इसके बाइनरी रिप्रजेंटेशन $\mathbf{a}_L$ को चुनता है और $\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}$ की गणना करता है।

प्रूवर फिर रैंडम रूप से ब्लाइंडिंग टर्म $\alpha$ चुनता है और बेसिस वेक्टर्स $\mathbf{G}$ और $\mathbf{H}$ का उपयोग करके $\mathbf{a}_L$ और $\mathbf{a}_R$ के संयुक्त कमिटमेंट की गणना इस प्रकार करता है:

A = \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B

प्रूवर फिर जल्द ही बनने वाले वेक्टर पॉलिनॉमियल्स $\mathbf{l}(x)$ और $\mathbf{r}(x)$ के लीनियर टर्म्स को $\mathbf{s}_L$ और $\mathbf{s}_R$ के रूप में चुनता है और उन्हें कमिट करता है:

S = \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B

प्रूवर $V$ के इनर प्रोडक्ट को $G$ के संबंध में एक अज्ञात डिस्क्रीट लॉग (अज्ञात बेस) (जो $\mathbf{G}$ से असंबंधित है) के साथ कमिट करता है:

V = vG+\gamma B

प्रूवर वेरिफायर को $(A, S, V)$ भेजता है।

वेरिफायर रैंडम मानों $(y, z)$ के साथ प्रतिक्रिया देता है जिसका उपयोग प्रूवर तीन इनर प्रोडक्ट्स को एक में मिलाने के लिए करेगा।

\left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z)

इनर प्रोडक्ट का बायां भाग $\mathbf{a}_L-z\cdot\mathbf{1}$ , $\mathbf{l}(x)$ का कांस्टेंट टर्म होगा और $\mathbf{y}^n \circ\mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ , $\mathbf{r}(x)$ का कांस्टेंट टर्म होगा।

इस प्रकार, हम $\mathbf{l}(x)$ का निर्माण इस प्रकार करते हैं:

\mathbf{l}(x)=\underbrace{\mathbf{a}_L-z\cdot\mathbf{1}}_\text{constant term}+\mathbf{s}_Lx

और हम $\mathbf{r}(x)$ का निर्माण इस प्रकार करते हैं:

\mathbf{r}(x)=\underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n}_\text{constant term}+\mathbf{y}^n\circ\mathbf{s}_Rx

ध्यान दें कि हमने ऊपर Prerequisites अनुभाग के भाग 3 में चर्चा किए गए कारणों से $\mathbf{s}_Rx$ को $\mathbf{y}^n$ के साथ एलिमेंट-वाइज़ गुणा किया है।

प्रूवर अब कांस्टेंट कोएफिशिएंट $t_0$ , लीनियर कोएफिशिएंट $t_1$ और क्वाड्रैटिक कोएफिशिएंट $t_2$ के साथ $t(x) = \langle\mathbf{l}(x),\mathbf{r}(x)\rangle$ का निर्माण इस प्रकार कर सकता है:

\begin{align*} t_0 &= \left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle\\ t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\\ t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle \end{align*}

जहाँ $t(x) = t_0 + t_1x + t_2x^2$ है।

प्रूवर $t_1$ और $t_2$ के कमिटमेंट्स इस प्रकार भेजता है:

\begin{align*} T_1 &= t_1G+\tau_1B\\ T_2 &= t_2G+\tau_2B \end{align*}

$t_0$ पर कमिट करने की कोई आवश्यकता नहीं है – ध्यान दें कि यह ठीक वही इनर प्रोडक्ट है जिसे हम साबित करने का प्रयास कर रहे हैं, इसलिए वेरिफायर के पास पहले से ही $V$ के रूप में कमिटमेंट है।

वेरिफायर रैंडमनेस $u$ भेजता है और प्रूवर गणना करता है:

\begin{align*} \mathbf{l}_u &= \mathbf{l}(u) \\ \mathbf{r}_u &= \mathbf{r}(u) \\ t_u &= \mathbf{t}(u)\\ \pi_{lr} &=\alpha+\beta u\\ \pi_t &= z^2\gamma + \tau_1u + \tau_2u^2\\ \end{align*}

ध्यान दें कि $\pi_t$ के कांस्टेंट टर्म को मूल इनर प्रोडक्ट के $z^2\cdot v$ टर्म को दर्शाने के लिए $z^2$ से गुणा किया जाता है।

वेरिफायर तब एक नया बेसिस वेक्टर $\mathbf{H}_{\mathbf{y}^{-1}}=\mathbf{y}^{-n}\circ\mathbf{H}$ की गणना करता है और निम्नलिखित चेक्स चलाता है:

$t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle$

$A + Su + \boxed{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \boxed{\langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B$

$t_uG+\pi_tB=V\boxed{z^2}+\boxed{\delta(y,z)}\cdot G+T_1u+T_2u^2$

याद करें कि प्रूवर ने इनर प्रोडक्ट के बाएँ और दाएँ पक्ष के लिए उपयोग किए गए संपूर्ण वेक्टर्स को कमिट नहीं किया था, बल्कि केवल $\mathbf{a}_L$ और $\mathbf{b}_L$ को कमिट किया था। बाकी वेक्टर्स एडिटिव पब्लिक वेक्टर्स (additive public vectors) थे जो वेरिफायर को ज्ञात थे, इसलिए वेरिफायर ने कांस्टेंट टर्म्स के कमिटमेंट्स का निर्माण करके और उन्हें प्रूवर द्वारा आपूर्ति किए गए गुप्त वेक्टर्स के कमिटमेंट में जोड़कर वेक्टर्स के कमिटमेंट्स का पुनर्निर्माण किया।

याद दिलाने के लिए, यहाँ वेरिफायर को ज्ञात मानों के बॉक्स के साथ मूल इनर प्रोडक्ट दिया गया है:

\left\langle \mathbf{a_L} + \boxed{-z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{\delta(y,z)}

पाठकों को यह वेरिफाई करने के लिए प्रोत्साहित किया जाता है कि मूल प्रोडक्ट में बॉक्स किए गए टर्म्स (वेरिफायर को ज्ञात मान) को ऊपर दिए गए समानता चेक्स (equality checks) के सेट में बॉक्स किए गए टर्म्स में वेरिफायर द्वारा फिर से बनाया गया था।

प्रूवर की गणना के एक हिस्से को दोहराकर, वेरिफायर यह सुनिश्चित करता है कि प्रूवर ने वास्तव में दावा की गई गणना की है।

Correctness of the verification algorithm

अब हम दिखाते हैं कि यदि प्रूवर ईमानदार था, तो अंतिम वेरिफिकेशन चेक्स पूरी तरह से सही हैं।

नीचे हम सटीक अलजेब्रा दिखाते हैं, लेकिन सहज रूप से वेरिफायर इनर प्रोडक्ट $\mathbf{a_L} - z \cdot \mathbf{1}^n$ में लेफ्ट वेक्टर, इनर प्रोडक्ट $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ में राइट वेक्टर और आउटपुट $z^2v+\delta(y,z)$ का “पुनर्निर्माण” कर रहा है।

वेरिफायर को $\mathbf{a_L} - z \cdot \mathbf{1}^n$ और $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ के कमिटमेंट्स नहीं दिए गए हैं बल्कि $\mathbf{a}_L$ और $\mathbf{a}_R$ के दिए गए हैं। इसी तरह, वेरिफायर को आउटपुट $z^2v + \delta(y,z)$ का कमिटमेंट नहीं दिया गया है बल्कि केवल $v$ का दिया गया है।

एडिटिव टर्म्स और $\mathbf{y}^n$ द्वारा एलिमेंट-वाइज़ गुणा किए गए टर्म्स को वेरिफायर द्वारा फिर से बनाया जाना चाहिए।

Correctness of $t_u = \mathbf{t}(u)$

$t_u\stackrel{?} =\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ चेक के लिए, यह परिभाषा के अनुसार सत्य है, क्योंकि प्रूवर ने $t_u$ की गणना इसी तरह की है।

Correctness of the committed $\mathbf{l}(x)$ and $\mathbf{r}(x)$ with respect to $A$ and $S$

के लिए:
$A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B$

हम निम्नलिखित प्रतिस्थापन (substitution) करते हैं:

$\underbrace{\langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B}_A + \underbrace{(\langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)}_Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \underbrace{\mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_Lu}_{\mathbf{l}_u}, \mathbf{G} \rangle + \langle \underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_Rx}_{\mathbf{r}_u}, \mathbf{H}_{y^{-1}} \rangle + \underbrace{(\alpha+\beta u)}_{\pi_{lr}} B$

सभी $\mathbf{G}$ टर्म्स इस प्रकार रद्द हो जाते हैं:

$\cancel{\langle\mathbf{a}_L,\mathbf{G}\rangle}+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\cancel{\langle\mathbf{s}_L,\mathbf{G}\rangle}+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \cancel{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_L u, \mathbf{G} \rangle} + \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B$

$\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B$

$B$ से संबंधित ब्लाइंडिंग टर्म्स इस प्रकार रद्द हो जाते हैं:

$\langle\mathbf{a}_R,\mathbf{H}\rangle+\cancel{\alpha B} + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\cancel{\beta B)u} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + \cancel{(\alpha+\beta u) B}$

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R u, \mathbf{H}_{y^{-1}} \rangle$

$\mathbf{H}_{y^{-1}}$ , $\mathbf{y}^n$ टर्म्स के साथ रद्द हो जाता है:

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R+z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle$

इनर प्रोडक्ट्स को अलग करें:

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R,\mathbf{H}\rangle+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle$

उन टर्म्स को रद्द करें जो समीकरण के दोनों ओर दिखाई देते हैं:

\cancel{\langle\mathbf{a}_R,\mathbf{H}\rangle} + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_R,\mathbf{H}\rangle}+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle

\cancel{(\langle\mathbf{s}_R,\mathbf{H}\rangle u)} + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\cancel{\langle\mathbf{s}_R u, \mathbf{H} \rangle}

\langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle} \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}

\langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle

$\mathbf{y}^n$ को दूसरी तरफ ले जाएं:

\langle z\cdot\mathbf{1},\mathbf{H}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle

\cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle} \stackrel{?}{=}\cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle}

Correctness of the evaluation of $t(u)$

यह देखने के लिए कि

t_uG+\pi_tB=Vz^2+\delta(y,z)G+T_1u+T_2u^2

सही है, हम इस प्रकार टर्म्स को प्रतिस्थापित कर सकते हैं:

\underbrace{\langle \mathbf{l}_u, \mathbf{r}_u \rangle}_{t_u}G+\underbrace{(z^2\gamma + \tau_1u + \tau_2u^2)}_{\pi_t}B=\underbrace{(vG+\gamma B)}_{V}z^2+\delta(y,z)G+\underbrace{(t_1G+\tau_1B}_{T_1})u+\underbrace{(t_2G+\tau_2B)}_{T_2}u^2

$\mathbf{l}_u$ , $\mathbf{r}_u$ , $t_1$ , $t_2$ के साथ:

\begin{align*} \mathbf{l}_u &= \mathbf{a_L} - z \cdot \mathbf{1}^n\\ \mathbf{r}_u &= \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n\\ t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\\ t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle \end{align*}

हालांकि, ऐसा अलजेब्रा बेहद जटिल होगा। इसके बजाय, हम देखते हैं कि $z^2v+\delta(y,z)G$ , $\langle\mathbf{l}(x),\mathbf{r}(x)\rangle$ के वेक्टर पॉलिनॉमियल इनर प्रोडक्ट का कांस्टेंट टर्म है। $V$ में $\gamma B$ में ब्लाइंडिंग टर्म को रद्द करने के लिए, ध्यान दें कि $\pi_t$ में $z^2\gamma$ शामिल है, इसलिए यह $Vz^2 = (vG + \gamma B)z^2$ में गामा टर्म के साथ रद्द हो जाएगा।

चूंकि पेडरसन कमिटमेंट्स एडिटिवली होमोमोर्फिक (additively homomorphic) हैं, इसलिए वेरिफायर पॉलिनॉमियल $t(x)$ के कांस्टेंट टर्म के कमिटमेंट की गणना करने के लिए आसानी से $\delta(y,z)G$ की गणना करके उसे $Vz^2$ में जोड़ सकता है।

Logarithmic-sized range proof

हम $\mathbf{l}_u$ और $\mathbf{r}_u$ का कमिटमेंट $C$ भेजकर और यह साबित करके डेटा ट्रांसमिशन के आकार को कम कर सकते हैं कि कमिट किए गए वेक्टर्स का इनर प्रोडक्ट $t_u$ है, इसके लिए लॉगरिदमिक-साइज्ड (logarithmic-sized) प्रूफ का उपयोग किया जाता है, और फिर वेरिफाई किया जाता है कि

A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle-\pi_{lr}B\stackrel{?}{=} C

और

t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle

बेसिस वेक्टर्स $\mathbf{G}$ और $\mathbf{H}_{\mathbf{y}^{-1}}$ के संबंध में।

Using the range proof algorithm for the subset sum

सबसेट सम प्रॉब्लम (subset sum problem) यह पूछता है, "संख्याओं का एक सेट दिए जाने पर, क्या कोई सबसेट (संभवतः पूरे सेट सहित) जुड़कर $k$ के बराबर होता है? उदाहरण के लिए यदि $k = 16$ है और सेट $\set{3,5,7,11}$ है तो उत्तर हाँ है क्योंकि $5 + 11 = 16$ । हालांकि यदि $k=13$ है, तो उत्तर नहीं है।

सबसेट सम प्रॉब्लम NP-Complete है, जिसका अर्थ है कि, एक बूलियन सर्किट (Boolean circuit) या एरिथमेटिक सर्किट (arithmetic circuit) के समान, यह NP में किसी भी समस्या का प्रतिनिधित्व कर सकता है। अर्थात, NP में किसी भी समस्या को सबसेट सम इंस्टेंस में फिर से लिखा (तकनीकी शब्द “रिड्यूस्ड (reduced)”) जा सकता है।

$\mathbf{2}^n$ को $[3,5,7,11]$ से बदलकर, हम यह साबित कर सकते हैं कि हम बिना उत्तर बताए सबसेट सम का समाधान जानते हैं। विशेष रूप से, प्रूवर को पता होगा कि यदि $k=16$ है तो $\mathbf{a}_L= [0,1,0,1]$ है। सामान्य तौर पर, $\mathbf{a}_L$ में एक (one) प्रविष्टि का अर्थ है कि हम उस एलिमेंट को सबसेट में शामिल करते हैं और शून्य का अर्थ है कि यह सबसेट में शामिल नहीं है।

इसलिए, Bulletproofs किसी भी NP समस्या के लिए किसी भी विटनेस (witness) का ज्ञान साबित करने में सक्षम हैं।

Appendix: Derivation of combining three inner products into one

तीन इनर प्रोडक्ट्स से शुरू करते हुए

z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v

हम दिखाते हैं कि अंतिम परिणाम कैसे प्राप्त करें

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle

हमारे द्वारा पहले सीखे गए इनर प्रोडक्ट अलजेब्रा का उपयोग करके।

मध्य टर्म को अलग-अलग इनर प्रोडक्ट्स में विभाजित किया जा सकता है:

z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + \boxed{z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle} + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v

z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle+\boxed{z\cdot\langle\mathbf{a}_L,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{1}^n,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{a}_R,\mathbf{y}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle=z^2\cdot v

हम कांस्टेंट $z$ टर्म्स को इनर प्रोडक्ट्स के अंदर ले जा सकते हैं:

$\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v$
वेरिफायर को ज्ञात मानों को दाईं ओर ले जाएं:

$\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v$

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}

$\mathbf{a}_R$ टर्म्स को इस तरह बदलें कि दोनों $\mathbf{a}_R\circ\mathbf{y}^n$ हो जाएं:

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-\mathbf{a}_R\circ\mathbf{y}^n,z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\boxed{\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

$\mathbf{a}_R\circ\mathbf{y}^n$ टर्म्स को एक में मिलाएं:

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\underbrace{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle} = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

बाईं ओर के दो $\mathbf{a}_L$ टर्म्स को मिलाएं:

\langle \boxed{\mathbf{a_L}}, z^2\cdot\mathbf{2}^n \rangle+\langle\boxed{\mathbf{a}_L},z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

अंतिम बाईं ओर के टर्म को दो इनर प्रोडक्ट्स में विभाजित करें:

$\langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle$

\langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

$\mathbf{a}_L$ टर्म्स को मिलाएं:

$\langle \boxed{\mathbf{a_L}}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n, \boxed{\mathbf{a}_L}\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle$

\langle \mathbf{a_L}, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

हम $\mathbf{a}_R\circ\mathbf{y}^n$ वाले टर्म्स को मिलाने के लिए नियम $\langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{y}\rangle = v \rightarrow \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle$ का उपयोग कर सकते हैं। यहाँ $\mathbf{b}$ , $\mathbf{a}_R\circ\mathbf{y}^n$ है, $\mathbf{c}$ , $z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n$ है, और $\mathbf{y}$ , $-z\cdot\mathbf{1}^n$ है।

\langle \underbrace{\mathbf{a_L}}_\mathbf{x}, \underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle+\langle\underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b},\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y}\rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v

\langle \underbrace{\mathbf{a_L}}_\mathbf{x}-\underbrace{z\cdot\mathbf{1}^n}_\mathbf{y}, \underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v+\langle\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y},\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c}\rangle

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n\rangle

अब हम दाईं ओर के टर्म्स को तोड़ते हैं:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z^2\cdot\mathbf{2}^n\rangle

दाईं ओर के इनर प्रोडक्ट्स से स्केलर्स को बाहर निकालें:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+z\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^2\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle

$\langle\mathbf{1}^n,\mathbf{y}^n\rangle$ को फैक्टर आउट (बाहर) करें:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle

चूंकि $\delta(y,z)=(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle$ है, हमारे पास है:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+\delta(y,z)

यह डेरिवेशन पूरा करता है। $\blacksquare$