Quadratic memory reductions for Zero-knowledge Proofs
8 hours ago
- #Rust Implementation
- #Zero-knowledge Proofs
- #Sublinear Space
- Reference implementation of a sublinear-space ZKP prover/verifier as described in the whitepaper 'Zero-knowledge Proofs in Sublinear Space'.
- Uses only O(√T) memory over a trace of length T, producing standard KZG commitments for wires, permutation accumulator Z, and quotient Q.
- Avoids buffering whole polynomials, maintaining O(√T) memory usage with blocked IFFTs and streaming accumulators.
- Supports production-style KZG commitments and openings over BN254 without full polynomial buffers.
- Features deterministic dev SRS for local runs, with the option to switch to trusted SRS files for production.
- Includes a five-phase pipeline (A→E) with aggregate-only Fiat–Shamir, strictly increasing time order.
- Provides CLI tools for prover and verifier, plus an end-to-end test script.
- Designed for easy integration with scalable zk systems, supporting streaming and aggregate-only FS without sacrificing cryptographic backends.
- Includes Rust implementation with no external SRS required for dev runs.
- Detailed instructions for cloning, building, and running tests provided.