Las pruebas de conocimiento cero (ZKP) son cada vez más importantes para los sistemas descentralizados. ZK saltó a la luz pública por su éxito en proyectos como ZCash, pero hoy en día ZK es conocido como una solución de escalado para Ethereum.
Aprovechando ZK, Layer 2 (por ejemplo, Scroll y Polygon), también conocido como Rollups, está desarrollando zkEVM (zk Ethereum Virtual Machine). Estos zkEVM procesan un lote de transacciones y generan una pequeña prueba (en kilobytes). Esta atestación se puede utilizar para verificar a toda la red que el lote de transacciones es válido y correcto.
Sin embargo, sus usos no se detienen ahí. ZK permite una variedad de aplicaciones interesantes.
Capa 1 privada: Mina, por ejemplo, oculta los detalles de las transacciones y los datos en su cadena de bloques, lo que permite a los usuarios solo probar la validez de sus transacciones sin revelar los detalles de la transacción en sí. neptune.cash y Aleo también son proyectos muy interesantes.
Plataforma descentralizada en la nube: FedML y together.xyz permiten que los modelos de aprendizaje automático (ML) se entrenen de forma descentralizada, subcontraten los cálculos a la red y verifiquen la corrección de los cálculos mediante ZKP. Druglike está construyendo una plataforma de descubrimiento de fármacos más abierta utilizando tecnologías similares.
Almacenamiento descentralizado - Filecoin está revolucionando el almacenamiento en la nube, y ZK está en su núcleo, permitiendo a los proveedores de almacenamiento demostrar que han almacenado los datos correctos durante un período de tiempo.
JUEGO - Puede aparecer una versión más avanzada de Darkforest, que requiere pruebas en tiempo real. ZK también puede expandir el juego para reducir la probabilidad de hacer trampa. ¡Tal vez también trabaje con una plataforma en la nube descentralizada para permitir que el juego pague su propio alojamiento!
Identidad - La autenticación descentralizada ahora también es posible a través de ZK. Alrededor de esta idea, se están construyendo una serie de proyectos interesantes. Por ejemplo, notebook y zkemail (recomendado para aprender).
El impacto de ZK y los sistemas descentralizados es enorme, sin embargo, el desarrollo de la historia no es perfecto y todavía hay muchos obstáculos y desafíos en la actualidad. El proceso de inclusión de la generación de pruebas requiere muchos recursos y muchas operaciones matemáticas complejas. A medida que los desarrolladores buscan crear protocolos y sistemas más ambiciosos y complejos utilizando la tecnología ZK, tanto para la generación de pruebas como para los procesos de verificación, los desarrolladores exigen tamaños de prueba más pequeños, un rendimiento más rápido y mejores optimizaciones.
En este artículo, exploraremos el estado actual de la aceleración de hardware y cómo desempeñará un papel clave en el avance de la adopción de ZK.
Snark vs Stark
Hay dos técnicas populares de conocimiento cero hoy en día, zk-STARK y zk-SNARK (hemos ignorado Bulletproofs en este artículo).
| | | |
| --- | --- | --- |
| zk-STARK | zk-SNARK | |
| Complejidad - Prover | O(N * poly-log(N)) | O(N * log(N)) |
| Complejidad - Verificador | O(polilog(N)) | O(1) |
| Tamaño de prueba | 45KB-200KB | ~ 288 bytes |
| 抗量子 | Sí (basado en la función hash) | No |
| Configuración de confianza | No | Sí |
| Conocimiento cero | Sí | Sí |
| Interactividad | Interactivo o no interactivo | No interactivo |
| Documentación para desarrolladores | Limitado, pero en expansión Bueno |
表1:Snark VS Stark
Como se mencionó anteriormente, existen diferencias y compensaciones entre los dos. El punto más importante es que la configuración confiable de un sistema basado en zk-SNARK depende de al menos un participante honesto involucrado en el proceso de configuración confiable y de que sus claves sean destruidas al final del proceso. En términos de verificación en cadena, los zk-SNARK son mucho más baratos en términos de tarifas de gas. Además, las pruebas de zk-SNARK también son significativamente más pequeñas, lo que las hace más baratas de almacenar en la cadena.
Actualmente, los zk-SNARKs son más populares que los zk-STARKs. La razón más probable es que los zk-SNARK tienen una historia mucho más larga. Otra posible razón es que Zcash, una de las primeras cadenas de bloques de ZK, utilizó zk-SNARK, por lo que la mayoría de las herramientas de desarrollo y la documentación actuales giran en torno al ecosistema zk-SNARK.
Cómo crear una aplicación ZK
Los desarrolladores pueden necesitar dos componentes para completar el desarrollo de una aplicación ZK
Un método de cálculo de expresiones compatible con ZK (DSL o biblioteca de bajo nivel).
Un sistema de atestación que implementa dos funciones: Probar y Verificar.
DSL (lenguaje específico de dominio) y bibliotecas de bajo nivel
Cuando se trata de DSL, hay muchas opciones, como Circom, Halo2, Noir y muchas más. Circom es probablemente el más popular en este momento.
Cuando se trata de bibliotecas de bajo nivel, un ejemplo popular es Arkworks; También hay bibliotecas en desarrollo, como ICICLE, que es una biblioteca de aceleración CUDA.
Estos DSL están diseñados para generar sistemas confinados. A diferencia del programa habitual, que generalmente se evalúa en forma de x:= y *z, el mismo programa en la forma restringida se parece más a x-y * z = 0. Al representar el programa como un sistema de restricciones, encontramos que operaciones como la suma o la multiplicación pueden ser representadas por una sola restricción. Sin embargo, las operaciones más complejas, como las operaciones de bits, pueden requerir cientos de restricciones.
Como resultado, se vuelve complicado implementar algunas funciones hash como programas compatibles con ZK. En las pruebas de conocimiento cero, las funciones hash se utilizan a menudo para garantizar la integridad de los datos y/o para verificar propiedades específicas de los datos, pero debido al gran número de restricciones de las operaciones de bits, algunas funciones hash son difíciles de adaptar al entorno de las pruebas de conocimiento cero. Esta complejidad puede afectar a la eficiencia de la generación y verificación de pruebas y, por tanto, convertirse en un problema que los desarrolladores deben tener en cuenta y resolver a la hora de crear aplicaciones basadas en ZK
Como resultado, se vuelve complicado implementar algunas funciones hash para que sean compatibles con ZK.
Prueba
Un sistema de pruebas puede compararse con un software que realiza dos tareas principales: generar pruebas y verificarlas. Los sistemas de prueba suelen aceptar circuitos, pruebas y parámetros públicos/privados como entradas.
Los dos sistemas de prueba más populares son las series Groth16 y PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | |
| --- | --- | --- | --- | --- | --- |
| | Configuración de confianza | Tamaño de la prueba | Complejidad de la prueba | Complejidad del verificador | Flexibilidad |
| Groth16 | Específico del circuito | Pequeño | Baja | Baja | Baja |
| Plonk | Universal | Grande | Alta | 常数 | Alta |
表2:Groth16 vs Plonk
Como se muestra en la Tabla 2, Groth16 requiere un proceso de configuración confiable, pero Groth16 nos proporciona tiempos de prueba y verificación más rápidos, así como un tamaño de prueba constante.
Plonk proporciona una configuración genérica que realiza una fase de preprocesamiento para el circuito que está ejecutando cada vez que se genera una prueba. A pesar de admitir muchos circuitos, el tiempo de verificación de Plonk es constante.
También hay diferencias entre los dos en términos de restricciones. Groth16 crece linealmente en términos de tamaño de restricción y carece de flexibilidad, mientras que Plonk es más flexible.
En general, comprenda que el rendimiento está directamente relacionado con el número de restricciones en su aplicación ZK. Cuantas más restricciones, más operaciones debe calcular el demostrador.
embotellamiento
El sistema de demostración consta de dos operaciones matemáticas principales: multiplicación multiescalar (MSM) y transformada rápida de Fourier (FFT). Hoy exploraremos los sistemas en los que ambos existen, donde MSM puede ocupar aproximadamente el 60% del tiempo de ejecución, mientras que FFT puede ocupar aproximadamente el 30%.
MSM requiere mucho acceso a la memoria, lo que en la mayoría de los casos consume mucha memoria en la máquina, al tiempo que realiza muchas operaciones de multiplicación escalar.
Los algoritmos FFT a menudo requieren reorganizar los datos de entrada en un orden específico para realizar transformaciones. Esto puede requerir mucho movimiento de datos y puede ser un cuello de botella, especialmente para entradas de gran tamaño. El uso de la memoria caché también puede ser un problema si los patrones de acceso a la memoria no encajan en la jerarquía de la memoria caché.
** En este caso, la aceleración de hardware es la única forma de optimizar completamente el rendimiento de ZKP. **
Aceleración de hardware
Cuando se trata de aceleración de hardware, nos recuerda cómo los ASIC y las GPU dominaron la minería de Bitcoin y Ethereum.
Si bien las optimizaciones de software son igualmente importantes y valiosas, tienen sus limitaciones. La optimización del hardware, por otro lado, puede mejorar el paralelismo mediante el diseño de FPGA con múltiples unidades de procesamiento, como la reducción de la sincronización de subprocesos o la vectorización. El acceso a la memoria también se puede optimizar de manera más eficiente mediante la mejora de las jerarquías de memoria y los patrones de acceso.
Ahora, en el espacio ZKP, la tendencia principal parece haber cambiado: las GPU y las FPGA.
A corto plazo, las GPU tienen una ventaja en precio, especialmente después de que ETH cambie a proof-of-stake (POS), dejando a un gran número de mineros de GPU inactivos y en espera. Además, las GPU tienen la ventaja de ciclos de desarrollo cortos y proporcionan a los desarrolladores una gran cantidad de paralelismo "plug-and-play".
Sin embargo, las FPGA deberían ponerse al día, especialmente cuando se comparan los factores de forma y el consumo de energía. Las FPGA también proporcionan una latencia más baja para los flujos de datos de alta velocidad. Cuando se agrupan varias FPGA, proporcionan un mejor rendimiento en comparación con los clústeres de GPU.
GPU FRENTE A FPGA
GPU:
Tiempo de desarrollo: Las GPU proporcionan un tiempo de desarrollo rápido. La documentación para desarrolladores de frameworks como CUDA y OpenCL está bien desarrollada y es popular.
Consumo de energía: Las GPU consumen mucha energía. Incluso cuando los desarrolladores aprovechan el paralelismo a nivel de datos y el paralelismo a nivel de subproceso, las GPU siguen consumiendo mucha energía.
Disponibilidad: Las GPU de consumo son baratas y están disponibles en este momento.
FPGA:
Ciclo de desarrollo: Las FPGA tienen un ciclo de desarrollo más complejo y requieren ingenieros más especializados. Las FPGA permiten a los ingenieros lograr muchas optimizaciones de "bajo nivel" que las GPU no pueden.
Latencia: Las FPGA proporcionan una latencia más baja, especialmente cuando se procesan grandes flujos de datos.
Costo vs. disponibilidad: Las FPGA son más caras que las GPU y no están tan disponibles como las GPU.
ZPRIZE
Hoy en día, cuando se trata del cuello de botella de la optimización del hardware y ZKP, hay una competencia que no se puede evitar: ZPRIZE
ZPrize es una de las iniciativas más importantes en el campo de ZK en este momento. ZPrize es una competencia que alienta a los equipos a desarrollar aceleración de hardware para los cuellos de botella clave de ZKP (por ejemplo, MSM, NTT, Poseidon, etc.) en múltiples plataformas (por ejemplo, FPGA, GPU, dispositivos móviles y navegadores) en función de la latencia, el rendimiento y la eficiencia.
El resultado fue muy interesante. Por ejemplo, las mejoras en la GPU son enormes:
MSM a 2^26 ha aumentado en un 131% de 5.86 segundos a 2.52 segundos. Por otro lado, las soluciones FPGA tienden a no tener puntos de referencia en comparación con los resultados de GPU, que tienen puntos de referencia anteriores para comparar, y la mayoría de las soluciones FPGA son de código abierto por primera vez y se espera que dichos algoritmos mejoren en el futuro.
Estos resultados indican la dirección en la que la mayoría de los desarrolladores se sienten cómodos en el desarrollo de sus soluciones de aceleración de hardware. Muchos equipos compiten por la categoría GPU, pero solo un pequeño porcentaje compite por la categoría FPGA. No estoy seguro de si se debe a la falta de experiencia a la hora de desarrollar para FPGA, o si la mayoría de las empresas/equipos de FPGA optan por desarrollar en secreto para vender sus soluciones comercialmente.
ZPrize ha proporcionado algunas investigaciones muy interesantes a la comunidad. A medida que comiencen más rondas de ZPrize, veremos aparecer más y más soluciones y problemas interesantes.
Ejemplos prácticos de aceleración de hardware
Tomando Groth16 como ejemplo, si examinamos la implementación de rapidsnark para Groth16, podemos observar que se realizan dos operaciones principales: FFT (Transformada Rápida de Fourier) y MSM (Multiplicación Multiescalar); Estas dos operaciones básicas son comunes en muchos sistemas de prueba. Su tiempo de ejecución está directamente relacionado con el número de restricciones en el circuito. Naturalmente, el número de restricciones aumenta a medida que se escriben circuitos más complejos.
Para tener una idea de lo intensivas que son las operaciones FFT y MSM desde el punto de vista computacional, podemos consultar el punto de referencia de Ingonyama del circuito Groth16 (el proceso Vanilla C2 de Filecoin realizado en un sector de 32 GB), y los resultados son los siguientes
Como se muestra en la figura anterior, MSM (multiplicación multiescalar) puede llevar mucho tiempo y ser un grave cuello de botella de rendimiento para muchos probadores, lo que convierte a MSM en uno de los operadores criptográficos más importantes que deben acelerarse.
Entonces, ¿cuánta computación ocupa MSM para el probador en otros sistemas de prueba de ZK? Esto se muestra en la siguiente figura
En Plonk, el MSM representa más del 85% de los gastos generales, como se muestra en el último artículo de Ingonyama, Pipe MSM. **
Entonces, ¿cómo debería acelerar MSM la aceleración de hardware? **
MSM
Antes de hablar de cómo acelerar el MSM, tenemos que entender qué es el MSM
La multiplicación multiescalar (MSM) es un algoritmo para calcular la suma de múltiples multiplicaciones escalares de la siguiente forma
donde G es un punto en el grupo de curvas elípticas, a es un escalar, y el resultado de MSM también será un punto de curva elíptica
Podemos descomponer el MSM en dos subcomponentes principales:
Multiplicación modular
Adiciones de puntos de curva elíptica
Tomemos Affine(x,y) como ejemplo para realizar una operación ingenua P+Q.
Cuando queremos calcular P + Q = R, necesitamos calcular un valor k, por la abscisa de k y P,Q
Obtén las coordenadas de R. El proceso de cálculo es el anterior, en este proceso realizamos 2 veces multiplicación, 1 operación al cuadrado, 1 operación inversa, y varias veces operaciones de suma y resta. Vale la pena señalar que las operaciones anteriores se realizan en un campo finito, es decir, bajo mod P. En realidad, P será muy grande. **
El costo de la operación anterior es encontrar el inverso >> multiplicación** **> **** al cuadrado, y el costo de sumar y restar es insignificante.
Por lo tanto, queremos evitar los inversos tanto como sea posible, porque el costo de una sola inversión es al menos cien veces mayor que la multiplicación. Podemos hacer esto expandiendo el sistema de coordenadas, pero a costa de aumentar el número de multiplicaciones en el proceso, como las coordenadas jacobianas: XYZ += XYZ, y multiplicando más de 10 veces, dependiendo del algoritmo de suma. **
GPU vs FPGA MSM acelerado
En esta sección se comparan dos implementaciones principales de MSM, PipeMSM y Sppark, donde PipeMSM se implementa en FPGA y Sppark se implementa en GPU.
Sppark y PipeMSM utilizan el algoritmo Pippenger de última generación para implementar MSM, también conocido como algoritmo de cubo; **
Sppark se implementa mediante CUDA; Sus versiones son altamente paraleleles y han logrado resultados impresionantes cuando se ejecutan en las últimas GPU.
Sin embargo, PipeMSM no solo optimiza el algoritmo, sino que también proporciona optimizaciones para las primitivas matemáticas de Multiplicación Modular y Suma EC. PipeMSM maneja toda la "pila de MSM", implementando una serie de trucos matemáticos y optimizaciones destinadas a hacer que MSM sea más adecuado para el hardware, y diseñando un diseño de hardware diseñado para reducir la latencia con un enfoque en la paralelización.
Hagamos un resumen rápido de la implementación de PipeMSM.
Baja latencia
PipeMSM está diseñado para proporcionar una baja latencia cuando se ejecutan varios MSM en un gran número de entradas. Las GPU no ofrecen una baja latencia determinista debido al escalado dinámico de frecuencia, y las GPU ajustan sus velocidades de reloj en función de las cargas de trabajo.
Pero gracias al diseño de hardware optimizado, las implementaciones de FPGA pueden proporcionar un rendimiento y una latencia deterministas para cargas de trabajo específicas.
Implementación de la adición de EC
La suma de puntos de curva elíptica (adición EC) se implementa como una fórmula de baja latencia, altamente paralela y completa (completa significa que calcula correctamente la suma de dos puntos cualesquiera en el grupo de curvas elípticas). La adición de puntos de curva elíptica se utiliza de forma canalizada en el módulo de adición EC para reducir la latencia.
Elegimos representar las coordenadas como coordenadas proyectivas, y en el algoritmo de suma usamos una fórmula de suma de puntos de curva elíptica completa. La principal ventaja es que no tenemos que lidiar con casos extremos. Fórmulas completas;
Implementamos esta fórmula de suma de manera canalizada y paralela, y nuestro circuito sumador de curva elíptica FPGA solo necesitó 12 multiplicaciones, 17 sumas de sumas, y se ejecutó esta fórmula. La fórmula original requiere 15 módulos de multiplicación y 13 sumas. El diseño de la FPGA es el siguiente
Multi mod
Se utilizaron los algoritmos de Reducción de Barrett y Karatsuba.
La reducción de Barrett es un algoritmo que calcula eficientemente r≡ab mod p (donde p es fijo). La Reducción de Barrett intenta reemplazar la división (una operación costosa) por la división aproximada. Se puede seleccionar una tolerancia de error para describir el rango dentro del cual estamos buscando el resultado correcto. Encontramos que la gran tolerancia al error permite el uso de constantes de reducción más pequeñas; Esto reduce el tamaño de los valores intermedios utilizados en las operaciones de reducción de módulos, lo que reduce el número de multiplicaciones necesarias para calcular el resultado final.
En el cuadro azul de abajo, podemos ver que, debido a nuestra alta tolerancia a errores, tenemos que realizar múltiples comprobaciones para encontrar un resultado preciso.
En pocas palabras, el algoritmo de Karatsuba se utiliza para optimizar la multiplicación que realizamos en la Reducción de Barrett. El algoritmo de Karatsuba simplifica la multiplicación de dos n-dígitos a la multiplicación de tres n/2-dígitos; Estas multiplicaciones pueden simplificar el número de dígitos para que sean lo suficientemente estrechos como para ser calculados directamente por hardware. Los detalles se pueden leer en el artículo de Ingo: Pipe MSM
Utilizando los operadores anteriores, hemos desarrollado una implementación de MSM de baja latencia y altamente paralela.
La idea central es que, en lugar de calcular todo el MSM a la vez, cada fragmento se pasa al sumador EC en paralelo. Los resultados del sumador de EC se acumulan en el MSM final.
Resultado final****
El diagrama anterior muestra la comparación entre Sppark y PipeMSM.
Lo más destacado es el importante ahorro de energía que ofrecen las FPGA, que podrían ser extremadamente importantes para futuras operaciones de generación a prueba a gran escala. Vale la pena señalar que nuestra implementación fue prototipada y evaluada bajo @125MHz, y aumentar la velocidad del reloj a @500MHz podría aumentar el tiempo de cálculo en 4 veces o más.
Otra ventaja de usar nuestras FPGAs es que se pueden instalar en servidores de chasis pequeños porque consumen menos energía y generan menos calor.
Estamos en las primeras etapas de la ingeniería de FPGA para ZKP y deberíamos esperar más mejoras en los algoritmos. Además, la FPGA está calculando el MSM mientras la CPU está inactiva, y puede ser posible lograr tiempos más rápidos utilizando la FPGA en combinación con los recursos del sistema (CPU/GPU).
Resumen
ZKP se ha convertido en una tecnología clave para los sistemas distribuidos.
La aplicación de ZKP irá mucho más allá de la simple ampliación del nivel de Ethereum, permitiendo la externalización de la computación a terceros no confiables, permitiendo el desarrollo de sistemas antes imposibles, como la computación en la nube distribuida, los sistemas de identidad y más.
Tradicionalmente, las optimizaciones de ZKP se han centrado en mejoras a nivel de software, pero a medida que aumente la demanda de un rendimiento más superior, veremos soluciones de aceleración más avanzadas que involucren tanto hardware como software.
En la actualidad, las soluciones de aceleración que vemos utilizan principalmente GPU, porque el tiempo de desarrollo con CUDA es corto, y las GPU de consumo actuales son muy baratas y abundantes. La GPU también ofrece un rendimiento increíble. Por lo tanto, es poco probable que las GPU desaparezcan de este espacio en el corto plazo.
A medida que los equipos de desarrollo más complejos entren en el espacio, es probable que veamos FPGA liderando el camino en términos de eficiencia energética y rendimiento. En comparación con las GPU, las FPGA ofrecen más personalización de bajo nivel, así como más opciones de configuración. Las FPGA ofrecen una velocidad de desarrollo y flexibilidad más rápidas que los ASIC. Con el rápido desarrollo del mundo ZKP, las FPGA se pueden reflashear con diferentes programas para adaptarse a diferentes sistemas y soluciones de actualización.
Sin embargo, para generar pruebas casi en tiempo real, puede ser necesario combinar configuraciones de GPU/FPGA/ASIC dependiendo del sistema para el que generemos pruebas.
También es probable que ZPU evolucione para proporcionar soluciones extremadamente eficientes para generadores a prueba de gran escala y dispositivos de baja potencia (consulte el artículo anterior para obtener más detalles).
Ver originales
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
Una nueva era de ZK impulsada por la aceleración de hardware
Historia hasta ahora
Las pruebas de conocimiento cero (ZKP) son cada vez más importantes para los sistemas descentralizados. ZK saltó a la luz pública por su éxito en proyectos como ZCash, pero hoy en día ZK es conocido como una solución de escalado para Ethereum.
Aprovechando ZK, Layer 2 (por ejemplo, Scroll y Polygon), también conocido como Rollups, está desarrollando zkEVM (zk Ethereum Virtual Machine). Estos zkEVM procesan un lote de transacciones y generan una pequeña prueba (en kilobytes). Esta atestación se puede utilizar para verificar a toda la red que el lote de transacciones es válido y correcto.
Sin embargo, sus usos no se detienen ahí. ZK permite una variedad de aplicaciones interesantes.
Capa 1 privada: Mina, por ejemplo, oculta los detalles de las transacciones y los datos en su cadena de bloques, lo que permite a los usuarios solo probar la validez de sus transacciones sin revelar los detalles de la transacción en sí. neptune.cash y Aleo también son proyectos muy interesantes.
Plataforma descentralizada en la nube: FedML y together.xyz permiten que los modelos de aprendizaje automático (ML) se entrenen de forma descentralizada, subcontraten los cálculos a la red y verifiquen la corrección de los cálculos mediante ZKP. Druglike está construyendo una plataforma de descubrimiento de fármacos más abierta utilizando tecnologías similares.
Almacenamiento descentralizado - Filecoin está revolucionando el almacenamiento en la nube, y ZK está en su núcleo, permitiendo a los proveedores de almacenamiento demostrar que han almacenado los datos correctos durante un período de tiempo.
JUEGO - Puede aparecer una versión más avanzada de Darkforest, que requiere pruebas en tiempo real. ZK también puede expandir el juego para reducir la probabilidad de hacer trampa. ¡Tal vez también trabaje con una plataforma en la nube descentralizada para permitir que el juego pague su propio alojamiento!
Identidad - La autenticación descentralizada ahora también es posible a través de ZK. Alrededor de esta idea, se están construyendo una serie de proyectos interesantes. Por ejemplo, notebook y zkemail (recomendado para aprender).
El impacto de ZK y los sistemas descentralizados es enorme, sin embargo, el desarrollo de la historia no es perfecto y todavía hay muchos obstáculos y desafíos en la actualidad. El proceso de inclusión de la generación de pruebas requiere muchos recursos y muchas operaciones matemáticas complejas. A medida que los desarrolladores buscan crear protocolos y sistemas más ambiciosos y complejos utilizando la tecnología ZK, tanto para la generación de pruebas como para los procesos de verificación, los desarrolladores exigen tamaños de prueba más pequeños, un rendimiento más rápido y mejores optimizaciones.
En este artículo, exploraremos el estado actual de la aceleración de hardware y cómo desempeñará un papel clave en el avance de la adopción de ZK.
Snark vs Stark
Hay dos técnicas populares de conocimiento cero hoy en día, zk-STARK y zk-SNARK (hemos ignorado Bulletproofs en este artículo).
| | | | | --- | --- | --- | | zk-STARK | zk-SNARK | | | Complejidad - Prover | O(N * poly-log(N)) | O(N * log(N)) | | Complejidad - Verificador | O(polilog(N)) | O(1) | | Tamaño de prueba | 45KB-200KB | ~ 288 bytes | | 抗量子 | Sí (basado en la función hash) | No | | Configuración de confianza | No | Sí | | Conocimiento cero | Sí | Sí | | Interactividad | Interactivo o no interactivo | No interactivo | | Documentación para desarrolladores | Limitado, pero en expansión Bueno |
表1:Snark VS Stark
Como se mencionó anteriormente, existen diferencias y compensaciones entre los dos. El punto más importante es que la configuración confiable de un sistema basado en zk-SNARK depende de al menos un participante honesto involucrado en el proceso de configuración confiable y de que sus claves sean destruidas al final del proceso. En términos de verificación en cadena, los zk-SNARK son mucho más baratos en términos de tarifas de gas. Además, las pruebas de zk-SNARK también son significativamente más pequeñas, lo que las hace más baratas de almacenar en la cadena.
Actualmente, los zk-SNARKs son más populares que los zk-STARKs. La razón más probable es que los zk-SNARK tienen una historia mucho más larga. Otra posible razón es que Zcash, una de las primeras cadenas de bloques de ZK, utilizó zk-SNARK, por lo que la mayoría de las herramientas de desarrollo y la documentación actuales giran en torno al ecosistema zk-SNARK.
Cómo crear una aplicación ZK
Los desarrolladores pueden necesitar dos componentes para completar el desarrollo de una aplicación ZK
Un método de cálculo de expresiones compatible con ZK (DSL o biblioteca de bajo nivel).
Un sistema de atestación que implementa dos funciones: Probar y Verificar.
DSL (lenguaje específico de dominio) y bibliotecas de bajo nivel
Cuando se trata de DSL, hay muchas opciones, como Circom, Halo2, Noir y muchas más. Circom es probablemente el más popular en este momento.
Cuando se trata de bibliotecas de bajo nivel, un ejemplo popular es Arkworks; También hay bibliotecas en desarrollo, como ICICLE, que es una biblioteca de aceleración CUDA.
Estos DSL están diseñados para generar sistemas confinados. A diferencia del programa habitual, que generalmente se evalúa en forma de x:= y *z, el mismo programa en la forma restringida se parece más a x-y * z = 0. Al representar el programa como un sistema de restricciones, encontramos que operaciones como la suma o la multiplicación pueden ser representadas por una sola restricción. Sin embargo, las operaciones más complejas, como las operaciones de bits, pueden requerir cientos de restricciones.
Como resultado, se vuelve complicado implementar algunas funciones hash como programas compatibles con ZK. En las pruebas de conocimiento cero, las funciones hash se utilizan a menudo para garantizar la integridad de los datos y/o para verificar propiedades específicas de los datos, pero debido al gran número de restricciones de las operaciones de bits, algunas funciones hash son difíciles de adaptar al entorno de las pruebas de conocimiento cero. Esta complejidad puede afectar a la eficiencia de la generación y verificación de pruebas y, por tanto, convertirse en un problema que los desarrolladores deben tener en cuenta y resolver a la hora de crear aplicaciones basadas en ZK
Como resultado, se vuelve complicado implementar algunas funciones hash para que sean compatibles con ZK.
Prueba
Un sistema de pruebas puede compararse con un software que realiza dos tareas principales: generar pruebas y verificarlas. Los sistemas de prueba suelen aceptar circuitos, pruebas y parámetros públicos/privados como entradas.
Los dos sistemas de prueba más populares son las series Groth16 y PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | | | --- | --- | --- | --- | --- | --- | | | Configuración de confianza | Tamaño de la prueba | Complejidad de la prueba | Complejidad del verificador | Flexibilidad | | Groth16 | Específico del circuito | Pequeño | Baja | Baja | Baja | | Plonk | Universal | Grande | Alta | 常数 | Alta |
表2:Groth16 vs Plonk
Como se muestra en la Tabla 2, Groth16 requiere un proceso de configuración confiable, pero Groth16 nos proporciona tiempos de prueba y verificación más rápidos, así como un tamaño de prueba constante.
Plonk proporciona una configuración genérica que realiza una fase de preprocesamiento para el circuito que está ejecutando cada vez que se genera una prueba. A pesar de admitir muchos circuitos, el tiempo de verificación de Plonk es constante.
También hay diferencias entre los dos en términos de restricciones. Groth16 crece linealmente en términos de tamaño de restricción y carece de flexibilidad, mientras que Plonk es más flexible.
En general, comprenda que el rendimiento está directamente relacionado con el número de restricciones en su aplicación ZK. Cuantas más restricciones, más operaciones debe calcular el demostrador.
embotellamiento
El sistema de demostración consta de dos operaciones matemáticas principales: multiplicación multiescalar (MSM) y transformada rápida de Fourier (FFT). Hoy exploraremos los sistemas en los que ambos existen, donde MSM puede ocupar aproximadamente el 60% del tiempo de ejecución, mientras que FFT puede ocupar aproximadamente el 30%.
MSM requiere mucho acceso a la memoria, lo que en la mayoría de los casos consume mucha memoria en la máquina, al tiempo que realiza muchas operaciones de multiplicación escalar.
Los algoritmos FFT a menudo requieren reorganizar los datos de entrada en un orden específico para realizar transformaciones. Esto puede requerir mucho movimiento de datos y puede ser un cuello de botella, especialmente para entradas de gran tamaño. El uso de la memoria caché también puede ser un problema si los patrones de acceso a la memoria no encajan en la jerarquía de la memoria caché.
** En este caso, la aceleración de hardware es la única forma de optimizar completamente el rendimiento de ZKP. **
Aceleración de hardware
Cuando se trata de aceleración de hardware, nos recuerda cómo los ASIC y las GPU dominaron la minería de Bitcoin y Ethereum.
Si bien las optimizaciones de software son igualmente importantes y valiosas, tienen sus limitaciones. La optimización del hardware, por otro lado, puede mejorar el paralelismo mediante el diseño de FPGA con múltiples unidades de procesamiento, como la reducción de la sincronización de subprocesos o la vectorización. El acceso a la memoria también se puede optimizar de manera más eficiente mediante la mejora de las jerarquías de memoria y los patrones de acceso.
Ahora, en el espacio ZKP, la tendencia principal parece haber cambiado: las GPU y las FPGA.
A corto plazo, las GPU tienen una ventaja en precio, especialmente después de que ETH cambie a proof-of-stake (POS), dejando a un gran número de mineros de GPU inactivos y en espera. Además, las GPU tienen la ventaja de ciclos de desarrollo cortos y proporcionan a los desarrolladores una gran cantidad de paralelismo "plug-and-play".
Sin embargo, las FPGA deberían ponerse al día, especialmente cuando se comparan los factores de forma y el consumo de energía. Las FPGA también proporcionan una latencia más baja para los flujos de datos de alta velocidad. Cuando se agrupan varias FPGA, proporcionan un mejor rendimiento en comparación con los clústeres de GPU.
GPU FRENTE A FPGA
GPU:
Tiempo de desarrollo: Las GPU proporcionan un tiempo de desarrollo rápido. La documentación para desarrolladores de frameworks como CUDA y OpenCL está bien desarrollada y es popular.
Consumo de energía: Las GPU consumen mucha energía. Incluso cuando los desarrolladores aprovechan el paralelismo a nivel de datos y el paralelismo a nivel de subproceso, las GPU siguen consumiendo mucha energía.
Disponibilidad: Las GPU de consumo son baratas y están disponibles en este momento.
FPGA:
Ciclo de desarrollo: Las FPGA tienen un ciclo de desarrollo más complejo y requieren ingenieros más especializados. Las FPGA permiten a los ingenieros lograr muchas optimizaciones de "bajo nivel" que las GPU no pueden.
Latencia: Las FPGA proporcionan una latencia más baja, especialmente cuando se procesan grandes flujos de datos.
Costo vs. disponibilidad: Las FPGA son más caras que las GPU y no están tan disponibles como las GPU.
ZPRIZE
Hoy en día, cuando se trata del cuello de botella de la optimización del hardware y ZKP, hay una competencia que no se puede evitar: ZPRIZE
ZPrize es una de las iniciativas más importantes en el campo de ZK en este momento. ZPrize es una competencia que alienta a los equipos a desarrollar aceleración de hardware para los cuellos de botella clave de ZKP (por ejemplo, MSM, NTT, Poseidon, etc.) en múltiples plataformas (por ejemplo, FPGA, GPU, dispositivos móviles y navegadores) en función de la latencia, el rendimiento y la eficiencia.
El resultado fue muy interesante. Por ejemplo, las mejoras en la GPU son enormes:
MSM a 2^26 ha aumentado en un 131% de 5.86 segundos a 2.52 segundos. Por otro lado, las soluciones FPGA tienden a no tener puntos de referencia en comparación con los resultados de GPU, que tienen puntos de referencia anteriores para comparar, y la mayoría de las soluciones FPGA son de código abierto por primera vez y se espera que dichos algoritmos mejoren en el futuro.
Estos resultados indican la dirección en la que la mayoría de los desarrolladores se sienten cómodos en el desarrollo de sus soluciones de aceleración de hardware. Muchos equipos compiten por la categoría GPU, pero solo un pequeño porcentaje compite por la categoría FPGA. No estoy seguro de si se debe a la falta de experiencia a la hora de desarrollar para FPGA, o si la mayoría de las empresas/equipos de FPGA optan por desarrollar en secreto para vender sus soluciones comercialmente.
ZPrize ha proporcionado algunas investigaciones muy interesantes a la comunidad. A medida que comiencen más rondas de ZPrize, veremos aparecer más y más soluciones y problemas interesantes.
Ejemplos prácticos de aceleración de hardware
Tomando Groth16 como ejemplo, si examinamos la implementación de rapidsnark para Groth16, podemos observar que se realizan dos operaciones principales: FFT (Transformada Rápida de Fourier) y MSM (Multiplicación Multiescalar); Estas dos operaciones básicas son comunes en muchos sistemas de prueba. Su tiempo de ejecución está directamente relacionado con el número de restricciones en el circuito. Naturalmente, el número de restricciones aumenta a medida que se escriben circuitos más complejos.
Para tener una idea de lo intensivas que son las operaciones FFT y MSM desde el punto de vista computacional, podemos consultar el punto de referencia de Ingonyama del circuito Groth16 (el proceso Vanilla C2 de Filecoin realizado en un sector de 32 GB), y los resultados son los siguientes
Como se muestra en la figura anterior, MSM (multiplicación multiescalar) puede llevar mucho tiempo y ser un grave cuello de botella de rendimiento para muchos probadores, lo que convierte a MSM en uno de los operadores criptográficos más importantes que deben acelerarse.
Entonces, ¿cuánta computación ocupa MSM para el probador en otros sistemas de prueba de ZK? Esto se muestra en la siguiente figura
En Plonk, el MSM representa más del 85% de los gastos generales, como se muestra en el último artículo de Ingonyama, Pipe MSM. **
Entonces, ¿cómo debería acelerar MSM la aceleración de hardware? **
MSM
Antes de hablar de cómo acelerar el MSM, tenemos que entender qué es el MSM
La multiplicación multiescalar (MSM) es un algoritmo para calcular la suma de múltiples multiplicaciones escalares de la siguiente forma
donde G es un punto en el grupo de curvas elípticas, a es un escalar, y el resultado de MSM también será un punto de curva elíptica
Podemos descomponer el MSM en dos subcomponentes principales:
Multiplicación modular
Adiciones de puntos de curva elíptica
Tomemos Affine(x,y) como ejemplo para realizar una operación ingenua P+Q.
Cuando queremos calcular P + Q = R, necesitamos calcular un valor k, por la abscisa de k y P,Q
Obtén las coordenadas de R. El proceso de cálculo es el anterior, en este proceso realizamos 2 veces multiplicación, 1 operación al cuadrado, 1 operación inversa, y varias veces operaciones de suma y resta. Vale la pena señalar que las operaciones anteriores se realizan en un campo finito, es decir, bajo mod P. En realidad, P será muy grande. **
El costo de la operación anterior es encontrar el inverso >> multiplicación** **> **** al cuadrado, y el costo de sumar y restar es insignificante.
Por lo tanto, queremos evitar los inversos tanto como sea posible, porque el costo de una sola inversión es al menos cien veces mayor que la multiplicación. Podemos hacer esto expandiendo el sistema de coordenadas, pero a costa de aumentar el número de multiplicaciones en el proceso, como las coordenadas jacobianas: XYZ += XYZ, y multiplicando más de 10 veces, dependiendo del algoritmo de suma. **
GPU vs FPGA MSM acelerado
En esta sección se comparan dos implementaciones principales de MSM, PipeMSM y Sppark, donde PipeMSM se implementa en FPGA y Sppark se implementa en GPU.
Sppark y PipeMSM utilizan el algoritmo Pippenger de última generación para implementar MSM, también conocido como algoritmo de cubo; **
Sppark se implementa mediante CUDA; Sus versiones son altamente paraleleles y han logrado resultados impresionantes cuando se ejecutan en las últimas GPU.
Sin embargo, PipeMSM no solo optimiza el algoritmo, sino que también proporciona optimizaciones para las primitivas matemáticas de Multiplicación Modular y Suma EC. PipeMSM maneja toda la "pila de MSM", implementando una serie de trucos matemáticos y optimizaciones destinadas a hacer que MSM sea más adecuado para el hardware, y diseñando un diseño de hardware diseñado para reducir la latencia con un enfoque en la paralelización.
Hagamos un resumen rápido de la implementación de PipeMSM.
Baja latencia
PipeMSM está diseñado para proporcionar una baja latencia cuando se ejecutan varios MSM en un gran número de entradas. Las GPU no ofrecen una baja latencia determinista debido al escalado dinámico de frecuencia, y las GPU ajustan sus velocidades de reloj en función de las cargas de trabajo.
Pero gracias al diseño de hardware optimizado, las implementaciones de FPGA pueden proporcionar un rendimiento y una latencia deterministas para cargas de trabajo específicas.
Implementación de la adición de EC
La suma de puntos de curva elíptica (adición EC) se implementa como una fórmula de baja latencia, altamente paralela y completa (completa significa que calcula correctamente la suma de dos puntos cualesquiera en el grupo de curvas elípticas). La adición de puntos de curva elíptica se utiliza de forma canalizada en el módulo de adición EC para reducir la latencia.
Elegimos representar las coordenadas como coordenadas proyectivas, y en el algoritmo de suma usamos una fórmula de suma de puntos de curva elíptica completa. La principal ventaja es que no tenemos que lidiar con casos extremos. Fórmulas completas;
Implementamos esta fórmula de suma de manera canalizada y paralela, y nuestro circuito sumador de curva elíptica FPGA solo necesitó 12 multiplicaciones, 17 sumas de sumas, y se ejecutó esta fórmula. La fórmula original requiere 15 módulos de multiplicación y 13 sumas. El diseño de la FPGA es el siguiente
Multi mod
Se utilizaron los algoritmos de Reducción de Barrett y Karatsuba.
La reducción de Barrett es un algoritmo que calcula eficientemente r≡ab mod p (donde p es fijo). La Reducción de Barrett intenta reemplazar la división (una operación costosa) por la división aproximada. Se puede seleccionar una tolerancia de error para describir el rango dentro del cual estamos buscando el resultado correcto. Encontramos que la gran tolerancia al error permite el uso de constantes de reducción más pequeñas; Esto reduce el tamaño de los valores intermedios utilizados en las operaciones de reducción de módulos, lo que reduce el número de multiplicaciones necesarias para calcular el resultado final.
En el cuadro azul de abajo, podemos ver que, debido a nuestra alta tolerancia a errores, tenemos que realizar múltiples comprobaciones para encontrar un resultado preciso.
En pocas palabras, el algoritmo de Karatsuba se utiliza para optimizar la multiplicación que realizamos en la Reducción de Barrett. El algoritmo de Karatsuba simplifica la multiplicación de dos n-dígitos a la multiplicación de tres n/2-dígitos; Estas multiplicaciones pueden simplificar el número de dígitos para que sean lo suficientemente estrechos como para ser calculados directamente por hardware. Los detalles se pueden leer en el artículo de Ingo: Pipe MSM
Utilizando los operadores anteriores, hemos desarrollado una implementación de MSM de baja latencia y altamente paralela.
La idea central es que, en lugar de calcular todo el MSM a la vez, cada fragmento se pasa al sumador EC en paralelo. Los resultados del sumador de EC se acumulan en el MSM final.
Resultado final****
El diagrama anterior muestra la comparación entre Sppark y PipeMSM.
Lo más destacado es el importante ahorro de energía que ofrecen las FPGA, que podrían ser extremadamente importantes para futuras operaciones de generación a prueba a gran escala. Vale la pena señalar que nuestra implementación fue prototipada y evaluada bajo @125MHz, y aumentar la velocidad del reloj a @500MHz podría aumentar el tiempo de cálculo en 4 veces o más.
Otra ventaja de usar nuestras FPGAs es que se pueden instalar en servidores de chasis pequeños porque consumen menos energía y generan menos calor.
Estamos en las primeras etapas de la ingeniería de FPGA para ZKP y deberíamos esperar más mejoras en los algoritmos. Además, la FPGA está calculando el MSM mientras la CPU está inactiva, y puede ser posible lograr tiempos más rápidos utilizando la FPGA en combinación con los recursos del sistema (CPU/GPU).
Resumen
ZKP se ha convertido en una tecnología clave para los sistemas distribuidos.
La aplicación de ZKP irá mucho más allá de la simple ampliación del nivel de Ethereum, permitiendo la externalización de la computación a terceros no confiables, permitiendo el desarrollo de sistemas antes imposibles, como la computación en la nube distribuida, los sistemas de identidad y más.
Tradicionalmente, las optimizaciones de ZKP se han centrado en mejoras a nivel de software, pero a medida que aumente la demanda de un rendimiento más superior, veremos soluciones de aceleración más avanzadas que involucren tanto hardware como software.
En la actualidad, las soluciones de aceleración que vemos utilizan principalmente GPU, porque el tiempo de desarrollo con CUDA es corto, y las GPU de consumo actuales son muy baratas y abundantes. La GPU también ofrece un rendimiento increíble. Por lo tanto, es poco probable que las GPU desaparezcan de este espacio en el corto plazo.
A medida que los equipos de desarrollo más complejos entren en el espacio, es probable que veamos FPGA liderando el camino en términos de eficiencia energética y rendimiento. En comparación con las GPU, las FPGA ofrecen más personalización de bajo nivel, así como más opciones de configuración. Las FPGA ofrecen una velocidad de desarrollo y flexibilidad más rápidas que los ASIC. Con el rápido desarrollo del mundo ZKP, las FPGA se pueden reflashear con diferentes programas para adaptarse a diferentes sistemas y soluciones de actualización.
Sin embargo, para generar pruebas casi en tiempo real, puede ser necesario combinar configuraciones de GPU/FPGA/ASIC dependiendo del sistema para el que generemos pruebas.
También es probable que ZPU evolucione para proporcionar soluciones extremadamente eficientes para generadores a prueba de gran escala y dispositivos de baja potencia (consulte el artículo anterior para obtener más detalles).