Los Pedersen Commitments nos permiten codificar vectores arbitrariamente grandes con un solo punto de la curva elíptica, mientras opcionalmente ocultamos cualquier información sobre el vector.

Esto nos permite hacer afirmaciones sobre un vector sin revelar el vector en sí.

Motivación

Cuando hablamos de Bulletproof Zero Knowledge Proofs, generalmente tendrán la forma “Tengo dos vectores cuyo producto interno es $v$”. Esto podría parecer básico, pero en realidad puedes usar este mecanismo para probar afirmaciones muy no triviales. Llegaremos a eso más adelante.

Pero para que tal prueba funcione, los vectores no pueden existir simplemente en la cabeza del prover (probador): de lo contrario, el prover puede cambiarlos a voluntad. Tienen que ser entidades matemáticas en el mundo real. Generalmente, el prover no quiere simplemente pasar los dos vectores al verificador, pero aún así necesita “pasar algo” al verificador para representar que ha seleccionado un par de vectores y no puede cambiarlo.

Aquí es donde los Pedersen Commitments entran en juego.

En un argumento de producto interno (inner product argument), el prover proporciona dos compromisos (commitments) para dos vectores, y luego proporciona una prueba de que los vectores comprometidos tienen un cierto producto interno.

Requisitos previos

Asumimos que el lector ya está familiarizado con la suma de puntos en la curva elíptica y la multiplicación escalar, y lo que significa que un punto esté “en la curva”.

En cuanto a la notación, las letras mayúsculas son puntos de la curva elíptica, las letras minúsculas son elementos de campos finitos.

Decimos que $A$ es un punto de la curva elíptica (EC), $a$ es un elemento de un campo finito, y $aA$ es la multiplicación de puntos entre el elemento del campo finito $a$ y el punto de la curva elíptica $A$. La expresión $A + B$ denota la suma de puntos en la curva elíptica.

Compromisos tradicionales

Cuando diseñamos funciones commit-reveal (comprometer-revelar) en los smart contracts, generalmente son de la forma

donde el $\text{salt}$ es un valor aleatorio para evitar que un atacante adivine el $\text{value}$ mediante fuerza bruta.

Por ejemplo, si estuviéramos comprometiendo un voto, solo hay un número limitado de opciones, y por lo tanto, la selección del voto puede ser adivinada intentando todos los votos para ver qué hash coincide.

La terminología académica para la variable salt en el caso de los Pedersen Commitments es el factor de cegado (blinding factor). Debido a que es aleatorio, el atacante queda “cegado” y no puede adivinar el valor comprometido.

Debido a que el valor “commitment” no puede ser adivinado por un adversario, decimos que este esquema de compromiso es hiding (que oculta).

Durante la fase de revelación, quien compromete (el committer) revela el valor y el salt, para que la otra parte (o el smart contract) pueda validar que coincide con el commitment original. No es posible obtener otro par $(\text{value}, \text{salt})$ que pueda resultar en el mismo commitment, por lo que decimos que este esquema es binding (vinculante): el committer no puede cambiar (es decir, está vinculado a) su valor comprometido a posteriori.

Un par $(\text{value}, \text{salt})$ que da como resultado el hash se llama la apertura (opening). Decir que alguien “conoce una apertura para el compromiso” significa que conoce (value, salt). Revelar $(\text{value}, \text{salt})$ significa abrir el compromiso.

Al hablar de Pedersen Commitments, hay una distinción entre conocer la apertura y abrir el compromiso. Generalmente queremos probar que conocemos la apertura, pero no necesariamente abrirla.

Resumen de terminología

• Un compromiso hiding (que oculta) no permite a un adversario saber qué valor fue seleccionado por el committer. Esto usualmente se logra incluyendo un término aleatorio que el atacante no puede adivinar.
• Un término blinding (de cegado) es el número aleatorio que hace que el compromiso sea imposible de adivinar.
• Una apertura (opening) son los valores que al computarse darán como resultado el compromiso.
• Un compromiso binding (vinculante) no permite al committer calcular un hash con valores diferentes. Es decir, no pueden encontrar dos pares (value, salt) que resulten en el mismo valor de hash.

Pedersen Commitments

Los Pedersen Commitments se comportan de manera muy similar al esquema commit-reveal descrito anteriormente, excepto que utilizan grupos de curvas elípticas en lugar de funciones hash criptográficas.

Bajo el supuesto del logaritmo discreto, dados los puntos de la curva elíptica $V$ y $U$, no podemos calcular $x$ donde $V$ = $xU$. Es decir, no conocemos su relación de logaritmo discreto, es decir, cuántas veces $U$ necesita ser sumado a sí mismo para obtener $V$.

