Los Bulletproofs son un argumento de producto interno de conocimiento cero (zero knowledge inner product argument), que permite a un probador (prover) convencer a un verificador (verifier) de que calculó correctamente un producto interno. Es decir, el probador tiene dos vectores $\mathbf{a} = [a_1, a_2, \dots, a_n]$ y $\mathbf{b} = [b_1, b_2, \dots, b_n]$ y calculó $v = \langle\mathbf{a},\mathbf{b}\rangle=a_1b_1+a_2b_2 + \dots +a_nb_n$. El probador puede, de manera opcional, ocultar o revelar los vectores o el resultado del producto interno, y aun así convencer al verificador de que realizó el cálculo de manera honesta.

El verificador no recibe los vectores $\mathbf{a}$, $\mathbf{b}$, ni el escalar $v$, sino más bien commitments (compromisos) de estos valores. Muy a grandes rasgos, se podría pensar que el verificador recibe un “hash” $h$ donde $h = \mathsf{hash}([a_1, a_2, \dots, a_n],[b_1, b_2, \dots, b_n],v)$, para luego recibir una prueba (a la que llamamos $\pi$) de que el hash realmente contiene dos vectores y su producto interno. En otras palabras, el verificador recibe $(h, \pi)$ y queda convencido de que el probador llevó a cabo una operación de producto interno correctamente sobre los valores hasheados – pero no aprende nada sobre el “contenido” del hash.

En el transcurso de la ejecución de la parte de verificación del Bulletproof, el verificador reconstruirá el hash y, por lo tanto, quedará convencido de que el probador evaluó el producto interno tal como lo afirmó.

Por supuesto, no es posible reconstruir un hash tradicional sin conocer la entrada, por lo que los Bulletproofs utilizan un tipo especial de hash llamado “Pedersen Commitment”, que es el tema del primer capítulo de este tutorial. Los Pedersen Commitments son un tipo especial de “hash” basado en curvas elípticas; los Pedersen Commitments pueden ser reconstruidos sin conocer la entrada original.

Algunos ingenieros reconocen la operación de combinar vectores de la forma $a_1b_1+a_2b_2 + \dots +a_nb_n$ como un “producto punto” (dot product). Técnicamente, un producto punto se refiere a la operación sobre vectores en un plano cartesiano, pero el producto interno (inner product) se refiere a la operación para vectores arbitrarios. Por lo tanto, nos referiremos a esta operación como producto interno. Utilizamos letras en negrita como $\mathbf{a}$ para denotar un vector, letras en minúscula como $v$ para denotar un elemento de un campo finito (aproximadamente, un “escalar” en aritmética modular), y corchetes angulares $\langle\mathbf{a},\mathbf{b}\rangle$ para denotar un producto interno de dos vectores, el cual siempre da como resultado un elemento de un campo finito.

Para probar conocimiento cero en general, el probador debe demostrar que conoce una asignación para un circuito aritmético (un witness o testigo) que satisface las restricciones del circuito. Sin embargo, los SNARKs, particularmente Groth16, no aceptan circuitos arbitrarios – los circuitos deben estar en un formato particular, el Sistema de Restricciones de Rango Uno (R1CS). A partir de ahí, el R1CS se convierte en un Programa Aritmético Cuadrático (QAP) utilizando la interpolación de Lagrange y división polinómica.

La sobrecarga adicional de interpolar polinomios y la división polinómica aumenta significativamente el trabajo para el probador.

Los Bulletproofs, por otro lado, nos permiten crear una prueba para el R1CS directamente, sin un QAP. Consideremos que la siguiente operación matricial a la izquierda y los cálculos de producto interno a la derecha son equivalentes:

En otras palabras, multiplicar una matriz de $n \times m$ por un vector de dimensión $m$ es lo mismo que calcular $n$ productos internos. Por lo tanto, si podemos probar directamente que un producto interno se calculó de forma correcta, entonces no necesitamos los pasos adicionales de crear un Programa Aritmético Cuadrático.

Además, los Bulletproofs no utilizan emparejamientos (pairings) (solo suma básica de curvas elípticas) y no requieren una configuración confiable (trusted setup).

Desventajas de los Bulletproofs

El tamaño de la prueba es logarítmico respecto al número de multiplicaciones, a diferencia de la prueba ZK-SNARK, que es de tamaño constante.

