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.
Escrito por: Estrella Li
La tecnología de prueba de conocimiento cero se usa cada vez más, como prueba de privacidad, prueba de cálculo, prueba de consenso, etc. Mientras buscaban más y mejores escenarios de aplicación, muchas personas han descubierto gradualmente que la prueba de conocimiento cero demuestra que el rendimiento es un cuello de botella. El equipo de Trapdoor Tech ha estado investigando profundamente la tecnología de prueba de conocimiento cero desde 2019 y ha estado explorando soluciones eficientes de aceleración de prueba de conocimiento cero. GPU o FPGA son plataformas de aceleración relativamente comunes actualmente en el mercado. Este artículo comienza con el cálculo de MSM y analiza las ventajas y desventajas del cálculo de prueba de conocimiento cero acelerado por FPGA y GPU.
##TL;DR
ZKP es una tecnología con amplias perspectivas de futuro. Cada vez más aplicaciones están adoptando tecnología de prueba de conocimiento cero. Sin embargo, hay muchos algoritmos ZKP y varios proyectos usan diferentes algoritmos ZKP. Al mismo tiempo, el rendimiento computacional de la prueba ZKP es relativamente pobre. Este documento 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 computación de prueba ZKP, la GPU a corto plazo tiene ventajas obvias, alto rendimiento, rendimiento de alto costo, programabilidad, etc. En términos relativos, FPGA tiene ciertas ventajas en el consumo de energía. A la larga, puede haber chips FPGA adecuados para cálculos ZKP o chips ASIC personalizados para ZKP.
Complejo de algoritmo ZKP
ZKP es un término general para la tecnología Zero Knowledge Proof (Prueba de conocimiento cero). Existen principalmente dos clasificaciones: zk-SNARK y zk-STARK. Los algoritmos comunes actuales de zk-SNARK son Groth16, PLONK, PLOOKUP, Marlin y Halo/Halo2. La iteración del algoritmo zk-SNARK es principalmente en dos direcciones: 1/si se necesita una configuración confiable 2/el rendimiento de la estructura del circuito. La ventaja del algoritmo zk-STARK es que no se requiere una configuración confiable, pero la cantidad de cálculo de verificación es logarítmica lineal.
En lo que respecta a 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 necesita una configuración confiable), puede haber más y más aplicaciones.
PLONK demuestra la cantidad de cálculo
Tomando el algoritmo PLONK como ejemplo, analice la cantidad de cálculo de la prueba PLONK.
La cantidad de 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 polinómicos.
2/ Cómputo NTT - Conversión polinomial entre el valor del punto y la representación del coeficiente.
3/ Cálculo de polinomios: suma, resta, multiplicación y división de polinomios. Evaluación de polinomios (uación) y así sucesivamente.
4/ Síntesis de circuitos - síntesis de circuitos. El cálculo de esta parte está relacionado con la escala/complejidad del circuito.
En términos generales, la cantidad de cálculo en la parte de síntesis de circuito es más juicio y lógica de bucle, y el grado de paralelismo es relativamente bajo, lo que 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, la cantidad de cálculo de MSM es relativamente la más grande, seguida por NTT.
¿Qué es MSM?
MSM (Multiple Scalar Multiplication) se refiere a una serie dada de puntos y escalares en la curva elíptica, y calcula los puntos correspondientes a los resultados de la suma de 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 específica:
[G_1, G_2, G_3, ..., G_n]
y coeficientes aleatorios:
y elementos de campo finito muestreados aleatoriamente del 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 = \sum_{i=1}^{n}s_i*G_i
La industria generalmente adopta el algoritmo de Pippenger para optimizar el cálculo de MSM. Eche un vistazo más de cerca 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/ División escalar en Windows. Si Scalar es de 256 bits y una ventana es de 8 bits, entonces todos los Scalars se dividen en 256/8 = 32 Windows. Cada capa de Window usa un "Cubo" para almacenar temporalmente resultados intermedios. GW_x es el resultado del punto de acumulación en una capa. Calcular GW_x también es relativamente simple. Atraviesa cada escalar en una capa a su vez, usa el valor de la capa escalar como índice y agrega el G_x correspondiente a los cubos correspondientes. De hecho, el principio es relativamente simple: si los coeficientes de la suma de dos puntos son iguales, primero se suman los dos puntos y luego se vuelve a sumar el Escalar, en lugar de sumar los dos puntos dos veces antes de sumar el Escalar.
2/ Los puntos calculados por cada Ventana se acumulan por doble suma para obtener el resultado final.
El algoritmo de Pippenger también tiene muchos algoritmos de optimización de 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 puntos agregados.
Suma de puntos de curva elíptica (Point Add)
Puede consultar varios algoritmos para la suma de puntos en curvas elípticas con forma de "Weierstrass corta" en este sitio.
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) puede calcularse mediante la siguiente fórmula de cálculo.
La razón para dar el proceso de cálculo en detalle es mostrar que todo el proceso de cálculo consiste principalmente en operaciones con números enteros. El ancho de bit del entero depende de los parámetros de la curva elíptica. Proporcione los anchos de bit de algunas curvas elípticas comunes:
BN256 - 256 bits
BLS12_381 - 381 bits
BLS12_377 - 377bits
Atención especial es que estas operaciones con enteros son operaciones sobre el campo módulo. La suma modular/resta de módulo es relativamente simple, se enfoca en el principio y la implementación de la multiplicación modular.
模乘（Multiplicación modular）
Dados dos valores sobre un campo de módulo: x e y. El cálculo de la multiplicación modular se refiere a x*y mod p. Tenga en cuenta que el ancho de bits de estos enteros es el ancho de bits de la curva elíptica. El algoritmo clásico de la multiplicación modular es la multiplicación de Montgomery (MontgomeryMulplication). Antes de realizar la multiplicación de Montgomery, el multiplicando debe convertirse a la representación de Montgomery:
La fórmula para calcular la multiplicación de Montgomery es la siguiente:
Hay muchos algoritmos de implementación de multiplicación de Montgomery: CIOS (Escaneo de operandos integrados gruesos), FIOS (Escaneo de operandos integrados finamente) y FIPS (Escaneo de productos integrados finamente), etc. Este artículo no presenta los detalles de varias implementaciones de algoritmos en profundidad, y los lectores interesados pueden hacer su propia investigación.
Para comparar la diferencia de rendimiento entre FPGA y GPU, elija el método de implementación de 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
Bajo tal diseño de FPGA, se puede estimar que todo el VU9P puede proporcionar el rendimiento en BLS12_381 puntos de curva elíptica. Una suma de puntos (forma add_mix) requiere alrededor de 12 multiplicaciones modulares. El reloj del sistema de FPGA es 450M.
Bajo el mismo algoritmo de adición de módulo/multiplicación modular, utilizando el mismo algoritmo de adición de punto, el punto más Troughput de Nvidia 3090 (considerando los factores de transmisión de datos) supera los 500M/s. Por supuesto, todo el cálculo involucra una variedad de algoritmos, algunos algoritmos pueden ser adecuados para FPGA y algunos algoritmos son adecuados para GPU. La razón para usar la misma comparación de algoritmos es comparar las capacidades informáticas centrales de FPGA y GPU.
Con base en los resultados anteriores, resuma la comparación entre GPU y FPGA en términos de rendimiento de prueba ZKP:
Resumir
Cada vez más aplicaciones están adoptando tecnología de prueba de conocimiento cero. Sin embargo, hay muchos algoritmos ZKP y varios proyectos usan diferentes algoritmos ZKP. Desde nuestra experiencia práctica en ingeniería, FPGA es una opción, pero GPU es actualmente una opción rentable. FPGA prefiere la computación determinista, que tiene las ventajas de la latencia y el consumo de energía. GPU tiene una alta capacidad de programación, tiene un marco informático de alto rendimiento relativamente maduro y tiene un ciclo de iteración de desarrollo corto y prefiere escenarios de rendimiento.
Ver originales
El contenido es solo de referencia, no una solicitud u oferta. No se proporciona asesoramiento fiscal, legal ni de inversión. Consulte el Descargo de responsabilidad para obtener más información sobre los riesgos.
Un artículo para comprender las ventajas y desventajas de la computación acelerada a prueba de conocimiento cero con FPGA y GPU
Escrito por: Estrella Li
La tecnología de prueba de conocimiento cero se usa cada vez más, como prueba de privacidad, prueba de cálculo, prueba de consenso, etc. Mientras buscaban más y mejores escenarios de aplicación, muchas personas han descubierto gradualmente que la prueba de conocimiento cero demuestra que el rendimiento es un cuello de botella. El equipo de Trapdoor Tech ha estado investigando profundamente la tecnología de prueba de conocimiento cero desde 2019 y ha estado explorando soluciones eficientes de aceleración de prueba de conocimiento cero. GPU o FPGA son plataformas de aceleración relativamente comunes actualmente en el mercado. Este artículo comienza con el cálculo de MSM y analiza las ventajas y desventajas del cálculo de prueba de conocimiento cero acelerado por FPGA y GPU.
##TL;DR
ZKP es una tecnología con amplias perspectivas de futuro. Cada vez más aplicaciones están adoptando tecnología de prueba de conocimiento cero. Sin embargo, hay muchos algoritmos ZKP y varios proyectos usan diferentes algoritmos ZKP. Al mismo tiempo, el rendimiento computacional de la prueba ZKP es relativamente pobre. Este documento 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 computación de prueba ZKP, la GPU a corto plazo tiene ventajas obvias, alto rendimiento, rendimiento de alto costo, programabilidad, etc. En términos relativos, FPGA tiene ciertas ventajas en el consumo de energía. A la larga, puede haber chips FPGA adecuados para cálculos ZKP o chips ASIC personalizados para ZKP.
Complejo de algoritmo ZKP
ZKP es un término general para la tecnología Zero Knowledge Proof (Prueba de conocimiento cero). Existen principalmente dos clasificaciones: zk-SNARK y zk-STARK. Los algoritmos comunes actuales de zk-SNARK son Groth16, PLONK, PLOOKUP, Marlin y Halo/Halo2. La iteración del algoritmo zk-SNARK es principalmente en dos direcciones: 1/si se necesita una configuración confiable 2/el rendimiento de la estructura del circuito. La ventaja del algoritmo zk-STARK es que no se requiere una configuración confiable, pero la cantidad de cálculo de verificación es logarítmica lineal.
En lo que respecta a 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 necesita una configuración confiable), puede haber más y más aplicaciones.
PLONK demuestra la cantidad de cálculo
Tomando el algoritmo PLONK como ejemplo, analice la cantidad de cálculo de la prueba PLONK.
La cantidad de 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 polinómicos.
2/ Cómputo NTT - Conversión polinomial entre el valor del punto y la representación del coeficiente.
3/ Cálculo de polinomios: suma, resta, multiplicación y división de polinomios. Evaluación de polinomios (uación) y así sucesivamente.
4/ Síntesis de circuitos - síntesis de circuitos. El cálculo de esta parte está relacionado con la escala/complejidad del circuito.
En términos generales, la cantidad de cálculo en la parte de síntesis de circuito es más juicio y lógica de bucle, y el grado de paralelismo es relativamente bajo, lo que 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, la cantidad de cálculo de MSM es relativamente la más grande, seguida por NTT.
¿Qué es MSM?
MSM (Multiple Scalar Multiplication) se refiere a una serie dada de puntos y escalares en la curva elíptica, y calcula los puntos correspondientes a los resultados de la suma de 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 específica:
[G_1, G_2, G_3, ..., G_n]
y coeficientes aleatorios:
y elementos de campo finito muestreados aleatoriamente del 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 = \sum_{i=1}^{n}s_i*G_i
La industria generalmente adopta el algoritmo de Pippenger para optimizar el cálculo de MSM. Eche un vistazo más de cerca 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/ División escalar en Windows. Si Scalar es de 256 bits y una ventana es de 8 bits, entonces todos los Scalars se dividen en 256/8 = 32 Windows. Cada capa de Window usa un "Cubo" para almacenar temporalmente resultados intermedios. GW_x es el resultado del punto de acumulación en una capa. Calcular GW_x también es relativamente simple. Atraviesa cada escalar en una capa a su vez, usa el valor de la capa escalar como índice y agrega el G_x correspondiente a los cubos correspondientes. De hecho, el principio es relativamente simple: si los coeficientes de la suma de dos puntos son iguales, primero se suman los dos puntos y luego se vuelve a sumar el Escalar, en lugar de sumar los dos puntos dos veces antes de sumar el Escalar.
2/ Los puntos calculados por cada Ventana se acumulan por doble suma para obtener el resultado final.
El algoritmo de Pippenger también tiene muchos algoritmos de optimización de 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 puntos agregados.
Suma de puntos de curva elíptica (Point Add)
Puede consultar varios algoritmos para la suma de puntos en curvas elípticas con forma de "Weierstrass corta" en este sitio.
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) puede calcularse mediante la siguiente fórmula de cálculo.
La razón para dar el proceso de cálculo en detalle es mostrar que todo el proceso de cálculo consiste principalmente en operaciones con números enteros. El ancho de bit del entero depende de los parámetros de la curva elíptica. Proporcione los anchos de bit de algunas curvas elípticas comunes:
模乘（Multiplicación modular）
Dados dos valores sobre un campo de módulo: x e y. El cálculo de la multiplicación modular se refiere a x*y mod p. Tenga en cuenta que el ancho de bits de estos enteros es el ancho de bits de la curva elíptica. El algoritmo clásico de la multiplicación modular es la multiplicación de Montgomery (MontgomeryMulplication). Antes de realizar la multiplicación de Montgomery, el multiplicando debe convertirse a la representación de Montgomery:
La fórmula para calcular la multiplicación de Montgomery es la siguiente:
Hay muchos algoritmos de implementación de multiplicación de Montgomery: CIOS (Escaneo de operandos integrados gruesos), FIOS (Escaneo de operandos integrados finamente) y FIPS (Escaneo de productos integrados finamente), etc. Este artículo no presenta los detalles de varias implementaciones de algoritmos en profundidad, y los lectores interesados pueden hacer su propia investigación.
Para comparar la diferencia de rendimiento entre FPGA y GPU, elija el método de implementación de 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
Bajo tal diseño de FPGA, se puede estimar que todo el VU9P puede proporcionar el rendimiento en BLS12_381 puntos de curva elíptica. Una suma de puntos (forma add_mix) requiere alrededor de 12 multiplicaciones modulares. El reloj del sistema de FPGA es 450M.
Bajo el mismo algoritmo de adición de módulo/multiplicación modular, utilizando el mismo algoritmo de adición de punto, el punto más Troughput de Nvidia 3090 (considerando los factores de transmisión de datos) supera los 500M/s. Por supuesto, todo el cálculo involucra una variedad de algoritmos, algunos algoritmos pueden ser adecuados para FPGA y algunos algoritmos son adecuados para GPU. La razón para usar la misma comparación de algoritmos es comparar las capacidades informáticas centrales de FPGA y GPU.
Con base en los resultados anteriores, resuma la comparación entre GPU y FPGA en términos de rendimiento de prueba ZKP:
Resumir
Cada vez más aplicaciones están adoptando tecnología de prueba de conocimiento cero. Sin embargo, hay muchos algoritmos ZKP y varios proyectos usan diferentes algoritmos ZKP. Desde nuestra experiencia práctica en ingeniería, FPGA es una opción, pero GPU es actualmente una opción rentable. FPGA prefiere la computación determinista, que tiene las ventajas de la latencia y el consumo de energía. GPU tiene una alta capacidad de programación, tiene un marco informático de alto rendimiento relativamente maduro y tiene un ciclo de iteración de desarrollo corto y prefiere escenarios de rendimiento.