Thread by @Tim_Roughgarden

A true gift from Justin Thaler (prof at Georgetown), making it 100x easier for all of us to understand what SNARKs are, the Pareto frontier of known constructions, and the labyrinthine considerations that govern the key bottleneck (proof generation time): a16zcrypto.com/measuring-snar…

Some background and additional context about how SNARKs fit into the current vision for web3 infrastructure 👇

One approach to increasing the throughput of an L1 blockchain like Ethereum is to offload computation to an L2 (perhaps another network, or even a centralized server), with the L2 periodically notifying the L1 about the transactions it has executed and the consequent L2 state.

How can the L1 know that the L2 is not fabricating the alleged new state (e.g., transferring everyone's assets into the account of the L2 operator)?

The vision behind validity rollups (often misleadingly called zk rollups, despite the lack of zero knowledge) is for the L2 to post to L1, alongside a description of the transactions executed by the L2 and the new L2 state, a proof that that state was correctly computed.

The L1 can't simply take the proof on faith, so it needs to verify its correctness. But wait, how can it do that without re-executing all the L2 transactions itself? (This would defeat the purpose of the L2, which is to take some of the load off of the L1.)

Here's the magic: for any computation you might do, it's possible to "show your work" (i.e., generate a proof) in such a way that the proof can be verified (in our case, by the L1) in much less time than it took to do the original computation (done in our case by the L2).

The fact that you can compress arbitrary computations in this way is shocking, IMO. (It's related to one of the deepest results in theoretical computer science, the PCP Theorem. Yet another example of how fundamental theoretical work can shape technology several decades later.)

(The "S" in SNARK stands for "succinct," and refers to this magical "computational compression" property.)

We've known since the 1990s that SNARKs are possible in principle. For the last 5+ years many researchers having been working hard to make them more and more practical.

These days, the most common bottleneck is the amount of computation needed to generate a SNARK proof. (Remember SNARKs are promised to be easy to *verify*, not necessarily easy to generate.)

There are lots of approaches to reducing prover time, including hardware acceleration, recursion, specialized assembly languages, better constructions, handcrafted optimizations, etc. See Justin's article for the full story.

Excited to watch how all the SNARK-related storylines are going to play out--the suspense is killing me!