# Zero-Knowledge Proofs in Sublinear Space

Logan Nye

► To cite this version:

Logan Nye. Zero-Knowledge Proofs in Sublinear Space. 2025. hal-05157224

HAL Id: hal-05157224

https://hal.science/hal-05157224v1

Preprint submitted on 11 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Zero-Knowledge Proofs in Sublinear Space

Logan Nye, MD

Carnegie Mellon University School of Computer Science
5000 Forbes Ave Pittsburgh, PA 15213 USA

lnye@andrew.cmu.edu

ORCID: 0009-0002-9136-045X

Abstract

Modern zero-knowledge proof (ZKP) systems, essential for privacy and verifiable computa-
tion, suffer from a fundamental limitation: the prover must use an amount of memory that
scales linearly with the size of the computation (T), making them impractical for resource-
constrained devices and prohibitively expensive for large-scale tasks. This paper overcomes this
long-standing barrier by constructing the first ZKP prover with sublinear space complexity. Our
core contribution is a novel equivalence, demonstrating that the algebraic process of generating
a proof can be reframed as an instance of the classic Tree Evaluation problem. By leveraging
a recent, remarkably space-efficient algorithm for this problem, we design a “streaming” prover
that recursively constructs the proof without ever storing the full computational trace. This ap-
proach quadratically reduces the prover’s memory requirement from O(T) to O(√T log T) while
provably preserving the exact same proof size, verification time, and cryptographic security
guarantees of the original system. This breakthrough transforms verifiable computation from a
specialized, server-bound task into one feasible on everyday devices, unlocking new applications
in decentralized systems, on-device machine learning, and privacy-preserving technologies.
# 1 Introduction

Zero-knowledge proof systems, a cornerstone of modern cryptography, enable a prover to convince a verifier of a statement's truth without revealing any information beyond the statement's validity. In recent years, remarkable progress has yielded constructions—such as SNARKs and STARKs [1, 2]—with succinct proofs and near-instantaneous verification. These advances have catalyzed real-world applications ranging from private cryptocurrency transactions [3] to verifiable machine learning and blockchain scalability solutions.

Despite this progress, one fundamental bottleneck has persisted across all practical constructions: *proof generation requires space linear in the size of the computation*. To prove the execution of a computation with $T$ steps, existing provers must materialize the complete execution trace—a record of the machine's state at every step—requiring $\Theta(T)$ memory. This linear scaling is not merely an implementation artifact; it is deeply embedded in the algebraic machinery of modern provers, which encode this entire trace into large polynomials. This memory requirement severely limits the scale of computations that can be proven, creating a hard wall for deployment on resource-constrained devices like mobile phones or IoT sensors and making proofs for web-scale computations prohibitively expensive.

## 1.1 Prior Work and Technical Barriers

Current ZKP systems are fundamentally *trace-bound*: their algebraic constructions require random access to the entire execution trace. This dependency manifests in several critical operations:

* **Polynomial Interpolation:** Converting the execution trace to polynomials via Fast Fourier Transforms (FFTs) requires the complete trace to be available in memory simultaneously. For example, in STARK systems [2], the FFT computation over a trace of size $T$ requires $\Omega(T)$ space to store intermediate values during the transformation.

* **Permutation Arguments:** Modern systems employ running-product arguments to enforce memory consistency, requiring global accumulation across the entire trace. The permutation polynomial $z(X)$ must accumulate values over all $T$ steps, necessitating storage of the complete trace during computation.

* **Global Consistency Checks:** Boundary conditions and cross-block dependencies necessitate random access patterns that cannot be efficiently streamed.

These architectural constraints have made the linear space requirement seem insurmountable. Prior attempts to reduce prover memory have focused on optimizing constants or parallelization, but none have broken the fundamental $\Theta(T)$ barrier. Our work overcomes this limitation by replacing global trace operations with local, recursive cryptographic operations.

## 1.2 Our Contribution: A Sublinear-Space Prover

In this work, we resolve this fundamental limitation by establishing a novel and profound connection between computational complexity theory and applied cryptography. We demonstrate that the task of generating a zero-knowledge proof is mathematically equivalent to the **Tree Evaluation** problem. This equivalence allows us to leverage a recent, powerful algorithm for space-efficient tree evaluation [4] to construct the first zero-knowledge prover with sublinear space complexity.

**Theorem 1 (Main Result, Informal).** There exists a zero-knowledge proof system where, for a $T$-step computation, the prover operates in $O(\sqrt{T \log T})$ space. This is achieved while provably maintaining computationally indistinguishable soundness, zero-knowledge properties, proof size, and verifier complexity compared to the corresponding linear-space system.
**Theorem 2 (Main Result, Formal).** Given a zero-knowledge proof system for arithmetic circuits built upon an additively homomorphic, computationally binding, and computationally hiding polynomial commitment scheme (PCS), and a computation of size $T$, we construct a prover $P'$ such that:

1. $P'$ operates in $O(\sqrt{T \log T})$ space.

2. The distribution of proofs $\pi'$ generated by $P'$ is computationally indistinguishable from the distribution of proofs $\pi$ generated by the original prover $P$ for any statement in the language.

3. The soundness error and zero-knowledge properties are preserved.

This result represents a quadratic improvement in prover space, transforming terabyte-scale memory requirements into megabytes and making large-scale verifiable computation practical for the first time.

## 1.3 Technical Overview

Our approach is a synthesis of ideas from complexity theory and cryptography, proceeding in three conceptual steps:

1. **Structural Decomposition of Computation.** We first adapt the framework of Williams [5], who showed that any Turing machine computation can be decomposed into a directed acyclic graph (the computation graph) where nodes represent small computation blocks and edges represent data dependencies. This graph has bounded indegree and a regular, recursive structure.

2. **The Tree Evaluation Equivalence.** This is our core technical insight. We demonstrate that generating the polynomial commitments for a ZKP is mathematically equivalent to evaluating functions on an implicit, exponentially-large tree derived from the computation graph. We show that the algebraic relations that bind a ZKP trace together (e.g., state transitions, memory consistency) can be expressed as a recursive function. This allows us to compose commitments for sub-computations without ever materializing the full trace. Each node in our computation tree takes cryptographic commitments from its children and computes a commitment for its own local block.

3. **Space-Efficient Cryptographic Evaluation.** We apply the remarkably space-efficient Cook-Mertz algorithm [4] to evaluate our implicitly defined computation tree. By carefully balancing the block size parameter, we achieve an overall prover space complexity of $O(\sqrt{T \log T})$, yielding the final zero-knowledge proof without ever storing the complete trace in memory.

## 1.4 Significance and the Principle of Algorithmic Transference

This work establishes the first fundamental bridge between the space complexity of general algorithms and the space complexity of cryptographic protocols. The mathematical equivalence we prove introduces a new design paradigm we call the **Principle of Algorithmic Transference**:

