Track M31 collision probability for fused-constraint range check tables #275
Description
Context
The range check optimization in PR #271 uses a LogUp-style lookup argument where a random Fiat-Shamir challenge X appears in denominators of the form 1 / (X - t_j) for each table entry. This is the same technique used in #270 for binop tables.
With MAX_BASE_WIDTH = 17, the largest possible range check table has 2¹⁷ = 131,072 entries.
Current State (M31)
Over M31 (p = 2³¹ - 1), the collision probability is:
P(collision) ≈ 2¹⁷ / 2³¹ ≈ 2⁻¹⁴ ≈ 1 in 16,384
A collision means X = t_j for some table entry, which makes the fused constraint (X - t_j) × quotient = multiplicity trivially satisfiable. This could compromise soundness if exploited.
Comparison with #272
| Optimization | Table Size | Collision Probability |
|---|---|---|
| Binop tables (#270) | 2¹⁶ | 2⁻¹⁵ ≈ 1 / 32,768 |
| Range check tables | 2¹⁷ | 2⁻¹⁴ ≈ 1 / 16,384 |
Action Required
No immediate action needed. Revisit if stricter security bounds are required or if MAX_BASE_WIDTH needs to match #272's bound.