En 2015 anunciamos que la función Confidential Transactions (CT) sería una de las características principales de Elements. Esta característica reemplazaba los montos de la transacción con compromisos de Pedersen, una herramienta criptográfica que permite ocultar los montos de una transacción sin perder la capacidad de verificar que su saldo contable cuadre.
Una de las principales dificultades derivadas de CT fue que esta función incrementaba significativamente el tamaño de las transacciones y ralentizaba su verificación, porque exigía que cada salida de una transacción contuviera una prueba de rango, un tipo de protocolo de conocimiento nulo que prueba que los montos son demasiado pequeños para desbordarse. A diferencia de las firmas digitales comunes y corrientes, que pesan menos de 100 bytes y se verifican en menos de 100 microsegundos, estas pruebas de rango tenían un tamaño de varios kilobytes cada una y tardaban varios milisegundos en ser verificadas. En la práctica, en cualquier transacción que las utilizara, las pruebas de rango constituían la mayor parte de los datos.
Si bien nuestras pruebas de rango, basadas en las firmas de tipo anillo borromeo, eran las más pequeñas y rápidas de toda la bibliografía existente –para los tamaños de rango que nosotros necesitábamos y sin una configuración de confianza– aun así eran bastante grandes.
Desde 2015, hubo intentos de mejorar la eficiencia de las pruebas de rango. A principios de 2017, Adam Back encontró una manera de reducir el tamaño de las pruebas de rango en un 24%, aunque no logró mejorar el desempeño de la verificación. En esa misma época, les mencionamos el problema a nuestros amigos y colegas criptógrafos, Dan Boneh y Benedikt Bünz, de Stanford, que estaban bastante convencidos de que había margen para realizar mejoras.
A la larga, se les ocurrió algo que nos dejó atónitos.
Más pequeñas, más rápidas, más fuertes
Bulletproofs –derivada de una optimización de la eficiencia en cuanto al uso de espacio ideada por Bootle et al en 2016 para las pruebas de conocimiento nulo basadas en el logaritmo discreto– constituye una variante de la prueba de conocimiento nulo que es todavía más eficiente en este sentido. Lo importante para nuestros objetivos es que estas pruebas también cuentan con recursos nativos para valores comprometidos como los compromisos de Pedersen y las claves públicas. Eso nos permite implementar elementos como las pruebas de rango en el marco general de las pruebas de conocimiento nulo sin tener que implementar la artillería pesada que constituye la aritmética de curva elíptica en el conocimiento nulo.
Más fuertes. Para limitar el tamaño de las transacciones, nuestras pruebas de rango anteriores limitaban el tamaño de las salidas a un rango de 2^32. En consecuencia, las salidas quedaban limitadas a aproximadamente 43 BTC, aunque esta cifra se podía incrementar reduciendo la granularidad de las pruebas de 1 satoshi a 10 o 100 satoshis, o bien aumentando el valor mínimo para que no fuese cero. Dichos ajustes eran posibles pero empleaban montos explícitos, lo cual limitaba la privacidad del sistema.
Estas pruebas de rango de 32 bits tenían un tamaño aproximado de 2,5 KiB. Con la optimización de Adam, su tamaño se hubiera reducido a 2 KiB. Con Bulletproofs, se hubieran reducido a 610 bytes. Y con un tamaño tan pequeño, ¿por qué no duplicar el rango a 64 bits y eliminar la necesidad de realizar ajustes no privados? En teoría, esa decisión llevaría los escasos 610 bytes a 1220. Pero no es así. De hecho, una prueba de rango Bulletproof de 64 bits solo ocupa 674 bytes.
Más pequeñas. El motivo por el cual solo se agregaron 64 bytes al tamaño de la prueba a pesar de haber duplicado el tamaño del rango es que el aumento de tamaño es de carácter logarítmico. Para ello, se empleó una variante del argumento del producto interno extraído del trabajo de investigación de Bootle et al de 2016. (Jonathan Bootle también ayudó a Benedikt y Dan a desarrollar Bulletproofs.) En particular, el argumento del producto interno de tamaño logarítmico que se describe en el trabajo de investigación se redujo aún más en Bulletproofs, de 6log(N) puntos en la curva a 2log(N).
Este mismo truco permite la agregación de múltiples pruebas de rango en una dentro de la misma transacción y, en este caso, el incremento de tamaño también es leve. El combinado de dos pruebas de rango equivaldría a 738 bytes, el de cuatro, a 802 y el de ocho, a 866. ¡Ocho pruebas de rango clásicas de 64 bits equivaldrían a más de 40.000 bytes!
Más rápidas. Este ahorro de espacio es genial pero, en nuestro análisis inicial de la técnica, observamos que la verificación sería más lenta que en las pruebas de rango anteriores. Aparentemente, la verificación de una sola prueba de 64 bits requeriría más de 200 multiplicaciones de puntos por escalares, cada una de ellas con una onerosa duración de 50 microsegundos, mientras que para las pruebas de rango anteriores solo hacían falta 128 multiplicaciones.
Pero, después de analizar la cuestión en mayor profundidad, fuimos capaces de combinar muchas de las multiplicaciones, lo cual redujo la cantidad total a apenas 147. Lo que es más, nos dimos cuenta de que, a diferencia de lo que ocurría en las pruebas de rango anteriores, ninguna de esas multiplicaciones dependía de las demás y, por ende, podíamos hacerlas todas en un único gran lote. Gracias a nuestro trabajo sobre las firmas combinadas, ya sabíamos cómo realizar multiplicaciones por lotes muy veloces. Pieter Wuille, Greg Maxwell, Jonas Nick, Peter Dettman y yo habíamos dedicado varios meses al problema y habíamos logrado reducir la duración de las 147 multiplicaciones a tan solo 15,5 microsegundos cada una, de modo tal que el tiempo total de verificación de Bulletproof se redujo a 2,3 ms (comparado con 5,8 ms en el caso de las pruebas anteriores).
Esto equivale a más del doble de la velocidad anterior, pero, dado que nuestra multiplicación por lotes se acelera más cuanto más puntos recibe, las cifras del desempeño de los combinados son todavía más impresionantes. Un combinado de ocho Bulletproofs de 64 bits se puede verificar en apenas 10,7 ms, con lo cual su velocidad de verificación equivale a más del cuádruple de la de las pruebas anteriores, que se verificaban en 46,5 ms.
Pero hay más. Bulletproofs es compatible con una forma extremadamente eficiente de verificación por lotes. De las 147 multiplicaciones necesarias, 130 emplean los mismos puntos en todas las Bulletproof, así que, durante la validación por lotes, esas 130 multiplicaciones se pueden combinar, de modo que solo restan 17 nuevas. De hecho, ese costo marginal solo se incrementa de manera logarítmica: para los combinados de 2 rangos, cada prueba adicional conlleva 19 puntos extra, y para los combinados de 4, cada prueba conlleva 21.
Cabe señalar que hemos presentado dos conceptos similares pero autónomos: la agregación ocurre cuando un probador combina múltiples pruebas de rango en una, mientras que el procesamiento por lotes tiene lugar cuando un verificador revisa varias pruebas distintas al mismo tiempo.
Esto quiere decir que dos pruebas de rango de 64 bits pueden validarse en menos de 2,7 ms, es decir, 1,3 ms por rango. Para validar mil pruebas de rango hacen falta 239 ms, es decir, 0,24 ms por rango, un desempeño 23 veces mejor que el de las pruebas anteriores. Pero, gracias a la agregación, todavía hay más. Mil combinados de ocho rangos cada uno (8000 rangos en total) se pueden validar en 588 ms, es decir, 74 microsegundos por rango, un desempeño 78 veces mejor que el de las pruebas anteriores.
A la larga, este efecto alcanza su tope cerca de los combinados de 64 pruebas, puesto que las multiplicaciones de puntos por escalares, cada vez más eficientes, dejan de ser el efecto dominante. Llegados a este punto, podemos realizar la validación por lotes en menos de 49 microsegundos por rango, un desempeño 120 veces mejor que los anteriores. Como dato de referencia, una firma del algoritmo de firma digital de curva elíptica (ECDSA, por sus siglas en inglés) toma aproximadamente 49 microsegundos, así que, a tal nivel de agregación, la prueba de rango ni siquiera es la parte dominante de la validación de la transacción. Obviamente, es poco probable que veamos muchas transacciones de 64 salidas en la blockchain, pero sin duda es posible que ocurran en otros contextos, como Provisions.
Este tipo de verificación también es eficiente en cuanto al uso de memoria, ya que alcanzan menos de 100 KiB para validar una sola prueba de rango; dicha cifra aumenta o disminuye linealmente en función del tamaño.
Todo (lo que sea cierto) se puede comprobar
Las Bulletproofs son mucho más generales que las pruebas de rango. En el contexto del conocimiento nulo, se pueden emplear para probar enunciados arbitrarios. En términos de capacidad, son equivalentes a los argumentos de conocimiento sucintos no interactivos y los argumentos de conocimiento ampliables y transparentes (SNARK y STARK, respectivamente, por sus siglas en inglés) pero cuentan con recursos nativos para claves públicas de curva elíptica (EC) y compromisos de Pedersen (de modo que, en general, no es necesario implementar matemática EC dentro del programa que se está poniendo a prueba). Además, a diferencia de los SNARK, las Bulletproofs cuentan con seguridad completa de 128 bits según supuestos estándar y sin necesidad de una configuración de confianza. Y, a diferencia de los STARK, tienen la velocidad suficiente para poner a prueba y verificar problemas de tamaño razonable en hardware de computación típico.
Como ejemplo específico, considere una sola ejecución de la función de compresión SHA2. Para demostrar el conocimiento de una preimagen SHA2, nuestro probador requiere menos de 30 MiB de memoria y aproximadamente 13 segundos. La verificación exige aproximadamente 23 MiB de memoria y lleva 435 ms, pero podemos verificar pruebas adicionales por lotes y cada una demora 28 ms y exige 13,4 KiB de memoria. La prueba resultante es de apenas 1379 bytes.
Para los SNARK, nuestro probador es más eficiente en cuanto al uso de memoria: en el mismo sistema, una prueba SNARK para SHA2 lleva solo 4 segundos pero consume 75 MiB de memoria. Si bien requiere para cada circuito un precómputo de tamaño considerable que se efectúa una sola vez (la descripción del enunciado que se va a comprobar), una vez completo ese paso, la verificación solo lleva entre 3 y 5 ms y consume muy poca memoria. Dichas cifras no aumentan con relación al tamaño del circuito, de modo que, para casos donde la cantidad de puertas supera varios millares, los SNARK superan a todas las demás opciones, incluida nuestra validación por lotes. Por desgracia, el precio que se paga por estas mejoras consiste en la necesidad de una configuración de confianza y la aplicación de supuestos criptográficos nuevos.
Todavía hay mucho margen para seguir optimizando Bulletproofs, tanto en la instancia del probador como en la del verificador.
La capacidad de comprobar enunciados arbitrarios –ya sea mediante Bulletproofs o argumentos SNARK o STARK– tiene muchas aplicaciones. Por ejemplo, puede emplearse para implementar firmas digitales comunes y corrientes, como las firmas en anillo y las firmas con umbral –lo cual, en el caso de los anillos de gran tamaño, probablemente resulte más eficiente que los esquemas tradicionales, tanto en términos de tiempos de verificación como de tamaño de las pruebas–, pero no se limita a este uso. También puede emplearse para vender problemas de sudoku sin depender de la confianza. Puede emplearse en cómputos de participantes múltiples para probar que todas las partes actuaron honestamente, incluso con datos secretos. (En particular, durante esquemas de multifirma como MuSig, esta característica permite la generación determinista de nonces sin tener que exigir a los firmantes que se mantengan en el mismo estado ni exponerlos a los ataques por reutilización del nonce.) Puede emplearse para probar la existencia de preimágenes de hash.
Y esta última aplicación, las preimágenes de hash, es particularmente interesante porque puede aprovecharse para crear pruebas de conocimiento nulo de Merkle, pruebas de inclusión eficientes en conjuntos masivos (de millones o incluso miles de millones de elementos). Vamos a profundizar sobre este tema en una publicación futura.
Conclusión
● Las Bulletproofs son pruebas de conocimiento nulo generales (como los SNARK).
● Es posible utilizarlas para extender los protocolos de participantes múltiples, como las multifirmas o los pagos contingentes de conocimiento nulo (ZKCP, por sus siglas en inglés).
● El protocolo Bulletproofs proporciona una versión mucho más eficiente de las pruebas de rango de CT (cuando se realizaron verificaciones por lotes, fueron más de 23 veces más rápidas).
● Estas pruebas de rango pueden combinarse dentro de las transacciones y el incremento de tamaño es únicamente de carácter logarítmico.
● Si la agregación llega al grado suficiente, como en Provisions, la verificación por lotes se vuelve más de 120 veces más rápida que en las pruebas anteriores.
Queremos agradecer a Bootle et al. por desarrollar el argumento del producto interno que nos condujo a todas estas novedades, así como también a Benedikt Bünz y Dan Boneh, nuestros coautores, que se encargaron del grueso del trabajo inventivo. También queremos agradecerles a Sean Bowe y Daira Hopwood por su investigación sobre la optimización de los circuitos aritméticos.
Todos los cómputos se realizaron en un solo núcleo de una CPU Intel i7-6820HQ a 2,70 GHz.
Enlaces
● Trabajo de investigación completo
● Bulletproofs - Criptografía aplicada, Stanford
● Charla de Benedikt Bünz en la BPASE ‘18
● Charla de Andrew Poelstra en el encuentro Bitcoin en Milán (diapositivas)