Sublinear-Space ZKP System in Rust: Streaming Prover with O(√T) Memory via KZG Commitments
By
logannyeMD
Crackling crust, pillowy middle. The kind of bagel that earns a second cup of coffee.
Summary
A reference implementation of a sublinear-space zero-knowledge proof (ZKP) prover/verifier system in Rust, based on a whitepaper. The streaming prover uses only O(√T) memory over a trace of length T, producing KZG commitments (BN254) for wires, permutation accumulator Z, and quotient Q. It employs aggregate-only Fiat–Shamir, blocked IFFT, and never materializes whole polynomials, solving the traditional O(T) memory bottleneck in zk proving pipelines. Includes CLI tools and tests.
Key quotes
· 3 pulledIt 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.
Traditional zk proving pipelines routinely buffer whole polynomials, forcing O(T) memory and large intermediate states.
You might also wanna read
How Shamir's Secret Sharing Algorithm Enables Threshold Cryptography
This article explains Adi Shamir's Secret Sharing algorithm, a cryptographic method published in 1979 that splits a secret into multiple pie
ente.com·6d ago
Apple publishes corecrypto with formal verification proofs for quantum-secure ML-KEM and ML-DSA algorithms
Apple has published the corecrypto library containing quantum-secure ML-KEM and ML-DSA algorithms, along with formal verification proofs tha
security.apple.com·9d ago
Understanding Beaver Triples: A Primer on Secure Multiparty Computation
The article introduces the concept of Beaver Triples in the context of secure multiparty computation (MPC). It uses an analogy about a frien
stoffelmpc.com·22d ago
Testing Quantum Computing Claims: Replacing IBM QPU with /dev/urandom in ECDLP Attack
This article tests a quantum computing claim from the Q-Day Prize submission by replacing the IBM Quantum Processing Unit (QPU) with /dev/ur
github.com·1mo ago
OpenSSL 4.0.0 Released with Significant New Features and Compatibility Changes
OpenSSL 4.0.0 is a major feature release that introduces significant new functionality along with potentially incompatible changes. Key upda
github.com·1mo ago
Threshold Signatures: Distributing Cryptographic Risk to Eliminate Single Points of Failure
The article discusses the security risks of single private keys as points of failure in cryptographic systems and introduces threshold signa
eric.mann.blog·2mo ago