Expliquez en détail les deux nouveaux outils SNARK lancés par a16z crypto

Cet article provient d'un 16 z, l'auteur original : Justin Thaler, compilé par Jessica, traductrice d'Odaily Planet Daily.

Le 10 août, un crypto 16z a lancé de nouveaux outils basés sur SNARK Lasso et Jolt, qui représentent ensemble une nouvelle approche de la conception SNARK qui peut améliorer les performances des chaînes d'outils largement déployées d'un ordre de grandeur ou plus ; fournir un meilleur, un plus pratique l'expérience des développeurs et facilite l'audit.

SNARK (Succinct Non-Interactive Argument of Knowledge) est un protocole cryptographique par lequel n'importe qui peut prouver à un vérificateur non fiable qu'il connaît un "témoin" qui satisfait certaines propriétés.

• Un cas d'utilisation important dans Web 3 est que L2 prouve à L1 qu'il connaît la signature numérique autorisant une série de transactions, de sorte que la signature elle-même n'a pas à être stockée et vérifiée par le réseau L1, ce qui améliore l'évolutivité.
• Les applications en dehors de la blockchain incluent : prouver rapidement la validité de toutes les sorties produites par des périphériques matériels non fiables, en veillant à ce que les utilisateurs puissent leur faire confiance. Les individus peuvent prouver en toute connaissance de cause qu'une autorité de confiance leur a délivré des identifiants prouvant qu'ils sont assez âgés pour accéder à un contenu soumis à une limite d'âge sans révéler leur date de naissance. Toute personne envoyant des données cryptées sur le réseau peut prouver aux administrateurs que les données sont conformes à la politique du réseau sans révéler plus de détails.

Alors que de nombreux SNARK restent un coût attractif pour le vérificateur, les SNARK introduisent généralement encore environ six ordres de grandeur de surcharge dans le calcul du prouveur. Le travail supplémentaire supporté par le prouveur est hautement parallélisé, mais la surcharge de millions de fois limite considérablement le champ d'application des SNARK.

** SNARK avec plus d'avantages en termes de performances accélérera L 2 et permettra également aux constructeurs de déverrouiller des applications non encore envisagées. **C'est pourquoi nous introduisons deux nouvelles technologies associées : Lasso, un nouveau paramètre de recherche qui peut augmenter considérablement le coût du prouveur ; Jolt, qui utilise Lasso pour fournir un nouveau cadre pour le soi-disant zkVM Et une conception frontale plus large pour concevoir des SNARK. Ensemble, ils améliorent les performances, l'expérience des développeurs et l'auditabilité des conceptions SNARK, qui à leur tour améliorent les versions Web 3.

Notre implémentation initiale de Lasso a démontré des accélérations de plus de 10 fois par rapport aux paramètres de recherche dans la célèbre chaîne d'outils SNARK halo 2. Lorsque la base de code Lasso est entièrement optimisée, nous nous attendons à une accélération d'environ 40x. Jolt inclut d'autres innovations en plus de Lasso, et nous nous attendons à ce qu'il atteigne une accélération similaire ou meilleure que la zkVM existante.

Paramètres de recherche, Lasso et Jolt

Un frontal SNARK est un compilateur qui convertit un programme informatique en un circuit qu'un backend SNARK peut ingérer. (Remarque : un circuit est un modèle de calcul extrêmement limité où les seules "opérations primitives" disponibles sont l'addition et la multiplication.)

Un outil clé dans les conceptions SNARK modernes est un protocole appelé paramètres de recherche, qui permet à un prouveur non fiable de soumettre de manière cryptographique un grand vecteur, puis de prouver que chaque entrée de ce vecteur est contenue dans un milieu de table prédéterminé. Les paramètres de recherche peuvent aider à garder les circuits petits en traitant efficacement les opérations qui ne sont pas naturellement calculées par de petites additions et multiplications.

Cependant, comme l'a dit Barry Whitehat de la Fondation Ethereum l'année dernière, "si nous pouvons définir efficacement des circuits en utilisant uniquement des paramètres de recherche, cela conduira à des outils et des circuits plus simples". Le circuit que nous avons conçu n'effectue que des recherches. Au fil du temps, les paramètres de recherche "deviendront plus efficaces que les contraintes polynomiales pour presque tout".

Cette vision contraste fortement avec la façon dont les choses fonctionnent aujourd'hui, où les développeurs déploient des SNARK en écrivant des programmes utilisant des langages spéciaux spécifiques à un domaine qui compilent les programmes en contraintes polynomiales, ou en codant directement les contraintes à la main. Cette chaîne d'outils demande beaucoup de travail et offre une grande surface pour que les bogues critiques pour la sécurité puissent s'y glisser. Même avec des outils et des circuits complexes, les performances des SNARK sont encore lentes, ce qui limite leur applicabilité.

