Folding Schemes:

From simple to complex and back again

The year I first read about Halo was 2020. The ZCash team had generated a lot of buzz for developing a breakthrough in cryptography. Most of the chatter in media and marketing presented it as a step towards removing ZCash’s trusted setup; an often eyebrow-raising aspect of its trust-assumptions.

As a privacy coin enthusiast but not (yet) a cryptographic engineer, I attempted to read the paper to figure out what it was about, armed with the “ELI5” explanation of zkSNARKs. No surprise, it was quite difficult to read without much background knowledge in cryptography.

Nevertheless, the main idea came across: this breakthrough was not just about eliminating trusted setups, it was about an optimization to something called recursive proofs: a powerful primitive that unlocks major scaling breakthroughs for ZK.

Over the next few years I fell deeper into the rabbit hole, learning ZK from industry colleagues as I matured as a blockchain engineer.

Come 2023, everyone returned from Zuzalu raving about something called folding schemes, which I came to understand after a series of conference talks and conversations with experienced pros. Like Halo, it’s a powerful optimization to recursive proof composition, and quite simple to understand. No wonder why so many practicioners were captivated by it; “simple but powerful” has a draw.

Many of the talks and lectures on folding schemes referenced Halo, describing it as an essential stepping stone in the lineage. So I attempted to revisit the Halo paper after learning about folding schemes, hoping to understand the connection.

Still, I struggled to make sense of the math or see the connection between the two concepts, aside from the superficial similarity. Why was everyone calling Halo a predecessor to folding?

What I learned is that it’s a classic example of simplicity and beauty arising from iteration in engineering, and a great story of how a powerful piece of technology evolved over time.

On Cultivating Mathematical Creativity

I was reminded about the tendency for for math and science teachers to reference the names of historical figures. Gauss, Lagrange, L’Hopital, and Leibniz come to mind. As a bored student sitting in the classroom, I didn’t understand the purpose of my teachers’ constant name-dropping, but now as an aspiring cryptographic engineer, it clicks. Learning math and science topics implies learning the history of the idea, and how it develops over time. This is why cryptography papers are dotted with references to older papers.

We’re focusing on the ancestry and offspring of Halo. One can follow a chain of citations going back at least as far as the 1990s, or 1980s. I wondered if I needed to go back to Alan Turing, or perhaps to the ancient Greeks be satisfied. I concluded no- you don’t need to go back to the Ancient Greeks, but it helps to go back far enough to something simple enough that you could have maybe invented yourself.

This turned out to be 2016, so I revisited the summer of Pokemon Go, Lil Yachty, and Kanye West’s Life of Pablo era. The authors of Bootle16 (see my last blog post) do a fantastic job not only explaining their innovation, but the thought process behind their discoveries!

The lineage developed like this:

Bootle16 (2016):

1. Researchers were interested in efficient ZKPs with ordinary elliptic curves (no fancy-shmancy pairings)
2. They intuited that ZKP constructions usually follow from polynomial commitment schemes, so they started by building efficient PCS using ordinary elliptic curves.
3. They design an IOP for arithmetic circuits using their newly-developed PCS
4. They observed that the IOP involves proving a claim with a specific “inner product” structure, reminiscent of a scheme from an older cryptography paper about verifiable shuffles.
5. They basically scrapped their lovely PCS, realizing the inner product argument inspired by the verifiable shuffle paper better suits the use-case.

Bulletproofs (2017):

1. Now that ZKP research motivates a renewed interest in inner product arguments, researchers revisited the construction and came up with straightforward optimizations.
2. Among the optimizations were batch verification, and aggregation for statements of a certain form.

Halo (2019):

1. Researchers attempted to construct recursive ZK proofs using techniques inspired from bulletproofs
2. Realized several optimizations are applicable
3. Realized that linear verifier work from the recursion circuit can be deferred to the verifier and batched, preventing deferred verifications from piling up.
4. Amazingly, this efficient recursive proof construction happens to not require a trusted setup

BCMS20 (2020):

1. A follow-up paper to Halo focuses on formalizing the construction, and reframing it from a recursive proof composition technique, into an “accumulation” technique.
2. While it appears to be superficial semantic framing, it leads to new insights that inspire the next breakthrough

Split-Accumulation (2020):

1. Finally, we arrive at the original description of what is often known as folding schemes.

Future Works (Nova, etc):

• After Split-Accumulation, many folding-related papers came out, see awesome-folding.

Conclusion

I’ve been re-writing this post for four months and my blog needed content. I drafted more-technical posts on how to construct a PCS from pedersen commitments, how to re-invent the IOP from first principles, and how to notice the same observations that the researchers noticed. However, I was not satisfied with any of the technical writing and this blog was taking too long, hope you enjoyed!