2. SNARKs

Q What are SNARKs ?
A Prover P claims to know witness w satisfying some property. For example:

1. A preimage “w” for a designated output “y” of a cryptographic hash function “h”. A “w” such that h(w) = y
2. A private key “w” corresponding to a designated public key “y” for some crypto system

The brute force way to do it is P sends “w” to V, who directly checks it satisfies the claimed property, but we don’t want V to see the “w”, this here we use SNARKs (Succinct Non-interactive Argument of Knowledge), which does the same but better costs to V

• SNARK proof “π” must be shorter than the witness w. This is what “succinct” means
• Ideally, checking n is faster than checking “w” directly. Called “work-saving” for V

Q How can we use this SNARKs ?
A

1. Start with a computer program written in high-level programming language (C, Java, etc.). Hash pre-image example: Program takes w as input, applied h to it, and checks that output equals y
2. Step 1: Turn the program into an equivalent model amenable to probabilistic checking. Typically some type of circuit-satisfiability or R1CS problem. Called the Front End of the system
3. Step 2: Run a SNARK for circuit-satisfiability/R1CS. Called the Back End of the system. Examples: Groth16, Marlin, Plonk, Ligero, Hyrax, Libra, Virgo, Brakedown, Supersonic, etc. etc.

Want a SNARK for circuit-SAT or R1CS for which:

1. P runs in linear-time, or as close as possible
2. Proof size is as small as possible, Ideally a few hundred bytes or a few KBs
3. V is as fast as possible. Ideally V reads any public input, and does a few milliseconds of extra work

Also ideal:

1. Transparent (no “toxic waste” produced in a trusted setup)
2. Plausibly post-quantum secure

Key Paradigm for Backend Design

1. Give a “polynomial IOP” for R1CS or circuit-satisfiability
   • P’s first message in the protocol is a polynomial “h”, V does not learn “h” in full
   • The description size of “h” is as large as the circuit. Rather, V is permitted to evaluate “h” at, say, one point
   • After that, P and V execute a standard interactive proof
   • Types of Different Polynomial IOPs in increasing order of P costs and decreasing order of proof length and V cost
     1. Based on interactive proofs (IPs). Example SNARKS: Hyrax, vSQL, Libra, Virgo
     2. Based on multi-prover interactive proofs (MIPs). Example SNARKS: Spartan, Brakedown, Xiphos
     3. Based on constant-round polynomial IOPs. Example SNARKS: Marlin, Plonk
2. Combine with polynomial commitment scheme to get succinct interactive argument
   • P binds itself to a polynomial “h” by sending a short string Com(h)
   • V can choose “x” and ask P to evaluate h(x)
   • P sends “y”, the purported evaluation, plus a proof “n” that “y” is consistent with Com(h) and “x”
   • Goals:
     • P cannot produce a convincing proof for an incorrect evaluation
     • Com(h) and “π” are short and easy to generate; “π” is easy to check
   • This is what decides is SNARK is quantum secure or not
   • Types of Polynomial Commitment schemes
     1. Based on pairings (not transparent nor post-quantum). e.g., KZG10, PST13, ZGKPP18. Unique property: constant sized evaluation proofs
     2. Based on discrete logarithm (transparent, not post-quantum). Examples: BCCGP16, Bulletproofs, Hyrax, Dory*
     3. Based on IOPs + hashing (transparent and post-quantum). e.g., Ligero, FRI, Brakedown
     4. Groups of unknown order (transparent if using class groups, not post-quantum). P very slow due to use of class groups. E.g., DARK, Dew
3. Apply Fiat-Shamir transformation to render non-interactive

This is how all SNARKs are designed other than “linear-PCP based” ones (GGPR13, Pinocchio, Groth16, etc.)

• So all transparent and “universal trusted-setup” SNARKs are designed this way
• Even linear-PCP based SNARKs use techniques very similar to certain polynomial commitments (KZG)

There are two types of SNARKs

1. Non-Transparent SNARKs (Trusted Setup): These require a setup ceremony to generate a Common Reference String (CRS) or Structured Reference String (SRS). This setup involves “toxic waste” which are random elements that, if not destroyed, could allow a malicious actor to forge proofs
   1. Linear-PCP based:
      • Pros: Shortest proofs (3 group elements), fastest V
      • Cons: Circuit-specific trusted setup, slow and space-intensive P, not post-quantum
      • Ex: Groth16
   2. Constant-round polynomial IOP + KZG polynomial commitment:
      • Pros: Universal trusted setup
      • Cons: Proofs are ~4x-6x larger than Groth16, P is slower than Groth16, also not post-quantum
      • Counterpoint for P: can use more flexible intermediate representations than circuits and R1CS
      • Ex: Marlin, Plonk
