Transmettre le titre original « Un paradigme à connaissance zéro : Partie 1 - Qu’est-ce qu’une zk-VM ? »

1. Preuves à divulgation nulle de connaissance : une introduction

Que sont les preuves à divulgation nulle de connaissance (ZKP) ?

Si vous n’avez aucune connaissance préalable des preuves à divulgation nulle de connaissance (ZKP), cette vidéo de Wired explique le concept à cinq niveaux de difficulté de manière interactive avec des exemples et des démonstrations facilement compréhensibles. Hautement recommandé.

En termes simples, les ZKP permettent à une partie (prouveur) de prouver à une autre partie (le vérificateur) qu’elle sait quelque chose sans révéler ce que c’est ou toute information supplémentaire. Plus précisément, les ZKP prouvent la connaissance d’une donnée, ou la connaissance du résultat d’un calcul, sans révéler les données ou les entrées. Le processus de création d’une preuve à divulgation nulle de connaissance implique une série de modèles mathématiques pour transformer les résultats d’un calcul en une information autrement dénuée de sens qui prouve l’exécution réussie du code, qui peut ensuite être vérifiée.

Dans certains cas, il faut moins de travail pour vérifier la preuve, qui est construite après plusieurs cycles de conversions algébriques et de cryptographie, qu’il n’en faudrait pour exécuter le calcul. Cette combinaison unique de sécurité et d’évolutivité est ce qui fait de la cryptographie à connaissance nulle un outil si puissant.

zkSNARKs : Argument de connaissance non interactif succinct de la connaissance

• S’appuie sur un processus de configuration initial (fiable ou non approuvé) pour établir les paramètres de vérification
• Nécessite au moins une interaction entre l’étalon et le vérificateur
• Les tailles d’épreuve sont petites et faciles à vérifier
• Les preuves basées sur NARK sont utilisées par des rollups comme zkSync, Scroll et Linea

zkSTARKs : Zero Knowledge Scalable Transparent Argument de la connaissance

• Aucune configuration fiable requise
• Offrir une grande transparence en utilisant le caractère aléatoire vérifiable publiquement pour créer des systèmes vérifiables sans confiance, c’est-à-dire en générant des paramètres aléatoires prouvés pour prouver et vérifier
• Hautement évolutif car ils peuvent générer et vérifier des preuves rapidement (pas toujours), même lorsque la taille du témoin sous-jacent (données) est importante
• Ne nécessite aucune interaction entre l’étalon et le vérificateur
• Cela se fait au prix que les STARK génèrent des preuves plus importantes, ce qui peut être plus difficile à vérifier que les SNARK
• Les preuves sont plus difficiles à vérifier que certaines preuves zkSNARK, mais pas aussi difficiles à vérifier que d’autres
• Les STARK sont utilisés par Starknet, ainsi que par les zkVM comme Lita, Risc Zero et Succinct Labs

(Note : le pont de Succinct utilise des SNARK mais SP1 est un protocole basé sur STARK)

Il convient de noter que tous les STARK sont des SNARK, mais que tous les SNARK ne sont pas des STARK.

Pour une meilleure compréhension générale des SNARK et des STARK, nous vous recommandons de lire cette série d’articles @krzhang/privacy-in-cryptocurrencies-zero-knowledge-and-zk-snarks-1-2-68ce1838fd9c"> écrite par Yan Zhang et Yi Sun d’Axiom, et cette collection d’articles dans le github de Ventali Tan.

2. Qu’est-ce qu’une zkVM ?

Une machine virtuelle (VM) est un programme qui exécute des programmes. Dans le contexte, une zkVM est un ordinateur virtuel qui est implémenté comme un système pour générer des preuves à divulgation nulle de connaissance, ou un circuit universel, ou un outil, pour générer des ZKP pour tout programme ou calcul.

