A Complexity-Theoretic Approach to Proofs of Space

Le Grand Casse du Stockage Numérique

Imaginez un monde où vous pouvez prouver que vous possédez une immense bibliothèque de livres sans jamais en montrer une seule page. C'est le cœur des Preuves d'Espace (Proofs of Space), un concept dans le domaine de la cryptographie et de l'informatique. C'est comme un propriétaire numérique qui veut s'assurer qu'un locataire possède réellement un entrepôt rempli de meubles, et non pas seulement un dessin ingénieux de meubles. Le propriétaire (le Vérificateur) doit être certain que le locataire (le Prouveur) utilise une énorme quantité de mémoire persistante pour stocker des données, plutôt que de garder une simple petite note disant « j'ai les meubles » pour ensuite faire apparaître magiquement les meubles lorsqu'on lui demande.

Pendant des années, la seule façon de construire ces entrepôts numériques reposait sur un outil imaginaire et magique appelé « Oracle Aléatoire ». Voyez cela comme une boîte noire magique qui recrache des réponses parfaitement aléatoires et imprévisibles chaque fois que vous posez une question. Bien qu'utile pour la théorie, c'est comme construire une maison sur des fondations de pure magie ; nous ne savons pas si cela tiendrait dans le monde réel. La grande question pour les scientifiques a été : pouvons-nous construire une Preuve d'Espace sécurisée en utilisant uniquement les lois physiques réelles de l'informatique, sans dépendre de boîtes magiques ? Ce document plonge dans cette question même, en utilisant les outils de la théorie de la complexité — l'étude de la difficulté des problèmes à résoudre — pour voir si nous pouvons construire ces preuves à partir de zéro.

La Grande Idée du Papier : La Chaîne « Profonde »

Les auteurs, Marshall Ball et Jiaxin Guan, présentent un nouveau cadre élémentaire pour construire des Preuves d'Espace sans magie. Leur conclusion principale est que vous pouvez créer ces preuves si vous disposez de deux ingrédients spécifiques : une hypothèse cryptographique (comme des fonctions de hachage résistantes aux collisions) et une hypothèse de « dérandomisation » (une croyance sur la difficulté de certains problèmes informatiques pour des machines non déterministes puissantes).

Pour comprendre leur astuce, imaginez que vous deviez prouver que vous possédez un immense tas de sable désordonné (la donnée). L'ancienne méthode exigeait une boîte magique pour garantir que le sable ne pouvait pas être compressé. Les auteurs réalisent que dans le monde réel, nous n'avons pas besoin que le sable soit impossible à compresser ; nous avons juste besoin qu'il soit difficile à compresser rapidement.

Ils introduisent le concept de Profondeur Computationnelle. Considérez une chaîne de données comme une histoire.

