Sublinear-Space Zero-Knowledge Proofs (Rust, KZG/BN254)

Legacy research repo — not the current product. This is the earlier KZG/BN254 research prototype and companion to the paper "Zero-knowledge Proofs in Sublinear Space". It is preserved for the thesis and the exploration, and is not maintained.

The current product is logannye/hc-stark — an MIT-licensed, resource-bounded proving backend for Plonky3 0.6.1. It carries the same space-efficiency thesis into a transparent STARK setting: complete larger traces under an explicit RAM ceiling using deterministic SSD scratch, while keeping the official Plonky3 proof format and an unmodified upstream verifier. Measured 5.9–6.2x lower peak resident memory than the conventional path on the reference workloads, at roughly 2.4–3.1x the CPU time.

Download: backend-v0.1.0 · Docs · Compatibility · Benchmarks

What TinyZKP no longer operates: hosted proving, hosted verification, customer accounts, usage metering, MCP commerce, SDKs, and the public beta were all retired on 2026-07-17. Ignore any older references to them.

Nothing in this repository — KZG, BN254, the trusted setup, or the streaming prover here — is part of the supported hc-stark engine or its trust model.

---

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. Neither does hc-stark — all of those were retired on 2026-07-17. hc-stark ships a local engine, verifier, and CLI only.

---

TinyZKP product path

If you want the current TinyZKP product, use:

• Website: https://tinyzkp.com
• Product repo: https://github.com/logannye/hc-stark
• Docs: https://tinyzkp.com/docs
• Research lineage page: https://tinyzkp.com/research

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.