Zk-SNARKs, FreeTON et OCamlPro
Vous avez peut-être entendu parler des zk-SNARKs, magie noire mathématique permettant, sous certaines conditions, de prouver que vous connaissez une solution à un problème sans révéler la moindre information sur cette solution: on appelle une telle preuve, une preuve zero-knowledge. C’était autrefois un amusement (surtout) théorique pour cryptologues ; depuis Zcash, c’est devenu une application bien réelle sur les blockchains, permettant de cacher complètement des transferts de crypto-monnaies. De nombreux projets sont en train d’intégrer une forme ou une autre de zk-SNARKs, comme par exemple Ethereum, Tezos ou Concordium. Le projet Mina construit même toute sa blockchain à partir des zk-SNARKs !
L’année dernière, grâce à notre langage de programmation Liquidity, nous avions commencé à adapter et étendre les zk-SNARKs de Tezos dans la blockchain Dune Network, qui est aujourd’hui en voie de fusion avec la blockchain FreeTON. Avec l’introduction des zk-SNARKs sur FreeTON par la Nil Foundation, il était temps de s’y remettre ! Nous avons participé ces dernières semaines au Contest DevEx 18 à l’occasion duquel nous devions proposer des applications des zk-SNARKs sur les smart contracts FreeTON. Le classement n’est pas encore connu, mais nous sommes fiers de vous présenter notre soumission qui contient trois applications différentes !
Vérification de Sudokus Cachés
Notre première application consiste en un smart contract de vérification de Sudokus. Le Sudoku est un peu aux preuves zero-knowledge ce que le Pierre-Feuille-Ciseau est aux smart contracts: un exemple simple, utile pour expliquer le concept en question, mais suffisamment embêtant pour poser déjà quelques problèmes techniques. Il faut notamment trouver un encodage des contraintes du Sudoku sous forme de programme quadratique (détails dans notre soumission pour les curieux). Ensuite, le principe est simple: une instance de Sudoku est proposée par le contrat, et l’utilisateur doit trouver une solution, générer localement une preuve zero-knowledge qu’il l’a trouvée, et la soumettre au contrat. Ainsi, il prouve qu’il l’a résolu, sans fournir la solution aux autres utilisateurs !
Infrastructure pour le Projet Euler
Project Euler est peut-être le site sur lequel j’ai le plus appris à programmer. Il soumet des problèmes mêlant mathématiques et informatique et de difficulté très variable (le premier problème a été résolu par un million de personnes ; certains n’ont qu’une dizaine de solutions à leur sortie). Pour éviter les attaques brute-force qui consisteraient à tester toutes les solutions possibles à un problème, le site utilise un système de captchas. Comment décentraliser Project Euler ? Les deux problèmes principaux résident
- dans la vérification des solutions sans les révéler dans le smart contract, soit à l’avance dans la fonction de vérification, soit par la suite après la soumission de la réponse ;
- dans le fait de décourager le brute-force.
Les zk-SNARKs sont une réponse parfaite au premier problème, puisqu’ils permettent de vérifier une solution sans la révéler. Quant au second problème, nous avons choisi l’approche suivante : chaque problème est muni d’un nonce aléatoire à sa création. La solution stockée (mais obfusquée par les zk-SNARKs) dans le contrat est en réalité :
SHA256¹⁰⁰⁰⁰⁰⁰(numéro du problème | solution | nonce)
Calculer un million d’itérations de SHA256 prend environ 20 secondes, ce qui émule en quelque sorte le captcha. Cela ne protège pas, en revanche, contre un pré-calcul de toutes les solutions possibles, d’où la présence du nonce et du numéro de problème qui compliquent singulièrement la tâche de l’attaquant. Par ce simple tour de passe-passe, on peut complètement décentraliser la plate-forme de soumission de Project Euler!
Au final, notre solution permet de facilement créer de nouveaux problèmes en ligne, d’obtenir pour chaque problème un TOP10 des premiers à l’avoir résolu, et de conserver, pour chaque utilisateur, la liste de tous les problèmes qu’il a résolu… sans jamais qu’aucune solution ne soit révélée !
Récupération de la Perte d’une Clé Secrète via une Passphrase
Notre dernier cas d’utilisation des zk-SNARKs sur FreeTON est plus technique : il s’agit de proposer une solution de secours pour changer de clé publique quand on a perdu la clé secrète correspondante. Une solution commune pour se prémunir de la perte d’une clé privée est le multisig, et d’ailleurs les wallets FreeTON sont multisig par défaut. Il s’agit alors de conserver en lieu sûr, typiquement dans le coffre-fort d’une banque (c’est un paradoxe du monde des cryptomonnaies…) la clé de récupération. Or c’est une solution compliquée à mettre en oeuvre, lente à récupérer, qu’au final, peu de gens prennent le temps de mettre en place… prenant ainsi des risques considérables !
Nous proposons donc une alternative simple et pratique à base de sk-SNARKs : choisir un mot de passe permettant de changer la clé publique qui contrôle un wallet, et n’importe quel contrat compatible. Cette solution est à proscrire en l’absence des zk-SNARKS: le mot de passe (ou son hash) pourrait être intercepté et réutilisé par un attaquant pour détourner le wallet à son avantage. Dans le cadre des zk-SNARKs, la preuve zero-knowledge atteste la connaissance du mot de passe couplée avec la clé publique, de sorte que cette preuve est inutilisable avec une autre clé publique.
Conclusion
Participer à ce contest au demeurant très amusant nous a permis de réfléchir aux différentes utilisations des zk-SNARKs sur la blockchain. Bien que cette première étape reste beaucoup plus simple que les applications à la Z-cash, qui font l’objet de contests séparés, nous avons déjà identifié différentes catégories :
- Calcul (un calcul mathématique précis est encodé dans l’instance de zk-SNARK utilisée) : c’est le cas du Sudoku, ça aurait pu être la factorisation d’un entier par exemple ;
- Statique : la réponse statique est connue, et on se contente de vérifier que l’utilisateur la connaît (en se prémunissant éventuellement d’un brute-force): c’est le cas du Project Euler ;
- Protocole : L’essentiel de la fonction du zk-SNARK peut être un calcul ou statique, mais l’enjeu essentiel est d’agir au niveau du protocole en déclenchant des transactions ou en modifiant des droits d’accès : c’est le cas du Pincode.
On voit aisément que ces catégories ne sont pas imperméables entre elles, mais elles permettent de penser des paradigmes d’utilisation.
Souhaitez-nous bonne chance pour le vote à venir et n’hésitez pas à nous poser des questions en commentaire ou sur twitter!
Si vous voulez en savoir plus sur FreeTON, vous pouvez notamment aller voir notre site www.freeton.link et essayer notre wallet en OCaml ft/freeton_wallet.
