Follow us for behind
the scenes content!

Sumcheck 201

Published on: 
Feb 2, 2024

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.



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.


Written by

Table of Contents

Want to discuss further?

Ingonyama is commited to developing hardware for a private future using Zero Knowledge Proofs.

Get in touch
Get our RSS feed