पॉलिनॉमियल्स (Polynomials) का ज़ीरो नॉलेज मल्टीप्लिकेशन

पिछले अध्याय की polynomial commitment स्कीम का उपयोग करके, एक प्रूवर (prover) यह दिखा सकता है कि उसके पास तीन पॉलिनॉमियल्स $l(x)$, $r(x)$, और $t(x)$ हैं और यह साबित कर सकता है कि $t(x) = l(x)r(x)$ है।

इस एल्गोरिदम के काम करने के लिए, वेरिफायर (verifier) को यह विश्वास होना चाहिए कि पॉलिनॉमियल इवैल्यूएशन (evaluations) सही हैं – लेकिन यह एक ऐसी चीज़ है जिसे हमने पिछले अध्याय में दिखाया था। यहाँ के अधिकांश चरण (steps) केवल उसी polynomial commitment एल्गोरिदम को दोहरा रहे हैं जो हमने पहले किया था।

एक हाई-लेवल पर, प्रूवर $l(x)$, $r(x)$, और $t(x)$ के लिए कमिट (commit) करता है और कमिटमेंट्स (commitments) को वेरिफायर के पास भेजता है। फिर, वेरिफायर $x$ के लिए एक रैंडम वैल्यू (random value) $u$ के रूप में चुनता है और प्रूवर से $u$ पर पॉलिनॉमियल्स को इवैल्यूएट करने के लिए कहता है। वेरिफायर तब जाँचता है कि इवैल्यूएशन सही ढंग से किए गए थे या नहीं, और क्या $l(x)$ के इवैल्यूएशन को $r(x)$ के इवैल्यूएशन से गुणा करने पर वह $t(x)$ के इवैल्यूएशन के बराबर है।

उदाहरण के लिए, मान लें कि पहला पॉलिनॉमियल $l(x)=2x$ है और दूसरा $r(x) = x + 1$ है। तो $t(x)=2x(x+1) = 2x^2+2$ होगा। वेरिफायर किसी भी रैंडम $x$ वैल्यू को सैंपल कर सकता है, और $l(x)r(x)$ के गुणनफल (product) का परिणाम $t(x)$ होगा। नीचे दिया गया ग्राफ वेरिफायर द्वारा $x=2$ चुनने का एक उदाहरण दिखाता है:

वेरिफायर फिर यह जाँचेगा कि $3 \times 4 = 12$ है और प्रूवर के दावे को स्वीकार करेगा।

Schwartz-Zippel lemma यह बताता है कि यदि $f(x) \neq g(x)$ है, तो किसी रैंडम वैल्यू $u$ के लिए $f(u) = g(u)$ होने की प्रोबेबिलिटी (probability) $d/p$ से कम होती है, जहाँ $d$ दोनों पॉलिनॉमियल्स की अधिकतम डिग्री (maximum degree) है और $p$ finite field का ऑर्डर (order) है। यदि $d \ll p$ ($d$, $p$ से बहुत बहुत छोटा है), तो $u$ के दो असमान पॉलिनॉमियल्स का इंटरसेक्शन पॉइंट (intersection point) होने की प्रोबेबिलिटी नगण्य (negligible) है।

विशेष रूप से, मान लीजिए कि प्रूवर झूठ बोल रहा है और $l(x)r(x) \neq t(x)$ है। उस स्थिति में, एक रैंडम $u$ के लिए, अत्यंत उच्च प्रोबेबिलिटी के साथ $l(u)r(u) \neq t(u)$ होगा। यदि $l(x)r(x) \neq t(x)$ है, तो $l(x)r(x)$ और $t(x)$ केवल अधिकतम $d$ पॉइंट्स पर इंटरसेक्ट करते हैं ($l(x)r(x)$ या $t(x)$ दोनों में से किसी की अधिकतम डिग्री), और इसकी संभावना बहुत कम है कि वेरिफायर रैंडमली ऐसा $u$ चुनेगा जो उन $d$ इंटरसेक्शन पॉइंट्स में से एक हो।

