Verifying a zkVM with Lean and Clean

Soundness is the property a zkVM's verifier relies on, and there is no test for it. Part 1 of the Lambda VM series on formal verification of circuits, with LambdaClass and 3MI Labs: a toy VM written in Clean and proved in Lean, table by table and bus by bus, up to the theorem about the machine.

Verifying a zkVM with Lean and Clean

The code in this post comes from clean_examples, a toy VM written in Clean. Every snippet is taken from that repository as is, and the whole thing compiles.

1. The problem

A zkVM turns the execution of a program into a trace: a table of field elements, one row per step. The rules of the machine become a constraint system over that table, polynomial identities that have to hold on every row and lookups between tables. The verifier checks the constraints and never looks at the trace, so everything rests on two properties. Completeness says that the trace of an honest execution satisfies the constraints. Soundness says that any trace satisfying the constraints comes from a valid execution.

Completeness talks about one trace per execution, and testing it is routine. Soundness talks about every trace that could be written, including the ones an adversary builds after reading the constraints, and it is the property the verifier relies on. There is no test for it, because a test evaluates the constraints on traces somebody wrote, and the traces that matter are the ones nobody wrote. The bugs that break soundness are quiet for the same reason: a column with no range check, a witness column no constraint pins down, a lookup multiplicity left unconstrained, a sum of limbs that wraps modulo p. None of them make an honest trace fail, and all of them let a dishonest one through.

Formal verification addresses exactly this. The constraint system is brought into a proof assistant, by transcription or by extraction from the compiled circuit. A specification states what a row of each table, or a step of the machine, is supposed to mean. A proof then shows that every trace satisfying the constraints satisfies the specification, for all traces at once. What is left to trust is short. The specification has to be the right one, whether written for the project or taken from a formal model of the instruction set. The formal constraints have to be the ones in production. And the lookup argument has to enforce what the constraints assume of it, which is the proof system's job. The proof system and the prover that implements it are separate problems, and we leave them out of this post.

2. Lean, and what "proven" means

A compiler checks a function against its signature without running it and with the argument unknown, so what it establishes holds for every input. Lean's checker is that with one addition: a type may mention a value, so n < p is a type. A proof is a value of that type: a proof of A ∧ B is a pair, a proof of A → B is a function, a proof of ∀ n, P n is a function of n, and a false statement is an empty type. Here is one from the example repository, with p the Goldilocks prime:

lemma lt_p_of_lt_two_pow_40 {n : ℕ} (h : n < 2^40) : n < p := lt_trans h (by decide)

The signature is a function of n and of h : n < 2^40 returning n < p, and the body is checked like a call. lt_trans has type a < b → b < c → a < c; h fixes a = n and b = 2^40, the declared result fixes c = p, so the second argument must have type 2^40 < p, which decide produces by computing it. The application has type n < p and is accepted. With n < 2^80 as hypothesis no second argument exists. The checker never used a value of n, so the result holds for every n, which no test gives.

decide is a tactic, a program that searches for a term, like omega and simp later on. The checker is a small kernel that re-checks every term the tactics produce, Mathlib included, so a bug in a tactic yields a term that fails to check, never one that checks for a false statement. What is trusted is the kernel, the axioms, and the statements.

That organises a verification project. The statement is what a person reads to know what was established, so it is short and in the vocabulary of the design. The proof can be long, since only the kernel reads it. A verified codebase is a few hundred lines of statements a reviewer checks against the design, and proofs nobody reads again.

For a zkVM, the objects already exist. The cells of a trace are elements of a prime field, ZMod p in Lean, arithmetic and lemmas from Mathlib, and a constraint is a polynomial over that field. There is no modelling step, because an AIR is already a mathematical object.

3. Clean

Clean is a library on top of Lean, written by zkSecurity as part of the Verified-zkEVM effort, for circuits of the shape a modern zkVM has: flat tables where one circuit is checked independently on every row, and all communication between rows and between tables goes through lookup channels. It gives names and types to the objects of the previous sections, and it comes with the theorem that assembles per-table proofs into a proof about a machine. The vocabulary is small and the rest of the post uses it constantly, so here it is in one place.

A circuit is a Lean program that emits operations: assertZero e for a polynomial constraint, a lookup, or an interaction with a channel. The program is written in do notation over a row whose columns are symbolic expressions, so r.a + r.b builds a polynomial rather than adding two numbers. Running it produces the list of operations of one row, and that list has two readings. Evaluated on concrete field elements it is the proposition "the constraints hold on this row". Read structurally it is the AIR itself, one polynomial per assertZero and one interaction per channel operation. Clean calls the program main.

