Lambda VM: the hash function

A STARK is only as strong as its hash

In our first post we said something that sounded like a feature: Lambda VM's security rests on hash functions and nothing else. No elliptic curves, no pairings, no trusted setup, and because of that, no known quantum attack beyond the generic speedups every hash has to live with. It is a feature. It also means that, with the hash being the only thing holding the proof up, which one you pick matters the most.

This post is about that decision: what a hash does inside a STARK, what kinds of hashes exist, why each one costs what it costs, and where we stand. It gets a bit more technical than the previous two, because the interesting part is in how these functions work inside.

A single cryptographic assumption

A STARK commits to data with Merkle trees and turns an interactive protocol into a non-interactive proof with Fiat-Shamir, and both of those are built from a hash function. That is the entire list of cryptographic assumptions. Everything else in the proof, the low-degree test, the lookup argument, the constraint checks, is either information-theoretic or rests on proven bounds, not on a hard problem that a better computer could crack.

This is what makes the proof post-quantum, with the usual care in the wording. Shor's algorithm breaks elliptic curves and pairings outright; nothing like that is known for hash functions, where quantum computers only get generic speedups (Grover's search and its relatives), which is one reason digests are 256 bits rather than 128. And it is not just folklore. Chiesa, Manohar and Spooner proved in 2019 that hash-based succinct arguments built from interactive oracle proofs, the family STARKs belong to, remain secure in the quantum random oracle model.

That is the security side of the hash. The cost side only shows up when you start verifying proofs inside proofs, and that is where the rest of this post goes.

Why recursion makes the hash expensive

A hash does two jobs in a STARK. The first is commitments: every table of the trace is extended and hashed into a Merkle tree, and the root is what the prover commits to. The second is the Fiat-Shamir transcript: the roots and the values the prover sends are absorbed into a running hash, and the challenges come out of it.

In a base proof, all of that hashing is simply computed. The prover builds the Merkle trees natively, millions of hash calls on a CPU or a GPU, and none of those calls is itself constrained: the tree is scaffolding, only its root goes into the proof, and the verifier recomputes a small part of it (one path per query, plus the transcript) natively too. At this level the only thing that matters about the hash is how fast it runs.

Recursion changes what a hash is. The verifier is now a program running inside the VM, and the point is to prove that it ran correctly. Every hash that program computes has to be proven like any other instruction: it becomes rows in a trace table, and every step of the permutation becomes a constraint the prover has to satisfy and commit to. The recursive verifier computes far fewer hashes than the base prover did, but each one now costs a table instead of an instruction, and with a bit-oriented hash that table is large. That is how hashing goes from being essentially free in the base proof to being the dominant cost of the recursive one.

This is also where the unit of cost changes. Natively you count nanoseconds. In a proof you count the size of the trace: every value in every row of every table has to be committed to and checked, so the cost of a hash is how many of those values one evaluation takes. A hash can be fast by the first measure and terrible by the second, and for almost every hash in existence that is exactly the case.

How a traditional hash works, and why a circuit struggles with it

SHA-2, Keccak (the SHA-3 family, and the hash Ethereum uses everywhere) and BLAKE3 belong to the same tradition: each is a permutation of a block of bits, built from operations a CPU does in one instruction. Keccak keeps a state of 1600 bits as 25 lanes of 64, and runs 24 rounds of the same five steps: XOR each lane with the parity of two neighbouring columns, rotate each lane by a fixed amount, shuffle the lanes around, apply the one non-linear step (each bit becomes a ⊕ (¬b ∧ c) with its two neighbours in the row), and XOR in a round constant. SHA-2 and BLAKE3 mix things differently, with additions modulo 2³², rotations and XORs instead of ANDs, but the flavour is the same. Everything is bits and machine words.

That is exactly why they are fast. XOR, AND, rotate and add are single instructions, they vectorize well, and they run in constant time. It is also why they have held up: these designs have been attacked in public for a long time, SHA-2 for about two decades and Keccak for most of that, and the best known attacks reach only a fraction of the rounds.

A proof system sees none of that. A STARK is written over a prime field, and the only operations it can express natively are addition and multiplication modulo p. A XOR is neither. The textbook way to constrain one is to split every word into its bits, one variable each, pinned to 0 or 1 by b·(1 − b) = 0, and then write a ⊕ b as a + b − 2ab, bit by bit. Rotations become a rewiring of those bit variables. Additions modulo 2³² need their carries made explicit and constrained. A single Keccak permutation, done that way, is tens of thousands of trace entries. The alternative, which is what we do in Lambda VM, is lookup tables: a precomputed table of every pair of bytes with their XOR and AND, so that each byte operation becomes one lookup instead of eight bit constraints. It helps a lot, and it is still expensive.

There is a second, quieter cost. Everything a STARK handles is a field element, and a byte-oriented hash wants bytes. So before you can hash a Merkle leaf or absorb a value into the transcript, you serialize field elements into bytes, and inside a circuit that serialization is its own gadget. When we measured our first recursive verifier, almost everything that was not hashing was this: turning numbers into bytes so that a hash could eat them.

How an algebraic hash works, and why a circuit loves it