स्केल (scale) का अंदाज़ा लगाने के लिए, हमारे मामले में $d$ 2 है, लेकिन हमारे इलिप्टिक कर्व्स (elliptic curves) का कर्व ऑर्डर (curve order) (और इसलिए फील्ड का ऑर्डर) लगभग $2^{254}$ है। इसलिए यदि $t(x) \neq l(x)r(x)$ है, तो $t(u) = l(u)r(u)$ होने की प्रोबेबिलिटी $1/2^{253}$ है, जो कि लुप्त होने की हद तक छोटी (vanishingly small) है।

अब हम एल्गोरिदम का विस्तार से वर्णन करते हैं, और फिर एक ऑप्टिमाइज़ेशन (optimization) दिखाते हैं।

पॉलिनॉमियल मल्टीप्लिकेशन की नॉलेज साबित करने के स्टेप्स

प्रूवर दो लीनियर (डिग्री 1) पॉलिनॉमियल्स $l(x)$, $r(x)$, और एक क्वाड्रैटिक (डिग्री 2) पॉलिनॉमियल $t(x)$ को कमिट करता है, और वेरिफायर को कमिटमेंट्स भेजता है। वेरिफायर एक रैंडम वैल्यू $u$ के साथ प्रतिक्रिया देता है, और प्रूवर इवैल्यूएशन के प्रूफ्स $\pi_l, \pi_r, \pi_t$ के साथ $l_u = l(u)$, $r_u = r(u)$, और $t_u = t(u)$ का इवैल्यूएशन करता है। वेरिफायर यह सुनिश्चित करता है कि सभी पॉलिनॉमियल्स का इवैल्यूएशन ठीक से किया गया था और $t_u = l_ur_u$ है।

सेटअप (Setup)

प्रूवर और वेरिफायर एक अज्ञात डिस्क्रीट लॉग रिलेशनशिप (discrete log relationship) वाले इलिप्टिक कर्व पॉइंट्स $G$ और $B$ पर सहमत होते हैं (यानी पॉइंट्स को रैंडमली चुना जाता है)।

प्रूवर $l(x)$, $r(x)$, और $t(x)$ के लिए कमिट करता है

प्रूवर तीन पॉलिनॉमियल्स बनाता है:

इसलिए उन्हें प्रत्येक गुणांक (coefficients) के लिए कुल 7 Pedersen commitments उत्पन्न करने की आवश्यकता होगी, जिसके लिए सात ब्लाइंडिंग टर्म्स (blinding terms) $\alpha_0, \alpha_1, \beta_0, \beta_1, \tau_0, \tau_1, \tau_2$ की आवश्यकता होगी।

प्रूवर वेरिफायर को $(L_0, L_1, R_0, R_1, T_0, T_1, T_2)$ भेजता है।

वेरिफायर रैंडम स्केलर $u$ जनरेट करता है

… और फील्ड एलिमेंट (field element) $u$ प्रूवर को भेजता है।

प्रूवर तीन पॉलिनॉमियल्स का इवैल्यूएशन करता है और तीन प्रूफ्स बनाता है

प्रूवर पॉलिनॉमियल्स में $u$ डालता है और जब $u$ लागू होता है तो पॉलिनॉमियल कोएफिशिएंट कमिटमेंट्स के ब्लाइंडिंग टर्म्स के योग (sum) की गणना करता है।

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

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

वेरिफायर जाँचता है कि प्रत्येक पॉलिनॉमियल्स का सही ढंग से इवैल्यूएशन किया गया था और $t(u)$ का इवैल्यूएशन $l(u)$ और $r(u)$ के इवैल्यूएशन का गुणनफल (product) है। पहले तीन चेक्स (checks) इस बात के प्रमाण हैं कि कोएफिशिएंट्स के कमिटमेंट के संबंध में पॉलिनॉमियल का सही ढंग से इवैल्यूएशन किया गया था, और अंतिम चेक यह वेरिफाई करता है कि पॉलिनॉमियल्स के आउटपुट में दावा किया गया प्रोडक्ट रिलेशनशिप (product relationship) है।

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

