Skip to content
Crypto.world

Research

Formal verification of the S-two AIR

StarkWare's S-two prover lets someone prove on a blockchain that a Cairo program ran to completion, by encoding that claim as an AIR — tables of finite-field values satisfying algebraic constraints…

Formal verification of the S-two AIR
arXiv
2606.04311
Published
2026-06-03
Authors
Jeremy Avigad, Anat Ganor, Lior Goldberg, David Levit, Ohad Nir, Yoav Seginer, Alon Titelman

AI summary

Formal Verification of the S-two AIR — Plain-Language Summary

Overview

Research area: Cryptography and security, specifically formal verification of STARK-based proof systems for the Cairo virtual machine (cs.CR; the paper is arXiv:2606.04311v1).

Technical level: Advanced. The paper assumes familiarity with interactive proof systems, algebraic intermediate representations (AIRs), finite fields, and interactive theorem proving in Lean 4.

One-sentence scope: The paper describes a Lean 4 formalization showing that satisfiability of StarkWare's S-two AIR implies the existence of a valid, terminating Cairo virtual machine execution trace consistent with the public inputs.

What This Paper Is About

StarkWare's S-two prover lets someone prove on a blockchain that a Cairo program ran to completion, by encoding that claim as an AIR — tables of finite-field values satisfying algebraic constraints — and certifying it with the circle STARK proof system. Trusting such a certificate requires trusting that the AIR encoding is sound: that satisfying the constraints really does imply the computational claim. The paper's goal is to machine-check that implication in the Lean 4 proof assistant, covering both the per-component polynomial constraints and the algebraic encoding of the message-passing protocol that links components together.

Key Contributions

  1. A machine-checked soundness theorem for the S-two AIR. The theorem states that if an instance of the S-two AIR satisfies the constraints (under a list of explicit hypotheses), then there is a full memory assignment extending the public partial assignment and a register-state sequence of length at most 2^29 + 1 starting at the agreed initial state, ending at the agreed final state, and satisfying the Cairo NextState relation at every step.

  2. Verification of the component-and-message architecture, not just individual constraints. Unlike the earlier Stone verification — where a small, explicitly enumerated polynomial list could be exported and reasoned about directly — the S-two AIR is generated by a composable infrastructure whose raw polynomial output "lacks sufficient structure" to reason about. The authors therefore ported the relevant generator code into Lean and proved that the constraints, uses, and yields it generates have the intended properties.

  3. Verification of the logup protocol (Section 5 of the paper), the general scheme used to share information between components. The authors establish that if a lookup claim fails, only a small set of "random" field values could fool the protocol into acceptance, yielding a negligible soundness error.

  4. A precisely delimited trust boundary. The paper is explicit about what was not modeled in Lean — global bookkeeping that collects lookups across components and arranges them into constraints — and reflects each such gap as a named hypothesis of the soundness theorem (e.g., h_use_agree, h_yield_agree, h_is_mem_addr_to_id, h_rc), so reviewers can see exactly what remains to be trusted.

