Skip to content
Blockchain 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.

The five-minute read

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.

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.

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.

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.

One action, walked through

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

The argument, unpacked

The machine is not the system

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.

Later Cairos are later machines

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

What has to be true

  • The STARK proof system is the one the constraints were written for.
  • The verifier checks public outputs against the claim the application actually cares about.
  • Memory consistency is part of the proof. A trace that skips it is not a Cairo execution.
  • Prover performance in a marketing line is not a result in this paper.

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.

What to check before you use the idea

  • What program, and which public outputs?
  • Is the proof a STARK of this machine, or a different proof system?
  • Where does the program read its inputs?
  • Which Cairo version is the constraint set?

Terms

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.

The problem the paper 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 a venture studio 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.

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.