Zero-Knowledge Proofs: SNARKs vs. STARKs, Plonk & Arithmetic Circuits

From Computation to Polynomials: The Compilation Pipeline (AST -> R1CS -> QAP)

Standard programming code (such as checking if a password hash matches or executing a token transfer loop) cannot be proven directly by zero-knowledge algorithms. The code must undergo a specialized cryptographic compilation pipeline that transforms high-level logic into an algebraic system of polynomial equations over a finite field ${\mathbb{F}}_p$.

The standard compilation pipeline proceeds through four stages:

1. Computation to Arithmetic Circuit:

High-level code is flattened into an directed acyclic graph (DAG) of basic arithmetic gates consisting exclusively of addition ($+$) and multiplication ($\times$) operations over ${\mathbb{F}}_p$. Non-linear logic (like Boolean conditionals and bit-shifts) are decomposed into polynomial equations ($b\cdot (b-1)=0$ enforces that $b\in \{0,1\}$).

1. Arithmetic Circuit to R1CS (Rank-1 Constraint System):

The circuit is expressed as a system of matrix constraints of the form:

$$(A\cdot s)\circ (B\cdot s)=(C\cdot s)$$

where $s=[1,x_1,\dots ,x_m,w_1,\dots ,w_n{]}^T$ is the complete witness vector containing all intermediate wire values, $A,B,C$ are sparse matrices representing gate connections, and $\circ$ denotes the Hadamard (element-wise) vector product. Each row in the matrix system represents a single multiplication gate: $(L_i\cdot s)\times (R_i\cdot s)=O_i\cdot s$.

1. R1CS to QAP (Quadratic Arithmetic Program):

Using Lagrange Polynomial Interpolation, the discrete matrix equations are encoded into continuous polynomials $A(x),B(x),C(x)$. The prover demonstrates that the constraint holds across all evaluation points by showing that:

$$P(x)=A(x)\cdot B(x)-C(x)=H(x)\cdot T(x)$$

where $T(x)={\prod }_{i=1}^m(x-i)$ is the public Target Polynomial with roots at every gate index, and $H(x)$ is the quotient polynomial.

If the prover knows a valid witness, $P(x)$ is perfectly divisible by $T(x)$ with zero remainder. Checking polynomial equality at a single secret random challenge point $s$ (via the Schwartz-Zippel Lemma) verifies the correctness of millions of arithmetic gates simultaneously.

SNARKs (zk-SNARKs): KZG Commitments, Groth16 & PlonK Universal Systems

zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge:

• Succinct: The proof size is tiny (typically 128 to 800 bytes) and can be verified in milliseconds.
• Non-Interactive: The prover generates the proof in a single message without requiring back-and-forth interactive rounds with the verifier (via the Fiat-Shamir Heuristic).
• Argument of Knowledge: Computationally sound under cryptographic hardness assumptions.

The evolution of zk-SNARK proving systems represents one of the most remarkable algorithmic advances in cryptography:

1. Groth16 (2016):
2. Uses bilinear pairings on elliptic curves (e.g., BN254 / alt_bn128).
3. Produces the absolute smallest proofs (3 group elements, ~130 bytes) with hyper-fast on-chain verification (~200,000 gas on Ethereum).
4. Major Drawback: Requires a Circuit-Specific Trusted Setup ceremony (Powers of Tau). If the smart contract circuit is modified by a single line of code, an entirely new multi-party trusted setup ceremony must be conducted.

1. PlonK (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge - 2019):
2. Introduces Universal and Updatable Trusted Setup: A single global setup ceremony can be used for any arbitrary circuit up to a maximum degree bound.
3. Uses Grand Product Permutation Arguments to enforce copy constraints between circuit wire inputs and outputs.
4. Polynomial Commitments (KZG / Kate-Zaverucha-Goldberg): Commits to high-degree polynomials using a single elliptic curve point $[P(\tau ){]}_1=\sum p_i[{\tau }^i{]}_1$. The verifier uses elliptic curve bilinear pairings $e(A,B)=e(C,D)$ to verify polynomial evaluations without revealing the underlying coefficients.

PlonK and its modern variants (Plonky2, HyperPlonk, Halo2) form the foundational backbone of modern zkEVMs and enterprise ZK scaling solutions.

STARKs (zk-STARKs): FRI Protocols, Hash-Based Security & Quantum Resistance

Invented by Eli Ben-Sasson et al. (the founders of StarkWare), zk-STARKs (Zero-Knowledge Scalable Transparent Argument of Knowledge) offer an alternative proving paradigm that eliminates the limitations of elliptic curve SNARKs.

The architectural hallmarks of STARKs:

1. Transparent (No Trusted Setup):
2. STARKs require zero multi-party trusted setup ceremonies. All randomness is generated transparently using public collision-resistant cryptographic hash functions (such as Keccak-256 or algebraic hashes like Rescue and Poseidon).

