Generalized Bulletproofs y divisores

En qué se apoya la prueba del camino en el árbol, sin configuración de confianza

Qué es un «circuito aritmético»

Cualquier cálculo se puede descomponer en pasos elementales del tipo «multiplicar dos números» y «sumar con coeficientes» en un cuerpo finito. Un conjunto de esos pasos es un circuito aritmético. Una prueba de conocimiento cero demuestra «conozco valores para todos los cables del circuito tales que se cumplen todas las ecuaciones» sin revelar los valores.

En Bulletproofs el circuito es sencillo y fijo: «estos 64 números son bits y suman el importe». En FCMP++ es más complejo: en cada nivel del árbol hay que comprobar que el hijo elegido está entre los hijos del nodo y que el nodo se ha calculado correctamente a partir de ellos.

Generalized Bulletproofs

Los Bulletproofs normales reciben como entrada compromisos de Pedersen separados. Los Generalized Bulletproofs (Eagen, Kamp, Parker y otros) permiten introducir en el circuito compromisos vectoriales: un solo punto fija muchos números a la vez. Es justo lo que necesita el árbol: el «hash» de un nodo es un compromiso vectorial con las coordenadas de sus hijos (ver Curve Trees). El circuito recibe el nodo como entrada y puede razonar sobre su contenido.

Las mismas propiedades que Bulletproofs:

• sin configuración de confianza;
• el tamaño de la prueba crece de forma logarítmica con el tamaño del circuito;
• la verificación es lineal en el tamaño del circuito, pero se agrupa bien: verificar muchas pruebas juntas es más barato que una a una.

El problema: multiplicación escalar dentro de un circuito

La rerandomización exige comprobar en el circuito algo como Õ = O + r_o·T. Multiplicar un punto por un escalar de 255 bits «a lo bruto» significa cientos de duplicaciones y sumas de puntos, cada una con varias multiplicaciones en el cuerpo. Son miles de restricciones por operación, y la prueba sería enorme.

Divisores: comprobar en lugar de calcular

La idea de Liam Eagen ("Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity"): para asegurarse de que los puntos P₁ … Pₙ suman cero, no hace falta sumarlos. Basta con presentar una función racional f sobre la curva cuyos ceros estén exactamente en esos puntos (su divisor) y comprobar una identidad algebraica en un punto aleatorio (un desafío del verificador).

La multiplicación r·T se escribe como una suma Σ bᵢ·(2ⁱ·T) sobre los bits de r, es decir, como una suma de puntos, y se comprueba con un solo divisor. El número de restricciones baja aproximadamente un orden de magnitud.

Dos circuitos, dos curvas

Los niveles del árbol se alternan entre Selene y Helios. La aritmética de cada nivel es natural en el cuerpo de una de las curvas, así que la prueba de pertenencia consta de dos Generalized Bulletproofs: uno sobre Selene (los niveles de Selene y la comprobación de la rerandomización de la hoja, cuyas coordenadas son elementos del cuerpo de Ed25519) y otro sobre Helios. Se conectan mediante nodos rerandomizados compartidos.

Tamaño y coste

El tamaño de la prueba depende de la profundidad del árbol y del ancho de los nodos. Con cientos de millones de salidas y nodos de decenas de hijos de ancho, la profundidad es de unos pocos niveles. A grandes rasgos, una entrada FCMP++ ocupa varios kilobytes, y su verificación es un orden de magnitud más costosa que la de CLSAG; los desarrolladores siguen optimizando ambas cosas (verificación por lotes, pruebas con varias entradas). Las cifras exactas están en los informes de benchmarks de la versión.