Zero Knowledge Proofs : Prenez le contrôle de vos données privées !

Sur Internet aujourd'hui, il est parfois nécessaire, pour accéder à certains services, de prouver son identité, son âge, sa nationalité, ...

Pour cela, nous sommes amenés à confier des données personnelles à des tiers fournisseurs de services, qui peuvent aller jusqu'à demander une carte d'identité, un passeport, une adresse postale, ...

De manière générale, les données privées sont l'or numérique de l'Internet aujourd'hui, et nous aimerions bien pouvoir contrôler davantage ce à quoi les tiers à qui nous faisons confiance ont accès et ce qu'ils en font.

En quoi les ZKPs peuvent-elles apporter une solution à cela ?

Les Zero Knowledge Proofs, ou Preuves à Zéro Connaissance, sont une solution technologique qui permet de prouver la validité d'une assertion sans avoir à révéler les données servant de collatéral pour la démontrer.

Pour l'expliquer simplement, vous pouvez démontrer, par exemple, que vous habitez en France, sans révéler ni votre adresse postale, ni même votre ville de résidence, et évidemment sans avoir à fournir de justificatif de domicile d'aucune sorte.

Ce concept ne date pas d'hier, puisqu'il a été introduit en 1989 dans le cadre d'une publication scientifique (https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf), mais nous verrons pourquoi aujourd'hui il devient plus facile et intéressant à implémenter.

Mais quelle est cette magie noire ?

Dans un protocole de ZKP, il y a 3 acteurs principaux :

Le "Prover" : C'est celui qui est en possession des éléments démontrant une déclaration.
Le "Verifier" : C'est celui qui est chargé de vérifier la validité d'une déclaration et d'en fournir la preuve au Challenger.
Le "Challenger" : C'est celui qui demande une preuve d'une déclaration.

Dans ce cadre, nous avons donc 3 éléments utilisés par ces acteurs :

L'affirmation (appelée "witness" en anglais) : Par exemple : "J'ai plus de 20 ans".
La preuve : Qui indique si oui ou non la déclaration est exacte.
Les secrets : Les éléments secrets en possession du "Prover".

L'important dans un protocole de ZKP est que ni le Challenger, ni le Verifier ne sachent jamais quels sont précisément les collatéraux en possession du Prover.

Le Challenger fait confiance au Verifier, et le Verifier s'assure, à l'aide d'une question, d'une épreuve ou d'une série de questions ou d'épreuves soumises au Prover, que ce dernier dispose bien d'éléments démontrant la déclaration.

Qu'est-ce qui permet de faire confiance au Verifier ?

Pour comprendre comment un Verifier fait pour valider une déclaration, sans même connaître la donnée secrète, il faut introduire trois facteurs importants :

La complétude (completeness) : C'est lorsqu'un vérificateur honnête atteint un niveau de probabilité très élevé de la véracité de la déclaration par un Prover honnête.
La solidité (soundness) : C'est lorsque la probabilité qu'un tricheur arrive à démontrer la véracité d'une déclaration fausse est extrêmement faible.
Zéro connaissance : C'est le fait que personne n'ait connaissance des éléments secrets en dehors du détenteur (Prover) de ceux-ci. Même le vérificateur ne peut pas en avoir connaissance. Un protocole à zéro connaissance doit donc permettre à un vérificateur de déterminer la véracité d'une déclaration sans qu'il ait besoin d'avoir accès aux éléments secrets.

Un exemple pour mieux comprendre

‍

‍

Imaginons que vous ayez un ami nommé Anthony qui est daltonien et ne sait pas distinguer le rouge du vert. Vous prenez deux balles, une rouge, une verte, qui, en dehors de leur couleur, sont identiques.

Bertrand, qui lui n'est pas daltonien, souhaite prouver (jouant donc le rôle de "prover") à Anthony (jouant alors le rôle de "challenger") que les balles sont bien différentes et que ce qui les distingue est leur couleur, et rien d'autre. Vous souhaitez y parvenir sans jamais révéler à Anthony quelle est la balle rouge et quelle est la balle verte.

Pour ce faire, le verifier lui soumet des épreuves ("challenges") : Vous donnez les deux balles à Anthony, qui les cache derrière son dos. Ensuite, il va montrer chaque balle l'une après l'autre à Bertrand, qui est chargé de lui dire s'il a changé de balle. Ce protocole est répété plusieurs dizaines de fois.

