Skip to content

In this repo we will construct a POC implementation of the MLE sumcheck end-end in a GPU

License

Notifications You must be signed in to change notification settings

ingonyama-zk/super-sumcheck

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

25 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

super-sumcheck: Parallelising Sumcheck Prover

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

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.

Roadmap

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

Example

WIP

License

About

In this repo we will construct a POC implementation of the MLE sumcheck end-end in a GPU

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages