SNARK vs. STARK

Start with the actual problem

Suppose Alice performs a computation and obtains a result.

Bob wants confidence that Alice really performed the computation correctly.

The obvious solution is for Bob to execute the program himself.

But that can be expensive when the computation is enormous.

A zero-knowledge proof system changes the problem:

The verifier checks the proof instead of repeating the entire computation.

SNARKs and STARKs are families of cryptographic proof systems that solve this general problem.

The shortest possible distinction

What do the words actually mean?

SNARK

Succinct means the proof can be much smaller than the computation being proved.

Non-interactive means the final proof can be verified without an ongoing back-and-forth conversation between prover and verifier. In practical constructions, Fiat–Shamir is often used to turn an interactive protocol into a non-interactive one.

Argument generally means computational soundness: a computationally bounded cheating prover should not be able to convince the verifier of a false statement except with negligible probability.

Knowledge means the proof is intended to demonstrate knowledge of a witness satisfying the statement, under the construction's precise knowledge assumptions.

STARK

Scalable refers to proof systems designed to handle very large computations efficiently, with prover complexity intended to scale well with computation size.

Transparent means the protocol does not require a secret toxic-waste setup parameter. Publicly specified randomness and hash functions can be used instead.

Where does zero knowledge enter?

Imagine the statement:

The prover wants to convince the verifier that such an x exists without revealing x.

We therefore distinguish:

A ZK proof aims to convince the verifier about correctness while revealing no additional useful information about the private witness beyond what is implied by the public statement.

Statement, witness, computation

Most modern proof systems can be viewed through the relation:

where:

The prover knows w and wants to prove:

For a computation, the relation can encode the fact that an execution trace, circuit witness, or other representation satisfies all required constraints.

First bridge: computation becomes constraints

Neither a SNARK nor a STARK directly proves an arbitrary program written in Rust or Python.

There is an intermediate mathematical representation.

For circuit-oriented systems, this might be R1CS or another circuit constraint system.

For STARK-style systems, this is commonly an execution trace plus AIR constraints.

SNARK path: R1CS as an example

Suppose:

We can create a witness vector:

An R1CS constraint can enforce:

For example:

which gives:

A complete circuit produces many such constraints.

STARK path: AIR as an example

A zkVM naturally produces a sequence of machine states:

These states form an execution trace.

AIR then describes the rules that every valid transition must satisfy.

For a toy register:

Boundary constraints specify where the computation starts or ends.

This trace-oriented structure is one reason STARKs fit naturally with zkVM architectures.

The common language: polynomials

Although SNARK and STARK constructions can look very different, polynomial algebra is central to many of them.

A polynomial is:

A proving system can transform computation into polynomial statements and then prove that those statements hold.

This is the deeper connection:

Polynomial commitments

Suppose the prover has a polynomial:

The verifier should be able to reason about this polynomial without receiving all of its coefficients.

A polynomial commitment provides a compact cryptographic commitment to f.

This is one of the most important architectural differences between many pairing-based SNARKs and STARKs.

KZG: the pairing-based path

Let the polynomial be:

Conceptually, a KZG commitment uses a secret setup value s and publishes group elements related to powers of it.

The commitment can then be formed conceptually as:

The verifier does not learn s. The cryptographic structure allows the verifier to check an evaluation proof using pairings.

What is the trusted setup?

A trusted setup is a protocol that generates public parameters containing secret randomness that must not remain known to an attacker.

For a simple conceptual setup:

If the toxic secret is destroyed correctly, users can safely use the public parameters.

The problem is not that every SNARK requires a trusted setup.

The accurate statement is:

Similarly, the STARK family is characterized by transparency and does not rely on a secret toxic-waste parameter in the same way.

FRI: the STARK path

FRI stands for Fast Reed–Solomon Interactive Oracle Proof of Proximity.

The high-level goal is to convince the verifier that a function represented by evaluations is close to a low-degree polynomial.

Conceptually:

At each stage, the prover commits to the relevant evaluations, and verifier challenges determine how the folding proceeds.

Fiat–Shamir can remove the need for an interactive verifier by deriving challenges from the transcript.

Why Merkle trees appear in STARKs

Suppose the prover has a huge list of field-element evaluations:

Hashing each value gives leaves of a Merkle tree.

The root is a compact commitment to the entire list.

Later, the prover can reveal selected values together with Merkle authentication paths.

The verifier checks that the revealed values belong to the committed dataset without downloading the entire list.

Transparency

Transparency means the verifier does not have to trust a secret setup contribution.

A STARK-style system can use publicly specified:

• finite fields;
• hash functions;
• evaluation domains;
• protocol parameters;
• Fiat–Shamir transcript rules.

There is no secret s that must be generated and destroyed as part of the core commitment mechanism.

Proof size

One of the most visible practical differences is proof size.

This creates a classic engineering trade-off:

Verification

The verifier should perform substantially less work than re-running the original computation.

For a pairing-based SNARK, verification may involve a small number of elliptic-curve operations and pairings, depending on the construction.

For a STARK, verification typically involves:

• hash computations;
• Merkle authentication checks;
• field arithmetic;
• FRI verification;
• constraint evaluations at queried points.

Both approaches aim for verification that is much cheaper than recomputing the full computation.

Prover cost

The prover is usually the party doing the expensive work.

A simplified picture is:

STARK provers often benefit from highly parallelizable operations such as:

• large-scale field arithmetic;
• FFT/NTT-like transforms;
• hashing;
• Merkle tree construction;
• FRI folding.

Pairing-based SNARK provers also perform substantial work, commonly involving multiscalar multiplication, polynomial operations, and commitment-specific computations.

Security assumptions

This is one of the most important differences.

Pairing-based SNARKs

Many pairing-based SNARKs rely on algebraic assumptions related to elliptic-curve groups and their discrete-logarithm-style hardness.

The exact assumption depends on the construction.

STARKs

STARKs primarily rely on collision resistance and related security properties of cryptographic hash functions, together with the soundness of the underlying algebraic proof protocol.

Post-quantum considerations

Many commonly used pairing-based SNARK constructions rely on elliptic-curve assumptions that are vulnerable to sufficiently powerful quantum computers using Shor's algorithm.

Hash-based STARK constructions do not rely on elliptic-curve discrete logarithms in the same way, so they are generally regarded as having a more direct path toward post-quantum security, with appropriate hash-function security margins.

This does not mean “STARKs are automatically post-quantum secure.” The concrete protocol and parameters still matter.

Recursion

A recursive proof verifies another proof inside a proof.

This is useful when a system wants to compress or aggregate many computations.

Recursion can be built for both SNARK and STARK families, but the engineering techniques differ.

Pairing-friendly curves can make some recursive SNARK constructions efficient. STARK systems can use their algebraic and hash-based structure to build recursive or proof-composition systems as well.

Aggregation

Suppose a blockchain has many transactions, each with a proof.

Instead of verifying every proof independently, a system may aggregate them into a smaller number of proofs.

This is important for rollups and scalable blockchain systems.

Not every SNARK is the same

This distinction matters when reading ZK papers.

The same computation through both lenses

Suppose we want to prove:

Circuit / R1CS style

Then convert those relationships into R1CS-style constraints.

Trace / AIR style

If this expression is part of a long-running machine execution, record the relevant machine state at each step and define transition constraints that describe how the state changes.

The two approaches prove the same logical statement, but organize the algebra differently.

SNARK vs STARK at a glance

Why are STARK proofs usually bigger?

A useful intuition is that STARKs expose more of the low-degree testing machinery to the verifier.

The proof may contain information associated with:

• Merkle roots;
• queried evaluation values;
• Merkle authentication paths;
• FRI commitments;
• FRI query responses;
• final low-degree information.

A pairing-based SNARK can compress a large amount of algebraic information into a small number of elliptic-curve group elements.

That is why comparing only proof size can be misleading: the systems make different cryptographic trade-offs.

Why can some SNARKs be so small?

Pairing-based constructions exploit algebraic structure in elliptic-curve groups.

A verifier can check a compact collection of group elements and pairing equations that encode the correctness of a much larger computation.

Conceptually:

The price is that the construction may depend on stronger algebraic assumptions and, for some schemes, trusted setup.

Rust: the difference at the representation level

// R1CS-style thinking:
// explicitly describe relationships among witness variables.

let witness = [1, x, y, z];

// x * y = z
let a = [0, 1, 0, 0];
let b = [0, 0, 1, 0];
let c = [0, 0, 0, 1];

// AIR-style thinking:
// record repeated machine states and constrain transitions.

let trace = [
    State { pc: 0, r0: 2, r1: 3, r2: 0 },
    State { pc: 4, r0: 2, r1: 3, r2: 5 },
];

// Conceptual transition:
// next.r2 = current.r0 + current.r1
// next.pc = current.pc + 4

The code is intentionally small. The real cryptographic machinery comes later: field elements, polynomial evaluation, commitments, transcript challenges, proof generation, and verification.

Why this matters for blockchains

A rollup may execute many transactions away from the base chain and then provide a proof that the resulting state transition is correct.

The base chain does not need to replay every computation if it can efficiently verify the proof.

This is one of the major reasons proof systems matter for blockchain scalability.

SNARKs and STARKs in zkVMs

A zkVM tries to prove ordinary machine execution.

The conceptual pipeline is:

For a trace-based STARK architecture:

A SNARK-based zkVM may instead transform the machine execution into a circuit or another arithmetization:

The same high-level objective can therefore be achieved using substantially different proving architectures.

The real engineering trade-off

Common misconceptions

Put everything together

Typical pairing-based SNARK-style mental model

Typical STARK-style mental model

These are mental models, not universal blueprints. Modern systems often combine ideas from multiple proof-system families.

Interview-level questions you should be able to answer

The whole idea in one map

If you remember only one sentence, remember this: SNARKs and STARKs are both ways to prove large computations succinctly, but common SNARK constructions achieve compact proofs through strong algebraic cryptography, while STARKs use transparent, hash-based polynomial proof machinery that is especially natural for large execution traces.