2. Transparent SNARKs (No Trusted Setup): These are public-coin systems that do not rely on secrets for setup, meaning anyone can verify the proof without trusting a third party
   1. MIPs and IPs + (fast-prover polynomial commitments):
      • Pros: Fastest P in the literature, plausibly post-quantum + transparent if polynomial commitment is
      • Cons: Bigger proofs than 1. and 2. above
      • Ex: Spartan, Brakedown, Xiphos, Hyrax
   2. (Any polynomial IOP) + FRI polynomial commitment:
      • Pros: Shortest proofs amongst plausibly post-quantum SNARKS
      • Cons: Slow P, proofs still fairly large
      • Ex: Fractal, Aurora, Virgo, Ligero++

Rollups

• Public blockchains should be verifiable by weak nodes
  • Extreme Bitcoin-community ethos: “Not your node, not your validation”
  • Less extreme: If most Ethereum nodes were to run on AWS servers, Amazon could disrupt the network
• Two costs to run a node:
  • Do computation to validate transactions
    • For currency transfers, this is mainly checking digital signatures and account balances
    • For general Ethereum smart contracts, may have to execute arbitrary EVM bytecode. Context: Smart contracts are written in the high-level language Solidity and compiled to Ethereum Virtual Machine (EVM) bytecode, which is then executed by Ethereum nodes
  • Download/store/access all data that lives on-chain
    • Let me call this data “the state of the world”
    • Think of it as the ETH account balances of all users
• The Main Idea of Rollups is
  • Treat the blockchain as a computationally weak V and the rollup service as an untrusted P. This idea alone can save nodes work. E.g., they don’t have to verify digital signatures directly, can just check a proof that all signatures in all on-chain transactions are valid
  • It does not directly reduce/compress the amount of on-chain data
  • We’ll call the blockchain “layer 1 (L1)”, or “the chain”, and the rollup “layer 2” (L2)
• The Second Idea of Rollups is
  • Don’t store the “state of the world” on-chain, only store a cryptographic commitment to it. E.g., a Merkle-hash of all account balances
  • Binding of the commitment ensures no one can “alter” the data. Anyone who succeeds in “authenticating” some piece of data against the commitment must be presenting the real data
  • Key consequence: No longer need to rely on the blockchain’s consensus mechanism to ensure no one futzes with the data
  • Two options for data availability (i.e., making the committed data available to anyone outside the rollup provider, to ensure liveness if the provider ever disappears):
    • Store the data on-chain anyway to ensure its availability
      • But it can live in cheaper storage, called CALLDATA, only stored by full nodes
      • Ethereum is considering changes to make this option more scalable
        • EIP4444 would have on-chain CALLDATA expiring after a year
        • Sharding would increase amount of on-chain storage
      • Still, the benefits of rollups will be bounded if data is stored on-chain
    • Use economic incentives to get off-chain entities to store the data and make it available

Q How Rollups work ?
A

• First attempt:

  • At all times, a commitment to the state-of-the-world is stored on L1
  • The rollup applies a batch of transactions to obtain an updated state-of-the-world and posts the new commitment on L1
  • Problem: how does L1 know that the new commitment is correct?

• Solution: The rollup pairs the new commitment with a SNARK proof of its correctness

  • The end state was obtained by applying the batch of transactions to the start state, and all of the transactions are all valid (digitally signed, no negative balances, etc.)
  • “π” must be verified on-chain. All blockchain nodes will apply the SNARK verifier to the proof

Q How do we measure Rollups Performance ?
A

