Formal verification

Machine-checked
from state to proof.

The path from a state change to an accepted GKR proof is modeled and machine-checked in Isabelle/HOL, and a refinement theorem connects the shipped Rust verifier to that model under stated conditions.

No admitted proofTheorems A to D are machine-checked in Isabelle/HOL, and all 20 proof files are rebuilt from clean on each push to the maintained branch.
All three operationsIn the compiler model, record present, absent and updated each compile to a circuit that accepts exactly the valid cases, proved in both directions.
One boundA machine-checked limit, in the model, on how often an invalid state change gets through. Its GKR part is proved over the exact field the verifier draws its challenges from.
Tied to the codeA refinement theorem connects the shipped Rust verifier to the model under stated conditions, and contracts anchor selected code clauses to the model in four areas.

Why it matters

One test, one case.
One theorem, every case.

A test checks the cases someone thought to try. A machine-checked theorem covers every case in its scope, including the ones nobody thought of. For StateSync-GKR, Theorem A covers every claim and witness of all three operations, in the compiler model.

TestingOne case per test

A test runs the shipped code on one case that someone wrote down and checks the outcome.

Shipped Rust code · chosen inputs

Record presentMembership

Record absentNon-membership

Record updatedUpdate

Inputs outside the suite stay unchecked.

Theorem A · machine-checkedEvery case in one proof

In the compiler model, each operation compiles to a circuit that accepts exactly the valid cases, over empty, occupied and deleted leaves, for every claimed root and every witness.

Compiler model · every input

Record presentMembership

Record absentNon-membership

Record updatedUpdate

Shipped Rust verifier

Connected to the model by a refinement theorem, under stated conditions.

An illustration with two panels of the same cases, in three bands, one for each operation: record present, record absent and record updated. Each cell stands for one case: an operation, the roots it claims and a witness. In the testing panel, framed as the shipped Rust code with chosen inputs, nine tests light nine cells one at a time, some valid and accepted, some invalid and rejected, and every other cell stays unchecked. In the theorem panel, framed as the compiler model with every input, one wave decides every cell, valid cases accepted and invalid cases rejected, out to the edge of the drawing, where the cases continue. A dashed link from that model leads to the shipped Rust verifier, which a refinement theorem connects to the model under stated conditions.

Illustration: each cell stands for one case, an operation with the roots it claims and a witness (the record and its Merkle path), and the cases run on past the edge. Tests run the shipped code on chosen inputs, while Theorem A covers every input of the compiler model, with the hash sub-circuits as abstract functions. The protocol theorem holds against every prover strategy as a probability bound, in the interactive model with uniformly drawn challenges. The refinement theorem that connects the shipped Rust verifier is described under Refinement below.

95 of 141vulnerabilities in SNARK implementations were under-constrained circuits, in one published survey.

What tests can miss

Under-constrained circuits account for 95 of the 141 vulnerabilities in SNARK implementations that Chaliasos et al. systematized at USENIX Security 2024. A circuit that omits a constraint accepts some invalid updates, and the protocol then proves the false statement with probability one. The compiler still produces circuits, proofs and acceptances, so no test has to fail.

In the compiler model, with the hash sub-circuits as abstract functions, Theorem A's soundness direction rules this out for all three operations, and its completeness direction rules out the opposite flaw, a circuit that rejects valid updates.

Trust chain

From a state change
to a verified proof.

Theorem A ties the circuit to what a state change means. Theorem B bounds how often a false claim survives the GKR protocol. Theorem C joins the two, so in the model an invalid state change gets through only within a proved bound.

Over the exact , the field, its size, each layer's lifting and Theorem B are machine-checked. Lifting the whole chain and composing across the two fields are paper steps. The shipped Rust verifier joins through a separate conditional theorem, under Refinement below.

Refinement

Tied to the Rust code,
under stated conditions.

A model matters only if the shipped code follows it. StateSync-GKR connects the two in two ways and states how far each connection reaches.

Verifier acceptance refinement

A theorem proves that every run the shipped Rust verifier accepts lies inside the event the GKR soundness theorem bounds, given a stated correspondence between the verifier's values and the model.

The bound is the one the GKR theorem proves. The documentation gives the exact statement and its premises.

  1. Theorem Acircuit-acceptance definitions
    R1 Compiler

    Layout, length, index and domain clauses, such as the input-vector layout below.

    compiler cratesemantics, compiler, leaf encoding
  2. Theorem Breduction chain, AFP round-step law
    R2 Protocol

    Round counting, rejection paths, transcript order and the final claim run as translated code.

    sumcheck and protocol cratesrounds, claim threading, two-point carry
  3. Theorem Cthe merged locale
    R3 Composed verification

    Public-side checks and operation keying of the composition facade.

    facade modulepublic entry points
  4. Hash functionsabstract parameters of the model
    R4 Opaque primitives

    Interface correspondence only, with no claim about hash values.

    hash-gadget traitinterface to the hash sub-circuits
Explicitly partial

A contract clause exists only where a model clause anchors it. Code without an anchor counts as trusted, not as verified.

Declared trust surface

Claim-bearing trusted annotations sit only at the library boundary.

Treated as black boxes
  • p3-field
  • p3-koala-bear
  • p3-challenger
  • p3-poseidon2
  • p3-symmetric
  • Rust / LLVM
  • OS
One contract, as written

The compiler's input layout, restated from the model.

This contract on the constructor of the compiler's input-vector layout restates, segment by segment, the layout that the compiler model defines. Its precondition carries only machine-width bounds, which the model, stated over unbounded natural numbers, does not need.

