Pedersen Commitments के माध्यम से Polynomial Commitments

Last updated on Oct 26, 2024

पॉलीनोमियल कमिटमेंट एक ऐसा मैकेनिज्म है जिसके द्वारा एक प्रूवर (prover) किसी वेरिफायर (verifier) को यह विश्वास दिला सकता है कि एक पॉलीनोमियल $p(x)$ का पॉइंट $x$ पर इवैल्यूएशन $y = p(x)$ है, वह भी $p(x)$ के बारे में कुछ भी उजागर किए बिना। इसका क्रम इस प्रकार है:

प्रूवर वेरिफायर को एक कमिटमेंट $C$ भेजता है, जिससे उनका पॉलीनोमियल “लॉक” हो जाता है।
वेरिफायर एक वैल्यू $u$ के साथ प्रतिक्रिया देता है, जिस पर वे पॉलीनोमियल को इवैल्यूएट करना चाहते हैं।
प्रूवर $y$ और $\pi$ के साथ प्रतिक्रिया देता है, जहाँ $y$ , $p(u)$ का इवैल्यूएशन है और $\pi$ इस बात का प्रमाण (proof) है कि इवैल्यूएशन सही था।
वेरिफायर $C$ , $u$ , $y$ , $\pi$ की जाँच करता है और यह स्वीकार या अस्वीकार करता है कि पॉलीनोमियल का इवैल्यूएशन मान्य था।

इस कमिटमेंट स्कीम के लिए किसी ट्रस्टेड सेटअप (trusted setup) की आवश्यकता नहीं होती है। हालाँकि, कम्युनिकेशन ओवरहेड $O(n)$ होता है क्योंकि प्रूवर को अपने पॉलीनोमियल में प्रत्येक गुणांक (coefficient) के लिए एक कमिटमेंट भेजना होता है।

पॉलीनोमियल पर कमिट करना

प्रूवर प्रत्येक गुणांक का एक Pedersen Commitment बनाकर पॉलीनोमियल पर कमिट कर सकता है। Pedersen Commitment के लिए, प्रूवर और वेरिफायर को अज्ञात डिस्क्रीट लॉग्स (discrete logs) वाले दो एलिप्टिक कर्व पॉइंट्स (elliptic curve points) पर सहमत होना आवश्यक है। हम $G$ और $B$ का उपयोग करेंगे।

उदाहरण के लिए, यदि हमारे पास एक पॉलीनोमियल है

p(x) = c_0+c_1x+c_2x^2

तो हम प्रत्येक गुणांक के लिए एक Pedersen commitment बना सकते हैं। हमें तीन ब्लाइंडिंग टर्म्स (blinding terms) $\gamma_0$ , $\gamma_1$ , $\gamma_2$ की आवश्यकता होगी। सुविधा के लिए, ब्लाइंडिंग के लिए उपयोग किए जाने वाले किसी भी स्केलर (scalar) के लिए लोअर-केस ग्रीक अक्षर का उपयोग किया जाएगा। हम हमेशा ब्लाइंडिंग टर्म के लिए एलिप्टिक कर्व पॉइंट $B$ का उपयोग करते हैं। हमारे कमिटमेंट्स इस प्रकार तैयार किए जाते हैं:

\begin{align*} C_0=c_0G+\gamma_0B \\ C_1=c_1G+\gamma_1B \\ C_2=c_2G+\gamma_2B \\ \end{align*}

प्रूवर ट्यूपल $(C_0, C_1, C_2)$ वेरिफायर को भेजता है।

वेरिफायर $u$ चुनता है

वेरिफायर $x$ के लिए अपनी वैल्यू चुनता है और उसे प्रूवर को भेजता है। हम उस वैल्यू को $u$ कहते हैं।

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

प्रूवर पॉलीनोमियल को इवैल्यूएट करता है

प्रूवर मूल पॉलीनोमियल की गणना इस प्रकार करता है:

y = p(u) = c_0 + c_1u + c_2u^2

प्रूवर ब्लाइंडिंग टर्म्स को इवैल्यूएट करता है

इवैल्यूएशन सही ढंग से किया गया था, इसका प्रमाण (proof) निम्नलिखित पॉलीनोमियल द्वारा दिया जाता है, जो $u$ की संबंधित घात (power) से गुणा किए गए ब्लाइंडिंग टर्म्स का उपयोग करता है। इसका कारण बाद में समझाया जाएगा।

\pi = \gamma_0 + \gamma_1u+\gamma_2u^2

प्रूवर $(y, \pi)$ को वेरिफायर को भेजता है। ध्यान दें कि प्रूवर केवल फील्ड एलिमेंट्स (स्केलर्स) भेज रहा है, न कि एलिप्टिक कर्व पॉइंट्स।

वेरिफिकेशन स्टेप

