A Complexity-Theoretic Approach to Proofs of Space

This paper introduces a novel framework for constructing Proofs of Space (PoS) protocols in the plain model, without relying on the random oracle model, which all prior constructions required. The authors present a complexity-theoretic approach based on derandomization assumptions and cryptographic assumptions.

Key Contributions:

1. Core Insight: The paper identifies that PoS requires strings that are simultaneously compressible (expandable from a short description in long time T) and incompressible (cannot be expanded from a short description in short time t). This corresponds to the complexity-theoretic notion of computational depth.

2. Main Construction Framework: The authors provide an elementary framework for constructing PoS from:

• Functions with high computational depth (derived from PRGs against nondeterministic distinguishers)

• Succinct arguments (either SNARGs for P or Kilian-style PCP-based arguments)

• Merkle tree-based vector commitments

3. Technical Results:

• Theorem 1 (Informal): Under the assumption that E = DTIME(2 O(n)) is hard for exponential-size nondeterministic circuits, there exists an explicit function f: 0,1 poly log N → 0,1 N computable in polynomial time that is time-t-incompressible to even S = N - O(ρN log2(1/ρ) - polylog N) bits within relative distance ρ.

• Theorem 2 (Informal): Assuming E is hard for exponential-size nondeterministic circuits, one-way functions, and semi-universal SNARGs for P, there is a PoS where the honest prover stores N bits and is secure against any cheating prover using (1-o(1))N storage.

• Theorem 3 (Informal): Assuming E is hard for exponential-size nondeterministic circuits and collision-resistant hash functions, there is a constant c such that there is a PoS where the honest prover stores N bits and is secure against any cheating prover using N(1/c) storage.

4. Technical Approach:

• The paper shows that PRGs against nondeterministic distinguishers yield functions with high computational depth

• It introduces a multiplicative PRG notion to achieve overwhelming probability guarantees despite black-box barriers to negligible error

• The extraction lemma (Lemma 11) is the core technical tool, showing that if a cheating prover succeeds, one can extract an approximate compression of the incompressible string

• The framework uses hitting set generators (HSGs) to efficiently encode useful queries for the extraction

5. Two Instantiations:

• Via SNARGs for P: Achieves nearly optimal parameters with minimal storage overhead

• Via Kilian-style arguments: Requires only collision-resistant hashing but the honest prover must store a PCP of the computation, leading to larger storage requirements

6. Open Problems: The paper discusses composition (amortization resistance), adapting the approach to memory-hard functions, and using GKR-style proof systems to reduce assumptions.

The paper emphasizes that its focus is on elementary, pedagogically clean, generic feasibility; not sophisticated threat models and practical protocols.

Improvement 1: Provably Secure AI Proof-of-Computation Systems

The framework enables an AI system to generate verifiable proofs that it performed a specific computation (e.g., training a model on a dataset) without revealing the data or relying on trusted random oracles. The improved system can produce succinct, non-interactive proofs of work that are secure against adversarial provers with near-optimal storage, using only standard cryptographic assumptions (e.g., one-way functions, collision-resistant hashing). This is useful for decentralized AI training verification, where a model trainer can prove they used N compute-steps or stored N parameters without a trusted third party.

Improvement 2: Memory-Hard AI Inference with Guaranteed Resource Usage

By instantiating the PoS framework with functions of high computational depth, an AI system can be designed to require a minimum amount of memory (e.g., for large-scale neural network inference) that cannot be compressed or shortcut by an adversary. The improved system can enforce that any AI model serving a request must use at least N bits of memory, preventing cheap approximations or distillation attacks that reduce memory footprint. This is valuable for anti-piracy in commercial AI APIs, where the provider wants to ensure the client cannot run a smaller model.

Improvement 3: Robust AI Model Fingerprinting via Incompressible Embeddings

The paper’s construction of time-t-incompressible strings (Theorem 1) can be used to embed unique, unforgeable fingerprints into AI models. The improved system can generate a model watermark that is: (a) expandable from a short secret key in long time T (so the owner can recover it), but (b) incompressible to any adversary in short time t (so an attacker cannot extract or remove it without massive computation). This enables tamper-evident AI models where any pruning, quantization, or fine-tuning that reduces storage below the threshold is provably detectable.

Improvement 4: Efficient AI Audit Logs with Succinct Proofs of Storage

Using the SNARG-based instantiation, the improved AI system can maintain an audit log (e.g., of training data access or inference requests) that is stored in N bits, and any auditor can verify the log’s integrity with a sublinear-size proof. The system can prove that it has retained the full log (not deleted or compressed it) using only O(polylog N) communication, even against a malicious prover with (1-o(1))N storage. This is directly applicable to regulatory compliance for AI systems that must prove data retention (e.g., GDPR or financial audit requirements).

Improvement 5: AI Systems Resilient to Black-Box Compression Attacks

The paper’s multiplicative PRG and extraction lemma (Lemma 11) provide a blueprint for building AI components (e.g., feature extractors or generative models) that are inherently resistant to distillation or knowledge transfer. The improved system can use these tools to ensure that any attempt to compress the model’s internal representation (e.g., via a smaller student network) fails unless the attacker uses more than T time, making model stealing computationally infeasible. This is a direct improvement over current adversarial robustness methods, which lack formal guarantees against storage-bounded attackers.

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) = is hard for exponential-size nondeterministic circuits (an assumption introduced to show =), 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.