Proof of space

A proof of space is a protocol in which a prover convinces a verifier that it is dedicating a given amount of storage, rather than computation as in a proof of work ¹.

In an initialization phase the prover stores data of the required size; later the verifier sends random challenges that the prover can answer quickly only if it still holds the data, because the data are expensive to regenerate ¹. Dziembowski and colleagues built secure schemes in the random-oracle model from graphs with high "pebbling complexity" and Merkle hash trees ¹. A related primitive, the proof of secure erasure, uses memory-filling challenges to show that a device's memory has been overwritten ². Earlier protocols required the prover to be isolated during the protocol; Bursuc and colleagues relax this to slow communication with an outside accomplice ². One low-trust system design applies these ideas with optional memory challenges that use response latency to check whether data is present, and with memory wiping to remove residual capacity for hidden workloads, as in timed memory-occupation challenges and memory wiping and proofs of secure erasure ³.