How Shafi Goldwasser Co-Invented Zero-Knowledge Proofs

Bienvenue à *First Principles*, une série d'A16Z Crypto. Je suis Tim Ruffgarden, responsable de la recherche chez A16Z Crypto, et nous parlons aujourd'hui d'une percée fondamentale en cryptographie : comment prouver qu'une chose est vraie sans révéler pourquoi elle l'est. Cette idée a donné naissance aux preuves à divulgation nulle de connaissance (Zero-Knowledge Proofs), l'un des concepts les plus puissants de l'informatique théorique. Ce qui a commencé comme une avancée théorique est aujourd'hui l'un des domaines les plus dynamiques de la cryptographie, alimentant tout, des systèmes de préservation de la vie privée aux rollups et aux calculs vérifiables. Notre invitée est Shaffi Goldwer, cryptographe lauréate du prix Turing qui, avec Silvio Micali et Charles Rackoff, a inventé les preuves à divulgation nulle de connaissance. Justin Taylor, partenaire de recherche chez A16Z Crypto et professeur associé d'informatique à l'Université de Georgetown, se joint à nous. Ensemble, nous explorons comment des problèmes apparemment anecdotiques comme le "mental poker" ont conduit le Dr Goldwer et ses co-auteurs à définir les preuves interactives et la divulgation nulle de connaissance, et comment ce travail a ouvert la porte à des résultats plus profonds sur ce qui peut être vérifié efficacement, y compris des théorèmes surprenants comme IP = PSPACE et les preuves vérifiables de manière probabiliste (PCP), qui montrent que des calculs complexes peuvent être vérifiés en inspectant seulement quelques emplacements aléatoires d'une preuve. Nous aborderons enfin les systèmes de blockchain modernes alimentés par les SNARKs. Shaffi, bienvenue et merci d'avoir pris le temps de nous parler aujourd'hui. Deux sujets reviennent souvent dans les discussions sur la technologie blockchain : les SNARKs et la confidentialité, au sens de la divulgation nulle de connaissance. Ces deux idées partagent en grande partie les mêmes racines intellectuelles, à savoir les travaux sur les systèmes de preuve interactifs. Le fameux article GMR (Goldwasser, Micali et Rackoff) en est un exemple. J'aimerais que vous nous parliez de l'ambiance de l'époque : pourquoi ces questions, pourquoi ces problèmes, comment vous y êtes arrivée, et comment tout cela s'est produit. À l'époque, il n'y avait ni SNARKs, ni contrats intelligents, ni blockchains, ni clouds, ni même le World Wide Web. J'étais étudiante diplômée à Berkeley, et mon conseiller a donné un cours sur la cryptographie et la théorie des nombres. Les deux dernières conférences portaient sur la cryptographie. Il a parlé du RSA, qui était alors le seul schéma de chiffrement à clé publique, et d'un article sur le "mental poker" par les mêmes auteurs du RSA. Ils considéraient le problème suivant : deux personnes, situées dans des parties différentes du monde, voulaient jouer aux cartes par téléphone, mais elles n'avaient pas de cartes. Comment allaient-elles distribuer un jeu de cartes ? Après le cours, Silvio et moi étions enthousiasmés par cette question, même si aucun de nous n'était un joueur de cartes. Je ne savais même pas qu'il y avait 52 cartes dans un jeu ! Quel est le rapport avec la divulgation nulle de connaissance et les preuves interactives ? Il y avait une idée de protocole pour définir des cartes chiffrées et comment distribuer une carte, et il y avait une certaine interaction. C'était un bon protocole. Il y avait des définitions de ce que signifie jouer en toute sécurité et selon les règles du mental poker. Mais pour vérifier à la fin que les règles avaient été suivies, les deux joueurs devaient tout révéler : ce qu'ils avaient chiffré à chaque coup, les messages envoyés, leur correspondance dans le jeu réel, etc. Quelqu'un nous a dit que ce n'était pas ainsi que l'on jouait au poker. On joue, mais personne ne sait nécessairement ce qui se passe quand les cartes sont face cachée. La question s'est alors posée : comment prouver que l'on a fait ce qu'il fallait sans révéler les cartes ? Comment prouver que l'on distribue correctement les cartes sans révéler tout ce que l'on a chiffré et le caractère aléatoire utilisé pour le chiffrement ? Nous avons élaboré un protocole pour un problème très spécifique : prouver que la carte était correctement ouverte, en utilisant la théorie des nombres. Il ne s'agissait pas de montrer de manière générale que tout peut être fait avec divulgation nulle de connaissance, mais d'un problème spécifique. Pour ce faire, nous avons réalisé que nous avions besoin d'interaction pour prouver quelque chose sans tout révéler, et que nous devions accepter une probabilité d'erreur. Il y avait donc une part d'aléatoire, tant dans le chiffrement des cartes que dans la preuve que quelque chose avait été fait correctement. Il y avait une petite chance que je vous triche, mais nous l'avons acceptée car la probabilité était très faible. Nous avons donc dû modifier la notion de preuve pour qu'elle puisse être interactive. Il y aurait un prouveur et un vérificateur. Le prouveur convaincrait le vérificateur de quelque chose. Deuxièmement, le vérificateur était prêt à accepter une petite chance d'erreur. Cela a permis de ne pas tout révéler. Mais nous avions une définition de ce que cela signifie de ne pas tout révéler. Nous devions définir ce qui est devenu plus tard la définition de la divulgation nulle de connaissance. Tous ces aspects montraient quelque chose qui, rétrospectivement, peut sembler ésotérique. À l'époque, c'était toute notre vie, car c'était notre article. Ensuite, cela a commencé à être généralisé, car la question était de savoir si l'on pouvait faire plus qu'un exemple. La définition de la divulgation nulle de connaissance est, en un sens, qu'à la fin, vous croirez ce que je prétends, mais vous ne découvrirez rien d'autre. Comment définir "rien d'autre" ? Il y a une définition opérationnelle : tout ce que vous auriez pu faire avant notre interaction, où je vous prouve une affirmation, vous pourriez le faire après. Et la façon de montrer que tout ce que vous auriez pu faire informatiquement avant est ce que vous auriez pu faire après est ce qu'on appelle le paradigme de simulation. Il faut montrer que toute connaissance que ce vérificateur a après, vous pouvez la simuler même sans le prouveur et l'interaction. C'était le début. Est-ce que tout s'est mis en place rapidement ? Y a-t-il eu des points bloquants pendant des mois ? Le conseiller n'a pas posé la question exactement comme nous l'avons résolue. Il y avait cet article sur le mental poker, puis il a montré qu'il y avait un autre article, de Lipton, qui montrait qu'il y avait un bug : un bit d'information sur les cartes pouvait être révélé. La question était alors : comment faire sans ce bit d'information ? Il y avait un problème dans la solution du mental poker, et c'était, rétrospectivement, un acte d'inspiration divine de réaliser que tout tournait autour de la façon de chiffrer un seul bit d'information et de prouver que ce bit était, disons, zéro ou un, sans rien révéler d'autre. Y a-t-il eu des embûches ? C'était votre question. C'était très excitant parce que les idées venaient les unes après les autres et nous avons réussi à trouver une définition intéressante et à la prouver. Mais bien sûr, quand on est étudiant diplômé, on a un conseiller, n'est-ce pas ? Et ils posent des questions : "Et ça ? Et ça ?" Et puis on réalise qu'on n'y a pas pensé et on en fait plus. Nous avons commencé tout cela avec juste un article sur le mental poker, mais ensuite nous l'avons généralisé à cette idée de preuves à divulgation nulle de connaissance plus généralement. Nous l'avons écrit. Nous étions très enthousiastes. Cet article a été soumis six fois et a été rejeté à chaque fois. Nous sommes arrivés à ces preuves interactives à divulgation nulle de connaissance avec Charlie Rackoff aussi. Il y a eu des embûches, mais nous étions très déterminés. Je suis beaucoup moins déterminée maintenant. On soumet un article une ou deux fois, mais ensuite, c'est "non, nous avons la bonne définition, c'est très intéressant" et nous allions, c'était comme une guerre en un sens. C'est une chose terrible à dire, mais... Non, je pense qu'il y a des leçons pour la prochaine génération de doctorants sur la ténacité comme une partie très importante de leur trajectoire. Absolument. Je ne sais pas si vous l'avez vécu, ou Justin, ou si vous pensez que la vie était plus facile. Elle ne l'était pas. La vie était difficile. Mais si chaque fois que vous recevez un rejet, vous supposez que les gens qui vous rejettent savent tout, alors vous ne pouvez pas aller plus loin. Mais d'une manière ou d'une autre, nous n'avons pas supposé cela, et je dois accorder beaucoup de crédit à mon co-auteur, Silvio, qui est aussi très compétitif. Il y a quelque chose qui me dit que la situation reste similaire aujourd'hui. Une chose que je trouve fascinante ici, c'est une métaphore traditionnelle pour expliquer la notion de preuves interactives aux gens : un mathématicien affirme qu'un théorème est vrai à un autre mathématicien, et plutôt que d'écrire une preuve de 50 pages au tableau, ils ont une conversation. Cela semble être une application moins frivole, plus formelle que le poker, peut-être selon vos goûts. Mais alors, il n'y a pas de notion d'information privée ou secrète. Je me suis toujours demandé pourquoi les notions de divulgation nulle de connaissance et de preuves interactives s'étaient réunies. Il semble que la réponse pourrait être le poker. Non, la réponse est la vie privée. La raison d'introduire l'interaction et le caractère aléatoire, la probabilité d'erreur, était que c'était le moyen d'obtenir la vie privée, ce qui était l'exemple du poker. Mais ensuite, plus généralement, on se demande si l'on peut prouver, par exemple, qu'un nombre composé est le produit de deux nombres premiers d'un format particulier sans donner la factorisation, en faisant une sorte d'interaction. Et ce n'est que plus tard que nous avons réalisé que nous pouvions réellement prouver des affirmations, et c'était un article de Goldwasser, Micali et Wigderson où ils ont montré que vous pouviez convaincre quelqu'un que deux graphes n'étaient pas isomorphes l'un à l'autre, ce qui est un problème que nous ne savions pas résoudre autrement à l'époque. Nous ne savions pas comment en faire une preuve courte. Je vous l'ai juste prouvé, mais il n'y avait pas de divulgation nulle de connaissance. La prise de conscience que l'on peut en fait prouver davantage en utilisant l'interaction et le probabilisme est venue après l'exemple de la divulgation nulle de connaissance. Et je veux juste ajouter une chose : vous avez raison, il est naturel de penser à un mathématicien prouvant une affirmation à un autre mathématicien. Mais les mathématiciens n'aimaient pas cette notion. Donc, quand on parle de preuves interactives aux mathématiciens, maintenant, beaucoup d'années plus tard, ils l'acceptent. Mais à l'époque, quand je donnais une conférence, je me souviens de certains colloques, et j'appelais cela une preuve interactive. Ils disaient : "Ce n'est pas une preuve, parce qu'une preuve est quelque chose qui a zéro erreur." Or, bien sûr, en réalité, de nombreuses preuves que les mathématiciens écrivent sont parfois complètement incorrectes dans le sens où l'affirmation qu'ils prouvent est incorrecte, mais souvent elles contiennent des erreurs. Je veux dire, ce sont juste de très longues preuves