Lasso et Jolt traitent les trois problèmes clés : performances, expérience des développeurs et auditabilité, et ensemble, ils concrétisent la vision de trouver la singularité. Lasso et Jolt obligent également à repenser une grande partie de la sagesse acceptée dans la conception de SNARK.

Après avoir fourni le contexte nécessaire, ce qui suit revient sur certaines idées courantes sur les performances de SNARK et explique comment elles peuvent être optimisées à la lumière d'innovations telles que Lasso et Jolt.

Arrière-plan de conception SNARK : pourquoi si lent ?

La plupart des backends SNARK demandent au prouveur de s'engager cryptographiquement sur la valeur de chaque porte du circuit à l'aide d'un schéma d'engagement polynomial. Le démonstrateur prouve alors que la valeur soumise correspond bien à l'exécution correcte du vérificateur témoin.

** Je me réfère ** au travail de preuve d'un schéma d'engagement polynomial comme coût d'engagement. ** Les SNARK ont des coûts de preuve supplémentaires à partir des schémas d'engagement polynomial. Mais les coûts d'engagement sont souvent le goulot d'étranglement. **Lasso et Jolt également. Si un SNARK est conçu là où le coût d'engagement n'est pas le coût principal du prouveur, cela ne signifie pas que le schéma d'engagement polynomial est bon marché. Cela signifie plutôt que d'autres coûts sont plus élevés qu'ils ne devraient l'être.

Intuitivement, le but des engagements est d'augmenter de manière sécurisée cryptographiquement la simplicité des systèmes de preuve. Lorsqu'un prouveur soumet un grand vecteur de valeurs, c'est à peu près comme si le prouveur envoyait le vecteur entier au vérificateur, tout comme les systèmes de preuve normaux envoient le témoin entier au vérificateur. Les schémas d'engagement peuvent y parvenir sans obliger les validateurs à recevoir l'intégralité du témoin, ce qui signifie que le but du schéma d'engagement dans la conception SNARK est de contrôler les coûts du validateur.

Mais ces méthodes cryptographiques sont très coûteuses pour le prouveur, en particulier par rapport aux méthodes théoriques de l'information que SNARK utilise en dehors des schémas d'engagement polynomiaux. Les méthodes de la théorie de l'information reposent uniquement sur des opérations à champ fini. Et une opération sur le terrain est des ordres de grandeur plus rapide que le temps nécessaire pour soumettre un élément de terrain arbitraire.

Le calcul des engagements implique des exponentiations multiples (également appelées multiplications scalaires multiples ou MSM) ou des FFT et des hachages de Merkle, selon le schéma d'engagement polynomial utilisé. Lasso et Jolt peuvent utiliser n'importe quel schéma d'engagement polynomial, mais ont un coût particulièrement attractif lorsqu'ils sont instanciés à l'aide de schémas basés sur MSM, tels que IPA/Bulletproofs, KZG/PST, Hyrax, Dory ou Zeromorph.

Pourquoi Lasso et Jolt sont importants

Lasso est un nouveau paramètre de recherche où le prouveur promet des valeurs moins nombreuses et plus petites que les travaux précédents. ** Cela pourrait être une accélération de 20x ou plus **, où une accélération de 2 à 4x provient de moins de valeurs validées et une autre accélération de 10x vient du fait que toutes les valeurs validées dans Lasso sont petites. Contrairement à de nombreux paramètres de recherche précédents, Lasso (et Jolt) évitent également les FFT, qui prennent beaucoup de place et peuvent constituer un goulot d'étranglement pour les instances volumineuses.

De plus, Lasso fonctionne même avec des tables énormes, tant que ces tables sont "structurées" (au sens technique précis). Ces tables sont trop volumineuses pour que quiconque les implémente explicitement, mais Lasso ne paie que pour les éléments de table auxquels il accède réellement. En particulier, par rapport aux paramètres de recherche précédents, si la table est structurée, aucune des parties n'a besoin de valider toutes les valeurs de la table sous forme chiffrée.

Lasso utilise deux concepts structurels différents : la décomposabilité et la structure LDE. (LDE est l'acronyme d'un concept technique appelé polynôme étendu de faible degré.) La décomposabilité signifie en gros qu'il est possible de répondre à une seule recherche d'une table en effectuant un plus petit nombre de recherches sur une table plus petite. Il s'agit d'une exigence plus stricte que la structure LDE, mais Lasso est particulièrement efficace lorsqu'il est appliqué à des tables décomposables.

Choc

