De zéro connaissance à une.

J'ai terminé avec succès le programme MINA zkapp Builders , un programme guidé pour aider les développeurs qui souhaitent en savoir plus sur la programmation de contrats intelligents sans connaissance et créer un zkApp pour le protocole Mina. Si vous avez 0 idée sur zk et Mina, vous voudrez peut-être vous diriger vers mon premier zklog .

Après avoir lancé un remue-méninges tangent pour une idée de zkapp, j'ai décidé de créer un jeu de chasse au trésor, que j'ai appelé "zk Schnitzelhunt". (Oui, en Autriche, nous appelons la chasse au trésor une chasse au Schnitzel , je suppose que nous aimons tellement le Schnitzel).

Lien vers le dépôt github :https://github.com/jenpaff/zk-schnitzeljagd
Lien vers l'enregistrement :https://www.youtube.com/watch?v=nA-dpJ_JEF4

Énoncé du problème

Supposons que vous souhaitiez jouer à un jeu de chasse au trésor que vous avez trouvé en ligne, mais que vous ayez plusieurs soucis : 1) le jeu vous demande de partager votre position et vous obtenez un message suspect : "ils veulent sûrement savoir où je suis pour pouvoir m'exposer à de la publicité ciblée ou pire encore à une arnaque. Préoccupation numéro 2) comment pouvez-vous être sûr à 100 % que personne d'autre ne joue au jeu et que les solutions ne sont pas altérées ? Après avoir fait quelques recherches, vous découvrez que le jeu est déclenché par un contrat intelligent- cela signifie donc que l'application est au moins décentralisée et que votre gain sera éternel et immuable, car il interagit avec une blockchain. Puisque vous connaissez une chose ou deux sur les blockchains, vous savez que la plupart d'entre elles sont transparentes et vous commencez à vous poser des questions sur la préoccupation numéro 3) comment pouvez-vous vous assurer que vos solutions ne sont pas exposées aux yeux du public ?

Le zk dans le schnitzelhunt

Le zk signifie zéro connaissance et c'est ce qui vous permet de prouver (cryptographiquement) que vous avez terminé le jeu avec succès tout en gardant les solutions ainsi que votre emplacement partagé privés.

Comment fonctionne zk schnitzelhunt : Pour terminer le jeu, un utilisateur devra résoudre 3 énigmes. Pour résoudre chaque énigme, un utilisateur partage sa position via son navigateur utilisé. Si l'emplacement est correct, l'utilisateur se verra présenter la prochaine énigme jusqu'à ce qu'il ait résolu toutes les énigmes. L'évaluation si l'emplacement que vous partagez est correct, se produit hors chaîne , c'est-à-dire que l'emplacement que vous partagez ne quitte jamais votre navigateur. Si l'emplacement que vous avez partagé se situe dans la plage valide, une preuve de connaissance nulle sera générée. Seule la résolution de toutes les énigmes complètera le jeu.

Mise en œuvre technique

Paramètres de décision de conception

1. au moment du développement un compte zkapp fournit 8 champs de 32 octets
2. toutes les fonctions utilisées dans un contrat intelligent doivent fonctionner sur des types de données compatibles SnarkyJS
3. capacité à résoudre une énigme dans une plage valide (boîte englobante)

Comme nous ne pouvons pas nous attendre à ce que l'utilisateur atteigne le point géographique exact (longitude/latitude) de l'objet en question, nous devons autoriser un plus large éventail de points de localisation (c'est-à-dire une boîte englobante). Chaque énigme a donc une boîte englobante dédiée.

En raison de la nature des zkapps, nous sommes liés par deux paramètres mentionnés ci-dessus.

Pour se conformer au n ° 1, nous ne stockons que la racine d'un arbre Merkle sur la chaîne. L'arbre merkle contiendra les hachages de tous les points de localisation possibles que nous autorisons dans la boîte englobante donnée, en stockant la racine de l'arbre merkle, nous pouvons les stocker hors chaîne et toujours utiliser la racine pour vérifier que les données hors chaîne étaient ' t altéré.

En ce qui concerne le paramètre de décision de conception n ° 2, nous devons transformer nos données de localisation, car les points de longitude/latitude sont généralement décrits comme des nombres à virgule flottante qui ne font pas partie des types de données compatibles SnarkyJS . En effet, chaque @methoddéfinit un circuit zk-SNARK sous le capot, nous ne sommes donc limités qu'à certains types par conception. Heureusement, il existe en fait un autre moyen agréable de définir un emplacement, à savoir les géohachages. Je n'entrerai pas trop dans les détails, mais à un niveau élevé, le géohash est un système de géocodage qui représente une zone d'un point géographique. La façon dont cela fonctionne est que nous divisons récursivement le monde en deux, par exemple d'abord verticalement, puis donnons à chaque moitié une valeur binaire de 0 ou 1 selon que l'emplacement en question tombe dans la moitié ou non. Le géohash représentera alors une adresse de la zone vers laquelle nous voulons pointer, plus nous voulons zoomer, plus notre géohash devient long. En réalité, notre géohash est limité au nombre de bits dont nous disposons sur notre système (par exemple avec javascript ce serait 52-bit), nous devons donc nous assurer que nous utilisons la même précision à tout moment pour rester cohérents.

Qu'y a-t-il de si intelligent dans le contrat ?

Lors de ma première itération, j'ai développé mon zkapp pour générer et soumettre une preuve après chaque énigme. Le contrat vérifie l'emplacement partagé en vérifiant s'il s'agit d'une entrée valide dans l'arborescence Merkle donnée.

Étant donné que zk schnitzeljagd constitue un bon cas d'utilisation pour la récursivité, j'ai décidé de me lancer dans l'utilisation de la fonctionnalité expérimentale (encore à l'époque) à savoir les contrats récursifs .

"Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité" disent-ils et ils ont raison. Cela peut être un peu long, mais en un mot, cela fonctionne comme ceci : au lieu de générer une preuve et de la soumettre en chaîne à chaque fois que nous résolvons une énigme, nous générons la preuve et l'intégrons à la preuve suivante. Pensez-y comme si nous emballions un cadeau (vous pouvez dire que c'est Noël au moment de l'écriture) et à chaque itération, j'enveloppe ma preuve précédente avec la prochaine preuve et une fois que j'ai fini d'emballer, je soumets mes preuves emballées sur -chaîne en une seule transaction permettant d'économiser du temps et des coûts de transaction.

Qu'y a-t-il sous le capot ? Les fonctions sous-jacentes de Mina

Je n'essaierai même pas ou ne prétendrai pas que je pourrais résumer le livre MINA décrivant les fonctions sous-jacentes pour prendre en charge les applications sans connaissance, mais il y a quelques choses que j'ai trouvé utiles à comprendre :

Comment les zkSNARKS sont-ils générés ?

Je vais écrire un article de blog entier à ce sujet (qui pourrait facilement être un livre). En un mot, pour transformer votre programme en zkSNARK, vous devez suivre un processus en 3 étapes :

1. Aplatissement de code (circuit arithmétique)
2. Conversion en un système de contraintes de rang 1 (RCS1)
3. Polynômes

Vous n'avez pas besoin de comprendre chaque étape, mais cela devrait mettre en évidence la complexité et la raison pour laquelle le développement de zk nous oblige à travailler avec certains compilateurs sous le capot afin que nous nous retrouvions dans le format qui nous aidera à produire zkSNARKS.

Quelles sont les fonctions sous-jacentes sur MINA pour générer zkSNARKS ?

Les Zkapps sur MINA sont écrits en tapuscrit à l'aide de SnarkyJS, une bibliothèque que vous utiliserez pour écrire votre contrat intelligent sans connaissance. SnarkyJS est compilé snarky- une interface OCaml pour écrire des SNARK R1CS - qui se traduira essentiellement par le circuit. Parce qu'OCaml peut être assez fastidieux, SnarkyJS est né pour offrir un wrapper autour de la bibliothèque snarky.

