How Zero-Knowledge Proof Systems Fit Together: A Map for SNARKs, STARKs, and Folding

Zero-knowledge proof systems are usually presented as a list of competing products: Groth16, PLONK, STARKs, Halo2, Nova, a dozen zkVMs. Every few months someone asks me which one is best, and every time the useful answer starts with a different question: best at which layer? A deployed proving system is a stack of five or six separable choices. Two systems that share a name can differ at every layer, and two with different names can share almost everything.

I run awesome-zkp, a curated list of resources for learning, researching, and building with zero-knowledge proofs. It has a companion research history that follows the primary papers from Goldwasser, Micali, and Rackoff in 1985 through folding schemes and lookup-based virtual machines. The list stopped ranking systems a while ago. It organises them by the layer they change instead, and that turned out to be the thing readers found most useful. This post is that organisation written out in prose, with the definitions I had to get straight first and the checklist I run before a project goes into the list.

Nothing here is new research. The sources are the papers themselves and Justin Thaler's book, both linked at the end. What I add is the ordering, and the places where the popular vocabulary misleads.

A proof system has three separate properties, and most confusion in this field comes from treating them as one. Completeness means an honest prover holding a valid witness can convince the verifier. Soundness means a cheating prover cannot convince the verifier of a false statement, except with negligible probability. Zero knowledge means the proof reveals nothing about the witness beyond the truth of the public statement.

Soundness comes in two strengths. A proof is sound even against a prover with unlimited computation. An argument is sound only against efficient provers, under stated assumptions such as the hardness of discrete logarithms or collision resistance of a hash function. Nearly every deployed SNARK and STARK is an argument. The ecosystem says "proof" for all of them, which is fine as an umbrella word as long as you remember that a broken assumption breaks soundness.

The one that costs people money is the third: succinctness does not imply privacy. A validity proof can establish that a program ran correctly while exposing the entire execution trace. Many STARK and zkVM stacks make the zero-knowledge blinding optional because it costs prover time, and the default in a benchmark configuration is often off. When I read a project page that says "zero-knowledge rollup", the first thing I check is the zero-knowledge mode. It can be inherent to the construction, optional, disabled in the cited numbers, or not there at all. All four occur.

Here is the model. A statement enters at the top as a program or a relation, and a proof comes out at the bottom that some verifier can check. In between there are six decisions, and each one can be swapped without touching the application.

1. Arithmetization. The computation becomes algebraic constraints over a finite field. R1CS and QAP encode it as multiplication gates. AIR (algebraic intermediate representation) encodes it as transition constraints between rows of an execution trace, which suits machines. PLONKish adds custom gates and lookup tables, so a range check can be a table membership rather than 64 bit constraints. CCS (customizable constraint systems) is a later common language that covers all three.
2. Interactive protocol or IOP. Given the constraints, an interactive oracle proof defines what the verifier would check if it could query polynomials at random points: a sum-check, a permutation argument, a lookup argument, a low-degree test such as FRI. This layer decides the asymptotic prover and verifier cost.
3. Commitment layer. The verifier cannot really hold the polynomials, so the prover commits to them and proves evaluation claims. KZG uses pairings and a structured setup and gives constant-size openings. Inner-product arguments are transparent but the verifier does linear work. FRI with Merkle trees is transparent and hash-based, with larger proofs. Multilinear and code-based commitments such as Brakedown and the binary-tower work behind Binius trade proof size for a linear-time, field-agnostic prover.
4. Non-interactivity. The verifier's random challenges are replaced by hashes of the transcript (Fiat-Shamir), or the interaction is removed by a common reference string. This is the layer where a surprising number of real bugs live. The Frozen Heart disclosures in 2022 were Fiat-Shamir transcripts that omitted public values, across several independent implementations.
5. Composition. Optionally, proofs verify other proofs. Recursion runs a verifier inside a circuit. Folding (Nova and its descendants) combines constraint instances first and compresses once at the end, which is what makes incremental verifiable computation affordable.
6. Application verifier. Something checks the final proof: native code, an EVM contract with a gas budget, a light client, or the next proof in a chain. The verifier environment often decides the whole stack backwards. If it has to be an Ethereum contract, three pairings are cheap and a 200 KB FRI proof is not, which is why a hash-based prover so often ends with a pairing-based wrapper.

Changing one layer changes the setup requirement, the quantum posture, the proof size, the prover memory, the verifier cost, or the recursion story, without changing the application statement at all. That is why the labels fail. "PLONK" names an arithmetization and an IOP. It does not say whether the commitment is KZG or an inner-product argument, which curve, which transcript, which lookup, or which implementation. "STARK" names an IOP and a commitment family. "zkVM" names the thing above the top of the diagram.

Abstract layers are easier to hold on to with one concrete example. Take a small claim: "I know a preimage of this hash, and the preimage is below 2^64." Here is what each layer does with it in a typical PLONKish system with a KZG backend. That is the kind of stack behind most current rollups.