Comme la personne lui répondant n'est pas daltonienne, elle sait à coup sûr lui répondre si oui ou non il a changé de balle. Anthony peut savoir si l'affirmation que les balles sont différentes en couleurs est exacte ou non, en tenant compte du fait que si elle répondait totalement au hasard, la probabilité qu'elle tombe juste à toutes les questions serait de 50% à chaque essai.

En effet, rien qu'au bout de 20 essais, la probabilité pour que Bertrand trouve totalement au hasard serait de 1 sur 2^20, soit un peu plus d'1 chance sur 1 million ("soundness"). De ce fait, si Bertrand a répondu correctement aux 20 essais, alors Anthony a une forte conviction ("completeness") que l'affirmation que les balles sont de couleurs différentes est belle et bien exacte.

Les ZKPs non interactives

Bien que révolutionnaire en soi, le concept initial faisait appel à des interactions entre les parties prenantes, ce qui nécessitait leur disponibilité et leurs rencontres régulières. De plus, cela empêchait la possibilité d'effectuer des vérifications indépendantes des parties prenantes, puisque de fait la conviction de la validité de la preuve tenait fortement à la confiance entre les parties prenantes.

Pour résoudre cette problématique, des solutions ne nécessitant pas l'intervention directe des parties prenantes ont été imaginées, et cela dès 1988, avec par exemple l'usage d'une clé partagée, comme exposé dans cette publication : https://dl.acm.org/doi/10.1145/62212.62222

Contrairement aux ZKPs interactives, leurs sœurs non interactives ne nécessitent qu'un cycle de communication entre les participants (Prover et Verifier). Le Prover passe le secret à un algorithme spécifique qui va calculer une preuve à zéro connaissance. Une fois la preuve générée, elle est alors transmise au Verifier, qui pourra alors contrôler si la preuve fournie par le Prover est fiable à l'aide d'un autre algorithme.

Ce faible nombre d'interactions nécessaires rend les ZKPs non interactives bien plus efficaces. De plus, une fois la preuve générée, elle est alors disponible pour tous ceux qui ont accès à la clé partagée et à l'algorithme de vérification.

Et la blockchain dans tout ça ?

Aujourd'hui d'énormes quantités de données sont échangées sur différents services sur Internet (Google, Facebook, YouTube, e-mail, ...). Ces données ont une valeur marchande directe et sont largement exploitées par des régies publicitaires ou d'autres algorithmes de recommandations pour établir votre profil d'internaute et adapter le contenu, vous enfermant inévitablement dans une sorte de bulle de filtre sans même vous en rendre compte et sans que vous puissiez le contrôler. Les données que vous confiez à ces services sont hébergées chez le prestataire de service, vous lui faites confiance pour leur stockage et vous avez peu de contrôle sur ce qu'il en fait ensuite en termes de monétisation.

La blockchain est une technologie de stockage de l'information de façon publique, distribuée et pseudonymée, qui permet de rendre la propriété des données stockées aux individus. De plus, les données sont répliquées sur de multiples ordinateurs ou ensembles d'ordinateurs à travers le monde, permettant ainsi d'offrir un haut niveau d'intégrité sur les données stockées, car aucun ordinateur individuellement ou même un petit ensemble d'entre eux ne peut prendre le contrôle sur les données sans se faire sanctionner par les autres.

Cependant, les blockchains les plus fiables étant publiques, pour permettre un réseau de grande taille et ainsi garantir le plus haut niveau de redondance et d'intégrité, elles ne permettent pas nativement de garantir la confidentialité des données stockées, bien au contraire.

On peut évidemment stocker des données chiffrées avec des protocoles de type RSA, qui sont aujourd'hui très fiables mais pourraient être vulnérables dans l'avenir. Or, la blockchain est non modifiable, et de ce fait, les données qui y sont stockées dans le passé ne peuvent pas être mises à jour avec de nouveaux algorithmes de chiffrement. À cause de cela, les entreprises qui disposent de données privées, voire confidentielles, sont frileuses quant à l'adoption de la blockchain.

C'est là que les ZKPs prennent tout leur sens lorsqu'on les combine à une blockchain. Au lieu de stocker la donnée en elle-même, on stocke les preuves, qui, étant à zéro connaissance, ne contiennent pas les données secrètes et ne permettent pas de les retrouver, garantissant ainsi la confidentialité de celle-ci.

La combinaison des ZKPs avec une blockchain publique permet d'avoir un très bon instrument de souveraineté numérique sur les données.

SNARK et STARK sont dans un bateau...

