Les preuves à divulgation nulle de connaissance (ZKP) deviennent de plus en plus importantes pour les systèmes décentralisés. ZK s’est d’abord fait connaître du public pour son succès dans des projets tels que ZCash, mais aujourd’hui, ZK est connu comme une solution de mise à l’échelle pour Ethereum.
En s’appuyant sur ZK, la couche 2 (par exemple, Scroll et Polygon), également connue sous le nom de Rollups, développe des zkEVM (zk Ethereum Virtual Machine). Ces zkEVM traitent un lot de transactions et génèrent une petite preuve (en kilo-octets). Cette attestation peut être utilisée pour vérifier à l’ensemble du réseau que le lot de transactions est valide et correct.
Cependant, leurs utilisations ne s’arrêtent pas là. ZK permet une variété d’applications intéressantes.
Couche privée 1 – Mina, par exemple, cache les détails des transactions et des données sur sa blockchain, ce qui permet aux utilisateurs de prouver uniquement la validité de leurs transactions sans révéler les détails de la transaction elle-même. neptune.cash et Aleo sont également des projets très intéressants.
Plate-forme cloud décentralisée - FedML et together.xyz permettent d’entraîner des modèles d’apprentissage automatique (ML) de manière décentralisée, d’externaliser les calculs sur le réseau et de vérifier l’exactitude des calculs à l’aide de ZKP. Druglike est en train de construire une plate-forme de découverte de médicaments plus ouverte en utilisant des technologies similaires.
Stockage décentralisé - Filecoin révolutionne le stockage en nuage, et ZK est au cœur de celui-ci, permettant aux fournisseurs de stockage de prouver qu’ils ont stocké les bonnes données sur une période de temps.
JEU - Une version plus avancée de Darkforest peut apparaître, ce qui nécessite une preuve en temps réel. ZK peut également étendre le jeu pour réduire la probabilité de tricherie. Peut-être aussi travailler avec une plateforme cloud décentralisée pour permettre au jeu de payer son propre hébergement !
Identité - L’authentification décentralisée est désormais également possible via ZK. Autour de cette idée, un certain nombre de projets intéressants sont en cours de construction. Par exemple, notebook et zkemail (recommandé pour en savoir plus).
L’impact de ZK et des systèmes décentralisés est énorme, cependant, le développement de l’histoire n’est pas parfait, et il y a encore beaucoup d’obstacles et de défis aujourd’hui. Le processus d’inclusion de preuves est très gourmand en ressources et nécessite de nombreuses opérations mathématiques complexes. Alors que les développeurs cherchent à créer des protocoles et des systèmes plus ambitieux et plus complexes à l’aide de la technologie ZK, à la fois pour la génération de preuves et les processus de vérification, les développeurs exigent des tailles de preuve plus petites, des performances plus rapides et de meilleures optimisations.
Dans cet article, nous allons explorer l’état actuel de l’accélération matérielle et comment elle jouera un rôle clé dans l’avancement de l’adoption de ZK.
Snark contre Stark
Il existe aujourd’hui deux techniques populaires à connaissance nulle, zk-STARK et zk-SNARK (nous avons ignoré les pare-balles dans cet article).
| | | |
| --- | --- | --- |
| zk-STARK | zk-SNARK | |
| Complexité - Étalon | O(N * poly-log(N)) | O(N * log(N)) |
| Complexité - Vérificateur | O(poly-log(N)) | O(1) |
| Taille épreuve numatique | 45 Ko à 200 Ko | ~ 288 octets |
| 抗量子 | Oui (basé sur une fonction de hachage) | Non |
| Configuration approuvée | Non | Oui |
| Zero-knowledge | Oui | Oui |
| Interactivité | Interactif ou non interactif | Non interactif |
| Documentation pour les développeurs | Limitée, mais en pleine expansion Bon |
表1 :Snark VS Stark
Comme mentionné ci-dessus, il existe des différences et des compromis entre les deux. Le point le plus important est que la configuration fiable d’un système basé sur zk-SNARK repose sur au moins un participant honnête impliqué dans le processus de configuration de confiance et sur la destruction de ses clés à la fin du processus. En termes de vérification on-chain, les zk-SNARK sont beaucoup moins chers en termes de frais de gaz. De plus, les preuves des zk-SNARK sont également beaucoup plus petites, ce qui les rend moins chères à stocker sur la chaîne.
Actuellement, les zk-SNARK sont plus populaires que les zk-STARK. La raison la plus probable est que les zk-SNARK ont une histoire beaucoup plus longue. Une autre raison possible est que Zcash, l’une des premières blockchains ZK, utilisait des zk-SNARKs, de sorte que la plupart des outils de développement et de la documentation actuels tournent autour de l’écosystème zk-SNARK.
Comment créer une application ZK
Les développeurs peuvent avoir besoin de deux composants pour terminer le développement d’une application ZK
Une méthode de calcul d’expression conviviale pour ZK (DSL ou bibliothèque de bas niveau).
Un système d’attestation qui implémente deux fonctions : Prouver et Vérifier.
DSL (langage spécifique à un domaine) et bibliothèques de bas niveau
En ce qui concerne les DSL, il existe de nombreuses options, telles que Circom, Halo2, Noir et bien d’autres. Circom est probablement le plus populaire en ce moment.
En ce qui concerne les bibliothèques de bas niveau, un exemple populaire est Arkworks ; Il existe également des bibliothèques en cours de développement, telles que ICICLE, qui est une bibliothèque d’accélération CUDA.
Ces DSL sont conçus pour produire des systèmes confinés. Contrairement au programme habituel, qui est généralement évalué sous la forme x := y *z, le même programme sous la forme contrainte ressemble plus à x-y * z = 0. En représentant le programme comme un système de contraintes, nous constatons que des opérations telles que l’addition ou la multiplication peuvent être représentées par une seule contrainte. Cependant, les opérations plus complexes, telles que les opérations sur les bits, peuvent nécessiter des centaines de contraintes !
En conséquence, il devient compliqué d’implémenter certaines fonctions de hachage en tant que programmes compatibles avec ZK. Dans les preuves à divulgation nulle de connaissance, les fonctions de hachage sont souvent utilisées pour assurer l’intégrité des données et/ou pour vérifier des propriétés spécifiques des données, mais en raison du grand nombre de contraintes liées aux opérations sur les bits, certaines fonctions de hachage sont difficiles à adapter à l’environnement des preuves à divulgation nulle de connaissance. Cette complexité peut affecter l’efficacité de la génération et de la vérification des preuves, et donc devenir un problème que les développeurs doivent prendre en compte et résoudre lors de la création d’applications basées sur ZK
En conséquence, il devient compliqué d’implémenter certaines fonctions de hachage pour qu’elles soient compatibles avec ZK.
Prouvant
Un système de preuves peut être comparé à un logiciel qui accomplit deux tâches principales : générer des preuves et vérifier des preuves. Les systèmes de preuve acceptent généralement les circuits, les preuves et les paramètres publics/privés en entrée.
Les deux systèmes d’épreuve les plus populaires sont les séries Groth16 et PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | |
| --- | --- | --- | --- | --- | --- |
| | Configuration sécurisée | Taille de l’épreuve | Complexité de l’étalon | Complexité du vérificateur | Flexibilité |
| Par Groth16 | Spécifique au circuit | petit | Faible | Faible | Faible |
| Plonk | Universel | Grand | Élevé | 常数 | Élevé |
表2 :Groth16 contre Plonk
Comme le montre le tableau 2, Groth16 nécessite un processus de configuration fiable, mais Groth16 nous fournit des temps de preuve et de vérification plus rapides, ainsi qu’une taille d’épreuve constante.
Plonk fournit une configuration générique qui effectue une phase de prétraitement pour le circuit que vous exécutez chaque fois qu’une preuve est générée. Bien qu’il prenne en charge de nombreux circuits, le temps de vérification de Plonk est constant.
Il existe également des différences entre les deux en termes de contraintes. Groth16 croît de manière linéaire en termes de taille de contrainte et manque de flexibilité, tandis que Plonk est plus flexible.
Dans l’ensemble, comprenez que les performances sont directement liées au nombre de contraintes dans votre application ZK. Plus il y a de contraintes, plus l’étalon doit calculer d’opérations.
goulot
Le système de preuve se compose de deux opérations mathématiques principales : la multiplication multiscalaire (MSM) et la transformée de Fourier rapide (FFT). Aujourd’hui, nous allons explorer les systèmes où les deux existent, où MSM peut occuper environ 60 % du temps d’exécution, tandis que FFT peut occuper environ 30 %.
MSM nécessite beaucoup d’accès à la mémoire, ce qui, dans la plupart des cas, consomme beaucoup de mémoire sur la machine, tout en effectuant de nombreuses opérations de multiplication scalaire.
Les algorithmes FFT nécessitent souvent de réorganiser les données d’entrée dans un ordre spécifique pour effectuer des transformations. Cela peut nécessiter beaucoup de déplacement de données et peut constituer un goulot d’étranglement, en particulier pour les entrées de grande taille. L’utilisation du cache peut également être un problème si les modèles d’accès à la mémoire ne rentrent pas dans la hiérarchie du cache.
**Dans ce cas, l’accélération matérielle est le seul moyen d’optimiser pleinement les performances de ZKP. **
Accélération matérielle
En ce qui concerne l’accélération matérielle, cela nous rappelle à quel point les ASIC et les GPU ont dominé le minage de Bitcoin et d’Ethereum.
Bien que les optimisations logicielles soient tout aussi importantes et précieuses, elles ont leurs limites. L’optimisation matérielle, quant à elle, peut améliorer le parallélisme en concevant des FPGA avec plusieurs unités de traitement, telles que la réduction de la synchronisation ou de la vectorisation des threads. L’accès à la mémoire peut également être optimisé plus efficacement en améliorant les hiérarchies de mémoire et les modèles d’accès.
Aujourd’hui, dans l’espace ZKP, la tendance principale semble s’être déplacée : les GPU et les FPGA.
À court terme, les GPU ont un avantage en termes de prix, en particulier après le passage de l’ETH à la preuve d’enjeu (POS), laissant un grand nombre de mineurs de GPU inactifs et en veille. De plus, les GPU ont l’avantage d’avoir des cycles de développement courts et offrent aux développeurs beaucoup de parallélisme « plug-and-play ».
Cependant, les FPGA devraient rattraper leur retard, en particulier lorsqu’ils comparent les facteurs de forme et la consommation d’énergie. Les FPGA offrent également une latence plus faible pour les flux de données à haut débit. Lorsque plusieurs FPGA sont regroupés, ils offrent de meilleures performances que les clusters GPU.
GPU VS FPGA
GPU:
Temps de développement : les GPU offrent un temps de développement rapide. La documentation destinée aux développeurs pour des frameworks tels que CUDA et OpenCL est bien développée et populaire.
Consommation d’énergie : les GPU sont très « gourmands en énergie ». Même lorsque les développeurs tirent parti du parallélisme au niveau des données et du parallélisme au niveau des threads, les GPU consomment toujours beaucoup d’énergie.
Disponibilité : Les GPU grand public sont bon marché et facilement disponibles dès maintenant.
FPGA :
Cycle de développement : Les FPGA ont un cycle de développement plus complexe et nécessitent des ingénieurs plus spécialisés. Les FPGA permettent aux ingénieurs de réaliser de nombreuses optimisations de « bas niveau » que les GPU ne peuvent pas réaliser.
Latence : les FPGA offrent une latence plus faible, en particulier lors du traitement de flux de données volumineux.
Coût par rapport à la disponibilité : les FPGA sont plus chers que les GPU et ne sont pas aussi facilement disponibles que les GPU.
ZPRIZE
De nos jours, lorsqu’il s’agit du goulot d’étranglement de l’optimisation matérielle et du ZKP, il existe une concurrence qui ne peut être évitée - ZPRIZE
ZPrize est l’une des initiatives les plus importantes dans le domaine de la ZK à l’heure actuelle. ZPrize est une compétition qui encourage les équipes à développer une accélération matérielle pour les principaux goulots d’étranglement de ZKP (par exemple, MSM, NTT, Poseidon, etc.) sur plusieurs plates-formes (par exemple, FPGA, GPU, appareils mobiles et navigateurs) en fonction de la latence, du débit et de l’efficacité.
Le résultat a été très intéressant. Par exemple, les améliorations apportées au GPU sont énormes :
MSM à 2^26 a augmenté de 131 %, passant de 5,86 secondes à 2,52 secondes. D’autre part, les solutions FPGA ont tendance à ne pas avoir de benchmarks par rapport aux résultats GPU, qui ont des benchmarks précédents à comparer, et la plupart des solutions FPGA sont open-source pour la première fois avec de tels algorithmes qui devraient s’améliorer à l’avenir.
Ces résultats indiquent la direction dans laquelle la plupart des développeurs se sentent à l’aise dans le développement de leurs solutions d’accélération matérielle. De nombreuses équipes concourent pour la catégorie GPU, mais seul un petit pourcentage concourt pour la catégorie FPGA. Je ne sais pas si c’est à cause d’un manque d’expérience dans le développement pour les FPGA, ou si la plupart des sociétés/équipes FPGA choisissent de développer secrètement pour vendre leurs solutions commercialement.
ZPrize a fourni des recherches très intéressantes à la communauté. Au fur et à mesure que d’autres tours de ZPrize commencent, nous verrons de plus en plus de solutions et de problèmes intéressants apparaître.
Exemples pratiques d’accélération matérielle
Si l’on prend l’exemple de Groth16, si l’on examine l’implémentation de rapidsnark pour Groth16, on peut observer que deux opérations principales sont effectuées : la FFT (Fast Fourier Transform) et la MSM (Multiscalar Multiplication) ; Ces deux opérations de base sont courantes dans de nombreux systèmes de preuve. Leur temps d’exécution est directement lié au nombre de contraintes dans le circuit. Naturellement, le nombre de contraintes augmente au fur et à mesure que des circuits plus complexes sont écrits.
Pour avoir une idée de l’intensité des opérations FFT et MSM en termes de calcul, nous pouvons consulter le benchmark d’Ingonyama sur le circuit Groth16 (le processus Vanilla C2 de Filecoin effectué sur un secteur de 32 Go), et les résultats sont les suivants
Comme le montre la figure ci-dessus, le MSM (Multiscalar Multiplication) peut prendre beaucoup de temps et constituer un sérieux goulot d’étranglement des performances pour de nombreux prouveurs, ce qui fait du MSM l’un des opérateurs cryptographiques les plus importants qui doivent être accélérés.
Alors, quelle quantité de calcul le MSM occupe-t-il pour le prouveur dans d’autres systèmes de preuve ZK ? C’est ce que montre la figure ci-dessous
À Plonk, le MSM représente plus de 85 % des frais généraux, comme le montre le dernier article d’Ingonyama, Pipe MSM. **
Alors, comment l’accélération matérielle devrait-elle accélérer le MSM ? **
MSM
Avant de parler de la façon d’accélérer le HSH, nous devons comprendre ce qu’est le MSM
La multiplication multiscalaire (MSM) est un algorithme permettant de calculer la somme de plusieurs multiplications scalaires sous la forme suivante
où G est un point dans le groupe de courbes elliptiques, a est un scalaire, et le résultat de MSM sera également un point de courbe elliptique
Nous pouvons décomposer le MSM en deux sous-composantes principales :
Multiplication modulaire
Ajouts de points de courbe elliptique
Prenons l’exemple d’Affine(x,y) pour effectuer une opération P+Q naïve.
Lorsque nous voulons calculer P + Q = R, nous devons calculer une valeur k, par l’abscisse de k et P,Q
Obtenir les coordonnées de R. Le processus de calcul est le suivant ci-dessus, dans ce processus, nous effectuons 2 fois la multiplication, 1 opération au carré, 1 opération inverse, et plusieurs fois des opérations d’addition et de soustraction. Il est intéressant de noter que les opérations ci-dessus sont effectuées dans un corps fini, c’est-à-dire sous mod P. En réalité, P sera très grand. **
Le coût de l’opération ci-dessus est de trouver l’inverse >> la multiplication** **> **** au carré, et le coût de l’addition et de la soustraction est négligeable.
Nous voulons donc éviter autant que possible les inverses, car le coût d’une seule inversion est au moins cent fois supérieur à celui de la multiplication. Nous pouvons le faire en développant le système de coordonnées, mais au prix d’une augmentation du nombre de multiplications dans le processus, telles que les coordonnées jacobiennes : XYZ += XYZ, et en multipliant plus de 10 fois, selon l’algorithme d’addition. **
GPU VS FPGA Accelerated MSM
Cette section compare deux implémentations MSM de premier plan, PipeMSM et Sppark, où PipeMSM est implémenté sur les FPGA et Sppark est implémenté sur les GPU.
Sppark et PipeMSM utilisent l’algorithme de pointe de Pippenger pour implémenter MSM, également connu sous le nom d’algorithme de compartiment ; **
Sppark est implémenté à l’aide de CUDA ; Leurs versions sont hautement parallélisées et ont obtenu des résultats impressionnants lorsqu’elles sont exécutées sur les derniers GPU.
Cependant, PipeMSM ne se contente pas d’optimiser l’algorithme, mais fournit également des optimisations pour les primitives mathématiques de la multiplication modulaire et de l’addition EC. PipeMSM gère l’ensemble de la « pile MSM », en mettant en œuvre une série d’astuces mathématiques et d’optimisations visant à rendre MSM plus adapté au matériel, et en concevant une conception matérielle conçue pour réduire la latence en mettant l’accent sur la parallélisation.
Faisons un bref récapitulatif de l’implémentation de PipeMSM.
Faible latence
PipeMSM est conçu pour fournir une faible latence lors de l’exécution de plusieurs MSM sur un grand nombre d’entrées. Les GPU n’offrent pas de faible latence déterministe en raison de la mise à l’échelle dynamique de la fréquence, et les GPU ajustent leurs vitesses d’horloge en fonction des charges de travail.
Mais grâce à la conception matérielle optimisée, les implémentations FPGA peuvent fournir des performances déterministes et une latence pour des charges de travail spécifiques.
Mise en œuvre de l’addition EC
L’addition de points de courbe elliptique (EC Addition) est implémentée sous la forme d’une formule à faible latence, hautement parallèle et complète (complète signifie qu’elle calcule correctement la somme de deux points quelconques dans le groupe de courbes elliptiques). L’addition de points de courbe elliptique est utilisée de manière canalisée dans le module d’addition EC pour réduire la latence.
Nous avons choisi de représenter les coordonnées sous forme de coordonnées projectives, et sur l’algorithme d’addition, nous utilisons une formule d’addition de points de courbe elliptique complète. Le principal avantage est que nous n’avons pas à nous occuper de cas limites. Formules complètes ;
Nous avons implémenté cette formule d’addition de manière pipeline et parallèle, et notre circuit d’additionneur de courbe elliptique FPGA n’a eu besoin que de 12 multiplications, 17 sommes d’additions, et cette formule a été exécutée. La formule originale nécessite 15 multiplications modulo et 13 additions. La conception du FPGA est la suivante
Multi mod
Nous avons utilisé les algorithmes de réduction de Barrett et de Karatsuba.
La réduction de Barrett est un algorithme qui calcule efficacement r≡ab mod p (où p est fixe). Barrett Reduction tente de remplacer la division (une opération coûteuse) par une division approximative. Une tolérance d’erreur peut être sélectionnée pour décrire la plage dans laquelle nous recherchons le résultat correct. Nous constatons que la grande tolérance d’erreur permet d’utiliser des constantes de réduction plus petites ; Cela réduit la taille des valeurs intermédiaires utilisées dans les opérations de réduction modulo, ce qui réduit le nombre de multiplications nécessaires pour calculer le résultat final.
Dans l’encadré bleu ci-dessous, nous pouvons voir qu’en raison de notre tolérance élevée aux erreurs, nous devons effectuer plusieurs vérifications pour trouver un résultat précis.
En un mot, l’algorithme de Karatsuba est utilisé pour optimiser la multiplication que nous effectuons dans la réduction de Barrett. L’algorithme de Karatsuba simplifie la multiplication de deux n chiffres à la multiplication de trois n/2 chiffres ; Ces multiplications peuvent simplifier le nombre de chiffres pour qu’il soit suffisamment étroit pour être directement calculé par le matériel. Les détails peuvent être lus dans l’article d’Ingo : Pipe MSM
À l’aide des opérateurs ci-dessus, nous avons développé une implémentation MSM hautement parallèle et à faible latence.
L’idée de base est qu’au lieu de calculer l’ensemble du MSM en une seule fois, chaque morceau est passé dans l’additionneur EC en parallèle. Les résultats de l’additionneur EC sont accumulés dans le MSM final.
Résultat final****
Le diagramme ci-dessus montre la comparaison entre Sppark et PipeMSM.
Le plus important est l’importante économie d’énergie offerte par les FPGA, qui pourrait être extrêmement importante pour les futures opérations de production de preuves à grande échelle. Il convient de noter que notre implémentation a été prototypée et évaluée sous @125MHz, et que l’augmentation de la vitesse d’horloge à @500MHz pourrait augmenter le temps de calcul de 4 fois ou plus.
Un autre avantage de l’utilisation de nos FPGA est qu’ils peuvent être installés dans des serveurs à châssis restreint car ils consomment moins d’énergie et génèrent moins de chaleur.
Nous n’en sommes qu’aux premiers stades de l’ingénierie FPGA pour ZKP et nous devons nous attendre à de nouvelles améliorations dans les algorithmes. De plus, le FPGA calcule le MSM lorsque le CPU est inactif, et il peut être possible d’obtenir des temps plus rapides en utilisant le FPGA en combinaison avec les ressources système (CPU/GPU).
Résumé
Le ZKP est devenu une technologie clé pour les systèmes distribués.
L’application de ZKP ira bien au-delà de la simple extension du niveau Ethereum, permettant l’externalisation du calcul à des tiers non fiables, permettant le développement de systèmes auparavant impossibles, tels que le cloud computing distribué, les systèmes d’identité, etc.
Traditionnellement, les optimisations ZKP se sont concentrées sur les améliorations au niveau logiciel, mais à mesure que la demande de performances supérieures augmente, nous verrons des solutions d’accélération plus avancées impliquant à la fois le matériel et le logiciel.
À l’heure actuelle, les solutions d’accélération que nous voyons utilisent principalement des GPU, car le temps de développement à l’aide de CUDA est court et les GPU grand public actuels sont très bon marché et abondants. Le GPU offre également des performances incroyables. Il est donc peu probable que les GPU disparaissent de cet espace de sitôt.
Au fur et à mesure que des équipes de développement plus complexes entrent dans l’espace, il est probable que nous verrons les FPGA ouvrir la voie en termes d’efficacité énergétique et de performances. Par rapport aux GPU, les FPGA offrent plus de personnalisation de bas niveau ainsi que plus d’options de configuration. Les FPGA offrent une vitesse de développement et une flexibilité plus rapides que les ASIC. Avec le développement rapide du monde ZKP, les FPGA peuvent être reflashés avec différents programmes pour s’adapter à différents systèmes et mettre à jour les solutions.
Cependant, pour générer des preuves en temps quasi réel, il peut être nécessaire de combiner des configurations GPU/FPGA/ASIC en fonction du système pour lequel nous générons des preuves.
Le ZPU est également susceptible d’évoluer pour fournir des solutions extrêmement efficaces pour les générateurs d’épreuve à grande échelle et les appareils de faible puissance (voir l’article précédent pour plus de détails).
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
Une nouvelle ère de ZK portée par l’accélération matérielle
Histoire jusqu’à présent
Les preuves à divulgation nulle de connaissance (ZKP) deviennent de plus en plus importantes pour les systèmes décentralisés. ZK s’est d’abord fait connaître du public pour son succès dans des projets tels que ZCash, mais aujourd’hui, ZK est connu comme une solution de mise à l’échelle pour Ethereum.
En s’appuyant sur ZK, la couche 2 (par exemple, Scroll et Polygon), également connue sous le nom de Rollups, développe des zkEVM (zk Ethereum Virtual Machine). Ces zkEVM traitent un lot de transactions et génèrent une petite preuve (en kilo-octets). Cette attestation peut être utilisée pour vérifier à l’ensemble du réseau que le lot de transactions est valide et correct.
Cependant, leurs utilisations ne s’arrêtent pas là. ZK permet une variété d’applications intéressantes.
Couche privée 1 – Mina, par exemple, cache les détails des transactions et des données sur sa blockchain, ce qui permet aux utilisateurs de prouver uniquement la validité de leurs transactions sans révéler les détails de la transaction elle-même. neptune.cash et Aleo sont également des projets très intéressants.
Plate-forme cloud décentralisée - FedML et together.xyz permettent d’entraîner des modèles d’apprentissage automatique (ML) de manière décentralisée, d’externaliser les calculs sur le réseau et de vérifier l’exactitude des calculs à l’aide de ZKP. Druglike est en train de construire une plate-forme de découverte de médicaments plus ouverte en utilisant des technologies similaires.
Stockage décentralisé - Filecoin révolutionne le stockage en nuage, et ZK est au cœur de celui-ci, permettant aux fournisseurs de stockage de prouver qu’ils ont stocké les bonnes données sur une période de temps.
JEU - Une version plus avancée de Darkforest peut apparaître, ce qui nécessite une preuve en temps réel. ZK peut également étendre le jeu pour réduire la probabilité de tricherie. Peut-être aussi travailler avec une plateforme cloud décentralisée pour permettre au jeu de payer son propre hébergement !
Identité - L’authentification décentralisée est désormais également possible via ZK. Autour de cette idée, un certain nombre de projets intéressants sont en cours de construction. Par exemple, notebook et zkemail (recommandé pour en savoir plus).
L’impact de ZK et des systèmes décentralisés est énorme, cependant, le développement de l’histoire n’est pas parfait, et il y a encore beaucoup d’obstacles et de défis aujourd’hui. Le processus d’inclusion de preuves est très gourmand en ressources et nécessite de nombreuses opérations mathématiques complexes. Alors que les développeurs cherchent à créer des protocoles et des systèmes plus ambitieux et plus complexes à l’aide de la technologie ZK, à la fois pour la génération de preuves et les processus de vérification, les développeurs exigent des tailles de preuve plus petites, des performances plus rapides et de meilleures optimisations.
Dans cet article, nous allons explorer l’état actuel de l’accélération matérielle et comment elle jouera un rôle clé dans l’avancement de l’adoption de ZK.
Snark contre Stark
Il existe aujourd’hui deux techniques populaires à connaissance nulle, zk-STARK et zk-SNARK (nous avons ignoré les pare-balles dans cet article).
| | | | | --- | --- | --- | | zk-STARK | zk-SNARK | | | Complexité - Étalon | O(N * poly-log(N)) | O(N * log(N)) | | Complexité - Vérificateur | O(poly-log(N)) | O(1) | | Taille épreuve numatique | 45 Ko à 200 Ko | ~ 288 octets | | 抗量子 | Oui (basé sur une fonction de hachage) | Non | | Configuration approuvée | Non | Oui | | Zero-knowledge | Oui | Oui | | Interactivité | Interactif ou non interactif | Non interactif | | Documentation pour les développeurs | Limitée, mais en pleine expansion Bon |
表1 :Snark VS Stark
Comme mentionné ci-dessus, il existe des différences et des compromis entre les deux. Le point le plus important est que la configuration fiable d’un système basé sur zk-SNARK repose sur au moins un participant honnête impliqué dans le processus de configuration de confiance et sur la destruction de ses clés à la fin du processus. En termes de vérification on-chain, les zk-SNARK sont beaucoup moins chers en termes de frais de gaz. De plus, les preuves des zk-SNARK sont également beaucoup plus petites, ce qui les rend moins chères à stocker sur la chaîne.
Actuellement, les zk-SNARK sont plus populaires que les zk-STARK. La raison la plus probable est que les zk-SNARK ont une histoire beaucoup plus longue. Une autre raison possible est que Zcash, l’une des premières blockchains ZK, utilisait des zk-SNARKs, de sorte que la plupart des outils de développement et de la documentation actuels tournent autour de l’écosystème zk-SNARK.
Comment créer une application ZK
Les développeurs peuvent avoir besoin de deux composants pour terminer le développement d’une application ZK
Une méthode de calcul d’expression conviviale pour ZK (DSL ou bibliothèque de bas niveau).
Un système d’attestation qui implémente deux fonctions : Prouver et Vérifier.
DSL (langage spécifique à un domaine) et bibliothèques de bas niveau
En ce qui concerne les DSL, il existe de nombreuses options, telles que Circom, Halo2, Noir et bien d’autres. Circom est probablement le plus populaire en ce moment.
En ce qui concerne les bibliothèques de bas niveau, un exemple populaire est Arkworks ; Il existe également des bibliothèques en cours de développement, telles que ICICLE, qui est une bibliothèque d’accélération CUDA.
Ces DSL sont conçus pour produire des systèmes confinés. Contrairement au programme habituel, qui est généralement évalué sous la forme x := y *z, le même programme sous la forme contrainte ressemble plus à x-y * z = 0. En représentant le programme comme un système de contraintes, nous constatons que des opérations telles que l’addition ou la multiplication peuvent être représentées par une seule contrainte. Cependant, les opérations plus complexes, telles que les opérations sur les bits, peuvent nécessiter des centaines de contraintes !
En conséquence, il devient compliqué d’implémenter certaines fonctions de hachage en tant que programmes compatibles avec ZK. Dans les preuves à divulgation nulle de connaissance, les fonctions de hachage sont souvent utilisées pour assurer l’intégrité des données et/ou pour vérifier des propriétés spécifiques des données, mais en raison du grand nombre de contraintes liées aux opérations sur les bits, certaines fonctions de hachage sont difficiles à adapter à l’environnement des preuves à divulgation nulle de connaissance. Cette complexité peut affecter l’efficacité de la génération et de la vérification des preuves, et donc devenir un problème que les développeurs doivent prendre en compte et résoudre lors de la création d’applications basées sur ZK
En conséquence, il devient compliqué d’implémenter certaines fonctions de hachage pour qu’elles soient compatibles avec ZK.
Prouvant
Un système de preuves peut être comparé à un logiciel qui accomplit deux tâches principales : générer des preuves et vérifier des preuves. Les systèmes de preuve acceptent généralement les circuits, les preuves et les paramètres publics/privés en entrée.
Les deux systèmes d’épreuve les plus populaires sont les séries Groth16 et PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | | | --- | --- | --- | --- | --- | --- | | | Configuration sécurisée | Taille de l’épreuve | Complexité de l’étalon | Complexité du vérificateur | Flexibilité | | Par Groth16 | Spécifique au circuit | petit | Faible | Faible | Faible | | Plonk | Universel | Grand | Élevé | 常数 | Élevé |
表2 :Groth16 contre Plonk
Comme le montre le tableau 2, Groth16 nécessite un processus de configuration fiable, mais Groth16 nous fournit des temps de preuve et de vérification plus rapides, ainsi qu’une taille d’épreuve constante.
Plonk fournit une configuration générique qui effectue une phase de prétraitement pour le circuit que vous exécutez chaque fois qu’une preuve est générée. Bien qu’il prenne en charge de nombreux circuits, le temps de vérification de Plonk est constant.
Il existe également des différences entre les deux en termes de contraintes. Groth16 croît de manière linéaire en termes de taille de contrainte et manque de flexibilité, tandis que Plonk est plus flexible.
Dans l’ensemble, comprenez que les performances sont directement liées au nombre de contraintes dans votre application ZK. Plus il y a de contraintes, plus l’étalon doit calculer d’opérations.
goulot
Le système de preuve se compose de deux opérations mathématiques principales : la multiplication multiscalaire (MSM) et la transformée de Fourier rapide (FFT). Aujourd’hui, nous allons explorer les systèmes où les deux existent, où MSM peut occuper environ 60 % du temps d’exécution, tandis que FFT peut occuper environ 30 %.
MSM nécessite beaucoup d’accès à la mémoire, ce qui, dans la plupart des cas, consomme beaucoup de mémoire sur la machine, tout en effectuant de nombreuses opérations de multiplication scalaire.
Les algorithmes FFT nécessitent souvent de réorganiser les données d’entrée dans un ordre spécifique pour effectuer des transformations. Cela peut nécessiter beaucoup de déplacement de données et peut constituer un goulot d’étranglement, en particulier pour les entrées de grande taille. L’utilisation du cache peut également être un problème si les modèles d’accès à la mémoire ne rentrent pas dans la hiérarchie du cache.
**Dans ce cas, l’accélération matérielle est le seul moyen d’optimiser pleinement les performances de ZKP. **
Accélération matérielle
En ce qui concerne l’accélération matérielle, cela nous rappelle à quel point les ASIC et les GPU ont dominé le minage de Bitcoin et d’Ethereum.
Bien que les optimisations logicielles soient tout aussi importantes et précieuses, elles ont leurs limites. L’optimisation matérielle, quant à elle, peut améliorer le parallélisme en concevant des FPGA avec plusieurs unités de traitement, telles que la réduction de la synchronisation ou de la vectorisation des threads. L’accès à la mémoire peut également être optimisé plus efficacement en améliorant les hiérarchies de mémoire et les modèles d’accès.
Aujourd’hui, dans l’espace ZKP, la tendance principale semble s’être déplacée : les GPU et les FPGA.
À court terme, les GPU ont un avantage en termes de prix, en particulier après le passage de l’ETH à la preuve d’enjeu (POS), laissant un grand nombre de mineurs de GPU inactifs et en veille. De plus, les GPU ont l’avantage d’avoir des cycles de développement courts et offrent aux développeurs beaucoup de parallélisme « plug-and-play ».
Cependant, les FPGA devraient rattraper leur retard, en particulier lorsqu’ils comparent les facteurs de forme et la consommation d’énergie. Les FPGA offrent également une latence plus faible pour les flux de données à haut débit. Lorsque plusieurs FPGA sont regroupés, ils offrent de meilleures performances que les clusters GPU.
GPU VS FPGA
GPU:
Temps de développement : les GPU offrent un temps de développement rapide. La documentation destinée aux développeurs pour des frameworks tels que CUDA et OpenCL est bien développée et populaire.
Consommation d’énergie : les GPU sont très « gourmands en énergie ». Même lorsque les développeurs tirent parti du parallélisme au niveau des données et du parallélisme au niveau des threads, les GPU consomment toujours beaucoup d’énergie.
Disponibilité : Les GPU grand public sont bon marché et facilement disponibles dès maintenant.
FPGA :
Cycle de développement : Les FPGA ont un cycle de développement plus complexe et nécessitent des ingénieurs plus spécialisés. Les FPGA permettent aux ingénieurs de réaliser de nombreuses optimisations de « bas niveau » que les GPU ne peuvent pas réaliser.
Latence : les FPGA offrent une latence plus faible, en particulier lors du traitement de flux de données volumineux.
Coût par rapport à la disponibilité : les FPGA sont plus chers que les GPU et ne sont pas aussi facilement disponibles que les GPU.
ZPRIZE
De nos jours, lorsqu’il s’agit du goulot d’étranglement de l’optimisation matérielle et du ZKP, il existe une concurrence qui ne peut être évitée - ZPRIZE
ZPrize est l’une des initiatives les plus importantes dans le domaine de la ZK à l’heure actuelle. ZPrize est une compétition qui encourage les équipes à développer une accélération matérielle pour les principaux goulots d’étranglement de ZKP (par exemple, MSM, NTT, Poseidon, etc.) sur plusieurs plates-formes (par exemple, FPGA, GPU, appareils mobiles et navigateurs) en fonction de la latence, du débit et de l’efficacité.
Le résultat a été très intéressant. Par exemple, les améliorations apportées au GPU sont énormes :
MSM à 2^26 a augmenté de 131 %, passant de 5,86 secondes à 2,52 secondes. D’autre part, les solutions FPGA ont tendance à ne pas avoir de benchmarks par rapport aux résultats GPU, qui ont des benchmarks précédents à comparer, et la plupart des solutions FPGA sont open-source pour la première fois avec de tels algorithmes qui devraient s’améliorer à l’avenir.
Ces résultats indiquent la direction dans laquelle la plupart des développeurs se sentent à l’aise dans le développement de leurs solutions d’accélération matérielle. De nombreuses équipes concourent pour la catégorie GPU, mais seul un petit pourcentage concourt pour la catégorie FPGA. Je ne sais pas si c’est à cause d’un manque d’expérience dans le développement pour les FPGA, ou si la plupart des sociétés/équipes FPGA choisissent de développer secrètement pour vendre leurs solutions commercialement.
ZPrize a fourni des recherches très intéressantes à la communauté. Au fur et à mesure que d’autres tours de ZPrize commencent, nous verrons de plus en plus de solutions et de problèmes intéressants apparaître.
Exemples pratiques d’accélération matérielle
Si l’on prend l’exemple de Groth16, si l’on examine l’implémentation de rapidsnark pour Groth16, on peut observer que deux opérations principales sont effectuées : la FFT (Fast Fourier Transform) et la MSM (Multiscalar Multiplication) ; Ces deux opérations de base sont courantes dans de nombreux systèmes de preuve. Leur temps d’exécution est directement lié au nombre de contraintes dans le circuit. Naturellement, le nombre de contraintes augmente au fur et à mesure que des circuits plus complexes sont écrits.
Pour avoir une idée de l’intensité des opérations FFT et MSM en termes de calcul, nous pouvons consulter le benchmark d’Ingonyama sur le circuit Groth16 (le processus Vanilla C2 de Filecoin effectué sur un secteur de 32 Go), et les résultats sont les suivants
Comme le montre la figure ci-dessus, le MSM (Multiscalar Multiplication) peut prendre beaucoup de temps et constituer un sérieux goulot d’étranglement des performances pour de nombreux prouveurs, ce qui fait du MSM l’un des opérateurs cryptographiques les plus importants qui doivent être accélérés.
Alors, quelle quantité de calcul le MSM occupe-t-il pour le prouveur dans d’autres systèmes de preuve ZK ? C’est ce que montre la figure ci-dessous
À Plonk, le MSM représente plus de 85 % des frais généraux, comme le montre le dernier article d’Ingonyama, Pipe MSM. **
Alors, comment l’accélération matérielle devrait-elle accélérer le MSM ? **
MSM
Avant de parler de la façon d’accélérer le HSH, nous devons comprendre ce qu’est le MSM
La multiplication multiscalaire (MSM) est un algorithme permettant de calculer la somme de plusieurs multiplications scalaires sous la forme suivante
où G est un point dans le groupe de courbes elliptiques, a est un scalaire, et le résultat de MSM sera également un point de courbe elliptique
Nous pouvons décomposer le MSM en deux sous-composantes principales :
Multiplication modulaire
Ajouts de points de courbe elliptique
Prenons l’exemple d’Affine(x,y) pour effectuer une opération P+Q naïve.
Lorsque nous voulons calculer P + Q = R, nous devons calculer une valeur k, par l’abscisse de k et P,Q
Obtenir les coordonnées de R. Le processus de calcul est le suivant ci-dessus, dans ce processus, nous effectuons 2 fois la multiplication, 1 opération au carré, 1 opération inverse, et plusieurs fois des opérations d’addition et de soustraction. Il est intéressant de noter que les opérations ci-dessus sont effectuées dans un corps fini, c’est-à-dire sous mod P. En réalité, P sera très grand. **
Le coût de l’opération ci-dessus est de trouver l’inverse >> la multiplication** **> **** au carré, et le coût de l’addition et de la soustraction est négligeable.
Nous voulons donc éviter autant que possible les inverses, car le coût d’une seule inversion est au moins cent fois supérieur à celui de la multiplication. Nous pouvons le faire en développant le système de coordonnées, mais au prix d’une augmentation du nombre de multiplications dans le processus, telles que les coordonnées jacobiennes : XYZ += XYZ, et en multipliant plus de 10 fois, selon l’algorithme d’addition. **
GPU VS FPGA Accelerated MSM
Cette section compare deux implémentations MSM de premier plan, PipeMSM et Sppark, où PipeMSM est implémenté sur les FPGA et Sppark est implémenté sur les GPU.
Sppark et PipeMSM utilisent l’algorithme de pointe de Pippenger pour implémenter MSM, également connu sous le nom d’algorithme de compartiment ; **
Sppark est implémenté à l’aide de CUDA ; Leurs versions sont hautement parallélisées et ont obtenu des résultats impressionnants lorsqu’elles sont exécutées sur les derniers GPU.
Cependant, PipeMSM ne se contente pas d’optimiser l’algorithme, mais fournit également des optimisations pour les primitives mathématiques de la multiplication modulaire et de l’addition EC. PipeMSM gère l’ensemble de la « pile MSM », en mettant en œuvre une série d’astuces mathématiques et d’optimisations visant à rendre MSM plus adapté au matériel, et en concevant une conception matérielle conçue pour réduire la latence en mettant l’accent sur la parallélisation.
Faisons un bref récapitulatif de l’implémentation de PipeMSM.
Faible latence
PipeMSM est conçu pour fournir une faible latence lors de l’exécution de plusieurs MSM sur un grand nombre d’entrées. Les GPU n’offrent pas de faible latence déterministe en raison de la mise à l’échelle dynamique de la fréquence, et les GPU ajustent leurs vitesses d’horloge en fonction des charges de travail.
Mais grâce à la conception matérielle optimisée, les implémentations FPGA peuvent fournir des performances déterministes et une latence pour des charges de travail spécifiques.
Mise en œuvre de l’addition EC
L’addition de points de courbe elliptique (EC Addition) est implémentée sous la forme d’une formule à faible latence, hautement parallèle et complète (complète signifie qu’elle calcule correctement la somme de deux points quelconques dans le groupe de courbes elliptiques). L’addition de points de courbe elliptique est utilisée de manière canalisée dans le module d’addition EC pour réduire la latence.
Nous avons choisi de représenter les coordonnées sous forme de coordonnées projectives, et sur l’algorithme d’addition, nous utilisons une formule d’addition de points de courbe elliptique complète. Le principal avantage est que nous n’avons pas à nous occuper de cas limites. Formules complètes ;
Nous avons implémenté cette formule d’addition de manière pipeline et parallèle, et notre circuit d’additionneur de courbe elliptique FPGA n’a eu besoin que de 12 multiplications, 17 sommes d’additions, et cette formule a été exécutée. La formule originale nécessite 15 multiplications modulo et 13 additions. La conception du FPGA est la suivante
Multi mod
Nous avons utilisé les algorithmes de réduction de Barrett et de Karatsuba.
La réduction de Barrett est un algorithme qui calcule efficacement r≡ab mod p (où p est fixe). Barrett Reduction tente de remplacer la division (une opération coûteuse) par une division approximative. Une tolérance d’erreur peut être sélectionnée pour décrire la plage dans laquelle nous recherchons le résultat correct. Nous constatons que la grande tolérance d’erreur permet d’utiliser des constantes de réduction plus petites ; Cela réduit la taille des valeurs intermédiaires utilisées dans les opérations de réduction modulo, ce qui réduit le nombre de multiplications nécessaires pour calculer le résultat final.
Dans l’encadré bleu ci-dessous, nous pouvons voir qu’en raison de notre tolérance élevée aux erreurs, nous devons effectuer plusieurs vérifications pour trouver un résultat précis.
En un mot, l’algorithme de Karatsuba est utilisé pour optimiser la multiplication que nous effectuons dans la réduction de Barrett. L’algorithme de Karatsuba simplifie la multiplication de deux n chiffres à la multiplication de trois n/2 chiffres ; Ces multiplications peuvent simplifier le nombre de chiffres pour qu’il soit suffisamment étroit pour être directement calculé par le matériel. Les détails peuvent être lus dans l’article d’Ingo : Pipe MSM
À l’aide des opérateurs ci-dessus, nous avons développé une implémentation MSM hautement parallèle et à faible latence.
L’idée de base est qu’au lieu de calculer l’ensemble du MSM en une seule fois, chaque morceau est passé dans l’additionneur EC en parallèle. Les résultats de l’additionneur EC sont accumulés dans le MSM final.
Résultat final****
Le diagramme ci-dessus montre la comparaison entre Sppark et PipeMSM.
Le plus important est l’importante économie d’énergie offerte par les FPGA, qui pourrait être extrêmement importante pour les futures opérations de production de preuves à grande échelle. Il convient de noter que notre implémentation a été prototypée et évaluée sous @125MHz, et que l’augmentation de la vitesse d’horloge à @500MHz pourrait augmenter le temps de calcul de 4 fois ou plus.
Un autre avantage de l’utilisation de nos FPGA est qu’ils peuvent être installés dans des serveurs à châssis restreint car ils consomment moins d’énergie et génèrent moins de chaleur.
Nous n’en sommes qu’aux premiers stades de l’ingénierie FPGA pour ZKP et nous devons nous attendre à de nouvelles améliorations dans les algorithmes. De plus, le FPGA calcule le MSM lorsque le CPU est inactif, et il peut être possible d’obtenir des temps plus rapides en utilisant le FPGA en combinaison avec les ressources système (CPU/GPU).
Résumé
Le ZKP est devenu une technologie clé pour les systèmes distribués.
L’application de ZKP ira bien au-delà de la simple extension du niveau Ethereum, permettant l’externalisation du calcul à des tiers non fiables, permettant le développement de systèmes auparavant impossibles, tels que le cloud computing distribué, les systèmes d’identité, etc.
Traditionnellement, les optimisations ZKP se sont concentrées sur les améliorations au niveau logiciel, mais à mesure que la demande de performances supérieures augmente, nous verrons des solutions d’accélération plus avancées impliquant à la fois le matériel et le logiciel.
À l’heure actuelle, les solutions d’accélération que nous voyons utilisent principalement des GPU, car le temps de développement à l’aide de CUDA est court et les GPU grand public actuels sont très bon marché et abondants. Le GPU offre également des performances incroyables. Il est donc peu probable que les GPU disparaissent de cet espace de sitôt.
Au fur et à mesure que des équipes de développement plus complexes entrent dans l’espace, il est probable que nous verrons les FPGA ouvrir la voie en termes d’efficacité énergétique et de performances. Par rapport aux GPU, les FPGA offrent plus de personnalisation de bas niveau ainsi que plus d’options de configuration. Les FPGA offrent une vitesse de développement et une flexibilité plus rapides que les ASIC. Avec le développement rapide du monde ZKP, les FPGA peuvent être reflashés avec différents programmes pour s’adapter à différents systèmes et mettre à jour les solutions.
Cependant, pour générer des preuves en temps quasi réel, il peut être nécessaire de combiner des configurations GPU/FPGA/ASIC en fonction du système pour lequel nous générons des preuves.
Le ZPU est également susceptible d’évoluer pour fournir des solutions extrêmement efficaces pour les générateurs d’épreuve à grande échelle et les appareils de faible puissance (voir l’article précédent pour plus de détails).