01 / The mechanism and its boundary
What is being described
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 S-1607.
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 S-1607. Dziembowski and colleagues built secure schemes in the random-oracle model from graphs with high "pebbling complexity" and Merkle hash trees S-1607.
A related primitive, the proof of secure erasure, uses memory-filling challenges to show that a device's memory has been overwritten S-0032. Most earlier protocols required the prover to be isolated during the protocol. Bursuc and colleagues relax this to slow communication with an outside accomplice S-0032. 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 S-0018.
Connections in the research map
Related research
Sources and provenance
- S-1607 / Tier A
Proofs of Space ↗
S. Dziembowski, S. Faust, V. Kolmogorov, K. Pietrzak · 2015 · CRYPTO 2015 (IACR Cryptology ePrint Archive 2013/796)
Supports: definition of proofs of space as the storage analogue of proofs of work; initialization and execution phases; construction with pebbling-hard graphs and Merkle hash trees in the random oracle model
Locator: abstract; §2
Version and catalogue details - S-0032 / Tier A
Software-Based Memory Erasure with Relaxed Isolation Requirements ↗
S. Bursuc, R. Gil-Pons, S. Mauw, R. Trujillo-Rasua · 2024 · 2024 IEEE 37th Computer Security Foundations Symposium (CSF 2024)
Supports: proofs of secure erasure: the verifier fills the prover's memory with random data and queries random blocks; isolation assumption relaxed to slow communication with an external conspirator
Locator: abstract; §2
Version and catalogue details - S-0018 / Tier B
A System Overview for Near-Term, Low-Trust AI Compute Verification ↗
N. Cankaya · 2026 · Machine Intelligence Research Institute
Supports: optional memory challenges using response latency; memory wiping with incompressible noise to remove residual capacity for hidden workloads
Locator: system architecture; §5.1.2
Version and catalogue details
- Source review date
- 2026-09-25
- Drafted by (source map)
- ai
- Review handles (source map)
- codex-review