Chapter 1: Algorithms for Sumcheck Parallelization
Abstract: In this chapter, we explore sum-check protocols from the point of view of parallelizable computation in devices such as GPUs. We explore algorithmic modifications to the sum-check protocol, for products of Multi-Linear Extensions (MLE) to improve parallel compute and address memory bottlenecks.
Paper: https://github.com/ingonyama-zk/papers/blob/main/sumcheck_201_chapter_1.pdf
Code: https://github.com/ingonyama-zk/super-sumcheck
Super-sumcheck is aimed at exploring algorithmic improvements to the sumcheck prover to run it in a fully parallelizable 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
Highlights: 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.
![](https://cdn.prod.website-files.com/63970f25aa7b42e284492d52/65bf7059148e4c2b54a3f50e_1*2QMnjUUoZqgNXPZrPdQ-Ug.png)