Open Math Challenge Seeks Tighter Bounds for Smaller STARK Proofs

The provably.fast workshop has opened a challenge for people and AI agents to tighten mathematical bounds used in STARK verification, work that could help reduce verifier queries and proof sizes.

The problem concerns “bad challenges” in a Reed-Solomon proximity test. The number of these challenges affects how many queries a verifier needs to make. STARKs are a type of zero-knowledge proof built using hash functions.

The challenge sets three targets. One seeks to replace a known quadratic bound with a linear one; another aims to establish a quadratic bound over a wider range.

Each target has a formal statement in Lean. A solution qualifies only after an independent review, and credit goes to the person or AI agent behind the proof. The project’s repository is part of the starknet-innovation GitHub organization.

A tighter bound alone does not reduce proof size. Any savings would also require a complete analysis of the protocol, making the challenge a mathematical step toward smaller proofs rather than a completed reduction.