A live challenge invites humans and AI agents to prove bounds that would let STARK proofs make fewer checks and take up less space
STARK proofs are some of the most trusted tools in crypto’s scaling toolkit. They are also, by cryptographic standards, a bit bulky.
A new open mathematics challenge hosted at starks.provably.fast wants to fix that. Its tools are proofs about polynomials rather than new hardware or clever engineering, and it is inviting both humans and AI agents to supply them.
The pitch is simple. If mathematicians can prove better bounds on a specific kind of error, STARKs can safely run fewer checks, and fewer checks mean smaller proofs.
What the challenge actually asks for #
STARKs are zero-knowledge proofs that rely on nothing more than a hash function. That minimalism is a big part of their appeal: no trusted setup ceremony, and security assumptions that are widely considered resistant to quantum attacks.
The tradeoff is size. STARKs currently need more queries than SNARKs, their main rival family of proof systems, which pushes proof sizes into the range of tens to hundreds of kilobytes.
The challenge targets a component called a Reed-Solomon proximity test. Think of it as a spot-check: the verifier pokes at random points of a dataset to confirm it really comes from a well-behaved polynomial, rather than reading the whole thing.
The weak spot is what researchers call “bad challenges.” These are random queries that happen to fool the verifier into accepting something it should reject.
The fewer bad challenges that can exist, the fewer spot-checks a verifier needs to reach a given level of confidence.
The challenge lists three targets, labeled T1 through T3. Each one is stated formally in Lean, a language that lets computers mechanically verify whether a mathematical proof is correct.
The numbers behind the gap #
The current state of knowledge is lopsided. Known results provide polynomial bounds on the number of bad challenges, which is a looser guarantee than cryptographers would like.
The news moving money, markets, and the world—before your day starts.
Daily. Free. Join 34,000+ readers across crypto, finance, and policy.
On the other side, certified counterexamples show roughly 7.125n bad challenges can occur at a rate of 1/2. Any valid upper bound therefore has to sit above that mark.
The goal is to close the distance. The challenge seeks an O(n) bound, meaning one that grows in a straight line with the size of the domain, with a ceiling of at most 16n in cases involving large-characteristic multiplicative cosets.
T3 is the most concrete of the three. It aims to cap bad challenges at 16n when agreement is at least 5/8, at a rate of 1/2.
Current proof strategies rely on approximately 200 queries. Optimizations could bring that down to 148, and in theory as low as 100 queries for 100-bit security in domains of size n=2^20.
Credit as the currency #
The challenge is structured as an open, collaborative effort. Accepted contributions, whether a single lemma or a complete proof, get documented in a research graph.
Every find is credited to whoever made it, person or AI agent. The recognition is academic, which makes this closer to a public research project than a bounty hunt.
Background: STARKs have been slimming down #
This is not the first push to compress STARK proofs. The technology is closely tied to the StarkWare and Starknet ecosystem, which has been building STARK-based systems for Ethereum scaling.
Recent work has already moved the needle. Circle STARKs, used by the Stwo prover, and recursive composition techniques have shown significant compression in practice.
In certain practical instances, recursion experiments with Stwo reduced proof sizes from 1.3 MB to 77 KB.
Recursion works by proving the validity of other proofs, folding many into one. The math challenge attacks the problem from a different angle, going after the soundness analysis that determines how many queries each proof needs in the first place.
What this means for STARK-based networks #
For networks like Starknet, proof size is a cost line. Smaller proofs could mean cheaper verification and improved efficiency for rollups that settle on Ethereum, where data is never free. STARKs have long traded size for transparency and post-quantum security, while SNARKs have offered compact proofs with different assumptions. If tighter bounds let STARKs drop toward 100 queries, that tradeoff narrows.
There are caveats. The 100-query figure is a theoretical floor, not a guarantee, and it depends on someone actually proving the target bounds.
The thing to watch is the research graph itself. Progress on T1 through T3, and who or what supplies it, will offer an early read on whether STARK proofs can shed more weight, and on whether AI agents are ready to contribute real results to cryptographic research.
Disclosure: This article was edited by Estefano Gomez. For more information on how we create and review content, see our Editorial Policy.