Cairo: A Turing-Complete STARK-Friendly CPU Architecture

Cairo – a Turing-complete STARK-friendly CPU architecture describes a virtual CPU whose executions can be checked through polynomial constraints. Published by Lior Goldberg, Shahar Papini, and Michael Riabzev in 2021, it gives developers a reusable programming model for computations intended for proof systems such as ZK-STARKs. Its central contribution is the CPU architecture and its constraint system. STARKs could already express general computations before Cairo. [1, 2]

Paper Details

Paper	Cairo – a Turing-complete STARK-friendly CPU architecture
Authors	Lior Goldberg, Shahar Papini, Michael Riabzev
Organization	StarkWare
Original publication	August 2021; IACR received the preprint on August 16, 2021
Archive revision	February 6, 2025; the record notes a new appendix on running untrusted code
Document type	CPU architecture and cryptographic computation research preprint
Paper license	Creative Commons Attribution 4.0 International, as linked in the IACR record
Software license	The cited Cairo software repository uses Apache License 2.0

This summary examines the original August 2021 architecture using the official Starknet-hosted PDF. The later Sierra section uses current Cairo documentation. It does not summarize the additions in the revised 2025 PDF. The paper and software licenses apply to different materials. [1, 2, 6, 7]

Why a Reusable CPU Helps

A proof system needs a mathematical statement describing a valid computation. One approach is to design an algebraic intermediate representation (AIR) specifically for an application. Cairo instead defines constraints for a small CPU. Different programs run on that CPU, letting the same architecture describe many computations without designing an entirely new AIR for each program. [2]

The execution is represented by a trace: values describing successive machine states. Polynomial constraints check whether those states obey the instruction set and memory rules. The program and relevant input/output information must also be bound to the statement being proved. Reusing a CPU offers a practical programming interface; it does not guarantee that every application will be faster than a specialized constraint system. [2, 3]

Instructions, Registers, and Memory

The original CPU works with field elements and a compact instruction set. Its three registers are the program counter (pc), allocation pointer (ap), and frame pointer (fp). The program counter selects an instruction; the other two support memory allocation conventions and function frames. Ordinary computation values reside in memory. [2]

Field arithmetic differs from unrestricted integer arithmetic. When an application needs bounded integers, comparisons, or a particular range, its constraints must express those requirements. A field multiplication alone does not establish all the properties a programmer might associate with multiplying ordinary integers. [2]

Cairo’s model is nondeterministic read-only memory: the prover supplies an assignment of memory values, and the constraints require consistent use of each address. A useful programming intuition is writing a cell once and then reading it. The allocation pointer is a convention for organizing cells, rather than a universal guarantee that an address has never been used. [2]

This memory model does not make application state permanently unchangeable. A program can represent later values in new cells, and Starknet storage can change between executions. The restriction concerns the memory assignment within a proved execution. [2, 3]

Hints and Builtins

A hint performs extra work outside the proved instruction trace and supplies values used by the program. It can find a candidate answer cheaply, leaving the Cairo instructions to check the required relationship. The verifier does not establish that the hint’s implementation ran correctly merely because the surrounding Cairo program has a proof. [2, 4]

For example, a hint could supply y and the program could check y² = x. That check allows both roots where they exist. If the application requires a particular root or another property, it needs additional constraints. This is a concrete source of underconstrained-program bugs. [2, 4]

Builtins have a different role: they add dedicated constraints for operations accessed through designated memory regions. The original paper includes range checking and Pedersen hashing among its examples. A proof layout must support the builtins the program uses. Hints supply witness values; builtins supply additional rules that the proof must satisfy. [2]

From Source Code to a Verified Statement

Compile: translate the program into instructions for the Cairo machine.
Run: execute the instructions and required hints to construct a trace and memory assignment.
Prove: use that witness and the applicable constraints to generate a cryptographic proof.
Verify: check the proof against the public statement, including the relevant program and public inputs or outputs.

A runner constructs execution data; it is not itself the cryptographic prover. Likewise, a valid proof establishes the specified execution statement. It does not automatically establish the programmer’s intended business logic, the truth of external data, or the correctness of every compiler transformation. Those guarantees need their own assumptions or checks. [2, 3]

Although Cairo can be used with zero-knowledge proofs, the CPU architecture alone does not guarantee that application data stays private. Privacy depends on the proof system, public-input choices, and surrounding protocol. General programmability also does not make unbounded computations practical: executions must fit finite proving resources. [2, 3]

How Sierra Fits into Later Cairo

Sierra is a later intermediate representation between Cairo source and Cairo assembly (CASM) in the Starknet workflow. It addresses, among other issues, how unsuccessful execution can still produce a provable outcome. The Cairo Book contrasts this with Cairo Zero programs that can reach an unsatisfiable assertion. Sierra’s handling of failure supports charging for work and resistance to denial-of-service through unprovable executions. [5]

These mechanisms do not eliminate transaction reverts or guarantee correct contract logic. Starknet’s accepted hint behavior is governed by its compilation and execution pipeline; it should not be confused with permitting arbitrary user-defined hints in a deployed contract. Sierra is useful later context, rather than part of the original August 2021 paper. [5]

Social Media Sentiment

No current social-media sample was collected for this reference. Community sentiment is therefore unassessed. The technical discussion here is grounded in the paper and official documentation, with particular attention to reusable constraints, witness validation, and provable failure handling.

Last updated: 2026-10

Related Terms

ZK-STARK — the proof-system family used in the paper’s design.
Zero-Knowledge Proof — a separate property relevant to what a verifier learns.