Introduction
This paper provides a major theoretical upgrade to our understanding of proximity gaps in Reed-Solomon codes—a mathematical phenomenon that underpins the security of STARK-based blockchain systems. By refining classical decoding algorithms, the authors prove significantly tighter bounds on "soundness error," effectively showing that these cryptographic proofs are more robust and potentially more efficient than previously proven.
The Proximity Gap Problem
In the world of zero-knowledge proofs and STARKs, we often need to verify that a large vector of data is "close" to a Reed-Solomon (RS) code (i.e., it represents a low-degree polynomial). To do this efficiently, we take a random linear combination of two vectors, $f + z \cdot g$, and check if the result is close to the code.
The proximity gap phenomenon asks: if the combination $f + z \cdot g$ is close to the code for many different values of $z$, does that guarantee that $f$ and $g$ were themselves close to the code? Quantifying this is critical. If the "gap" is small, a malicious prover could find a few "lucky" $z$ values to fool the verifier. Previous bounds were somewhat loose, requiring either very large fields or many expensive queries to ensure security. This paper aims to find the optimal quantitative limits of this phenomenon.
Methodology
The authors approach the problem by viewing the random combination through the lens of decoding algorithms over rational function fields.
Positive Results (Upper Bounds)
They adapt the classical Berlekamp–Welch (for unique decoding) and Guruswami–Sudan (for list decoding) algorithms. Instead of working over a standard finite field, they work over the field of rational functions $\mathbb{F}_q(Z)$.
A key innovation is the introduction of "slack"—oversizing the interpolating polynomials. By making the linear systems in these algorithms significantly under-determined, they can find solutions with much lower degrees in the variable $Z$. They describe this as a polynomial analogue of Siegel’s Lemma from number theory.
Negative Results (Lower Bounds)
To show where proximity gaps fail, they use the algebraic structure of $\mathbb{F}_2$-linear subspaces and "subspace polynomials." They employ the second moment method to prove the existence of "bad" configurations where many linear combinations look like codewords, even though the underlying vectors are far from the code.
Key Insights and Results
The paper establishes several new state-of-the-art bounds for Reed-Solomon codes with relative distance $\delta$. The most significant improvements are found in the unique decoding and Johnson radius regimes.
- Constant Exceptions at Unique Decoding: For proximity gaps up to half the minimum distance ($\gamma < \delta/2$), the authors show you only need a constant number of "exceptional" $z$ values to achieve arbitrarily small proximity loss. Previously, this was thought to scale with the length of the code ($n$).
- Linear vs. Quadratic Exceptions: At the Johnson radius, they improved the bound for exceptional $z$ values from $O(n^2)$ down to $O(n)$. This directly translates to a significant reduction in the soundness error for STARKs.
- The Johnson Radius is a Hard Wall: The paper refutes a popular conjecture that proximity gaps could be bounded by a small polynomial ($n^\tau$) all the way up to the distance of the code. They show that beyond the Johnson radius, the number of exceptions must "jump" significantly.
As shown in the comparative analysis above, this work significantly reduces the requirement on the number of exceptional values ($a$) across multiple regimes. Furthermore, the paper provides specific parameter instances and counter-examples that delineate the theoretical limits of these gaps.
Conclusion and Future Work
These results mean that for a fixed security level, developers can use smaller finite fields or fewer interaction rounds in their proof systems, leading to faster provers and smaller proofs. However, some limitations remain:
- Characteristic Constraints: Some negative results are specifically constructed for fields of characteristic 2. While similar limits are suspected for prime fields, they have not been formally verified for all cases.
- List-Decoding Prerequisite: A major insight is that improved proximity gaps are fundamentally tied to the list-decodability of the code. Future leaps in this field likely require solving the long-standing open problem of the exact list-decoding radius of Reed-Solomon codes.
Summary updated