Skip to content

formal: plan to shrink the Lean proofs and tie them to the Rust and the spec (tracking) #783

Open

Description

@scaraven

This issue tracks a plan to make formal/ smaller, cheaper to change, and mechanically tied to the Rust and to the LaTeX specification, without changing what is proved. The detailed blueprint (every step with its acceptance check, estimate and risk) is formal/notes/blueprint.md; it will land in its own PR. Figures are measured at fa4b43935 unless marked estimate.

Why

  • Size. formal/ holds 465k hand-written code lines (comments and blank lines removed) and 2.06M generated lines. The trusted statement is small (17 files, about 3.6k code lines) and close to minimal. The bulk is proofs, and above all the guest's meaning layer (Guest/B1): 166k code lines, one hand proof per compiled guest function, written against templates and numbered values.
  • Change cost. Every recorded change rebuilds most of the tree, and a small guest change hand-edits 26 to 47 proof files (draft guest: the leanSPHINCS FORS and hypertree walks dispatch on windows of the leaf #773: one 107-line guest function, 42 files).
  • CI. The proofs are green: the full gate passes at fa4b43935 in about 100 minutes on a 32-core host. But the Lean job is red or cancelled on most main pushes, for two reasons:
    • A Rust rename in d41a32045 broke a Rust helper under formal/ that no Rust job compiles.
    • The workflow's per-branch concurrency group replaces a pending run whenever the next push arrives, so most direct pushes to main are never checked: 18 of the last 30 runs were cancelled.
  • Coupling. Rust, LaTeX and Lean are tied by careful prose that nothing checks: 409 of 803 statement declarations cite Rust, two cited names no longer exist, and one cited doc label does not exist.

Decisions taken (2026-11-18)

  • D0: plan as if formal: compile the guest with a verified Lean back end; delete the per-function certificates #756 (a verified Lean back end for the guest) does not land, but keep the plan compatible with it.
  • D1: most main commits stay direct pushes. Checks therefore run before the push (one local command, which the agents run automatically) and after it on every commit, rather than as PR gates.
  • D2: proofs may lag a statement change, inside a bounded, kernel-checked debt ledger, with the workflow modelled on ArkLib's (below).

How changes are kept in sync (modelled on ArkLib's workflow)

ArkLib merges about 500 PRs in two months, many written by agents, and took its proof debt from 416 declarations to zero once the debt could only shrink. Its enforcement is a merge queue, which leanVM does not use (D1). So the same ideas move to the push:

  • Before a push. formal/tools/precheck runs the cheap checks in at most 2 minutes:

    • Rust helpers compile, citations resolve, and the six Lake manifests agree.
    • The guest data is current.
    • The statement fingerprint is compared with what was last pushed.

    A committed Claude Code hook runs it before every git push, and before commits that touch formal/, crates/, guests/ or doc/. An optional git hook covers humans.

  • After each push on main. Cheap checks (A0, no Lean) and statement checks (A1, Lean without proofs, against the Rust) run on every commit; nothing is cancelled. A failure opens a rolling main-red issue that names the first bad commit and its author, who fixes forward or reverts within one working day. Proofs (B) run on a large runner.

  • Statement changes. A commit that changes the statement carries trailers (Statement-change:, Rust:, Formal-debt:). Each such push opens a review issue with the field-by-field diff of what is proved. An agent posts an adversarial review on it, and a formal owner closes it with ack or revert.

  • Proof debt. When a statement change breaks proofs, the failing proof bodies become sorry and are listed in formal/debt.toml. Statements are never sorried, and nothing in Statement/ is.

    • A kernel sweep checks that every sorry is in the ledger.
    • The ledger may grow only in a statement-changing push. Starting bounds are 3 open changes, 60 entries and 5 working days, to be fixed after replaying four weeks of main.
    • Past a bound, further statement changes must land already proved, from a branch. Rust work is never blocked.
    • "Formally verified" claims cite the tag formal-proved: the last commit where the full build passed with an empty ledger.
  • Skills. Tool-neutral Markdown skills in formal/skills/: formal-precheck, formal-statement-change, formal-debt-repair, formal-main-red, formal-statement-review and formal-docs-sync. Each records the rule, not the incident, and formal/AGENTS.md shrinks to one-line rules.

  • Ratchets. Migration targets become counts that may only shrink: numbered values in B1, compiler indices in Cost, parameter numerals, and maxHeartbeats overrides. Every gate ships with planted violations it must catch.

Targets

Baseline Target
Local check before a push none at most 2 min
Formal verdict after a push off the spec surface 3+ h, often never at most 10 min
Formal verdict after a spec-surface push (checks without proofs) same at most 40 min
Hand-edited B1 files per guest-only edit 26 to 47 at most 3
Files a verifier check change edits 55 (41e89f2e5) one normal form plus at most 8
Guest/B1 code lines 166k 55k to 90k estimate; first probe passed
All hand-written code lines 465k 340k to 385k estimate, if the guest redesign works
Reading list for zkVM knowledge soundness 17 files, 3.6k code lines 7 files, at most 2.4k

The total depends on the guest redesign:

  • If it stops after its first stage, the total is about 395k to 420k.
  • If it does not scale beyond the first probe, the total stays near 450k, and the gains are in change cost and CI.

Decisions still open for the owners

  • D3 Guest completeness on acceptable children instead of the honest prover's exact output (stronger, about 70 trusted lines).
  • D4 Allow more than seventeen statement files, for internal firewalls and short reading lists.
  • D5 Defer guest completeness, which weakens the statement. Revisit only after the guest redesign has been measured.
  • D6 Drop the priced guest decoder, which weakens the statement.
  • D7 Bounds that move with guest performance (guestWitnessDecoderSizeBound): a literal, or a generated definition with fixed slack.

Milestones

M0 Unblock (about 1 week)

  • Formal's Rust helpers (formal/lean_vm/scripts/*) join the Rust workspace, so a Rust rename that breaks them fails rust.yml in minutes. Fix the current break.
  • Split lean.yml into tiers.
    • A0 and A1 use per-commit concurrency, so every push is checked.
    • B keeps "latest wins" but records which commit it proved.
    • The experimental prover triggers nothing.
    • Only main writes the build cache.
  • formal/tools/precheck and the Claude Code hook on git push; optional git pre-push hook.
  • main-red issues on post-push failure, naming the first bad commit (bisected) and its author; a revert PR after 24 hours red.
  • Statement text fingerprint and commit trailers; a statement-review issue per push that changes it. CODEOWNERS for the PRs that exist.
  • formal/tools/cite-check.py with forward checks: every cited Rust path, Rust item and doc label exists. Folds in tools/docnames.py.
  • Skill formal-precheck.

M1 Gates complete

  • Debt ledger formal/debt.toml and lake exe debtsweep --check, certified by planted fixtures. Replay four weeks of main to fix the bounds. Add the formal-proved tag and the formal-debt issue.
  • Elaborated fingerprint: the type of each end statement and a hash of everything it reaches. Library bumps count as statement changes.
  • An agent review is posted on each statement-review issue.
  • cite-check reverse coverage: every pub item and check site of crates/verifier is either cited from the statement or listed with a reason. Also a generated cross-reference linking doc label, Rust item, Lean name and guest function.
  • crates/verifier/tests/lean_constants.rs checks every numeric verifier constant against the Lean.
  • LaTeX macros carry [rust: …; lean: …] names, checked.
  • Self-hosted runner and olean cache for tier B, never for fork PRs.
  • Ratchets: numbered values, compiler indices, parameter numerals and budget overrides become counts that may only shrink. A weekly size table is posted here.
  • Skills formal-statement-change, formal-debt-repair, formal-main-red, formal-statement-review and formal-docs-sync; formal/AGENTS.md shrinks to its rules, and the recipes move to formal/docs/.
  • Nightly job: cold build, random-seed fuzz, deployed-shape fixtures, and an upstream drift report.
  • Module headers (Rust:, Doc:, Category:) and Deviations blocks in every statement file.
  • Name-level layer check for Statement/.
  • Guard for Statement/Fast.
  • Rules for To* folders.

M2 Probes (in parallel with M1)

  • Guest meaning-layer probe.
    • A: a verification-condition generator on the real core IR re-proves sumcheck_round4 without a template. Done: 32 code lines instead of 186, about 3 s of elaboration instead of about 16, standard axioms only. Bodies over about 30 statements need a dedicated vc tactic, which lands before any port.
    • B: a source-level reference function for verify_merkle_cap, with automatic links to its 7 specialisations.
    • C: stress runs on a Keccak function and a level_residual specialisation.
  • Measure the hand edits of the field change (128 bits field #751) by cause, to decide whether a limb contract pays.
  • vp_chain and cost_bound tactics, one directory each.

M3 Consolidation

  • Normal forms for the bus, table sumcheck, Keccak, WHIR level loop, sumcheck and Merkle phases. Split Verifier/Phases.lean.
  • vp_chain replaces the 117 moves_/costs_/retOK_/allRet_ lemmas.
  • No parameter numerals in proofs (13708 and others).
  • Delete dead and duplicated protocol code, about 2.5k lines.
  • Stable names for cost-compiled functions, replacing 906 index references.
  • cost_bound registry.
  • Twins of the scheme proofs move to common, plus dead code and bundled contexts (after QROM sphincs #737).
  • Use VCVio's until-bad lemmas, CompPoly's vertex and CompPoly's additive NTT lemmas in place of local copies.
  • Seam for ArkLib's affine-combiner theorem. After ArkLib #1517, one bump deletes 12 local files (3,249 lines).
  • ISA equivalence theorem: constraints hold iff a valid execution exists.
  • LeanVmVerifier.lean follows crates/verifier file by file.
  • The honest prover's fast copies are generated, not hand-written.
  • Extractor reading guide.
  • Differential tests compare which named check rejected, not only the verdict.

M4 Guest meaning layer (after #755)

  • Stage V: the verification-condition generator and its vc tactic, ported directory by directory.
  • Stage S: one reference function and one hand proof per source function (130), linked automatically to the compiled specialisations (1,549).

M5 Structural

Upstream watch list

  • ArkLib #1517 (affine-combiner rename) and the announced interleaving theorem: one bump deletes 12 local files, and the interleaving theorem would replace 2 more.
  • ArkLib #1482 stack (composition of knowledge soundness): until it merges, protocol components stay local.
  • ArkLib #1491, #1333 and #1334 (sumcheck); Clean Prove leanXMSS guest program is equivalent to the cryptography specs implementation #494 (counted-read channel).
  • VCVio permutation and sponge work (none since fc54dd3d). VCVio has moved to Lean v4.36, so stay on v4.35 until there is a named gain.
  • CompPoly: irreducibility of E's modulus, an issue to open.
  • Pins are exact merged upstream commits, identical across the six manifests, with one library per bump.

In-flight PRs this plan works around

What does not change

No step changes what Statement.Theorems proves, except decisions D3 to D7. Any step that edits the statement ships a proved old ↔ new theorem, and the fingerprint shows the diff. While the debt ledger is non-empty, the end theorems on main depend on sorryAx and the axiom check says so; what is proved is then what holds at formal-proved.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions