Zero-Knowledge Proofs — Deep Dive

Starting From First Principles

Before ZKPs, cryptographic proofs were blunt instruments. You prove knowledge of a secret key by signing a challenge — but that signature reveals information about the key. You prove ownership of data by hashing it — but the hash reveals nothing to anyone, including the verifier.

The question Shafi Goldwasser, Silvio Micali, and Charles Rackoff asked in their 1985 paper was sharper: can you prove a computational statement — “I know x such that f(x) = y” — without revealing x?

Their answer was yes, with an interactive protocol, and it sparked 40 years of work that’s now deployed at billion-dollar scale.

The Quadratic Arithmetic Program

Modern zk-SNARKs start by converting a computational problem into an algebraic form. Here’s how.

Take any computation you want to prove. Call it a circuit — a DAG of addition and multiplication gates over a finite field. You want to prove you know inputs that produce a specific output, without revealing those inputs.

Step 1: R1CS (Rank-1 Constraint System)

Every gate in your circuit becomes a constraint of the form:

(a · w) * (b · w) = (c · w)

where w is a vector of all wire values in the circuit and a, b, c are selector vectors. A satisfying assignment to the circuit corresponds to a witness vector w that satisfies all R1CS constraints simultaneously.

Step 2: QAP (Quadratic Arithmetic Program)

The R1CS is then converted into polynomial form. Each constraint becomes a relation between polynomials evaluated at specific points. A valid witness corresponds to a polynomial h(x) such that:

A(x) · B(x) - C(x) = h(x) · Z(x)

where Z(x) is the “vanishing polynomial” for the evaluation domain, and A, B, C are target polynomials encoding the constraints.

The prover must demonstrate they know polynomials satisfying this relation — without revealing the polynomials themselves.

Step 3: Polynomial Commitments

This is where elliptic curve cryptography comes in. The prover commits to polynomials using a polynomial commitment scheme — typically based on pairing-friendly elliptic curves (BN254 for Groth16, BLS12-381 for more recent systems).

A commitment [f] to polynomial f is computed as:

[f] = f(τ) · G

where G is a generator of an elliptic curve group and τ is a secret (the “toxic waste” from the trusted setup — more on this shortly). The discrete log problem ensures you can’t recover τ from [f].

The pairing function e(P, Q) then lets the verifier check polynomial relations without knowing the polynomials:

e([A], [B]) = e([C], [1]) · e([h], [Z])

The proof is just a few elliptic curve points — typically 128-256 bytes for Groth16. Verification is O(1) regardless of circuit size: just a handful of pairing operations. This is why SNARKs are called “succinct.”

The Trusted Setup Problem

To compute the [f] = f(τ) · G commitments, someone has to pick τ. But they can’t keep it — if they do, they can forge proofs for false statements.

The solution is a multi-party computation ceremony. Multiple participants each contribute randomness, and the final parameters are the combination of all contributions. As long as at least one participant honestly destroys their piece, τ is unknown to everyone.

Zcash’s first “Powers of Tau” ceremony in 2016 had 6 participants. Their second ceremony in 2017-2018 had 90. Ethereum’s KZG ceremony in 2022-2023 had 141,416 participants — probably the largest cryptographic ceremony ever run.

The attack surface is real. In 2016, a Zcash researcher described the failure mode: “If I had kept my toxic waste, I could have created Zcash out of thin air.” Whether anyone actually did this with early Zcash is unknowable — that’s the uncomfortable property of the trusted setup.

zk-STARKs: The Alternative Architecture

StarkWare’s zk-STARKs avoid the trusted setup entirely, at the cost of larger proofs.

Instead of elliptic curve pairings, STARKs use hash functions and FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity).

The computation is arithmetized into a polynomial over a large prime field. The prover commits to evaluations of this polynomial using a Merkle tree (hash-based). The FRI protocol then proves, through a series of recursive “folding” steps, that a committed polynomial is “close” to a polynomial of low degree — which is equivalent to proving the computation was done correctly.

Proof size grows logarithmically with circuit complexity (O(log² n) vs O(1) for SNARKs), but the underlying assumption is just collision-resistant hash functions — the same assumption behind Bitcoin’s proof-of-work. No trusted setup, no exotic cryptographic assumptions.

A StarkNet transaction proof on Ethereum in early 2024 was about 45 KB. A Groth16 SNARK proof is 192 bytes. That’s the tradeoff.