ऑप्टिमाइज़ेशन (Optimization): कम कमिटमेंट्स भेजना

पहले चरण में, प्रूवर 7 इलिप्टिक कर्व पॉइंट्स भेजता है, और अंतिम चरण में, वेरिफायर 4 इक्वालिटीज़ (equalities) की जाँच करता है। हम केवल 5 इलिप्टिक कर्व पॉइंट्स भेजने और 3 इक्वालिटी चेक करने के लिए एल्गोरिदम में सुधार कर सकते हैं।

यह $l(x)$ और $r(x)$ के कांस्टेंट कोएफिशिएंट्स को एक ही कमिटमेंट में और उन पॉलिनॉमियल्स के लीनियर कोएफिशिएंट्स को एक अलग कमिटमेंट में रखकर किया जाता है। याद दिलाने के लिए, हमने $l(x)$ और $r(x)$ को इस प्रकार परिभाषित किया था:

इसलिए $a$ और $b$ कांस्टेंट कोएफिशिएंट्स हैं, और $s_L$ तथा $s_R$ लीनियर कोएफिशिएंट्स हैं।

यह उसी तरह है जैसे हम एक वेक्टर (vector) को कमिट करते हैं। हम एक तरह से कांस्टेंट कोएफिशिएंट्स को एक वेक्टर के रूप में और लीनियर कोएफिशिएंट्स को दूसरे वेक्टर के रूप में कमिट कर रहे हैं।

सेटअप (Setup)

सेटअप के दौरान, अब हमें 3 इलिप्टिक कर्व पॉइंट्स की आवश्यकता है: $G$, $H$, और $B$।

पॉलिनॉमियल कमिटमेंट (Polynomial commitment)

ध्यान दें कि $l(x)$ के कोएफिशिएंट्स $G$ पर लागू होते हैं और $r(x)$ के कोएफिशिएंट्स $H$ पर लागू होते हैं। प्रूवर वेरिफायर को $(A, S, T_0, T_1, T_2)$ भेजता है, जो $u$ के साथ प्रतिक्रिया देता है।

पॉलिनॉमियल इवैल्यूएशन

$l_u$, $r_u$, $t_u$, $\pi_{lr}$, और $\pi_t$ की गणना पहले की तरह की जाती है, लेकिन $l(x)$ और $r(x)$ के इवैल्यूएशन के प्रूफ्स, जो पहले $\pi_l$ और $\pi_r$ थे, उन्हें मिलाकर एक कर दिया गया है: $\pi_{lr}$।

फाइनल वेरिफिकेशन

चेक $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ का विस्तार (expand) इस प्रकार होता है:

बाईं ओर (left-hand-side) कुछ पुनर्व्यवस्था (rearranging) के साथ, हम देख सकते हैं कि इक्वालिटी चेक एक साथ यह जाँचता है कि $l(x)$ और $r(x)$ दोनों का इवैल्यूएशन सही ढंग से किया गया था।

चेक $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ को देखने के एक और तरीके के रूप में, निम्नलिखित विज़ुअलाइज़ेशन (visualization) पर विचार करें:

स्केलर्स (Scalars) का ज़ीरो नॉलेज मल्टीप्लिकेशन

हमारा यह प्रूफ कि हमने तीसरे पॉलिनॉमियल को प्राप्त करने के लिए दो पॉलिनॉमियल्स को सही ढंग से गुणा किया है, का उपयोग यह साबित करने के लिए किया जा सकता है कि हमने तीसरे को प्राप्त करने के लिए दो स्केलर्स (scalars) को एक साथ गुणा किया है। एल्गोरिदम में किसी बदलाव की आवश्यकता नहीं है, केवल सिमेंटिक्स (semantics) में एक मामूली बदलाव है (हम कमिटमेंट्स की व्याख्या कैसे करते हैं)।