Aún nos referimos a $x$ como el logaritmo discreto de $U$ aunque no podamos calcularlo, porque sabemos que existe. Todos los puntos (criptográficos) de la curva elíptica tienen un logaritmo discreto, incluso si no se pueden calcular.

En este sentido, la multiplicación de puntos en la curva elíptica se comporta como una función hash. Son vinculantes siempre y cuando solo permitamos aperturas dentro del orden de la curva.

Sin embargo, si el rango de los logaritmos discretos es pequeño y está limitado por el contexto de la aplicación (como las opciones de voto), entonces el logaritmo discreto podría volverse adivinable.

Podemos hacer que un Pedersen Commitment sea hiding de la siguiente manera:

donde $v$ es el valor que estamos comprometiendo y $s$ es el salt (o factor de cegado) y $B$ es otro punto de la curva elíptica tal que el committer no conoce la relación de logaritmo discreto entre $B$ y $G$.

Debemos enfatizar que aunque los logaritmos discretos son desconocidos, los puntos $G$ y $B$ son públicos y conocidos tanto por el verificador como por el committer.

Por qué el committer no debe conocer la relación de logaritmo discreto entre $B$ y $G$

Supongamos que el committer conoce $b$ tal que $B = bG$.

En ese caso, pueden abrir el compromiso

a un $(v', s')$ diferente al valor que comprometieron originalmente.

Así es como el committer podría hacer trampa si sabe que $b$ es el logaritmo discreto de $B$.

El committer puede reescribir la ecuación del compromiso:

El committer elige un nuevo valor $v'$ y calcula $s'$:

Luego, el prover presenta $(v', s')$ como la apertura falsificada.

Esto funciona porque

Una forma de lograr esto es tener un verificador que suministre los puntos de la curva elíptica para el committer. Una forma más simple, sin embargo, es elegir los puntos de la curva elíptica de una manera aleatoria y transparente, como seleccionando pseudoaleatoriamente puntos de la curva elíptica. Dado un punto aleatorio de la curva elíptica, no conocemos su logaritmo discreto.

Por ejemplo, podríamos comenzar con el punto generador, hashear los valores $x$ e $y$, y luego usar eso como semilla para una búsqueda pseudoaleatoria pero determinista del siguiente punto.

¿Por qué son útiles los Pedersen Commitments?

Parece que los Pedersen Commitments son solo un commit-reveal normal con una función hash diferente, entonces, ¿cuál es el punto?

Este esquema tiene un par de ventajas.

Los Pedersen commitments son aditivamente homomórficos

Dado un punto $G$, podemos sumar dos compromisos entre sí $a_1G + a_2G$ = $(a_1 + a_2)G$.

Si incluimos términos de cegado aleatorios, aún podemos hacer una apertura válida sumando los términos de cegado y proporcionándoselo al verificador. Sean $C_1$ y $C_2$ compromisos. Ahora consideremos qué sucede cuando sumamos $C_1 + C_2$:

Alternativamente, el verificador puede comprobar que

Los hashes regulares (como SHA-256) no pueden sumarse de esta manera.

Dados dos Pedersen Commitments que utilizan los mismos puntos de la curva elíptica para comprometer, podemos sumar los compromisos y seguir teniendo una apertura válida para ellos.

Los Pedersen Commitments permiten a un prover hacer afirmaciones sobre las sumas de los valores comprometidos.

Podemos codificar tantos puntos como queramos en un solo punto

Nuestro ejemplo de usar $G$ y $B$ también puede ser considerado como un compromiso de vector 2D sin un término de cegado. Pero podemos agregar tantos puntos de curva elíptica como queramos $[G₁, G₂, …, Gₙ]$ y comprometer tantos escalares como queramos. (Aquí, $G_1$, $G_2$, etc. significan diferentes puntos en el mismo grupo, no generadores de diferentes grupos).

Pedersen Vector Commitments

Podemos llevar el esquema anterior un paso más allá y comprometer un conjunto de valores en lugar de un valor y un término de cegado.

Esquema de compromiso de vector

Supongamos que tenemos un conjunto de puntos aleatorios de la curva elíptica $(G₁,…,Gₙ)$ (de los cuales no conocemos el logaritmo discreto), y hacemos lo siguiente:

Esto nos permite comprometer $n$ valores en $C$ y ocultarlo con $s$.

Dado que el committer no conoce el logaritmo discreto de ningún $G_i$, no conoce el logaritmo discreto de $C$. Por lo tanto, este esquema es vinculante: solo pueden revelar $(v₁,…,vₙ)$ para producir $C$ más adelante, no pueden producir otro vector.

Los compromisos de vectores se pueden combinar

Podemos sumar dos Pedersen Vector Commitments para obtener un compromiso de dos vectores. Esto seguirá permitiendo al committer abrir únicamente los vectores originales. El detalle de implementación importante es que tenemos que usar un conjunto diferente de puntos de la curva elíptica contra los cuales comprometer.