1. Algebraic Intermediate Representation (AIR):
2. Rather than R1CS circuits, STARKs express computations as Execution Traces (two-dimensional tables where each row represents a CPU state transition over time) governed by polynomial Transition Constraints and Boundary Constraints.

1. FRI Protocol (Fast Reed-Solomon Interactive Oracle Proof of Proximity):
2. To prove that the execution trace polynomial is low-degree without using elliptic curve pairings, STARKs utilize the FRI protocol.
3. FRI uses iterative folding algorithms: the prover repeatedly folds a polynomial of degree $d$ into a polynomial of degree $d\mathrm{/}2$ using random challenge scalars, committing to the intermediate evaluations in Merkle Trees.
4. After ${\log }_2(d)$ rounds, the polynomial is reduced to a constant, proving low-degree proximity using Merkle inclusion authentication paths.

1. Post-Quantum Cryptography:
2. Because STARKs rely exclusively on symmetric hash functions and information-theoretic polynomial commitments (rather than the discrete logarithm or elliptic curve pairing problems that can be solved by Shor's algorithm on a quantum computer), STARKs are inherently Quantum-Resistant.

The tradeoff: STARK proofs are significantly larger than SNARK proofs (typically 40 KB to 100 KB compared to 300 bytes), resulting in higher L1 on-chain verification gas costs unless proofs are recursively aggregated into an outer SNARK wrapper before settlement.

Deep Comparison Matrix: SNARKs vs. STARKs vs. Bulletproofs

Selecting the optimal zero-knowledge proving system requires analyzing the strict tradeoffs across proof size, prover memory, verification complexity, and cryptographic assumptions.

Modern zero-knowledge architectures frequently employ Hybrid Recursive Proof Pipelines: a high-throughput STARK or Plonky2 prover generates fast proofs for millions of execution steps off-chain, and an outer Groth16/PlonK wrapper compresses the STARK proof into a single 300-byte SNARK for ultra-cheap verification on Ethereum Layer-1.

Modern ZK Engineering Frontiers: Folding Schemes, Nova & ZK Coprocessors

The cutting edge of zero-knowledge research is moving beyond traditional monolithic circuits toward Incremental Verifiable Computation (IVC) and ZK Coprocessing:

1. Folding Schemes (Nova, SuperNova, HyperNova):
2. Traditional recursion requires verifying a full SNARK verifier circuit inside another SNARK circuit, incurring massive arithmetic overhead.
3. Nova introduced non-interactive folding: instead of proving each step, two R1CS instances are mathematically "folded" into a single relaxed R1CS instance of the same size using a simple random linear combination.
4. The heavy cryptographic proof is generated only once at the very end of millions of execution steps, reducing prover memory and overhead by up to $100\times$.

1. ZK Coprocessors (Axiom, Brevis, Herodotus):
2. Smart contracts on Ethereum cannot access historical blockchain state (older than 256 blocks) without incurring astronomical gas costs.
3. ZK Coprocessors allow smart contracts to query terabytes of historical L1/L2 data, execute complex quantitative calculations (such as calculating a user's 1-year average DeFi balance or credit score) off-chain, and return the verifiable cryptographic result with a SNARK validity proof directly into Solidity contract state in a single transaction.

## Frequently asked questions

Why do STARKs not require a trusted setup ceremony?

STARKs replace elliptic curve pairings with transparent collision-resistant hash functions and the FRI protocol, allowing all protocol randomness to be derived publicly via Fiat-Shamir without private toxic waste.

What is "toxic waste" in a ZK trusted setup?

Toxic waste refers to the secret random evaluation points (trapdoor values) generated during a multi-party setup. If malicious actors retain these values, they can forge false proofs that steal funds, though they cannot compromise privacy.

What is a ZK Coprocessor?

A ZK coprocessor allows smart contracts to trustlessly offload heavy historical data queries and complex computations to off-chain provers, verifying the final output on-chain with a succinct ZK proof.

Related reading

• zkEVM validity proof integration in rollups — See how ZK circuits are deployed in production Layer-2 rollup verification contracts.

## Sources

• On the Size of Pairing-based Non-interactive Arguments (Groth, 2016) — IACR ePrint
• PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge — IACR ePrint
• Scalable, transparent, and post-quantum secure computational integrity (STARKs) — IACR ePrint
• Bulletproofs: Short Proofs for Confidential Transactions and More — IACR ePrint

No contributor to this article holds a professional cryptography or security credential. Every technical claim above is sourced to primary protocol documentation rather than to personal authority — follow the sources and verify anything you intend to act on.

Not financial advice. Crypto assets are volatile and can lose value. This article describes how protocols work, not what you should buy.