A channel is a bus between tables: a name, a message type, and a guarantee, which is a predicate on messages stating what a message on that channel means. A table interacts with a channel in one of two ways. A pull emits a message with multiplicity −1 and is marked as assumed: the table claims that somebody provides this message, and takes the guarantee as a hypothesis. A push emits a message with multiplicity +1 and owes the guarantee: the table has to prove it for every message it emits. In zkVM codebases a pull is usually called a send and a push a receive. The two directions are what make per-table proofs compose, since a consumer assumes exactly what a provider promises and the bus is where the two meet. A precomputed table is the special case of a static lookup channel, where the guarantee comes with the list of entries and a proof that the two agree.

A formal circuit is main plus a contract. Spec is what a row establishes, written in the vocabulary of the design rather than of the constraints, and it is the line a reviewer reads. Assumptions is what the table may take for granted about its inputs from outside, usually nothing. ProverAssumptions describes the row the honest prover fills in, which is the row completeness is proved for. Then come the two proofs. Soundness: for every row on which the constraints hold, with the guarantee of every pulled message available as a hypothesis, Spec holds and every pushed message satisfies the guarantee of its channel. Completeness: the honest row satisfies every constraint, and every message it pulls satisfies the guarantee of its channel, so that a provider can in fact supply it.

An ensemble is the machine: a list of tables, the channels they share, and a verifier circuit for the public input. A witness assigns rows to every table. Constraints says that every table's main holds on every one of its rows, and BalancedChannels says that on every channel the multiplicities of each distinct message sum to zero, with the total number of interactions below the field size. The ensemble theorem is that Constraints and BalancedChannels together imply every table's Spec on every row. Its proof needs the tables in an order, with every channel finished by its providers before a consumer pulls from it, and Clean makes you build the ensemble in that order and discharge the ordering obligations as you go.

What Clean does not contain matters as much as what it does. It has no notion of the proof system: the polynomial commitment, FRI, the random challenge that turns balance into an equation, none of it is modelled. BalancedChannels is a premise of the ensemble theorem, not something Clean proves. It says nothing about the prover that fills the tables or the code that evaluates the constraints. Its subject is the arithmetization and what it means, and the only bridge to the rest is a correspondence, maintained outside Lean, between main and the production circuit.

4. The example

The machine in the repository has four tables and three buses. A precomputed byte table provides the BYTE channel, whose guarantee is that a value is below 256. An adder and a multiplier pull their operands and results from BYTE and provide ADD and MUL, each with a guarantee that says what the result is in terms of the operands. A CPU table has a selector per operation and pulls from ADD or from MUL according to it.

The code is six files under VM/. Basic.lean has the field and the lemmas every proof uses. Byte.lean has the byte table. Adder.lean, Multiplier.lean and Cpu.lean are one table each, with the bus the table provides defined in the same file. Ensemble.lean puts the four tables together and states the theorem about the machine. We start with the adder. It is the smallest table, and it already has the one difficulty every larger table has: showing that a polynomial identity over the field means the arithmetic over the naturals it was written for.

5. Tables

A table in Clean is five declarations: the row type, the circuit, the specification, the row the honest prover fills in, and the two proofs that tie them together. The CPU table of a real VM has dozens of columns and a few hundred operations in its circuit, and it is the same five declarations with more in each. The example for this section is the adder of the toy machine, which adds two bytes and has four columns: the operands a and b, the result sum, which is the sum modulo 256, and carry, the overflow.

The row type is the set of columns, one field each, and the circuit is the list of operations that have to hold on every row:

structure Row (F : Type) where
  a : F
  b : F
  sum : F
  carry : F
deriving ProvableStruct

def main (r : Var Row (F p)) : Circuit (F p) Unit := do
  Byte.pull r.a
  Byte.pull r.b
  Byte.pull r.sum
  isBit r.carry
  assertZero (r.a + r.b - r.sum - 256 * r.carry)
  AddBus.push ⟨r.a, r.b, r.sum⟩