Recursive Proofs: Proving Proofs

One of the weirder things you can do with ZKPs is prove that a proof was correctly verified.

If you can write a ZK circuit for “verification of a ZK proof,” you can chain proofs together. Prove you proved you proved something. This lets you:

• Accumulate proofs: Build a proof that 1 million transactions were valid by folding them recursively. The final proof is still tiny.
• Parallelize proving: Split a large circuit into chunks, prove each chunk in parallel, then aggregate with a recursive proof.
• Incrementally verifiable computation: Maintain a running proof that a long-running computation is correct at any point in time.

Halo2 (used by Zcash’s Orchard protocol and Scroll’s zkEVM) pioneered this in 2020. Nova (2021) simplified the construction dramatically. Hypernova extended it to folding schemes. This is the current research frontier, and the reason zkEVM projects went from “theoretically possible” to “in production” between 2021 and 2024.

zkEVM: Proving the Ethereum Virtual Machine

The most ambitious near-term application: prove that every Ethereum transaction in a block was executed correctly.

The EVM was not designed with ZK proving in mind. Instructions like KECCAK256 (the hash function) require enormous circuits — keccak alone takes ~150,000 constraints per hash. A single complex Ethereum transaction might require millions of constraints.

Different teams took different approaches to this:

Project	Approach	Proving time (2024)	EVM compatibility
zkSync Era	Custom zkEVM (Type 4)	~1 min per block	Solidity-compatible, not EVM-bytecode
StarkNet	Cairo VM (not EVM)	~10 min per block	Custom language
Scroll	Type 2 zkEVM	~5 min per block	Full EVM bytecode
Polygon zkEVM	Type 2 zkEVM	~3 min per block	Full EVM bytecode
Taiko	Type 1 zkEVM	~10 min per block	Identical to Ethereum

Type 1 (identical to Ethereum) is the holy grail — it means any Ethereum tooling works unchanged. Taiko achieved this in 2024, at the cost of slower proving times. Hardware acceleration (GPUs, FPGAs, and purpose-built ZK ASICs from companies like Cysic and Ingonyama) is the active battleground to make proving fast enough to matter.

Practical Code: What a Circom Circuit Looks Like

Circom is the most widely used ZK circuit language. Here’s a simple example — proving you know a pre-image of a Poseidon hash (Poseidon is a ZK-friendly hash, unlike keccak):

pragma circom 2.0.0;

include "node_modules/circomlib/circuits/poseidon.circom";

template HashPreimage() {
    signal input preimage;      // private input (the secret)
    signal input hash;          // public input (the hash)
    
    component hasher = Poseidon(1);
    hasher.inputs[0] <== preimage;
    
    // Constraint: hasher output must equal the public hash
    hasher.out === hash;
}

component main {public [hash]} = HashPreimage();

You compile this to R1CS, generate a proving key (with trusted setup), and then:

# Generate witness (knows preimage = 42, hash = Poseidon(42))
node generate_witness.js circuit.wasm input.json witness.wtns

# Create proof
snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json

# Verify
snarkjs groth16 verify verification_key.json public.json proof.json
# Output: OK

The proof.json is 3 elliptic curve points (192 bytes). Anyone with verification_key.json can verify you know a preimage of that hash — and the verification reveals nothing about the preimage.

The Quantum Threat

SNARKs based on elliptic curve pairings are broken by quantum computers (Shor’s algorithm). STARKs, being hash-based, are considered quantum-resistant (Grover’s algorithm offers only a quadratic speedup against hash functions, manageable by doubling hash sizes).

No cryptographically relevant quantum computer exists today, but NIST finalized its first post-quantum cryptography standards in 2024. The ZKP community is watching closely — migrating SNARK-based systems would require replacing the entire trusted setup and proof system infrastructure.

One Thing to Remember

The key insight of zero-knowledge proofs is that “knowing something” and “revealing something” are separable. Modern ZKP systems convert computation into polynomials, commit to those polynomials using elliptic curves or hash functions, and let a verifier check algebraic relations without seeing the values. The cost is computational: proving is expensive (seconds to minutes), even if verification is cheap (milliseconds). As hardware catches up, the tradeoff increasingly favors deploying ZKPs widely — and the identity/privacy applications are arguably more important than the blockchain ones.