Multiplicación de Conocimiento Cero

Last updated on Aug 20, 2025

Multiplicación de Conocimiento Cero de Polinomios

Usando el esquema de compromiso polinómico del capítulo anterior, un probador (prover) puede demostrar que tiene tres polinomios $l(x)$ , $r(x)$ y $t(x)$ y probar que $t(x) = l(x)r(x)$ .

Para que este algoritmo funcione, el verificador debe creer que las evaluaciones polinómicas son correctas – pero esto es algo que mostramos en el capítulo anterior. La mayoría de los pasos aquí son simplemente repetir el algoritmo de compromiso polinómico que hicimos previamente.

A un alto nivel, el probador se compromete con $l(x)$ , $r(x)$ y $t(x)$ y envía los compromisos al verificador. Luego, el verificador elige un valor aleatorio para $x$ como $u$ y le pide al probador que evalúe los polinomios en $u$ . El verificador entonces comprueba que las evaluaciones se hicieron correctamente y que la evaluación de $l(x)$ multiplicada por la evaluación de $r(x)$ es igual a la evaluación de $t(x)$ .

Por ejemplo, supongamos que el primer polinomio es $l(x)=2x$ y el segundo es $r(x) = x + 1$ . Entonces $t(x)=2x(x+1) = 2x^2+2$ . El verificador puede muestrear cualquier valor aleatorio $x$ , y el resultado del producto $l(x)r(x)$ será $t(x)$ . El gráfico a continuación muestra un ejemplo donde el verificador elige $x=2$ :

El verificador luego comprobaría que $3 \times 4 = 12$ y aceptaría la afirmación del probador.

El lema de Schwartz-Zippel establece que si $f(x) \neq g(x)$ entonces la probabilidad de que $f(u) = g(u)$ para algún valor aleatorio $u$ es menor que $d/p$ donde $d$ es el grado máximo de los dos polinomios y $p$ es el orden del campo finito. Si $d \ll p$ ( $d$ mucho menor que $p$ ), entonces la probabilidad de que $u$ sea un punto de intersección de dos polinomios no iguales es insignificante.

Específicamente, supongamos que el probador está mintiendo y $l(x)r(x) \neq t(x)$ . En ese caso, para un $u$ aleatorio, $l(u)r(u) \neq t(u)$ con una probabilidad extremadamente alta. Si $l(x)r(x) \neq t(x)$ , entonces $l(x)r(x)$ y $t(x)$ solo se intersectan en como máximo $d$ puntos (el grado máximo ya sea de $l(x)r(x)$ o de $t(x)$ ), y es extremadamente improbable que el verificador elija aleatoriamente un $u$ que sea uno de los $d$ puntos de intersección.

Para tener una idea de la escala, $d$ en nuestro caso es 2, pero el orden de la curva de nuestras curvas elípticas (y por lo tanto el orden del campo) es de aproximadamente $2^{254}$ . Así que si $t(x) \neq l(x)r(x)$ , entonces la probabilidad de $t(u) = l(u)r(u)$ es $1/2^{253}$ , la cual es insignificantemente pequeña.

Ahora describimos el algoritmo en detalle, y luego mostramos una optimización.

Pasos para probar el conocimiento de la multiplicación de polinomios

El probador se compromete con dos polinomios lineales (de grado 1) $l(x)$ , $r(x)$ , un polinomio cuadrático (de grado 2) $t(x)$ , y envía los compromisos al verificador. El verificador responde con un valor aleatorio $u$ , y el probador evalúa $l_u = l(u)$ , $r_u = r(u)$ , y $t_u = t(u)$ junto con las pruebas de evaluación $\pi_l, \pi_r, \pi_t$ . El verificador comprueba que todos los polinomios fueron evaluados correctamente y que $t_u = l_ur_u$ .

Configuración

El probador y el verificador acuerdan los puntos de la curva elíptica $G$ y $B$ con una relación de logaritmo discreto desconocida (es decir, los puntos se eligen aleatoriamente).

El probador se compromete con $l(x)$ , $r(x)$ y $t(x)$

El probador crea tres polinomios:

\begin{align*} l(x) &= a + s_Lx \\ r(x) &= b + s_Rx \\ t(x) &= l(x)r(x) = (a + s_Lx)(b + s_Rx) = ab+(as_R+bs_L)x+s_Ls_Rx^2\\ \end{align*}

