17 Sumcheck

🎯 Goals

• Understand the Sumcheck protocol and underlying ideas
• Understand applications
• Relation to Bulletproofs

📚 Material

• Five minute intuition (David Wong)
• Justin Thaler ZK MOOC lecture (Slides)
• Justin Thaler Whiteboard session
• Jonathan Bootle lecture (with lots of embedding into literature)
• Paper: Sumcheck Arguments and their Applications
  • Appendix A: relation to Bulletproofs(‘s predecessor)
• Thaler lecture notes Chapters 3 & 4.
• Chiesa Lecture with proofs
• GKR overview talk

Advanced:

• Sublinear sumchecking paper
• HyperNova
• A Note on the GKR Protocol
• A Time-Space Tradeoff for the Sumcheck Prover
• Blendy (talk, slides)
• The Sum-Check Protocol over Fields of Small Characteristic

📝 Notes

June 19

• Intro session: watching one of the intro talks on the topic together
  • https://youtu.be/4018OYyoAf8 from 45:00

June 26

• Continue https://youtu.be/4018OYyoAf8?t=4402 (starting with linked timestamp)

July 3

• Finish https://youtu.be/4018OYyoAf8?t=6425 (Circuit → IOP → Sumcheck)
• Discuss ideas
• Discuss next steps for reading group

July 10

The lecture last week left did not explain how to check (using sumchecks) that a multivariate polynomial vanishes on the boolean hypercube, i.e. $f(x_1,\dots ,x_n)=0\forall \{0,1{\}}^n$ (this statement is interesting because $f$ is set up such that this statement is equivalent to all circuit constraints being fulfilled). This session’s goal is to find out how that actually works.

Material:

• Thaler lecture notes probably around Lemma 4.7 / Remark 4.4. We should probably just look at GKR at this point.

For comedic effect, one might also ask ChatGPT about it, which has a very simple solution: To be fair, it’s quite impressive that it understood the question (“I was watching a lecture about sumchecks (as in SNARKs). The lecturer reduced circuit satisfiability to a certain polynomial vanishing on the boolean hypercube, and said that this can be checked with a sumcheck. How?”), and it supplied me with lots of explanations of how sumchecks work (which seemed decent), but it really messed up actual answer.