Développement et application de la technologie zk-SNARKs : aperçu dans le domaine du Blockchain

Résumé

zk-SNARKs(ZKP) est une percée importante dans le domaine de la cryptographie, jouant un rôle clé dans la technologie Blockchain. Cet article présente une revue systématique de l'évolution de ZKP au cours des quarante dernières années et des recherches les plus récentes.

Tout d'abord, le concept de base et le contexte historique des ZKP sont présentés. Ensuite, l'accent est mis sur l'analyse des techniques ZKP basées sur des circuits, y compris la conception, les applications et les méthodes d'optimisation des modèles tels que zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs et Ligero. En ce qui concerne l'environnement de calcul, cet article discute de la manière dont ZKVM et ZKEVM améliorent la capacité de traitement des transactions, protègent la vie privée et augmentent l'efficacité de la vérification. Il présente également le fonctionnement et les méthodes d'optimisation des Rollups à connaissance nulle en tant que solution d'extension Layer 2, ainsi que les derniers développements en matière d'accélération matérielle, de solutions hybrides et de ZK EVM dédiés.

Enfin, nous avons examiné les concepts émergents tels que ZKCoprocessor, ZKML, ZKThreads, ZK Sharding et ZK StateChannels, en discutant de leur potentiel en matière d'évolutivité, d'interopérabilité et de protection de la vie privée dans le domaine de la Blockchain.

En analysant ces tendances de développement technologique, cet article fournit une perspective complète pour comprendre et appliquer la technologie ZKP, montrant son potentiel énorme pour améliorer l'efficacité et la sécurité des systèmes Blockchain, offrant ainsi une référence importante pour les décisions d'investissement futures.

Table des matières

Préface

I. Connaissances de base sur les zk-SNARKs

1. Aperçu
2. Exemple de zk-SNARKs

Deux, zk-SNARKs non interactifs

1. Contexte
2. Proposition de NIZK
3. Transformation Fiat-Shamir
4. Jens Groth et ses recherches
5. Autres recherches

Trois, preuve de connaissance nulle basée sur des circuits

1. Contexte
2. Concepts et caractéristiques de base des modèles de circuits
3. Conception et application des circuits dans les zk-SNARKs
4. Défauts et défis potentiels

Quatre, modèle zk-SNARKs

1. Contexte
2. Modèles d'algorithmes courants
3. Schéma basé sur le PCP linéaire et le problème du logarithme discret
4. Solution basée sur la preuve des gens ordinaires
5. Preuve vérifiable basée sur la probabilité ( PCP ) zk-SNARKs
6. Classification basée sur la phase de configuration de la construction de preuve générale CPC( ).

V. Aperçu et développement des machines virtuelles à preuve nulle

1. Contexte
2. Classification actuelle du ZKVM
3. Paradigme front-end et back-end
4. Avantages et inconvénients du paradigme ZKVM

VI. Vue d'ensemble et développement de zk-SNARKs sur la machine virtuelle Ethereum

1. Contexte
2. Fonctionnement du ZKEVM
3. Le processus de mise en œuvre de ZKEVM
4. Les caractéristiques de ZKEVM

Sept, aperçu et développement des solutions de réseau de deuxième couche zk-SNARKs.

1. Contexte
2. Mécanisme de fonctionnement des ZK Rollups
3. Inconvénients et optimisation des zk-Rollups

Huit, les directions futures du zk-SNARKs

1. Accélérer le développement des environnements de calcul
2. Proposition et développement de ZKML
3. Développements liés à la technologie d'extension de ZKP
4. Le développement de l'interopérabilité des zk-SNARKs

Neuf, conclusion

Introduction

Internet entre dans l'ère du Web3, les applications Blockchain ( DApps ) se développent rapidement. Ces dernières années, les plateformes Blockchain supportent des millions d'activités d'utilisateurs chaque jour, traitant des milliards de transactions. Les données massives générées par ces transactions incluent souvent des informations personnelles sensibles. Étant donné les caractéristiques d'ouverture et de transparence de la Blockchain, les données stockées sont accessibles à tous, ce qui soulève divers problèmes de sécurité et de confidentialité.

Actuellement, plusieurs technologies cryptographiques peuvent relever ces défis, y compris le chiffrement homomorphe, les signatures en anneau, le calcul multipartite sécurisé et les zk-SNARKs. Les zk-SNARKs constituent une solution plus complète, ce protocole de vérification permet de vérifier la validité de certaines propositions sans divulguer aucune donnée intermédiaire. Ce protocole ne nécessite pas d'infrastructure de clé publique complexe, et sa mise en œuvre répétée ne donne pas aux utilisateurs malveillants la possibilité d'obtenir des informations supplémentaires utiles. Grâce aux zk-SNARKs, le vérificateur peut confirmer si le prouveur dispose d'un montant de transaction suffisant sans divulguer aucune donnée de transaction privée.

Cette caractéristique des zk-SNARKs leur permet de jouer un rôle central dans les transactions Blockchain et les applications de cryptomonnaie, en particulier en matière de protection de la vie privée et d'extensibilité du réseau, ce qui en fait non seulement un point focal de la recherche académique, mais aussi l'une des innovations technologiques les plus importantes depuis la mise en œuvre réussie des technologies de registre distribué. C'est également une piste clé pour les applications industrielles et le capital-risque.