Les zkVM éliminent le besoin d’apprendre des mathématiques et de la cryptographie compliquées pour concevoir et coder ZK, et permettent à tout développeur d’exécuter des programmes écrits dans ses langages préférés et de générer des ZKP, ce qui facilite grandement l’intégration et l’interaction avec zéro connaissance. D’une manière générale, la plupart des références aux zkVM incluent implicitement les chaînes d’outils du compilateur et les systèmes de preuve ajoutés à la machine virtuelle qui exécute les programmes, et pas seulement la machine virtuelle elle-même. Ci-dessous, nous résumons les principaux composants d’une zkVM et leurs fonctions :

Les principaux composants d’une zkVM

La conception et l’implémentation de chaque composant sont régies par le choix de la preuve (SNARK ou STARK) et l’architecture du jeu d’instructions (ISA) de la zkVM. Traditionnellement, un ISA spécifie ce dont un processeur est capable (types de données, registres, mémoire, etc.) et la séquence d’actions que le processeur effectue lorsqu’il exécute un programme. Dans le contexte, l’ISA détermine le code machine qui est interprétable et exécutable par la machine virtuelle. Le choix d’un ISA peut entraîner des différences radicales dans l’accessibilité et la convivialité de la zkVM, ainsi que dans la vitesse et l’efficacité des processus de génération de preuves, et sous-tend la construction de toute zkVM.

Vous trouverez ci-dessous quelques exemples de zkVM et de leurs composants pour votre référence.

zkVM et leurs composants

Pour l’instant, nous nous concentrerons sur les interactions entre chaque composant à un niveau élevé afin de fournir un cadre pour comprendre les processus algébriques et cryptographiques ainsi que les compromis de conception d’une zkVM dans un article ultérieur.

3. Flux de processus zkVM abstrait

Le diagramme suivant est un organigramme abstrait et généralisé d’une zkVM, divisé et catégorisé entre le format (entrées / sorties) d’un programme lorsqu’il se déplace à travers les composants d’une zkVM. Nous examinerons chaque processus en profondeur dans les articles suivants.

Flux général pour une zkVM

Le flux de processus d’une zkVM est généralement le suivant :

• Étape du compilateur

1. Le compilateur compile d’abord des programmes écrits dans des langages conventionnels (C, C++, Rust, Solidity) en code machine. Le format du code machine est dicté par le choix de l’ISA.

• Étape de la machine virtuelle

1. La machine virtuelle exécute le code machine et génère une trace d’exécution, qui est la série d’étapes du programme sous-jacent. Le format de celui-ci est prédéterminé par le choix de l’arithmétisation ainsi que par l’ensemble des contraintes polynomiales. Les schémas d’arithmétisation courants incluent R1CS comme dans Groth16, l’arithmétisation PLONKish comme dans halo2 et AIR comme dans plonky2 et plonky3.

• Étage de démonstrateur

1. Le prouveur reçoit la trace et la représente comme un ensemble de polynômes liés par un ensemble de contraintes, traduisant essentiellement le calcul en algèbre en cartographiant mathématiquement les faits.

2. Le prouveur s’engage sur ces polynômes en utilisant un schéma d’engagement polynomial (PCS). Un schéma d’engagement est un protocole qui permet au prouveur de créer une empreinte digitale de certaines données X, ce qui est appelé un engagement envers X, et de prouver plus tard des faits sur X sans révéler X, en utilisant l’engagement envers X. Le PCS est l’empreinte digitale ; une version succincte « prétraitée » des contraintes sur le calcul. Cela permet au prouveur de prouver des faits sur le calcul, maintenant exprimés dans une équation polynomiale, en utilisant des valeurs aléatoires proposées par le vérificateur dans les étapes suivantes.