• Latency: delay between transaction posting to L2 and a proof capturing it posting to L1. Determined by P time. Plus how long one has to wait for enough transactions to hit L2 to fill a batch
• Throughput: number of L2 transactions that can be processed by the rollup in a given amount of time
  • Suppose one can upload a proof capturing X transactions to L1 in Y seconds. And X transactions hit L2 every Y seconds
  • Then one can send a new batch to P every Y seconds, and at the same time post to L1 the most recently completed proof. In steady state this posts a proof to L1 covering X transactions every Y seconds
  • Throughput: X/Y transactions/second (TPS). This has nothing to do with latency (P time). It only involves V costs. More precisely, the ratio of V costs to batch size. Throughput is what determines “blockchain scalability”. But latency demands will constrain batch sizes, and hence throughput, in practice
  • When validity rollups discuss TPS, they are talking about throughput. Often ignoring latency
    • Counterpoint: alternatives to validity rollups do have high latency
    • Optimistic Rollups: ~7 days
    • Visa: ~48 hours
    • Not a high bar to clear. Not clear people mind the wait (in some contexts)
    • It may not be the end-user taking on risk induced by latency. A centralized exchange may want to instantly finalize trades for users, taking on the risk that something goes wrong before finalization to L1
  • Recursion/Proof aggregation might help P latency by unlocking parallelism
    • Prover latency in SNARK systems can be reduced by splitting a large computation into smaller independent parts, proving them in parallel, and then aggregating the results into a single proof
    • Instead of running one heavy prover over the entire circuit, the computation is divided into sub-circuits (or batches). Each sub-circuit is proven independently, producing its own proof. Since these are independent, they can run simultaneously across multiple cores or machines, significantly reducing wall-clock time
    • However, multiple proofs are inefficient to verify, especially on-chain. So, an aggregation step combines all sub-proofs into one succinct proof. This can be done either via dedicated aggregation schemes or through recursion, where a proof verifies other proofs
    • This approach gives a key benefit: parallelism reduces proving time, while aggregation preserves constant-size verification. The main trade-off is overhead, too many small splits increase aggregation cost, so choosing the right batch size is important

Q Where do the data in the L1 stays ?
A Two options for data availability (i.e., making the committed data available to anyone outside the rollup provider, to ensure liveness if the provider ever disappears or someone needs to withdraw their funds):

1. Store the data on-chain to ensure strong data availability guarantees. This is typically done using CALLDATA (or newer blob data), which is part of the transaction input and is accessible to all nodes
   • CALLDATA is cheaper than persistent storage but still contributes to L1 bandwidth usage (not “only full nodes”, it’s part of the chain, though some nodes may prune history)
   • Ethereum is evolving this model for better scalability:
     • EIP-4444 proposes pruning historical data (~1 year), reducing storage burden but requiring archival providers for old data
     • Danksharding (and proto-danksharding / blobs like EIP-4844) increases data throughput by introducing cheaper, temporary data availability
   • It guarantees that anyone can reconstruct the rollup state from L1 data with this it enables trust-less exits and independent verification
   • Limitation: Rollup scalability is bounded by L1 data throughput, not computation
2. Use off-chain data availability (DA) where external entities store and serve the data
   • Examples: Data Availability Committees (DACs), Peer-to-peer storage, and Dedicated DA layers
   • This guarantees much higher scalability as there’s no L1 data bottleneck
   • Trade-offs:
     • Requires trust or economic incentives for availability
     • If data is withheld, users cannot reconstruct state → funds may become temporarily or permanently stuck
   • This model is typically referred to as Validium-style systems

Q Should entities other than the rollup service be able to submit proofs to advance the state of the system?
A

• If no, the system becomes inherently centralized, with a single prover or sequencer controlling state progression. This introduces risks like the operator can censor transactions by simply ignoring them, and the entire system becomes fragile from a liveness perspective, if the operator goes offline or is compromised, the rollup can halt completely since no one else is permitted to advance the state
• If yes, where anyone can generate and submit proofs, improves decentralization and censorship resistance significantly. It ensures that even if one party fails or behaves maliciously, others can continue progressing the system. However, this openness introduces a subtle but critical issues like data availability attacks, which arise when correctness (valid proofs) is decoupled from availability (access to underlying data)
• In a data availability attack, an adversary generates a perfectly valid proof for a legitimate state transition but withholds the underlying transaction data (or provides incorrect data). The on-chain verifier, which only checks the proof’s validity, accepts it and updates the state commitment (for example, a Merkle root). At this point, the system is technically in a valid state, but no one else has access to the actual data that produced this new state. As a result, future provers cannot reconstruct the state or compute the necessary intermediate values such as Merkle paths or updated hashes. This leads to a situation where the system is cryptographically valid but operationally stuck, breaking liveness because no further state transitions can be proven
• Prevention techniques
  • Enforce on-chain data availability. The verifier contract requires that all state transition data be published on-chain, typically via CALLDATA or newer blob-based mechanisms. This guarantees that the data is publicly accessible, allowing any participant to reconstruct the full state and continue generating proofs, thereby preserving liveness
  • However, a naive implementation of this approach is inefficient. If all state changes are directly fed into the SNARK for verification, the cost becomes prohibitive. Each account update would require cryptographic checks inside the circuit, significantly increasing both proving and verification complexity
  • To address this, systems use an optimization known as the “hash trick.” Instead of including the full state transition data inside the SNARK, the prover includes only a cryptographic hash h of that data as a public input. The actual data itself is posted separately as CALLDATA on-chain. The verifier contract then recomputes the hash of the posted data and checks that it matches h. This approach keeps the SNARK circuit small and efficient while still ensuring that the underlying data is available and verifiable on-chain
  • The key insight here is a clean separation of responsibilities: the SNARK is responsible for verifying the correctness of computation, while the L1 layer ensures data availability. This separation is what enables scalable, secure, and decentralized rollup designs