La principal desventaja de los Bulletproofs es que el tiempo de ejecución del verificador es lineal respecto al tamaño del circuito. Esto se debe a que el trabajo que habría sido realizado por el trusted setup ahora tiene que ser hecho por el verificador.

ZK Sin Circuitos Aritméticos

Una gran ventaja de los productos internos es que pueden modelar algunos problemas “directamente” – es decir – no necesitan un circuito aritmético.

Por ejemplo, probar que un número $v$ es menor que $2^n$ puede hacerse mostrando que $v$ tiene una representación binaria de $\mathbf{b}$, y que el producto interno de $\mathbf{b}$ y el vector $[1,2,4,8,...,2^{n-1}]$ es $v$. Esto implica directamente que $v < 2^n$. Por ejemplo, si el vector de potencias de 2 es $[1,2,4,8,16,32,64,128]$, entonces sabemos que $v$ debe ser menor que 256, por la misma razón que un uint8 no puede contener valores mayores que 255. Pero dado que $\mathbf{b}$ está oculto, no conocemos el valor real de $v$. A esto se le llama una prueba de rango (range proof) porque sabemos que $v$ está en el rango $[0,255]$ sin conocer el valor real.

Si, por el contrario, fuéramos a crear un circuito aritmético para la prueba de rango, esto introduciría una sobrecarga computacional sustancial.

Para los lectores familiarizados con la completitud NP (NP-Completeness), el problema de la Suma de Subconjuntos (Subset Sum) también puede ser modelado directamente con un argumento de producto interno. Cualquier problema en NP puede ser reducido a una instancia de Subset Sum y la solución puede ser probada con un argumento de producto interno. En algunos casos, esa reducción puede ser más eficiente que un circuito aritmético.

Bulletproofs en la Práctica

La blockchain de privacidad Monero utiliza la prueba de rango descrita anteriormente para garantizar que las transacciones no tengan valores negativos en la entrada (es decir, un desbordamiento en el campo finito). ZCash utiliza Bulletproofs como reemplazo del commitment polinómico de SNARK usando un circuito PLONKish.

El tiempo de ejecución lineal de los Bulletproofs los hace inadecuados para su uso en contratos inteligentes (smart contracts) en la red principal (mainnet) de Ethereum. Sin embargo, para los protocolos que necesitan una generación y verificación rápida de pruebas para un problema pequeño – como una prueba de rango, los Bulletproofs son difíciles de superar.

El Libro ZK de RareSkills sobre Bulletproofs

Nuestro recorrido por los Bulletproofs se basa en el artículo original de Bulletproofs. El artículo está muy bien organizado, pero es extremadamente denso, ya que está dirigido a investigadores profesionales de criptografía y asume un conocimiento previo considerable. Nuestra colección de tutoriales de Bulletproof es en gran medida una traducción del artículo a una versión que los desarrolladores web3 senior puedan entender. Creamos tutoriales completos para los prerrequisitos que el artículo asume implícitamente que el lector tiene.

Como es habitual, nos esforzamos por proporcionar un modelo mental intuitivo del algoritmo, y no simplemente recitar los pasos que este da. Cuando es adecuado, incluimos animaciones matemáticas para hacer la explicación más eficiente. A toda costa, evitamos la simplificación excesiva para que tengas una intuición completa de lo que logra cada paso del algoritmo.

Lectura de esta obra

Asumimos que el lector ha leído y entendido los primeros nueve capítulos de nuestro Libro ZK. No se espera familiaridad con Groth16 u otros algoritmos ZK.

Incluimos ejercicios de programación en Python de “completar los espacios en blanco” adjuntos para que puedas practicar lo que aprendes.

Para el lector con los prerrequisitos correctos, es posible, con un mínimo de disciplina, programar el algoritmo de Bulletproofs desde cero dedicando no más de tres horas al día durante dos semanas. Este tratamiento de los Bulletproofs proporciona un marco de trabajo sobre cómo hacerlo sin llevarte excesivamente de la mano.

Los Bulletproofs son, en cierto sentido, “más simples” que los SNARKs, por lo que son una gran manera de desarrollar confianza en la comprensión del campo de ZK.

Índice de Contenidos

