🔢 mathematics

Locality of Curve-Decoding and Improved Proximity Gaps

This paper improves proximity gaps for random ensembles of error-correcting codes by extending the Local Coordinate-wise Linear (LCL) framework to a row-span constrained version, thereby enabling a black-box transference of optimal parameters from subspace design codes and eliminating the parameter losses associated with prior proxy-based approaches.

Original authors: Rohan Goyal, Venkatesan Guruswami, Yihang Sun, Mary Wootters

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Rohan Goyal, Venkatesan Guruswami, Yihang Sun, Mary Wootters

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, magical library of secret codes. These codes are like special recipes for sending messages that can survive even if some letters get scribbled over or lost in the mail. In the world of cryptography and blockchain (the tech behind things like Bitcoin and Ethereum), these codes are the guardians that keep your data safe.

Recently, a team of researchers—Rohan Goyal, Venkatesan Guruswami, Yihang Sun, and Mary Wootters—decided to check if these codes could handle a very specific, tricky kind of test. They wanted to see if the codes could spot "fake" messages that look almost like real ones, but are actually just a wobbly, curved line of nonsense trying to sneak in.

The "Curve" Problem: A Wobbly Line vs. a Straight Path

To understand their discovery, let's use an analogy. Imagine you are drawing a path on a giant grid.

The Real Code: This is a perfectly straight, rigid highway. If you try to drive on it, you must stay exactly on the white lines.
The Curve: Now, imagine someone tries to draw a wobbly, curvy line (a "degree-ℓ curve") across the same grid.
The Test: The researchers asked: If I draw this wobbly line, will the code immediately scream, "Hey! That's not a highway!"? Or will the code get confused and think, "Oh, this wobbly line is close enough to the highway, I'll let it pass"?

In the past, scientists knew that some very special, carefully built codes (called Subspace Design Codes) were great at this. They could tell the difference between a real highway and a wobbly line almost perfectly. But for the "random" codes—the ones you just pick by rolling dice to see where the lines go—the math was messy. Previous studies suggested that as the wobbly line got more complicated (higher "degree" ℓ), the random codes would start to fail, letting the fake lines slip through.

The Big Discovery: Random Codes Are Just as Good!

The main finding of this paper is a happy surprise: Random codes are actually just as good at spotting these wobbly lines as the fancy, carefully built ones.

