Explica en detalle las dos nuevas herramientas SNARK lanzadas por a16z crypto

Este artículo proviene de un 16 z, el autor original: Justin Thaler, compilado por la traductora Jessica de Odaily Planet Daily.

El 10 de agosto, 16 z crypto lanzó nuevas herramientas basadas en SNARK, Lasso y Jolt, que juntas representan un nuevo enfoque para el diseño de SNARK que puede mejorar el rendimiento de las cadenas de herramientas ampliamente implementadas en un orden de magnitud o más; brindando una mejor y más conveniente experiencia del desarrollador y facilitar la auditoría.

SNARK (Argumento de conocimiento sucinto no interactivo) es un protocolo criptográfico mediante el cual cualquier persona puede demostrar a un verificador que no es de confianza que conoce un "testigo" que cumple ciertas propiedades.

• Un caso de uso destacado en Web 3 es que L2 demuestre a L1 que conocen la firma digital que autoriza una serie de transacciones, por lo que la firma en sí no tiene que ser almacenada y verificada por la red L1, lo que mejora la escalabilidad.
• Las aplicaciones fuera de la cadena de bloques incluyen: probar rápidamente la validez de todas las salidas producidas por dispositivos de hardware que no son de confianza, asegurando que los usuarios puedan confiar en ellos. Las personas pueden probar sin conocimiento que una autoridad de confianza les ha emitido credenciales que prueban que tienen la edad suficiente para acceder a contenido con restricción de edad sin revelar su fecha de nacimiento. Cualquiera que envíe datos cifrados a través de la red puede demostrar a los administradores que los datos cumplen con la política de la red sin revelar más detalles.

Si bien muchos SNARK siguen siendo un costo atractivo para el verificador, los SNARK generalmente aún introducen alrededor de seis órdenes de magnitud de sobrecarga en el cálculo del probador. El trabajo adicional que soporta el probador está altamente paralelizado, pero la sobrecarga de millones de veces limita severamente el alcance de la aplicación de SNARK.

**SNARK con más ventajas de rendimiento acelerará L 2 y también permitirá a los desarrolladores desbloquear aplicaciones aún no previstas. **Es por eso que presentamos dos nuevas tecnologías relacionadas: Lasso, un nuevo parámetro de búsqueda que puede aumentar significativamente el costo del probador; Jolt, que usa Lasso para proporcionar un nuevo marco para el llamado zkVM y un diseño frontal más amplio para diseñar SNARK. Juntos, mejoran el rendimiento, la experiencia del desarrollador y la auditabilidad de los diseños de SNARK, que a su vez mejoran las compilaciones en web 3.

Nuestra implementación inicial de Lasso ha demostrado aceleraciones de más de 10 veces en comparación con los parámetros de búsqueda en la popular cadena de herramientas SNARK halo 2. Cuando el código base de Lasso esté completamente optimizado, esperamos una aceleración de ~40x. Jolt incluye otras innovaciones además de Lasso, y esperamos que logre una aceleración similar o mejor que la zkVM existente.

Buscar parámetros, Lasso y Jolt

Un front-end de SNARK es un compilador que convierte un programa de computadora en un circuito que puede ingerir un back-end de SNARK. (Nota: un circuito es un modelo de cálculo extremadamente limitado en el que las únicas "operaciones primitivas" disponibles son la suma y la multiplicación).

Una herramienta clave en los diseños modernos de SNARK es un protocolo llamado parámetros de búsqueda, que permite que un probador no confiable envíe criptográficamente un vector grande y luego demuestre que cada entrada de ese vector está contenida en algún centro de tabla predeterminado. Los parámetros de búsqueda pueden ayudar a mantener los circuitos pequeños mediante el procesamiento eficiente de operaciones que no se calculan naturalmente mediante pequeñas sumas y multiplicaciones.

Sin embargo, como dijo Barry Whitehat de la Fundación Ethereum el año pasado, "si podemos definir circuitos de manera eficiente usando solo parámetros de búsqueda, conducirá a herramientas y circuitos más simples". El circuito que diseñamos solo realiza búsquedas. Con el tiempo, los parámetros de búsqueda "serán más eficientes que las restricciones polinómicas para casi todo".

Esta visión contrasta marcadamente con la forma en que funcionan las cosas hoy en día, donde los desarrolladores implementan SNARK escribiendo programas usando lenguajes específicos de dominio especiales que compilan los programas en restricciones polinómicas, o codificando manualmente las restricciones directamente. Esta cadena de herramientas es mucho trabajo y proporciona una gran cantidad de área de superficie para que se introduzcan errores críticos para la seguridad. Incluso con herramientas y circuitos complejos, el rendimiento de los SNARK sigue siendo lento, lo que limita su aplicabilidad.