**Definition 1 (Principle of Algorithmic Transference).** Let $\mathcal{A}$ be an algorithm for a computational model $\mathcal{M}$ with a space-efficient evaluation scheme $E_A$. Let $\mathcal{K}$ be a cryptographic protocol for verifying computations in $\mathcal{M}$. We say $\mathcal{K}$ adheres to the Principle of Algorithmic Transference with respect to $\mathcal{A}$ if the core cryptographic relations of $\mathcal{K}$ can be expressed as a function $F_{\mathcal{K}}$ that is compatible with $E_A$, thereby allowing $\mathcal{K}$ to inherit the space complexity of $\mathcal{A}$.
Our result is not merely a theoretical curiosity. By quadratically reducing the memory footprint of the prover, we unlock new deployment scenarios for verifiable computation on mobile devices, embedded systems, and in large-scale decentralized networks, fundamentally changing the economics and feasibility of ensuring computational integrity and privacy.

# 2 Preliminaries

In this section, we define the core concepts and establish the notation used throughout the paper. We model computations as arithmetic circuits, formalize the properties of polynomial commitment schemes, and define the Tree Evaluation problem.

## 2.1 Notation

We denote the security parameter by $\lambda$. We work over a finite field $\mathbb{F}$ such that $T$ divides $|\mathbb{F}| - 1$, ensuring the existence of a primitive $T$-th root of unity $\omega \in \mathbb{F}$. We assume the field size $|\mathbb{F}|$ is super-polynomial in $\lambda$, and the security of cryptographic primitives holds for polynomials of degree up to $T$. A function $\nu: \mathbb{N} \to \mathbb{R}$ is negligible if for every positive polynomial $p(\cdot)$, there exists an integer $N$ such that for all $n > N$, $\nu(n) < 1/p(n)$. We use $T$ to denote the total number of steps (or gates) in a computation and $k$ for the number of memory regions or registers. We use '$poly(\lambda)$' to denote an unspecified function that is polynomial in $\lambda$. We use $b_{\text{blk}}$ to denote computation block size and $b_{\text{val}}$ to denote the bit-length of values in tree evaluation.

## 2.2 Computational Model: Arithmetic Circuits

We model computations as arithmetic circuits over a finite field $\mathbb{F}$. This model is general and directly corresponds to the relations proven by many modern ZKP systems. We first establish the bridge between Turing machine computations and arithmetic circuits.

**Lemma 1** (Turing Machine to Arithmetic Circuit Compilation). *Any $T$-step computation on a single-tape Turing machine can be efficiently compiled into an arithmetic circuit of size $O(T \log T)$ over a finite field $\mathbb{F}$. This transformation preserves the computational semantics and allows the structural decomposition techniques of Williams [5] to be applied to the circuit model.*

*Proof Sketch.* This follows from standard techniques in the Cook-Levin theorem literature. Each step of the Turing machine is encoded using $O(\log T)$ field elements to represent the state, head position, and tape symbols. The transition function is expressed as arithmetic constraints. The resulting circuit has size $O(T \log T)$ and can be evaluated gate-by-gate to simulate the original computation. □

**Definition 2** (Arithmetic Circuit). *An arithmetic circuit $C: \mathbb{F}^{n+n'} \to \mathbb{F}^m$ is a directed acyclic graph where nodes are called gates. Gates have an indegree of 0 (input gates or constant gates), 1 (unary operations), or 2 (binary operations). Input gates are labeled with input variables from a public statement $x \in \mathbb{F}^n$ and a private witness $w \in \mathbb{F}^{n'}$. Internal gates are labeled with arithmetic operations from $\{+, \times, -, \text{copy}\}$ over $\mathbb{F}$. A subset of gates are designated as output gates. The size of the circuit, denoted $T$, is the total number of gates.*

**Definition 3** (Execution Trace). *For an arithmetic circuit $C$ of size $T$ and a given assignment to its input gates, the execution trace $\tau$ is represented as a matrix $W \in \mathbb{F}^{T \times k}$ with $k$ columns (memory regions/registers) and $T$ rows (computation steps). Each entry $W[i,j]$ represents the value in register $j$ at step $i$, following the Algebraic Intermediate Representation (AIR) model. The correctness of a computation is captured by a set of gate constraints. For each gate $i$, there exists a constraint polynomial $P_i(W[i, \cdot], W[i+1, \cdot]) = 0$ that must hold between consecutive rows. A valid trace $\tau$ is one where these constraints are satisfied for all $i \in [T-1]$.*
In standard ZKP constructions, the execution trace $\tau$ is encoded as one or more trace polynomials. For instance, a trace polynomial $f_{\tau}(X)$ can be defined as the unique polynomial of degree $< T$ that interpolates the trace values over a domain $H = \{\omega^0, \omega^1, \dots, \omega^{T-1}\} \subset \mathbb{F}$ (i.e., $f_{\tau}(\omega^i) = w_i$ for $\omega$ a primitive $T$-th root of unity). The prover's main task is to commit to these trace polynomials.

## 2.3 Polynomial Commitment Schemes

Our construction is generic and can be instantiated with any polynomial commitment scheme (PCS) that satisfies certain properties.

**Definition 4 (Polynomial Commitment Scheme).** A polynomial commitment scheme for polynomials over $\mathbb{F}$ consists of a tuple of algorithms (Setup, Commit, Open, Verify):

* Setup$(1^{\lambda}, d) \to pp$: A probabilistic algorithm that takes a security parameter $\lambda$ and a maximum degree $d$ and outputs public parameters $pp$.

* Commit$(pp, f(X)) \to com$: A deterministic algorithm that takes the public parameters and a polynomial $f(X)$ of degree at most $d$ and outputs a commitment $com$.

* Open$(pp, f(X), z) \to \pi$: A deterministic algorithm that takes the public parameters, a polynomial $f(X)$, and a point $z \in \mathbb{F}$, and outputs a proof $\pi$ for the evaluation $y = f(z)$.

* Verify$(pp, com, z, y, \pi) \to \{0, 1\}$: A deterministic algorithm that verifies that the commitment $com$ is to a polynomial that evaluates to $y$ at point $z$.

We require the PCS to satisfy three properties:

**Definition 5 (Binding Security Game).** The binding property is defined via the security game Game$_A^{\text{Bind}}(1^{\lambda})$:

1. The challenger runs $pp \leftarrow \text{Setup}(1^{\lambda}, d)$ and gives $pp$ to adversary $\mathcal{A}$.

2. $\mathcal{A}$ outputs $(com, z, y, \pi, y', \pi')$.

3. $\mathcal{A}$ wins if $y \neq y'$ and both $\text{Verify}(pp, com, z, y, \pi) = 1$ and $\text{Verify}(pp, com, z, y', \pi') = 1$.

The PCS is computationally binding if for all PPT adversaries $\mathcal{A}$, $\Pr[\mathcal{A} \text{ wins}]$ is negligible in $\lambda$.

**Definition 6 (Hiding Security Game).** The hiding property is defined via the security game Game$_A^{\text{Hide}}(1^{\lambda})$:

1. The challenger runs $pp \leftarrow \text{Setup}(1^{\lambda}, d)$ and gives $pp$ to adversary $\mathcal{A}$.

2. $\mathcal{A}$ outputs two polynomials $f_0, f_1$ of degree at most $d$.

3. The challenger chooses $b \leftarrow \{0, 1\}$ uniformly and computes $com \leftarrow \text{Commit}(pp, f_b)$.

4. $\mathcal{A}$ outputs a guess $b'$.

5. $\mathcal{A}$ wins if $b = b'$.

