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.
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.
A test runs the shipped code on one case that someone wrote down and checks the outcome.
Record presentMembership
Record absentNon-membership
Record updatedUpdate
Inputs outside the suite stay unchecked.
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.
Record presentMembership
Record absentNon-membership
Record updatedUpdate
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.
95 of 141vulnerabilities in SNARK implementations were under-constrained circuits, in one published survey.
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.
- Machine-checked in Isabelle/HOL
- Paper step over machine-checked parts
- Conditional theorem with a stated premise
Over the exact extension field (glossary), 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.
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 soundness (glossary) theorem proves. The documentation gives the exact statement and its premises.
- Theorem Acircuit-acceptance definitionsR1 Compiler
Layout, length, index and domain clauses, such as the input-vector layout below.
compiler cratesemantics, compiler, leaf encoding - Theorem Breduction chain, AFP round-step lawR2 Protocol
Round counting, rejection paths, transcript order and the final claim run as translated code.
sumcheck and protocol cratesrounds, claim threading, two-point carry - Theorem Cthe merged localeR3 Composed verification
Public-side checks and operation keying of the composition facade.
facade modulepublic entry points - Hash functionsabstract parameters of the modelR4 Opaque primitives
Interface correspondence only, with no claim about hash values.
hash-gadget traitinterface to the hash sub-circuits
A contract clause exists only where a model clause anchors it. Code without an anchor counts as trusted, not as verified.
Claim-bearing trusted annotations sit only at the library boundary.
- p3-field
- p3-koala-bear
- p3-challenger
- p3-poseidon2
- p3-symmetric
- Rust / LLVM
- OS
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.
#[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) -> SelfContracts are written in Creusot (glossary) 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.
Sumcheck_ ProtocolPer-round sumcheck soundness, imported from its machine-checked AFP entry.
GKR_ ProtocolCircuits, 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_AFP importInstance layer integrand on the AFP entry
Layer_Representative interpolation representative, degree bound
GKR_Theorem BAssembly chain event, assembly bound
Verifier_Conditional refinementAcceptance_ Refinement acceptance trace, conditional refinement
GKR_Theorem DBatching batching contract
SMT_ Circuit_ Compiler_ CorrectnessAdds 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_Theorem ACorrectness acceptance equals validity
CompositionTheorem Cmerged locale
KoalaBear_Field prime field type, primality
Compiler_InstanceInstance compiler activations over KoalaBear
Composition_InstanceInstance composition activation
Each imports only its predecessor: certificates, the field, the lifting, then the protocol instance.
- Theories
- 4
- Lines
- 1,244
- Named results
- 55
KoalaBear_Ext4_ Nonsquare nonsquare certificates
KoalaBear_Ext4_ Field quadratic tower, size p⁴, embedding
KoalaBear_Ext4_ Lift lifting polynomials, circuits, false outputs
KoalaBear_Theorem B · exact fieldExt4_ GKR extension-field instance, pushforward
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.
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)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)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.