Algebraic hashes (the formal name is arithmetization-oriented) start from the other end. Instead of bits, the state is a small vector of field elements: a dozen in a 64-bit field like Goldilocks, more in the 31-bit fields some zkVMs use. The hash is a sponge: part of the state, the rate, absorbs input and emits output, and the rest, the capacity, is never touched from outside; the size of the capacity is what sets the security level. Hashing is just running one permutation on that state over and over.

The permutation is a substitution-permutation network written directly in field arithmetic. Each round adds a constant to every element, applies a non-linear map to each element, and mixes them all together with a matrix. The non-linear map is the whole trick. It is x ↦ x^α for the smallest exponent α that makes the map a bijection on the field (any α coprime with p − 1 will do), which gives x⁷ in Goldilocks and BabyBear, x³ in KoalaBear and x⁵ in BN254. The mixing is an MDS matrix, chosen so that every output depends on every input and small differences spread as fast as they possibly can.

Poseidon arranged this as a few full rounds at the start and at the end, where every element goes through the S-box, and a longer run of partial rounds in the middle, where only one element does. That keeps the algebraic degree high enough for security while cutting most of the multiplications. Poseidon2 kept the structure and replaced the matrices with much cheaper ones, removing most of what the linear layer used to cost. The Rescue family (Rescue-Prime, and Miden's RPO and RPX) went a different way: each round applies x^α and then its inverse, x^{1/α}. The inverse is expensive to compute, since 1/α is a huge exponent, but it is cheap to verify, because checking that y = x^{1/α} is the same as checking that y^α = x, and a verifier only ever checks. That asymmetry, costly for whoever computes and cheap for whoever verifies, is exactly what a recursive verifier wants.

Inside a circuit all of this is nearly free. An S-box x⁷ is three multiplications. The matrix is linear, so it costs nothing in constraints. There are no bits, so no decomposition, and the inputs are already field elements, so no serialization either. A whole permutation comes out at a few hundred trace entries where Keccak needs tens of thousands.

The price is paid elsewhere. Natively, every one of those steps is a field multiplication, which is several CPU instructions, and there are hundreds of them per permutation, so an algebraic hash is slower than BLAKE3 by a large factor, and that cost lands on the prover, which runs millions of them. And they are young: Poseidon and Rescue date from 2019, Poseidon2 and RPX from 2023, against about two decades of public attacks on SHA-2. The attacks that apply to them are algebraic rather than statistical, which is newer ground, and there are open bounty programs trying to break them. Nothing with recommended parameters has fallen so far, but "how long have people been trying" is a real criterion, and it favours the old hashes.

A third way: change the field, not the hash

Until recently the choice looked like a dial between those two families. Then a line of work turned the problem around: instead of designing hashes for prime-field circuits, design the circuit for the field the hashes already live in. In a binary field, an extension of GF(2), addition is XOR and multiplying two bits is an AND, so the operations SHA-2 and BLAKE3 are made of become native constraints instead of expensive gadgets. Binius showed the proof system could be built on such fields, and more recently Flock showed that batches of standard hashes can be proven this way at practical speed. As Justin Drake put it when Ethereum's research roadmap moved in this direction, the key was not SNARK-friendly hashes but hash-friendly SNARKs.

It is early, and it is a different proof system rather than a drop-in change. But it means the trade-off is not fixed. It moves when the prover moves, which is worth keeping in mind before committing to a hash for the next ten years.

What others chose

Every zkVM team has had to make this call, and they did not all land in the same place. SP1 and RISC Zero went algebraic all the way: Poseidon2 for the base proofs and for every recursion layer, over 31-bit fields where Poseidon2's S-box is cheap. StarkWare's Stwo went the other way. It commits with Blake2s by default, keeps a Poseidon option for the proofs that have to be verified on-chain, and accepts that recursion is dearer; their argument is that if you have enough to prove, the cost of the recursion layer stops mattering. Miden lets each proof choose: BLAKE3 unless the proof is going to be verified recursively, in which case one of its algebraic hashes. ZisK ships Poseidon today and is building out a BLAKE3 path alongside it. And Ethereum's own lean zkVM, after years of work on Poseidon, switched to a traditional hash over binary fields, the third way above.

If there is a pattern, it is that the choice follows where the cost is felt. Teams whose bottleneck is the recursive verifier go algebraic. Teams whose bottleneck is the base prover go traditional and absorb the recursion cost. And the binary-field work is an attempt to not have to choose.

Where we are

Lambda VM uses Keccak-256 for both jobs, commitments and transcript. We chose it for the same reasons we chose everything else in the first post: it is standard, it has been attacked in public for a long time, Ethereum speaks it natively, and it meant one fewer new primitive to be responsible for. For proving a block on its own, that was and still is a perfectly good choice.

Recursion changed the picture. When we built our first recursive verifier and measured where its cost went, the answer was hashing, by a wide margin, and most of what was not hashing was the byte serialization that Keccak forces on us. Of the hashes we could pick, Keccak is close to the most expensive one to verify inside a circuit. So we did what the measurements asked for: we built a BLAKE3 accelerator and measured it, we measured Poseidon, and our recursion experiments currently run on an algebraic hash, which cuts the verifier's work by a large factor.

None of that is a final answer. Keccak is what we run today; the work on making recursion faster is what is pushing us to experiment, and the decision will come from measurements and from how much we trust each candidate, not from which one is fastest this month. When it is settled, it will get its own post.