मान लें कि हम यह साबित करना चाहते हैं कि हमने $ab = v$ का गुणा (multiplication) किया है।

समस्या का विवरण (Problem statement)

$A$, $a$ और $b$ के लिए एक कमिटमेंट है, और $V$, $v$ के लिए एक कमिटमेंट है जहाँ $v = ab$ है। हम यह साबित करना चाहते हैं कि $A$ और $V$ को दावे के अनुसार कमिट किया गया है बिना $a$, $b$, या $v$ को प्रकट किए।

समाधान (Solution)

हाई-लेवल विचार यह है कि स्वेच्छा से (arbitrarily) चुने गए लीनियर टर्म को जोड़कर एक स्केलर को पॉलिनॉमियल में बदला जा सकता है, उदाहरण के लिए $a$, $a + s_Lx$ बन जाता है और $b$, $b + s_Rx$ बन जाता है। $s_L$ और $s_R$ प्रूवर द्वारा रैंडमली चुने जाते हैं।

जब पॉलिनॉमियल्स $a + s_Lx$ और $b + s_Rx$ को एक साथ गुणा किया जाता है, तो $ab$ का गुणा पॉलिनॉमियल मल्टीप्लिकेशन के “अंदर” होता है।

याद करें कि प्रूवर कमिटमेंट्स भेजकर एल्गोरिदम शुरू करता है:

हम बस $A$ की “व्याख्या (interpretation)” को पॉलिनॉमियल्स के कांस्टेंट टर्म्स होने के बजाय उन कांस्टेंट्स $a$ और $b$ में बदल देते हैं जिन्हें हम गुणा कर रहे हैं। हम उस मल्टीप्लिकेशन में $V$ के कमिटमेंट के रूप में व्याख्या के बदलाव को दर्शाने के लिए $T_0$ को $V$ में बदलते हैं जिसे हम यह साबित करने का प्रयास कर रहे हैं कि हमने सही ढंग से किया है, यानी $v = ab$।

अभ्यास (Exercise): ऊपर वर्णित एल्गोरिदम को लागू करने के लिए छूटे हुए Python कोड को भरें।

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

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

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

H = (FQ(13728162449721098615672844430261112538072166300311022796820929618959450231493), FQ(12153831869428634344429877091952509453770659237731690203490954547715195222919))

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

# utility function
def addd(A, B, C):
    return add(A, add(B, C))

# 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(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2):
    pass
    # return (A, S, V, T1, T2)


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

def prove(blinding_0, blinding_1, blinding_2, u):
    # fill this in
    # return pi
    pass

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

## step 1: Prover creates the commitments
a = ...
b = ...
sL = ...
sR = ...
t1 = ...
t2 = ...

### blinding terms
alpha = ...
beta = ...
gamma = ...
tau_1 = ...
tau_2 = ...

A, S, V, T1, T2 = commit(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2)

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

## step 3: Prover evaluates l(u), r(u), t(u) and creates evaluation proofs
l_u = evaluate(a, sL, 0, u)
r_u = evaluate(b, sR, 0, u)
t_u = evaluate(a*b, t1, t2, u)

pi_lr = prove(alpha, beta, 0, u)
pi_t = prove(gamma, tau_1, tau_2, u)

## step 4: Verifier accepts or rejects
assert t_u == (l_u * r_u) % p, "tu != lu*ru"
assert eq(add(A, multiply(S, u)), addd(multiply(G, l_u), multiply(H, r_u), multiply(B, pi_lr))), "l_u or r_u not evaluated correctly"
assert eq(add(multiply(G, t_u), multiply(B, pi_t)), addd(V, multiply(T1, u), multiply(T2, u**2 % p))), "t_u not evaluated correctly"

और जानें (Learn more)

यह लेख Bulletproof ZKPs पर एक सीरीज़ का हिस्सा है।