Un compromiso polinómico es un mecanismo mediante el cual un probador (prover) puede convencer a un verificador (verifier) de que un polinomio $p(x)$ tiene una evaluación $y = p(x)$ en el punto $x$ sin revelar nada sobre $p(x)$. La secuencia es la siguiente:

1. El probador envía al verificador un compromiso $C$, “fijando” su polinomio.
2. El verificador responde con un valor $u$ en el cual desea que se evalúe el polinomio.
3. El probador responde con $y$ y $\pi$, donde $y$ es la evaluación de $p(u)$ y $\pi$ es la prueba de que la evaluación fue correcta.
4. El verificador comprueba $C$, $u$, $y$, $\pi$ y acepta o rechaza que la evaluación del polinomio haya sido válida.

Este esquema de compromiso no requiere una configuración confiable (trusted setup). Sin embargo, la sobrecarga de comunicación es $O(n)$, ya que el probador debe enviar un compromiso por cada coeficiente de su polinomio.

Comprometerse con el Polinomio

El probador puede comprometerse con el polinomio creando un Pedersen Commitment para cada coeficiente. Para un Pedersen Commitment, el probador y el verificador deben acordar dos puntos de curva elíptica con logaritmos discretos desconocidos. Usaremos $G$ y $B$.

Por ejemplo, si tenemos un polinomio

podemos crear un Pedersen Commitment para cada coeficiente. Necesitaremos tres términos de ocultamiento (blinding terms) $\gamma_0$, $\gamma_1$, $\gamma_2$. Por conveniencia, cualquier escalar utilizado para ocultamiento usará una letra griega minúscula. Siempre usamos el punto de curva elíptica $B$ para el término de ocultamiento. Nuestros compromisos se producen de la siguiente manera:

El probador envía la tupla $(C_0, C_1, C_2)$ al verificador.

El verificador elige $u$

El verificador elige su valor para $x$ y se lo envía al probador. Llamamos a ese valor $u$.

El probador calcula la prueba

El probador evalúa el polinomio

El probador calcula el polinomio original de la siguiente manera:

El probador evalúa los términos de ocultamiento

La prueba de que la evaluación se realizó correctamente viene dada por el siguiente polinomio, que utiliza los términos de ocultamiento multiplicados por la potencia asociada de $u$. La razón de esto se explicará más adelante.

El probador envía $(y, \pi)$ al verificador. Ten en cuenta que el probador solo envía elementos de campo (escalares), no puntos de curva elíptica.

Paso de verificación

El verificador ejecuta la siguiente comprobación:

Por qué funciona el paso de verificación

Si expandimos los puntos de curva elíptica a sus valores subyacentes, vemos que la ecuación está equilibrada:

En cierto sentido, el probador está evaluando el polinomio usando los coeficientes del polinomio y su elección de $u$. Esto producirá la evaluación del polinomio original más los términos de ocultamiento del polinomio.

La prueba de la evaluación correcta es que el probador puede separar los términos de ocultamiento de la evaluación del polinomio, a pesar de que el probador no conoce los logaritmos discretos de $yG$ y $\pi B$.

Una ilustración alternativa de por qué funciona la verificación

Recordemos que $p(x) = c_0 + c_1x + c_2x^2$. Por lo tanto, los compromisos de los coeficientes se calculan de la siguiente manera:

Cuando el verificador envía $\color{red}{u}$, el probador calcula:

En el paso final, el verificador comprueba:

Si expandimos los términos verticalmente, vemos que la ecuación está equilibrada si el probador fue honesto:

Es muy importante que comprendas firmemente cómo funciona esta técnica de probar la evaluación correcta de un polinomio dados compromisos de ocultamiento para los coeficientes, porque Bulletproofs utilizan esta técnica en todas partes.

Ejercicio: Escribe los pasos de cómo un probador convencería a un verificador de que evaluó correctamente un polinomio de grado 1, sin revelar el polinomio al verificador.

Ejercicio: Completa el código en Python a continuación para implementar el algoritmo descrito en este capítulo:

Copy
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")

Por qué el probador no puede hacer trampa

Hacer trampa por parte del probador significa que no evalúan honestamente $y = p(u)$ pero aun así intentan pasar el paso de evaluación final.

Sin pérdida de generalidad, digamos que el probador envía los compromisos correctos para los coeficientes $C_0, C_1, C_2$.

Decimos sin pérdida de generalidad porque existe una discrepancia entre los coeficientes enviados en los compromisos y los coeficientes utilizados para evaluar el polinomio.

Para hacerlo, el probador envía $y'$ donde $y' \neq c_0 + c_1u + c_2u^2$.

Usando la ecuación final de la sección anterior, vemos que el probador debe satisfacer:

Los términos $G$ de la ecuación están claramente desequilibrados. La otra “palanca” que el probador puede mover es ajustar el $\pi$ que envía.

Dado que $y' \neq c_0 + c_1u + c_2u^2$, el probador malicioso debe reequilibrar la ecuación eligiendo un término $\pi'$ que compense la discrepancia en los términos $G$. El probador puede intentar despejar $\pi'$ con

Pero resolver esta ecuación requiere que el probador malicioso conozca los logaritmos discretos de $G$ y $B$.

Despejemos $\pi'$ en la ecuación anterior:

y luego reemplazamos $B$ con $b$ y $G$ con $g$, donde $b$ y $g$ son los logaritmos discretos de $B$ y $G$ respectivamente:

Pero nuevamente, esto no es posible porque calcular el logaritmo discreto de $B$ y $G$ es inviable.

Lo que aprende el verificador

El verificador aprende que los compromisos $C_0, C_1, C_2$ representan compromisos válidos para un polinomio que es de grado 2 como máximo, y que $y$ es el valor del polinomio evaluado en $u$.