Al sumar $C_1$ y $C_2$, funcionalmente estamos comprometiendo un vector más grande de tamaño $2n$.

Aquí, $rB$ y $sB$ son los términos de cegado. Incluso si el committer compromete el vector cero, el compromiso seguirá pareciendo un punto aleatorio.

El committer revelará más adelante los vectores originales $(v₁…vₙ)$ y $(w₁…wₙ)$ y el término de cegado $r + s$. Esto es vinculante: no pueden revelar otro par de vectores y términos de cegado.

El hecho de que estemos utilizando $(G₁,…,Gₙ)$ para un vector y $(H₁,…,Hₙ)$ no debe implicar que haya una relación especial entre los puntos $G$ y una relación especial entre los puntos $H$. Todos los puntos deben seleccionarse pseudoaleatoriamente. Esto es simplemente una conveniencia de notación para decir “este vector de puntos de la curva elíptica va con este vector de elementos del campo, y este otro vector de puntos EC va con este otro vector de elementos del campo”.

No hay un límite superior práctico para la cantidad de vectores que podemos comprometer.

Ejercicio para el lector: Si utilizáramos los mismos $G₁…Gₙ$ para ambos vectores antes de sumarlos, ¿cómo podría un committer abrir dos vectores diferentes para $C_3$? Da un ejemplo. ¿Cómo previene esto el uso de un conjunto diferente de puntos $H₁…Hₙ$?

Ejercicio para el lector: ¿Qué sucede si el committer intenta intercambiar los mismos elementos dentro del vector?

Por ejemplo, comprometen:

Pero abren con los dos primeros elementos intercambiados:

Es decir, intercambian los dos primeros elementos dejando el resto sin cambios. Supón que el vector $G₁…Gₙ$ no está permutado.

Generando puntos aleatorios de forma transparente

¿Cómo podemos generar estos puntos aleatorios de la curva elíptica? Una solución obvia es usar un trusted setup, pero esto no es necesario. El committer puede configurar los puntos de tal manera que no pueda conocer su logaritmo discreto seleccionando los puntos aleatoriamente de forma transparente.

Pueden elegir el punto generador, mezclarlo con un número aleatorio elegido públicamente, y hacer un hash de ese resultado (y tomar su módulo respecto al módulo del campo) para obtener otro valor. Si eso da como resultado un valor $x$ que se encuentra en la curva elíptica, úsalo como el siguiente generador y hashea el par $(x, y)$ nuevamente. De lo contrario, si el valor $x$ no cae en la curva, incrementa $x$ hasta que lo haga. Debido a que el committer no está generando los puntos, no conoce su logaritmo discreto.

Ejercicio: Ajusta el siguiente código para generar n puntos con logaritmos discretos desconocidos:

Copy
from py_ecc.bn128 import is_on_curve, FQ
from py_ecc.fields import field_properties
field_mod = field_properties["bn128"]["field_modulus"]
from hashlib import sha256
from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power

b = 3 # for bn128, y^2 = x^3 + 3
seed = "RareSkills"

x = int(sha256(seed.encode('ascii')).hexdigest(), 16) % field_mod 

entropy = 0

vector_basis = []
# modify the code below to generate n points
while not has_sqrtmod_prime_power((x**3 + b) % field_mod, field_mod, 1):
    # increment x, so hopefully we are on the curve
    x = (x + 1) % field_mod
    entropy = entropy + 1

# pick the upper or lower point depending on if entropy is even or odd
y = list(sqrtmod_prime_power((x**3 + b) % field_mod, field_mod, 1))[entropy & 1 == 0]
point = (FQ(x), FQ(y))
assert is_on_curve(point, b), "sanity check"
vector_basis.append(point)

# new x value
x = int(sha256(str(x).encode('ascii')).hexdigest(), 16) % field_mod 
print(vector_basis)

En ningún momento debes generar un punto eligiendo un escalar y luego multiplicándolo por el generador, ya que eso llevaría a que se conozca el logaritmo discreto. Necesitas seleccionar los valores $x$ del punto de la curva pseudoaleatoriamente a través de una función hash y averiguar si está en la curva.

Está bien comenzar con el generador (que tiene un logaritmo discreto conocido de 1) y generar los demás puntos.

Ejercicio para el lector: Supongamos que comprometemos un vector de valores con los puntos $G_1$ y $G_2$. Se conoce el logaritmo discreto para $G_1$, pero no se conoce el logaritmo discreto para $G_2$. Ignoraremos el término de cegado por ahora. ¿Puede el committer abrir a dos vectores diferentes? ¿Por qué o por qué no?

Aprende más con RareSkills
Echa un vistazo a nuestro bootcamp de ZK si buscas aprender sobre pruebas de conocimiento cero.