3. Le prouveur exécute une preuve Oracle interactive polynomiale (PIOP) pour montrer que les polynômes validés représentent une trace d’exécution qui satisfait les contraintes données. Un PIOP est un protocole de preuve interactif consistant en une série de tours dans lesquels le prouveur envoie des engagements aux polynômes, le vérificateur répond avec des valeurs de champ aléatoires et le prouveur fournit des évaluations du polynôme à ces valeurs aléatoires, comme si l’on « résolvait » l’équation polynomiale en utilisant des valeurs aléatoires pour persuader le vérificateur de manière probabiliste.

4. Application de l’heuristique Fiat-Shamir ; le prouveur exécute le PIOP en mode non interactif, où le comportement du vérificateur se limite à l’envoi de points de défi pseudo-aléatoires. En cryptographie, l’heuristique Fiat-Shamir convertit une preuve de connaissance interactive en une signature numérique pour vérification. Cette étape crypte la preuve et en fait une connaissance nulle.

5. Le prouveur doit convaincre le vérificateur que les évaluations polynomiales revendiquées sont correctes, en ce qui concerne les engagements polynomiaux qu’il a envoyés au vérificateur. Pour ce faire, le prouveur produit une preuve d'« évaluation » ou d'« ouverture », qui est fournie par le schéma d’engagement polynomial (empreinte).

• Étape du vérificateur

1. Le vérificateur vérifie la preuve en suivant le protocole de vérification du système de preuve, soit en utilisant les contraintes, soit l’engagement. Le vérificateur accepte ou rejette le résultat en fonction de la validité de la preuve.

En résumé, une preuve zkVM prouve, pour un programme donné, un résultat donné, et des conditions initiales données, qu’il existe une entrée qui fait que le programme produit le résultat donné lorsqu’il est exécuté à partir des conditions initiales données. Nous pouvons combiner cette instruction avec le flux de processus pour arriver à la description suivante d’une zkVM.

Une preuve zkVM prouve, pour un programme de machine virtuelle donné et une sortie donnée, qu’il existe une entrée qui amène le programme donné à produire la sortie donnée lorsqu’il est exécuté sur la machine virtuelle.

4. Évaluation des zkVM

Quels sont les critères selon lesquels nous devrions évaluer les zkVM ? En d’autres termes, quand devrions-nous dire qu’une zkVM est meilleure qu’une autre ? À vrai dire, la réponse dépend du cas d’utilisation.

L’étude de marché de Lita suggère que pour la plupart des cas d’utilisation commerciale, les propriétés les plus importantes, à savoir la vitesse, l’efficacité et la concision, sont soit la vitesse, soit l’efficacité du cœur-temps, selon l’application. Certaines applications sont sensibles au prix et veulent optimiser la faible consommation d’énergie et la faible utilisation du capital dans la prouvation ; Pour ceux-ci, l’efficacité du temps de base est probablement la mesure la plus importante à optimiser. D’autres applications, en particulier les applications liées à la finance ou au trading, sont sensibles à la latence et souhaitent optimiser la vitesse.

La plupart des comparaisons de performance se concentrent exclusivement sur la vitesse, ce qui est important mais ne constitue pas une mesure holistique de la performance. Il existe également quelques propriétés importantes qui mesurent la fiabilité d’une zkVM ; dont la plupart ne sont pas conformes aux normes de production, même pour les leaders du marché.

Nous proposons par la présente que les zkVM soient évaluées sur les critères suivants, séparés en deux sous-ensembles :

Principaux critères d’évaluation des machines virtuelles zk

Base de référence : Mesure la fiabilité des zkVM

• Exactitude
• Sécurité
• Hypothèses de confiance

Performance : Mesure les capacités d’une zkVM

• Efficacité
• Vitesse
• Concision

4.1 Base de référence : hypothèses relatives à l’exactitude, à la sécurité et à la confiance

Lors de l’évaluation des zkVM pour les applications critiques, l’exactitude et la sécurité doivent être considérées comme la base de référence. Il doit y avoir suffisamment de raisons d’être confiant quant à l’exactitude et une garantie revendiquée suffisamment solide. En outre, les hypothèses de confiance doivent être suffisamment faibles pour l’application.

