इनर प्रोडक्ट के लिए एक ज़ीरो नॉलेज प्रूफ

Last updated on Nov 13, 2024

एक inner product argument यह proof है कि prover ने inner product computation को सही ढंग से किया है। यह अध्याय (chapter) दिखाता है कि inner product argument के लिए zero knowledge proof कैसे बनाया जाए।

पिछले अध्याय में, हमने दिखाया था कि दो scalars को zero knowledge तरीके से एक साथ कैसे multiply किया जाए: हम दो degree-one polynomials के लिए commit करते हैं, और साबित करते हैं कि हमने उनके product की सही गणना की है, और फिर दिखाते हैं कि degree one polynomials के constant term उन secret factors के commitments हैं जिन्हें हम multiply कर रहे हैं।

यदि हमारे polynomial के coefficients scalars के बजाय vectors हैं, तो हम यह साबित कर सकते हैं कि हमने vector के inner product की सही गणना की है। अब हम vector polynomial को पेश करते हैं।

Vector polynomials: vectors वाले polynomials बतौर coefficients

नीचे दिए गए दो polynomials हैं जिनमें vector coefficients हैं:

\begin{align*} \mathbf{l}(x) &= \begin{bmatrix} 1 \\ 2 \end {bmatrix} x + \begin{bmatrix} 3 \\ 4 \end{bmatrix} \\ \mathbf{r}(x) &= \begin{bmatrix} 2 \\ 3 \end{bmatrix} x +\begin{bmatrix} 7 \\ 2 \end{bmatrix} \end{align*}

एक vector polynomial को evaluate करने पर एक और vector प्राप्त होता है। उदाहरण के लिए, $\mathbf{l}(2)$ उत्पन्न करता है:

\begin{align*} \mathbf{l}(2) &= \begin{bmatrix} 1 \\ 2 \end{bmatrix} (2) + \begin{bmatrix} 3 \\ 4 \end{bmatrix}\\ &= \begin{bmatrix} 2 \\ 4 \end{bmatrix}+\begin{bmatrix} 3 \\ 4 \end{bmatrix}\\ &=\begin{bmatrix} 5 \\ 8 \end{bmatrix} \end{align*}

और 2 पर $\mathbf{r}$ को evaluate करने पर प्राप्त होता है:

\begin{align*} \mathbf{r}(2) &= \begin{bmatrix} 2 \\ 3 \end{bmatrix} (2) + \begin{bmatrix} 7 \\ 2 \end{bmatrix}\\ &= \begin{bmatrix} 4 \\ 6 \end{bmatrix} + \begin{bmatrix} 7 \\ 2 \end{bmatrix}\\ &= \begin{bmatrix} 11 \\ 8 \end{bmatrix} \end{align*}

$\mathbf{l}(x)$ और $\mathbf{r}(x)$ को bold में लिखा गया है क्योंकि जब उन्हें किसी scalar $x$ पर evaluate किया जाता है, तो वे vectors उत्पन्न करते हैं।

Vector polynomials को multiply करना

Vector polynomials को scalar polynomials की तरह एक साथ multiply किया जा सकता है। उदाहरण के लिए, $\mathbf{l}(x)$ और $\mathbf{r}(x)$ को multiply करने पर प्राप्त होता है:

\begin{align*} \mathbf{l}(x)\mathbf{r}(x) &= (\begin{bmatrix} 1\\2 \end{bmatrix}x+ \begin{bmatrix} 3\\4 \end{bmatrix})( \begin{bmatrix} 2 \\ 3 \end{bmatrix}x + \begin{bmatrix} 7\\2 \end{bmatrix} )\\ &=\begin{bmatrix} 1\\2 \end{bmatrix}\circ \begin{bmatrix} 2\\3 \end{bmatrix}x^2+ \begin{bmatrix} 1\\2 \end{bmatrix}\circ \begin{bmatrix} 7\\2 \end{bmatrix}x+ \begin{bmatrix} 3\\4 \end{bmatrix}\circ \begin{bmatrix} 2\\3 \end{bmatrix}x+ \begin{bmatrix} 3\\4 \end{bmatrix}\circ \begin{bmatrix} 7\\2 \end{bmatrix}&&\\ &=\begin{bmatrix} 2\\6 \end{bmatrix}x^2+ \begin{bmatrix} 7\\4 \end{bmatrix}x+ \begin{bmatrix} 6\\12 \end{bmatrix}x+ \begin{bmatrix} 21\\8 \end{bmatrix}\\ &=\begin{bmatrix} 2\\6 \end{bmatrix}x^2+ \begin{bmatrix} 13\\16 \end{bmatrix}x+ \begin{bmatrix} 21\\8 \end{bmatrix} \end{align*}

