Etude de cas d'utilisation de Zero Knowledge Proof (ZKP)

le 07/12/2021 par Aymeric NOËL
Tags: Cloud & Platform

INTRODUCTION

Depuis 1976, date de l'implémentation de la cryptographie asymétrique par Whitfield Diffie et Martin Hellman, la cryptographie ne cesse d'évoluer et de se réinventer pour être toujours plus performante et impressionnante. Il faut dire que le fait de chiffrer une donnée avec une clé publique pour que seule la personne en possession de la clé privée associée puisse la déchiffrer, était une révolution par rapport à tous les moyens de chiffrement de l'époque.

C'est dans ce contexte qu'en 1985 le Zero Knowledge Proof voit le jour. Le Zero Knowledge Proof (preuve à divulgation nulle de connaissances en français), autrement appelé ZKP, est un procédé cryptographique introduit par une chercheuse du nom de Shafi Goldwasser et permettant de prouver une assertion sans en révéler directement le contenu.  Son protocole évolua par la suite en fonction des différentes thèses réalisées sur ce sujet...

Durant de nombreuses années, ce procédé était méconnu du grand public et reposait uniquement sur les papiers de différents chercheurs. Cependant depuis 2017, le ZKP a été remis au goût du jour grâce à son utilisation, en production, par de nombreux projets blockchain.

Dans cet article, nous verrons dans un premier temps ce qu'est en détail le Zero Knowledge Proof, ainsi que ses limites, puis nous verrons une étude de cas de preuve d'identité, appliquée à la blockchain.

1) Qu'est-ce que le ZKP et quelles sont ses limites ?

Pour illustrer simplement le ZKP, prenons l'exemple du célèbre livre "Où est Charlie ?" consistant à trouver un personnage nommé Charlie parmi une multitude d'autres personnages et de dessins. Si je veux prouver à un tiers que j'ai bien trouvé Charlie sans pour autant révéler sa position sur la page, je peux prendre une feuille de papier plus grande que le livre et faire un trou pour la tête de Charlie, ainsi je prouve bien que j'ai trouvé Charlie sans fournir sa position exacte !

Le ZKP a un fonctionnement analogue car c'est un procédé permettant de prouver une assertion numérique sans pour autant révéler son contenu. On peut, par exemple, prouver que a*b=15, sans pour autant révéler a et b, qui sont ici 5 et 3.

Pour être une technologie Zero Knowledge Proof, le protocole implémenté doit avoir 3 caractéristiques :

  • Integrity and completeness : Si l'affirmation est vraie, et que les deux parties suivent le protocole, le vérificateur ne pourra douter de l'affirmation
  • Soundness and robust : Le protocole implique une honnêteté nulle ou faible. De ce fait, si l'affirmation est fausse, il n'y aura aucun moyen de convaincre le vérificateur
  • Zero Knowledge : Aucune information, autre qu'une ou plusieurs preuves, ne sera échangée durant le protocole

Il existe deux grands types de ZKP : l'interactive ZKP (IZKP) et le Non-Interactive ZKP (NIZKP).

Le IZKP consiste à un échange de preuves entre un vérificateur et un prouveur, c'est le premier protocole ZKP qui a vu le jour car plus simple à mettre en place au niveau cryptographique.

Le NIZKP consiste en une création de preuve unique qui sera à la disposition de tous ceux qui souhaitent effectuer une vérification. Ce type est le seul utilisé en production aujourd'hui car il est plus performant du fait qu'il soit plus scalable (1) car les utilisateurs n'ont pas besoin d'être connectés tout le temps, plus rapide et plus accessible pour un vaste projet.


Illustration du IZKP


Illustration du NIZKP

Il existe plus de 8 types de protocoles NIZKP aujourd'hui, notamment le Fiat Shamir heuristic (1986), le Blum-Feldman-Micali (1988), le De Santis-DiCrescenzo-Persiano-Blum (2002), le Groth-Ostrovsky-Sahai (2006), le Groth-Sahai Proof System (2008), le zk-SNARK (2012), le BulletProofs (2017), le zk-STARK (2018) et le Libra (2019), qui n'est pas la célèbre monnaie numérique de Facebook.