crates/compiler/src/compile.rs · R1, abridged
#[requires(depth@ <= 0xFFFF && leaf_max_fields@ <= 0xFFFF)]
#[ensures(result.kind == kind && result.depth@ == depth@)]
#[ensures(kind != SmtOpKind::Update ==> !result.l_has_second()
    && result.l_leaf_pre() == 0
    && result.l_acc() == result.l_leaf_lanes()
    && result.l_sib() == result.l_leaf_lanes() + 8 * (depth@ + 1)
    && result.l_key_bits() == result.l_leaf_lanes() + 8 * (2 * depth@ + 1)
    && result.l_root() == result.l_leaf_lanes() + 8 * (2 * depth@ + 1) + depth@
    && result.l_value_digest() == result.l_root() + 8
    && result.input_width@ == result.l_value_digest() + 8)]
pub fnnew(kind: SmtOpKind, depth: usize, leaf_max_fields: usize) -> Self

Contracts are written in and checked through Why3 with automated solvers. The listing is abridged: its configuration wrappers and the update-branch clause are omitted.

Scope

What the verification covers.

  • Sparse-Merkle semantics, the circuit compiler and GKR assembly are modeled and composed in Isabelle/HOL.
  • The GKR soundness bound is proved over the exact extension field the verifier draws its challenges from, with each base-field layer lifted into it.
  • The Rust code is tied to the model by contracts in four scopes and a conditional acceptance refinement theorem, and differential and adversarial tests check it alongside them.
  • Every registered proof session is rebuilt from clean on each push to the maintained branch and weekly.

Each result is stated with its assumptions in the formal verification paper and the documentation, so an integrator can see exactly what an accepted proof rests on.

The development

Six sessions,
one reusable core.

The general GKR session knows nothing about sparse Merkle trees, so a new workload inherits the composition by proving only its own compiler theorem.

Archive of Formal ProofsSumcheck_Protocol

Per-round sumcheck soundness, imported from its machine-checked AFP entry.

General layerGKR_Protocol

Circuits, multilinear extensions, sumcheck, the assembly bound, batching and the verifier bridge. It knows nothing about sparse Merkle trees.

Theories
8
Lines
5,525
Named results
197
  • Layered_Circuit

    gates, layers, evaluation, acceptance

  • Multilinear_Extension

    equality kernel, multilinear extensions

  • Wiring_MLE

    wiring predicates, oracle equivalence

  • Sumcheck_InstanceAFP import

    layer integrand on the AFP entry

  • Layer_Representative

    interpolation representative, degree bound

  • GKR_AssemblyTheorem B

    chain event, assembly bound

  • Verifier_Acceptance_RefinementConditional refinement

    acceptance trace, conditional refinement

  • GKR_BatchingTheorem D

    batching contract

Sparse-Merkle specializationSMT_Circuit_Compiler_Correctness

Adds the meaning of a state change, the compiler model, the composition and concrete instances over the production field.

Theories
8
Lines
4,343
Named results
166
  • SMT_Semantics

    sparse-Merkle states and operations

  • Leaf_Fold

    leaf encoding, injectivity, collision reduction

  • Compiler_Model

    residual constraints, input layout

  • Compiler_CorrectnessTheorem A

    acceptance equals validity

  • CompositionTheorem C

    merged locale

  • KoalaBear_Field

    prime field type, primality

  • Compiler_InstanceInstance

    compiler activations over KoalaBear

  • Composition_InstanceInstance

    composition activation

Exact extension fieldFour sessions in a chain

Each imports only its predecessor: certificates, the field, the lifting, then the protocol instance.

Theories
4
Lines
1,244
Named results
55
  1. KoalaBear_Ext4_Nonsquare

    nonsquare certificates

  2. KoalaBear_Ext4_Field

    quadratic tower, size p⁴, embedding

  3. KoalaBear_Ext4_Lift

    lifting polynomials, circuits, false outputs

  4. KoalaBear_Ext4_GKRTheorem B · exact field

    extension-field instance, pushforward

In session names, SMT abbreviates sparse Merkle tree.
6registered sessions: two core sessions and a four-session chain for the exact field.
20theories, each inside the build of its own session.
11,112lines of Isabelle/HOL theory text.
418named results: 384 lemmas, 23 theorems and 11 corollaries.
0sorry, oops, axiomatization or oracle declarations in any theory.
14m 31sto rebuild all six sessions from clean on a hosted four-thread runner, library heaps cached.

Counts are taken from the released theory sources; the rebuild time is the hosted clean build of 14 October 2026.

Research

Two papers, two kinds of evidence.

One paper reports the machine-checked argument and the other measures the engine, each with the conditions its results rest on.

Formal verification

Soundness of the GKR Protocol for Sparse-Merkle Updates, with a Machine-Checked Core

Extends the Isabelle/HOL sumcheck formalization to the full GKR layer chain and composes it with a proof that, in the compiler model, the circuits accept exactly the valid state operations. The GKR bound is carried to the exact extension field the verifier uses.

Formal verification paper · arXiv:2610.05335 (opens in a new tab)
Design and evaluation

StateSync-GKR: Design and Evaluation of a Reusable Sparse GKR Engine

Connects the nine design mechanisms to controlled measurements of memory, preparation, verification, parallel proving and serving under load.

Design and evaluation paper · arXiv:2610.14849 (opens in a new tab)
Independent review

Bernhard Müller (opens in a new tab) wrote the independent review of the verifier's challenge-generation assumptions (opens in a new tab), which is part of the source repository.

Security researcher. Creator of Mythril, the security analysis tool for Ethereum smart contracts, an author of the OWASP Mobile Application Security Testing Guide, and a 2009 Pwnie Award winner for Best Research.