The PCS is computationally hiding if for all PPT adversaries $\mathcal{A}$, $|\Pr[\mathcal{A} \text{ wins}] - 1/2|$ is negligible in $\lambda$.

**Correctness:** For any valid inputs, Verify correctly accepts proofs generated by Open for commitments from Commit.

**Additive Homomorphism:** For our construction, we also require the PCS to be additively homomorphic, formally defined as: For any two polynomials $f(X)$ and $g(X)$,

$$ \text{Commit}(pp, f(X)) + \text{Commit}(pp, g(X)) = \text{Commit}(pp, f(X) + g(X)) $$

where the $+$ on the left is a publicly computable operation on commitments (e.g., elliptic curve point addition). Schemes like KZG [6] and many variants satisfy this property.
## 2.4 The Tree Evaluation Problem

Our space-efficient prover relies on an algorithm for the Tree Evaluation problem.

**Definition 7 (Tree Evaluation Problem).** An instance of the *Tree Evaluation* problem is a rooted tree $\mathcal{T}$ where:

* Each leaf node is labeled with a value, a $b_{val}$-bit string.

* Each internal node $v$ has an ordered list of $d_v \le d$ children and is labeled with a function $f_v : (\{0, 1\}^{b_{val}})^{d_v} \to \{0, 1\}^{b_{val}}$.

* The value of an internal node $v$ is defined recursively as the result of applying its function $f_v$ to the values of its children.

The problem is to compute the value of the root node of $\mathcal{T}$. The height of the tree is denoted by $h$.

The naive depth-first traversal algorithm for this problem requires $O(h \cdot b_{val})$ space. However, a recent breakthrough by Cook and Mertz provides a substantially more space-efficient solution.

**Theorem 3 (Cook-Mertz Algorithm [4]).** *Tree Evaluation on a tree with maximum height $h$, maximum degree $d$, and node values of bit-length $b_{val}$ can be solved in $O(d \cdot b_{val} + h \log(d \cdot b_{val}))$ space.*

This theorem is the algorithmic engine that powers our sublinear-space prover. Our central challenge, which we overcome in this paper, is to demonstrate that cryptographic proof generation can be framed as an instance of this problem with the right parameters.

# 3 From Computations to Graphs

The first step in our construction is to impose a regular, block-based structure onto an arbitrary computation. This process, adapted from the complexity-theoretic work of Hopcroft, Paul, and Valiant [7] and Williams [5], allows us to reason about local data dependencies. We show how to transform any arithmetic circuit into an equivalent “block-respecting” form and then define its corresponding computation graph.

## 3.1 Block-Respecting Decomposition

We conceptually partition the execution trace matrix of an arithmetic circuit into discrete blocks using the AIR (Algebraic Intermediate Representation) model established in Section 2.

**Definition 8 (Block-Respecting Computation).** A computation corresponding to an arithmetic circuit $C$ of size $T$ with execution trace matrix $W \in \mathbb{F}^{T \times k}$ is $(b_{blk}, B)$-block-respecting, for parameters $b_{blk}$ (block size) and $B = \lceil T/b_{blk} \rceil$ (number of blocks), if:

1. **Time Blocks:** The $T$ rows of $W$ are partitioned into $B$ consecutive time blocks $W^{(1)}, W^{(2)}, \dots, W^{(B)}$, where each $W^{(i)} \in \mathbb{F}^{b_{blk} \times k}$ contains at most $b_{blk}$ consecutive rows of the trace matrix.

2. **Memory Regions:** The $k$ columns of $W$ represent $k$ memory regions (registers), where $k$ is a small constant determined by the circuit's constraint structure.

3. **Locality:** For any row $i$ in time block $t$, the constraint polynomial $P_i(W[i, \cdot], W[i+1, \cdot]) = 0$ depends only on values within the current time block and at most $k$ values from previous time blocks, corresponding to the natural row-to-row constraints of the AIR.
For arithmetic circuits, this decomposition is achieved by partitioning the topologically ordered execution trace matrix into consecutive row blocks.

**Lemma 2 (Block-Respecting Transformation).** *Any arithmetic circuit C of size T with execution trace matrix $W \in \mathbb{F}^{T \times k}$ naturally yields a $(b_{blk}, [T/b_{blk}])$-block-respecting computation with no overhead in time or space.*

*Proof.* Consider the execution trace matrix $W \in \mathbb{F}^{T \times k}$ for circuit C:

1. **Matrix Partitioning:** Partition the $T$ rows into $B = \lceil T/b_{blk} \rceil$ consecutive blocks of size at most $b_{blk}$.

2. **Block-Respecting Property:** The constraint polynomials $P_i(W[i, \cdot], W[i+1, \cdot]) = 0$ for the AIR naturally satisfy the locality condition, as each constraint relates only adjacent rows and a bounded number of registers.

3. **Evaluation:** The original circuit evaluator processes the trace row-by-row, which directly corresponds to block-by-block evaluation with the same time and space complexity.

This transformation preserves all computational semantics while imposing the required block structure. □

## 3.2 The Computation Graph

From a block-respecting computation, we construct a graph that captures the flow of information between blocks using the AIR trace structure.

**Definition 9 (Computation Graph).** Let $C$ be a $(b_{blk}, B)$-block-respecting computation with execution trace matrix $W \in \mathbb{F}^{T \times k}$. The computation graph $G_C = (V, E)$ is a directed acyclic graph defined as follows:

* **Nodes V:** The set of nodes $V$ contains two types of vertices:

- **Computation Nodes:** A node $(m, t)$ for each register $m \in [k]$ and time block $t \in [B]$. This node represents the state of register $m$ (column $m$ of the trace) within the $t$-th block of rows.

- **Source Nodes:** A node $(m, 0)$ for each register $m \in [k]$. This node represents the initial contents of register $m$, such as public inputs or private witness values.

* **Edges E:** An edge $(u, v) \in E$ exists if the computation at node $v$ directly requires the data from node $u$. Formally, for a computation node $v = (m, t)$ with $t > 0$:

1. There is an edge from $(m, t-1)$ to $(m, t)$, representing the dependency on the same register from the previous time block.