Les implémentations des premiers protocoles, Blum-Feldman-Micali et De Santis-DiCrescenzo-Persiano-Blum,  ont été cassées, autrement dit les preuves ont pu être falsifiées et/ou les vérifications n'ont pas abouties, ce qui signifie que les preuves générées étaient incorrectes.

D'autres systèmes n'ont jamais été implémentés, comme les protocoles Groth-Sahai Proof System et Groth-Ostrovsky-Sahai.

Les principaux protocoles sont le zk-SNARK, le BulletProofs et le zk-STARK :


Temps de mesure des principaux protocoles NIZKP. Ces mesures sont indicatives, elles changent en fonction de l'algorithme et de la puissance de l'ordinateur.

Étant donné que cet article présente toutes les facettes de cette technologie, il convient aussi de dresser ses limites.

Limites liées à la sécurité des protocoles :

  • Certains protocoles sont sensibles aux attaques par ordinateur quantique.
  • D'autres ont des setups initiaux, qui ne doivent pas tomber entre de mauvaises mains, pour éviter la génération de fausses preuves.

Limites liées à la mise en place des protocoles :

  • Le temps de création/vérification de preuves peut être long, parfois très long, cela rend le ZKP non scalable.
  • Le processus de création/vérification de preuves peut être coûteux en énergie, ce qui rend les implémentations sur smartphone impossible pour le moment.
  • On ne prouve pas des faits mais des assertions numériques. C'est un point important car on peut prouver que a*b=15 est vrai, sans pour autant révéler a et b mais on ne peut pas prouver que telle personne se prénomme bien Bob sans pour autant révéler son nom.

Limites liées à la complexité des protocoles :

  • Il faut un niveau élevé de connaissances car les librairies sont complexes.
  • Petite communauté en cas de blocages.
  • Pas de standards entre les différents protocoles, ce qui ralentit l'adoption de cette technologie. Un collectif essaye de remédier à cela : https://zkproof.org/.

2) Etude de cas : Comment mettre en place un 2FA sur blockchain ?

Dans son rapport publié en décembre 2018, la mission d’information commune de l’Assemblée nationale sur les usages des chaînes de blocs et autres technologies de certification de registre donne la définition suivante de la blockchain :

"Une blockchain est un registre, une grande base de données qui a la particularité d’être partagée simultanément avec tous ses utilisateurs, tous également détenteurs de ce registre, et qui ont également tous la capacité d’y inscrire des données, selon des règles spécifiques fixées par un protocole informatique très bien sécurisé grâce à la cryptographie."

Au sein de la blockchain, chaque utilisateur est identifié avec une clé publique, cela peut être assimilé à une boîte postale. Pour interagir avec la blockchain, chaque utilisateur doit signer ses transactions avec la clé privée associée à sa clé publique.

Voici un exemple de clé privée : "0x8da4ef21b864d2cc526dbdb2a120bd2874c36c9d0a1fb7f8c63d7f7a8b41de8f".

Les clés privées sont longues et difficiles à retenir, c'est pourquoi bien souvent les utilisateurs font de simples copier/coller dans des fichiers textes ou les notent sur papier. La première solution est propice aux vols et aux piratages, ce qui met en danger l'ensemble des fonds détenus d'un utilisateur.

Il convient donc de mettre en place un système sécurisé permettant de vérifier que celui qui interagit avec la blockchain est bien le propriétaire de la clé privée qui a signé la transaction, à savoir un Two Factor Authentication (2FA).


Illustration d'un 2FA

Hors blockchain, les 2FA sont assez faciles à mettre en place. Les principaux moyens sont :

  • SMS : Lors de la connexion, un sms contenant un code aléatoire va être envoyé à l'utilisateur. Celui-ci sera requis lors de l'authentification. Si le code entré sur le site est correct alors il s'agit de l'utilisateur légitime. Cette méthode sous-entend que le site tourne sur un serveur sécurisé pouvant stocker provisoirement le code aléatoire car s'il tombait entre de mauvaises mains, quiconque possédant le mot de passe de l'utilisateur pourrait se connecter.
  • Email : Fonctionnement identique à celui par sms, mais le code aléatoire est envoyé par mail.
  • Application mobile : Fonctionnement analogue à celui par sms, sauf que le code est généré sur application mobile. Il existe plusieurs applications de ce type comme Google authenticator, par exemple_._

