GitHub - logannye/space-efficient-zero-knowledge-proofs: Sublinear-space ZKP system in Rust: a streaming prover that uses only O(√T) memory to commit wires/Z/Q via KZG (BN254) with blocked IFFT and aggregate-only Fiat–Shamir. Supports eval/coeff bases, deterministic dev SRS, and pairing checks. Includes CLI prover/verifier and tests.

6 min read Original article ↗

Legacy research repo. This repository is the earlier KZG/BN254 research prototype and paper companion for "Zero-knowledge Proofs in Sublinear Space" (https://arxiv.org/abs/2509.05326). The current TinyZKP product lives in logannye/hc-stark and powers tinyzkp.com: transparent STARK state-transition receipts, no trusted setup for the hosted receipt path, SDKs, MCP, billing, and browser verification.

This repo is still useful for understanding the original space-efficiency thesis, the aggregate-only Fiat-Shamir schedule, and the KZG/BN254 exploration. It should not be treated as the hosted TinyZKP engine or as the current production trust model. See tinyzkp.com/research for the public reconciliation story.

Why this matters

Traditional zk proving pipelines routinely buffer whole polynomials, forcing O(T) memory and large intermediate states. This repository explores a practical alternative:

  • Space-efficiency thesis: restructure proving around blocked transforms, streaming accumulators, and aggregate-only Fiat-Shamir.
  • KZG research path: standard KZG commitments/openings (pairing-checked) over BN254.
  • Deterministic dev SRS: easy to run locally; a real deployment of this KZG path requires trusted SRS files.
  • Historical signal: this repo shows the earlier research direction that led to TinyZKP's current STARK product, but it is not the product repo.

Implementation status matters: parts of the code implement streaming/blocking interfaces, but the current scheduler still uses full-vector/global-IFFT paths for some opening work. Treat the repo as a research prototype and paper companion, not as a production memory-bound claim.

Features at a glance

  • PCS: KZG over BN254 with a linear interface and a streaming Aggregator.
  • Two commitment bases: commit from evaluation (domain-aligned) or coefficient slices.
  • Openings: real KZG openings for wires/Z/Q, with consistent witness construction.
  • Domain & transforms: radix-2 blocked IFFT/NTT, barycentric eval for streaming points.
  • AIR & residuals: small fixed-column AIR and permutation-coupled residual stream.
  • Scheduler: five-phase A-to-E pipeline, aggregate-only Fiat-Shamir, strictly increasing time order.
  • CLI tools: prover and verifier plus an end-to-end script.
  • Space profile target: peak memory is intended to track O(b_blk) with b_blk near sqrt(T), but current opening code still contains full-vector paths. See "Implementation status" below.

How it works (one-screen version)

  1. Phase A: (Optional) commit selectors/fixed columns.
  2. Phase B: Wires - stream a register's evaluations block-by-block, run blocked IFFT work, and feed coefficient tiles into the PCS aggregator.
  3. Phase C: Permutation accumulator Z - stream locals, update Z, and emit the Z column in time order.
  4. Phase D: Quotient Q - stream residual R(omega^i) and convert toward Q coefficients using Z_H(X)=X^N-c.
  5. Phase E: Openings - produce KZG openings for wires, Z, and Q 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 a non-dev KZG deployment, provide trusted SRS files.

Implementation status

The intended architecture is sublinear-space, but the current code is not a complete production realization of that memory profile. In particular, src/scheduler.rs still materializes full vectors and uses full IFFT paths for some wire, Z, and Q openings. That is acceptable for a research prototype, but it is the reason TinyZKP's live product is not based on this repository.

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
bash 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 <T>: total rows in the trace (domain size rounds up to power of two).
  • --b-blk <B>: block size; the research target is near sqrt(T) working blocks, but this prototype still has full-vector opening paths.
  • --k <K>: number of registers (columns) in the AIR.
  • --basis <eval|coeff>: commitment basis for wires (Q is always coeff).
  • --selectors <FILE>: optional selectors/fixed columns CSV (rows × S).
  • --omega <u64>: override ω (power-of-two order must hold).
  • --coset <u64>: reserved; current domain uses subgroup (Z_H(X)=X^N−1).

Repository layout

  • src/pcs.rs — KZG PCS (BN254), streaming Aggregator, real openings, pairings.
  • src/domain.rs — domain H, barycentric weights, blocked NTT/IFFT.
  • src/air.rs — tiny fixed-column AIR + residual stream + permutation coupling.
  • src/perm_lookup.rs — permutation accumulator Z (lookups optional).
  • src/quotient.rs — streaming quotient builder (R→Q tilewise).
  • src/scheduler.rs — 5-phase orchestrator (aggregate-only FS schedule; current opening implementation still materializes full vectors in places).
  • src/opening.rs — streaming polynomial evaluation helpers (eval/coeff mode).
  • src/transcript.rs — domain-separated FS transcript (BLAKE3→field).
  • src/stream.rs — block partitioning + restreaming interfaces.
  • bin/prover.rs, bin/verifier.rs — 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). If you need a production memory-bound prover, audit the remaining full-vector paths first.
  • Keep your permutation/lookup logic time-ordered; the accumulator state must evolve monotonically in t.
  • When committing from evaluations, ensure your blocks align to the domain and use the provided blocked IFFT 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 tamper test flips one byte in proof.bin; 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.
  • This repo has no hosted service, billing system, MCP server, browser verifier, or production operations stack. Those live in hc-stark.

TinyZKP product path

If you want the current TinyZKP product, use:

The production product is a transparent STARK state-transition receipt service. The default hosted receipt is not this KZG/BN254 prototype and does not require a trusted setup ceremony.

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. It is best read as the KZG/BN254 research ancestor of TinyZKP's current STARK product, not as the hosted production implementation.