Spread trick unsound for small fields (M31)

Begin by reading r1cs-compiler/src/spread.rs and r1cs-compiler/src/sha256_compression.rs, including the compile-time modulus guard and the listed spread-based operations. Done means the SHA256 spread approach is sound for M31 as well as bn254, with carry ranges, spread sums, and recomposition coefficients handled without field-wraparound gaps.

Description

The spread-based SHA256 implemnted in PR #284 implementation requires p >> 2^64. Three independent constraints break for small fields like M31 (p = 2^31 - 1):

1. Spread sum overflow

The 3-way Maj computation sums three spread values:

spread(a) + spread(b) + spread(c)

The maximum spread value is:

spread(0xFFFFFFFF) = 0x5555555555555555

So the 3-way sum reaches:

3 × 0x5555555555555555 = 2^64 - 1

This wraps in any field with p < 2^64.

Requires: p > 2^64

2. Spread recomposition coefficients

Spread decomposition uses coefficients 4^k to position spread values at the correct bit offset.

The largest coefficient is:

4^31 = 2^62

If p < 2^62, these coefficients wrap and the recomposition constraint becomes unsound.

Requires: p > 2^62

3. Carry range check

In add_u32_addition_spread, the carry is range-checked to [0, 255] via the spread table.

The constraint:

sum = result + carry × 2^32

has intermediate values up to:

255 × 2^32 ≈ 2^40

For M31, field wrapping allows a malicious prover to satisfy the range check with an incorrect carry.

Requires: p > 2^40

Current State

All three are sound for bn254 (p ≈ 2^254).

A compile-time guard has been added:

assert!(FieldElement::MODULUS_BIT_SIZE > 64,
    "Spread trick requires p >> 2^64; unsound for small fields like M31");

What Needs to Change for M31

The entire spread approach would need redesign for small fields.

Key changes:

• Carry: Use tight range check [0, N-1] based on operand count instead of [0, 255]
• Spread sums: Split multi-way XOR/AND into a tree of 2-way operations that fit in the field
• Coefficients: Use multi-limb representation or a different decomposition strategy

Impact

Affected code:
r1cs-compiler/src/spread.rs
r1cs-compiler/src/sha256_compression.rs

Affected operations:
All spread-based SHA256 operations (Σ₀, Σ₁, σ₀, σ₁, Ch, Maj, message schedule, compression rounds, u32 additions)