जब हम प्रत्येक vectors को एक साथ multiply करते हैं, तो हम Hadamard product (element-wise product, जिसे $\circ$ से दर्शाया जाता है) लेते हैं।

ध्यान दें कि यदि हम परिणामी vector polynomial में $x = 2$ डालते हैं, तो हमें निम्नलिखित प्राप्त होता है:

\begin{bmatrix} 2\\6 \end{bmatrix}(2)^2+ \begin{bmatrix} 13\\16 \end{bmatrix}(2)+ \begin{bmatrix} 21\\8 \end{bmatrix}= \begin{bmatrix} 55\\64 \end{bmatrix}

यह उसी के समान है जैसे कि हम गणना करें:

\mathbf{l}(2)\circ\mathbf{r}(2) = \begin{bmatrix}5\\8\end{bmatrix}\circ\begin{bmatrix}11\\8\end{bmatrix}=\begin{bmatrix}55\\64\end{bmatrix}

दूसरे शब्दों में, दो vector polynomials को एक साथ multiply करना और फिर किसी बिंदु पर product को evaluate करना, vector polynomials को अलग-अलग evaluate करने और फिर परिणामी vectors पर Hadamard product लेने के समान है।

Vector polynomials का inner product

दो vector polynomials के inner product की गणना करने के लिए, हम उन्हें ऊपर बताए अनुसार एक साथ multiply करते हैं, लेकिन फिर vector entries को जोड़ते हैं ताकि परिणाम एक scalar बन जाए। हम इस operation को $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$ के रूप में दर्शाते हैं। Hadamard product का उपयोग करने के बजाय vector coefficients को multiply करते समय inner product का उपयोग करके हम यही चीज़ प्राप्त कर सकते हैं।

ऊपर दिए गए दो उदाहरण polynomials के लिए, यह होगा:

\langle \mathbf{l}(x), \mathbf{r}(x) \rangle = \langle \begin{align*}\end{align*} \begin{bmatrix} 1 \\ 2 \end{bmatrix} x +\begin{bmatrix} 3 \\ 4 \end{bmatrix},\begin{bmatrix}2\\3\end{bmatrix}x+\begin{bmatrix}7\\2\end{bmatrix}\rangle

=\langle \begin{bmatrix} 1 \\ 2 \end{bmatrix},\begin{bmatrix}2 \\ 3 \end{bmatrix}\rangle x^2 + \langle \begin{bmatrix} 3 \\ 4 \end{bmatrix},\begin{bmatrix}2 \\ 3 \end{bmatrix}\rangle x + \langle \begin{bmatrix} 1 \\ 2 \end{bmatrix},\begin{bmatrix}7 \\ 2 \end{bmatrix}\rangle x+\langle \begin{bmatrix} 3 \\ 4 \end{bmatrix},\begin{bmatrix}7 \\ 2 \end{bmatrix}\rangle

=(1\cdot2+2\cdot3)x^2+(3\cdot2+4\cdot3)x + (1\cdot7+2\cdot2) x + (3\cdot7+4\cdot2)

=8x^2 + 18x + 11x + 29

=8x^2 + 29x + 29

ध्यान दें कि $\langle\mathbf{l}(2), \mathbf{r}(2)\rangle$ बिल्कुल $x = 2$ पर evaluate किए गए $\langle \mathbf{l}(x), \mathbf{r}(x)\rangle$ के समान है। यानी, $\langle [5, 8], [11, 8]\rangle = 119$ और $8(2)^2 + 29(2) + 29 = 119$ ।

सामान्य रूप से यह क्यों काम करता है

