Presentamos Expander: El Sistema de Pruebas GKR más Rápido hasta la Fecha

TL;DR: Nos complace anunciar la evaluación comparativa y el código abierto de nuestro sistema de prueba de conocimiento cero (ZKP), Expander, desarrollado por Polyhedra Network. Expander puede probar 4500 permutaciones de Keccak-f por segundo en una máquina Apple M3 Max. Esto convierte a Expander en el sistema de prueba de código abierto más eficiente de la industria hasta la fecha. Habiendo demostrado su eficiencia en nuestro zkBridge, Expander también revolucionará zkVM y zkML.

Keccak-256 es una función hash criptográfica estandarizada por el NIST en el algoritmo hash seguro 3 (SHA-3) y es la función hash utilizada por la cadena de bloques Ethereum. Aparece en todas partes en la tecnología ZK en la cadena Ethereum, incluyendo la prueba de la inclusión de datos en Ethereum en zkBridge, la prueba de la función hash Keccak en la firma ECDSA en zkRollup y la prueba de las instrucciones KECCAK256 en zkEVM. Sin embargo, es quizás la función hash menos compatible con ZK. Se necesitan decenas de millones de puertas para implementar Keccak como circuito, y el tiempo para generar la prueba ZK crece proporcionalmente con el tamaño del circuito. Para poner las cosas en contexto, la función hash SHA-256 estandarizada en la misma longitud de entrada requiere alrededor de 20k puertas para implementarse, y las funciones hash compatibles con ZK, como MiMC, Poseidon y Rescue, requieren solo cientos de puertas, pero estas funciones no son fácilmente accesibles en Ethereum. Por lo tanto, es un desafío probar eficientemente las funciones hash Keccak-256 para construir aplicaciones ZK con soporte nativo de Ethereum.

Nuestro sistema de prueba : Para abordar este problema, desarrollamos nuestro sistema ZKP con un enfoque en optimizar la eficiencia del probador. Nuestro sistema de prueba combina las pruebas interactivas doblemente eficientes, conocidas como el protocolo GKR [1], con el reciente esquema de compromiso polinomial basado en códigos de corrección de errores en Orion [2] y Brakedown [3]. Con los algoritmos propuestos en Libra [4], el protocolo GKR produce un tiempo de probador estrictamente lineal en el tamaño del circuito aritmético. Para obtener un esquema de argumento, el protocolo GKR se combina con un esquema de compromiso polinomial en polinomios multilineales. Implementamos las construcciones en Orion y Brakedown basadas en el código Spielman generalizado con gráficos expansores. El cálculo del probador solo consiste en un número lineal de hashes y operaciones de campo en el tamaño del polinomio. En nuestro sistema de prueba no interviene ninguna FFT, por lo que el esquema puede funcionar en cualquier campo finito, a diferencia de los SNARK basados ​​en el código Reed-Solomon y polinomios univariados, como STARK y Plonk.

Elección del cuerpo : Implementamos nuestro sistema de prueba sobre el primo de Mersenne p = 231–1. El protocolo se ejecuta sobre el tercer cuerpo de extensión F_p3. Las operaciones aritméticas sobre este cuerpo se pueden calcular de manera extremadamente eficiente.

Compilador : Como la representación del circuito del protocolo GKR es diferente de la de R1CS, la aritmetización de Plonkish y Stark, tuvimos que desarrollar nuestro propio compilador. Expander compila el cálculo en un circuito aritmético en capas con puertas personalizadas, como puertas de producto interno, que son compatibles con nuestro protocolo GKR. Con nuestro compilador, una permutación de Keccak-f se compila en un circuito con 400 mil puertas, que en realidad es más grande que el tamaño de Keccak en R1CS y AIR. Se están realizando optimizaciones adicionales, como tablas de búsqueda, para reducir aún más el tamaño del circuito.

Benchmark : Con estas optimizaciones, estamos entusiasmados de informar sobre la evaluación comparativa de nuestro sistema de prueba en Keccak. Expander puede generar la prueba de 4500 permutaciones de Keccak-f por segundo en una máquina Apple M3 Max. También evaluamos el mismo algoritmo en una máquina x86 con la CPU AMD 7950X3D y Expander puede probar 4500 funciones de Keccak por segundo en esta configuración. También queremos destacar el bajo costo de memoria de nuestro sistema de prueba. Solo requiere 16 MB por Keccak, y el uso máximo de memoria para 4000 hashes de Keccak es de solo 63 GB.

Implicación : El rendimiento de Expander abre la posibilidad de crear muchas aplicaciones ZK que sean compatibles con Ethereum. Por ejemplo, en nuestra solución zkBridge, habilitamos la interoperabilidad sin confianza entre Ethereum y otras cadenas de bloques, que deben probar el consenso de Casper FFG que involucra una gran cantidad de hashes de Keccak. Con los encabezados de bloque de Ethereum, en teoría, uno puede usar cualquier dato de Ethereum en otras redes de Capa 1 y Capa 2 al proporcionar un ZKP que demuestre que existe una ruta válida de Merkle Patricia Trie (MPT) al contrato inteligente. Esto se conoce como la prueba de inclusión de datos en nuestro zkBridge. Sin embargo, esto no es posible actualmente en la práctica para datos grandes precisamente debido a la sobrecarga de probar Keccak. Como Keccak es la función hash utilizada en Ethereum MPT, para probar la inclusión de 1 MB de datos necesitaríamos probar más de 32768 permutaciones de Keccak-f. Nuestra evaluación comparativa espera resolver este problema en un futuro cercano. Con Expander, podemos generar la prueba de inclusión de 1 MB de datos en un minuto con una sola máquina (probador), lo que se puede mejorar aún más utilizando varias máquinas.

[1] Goldwasser S, Kalai YT, Rothblum GN. Delegación de computación: pruebas interactivas para muggles. Journal of the ACM (JACM). 11 de septiembre de 2015;62(4):1–64.

[2] Xie T, Zhang Y, Song D. Orion: Prueba de conocimiento cero con tiempo de demostrador lineal. En la Conferencia Anual Internacional de Criptología de 2022, 15 de agosto (págs. 299–328).

[3] Golovnev A, Lee J, Setty S, Thaler J, Wahby RS. Análisis: SNARK lineales y agnósticos de campo para R1CS. En la Conferencia Anual Internacional de Criptología de 2023, 9 de agosto (págs. 193–226).

[4] Xie, T., Zhang, J., Zhang, Y., Papamanthou, C. y Song, D., 2019. Libra: Succinct zero-knowledge proofs with optimal prover computation. En Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, EE. UU., 18–22 de agosto de 2019, Actas, Parte III 39 (pp. 733–764).