Jolt (Just One Lookup Table) est une nouvelle interface déverrouillée par la capacité de Lasso à utiliser d'énormes tables de recherche. Jolt cible l'abstraction machine virtuelle/CPU, également connue sous le nom d'architecture de jeu d'instructions (ISA). Les SNARK qui prennent en charge cette abstraction sont appelés zkVM. Par exemple, considérons le jeu d'instructions RISC-V (y compris l'extension de multiplication) que le projet RISC-Zero cible également. Il s'agit d'un ISA open source populaire développé par la communauté de l'architecture informatique sans penser aux SNARK.

Pour chaque instruction RISC-V fi, l'idée principale de Jolt est de créer une table de correspondance contenant la table d'évaluation complète de fi. Pour pratiquement toutes les instructions RISC-V, la table de correspondance résultante est décomposable et le lasso s'applique.

Revisiter la sagesse acceptée dans la conception de SNARK

Lasso et Jolt renversent également une partie de la sagesse acceptée dans la conception de SNARK.

** # 1. Les SNARK de grande surface sont un gaspillage. Tout le monde devrait utiliser FRI, Ligero, Brakedown ou des variantes, car ils évitent les techniques de courbes elliptiques qui sont généralement applicables aux grandes échelles. **

La taille du champ ici correspond à peu près à la taille des nombres apparaissant dans la preuve SNARK. Étant donné que l'addition et la multiplication de très grands nombres coûtent cher, l'idée que les SNARK sur de grands champs sont un gaspillage signifie que nous devrions nous efforcer de concevoir des protocoles qui n'ont jamais de grands nombres. Les engagements basés sur MSM utilisent des courbes elliptiques, qui sont généralement définies sur de grands champs (d'une taille d'environ 2 256), de sorte que ces promesses ont la réputation d'être peu performantes.

La pertinence d'utiliser de petits champs (même s'ils sont une option) dépend en grande partie de l'application. Lasso et Jolt vont encore plus loin. Ils montrent que même avec un schéma d'engagement basé sur MSM, le travail du démonstrateur peut être presque indépendant de la taille du champ. En effet, pour les engagements basés sur MSM, la taille des valeurs engagées est plus importante que la taille des champs dans lesquels ces valeurs résident.

