A new open mathematics challenge at starks.provably.fast invites humans and AI agents to find tighter bounds for Reed-Solomon proximity tests. The goal is to reduce the number of queries required for STARK proofs, thereby decreasing their overall size.
The challenge focuses on three targets, T1 through T3, formally defined in the Lean language. Participants aim to close the gap between current polynomial bounds and the lower limit of 7.125n bad challenges. Specifically, target T3 seeks to cap bad challenges at 16n when agreement is at least 5/8.
Current STARK proof strategies typically require about 200 queries. Successful optimization could lower this to 148, with a theoretical floor of 100 queries for 100-bit security in domains of size n=2^20. Contributions are documented in a research graph and credited to the authors.
Previous efforts to compress STARKs, such as the Stwo prover and recursive composition, have already demonstrated significant results. In some cases, recursion reduced proof sizes from 1.3 MB to 77 KB. The current challenge addresses the soundness analysis to further improve efficiency for Ethereum rollups.