Frontend for Rollups

In validity rollups, the frontend converts program execution into a circuit (constraint system), which is then proven using SNARKs/STARKs. The idea is to express computation as a satisfiability problem and prove that a valid execution (witness) exists. This is the core pipeline: program → circuit → proof

• Languages like Cairo (used by StarkWare) are designed specifically for this purpose. Cairo is low-level and close to assembly, so developers must be aware of proof constraints. Arithmetic is done over a finite field, and operations like comparisons are not native and must be manually encoded, which increases complexity. It also uses techniques like non-deterministic advice to reduce constraint costs
• Other projects (zkSync, Scroll, Polygon Hermez) aim to support higher-level languages like Solidity by compiling them into circuits. This improves developer experience but makes the system much harder to build, since it requires a full compiler + proving pipeline. As a result, many systems historically launched partial stacks before achieving full end-to-end proving

Efficient proving requires small, optimized circuits, so projects rely heavily on hand-written circuit components (gadgets). These optimize common operations but introduce complexity, often resulting in thousands of lines of low-level circuit code

• This creates a trade-off: rollups “rely on math,” but that math becomes large and hard to audit. Advanced features like recursive proofs (especially on curves like BN254 used in Ethereum) further increase complexity, sometimes requiring big-integer arithmetic inside circuits
• So systems either hide complexity in large backend circuit code, or push responsibility to developers (e.g., Cairo requires SNARK-aware programming)

Backends for Rollups

The backend in rollups is responsible for actually generating and verifying proofs once the computation has been expressed as a circuit. It mainly consists of a proof system (SNARK/STARK) and a polynomial commitment scheme, which is a core building block used to efficiently verify large computations

• StarkWare’s backend is based on STARKs, using FRI (Fast Reed-Solomon IOP of Proximity) as the polynomial commitment scheme combined with a constant-round polynomial IOP. This approach is fully transparent (no trusted setup) and highly scalable, but proofs tend to be larger compared to SNARK-based systems
• Plonk-based systems take a different approach. zkSync uses Plonk with KZG polynomial commitments, which produce very small proofs and fast verification, making them attractive for L1 verification costs. However, KZG requires a trusted setup. Polygon Zero also builds on Plonk-like ideas but replaces KZG with FRI to achieve transparency, effectively blending SNARK-style circuits with STARK-style commitments
• Some systems, like Zcash Orchard, experiment with alternative commitments such as Bulletproofs to avoid trusted setups. However, Bulletproof-based commitments are generally not “work-saving” for verifiers (verification cost grows with circuit size), which makes them less suitable for rollups where cheap on-chain verification is critical

Backend design is mainly about trade-offs between:

• Trusted setup vs transparency (KZG vs FRI)
• Proof size vs scalability (SNARKs vs STARKs)
• Verifier cost vs prover cost

How does Polynomial IOP works ?

To understand how a Polynomial Interactive Oracle Proof (Polynomial IOP) works, we start from the Arithmetic Circuit Satisfiability (AC-SAT) problem. We are given an arithmetic circuit C defined over a field F, with size S, and a claimed output value y. The goal is to check whether there exists an input (called a witness w) such that evaluating the circuit on this input yields C(w) = y

