# Cairo M ## Introduction Cairo M is a new zkVM proposed to address the structural limitations of the original [**Cairo VM**](https://fractalyze.gitbook.io/intro/~/revisions/6ILOvDSvW4zAg8fUzupj/zkdsl/cairo). While Cairo was designed to be STARK-friendly, it faces critical constraints in terms of scalability and parallel proving (continuation): * **Non-deterministic continuous read-only memory with relocation model** In the original Cairo, the runner must perform a memory segment **relocation** after program execution. This design prevents the use of the **continuation** technique—where proofs can be generated as soon as each segment is ready — because the final memory addresses are only known **after** relocation is completed. * **Large prime field requirement** The design of Cairo requires a base prime field larger than $$2^{63}$$. However, modern STARK provers typically operate over **small prime fields** such as BabyBear or Mersenne31, making Cairo inefficient in contemporary proving frameworks. *** ## Background ### Stwo Lookup All aspects of Cairo M — including memory consistency, register updates, and hash computations —\ are verified through the **Lookup Component** provided by the **Stwo framework**. In Stwo, all lookup relations are combined into a **single global fraction sum**: $$ \sum\_i m\_i \cdot \mathsf{Relation}(v\_{i,0}, \dots, v\_{i,n}) = 0 $$ where: * $$m\_i$$ denotes the **multiplicity (number of occurrences)** of the relation * $$\mathsf{Relation}(v\_{i,0}, \dots, v\_{i,n})$$ represents the **lookup term** for that relation When all relations are balanced within this global sum such that the total equals zero,\ it guarantees **global lookup consistency** across the entire proof. In this model: * $$+\mathsf{Relation(\dots)}$$ represents an **emit / produce** operation * $$-\mathsf{Relation(\dots)}$$ represents a **consume / remove** operation The proof system is designed so that the sum of all emitted and consumed terms equals zero,\ ensuring state consistency across all components. *** ## Description ### Memory To support **continuation**, Cairo M must ensure that the **final memory state** of stage $$n$$\ is identical to the **initial memory state** of stage $$n + 1$$. To achieve this, Cairo M commits the memory state using a **Merkle tree** structure. #### Commitment The Merkle tree is used for memory state commitment for the following reasons: 1. **Challenge-independent commitment**\ — The initial and final root hashes alone are sufficient to ensure state consistency. 2. **Sparse memory support**\ — Partial pruning of unused branches allows for efficient memory handling. **Features** * Hash function: **Poseidon2** (a STARK-friendly hash) * Number of leaves: $$2^{30}$$ — the largest power of two smaller than $$P$$ * Leaf hashing: leaf nodes are **not hashed** to reduce computational overhead * Although sibling nodes may be revealed during inclusion proofs, this is not an issue for **state root commitment** purposes. *** #### Lookup Argument The Merkle component must prove that the root of the Merkle tree, composed of $$2^{30}$$ leaves, corresponds to the **initial or final root hash**. This is achieved by removing the parent node and adding its child nodes, expressed as a relation within the **global LogUp sum**: $$ -\mathsf{Merkle(index, depth, parent, root)} \\ +b\_{2 \cdot \mathsf{index}} \cdot \mathsf{Merkle(2 \cdot index, depth + 1, child\_L, root)} \\ +b\_{2 \cdot \mathsf{index + 1}} \cdot \mathsf{Merkle(2 \cdot index + 1, depth + 1, child\_R, root)} \\ -\mathsf{Poseidon2(parent)} \\ +\mathsf{Poseidon2(child\_L, child\_R)} $$ where: * $$b\_{2 \cdot \mathsf{index}}$$ and $$b\_{2 \cdot \mathsf{index} + 1}$$ are binary flags indicating whether the left or right child exists (1 if present, 0 otherwise) * Unused branches have multiplicity set to 0 and are automatically **pruned** This relation ensures that the Merkle path is consistently connected through the **Poseidon2** hash function. *** #### Memory Access Memory accesses are expressed as a 3-tuple: $$ \mathsf{(address, clock, value)} $$ Here, $$\mathsf{clock}$$ is a **monotonically increasing counter** that determines the order of memory accesses. *** #### Word Size Although Cairo M’s memory is committed at the level of individual **field elements**, each address can group multiple leaves together to form a **multi-limb word**. For example, if four leaves are combined into one memory word: $$ -\mathsf{Merkle}(a, 30, v\_0, \mathsf{root}) \\ -\mathsf{Merkle}(a + 1, 30, v\_1, \mathsf{root}) \\ -\mathsf{Merkle}(a + 2, 30, v\_2, \mathsf{root}) \\ -\mathsf{Merkle}(a + 3, 30, v\_3, \mathsf{root}) \\ +\mathsf{Memory}(a, \mathsf{clock}, v\_0, v\_1, v\_2, v\_3) $$ This is merely an example — in Cairo M, **word size is not fixed**. Because the LogUp argument ignores trailing zeros, the number of limbs per address can vary while still preserving consistency. This concept is referred to as **lazy word size**. For instance, types such as `u16`, `u32`, and `u64` can share the same memory address: $$ \mathsf{Memory}(a, \mathsf{clock, value}, 0, \dots, 0) \= \mathsf{Memory}(a, \mathsf{clock, value}) $$ If necessary, a fixed word length can be explicitly defined by adding a $$\mathsf{LEN}$$ term: $$ \mathsf{Memory}(a, \mathsf{LEN, clock, value}, \dots) $$ *** #### Read / Write Operations **Write Operation** $$ -\mathsf{Memory(address, prev\_clock, prev\_value)} \\ +\mathsf{Memory(address, clock, value)} \\ +\mathsf{RangeCheck20(clock - prev\_clock - 1)} $$ Here, $$\mathsf{RangeCheck20}(v)$$ represents a component that ensures the input value is constrained to a 20-bit range $$(0 \leq v < 2^{20})$$. * The first term consumes the previous memory state * The second term emits the new state * The third term enforces the monotonic increase of $$\mathsf{clock}$$ (ordering constraint) **Read Operation** For a read-only operation, where $$\mathsf{prev\_value = value}$$: $$ -\mathsf{Memory(address, prev\_clock, value)} \\ +\mathsf{Memory(address, clock, value)} \\ +\mathsf{RangeCheck20(clock - prev\_clock - 1)} $$ By subtracting and adding memory terms in this way, Cairo M can naturally prove that the transition from the **initial state to the final state** is consistent across the entire memory. *** #### Clock Update $$\mathsf{RangeCheck20}$$ can only verify a 20-bit range (i.e., up to $$2^{20}$$). Therefore, if the clock difference $$\delta$$ exceeds this $$\mathsf{RC\_LIMIT}$$([**R**anche](#user-content-fn-1)[^1]**C**heck **LIMIT**), a **clock update** must be performed. $$ -\mathsf{Memory(address, prev\_clock, prev\_value)} \\ +\mathsf{Memory(address, prev\_clock + RC\_LIMIT, prev\_value)} $$ This process does not modify the stored value; it simply **splits a long time interval into smaller steps (step-splitting)**. In practice, the prover divides a large clock gap into multiple smaller RangeCheck blocks. {% hint style="info" %} I assume that $$\mathsf{RC\_LIMIT}$$ is a negative value. {% endhint %} *** #### Cost Analysis Now, let’s compare the cost between the **read-write memory model** and the **read-only memory model**. Here, cost is measured in units of **trace columns**. *** **Write Access on Read-Write Memory** * Main trace: $$(\mathsf{address, prev\_clock, clock, prev\_value, value})$$ * Lookup: $$ -\mathsf{Memory(address, prev\_clock, prev\_value)} \\ +\mathsf{Memory(address, clock, value)} \\ +\mathsf{RangeCheck20(clock - prev\_clock - 1)} $$ * **Total:** $$5T + 3L$$ *** **Read Access on Read-Write Memory** * Main trace: $$(\mathsf{address, prev\_clock, clock, value})$$ * Lookup: $$ -\mathsf{Memory(address, prev\_clock, value)} \\ +\mathsf{Memory(address, clock, value)} \\ +\mathsf{RangeCheck20(clock - prev\_clock - 1)} $$ * **Total:** $$4T + 3L$$ *** **Read Access on Read-Only Memory** * Main trace: $$(\mathsf{address, value})$$ * Lookup: $$-\mathsf{Memory(address, value)}$$ * **Total:** $$2T + 1L$$ *** **Tradeoff** Lookup columns are defined over the **secure field**, typically $$\mathsf{QM31} \approx 4\mathsf{M31}$$. Thus, we can approximate $$1L \approx 4T$$ and estimate the following overhead:
Operation TypeOverhead per Access
Write(5T + 3L) - (2T + 1L) = 3T + 2L ≈ 11T
Read(4T + 3L) - (2T + 1L) = 2T + 2L ≈ 10T
For example, a `STORE` operation such as `dst = op0 + op1` requires **2 reads + 1 write**, resulting in approximately **31T** of overhead. *** **Mitigation Strategies** This overhead can be mitigated in the following ways: * **In-place opcodes:** Reduce the number of read/write operations (e.g., use `x += y` instead of `x = x + y`) * **Pre-sum optimization (**[**Section 6.1.2**](https://github.com/kkrt-labs/cairo-m/blob/ba42e4182a4678c5699fa106e4c33c1cd48d852a/docs/design.pdf)**):** Combine multiple lookup terms to cut lookup cost roughly in half Although the overhead increases, the design offers significant advantages: * Flexible control flow * No need for frame duplication * Simplified program development Therefore, Cairo M considers this overhead a **worthwhile trade-off**. Meanwhile, immutable data such as program bytecode can remain in a **read-only segment**, while only dynamic data is stored in **read/write memory**, allowing for more efficient overall design. *** ### Registers The original **Cairo VM** includes three registers:
NameMeaning
pcProgram Counter — the address of the currently executing instruction
fpFrame Pointer — the base address of the current function frame
apAllocation Pointer — a free memory pointer (the end of the contiguous memory region)
However, since Cairo M adopts a **read/write RAM model**, the concept of “free memory” is no longer needed. In other words, there is no need to dynamically append memory, so the `ap` register can be removed. Cairo M’s initial design therefore includes only the following three registers:
RegisterRole
pcThe address of the current instruction
fpThe base address of the current frame
clockA monotonically increasing counter used to enforce memory access order and timing constraints
*** #### The Register Model from the Prover’s Perspective From the ZK prover’s point of view, each register is represented as a **column in the trace table**. In other words: * `pc`, `fp`, and `clock` each occupy one column * Each opcode component (e.g., `StoreAdd`, `JmpRel`, etc.) consumes the current register state and produces the next one This means that **register state transitions can also be represented using the same LogUp lookup relation** as memory. $$ -\mathsf{Registers(prev\_pc, prev\_fp, prev\_clock)} \\ +\mathsf{Registers(pc, fp, prev\_clock + 1)} $$ Here, the $$\mathsf{Registers}$$ relation represents a state transition of the register vector, where each opcode execution “consumes (−)” the previous state and “produces (+)” the next one. *** #### Register Expansion Trade-off In Cairo M, registers are grouped together as a **main register stack**. When increasing the number of registers, a trade-off arises:
OptionAdvantageDisadvantage
Expand the main register stackAdds one column per component → faster accessEach component must always use the column → wasted space
Introduce secondary register stacksAccess only when needed → saves columnsRequires two lookup terms (≈ 4 base columns) per access
Because the values in the secondary stack do not exist directly in the main trace, every access must perform two lookups — one to consume (−) the previous state and another to produce (+) the new state. Thus, Cairo M must balance **space cost (columns)** and **computation cost (lookups)**. In the current design, only $$\mathsf{(pc, fp, clock)}$$ reside in the **main stack**, while any additional registers will be introduced later via **secondary stacks** if needed. *** ### Opcodes Cairo M’s instruction set originates from the original Cairo VM, but it has been redesigned to fit the new proving model based on **LogUp** and **component-based AIR**. The goal of Cairo M’s opcode design is to strike a balance among **performance, simplicity, and parallelism**. *** #### AIR Basics AIR (Algebraic Intermediate Representation) expresses computation as a set of **polynomial constraints**. An AIR can be viewed as a dataframe composed of **columns** (variables) and **rows** (state transition steps). Each operation is expressed as a constraint that must evaluate to zero for every row. For example, the equation $$c = a + b$$ can be represented in AIR form as: $$ \mathsf{df}\[c] - \mathsf{df}\[a] - \mathsf{df}\[b] = 0 $$ This constraint must hold for every row, and each column is interpreted as a polynomial. During STARK proving, the polynomial commitments are stored via a Merkle tree. Thus: * **More columns** → larger proof size, more verification cost * **Higher constraint degree** → larger evaluation domain and higher proving cost Cairo M’s design goal is to **minimize both the number of columns and the degree of constraints for reduced proving and verification costs.** *** #### Design Principles Cairo M’s ISA design follows the classical **RISC (Reduced Instruction Set)** vs **CISC (Complex Instruction Set)** trade-off logic: | Type | Characteristic | Trade-off | | ------------------ | ---------------------- | ----------------------------- | | **RISC-style ISA** | Fewer, simpler opcodes | More cycles but fewer columns | | **CISC-style ISA** | Many, complex opcodes | Fewer cycles but more columns | For long traces, Cairo M can leverage **continuation** to split a large trace into smaller proving segments, and then recursively aggregate the resulting proofs. If the execution trace is represented as a dataframe with shape $$(n, m)$$ ($$n$$ rows, $$m$$ columns), it can be reshaped into $$(n / k, m \cdot k)$$, but not the other way around — this highlights that increasing column count inherently increases the proof size and verifier complexity, since each additional column introduces another commitment. {% hint style="info" %} The paper doesn't explain how reshape is possible and why it's impossible to change the shape from $$(n/k, m \cdot k)$$ to $$(n, m)$$. {% endhint %} Therefore, Cairo M chooses the **RISC approach (a long & thin AIR)**, which keeps columns few and constraints simple. *** #### Minimal Instruction Set Cairo M’s **minimal instruction set** is defined as the smallest possible configuration that maintains RAM consistency while still supporting all general-purpose computations. | Category | Instruction | Description | | ---------------- | ---------------------------------------------------------- | ----------------------------------- | | **Control Flow** | `CallRel`, `Ret` | Function calls and returns | | **Branching** | `JmpRel`, `JnzRel` | Conditional and unconditional jumps | | **Arithmetic** | `StoreAdd`, `StoreSub`, `StoreMul`, `StoreDiv` | Field arithmetic and result storage | | **Memory Move** | `MoveString`, `MoveStringIndirect`, `MoveStringIndirectTo` | Memory copy and indirect moves | This instruction set alone supports field arithmetic, control flow, function calls, and memory manipulation. The overall AIR footprint for this minimal set is approximately **52T + 39L columns**. *** #### Extensions The base instruction set alone is not always efficient in every context. Therefore, Cairo M introduces the concept of **extension opcodes**, which allow certain operations to be handled **natively at the prover level**. *** **Uint Types** While the STARK prover’s native type is a **field element**, real-world software typically relies on integer types such as `u8`, `u16`, `u32`, and `u64`. To bridge this gap, Cairo M supports these integer types **directly at the AIR level**, using **range-checked memory segments**. * Division is defined as **Euclidean division** * Each limb is range-checked to guarantee that its value lies within $$\[0, 2^k)$$ * The largest simple native uint type is **u20** (as determined by the RangeCheck20 component) However, since `u20` is not software-friendly, the practical implementation uses **u8** or **u16** as the base limb size. | Type | RangeCheck Component | Characteristic | | ----- | -------------------- | --------------------------------------------------------- | | `u8` | $$\[0, 2^8)$$ | Byte-addressable, compatible with WASM/RISC-V | | `u16` | $$\[0, 2^{16})$$ | Reduced arithmetic cost, efficient 16-bit limb operations | This makes Cairo M’s memory layout compatible with byte-level zkVM architectures such as **RISC-V** and **WASM-based** systems. *** **Built-in Functions (Precompiles)** Cairo M also supports the concept of **built-in functions (precompiles)**, which define complex operations as dedicated AIR components. Operations such as **Poseidon hashing** or **modular exponentiation** are inefficient to implement as normal opcodes. By defining them as precompiles, Cairo M gains several advantages: 1. **Fewer lookup arguments** → reduced column count 2. **Support for non-deterministic computations** → the prover can provide intermediate values as hints during witness generation Precompiles can be integrated in two ways: | Method | Description | Trade-off | | -------------------------------- | ------------------------------------------------------------------------------- | ------------------------------------------ | | **(1) Opcode-level** | Add a unique opcode ID and include it in the main AIR | Increases column count | | **(2) Recursive pre-processing** | Prove the operation in a separate AIR and recursively merge with the main proof | Improves parallelism and memory efficiency | This design aligns with modern zk compiler trends, where the compiler can automatically generate precompile circuits and handle recursive composition transparently. *** ## Conclusion The goal of Cairo M is simple — **“To build the fastest, simplest, and most general-purpose zkVM.”** Cairo M is not merely an “updated version” of the original Cairo VM; it represents a new design standard for modern zkVM architectures. | Design Aspect | Cairo VM | Cairo M | | ------------------------- | ---------------------------- | ------------------------------------ | | **Memory model** | Relocation-based, read-only | Merkle committed, read/write capable | | **Field** | Large (2²⁵¹ + 17⋅2¹⁹² + 1) | Small (M31) | | **Proof style** | Sequential, monolithic | Continuation + recursion | | **Execution scalability** | Limited (\~10⁵ steps) | Scalable to 10⁸+ steps | | **Implementation focus** | StarkNet transaction proving | General-purpose computation | In other words, Cairo M can be seen as a **zk-friendly CPU architecture** redesigned into a **scalable proving environment**. Cairo M began as a **minimal felt-based zkVM**, but ultimately reached the conclusion that a shift toward **byte-addressable memory** and a **byte-level ISA** is necessary. From this perspective, it acknowledges that reusing existing ISAs such as **RISC-V** or **WASM** in a ZK-friendly form is the most practical approach. Projects like **RISC Zero** are already leading the way in this direction. *** The most important insight that emerged from Cairo M is this: > **“The essence of a zkVM lies not in its instruction set, but in the communication and proof composition between components (continuation + recursion).”** That is, the future of zkVMs will not be defined by *which instructions they support*, but by *how each AIR component exchanges proof data* and *how multiple proofs are ultimately combined into a single unified proof*. ## References * > Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze [^1]: Range?