Les SNARK existants obligent le prouveur à s'engager sur de nombreux éléments de champ aléatoires. Par exemple, le prouveur d'un backend SNARK populaire appelé Plonk engage environ 7 éléments de champ aléatoires (et d'autres éléments de champ non aléatoires) par porte de circuit. Ces éléments de champ aléatoires peuvent être grands même si toutes les valeurs qui apparaissent dans les calculs éprouvés sont petites.

En revanche, Lasso et Jolt exigent uniquement que le prouveur soumette une petite valeur (le prouveur de Lasso soumet également moins de valeurs que le paramètre de recherche précédent). Cela améliore considérablement les performances des schémas basés sur MSM. Au minimum, Lasso et Jolt devraient démanteler la notion selon laquelle la communauté devrait abandonner les engagements basés sur les MSM dans les cas où la performance du prouveur est importante.

** # 2 Un jeu d'instructions plus simple conduit à un zkVM plus rapide. **

La complexité de Jolt (par instruction) ne dépend que de la taille d'entrée de l'instruction, tant que la table d'évaluation de chaque instruction est décomposable. Jolt a démontré que des instructions étonnamment complexes sont décomposables, en particulier toutes les RISC-V.

Ceci est contraire à la croyance répandue selon laquelle des machines virtuelles plus simples (zkVM) conduisent nécessairement à des circuits plus petits et à des prouveurs plus rapides associés (à chaque étape de la VM). C'est la motivation qui sous-tend les zkVM particulièrement simples telles que la VM Cairo, qui sont spécifiquement conçues pour être compatibles avec SNARK.

En fait, pour les machines virtuelles plus simples, Jolt atteint un coût d'engagement inférieur pour le prouveur par rapport aux SNARK précédents. Par exemple, pour l'exécution de la machine virtuelle Cairo, le prouveur SNARK soumet 51 éléments de champ à chaque étape de la machine virtuelle. Les SNARK déployés par Cairo fonctionnent actuellement sur des champs de 251 bits (63 bits est la limite inférieure stricte de la taille de champ qu'un SNARK peut utiliser). Le prouveur de Jolt fonctionne sur environ 60 éléments de champ par étape (définissant plus de types de données 64 bits) pour les processeurs RISC-V. Après avoir pris en compte le fait que les éléments de champ soumis sont petits, le coût du prouveur Jolt est à peu près équivalent au coût de soumission de 6 éléments de champ aléatoires de 256 bits.

** # 3 Il n'y a aucune pénalité de performance pour diviser de gros calculs en petits morceaux. **

Sur la base de ce point de vue, les projets actuels décomposent tout grand circuit en petits blocs, prouvent chaque bloc séparément et agrègent de manière récursive les résultats via des SNARK. Ces déploiements utilisent cette approche pour atténuer les goulots d'étranglement des performances dans les SNARK populaires. Par exemple, les SNARK basés sur FRI nécessitent près de 100 Go d'espace de preuve, même pour les petits circuits. Ils nécessitent également la FFT, une opération ultra-linéaire qui peut devenir un goulot d'étranglement si les SNARK sont appliqués "simultanément" à de grands circuits.

La réalité est que certains SNARK (tels que Lasso et Jolt) présentent des économies d'échelle (plutôt que les déséconomies d'échelle trouvées dans les SNARK actuellement déployés). Cela signifie que plus la déclaration en cours de preuve est grande, plus la surcharge du prouveur par rapport à la vérification directe des témoins (c'est-à-dire le travail requis pour évaluer un circuit témoin sans garantir l'exactitude) est faible. Sur le plan technique, les économies d'échelle proviennent de deux endroits.

Accélération de Pippenger pour les MSM de taille n : amélioration du facteur log(n) par rapport à l'algorithme naïf. Plus n est grand, plus l'amélioration est importante.

Dans les paramètres de recherche tels que Lasso, le prouveur paie un coût "unique" qui dépend de la taille de la table de recherche mais n'a rien à voir avec le nombre de valeurs recherchées. Le coût ponctuel du prouveur est amorti sur toutes les recherches dans la table. Des blocs plus gros signifient plus de recherches, ce qui signifie un meilleur amortissement.

La façon populaire de traiter les grands circuits aujourd'hui est de décomposer les choses en morceaux les plus petits possibles. La principale contrainte sur la taille de chaque partie est qu'elles ne peuvent pas être si petites que la preuve d'agrégation récursive devienne un goulot d'étranglement pour le prouveur.

Lasso et Jolt proposent une approche essentiellement opposée. Les gens devraient utiliser des SNARK qui ont des économies d'échelle. Ensuite, décomposez le gros calcul en morceaux aussi gros que possible et répétez sur les résultats. La principale limitation de la taille de chaque fragment est l'espace de preuve, qui s'agrandit à mesure que le fragment s'agrandit.

**#4 Les contraintes de hauteur sont nécessaires pour des SNARK efficaces. **

Jolt utilise R 1 CS comme représentation intermédiaire. Il n'y a aucun avantage à utiliser des contraintes de hauteur ou personnalisées dans Jolt. La majeure partie du coût du prouveur dans Jolt réside dans la recherche du paramètre Lasso, plutôt que dans la preuve de la satisfaisabilité du système de contraintes résultant qui prend la recherche pour acquise.

Jolt est universel, il ne perd donc pas sa polyvalence. En tant que tel, il contrecarre l'attention intense des développeurs sur les contraintes de hauteur de conception (souvent spécifiées manuellement) dans le but d'améliorer les performances des SNARK populaires d'aujourd'hui.

Bien sûr, certains contextes peuvent toujours bénéficier de contraintes de hauteur ou personnalisées. Un exemple important est le Minroot VDF, dont la contrainte de 5 degrés peut réduire le coût d'engagement d'un facteur d'environ 3.

** # 5 Les schémas d'engagement polynomiaux clairsemés sont coûteux et doivent être évités autant que possible. **

C'est la principale critique contre le système de retenue récemment introduit appelé CCS et les SNARK qui le soutiennent - Spartan et Marlin, CCS est une généralisation claire de tous les systèmes de retenue répandus dans la pratique aujourd'hui.

Cette critique n'est pas fondée. En fait, le noyau technique de Lasso et Jolt est le schéma d'engagement polynomial clairsemé de Spartan - Spark. Spark lui-même est une conversion générique de tout schéma d'engagement polynomial (non clairsemé) en un schéma qui prend en charge les polynômes clairsemés.

Lasso optimise et étend Spark pour s'assurer que le prouveur ne s'engage que sur de "petites" valeurs, mais même sans ces optimisations, la critique n'est pas justifiée. En fait, le prouveur de Spartan s'engage sur moins d'éléments de champ (aléatoires) que les SNARK (comme Plonk qui évite les engagements polynomiaux clairsemés).

L'approche de Spartan présente des avantages supplémentaires en termes de performances, en particulier pour les circuits à structures répétitives. Pour ces circuits, les portes d'addition n'ajoutent rien au travail cryptographique du prouveur spartiate. Ce travail n'augmente qu'avec le nombre de variables dans un système de contraintes donné, pas avec le nombre de contraintes. Contrairement à Plonk, les démonstrateurs spartiates n'ont pas besoin de soumettre plusieurs "copies" différentes de la même variable.

Nous sommes optimistes que Lasso et Jolt changeront radicalement la façon dont les SNARK sont conçus, améliorant les performances et l'auditabilité. Il s'agit d'un outil clé avec la capacité étonnante de minimiser le coût d'engagement du prouveur.