Repository navigation
Description
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
fa4b43935in about 100 minutes on a 32-core host. But the Lean job is red or cancelled on mostmainpushes, for two reasons:- A Rust rename in
d41a32045broke a Rust helper underformal/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
mainare never checked: 18 of the last 30 runs were cancelled.
- A Rust rename in
- 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
maincommits 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/precheckruns 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 touchformal/,crates/,guests/ordoc/. 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 rollingmain-redissue 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 withackorrevert. -
Proof debt. When a statement change breaks proofs, the failing proof bodies become
sorryand are listed informal/debt.toml. Statements are never sorried, and nothing inStatement/is.- A kernel sweep checks that every
sorryis 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.
- A kernel sweep checks that every
-
Skills. Tool-neutral Markdown skills in
formal/skills/:formal-precheck,formal-statement-change,formal-debt-repair,formal-main-red,formal-statement-reviewandformal-docs-sync. Each records the rule, not the incident, andformal/AGENTS.mdshrinks to one-line rules. -
Ratchets. Migration targets become counts that may only shrink: numbered values in B1, compiler indices in Cost, parameter numerals, and
maxHeartbeatsoverrides. 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 failsrust.ymlin minutes. Fix the current break. - Split
lean.ymlinto 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
mainwrites the build cache.
-
formal/tools/precheckand the Claude Code hook ongit push; optional gitpre-pushhook. -
main-redissues 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.
CODEOWNERSfor the PRs that exist. -
formal/tools/cite-check.pywith forward checks: every cited Rust path, Rust item and doc label exists. Folds intools/docnames.py. - Skill
formal-precheck.
M1 Gates complete
- Debt ledger
formal/debt.tomlandlake exe debtsweep --check, certified by planted fixtures. Replay four weeks ofmainto fix the bounds. Add theformal-provedtag and theformal-debtissue. - 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-checkreverse coverage: everypubitem and check site ofcrates/verifieris 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.rschecks 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-reviewandformal-docs-sync;formal/AGENTS.mdshrinks to its rules, and the recipes move toformal/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_round4without 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 dedicatedvctactic, 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_residualspecialisation.
- A: a verification-condition generator on the real core IR re-proves
- Measure the hand edits of the field change (128 bits field #751) by cause, to decide whether a limb contract pays.
-
vp_chainandcost_boundtactics, 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_chainreplaces the 117moves_/costs_/retOK_/allRet_lemmas. - No parameter numerals in proofs (
13708and others). - Delete dead and duplicated protocol code, about 2.5k lines.
- Stable names for cost-compiled functions, replacing 906 index references.
-
cost_boundregistry. - 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
vertexand 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.leanfollowscrates/verifierfile 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
vctactic, 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
- Per-function rebuild cones, mainly on the Lean side, by relocating the certificates.
- Layer-indexed XMSS proof and one FORS potential.
- Exit test: replay three past changes and a synthetic guest edit against the targets.
- Only if formal: compile the guest with a verified Lean back end; delete the per-function certificates #756 lands: a verified front end.
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
- FV witness gen #755 and QROM sphincs #737: the guest and scheme work waits for them.
- formal: compile the guest with a verified Lean back end; delete the per-function certificates #756: assumed not to land. If it does, B1 changes only in its imports and the verified front end opens.
- XOR/MUL immediates and DISPATCH: -25% single-thread proving at 1440 leanXMSS #778, Keccak reduction: commit no middle state (KECCAK_DEPTH 24) #777, memory: announce N_mem and commit only the cells a run covers (-15% committed, M 27->26, -11% proving) #718 and Stack table columns as up to three dyadic runs: padding rows are committed nowhere #779: each gets a row in the change playbook.
- formal: scaffold the Rust-to-Lean extraction (hax), after Plonky3-lean #736, verification: the Rust WHIR verifier refines the Lean model, via Aeneas #632 and FV rust verifier via riscV #738 (Rust extraction): complementary. If one lands for a kernel, the target is a refinement theorem against the transcription.
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