A Complexity-Theoretic Approach to Proofs of Space
2026-08-10 • Cryptography and Security
Cryptography and SecurityComputational Complexity
AI summaryⓘ
The authors study Proofs of Space (PoS), which are methods for proving that someone is using a large amount of memory. They note that existing PoS methods rely on idealized models or special assumptions. The authors present a new way to build PoS using common cryptographic tools combined with assumptions about the hardness of certain computational problems. Their work shows how PoS can be constructed from well-studied assumptions like the difficulty of some circuit problems, collision-resistant hash functions, and succinct arguments for efficient computations.
Proof of Spacerandom oracle modelcollision-resistant hash functionderandomizationnondeterministic circuitsSNARGcomputational hardnesscryptographic assumptions
Authors
Marshall Ball, Jiaxin Guan
Abstract
A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.