Zero-Knowledge Cryptography: Mathematical Foundations of zk-SNARKs & zk-STARKs

The Pipeline of Arithmetization: Computation to R1CS to QAP

To generate a cryptographic zero-knowledge proof for an arbitrary computation (e.g., verifying a hash function or executing an EVM smart contract), the computation must first be translated from standard imperative code into an algebraic representation over a prime finite field ${\mathbb{F}}_p$. This multi-stage compilation process is known as Arithmetization.

The classical zk-SNARK pipeline proceeds through four distinct stages:

1. Computation Code: Written in high-level DSLs like Circom, Noir, or Cairo.
2. Arithmetic Circuit: Decomposed into a Directed Acyclic Graph (DAG) of basic addition ($+$) and multiplication ($\times$) gates over finite field ${\mathbb{F}}_p$.
3. Rank-1 Constraint System (R1CS): Formatted into a system of quadratic equations. An R1CS consists of three vector sets $A,B,C$ such that for a complete assignment vector $s$ (containing 1, the public inputs, and the private witness):

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

where $\circ$ represents the Hadamard (entry-wise) vector product.

1. Quadratic Arithmetic Program (QAP): To evaluate thousands of R1CS constraints simultaneously, the vectors are interpolated via Lagrange polynomials into continuous polynomials $A(x),B(x),C(x)$ defined over a target domain. The relation holds if and only if the polynomial:

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

is evenly divisible by the target vanishing polynomial $T(x)={\prod }_{i=1}^m(x-r_i)$, meaning there exists a quotient polynomial $H(x)$ such that:

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

By evaluating this polynomial identity at a secret random challenge point $\tau$ using homomorphic elliptic curve encryption, the verifier checks millions of constraints in a single pairing operation.

Groth16 vs. PLONK: Trusted Setups vs. Universal Structured Reference Strings

The practical evolution of zk-SNARKs has centered on reducing setup complexity and improving prover efficiency:

Groth16 (2016):

• Proof Size: Exceptionally small (exactly 3 group elements: 2 in $G_1$, 1 in $G_2$ = 128 bytes).
• Verification Time: Extremely fast (~3ms, requiring only 3 pairing checks on BN254 curves).
• Critical Limitation: Circuit-Specific Trusted Setup. Every individual circuit requires its own dedicated multi-party ceremony (toxic waste generation). Changing a single line of circuit code invalidates the ceremony and requires a new global setup.

PLONK (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge, 2019):

• Universal & Updatable SRS: PLONK uses a single universal trusted setup (such as the Ethereum KZG ceremony) up to a maximum degree bound $N$. Any circuit of size $<N$ can be compiled and proved without new ceremonies.
• Permutation Arguments: Uses grand product polynomials based on copy constraints to enforce that wires connecting different arithmetic gates share identical field values.
• Polynomial Commitments (KZG): Replaces complex QAPs with Kate-Zaverucha-Goldberg (KZG) polynomial commitments, allowing a prover to commit to a polynomial $f(x)$ with a single 32-byte group element and prove $f(z)=y$ with a constant-sized evaluation proof.

## zk-STARKs & The FRI Protocol: Transparent, Quantum-Resistant Verification

zk-STARKs (Zero-Knowledge Scalable Transparent ARguments of Knowledge), pioneered by Eli Ben-Sasson et al., eliminate the trusted setup requirement entirely while introducing quantum resistance.

Key architectural distinctions of zk-STARKs:

1. Transparency: STARKs use pure public randomness (via the Fiat-Shamir heuristic over cryptographic hash functions like Rescue, Poseidon, or BLAKE3), requiring zero trusted ceremonies or toxic waste parameters.
2. Algebraic Intermediate Representation (AIR): Computations are structured as an execution trace matrix where constraints enforce valid state transitions between consecutive execution rows.
3. FRI Protocol (Fast Reed-Solomon Interactive Oracle Proof of Proximity): To prove that the execution trace polynomials have low degree without relying on elliptic curve pairings or discrete logarithm hardness, STARKs use the FRI protocol. FRI recursively folds a polynomial of degree $<d$ into polynomials of degree $<d\mathrm{/}2$, bounding degree growth using Merkle tree root commitments and opening queries.
4. Quantum Resistance: Because STARKs rely exclusively on collision-resistant hash functions rather than elliptic curves, they are inherently immune to Shor's quantum algorithm.

