Quadratic memory reductions for Zero-knowledge Proofs

SSZKP — Sublinear-Space Zero-Knowledge Proofs (Rust, KZG/BN254) A reference implementation of the sublinear-space ZKP prover/Verifier described in our whitepaper: "Zero-knowledge Proofs in Sublinear Space" (https://arxiv.org/abs/2509.05326). It realizes a streaming prover that uses only O(√T) memory over a trace of length T, while producing standard KZG commitments (BN254) for wires, the permutation accumulator Z , and the quotient Q . The design keeps aggregate-only Fiat–Shamir and never materializes whole polynomials. Why this matters Traditional zk proving pipelines routinely buffer whole polynomials, forcing O(T) memory and large intermediate states. This repository demonstrates a practical alternative: Sublinear space: the active working set stays O(√T) using blocked IFFTs and streaming accumulators. the active working set stays using blocked IFFTs and streaming accumulators. Production-style commitments: standard KZG commitments/openings (pairing-checked) over BN254 . standard commitments/openings (pairing-checked) over . No full-poly buffers: wires, Z , and Q are built and opened without holding entire vectors. wires, , and are built and opened holding entire vectors. Deterministic dev SRS: easy to run locally; switch to trusted SRS files for production. If you’re building scalable zk systems, this repo shows how to restructure your pipeline around streaming and aggregate-only FS without giving up familiar cryptographic backends. Features at a glance PCS: KZG over BN254 with a linear interface and a streaming Aggregator . KZG over BN254 with a interface and a streaming . Two commitment bases: commit from evaluation (domain-aligned) or coefficient slices. commit from (domain-aligned) or slices. Openings: real KZG openings for wires/ Z / Q , with consistent witness construction. real KZG openings for wires/ / , with consistent witness construction. Domain & transforms: radix-2 blocked IFFT/NTT, barycentric eval for streaming points. radix-2 blocked IFFT/NTT, eval for streaming points. AIR & residuals: small fixed-column AIR and permutation-coupled residual stream. small fixed-column AIR and permutation-coupled residual stream. Scheduler: five-phase A→E pipeline, aggregate-only Fiat–Shamir, strictly increasing time order. five-phase A→E pipeline, aggregate-only Fiat–Shamir, strictly increasing time order. CLI tools: prover and verifier plus an end-to-end script. and plus an end-to-end script. Space profile: peak memory ≈ O(b_blk) with b_blk ≈ √T . How it works (one-screen version) Phase A: (Optional) commit selectors/fixed columns. Phase B: Wires — stream a register’s evaluations block-by-block → blocked IFFT → feed coeff tiles (low→high) into PCS Aggregator. Phase C: Permutation accumulator Z — stream locals, update Z on the fly and emit the Z column in time order, then commit via the same blocked IFFT path. Phase D: Quotient Q — stream residual R(ω^i) and convert to Q coefficients online using Z_H(X)=X^N−c (no full-poly buffers). Phase E: Openings — produce real KZG openings for wires, Z , and Q (witness W = (f−f(ζ))/(X−ζ) ) and verify via pairings. All Fiat–Shamir challenges are replayed by the verifier; pairing checks are always enforced. In dev builds, SRS is deterministic; in production, provide trusted SRS files. Quick start Prerequisites Rust (stable toolchain) No external SRS required for dev runs (deterministic in-crate SRS) Build & test (dev SRS) # Clone, then: cargo build --quiet --bins --features dev-srs # End-to-end script runs three scenarios + a tamper test scripts/test_sszkp.sh Expected output (abridged): ✔ build succeeded ✔ verification OK for eval-basis wires, b_blk=128, rows=1024 ✔ tampered proof correctly rejected ✔ verification OK for coeff-basis wires, b_blk=64, rows=1536 ✔ verification OK for eval-basis wires, b_blk=256, rows=2048 ==> All tests passed 🎉 Run the prover manually cargo run --features dev-srs --bin prover -- \ --rows 1024 --b-blk 128 --k 3 --basis eval # writes proof.bin Run the verifier manually cargo run --features dev-srs --bin verifier -- --rows 1024 --basis eval # reads proof.bin and verifies Production SRS (trusted, non-dev) In non-dev builds you must provide both G1 and G2 SRS files. Prover: cargo run --bin prover -- \ --rows 1024 --b-blk 128 --k 3 --basis eval \ --srs-g1 srs_g1.bin --srs-g2 srs_g2.bin Verifier: cargo run --bin verifier -- --rows 1024 --basis eval \ --srs-g1 srs_g1.bin --srs-g2 srs_g2.bin Format: the SRS files are Arkworks-serialized vectors of affine powers. G1: [τ^0]G1 … [τ^d]G1 (we use the degree bound you load). G2: a vector containing at least [τ]G2 (we read element 1 or 0). Configuration knobs --rows : total rows in the trace (domain size rounds up to power of two). : total rows in the trace (domain size rounds up to power of two). --b-blk : block size; pick ≈ √T to achieve the sublinear memory bound. : block size; pick to achieve the sublinear memory bound. --k : number of registers (columns) in the AIR. : number of registers (columns) in the AIR. --basis : commitment basis for wires (Q is always coeff ). : commitment basis for (Q is always ). --selectors : optional selectors/fixed columns CSV (rows × S). : optional selectors/fixed columns CSV (rows × S). --omega : override ω (power-of-two order must hold). : override ω (power-of-two order must hold). --coset : reserved; current domain uses subgroup ( Z_H(X)=X^N−1 ). Repository layout src/pcs.rs — KZG PCS (BN254), streaming Aggregator , real openings, pairings. — KZG PCS (BN254), streaming , real openings, pairings. src/domain.rs — domain H , barycentric weights, blocked NTT/IFFT. — domain , barycentric weights, blocked NTT/IFFT. src/air.rs — tiny fixed-column AIR + residual stream + permutation coupling. — tiny fixed-column AIR + residual stream + permutation coupling. src/perm_lookup.rs — permutation accumulator Z (lookups optional). — permutation accumulator (lookups optional). src/quotient.rs — streaming quotient builder ( R→Q tilewise). — streaming quotient builder ( tilewise). src/scheduler.rs — 5-phase orchestrator (aggregate-only FS, O(√T) space). — 5-phase orchestrator (aggregate-only FS, O(√T) space). src/opening.rs — streaming polynomial evaluation helpers (eval/coeff mode). — streaming polynomial evaluation helpers (eval/coeff mode). src/transcript.rs — domain-separated FS transcript (BLAKE3→field). — domain-separated FS transcript (BLAKE3→field). src/stream.rs — block partitioning + restreaming interfaces. — block partitioning + restreaming interfaces. bin/prover.rs , bin/verifier.rs — CLIs. , — CLIs. scripts/test_sszkp.sh — end-to-end tests + tamper test. Using this in your own pipeline Treat the Restreamer trait as the integration seam: implement it to feed rows from your own storage (disk, network, GPU), all while keeping O(b_blk) memory. trait as the integration seam: implement it to feed rows from your own storage (disk, network, GPU), all while keeping memory. Keep your permutation/lookup logic time-ordered; the accumulator state must evolve monotonically in t . logic time-ordered; the accumulator state must evolve monotonically in . When committing from evaluations , ensure your blocks align to the domain and use the provided blocked IFFT helpers to produce coeff tiles. , ensure your blocks align to the domain and use the provided helpers to produce coeff tiles. For openings, prefer the coeff-stream path; the code adapts eval-streams internally when needed. Correctness & security notes Pairing checks are always enforced; the verifier replays the FS transcript and checks KZG equalities for wires, Z , and Q . the FS transcript and checks KZG equalities for wires, , and . The tamper test flips one byte in proof.bin —verification must fail. flips one byte in —verification must fail. Dev SRS exists only for convenience; do not use dev mode in production. Algebraic identity at ζ (gate + perm coupling + boundary = Z_H(ζ)·Q(ζ) ) is implemented; by default, selectors are optional and gates are minimal. Limitations & roadmap AIR is a compact demo; plug in your real selector/table wiring as needed. Lookup accumulator is feature-gated and intentionally minimal (demo path). Only BN254/KZG is shipped; adding Pallas/BLS12-381 is straightforward in this architecture. Getting help File issues for bugs or suggestions. PRs welcome—especially alternative domains, SRS loaders, or integration examples. Acknowledgments This codebase follows the aggregate-only Fiat–Shamir and streaming discipline described in the whitepaper and demonstrates that production-style commitments and sublinear space can coexist in a practical Rust implementation.