Track M31 collision probability for combined AND/XOR lookup table optimization
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Stale
- Domain
- cryptography, security
Research direction
Start by reading PR #270 and the combined AND/XOR lookup-table optimization; this issue names no files or tests. Revisit the denominator collision behavior if ProveKit moves to M31 or another small field, and document or implement a sound approach for handling the resulting collision probability.
Written by the indexing model from the issue text.
Description
Context
The combined AND/XOR lookup table optimization introduced in PR #270 uses a LogUp-style lookup argument where a random Fiat-Shamir challenge γ appears in denominators of the form 1 / (γ - tᵢ) for each of the 65,536 table entries.
Current State (BN254) — No Issue
Over BN254 (p ≈ 2^254), the probability that γ collides with any table entry is:
P(collision) ≈ 65,536 / 2^254 ≈ 2^(-238)
This is cryptographically negligible.
Future Concern (M31)
If ProveKit migrates to M31 (p ≈ 2^31), the collision probability becomes:
P(collision) ≈ 65,536 / 2^31 ≈ 2^(-15) ≈ 1/32,768
This would need further investigation, a collision means γ = tᵢ for some table entry, which causes division by zero in the lookup argument and could compromise soundness. Whether this probability is tolerable depends on the target security level and usage context, but it warrants careful consideration before adopting this optimization over a smaller field.
Action Required
No action needed while using BN254. Revisit this optimization if/when migrating to M31 or other small-characteristic fields.
- Dominant language
- Noir
- Stars
- 138
- Forks
- 47
- Avg merge
- 1d 34m
- Merged PRs (30d)
- 6
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from worldfnd/provekit
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 1/5 Under an hour Newbie friendliness 68/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
All issues in worldfnd/provekit
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
aegis-aead/libaegis#35 ·
-
enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
snapshot-labs/snapshot.js#1247 · 1 comment ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
ietf-plants-wg/merkle-tree-certs#323 · 1 reaction ·
-
DataRowRecord JSON key order differs from canonical output (breaks raw-string ciphertext detection) Openbug documentation rust
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
godaddy/asherah-ffi#392 ·