Lasso y Jolt abordan los tres temas clave: rendimiento, experiencia del desarrollador y auditabilidad, y juntos realizan la visión de encontrar la singularidad. Lasso y Jolt también obligan a repensar gran parte de la sabiduría aceptada en el diseño de SNARK.

Después de proporcionar los antecedentes necesarios, a continuación se revisan algunas ideas comunes sobre el rendimiento de SNARK y se explica cómo se pueden optimizar a la luz de innovaciones como Lasso y Jolt.

Fondo de diseño de SNARK: ¿por qué tan lento?

La mayoría de los backends de SNARK hacen que el probador se comprometa criptográficamente con el valor de cada puerta en el circuito utilizando un esquema de compromiso polinomial. El probador prueba entonces que el valor presentado corresponde efectivamente a la ejecución correcta del verificador de testigos.

Me refiero a el trabajo probador de un esquema de compromiso polinomial como el costo de compromiso. **Los SNARK tienen costos de prueba adicionales de los esquemas de compromiso polinomial. Pero los costos de compromiso son a menudo el cuello de botella. **Lasso y Jolt también. Si se diseña un SNARK donde el costo de compromiso no es el costo principal del probador, no significa que el esquema de compromiso polinomial sea barato. Más bien, significa que otros costos son más altos de lo que deberían ser.

Intuitivamente, el propósito de los compromisos es aumentar de forma criptográficamente segura la simplicidad de los sistemas de prueba. Cuando un probador envía un gran vector de valores, es más o menos como si el probador estuviera enviando el vector completo al verificador, al igual que los sistemas de prueba normales envían el testigo completo al verificador. Los esquemas de compromiso pueden lograr esto sin obligar a los validadores a recibir realmente el testigo completo, lo que significa que el propósito del esquema de compromiso en el diseño de SNARK es controlar los costos del validador.

Pero estos métodos criptográficos son muy costosos para el probador, especialmente en comparación con los métodos teóricos de la información que utiliza SNARK fuera de los esquemas de compromiso polinomial. Los métodos teóricos de la información se basan únicamente en operaciones de campo finito. Y una operación de campo es mucho más rápida que el tiempo requerido para enviar un elemento de campo arbitrario.

Los compromisos informáticos implican exponenciaciones múltiples (también conocidas como multiplicaciones escalares múltiples o MSM) o FFT y hashes de Merkle, según el esquema de compromiso polinomial utilizado. Lasso y Jolt pueden usar cualquier esquema de compromiso polinomial, pero tienen un costo particularmente atractivo cuando se instancian usando esquemas basados en MSM, como IPA/Bulletproofs, KZG/PST, Hyrax, Dory o Zeromorph.

Por qué Lasso y Jolt son importantes

Lasso es un nuevo parámetro de búsqueda en el que el probador promete menos valores y más pequeños que el trabajo anterior. Esta podría ser una aceleración de 20x o más, donde la aceleración de 2 a 4x proviene de menos valores comprometidos y otra aceleración de 10x proviene del hecho de que todos los valores comprometidos en Lasso son pequeños. A diferencia de muchos parámetros de búsqueda anteriores, Lasso (y Jolt) también evitan las FFT, que ocupan mucho espacio y pueden ser un cuello de botella para instancias grandes.

Además, Lasso funciona incluso con tablas enormes, siempre que esas tablas estén "estructuradas" (en el sentido técnico preciso). Estas tablas son demasiado grandes para que alguien las implemente explícitamente, pero Lasso solo paga por los elementos de la tabla a los que realmente accede. En particular, en comparación con los parámetros de búsqueda anteriores, si la tabla está estructurada, ninguna de las partes necesita confirmar todos los valores de la tabla en forma cifrada.

Lasso utiliza dos conceptos estructurales diferentes: descomponibilidad y estructuras LDE. (LDE es un acrónimo de un concepto técnico llamado polinomio extendido de bajo grado). Descomponibilidad significa aproximadamente que una sola búsqueda de una tabla puede responderse realizando un número menor de búsquedas en una tabla más pequeña. Este es un requisito más estricto que la estructura LDE, pero Lasso es particularmente efectivo cuando se aplica a tablas descomponibles.

sacudida