वेरिफायर निम्नलिखित जाँच रन करता है:

C_0+C_1u+C_2u^2\stackrel{?}{=}yG+\pi B

वेरिफिकेशन स्टेप कैसे काम करता है

यदि हम एलिप्टिक कर्व पॉइंट्स को उनके अंतर्निहित मूल्यों (underlying values) में विस्तारित करते हैं, तो हम देखते हैं कि समीकरण संतुलित है:

\begin{align*} C_0 + C_1u + C_2u^2 &= yG + \pi B \\ (c_0G + \gamma_0B) + (c_1G + \gamma_1B)u + (c_2G + \gamma_2B)u^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \\ c_0G + \gamma_0B + c_1Gu + \gamma_1Bu + c_2Gu^2 + \gamma_2Bu^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \\ c_0G + c_1Gu + c_2Gu^2 + \gamma_0B + \gamma_1Bu + \gamma_2Bu^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \\ (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \\ \end{align*}

एक तरह से, प्रूवर पॉलीनोमियल के गुणांकों और $u$ के अपने चुनाव का उपयोग करके पॉलीनोमियल को इवैल्यूएट कर रहा है। यह मूल पॉलीनोमियल के इवैल्यूएशन के साथ-साथ पॉलीनोमियल के ब्लाइंडिंग टर्म्स उत्पन्न करेगा।

सही इवैल्यूएशन का प्रमाण यह है कि प्रूवर पॉलीनोमियल के इवैल्यूएशन से ब्लाइंडिंग टर्म्स को अलग कर सकता है – भले ही प्रूवर $yG$ और $\pi B$ के डिस्क्रीट लॉग्स नहीं जानता हो।

वेरिफिकेशन कैसे काम करता है, इसका एक वैकल्पिक उदाहरण

याद रखें कि $p(x) = c_0 + c_1x + c_2x^2$ है। इसलिए, गुणांकों के कमिटमेंट्स की गणना इस प्रकार की जाती है:

\begin{matrix} &\space\space\space c_0G&\space\space\space c_1G&\space\space\space c_2G\\ &+\gamma_0B&+\gamma_1B&+\gamma_2B\\ &\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\\ &C_0&C_1&C_2 \end{matrix}

जब वेरिफायर $\color{red}{u}$ भेजता है, तो प्रूवर गणना करता है:

\begin{matrix} y=& c_0& +c_1\color{red}{u}& +c_2\color{red}{u^2}\\ \pi=&\gamma_0&+\gamma_1\color{red}{u}&+\gamma_2\color{red}{u^2}\\ \end{matrix}

अंतिम स्टेप में, वेरिफायर जाँच करता है:

yG + \pi B\stackrel{?}=C_0 + C_1 {\color{red} u} + C_2 {\color{red} u^2}

यदि हम पदों को वर्टिकली (vertically) विस्तारित करते हैं, तो हम देखते हैं कि यदि प्रूवर ईमानदार था, तो समीकरण संतुलित है:

\begin{matrix} yG&=& c_0G& c_1G\color{red}{u}& c_2G\color{red}{u^2}\\ \pi B&=&\gamma_0B&\gamma_1B\color{red}{u}&\gamma_2B\color{red}{u^2}\\ \vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\\ yG+\pi B&\stackrel{?}=&C_0&+C_1\color{red}{u}&+C_2\color{red}{u^2} \end{matrix}

यह बहुत महत्वपूर्ण है कि आप गुणांकों के ब्लाइंडिंग कमिटमेंट्स दिए जाने पर, पॉलीनोमियल के सही इवैल्यूएशन को साबित करने की यह तकनीक कैसे काम करती है, इसे अच्छी तरह से समझ लें क्योंकि Bulletproofs इस तकनीक का उपयोग हर जगह करते हैं।

Exercise: उन स्टेप्स को लिखें जिनके माध्यम से एक प्रूवर वेरिफायर को यह विश्वास दिलाएगा कि उन्होंने पॉलीनोमियल को वेरिफायर के सामने उजागर किए बिना, डिग्री 1 के पॉलीनोमियल का सही इवैल्यूएशन किया है।

Exercise: इस अध्याय में वर्णित एल्गोरिथम को इम्प्लीमेंट करने के लिए नीचे दिए गए Python कोड को भरें:

from py_ecc.bn128 import G1, multiply, add, FQ
from py_ecc.bn128 import curve_order as p
import random

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

# these EC points have unknown discrete logs:
G = (FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138))

B = (FQ(12848606535045587128788889317230751518392478691112375569775390095112330602489), FQ(18818936887558347291494629972517132071247847502517774285883500818572856935411))

# scalar multiplication example: multiply(G, 42)
# EC addition example: add(multiply(G, 42), multiply(G, 100))

# remember to do all arithmetic modulo p

