Un resumen de Fflonk

El sistema de prueba de Plonk, introducido en 2019, abstrae un conjunto completo de polinomios de circuito. Más tarde, se agregan puertas personalizadas y tablas de búsqueda en el sistema Plonk. Estas técnicas esencialmente abstraen más polinomios. La capacidad de expresión de estos polinomios es más fuerte, lo que puede abstraer el proceso de cálculo relativamente complejo en polinomios más bajos, ahorrando así muchas puertas de Plonk. Con el uso cada vez mayor de la tecnología de puerta personalizada y la tabla de búsqueda, aparecen más polinomios y más puntos abiertos en el sistema Plonk.

Por un lado, los sistemas de cadena de bloques son muy sensibles a la complejidad de la verificación. Por otro lado, diferentes sistemas de compromiso de polinomios tienen diferente complejidad de verificación para el número de polinomios y el número de puntos abiertos. Por lo tanto, es necesario comparar los sistemas de compromiso de polinomios.

(1) la complejidad de verificación del compromiso KZG está relacionada linealmente con el número de polinomios y el número de puntos abiertos. En ausencia de puertas personalizadas y tablas de búsqueda, el sistema Plonk utiliza el compromiso de KZG para verificar una complejidad de 2 mapas bilineales y 18 operaciones multipunto .

(2) la complejidad de verificación del compromiso de Dan solo está relacionada con el número de polinomios, pero no con el número de puntos abiertos. En ausencia de puertas personalizadas y tablas de búsqueda, el sistema Plonk utiliza el compromiso de KZG para verificar una complejidad de 2 mapas bilineales y 16 operaciones multipunto.

Para compromisos KZG y compromisos Dan, si se utilizan tablas de búsqueda y técnicas de puerta personalizadas, el cálculo de puntos múltiples aumentará aún más.

(3) Usar Fflonk para combinar múltiples polinomios en un polinomio y luego usar el compromiso de Dan. El sistema Plonk requiere solo 2 mapas bilineales y 5 operaciones multipunto . Además, con las tablas de búsqueda y la puerta personalizada, la complejidad de la verificación no aumenta y es constante. Por lo tanto, la tecnología Fflonk combinada con el compromiso de Dan es la solución óptima en el sistema Plonk.

Cómo funciona

Fflonk convierte m polinomios f1(X),…,fm(X) que abren n puntos a1,…,an en un equivalente de 1 polinomio F(X) que abre m*n puntos b1,…,b_n*m.

El principio es el siguiente: definimos operadores y para agrupar y descomponer polinomios "estilo FFT":

Tenga en cuenta que estas son operaciones inyectivas e inversas. Es decir, para cualquier

Notación sobre raíces

El siguiente lema simple es la base de nuestro esquema.

Luego convierte 1 polinomios F(X) abriendo n*m puntos b1,…,b_n*m. en un equivalente de 1 polinomio L(X) que abre 1 puntos a.

El principio es el siguiente:

Para resumir, finalmente simplificamos a 1 polinomio L(X) que abre 1 punto a, que puede comprometerse usando el sistema de compromiso KZG.

Para obtener más detalles, lea el documento y el video originales , y bienvenido a discutir aquí.