Skip to content
Blockchain LabBlockchain LabTHE VENTURE STUDIO

LibraryScaling2021Design paperCorpus record

Cairo – a Turing-complete STARK-friendly CPU architecture

Cairo. Lior Goldberg, Shahar Papini and Michael Riabzev.

A CPU whose every instruction was chosen so that a STARK can prove 'this program ran'. You write a program instead of a new set of polynomial equations for each statement. The paper is the machine, not a network's throughput.

Cairo is a machine built so that one STARK can prove a program ran. Instead of writing polynomial constraints for every application, a developer writes a program for this CPU, and the same constraint system checks every instruction. The paper is the architecture. It is not a rollup and not a throughput claim.
Evidence
Primary paper
Re-measured
No
Assumptions
4
Records linked
3

Code

Source, repository, and what is actually hosted

  • ePrint 2021/1063https://eprint.iacr.org/2021/1063
  • 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.

  1. Claim 01 · Paper model

    One constraint system

    The machine's transition is fixed. Each application is a program in memory, not a new set of equations. That is the engineering move.

  2. Claim 02 · Paper model

    The trace is the witness

    A proof attests that a table of machine states is a valid execution. The verifier does not re-execute the program instruction by instruction.

  3. Claim 03 · Paper model

    STARK-friendly is concrete

    The instruction set is chosen for the field arithmetic STARKs want. 'Friendly' is not a general compliment. A different proof system might want a different machine.

  4. Claim 04 · Paper model

    Turing-complete is not cheap

    The machine can express general programs. The prover's cost still follows the length of the trace. A loop can be a very large proof.

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.

  1. 01 One constraint system

    Observation

    What the study says

    The machine's transition is fixed. Each application is a program in memory, not a new set of equations. That is the engineering move.

    Model

    What has to hold

    The STARK proof system is the one the constraints were written for.

    Falsifier

    What would retire it

    Is the proof a STARK of this machine, or a different proof system?

  2. 02 The trace is the witness

    Observation

    What the study says

    A proof attests that a table of machine states is a valid execution. The verifier does not re-execute the program instruction by instruction.

    Model

    What has to hold

    Memory consistency is part of the proof. A trace that skips it is not a Cairo execution.

    Falsifier

    What would retire it

    Is the proof a STARK of this machine, or a different proof system?

  3. 03 STARK-friendly is concrete

    Observation

    What the study says

    The instruction set is chosen for the field arithmetic STARKs want. 'Friendly' is not a general compliment. A different proof system might want a different machine.

    Model

    What has to hold

    The STARK proof system is the one the constraints were written for.

    Falsifier

    What would retire it

    Is the proof a STARK of this machine, or a different proof system?

  4. 04 Turing-complete is not cheap

    Observation

    What the study says

    The machine can express general programs. The prover's cost still follows the length of the trace. A loop can be a very large proof.

    Model

    What has to hold

    Memory consistency is part of the proof. A trace that skips it is not a Cairo execution.

    Falsifier

    What would retire it

    Is the proof a STARK of this machine, or a different proof system?

03 Sequence

One action, as an operating tape

  1. 01A program is written against the Cairo instruction set.
  2. 02An execution produces a trace of register and memory states.
  3. 03The STARK proves the trace obeys the transition constraints and that memory is consistent.
  4. 04A verifier checks the proof and the public outputs.
  5. 05Inputs that were not public are not part of what the verifier learned, unless the program made them public.

04 Load-bearing

The argument, and where a pitch drops it

  1. The machine is not the system

    The cut

    A chain that 'uses Cairo' still has to say what program is proved, who posts the proof, what data the program read, and what happens if the proof is absent. Those are system questions. The CPU paper is silent on them.

    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

    The paper does not establish the security of a particular proving stack or a particular chain.

  2. Later Cairos are later machines

    The cut

    If the instruction set or the constraint system changed, the 2021 theorems do not automatically move. Cite the version.

    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 STARK proof system is the one the constraints were written for.

  • Model · Not re-measured

    The verifier checks public outputs against the claim the application actually cares about.

  • Cryptography · Not re-measured

    Memory consistency is part of the proof. A trace that skips it is not a Cairo execution.

  • Model · Not re-measured

    Prover performance in a marketing line is not a result in this paper.

06 Divergence

What happened after the paper

Cairo is the right citation when a stack says programmers write code and a STARK proves it, rather than writing circuits by hand. STARKs themselves are a different paper. So is any particular rollup built on top.

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

  5. 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

STARK statements want polynomial constraints. Hand-writing those constraints for each application does not scale to general programs. Cairo fixes one instruction set and one constraint system, then compiles programs into it.

What the design proposes

  • A read-only memory of instructions and a mutable memory of values.
  • A single transition constraint that every pair of consecutive machine states must satisfy.
  • A proof that the execution trace of that machine is valid, produced as a STARK.

How the mechanism is specified

  • The verifier checks the STARK, not the program, step by step. That is the succinctness.
  • Turing-complete here means the machine can express general programs. It does not mean the proof is cheap for every program.
  • The constraint system is specific to this architecture. A later Cairo is a later machine if the constraints changed.

What this page does not treat as proven

  • A proof of execution is not a consensus protocol and not data availability.
  • The paper does not establish the security of a particular proving stack or a particular chain.
  • Friendly to STARKs is an engineering claim about field arithmetic. It is not a claim that proving is free.

Why the desk still reads it

Ask what was proved: one execution of one program on this machine. Then ask who supplies the inputs, and where the public output is checked. The CPU paper does not answer the surrounding system.

09 Lexicon

Terms, opened into the record

Execution trace
The table of machine states whose validity the STARK attests.
Transition constraint
The fixed equation every pair of consecutive Cairo states 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.