Sans ces propriétés, la zkVM est potentiellement pire qu’inutile pour l’application, car elle peut ne pas fonctionner comme spécifié et exposer les utilisateurs au piratage et aux exploits.

i. Exactitude

• La machine virtuelle doit exécuter le calcul comme prévu
• Le système de preuve doit satisfaire à ses propriétés de sécurité revendiquées

L’exactitude est composée de trois propriétés :

• Solidité : Le système de preuve est véridique et donc tout ce qu’il prouve est vrai. Le vérificateur rejette les preuves de fausses déclarations ; il n’accepte le résultat d’un calcul que si les entrées produisent réellement ce résultat.
• Exhaustivité : Le système de preuve est complet et peut prouver toutes les affirmations vraies. Si le prouveur prétend qu’il peut prouver le résultat d’un calcul, il doit être en mesure de produire une preuve que le vérificateur accepte.
• Connaissance zéro : Posséder une preuve ne révèle pas plus sur les entrées du calcul que ne le ferait la connaissance du résultat lui-même

Vous pouvez avoir la complétude sans la solidité ; Si le système de preuve prouve tout, y compris la fausseté, il est évident qu’il est complet mais pas solide. Inversement, vous pouvez avoir la solidité sans l’exhaustivité ; Si le système de preuve prouve qu’un programme a existé mais ne peut pas prouver les calculs, il est évidemment solide (après tout, il ne prouve jamais aucune fausseté), mais pas complet.

ii. Sécurité

• Se rapporte aux tolérances de solidité, d’exhaustivité et de connaissance nulle

En pratique, les trois propriétés d’exactitude ont des tolérances non nulles. Cela implique que toutes les preuves sont des probabilités statistiques d’exactitude, et non des certitudes absolues. Une tolérance fait référence à la probabilité maximale tolérable qu’une propriété échoue. Les tolérances zéro sont bien sûr l’idéal, mais les zkVM n’atteignent pas les tolérances zéro sur toutes ces propriétés dans la pratique. La solidité et l’exhaustivité parfaites semblent être incompatibles avec la concision, et il n’y a pas de méthodes connues pour atteindre une connaissance nulle parfaite. Une façon courante de mesurer la sécurité est en bits de sécurité, où une tolérance de 1 / (2^n) est appelée n bits de sécurité. Plus il y a de sécurité, mieux c’est.

Si une zkVM est parfaitement correcte, cela n’implique pas nécessairement qu’elle est fiable. L’exactitude implique seulement que la zkVM satisfait ses propriétés de sécurité jusqu’aux tolérances revendiquées. Cela ne signifie pas que les tolérances alléguées sont suffisamment faibles pour être prêtes à être commercialisées. De plus, si une zkVM est suffisamment sécurisée, cela ne signifie pas qu’elle est correcte ; La sécurité fait référence aux tolérances revendiquées, et non aux tolérances réellement atteintes. Ce n’est que lorsqu’une zkVM est à la fois parfaitement correcte et suffisamment sûre que l’on peut dire qu’elle est fiable jusqu’aux tolérances revendiquées.

iii. Hypothèses de confiance

• Hypothèses sur l’honnêteté du prouveur et du vérificateur pour arriver à la conclusion que la zkVM fonctionne de manière fiable

Lorsque les zkVM ont des hypothèses de confiance, cela prend généralement la forme d’un processus de configuration approuvé. Un processus de configuration pour un système d’épreuve ZK s’exécute une fois, avant que la première épreuve ne soit générée à l’aide du système d’épreuve, afin de générer des informations appelées « données de configuration ». Dans un processus de configuration approuvé, un ou plusieurs individus génèrent un caractère aléatoire qui est incorporé dans les données de configuration, et il faut supposer qu’au moins un de ces individus a supprimé le caractère aléatoire qu’il a incorporé dans les données de configuration.

Il existe deux modèles courants d’hypothèse de confiance dans la pratique.

