Our SHA-256 circuit is one 184-row compression circuit repeated once per block, chained by feeding block i's output state into block i+1 (sha256_block_aligned_circuit). ConstraintGenerator flattens that as it builds, so Spartan receives a single matrix with no record of the repetition.
Every instance contributes 54,120 nonzeros to C, and A and B are empty. At 512 compressions that is 27,709,440 entries which are 512 identical copies of 54,120. bind_and_batch scatters all of them into a 2^24 dense table on the prover, evaluate_batched walks them again on the verifier, and both matrices and the table stay resident. Peak resident set for 512 compressions is around 4.5 GB against 218 MB for the same statement in BitZ-pcs. Memory, not time, is what caps the batch size we can prove at all.
The structure that is there
Rewriting every entry of instance i's rows as (owner instance - i, column within that instance, coefficient) and comparing across instances gives, at 6, 16 and 24 blocks alike:
C: one pattern for every instance, 54,120 entries, reaching only {constant, +0}. The batch matrix is exactly I_N (x) C_local, with no cross-instance term.M: three patterns. Instance 0 reaches {constant, +0}, every middle instance reaches {-1, +0} with 42,360 entries, and the final padding instance reaches {constant, -1, +0}.
The chain link lives in M, not in the R1CS, because the R1CS columns index the derived assignment h and each compression allocates fresh h entries even when they are combinations of a previous instance's committed bits. Nothing is shared in h; the sharing is in f, which M owns.
So collapsing the R1CS locally needs one 184-row matrix and no cross-instance handling. Collapsing M needs the three blocks above, where the -1 block is the successor relation on the instance index. Its multilinear extension has a closed form linear in the instance variables, splitting on the position where the increment stops carrying:
shift(x, y) = sum_k [prod_{j<k} y_j (1 - x_j)] (1 - y_k) x_k [prod_{j>k} eq(x_j, y_j)]
checked against brute-force summation over the hypercube at 200 random points for each width from 1 to 7.
What blocks it
Nothing records that the relation is a repetition. into_matrices flattens it, and the structure above only shows up if you go looking for it. Three Circuit backends would have to carry it: ConstraintGenerator for the local C, MTransposeGenerator for the three M blocks, and Witgen for the layout.
The committed witness is not instance-major. ConstraintGenerator::new preallocates every relation input first, so the layout is all blocks * 512 message bits followed by each compression's 6,376 hint bits, rather than one contiguous run per instance. A repetition-aware map wants the per-instance runs adjacent, so this reaches the input allocation and not only the map.
The coordinate convention is the one part that cannot live in crates/circuit. Once the map is I (x) local + S (x) prev + ..., the evaluation point has to split into instance coordinates and local coordinates, and LinearClaim and the packing that feeds it have to agree on which half is which.
The final padding instance is not a fixed block: it encodes the message length, so its entry count moves with the block count.
A relation of independent instances is the special case where M's -1 block is empty. Batched signature verification and recursive proof verification have that shape; VM execution traces chained through registers have the general one.
Depends: a way for crates/circuit to record repetition, which does not exist today.
Effort L.
September 2026 optimization-port audit
This section adds implementation evidence and completion criteria to the existing repetition issue. It does not change the existing logical relation or claim that the historical timings above are a new matched measurement.
Implementation references
The current global preparation path still constructs the expanded relation. The reference local SHA relation synthesizes one local circuit and retains its local matrices once, with implicit tensor repetition. Treat the target's executable SHA relation and layout contracts as normative; older illustrative row counts in related issues must be reconciled with the current implementation before hard-coding dimensions.
Required work
- Represent local constraint/map blocks, repetition count and first/middle/final-chain corrections explicitly.
- Share one source of truth for local/instance indexing across matrix contraction, witness synthesis, commitment packing and virtual transpose.
- Derive structured contraction/evaluation without expanding the repeated global matrix. Keep a bounded dense materialization only as a test oracle.
- Compute a canonical digest that binds the complete logical repeated relation and boundary corrections; compact metadata must not omit public shape.
- Preserve chain successor wiring, public IO and final padding semantics. Independent repetitions are the special case without predecessor wiring.
Done when
- Forward application, transpose and bilinear evaluation match the expanded oracle on small independent and chained instances.
- Boundary, non-power-of-two live count, constant-slot and final-block padding tests pass; mutated metadata/digests are rejected by composed proofs.
- Public setup memory scales with local topology and repetition metadata rather than repeated nonzeros.
- Benchmarks separately report setup, prover binding, verifier contraction and peak allocations/RSS at matched statement/security/thread settings.
- Any layout/proof-format change is explicitly versioned; otherwise continuing transcripts remain identical.
Related implementation work
This provides geometry for #77, #78, #86, #102 and #122; those own their protocol, packed-prefix, witness and opening kernels. Existing #17/#19/#20 remain the relation/protocol/matrix boundaries.
Potential impact: remove O(instances × local nonzeros) topology replication and enable factored O(local width + instances) coefficient processing. This is a structural estimate, not an independently measured speedup.
Our SHA-256 circuit is one 184-row compression circuit repeated once per block, chained by feeding block
i's output state into blocki+1(sha256_block_aligned_circuit).ConstraintGeneratorflattens that as it builds, so Spartan receives a single matrix with no record of the repetition.Every instance contributes 54,120 nonzeros to
C, andAandBare empty. At 512 compressions that is 27,709,440 entries which are 512 identical copies of 54,120.bind_and_batchscatters all of them into a 2^24 dense table on the prover,evaluate_batchedwalks them again on the verifier, and both matrices and the table stay resident. Peak resident set for 512 compressions is around 4.5 GB against 218 MB for the same statement in BitZ-pcs. Memory, not time, is what caps the batch size we can prove at all.The structure that is there
Rewriting every entry of instance
i's rows as(owner instance - i, column within that instance, coefficient)and comparing across instances gives, at 6, 16 and 24 blocks alike:C: one pattern for every instance, 54,120 entries, reaching only{constant, +0}. The batch matrix is exactlyI_N (x) C_local, with no cross-instance term.M: three patterns. Instance 0 reaches{constant, +0}, every middle instance reaches{-1, +0}with 42,360 entries, and the final padding instance reaches{constant, -1, +0}.The chain link lives in
M, not in the R1CS, because the R1CS columns index the derived assignmenthand each compression allocates freshhentries even when they are combinations of a previous instance's committed bits. Nothing is shared inh; the sharing is inf, whichMowns.So collapsing the R1CS locally needs one 184-row matrix and no cross-instance handling. Collapsing
Mneeds the three blocks above, where the-1block is the successor relation on the instance index. Its multilinear extension has a closed form linear in the instance variables, splitting on the position where the increment stops carrying:checked against brute-force summation over the hypercube at 200 random points for each width from 1 to 7.
What blocks it
Nothing records that the relation is a repetition.
into_matricesflattens it, and the structure above only shows up if you go looking for it. ThreeCircuitbackends would have to carry it:ConstraintGeneratorfor the localC,MTransposeGeneratorfor the threeMblocks, andWitgenfor the layout.The committed witness is not instance-major.
ConstraintGenerator::newpreallocates every relation input first, so the layout is allblocks * 512message bits followed by each compression's 6,376 hint bits, rather than one contiguous run per instance. A repetition-aware map wants the per-instance runs adjacent, so this reaches the input allocation and not only the map.The coordinate convention is the one part that cannot live in
crates/circuit. Once the map isI (x) local + S (x) prev + ..., the evaluation point has to split into instance coordinates and local coordinates, andLinearClaimand the packing that feeds it have to agree on which half is which.The final padding instance is not a fixed block: it encodes the message length, so its entry count moves with the block count.
A relation of independent instances is the special case where
M's-1block is empty. Batched signature verification and recursive proof verification have that shape; VM execution traces chained through registers have the general one.Depends: a way for
crates/circuitto record repetition, which does not exist today.Effort L.
September 2026 optimization-port audit
This section adds implementation evidence and completion criteria to the existing repetition issue. It does not change the existing logical relation or claim that the historical timings above are a new matched measurement.
Implementation references
The current global preparation path still constructs the expanded relation. The reference local SHA relation synthesizes one local circuit and retains its local matrices once, with implicit tensor repetition. Treat the target's executable SHA relation and layout contracts as normative; older illustrative row counts in related issues must be reconciled with the current implementation before hard-coding dimensions.
Required work
Done when
Related implementation work
This provides geometry for #77, #78, #86, #102 and #122; those own their protocol, packed-prefix, witness and opening kernels. Existing #17/#19/#20 remain the relation/protocol/matrix boundaries.
Potential impact: remove O(instances × local nonzeros) topology replication and enable factored O(local width + instances) coefficient processing. This is a structural estimate, not an independently measured speedup.