Read the assignment as packed bits instead of a dense field MLE

[shreyas-londhe]

The assignment h is a vector of bits, but build_assignment_mle turns it into one field element per bit, each holding either F::ONE or F::ZERO. At 512 compressions the column domain is 2^24, so the table is 2^24 values of Fq<Q100> carrying one bit each. Sixteen bytes to hold one bit.

It is then copied and expanded again. prove_inner_sumcheck takes the table by value and allocates a half-length scratch buffer beside it, and the prover has to hand it a fresh copy for every proof because folding consumes it. Three tables of that shape are alive at once.

Round zero is where the bits stop being bits. Folding by the first challenge turns them into real field elements, so only the input table can stay packed.

What it could win: the input table shrinks by a factor of 128, from 2^24 field elements down to 2^24 bits. The scratch buffers stay as they are. So the live footprint at that point goes from three full tables to roughly one and a half.

BitZ reads packed bits through a source trait rather than a table (Sha256InnerBitSource, src/piop/spartan/sha256/inner_sumcheck.rs:40).

Effort M.

Current optimization audit — 2026-09-23

This section supersedes historical implementation descriptions, cost claims, and estimates above where they conflict with the current target. The earlier body is retained for context.

Extend #46 to consume packed assignment bits and optionally prepare k=1..4 ordinary inner rounds using small-value ternary buckets.

Current behavior and sources

The current target borrows the field-expanded witness, so the cloning description above is stale. The input remains sixteen bytes per logical bit. The PoC also goes beyond the older single-round proposal: it prepares up to four ordinary rounds while retaining packed input bits.

The target's current field profile, relation, index ordering, transcript, and terminal-claim contracts remain authoritative (including #19 and the specification tracked by #2). The current target implementation establishes the behavior to preserve. The PoC implementation reference is an implementation reference, not a replacement protocol specification. Preserve the target arithmetic representations; convert explicitly when crossing between canonical Barrett field elements and tape Montgomery residues.

In scope

• Provide checked packed-word and lazy bit-source access; validate live length and canonical trailing zero bits.
• Precompute 3^k small prefix buckets, derive each ordinary message only after previous transcript challenges, and build the field tail after k variables. Keep k=0 as a reference/fallback.
• Use Defer Barrett reduction in the Spartan sumcheck round bodies #47 bounded mixed accumulators. Keep source and coefficient representations separate so factored coefficients can be added independently.

Done when

• Compare exact messages, sampled points, terminal weight/witness evaluations and continuing transcripts across k=0..4 and serial/parallel execution.
• Cover all-zero/all-one bits, singleton and empty-tail cases, word/instance-boundary crossings, zero/one challenges and partial final words; reject noncanonical padding and dimensions.
• Preserve proof messages, Fiat–Shamir absorb/squeeze order, verifier-derived points and final PCS handoff; assert transcript-byte equivalence against the existing implementation for valid inputs.
• Report matched release-build phase timings and named-buffer/peak-memory measurements with fixed field, input, compiler, thread count and proof validation. State regressions and setup amortization separately.

Impact and boundaries

Packed witness payload is 128× smaller than one 16-byte field element per bit, excluding coefficients/buckets. Early full-field witness tables are deferred; the entire prover does not gain that memory ratio. Every ordinary round and message remains: this is not a univariate-skip protocol. Wall-clock improvement is unmeasured on the target and is not an acceptance assumption.

Out of scope: changing the relation, field/security profile, proof format, PCS, or transcript; unrelated refactors and new workload support.

Depends: #47. Related: #19, #41, #47, #50.

Difficulty: hard; urgency: high. High priority memory/arithmetic port. Hard difficulty reflects multi-round preprocessing, small signed extension bounds and exact transcript equivalence; the historical three-table memory estimate above is superseded.