Snarking intensity: Measuring general compute-efficiency of zkSNARKs

From time to time, I think about how efficient zkSNARKs currently are, and how efficient they need to be for practitioners to simply say "I will SNARK the entire CPU execution" (as if it's as ubiquitous as I'll just run it in SGX). Since I run this calculation in my brain from time to time, I'm curious how correct my current priors are w.r.t the state of the art. What do you think? Let me know:

SNARKing ETH mainnet

This is perhaps the most true-to-world number we can obtain since zkEVM are kinda the raison d'être for zkSNARKs in the real world these days.

From Devcon Bogota, slide from Jordi/Polygon zkEVM

The important line: a 4M gas proof takes ~9 minutes to generate.

Ethereum mainnet targets a mean gas consumption of 15 million gas per 12.5 seconds

$\to$ 1.2 million gas per second, i.e. to SNARK 1 second of ETH mainnet takes ~2 minutes of prover compute.

General compute

Now, we get much more back-of-the-envelope about the state of VMs as I understand them. For the instruction set, we'll use MIPS architecture as our base machine (for reasons that'll become clearer later). For proving, we will work with Nova as the backend, mostly because it's the easiest to cost model and reason about for me. I'd appreciate if someone can do the same math for plonky2 or STARKs and share.

zkSNARKing one instruction in Nova/SuperNova

Having written a MIPS machine in Nova, it takes roughly 100k constraints to prove one step of a MIPS VM. With Supernova, my estimate is that this becomes ~10k constraints per step of a MIPS machine. Ignoring the amortized compression time at the end, for each step, you do ~ 6 * (number of constraint) sized MSM, which takes roughly

$O(N/logN)$ time, or in practical terms:

The cost of proving 1 MIPS instruction in Nova takes ~100k constraints

$\to$ ~1e5 size MSM

$\to$ ~100 ms.

With Super Nova, proving 1 MIPS instruction takes ~10k constraints

$\to$ ~1e4 size MSM

$\to$ ~10ms.

OK! Let's circle back to Ethereum mainnet and compare these to purpose-built SNARKs:

We are told by Optimism's Cannon that for go-ethereum:

Cannon uses about 5-10M of MIPS instructions to process a transaction.

At ~80k average gas per tx, 1 second of Ethereum mainnet is about 15 transactions, or about 120 million MIPS instructions.

According to our previously noted Supernova constraints, this is ~1.2 trillion constraints

$\to$ 1.2 million seconds

$\to$ ~13 days(!).

Gameboy Color

ETH mainnet is not a machine easily contextualised in everyday use, so let's look at a Gameboy instead.^[1]

Gameboy runs at ~3MHz, so one second of compute is around 3e6 MIPS instructions. At Supernova multiplier, this is 3e10 constraints, which means SNARKing one second of Gameboy compute takes ~30k seconds = 8 hours.

Arithmetic intensity

$\to$ SNARKing intensity

These rough back of the envelopes demonstrate how far zkSNARKs lag in terms of "general" compute, but also notes how much faster specific workloads can be (as in the case of ETH mainnet with zkEVM, for instance).

In high performance computing/machine learning, one measurement often made to measure the efficiency of algorithms is that of arithmetic intensity: How many computation operations can be run relative to each memory load, i.e. how many FLOPs per Bytes does an algorithm/hardware implementation support? This is particularly important because a lot of computation nowadays is memory read/write speed bound, not raw compute.

I wish we measured a similar number for SNARK proving algorithms: What is the SNARK intensity of this VM/prover backend? How many instructions can you run per unit of prover computation? How many VM Cycles per Prover Cycles is your algorithm?

In general, the way to think about the SNARKing intensity of general compute is 3-tiered, from compute

$\to$ instructions

$\to$ prover constraints

$\to$ prover compute per constraint:

1. The cost of expressing operations in an instruction set: For instance, a hash takes ~100K MIPS instructions to write
2. The average number and cost of constraints for different instructions of the chosen instruction set: For instance, earlier in this note we assumed an average cost of ~10k constraints for MIPS in Supernova.
3. The average amount of prover work per constraint: For Supernova, this was expressed in the compute cost of MSMs.

Each of these transformations is surface for possible optimizations and future work! For instance, tinygrad optimises at the first transformation — expressing general ML models in small/efficient instruction sets tightly, tinyRAM optimises at the second layer by building an instruction set efficient to constrain, and finally Supernova is a trick specifically meant to reduce prover compute cost for VMs.

Risc0

Side note: What numbers does risc0 get? Why is this so difficult to find? I've even asked them on email and still can't find out -_-

---

1. I have practical interest in this, for… reasons. ↩︎