Nock zkVM

Nock zkVM#

Nockchain is a blockchain which uses the Nock ISA as its primary instruction set. The Nock zkVM is a STARK-based proving system that allows validators to efficiently verify off-chain computation without re-executing it (succinctness). Despite the “zk” in its name, it is not yet a zero-knowledge system: it provides succinctness and soundness, not privacy, and the witness is not hidden.

This article is a short overview of the bottom layers of the Nock zkVM, primarily of interest for how it represents and interacts with Nock nouns and the formal verification of Nock-based computations. The “Open Proof Machine” page has a comprehensive and widget-enabled explanation of the entire system.

Status as of ~2026.11.17: the zkVM is an alpha research release. It has not been independently audited and must not be used in production.

How does the Nock ISA lend itself to STARK-based proofs? The Nock ISA has several properties that make it a suitable target for STARK-based proving:

  • Small instruction set. With only twelve opcodes, the compute chip’s state selector stays small, simplifying proof generation.

  • Deterministic behavior. Every Nock formula has one of three outcomes — a value, a deterministic crash, or non-termination — with no undefined behavior. The reference interpreter evalN is fuel-indexed and returns none for both a crash and fuel exhaustion.

  • Stateless evaluation. Each Nock step is a pure function from [subject formula] → noun, which maps naturally onto a STARK execution trace.

  • No hidden state. The only non-structural opcode is 11 (hints). In the modelled semantics hints are pure: static and dynamic hints are transparent, and a jet hint (a registered id with the exact body formula) is checked inside the circuit by the J and ALU chips. There is no side-effect channel for the prover to model.

The zkVM is a Lean 4 formalization, with native executables, carrying kernel-checked soundness theorems for a STARK-based proof system over Nock. It establishes soundness (a false claim is accepted only with negligible probability); it is not zero-knowledge, and completeness of the compiled protocol is not an end-to-end theorem.

How it works#

The design goal of this zkVM is to let a prover convince a verifier that a computation was performed correctly without the verifier re-executing it (succinctness). The prover generates a proof that the claim HoldsN c is true, and the verifier checks it efficiently. The system is not zero-knowledge: the prover is Reed–Solomon plus FRI with no masking, so the witness is not hidden — it delivers soundness and succinctness, not privacy.

A claim c consists of a subject, a formula, and an expected result. The prover’s goal is to demonstrate that evaluating the formula with the given subject produces the expected result.

All evaluation routes through Nock.evalN, which is a fuel-indexed big-step interpreter.

evalN : ℕ → Noun → Noun → Option Noun      -- fuel, subject, formula

A proof establishes a claim,

HoldsN c  :=  ∃ fuel, evalN fuel c.subject c.formula = some c.result

This definition states that a claim c holds if there exists some amount of fuel such that evaluating c.formula with c.subject using evalN produces c.result. In other words, the claim is true if the formula successfully evaluates to the expected result within a finite number of steps.

Let’s establish some terminology before we look at how the zkVM works:

  • A chip is one table of the arithmetization.

  • A handle is a reference to a noun by a (kind, value) pair rather than by content.

  • A coin is a random field element the verifier draws.

  • Staged means a trace column may depend only on coins drawn in earlier rounds.

The machine#

The point of a zkVM machine is to execute Nock formulas in a way that can be efficiently proven and verified using STARK-based proofs. It maintains an execution trace that captures the evaluation of the formula step by step, allowing the prover to generate a proof that the computation was performed correctly.

The machine consists of several components, including the execution trace, the arithmetization tables (chips), and the mechanisms for handling coins and staged computations. Each step of the Nock evaluation is recorded in the trace, and the arithmetization ensures that the trace can be checked efficiently by the verifier.

The first thing to do is convert a Nock evaluation run into a table-based execution trace. This trace will record each step of the evaluation, including the current subject, formula, and intermediate results. By organizing the computation in this way, we can later apply the arithmetization to generate the corresponding chips and ensure that the trace can be efficiently verified.

The honest prover runs a generator that mirrors evalN and emits an execution tree, one node per evaluation step. A compute chip has one row per node, with a one-hot selector over 17 states: ten for opcodes 0–9, one for cons, three for op 10 (s10, s10L, s10T) and three for op 11 (static, dynamic, jet). It names nouns by handle, never by content. The nouns themselves live in other chips:

  • Cell table: one row per distinct cell, hash-consed (each cell stored once). Each row carries a fingerprint of its noun and the fingerprints of its two children.

  • Atom table: big atoms as chains of 32-bit limbs with the +1 carry logic for op 4 built in.

  • Walk chips: forest walks over the cell and atom tables that turn a statement that “the noun at axis a of root r” into a record the compute chip consumes. (This is how opcodes 0, 9 and 10 read memory.)

  • J chip: a straight-line interpreter for compiled jet templates.

  • ALU chip: checks limb-level arithmetic for the primitive jets.

Tables are tied by arguments, such that one table provides records, another consumes them, and the verifier checks that the two multisets balance. Each balance costs one coin, drawn from a quadratic extension K′ of a cubic extension K of Goldilocks, so |K′| = p⁶ ≈ 2³⁸⁴.

A noun’s fingerprint is a triple (size, dyck, leaf) at a random coin z. The leaf component is Σ zⁱ·vᵢ over the noun’s leaves in in-order position—consecutive powers of z, linear in the leaf values. Tree shape enters only through the separate size and dyck components. Big atoms are supported through using a second, independent coin for their limbs, with coin collision detection enabled.

A jet call occurs due to a hint like [11 [id clue] body]. In the zkVM, a registry maps an id to a template (argument axes plus a semantic function) and the Nock formula for which the template stands.

  • Jets are keyed on the id and the exact body formula. If the body is not literally the registered formula, the call is evaluated as an ordinary hint.

  • A registry entry must be Faithful ∧ Complete against evalN: the template returns a value exactly when the formula does. Off-domain, the template returns nothing and the generator falls back to running the body.

The template jets are written in a tiny typed language and compiled to their Nock formula, so faithfulness is a theorem about the compiler, not a per-jet proof. The primitive arithmetic jets are hand-written guarded counting loops, proved against each specification.

The remainder of the Nock zkVM stack consists of the proof generation and verification layers, which go far beyond Nock evaluation as such. We recommend the “Open Proof Machine” page for a comprehensive explanation of these layers.