Les ZKPs, “Zero Knowledge Proof”, remplacer les données par des preuves

Les ZKPs, qu’est-ce que c’est ?

Les ZKP (“preuves à divulgation nulles de connaissance” en français) sont des méthodes cryptographiques par lesquelles une première entité, le « prouveur », peut prouver qu’il est en possession d’une information (mot de passe, solution d’un problème, etc.) à une autre entité, le « vérificateur », sans toutefois ne rien révéler de l’information elle-même.

Les protocoles ZKP ont été introduits au milieu des années 80 par un groupe de chercheurs du MIT, et connaissent un développement très important aujourd’hui car ils peuvent constituer la solution au problème de la protection des données personnelles.

Autrement dit, le protocole ZKP nous permet de nous partager des preuves à la place des informations elles-mêmes, alors qu’aujourd’hui la majorité des systèmes reposent sur le partage de données, souvent confidentielles.

Comment ça marche ?

Quelques exemples qui décrivent le principe des ZKPs :

1/ « Où est Charlie ? »

Vous voulez prouver à votre meilleur ami que vous avez trouvé Charlie, sans lui montrer où est Charlie sur la page.

La solution est de couvrir toute la page avec une feuille noire plus grande que la page, en laissant un trou de la taille de Charlie. Vous pouvez ainsi prouver à votre ami que vous avez trouvé Charlie sans lui révéler la position de Charlie sur le dessin, comme montré sur le schéma qui suit :

2/ Le jeu de cartes

Votre amie veut vous prouver qu’elle a une figure mais sans vous montrer sa carte.

La solution est de montrer toutes les cartes numérales. Ainsi, s’il n’en manque aucune, alors votre amie vous a prouvé qu’elle avait une figure sans vous montrer laquelle.

3/ L’exemple de la caverne

Considérez Alice et Bob dans une caverne avec deux chemins A et B reliés par l’entrée d’un côté, et de l’autre par une porte fermée à clef :

Alice veut prouver à Bob qu’elle possède la clef permettant d’ouvrir la porte verrouillée.

Bob met donc un protocole en place pour vérifier les dire d’Alice. Bob à l’entrée de la caverne, demande à Alice, qui est quelque part dans la caverne, d’apparaître par le chemin A ou le chemin B ; de telle façon que si Alice arrive du bon chemin, alors elle prouve à Bob qu’elle est en possession de la clef.

Si Alice possède la clef :

• Si Bob lui demande d’arriver en A alors qu’elle est en A > Alice valide le protocole (sans utiliser la clef)
• Si Bob lui demande d’arriver en A alors qu’elle est en B > Alice valide le protocole (en passant par la porte grâce à la clef)
• Si Bob lui demande d’arriver en B alors qu’elle est en B > Alice valide le protocole (sans utiliser la clef)
• Si Bob lui demande d’arriver en B alors qu’elle est en A > Alice valide le protocole (en passant par la porte grâce à la clef)

Si Alice ne possède pas la clef :

• Si Bob lui demande d’arriver en A alors qu’elle est en A > Alice valide le protocole (pas besoin d’avoir la clef)
• Si Bob lui demande d’arriver en A alors qu’elle est en B > Alice ne valide pas le protocole
• Si Bob lui demande d’arriver en B alors qu’elle est en B > Alice valide le protocole (pas besoin d’avoir la clef)
• Si Bob lui demande d’arriver en B alors qu’elle est en A > Alice ne valide pas le protocole

Nous remarquons à ce stade que si Alice ne possède pas la clef, alors il y a 1/2 chance qu’elle valide tout de même le protocole.

Imaginons que Bob conduise trois fois de suite le protocole alors qu’Alice ne possède pas la clef :

• La 1ère fois, Alice a 1/2 chance de valider le protocole
• La 2ème fois, Alice a 1/2 chance de valider le protocole
• La 3ème fois, Alice a 1/2 chance de valider le protocole

Donc après la 3ème fois, il y a 1/8 chance (= 1/2 x 1/2 x 1/2) qu’Alice valide le protocole alors qu’elle n’est pas en possession de la clef.

Plus généralement, Bob va alors répéter le test plusieurs fois pour faire baisser la probabilité qu’Alice valide le protocole sans avoir la clef : cette probabilité étant égale à 1/2^N, où N est le nombre de fois que le protocole est répété.

