wrap chain — prover memory and time, verifier time, 2026-10-10

superseded (2026-10-27): the chain 4i:16,8i,9f:24 below became 4i:16,7i:22,9f:26 (zheng#61, proof-stack-review-2026-10.md). the .stands/ checkouts named below were removed in the cleanup of 2026-10-16; the revisions they held are named here, the directories are gone.

Follow-up to audit/wrap-2026-10.md (zheng #56, feat/wrap 606cda1). Goals: the final proof verifies in ≤ 1 ms, stays ≤ 64 KB, every ledger row ≥ 128 bits (grinding priced; interactive figures stated); the wrap chain proves in seconds, not 13–20 minutes, in far less than 32–38 GB. Branch feat/wrap-fastverify (stand .stands/V: B's siblings, lens feat/field-native-whir c91f55a, hemera cf28a64). Apple M4 Max (12 P + 4 E cores), 48 GB, rustc 1.95.0, --release.

Machine load. The machine was shared with other agents during every run: load average 22–103 (sampled per run below). Wall-clock times are upper bounds and vary 2–5× between runs of the same binary; the tables give the run's load. A verifier's one-thread CPU time (clock_gettime of the verifying thread) is load-independent up to core type (P vs E) and is reported beside wall time. Sizes and permutation counts are deterministic.

1. what changed

Wire format: the final proof's byte layout is unchanged (same fields, same order); its shapes follow the new parameters (final level 1/512, 24 grinding bits: round queries 24 / 18 / 15) and its transcript absorbs two messages as digests, so proofs of feat/wrap and of this branch do not verify under each other's keys. Envelope profile 6 must take the new final key (the chain wrap::SHIPPED).

2. gates

Fixture add.tri (7, 5), 33 cycles, one IVC step (IVC proof stored and reused, ZHENG_IVC_DIR). Before: audit/wrap-2026-10.md (same machine, load 13–40). After: this branch, chain 4i:16,8i,9f:24.

Permutations per verification (deterministic): before ≈ 1,000 batched + the transcript's (not counted); after 107 one at a time + 1,500 batched (the parse's multi-opening expansion; the verifier's Merkle check reads those permutations instead of recomputing them).

3. ledger

wrap::ledger per level (recursion::wrap::review::the_shipped_wrap_levels_reach_128_bits_and_their_interactive_rows_are_stated):

The final level's rate cannot rise further without grinding above 24 bits: at 1/1024 the Johnson-regime fold terms (BCGM MCA error grows with the domain) need 25+ bits per fold challenge (wrap_plan 14 10 …). At 1/256 with 20–22 grinding bits the opening alone is 61–62 KB (with the 6 KB of header, claim and AIR, over 64 KB). The inner 1/256 level is fixed by the final circuit: at 1/128 the final circuit outgrows 2^14 rows (wrap_chain 6i,7i,9f:24).

New row: final-level message digests (soundness.md): binding is the hash row's collision resistance.

4. where the time goes now

Prove, chain 4i:16,8i,9f:24 (wall, load 24–41; ZHENG_TIMING):

Hashing the commitments (leaf sponges and tree nodes, hemera batched) is ≈ 70 % of the chain (≈ 59 of 83 s), grinding ≈ 20 % (≈ 15 s); both are the GPU backend's (feat/gpu-backend). Per proof the calling thread's CPU is 1–3 s a level: the rest runs on every core.

Verify, one thread, CPU time of the verifying thread (ZHENG_TIMING, add.tri): parse 1.5 ms (decoding; expanding the multi-openings: 1,460 batched permutations), the nox-public claim 0.06, the public digest 0.12, zerocheck 0.12, the key's 64 used columns at ρ 0.5–0.9, the constraint graph (7,506 operations) 0.05–0.15, the opening's rounds and final queries 0.6 (transcript: 107 single permutations ≈ 0.31 ms of hemera's 2.9 µs latency), the closing check 2.3 (the wiring u_λ over 49,333 reads and 23,892 writes: one Fp3 product per slot), the Merkle check 0.1 (the parse's permutations recalled). On 16 threads the closing, the key, the Merkle checks and the expansion of the three trees run in parallel; what stays on one thread is ≈ 1–1.3 ms (the transcript, decoding, zerocheck, the round-0 tree's expansion, the public digest) — the floor of this design on a quiet machine, above the 1 ms goal.

5. checks

6. what is left

• verify ≤ 1 ms: missed. One thread 5.3–5.7 ms; sixteen threads min 2.8 ms under load, ≈ 1–1.3 ms of single-thread work left. Levers: fewer serial transcript permutations (zerocheck messages, fold rounds: a lower-latency single permutation — hemera's inverse chain is 2.2 of its 2.9 µs — or fewer rounds); the round-0 tree's expansion (≈ 0.45 ms, one level at a time); decoding without per-query clones; a quiet machine to measure on.
• prove in seconds: 83 s for the chain (from 985 s), IVC 27–44 s per step. Hashing and grinding dominate (GPU backend). Algorithmic levers not taken: a rate-12 leaf sponge (Fp3 leaves 6 → 4 permutations; changes the circuit's permutation rows); the inner 1/256 level's key words in the base field (key columns split in limbs: the key group's leaf 11 → 4 permutations in the final circuit, room to lower that level's rate); IVC grinding (22–24 bits per challenge, half of the decider's time) needs the step circuit re-fitted.
• memory: 19.5 GB peak, ≈ 7 GB of it the keys of every level (the IVC key's held key words, the 1/256 key words' tree). A prover that holds only the next level's key would stay near 10 GB.
• rec-16 not re-run (its IVC proof is 45 min); proof sizes and the final circuit are flat in the run length (audit/wrap-2026-10.md).
• the deferred nox-public claim still travels (1,272 B).

7. second round, 2026-10-13 (after the review merge, 5ec724e and later)

Measured on a nearly quiet machine (1-minute load 4–8 at the start of each run; the chain's run rose to 28). Same fixture (add.tri), chain wrap::SHIPPED = 4i:16,8i:24,9f:24, IVC at ivc::SHIPPED_POW = 16.

CPU per level (all threads, the run above): IVC 84 CPU-s (step 65, decider 19); wrap 0 84, wrap 1 556, wrap 2 380 CPU-s. The 1/256 level's commitments and its 24-bit grinding are the chain's largest cost.

What changed since §2:

• IVC grinding 16 bits per challenge (ivc::SHIPPED_POW; the step circuit fits 29,628 of 2^15 rows; examples/ivc_plan plans step size, rate and grinding without proving). Recursion ledger: every row ≥ 128, interactive weakest 111.34 (104.01 at 24 bits) — soundness.md § recursion.
• zerocheck prover: each line walked by additions; the first round in mixed base/Fp3 arithmetic (air::mix); the round's eq factor taken out (h = L·q, q at 8 points, 7 in the first round). Messages unchanged. The step's zerocheck went from 37 to 15.7 CPU-s.
• memory: key words always streamed; streamed trees keep no leaf level; streamed cosets as limb vectors written in place; wrap_bench holds two keys at a time.
• verifier: multi-openings expanded chain by chain in parallel; direct-opening folds in parallel (native interpreters only); parallel eq tables. With 4, 8 and 16 threads the warm verify is 2.80, 2.57 and 2.52 ms: ≈ 2 ms of it is one thread's work (the transcript's 107 single permutations ≈ 0.3 ms, decoding and the shared tree tops ≈ 0.45 ms, the pool's passes and the remaining serial arithmetic). Spinning pool workers were tried and made it slower (4.9 ms: they take cores from the verifying thread).

Still open: verify ≤ 1 ms (2.5 ms now, single-thread bound); the chain in seconds (97 s quiet; the 1/256 level is ≈ 55 % of it — lowering its rate needs ≈ 300 fewer rows in the final circuit, e.g. base-field key words: the key's 12 Fp3 gate-coefficient columns make the key group's leaf 11 permutations instead of 4); a 16 GB laptop is within reach (10.6 GB footprint).

8. a hard size bound; the integrated stack (2026-10-13, feat/proof-stack)

• wrap::max_proof_bytes bounds the outermost proof over every transcript: all message shapes are the key's; a multi-opening of q leaves carries at most Σ (a·n_{l+1} − n_l) siblings, n_l = min(q, nodes at level l) (exact). Shipped chain: 65,177 B ≤ 65,536, with no parameter change (a looser per-level bound gave 66,905 B and would have needed 27 grinding bits at the final level). The measured proofs (63,257–64,217 B) sit 1–2 KB under it.
• The envelope's MAX_PROOF_BYTES is wrap::MAX_FINAL_BYTES; the admitted final key is checked against it. The envelope itself adds its header, the chain and the statement (≈ 0.6–0.9 KB for small programs).
• Integrated with #57 (profile 6) and #59 (GPU backends): profile-6 envelopes of hash.tri 64,003 B and tree-12 63,772 B; joy proves loop.tri wrapped in 75 s on Metal and 170 s on the CPU backend (keys derived in-process; load 12–50), peak 13.7 GB.

9. the size gate at 26 bits; inner keys over the base field (2026-10-13)

Gate. wrap::max_proof_bytes(final key) ≤ 64 KiB, hard, by key. At the coordinator's decision the final level grinds 26 bits (9f:26): the outermost proof is ≤ 64,213 B over every transcript, so a profile-6 envelope is ≤ 64 KiB whenever its encoded statement takes ≤ 1,272 B (specs/recursion.md § size gate). Ledger: final weakest 128.43, interactively 102.62 (fin after 26 query-grinding bits; review D1: shift_2 is 104.00).

Split key (feat/split-key, stacked on #60). An inner level's key columns with Fp3 entries (the four gates' qa, qb, qc: 12 of 108) are committed as their three limbs, every column over the base field — 132 physical columns in three base words under one tree; the prover sends the physical columns at ρ, the verifier rebuilds the logical ones for G and batches the physical ones over 8 variables (recursion::splitkey; ledger row γ_k 189.0). The key group's leaf costs the next circuit 6 permutations instead of 11, so the final circuit verifying a 1/128 second level fits 2^14 (16,230 of 16,384 rows; 15,236 at 1/256). Shipped chain 4i:16,7i:22,9f:26; level 1 weakest 128.08, interactively 102.35 (its combination after 26 bits: five words now; level 0 108.92 after 20 combination bits — corrected by audit/proof-stack-review-2026-10.md D1, the earlier 102.76 / 109.34 priced two key words). WRAPPED_FORMAT 5; INNER_ROOTS, WRAPPED_DIGEST re-pinned.

Measured (machine shared, load 15–56; add.tri unless named):

Checks on the split-key branch: cargo test --release -p zheng all suites green (297 lib); ignored tests/wrapped_envelope.rs 4/4, its bit-flip sample 3,036 tried, 0 accepted; tests/wrap_fastverify_review.rs --ignored on stored proofs green; wrap_flip: 503,720 flips, 502,921 decoded, 0 accepted (567 s); joy e2e profile-6 test green.

Cost found: the final level's fold grinding. At a 26-bit budget lens's schedule picks, per round, the regime with the fewest queries, and for the final level's last round that regime needs 25-bit grinding before each of its four folding challenges (at 24 bits: 22). The final level's CPU rose from ≈ 380 to 724 CPU-s, ≈ 270 of them that grinding. The size gate needs the 26 bits on the queries only (one query fewer in the last round); a schedule with separate query and fold budgets (26 / 22) would keep the bound and drop that cost — a lens schedule option (WhirConfig::derive couples them today).

10. separate query and fold grinding budgets — evaluated, not adopted (2026-10-13)

lens feat/whir-fold-budget (8ec1f2b, on a3ce318): WhirParams::fold_pow_bits (0: pow_bits; a version-2 header carries it), queries grinding pow_bits, each round's regime chosen within the fold budget; lens's 39 rspcs tests pass with a test of the split schedule.

The size gate's last-round query saving (15 → 14) does not come from the 26 query bits: at rate 1/512, ℓ = 20 the last round reaches 14 queries only through the Johnson regime that grinds 25 bits before each of its four folds; within a 22–24-bit fold budget it needs 15 at 26 query bits and 14 only from 27. The final level's grinding (permutations per proof: query grinds once per round, fold grinds once per folding challenge):

Every configuration meeting the 64,213 B gate grinds at least as much as the shipped one, so zheng keeps 9f:26 and the lens branch is not merged into the stack. The lever left is a per-round query budget (24 bits in rounds 0 and 1, 27 in the last with 22-bit folds: ≈ 190 M, about 45 % less) — a further schedule option, not built.

11. the stack at merge time (2026-10-13, #61 on #60 on #58)

Measured 18:24–18:33 (1-minute load 5–20 except the verify runs, 51); chain 4i:16,7i:22,9f:26, IVC at 16 grinding bits; Metal and CPU give the same bytes.

Against #56 (audit/wrap-2026-10.md): the wrap chain alone took 985 s; now a whole profile-6 prove (IVC and wrap chain) of hash.tri takes 36.8 s on Metal and 73.7 s on the CPU (the joy prove of loop.tri, keys included, 46 s), peak memory from 32–38 GB to 14.2 GB, verify from 6.4–7.2 ms to 2.5 ms on 16 threads (10.1–10.9 → 5.1 ms on one), the proof bounded by construction at 64,213 B. Checks: zheng suites green on #61, the bit-flip scan (503,720 flips, 0 accepted) and the ignored envelope tests (bit-flip sample 0 accepted) on #61's code; joy's 34 suites and the end-to-end profile-6 test green on it. joy wraps by default from 16 GiB available (the 14.6 GB peak plus 15 %).

Open: verify ≤ 1 ms (≈ 2 ms of single-thread work); the final level's grinding (a per-round query budget, §10).