While STARK proofs are significantly larger than SNARK proofs (typically 40 KB to 100 KB compared to Groth16's 128 bytes), recursive STARK-to-SNARK wrappers allow systems like Polygon zkEVM, Starknet, and zkSync to generate fast STARK execution proofs and wrap them in a compact final SNARK for cheap Layer-1 EVM verification.

Recursive SNARKs, Folding Schemes & IVC (Nova / SuperNova)

A monumental advancement in practical zero-knowledge systems is Incrementally Verifiable Computation (IVC) and folding schemes like Nova, Sangria, and HyperNova.

In classical proof recursion, verifying a SNARK inside another SNARK requires encoding the entire elliptic curve pairing check or polynomial verification circuit inside the prover's arithmetic constraints. This introduces millions of additional R1CS gates, consuming immense memory and CPU time.

Folding schemes eliminate recursive proof generation overhead through non-interactive folding:

• Relaxed R1CS: Nova introduces a relaxed R1CS representation with an error slack vector $E$ and a scalar multiplier $u$.
• Constant-Size Folding Step: Instead of fully verifying a proof at every step of a computation loop (e.g., each EVM opcode execution in a zkEVM), the prover merely folds two relaxed R1CS instances into a single combined instance using a random challenge scalar $r$:

$$s_{\text{folded}}=s_1+r\cdot s_2,E_{\text{folded}}=E_1+r\cdot T+r^2\cdot E_2$$

• Deferred Verification: The expensive cryptographic proof is generated only once at the very end of millions of computational steps, verifying the single folded accumulator.

This innovation reduces prover memory requirements by $10\times$ to $50\times$, enabling zero-knowledge proof generation on mobile devices, consumer laptops, and web browsers.

Hardware Acceleration & The Future of ZK Prover Networks

As zero-knowledge rollups and zk-bridges scale to process millions of transactions per second, proof generation speed has become the primary operational bottleneck. The two most computationally intensive subroutines in modern ZK provers are:

1. Multi-Scalar Multiplication (MSM): Computing ${\sum }_{i=1}^N{s}_i{P}_i$ over elliptic curves. MSM accounts for $60\mathrm{\%}$ to $80\mathrm{\%}$ of prover time in SNARKs and is bounded by memory bandwidth.
2. Number Theoretic Transforms (NTT): Fast Fourier Transforms over finite fields used for polynomial multiplication, accounting for $20\mathrm{\%}$ to $30\mathrm{\%}$ of execution time.

To achieve real-time sub-second block proving, the blockchain industry is transitioning to specialized hardware acceleration:

• GPU Acceleration (CUDA / Metal): Frameworks like ICICLE leverage massive parallel GPU cores to accelerate MSM and NTT operations by $20\times$ over standard multi-core CPUs.
• FPGA & ASIC Provers: Custom silicon chips purpose-built for finite field arithmetic pipelines process zero-knowledge proofs with ultra-low thermal dissipation and millisecond latency.
• Decentralized Prover Markets: Protocols like Succinct, Gevulot, and Boundless create decentralized auction markets where rollups outsource proof generation to global competitive clusters of hardware provers, driving proving costs down to fractions of a cent per transaction.

## Frequently asked questions

What is the "toxic waste" in a zk-SNARK trusted setup?

Toxic waste refers to the secret random scalars (tau, alpha, beta) generated during the CRS setup ceremony. If not securely destroyed by participants, anyone possessing them can forge false proofs.

Why are zk-STARKs considered quantum-resistant while zk-SNARKs are not?

ZK-SNARKs rely on the discrete logarithm problem over elliptic curves (which Shor's quantum algorithm breaks). STARKs rely only on cryptographic hash functions and Merkle trees, which are quantum-safe.

What does "Succinctness" mean in zk-SNARKs?

Succinctness means that the proof size is tiny (a few hundred bytes) and verification takes milliseconds (O(1) complexity), regardless of how massive or complex the original computation was.

Related reading

• elliptic curve discrete logarithm hardness — Review the underlying elliptic curve point arithmetic required for Groth16 and KZG commitments.

## Sources

• On the Size of Pairing-based Non-interactive Arguments (Groth, 2016) — IACR ePrint
• Scalable, transparent, and post-quantum secure computational integrity (STARKs) — IACR ePrint
• PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge — 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.