deriving ProvableStruct is what lets the same Row be used both as symbolic columns, which is what main receives, and as field elements, which is what the proofs talk about. The circuit has three kinds of operations, and every circuit of every table has the same three. A constraint, assertZero, is a polynomial that has to vanish on the row, and isBit is a one-line wrapper around assertZero (x * (1 - x)). A pull is a claim on a channel: the three pulls from BYTE claim that a, b and sum are bytes, and the table takes the guarantee of BYTE, which is x.val < 256, as given. A push is a promise on a channel: the adder promises ⟨a, b, sum⟩ on ADD, whose guarantee is that sum is the sum of the operands modulo 256 and that the operands are bytes.

The specification is what a row establishes, written in the vocabulary of the design and not of the constraints. The honest row is the one the prover fills in from a real execution:

def Spec (r : Row (F p)) : Prop := r.sum.val = (r.a.val + r.b.val) % 256

def Honest (r : Row (F p)) : Prop :=
  r.a.val < 256 ∧ r.b.val < 256 ∧ r.sum.val = (r.a.val + r.b.val) % 256 ∧
  r.carry.val = (r.a.val + r.b.val) / 256

Spec says nothing about carries. The carry is a device of the constraints, and the specification is what a reviewer reads to check that the table does what the design says, so it has to be free of such devices. That is the general rule: every auxiliary column, every limb decomposition and every selector that exists to keep the constraints low-degree belongs in main and in Honest, and none of it belongs in Spec.

Soundness is the proof that every row on which the constraints hold satisfies Spec. Each operation of main becomes one hypothesis or one obligation. Constraints and pulls are hypotheses: a.val < 256, b.val < 256, sum.val < 256, carry * (1 - carry) = 0 and a + b - sum - 256 * carry = 0. Pushes are obligations: the ADD guarantee has to be proved for ⟨a, b, sum⟩. The work, in this table as in almost every table of any VM, is reading the identity. The constraints hold in the field, where a + b - sum - 256 * carry = 0 says nothing by itself, since any a, b and sum satisfy it for some carry. It says something once every term is known to be small, and that is what the range checks are for. If the three bytes are below 256 and carry is 0 or 1, both sides of a + b = sum + 256 * carry are below 2^40, far below p, and two naturals below p that agree in the field agree as naturals:

lemma lift {a b sum carry : F p} (ha : a.val < 256) (hb : b.val < 256) (hs : sum.val < 256)
    (hc : IsBool carry) (h : a + b - sum - 256 * carry = 0) :
    a.val + b.val = sum.val + 256 * carry.val := by
  have hc2 := IsBool.val_lt_two hc
  have hcast : ((a.val + b.val : ℕ) : F p) = ((sum.val + 256 * carry.val : ℕ) : F p) := by
    push_cast
    simp only [ZMod.natCast_zmod_val]
    linear_combination h
  exact natCast_inj_of_lt (lt_p_of_lt_two_pow_40 (by omega)) (lt_p_of_lt_two_pow_40 (by omega))
    hcast

Every identity in every table we have modelled is lifted this way: state it as an equality of casts, close it in the field with linear_combination, and bring it down to the naturals with the bounds and the injectivity of the cast. Once on the naturals, omega turns a + b = sum + 256 * carry with sum < 256 into Spec.

Completeness is the proof in the other direction: the honest row satisfies every constraint, and every message it pulls satisfies the guarantee of its channel, so that a provider can supply it. The pulls and the constraints are now obligations, discharged from Honest, and the push costs nothing. It is a cheap proof and an important one, because a table whose constraints no honest row can satisfy is sound for free, and an over-constrained table is a bug the soundness proof will never see. Here is the whole bundle:

def circuit : GeneralFormalCircuit (F p) Row unit where
  main
  Spec r _ _ := Spec r
  channelsWithRequirements := [AddBus.toRaw]

  soundness := by
    circuit_proof_start [main, isBit, Spec, AddBus, byteTable]
    obtain ⟨ha, hb, hs, hc, he⟩ := h_holds
    have e := lift ha hb hs (mul_one_sub_eq_zero_iff.mp hc) he
    have hspec : input_sum.val = (input_a.val + input_b.val) % 256 := by omega
    refine ⟨hspec, ?_⟩
    intros
    exact ⟨ha, hb, hspec⟩

  ProverAssumptions r _ _ := Honest r

  completeness := by
    circuit_proof_start [main, isBit, AddBus, byteTable, Honest]
    obtain ⟨ha, hb, hs, hc⟩ := h_assumptions
    refine ⟨ha, hb, by omega, ?_, ?_⟩
    · exact mul_one_sub_eq_zero_iff.mpr (isBool_of_val_lt_two (by omega))
    · have h := congrArg (fun n : ℕ => (n : F p))
        (show input_a.val + input_b.val = input_sum.val + 256 * input_carry.val by omega)
      push_cast at h
      simp only [ZMod.natCast_zmod_val] at h
      linear_combination h