The authors proved that if you pick a random code (like a Random Linear Code, a Random Reed-Solomon Code, or a Gallager's LDPC code), it will almost certainly catch the fake wobbly lines, even when those lines are very complex. They showed that the "safety margin" for these random codes is just as tight as the best possible margin for the fancy codes.

Think of it like this: For years, people thought that only a master architect (the fancy code) could build a bridge that wouldn't collapse under a specific type of heavy, wobbly truck. This paper proves that a random builder, just flipping coins to decide where to put the beams, can build a bridge that is just as strong against that truck.

What They Did Not Do (and What They Argued Against)

It's important to know what this paper didn't say.

They didn't say random codes are perfect in every situation. They specifically argued against the idea that random codes get worse as the curves get more complex. Previous work suggested that for complex curves, the "error" in random codes would explode, making them useless. The authors proved this is not true; the error stays small and manageable.
They didn't solve the mystery of explicit codes. The paper focuses on "random" codes (codes you generate by chance). It does not tell us exactly which specific, pre-written list of numbers (an "explicit" code) is the best. It just says, "If you pick one at random, it will likely be great." There is still a big question mark over which specific, hand-picked codes are the champions.
They didn't claim this is a finished, solved problem for everyone. They proved that random codes behave like the fancy ones under specific mathematical conditions. They didn't say, "Now we can build a new blockchain tomorrow." They said, "We have a mathematical proof that these random codes have a hidden superpower we didn't fully appreciate before."

How They Did It: The "Row-Span" Trick

How did they figure this out? They used a clever new tool they called a "Row-Span Constrained LCL Property." That's a mouthful, so let's break it down with a metaphor.

Imagine you are trying to find a group of spies (the "bad" curves) hiding in a crowd.

The Old Way: Previous researchers tried to catch the spies by looking at them one by one (coordinate by coordinate). They realized that "being a wobbly curve" is a weird, global property that's hard to spot just by looking at individual people. So, they used a "proxy" (a stand-in spy) to catch them. But this stand-in was a bit clumsy, and it made the math messy, leading to those "worse parameters" we mentioned earlier.
The New Way: The authors realized they could look at the whole group of spies at once. They introduced a rule about the "row-span" (a fancy way of saying the overall shape or direction the group of spies is pointing). By adding this rule, they could describe the "wobbly curve" problem directly, without needing a clumsy stand-in.

It's like realizing you don't need to check every single brick in a wall to know if it's crooked; you can just look at the overall tilt of the wall. By looking at the tilt (the row-span), they could prove that the random codes are just as good at spotting the crookedness as the fancy codes.

The Bottom Line

The authors have mathematically proved (with high confidence) that for a wide variety of random codes, the "proximity gap" (the ability to tell the difference between a real code and a fake curve) is near-optimal.

For Random Linear Codes: They work great.
For Random Reed-Solomon Codes: They work great.
For Random LDPC Codes (Gallager's Ensemble): They work great.

The paper shows that the "bad" parameters from previous studies were an illusion caused by using the wrong tool (the proxy). Once they used the right tool (the row-span constraint), the random codes shined just as brightly as the best-designed ones.

So, while we still don't know exactly which specific code is the absolute best to use in a real-world blockchain, we now know for sure that if you pick a random one, it's likely to be a superhero against these tricky, wobbly curve attacks. The math is solid, the proof is there, and the random codes are ready for their close-up.

Technical Summary: Locality of Curve-Decoding and Improved Proximity Gaps

1. Problem Statement

The paper addresses the problem of establishing proximity gaps for random ensembles of error-correcting codes. Proximity gaps are a property crucial for Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Informally, a code $C$ exhibits a proximity gap with respect to degree- $\ell$ curves if, for any degree- $\ell$ curve $u(x)$ , either every point on the curve is close to $C$ , or a $(1-\varepsilon)$ fraction of the points are far from $C$ .

Recent work by Guruswami and Goyal [GG25] established near-optimal proximity gaps for subspace design codes (including Folded Reed-Solomon and Multiplicity codes) with parameters where the error tolerance $\delta$ approaches $1-R$ (where $R$ is the code rate). Specifically, for subspace design codes, the bound on the number of "close" points $\varepsilon q$ scales as:
$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$
However, when [GG25] extended these results to random ensembles (Random Linear Codes, Random Reed-Solomon codes with random evaluation points, and Gallager's ensemble of LDPC codes) using a framework from [BCDZ25, LMS25], the parameters degraded. The resulting bound for random ensembles included an exponential dependence on $\ell$ :
$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + \left(\frac{\ell}{\eta^2}\right)^{O(\ell)}$
This degradation becomes significant when $\ell$ is large (e.g., $\ell = \Omega(\log n)$ ), rendering the bounds impractical. The central question is whether the optimal parameters achieved for subspace design codes can be matched by these random ensembles.

2. Methodology: Row-Span Constrained LCL Properties

The authors' primary technical innovation is the extension of the Local Coordinate-wise Linear (LCL) framework to a row-span constrained version.

The LCL Framework and the Challenge

The LCL framework (introduced in [LMS25]) characterizes "bad" properties of codes by the existence of a "witness" matrix $M$ whose columns are codewords and whose rows satisfy specific linear constraints defined by a profile $V$ .

The Obstacle: The property of curve-decodability (which implies proximity gaps) was not obviously an LCL property. Previous work [GG25] circumvented this by defining a proxy property called W-decoding. While W-decoding fit the LCL framework, translating results back to curve-decoding incurred the aforementioned exponential loss in parameters.

The Solution: Row-Span Constraints

The authors observe that curve-decodability can be captured directly by extending the LCL framework to include constraints on the row-span of the witness matrix.

Local Profile (Property A): The columns of the witness matrix (codewords) must agree with an ambient degree- $\ell$ curve $u(x)$ on a large set of coordinates. This is captured by a standard local profile $V$ .
Row-Span Constraint (Property B): The "badness" of the example requires that no $b$ $b$ columns of the matrix lie on a single degree- $\ell$ $ℓ$ codeword curve. This is a global constraint on the matrix structure.
- The authors define a subspace $U$ to be $(\ell, A, b)$ curve-free if no $b$ coordinates of any vector in $U$ lie on a degree- $\ell$ polynomial.
- They show that the failure of curve-decodability is equivalent to the existence of a witness matrix $M$ where the row-span $U$ is curve-free, and the rows satisfy the local profile $V$ .

By defining an LCL family $\mathcal{F}$ as a collection of pairs $(V, U)$ (profile, row-span), the authors cast curve-decodability as a row-span constrained LCL property. This allows them to apply the machinery of [LMS25] and [BCDZ25] directly to curve-decoding without the intermediate W-decoding step.

3. Key Contributions

1. Black-Box Transference

The paper establishes a black-box transference from subspace design codes to random ensembles. The authors prove that for any row-span constrained LCL property, the threshold rate at which random linear codes (and related ensembles) satisfy the property is essentially identical to the threshold for subspace design codes.

Implication: Any future improvement in the parameters for subspace design codes will automatically yield analogous improvements for random linear codes, random Reed-Solomon codes, and random LDPC codes.

2. Improved Proximity Gap Bounds

By applying this framework to curve-decoding, the authors derive improved proximity gap bounds for random ensembles that match the optimal bounds previously known only for subspace design codes.

Result: For Random Linear Codes, Random Reed-Solomon codes, and Gallager's LDPC ensemble, the proximity gap parameters are now:
$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$
This eliminates the exponential dependence on $\ell$ found in [GG25].

3. Equivalence Theorems

The paper proves equivalence theorems for the row-span constrained LCL properties across different code families:

Random Linear Codes and Random Reed-Solomon codes share the same thresholds.
Random LDPC codes (Gallager's ensemble) share the same thresholds as Random Linear Codes, provided the code has good distance (which occurs with high probability).

4. Main Results

The paper formalizes these findings in Theorem 1.2 (and detailed in Theorems 5.3, 5.6, and 5.10). For a random code $C$ (Linear, Reed-Solomon, or LDPC) of rate $R$ and degree $\ell$ :

With high probability, $C$ exhibits $(\ell, 1-R-2\eta, \varepsilon)$ proximity gaps.
The condition on $\varepsilon$ is:
$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$
The results also establish stronger notions: Correlated Agreement (CA) and Mutual Correlated Agreement (MCA) with the same improved parameters.

Specifically, for Random LDPC codes, the result holds for sufficiently large odd degree $s$ in Gallager's ensemble, with the leading term in the bound slightly adjusted (e.g., $2n\ell(1-R)/\eta$ in some formulations, though the constant factor can be improved).

5. Significance and Claims

The paper claims significance in three main areas:

Parameter Optimization: It resolves the parameter degradation issue for random ensembles, matching the near-optimal bounds of subspace design codes. This is particularly relevant for applications like WHIR (which uses large $\ell$ ) and protocols like Blaze and Bolt (which use random ensembles).
Theoretical Unification: It demonstrates that curve-decoding is a natural row-span constrained LCL property, unifying the analysis of explicit codes (subspace designs) and random ensembles under a single framework.
Future-Proofing: The "black-box" nature of the transference means that the results for random ensembles are not static; they will improve automatically as the theory of subspace design codes advances.

The authors explicitly note that while their results show random Reed-Solomon codes attain near-optimal proximity gaps, it remains an open problem to identify explicit Reed-Solomon codes (with specific evaluation points) that achieve these same optimal parameters, a question linked to the "Proximity Prize" and explicit list-decoding.