Vous verrez souvent, dans les projets et documentations sur les ZKPs, deux protocoles principaux, zk-SNARK et zk-STARK.

zk-SNARK correspond à "Zero-Knowledge Succinct Non-interactive Argument of Knowledge", autrement dit une approche permettant de fournir des éléments de preuve de connaissance sans nécessité d'interaction entre les provers et les verifiers. Ils sont dits succincts car ils utilisent peu de données tout en étant très efficaces, ce qui en fait un protocole particulièrement intéressant pour les blockchains où la mémoire et l'espace de stockage sont précieux et doivent être économisés au maximum. C'est ce protocole qui est utilisé par ZCash par exemple. Son point fort principal est de générer des preuves de très petites tailles (généralement moins de 1 Ko) et très rapides à vérifier (en quelques millisecondes).

Cependant, le protocole zk-SNARK nécessite une phase initiale de confiance (trusted setup) pour démarrer, où des informations privées sont utilisées et peuvent, si elles tombent entre de mauvaises mains, permettre de prendre le contrôle et de corrompre le système. Dans le cas de ZCash, les clés privées utilisées au lancement et les ordinateurs qui ont servi à les générer ont été détruits par la suite. Cette phase initiale est considérée comme une faille de sécurité parce que les personnes doivent faire confiance sur le fait que les données utilisées dans la phase d'initialisation soient bien supprimées correctement. Également, le protocole zk-SNARK est critiqué pour sa vulnérabilité cryptographique théorique face aux ordinateurs quantiques.

Pour résoudre ces inconvénients de zk-SNARK, le protocole zk-STARK (Zero-Knowledge Scalable Transparent Arguments of Knowledge) a été créé. Celui-ci ne nécessite pas cette phase d'initialisation de confiance et gère, en principe, mieux la mise à l'échelle (scalability), et est théoriquement résistant aux attaques cryptographiques par des ordinateurs quantiques. Dans le cas de zk-STARK, le mécanisme de randomisation utilisé est public. Cet aspect public permet d'améliorer la confiance des utilisateurs dans les systèmes à zéro connaissance. Du fait à la fois de la non-nécessité d'une phase d'initialisation privée effectuée par des tiers et du fait qu'une randomisation publiquement vérifiable soit utilisée, les systèmes de ZKProofs basés sur zk-STARK bénéficient d'un protocole de confiance vérifiable. Le protocole zk-STARK peut être implémenté aussi bien sous forme interactive (donc avec des interactions entre le prover et le verifier) que de manière non-interactive (auquel cas il est souvent appelé zk-nSTARK).

Cependant tout n'est pas rose dans le monde du protocole zk-STARK, car il génère des preuves plus volumineuses (quelques dizaines de kilo-octets) et plus longues à vérifier.

La blockchain de niveau 2 StarkNet utilise ce protocole. Elle a été cofondée par l'un des créateurs du protocole zk-STARK, Alessandro Chiesa.

<table class="tg">
<thead>
<tr>
<th></th>
<th>zk-Snark</th>
<th>zk-stark</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>Taille des preuves</strong></td>
<td>Très faible (< 1Ko)</td>
<td>Plus importantes (> 10Ko)</td>
</tr>
<tr>
<td><strong>Rapidité de vérification des preuves</strong></td>
<td>Très rapide (quelques millisecondes)</td>
<td>Rapide mais plus long que zk-SNARK</td>
</tr>
<tr>
<td><strong>Scalabilité</strong></td>
<td>Moins scalable que zk-STARK</td>
<td>Plus scalable que zk-SNARK</td>
</tr>
<tr>
<td><strong>Résistance aux attaques</strong></td>
<td>Potentiellement vulnérable aux ordinateurs quantiques</td>
<td>Résistant aux ordinateurs quantiques</td>
</tr>
<tr>
<td><strong>Confiance</strong></td>
<td>Nécessite de faire confiance à ceux qui ont généré la paire de clés public/privé à l'initialisation</td>
<td>Pas de nécessité de phase d'initialisation par un tier de confiance. Le mécanisme de randomisation utilisé est public et vérifiable</td>
</tr>
</tbody>
</table>

‍

Si vous voulez creuser davantage ces deux protocoles, vous pouvez consulter ces deux billets de blog très complets (en anglais) :

C'est bien beau tout ça, mais y a-t-il des cas d'usage concrets ?

Aujourd'hui, les mécanismes à zéro connaissance sont déjà utilisés dans des blockchains pour de nombreux cas d'usage ou sont en cours de développement pour y parvenir :