De ce fait, de nombreux projets de réseau basés sur les ZKP ont émergé, tels que ZkSync, StarkNet, Mina, Filecoin et Aleo. Avec le développement de ces projets, les innovations algorithmiques autour des ZKP ne cessent d'apparaître, et il a été rapporté qu'à peu près chaque semaine, un nouvel algorithme voit le jour. De plus, le développement de matériel lié à la technologie ZKP progresse rapidement, y compris des puces optimisées spécifiquement pour les ZKP. Par exemple, des projets comme Ingonyama, Irreducible et Cysic ont déjà achevé des levées de fonds à grande échelle. Ces développements non seulement démontrent les progrès rapides de la technologie ZKP, mais reflètent également la transition des matériels génériques vers des matériels dédiés comme les GPU, FPGA et ASIC.

Ces progrès indiquent que la technologie des zk-SNARKs n'est pas seulement une percée importante dans le domaine de la cryptographie, mais aussi un moteur clé pour la mise en œuvre d'applications plus larges de la technologie Blockchain.

Ainsi, nous avons décidé de rassembler systématiquement les connaissances pertinentes sur les zk-SNARKs ( ZKP ) afin de mieux nous aider à prendre des décisions d'investissement à l'avenir. Pour ce faire, nous avons examiné en profondeur les articles académiques clés liés aux ZKP; en même temps, nous avons également analysé en détail les informations et les livres blancs des projets leaders dans ce domaine. Cette collecte et analyse de données complètes ont fourni une base solide pour la rédaction de cet article.

I. Connaissances de base sur les zk-SNARKs

1. Aperçu

En 1985, les chercheurs Goldwasser, Micali et Rackoff ont proposé pour la première fois le concept de zk-SNARKs ( Zero-Knowledge Proof, ZKP ) et Interactive Zero-Knowledge, IZK (. Cet article est la pierre angulaire des zk-SNARKs, définissant de nombreux concepts qui influencent les recherches académiques ultérieures. Par exemple, la définition de la connaissance est "une sortie de calcul non réalisable", ce qui signifie que la connaissance doit être une sortie et qu'il s'agit d'un calcul non réalisable, ce qui signifie qu'elle ne peut pas être une simple fonction, mais doit être une fonction complexe. Un calcul non réalisable peut généralement être compris comme un problème NP, c'est-à-dire un problème dont la solution peut être vérifiée en temps polynomial, le temps polynomial désignant le temps d'exécution de l'algorithme qui peut être exprimé par une fonction polynomiale en fonction de la taille de l'entrée. C'est un critère important pour évaluer l'efficacité et la faisabilité des algorithmes en informatique. Étant donné que le processus de résolution des problèmes NP est complexe, il est donc considéré comme un calcul non réalisable ; mais son processus de vérification est relativement simple, ce qui le rend très adapté à la validation des zk-SNARKs.

Un exemple classique de problème NP est le problème du voyageur de commerce, où il s'agit de trouver le chemin le plus court pour visiter une série de villes et revenir au point de départ. Bien qu'il puisse être difficile de trouver le chemin le plus court, il est relativement facile de vérifier si un chemin donné est le plus court. En effet, la distance totale d'un chemin spécifique peut être calculée en temps polynomial.

Dans leur article, Goldwasser et al. introduisent le concept de "complexité de la connaissance" pour quantifier la quantité de connaissance que le prouveur divulgue au vérificateur dans les systèmes de preuve interactifs. Ils proposent également le système de preuve interactif )Interactive Proof Systems, IPS(, où le prouveur )Prover( et le vérificateur )Verifier( interagissent par de multiples tours pour prouver la véracité d'une déclaration.

En résumé, la définition du zk-SNARKs résumée par Goldwasser et al. est une preuve interactive particulière, dans laquelle le vérificateur ne reçoit aucune information supplémentaire en dehors de la vérité de l'énoncé durant le processus de vérification; et trois caractéristiques fondamentales ont été proposées, y compris:

1. Complétude ) completeness ( : si la démonstration est vraie, un prouveur honnête peut convaincre un vérificateur honnête de ce fait ;

2. Fiabilité ) soundness ( : Si le prouveur ne connaît pas le contenu de la déclaration, il ne peut tromper le vérificateur qu'avec une probabilité négligeable ;

3. zk-SNARKs ) zero-knowledge ( : à la fin du processus de preuve, le vérificateur ne reçoit que l'information "le prouveur possède cette connaissance", sans obtenir de contenu supplémentaire.

) 2. Exemples de zk-SNARKs

Pour mieux comprendre les zk-SNARKs et leurs attributs, voici un exemple de vérification si le prouveur possède certaines informations privées, cet exemple est divisé en trois phases : configuration, défi et réponse.

Première étape : configurer ###Setup(

À ce stade, l'objectif du prouveur est de créer une preuve qu'il connaît un certain nombre secret s, sans révéler directement s. Soit le nombre secret s;

