Una prueba de conocimiento cero para el producto interno

Last updated on Nov 13, 2024

Un argumento de producto interno es una prueba de que el probador realizó el cálculo del producto interno correctamente. Este capítulo muestra cómo construir una prueba de conocimiento cero para un argumento de producto interno.

En el capítulo anterior, mostramos cómo multiplicar dos escalares juntos con conocimiento cero: nos comprometemos con dos polinomios de grado uno, probamos que calculamos correctamente su producto, y luego demostramos que el término constante de los polinomios de grado uno son los compromisos de los factores secretos que estamos multiplicando.

Si los coeficientes de nuestro polinomio son vectores en lugar de escalares, entonces podemos probar que calculamos el producto interno del vector correctamente. Ahora introducimos el polinomio vectorial.

Polinomios vectoriales: polinomios con vectores como coeficientes

Los siguientes son dos polinomios con coeficientes vectoriales:

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

Evaluar un polinomio vectorial produce otro vector. Por ejemplo, $\mathbf{l}(2)$ produce

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

y evaluar $\mathbf{r}$ en 2 devuelve:

\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)$ y $\mathbf{r}(x)$ se escriben en negrita ya que producen vectores cuando se evalúan en algún escalar $x$ .

Multiplicación de polinomios vectoriales

Los polinomios vectoriales se pueden multiplicar entre sí al igual que los polinomios escalares. Por ejemplo, multiplicar $\mathbf{l}(x)$ y $\mathbf{r}(x)$ da como resultado:

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

Cuando multiplicamos cada uno de los vectores entre sí, tomamos el producto de Hadamard (producto elemento por elemento, denotado con $\circ$ ).

Ten en cuenta que si sustituimos $x = 2$ en el polinomio vectorial resultante, obtenemos lo siguiente:

\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}

Esto es lo mismo que si calculamos:

\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}

En otras palabras, multiplicar dos polinomios vectoriales entre sí y luego evaluar el producto en algún punto es lo mismo que evaluar los polinomios vectoriales por separado y luego aplicar el producto de Hadamard a los vectores resultantes.

Producto interno de polinomios vectoriales

Para calcular el producto interno de dos polinomios vectoriales, los multiplicamos entre sí como se describió anteriormente, pero luego sumamos las entradas del vector para que el resultado se convierta en un escalar. Denotamos esta operación como $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$ . Podemos lograr lo mismo utilizando el producto interno cuando multiplicamos los coeficientes vectoriales en lugar de usar el producto de Hadamard.

Para los dos polinomios de ejemplo anteriores, esto sería:

\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

Observa que $\langle\mathbf{l}(2), \mathbf{r}(2)\rangle$ es lo mismo que $\langle \mathbf{l}(x), \mathbf{r}(x)\rangle$ evaluado en $x = 2$ . Es decir, $\langle [5, 8], [11, 8]\rangle = 119$ y $8(2)^2 + 29(2) + 29 = 119$ .

Por qué esto funciona en general

Supongamos que multiplicamos los polinomios vectoriales de la manera “normal”, es decir, tomamos el producto elemento por elemento (producto de Hadamard) de los coeficientes en lugar del producto interno. El producto interno de cada uno de los coeficientes es simplemente la suma de los términos del producto de Hadamard de cada uno de los coeficientes.

Por lo tanto, podemos decir que si tenemos dos polinomios vectoriales $\mathbf{l}(x)$ y $\mathbf{r}(x)$ , y los multiplicamos entre sí como $\mathbf{t}(x)=\mathbf{l}(x)\mathbf{r}(x)$ , entonces el producto interno de $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$ es igual a la suma elemento por elemento de los coeficientes de $\mathbf{t}$ . Ten en cuenta que la multiplicación de dos polinomios vectoriales da como resultado un polinomio vectorial, pero el producto interno de dos polinomios vectoriales da como resultado un polinomio donde todos los coeficientes son escalares.

Prueba de conocimiento cero del producto interno

En el capítulo anterior sobre multiplicación con conocimiento cero, demostramos que tenemos una multiplicación válida al probar que el producto de los términos constantes de dos polinomios lineales es igual al término constante en el producto de los polinomios.

Para probar el cálculo correcto de un producto interno, reemplazamos los polinomios con polinomios vectoriales y reemplazamos la multiplicación de polinomios escalares con el producto interno de polinomios vectoriales.

Todo lo demás permanece igual.

El algoritmo