Ainsi, en répétant le protocole un nombre important de fois, Bob peut être quasiment certain qu’Alice est bien en possession de la clef si elle valide le protocole.

Cet exemple a été conçu en 1989 pour illustrer les formules mathématiques du papier originel « The knowledge complexity of interactive proof-systems » écrit par Shafi Goldwasser, Silvio Micali et Charrles Rackoff (les chercheurs du MIT) en 1985. C’est un des exemples les plus précis, contrairement à d’autres qui confondent souvent plusieurs notions et qui ne sont finalement pas vraiment des exemples de ZKP.

De la pratique à la théorie

Il a été établi qu’un protocole ZKP doit avoir trois propriétés qui sont :

• Completeness : Si l’affirmation est vraiment vraie et que les deux utilisateurs suivent les règles correctement, alors le vérificateur sera convaincu de sa véracité sans aucune aide artificielle ;
• Soundness : Dans le cas où la déclaration serait fausse, le vérificateur ne serait en aucun cas convaincu du contraire (la méthode est vérifiée de façon probabiliste pour s’assurer que la probabilité de fausseté est égale à zéro) ;
• Zero Knowledge : Dans tous les cas, le vérificateur n’aura pas accès à plus d’informations.

Ainsi, le fonctionnement général d’un ZKP est un processus de questions/réponses entre deux parties : « le prouveur » qui veut prouver la véracité d’une déclaration et « le vérificateur » qui doit être convaincu en vérifiant la preuve apportée par le prouveur. Ce protocole requiert donc un canal de communication stable et continu, ce qui peut poser certaines difficultés.

***

Depuis les années 80, les recherches ont évolué et se sont portées sur l’application du protocole ZKP à un système multipartite : comment mettre en place les ZKPs pour servir plus de deux acteurs en même temps et plus simplement ?

Une technique a été développée : les protocoles NIZKPs (Non-Interactive Zero Knowledge Proof), considérés plus efficaces pour plusieurs raisons :

• Les preuves sont moins denses et le temps de vérification des preuves est plus court ;
• Il y a un minimum d’interactions entre les parties, ce qui résout le problème de disposer d’un canal de communication stable et continu pour effectuer le protocole ;
• Ce type de protocole nécessite seulement l’envoi de la preuve au système et qu’elle soit stockée de telle façon que n’importe quel vérificateur puisse y avoir accès quand il le souhaite.

Parmi les protocoles NIZKP, il existe les zk-SNARKs qui, dans la blockchain, permettent de vérifier l’exactitude de calculs sans avoir à les exécuter et sans savoir quels calculs ont été exécutés. Les zk-SNARKs sont construits grâce à la combinaison de plusieurs outils cryptographiques et sont à la base du projet Zcash permettant d’effectuer des transactions sur une blockchain de façon totalement anonyme.

En effet, sur une blockchain publique, quand Alice veut faire une transaction en cryptomonnaie à Bob :

• tout individu ayant accès à internet a accès aux activités de la blockchain et aux pseudonymes des personnes qui effectuent les transactions
• les bâtisseurs de la blockchain (appelés mineurs) qui doivent vérifier l’existence du porte-monnaie d’Alice et la véracité des informations liées à la transaction (identités d’Alice et Bob, montant, etc.), ont accès eux aussi à ces données

Grâce aux protocoles zk-SNARKs, un système externe à la blockchain va s’occuper de vérifier toutes les informations de la transaction et de générer une preuve qui montre que les informations ont été vérifiées et qu’elles sont vraies (l’historique du portefeuille d’Alice, le montant de la transaction, etc.). De cette façon, les mineurs qui s’occupent d’intégrer l’existence de la transaction dans la blockchain ainsi que tout individu qui peut observer les activités de la blockchain n’ont accès qu’aux preuves de la véracité des informations relatives à une transactions, à la place des informations elles-mêmes. Ce protocole permet de garder des informations secrètes, même sur une blockchain publique.

En effet, les ZKPs ont été l’un des domaines de recherche les plus actifs en cryptographie, et ont eu un impact significatif sur la technologie Blockchain dont les cas d’usage sont explicités dans l’article Les ZKPs, “Zero Knowledge Proof”, une nouvelle ère pour le partage des données.