Um Resumo de Fflonk

O sistema de prova Plonk, introduzido em 2019, abstrai um conjunto completo de polinômios de circuito. Mais tarde, o portão personalizado e a tabela de pesquisa são adicionados ao sistema Plonk. Essas técnicas estão essencialmente abstraindo mais polinômios. A capacidade de expressão desses polinômios é mais forte, o que pode abstrair o processo de cálculo relativamente complexo em polinômios menores, economizando assim muitos portões Plonk. Com o uso crescente da tecnologia de porta personalizada e tabela de consulta, mais polinômios e mais pontos abertos aparecem no sistema Plonk.

Por um lado, os sistemas blockchain são muito sensíveis à complexidade da verificação. Por outro lado, diferentes sistemas de compromisso polinomial têm diferentes complexidades de verificação para o número de polinômios e o número de pontos abertos. Portanto, é necessário comparar os sistemas de compromisso polinomial.

(1) a complexidade de verificação do comprometimento KZG é linearmente relacionada ao número de polinômios e ao número de pontos abertos. Na ausência de portas personalizadas e tabelas de pesquisa, o sistema Plonk usa o compromisso KZG para verificar uma complexidade de 2 mapas bilineares e 18 operações multiponto .

(2) a complexidade de verificação do comprometimento de Dan está relacionada apenas ao número de polinômios, mas não ao número de pontos em aberto. Na ausência de portas personalizadas e tabelas de pesquisa, o sistema Plonk usa o compromisso KZG para verificar uma complexidade de 2 mapas bilineares e 16 operações multiponto.

Para compromissos KZG e compromissos Dan, se forem usadas tabelas de consulta e técnicas de portão personalizadas, o cálculo de pontos múltiplos será aumentado ainda mais.

(3) Usando Fflonk para combinar vários polinômios em um polinômio e, em seguida, usando o compromisso de Dan. O sistema Plonk requer apenas 2 mapas bilineares e 5 operações multiponto . Além disso, com tabelas de consulta e portão personalizado, a complexidade da verificação não é aumentada e é constante. Portanto, a tecnologia Fflonk combinada com o compromisso de Dan é a solução ideal no sistema Plonk.

Como funciona

Fflonk converte m polinômios f1(X),…,fm(X) abrindo n pontos a1,…,an em um equivalente de 1 polinômio F(X) abrindo m*n pontos b1,…,b_n*m.

O princípio é o seguinte: definimos operadores e agrupamos e decompomos polinômios “estilo FFT”:

Observe que essas são operações injetivas e inversas. Ou seja, para qualquer

Notação sobre raízes

O seguinte lema simples é a base do nosso esquema.

Então converte 1 polinômio F(X) abrindo n*m pontos b1,…,b_n*m. em um equivalente de 1 polinômio L(X) abrindo 1 pontos a.

O princípio é o seguinte:

Para resumir, finalmente simplificamos para 1 polinômio L(X) abrindo 1 pontos a, que podem ser confirmados usando o sistema de compromisso KZG.

Para obter mais detalhes, leia o artigo e o vídeo originais e seja bem-vindo para discutir aqui.