1. La Configuration : Le Prouveur prend une minuscule graine (un court résumé de l'histoire) et passe beaucoup de temps (Phase 1) à l'étendre en un immense roman détaillé (la donnée).
2. Le Piège : Le Vérificateur demande ensuite des pages spécifiques de ce roman.
3. Le Piège : Si le Prouveur n'a pas réellement écrit tout le roman et a simplement gardé le court résumé, il devrait réécrire les pages de zéro. Mais le Vérificateur ne lui accorde qu'un temps infime (Phase 2) pour le faire.

Les auteurs montrent que si l'on suppose que certains problèmes sont difficiles (spécifiquement, que certains problèmes sont trop difficiles pour que des circuits « non déterministes » les résolvent rapidement), on peut créer une fonction qui transforme une courte graine en une longue chaîne. Cette chaîne est « profonde » : elle peut être générée à partir d'une courte graine si l'on dispose de beaucoup de temps, mais elle ne peut pas être reconstruite à partir d'une courte graine si l'on est pressé. C'est comme un puzzle qui prend un an à résoudre mais une minute à vérifier ; si vous essayez de le résoudre en une minute, vous ne le pouvez tout simplement pas.

Comment la Preuve Fonctionne : L'« Arbre de Merkle » et le « Sortilège Magique »

Le papier décrit un protocole en deux étapes pour tester cette « profondeur ».

Phase 1 : La Configuration (L'Attente Longue)
Le Vérificateur envoie une graine aléatoire au Prouveur. Le Prouveur passe beaucoup de temps (disons, des heures) en utilisant sa fonction « profonde » spéciale pour transformer cette graine en un fichier de données massif. Il construit ensuite un Arbre de Merkle sur ces données. Imaginez l'Arbre de Merkle comme l'empreinte digitale numérique de l'ensemble du fichier. C'est comme un arbre généalogique où chaque feuille est une donnée, et chaque branche est un hachage (une empreinte digitale numérique unique) des deux branches situées en dessous. Tout en haut se trouve un seul « Root » (racine) hash qui représente l'intégralité du fichier. Le Prouveur stocke ce fichier massif et la Racine.

Phase 2 : La Vérification (Le Quiz Rapide)
Le Vérificateur demande soudainement des pages spécifiques du fichier (indices aléatoires). Le Prouveur doit rapidement fournir ces pages et le « chemin » à travers l'Arbre de Merkle qui prouve que ces pages appartiennent au fichier original.

C'est ici que l'ingéniosité des auteurs brille. Pour empêcher le Prouveur de tenter de contourner le protocole (en gardant simplement la courte graine et en essayant de deviner les pages), ils ajoutent un Argument Succinct (une preuve courte).

• Option A (L'Hypothèse la plus forte) : Ils utilisent un « SNARG » (une preuve très courte et non interactive) pour prouver que le Root hash envoyé provient réellement du fichier généré par la graine. Cela nécessite une hypothèse forte sur l'existence de certains outils cryptographiques, mais cela maintient la surcharge de stockage basse.
• Option B (L'Hypothèse la plus faible) : Ils utilisent un argument de type « Kilian » basé sur des fonctions de hachage résistantes aux collisions. C'est une hypothèse plus standard, plus « sûre », mais elle force le Prouveur honnête à stocker un peu plus de données (une chaîne « PCP ») pour prouver que l'arbre de Merkle a été construit correctement.

Ce Qu'Ils Écarteront et Ce Qu'Ils Prouvent

Le papier argumente explicitement contre l'idée que les Preuves d'Espace doivent reposer sur le modèle de l'Oracle Aléatoire. Ils montrent que la « boîte magique » n'est pas nécessaire. Au lieu de cela, ils prouvent que si nous acceptons l'hypothèse de la « dérandomisation » (que certains problèmes sont difficiles pour les circuits non déterministes), alors les Preuves d'Espace sont possibles.

Ils abordent également un type spécifique de tentative de contournement du protocole : et si le Prouveur stockait une infime partie des données et tentait de « compresser » le gros fichier à la volée ? Les auteurs prount que si le Prouveur parvient à convaincre le Vérificateur, il doit avoir stocké une quantité significative de données. Plus précisément, ils montrent qu'un Prouveur tentant de contourner le protocole ne peut pas stocker nettement moins que le prouveur honnête (par exemple, si le prouveur honnête stocke $N$ bits, un Prouveur tentant de contourner le protocole ne peut pas s'en sortir en stockant beaucoup moins que $N$ bits, selon la construction spécifique utilisée).

L'Essentiel

Ce papier ne prétend pas avoir construit un produit commercial prêt pour votre smartphone aujourd'hui. Au lieu de cela, il fournit un plan théorique. Il démonte l'idée que la tâche « impossible » de prouver que vous avez un entrepôt de données sans magie est en fait possible, à condition d'accepter certaines croyances standards sur la difficulté des problèmes informatiques.

Ils démontrent que :

1. Cela fonctionne : Vous pouvez construire ces preuves en utilisant la « profondeur computationnelle » plutôt que la magie.
2. C'est efficace : L'utilisateur honnête n'a pas besoin de faire rien de trop extravagant, bien qu'il doive stocker les données.
3. C'est sécurisé : Si quelqu'un tente de contourner le protocole en stockant moins de données, les mathématiques disent qu'il sera presque certainement pris, en supposant que les problèmes difficiles sous-jacents restent difficiles.

En bref, Ball et Guan ont sorti la « Preuve d'Espace » du domaine des boîtes noires magiques pour la planter fermement dans le sol de la théorie de la complexité, nous montrant qu'avec les bonnes hypothèses, nous pouvons construire des entrepôts numériques aussi sûrs que les lois de l'informatique le permettent.