Main Findings

  • The Cairo semantics did not need to change. The NextState relation over an arbitrary finite field F, with memory modeled as a function F → F, is reused verbatim from the earlier Stone verification (def NextState (mem : F → F) (s t : RegisterState F) : Prop). The underlying semantics is the same; only the AIR encoding differs.

  • Two different fields are in play. The AIR works over the M31 field (integers modulo 2^31 − 1), while the Cairo machine operates over the Felt252 field (integers modulo 2^251 + 17·2^192 + 1). The paper calls elements of the first field Felts and of the second Felt252s, and reasoning about the latter in terms of the former is described as one of the most challenging aspects of the work.

  • Five component kinds in the Lean model. The Lean code fixes a component set: Opcode o, RangeCheck, MemoryAddrToId, MemoryIdToValue, and VerifyInstr. The first three in that list are lookup-only components that add yields and no uses.

  • VerifyInstruction operates on 19 Felts. It takes a tuple (c, o1, o2, o3, f1, f2, …, f15) — a memory location plus three 16-bit offsets and 15 boolean flags — and adds constraints ensuring the Felt252 at location c encodes an instruction with those offsets and flags, issuing lookups to the memory and range-check components as needed.

  • Range checks were collapsed in the model. The real S-two implementation has specialized components such as rc20 for 20-bit values and rc9_9 for pairs of 9-bit values; the Lean modeling collapses these into a single RangeCheck component.

  • Memory uses an intermediate id, and its well-definedness is assumed. MemoryAddrToId registers pairs (x, i) mapping a Felt address to a Felt id, and MemoryIdToValue registers pairs (i, y) mapping an id to a Felt encoding of a Felt252 value. Distinctness of the preprocessed column values (addresses or ids) enforces that these are well-defined functions; this is not verified but supplied as hypotheses h_is_mem_addr_to_id and h_is_mem_id_to_value.

  • Chain lookups are what produce a trace rather than a set of steps. For chain relations, the multiset of use values must equal the multiset of yield values (rather than the weaker subset condition used elsewhere), with the initial and final states introduced as external lookups. This is what forces the certified state pairs (s, s′) to chain into a single execution trace.

  • Concrete size bounds appear in the hypotheses. The number of uses of the opcode lookup table must be at most 2^29 (h_num_steps), and the initial allocation pointer must satisfy strongly_bounded₀ 0, described as amounting to the initial allocation pointer being less than 2^29 − 1 (h_state_bound). The conclusion bounds the trace length by 2^29 + 1.

  • Primality is assumed, not proved. [Fact (Nat.Prime Stwo.P)] and [Fact (Nat.Prime Felt252Prime)] are carried along as hypotheses to the final theorem rather than established in Lean.

  • Completeness is explicitly out of scope. The paper notes that the prover can always produce an AIR under the relevant circumstances is completeness, dual to soundness; similar completeness claims were established in other work, but this paper addresses soundness only.

  • The formal proofs are publicly available at https://github.com/starkware-libs/formal-proofs.

Methodology in Plain English

The team writes mathematics and code in Lean 4, a proof assistant whose small trusted kernel checks every proof step, backed by the Mathlib library of formalized mathematics.

The tempting shortcut — run the AIR-generating code, dump the resulting polynomials, translate them into Lean, and reason about the list — was rejected as infeasible. The encoding is too large, and more importantly the flat polynomial list loses the structure that explains why the constraints work: they guarantee an execution trace because of how the generating code was written. So the authors instead translated the relevant parts of the generator infrastructure itself into Lean and proved that the constraints, uses, and yields it produces have the right properties.

Because Lean is a pure functional language (no mutation of global state), reasoning about the ported code is tractable, though modeling stateful computation takes extra effort. The authors were selective: they modeled per-component constraints, yields, and lookups; they verified the logup protocol; and they deliberately did not model global infrastructure such as the machinery that collects all lookups in one place or arranges lookups into constraints. Those omissions appear as explicit hypotheses in the theorem statement, so nothing is silently assumed.

A recurring pattern in the formalization is to model the S-two data structures first and then define their intended semantics separately. A polynomial constraint is represented as a FeltExpr (a constant, a variable, or a unary/binary operation on expressions), evaluated against a VarAssign from variable indices to Felts, and satisfied when it evaluates to 0. A component's constraints are satisfied when every entry evaluates to 0 under the row's assignment.

The final theorem takes as parameters the public InputData — initialAp, initialPc, finalAp, finalPc, and mStar : Felt252 → Option Felt252, a partial memory assignment — together with PublicMem.Lookups and a hypothesis that these lookups agree with mStar. The initial state sets fp = initialAp; the final state sets fp = initialAp and ap = finalAp, mirroring the verifier's checks on the frame pointer. From these, plus the component, range-check, memory, logup, and size-bound hypotheses, the conclusion produces a memory function extending mStar and an execution trace.