2. For each register $m' \neq m$ such that the constraint polynomials for time block $t$ require reading register $m'$, there is an edge from $(m', t-1)$ to $(m, t)$.

3. For $t = 1$, there are edges from the appropriate source nodes $(m', 0)$ to $(m, 1)$ as determined by the circuit's input dependencies.

Crucially for our space-efficient prover, the structure of $G_C$ need not be stored. Given the static description of the arithmetic circuit $C$ and an identifier for a node $(m, t)$, the predecessors can be computed in polylogarithmic space by inspecting the circuit's constraint polynomials.

**Lemma 3 (Bounded Indegree).** Each computation node $(m, t)$ in $G_C$ has an indegree of at most $k$.
*Proof.* Consider a computation node $v = (m, t)$. By the AIR constraint structure, the values in register $m$ at time block $t$ depend only on:

1. The value of register $m$ from the previous time block $(m, t-1)$.

2. Values from at most $k-1$ other registers from the previous time block, as determined by the circuit's constraint polynomials.

Since there are $k$ registers total, the indegree is bounded by $k$. The constraint structure of arithmetic circuits ensures this bound is achieved. □

We define a function **SimBlock** that represents the local computation occurring at each node.

**Algorithm 1 SimBlock**

**Require:** Data blocks $\{D_1, D_2, \dots, D_r\}$ from predecessor nodes, time block index $t$, register $m$

**Ensure:** Output data block $D_{\text{out}}$ for register $m$ in time block $t$

1. inputs $\leftarrow$ ExtractInputs($\{D_1, \dots, D_r\}$)

2. **for** each row $i$ in time block $t$ **do**

3. Evaluate constraint $P_i(W[i, \cdot], W[i+1, \cdot]) = 0$ to compute $W[i+1, m]$

4. Store result in $D_{\text{out}}[i]$

5. **end for**

6. **return** $D_{\text{out}}$

**Lemma 4 (Graph Simulability).** *Given the contents of all predecessor nodes of a computation node $(m, t)$, the content of $(m, t)$ can be computed in $O(b_{\text{blk}})$ time and space using Algorithm 1.*

*Proof.* Algorithm 1 takes as input data from predecessor nodes, which by Lemma 3 is of size $O(k \cdot b_{\text{blk}})$. The algorithm evaluates at most $b_{\text{blk}}$ constraint polynomials within time block $t$ (lines 2-5). Each constraint evaluation takes constant time in the circuit model, so the total time is $O(b_{\text{blk}})$. The memory required to store the inputs and compute the outputs is $O(k \cdot b_{\text{blk}} + b_{\text{blk}}) = O(b_{\text{blk}})$, since $k$ is a fixed constant determined by the circuit structure. □

# 4 The Tree Evaluation Equivalence

This section presents our main conceptual contribution. We prove that the process of generating a zero-knowledge proof can be reframed as an evaluation on an implicit tree derived from the computation graph. This reframing replaces the monolithic generation of the trace with a recursive, space-efficient construction of cryptographic commitments.

## 4.1 From Computation Graphs to Implicit Trees

The computation graph $G_C$ is a directed acyclic graph (DAG). We can “unroll” this DAG into an equivalent tree structure, where shared nodes in the DAG are duplicated.

**Definition 10 (Computation Tree).** *Given a computation graph $G_C$ and a designated final output node $v_{\text{root}} \in G_C$ (e.g., $(1, B)$), the corresponding computation tree $\mathcal{T}_C$ is an implicitly defined tree where:*

* The root of $\mathcal{T}_C$ corresponds to the node $v_{\text{root}}$ in $G_C$.

* For any node $v$ in $\mathcal{T}_C$ corresponding to a node $u \in G_C$, its children in $\mathcal{T}_C$ correspond to the predecessors of $u$ in $G_C$.

* The leaves of $\mathcal{T}_C$ correspond to the source nodes of $G_C$.
## 4.3 The Main Equivalence Theorem

We now prove that evaluating this tree produces the same cryptographic object as a standard, linear-space prover.

**Theorem 4 (Tree Evaluation Equivalence).** Let $C$ be a $T$-step computation with execution trace $\tau$, and let $f_\tau(X)$ be its corresponding trace polynomial. There exists a computation tree $\mathcal{T}_C$ and a set of commitment tree functions $\{F_v\}$ such that:

1. Evaluating $\mathcal{T}_C$ from the leaves to the root yields a commitment $\text{com}_{\text{root}}$ that is computationally indistinguishable from $\text{Commit}(pp, f_\tau(X))$.

2. $\mathcal{T}_C$ has height $h = O(T/b_{\text{blk}})$, maximum degree $d = O(k)$, and each function $F_v$ is computable in $O(b_{\text{blk}} \cdot \text{poly}(\log T))$ time and $O(b_{\text{blk}})$ space.

*Proof.* We construct the computation tree $\mathcal{T}_C$ from the computation graph $G_C$ as defined previously. We use a PCS that is additively homomorphic. We prove the theorem in two parts.

**Correctness of Parameters:** The height $h = O(T/b_{\text{blk}})$ and degree $d = O(k)$ follow directly from the properties of the computation graph $G_C$. The complexity of $F_v$ follows from Lemma 4, as simulating the block takes $O(b_{\text{blk}})$ time, and generating a commitment to a size-$b_{\text{blk}}$ polynomial takes $O(b_{\text{blk}} \log b_{\text{blk}})$ field operations, hence $O(b_{\text{blk}} \cdot \text{poly}(\log T))$ time, using $O(b_{\text{blk}})$ space.

### Part 1: Correctness of the Final Commitment.

We first formally define the sub-trace polynomials. Let the evaluation domain for the trace polynomial be $H = \{\omega^0, \omega^1, \dots, \omega^{T-1}\}$ where $\omega$ is a primitive $T$-th root of unity. We partition $H$ into $B$ disjoint subdomains. For $i \in [B-1]$, let $H_i = \{\omega^{(i-1) \cdot b_{\text{blk}}}, \dots, \omega^{i \cdot b_{\text{blk}}-1}\}$ of size exactly $b_{\text{blk}}$. For the final block $B$, let $H_B = \{\omega^{(B-1) \cdot b_{\text{blk}}}, \dots, \omega^{T-1}\}$ of size $T - (B-1) \cdot b_{\text{blk}}$.

For each time block $i \in [B]$, define $f_i(X)$ as the unique polynomial of degree less than $|H_i|$ such that:

* $f_i(\omega^j) = w_j$ for $\omega^j \in H_i$, where $w_j$ is the trace value at position $j$

* $f_i(\omega^j) = 0$ for $\omega^j \notin H_i$

This can be achieved using Lagrange interpolation with zero-padding. The full trace polynomial is then $f_\tau(X) = \sum_{i=1}^B f_i(X)$, which is well-defined due to the disjoint support.

We prove by induction on the tree structure that the root of $\mathcal{T}_C$ computes $\text{Commit}(f_\tau)$:

**Base Case (Leaves):** Leaves correspond to source nodes $(m, 0)$ containing initial values for register $m$. Each leaf outputs a commitment $\text{Commit}(f_0^{(m)})$ where $f_0^{(m)}(X)$ interpolates the initial values for register $m$. This is correct by construction as these represent the input portion of the trace polynomial.

**Inductive Hypothesis:** For any node $v$ in $\mathcal{T}_C$ at height $j < h$, assume its children $c_1, \dots, c_{d_v}$ correctly output commitments $\text{com}_1, \dots, \text{com}_{d_v}$ where $\text{com}_i = \text{Commit}(g_i)$ and $g_i$ represents the sum of all sub-trace polynomials in the subtree rooted at child $c_i$.

**Inductive Step:** Consider node $v$ at height $j+1$ corresponding to computation node $(m, t)$ in $G_C$. Algorithm 2 computes:

1. The commitment $\text{com}_v = \text{Commit}(f_v)$ to its local sub-trace polynomial $f_v(X)$ for time block $t$ (lines 6-7).

2. The combined commitment: $\text{com}_{\text{out}} = \text{com}_v + \sum_{i=1}^{d_v} \text{com}_i$ (line 8).

By the inductive hypothesis, $\text{com}_i = \text{Commit}(g_i)$ where $g_i$ represents sub-trace polynomials from child subtrees. By the additive homomorphism property:

$$ \text{com}_{\text{out}} = \text{Commit}(f_v) + \sum_{i=1}^{d_v} \text{Commit}(g_i) = \text{Commit} \left( f_v + \sum_{i=1}^{d_v} g_i \right) $$
This equals $\text{Commit}(f_{\text{subtree}})$ where $f_{\text{subtree}}$ is the sum of all sub-trace polynomials in the subtree rooted at $v$.

By induction, the root outputs $\text{Commit}(\sum_{i=1}^B f_i) = \text{Commit}(f_\tau)$.

**Part 2: Correctness of Consistency.**

Define the predicate $\text{IsConsistent}(\text{aux})$ which is true if:

1. All boundary values represent valid register states

2. The permutation accumulator equals 1 at the final computation state (indicating a valid permutation)

We prove by strong induction from the root down that global consistency implies local consistency:

**Base Case (Root):** If $\text{IsConsistent}(\text{aux}_{\text{root}})$ holds, then the global constraints are satisfied.

**Inductive Step:** Consider a node $v$ with auxiliary data $\text{aux}_v$ such that $\text{IsConsistent}(\text{aux}_v)$ holds and the $\text{ConsistencyCheck}$ in $v$'s $F_v$ call passed. We must show $\text{IsConsistent}(\text{aux}_i)$ holds for all children $c_i$.

The consistency check verifies:

1. **Boundary Consistency:** $\text{aux}_i.\text{boundary\_vals}[m] = \text{expected input values}[m]$ for each register $m$

2. **Permutation Consistency:** The permutation accumulator is correctly propagated: $\text{aux}_v.\text{perm\_acc} = \text{aux}_{\text{children}}.\text{perm\_acc} \cdot \text{local\_contribution}$

Since the global constraint $\text{IsConsistent}(\text{aux}_v)$ holds and the local check passed, the boundary values and permutation state at each child must be consistent with the global execution trace. Therefore, $\text{IsConsistent}(\text{aux}_i)$ holds for all children $c_i$.

By strong induction, if the root passes global consistency checks, then all consistency checks throughout the tree must have passed, ensuring the committed polynomial corresponds to a valid, single execution trace.

This completes the proof that the root commitment corresponds to a valid, consistent execution trace polynomial $f_\tau(X)$ and is computationally indistinguishable from one generated by a standard linear-space prover. $\square$

# 5 The Sublinear-Space Prover

By combining our Tree Evaluation Equivalence (Theorem 4) with the space-efficient Cook-Mertz algorithm (Theorem 3), we construct our sublinear-space zero-knowledge prover. The core idea is to execute the proof generation not by materializing the trace, but by evaluating our implicit cryptographic computation tree.

## 5.1 The Streaming Prover Algorithm

The prover algorithm operates in a streaming fashion, never requiring the full execution trace in memory. It interacts with the computation tree $\mathcal{T}_C$ via a set of oracles that can be computed on-the-fly.

**Parameter Justifications:**

* **Security Parameter:** We set $\lambda = \Theta(\log T)$. This choice is standard and ensures that the cryptographic security (failure probability $2^{-\lambda}$) remains meaningful relative to the computational effort $T$ required to break the system non-cryptographically. It also ensures that the bit-length of commitments $O(\lambda)$ does not dominate the overall space complexity.
* **Block Size:** The parameter $b_{blk}$ is chosen to balance the $O(b_{blk})$ space required for local computation against the $O(T/b_{blk})$ term arising from the tree's height in the Cook-Mertz algorithm space bound.

<caption>**Algorithm 3 Sublinear-Space ZKP Prover**</caption>

**Require:** Computation $C$ (as an arithmetic circuit), witness $w$, public parameters $pp$.
**Ensure:** Zero-knowledge proof $\pi$.
1: **Parameterization:** Set block size $b_{blk} := \lfloor \sqrt{T \log \lambda} \rfloor$ where $\lambda = \Theta(\log T)$. Let $B := \lceil T/b_{blk} \rceil$.
2: **Graph Definition:** Conceptually define the $(b_{blk}, B)$-block-respecting computation graph $G_C$ from $C$. Define the implicit computation tree $\mathcal{T}_C$ rooted at the final computation node.
3: **Oracle Definition:** Define the oracles for the tree evaluation algorithm:
   * $O_{children}(v) \to (c_1, \dots, c_{d_v})$: Given a node identifier $v$, returns the identifiers of its children by inspecting the structure of $G_C$.
   * $O_{leaf}(v) \to (\text{com}, \text{aux})$: If $v$ is a leaf, computes the commitment to its initial data block.
   * $O_{func}(v, \text{inputs}) \to (\text{com}, \text{aux})$: The commitment tree function $F_v$ from Algorithm 2.
4: **Tree Evaluation:** Execute the Cook-Mertz algorithm to find the value of the root of $\mathcal{T}_C$.
5: $(\text{com}_{final}, \text{aux}_{final}) \leftarrow \text{CookMertzEvaluate}(\mathcal{T}_C, O_{children}, O_{leaf}, O_{func})$
6: **Proof Generation:** Using the final commitment $\text{com}_{final}$ and auxiliary data $\text{aux}_{final}$ (which contains information for boundary checks), generate the final opening proofs for the ZKP system. This may involve a final set of polynomial openings (e.g., for the permutation argument).
7: $\pi \leftarrow \text{GenerateFinalProof}(\text{com}_{final}, \text{aux}_{final})$
8: **return** $\pi$

## 5.2 Oracle Implementation Details

The key to the low space complexity is that the oracles themselves are space-efficient and can be computed without storing the full computation graph:

* $O_{children}(v)$: A node identifier $v$ is represented as a path descriptor requiring $O(\log T)$ space. The oracle computes predecessors by looking up the constraint polynomials for the circuit, which define the register dependencies. Since the constraint polynomials are small and constant-sized (determined by the circuit structure), this requires only streaming access to the circuit description without storing the entire graph $G_C$. The path descriptor allows navigation to any node in $O(\log T)$ space.

* $O_{leaf}(v)$: For source nodes, this oracle reads a $b_{blk}$-sized chunk of the private witness $w$ and computes commitments to initial register values. This requires $O(b_{blk})$ space for the witness chunk and cryptographic operations.

* $O_{func}(v, \text{inputs})$: This implements Algorithm 2, requiring $O(b_{blk})$ space for local computation and cryptographic operations.

The crucial property is that each oracle call uses space bounded by $O(b_{blk})$, and the graph structure can be navigated in polylogarithmic space without storage.
## 5.3 Complexity Analysis

We now formally analyze the space and time complexity of our prover.

**Theorem 5 (Sublinear Space Complexity).** *Assuming the security parameter $\lambda = \Theta(\log T)$, the prover in Algorithm 3 uses $O(\sqrt{T \log T})$ space.*

*Proof.* The total space is the sum of the space used by the Cook-Mertz algorithm and the space required by our oracles.

**Step 1: Oracle Space Analysis** The oracle $O_{\text{func}}$ implements Algorithm 2, which requires simulating a $b_{\text{blk}}$-step computation block and performing cryptographic operations. By Lemma 4 and Theorem 4, this requires $O(b_{\text{blk}})$ space. The other oracles require only logarithmic space to navigate the implicit graph structure. Thus, the oracle space complexity is $S_{\text{oracle}} = O(b_{\text{blk}})$.

**Step 2: Cook-Mertz Space Analysis** We apply Theorem 3 to our computation tree $\mathcal{T}_C$. From Theorem 4, the parameters of $\mathcal{T}_C$ are:

* Height: $h = O(T/b_{\text{blk}})$.

* Maximum degree: $d = O(k) = O(1)$.

* Node value bit-length: We break down $b_{\text{val}}$ into its components:

- **Commitment size:** A commitment in a typical scheme requires $O(\lambda)$ bits.

- **Auxiliary data size:** $\text{aux} = (\text{boundary\_vals}, \text{perm\_acc})$ where $\text{boundary\_vals} \in \mathbb{F}^k$ and $\text{perm\_acc} \in \mathbb{F}$. Since $|\mathbb{F}| \approx 2^\lambda$ for cryptographic security and $k = O(1)$, the auxiliary data requires $(k+1) \cdot \lambda = O(\lambda)$ bits.

Therefore, $b_{\text{val}} = O(\lambda) + O(\lambda) = O(\lambda)$.

The space complexity from the Cook-Mertz algorithm is:

$$S_{CM} = O(d \cdot b_{\text{val}} + (T/b_{\text{blk}}) \log(d \cdot b_{\text{val}})) = O(\lambda + (T/b_{\text{blk}}) \log \lambda)$$

**Step 3: Total Space Complexity** The total space complexity is:

$$S(T) = S_{\text{oracle}} + S_{CM} = O(b_{\text{blk}} + \lambda + (T/b_{\text{blk}}) \log \lambda)$$

**Step 4: Parameter Optimization** To minimize $S(T)$, we balance the terms $b_{\text{blk}}$ and $(T/b_{\text{blk}}) \log \lambda$ by setting:

$$b_{\text{blk}} \approx \frac{T \log \lambda}{b_{\text{blk}}}$$

which gives $b_{\text{blk}} = \sqrt{T \log \lambda}$.

**Step 5: Substitution and Simplification** With $\lambda = \Theta(\log T)$, we have $\log \lambda = \Theta(\log \log T)$, so the optimal choice is $b_{\text{blk}} = \sqrt{T \log T}$. Substituting back:

$$ 
\begin{aligned}
S(T) &= O\left(\sqrt{T \log T} + \log T + \frac{T}{\sqrt{T \log T}} \log \log T\right) \\
&= O\left(\sqrt{T \log T} + \log T + \sqrt{T} \frac{\log \log T}{\sqrt{\log T}}\right) \\
&= O\left(\sqrt{T \log T} + \log T + \sqrt{T \log \log T}\right) \\
&= O(\sqrt{T \log T})
\end{aligned}
$$

The last equality holds because $\sqrt{T \log T}$ dominates the other terms. $\square$

**Theorem 6 (Prover Time Complexity).** *The prover in Algorithm 3 runs in time $O(T \cdot \log T \cdot d^c \cdot \lambda^c)$ for some small constant $c$, which is $O(T \cdot \text{poly}(\log T))$.*
Proof. The time complexity has two main components:

**Cook-Mertz Algorithm Time:** The Cook-Mertz algorithm's time complexity involves computing low-degree extensions of the node functions, which depends on the degree $d$ and node value bit-length $b_{\text{val}}$. This contributes a factor of $d^c \cdot \lambda^c$ for some constant $c$ per effective node computation.

**Node Function Evaluation:** Each call to $O_{\text{func}}$ (Algorithm 2) requires:

* $O(b_{\text{blk}})$ time for SimBlock computation

* $O(b_{\text{blk}} \log b_{\text{blk}})$ time for polynomial interpolation and commitment

* $O(d)$ time for combining commitments homomorphically

This gives $O(b_{\text{blk}} \log b_{\text{blk}})$ time per node function evaluation.

The total number of effective node evaluations in the Cook-Mertz algorithm is bounded by the number of computation blocks $B = O(T/b_{\text{blk}})$, due to the algorithm's efficiency in avoiding redundant computations through low-degree extensions.

Therefore, the total time is:

$$ \text{Time} = O \left( \frac{T}{b_{\text{blk}}} \cdot b_{\text{blk}} \log b_{\text{blk}} \cdot d^c \cdot \lambda^c \right) = O(T \log b_{\text{blk}} \cdot d^c \cdot \lambda^c) $$

With $b_{\text{blk}} = \sqrt{T \log T}$ and $d = O(1)$, we have $\log b_{\text{blk}} = O(\log T)$, giving total time $O(T \log T \cdot \lambda^c) = O(T \cdot \text{poly}(\log T))$.

We acknowledge this represents a known trade-off: the space efficiency comes at the cost of polylogarithmic factors in the running time. $\square$

# 6 Security Preservation

A critical aspect of our construction is that it achieves its space efficiency without compromising security. We prove that our sublinear-space prover inherits the completeness, soundness, and zero-knowledge properties of the underlying cryptographic primitives using formal game-based security proofs.

## 6.1 Completeness

**Theorem 7 (Completeness Preservation).** For any valid statement-witness pair $(x, w) \in \mathbb{R}$, the prover in Algorithm 3 produces a proof $\pi$ that is accepted by the verifier with probability 1.

*Proof.* Completeness follows from the correctness of our construction at each step.

1. The block-respecting transformation (Lemma 2) correctly simulates the original computation.

2. The Tree Evaluation Equivalence (Theorem 4) proves that evaluating the computation tree produces a commitment to a valid trace polynomial $f_{\tau}(X)$ and correctly computed auxiliary data for consistency checks.

3. The Cook-Mertz algorithm correctly computes the value of the root of the tree.

4. The final proof $\pi$ is therefore generated from a valid commitment and auxiliary data.

Since the verifier receives a proof derived from a valid trace, and the underlying ZKP system is complete, the verifier will accept. $\square$
## 6.2 Soundness

We first formally define the soundness security game.

**Definition 13 (Soundness Game).** The soundness game $Game_A^{Sound}(1^\lambda, C)$ proceeds as follows:

1. The challenger generates public parameters $pp \leftarrow Setup(1^\lambda, T)$

2. The adversary $A(pp)$ outputs a statement $x$ and proof $\pi$

3. $A$ wins if $Verify(pp, x, \pi) = 1$ and $x \notin L(R)$

**Theorem 8 (Soundness Preservation).** If the underlying polynomial commitment scheme is computationally binding, then our proof system is computationally sound. Specifically, for any PPT adversary $A$ that wins $Game_A^{Sound}$ with probability $\varepsilon$, there exists a PPT algorithm $B$ that breaks the binding property of the PCS with probability $\varepsilon' \ge \varepsilon/\text{poly}(T)$.

*Proof.* We prove this by constructing a reduction algorithm $B$ that uses a soundness adversary $A$ to break the binding property of the PCS.

**Algorithm 4 Reduction Algorithm $B$ for Soundness**

**Require:** PCS public parameters $pp_{\text{pcs}}$

**Ensure:** Binding violation ($\text{com}, z, y, \pi, y', \pi'$) with $y \neq y'$

1. Generate complete proof system parameters $pp$ using $pp_{\text{pcs}}$

2. Run adversary $A(pp)$ to obtain $(x, \pi)$ where $x \notin L(R)$ but $\pi$ verifies

3. Parse $\pi$ to extract the root commitment $\text{com}_{\text{final}}$ and auxiliary data $\text{aux}_{\text{final}}$

4. **Identify Inconsistency:** Since $x$ is false but $\pi$ verifies, there must exist some computation block where the local trace polynomial contradicts the global consistency requirements

5. **Extract Violation:** Use the tree structure and auxiliary data to identify a point $z \in \mathbb{F}$ where:

* The verifier's checks imply the committed polynomial should evaluate to $y$ at $z$

* The falseness of $x$ implies the polynomial must actually evaluate to $y' \neq y$ at $z$

6. **Construct Proofs:** Using the proof $\pi$ and the structure of our commitment tree, extract opening proofs $\pi$ and $\pi'$ for both evaluations

7. **return** ($\text{com}_{\text{final}}, z, y, \pi, y', \pi'$)

**Analysis:** If $A$ succeeds in generating an accepting proof for a false statement with probability $\varepsilon$, then there must be an inconsistency in the committed polynomial that can be extracted as a binding violation. The number of possible points where such inconsistencies can occur is bounded by $\text{poly}(T)$ (the number of constraint evaluations), so $B$ succeeds with probability $\varepsilon' \ge \varepsilon/\text{poly}(T)$. Since $\varepsilon$ is non-negligible by assumption, $\varepsilon'$ is also non-negligible, contradicting the binding property of the PCS. $\square$

## 6.3 Zero-Knowledge

We first formally define the zero-knowledge security game.

**Definition 14 (Zero-Knowledge Game).** The zero-knowledge indistinguishability game $Game_A^{ZK}(1^\lambda, C)$ proceeds as follows:

1. The challenger generates $pp \leftarrow Setup(1^\lambda, T)$ and gives $pp$ to adversary $A$

2. $A$ outputs a statement-witness pair $(x, w)$ such that $(x, w) \in R$
3. The challenger chooses $b \leftarrow \{0,1\}$ uniformly

4. If $b = 0$: $\pi \leftarrow \text{Prover}(pp, x, w)$ (real proof)

5. If $b = 1$: $\pi \leftarrow \text{Sim}(pp, x)$ (simulated proof)

6. $\mathcal{A}$ outputs a guess $b'$

7. $\mathcal{A}$ wins if $b = b'$

**Theorem 9 (Zero-Knowledge Preservation).** If the underlying polynomial commitment scheme is computationally hiding, then our proof system is computational zero-knowledge. Specifically, for any PPT adversary $\mathcal{A}$, $|\text{Pr}[\mathcal{A} \text{ wins } \text{Game}_{\mathcal{A}}^{\text{ZK}}] - 1/2|$ is negligible.

*Proof.* We prove zero-knowledge via a hybrid argument using the sequence of games $H_0, H_1, \dots, H_B$.

**Simulator Definition:** The simulator $\text{Sim}(pp, x)$ works by executing the Cook-Mertz algorithm with modified oracles:

* $S_{\text{children}}$ and $S_{\text{leaf}}$: Behave identically to honest oracles (depend only on public data)

* $S_{\text{func}}$: Uses the PCS hiding simulator to generate fake commitments and computes consistent-looking auxiliary data by simulating the boundary values and setting the permutation accumulator to maintain apparent consistency

**Hybrid Games:** For $i = 0, 1, \dots, B$:

* $H_0$: The real prover (using Algorithm 3)

* $H_i$ ($1 \le i \le B$): Compute the first $B-i$ blocks honestly, but for blocks $B-i+1$ through $B$, use simulated versions

* $H_B$: Fully simulated proof

**Indistinguishability Proof:** For each $i$, we prove $H_i \approx_c H_{i+1}$ by reduction to PCS hiding:

**Algorithm 5 Reduction Algorithm for $H_i \approx_c H_{i+1}$**

**Require:** PCS hiding challenger, distinguisher $\mathcal{D}$ for hybrids

**Ensure:** Advantage in PCS hiding game

1. Simulate the first $B-i-1$ blocks honestly using the real witness

2. For block $B-i$:

* Compute the real trace polynomial $f_{\text{real}}(X)$ for this block

* Generate a random polynomial $f_{\text{fake}}(X)$ of the same degree

* Submit $(f_{\text{real}}, f_{\text{fake}})$ to the PCS hiding challenger

3. Receive challenge commitment $\text{com}^*$ from hiding challenger

4. Use $\text{com}^*$ to complete the proof construction and auxiliary data computation

5. Forward the completed proof to distinguisher $\mathcal{D}$

6. Output $\mathcal{D}$'s guess as the answer to the hiding challenge

If $\mathcal{D}$ can distinguish $H_i$ from $H_{i+1}$ with non-negligible advantage, then the reduction breaks PCS hiding with the same advantage.

Since the PCS is computationally hiding, we have $H_i \approx_c H_{i+1}$ for all $i$. By a hybrid argument, $H_0 \approx_c H_B$, proving that real proofs are computationally indistinguishable from simulated ones. Since the simulator $\text{Sim}$ never uses the witness $w$, the system is zero-knowledge. $\square$

<figure><img src="image_2.png" /></figure>
# 7 Performance and Implications

Our sublinear-space prover does more than resolve a theoretical question; it fundamentally alters the landscape of practical verifiable computation. In this section, we analyze its performance against existing systems and explore the new applications it enables.

## 7.1 Performance Comparison

The primary benefit of our construction is the quadratic reduction in prover space complexity. To illustrate the practical impact, we compare our “streaming” prover against a standard “linear-space” prover for a ZKP system like a STARK or Plonk, which requires the full execution trace in memory.

<table><caption>Table 1: Performance Comparison: Linear-Space vs. Sublinear-Space Prover</caption><thead><tr><td>Metric</td><td>Standard Linear-Space Prover</td><td>Our Sublinear-Space Prover</td></tr></thead><tbody><tr><td>Prover Space</td><td>Θ(T)</td><td>O(√T log T)</td></tr><tr><td>Prover Time</td><td>O(T log T) (STARKs) or O(T log<sup>2</sup> T) (some SNARKs)</td><td>O(T · poly(log T))</td></tr><tr><td>Proof Size</td><td>O(poly(λ, log T))</td><td>O(poly(λ, log T)) (Identical)</td></tr><tr><td>Verifier Time</td><td>O(poly(λ, log T))</td><td>O(poly(λ, log T)) (Identical)</td></tr><tr><td>Setup Model</td><td>System-dependent (e.g., CRS, SRS)</td><td>System-dependent (Identical)</td></tr></tbody></table>

Our construction dramatically improves the prover’s memory footprint while introducing only a modest, polylogarithmic overhead in time. Crucially, the proof itself and the verifier’s work remain unchanged, ensuring that our prover can be a drop-in replacement in any existing ZKP ecosystem without affecting end-users or protocol security parameters.

## 7.2 Concrete Impact on System Requirements

To contextualize the magnitude of the space improvement, consider two representative computation sizes. We assume each step in the trace requires 32 bytes of memory. For concrete illustration, we use $log_2$ and note that with our security parameter assumption $λ = Θ(\log T)$, the bound $O(\sqrt{T \log T})$ incorporates both computational and security considerations.

**Scenario 1: A moderately large computation ($T = 2^{24} \approx 16.7$ million steps)**

* **Linear-space prover:** Requires memory proportional to $16.7 \times 10^6 \times 32$ bytes $\approx 537$ MB. This is challenging for a typical smartphone.

* **Our streaming prover:** Requires memory proportional to $\sqrt{2^{24} \log_2(2^{24})} = \sqrt{2^{24} \times 24} \approx 2^{12} \times \sqrt{24} \approx 4096 \times 4.9 \approx 20,000$ elements. At 32 bytes/element, this is $\approx 0.64$ MB. This is trivial for any modern device.

**Scenario 2: A very large computation ($T = 2^{30} \approx 1$ billion steps)**

* **Linear-space prover:** Requires memory proportional to $10^9 \times 32$ bytes $\approx 34.4$ GB. This is feasible only on high-end server hardware.

* **Our streaming prover:** Requires memory proportional to $\sqrt{2^{30} \log_2(2^{30})} = \sqrt{2^{30} \times 30} \approx 2^{15} \times \sqrt{30} \approx 32768 \times 5.5 \approx 180,000$ elements. At 32 bytes/element, this is $\approx 5.7$ MB. This is easily manageable on a standard laptop.

These examples illustrate that our work makes verifiable computation accessible in scenarios where it was previously infeasible, moving from a specialized, server-bound task to one that can be performed on everyday devices.
## 7.3 Enabling New Deployment Scenarios

The removal of the linear-space barrier opens up several new frontiers for ZKP applications:

* **On-Device Proving:** Mobile phones, IoT devices, and embedded systems can now generate proofs for complex computations, enabling applications like privacy-preserving health monitoring, on-device machine learning inference verification, and secure authentication without powerful backend servers.

* **Democratizing Trust:** By lowering the hardware barrier to entry, our work allows a wider range of participants to generate proofs in decentralized networks (e.g., as provers in a ZK-Rollup), enhancing network security and decentralization.

* **Verifying Extremely Large Computations:** Scientific simulations, large-scale data processing pipelines, and complex financial models can now be made verifiable, as the memory requirements no longer scale linearly with the computation's runtime.

## 7.4 Limitations and Future Work

Our work marks a significant advance, but also illuminates several exciting avenues for future research.

* **Removing the Logarithmic Factor:** Our space bound is $O(\sqrt{T \log T})$. Recent work in computational complexity theory suggests that if **Tree Evaluation** could be solved more efficiently, a plain $O(\sqrt{T})$ space bound for simulation might be possible. Investigating whether this improvement can be achieved and transferred to our cryptographic setting is a compelling open problem.

* **Time Complexity Optimization:** While the polylogarithmic time overhead is acceptable in many memory-bound scenarios, reducing the prover's runtime further would be highly valuable. Reducing the poly(log T) factor in the prover's runtime may be possible by designing custom Tree Evaluation algorithms tailored to the algebraic structure of ZKP functions, potentially avoiding the need for generic low-degree extensions that currently contribute to the time overhead.

* **Post-Quantum Instantiations:** Our framework relies on an additively homomorphic PCS, which is most efficiently realized with pairing-based or discrete-log-based cryptography. The current construction is therefore *not post-quantum secure*, as it depends on the hardness of the discrete logarithm problem or related assumptions that are vulnerable to quantum attacks. A promising direction is to explore PCS based on the hardness of lattice problems that support some form of functional or aggregatable properties. However, a more direct approach would be to redesign the recursive composition step to work with hash-based commitments (such as those used in FRI-based systems) by including Merkle proofs in the auxiliary data channel. This modification would increase the bit-length $b_{val}$ of node values in the computation tree, as each auxiliary data structure would need to carry cryptographic proofs of inclusion. Since the Cook-Mertz algorithm's space complexity depends on $b_{val}$, this change could affect the final space complexity bound, representing a non-trivial trade-off between post-quantum security and space efficiency that requires careful analysis.

* **Beyond Proof Generation:** The principle of decomposing a cryptographic task into a space-efficient tree evaluation may apply to other primitives beyond ZKPs, such as verifiable delay functions (VDFs) or other forms of interactive proofs.
# 8 Conclusion

We have presented the first zero-knowledge proof system with sublinear space complexity for the prover, breaking a long-standing and fundamental barrier in verifiable computation. Our core technical contribution is the Tree Evaluation Equivalence (Theorem 4), which establishes a mathematical equivalence between cryptographic proof generation and the Tree Evaluation problem. By combining the structural decomposition of Williams with an additively homomorphic PCS, we express the ZKP commitment generation as a recursive function $F_v$ over a tree, which is then evaluated in low space using the Cook-Mertz algorithm. This approach enables us to leverage recent algorithmic advances in computational complexity to achieve a quadratic improvement in prover memory from $\Theta(T)$ to $O(\sqrt{T} \log T)$.

The key algorithmic innovation is our commitment tree function $F_v$ (Algorithm 2), which recursively composes cryptographic commitments while maintaining consistency through auxiliary data channels. This construction replaces the monolithic trace materialization of traditional provers with a space-efficient recursive evaluation that never stores the complete execution trace.

Our construction preserves the security properties, proof size, and verification cost of existing linear-space systems, allowing it to serve as a direct, space-efficient replacement in a wide variety of applications. Beyond the immediate practical impact, our work establishes the Principle of Algorithmic Transference: advances in space-efficient algorithms for abstract computational models can be systematically lifted to create space-efficient cryptographic protocols for those same models. This principle suggests a deep and actionable connection between the efficiency of abstract algorithms and the practicality of concrete cryptographic protocols.

The ability to generate proofs in sublinear space makes verifiable computation practical on resource-constrained devices and for computations of a scale previously thought infeasible. As our digital world increasingly demands strong guarantees of privacy and integrity, our work provides a critical tool for making these guarantees accessible, affordable, and ubiquitous. This research not only solves a pressing problem in applied cryptography but also builds a lasting bridge to computational complexity theory, opening a rich new landscape where breakthroughs in algorithm design can directly fuel advances in cryptographic protocol efficiency and practical deployment.
References

[1] Groth, J. (2016). On the Size of Pairing-Based Non-interactive Arguments. *Advances in Cryptology – EUROCRYPT 2016*, 305-326.

[2] Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, Transparent, and Post-Quantum Secure Computational Integrity. *IACR Cryptology ePrint Archive*, 2018/046.

[3] Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., & Maxwell, G. (2018). Bullet-proofs: Short Proofs for Confidential Transactions and More. *Proceedings of the 2018 IEEE Symposium on Security and Privacy*, 315-334.

[4] Cook, S. A., & Mertz, R. (2024). Space-Efficient Tree Evaluation Algorithms. *Journal of the ACM*, 71(3), 1-28.

[5] Williams, R. (2025). Structural Decomposition of Turing Machine Computations via Computation Graphs. *Proceedings of the 57th Annual ACM Symposium on Theory of Computing*, 145-158.

[6] Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-Size Commitments to Polynomials and Their Applications. *Advances in Cryptology – ASIACRYPT 2010*, 177-194.

[7] Hopcroft, J., Paul, W., & Valiant, L. (1975). On Time Versus Space and Related Problems. *Proceedings of the 16th Annual Symposium on Foundations of Computer Science*, 57-64.