Un résumé de Fflonk

Le système de preuve Plonk, introduit en 2019, résume un ensemble complet de polynômes de circuit. Plus tard, une porte personnalisée et une table de recherche sont ajoutées au système Plonk. Ces techniques extraient essentiellement plus de polynômes. La capacité d'expression de ces polynômes est plus forte, ce qui peut résumer le processus de calcul relativement complexe en polynômes inférieurs, économisant ainsi de nombreuses portes Plonk. Avec l'utilisation croissante de la technologie de porte personnalisée et de la table de consultation, davantage de polynômes et de points ouverts apparaissent dans le système Plonk.

D'une part, les systèmes blockchain sont très sensibles à la complexité de la vérification. D'autre part, différents systèmes d'engagement polynomial ont une complexité de vérification différente pour le nombre de polynômes et le nombre de points ouverts. Par conséquent, il est nécessaire de comparer les systèmes d'engagement polynomiaux.

(1) la complexité de vérification de l'engagement KZG est linéairement liée au nombre de polynômes et au nombre de points ouverts. En l'absence de portes personnalisées et de tables de recherche, le système Plonk utilise l'engagement de KZG pour vérifier une complexité de 2 cartes bilinéaires et 18 opérations multipoints .

(2) la complexité de vérification de l'engagement de Dan n'est liée qu'au nombre de polynômes, mais pas au nombre de points ouverts. En l'absence de portes personnalisées et de tables de recherche, le système Plonk utilise l'engagement KZG pour vérifier une complexité de 2 cartes bilinéaires et 16 opérations multipoints.

Pour les engagements KZG et les engagements Dan, si des tables de consultation et des techniques de porte personnalisées sont utilisées, le calcul de plusieurs points sera encore augmenté.

(3) Utiliser Fflonk pour combiner plusieurs polynômes en un seul polynôme, puis utiliser l'engagement Dan. Le système Plonk ne nécessite que 2 cartes bilinéaires et 5 opérations multipoints . De plus, avec les tables de correspondance et la porte personnalisée, la complexité de la vérification n'est pas augmentée et elle est constante. Par conséquent, la technologie Fflonk combinée à l'engagement de Dan est la solution optimale dans le système Plonk.

Comment ça fonctionne

Fflonk convertit m polynômes f1(X),…,fm(X) ouvrant n points a1,…,an en un équivalent de 1 polynôme F(X) ouvrant m*n points b1,…,b_n*m.

Le principe est le suivant : on définit des opérateurs et pour regrouper et décomposer des polynômes « style FFT » :

Notez qu'il s'agit d'opérations injectives et inverses. C'est-à-dire que pour tout

Notation concernant les racines

Le lemme simple suivant est la base de notre schéma.

Convertit alors 1 polynômes F(X) ouvrant n*m points b1,…,b_n*m. en un équivalent de 1 polynôme L(X) ouvrant 1 points a.

Le principe est le suivant :

Pour résumer, nous simplifions finalement à 1 polynôme L(X) ouvrant 1 points a, qui peut être engagé en utilisant le système d'engagement KZG.

Pour plus de détails, veuillez lire l' article original et la vidéo , et bienvenue pour en discuter ici.