def commit(f_0, f_1, f_2, gamma_0, gamma_1, gamma_2, G, B):
    # fill this in
    # return the commitments as a tuple (C0, C1, C2)
    pass

def evaluate(f_0, f_1, f_2, u):
    return (f_0 + f_1 * u + f_2 * u**2) % p

def prove(gamma_0, gamma_1, gamma_2, u):
    # fill this in
    # return pi
    pass

def verify(C0, C1, C2, G, B, f_u, pi):
    # fill this in
    # Return true or false
    pass

## step 0: Prover and verifier agree on G and B

## step 1: Prover creates the commitments
### f(x) = f_0 + f_1x + f_2x^2
f_0 = ...
f_1 = ...
f_2 = ...

### blinding terms
gamma_0 = ...
gamma_1 = ...
gamma_2 = ...
C0, C1, C2 = commit(f_0, f_1, f_2, gamma_0, gamma_1, gamma_2, G, B)

## step 2: Verifier picks u
u = ...

## step 3: Prover evaluates f(u) and pi

f_u = evaluate(f_0, f_1, f_2, u)
pi = prove(gamma_0, gamma_1, gamma_2, u)

## step 4: Verifier accepts or rejects
if verify(C0, C1, C2, G, B, f_u, pi):
    print("accept")
else:
    print("reject")

प्रूवर धोखा (cheat) क्यों नहीं दे सकता

प्रूवर की ओर से धोखा देने का अर्थ है कि वे $y = p(u)$ को ईमानदारी से इवैल्यूएट नहीं करते हैं, लेकिन फिर भी अंतिम इवैल्यूएशन स्टेप को पास करने का प्रयास करते हैं।

व्यापकता खोए बिना (Without loss of generality), मान लेते हैं कि प्रूवर गुणांक $C_0, C_1, C_2$ के लिए सही कमिटमेंट्स भेजता है।

हम ‘व्यापकता खोए बिना’ इसलिए कहते हैं क्योंकि कमिटमेंट्स में भेजे गए गुणांकों और पॉलीनोमियल को इवैल्यूएट करने के लिए उपयोग किए गए गुणांकों के बीच बेमेल (mismatch) होता है।

ऐसा करने के लिए, प्रूवर $y'$ भेजता है जहाँ $y' \neq c_0 + c_1u + c_2u^2$ है।

पिछले अनुभाग के अंतिम समीकरण का उपयोग करते हुए, हम देखते हैं कि प्रूवर को निम्नलिखित को संतुष्ट करना होगा:

(c_0 + c_1u + c_2u^2)G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B=y'G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B

समीकरण के $G$ पद स्पष्ट रूप से असंतुलित हैं। दूसरा “लीवर” जिसे प्रूवर खींच सकता है वह उनके द्वारा भेजे गए $\pi$ को एडजस्ट करना है।

(c_0 + c_1u + c_2u^2)G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B=y'G + \boxed{\pi'}B

चूँकि $y' \neq c_0 + c_1u + c_2u^2$ है, दुर्भावनापूर्ण (malicious) प्रूवर को एक ऐसा पद $\pi'$ चुनकर समीकरण को फिर से संतुलित करना चाहिए जो $G$ पदों में बेमेल को कवर करे। प्रूवर निम्नलिखित के साथ $\pi'$ के लिए हल करने का प्रयास कर सकता है:

\pi'B = (c_0 + c_1u + c_2u^2)G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B - y'G

लेकिन इस समीकरण को हल करने के लिए दुर्भावनापूर्ण प्रूवर को $G$ और $B$ के डिस्क्रीट लॉग्स जानने की आवश्यकता होगी।

आइए उपरोक्त समीकरण में $\pi'$ के लिए हल करें:

\pi' = \frac{(c_0 + c_1u + c_2u^2)G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B - y'G}{B}

और फिर $B$ को $b$ से और $G$ को $g$ से बदलें, जहाँ $b$ और $g$ क्रमशः $B$ और $G$ के डिस्क्रीट लॉग्स हैं:

\pi' = \frac{(c_0 + c_1u + c_2u^2)g+(\gamma_0 + \gamma_1u+\gamma_2u^2)b - y'g}{b}

लेकिन फिर से, यह संभव नहीं है क्योंकि $B$ और $G$ के डिस्क्रीट लॉग की गणना करना अव्यवहारिक (infeasible) है।

वेरिफायर को क्या पता चलता है

वेरिफायर को यह पता चलता है कि कमिटमेंट्स $C_0, C_1, C_2$ एक ऐसे पॉलीनोमियल के वैध कमिटमेंट्स को दर्शाते हैं जो अधिकतम 2 डिग्री का है, और $y$ , $u$ पर इवैल्यूएट किए गए पॉलीनोमियल का मान (value) है।