Jolt (Just One Lookup Table) es una nueva interfaz desbloqueada por la capacidad de Lasso para usar enormes tablas de búsqueda. Jolt apunta a la abstracción de la máquina virtual/CPU, también conocida como arquitectura de conjunto de instrucciones (ISA). Los SNARK que admiten esta abstracción se denominan zkVM. Por ejemplo, considere el conjunto de instrucciones RISC-V (incluida la extensión de multiplicación) al que también apunta el proyecto RISC-Zero. Este es un popular ISA de código abierto desarrollado por la comunidad de arquitectura informática sin SNARK en mente.

Para cada instrucción fi de RISC-V, la idea principal de Jolt es crear una tabla de búsqueda que contenga la tabla de evaluación completa de fi. Básicamente, para cada instrucción RISC-V, la tabla de búsqueda resultante se puede descomponer y se aplica el lazo.

Revisando la sabiduría aceptada en el diseño de SNARK

Lasso y Jolt también subvierten parte de la sabiduría aceptada en el diseño de SNARK.

**# 1. Los SNARK de área grande son un desperdicio. Todos deberían usar FRI, Ligero, Brakedown o variantes, ya que evitan las técnicas de curva elíptica que generalmente se aplican a grandes escalas. **

El tamaño del campo aquí corresponde aproximadamente al tamaño de los números que aparecen en la prueba de SNARK. Dado que la suma y la multiplicación de números muy grandes son costosas, la idea de que los SNARK en campos grandes son un desperdicio significa que debemos esforzarnos por diseñar protocolos que nunca tengan números grandes. Los compromisos basados en MSM utilizan curvas elípticas, que normalmente se definen en campos grandes (de tamaño ~2 256), por lo que estas promesas tienen una reputación de bajo rendimiento.

Si tiene sentido usar campos pequeños (incluso si son una opción) depende en gran medida de la aplicación. Lasso y Jolt van más allá. Muestran que incluso con un esquema de compromiso basado en MSM, el trabajo del probador puede ser casi independiente del tamaño del campo. Esto se debe a que, para los compromisos basados en MSM, el tamaño de los valores comprometidos es más importante que el tamaño de los campos en los que residen esos valores.

Los SNARK existentes hacen que el probador se comprometa con muchos elementos de campo aleatorios. Por ejemplo, el probador en un backend popular de SNARK llamado Plonk compromete alrededor de 7 elementos de campo aleatorios (y otros elementos de campo no aleatorios) por puerta de circuito. Estos elementos de campo aleatorio pueden ser grandes incluso si todos los valores que aparecen en los cálculos probados son pequeños.

Por el contrario, Lasso y Jolt solo requieren que el probador envíe un valor pequeño (el probador de Lasso también envía menos valores que el parámetro de búsqueda anterior). Esto mejora enormemente el rendimiento de los esquemas basados en MSM. Como mínimo, Lasso y Jolt deben desmantelar la noción de que la comunidad debe abandonar los compromisos basados en HSH en los casos en que el desempeño del probador importa.

**#2 El conjunto de instrucciones más simple conduce a un zkVM más rápido. **

La complejidad de Jolt (por instrucción) solo depende del tamaño de entrada de la instrucción, siempre que la tabla de evaluación para cada instrucción sea descomponible. Jolt demostró que las instrucciones sorprendentemente complejas son descomponibles, especialmente todas las RISC-V.

Esto es contrario a la creencia común de que las máquinas virtuales más simples (zkVM) conducen necesariamente a circuitos más pequeños y probadores más rápidos asociados (cada paso de la VM). Esta es la motivación principal detrás de zkVM particularmente simples, como Cairo VM, que están diseñados específicamente para ser compatibles con SNARK.

De hecho, para máquinas virtuales más simples, Jolt logra un costo de compromiso más bajo para el probador que los SNARK anteriores. Por ejemplo, para la ejecución de la máquina virtual Cairo, el probador SNARK envía 51 elementos de campo en cada paso de la máquina virtual. Los SNARK implementados por Cairo actualmente funcionan en campos de 251 bits (63 bits es el límite inferior estricto en el tamaño de campo que puede usar un SNARK). El probador de Jolt funciona en ~60 elementos de campo por paso (que definen más de tipos de datos de 64 bits) para CPU RISC-V. Después de tener en cuenta el hecho de que los elementos de campo enviados son pequeños, el costo del probador Jolt es aproximadamente equivalente al costo de enviar 6 elementos de campo aleatorios de 256 bits.

**#3 No hay penalización de rendimiento por dividir cálculos grandes en partes pequeñas. **

