As we head in to ZK Hack, I’m finally getting around to releasing this note I wrote summarizing some research threads on my mind after zkSummit 10. You can catch all the talks from zk10 here. Read on for some brief thoughts on sumcheck, lookups protocols, and folding schemes.
But first — let’s take a minute to highlight the bounties we’re offering for the upcoming ZK Hack. We’re offering $10,000 of bounties:
For full details, check out our bounty description on the official page.
If you’re looking for ideas for what you might build using RISC Zero, you might check out these projects for inspiration:
Now, let’s turn our attention toward what’s hot in terms of ZK protocol design. I shared a similar update after zk9; mostly in order to help me process and organize all of the ideas brewing in my mind after a week of intellectual overstimulation. After zk10, the major repeated themes seem to be:
Let’s dig in to each of these themes a bit more.
The wise ones tell us that the best time to learn the sum check protocol was 1992. The second best time is today.
Sum check is a classic interactive protocol, and it’s appearing all over the place this year. In particular, the GKR protocol has been popping up left and right, and the sum check protocol is the core of the GKR protocol. If you’re looking for a comprehensive resource on sum check and GKR, Thaler’s manuscript offers a fantastic balance of readability and completeness. Shahar’s talk at zk10 (linked below) offers a nice introduction to GKR as well.
The main selling point for GKR is that it provides a SNARK protocol for layered circuits that doesn’t require any commitments for the intermediate layers of the circuit. For highly repetitive computations — such as accumulators for lookup arguments — avoiding the commitment costs for intermediate layers can be a huge savings. This savings is the main enabler for LASSO to be able to handle such large lookup tables.
We first heard about LogUp at zk9 , and since then, our intention has been to replace our current PLOOKUP-based lookup argment with one based on LogUp on the next version of the circuit. But now, there’s another option on the table!
Last month, Shahar Papini and Ulrich Haböck released a new paper which introduces GKR-LogUp. This approach looks very promising, and the paper is delightfully clear (as is Shahar’s talk at zk10). Massive kudos to Shahar & Ulrich for moving this idea from insight to eprint in a few short weeks. After a brief initial analysis, our plan for now is to move forward with LogUp — since lookups aren’t a huge proportion of the costs of our prover, we’re prioritizing our engineering efforts elsewhere.
Folding continues to the hottest topic in zk research. The idea of combining witnesses before proving is very attractive, and the implementations for folding-based systems are coming along. From a theoretical perspective, shortly after zk10, the ProtoStar paper introduced a different “style” of folding than the Nova/SuperNova/HyperNova/Sangria lineage, and ProtoGalaxy extends that framework to folding multiple instances.
From a practical perspective, a major challenge with folding seems to be horizontal scalability. How do we use folding in a system that spans hundreds or thousands of machines? Is there a good workaround to the problem of sending many witnesses back and forth? I referenced this challenge toward the end of my zk10 talk; I’m curious to see what the path forward here will look like. Thanks to Srinath and Ying Tong for pointing out some recent and relevant reading material discussing parallelization of folding; to clarify my understanding of the problem-space here, I’ve written a more complete note describing my impressions.
Well, I won't personally be there this time, but the team will have a strong presence and we’re excited to see what you build in Istanbul — check out our bounties. If you want to ideate about project ideas or get technical support, we're happy to connect on Discord.
And if you haven’t already heard, Bonsai is now up and running, generating massive proofs with a dynamically-sized AWS cluster. Click here to learn more and get your API key.