• A useful way to think about this is through a transcript T. A transcript assigns a value to every gate in the circuit, not just the inputs. If the witness w is valid, then evaluating the circuit naturally determines the value at every internal gate. A transcript is therefore correct if all these assigned values are consistent with the circuit’s operations (addition, multiplication, etc.) and the final output equals y
• The key conceptual shift is instead of viewing the transcript as a list of values attached to circuit gates, we reinterpret it as a function. Since the circuit has size S, we can label each gate with a unique binary string of length log S. This lets us treat the transcript as a function: $$
  T : {0,1}^{\log S} \rightarrow F
• In other words, the Boolean hypercube ({0,1}^{\log S}) indexes all gates, and (T(x)) gives the value assigned to the gate labeled by x

Start of Polynomial-IOP

• The prover P does not send the full transcript (too large). Instead, the first message is a (log S)-variate polynomial h which is claimed to be the multilinear extension of a correct transcript T, meaning: $$
  h(x) = T(x) \quad \forall x \in {0,1}^{\log S}
• This means:
  • On Boolean inputs → h matches the actual circuit transcript
  • On non-Boolean inputs → h is still well-defined (since it’s a polynomial over (F^{log S})
• Important:
  • Domain of T: ({0,1}^{\log S}) (small)
  • Domain of h: (F^{\log S}) (huge)
• So h is a low-degree extension of the transcript that compresses the entire computation into a structured algebraic object
• The verifier V cannot read all of h, it can only query a few evaluations

Q Why is sending h powerful?
A Think of h as a distance-amplified encoding of the transcript T

• Intuition:
  • Two transcripts T and T' might differ in just one gate
  • But their extensions h and h' will differ on almost all points in (F^{\log S})
• By the Schwartz-Zippel lemma:
  • If h \neq h', then they disagree on most of the domain
  • Probability of missing an error ≈ \frac{log S}{|F|}
• This gives:
  • Even a single incorrect gate → becomes globally detectable
  • This is why we call it distance amplification
• So instead of checking all gates, V just checks a few random points

From Circuit Constraints → Polynomial Constraints

• Now we need to verify that h actually corresponds to a valid computation
• Instead of checking each gate individually, we encode all constraints into a single polynomial condition
• Step 1: Constructing a constraint polynomial
  • Given polynomial h, define a new polynomial: $$
    g_h(a,b,c)
  - Goal: $$ h \text{ is valid } \iff g_h(a,b,c) = 0 \ \forall (a,b,c) \in {0,1}^{3\log S} $$ - Key idea: - Each triple (a, b, c) corresponds to a gate and its inputs - `g_h` checks whether gate computations are correct - Construction (intuition): $$ g_h(a,b,c) = \text{add}(a,b,c)\cdot (h(a) - (h(b)+h(c))) + \text{mult}(a,b,c)\cdot (h(a) - h(b)h(c)) $$ - This enforces: - If gate `a` is addition of `b,c` → checks `h(a) = h(b) + h(c)` - If gate `a` is multiplication → checks `h(a) = h(b) * h(c)` - Otherwise → contributes 0 - To evaluate (g_h(r)), we only need 3 evaluations of `h`, this keeps verifier work small
• Step 2: Checking the constraint efficiently
  • Problem:
    • Need to check: $$
      g_h(x) = 0 \quad \forall x \in {0,1}^{3\log S}
    $$-Thisisstillexponential\to notfeasibledirectly$$

The Key trick is to use Vanishing Polynomials:

• Suppose we want to check a polynomial is zero over a set (H)
• Fact: If (g(x)=0) for all (x \in H), then: $g(X)=q(X)\cdot Z_H(X)$
• Where Z_H(X) = \prod_{a \in H} (X - a) called the vanishing polynomial

Polynomial IOP Check:

• Prover sends polynomial q such that: $$
  g_h(X) = q(X)\cdot Z_H(X)
• Verifier checks this by:
  1. Sample random F(r)
  2. Check: $$
     g_h(r) = q(r)\cdot Z_H(r)
• If false → reject
• If true → accept with high probability

Efficiency:

• Evaluating g_h(r): Requires only 3 evaluations of h
• Evaluating Z_H(r): Efficient if (H) has structure. for example, if (H) = set of (n)-th roots of unity: $Z_H(r)=r^n-1$
• So verifier work is Logarithmic / very small and Independent of circuit size (S)

Summary:

• We started with Checking (S) gates → expensive
• Then:
  1. Encode transcript as function T
  2. Extend to polynomial h
  3. Encode constraints into polynomial g_h
  4. Reduce global check → single random check using Z_H
• Move from discrete computation (circuits) → to continuous algebra (polynomials) → enables randomized verification with very few queries