Une hypothèse de confiance majoritaire honnête stipule que sur un ensemble de N individus, plus de N/2 de ces individus ont fait preuve d’intégrité dans certaines interactions particulières avec le système, qui est couramment utilisé par les blockchains

Une hypothèse de confiance « 1 sur N » stipule que sur un ensemble de N individus, au moins un de ces individus a fait preuve d’intégrité dans une ou plusieurs interactions particulières avec le système, ce qui est couramment utilisé par les outils et applications basés sur MPC.

Il est généralement admis que toutes choses étant égales par ailleurs, les zkVM sans hypothèses de confiance sont plus sûres que les zkVM qui nécessitent des hypothèses de confiance.

4.2 Le trilemme de la zkVM : équilibrer la vitesse, l’efficacité et la concision dans les zkVM

Le trilemme de la zkVM : vitesse, efficacité et concision

La rapidité, l’efficacité et la concision sont toutes des propriétés à échelle mobile. Tous ces facteurs contribuent au coût de l’utilisateur final de zkVM. La façon dont ils doivent être pondérés dans une évaluation dépend de l’application. Souvent, la solution la plus rapide n’est pas la plus efficace ou la plus succincte ; La solution la plus succincte n’est pas la plus rapide ni la plus efficace ; et ainsi de suite. Définissons d’abord chaque propriété avant d’expliquer leur relation

i. Vitesse

• En combien de temps l’étalon peut-il générer des preuves
• Mesuré en temps d’horloge murale, qui est le temps écoulé du début à la fin du calcul

La vitesse doit être définie et mesurée par rapport à des programmes, des intrants et des systèmes d’essai spécifiques pour s’assurer qu’elle peut être évaluée quantitativement. Cette métrique est essentielle pour les applications sensibles à la latence où la disponibilité rapide des preuves est essentielle, mais s’accompagne d’une surcharge plus élevée et de tailles d’épreuve plus importantes

ii. Efficience

• Les ressources consommées par le prouveur, moins étant préférable
• Peut être approximé par le temps utilisateur, qui est le temps d’ordinateur dépensé par le code du programme

Le prouveur consomme deux types de ressources : le temps du cœur et l’espace. L’efficacité peut donc être subdivisée en efficacité du temps de base et efficacité de l’espace.

Efficacité cœur-temps : Temps moyen de fonctionnement du prouveur sur tous les cœurs multiplié par le nombre de cœurs exécutant le prouveur. Pour un étalon monocœur, la consommation de temps de cœur et la vitesse sont la même chose. Pour un étalon multicœur fonctionnant en mode multicœur sur un système multicœur, la consommation de temps de cœur et la vitesse ne sont pas la même chose. Si un programme utilise pleinement 5 cœurs ou threads pendant 5 secondes, cela représenterait 25 secondes de temps utilisateur et 5 secondes de temps d’horloge murale.

Efficacité de l’espace : Fait référence à la capacité de stockage utilisée, telle que la RAM

Le temps de l’utilisateur est intéressant en tant qu’approximation de l’énergie consommée par l’exécution d’un calcul. Dans une situation où tous les cœurs sont pleinement utilisés presque tout le temps, la consommation d’énergie d’un processeur doit rester relativement constante. Dans cette situation, le temps passé par l’utilisateur à exécuter du code en mode utilisateur, principalement en mode utilisateur, doit être à peu près linéairement proportionnel au nombre de wattheures (c’est-à-dire d’énergie) consommés par cette exécution de code.

L’économie de la consommation d’énergie, ou de l’utilisation des ressources informatiques, devrait être intéressante du point de vue de toute opération d’essai qui a une échelle suffisante pour que sa facture d’énergie (ou sa facture de cloud computing) pour l’étalonnage représente un coût opérationnel considérable. Pour ces raisons, le temps de l’utilisateur est une mesure intéressante. La réduction des coûts de vérification permet aux fournisseurs de services de répercuter les prix de vérification plus bas sur les clients sensibles aux coûts.