El capítulo 2 introduce el Pedersen Commitment, que es el bloque de construcción fundamental de los Bulletproofs. Los capítulos 3-5 muestran cómo lograr una prueba de producto interno con conocimiento cero, pero sin la propiedad de ser sucinta (el tamaño de la prueba es $\mathcal{O}(n)$ donde $n$ es el tamaño de los vectores). Los capítulos 6-7 muestran cómo probar el conocimiento de un producto interno sin ZK, pero con un tamaño de prueba logarítmico respecto a $n$. El capítulo 8 muestra el algoritmo central de los Bulletproofs. Los capítulos 9 y 10 son prerrequisitos para el capítulo 11, donde mostramos cómo construir una prueba de rango sin el uso de un circuito aritmético.

1. Introducción a Bulletproofs (este capítulo)
2. Pedersen Commitments Los Pedersen Commitments son lo que llamamos el “hash” al principio de este artículo. Sin embargo, son más componibles que las funciones hash tradicionales, ya que son aditivamente homomórficos. Es decir, podemos hacer un commit de 2 a $A$ y de 5 a $B$ y “revelar” 7 a $A + B$.
3. Commitments Polinómicos mediante Pedersen Commitments Al crear Pedersen commitments de los coeficientes de un polinomio, podemos probar que 1) hicimos un commit a un polinomio y 2) lo evaluamos correctamente sin revelar el polinomio original.
4. Multiplicación de Conocimiento Cero Podemos verificar que dos polinomios se multiplicaron correctamente al 1) hacer un commit de ellos, 2) evaluarlos, y 3) comprobar que las evaluaciones de los dos primeros se multiplican para dar el tercero. Al tener un esquema para multiplicar polinomios (con conocimiento cero), también obtenemos la multiplicación escalar gratis.
5. Argumentos de Producto Interno Ahora que tenemos el mecanismo para hacer pruebas de conocimiento cero para la multiplicación, solo se requiere un pequeño cambio para soportar pruebas de conocimiento cero para el producto interno. Específicamente, cambiamos los polinomios de coeficientes escalares por “polinomios vectoriales” y hacemos commitments vectoriales en lugar de commitments escalares para los coeficientes. También definimos una operación de “producto interno de polinomio vectorial” que nos permite llevar a cabo el argumento de producto interno. Aunque tiene conocimiento cero, este argumento aún no es sucinto.
6. Argumentos de Producto Interno Sucintos Normalmente, para probar que calculaste correctamente un producto interno con dos vectores de longitud $n$, necesitarías enviar $2n$ elementos (es decir, ambos vectores). Este capítulo muestra un truco ingenioso para enviar solamente $n$ elementos.
7. Pruebas de Conocimiento de Tamaño Logarítmico para Productos Internos Este capítulo utiliza el algoritmo descrito en el capítulo 6 recursivamente para probar que calculamos correctamente un producto interno de dos vectores de tamaño $n$ con un tamaño de prueba de solo $\mathcal{O}(n)$ datos.
8. Bulletproof ZKP: el algoritmo de principio a fin Combinamos el argumento de producto interno de conocimiento cero del capítulo 5 con el producto interno sucinto del capítulo 7 para producir el Bulletproof. En este punto, tienes conocimientos suficientes para programar el algoritmo por ti mismo combinando los ejercicios anteriores.
9. Álgebra de Producto Interno Este capítulo introduce y prueba varias identidades algebraicas para sumar productos internos entre sí, las cuales serán útiles al aprender la prueba de rango de Bulletproofs.
10. Combinaciones Lineales Aleatorias En lugar de crear dos pruebas (o más) para dos (o más) productos internos, podemos crear una prueba para múltiples productos internos utilizando el truco de la combinación lineal aleatoria.
11. Pruebas de Rango Una prueba de rango (range proof) es una prueba de que un valor sobre el que se hizo un commit se encuentra en un cierto rango. Los Bulletproofs pueden lograr esto directamente, sin la necesidad de aritmetizar el problema. Las pruebas de rango de Bulletproofs prueban que un número puede ser codificado como el producto interno de un vector de potencias de 2 $[1,2,4,...,2^{n-1}]$ y un vector binario, pero no revelan qué bits son unos o ceros.

Te recomendamos que hagas un fork de este repositorio de Bulletproofs ZK y realices los ejercicios a medida que lees, para que puedas practicar inmediatamente lo que aprendes.

Agradecimientos

La excelente documentación del crate de Rust de Bulletproofs por Henry de Valence, Cathie Yun y Oleg Andreev proporcionó indicaciones útiles donde el artículo no era claro, y a veces usamos su notación, la cual en algunos casos es más intuitiva que la notación en el artículo original. El lector puede encontrar útil ese recurso como un enfoque alternativo sobre los Bulletproofs.