Super-sumcheck is aimed at exploring algorithmic improvements to the sumcheck prover to run it in a fully parallelisable and memory-efficient manner. We implement two algorithms for running sumcheck prover for arbitrary statements in MLE polynomials (read the full description here):
- Algorithm 1: Collapsing arrays
- Algorithm 2: Precomputations
super-sumcheck enables running sumcheck prover for any "gate" equation in MLE polynomials and hence provides a proof-system and arithmetisation agnostic sumcheck prover backend. The two algorithms fall in different ends of the performance spectrum, algorithm 1 is less-memory intensive but consumes more computation cycles, algorithm 2 is memory intensive but allows offloading lot of work to pre-computation.
This is being actively developed and is not yet ready for production. We intend to follow the following roadmap to take this project ahead:
- Reference implementation of the sumcheck prover with:
- Algorithm 1: Collapsing arrays
- Algorithm 2: Precomputations
- Use merlin library for computing challenges as per the Fiat-Shamir heuristic
- Multi-threading in both algorithms
- Benchmark the two algorithms and analyse space-time trade-offs in them
- Benchmark this implementation against other sumcheck implementations
- Implement a commitment scheme for MLE polynomials for final verifier evaluation check
WIP