Skip to content
Blockchain LabTHE VENTURE STUDIO

LibraryScaling2018Design paperCorpus record

Scalable, transparent, and post-quantum secure computational integrity

StarkWare. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev.

The STARK paper: proofs of computational integrity that are succinct, do not need a trusted setup, and are argued to resist quantum attackers on the underlying hashes. StarkWare's later systems, including StarkEx and Starknet, are built on this proof system. They are not identical to it.

The StarkWare paper shows a proof of computational integrity that is succinct, needs no trusted setup, and is argued to stay sound against quantum adversaries, so a chain can check a large computation by checking a small proof.

The five-minute read

Integrity, not secrecy, is the headline

The proof shows that a computation was done correctly. It does not, by itself, hide the inputs. Zero-knowledge is a further property. Do not assume it.

No toxic waste

Unlike a structured SNARK setup, the paper's STARK construction is transparent. There is no ceremony whose secret must be destroyed. That is the deployment claim.

The proof is exponentially smaller than the trace

A verifier reads a short proof and queries a few spots, instead of replaying every step. The asymptotics are the result. Concrete sizes in 2018 are not today's prover benchmarks.

Post-quantum is a hash-based argument

Security rests on hash functions and information theory, not on elliptic-curve pairings. That is why the paper can talk about quantum adversaries. The claim is only as strong as the hashes.

A proof needs a machine to be about

Later Cairo and similar machines exist so programmers can target the proof system. The 2018 paper is the integrity argument. It is not a language manual.

One action, walked through

  1. A prover executes a computation and records an execution trace.
  2. The trace is encoded so that a correct execution satisfies a low-degree constraint.
  3. The prover commits to that encoding, typically with a Merkle tree over a Reed-Solomon codeword.
  4. The verifier asks for a few openings. The prover supplies the leaves and the paths.
  5. If the openings fit the constraint, the verifier accepts. Replaying the original computation is not required.

The argument, unpacked

Transparency changes who can deploy

A proof system with a setup asks the user to trust a ceremony. A transparent system asks the user to trust the maths and the hash. That is a smaller social problem and a still-real cryptographic problem. The paper's advantage is the disappearance of the ceremony, not the disappearance of assumptions.

Scalability is on the verifier's side

Proving is heavy. Verification is light. A chain that verifies STARKs is doing the cheap half. The expensive half sits with a prover who must be paid. Designs that ignore prover cost will not ship the throughput the verifier math suggests.

Integrity of the wrong programme is still integrity

The proof says the trace matched a constraint. If the constraint does not encode the contract you think it does, the proof is a correct execution of the wrong rules. Specification of the machine is part of the user's audit.

What has to be true

  • The hash used for commitments is collision-resistant in the model the proof uses.
  • The verifier's queries are unpredictable to a cheating prover.
  • Someone will pay the proving cost at the volume the application needs.
  • The constraint system matches the intended programme. The proof will not catch a specification error.

What happened after the paper

StarkWare used this line of work in StarkEx and Starknet, with the Cairo machine as the programming layer. Prover performance moved a long way after 2018. The paper's durable claims are transparency, succinct verification, and the stated post-quantum posture, not a transactions-per-second figure.

What to check before you use the idea

  • Is there a trusted setup for this proof, or is it the transparent construction?
  • Does the proof hide inputs, or only show correct execution?
  • Who pays the prover, and what is that cost relative to verification?
  • Which machine's constraints are being proved?

Terms

Computational integrity
A proof that a stated computation ran correctly, which is separate from hiding the data.
Transparent setup
Public randomness only. No secret parameters that must be destroyed.
STARK
A scalable transparent argument of knowledge, built in this paper on hashes and low-degree tests.
Execution trace
The step-by-step record the prover commits to, which a correct programme must satisfy.

The problem the paper names

Many succinct proofs require a structured setup whose toxic waste must be destroyed. STARKs aim at a proof that is only as trusted as public randomness and a hash function, and that stays small relative to the computation.

What the design proposes

  • An algebraic intermediate representation of a computation is proved by an interactive oracle proof, then made non-interactive.
  • Transparency means the randomness is public. There is no structured reference string in the construction.
  • Post-quantum security is argued from hash-based assumptions, not from elliptic-curve pairings.

How the mechanism is specified

  • The prover commits to an execution trace. The verifier queries a small number of positions.
  • Proof size and prover cost are the engineering trade the paper quantifies for its construction, not for a particular L2 today.
  • A proof shows the trace satisfied the constraints that were encoded. Encoding the wrong program yields a valid proof of the wrong thing.

What this page does not treat as proven

  • This paper is not the Starknet documentation, the Cairo language spec, or a token paper.
  • Transparent does not mean trustless in the casual sense. Verifiers still trust the hash and the circuit.
  • We do not repeat the paper's performance tables as current product metrics.

Why a venture studio still reads it

When a venture says 'zk' , ask whether there is a setup ceremony and what the proof actually constrains. STARKs are the citation for the transparent, hash-based branch of that answer.

This is Blockchain Lab's reading of a public design paper. It is not the paper, not a copy of it, and not an offer of tokens, equity, custody or a partnership. Later network behaviour can diverge from the text. Nothing here is investment, legal or technical advice.

Research status: Design paper. Last reviewed: 1 October 2026. This is a reading of a public paper, not investment, legal or security advice.