Les deux types d’efficacité sont liés à la consommation d’énergie du processus d’étalonnage et à la quantité de capital utilisée par le processus d’étalonnage, qui se rapporte au coût financier de l’étalonnage. Pour opérationnaliser la définition de l’efficacité pour la mesure, la définition doit être faite par rapport à un ou plusieurs programmes d’essai, à un ou plusieurs intrants d’essai à chacun de ces programmes et à un ou plusieurs systèmes d’essai.

iii. Concision

• La taille des preuves générées et la complexité de leur vérification

La concision est un composite de trois mesures distinctes, la complexité de la vérification des preuves étant subdivisée :

• Taille de l’épreuve : taille physique des épreuves, généralement mesurée en kilo-octets
• Temps de vérification des preuves : Durée requise pour vérifier les preuves.
• Espace de vérification des preuves : utilisation de la mémoire pendant la vérification des preuves

La vérification est généralement une opération à cœur unique, donc la vitesse et l’efficacité du temps de cœur sont généralement équivalentes dans ce contexte. Comme pour la vitesse et l’efficacité, l’opérationnalisation de la définition de la concision nécessite de spécifier des ensembles de programmes de test, d’entrées de test et de systèmes de test.

Une fois chaque propriété de performance définie, nous illustrons maintenant les effets dimunitifs de l’optimisation d’une propriété par rapport aux autres.

• Vitesse : la génération rapide d’épreuves conduit à des tailles d’épreuve plus grandes, mais la vérification des épreuves est lente. Plus de ressources sont consommées pour générer des preuves, ce qui réduit l’efficacité
• Concision : Le démonteur a besoin de plus de temps pour compresser les épreuves. Mais la vérification des preuves est rapide. Plus la preuve est succincte, plus la surcharge de calcul est élevée
• Efficacité : la minimisation de l’utilisation des ressources réduit la vitesse de génération de l’épreuve et la concision de l’épreuve

En général, optimiser pour une qualité signifie ne pas optimiser pour une autre qualité, et donc une analyse multidimensionnelle est nécessaire pour choisir une solution optimale au cas par cas.

Une bonne façon de pondérer ces propriétés dans une évaluation peut être de définir des niveaux acceptables pour chaque propriété, puis de déterminer quelles propriétés sont les plus importantes. Les propriétés les plus importantes doivent être optimisées, sous réserve de maintenir des niveaux suffisamment bons sur toutes les autres propriétés.

Ci-dessous, nous résumons chaque propriété et leurs principales considérations :

Propriétés d’évaluation des zkVM

5. Quelle est la prochaine étape ?

Avec le tableau ci-dessus, nous concluons ici le premier article de notre série. Dans les prochains articles, nous nous appuierons sur l’organigramme ci-dessus pour expliquer les processus arithmétiques et cryptographiques courants dans les zkVM.

Si vous avez trouvé cela utile, visitez notre site Web et notre gitbook pour en savoir plus sur ce que nous construisons chez Lita.

Suivez-nous également sur X et Discord pour rester à jour afin de ne pas manquer le reste de la série

Démenti:

1. Cet article est reproduit de [lita]. Transmettre le titre original 'A Zero Knowledge Paradigm : Part 1 - What is a zk-VM ?'. Tous les droits d’auteur appartiennent à l’auteur original [Lita Team]. S’il y a des objections à cette réimpression, veuillez contacter l’équipe Gate Learn , et ils s’en occuperont rapidement.
2. Clause de non-responsabilité : Les points de vue et opinions exprimés dans cet article sont uniquement ceux de l’auteur et ne constituent aucun conseil en investissement.
3. Les traductions de l’article dans d’autres langues sont effectuées par l’équipe de Gate Learn. Sauf mention contraire, il est interdit de copier, distribuer ou plagier les articles traduits.