Paiements anonymisés

Des blockchains dédiées aux transactions anonymes, sorte de cash numérique, existent et exploitent les technologies de preuves à zéro connaissance pour y parvenir.

On peut citer par exemple Monero, ZCash ou l'outil Tornado Cash.

Améliorer la scalabilité des blockchains dans les solutions de niveau 2

Les blockchains de premier niveau, telles que Bitcoin ou Ethereum, sont souvent peu aptes à supporter de gros volumes de transactions rapidement. Des blockchains de niveau 2 sont apparues pour répondre à cette problématique, et nombre d'entre elles ont choisi de se baser sur des mécanismes à divulgation nulle, par l'intermédiaire d'un mécanisme appelé ZK-Rollup.

Ce mécanisme permet aux blockchains de niveau 2 de regrouper les transactions et de déposer des preuves, et uniquement des preuves, à zéro connaissance sur la blockchain de niveau 1. Cela permet de ne pas avoir besoin de stocker les détails des transactions sur la blockchain de niveau 1, tout en permettant de l'utiliser comme garantie en y déposant des preuves de validité des transactions.

De ce fait, valider un bloc avec un mécanisme de ZK-Rollup est plus rapide et moins coûteux du fait que moins de données sont incluses.

Accès à des services/biens selon des critères spécifiques

Prenons un exemple concret, vous devez louer un appartement, aujourd'hui on vous demande vos feuilles d'imposition, vos fiches de paie, votre carte d'identité et bien d'autres éléments. Des éléments qui contiennent énormément d'informations sur vous et votre situation. Or, en réalité, les propriétaires bailleurs n'ont pas besoin de la totalité des informations inscrites sur ces documents, ils ont besoin de savoir d'une part si vos revenus sont suffisants par rapport au montant du loyer ou encore si vous avez des papiers d'identité valides et que vous êtes majeur.

Avec des systèmes basés sur les ZK-Proofs, vous pourriez fournir des preuves garantissant au bailleur votre capacité à assumer le loyer convenablement, précisément sur les critères qu'il demande, par exemple une preuve lui indiquant que vous gagnez au moins 3 fois le loyer sans révéler vos revenus réels, ni leur source.

Cela peut s'appliquer à bien d'autres usages, par exemple sur les sites internet, justifier de votre âge, ou encore prouver que vous disposez d'un compte GitHub, Google, ... sans donner le token d'authentification au service, ...

Identités décentralisées

Des projets d'identités décentralisées tels que PolygonID ou Sismo exploitent également les preuves à zéro connaissance. PolygonID promet de fournir un service permettant de générer des preuves pour s'authentifier sur des services sans révéler vos informations privées.

Sismo, lui, permet d'avoir un coffre-fort contenant les tokens d'authentification de différentes plateformes (Google, GitHub, ...) et ainsi démontrer votre possession de compte sur ces services, sans avoir besoin d'autoriser l'accès directement aux informations de vos comptes, en vous permettant de générer des preuves basées sur les informations dont vous disposez dans ces services, sans révéler les données précises.

Votes en ligne anonymisés

À l'heure actuelle, les systèmes de votes en ligne n'offrent souvent pas un niveau de fiabilité et d'anonymat très élevé. Les ZKPs, combinées à la blockchain, pourraient permettre de concevoir des outils de votes numériques fiables et anonymes.

Actuellement, les systèmes de votes utilisant ces technologies sont encore expérimentaux et à petite échelle, principalement utilisés par des organisations décentralisées autonomes (DAO).

Et bien plus encore...

Et probablement bien d'autres usages encore à imaginer.

ZKPs dans le web3, des solutions encore jeunes

Les ZKPs sont encore assez jeunes dans le monde de la blockchain et ne peuvent pour l'instant être envisagées que pour des usages à faibles risques. Ce n'est donc pas encore pour demain que l'on verra des systèmes de votes utilisant les ZKPs pour les scrutins nationaux, ni pour les documents d'identité officiels.

Cependant, cette solution est déjà aujourd'hui intéressante pour les projets privés, la gouvernance et l'identité numérique dans des petites structures, comme les DAO (Decentralized Autonomous Organizations) ou encore dans le cadre de blockchains de niveau 2, notamment pour la scalabilité.

Ces protocoles sont la clé de voûte pour permettre des applications offrants un haut niveau de contrôle des informations privées sans intermédiaire de confiance, et garantissant au détenteur des données privées leur non-divulgation.

The end ...