Research
ReleaseNockchain Research36 min read

The Open Proof Machine: a Nock zkVM with an end-to-end soundness proof

We built the Open Proof Machine (OPM), Nockchain’s zkVM for Nock, whose verifier is proved sound in Lean, from the rules of the language down to the bytes the verifier reads, and whose arithmetization is also proved complete. This report explains what that means, how the proof is put together, what it builds on, and where it stops.

The results, in one sentence each

  1. ≈2−81.4

    soundness error

    Soundness, end to end. No adversary, however much it computes, gets the verifier to accept a false Nock claim with probability above about 2−81.4, within 264 hash and Fiat–Shamir queries (Theorem 3) kernel. The main term is proved for every query budget Q: at most Q · 2−147 + 2−144 + 2−146 (Section 11) kernel

  2. <2−155

    arithmetization soundness error

    Full Nock. All twelve opcodes, unbounded atoms with big-atom arithmetic on operands up to 1,984 bits, and jets. For a faithful jet registry and tables of at most 231 rows, the arithmetization is proved sound with error below 2−155 over the verifier’s ideal coins, for any prover, and the kernel shows that figure is tight for its accounting (Theorem 1) kernel

  3. <2−120

    bad coins

    Completeness of the arithmetization. An honest run within stated bounds is accepted at every good , and the bad coins have measure below 2−120 (Theorem 2) kernel

  4. 1

    command

    A certified verifier. Checking a proof is one command. Its verdict logic is a kernel-checked Lean function, and a theorem ties its verdict on the bytes of a proof to the soundness theorem (Theorem 5) kernel: an accept gives the instance-side hypotheses of the bound and the claim, while the side numeric conditions, the bound on the side key’s size and the query budgets remain hypotheses of the bound. What is trusted is the standard compilation path and a few lines of input and output, as for any verified software built without a verified compiler.

  5. 1

    modelling gap

    Every link is a theorem, in the random-oracle model. From the arithmetization to the bytes the verifier reads, each step is a kernel-checked theorem with an explicit numeric bound under named hypotheses, about the function the shipped executable runs, at its shipped configuration. As is standard, the hash is modelled as a random oracle, here taken to yield uniform query positions directly; the executable derives them within 2−64 of uniform, a gap that can be sharpened (Section 19). Statements are fixed in advance. The certified verifier carries the theorem down to the bytes it reads; only its file reading, the Lean compiler and runtime, and the C toolchain are trusted (Section 16).

All are checked by the Lean 4 kernel; every cited theorem whose #print axioms line the release records depends only on the standard axioms propext, Classical.choice and Quot.sound. The proof is not zero-knowledge, is non-adaptive and lives in the random-oracle model (Section 19).

Part I

The idea, in plain words

01

Why a proof about the verifier

Some systems use proofs as money. A blockchain that accepts a proof of a computation instead of re-running it pays out on the strength of that proof. If the verifier can be fooled into accepting a proof of something false, it will pay out for something that never happened. A soundness bug in a verifier is a counterfeiting bug.

Such bugs are not hypothetical. Chaliasos et al. analysed 141 real vulnerabilities in SNARK implementations [2], and the patterns they record are simple to state: a value the prover controls that no rule constrains, a range that is never checked, or a piece of data left out of the hash that is supposed to bind the proof to its statement. Each of these is a rule that should have been there and was not. Audits catch some, and tests catch some. But an attacker with automated tools can search for the one that was missed far faster than any audit can look, and a guarantee that depends on the auditor being thorough enough weakens as attackers get stronger.

A machine-checked proof works differently. It is a theorem, checked by a small trusted program, that says: whatever the prover sends, if the verifier accepts, the claim is true, except with a stated, tiny probability. A missing rule is not a bug the theorem might miss; it is a step of the proof that does not go through. (The theorem is only as good as the definitions it is about, which is why we list them in the trusted base.) And the guarantee does not depend on how strong the attacker is: it holds against any adversary within the stated query budget, however it was built.

02

What a zkVM does

A program runs; someone wants to convince everyone else of its result without everyone re-running it. The prover runs the program and writes down everything that happened, step by step, in large tables of numbers. It then turns those tables into a short proof. The verifier reads the proof, does a small amount of work (it checks the tables at under two hundred random positions, not the whole run), and answers accept or reject.

Why are so few spot checks enough? Because the tables are not checked as raw numbers. They are encoded as polynomials, and polynomials have a useful property: two different low-degree polynomials agree on very few points. So if the prover cheats anywhere, the cheat spreads through the encoding, and random spot checks catch it with overwhelming probability. The randomness comes from hashing what the prover has already sent, so nobody has to be online to supply it.

Fig. 1Spot checks on an encoded table
The table · 8 rows

Each row is the sum of the two before it. Click a row to change it.

Its encoding · 32 evaluations of one polynomial of degree < 8
95
73
80
45
24
3
63
18
38
81
79
6
9
53
69
41
75
50
76
28
2
78
54
93
46
92
33
46
56
12
85
68

This is the honest encoding. Nothing is changed yet.

Spot checks4

An honest table passes every check.

Run the checks to see the verdict.
Figure 1. A toy over the 97-element field. Eight rows of a table are encoded as one polynomial of degree below 8, evaluated at 32 places. Change any row and the encoding changes almost everywhere, so a random check is likely to land on a changed place. The real checks are the constraint and low-degree tests of Part III; the shipped verifier makes 170 of them.

That is the whole idea. Everything else is making it exact: which tables, which rules, which spot checks, and how small “overwhelming” really is.

The end point we are building towards is simple to say. A single verifier program, which anyone can run on a proof, whose “accept” is backed by a theorem: not by trust in the people who wrote it, and not by an audit, but by a proof the Lean kernel has checked. This report describes the theorem. The release also ships that program, nockvm-e2e-verify-cert, the certified verifier of Section 16. Its verdict logic is the kernel-checked Lean function itself; what remains is the standard trust of any verified software built without a verified compiler: Lean’s compiler and runtime, the C toolchain, the few lines that read the input files and print the verdict, and the meaning of the input parser.

03

Nock in twelve rules

Our VM runs Nock, a tiny combinator language. It has one data type, the noun: either an atom (a natural number of any size) or a cell, a pair of two nouns. A program is a formula applied to a subject, and twelve opcodes define it:

Fig. 2The twelve rules of Nock, with an interpreter
OpFormula and meaning
  • Rule 4: add one to an atom.

    Result2 steps

    43

    Evaluation steps
    1. 14*[42 [4 0 1]]43
    2. 20*[42 [0 1]]42
Longer runs
Figure 2. Choose a rule to run an example of it, or type any subject and formula. Marks at the end of a row count how often that rule fired in the run. The interpreter runs in your browser on atoms of any size, follows the release’s reference interpreter rule for rule, crashes included, and stops after 4,000 steps. The prover records a run like this as an execution tree, one node per evaluation step (Section 6).

Two features make Nock harder to prove than a typical VM. Atoms are unbounded, so numbers far larger than any machine word must be handled exactly. And real Nock programs rely on jets: known formulas, such as addition or multiplication of large numbers, that an interpreter replaces with native code. A proof system for real Nock has to cover both, and this one does.

04

The pipeline at a glance

The proof is a chain of layers. Each takes a guarantee from the layer above and hands a stronger, more concrete one to the layer below, until the last layer talks about the bytes the verifier actually reads.

Fig. 3The layers of the proof

The rules of Nock

  1. Layer 01 of 12

    Semantics

    the prover’s step-by-step record really is a run of Nock.

    Checked by the Lean kernel

