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.
- Evidence
- Primary paper
- Re-measured
- No
- Assumptions
- 4
- Records linked
- 7
Code
Source, repository, and what is actually hosted
- IACR ePrint 2018/046https://eprint.iacr.org/2018/046.pdf
- The source URL is not a GitHub repository. No code remote is invented.
- Full text is not mirrored. Public availability is not a licence to copy the file onto this site.
- Add to a reading list
01 Claim ledger
What the paper is allowed to say
Each row is a sentence already in the study. The status is the same on every row: a model claim, not a live measurement.
Claim 01 · Paper model
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.
Claim 02 · Paper model
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.
Claim 03 · Paper model
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.
Claim 04 · Paper model
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.
Claim 05 · Paper model
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.
02 Three cuts
Observation, model, falsifier
A desk does not stop at the summary. Each claim is cut three ways, using only this study's own assumptions and checks. Nothing here is a new figure.
01 Integrity, not secrecy, is the headline
Observation
What the study says
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.
Model
What has to hold
The hash used for commitments is collision-resistant in the model the proof uses.
Falsifier
What would retire it
Does the proof hide inputs, or only show correct execution?
02 No toxic waste
Observation
What the study says
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.
Model
What has to hold
The verifier's queries are unpredictable to a cheating prover.
Falsifier
What would retire it
Is there a trusted setup for this proof, or is it the transparent construction?
03 The proof is exponentially smaller than the trace
Observation
What the study says
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.
Model
What has to hold
The verifier's queries are unpredictable to a cheating prover.
Falsifier
What would retire it
Is there a trusted setup for this proof, or is it the transparent construction?
04 Post-quantum is a hash-based argument
Observation
What the study says
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.
Model
What has to hold
The constraint system matches the intended programme. The proof will not catch a specification error.
Falsifier
What would retire it
Which machine's constraints are being proved?
05 A proof needs a machine to be about
Observation
What the study says
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.
Model
What has to hold
The constraint system matches the intended programme. The proof will not catch a specification error.
Falsifier
What would retire it
Is there a trusted setup for this proof, or is it the transparent construction?
03 Sequence
One action, as an operating tape
- 01A prover executes a computation and records an execution trace.
- 02The trace is encoded so that a correct execution satisfies a low-degree constraint.
- 03The prover commits to that encoding, typically with a Merkle tree over a Reed-Solomon codeword.
- 04The verifier asks for a few openings. The prover supplies the leaves and the paths.
- 05If the openings fit the constraint, the verifier accepts. Replaying the original computation is not required.
04 Load-bearing
The argument, and where a pitch drops it
Transparency changes who can deploy
The cut
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.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
Transparent does not mean trustless in the casual sense. Verifiers still trust the hash and the circuit.
Scalability is on the verifier's side
The cut
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.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
A later client, parameter or reward formula is a different object from this paragraph.
Integrity of the wrong programme is still integrity
The cut
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.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
A later client, parameter or reward formula is a different object from this paragraph.
05 Register
What has to be true
Cryptography · Not re-measured
The hash used for commitments is collision-resistant in the model the proof uses.
Model · Not re-measured
The verifier's queries are unpredictable to a cheating prover.
Model · Not re-measured
Someone will pay the proving cost at the volume the application needs.
Cryptography · Not re-measured
The constraint system matches the intended programme. The proof will not catch a specification error.
06 Divergence
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.
A later client, parameter set, or reward formula is a different object. Cite this paper for the mechanism. Cite a primary release for the network. This desk has not re-run the proof.
07 Pre-mortem
What to check before you use the idea
- 0 of 4 marked on this browser. A mark is a reading note, not a pass, a rating, or a recommendation.
08 Anatomy
The paper, in the order a builder needs
The problem it 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
Why the desk 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.
09 Lexicon
Terms, opened into the record
- 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.
10 Repository
Every linked record on this page
Underlined words open a page that already exists: a concept, a protocol profile, a failure record, or another paper. If a word is not underlined, this desk does not have a record for it.
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.