Con base en esta vista, los proyectos actuales descomponen cualquier circuito grande en pequeños bloques, prueban cada bloque por separado y agregan recursivamente los resultados a través de SNARK. Estas implementaciones utilizan este enfoque para aliviar los cuellos de botella de rendimiento en SNARK populares. Por ejemplo, los SNARK basados en FRI requieren cerca de 100 GB de espacio de prueba, incluso para circuitos pequeños. También requieren FFT, una operación ultralineal que puede convertirse en un cuello de botella si los SNARK se aplican "simultáneamente" a circuitos grandes.

La realidad es que algunos SNARK (como Lasso y Jolt) exhiben economías de escala (en lugar de las deseconomías de escala que se encuentran en los SNARK actualmente implementados). Esto significa que cuanto mayor sea la declaración que se prueba, menor será la sobrecarga del probador en relación con la verificación directa de testigos (es decir, el trabajo requerido para evaluar un circuito de testigos sin garantizar la corrección). A nivel técnico, las economías de escala provienen de dos lugares.

Aceleración de Pippenger para MSM de tamaño n: mejora del factor log(n) sobre el algoritmo ingenuo. Cuanto mayor sea n, mayor será la mejora.

En parámetros de búsqueda como Lasso, el probador paga un costo "único" que depende del tamaño de la tabla de búsqueda pero no tiene nada que ver con la cantidad de valores buscados. El costo único del probador se amortiza en todas las consultas a la tabla. Los bloques más grandes significan más búsquedas, lo que significa una mejor amortización.

La forma popular de lidiar con circuitos grandes hoy en día es dividir las cosas en las piezas más pequeñas posibles. La principal restricción sobre el tamaño de cada parte es que no pueden ser tan pequeñas que la prueba de agregación recursiva se convierta en un cuello de botella para el probador.

Lasso y Jolt proponen un enfoque esencialmente opuesto. La gente debería usar SNARK que tengan economías de escala. Luego divida el cálculo grande en partes tan grandes como sea posible y recurra a los resultados. La principal limitación en el tamaño de cada fragmento es el espacio de prueba, que crece a medida que el fragmento se hace más grande.

**#4 Las restricciones de altura son necesarias para SNARK eficientes. **

Jolt usa R 1 CS como su representación intermedia. No hay ningún beneficio en usar restricciones de altura o personalizadas en Jolt. La mayor parte del costo del probador en Jolt radica en buscar el parámetro Lasso, en lugar de probar la satisfacibilidad del sistema de restricciones resultante que da por sentada la búsqueda.

Jolt es universal, por lo que no pierde su versatilidad. Como tal, contrarresta el intenso enfoque de los desarrolladores en las restricciones de altura del diseño (a menudo especificadas manualmente) en un esfuerzo por obtener un rendimiento mejorado de los populares SNARK de hoy.

Por supuesto, algunos contextos aún pueden beneficiarse de las restricciones personalizadas o de altura. Un ejemplo importante es Minroot VDF, cuya restricción de 5 grados puede reducir el costo de compromiso en un factor de aproximadamente 3.

**#5 Los esquemas de compromiso de polinomios dispersos son costosos y deben evitarse siempre que sea posible. **

Esta es la principal crítica contra el sistema de sujeción recientemente introducido llamado CCS y los SNARK que lo respaldan: Spartan y Marlin, CCS es una clara generalización de todos los sistemas de sujeción que prevalecen en la práctica hoy en día.

Esta crítica es infundada. De hecho, el núcleo técnico de Lasso y Jolt es el esquema de compromiso polinomial disperso en Spartan - Spark. Spark en sí mismo es una conversión genérica de cualquier esquema de compromiso polinomial (no disperso) a uno que admita polinomios dispersos.

Lasso optimiza y amplía Spark para garantizar que el probador solo se comprometa con valores "pequeños", pero incluso sin estas optimizaciones, la crítica no está justificada. De hecho, el probador de Spartan se compromete con menos elementos de campo (aleatorios) que los SNARK (como Plonk, que evita compromisos de polinomios escasos).

El enfoque de Spartan tiene ventajas de rendimiento adicionales, especialmente para circuitos con estructuras repetitivas. Para estos circuitos, las puertas de adición no se suman al trabajo criptográfico del probador espartano. Este trabajo solo crece con el número de variables en un sistema de restricciones dado, no con el número de restricciones. A diferencia de Plonk, los probadores de Spartan no necesitan enviar múltiples "copias" diferentes de la misma variable.

Somos optimistas de que Lasso y Jolt cambiarán drásticamente la forma en que se diseñan los SNARK, mejorando el rendimiento y la auditabilidad. Esta es una herramienta clave con la extraña habilidad de minimizar el costo de compromiso del probador.