The bytes the verifier reads

  • A theorem checked by the Lean kernel
  • Standard trust, not proved
Figure 3. Each layer takes a guarantee from the one above and hands a more concrete one to the one below. Eleven of the twelve are theorems checked by the Lean kernel; the last, the compiled binary, is standard trust. Select a layer to see what it says and where it is stated.

Every row except the last is a theorem checked by the Lean kernel. The rest of this report goes down the table, from here on in the language of a formal paper.

Part II

The machine

05

Preliminaries

Field and extensions. Let p = 264 − 232 + 1 (the Goldilocks prime). Challenges are drawn from a cubic extension K ⊇ Fp with |K| = p3, and records are compressed in its quadratic extension K′ = K(√ν). The library’s statements take any K with |K| = p3; the executable uses K = Fp[X]/(X3 − 7) with ν = 7. (The Lean calls the non-residue δ; we write ν to keep δ for the FRI proximity parameter.)

Nouns and claims. A noun is an atom n ∈ ℕ or a cell [a b] of nouns. The semantics is a fuel-indexed reference interpreter evalN : ℕ → Noun → Noun → Option Noun (evalN), where none is a crash (for example, a formula whose head is an atom it cannot run) or exhausted fuel. evalN is written directly from the Nock 4K specification.

Definition 1claim

A claim is a triple c = ⟨s, f, r⟩ of nouns. It holds, written HoldsN c, if evalN fuel s f = some r for some fuel (HoldsN).

Every soundness statement below bounds the probability that a verifier accepts while HoldsN c fails. A jet call is the hint [11 [n clue] c], where n is a registered id for c; semantically the hint is transparent: once the clue returns, the hint evaluates as c with one unit of fuel more (evalN_hint_jet), so a jet is sound exactly when its implementation agrees with c under evalN.

Chips and RAPs. A chip is a table whose columns are interpolated as polynomials over a multiplicative subgroup (the orbit) of Fp, with polynomial constraints of total degree at most 4 in the current and next row. Columns come in rounds; a later-round column may depend on challenges drawn after the earlier rounds. These are randomized AIRs with preprocessing (RAPs), as defined in [1].

Definition 2LogUp balance [10]

A record r = (r0, …, rm−1) is compressed to κ(r) = ρ + Σj γj rj ∈ K′ at coins ρ, γ. A provider row with multiplicity μ adds μ/κ(r) to an accumulator column; a consumer row adds w/κ(r). A channel balances when the verifier’s linear equation between the accumulators’ terminal values holds.

Outside a set of coins of small measure, a balance implies that every consumed record is a provided record; the measure is priced in Theorem 1. The lookup lemma allows arbitrary provider multiplicities and needs only that the number of consumed records is below p (finiteIO_lookup_sound_weighted) kernel.

Definition 3staged prover

A prover map Q : Coins → Traces is staged if every round-i column depends only on the coins drawn before round i.

06

The machine and its tables

Execution trees. The honest prover runs a generator that returns an execution tree and a result: one node per evaluation step, in one of 17 states (opcodes 0–9, autocons, three edit states, three hint states); the big-axis system’s compute twin adds three one-hot states (a big or field axis in op 0, a big axis in op 10, and a segment pseudo-row). A registered jet call becomes a jet node with one child, the clue; the jet body is not expanded. For a faithful registry the generator is sound and complete against the interpreter, completeness at the same fuel (genX_sound, genX_complete).

Fingerprints. A noun’s fingerprint is a triple over K′: the monomial z#leaves, its Dyck word evaluated at a structure coin z, and its leaf polynomial at z, where a big atom’s leaf value is its limb polynomial Σi ℓi yi at an independent limb coin y.

Proposition 1kernel-checked

With one coin for both roles, there are distinct nouns whose fingerprints collide at every coin (sameCoin_collision) kernel.

So the two independent coins are necessary, not a convenience.

Fig. 4Noun fingerprints with one coin and with two

Same fingerprint

Noun A[a 0]
521LIMBS0ATOM
Size
47
Structure
12
Leaves
76
Noun B[b 1]
511LIMBS1ATOM
Size
47
Structure
12
Leaves
76
Structure coin z12
Limb coin y12 (= z)
Every value of the one coin96 of 96 collide

The second limb of each atom is multiplied by the same coin as the tail of the cell, so moving 1 from the limb to the tail changes nothing: the leaf values are equal at every coin. No amount of randomness separates these two nouns.

Figure 4. Proposition 1 with numbers. The two nouns are the pair in the Lean proof of sameCoin_collision: different nouns whose fingerprints agree at every coin when the limbs and the structure share one. With a separate limb coin they agree only when the two coins happen to be equal. Shown over the 97-element field so the numbers fit on screen; the theorem is stated for any field.

Chips. The base system has six chips; their widths are kernel facts. The ALU system that the theorems below cover keeps five of them, widens the compute chip to 137 columns, and adds an axis chip (52 columns), a split chip for big atoms (90 columns) and the ALU. The figure shows the base chips and the ALU.

Fig. 5The chips and their LogUp channels
LogUp channel
  1. compute

    one row per execution-tree node: one-hot state, twelve noun handles, increment and comparison witnesses

    123
  2. cell table

    one row per distinct cell (hash-consed), with a rank

    242
  3. cell walk

    certified reads at an axis through cells

    166
  4. J chip

    straight-line interpreter for jet templates

    71
  5. atom table

    big atoms as limb lists in base 232; increments

    349
  6. atom walk

    limb reads for op 5 on big atoms

    166
  7. ALU

    add, sub, lt, mul, div, mod on atoms of up to 62 limbs (1,984 bits)

    196

columns

Five LogUp channels tie the chips together: handle export, path, service, cell validity and atom export.

Figure 5. Bars are drawn to each table's width in columns. Select a channel to see which tables its balance ties together: a record one table provides has to be a record another consumes. Membership is read from the balance equations of the specification.

Each cell row carries a rank equal to one plus the sum of its children’s ranks (an inline atom has rank 0), and every accepted row has rank at least 1 (cellRow_rank_pos); on a table that satisfies these row and child constraints, every row of rank n decodes to an actual finite noun with n + 1 leaves whose encodings match the row (decodeTree_sound) kernel, which rules out cyclic “nouns”; that an accepted balance yields such a table is inferred. Walks bound path length by 60 (walkJ8_len_le_60). Increment has a fast path for small atoms and a slow path certified by a carry chain (inc_chain_sound). Five LogUp channels tie the chips together: handle export, path, service, cell validity and atom export.

Jets and the ALU. Non-primitive jets are compiled templates run on the J chip; each registered id must map to its compiled, well-typed template, a check that is part of the verifier predicate. Big-atom primitives run on the ALU: each operation’s identity is a sum of per-slot contributions evaluated at the limb coin, so a false operation survives only with Schwartz–Zippel probability. A primitive registered at another operation’s specification has no accepting instance (opConfusion_rejected). The ALU’s next-row gates are multiplied by 1 − isLT, a verifier-fixed last-row mask, so an honest table is accepted at every orbit that fits (genJ9ALXJ_honest_at').

Four nested systems. The library proves its results for four verifier predicates, each extending the previous one: the base system; big claim atoms; big axes (op-0 and op-10 axes up to 62 limbs); and the ALU system. Each has its own soundness theorem (probJ8V_final_clean, probJ9B_final_clean, probJ9A_final_clean, probJ9AL_final_clean); the larger systems add premises such as a leaf bound and 231 axis and split rows. We display the ALU theorem, which the end-to-end theorem uses.

07

How the input and output are bound

A verifier is only as sound as its handling of what comes from outside. Each external input is tied down as follows.

  1. 01

    The claim is never taken from the prover.

    The verifier computes the claim’s records from the public subject, formula and result and pins them into the cell-validity balance. A claim atom of any size gets a big-atom handle and one extra record.

  2. 02

    Statement binding.

    In the ALU and template-jet verdicts, the Fiat–Shamir statement z must begin with a fixed encoding of the public input. (The jet-free big-axis verdict does not check this.)

    Definition 4statement binding

    zBind(pubIn, z) holds when z starts with zHdr(pubIn) = tag :: encPub(pubIn) (zBind).

    Lemma 1kernel-checked

    encPub is injective and prefix-free (encPub_inj, encPub_pf); hence a statement binds at most one public input (zBind_inj) kernel.

  3. 03

    Constraint tables.

    The chip files are untrusted input. The verifier accepts a chip only if it equals one of a fixed list of Lean literals, and each literal is tied to its specification by decide +kernel: same shared sub-expressions, constraint expressions, base columns and width (tieB). There are seventeen literals for the base and big-axis tables and one for the ALU; the ALU literal is tied by split checks of the same kind in J9ALChipsK_alu.

  4. 04

    The verification key.

    Setup is transparent: the key is a deterministic Lean function of the instance (the fixed columns and the Merkle root of their extensions). The verifier nockvm-e2e-verify-fam in its verify --vk mode recomputes it and rejects a differing key file (plain verify checks the main proof only); a side proof opens the fixed columns against its root (verdict9LVS_sound).

08

The arithmetization is sound and complete

Theorem 1algebraic soundnesskernel-checked

Fix public data Pb, a faithful registry Rg, a claim c, a staged prover map Q, and row and id budgets r, g within the bounds below. Then

Prχ [ ∃ M : Accepts(Pb, Rg, c, χ, M, Q(χ), r, g) ∧ ¬HoldsN c ] < 2−155,

where χ ranges over the verifier’s coins and M over all prover messages (probJ9AL_final_clean) kernel.

The budgets are premises: at most 231 rows per table, 231 registered ids, a census of at most 231 nouns, and in the ALU system 231 ALU rows. The proof (prob_le_of_outside) covers the coins by a list of bad events, each priced by a union bound, and shows that outside all of them acceptance implies HoldsN c: every consumed record is a provided record (lookup inclusion), the tables decode to actual nouns (from the balances, inferred as in Section 6), the walks give genuine reads, each jet call holds (jetChip_holds), each compute row satisfies the local evaluation step (local_stepX), and the root of the execution tree is the claim. The event list is exposed as one-round events (oneRound_listJ9AL), which is what the Fiat–Shamir step in Section 10 consumes.

The figure 2−155 is tight for this accounting: at the budget corner, the quantity the proof bounds the sum of the bad events by is not below 2−156 (numJ8X_optL_not_156). We claim no matching attack.

Theorem 2completenesskernel-checked

Let a run of the generator satisfy the run binders below, with a verified registry, and let B be the honest record built from it. Then B’s traces are staged, the claim holds, and the predicate accepts B at every good coin; the bad coins have measure below 2−120, so an accepting coin exists (complJ9AL_closed) kernel.

The run binders: axes, edit levels and jet ids below p, including op-9 axes and the axes inside registered templates (only op-0 and op-10 axes may have up to 62 limbs); the first differing axis of every op-5 comparison below p; walked roots with at most 2109 leaves; path depth at most 61; at most 231 rows per table; registered templates well typed; primitive ids distinct and registered at their specifications; operands of at most 62 limbs; and no dec primitive (proved faithful, but with no ALU operation code; the ALU covers add, sub, lt, mul, div and mod). For the code path, the executable checker accepts the generator’s input at a good coin (checkJ9ALX_genJ9ALXJ), and good coins exist in executable form (exists_good_coinEJL).

The completeness theorem is instantiated at concrete programs with every binder discharged by the kernel, including add, mul, lt and div on atoms such as 270 + 3 and 295 + 7; the soundness bound is read at 23 concrete false claims (wrapped additions, dropped carries, subtraction underflow, division by zero, forged comparisons), for every verifier datum that meets its regime conditions.

The library also proves trace uniqueness for a fragment (P1): except with probability below 2−119, an accepted record for a P1 claim is the canonical one (trace_unique_prob_119, under a size premise) kernel. The end-to-end theorem does not use it.

Part III

From tables to a succinct proof

09

What ArkLib provides, and what we added on top

The succinct layer is built on ArkLib [11], a Lean library for interactive oracle reductions, at upstream c488a3a4, and on VCVio [12], the oracle-computation framework beneath it.

ArkLib provides Reed–Solomon codes; FRI [4] and batched FRI with their round-by-round soundness; the oracle-reduction framework; and the single-salt Fiat–Shamir framework with its theorem singleSalt_knowledge_soundness. That framework is Quang Dao’s, from a stack of upstream pull requests (#1267, #1268, #1274 and #1277; the security theorem is from #1277) that were closed without being merged; we vendor its ten modules under the namespace ArkLibFs, with declarations and proofs as upstream. They are kernel-checked here, but not reviewed by ArkLib’s maintainers. VCVio provides multi-checkpoint Merkle extractability.

We added on top the on-ramp from our constraint system to ArkLib’s machinery (Section 10): the staged RAP as an ArkLib protocol; a transport from round-by-round soundness to single-salt Fiat–Shamir (NockvmE2E/Lift); FRI’s soundness re-derived around its acceptance predicate (FriPort); DEEP and its composition with FRI (Deep, Rap, Succ); the Merkle compilation in the random-oracle model (Merkle); the verification-key side proof; the numbers; the verdict functions; and the end-to-end theorems.

10

The on-ramp

Theorem 1 is a statement about polynomial traces and ideal coins. A deployed verifier sees Merkle roots, folded words and openings, and its coins are hashes of what the prover sent. Six steps carry the guarantee across.

Step 1 of 6

Constraints as a protocol

The staged RAP becomes an ArkLib protocol with one round per block of columns, followed by the coins drawn after that block. Theorem 1 enters pointwise: acceptance with no priced bad event implies the claim, and each bad event reads the coins of one block, so it is charged to one round (roundBound_rapJ_le). An aggregate bound would not suffice, because round-by-round soundness needs a per-round error.

Step 2 of 6

Fiat–Shamir

In the single-salt game the adversary chooses a statement, one salt, all prover messages and a witness, querying a lazy random oracle at any transcript prefix; the verifier recomputes the challenges from the same oracle. This is state-restoration security [6]. Round-by-round soundness [7] implies it, and Holmgren shows the two are equivalent [8]; the release uses only the direction from round-by-round soundness to the single-salt game, at the cost given below.

Lemma 2round-by-round to single-saltkernel-checked

For a verifier-first protocol whose rounds alternate challenge and message, with per-round errors errt, an adversary touching at most Q distinct fresh oracle keys succeeds with probability at most

Q · maxt errt + Σt errt

(singleSalt_soundness_of_rbrSoundness, stated for ArkLib’s legacy verifier interface; the accept-predicate form is singleSalt_soundness_of_stateFamily') kernel.

The cost is in fresh keys, not rounds. This is why the end-to-end bound is not 2−155: it grows linearly in Q.

Step 3 of 6

Batched FRI

ArkLib states FRI’s round-by-round soundness existentially, which hides the state function. We use its ingredients instead (the bad-event state function and the per-challenge bound), so that the final check is FRI’s acceptance predicate.

Lemma 3batched FRI, single saltkernel-checked

For a statement outside FRI’s input relation at distance δ (the input words have no common agreement set of density 1 − δ with degree-bounded witnesses), with l queries and proximity parameter θ, acceptance has probability at most

Q · max(ε, maxj challengeErrorj) + ε + Σi foldingErrori + (1 − min(θ, δ))l

where ε bounds the correlated-agreement error of the batching [9] (batchedFri_singleSalt_soundness) kernel.

Step 4 of 6

DEEP

Two further coins α, ζ and the quotient chunks as columns [5]. The verifier does not check the out-of-domain claims directly; they follow from FRI’s input relation (deep_of_inputRelation) through a single-opening lemma.

Lemma 4DEEP bindingkernel-checked

If a word agrees with a polynomial P of degree < M + 1 and its DEEP quotient word agrees with a polynomial of degree < M, on sets whose sizes sum to at least |D| + M + 1, the domain map is injective, and z is off the domain, then P = q · (X − z) + v, so P(z) = v (deep_binding) kernel.

The argument stays in the unique-decoding regime (δ at most the relative unique-decoding radius); it assumes no list-decoding or proximity-gap conjecture.

Step 5 of 6

Merkle compilation

Each committed word is replaced by its root, with openings in a final round [6]. The proof (merkle_singleSalt_soundness) is a game hop: a reduction simulates the hash oracle lazily, extracts the committed words from the hash log with VCVio’s multi-checkpoint extractability, and runs the in-the-clear protocol at a renamed key; off a bad event, the opened values equal the extracted words (pr_world_split).

Step 6 of 6

The verification key

The fixed columns are committed in the key, and a separate side proof, with its own Merkle trees and batched FRI, opens them against its root (side_merkle_singleSalt_soundness).

11

The end-to-end theorem

Definition 5soundness game

Fix an instance I (tables, chip files, public input), a claim c and budgets QFS, QH, V. Sample two independent uniform functions: g, for the Merkle hash and Fiat–Shamir on disjoint key spaces, and gF, for the verification key and its opening proof. An oracle adversary with no time bound outputs a statement z, a salt, a main proof π and a side proof πF, using at most QFS fresh Fiat–Shamir keys and QH hash queries on g, and its own budgets QFSF, QHF on gF; the verifier makes at most V (and VF) hash queries. The adversary wins if Vg,gF(I, vk(I, gF), z, π, πF) accepts and ¬HoldsN c. I and c are fixed before the oracles are sampled.

Theorem 3end-to-end soundnesskernel-checked

For an instance of the ALU system with l = 170 queries and the gate facts of Section 12, side parameters satisfying the side numeric conditions, and budgets QFS, QH ≤ 264 and V ≤ 232,

Pr[win] ≤ 2−82 + (εFRIF + εMerkleF + εcollF)

(exec_e2e_J9ALV) kernel. At side budgets QFSF, QHF ≤ 264 and VF ≤ 232, a key tree of T ≤ 240 nodes, the side numeric conditions taken with a multiplier m satisfying m + 1 ≤ 212, and a digest set of size |Dg| = p5 (the lemmas use only |Dg| ≥ p4), the bracket is at most 2−83 + 2−120 (epsfix_numbers, bfriErr_numbers), so

Pr[win] ≤ 2−82 + 2−83 + 2−120 ≈ 2−81.4

(nock_e2e_J9AL_numbers) kernel.

The first display holds in the same form for programs with one template-jet table over a fixed catalogue (nock_e2e_J9ALJ_succinct_B); the numeric corollary is stated for the ALU system.

Where the bound comes from. The 2−82 is the main proof; the bracket is the side proof that opens the verification key. Parameters: l = 170 queries, θ = δ = 31/64 (inside the unique-decoding radius 63/128 at rate at most 1/64), evaluation domain 2nD with nD = k + 7 ≤ 32. In the usual per-query convention (an adversary making Q queries wins with probability at most Q · 2−λ), the main term is about 147 bits per query, and about 145 for the two proofs together inferred; the shipped 170 queries are far more than 80 or 100 bits would need, so fewer queries are a natural next step (Section 21). Theorem 3 is proved at this configuration (its instance fixes l = 170, and its 2−82 term is computed at θ = δ = 31/64), as is the numbers theorem (nock_e2e_J9AL_numbers), so a smaller, faster configuration re-proves both inferred from the statements’ binders.

Fig. 6The error terms of Theorem 3
Pr[win] ≤2−82main proof2−83 + 2−120side proof2−81.4
main proofside proof

Drawn to scale, the side proof that opens the verification key adds half as much again as the main proof, so the total is 1.5 × 2−82, about 2−81.4. The last term, 2−120, is too small to draw.

2−402−802−1202−160

Main proof

  • The adversary may try up to Q = 264 fresh Fiat–Shamir keys, and each try gets through with probability at most 2−147: 264 × 2−147 = 2−83. This is the Q · max err term of Lemma 2, and the reason the bound grows linearly in Q.

    rapFriEps_le

Side proof

the bound, 2−81.4sets the boundfar smaller

Figure 6. Every term of the bound, at the stated budgets. A bar reaches as far as its term is small, on a scale where each step of 40 is a factor of a million million; the dotted line is the bound itself. Two terms end just past it and set it; the others are far smaller. The first three main-proof rows are the summands of rapFriEps_le; only their sum is a stated theorem.

The first three main-proof rows are the summands of rapFriEps_le; only their sum is a stated theorem. The composition is one theorem: there is no step where two bounds are combined by an argument outside Lean. The arithmetization’s 2−155 sits inside the per-round errors; it is not the security level of the compiled verifier. For every number Q of Fiat–Shamir keys, the main-proof term is at most Q · 2−147 + 2−144 + 2−146 (rapFriEps_le_Q) kernel. This holds for the main term only; the headline theorems keep the budget Q ≤ 264 and bound the total by 2−81.4 there. The constants are loose upper bounds.

12

From the theorem to the code

Theorem 3 takes gate facts as hypotheses: the shape, extended-shape, chip, mask, numeral and setup gates; the claim’s datum and its link to the public input; and the link of the ALU’s preprocessed columns to the public primitives. Each is either a Boolean gate, defined in Lean and evaluated by the executable, or a proposition a kernel theorem derives from those gates (verdict9LV_run).

Theorem 4release headlinekernel-checked

nock_e2e_J9AL_succinct_B has the conclusion of Theorem 3. Besides the query budgets, the side numeric conditions (hnum) and a bound on the side key’s size (hTb), which stay named hypotheses, its one instance-side hypothesis is verdict9LVB(I, …) = ok c, where verdict9LVB is the Lean function the executable runs. nock_e2e_J9AL_succinct_S adds key recomputation: an accept implies the file’s root equals the honest key’s root and the side proof was checked at it (verdict9LVS_sound) kernel.

So an ACCEPT printed by the executable means that the instance-side hypotheses of the soundness theorem hold for this instance, by a theorem, provided the binary computes the Lean function; the side numeric conditions, the query budgets and the other modelling assumptions stay hypotheses of the bound. The certified verifier, nockvm-e2e-verify-cert, narrows that proviso: its accept on the bytes it reads implies the conclusion of nock_e2e_J9AL_succinct_S for whatever instance those bytes parse to (verifyBytesL_sound) kernel. No parser correctness is needed; that the binary runs this parser rests on the compiler, as for the rest of the program. Commands of nockvm-e2e-verify-fam that no end-to-end theorem covers print ACCEPT-UNCOVERED instead of ACCEPT, and its debugging probe labels its output untrusted.

Non-vacuity. At the two shipped programs (add, a big-atom addition; and jp, one template-jet call and one big-atom add), every numeric side condition is proved, and at a false twin of add (same tables, claimed result 2p + 13) the datum and link hypotheses and ¬HoldsN hold by kernel theorems (add_witness_false, bad_event_add), so the bound has a false claim to bite on. These theorems keep one executed gate as a hypothesis at the twin, the shape gate. It does not read the public input, the only difference between the twin and add, so it carries over inferred.

Part IV

Evidence

13

Blueprint

Each component of the development, what it builds on, and its size. Counted at the release tag rel5.4 with a script that is not part of the release: tracked .lean files by directory, excluding the red team, generated files and the vendored ArkLib modules; a theorem is a theorem or lemma block; its statement lines run to the first :=, its proof lines are the rest of the block.

Fig. 9Size of the development
872,360 lines

82% is the arithmetization

ComponentFilesLinesTheoremsStatement linesProof lines
  • semantics and generator

    builds on Mathlib

    4816,0997852,1218,636
  • arithmetization: soundness and completeness

    builds on Mathlib

    1,592711,31934,179122,460407,499
  • executable checkers and drivers

    builds on the arithmetization

    6013,7085611,1694,500
  • RAP as a protocol

    builds on ArkLib (oracle reductions)

    298,9784261,2964,329
  • Fiat–Shamir transport

    builds on ArkLibFs (Quang Dao)

    245920114135
  • batched FRI

    builds on ArkLib (FRI)

    87182275327
  • DEEP

    builds on ArkLib (Reed–Solomon codes)

    54081699176
  • Merkle compilation

    builds on VCVio, ArkLibFs

    5313,6724512,1417,057
  • succinct composition

    builds on the four above

    182,800833721,124
  • end to end, verdicts, executable verifier

    builds on all of the above

    30170,0413,0188,65834,085
  • other top-level modules

    5134,1581,4064,29318,920

total

2,167872,36040,967
Figure 9. Each component of the development, what it builds on, and its size. The strip divides the counted lines among the components, in the order of the table; point at a row to find it in the strip. Lines include comments and blank lines; a line count is not a measure of difficulty.

Not counted above: the red team (1,217 files, about 237,000 lines, 12,684 theorems), generated files (27 files, 33,596 lines, two of them in the red team) and the vendored ArkLib modules (10 files, 4,118 lines, 117 theorems). Lines include comments and blank lines; a line count is not a measure of difficulty.

14

Stress test: we broke it on purpose

A soundness theorem is about the verifier we run, so we deliberately broke its inputs and recorded what it did. Every run was executed at an earlier development commit, which is not in the public repository, with nockvm-e2e-verify-fam on the two shipped programs executed. Of twenty runs, the two honest proofs are accepted and all eighteen tampered inputs are rejected: fifteen by the verdict, which prints REJECT and the failed check, and three by the parser, before the verdict runs. The runs have not been repeated at this release. From that commit to this release the verdict functions did not change; the verifier’s commands that no end-to-end theorem covers now print ACCEPT-UNCOVERED where they printed ACCEPT inferred.

Fig. 7The verifier’s checks, and where tampered inputs stop
Twenty runs
  • 2honest, accepted
  • 15tampered, rejected by the verdict
  • 3tampered, rejected by the parser
Hand the verifier
The verifier's checks, in order
  1. ParserParse and load: passed. The instance, chip, key and proof files parse into the shapes the verifier expects.
  2. KeyRecompute the key: passed. The verification key is recomputed from the instance; the key file must carry the same root.
  3. StatementStatement binding: passed. The Fiat–Shamir statement starts with the encoding of this public input (Lemma 1).
  4. InstanceShape, chips, masks: passed. The instance has the shape of its family, and every chip file equals a Lean literal tied to its specification.
  5. Query count: passed. The proof is checked at 170 queries, the configuration the numbers are proved at.
  6. Claim and link: passed. The public input is canonical and decodes to a claim, and the claim is linked to the tables.
  7. Setup gate: passed. The setup gate holds for the instance.
  8. ProofProof shape: passed. Every limb is below p, and the roots, openings and positions have the expected sizes.
  9. Fiat–Shamir challenges: passed. The challenges are recomputed by hashing the statement and the prover’s messages; the opened positions must be the ones the hash asks for.
  10. Key opening: passed. The side proof opens the fixed columns against the key’s root.
  11. Merkle openings: passed. Every opened value hashes up to the root the prover committed to.
  12. Constraints at a random point: passed. The constraints, combined at the out-of-domain point, equal the quotient: the DEEP check.
  13. Low-degree test: passed. At every query the folded words agree with the final polynomial: FRI.

$ nockvm-e2e-verify-fam verify --family j9al --vk add.vk.json …

ACCEPT claim ⟨claim⟩

Every check passes and the verifier prints the claim it accepts.

Figure 7. The checks of the verify command, in the order the code runs them, and where the tamperings described in this section stop. Check order and messages are read from the verdict functions in the release; ⟨…⟩ stands for a value that depends on the run, and timings are omitted.

Three rows deserve a word. A flipped byte inside a committed word fails at its Merkle root. A changed claim, or a proof moved to another program, fails at statement binding (Lemma 1). And a bound wrong claim, with a false result and the statement rewritten so that it binds, passes statement binding and is caught by the proof itself: the rewritten statement changes the Fiat–Shamir transcript, the challenges change, and the opened positions no longer match the query challenge.

The kernel side. The release carries a red-team tree, Nock/RedTeam, of 1,217 modules that re-derive the main results adversarially. One example builds a complete proof package over a 97-element field whose claim is false ([5 [1 [7 9]] [1 [15 8]]] is claimed to give 0; Nock gives 1), with operands chosen to collide at the honest coin (7 + 9·8 = 15 + 8·8 = 79 mod 97). The kernel proves that every tuple this package gets accepted on lies in the failure event the bound pays for (wc_every_accepting_tuple_in_event): a cheat that works only on bad coins is exactly what ε prices.

Fig. 8The red team’s false claim at each coin
The false claim

*[0 [5 [1 [7 9]] [1 [15 8]]]]

Claimed
0
“equal”
Nock gives
1
not equal
The verifier's coin z31

[7 9]

7 + 9·31

92

[15 8]

15 + 8·31

69

All 97 coins1 of 97 lets the claim through

At z = 31 the two cells compress to different values, so the check that would have to pass cannot. Move the coin to 8 to see the one place the cheat works. A cheat that works only on bad coins is exactly what ε prices.

Figure 8. The red team's false package, over the 97-element field. The claim says two different cells are equal; it can only pass at a coin where their fingerprints agree. The kernel proves that every tuple this package is accepted on lies in the failure event the bound pays for (wc_every_accepting_tuple_in_event).
15

Methods: how it was built and checked

A machine-checked proof is only as good as its statements. A theorem with a weakened conclusion, an extra hypothesis or an unsatisfiable premise is still “checked”, so most of our method is about getting the statements right and keeping them right.

  1. 01

    Statements first.

    The specification, docs/SPEC.md in the release, fixes the arithmetization, the verifier predicate and the theorems before and alongside the proofs. In it “every normative statement names a Lean declaration and its file:line in this tree”, and a statement marked (informal) is an explanation, not something a theorem states. Statements are reviewed on their own, apart from the proofs, with one question in mind: does the Lean statement say what we claim, with no weakened conclusion, no extra hypothesis and no unsatisfiable premise?

  2. 02

    AI agents in the workflow.

    The proofs, the executables and this report were written with AI agents as part of the workflow, under human direction. The process is built so that no kernel-checked claim rests on an agent’s word. One agent writes a proof against a fixed statement, and a different agent audits headline changes before they are merged; a person approves every merge into the release and every release, by exact commit. A proof counts only when the Lean kernel accepts it in a clean build of that commit, with nothing beyond the three standard axioms. Audits reject changes on the grounds above, for example a definition that a trivial witness satisfies.

  3. 03

    Mechanical checks.

    Every build reprints the axioms its theorems use. Every headline declaration except one definition has a recorded #print axioms line, and docs/THEOREMS.md lists them with the build each line comes from; not every theorem in the release has such a line. The library’s headline modules and the end-to-end theorem were replayed from scratch by Lean’s independent checker, leanchecker --fresh (Section 16) executed. The certified verifier is built by a script that records the emitted C, the binary and their hashes, and two clean builds agree (Section 16) executed.

  4. 04

    Adversarial checks.

    Each headline’s hypotheses are shown satisfiable at concrete programs, and at a false twin where the conclusion has something to rule out (Section 12). The red team proves negative facts in the kernel: that a weakened form fails, that a bound would be vacuous, or that a false proof package is rejected. And the executable was run on deliberately broken inputs (Section 14).

  5. 05

    Independent reads.

    This report and the companion paper were each read, claim by claim against the Lean, by reviewers who did not write them.

16

Proof checking and the trusted base

The release. This report describes the release at https://github.com/nockchain/nock-zkvm, tag rel5.4: the code and its documentation. It is an alpha research release: it is not production software, it has not yet been independently audited, and it must not be used in production (Section 23). It was prepared from earlier internal builds of the same code, which are not public. Relative to the last of them, the release adds the certified verifier, the key-budget corollary rapFriEps_le_Q, a front end for your own programs, a benchmark script and the documentation; it changes no library file and no statement of an end-to-end theorem or verdict, so the results checked on that build hold for the release inferred. Where a count or a measurement in this report was taken on an internal build, it says so.

Kernel. The release records every #print axioms line its builds printed (docs/theorems-all.tsv). Each recorded line lists only axioms among propext, Classical.choice and Quot.sound, and none mentions sorryAx; no module declares an axiom, and native_decide appears only in comments and strings. Not every theorem has a recorded line. The theorem explorer lists each cited declaration with its file, line and, where the release records one, its axioms line.

Fig. 10Theorem explorer
63 of 63
TheoremDefinition
Figure 10. Every Lean declaration this essay cites: 63 in all. Open one to see its file and line at the release tag rel5.4, and its statement exactly as the source has it. Each cited theorem with a recorded #print axioms line (40 of 58, recorded in the release's docs/theorems-all.tsv) depends only on the three standard axioms; the release records no line for the others. Citations in the text link here.

Independent replay. Lean’s independent checker, leanchecker --fresh, replayed fourteen library modules carrying the ALU-system soundness and completeness headlines and their red-team checks, all successfully executed, on an earlier internal build whose library differs from the release only in comments and documentation inferred. The end-to-end theorem’s module was replayed the same way on an earlier internal build of the same code, with Lean 4.35.0, successfully, in 3,907 s executed.

Execution. Accept on the honest fixtures, reject on every tampered input in Section 14 executed.

The trusted base, item by item.

the Lean 4 kernel
it checks every proof; the release builds with Lean 4.35.0
Sizeone checker
the specification
the definitions the theorems are about must say what we mean: the reference interpreter evalN and HoldsN, the verifier predicate, the soundness game (Definition 5) and the verdict functions; they are short and readable, and the theorem explorer links each
Sizethe statements of Theorems 1-5
three standard axioms
propext, Classical.choice, Quot.sound
Size3
vendored, unmerged ArkLib modules
kernel-checked here, not reviewed upstream
Size10 modules, 117 theorems
hash model
Tip5 modelled as two independent random oracles, one for the main proof and one for the side proof, each answering hash and Fiat–Shamir queries on disjoint keys (standard)
Size2 oracles
compilation
the verdict logic is the kernel-checked Lean function; trusted are Lean’s compiler and runtime, the C toolchain, the few lines that read the input files and print the verdict, and the meaning of the input parser, which includes partial definitions (standard for verified software)
Size1 binary
executed gates
shape, extended shape, chips, mask, numerals, ALU preprocessed columns, setup (and jet layout for jp), run by the executable
Size7 gates (8 for jp)

A certified verifier. The release includes the executable nockvm-e2e-verify-cert. It takes the same arguments as verify --vk: the family, the key file, the instance, the main proof and the side proof. Its main only reads the input files, calls the pure Lean function verifyReport on the bytes, prints the result and returns its exit code.

Theorem 5certified acceptancekernel-checked

If the Lean function verifyReport on the byte strings (vk, inst, chips, π, πF) returns exit code 0, then for the ALU family (or, for the template-jet family, its variant) the bytes parse to an instance I, a key root, a statement and two proofs on which the verdict returns ok c, and the conclusion of Theorem 4 (nock_e2e_J9AL_succinct_S) holds at I: the gate facts hold, the claim is c, and the bound of Theorem 3 holds for I and c under its remaining hypotheses, the side numeric conditions, the bound on the side key’s size (hTb) and the query budgets QFS, QH ≤ 264 and V ≤ 232 (the side numeric conditions are proved at the two shipped programs, Section 12) (verifyReport_ok, verifyBytesL_sound, verifyBytesLJ_sound) kernel.

Three points matter in reading it. First, the theorem is about the Lean function, which is the verdict logic itself; that the binary’s exit code equals its value rests on the standard compilation path, as for any verified software without a verified compiler: Lean’s compiler and runtime, the C toolchain, the few lines that read the input files and print the verdict, and the meaning of the input parser. Second, the bound is a probability over ideal oracles and does not depend on the proof supplied: exit code 0 certifies that the parsed instance satisfies the instance-side hypotheses of Theorem 3 (the gate facts) with claim c, not that this particular proof is sound, and concluding that c is true still rests on the random-oracle model. Third, no parser is proved correct, and the parser includes partial (possibly non-terminating) definitions, such as the JSON parser and the trace-expression parser; a run that does not terminate gives no verdict. The theorem does not need one, because it covers whatever the parser returns, but which instance and claim were certified depends on the parser and on the user reading the printed claim. The chip files are untrusted input, compared inside the verdict with the Lean literals. The other modes of nockvm-e2e-verify-fam are not certified, and they say so: they print ACCEPT-UNCOVERED. The release also keeps the older executable nockvm-e2e-verify, which prints a plain ACCEPT that no theorem covers; its verify --vk does not recompute the key.

Checking a proof is one command:

Check a proof
nockvm-e2e-verify-cert verify --family j9al --vk add.vk.json add.inst.json add.proof.json add.fix.json

It prints ACCEPT claim … or REJECT: … and exits 0 only on ACCEPT. nockvm-e2e/scripts/build-certified.sh records the emitted C files, the binary and their SHA-256 sums; two clean builds of the same verifier sources gave identical hashes for all 1,365 files (the binary and 1,364 emitted C files), and the release build gave the same binary hash executed.

Part V

Context

Theory. FRI [4], DEEP-FRI [5], interactive oracle proofs and their compilation to succinct arguments [6], Fiat–Shamir through round-by-round soundness [7] and state-restoration soundness [6], shown equivalent by Holmgren [8], proximity gaps for Reed–Solomon codes [9] and LogUp [10] are prior work; we formalize the parts we use. The arithmetization follows Kattis, Klatt, Quirk and Allen [1], who compile custom languages into efficiently verifiable VMs and instantiate the framework for Nock; the library builds on its Theorem 5.4, adapted to the design described here.

Machine-checked proof systems. ArkLib [11] specifies interactive oracle reductions in Lean and proves their security, with FRI and batched FRI among its protocols, on VCVio [12]. Bailey and Miller formalized SNARK soundness proofs in Lean [20]. Isabelle/STARK proves a query-bounded soundness bound for a STARK-style protocol with FRI, Merkle authentication and Fiat–Shamir in Isabelle/HOL [18].

Verified constraints. Several projects prove constraints sound for the semantics they encode: Cairo’s algebraic representation in Lean 3 and the S-two AIR in Lean 4 [13, 14]; single-row soundness for most of SP1 Hypercube’s RV64 opcodes against the Sail RISC-V model, by Nethermind and Succinct, analysed in an Ethereum Foundation blog post [16]; and Clean, a Lean DSL with per-circuit soundness and completeness theorems [15]. Jolt-QED proves in Lean that most of Jolt’s bytecode expansions are equivalent to the RISC-V instructions they replace [19]. The Ethereum Foundation’s Verified zkEVM project hosts ArkLib, VCVio and Clean [17]. These results relate constraints or instructions to a machine semantics, with the proof system outside them or assumed.

Surveys. Kolozyan et al. survey security tools and verification for zero-knowledge systems; as of July 2026 they write that “no zkVM has end-to-end formal verification, and verified components are isolated” [3]. Chaliasos et al. [2] and Tang et al. [21] analyse and classify real vulnerabilities.

18

What is new here, and what is not

New in this work, each tied to a theorem:

  1. 01

    A combinator VM with unbounded atoms, end to end.

    The machine is full Nock, with all twelve opcodes, template jets and a big-atom ALU for atoms of up to 1,984 bits, not a register or stack machine. Its succinct verifier is sound end to end (Theorem 3), and the executable’s own verdict is the theorem’s hypothesis (Theorem 4).

  2. 02

    Completeness alongside soundness.

    The arithmetization is proved complete as well as sound (Theorem 2), and the executable checker accepts the generator’s output (checkJ9ALX_genJ9ALXJ).

  3. 03

    An on-ramp onto a shared library.

    The transport of Lemma 2, the FRI port of Lemma 3, DEEP without conjectures (Lemma 4) and the Merkle compilation connect a VM’s constraint system to ArkLib’s codes and FRI.

  4. 04

    Machine-specific design, proved necessary or sound.

    Two coins for fingerprints (Proposition 1), hash-consed cells with a rank, big atoms at a separate limb coin with a masked last row, operation confusion ruled out, and constraint tables tied to their specifications by the kernel.

  5. 05

    Statement binding, checked.

    The ALU and template-jet verdicts, which the certified verifier uses, reject any Fiat–Shamir statement that does not begin with the encoding of the public input; the encoding is injective and prefix-free (Lemma 1) kernel. The check is part of the Lean verdict that nockvm-e2e-verify-fam verify --vk runs for these families: its accept implies the binding (verdict9LVB_sound, verdict9LVS_sound, with zBind_iff) kernel. No probability bound uses it yet, so the bound stays non-adaptive.

Not new here: the cryptographic theory of Section 17; ArkLib’s FRI soundness and Quang Dao’s Fiat–Shamir framework; VCVio’s Merkle extractability; and the arithmetization’s design, which is Kattis et al.’s [1].

19

Scope of the result

Theorem 3 is a precise statement, and its main limits are these.

  • Random-oracle model. As is standard for hash-based proof systems, the hash and the Fiat–Shamir challenges are modelled as random oracles on disjoint key spaces, one independent oracle for the main proof and one for the side proof. The verifier instantiates them with the Tip5 hash [22], using domain-separation tags; no theorem relates Tip5 to a random oracle. The theorems take the query positions to be uniform. The executable derives each position as a field element reduced mod 2nD, at statistical distance below 2−64 from uniform per position. Counted multiplicatively, this changes the end-to-end bound by a factor below (1 + 2nD−64)170: about 1 + 2−42.6 at nD = 14, the largest over the shipped instances, and below 1 + 2−24.5 at nD = 32, the largest the shape gate allows inferred, not proved.

  • A statement fixed in advance. The instance and claim are fixed before the oracles are sampled. The ALU and template-jet verdicts already enforce statement binding (Lemma 1); a bound for statements chosen adaptively is not yet proved.

  • Not zero-knowledge. The proof shows the claim is true; it does not hide the trace (no masking).

  • Standard compilation trust. The theorems are about Lean functions, and the certified verifier’s verdict logic is such a function. As for any verified software built without a verified compiler, what is trusted is Lean’s compiler and runtime, the C toolchain, the few lines that read the input files and print the verdict, and the meaning of the input parser (Theorem 5).

  • Pre-optimization costs. Nothing has been optimized (Section 20).

  • Completeness is for the arithmetization. An honest run that meets the conditions of Theorem 2 is accepted by the arithmetization; completeness from an honest prover through to the compiled verifier is not yet proved.

20

What it costs

Fig. 11Proving and verifying times

adda big-atom addition

prove
≈ 98 s
verify
≈ 10.5 s

jpone template-jet call and one big-atom add

prove
≈ 285 s
verify
≈ 14.8 s
Peak memory
≤ 1.1 GB
Proof for add, as JSON
5.5 MB
an estimated 3.5 MB in a binary encoding
Figure 11. Medians of five runs per step with the release’s benchmark script, on a shared machine under load, so the times are upper-end indications. Bars share one scale. Proving dominates.

These are pre-optimization figures for a security-first proof of concept: no step has been optimized. Measured with the release’s benchmark script during release preparation, before the front end was added; the proving and verifying code has not changed since, only argument handling and output wording inferred from the diff: five runs per step, medians, each run under an 8 GB memory cap, on a shared 14-core, 20-thread machine (Intel i5-13500, 62.6 GB) that was under load throughout, so the times are upper-end indications, not a quiet measurement measured. Sizes are exact for the JSON files; the binary sizes are 8 bytes per field element plus 40 per digest, computed from the JSON (there is no binary encoder yet).

addjp (template jet)
prove (wall, peak memory)98 s, 619 MB285 s, 1.07 GB
verify, verify --vk (key recomputed)10.5 s, 242 MB14.8 s, 252 MB
verify-online (key read from file; ACCEPT-UNCOVERED)no online mode for this family11.3 s, 250 MB
key setup / side-proof generation1.4 s / 1.8 s3.8 s / 4.6 s
main proof, JSON (measured) / binary (estimate)5,465,691 B / 3.46 MB5,990,456 B / 3.88 MB
side proof, JSON (measured) / binary (estimate)391,641 B / 0.16 MB617,468 B / 0.26 MB
verification-key file (JSON)156 B155 B
online key / public input (JSON)n/a10.9 KB / 3.1 KB

The online verifier also has a proved cost bound: for the jet-free big-axis system, its cost is at most 6000 · S6, with S the sum of the instance’s size parameters, in a stated cost model, and the trace height enters only through its logarithm (verifyOnline_cost) kernel. We do not prove such a bound for the ALU system. The cost model follows the code by inspection and leaves out the public-input check, the gates and setup.

Almost all of the proof is the opened columns at the query positions: in the add proof, 97 % of the field elements are openings of the four trace trees, about l · 2W · 8 bytes for W committed columns inferred, so the number of queries l is the lever.

Your own program. The release includes a front end, nockvm-e2e/scripts/run-free.sh, that takes a subject and a formula as noun text, optional primitive jets and a fuel bound, and runs the whole chain: emit, prove, key setup, the side proof and verify --vk. It works for programs whose tables fit the supported sizes. Before proving, it checks the conditions an honest run must meet and stops with a clear message if one fails. It is a driver, not a theorem executed.

21

Next step

This release is a proof of concept for the method: built in layers, each with its own theorem, and security-first. Nothing in it is optimized yet.

The main next step is optimized arithmetizations that keep a certified verifier extracted from Lean: the same chain on this framework, with efficient polynomial commitment schemes, including lattice-based ones, in place of the commitment layer used here. This is a plan; nothing in this report claims it.

Further work on the same chain includes end-to-end completeness, knowledge soundness, an adaptive bound and fewer queries.

22

Reproduce it

The release repository is public: https://github.com/nockchain/nock-zkvm, tag rel5.4. The commands below rebuild it and check a proof.

Build
git clone https://github.com/nockchain/nock-zkvm && cd nock-zkvm && git checkout rel5.4cd nockvm-e2elake build NockvmE2E                      # every theorem; one "depends on axioms" line per #print axioms linelake build nockvm-e2e-verify-fam          # the verifier executablelake build nockvm-e2e-verify-cert         # the certified verifier

A from-source build of the package and its executables peaked at about 20 GB of memory, with two Lean threads (nockvm-e2e/README.md). A full lake build of the whole library at the repository root needs about 48 GB because of one red-team module that no headline theorem depends on; the root README.md gives the build command for the subset the headlines import, which peaked at 16.7 GB once. Every depends on axioms line must be a subset of [propext, Classical.choice, Quot.sound].

Verify the add fixture:

Verify the add fixture
V=.lake/build/bin/nockvm-e2e-verify-famF=fixtures/j9al-addmkdir -p out3 && ln -sfn ../$F out3/add$V vk-setup  --family j9al $F/add.inst.json add.vk.json$V fix-prove --family j9al $F/add.inst.json $F/add.proof.json add.fix.json$V verify    --family j9al --vk add.vk.json $F/add.inst.json $F/add.proof.json add.fix.json.lake/build/bin/nockvm-e2e-verify-cert verify --family j9al --vk add.vk.json fixtures/j9al-add/add.inst.json fixtures/j9al-add/add.proof.json add.fix.json

Both verifiers print ACCEPT claim …. Section 14 shows what each kind of tampering produces.

23

Review and audit

This is a large and complex development. Its theorems are machine-checked, but a machine-checked proof is only as strong as its statements and its trusted base: the Lean kernel and compiler, the C toolchain and file I/O, and for nockvm-e2e-verify-fam also the input parser; see Section 16 and docs/LIMITS.md. Because of its size and complexity, we welcome review, issues and pull requests from the community at https://github.com/nockchain/nock-zkvm, and we are commissioning an independent audit. This release is for research and review; we will complete that audit before any production deployment.

References

  1. 1.A. A. Kattis, B. Klatt, P. Quirk, L. Allen. A Framework for Compiling Custom Languages as Efficiently Verifiable Virtual Machines. IACR ePrint 2025/1110.
  2. 2.S. Chaliasos, J. Ernstberger, D. Theodore, D. Wong, M. Jahanara, B. Livshits. SoK: What Don’t We Know? Understanding Security Vulnerabilities in SNARKs. USENIX Security 2024; arXiv:2402.15293.
  3. 3.A. Kolozyan, T. Sorger, A. Hicks, S. Chaliasos. ZKP Security Tools and Verification: Coverage, Effectiveness, Adoption, and Challenges. arXiv:2607.23752, 2026.
  4. 4.E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev. Fast Reed–Solomon Interactive Oracle Proofs of Proximity. ICALP 2018.
  5. 5.E. Ben-Sasson, L. Goldberg, S. Kopparty, S. Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. ITCS 2020.
  6. 6.E. Ben-Sasson, A. Chiesa, N. Spooner. Interactive Oracle Proofs. TCC 2016-B; IACR ePrint 2016/116.
  7. 7.R. Canetti, Y. Chen, J. Holmgren, A. Lombardi, G. N. Rothblum, R. D. Rothblum, D. Wichs. Fiat–Shamir: from Practice to Theory. STOC 2019.
  8. 8.J. Holmgren. On Round-By-Round Soundness and State Restoration Attacks. IACR ePrint 2019/1261.
  9. 9.E. Ben-Sasson, D. Carmon, Y. Ishai, S. Kopparty, S. Saraf. Proximity Gaps for Reed–Solomon Codes. FOCS 2020.
  10. 10.U. Haböck. Multivariate lookups based on logarithmic derivatives. IACR ePrint 2022/1530.
  11. 11.ArkLib: a formally verified library for interactive oracle proofs. github.com/Verified-zkEVM/ArkLib, commit c488a3a4; single-salt Fiat–Shamir framework by Quang Dao from stacked pull requests #1267, #1268, #1274 and #1277 (closed without being merged).
  12. 12.D. Tuma, Q. Dao, J. Waters, A. Hicks, N. Hopper. VCVio: Verified Cryptography in Lean via Oracle Effects and Handlers. IACR ePrint 2026/899; library at github.com/Verified-zkEVM/VCVio.
  13. 13.J. Avigad, L. Goldberg, D. Levit, Y. Seginer, A. Titelman. A verified algebraic representation of Cairo program execution. CPP 2022; arXiv:2109.14534.
  14. 14.J. Avigad, A. Ganor, L. Goldberg, D. Levit, O. Nir, Y. Seginer, A. Titelman. Formal verification of the S-two AIR. arXiv:2606.04311, 2026.
  15. 15.G. Mitscha-Baude. Clean: From Verified Circuits to Verified zkVMs. ZK/SEC blog, 5 June 2026.
  16. 16.C. Gunton. On Formal Verification and a Bug in SP1 Hypercube. Ethereum Foundation zkEVM blog, 20 May 2026.
  17. 17.Verified zkEVM project (Ethereum Foundation). github.com/Verified-zkEVM.
  18. 18.D. Marmsoler. Isabelle/STARK: A Formalization of zk-STARK in Isabelle/HOL. arXiv:2608.01965, 2026.
  19. 19.A. Biswas, Q. Dao, D. Ross, J. Thaler. Jolt-QED: Formally Verifying Bytecode Expansions in Lean. IACR ePrint 2026/2157.
  20. 20.B. Bailey, A. Miller. Formalizing Soundness Proofs of SNARKs. IACR ePrint 2023/656.
  21. 21.X. Tang, L. Shi, X. Wang, K. Charbonnet, S. Tang, S. Sun. Zero-Knowledge Proof Vulnerability Analysis and Security Auditing. IACR ePrint 2024/514.
  22. 22.A. Szepieniec, A. Lemmens, J. F. Sauer, B. Threadbare, Al-Kindi. The Tip5 Hash Function for Recursive STARKs. IACR ePrint 2023/107.