Les circuits sont vérifiés par le système de vérification kimchi. Kimchi est un protocole plonk-ish, ce qui signifie qu'il s'agit d'une variante de Plonk - un système de preuve largement utilisé. Habituellement, Plonk nécessite une configuration de confiance, mais grâce aux dernières recherches, MINA a également pu utiliser le schéma d'engagement polynomial du produit interne (ou argument du produit interne ou IPA) qui permet une configuration transparente pour le zkSNARKS (c'est-à-dire au revoir configuration de confiance cérémonies).

Lorsqu'un développeur zkApp construit son contrat intelligent, il se retrouve avec un fichier sudoko.js. En utilisant cela, ils généreront d'abord une clé de vérification qu'ils déploieront avec leur zkapp. La clé de vérification vit en chaîne pour un compte zkApp donné et est utilisée par le réseau Mina pour vérifier qu'une preuve à connaissance nulle a satisfait à toutes les contraintes définies dans le prouveur. L'utilisateur du zkapp exécutera la fonction de preuve dans son navigateur Web et générera une clé de preuve . Kimchi est la partie de la pile qui compile réellement le programme dans les deux clés.

Donc, pour résumer : nous utilisons snarkyJS pour écrire le programme, snarky pour générer les circuits à partir de snarkyJS et Kimchi pour les compiler en clé de vérification et de preuve qui sont utilisées pour leur objectif respectif.

Si vous vouliez aller encore plus loin dans la pile…

Vous trouverez bientôt pickles , la couche de récursivité qui nous permet de générer des preuves de preuves et c'est la raison pour laquelle MINA peut rester aussi petit que 22 Ko . Pickles est un protocole halo-ish, donc une variante du protocole Halo . C'est nécessaire car Kimchi seul ne permettrait pas la récursivité, donc les cornichons viennent à la rescousse.

Si vous regardez plus loin, vous trouverez des courbes de pâtes, les deux fameuses courbes largement utilisées dans l'écosystème zk. Si vous avez remarqué le type Fieldau lieu d' U32Intêtre utilisé, par exemple, dans les contrats intelligents zk, les courbes de pâtes sont la raison pour laquelle nous devons spécifier nos types en tant que champs. La cryptographie à courbe elliptique est ce qui nous permet de préserver le secret de nos entrées privées, puisque nous chiffrerons nos entrées et exécuterons ensuite des calculs dessus .

Et si vous osez aller tout en bas, vous trouverez bientôt arkworks , un écosystème Rust pour la programmation zkSNARK. Les bibliothèques de l' arkworksécosystème fournissent des implémentations efficaces de tous les composants nécessaires à l'implémentation des applications zkSNARK, des champs finis génériques aux contraintes R1CS pour les fonctionnalités communes.

Au moment de l'écriture, Kimchi était écrit en Rust, tandis que snarky et pickles sont réécrits d'OCaml en Rust.

…Sommes-nous déjà là?

Certains bloqueurs

Il y a plusieurs raisons pour lesquelles ce jeu n'est pas déployé sur le testnet de Berkely, dont l'une est certainement que l'interface n'est pas mon point fort. Un autre était qu'en essayant de mettre à niveau vers la dernière version 0.7.x de snarkyJS, j'ai découvert un bogue qui signifiait que je n'aurais pas pu déployer la version récursive du contrat intelligent.

Le temps, c'est de l'argent

Autant j'aime mon zk schnitzelhunt, autant générer les preuves prend encore beaucoup de temps, surtout sur une machine Apple M1 (il y a un bug qui sera corrigé pour améliorer les performances ) ce qui signifie que dans un bon jour j'ai enregistré 162,639 sec pour la génération de preuve et le jour de la mauvaise pomme 326.431 sec. Soyons honnêtes, je clique déjà sur Actualiser si je n'obtiens pas de réponse dans un délai d'une seconde sur un site Web - et je suis quelqu'un qui a été témoin du son de l'Internet commuté.

Faites semblant jusqu'à ce que vous le fassiez

Si vous avez l'esprit hacker, vous avez peut-être déjà découvert l'énorme bogue de conception dans zk schnitzelhunt, à savoir la possibilité de falsifier les données d'entrée tout en créant des preuves zk valides . Étant donné que les données GPS peuvent être facilement usurpées (par exemple, à des fins de test, j'ai utilisé une extension Chrome pour le faire), le simple fait de se fier à l'entrée de l'utilisateur ne suffira pas, surtout s'il est essentiel pour votre cas d'utilisation que l'utilisateur se trouve à l'emplacement spécifié. . Il existe plusieurs façons de résoudre ce problème, par exemple FOAMest un projet d'installation de balises radio qui offriraient des services de localisation sécurisés. Une autre façon intéressante serait de tirer parti de plusieurs capteurs sur l'appareil pour vérifier la proximité des utilisateurs avec l'objet en question ou de vérifier une signature numérique, par exemple une photo prise de l'emplacement en question. Cependant, tout cela aurait été bien au-delà de la portée de mon programme de constructeurs.

Remarques finales

Même si le temps de prouver est beaucoup trop long pour mon cerveau millénaire, je suis vraiment optimiste sur zk tech. L'espace se déplace incroyablement vite, si vite que le matériel d'apprentissage semble rapidement obsolète (« comme quoi - vous pouvez avoir des zkSNARKS transparents ? » ). Et je crois vraiment que cela débloquera des cas d'utilisation très intéressants parmi lesquels la confidentialité est certainement ma préférée.

Enfin, je tiens à remercier O(1) labs & la fondation Mina de m'avoir donné l'opportunité de faire partie de ce programme incroyable et de m'avoir soutenu dans le voyage de zéro connaissance à une ❤️.

Ressources

• MINA BOOK —profondeur du système de vérification de MINA
• Comprendre l'ECC dans zkSNARKS
• Comprendre les fonctions sous-jacentes de MINA

• ensemble de ressources organisé par a16z
• Podcast Zero-Knowledge par Anna Rose
• Session de tableau blanc ZKHack