# Preuve d'espace

La preuve d'espace (PoS) est un type d'algorithme de consensus obtenu en prouvant son intérêt légitime pour un service (comme par exemple l'envoi d'un e-mail) en allouant une quantité non négligeable de mémoire ou d'espace disque pour résoudre un défi présenté par le fournisseur de services.
Les preuves d'espace sont très similaires aux preuves de travail (PoW), sauf qu'au lieu du calcul, le stockage est utilisé pour gagner de la crypto-monnaie. La preuve d'espace est différente des fonctions gourmandes en mémoire dans la mesure où le goulot d'étranglement ne réside pas dans le nombre d'événements d'accès à la mémoire, mais dans la quantité de mémoire requise.

## Histoire

Après la sortie de Bitcoin, des alternatives à son mécanisme d'extraction PoW sont recherchées et le PoS est étudié. La preuve d'espace est considérée comme une alternative plus juste et plus écologique par les passionnés de blockchain en raison de la nature polyvalente du stockage et du coût énergétique inférieur requis par le stockage.
Le concept est formulé en 2013 par Dziembowski et al.$^,$ et (avec une formulation différente) par Ateniese et al.$^,$.
En 2014, Signum (anciennement Burstcoin) devient la première implémentation pratique d'une technologie blockchain en PoS (initialement comme preuve de capacité) et est toujours activement développée. Outre Signum, plusieurs implémentations théoriques et pratiques de PoS ont été publiées et discutées, telles que SpaceMint et Chia.
Certaines sont critiquées pour avoir augmenté la demande et raccourci la durée de vie des périphériques de stockage en raison d'exigences de lecture de disque plus importantes que Signum$^,$.

## Concept

La preuve d'espace est un élément de données qu'un « prouveur » envoie à un « vérificateur » pour prouver avoir réservé une certaine quantité d'espace. Pour des raisons pratiques, le processus de vérification doit être efficace, c’est-à-dire consommer peu d’espace et de temps. Pour des raisons de sécurité, il doit être difficile pour le prouveur de réussir la vérification s'il ne réserve pas réellement la quantité d'espace revendiquée.
Une façon de mettre en œuvre le PoS consiste à utiliser des graphiques difficiles à cerner$^,$. Le vérificateur demande au prouveur de construire un étiquetage d'un graphe difficile à cerner. Le démonstrateur s'engage à l'étiquetage. Le vérificateur demande ensuite au prouveur d’ouvrir plusieurs emplacements aléatoires dans l’engagement.

### Preuve de stockage

Une preuve de stockage (également preuve de récupérabilité ou preuve de possession de données) est liée à une preuve d'espace, mais au lieu de montrer que l'espace est disponible pour résoudre une énigme, le prouveur montre que l'espace est réellement utilisé pour stocker correctement un élément de données au moment de la preuve.

### Preuve de capacité

La preuve de capacité est un système dans lequel les mineurs sont autorisés à pré-calculer (« tracer ») les fonctions PoW et à les stocker sur le disque dur. La première implémentation de la preuve de capacité est Signum (anciennement Burstcoin).

### Preuve conditionnelle de capacité

L'algorithme de consensus de Proof of Capacity (PoC) est utilisé dans certaines crypto-monnaies. La preuve conditionnelle de capacité (CPOC) est une version améliorée de la PoC. Elle dispose d'un système de travail, d'enjeu et de capacité qui fonctionne comme les algorithmes PoW, PoS et PoC. Ainsi, en mettant en gage leurs actifs numériques, les utilisateurs reçoivent un revenu plus élevé en guise de récompense.
La CPOC conçoit une nouvelle mesure de récompense pour les meilleurs utilisateurs. Dans cet algorithme, les mineurs ajoutent un composant conditionnel à la preuve en s'assurant que leur fichier de tracé contient des données spécifiques liées au bloc précédent. Cette condition supplémentaire renforce la sécurité et la décentralisation du mécanisme de consensus au-delà des algorithmes traditionnels de preuve de capacité.

### Preuve d'espace-temps

La preuve d'espace-temps (PoST) est une preuve qui montre que le démonstrateur a passé un certain temps à maintenir l'espace réservé inchangé. Ses créateurs estiment que le coût du stockage est inextricablement lié non seulement à sa capacité, mais également au temps pendant lequel cette capacité est utilisée. Elle est liée à une preuve de stockage (mais sans nécessairement stocker de données utiles), bien que la construction Moran-Orlov permette également un compromis entre l'espace et le temps. La première implémentation de PoST se fait avec la blockchain Chia.

## Utilisations

Les preuves d'espace pourraient être utilisées comme une alternative aux preuves de travail dans les applications de puzzle client traditionnelles, telles que les mesures anti-spam et la prévention des attaques par déni de service. La preuve d'espace a également été utilisée pour la détection de logiciels malveillants, en déterminant si le cache L1 d'un processeur est vide (par exemple, s'il dispose de suffisamment d'espace pour évaluer la routine PoS sans échec de cache) ou s'il contient une routine qui a résisté à l'éviction.

### Signum (anciennement Burstcoin)

La première blockchain à utiliser la validation de blockchain basée sur le disque dur est créée en 2014. Signum Proof of Capacity consomme de l'espace disque plutôt que des ressources informatiques pour exploiter un bloc. Contrairement au PoW, où les mineurs continuent de modifier l'en-tête et le hachage du bloc pour trouver la solution, la preuve de capacité (telle qu'implémentée par Burstcoin et développée par Signum) génère des solutions aléatoires, également appelées tracés, en utilisant à l'avance l'algorithme cryptographique Shabal et les stocke sur des disques durs. Cette étape est appelée traçage et peut prendre des jours, voire des semaines, selon la capacité de stockage du disque. Dans l'étape suivante, l'exploitation minière, les mineurs font correspondre leurs solutions au puzzle le plus récent et le nœud avec la solution la plus rapide obtient l'exploitation du bloc suivant$^,$.

### SpaceMint

En 2015, un article propose une cryptomonnaie appelée SpaceMint. Il tente de résoudre certains des problèmes de conception pratiques associés aux schémas PoS basés sur le pebbling. Lors de l'utilisation de PoS pour la cryptomonnaie décentralisée, le protocole doit être adapté pour fonctionner dans un protocole non interactif puisque chaque individu du réseau doit se comporter comme un vérificateur.

### Chia

En 2018, Chia, un projet de cryptomonnaie, publie deux articles présentant un nouveau protocole basé sur la preuve d'espace et la preuve de temps.
En février 2021, Chia publie un livre blanc décrivant son activité avant de lancer son réseau principal et son coin, le « Chia » (XCH) en utilisant le concept Proof of Space Time. Le modèle spatio-temporel de Chia dépend également du « traçage » (génération de fichiers de preuve d'espace) sur le support de stockage pour résoudre un puzzle.
Contrairement à de nombreuses crypto-monnaies de preuve de stockage, les tracés Chia ne stockent aucune donnée utile. De plus, la méthode de preuve de temps de Chia pour le traçage a soulevé des inquiétudes quant à la durée de vie réduite des disques SSD en raison de l'intensité de l'activité d'écriture impliquée dans la génération de tracés (généralement, le traçage se produit sur un SSD, puis les tracés terminés sont transférés sur un disque dur pour un stockage à long terme).