Why This Matters

Impact on research. This is a substantial step beyond prior formal verification of AIR encodings. Earlier work covered the Stone prover's AIR (a comparatively small, explicitly enumerated constraint list), end-to-end verification of CairoZero library functions including dictionary lookups and elliptic curve signature validation, and several Libfuncs for the current Cairo. The S-two encoding is described as "much more elaborate," uses a fundamentally different composable architecture with inter-component messaging, and required verifying not just local constraints but the soundness of the communication protocol between components.

Real-world applications:

  • On-chain smart contract verification. Cairo is used to verify smart contract execution on blockchain; a formally verified soundness result strengthens the guarantee that an accepted STARK certificate corresponds to an actual terminating computation.
  • Rollup and proving-system assurance. StarkWare's prover stack underpins production proving systems, where a subtle AIR bug could allow invalid state transitions to be certified.
  • Audit and review leverage. Because the trust boundary is itemized as theorem hypotheses, auditors can concentrate manual review on the specific unverified pieces — preprocessed column distinctness, lookup collection, and constraint assembly — rather than the whole stack.
  • Reusable verification infrastructure. The ported models of FeltExpr, AirBuilder, LookupTerm, and the logup constraints provide a template for verifying future AIR generators rather than one-off constraint lists.

Industry relevance. The work comes from a collaboration between Carnegie Mellon University and StarkWare Industries, and the proofs are published openly. It demonstrates a practical division of labor for production cryptography: verify the parts where subtle errors are most likely, and state clearly — as machine-checked hypotheses — the parts that remain trusted.

Future Directions

  1. Closing the stated hypotheses. The paper leaves unverified the global bookkeeping that collects lookups across all components and the code that arranges lookups into constraints (h_use_agree, h_yield_agree), the distinctness of preprocessed column values, and the range-check assignment property. Formalizing these would shrink the trusted base substantially.

  2. Verifying completeness. The paper explicitly addresses only soundness. Establishing that the prover can always produce a satisfying AIR under the appropriate conditions — as was done in other work — remains a separate obligation.

  3. Discharging the arithmetic hypotheses. The primality facts for the M31 prime and the Felt252 prime are carried as Fact hypotheses rather than proved in Lean; proving them would remove an assumption from the final theorem.

  4. Extending beyond the collapsed model. The Lean model merges the specialized range-check components (rc20, rc9_9, and others) into a single RangeCheck. Verifying the specialized versions directly, along with the parts of the AIR generator that the Lean component set abstracts away, would bring the formalization closer to the deployed code.

Target Audience

This paper is written for cryptographers and proof-system engineers who need to understand precisely what guarantee a STARK certificate provides for Cairo execution, and for formal-methods researchers interested in how large-scale, code-generated AIRs can be verified without flattening them into unmanageable polynomial lists. Readers will benefit most from background in finite-field arithmetic, AIR/STARK architecture, and interactive theorem proving; the paper is not an introduction to any of these. Auditors and security reviewers of StarkWare's stack are a secondary audience, since the hypothesis list defines exactly what still requires manual trust.

Note on completeness of this summary: the supplied paper content is truncated partway through Section 4.1. Section 5 (the logup protocol verification) and Appendix A (the full theorem statement) are referenced by the paper but their contents are not included above, so the specific logup definitions, bad-set sizes, error bounds, and the verbatim appendix statement are not reported here.

Authors’ abstract

StarkWare's S-two prover provides an efficient means for establishing, on blockchain, that a program written in the Cairo virtual machine language runs to completion. The latter claim is encoded by an algebraic intermediate representation (AIR) that captures the semantics of the Cairo language. The AIR asserts the existence of tables of values from a finite field satisfying certain algebraic constraints. A cryptographic interactive proof system, circle STARK, provides an…

The full abstract on arXiv
Read the original paper