💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

This paper presents an elementary framework for constructing secure Proofs of Space (PoS) without relying on the random oracle model, demonstrating that such protocols can be built from a combination of standard cryptographic assumptions (like collision-resistant hash functions or SNARGs) and specific derandomization complexity assumptions.

Original authors: Marshall Ball, Jiaxin Guan

Published 2026-08-11

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Marshall Ball, Jiaxin Guan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Digital Storage Heist

Imagine a world where you can prove you own a massive library of books without ever showing a single page. This is the heart of Proofs of Space, a concept in the field of cryptography and computer science. It's like a digital landlord who wants to make sure a tenant actually has a warehouse full of furniture, not just a clever drawing of furniture. The landlord (the Verifier) needs to be sure the tenant (the Prover) is using a huge amount of persistent memory to store data, rather than just keeping a tiny note that says "I have the furniture" and then magically conjuring the furniture only when asked.

For years, the only way to build these digital warehouses relied on a magical, imaginary tool called a "Random Oracle." Think of this as a magical black box that spits out perfectly random, unpredictable answers every time you ask a question. While useful for theory, it's like building a house on a foundation of pure magic; we don't know if it would hold up in the real world. The big question for scientists has been: Can we build a secure Proof of Space using only real, physical laws of computing, without relying on magic boxes? This paper dives into that very question, using the tools of complexity theory—the study of how hard problems are to solve—to see if we can construct these proofs from scratch.

The Paper's Big Idea: The "Deep" String

The authors, Marshall Ball and Jiaxin Guan, present a new, elementary framework for building Proofs of Space without magic. Their main finding is that you can create these proofs if you have two specific ingredients: a cryptographic assumption (like collision-resistant hash functions) and a "derandomization" assumption (a belief about how hard certain computer problems are for powerful, non-deterministic machines).

To understand their trick, imagine you need to prove you have a giant, messy pile of sand (the data). The old way required a magic box to guarantee the sand couldn't be compressed. The authors realize that in the real world, we don't need the sand to be impossible to compress; we just need it to be hard to compress quickly.

They introduce a concept called Computational Depth. Think of a string of data as a story.

The Setup: The Prover takes a tiny seed (a short story summary) and spends a long time (Phase 1) expanding it into a massive, detailed novel (the data).
The Catch: The Verifier then asks for specific pages from that novel.
The Trap: If the Prover didn't actually write the whole novel and just kept the short summary, they would need to re-write the pages from scratch. But the Verifier gives them only a tiny amount of time (Phase 2) to do this.

The authors show that if you assume certain hard problems exist (specifically, that some problems are too hard for "nondeterministic" circuits to solve quickly), you can create a function that turns a short seed into a long string. This string is "deep": it can be generated from a short seed if you have plenty of time, but it cannot be reconstructed from a short seed if you are in a hurry. It's like a puzzle that takes a year to solve but only a minute to check; if you try to solve it in a minute, you simply can't.

How the Proof Works: The "Merkle Tree" and the "Magic Spell"

The paper outlines a two-step protocol to test this "depth."

