Autor: Estrella Li
Este artículo está destinado únicamente a fines de aprendizaje e intercambio de la industria y no constituye ninguna referencia de inversión. Si necesita una cotización, indique la fuente. Para la reimpresión, comuníquese con el equipo de IOSG para obtener autorización e instrucciones de reimpresión. ¡Un agradecimiento especial a la autora Star Li por el contenido!
La tecnología de prueba de conocimiento cero se utiliza cada vez más en pruebas de privacidad, pruebas de cálculo, pruebas de consenso, etc. Mientras buscaban más y mejores escenarios de aplicación, muchas personas han descubierto gradualmente que el rendimiento a prueba de conocimiento cero es un cuello de botella. El equipo de Trapdoor Tech comenzó una investigación en profundidad sobre la tecnología a prueba de conocimiento cero en 2019 y ha estado explorando soluciones eficientes de aceleración a prueba de conocimiento cero. GPU o FPGA son plataformas de aceleración comunes actualmente en el mercado. Este artículo comienza con el cálculo de MSM y analiza las ventajas y desventajas de los cálculos de prueba de conocimiento cero acelerados por FPGA y GPU.
TL;DR
ZKP es una tecnología con amplias perspectivas de futuro. Cada vez más aplicaciones están comenzando a adoptar tecnología de prueba de conocimiento cero. Sin embargo, existen muchos algoritmos ZKP y varios proyectos utilizan diferentes algoritmos ZKP. Al mismo tiempo, el rendimiento computacional de la prueba ZKP es relativamente pobre. Este artículo analiza en detalle el algoritmo MSM, el algoritmo de suma de puntos de curva elíptica, el algoritmo de multiplicación de Montgomery, etc., y compara la diferencia de rendimiento entre GPU y FPGA en la suma de puntos de curva BLS12_381. En general, en términos de cálculos de prueba ZKP, las ventajas a corto plazo de la GPU son relativamente obvias, como alto rendimiento, alto costo, programabilidad, etc. FPGA tiene ciertas ventajas en términos de consumo de energía. A largo plazo, es posible que existan chips FPGA adecuados para cálculos ZKP o chips ASIC personalizados para ZKP.
El algoritmo ZKP es complejo
ZKP es el nombre colectivo de la tecnología de prueba de conocimiento cero (Zero Knowledge Proof). Hay dos categorías principales: zk-SNARK y zk-STARK. Los algoritmos comunes actualmente para zk-SNARK son Groth16, PLONK, PLOOKUP, Marlin y Halo/Halo2. La iteración del algoritmo zk-SNARK se realiza principalmente en dos direcciones: 1/si se requiere una configuración confiable 2/el rendimiento de la estructura del circuito. La ventaja del algoritmo zk-STARK es que no requiere una configuración confiable, pero la cantidad de cálculo de verificación es logarítmica lineal.
En términos de la aplicación del algoritmo zk-SNARK/zk-STARK, los algoritmos de prueba de conocimiento cero utilizados por diferentes proyectos están relativamente dispersos. En la aplicación del algoritmo zk-SNARK, debido a que el algoritmo PLONK/Halo2 es universal (no se requiere una configuración confiable), puede haber cada vez más aplicaciones.
PLONK demuestra el esfuerzo computacional
Tome el algoritmo PLONK como ejemplo para analizar la cantidad de cálculo de la prueba PLONK.
El importe del cálculo de la parte de prueba PLONK consta de cuatro partes:
1/ MSM - Multiplicación escalar múltiple. MSM se utiliza a menudo para calcular compromisos polinomiales.
2/ Cálculo de NTT: transformaciones polinómicas entre el valor del punto y la representación del coeficiente.
3/ Cálculos de polinomios: suma, resta, multiplicación y división de polinomios. Evaluación polinómica (Evaluación), etc.
4/ Sintetizar circuitos - Síntesis de circuitos. Esta parte del cálculo está relacionada con el tamaño/complejidad del circuito.
En términos generales, la cantidad de cálculo de la parte Circuit Synthesize es más lógica de juicio y bucle, el grado de paralelismo es relativamente bajo y es más adecuado para el cálculo de la CPU. En términos generales, la aceleración de prueba de conocimiento cero generalmente se refiere a la aceleración de cálculo de las tres primeras partes. Entre ellos, MSM tiene relativamente la mayor cantidad de cálculo, seguido de NTT.
¿Qué es MSM?
MSM (multiplicación escalar múltiple) se refiere a una serie dada de puntos y escalares en la curva elíptica, y calcula el punto correspondiente al resultado de sumar estos puntos.
Por ejemplo, dada una serie de puntos en una curva elíptica:
Dado un conjunto fijo de puntos de curva elíptica de una curva especificada:
[Sol_1, Sol_2, Sol_3, ..., Sol_n]
Y coeficientes aleatorios:
y un campo finito de elementos muestreados aleatoriamente de un campo escalar especificado:
[s_1, s_2, s_3, ..., s_n]
MSM es el cálculo para obtener el punto Q de la curva elíptica:
Q = suma_{i=1}^{n}s_i*G_i
La industria generalmente utiliza el algoritmo de Pippenger para optimizar los cálculos de MSM. Echemos un vistazo en profundidad al diagrama esquemático del proceso del algoritmo de Pippenger:
El proceso de cálculo del algoritmo de Pippenger se divide en dos pasos:
1/ Scalar se divide en Windows. Si el escalar es de 256 bits y una ventana es de 8 bits, entonces todo el escalar se divide en 256/8 = 32 ventanas. Cada capa de Ventana utiliza "Cubos" para almacenar temporalmente resultados intermedios. GW_x es el punto del resultado acumulativo en una capa. Calcular GW_x también es relativamente simple. Cada escalar en una capa se recorre por turno, y el valor de la capa escalar se usa como índice, y el G_x correspondiente se agrega al bit de cubos correspondiente. De hecho, el principio es relativamente simple. Si los coeficientes de la suma de dos puntos son iguales, primero sume los dos puntos y luego haga una suma escalar. No es necesario hacer dos sumas escalares para los dos puntos y luego sumar. ellos arriba.
2/ Los puntos calculados por cada Ventana se acumulan mediante doble suma para obtener el resultado final.
El algoritmo de Pippenger también tiene muchos algoritmos de optimización de la deformación. En cualquier caso, el cálculo subyacente del algoritmo MSM es la suma de puntos en la curva elíptica. Diferentes algoritmos de optimización corresponden a diferentes números de suma de puntos.
Agregar punto de curva elíptica
Puede consultar varios algoritmos para la suma de puntos en curvas elípticas de la forma "weierstrass corta" en este sitio web.
http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
Suponiendo que las coordenadas proyectivas de los dos puntos son (x1, y1, z1) y (x2, y2, z2) respectivamente, el resultado de la suma de puntos (x3, y3, z3) se puede calcular mediante la siguiente fórmula de cálculo.
La razón para dar el proceso de cálculo en detalle es para mostrar que todo el proceso de cálculo consiste principalmente en operaciones de números enteros. El ancho de bits de un número entero depende de los parámetros de la curva elíptica. Indique los anchos de bits de algunas curvas elípticas comunes:
BN256 - 256 bits BLS12_381 - 381 bits BLS12_377 - 377 bits
Tenga en cuenta en particular que estas operaciones con números enteros son operaciones en el campo de módulo. La suma/resta modular es relativamente simple. Centrémonos en el principio y la implementación de la multiplicación modular.
Multiplicación modular
Dados dos valores en el dominio modular: x e y. Los cálculos de multiplicación modular se refieren a x*y mod p. Tenga en cuenta que el ancho de bits de estos números enteros es el de la curva elíptica. El algoritmo clásico para la multiplicación modular es la multiplicación de Montgomery. Antes de realizar la multiplicación de Montgomery, es necesario convertir el multiplicando a la representación de Montgomery:
La fórmula para la multiplicación de Montgomery es la siguiente:
Existen muchos algoritmos de implementación de multiplicación de Montgomery: CIOS (escaneo de operandos finamente integrado), FIOS (escaneo de operandos finamente integrado) y FIPS (escaneo de productos finamente integrado), etc. Este artículo no entra en detalles sobre la implementación de varios algoritmos y los lectores interesados pueden estudiarlo por su cuenta.
Para comparar las diferencias de rendimiento entre FPGA y GPU, se selecciona el método de implementación del algoritmo más básico:
En pocas palabras, el algoritmo de multiplicación modular se puede dividir en dos cálculos: multiplicación de números grandes y suma de números grandes. Después de comprender la lógica de cálculo de MSM, puede elegir el rendimiento de la multiplicación modular (rendimiento) para comparar el rendimiento de FPGA y GPU.
Observa y piensa
Con un diseño de FPGA de este tipo, se puede estimar que todo el VU9P puede proporcionar rendimiento en puntos de curva elíptica BLS12_381. La suma de un punto (método add_mix) requiere aproximadamente 12 multiplicaciones modulares. El reloj del sistema de FPGA es 450M.
Bajo el mismo algoritmo modular de multiplicación/suma de módulos, utilizando el mismo algoritmo de suma de puntos, el rendimiento de suma de puntos de la Nvidia 3090 (teniendo en cuenta los factores de transmisión de datos) supera los 500 M/s. Por supuesto, todo el cálculo implica una variedad de algoritmos. Puede haber algunos algoritmos adecuados para FPGA y algunos algoritmos adecuados para GPU. La razón para utilizar la misma comparación de algoritmos es comparar las capacidades informáticas centrales de FPGA y GPU.
Con base en los resultados anteriores, resumamos la comparación entre GPU y FPGA en términos de rendimiento de prueba ZKP:
Resumir
Cada vez más aplicaciones están comenzando a adoptar tecnología de prueba de conocimiento cero. Sin embargo, existen muchos algoritmos ZKP y varios proyectos utilizan diferentes algoritmos ZKP. A juzgar por nuestra experiencia práctica en ingeniería, FPGA es una opción, pero actualmente la GPU es una opción rentable. FPGA prefiere la computación determinista y tiene ventajas en latencia y consumo de energía. La GPU es altamente programable, tiene un marco informático de alto rendimiento relativamente maduro, tiene un ciclo de iteración de desarrollo corto y prefiere escenarios de rendimiento.