Por lo tanto, necesitan producir un total de 7 compromisos de Pedersen para cada uno de los coeficientes, lo que requerirá siete términos de cegamiento $\alpha_0, \alpha_1, \beta_0, \beta_1, \tau_0, \tau_1, \tau_2$

\begin{align*} L_0&=aG + \alpha_0B &&\text{// coeficiente constante de }l(x)\\ L_1&=s_LG + \alpha_1B &&\text{// coeficiente lineal de }l(x)\\ \\ R_0&=bG + \beta_0B &&\text{// coeficiente constante de }r(x)\\ R_1&=s_RG + \beta_1B &&\text{// coeficiente lineal de }r(x)\\ \\ T_0 &= abG + \tau_0 B &&\text{// coeficiente constante de }t(x)\\ T_1 &=(as_R + bs_L)G + \tau_1B &&\text{// coeficiente lineal de }t(x)\\ T_2 &= s_Ls_RG + \tau_2B &&\text{// coeficiente cuadrático de }t(x) \end{align*}

El probador envía $(L_0, L_1, R_0, R_1, T_0, T_1, T_2)$ al verificador.

El verificador genera un escalar aleatorio $u$

… y envía el elemento del campo $u$ al probador.

El probador evalúa los tres polinomios y crea tres pruebas

El probador sustituye $u$ en los polinomios y calcula la suma de los términos de cegamiento de los compromisos de los coeficientes polinómicos cuando se aplica $u$ .

\begin{align*} l_u &= a + s_Lu\\ r_u &= b + s_Ru\\ t_u &= ab + (as_R + bs_l)u + s_Ls_Ru^2\\ \\ \pi_l &= \alpha_0 + \alpha_1u \\ \pi_r &= \beta_0 + \beta_1u \\ \pi_t &= \tau_0 + \tau_1u + \tau_2u^2 \end{align*}

El probador envía los valores $(l_u, r_u, t_u, \pi_l, \pi_r, \pi_t)$ al verificador. Ten en cuenta que todos estos son elementos del campo, no puntos de la curva elíptica.

Paso final de verificación

El verificador comprueba que cada uno de los polinomios fue evaluado correctamente y que la evaluación de $t(u)$ es el producto de la evaluación de $l(u)$ y $r(u)$ . Las primeras tres comprobaciones son pruebas de que el polinomio se evaluó correctamente con respecto al compromiso de los coeficientes, y la última comprobación verifica que la salida de los polinomios tiene la relación de producto afirmada.

\begin{align*} l_uG + \pi_l B &\stackrel{?}= L_0+L_1u &&\text{// Comprobar que }l(u) \text{ fue evaluado correctamente}\\ r_uG + \pi_r B &\stackrel{?}= R_0+R_1u &&\text{// Comprobar que }r(u) \text{ fue evaluado correctamente}\\ t_uG + \pi_t B &\stackrel{?}= T_0+T_1u+T_2u^2&&\text{// Comprobar que }t(u) \text{ fue evaluado correctamente}\\ t_u &\stackrel{?}= l_ur_u &&\text{// Comprobar que }t(u)=l(u)r(u) \end{align*}

Cuando expandimos los términos, vemos que se equilibran si el probador fue honesto:

\begin{align*} \underbrace{(a + s_Lu)}_{l_u}G + \underbrace{(\alpha_0 + \alpha_1u)}_{\pi_l} B &\stackrel{?}= \underbrace{(aG + \alpha_0B)}_{L_0}+\underbrace{(s_LG + \alpha_1B)}_{L_1}u \\ \underbrace{(b + s_Ru)}_{r_u}G + \underbrace{(\beta_0 + \beta_1u)}_{\pi_r} B &\stackrel{?}= \underbrace{(bG + \beta_0B)}_{R_0}+\underbrace{(s_RG + \beta_1B)}_{R_1}u \\ \underbrace{(ab + (as_R + bs_l)u + s_Ls_Ru^2)}_{t_u}G + \underbrace{(\tau_0 + \tau_1u + \tau_2u^2)}_{\pi_t} B &\stackrel{?}= \underbrace{(abG + \tau_0 B)}_{T_0}+\underbrace{(as_R + bs_L+ \tau_1B)}_{T_1}u+\underbrace{(s_Ls_R+ \tau_2B)}_{T_2}u^2 \\ t_u &\stackrel{?}= l_ur_u \end{align*}

Optimización: enviando menos compromisos

En el primer paso, el probador envía 7 puntos de la curva elíptica, y en el paso final, el verificador comprueba 4 igualdades. Podemos mejorar el algoritmo para enviar solo 5 puntos de la curva elíptica y hacer 3 comprobaciones de igualdad.

Esto se hace poniendo los coeficientes constantes de $l(x)$ y $r(x)$ en un solo compromiso y los coeficientes lineales de esos polinomios en un compromiso separado. A modo de recordatorio, definimos $l(x)$ y $r(x)$ como

\begin{align*} l(x) &= a + s_Lx \\ r(x) &= b + s_Rx \\ \end{align*}

así que $a$ y $b$ son los coeficientes constantes, y $s_L$ y $s_R$ son los coeficientes lineales.

Esto es similar a cómo comprometeríamos un vector. En cierto sentido, estamos comprometiendo los coeficientes constantes como un vector y los coeficientes lineales como otro vector.

Configuración

Durante la configuración, ahora necesitamos 3 puntos de la curva elíptica: $G$ , $H$ y $B$ .

Compromiso polinómico

\begin{align*} A &= aG + bH + \alpha B &&\text{// comprometer los términos constantes}\\ S &= s_LG + s_RH + \beta B &&\text{// comprometer los términos lineales}\\ T_0 &= abG + \tau_0 B &&\text{// comprometer el coeficiente constante de } t(x) \\ T_1 &=(as_R + bs_L)G + \tau_1B &&\text{// coeficiente lineal de }t(x)\\ T_2 &= s_Ls_RG + \tau_2B &&\text{// coeficiente cuadrático de }t(x) \end{align*}

Nota que los coeficientes de $l(x)$ se aplican a $G$ y los coeficientes de $r(x)$ se aplican a $H$ . El probador envía $(A, S, T_0, T_1, T_2)$ al verificador, quien responde con $u$ .

Evaluación polinómica

\begin{align*} l_u &= l(u) = a + s_Lu\\ r_u &= r(u) = b + s_Ru\\ t_u &= t(u) = l(u)r(u) = ab + (as_R + bs_L)u + s_Ls_Ru^2\\ \pi_{lr} &= \alpha + \beta u \\ \pi_t &= \tau_0 + \tau_1u + \tau_2u^2 \end{align*}

$l_u$ , $r_u$ , $t_u$ , $\pi_{lr}$ y $\pi_t$ se calculan como antes, pero la prueba de evaluaciones para $l(x)$ y $r(x)$ , que antes eran $\pi_l$ y $\pi_r$ , se combinan en una sola: $\pi_{lr}$ .

Verificación final

\begin{align*} A + Su &\stackrel{?}= l_uG + r_uH+\pi_{lr}B \\ t_uG + \pi_tB &\stackrel{?}= T_0 + T_1u + T_2u^2 \\ t_u &\stackrel{?}= l_ur_u \end{align*}

La comprobación $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ se expande a

\underbrace{(aG + bH + \alpha B)}_A + \underbrace{(s_LG + s_RH + \beta B)u}_{Su} = \underbrace{(a + s_Lu)}_{l_u}G + \underbrace{(b + s_Ru)}_{r_u}H + \underbrace{(\alpha + \beta u)}_{\pi_{lr}}B

Con cierta reorganización en el lado izquierdo, podemos ver que la comprobación de igualdad verifica simultáneamente que tanto $l(x)$ como $r(x)$ fueron evaluados correctamente.

(a + s_Lu)G + (b + s_Ru)H + (\alpha + \beta u)B=\underbrace{(a + s_Lu)}_{l_u}G + \underbrace{(b + s_Ru)}_{r_u}H + \underbrace{(\alpha + \beta u)}_{\pi_{lr}}B

Como otra forma de ver la comprobación $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ , considera la siguiente visualización:

\begin{align*} A &= &aG& + &bH &+ &\alpha B\\ Su &= &s_LuG& + &s_RuH &+ &\beta u B\\ &&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\\ &&l(u)G&&r(u)H&&\pi_{lr}B \end{align*}

Multiplicación de Conocimiento Cero de Escalares

Nuestra prueba de que multiplicamos dos polinomios correctamente para obtener un tercero puede ser usada para probar que multiplicamos dos escalares para obtener un tercero. No se necesitan cambios en el algoritmo, solo un cambio menor en la semántica (cómo interpretamos los compromisos).

Supongamos que queremos probar que llevamos a cabo la multiplicación $ab = v$ .

Planteamiento del problema

$A$ es un compromiso de $a$ y $b$ , y $V$ es un compromiso de $v$ donde $v = ab$ . Deseamos probar que $A$ y $V$ están comprometidos según lo afirmado sin revelar $a$ , $b$ o $v$ .

Solución

La idea a alto nivel es que un escalar puede convertirse en un polinomio agregando un término lineal elegido arbitrariamente, por ejemplo, $a$ se convierte en $a + s_Lx$ y $b$ se convierte en $b + s_Rx$ . $s_L$ y $s_R$ son elegidos aleatoriamente por el probador.

Cuando los polinomios $a + s_Lx$ y $b + s_Rx$ se multiplican entre sí, la multiplicación de $ab$ ocurre “dentro” de la multiplicación polinómica.

(a + s_Lx)(b + s_Rx) = \boxed{ab} + (as_R + bs_L)x + s_Ls_rx^2

Recuerda que el probador comienza el algoritmo enviando compromisos:

\begin{align*} A &= aG + bH + \alpha B &&\text{// compromiso de }a\text{ y }b\\ S &= s_LG + s_RH + \beta B &&\text{// comprometer los términos lineales}\\ V &= abG + \tau_0 B &&\text{// comprometer el producto V} \\ T_1 &=(as_R + bS_L)G + \tau_1B &&\text{// coeficiente lineal de }t(x)\\ T_2 &= s_Ls_RG + \tau_2B &&\text{// coeficiente cuadrático de }t(x) \end{align*}

Simplemente cambiamos la “interpretación” de $A$ de ser los términos constantes de los polinomios a las constantes $a$ y $b$ que estamos multiplicando. Cambiamos $T_0$ a $V$ para reflejar el cambio de interpretación como un compromiso de $V$ en la multiplicación que estamos tratando de probar que hicimos correctamente, es decir, $v = ab$ .

Ejercicio: Completa el código Python faltante para implementar el algoritmo descrito anteriormente.

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"

Aprende más

Este artículo es parte de una serie sobre Bulletproof ZKPs.

Last updated on Aug 20, 2025

Multiplicación de Conocimiento Cero de Polinomios

Usando el esquema de compromiso polinómico del capítulo anterior, un probador (prover) puede demostrar que tiene tres polinomios $l(x)$ , $r(x)$ y $t(x)$ y probar que $t(x) = l(x)r(x)$ .

El verificador luego comprobaría que $3 \times 4 = 12$ y aceptaría la afirmación del probador.

Ahora describimos el algoritmo en detalle, y luego mostramos una optimización.

Pasos para probar el conocimiento de la multiplicación de polinomios

Configuración

El probador y el verificador acuerdan los puntos de la curva elíptica $G$ y $B$ con una relación de logaritmo discreto desconocida (es decir, los puntos se eligen aleatoriamente).

El probador se compromete con $l(x)$ , $r(x)$ y $t(x)$

El probador crea tres polinomios:

\begin{align*} l(x) &= a + s_Lx \\ r(x) &= b + s_Rx \\ t(x) &= l(x)r(x) = (a + s_Lx)(b + s_Rx) = ab+(as_R+bs_L)x+s_Ls_Rx^2\\ \end{align*}

\begin{align*} L_0&=aG + \alpha_0B &&\text{// coeficiente constante de }l(x)\\ L_1&=s_LG + \alpha_1B &&\text{// coeficiente lineal de }l(x)\\ \\ R_0&=bG + \beta_0B &&\text{// coeficiente constante de }r(x)\\ R_1&=s_RG + \beta_1B &&\text{// coeficiente lineal de }r(x)\\ \\ T_0 &= abG + \tau_0 B &&\text{// coeficiente constante de }t(x)\\ T_1 &=(as_R + bs_L)G + \tau_1B &&\text{// coeficiente lineal de }t(x)\\ T_2 &= s_Ls_RG + \tau_2B &&\text{// coeficiente cuadrático de }t(x) \end{align*}

El probador envía $(L_0, L_1, R_0, R_1, T_0, T_1, T_2)$ al verificador.

El verificador genera un escalar aleatorio $u$

… y envía el elemento del campo $u$ al probador.

El probador evalúa los tres polinomios y crea tres pruebas

El probador sustituye $u$ en los polinomios y calcula la suma de los términos de cegamiento de los compromisos de los coeficientes polinómicos cuando se aplica $u$ .

\begin{align*} l_u &= a + s_Lu\\ r_u &= b + s_Ru\\ t_u &= ab + (as_R + bs_l)u + s_Ls_Ru^2\\ \\ \pi_l &= \alpha_0 + \alpha_1u \\ \pi_r &= \beta_0 + \beta_1u \\ \pi_t &= \tau_0 + \tau_1u + \tau_2u^2 \end{align*}

El probador envía los valores $(l_u, r_u, t_u, \pi_l, \pi_r, \pi_t)$ al verificador. Ten en cuenta que todos estos son elementos del campo, no puntos de la curva elíptica.

Paso final de verificación

\begin{align*} l_uG + \pi_l B &\stackrel{?}= L_0+L_1u &&\text{// Comprobar que }l(u) \text{ fue evaluado correctamente}\\ r_uG + \pi_r B &\stackrel{?}= R_0+R_1u &&\text{// Comprobar que }r(u) \text{ fue evaluado correctamente}\\ t_uG + \pi_t B &\stackrel{?}= T_0+T_1u+T_2u^2&&\text{// Comprobar que }t(u) \text{ fue evaluado correctamente}\\ t_u &\stackrel{?}= l_ur_u &&\text{// Comprobar que }t(u)=l(u)r(u) \end{align*}

Cuando expandimos los términos, vemos que se equilibran si el probador fue honesto:

\begin{align*} \underbrace{(a + s_Lu)}_{l_u}G + \underbrace{(\alpha_0 + \alpha_1u)}_{\pi_l} B &\stackrel{?}= \underbrace{(aG + \alpha_0B)}_{L_0}+\underbrace{(s_LG + \alpha_1B)}_{L_1}u \\ \underbrace{(b + s_Ru)}_{r_u}G + \underbrace{(\beta_0 + \beta_1u)}_{\pi_r} B &\stackrel{?}= \underbrace{(bG + \beta_0B)}_{R_0}+\underbrace{(s_RG + \beta_1B)}_{R_1}u \\ \underbrace{(ab + (as_R + bs_l)u + s_Ls_Ru^2)}_{t_u}G + \underbrace{(\tau_0 + \tau_1u + \tau_2u^2)}_{\pi_t} B &\stackrel{?}= \underbrace{(abG + \tau_0 B)}_{T_0}+\underbrace{(as_R + bs_L+ \tau_1B)}_{T_1}u+\underbrace{(s_Ls_R+ \tau_2B)}_{T_2}u^2 \\ t_u &\stackrel{?}= l_ur_u \end{align*}

Optimización: enviando menos compromisos

\begin{align*} l(x) &= a + s_Lx \\ r(x) &= b + s_Rx \\ \end{align*}

así que $a$ y $b$ son los coeficientes constantes, y $s_L$ y $s_R$ son los coeficientes lineales.

Esto es similar a cómo comprometeríamos un vector. En cierto sentido, estamos comprometiendo los coeficientes constantes como un vector y los coeficientes lineales como otro vector.

Configuración

Durante la configuración, ahora necesitamos 3 puntos de la curva elíptica: $G$ , $H$ y $B$ .

Compromiso polinómico

\begin{align*} A &= aG + bH + \alpha B &&\text{// comprometer los términos constantes}\\ S &= s_LG + s_RH + \beta B &&\text{// comprometer los términos lineales}\\ T_0 &= abG + \tau_0 B &&\text{// comprometer el coeficiente constante de } t(x) \\ T_1 &=(as_R + bs_L)G + \tau_1B &&\text{// coeficiente lineal de }t(x)\\ T_2 &= s_Ls_RG + \tau_2B &&\text{// coeficiente cuadrático de }t(x) \end{align*}

Nota que los coeficientes de $l(x)$ se aplican a $G$ y los coeficientes de $r(x)$ se aplican a $H$ . El probador envía $(A, S, T_0, T_1, T_2)$ al verificador, quien responde con $u$ .

Evaluación polinómica

\begin{align*} l_u &= l(u) = a + s_Lu\\ r_u &= r(u) = b + s_Ru\\ t_u &= t(u) = l(u)r(u) = ab + (as_R + bs_L)u + s_Ls_Ru^2\\ \pi_{lr} &= \alpha + \beta u \\ \pi_t &= \tau_0 + \tau_1u + \tau_2u^2 \end{align*}

$l_u$ , $r_u$ , $t_u$ , $\pi_{lr}$ y $\pi_t$ se calculan como antes, pero la prueba de evaluaciones para $l(x)$ y $r(x)$ , que antes eran $\pi_l$ y $\pi_r$ , se combinan en una sola: $\pi_{lr}$ .

Verificación final

\begin{align*} A + Su &\stackrel{?}= l_uG + r_uH+\pi_{lr}B \\ t_uG + \pi_tB &\stackrel{?}= T_0 + T_1u + T_2u^2 \\ t_u &\stackrel{?}= l_ur_u \end{align*}

La comprobación $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ se expande a

\underbrace{(aG + bH + \alpha B)}_A + \underbrace{(s_LG + s_RH + \beta B)u}_{Su} = \underbrace{(a + s_Lu)}_{l_u}G + \underbrace{(b + s_Ru)}_{r_u}H + \underbrace{(\alpha + \beta u)}_{\pi_{lr}}B

Con cierta reorganización en el lado izquierdo, podemos ver que la comprobación de igualdad verifica simultáneamente que tanto $l(x)$ como $r(x)$ fueron evaluados correctamente.

(a + s_Lu)G + (b + s_Ru)H + (\alpha + \beta u)B=\underbrace{(a + s_Lu)}_{l_u}G + \underbrace{(b + s_Ru)}_{r_u}H + \underbrace{(\alpha + \beta u)}_{\pi_{lr}}B

Como otra forma de ver la comprobación $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ , considera la siguiente visualización:

\begin{align*} A &= &aG& + &bH &+ &\alpha B\\ Su &= &s_LuG& + &s_RuH &+ &\beta u B\\ &&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\\ &&l(u)G&&r(u)H&&\pi_{lr}B \end{align*}

Multiplicación de Conocimiento Cero de Escalares

Supongamos que queremos probar que llevamos a cabo la multiplicación $ab = v$ .

Planteamiento del problema

$A$ es un compromiso de $a$ y $b$ , y $V$ es un compromiso de $v$ donde $v = ab$ . Deseamos probar que $A$ y $V$ están comprometidos según lo afirmado sin revelar $a$ , $b$ o $v$ .

Solución

Cuando los polinomios $a + s_Lx$ y $b + s_Rx$ se multiplican entre sí, la multiplicación de $ab$ ocurre “dentro” de la multiplicación polinómica.

(a + s_Lx)(b + s_Rx) = \boxed{ab} + (as_R + bs_L)x + s_Ls_rx^2

Recuerda que el probador comienza el algoritmo enviando compromisos:

\begin{align*} A &= aG + bH + \alpha B &&\text{// compromiso de }a\text{ y }b\\ S &= s_LG + s_RH + \beta B &&\text{// comprometer los términos lineales}\\ V &= abG + \tau_0 B &&\text{// comprometer el producto V} \\ T_1 &=(as_R + bS_L)G + \tau_1B &&\text{// coeficiente lineal de }t(x)\\ T_2 &= s_Ls_RG + \tau_2B &&\text{// coeficiente cuadrático de }t(x) \end{align*}

Ejercicio: Completa el código Python faltante para implementar el algoritmo descrito anteriormente.

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"

Aprende más

Este artículo es parte de una serie sobre Bulletproof ZKPs.

Multiplicación de Conocimiento Cero

Multiplicación de Conocimiento Cero de Polinomios

Pasos para probar el conocimiento de la multiplicación de polinomios

Configuración

El probador se compromete con l(x)l(x)l(x), r(x)r(x)r(x) y t(x)t(x)t(x)

El verificador genera un escalar aleatorio uuu

El probador evalúa los tres polinomios y crea tres pruebas

Paso final de verificación

Optimización: enviando menos compromisos

Configuración

Compromiso polinómico

Evaluación polinómica

Verificación final

Multiplicación de Conocimiento Cero de Escalares

Planteamiento del problema

Solución

Aprende más

Multiplicación de Conocimiento Cero

Multiplicación de Conocimiento Cero de Polinomios

Pasos para probar el conocimiento de la multiplicación de polinomios

Configuración

El probador se compromete con l(x)l(x)l(x), r(x)r(x)r(x) y t(x)t(x)t(x)

El verificador genera un escalar aleatorio uuu

El probador evalúa los tres polinomios y crea tres pruebas

Paso final de verificación

Optimización: enviando menos compromisos

Configuración

Compromiso polinómico

Evaluación polinómica

Verificación final

Multiplicación de Conocimiento Cero de Escalares

Planteamiento del problema

Solución

Aprende más

El probador se compromete con $l(x)$ , $r(x)$ y $t(x)$

El verificador genera un escalar aleatorio $u$

El probador se compromete con $l(x)$ , $r(x)$ y $t(x)$

El verificador genera un escalar aleatorio $u$