1. The hash function is written as a circuit. In a PLONKish arithmetization the S-box rounds become custom gates, and the range check on the preimage becomes a lookup into a table of small values rather than a bit decomposition. The witness is the preimage plus every intermediate value the gates need.
2. The prover interpolates the witness columns into polynomials over a multiplicative subgroup of the field. The IOP now says: the gate polynomial vanishes on the subgroup, the permutation argument holds (the same wire value appears everywhere it is copied), and the lookup argument holds (every looked-up value appears in the table).
3. Each of those is a polynomial identity. The prover commits to the witness polynomials with KZG, which means computing a multi-scalar multiplication against the structured reference string from a trusted setup ceremony. The commitment is one group element per polynomial.
4. The verifier would pick random evaluation points. In the non-interactive version the prover derives those points by hashing the transcript so far, which must include the public inputs, the commitments, and a domain separator. Leave the public inputs out of the hash and a malicious prover can pick them after seeing the challenge.
5. The prover opens the committed polynomials at the challenge points and batches the openings into a single KZG proof. The final proof is a handful of group elements and field elements, a few hundred bytes.
6. An EVM contract checks two or three pairings and a few scalar multiplications. It never sees the preimage. Whether it learns anything else depends on whether the witness polynomials were blinded with random terms before commitment, which is the zero-knowledge step, and which some libraries expose as a flag.

Now swap one layer. Replace KZG with FRI and the same circuit needs no ceremony, the proof grows to tens of kilobytes, the on-chain verifier becomes expensive, and the security assumptions move from pairings to hashes. Replace the PLONKish arithmetization with R1CS and a Groth16 backend and the proof shrinks to three group elements, the verifier does three pairings, and every circuit change needs its own setup ceremony. Same statement, same witness, three different products.

With the layers named, the families most people have heard of become easy to place. This is the table the list keeps, with the caveat it carries there. These are families, not comparable products. Concrete proof size and performance depend on the implementation, security level, and workload.

Two lineages are worth calling out because they explain most of what is happening now. The first runs from the sum-check protocol of 1992, through the GKR protocol of Goldwasser, Kalai, and Rothblum, to Spartan, HyperPlonk, Lasso, and Jolt. Its signature is multilinear polynomials instead of univariate ones: no FFTs, linear-time provers, and lookups big enough to hold an instruction set. The second runs from Kilian's 1992 idea of committing to a probabilistically checkable proof, through interactive oracle proofs, to FRI and STARKs. It is why hash-based systems are where the post-quantum arguments live.

The practical consequence is that "SNARK versus STARK" is usually a question about layer three. A STARK is a SNARK whose commitment layer is hash-based and transparent. Most of what people attribute to the S in STARK, scalability, follows from FRI and the AIR arithmetization. Both can be combined with a pairing-based wrapper at the end for a small final proof. Several production stacks are built that way.

If you only have time to understand one layer, make it the polynomial commitment scheme. In most modern SNARKs the arithmetization and the IOP define what must be checked. The commitment scheme determines how those checks become succinct, and what you have to trust for that to hold. The families have different profiles:

The setup model follows from this row. A pairing-based commitment needs a structured reference string, and someone has to generate it. Groth16 needs a new string per circuit. Sonic, PLONK, and Marlin made the string universal and updatable: one ceremony covers every circuit up to a size bound, and anyone can add a contribution later. In both cases the security claim is the same shape: the parameters are safe if at least one contributor generated their secret correctly and destroyed it. That is a real assumption with a real operational history behind it, and a hash-based commitment removes it at the cost of proof size.

Composition is the layer that changed the most in the last five years. Recursion means verifying one proof inside the circuit of another. It was established in theory in 2013 and made practical without a trusted setup by Halo in 2019, using an amortised inner-product commitment over a cycle of elliptic curves. Fractal did the same for hash-based proofs. Recursion is expensive because a verifier is a large circuit.

Folding takes a different route. Nova observed that for incremental computation you do not need a full proof at every step. You can combine two constraint instances into one relaxed instance with a single random linear combination, keep folding, and produce one real proof at the very end. The per-step cost drops to a couple of multi-scalar multiplications. SuperNova extended this to computations where each step runs a different circuit, and HyperNova and ProtoStar generalised it from R1CS to CCS and PLONKish relations. Folding is why "prove a long-running process" went from impractical to routine, and it is also where the soundness arguments are youngest, which the list flags with a Research label.

A zkVM sits above all of this. It is an instruction set, an execution trace, a memory-consistency argument, an arithmetization of that trace, and a backend proof system. Three architectural generations are visible in the papers. Compile a bounded program into a circuit (TinyRAM, 2013). Prove a machine trace with an instruction set designed for the arithmetization (Cairo, 2021). Or move instruction semantics into structured lookup tables (Jolt, 2023, on top of Lasso). Production zkVMs add compilers, continuations, proof compression, and verifier integrations that the backend paper never mentions.

So when a project says it is a zkVM, that is a statement about the top of the diagram and nothing else. One zkVM can use a STARK backend and another a folding backend. One can have zero knowledge on by default and the other off. Both are correctly described by the same three letters.

The curation rule for awesome-zkp is that an entry has to save readers time, expose a trade-off, or be a clearly better source than what is already there. Marketing pages, reposts, and abandoned projects with no historical weight do not go in. Inclusion is not an endorsement or a security review. Before a proof system or a zkVM is added, these are the questions I try to answer from primary sources, and if I cannot answer one the entry says so.

• Which arithmetization, which IOP, which commitment scheme, and which curve or field? If the documentation names only the family, the answer is incomplete.
• What is the setup model, and if there was a ceremony, where is the transcript and the verification procedure?
• Is zero knowledge inherent, optional, or off in the cited configuration? Benchmarks with blinding disabled are common and rarely labelled.
• What does the Fiat-Shamir transcript include, and has the implementation been checked against the Frozen Heart class of bugs?
• Is the security argument in the standard model, the random-oracle model, or an algebraic group model, and are the assumptions post-quantum? "Transparent" answers none of this.
• What are the proof size, prover memory, and verifier cost on a stated workload at a stated security level, measured by someone who does not sell the system?
• What do the audits cover, and what is the license?
• What does the project itself say its maturity is?

That last question is where the list's lifecycle labels come from. The habit of checking the zero-knowledge mode and the transcript contents comes from reviewing production circuits, where both had to be verified rather than assumed. An entry is marked Research, Alpha, Beta, Production, LTS, or Historical only when an official source says so. Mainnet deployment, GitHub stars, funding, and confident marketing do not count, and an unlabelled entry means nobody has classified it, not that it is fine. I got this wrong early on by labelling things from context, and the corrections taught me that the label a project gives itself is the only one I can defend.

The mechanics are boring and matter. Every link is checked by a weekly CI job using lychee, so dead links are caught before a reader hits them. It sends a browser user agent, because several academic hosts return 403 to the default one. Descriptions cite the linked source, end with a period, and avoid superlatives unless the source defines the comparison. Publication year is the first public version, and when a paper has a known correction, such as the gap in the original DARK security proof and its repair, the annotation says so rather than linking the fixed version without comment.

Is a STARK a SNARK? In the sense that matters, yes. A STARK is a succinct non-interactive argument whose commitment layer is hash-based and transparent, with FRI as its low-degree test. The two words describe different layers, so "SNARK vs STARK" is a question about the commitment scheme, not about two rival technologies.

Does transparent mean post-quantum? No. Transparent only means there is no secret setup. Bulletproofs and Halo are transparent and rest on discrete logarithms, which a large quantum computer breaks. STARKs are transparent and hash-based, which is the combination people usually mean.

Does a zkVM give me zero knowledge? Not by default. A zkVM is an execution model. Whether the proof hides the trace depends on the backend and on a configuration flag that several production stacks leave off for speed. Read the configuration the benchmark used, not the product name.

Groth16 or PLONK? Groth16 gives the smallest proof and the cheapest on-chain verifier and needs a ceremony per circuit. PLONK with KZG gives a slightly larger proof, a universal setup shared across circuits, and custom gates and lookups. If the circuit is stable and verified on Ethereum, Groth16 is still hard to beat. If the circuit changes often, PLONK.

Do I need a trusted setup? Only if the commitment layer is pairing-based. Choose a hash-based or inner-product commitment and there is no ceremony, at the cost of proof size or verifier work. Many stacks use both: a transparent prover inside and a pairing-based wrapper outside for the final on-chain proof, which brings the ceremony back for the wrapper.

The map earns its keep when something new appears. The procedure is short. Find the arithmetization: R1CS, AIR, PLONKish, CCS, or something custom. Find the commitment scheme, because that fixes the setup model and most of the trust story. Find where the challenges come from and what goes into the hash. Find whether there is a composition step and which kind. Then find the verifier environment, because that usually explains every other choice.

Do that and the marketing vocabulary falls away. A "post-quantum zkVM with STARK-based proving and Groth16 compression" becomes: AIR arithmetization, FRI commitment, Fiat-Shamir, recursive compression into a pairing-based wrapper, EVM verifier. Now you can ask the real questions. Is the final wrapper post-quantum? No, so the claim applies only to the inner proofs. Is zero knowledge on in the compression step? Check. What does the Groth16 wrapper's setup look like? A ceremony, with the usual assumption.

If you want the primary sources in order, the research history in the repository has reading paths for each lineage. The short versions: for theory, GMR to GMW to sum-check to the PCP theorem to Kilian to IOPs. For pairing SNARKs, KZG to GGPR to Pinocchio to Groth16 to Sonic and PLONK. For transparent proofs, IOPs to FRI to STARK to DEEP-FRI and Fractal. For recursion, Spartan and Halo to Nova to SuperNova and HyperNova. Each path is five or six papers and a few evenings.