Phase 1: The Setup (The Long Wait)
The Verifier sends a random seed to the Prover. The Prover spends a long time (let's say, hours) using their special "deep" function to turn that seed into a massive file of data. They then build a Merkle Tree on top of this data. Imagine the Merkle Tree as a digital fingerprint of the entire file. It's like a family tree where every leaf is a piece of data, and every branch is a hash (a unique digital fingerprint) of the two branches below it. At the very top is a single "Root" hash that represents the entire file. The Prover stores this massive file and the Root.

Phase 2: The Check (The Quick Quiz)
The Verifier suddenly asks for specific pages from the file (random indices). The Prover must quickly provide those pages and the "path" through the Merkle Tree that proves those pages belong to the original file.

Here is where the authors' cleverness shines. To stop the Prover from attempting to bypass the protocol (by just keeping the short seed and trying to guess the pages), they add a Succinct Argument (a short proof).

Option A (The Stronger Assumption): They use a "SNARG" (a very short, non-interactive proof) to prove that the Root hash they sent actually came from the file generated by the seed. This requires a strong assumption about the existence of certain cryptographic tools, but it keeps the storage overhead low.
Option B (The Weaker Assumption): They use a "Kilian-style" argument based on collision-resistant hash functions. This is a more standard, "safer" assumption, but it forces the honest Prover to store a bit more data (a "PCP" string) to prove the Merkle tree was built correctly.

What They Rule Out and What They Prove

The paper explicitly argues against the idea that Proofs of Space must rely on the Random Oracle model. They show that the "magic box" isn't necessary. Instead, they prove that if we accept the "derandomization assumption" (that some problems are hard for nondeterministic circuits), then Proofs of Space are possible.

They also address a specific type of attempt to bypass the protocol: what if the Prover stores a tiny bit of data and tries to "compress" the big file on the fly? The authors prove that if the Prover can convince the Verifier to accept, they must have stored a significant amount of data. Specifically, they show that a Prover attempting to bypass the protocol cannot store significantly less than the honest prover (e.g., if the honest prover stores $N$ bits, a Prover attempting to bypass the protocol cannot get away with storing much less than $N$ bits, depending on the specific construction used).

The Bottom Line

This paper doesn't claim to have built a commercial product ready for your smartphone today. Instead, it provides a theoretical blueprint. It demonstrates that the "impossible" task of proving you have a warehouse of data without magic is actually possible, provided we accept certain standard beliefs about the hardness of computer problems.

They show that:

It works: You can build these proofs using "computational depth" instead of magic.
It's efficient: The honest user doesn't need to do anything too crazy, though they do need to store the data.
It's secure: If someone tries to bypass the protocol by storing less data, the math says they will almost certainly get caught, assuming the underlying hard problems remain hard.

In short, Ball and Guan have taken the "Proof of Space" out of the realm of magical black boxes and planted it firmly in the soil of complexity theory, showing us that with the right assumptions, we can build digital warehouses that are as secure as the laws of computation allow.

Technical Summary: A Complexity-Theoretic Approach to Proofs of Space

Problem Statement
Proofs of Space (PoS), introduced by Dziembowski et al. [DFKP15], are two-phase protocols allowing a Prover to convince an efficient Verifier that it has allocated a significant amount of persistent memory. The protocol consists of an initialization phase (long duration) where the Prover stores data, and an execution phase (short duration) where the Verifier challenges the Prover to prove the data is still stored.

A critical limitation of existing PoS protocols is that their security proofs rely heavily on the Random Oracle Model (ROM) or ad hoc cryptographic assumptions. Specifically, they depend on the simultaneous incompressibility and extractibility of random oracle queries. To date, no constructions are known to be secure in the plain model (without random oracles) based on standard cryptographic assumptions alone. There is a lack of clean, falsifiable assumptions regarding cryptographic hash functions that suffice for the provable security of these constructions.

Methodology and Framework
This paper presents an elementary framework for constructing PoS in the plain model by combining derandomization assumptions with cryptographic assumptions. The core insight is that a PoS requires a string $\sigma$ that is paradoxically both compressible from a short description (given sufficient time $T$ ) and incompressible from any slightly shorter description (within a short time $t$ ).

The authors formalize this using the complexity-theoretic notion of computational depth (introduced by Antunes et al. [AFvMV06]). They seek a function $f$ with high computational depth:

Long-time compressibility: $f(x)$ can be computed from a short seed $x$ in time $T$ .
Short-time incompressibility: $f(x)$ cannot be reconstructed from any description shorter than $|f(x)|$ within time $t$ , even given $x$ .

The construction proceeds in three main steps:

Constructing High-Depth Functions:
The authors utilize seed-extending Pseudorandom Generators (PRGs) against nondeterministic distinguishers. Under the assumption that $E = \text{DTIME}[2^{O(n)}]$ requires exponential-size nondeterministic circuits (a standard assumption used to show $\text{AM} = \text{NP}$ ), they construct PRGs that are hard for nondeterministic circuits.
- To achieve overwhelming probability of incompressibility (rather than just noticeable error), they employ multiplicative PRGs against nondeterministic distinguishers. These preserve the probability of negligible events, ensuring that the output of the PRG remains incompressible with overwhelming probability.
- To handle approximate incompressibility (resilience to Hamming distance errors), they compose the PRG with list-decodable error-correcting codes (ECC). This ensures that even if an adversary recovers a string close to $f(x)$ , the original string remains incompressible.
The Extraction Lemma:
A central technical contribution is the Extraction Lemma (Lemma 11). It states that if a prover can maintain a small state $S$ and successfully answer verification challenges with non-negligible probability, then the underlying string $y = f(x)$ is approximately compressible.
- The lemma uses a Hitting Set Generator (HSG) to deterministically select a set of "useful" challenge indices that cover a large fraction of the stored string.
- This allows an extractor to recover most of the bits of $y$ from the prover's small state within time $t$ , contradicting the assumed incompressibility of $f$ .
Protocol Instantiation:
The framework is instantiated into two specific PoS protocols, differing in their cryptographic assumptions and storage overhead:
- Construction 1 (SNARG-based): Uses a Semi-Universal Non-Interactive Argument (SNARG) for $P$ . The Prover stores the Merkle root of $f(x)$ and a succinct proof that the root corresponds to $f(x)$ . This relies on the existence of SNARGs for $P$ (a strong assumption) but offers near-optimal storage for the honest prover ( $N$ bits).
- Construction 2 (Kilian-based): Uses Kilian's interactive argument system based on PCPs and Collision-Resistant Hash Functions (CRHF). The Prover must store the PCP string of the computation $f(x)$ , leading to higher honest storage requirements ( $N + \tilde{O}(T)$ ), but relies on weaker cryptographic assumptions (CRHF + derandomization).

Key Results
The paper establishes the following theorems (informally):

Theorem 1: Assuming $E$ is hard for exponential-size nondeterministic circuits, there exist explicit functions that are time- $t$ incompressible to size $N - O(\rho N \log(1/\rho))$ .
Theorem 2 (SNARG instantiation): Assuming $E$ is hard for exponential-size nondeterministic circuits, one-way functions, and a semi-universal SNARG for $P$ , there exists a PoS where the honest prover stores $N$ bits, and the scheme is secure against any prover using $(1-o(1))N$ bits.
Theorem 3 (CRHF instantiation): Assuming $E$ is hard for exponential-size nondeterministic circuits and collision-resistant hash functions, there exists a PoS where the honest prover stores $N$ bits, and the scheme is secure against any prover using $N^{1/c}$ bits (for some constant $c$ ).

Significance and Claims
The authors emphasize that their work provides a pedagogically clean, generic feasibility result for PoS in the plain model.

Breaking the ROM Barrier: They demonstrate that PoS can be constructed without random oracles, relying instead on standard derandomization assumptions (hardness of $E$ against nondeterministic circuits) combined with standard cryptographic primitives.
Trade-offs: The paper highlights the trade-off between cryptographic assumptions and storage efficiency. The SNARG-based approach minimizes honest prover storage but requires stronger assumptions. The Kilian-based approach uses weaker assumptions (CRHF) but requires the honest prover to store a PCP of the computation, increasing storage significantly.
Limitations: The authors explicitly state that their focus is on theoretical feasibility, not sophisticated threat models or practical protocols. They note that while their framework yields PoS, it is not immediately clear how to adapt these ideas to construct Memory-Hard Functions (MHFs), a related object often derived from ROM-based PoS. Additionally, they acknowledge that handling composition (a single prover interacting with many verifiers) requires further work to ensure storage costs do not amortize.

In summary, this work bridges the gap between complexity theory and cryptographic protocols, showing that the "hardness" required for Proofs of Space can be derived from fundamental derandomization assumptions rather than heuristic random oracle models.