मान लीजिए कि हमने vector polynomials को “सामान्य” तरीके से एक साथ multiply किया – यानी हम inner product के बजाय coefficients का elementwise-product (Hadamard product) लेते हैं। प्रत्येक coefficients का inner product बस प्रत्येक coefficients के Hadamard product के terms का योग (sum) होता है।

इसलिए, हम कह सकते हैं कि यदि हमारे पास दो vector polynomials $\mathbf{l}(x)$ और $\mathbf{r}(x)$ हैं, और हम उन्हें $\mathbf{t}(x)=\mathbf{l}(x)\mathbf{r}(x)$ के रूप में एक साथ multiply करते हैं, तो $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$ का inner product, $\mathbf{t}$ के coefficients के element-wise योग के बराबर होता है। ध्यान दें कि दो vector polynomials के multiplication से एक vector polynomial प्राप्त होता है, लेकिन दो vector polynomials के inner product से एक ऐसा polynomial प्राप्त होता है जहाँ सभी coefficients scalars होते हैं।

Zero knowledge inner product proof

Zero knowledge multiplication पर पिछले अध्याय में, हमने यह प्रदर्शित किया था कि हमारे पास एक वैध multiplication है, यह साबित करके कि दो linear polynomials के constant terms का product, उन polynomials के product में constant term के बराबर होता है।

Inner product की सही गणना को साबित करने के लिए, हम polynomials को vector polynomials से बदल देते हैं और हम scalar polynomials के multiplication को vector polynomials के inner product से बदल देते हैं।

बाकी सब कुछ समान रहता है।

Algorithm

लक्ष्य यह है कि prover, verifier को यह विश्वास दिलाए कि $A$ , $\mathbf{a}$ और $\mathbf{b}$ का commitment है, $V$ , $v$ का commitment है, और यह कि $\langle \mathbf{a}, \mathbf{b} \rangle = v$ है, बिना $\mathbf{a}$ , $\mathbf{b}$ , या $v$ को प्रकट किए।

Setup

Prover और verifier इस पर सहमत होते हैं:

basis vectors $\mathbf{G}$ और $\mathbf{H}$ जिनके साथ prover vectors को commit कर सकता है
elliptic curve point $G$ ( $\mathbf{G}$ से अलग) जिसका उपयोग $t(x)$ के coefficients और $V$ में commit किए गए inner product को commit करने के लिए किया जाएगा
blinding terms के लिए elliptic curve point $B$

Prover

Prover blinding terms $\alpha$ , $\beta$ , $\gamma$ , $\tau_1$ , और $\tau_2$ जनरेट करता है और गणना करता है:

\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 &= vG + \gamma B \\ T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle )G + \tau_1B\\ T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle G + \tau_2B \end{align}

ध्यान दें कि इस बार linear coefficients $\mathbf{s}_L$ और $\mathbf{s}_R$ scalars के बजाय vectors हैं। Prover $(A, S, V, T_1, T_2)$ को verifier के पास भेजता है। Verifier द्वारा एक random $u$ के साथ प्रतिक्रिया देने के बाद, prover $u$ पर $\mathbf{l}(x)$ , $\mathbf{r}(x)$ , और उनके inner product $\mathbf{t}(x)$ को evaluate करता है।

\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 &= 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*}

अंतिम verification चरण

सबसे पहले, verifier जाँचता है कि $t_u$ , $u$ पर evaluate किए गए $\mathbf{l}_u$ और $\mathbf{r}_u$ का inner product है।

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

यदि prover ईमानदार है तो यह सही होना चाहिए, क्योंकि $u$ पर evaluate किए गए polynomials का inner product, $x = u$ पर evaluate किए गए vector polynomials $\mathbf{l}_x$ और $\mathbf{r}_x$ के inner product के समान होता है।

दूसरा, verifier जाँचता है कि $A$ और $S$ क्रमशः $\mathbf{l}$ और $\mathbf{r}$ के constant और linear terms के commitments हैं।

A + Su \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle + \pi_{lr} B

याद करें कि $A$ और $S$ क्रमशः $\mathbf{l}$ और $\mathbf{r}$ के constant और linear terms के commitments हैं और $\pi_{lr}$ क्रमशः $A$ और $S$ में blinding terms $\alpha$ और $\beta$ का योग है।

