Spread trick unsound for small fields (M31) #285
Description
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)