Ce qui nous donne le problème suivant : Comment mettre en place un 2FA sur blockchain sachant que toutes les données sont transparentes et qu'il n'est pas possible de faire des appels vers des systèmes extérieurs à l'écosystème, dans le but de requêter une base de données ?

Je me suis penché sur cette question dans le contexte d'un sujet de R&D chez OCTO Technology de 6 mois et ai trouvé une solution que j'ai pu implémenter.

Pour comprendre cette solution, il faut comprendre le fonctionnement d'une fonction de hachage.


Illustration d'une fonction de hachage

Une fonction de hachage est une fonction cryptographique qui prend en entrée une préimage, pouvant être n'importe quelle chaîne de caractère et ressort un hash hexadécimal unique de taille fixe.  Par exemple, le hash, en SHA256, du mot "maison" sera toujours "0x32d2f1f71cfc1913e32c0738f1027a4e85acf9fac3bf26148820d5b363bc319b".  De plus, à partir de ce hash, il sera impossible de remonter au mot "maison". Il existe plusieurs fonctions de hachages différentes, cependant nous utiliserons ici SHA256 qui est une fonction de hachage robuste et non cassée à l'heure actuelle.

Etant donné que chaque préimage a un unique hash, si je hash mon mot de passe et que je suis capable de créer une preuve ZKP que je connais bien la préimage de ce hash, alors implicitement, j'aurais prouvé que je connais bien mon mot de passe.

Il faut rappeler qu'une telle preuve ZKP est créée à partir du mot de passe mais que depuis la preuve, il est impossible de remonter au mot de passe.

J'ai appliqué ce principe a une plateforme de location de jardins, décentralisée, sur la blockchain Ethereum. Le choix de cette blockchain a été motivé par le fait que le langage d'écriture des smart contracts(2) sur Ethereum est puissant et moderne, et qu'il existe une librairie compatible, ZoKrates, permettant de créer et vérifier des preuves ZKP. Dans le but de pouvoir interagir avec la plateforme, le propriétaire d'un jardin devra fournir une preuve qu'il est bien en possession de son mot de passe en plus de signer ses transactions.

Comment se passe la génération de preuves de connaissance de mot de passe ?

  1. L*'utilisateur enregistre le hash de son mot de passe sur la blockchain.*


Création d'un jardin sur la plateforme nécessitant l'enregistrement du mot de passe

  1. Sur un site web dédié, que j'ai développé, il va créer une preuve de connaissance de préimage en entrant son mot de passe. Il est important de préciser que le mot de passe ne quitte jamais l'ordinateur de l'utilisateur, tout se passe en local dans le navigateur, il n'y a pas d'appel vers un serveur. Cette preuve est ensuite envoyée sur la blockchain via une transaction(3) signée par l'utilisateur.


Proposition d'offre de location en envoyant une preuve de mot de passe ZKP

  1. La preuve va alors être vérifiée sur la blockchain. Si elle est valide, alors la transaction de l'utilisateur est acceptée, dans le cas contraire elle est rejetée.

Voici un exemple de preuve ZKP, générée à partir d'un mot de passe, c'est un fichier json(4) :


Génération de preuve à partir de la librairie Zokrates

L'objet proof contient trois champs a****, b et c****, ils sont le résultat de diverses opérations cryptographiques sur le mot de passe. Inputs est le hash du mot de passe, généré automatiquement par la librairie Zokrates dans le fichier, cependant nous n'en avons pas besoin car il est déjà stocké sur la blockchain. proof est directement reliée au hash du mot de passe, de façon cryptographique**.** Ainsi, en envoyant cette preuve sur la blockchain, il sera vérifié que a, b et c correspondent bien au hash associé à l'utilisateur effectuant la transaction.

Précisons tout de même que ce fichier fait office de mot de passe et qu'il ne faut donc pas le rendre public. Le cas échéant, il conviendra tout simplement de changer de mot de passe, en changeant le hash enregistré sur la blockchain.

Fonctionnement de la vérification de preuve :

  1. Création de la transaction à envoyer sur la blockchain


Contenu d'une transaction

  1. Vérification de la transaction


Vérification de la transaction sur la blockchain

On a ici un 2FA car l'utilisateur devra d'une part prouver qu'il connaît bel et bien son mot de passe et d'autre part il devra signer la transaction avec sa clé privée.

Cette solution permet de contrer les nombreux vols de clés privées blockchain car en ne possédant que la clé privée, l'usurpateur ne sera pas en mesure d'accéder ou d'interagir avec du contenu qui ne lui est pas destiné.

Ce système comporte tout de même quelques limitations car il assure un 2FA uniquement pour les interactions avec les smart contracts. Par conséquent, le 2FA peut être appliqué pour tous les transferts de tokens (ERC20(5), ERC721), c'est-à-dire de jetons créés par smart contracts et répondant à un certain type de standard, et les appels vers les protocoles décentralisés tels que Uniswap, Aave, etc… Mais non sur les envois d'Ether ou de Bitcoin qui ne sont pas gérés via smart contracts.

Conclusion

Zero knowledge Proof (ZKP) est une technologie remarquable qui doit encore faire ses preuves. En effet, aujourd'hui le ZKP est très peu utilisé pour plusieurs raisons énoncées plus haut, notamment à cause du manque de développeurs sur ce sujet complexe. Cependant, les cas d'utilisation de cette technologie sont de plus en plus nombreux, principalement dans le domaine de la blockchain.

De nos jours, pour intégrer un protocole Zero Knowledge Proof sur une blockchain, il y a différents moyens :

  • Intégrer nativement le ZKP à a blockchain comme le fait Zcash
  • Intégrer le ZKP après un update/fork de la blockchain, comme va le faire Tezos avec son update EDO. Cela nécessite donc de devoir mettre à jour la blockchain, ce qui peut s'avérer difficile en fonction de la blockchain utilisé car bien souvent il faut un accord et une approbation de la communauté
  • Intégrer le ZKP via un layer 2(6), c'est-à-dire ajouter un protocole sur le noyau de la blockchain, comme les Zk-Rollups sur la blockchain ethereum. Pour cela, il faut que la blockchain puisse supporter les surcouches. Cela permet notamment de rendre une blockchain plus scalable et de réduire considérablement les frais de transaction
  • Intégrer le ZKP via des smart contracts comme le fait la librairie ZoKrates sur la blockchain ethereum. Pour cela, il faut que la blockchain supporte l'implémentation et l'exécution de smart contracts

Si l'on veut intégrer une technologie ZKP sur une blockchain, il faut impérativement passer par une de ces 4 étapes. Il sera donc plus ou moins facile d'intégrer le ZKP en fonction du mode de fonctionnement de la blockchain. Une intégration sur bitcoin par exemple serait plus compliqué car il faudrait un fork de la blockchain et une proposition d'amélioration, un BIP (Bitcoin Improvement Proposal), ce qui prendrait du temps.

Pour aller plus loin

(1) Scalable : Se dit d'un système informatique pouvant s'adapter en fonction de la demande. Un système scalable aura une performance stable malgré le fait qu'il soit utilisé par 10 ou 100 000 personnes.

(2) Smart contract : Les smart contracts, sont des programmes informatiques immuables, le plus souvent déployés sur la blockchain Ethereum, qui exécutent un ensemble d’instructions prédéfinies.

(3) Transaction : Interaction avec la blockchain.

(4) Json : Le JavaScript Object Notation (JSON) est un format standard utilisé pour représenter des données structurées de façon semblable aux objets Javascript.

(5) ERC20 : Standard d'écriture de smart contracts de  tokens sur la blockchain Ethereum.

(6) Layer 2 : Surcouche sur un réseau blockchain permettant de diminuer les frais de transactions et en ajoutant des fonctionnalités d'anonymat.