अंत में, verifier जाँचता है कि $t_u$ , $V, T_1, T_2$ पर commit किए गए quadratic polynomial का evaluation है:

t_uG + \pi_tB \stackrel{?}{=} V + T_1 u + T_2 u^2

Proof size में सुधार करना

जब prover $(\mathbf{l}, \mathbf{r}, t, T_1, T_2, \pi)$ भेजता है, तो prover $2n$ elements (जो $\mathbf{l}$ और $\mathbf{r}$ की लंबाई है) भेजता है जो कि succinct नहीं है।

आने वाले अध्यायों में हम सीखेंगे कि proof के size को कैसे कम किया जाए। $\log n$ size का एक proof बनाना संभव है जो यह बताए कि एक inner product सही है। यानी, यदि हम यह साबित करना चाहते हैं कि हमने $n$ लंबाई के दो vectors के inner product की गणना की है, तो proof का size केवल $\log n$ होगा – जो exponentially छोटा है।

विशेष रूप से, हम वास्तविक vectors के बजाय $\mathbf{l}_u$ और $\mathbf{r}_u$ के लिए एक commitment भेजकर $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$ चरण को optimize करेंगे, साथ ही यह दिखाने के लिए एक logarithmic size proof भेजेंगे कि commitment उन vectors को होल्ड करता है जिनका inner product $t_u$ है।

सारांश

हमने एक protocol का वर्णन किया है जो यह साबित करता है कि $A$ , $\mathbf{a}$ और $\mathbf{b}$ का commitment है, $V$ , $v$ का commitment है, और यह कि $\langle \mathbf{a}, \mathbf{b} \rangle = v$ है, बिना $\mathbf{a}$ , $\mathbf{b}$ , या $v$ को प्रकट किए। हालाँकि, proof का size linear है, क्योंकि $(\mathbf{l}_u, \mathbf{r}_u, t, T_1, T_2, \pi_{lr},\pi_t)$ में $\mathbf{l}_u$ और $\mathbf{r}_u$ प्रत्येक का size $n$ है।

Exercise: इस lecture में algorithm को implement करने के लिए missing code भरें। यह साबित करें कि आप एक $n=4$ vector के inner product को उसे प्रकट किए बिना जानते हैं। ध्यान दें कि numpy arrays element-wise addition और multiplication की अनुमति देते हैं। उदाहरण के लिए:

import numpy as np
a = np.array([1,2,3,4])
b = np.array([2,2,2,2])

print(a + b) # np.array([3,4,5,6])
print(a * b) # np.array([2,4,6,8])
print(numpy.inner(a, b)) # 20

# casting a numpy array to numpy doesn't do anything
print(np.array(a) + b) # np.array([3,4,5,6])

निम्नलिखित code भरें:

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 = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
     (FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
     (FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
     (FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]

H = [(FQ(13728162449721098615672844430261112538072166300311022796820929618959450231493), FQ(12153831869428634344429877091952509453770659237731690203490954547715195222919)),
    (FQ(17471368056527239558513938898018115153923978020864896155502359766132274520000), FQ(4119036649831316606545646423655922855925839689145200049841234351186746829602)),
    (FQ(8730867317615040501447514540731627986093652356953339319572790273814347116534), FQ(14893717982647482203420298569283769907955720318948910457352917488298566832491)),
    (FQ(419294495583131907906527833396935901898733653748716080944177732964425683442), FQ(14467906227467164575975695599962977164932514254303603096093942297417329342836))]

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(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 = np.array([89,15,90,22])
b = np.array([16,18,54,12])
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(np.inner(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 == np.mod(np.inner(np.array(l_u), np.array(r_u)), p), "tu !=〈lu, ru〉"
assert eq(add(A, commit(S, u)), add_points(vector_commit(G, l_u), vector_commit(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)), add_points(V, multiply(T1, u), multiply(T2, u**2 % p))), "t_u not evaluated correctly"

यह ट्यूटोरियल ZK Bulletproofs पर एक सीरीज़ का हिस्सा है।