El objetivo es que el probador convenza al verificador de que $A$ es un compromiso con $\mathbf{a}$ y $\mathbf{b}$ , $V$ es un compromiso con $v$ , y que $\langle \mathbf{a}, \mathbf{b} \rangle = v$ sin revelar $\mathbf{a}$ , $\mathbf{b}$ , ni $v$ .

Configuración

El probador y el verificador acuerdan en:

los vectores base $\mathbf{G}$ y $\mathbf{H}$ con los cuales el probador puede comprometer los vectores
el punto de la curva elíptica $G$ (distinto de $\mathbf{G}$ ) que se utilizará para comprometer los coeficientes de $t(x)$ y el producto interno comprometido en $V$
el punto de la curva elíptica $B$ para los términos de cegado

Probador

El probador genera los términos de cegado $\alpha$ , $\beta$ , $\gamma$ , $\tau_1$ y $\tau_2$ y calcula:

\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}

Ten en cuenta que esta vez los coeficientes lineales $\mathbf{s}_L$ y $\mathbf{s}_R$ son vectores en lugar de escalares. El probador transmite $(A, S, V, T_1, T_2)$ al verificador. Después de que el verificador responde con un $u$ aleatorio, el probador evalúa $\mathbf{l}(x)$ , $\mathbf{r}(x)$ , y su producto interno $\mathbf{t}(x)$ en $u$ .

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

Paso final de verificación

Primero, el verificador comprueba que $t_u$ es el producto interno de $\mathbf{l}_u$ y $\mathbf{r}_u$ evaluado en $u$ .

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

Esto debería cumplirse si el probador es honesto, porque el producto interno de los polinomios evaluado en $u$ es el mismo que el producto interno de los polinomios vectoriales $\mathbf{l}_x$ y $\mathbf{r}_x$ evaluado en $x = u$ .

En segundo lugar, el verificador comprueba que $A$ y $S$ son compromisos con los términos constante y lineal de $\mathbf{l}$ y $\mathbf{r}$ respectivamente.

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

Recuerda que $A$ y $S$ son compromisos con los términos constante y lineal de $\mathbf{l}$ y $\mathbf{r}$ , y $\pi_{lr}$ es la suma de los términos de cegado $\alpha$ y $\beta$ en $A$ y $S$ respectivamente.

Finalmente, el verificador comprueba que $t_u$ es la evaluación del polinomio cuadrático comprometido en $V, T_1, T_2$ :

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

Mejora del tamaño de la prueba

Cuando el probador envía $(\mathbf{l}, \mathbf{r}, t, T_1, T_2, \pi)$ , transmite $2n$ elementos (la longitud de $\mathbf{l}$ y $\mathbf{r}$ ), lo cual no es sucinto.

En los siguientes capítulos aprenderemos cómo reducir el tamaño de la prueba. Es posible crear una prueba de tamaño $\log n$ de que un producto interno es correcto. Es decir, si quisiéramos probar que calculamos el producto interno de dos vectores de longitud $n$ , entonces la prueba solo tendría un tamaño de $\log n$ , siendo exponencialmente más pequeña.

Específicamente, optimizaremos el paso $t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ y $A + Su \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle + \pi_{lr} B$ enviando un compromiso con $\mathbf{l}_u$ y $\mathbf{r}_u$ en lugar de los vectores reales, junto con una prueba de tamaño logarítmico para demostrar que el compromiso contiene los vectores cuyo producto interno es $t_u$ .

Resumen

Hemos descrito un protocolo que prueba que $A$ es un compromiso con $\mathbf{a}$ y $\mathbf{b}$ , $V$ es un compromiso con $v$ , y que $\langle \mathbf{a}, \mathbf{b} \rangle = v$ sin revelar $\mathbf{a}$ , $\mathbf{b}$ , ni $v$ . El tamaño de la prueba, sin embargo, es lineal, ya que $\mathbf{l}_u$ y $\mathbf{r}_u$ en $(\mathbf{l}_u, \mathbf{r}_u, t, T_1, T_2, \pi_{lr},\pi_t)$ tienen cada uno un tamaño $n$ .

Ejercicio: Completa el código que falta para implementar el algoritmo de esta lección. Prueba que conoces el producto interno para un vector de $n=4$ sin revelarlo. Ten en cuenta que los arrays de numpy permiten la adición y multiplicación elemento por elemento. Por ejemplo:

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])

Completa el siguiente código:

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"

Este tutorial es parte de una serie sobre ZK Bulletproofs.