circuit_proof_start unfolds main and hands over the hypotheses, one per operation. Soundness applies lift, gets Spec by omega, and proves the push obligation from the bounds it already has together with Spec. Completeness discharges the five obligations in order: the three bounds, the carry being a bit, which follows from carry = (a + b) / 256 with a + b < 512, and the identity, which is the arithmetic of lift run backwards. channelsWithRequirements lists the channels the table pushes to, so that the ensemble knows who provides ADD.

An under-constrained column shows up in this process as a hypothesis the proof cannot obtain. Without isBit r.carry, soundness reaches lift, needs IsBool carry and finds nothing that gives it. That is not Lean being difficult: with carry free, the row a = 1, b = 1, sum = 0, carry = 2 · 256⁻¹ satisfies every remaining operation and Spec is false on it. That is the usual way a model of this kind finds a real bug, and it is the same way whether the column is the carry of a toy adder or the borrow of a 64-bit comparison.

6. Buses: what is assumed, what is inherited, what is proved

A bus is a contract. Its guarantee is a predicate on messages, the provider proves the predicate for every message it pushes, and the consumer receives it for every message it pulls. The guarantee is the whole interface: nothing about how the provider is built reaches the consumer, and if the adder were rewritten tomorrow with other constraints, the CPU and its proofs would not change, as long as the ADD guarantee stayed the same. The ADD bus of the toy machine is a message type and the predicate:

structure AddMsg (F : Type) where
  a : F
  b : F
  sum : F
deriving ProvableStruct

def AddBus : Channel (F p) AddMsg where
  name := "ADD"
  Guarantees m _ := m.a.val < 256 ∧ m.b.val < 256 ∧ m.sum.val = (m.a.val + m.b.val) % 256

The guarantee carries the byte bounds as well as the sum, because a consumer that needs to know the operands were bytes can only know it if the bus says so. Deciding what goes into each guarantee is the design work of the model, and it is the same work as deciding what each table of the VM is allowed to assume about the others. A precomputed table is a bus of a special kind, where the guarantee comes with the list of entries and a proof, written once, that the two agree:

def byteTable : StaticLookupChannel (F p) field where
  name := "BYTE"
  table := List.map (fun n : ℕ => (n : F p)) (List.range 256)
  Guarantees x := x.val < 256
  guarantees_iff := by
    intro x
    simp only [List.mem_map, List.mem_range]
    constructor
    · intro hx
      exact ⟨x.val, hx, ZMod.natCast_zmod_val x⟩
    · rintro ⟨n, hn, rfl⟩
      rw [val_natCast_of_lt_two_pow_40 (by omega)]
      exact hn

abbrev Byte : Channel (F p) field := .fromStatic _ _ byteTable

From then on the list is never unfolded, and a table that pulls ⟨x⟩ learns x.val < 256 and nothing else. The third bus, MUL, promises a * b = lo + 256 * hi with the operand bounds, and the multiplier that provides it is the adder with one more byte and a quadratic identity, whose proof only adds a bound on the product before the lift.

The consumer side is where a VM differs from a collection of arithmetic tables. A CPU row executes one instruction, so it pulls from one bus among several, under a selector. The CPU of the toy machine does no arithmetic at all, and its whole circuit is to pull the right message from the right bus:

structure Row (F : Type) where
  is_add : F
  is_mul : F
  a : F
  b : F
  out : F
  out_hi : F
deriving ProvableStruct

def main (r : Var Row (F p)) : Circuit (F p) Unit := do
  isBit r.is_add
  isBit r.is_mul
  assertZero (r.is_add * r.is_mul)
  AddBus.pullIf r.is_add ⟨r.a, r.b, r.out⟩
  MulBus.pullIf r.is_mul ⟨r.a, r.b, r.out, r.out_hi⟩

pullIf e msg is a pull with multiplicity −e instead of −1. With the selector at 1 it is an ordinary pull, and with the selector at 0 it contributes nothing, so a row with both selectors off is padding that pulls nothing and promises nothing. The CPU proves no arithmetic of its own. What it inherits is the guarantee of each bus under its selector: the hypothesis that AddBus.pullIf leaves in the soundness proof is literally -is_add = -1 → AddBus.Guarantees ⟨a, b, out⟩. The specification is conditional in the same way:

def Spec (r : Row (F p)) : Prop :=
  (r.is_add = 1 → r.out.val = (r.a.val + r.b.val) % 256) ∧
  (r.is_mul = 1 → r.a.val * r.b.val = r.out.val + 256 * r.out_hi.val)

The honest row, Honest, is a valid selector pattern together with the result of whichever operation was selected and the byte bounds on the operands, since the guarantee the row has to meet when it pulls includes them.

A conditional pull brings one obligation that an unconditional one does not. Clean classifies an interaction by its multiplicity: −1 is a pull, 0 is nothing, and anything else is a push that would oblige the table to prove the guarantee. When the multiplicity is a column, the table has to show that the column only takes values that make the interaction a pull or nothing, and that is where selector bits get their constraints. The obligation is requirementsChannelsLawful, and the two isBit lines in main are there to discharge it:

def circuit : GeneralFormalCircuit (F p) Row unit where
  main
  Spec r _ _ := Spec r
  requirementsChannelsLawful input_var i₀ := by
    obtain ⟨is_add, is_mul, a, b, out, out_hi⟩ := input_var
    simp only [circuit_norm, main, isBit, AddBus, MulBus]
    refine ⟨fun _ h => h, fun env ⟨hA, hM, _⟩ => ?_⟩
    rcases mul_one_sub_eq_zero_iff.mp hA with h | h <;>
      rcases mul_one_sub_eq_zero_iff.mp hM with h' | h' <;> simp [h, h']

  soundness := by
    circuit_proof_start [main, isBit, Spec, AddBus, MulBus]
    obtain ⟨hA, hM, _, hadd, hmul⟩ := h_holds
    refine ⟨⟨fun h => (hadd (neg_inj.mpr h)).2.2, fun h => (hmul (neg_inj.mpr h)).2.2⟩, ?_⟩
    rcases mul_one_sub_eq_zero_iff.mp hA with h | h <;>
      rcases mul_one_sub_eq_zero_iff.mp hM with h' | h' <;> simp [h, h']

  ProverAssumptions r _ _ := Honest r

  completeness := by
    circuit_proof_start [main, isBit, AddBus, MulBus, Honest]
    obtain ⟨hA, hM, hAM, hadd, hmul⟩ := h_assumptions
    refine ⟨mul_one_sub_eq_zero_iff.mpr hA, mul_one_sub_eq_zero_iff.mpr hM, ?_,
      fun h => hadd (neg_inj.mp h), fun h => hmul (neg_inj.mp h)⟩
    rcases hA with h | h <;> rcases hM with h' | h' <;> simp_all

With each selector known to be 0 or 1, a case split on the two bits closes the obligation, and the same split appears inside soundness, where Clean asks for it again. The rest of soundness projects the sum or the product out of each inherited guarantee, with neg_inj converting between -is_add = -1 and is_add = 1. Completeness goes from Honest to the five obligations, where the two pulls require exactly the conditional facts Honest carries. The constraint is_add * is_mul = 0 is part of the instruction encoding a real CPU wants, and no proof in the file depends on it: a row that selected both would pull both messages and satisfy both halves of Spec.

That is the division of labour. Lean proves that the adder pushes only correct sums, that the multiplier pushes only correct products, that the CPU's honest rows pull only messages an honest provider can supply, and that a CPU row holds the right result provided the message it pulled was in fact pushed by somebody. Whether every pulled message was pushed is the balance of the bus, which the lookup argument enforces inside the proof system and which Lean takes as a premise. Whether the prover fills the byte table with the right 256 values, or evaluates the polynomials of main correctly, is outside both.

7. The machine

Every per-table proof is conditional. The adder's soundness assumes that the bytes it pulled were provided, and the CPU's assumes that the message it pulled from ADD was pushed by somebody who proved the guarantee. The ensemble is where the conditions are discharged. Its theorem is that if every table's constraints hold on every row and every bus balances, then every table's Spec holds on every row. Its proof is an induction over the tables in dependency order: a table whose buses are all finished gets its hypotheses from balance and from the soundness of its providers, and its own soundness then finishes the buses it provides. The induction is written once, in the library. What a model supplies is the list of tables in an order, and two obligations per table:

def ensemble : SoundEnsemble (F p) unit :=
  SoundEnsemble.empty (F p) unit
  |>.addTable ⟨pushStatic byteTable⟩
      (by rw [pushStatic_channelsWithGuarantees]; simp)
      (by simp [circuit_norm])
  |>.addFinishedChannel Byte.toRaw
  |>.addTable ⟨Adder.circuit⟩
      (by simp [circuit_norm, Adder.circuit, byteTable])
      (by simp [circuit_norm, Adder.circuit, AddBus, byteTable])
  |>.addFinishedChannel AddBus.toRaw
  |>.addTable ⟨Multiplier.circuit⟩
      (by simp [circuit_norm, Multiplier.circuit, byteTable])
      (by simp [circuit_norm, Multiplier.circuit, MulBus, AddBus, byteTable])
  |>.addFinishedChannel MulBus.toRaw
  |>.addTable ⟨Cpu.circuit⟩
      (by simp [circuit_norm, Cpu.circuit, AddBus, MulBus])
      (by simp [circuit_norm, Cpu.circuit, AddBus, MulBus])

The first proof of each addTable is that every channel the table pulls from is already finished, so that its providers are all in. The second is that the table pushes to no channel already finished, so that marking it finished was not premature. Both are simp on the definitions, and both fail if the tables are listed in the wrong order. That is what Lean knows about the structure of the machine: the dependency graph is acyclic, the only table that pushes to ADD is the adder, and the only one that pushes to MUL is the multiplier, which are facts that in most codebases live in a comment.

Two things a real VM has do not fit this picture as is. A channel that a table both pulls from and pushes to, like the memory or the register state, has no finishing point, and Clean has a separate construction for that case. A precomputed table has no main of its own, and a flat AIR has no fixed columns to hold its entries, so it enters the ensemble as a component whose row carries one multiplicity per entry and pushes the whole list at once. That is pushStatic byteTable in the first line. Its Spec is True, since it establishes nothing about its own row, and its soundness is guarantees_iff read from right to left: every entry is in the list, so every entry satisfies the guarantee.

The theorem is stated about a witness, the concrete trace of the whole machine, one table per component with its rows as arrays of field elements:

theorem cpu_rows_correct (witness : EnsembleWitness ensemble.ensemble)
    (hc : witness.Constraints) (hb : witness.BalancedChannels) :
    ∀ table ∈ witness.tables, table.component = ⟨Cpu.circuit⟩ →
      ∀ row ∈ table.table, Cpu.Spec (valueFromOffset Cpu.Row 0 (table.environment row))

hc says that every table's main holds on every one of its rows, and hb that every channel balances. The conclusion is that every row of the CPU table satisfies Cpu.Spec. Along the chain, the byte table pulls from nothing, so its pushes meet the BYTE guarantee outright. Balance on BYTE gives the adder and the multiplier the bounds their proofs assumed, their soundness makes every message on ADD and MUL meet its guarantee, and balance on those two gives the CPU its hypotheses.

Stated plainly, the theorem says that if the constraints hold on every row and every bus balances, every CPU row holds the right result. What the proof system establishes on its side is that a verifier who accepts a proof has seen the constraints hold and the buses balance, up to its soundness error. The two compose into the statement that matters, and each half is established by a different method. Lean proves the first entirely and does not prove the second: balance is a hypothesis of the theorem, not a conclusion, and the type of the theorem says so.

8. What it can and cannot say

What you get from a theorem of that shape: every table does what its specification says, on every row that satisfies its constraints, and not only on the rows somebody tested. The tables fit together, because each one assumes exactly what its providers prove. And the honest rows do satisfy the constraints, so the system is not sound merely by being impossible to satisfy.

What you do not get is just as clear. The proof does not say the specifications are the right ones; that is for a reviewer, and the point of the method is to keep that review short, five lines for the toy machine and a few hundred for a real one. It does not say the Lean circuit is the one the prover runs; that is checked outside Lean, with a differential test or by extracting the circuit from the code. It does not say the lookup argument, the commitment scheme or the low-degree test are sound; that is the proof system's problem. And it says nothing about whether the prover's code computes the right values.

What it settles is the question in the middle: if the constraints are satisfied, the properties written in Spec follow. That is the part of the problem Lean can take on directly, and it settles it for good.

The toy machine is at clean_examples. It builds with lake build against a pinned revision of Clean, and every theorem in it depends only on Lean's standard axioms.