Choisissez deux grands nombres premiers p et q, et calculez leur produit n. Soit les nombres premiers p et q, calculez n obtenu;

Calculer v=s^2 mod n, ici, v est envoyé au vérificateur comme une partie de la preuve, mais il n'est pas suffisant pour que le vérificateur ou tout observateur puisse déduire s;

Choisissez un entier aléatoire r, calculez x=r^2 mod n et envoyez-le au vérificateur. Cette valeur x est utilisée pour le processus de vérification ultérieur, mais n'expose pas non plus s. Soit r un entier aléatoire, calculez x obtenu.

Deuxième étape : défi )Challenge(

Le validateur choisit aléatoirement un bit a) qui peut être 0 ou 1(, puis l'envoie au prouveur. Ce "défi" détermine les étapes que le prouveur doit suivre ensuite.

Troisième étape : réponse )Response(

Selon la valeur a émise par le validateur, le prouveur répond :

Si a=0, le prouveur envoie g=r) ici r est le nombre choisi aléatoirement par lui auparavant (.

Si a=1, le prouveur calcule g=rs mod n et l'envoie. Supposons que le vérificateur envoie un bit aléatoire a, en fonction de la valeur de a, le prouveur calcule g;

Enfin, le vérificateur utilise g reçu pour vérifier si x est égal à g^2 mod n. Si l'égalité est vraie, le vérificateur accepte cette preuve. Lorsque a=0, le vérificateur calcule x=g^2 mod n, vérification à droite g^2 mod n ; lorsque a=1, le vérificateur calcule x=g^2/v mod n, vérification à droite )rs(^2/s^2 mod n.

Ici, nous voyons que le x calculé par le validateur = g^2 mod n prouve que le prouveur a réussi à passer le processus de vérification, tout en ne révélant pas son nombre secret s. Ici, comme a ne peut prendre que 0 ou 1, il n'y a que deux possibilités, la probabilité que le prouveur réussisse la vérification par chance est de 1/2) lorsque a est 0, (. Mais le validateur défie ensuite le prouveur k fois, le prouveur change constamment les nombres concernés, les soumet au validateur, et réussit toujours à passer le processus de vérification. Ainsi, la probabilité que le prouveur réussisse la vérification par chance devient )1/2(^k) tend vers 0(, ce qui prouve que le prouveur connaît effectivement un certain nombre secret s. Cet exemple prouve l'intégrité, la fiabilité et la propriété de zéro connaissance du système de preuve à connaissance nulle.

Deux, zk-SNARKs non interactifs

) 1. Contexte

zk-SNARKs###ZKP( dans le concept traditionnel, sont généralement sous forme de protocoles interactifs et en ligne ; par exemple, le protocole Sigma nécessite souvent trois à cinq tours d'interaction pour compléter l'authentification. Cependant, dans des scénarios tels que les transactions instantanées ou le vote, il n'y a souvent pas d'opportunité pour plusieurs tours d'interaction, en particulier dans les applications de la technologie Blockchain, où la capacité de vérification hors ligne est particulièrement importante.

) 2. Proposition de NIZK

En 1988, Blum, Feldman et Micali ont proposé pour la première fois le concept de preuve non interactive de connaissance zéro ###NIZK(, prouvant qu'il est possible pour le prouveur )Prover( et le vérificateur )Verifier( de compléter le processus d'authentification sans avoir besoin de plusieurs échanges interactifs. Cette avancée a rendu possibles les transactions instantanées, le vote et les applications Blockchain.

Ils proposent que les zk-SNARKs non interactifs ) NIZK ( peuvent être divisés en trois étapes :

1. Paramètres
2. Calculer
3. Vérification

Dans la phase de configuration, une fonction de calcul est utilisée pour convertir les paramètres de sécurité en connaissances publiques ), que le prouveur et le vérificateur peuvent tous deux obtenir (, généralement encodées dans une chaîne de référence commune ) CRS (. C'est ainsi que la preuve est calculée et que la vérification est effectuée en utilisant les bons paramètres et algorithmes.

La phase de calcul utilise une fonction de calcul, des clés d'entrée et de preuve, et produit le résultat du calcul ainsi que la preuve.

Au stade de la vérification, la validité de la preuve est vérifiée par une clé de vérification.

Le modèle de chaîne de référence publique proposé, )CRS(, repose sur le partage d'une chaîne de caractères par tous les participants pour réaliser des preuves de connaissance nulle non interactives pour les problèmes NP. Le fonctionnement de ce modèle dépend de la génération fiable du CRS, tous les participants devant avoir accès à la même chaîne de caractères. La sécurité des schémas mis en œuvre selon ce modèle ne peut être garantie que si le CRS est généré de manière correcte et sécurisée. Pour un grand nombre de participants, le processus de génération du CRS peut être complexe et long, c'est pourquoi, bien que ces schémas soient généralement faciles à utiliser et que la taille des preuves soit réduite, leur processus de configuration est assez difficile.

Par la suite, la technologie NIZK a connu un développement rapide, donnant lieu à plusieurs méthodes pour transformer les preuves de connaissance zéro interactives en preuves non interactives. Ces méthodes dans la construction du système