# [DG25] On the Distribution of Distances of Random Words

**Authors:** Benjamin E. Diamond and Angus Gruen
**Publication:** [IACR ePrint 2025/2010](https://eprint.iacr.org/2025/2010)
**Date:** November 2025

[TOC]

---

:::info
:bulb: **Summary**

This paper presents a fundamental result in coding theory with significant implications for the security of deployed cryptographic systems. The authors prove that the [capacity conjecture](https://dl.acm.org/doi/10.1145/3564246.3585114) proposed by Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf [**BCIKS23**] in 2023 is **false** by constructing explicit counterexample families of [Reed-Solomon codes](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction). The disproof relies on developing new, extremely sharp combinatorial estimates for Hamming ball volumes and their intersections. These results indicate that many currently deployed [SNARKs](https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof) (Succinct Non-Interactive Arguments of Knowledge) may be less secure than previously assumed under optimistic security analyses.
:::

---

## 0. Intuitive Explanation: What Are Proximity Gaps?

Before diving into the technical results, it helps to understand what proximity gaps are and why they matter for cryptographic proofs.

### Basic Setup: Words and Codes

Consider an **alphabet** (such as the digits 0 through 7) and a **word length** $n$. A **word** is simply a sequence of $n$ letters from the alphabet. For example, with alphabet $\{0,1,2,3,4,5,6,7\}$ and $n=4$, we might have words like:
- `4444`
- `0061`
- `0123`

The **Hamming distance** between two words counts how many positions differ. For instance, `0061` and `0123` have distance 3 because only the first position matches (they differ in positions 2, 3, and 4).

A **code** is a special subset of all possible words. In our example, we might define the code as "all words where every position contains the same letter," giving us the codewords `0000`, `1111`, `2222`, through `7777`.

The **distance from a word to the code** is the minimum distance to any codeword. In our example:
- `4444` has distance 0 (it is already a codeword)
- `0061` has distance 2 (closest to `0000`)
- `0123` has distance 3 (closest to `0000`)

### Proximity Gaps and Zero-Knowledge Proofs

A code has a **$(z/n, \varepsilon)$-proximity gap** if the following property holds: when you take two words that are both $z$-far from the code and randomly combine them (using a linear combination with a random coefficient from the alphabet), the probability that this combination lands close to the code (within distance $z$) is less than $\varepsilon$.

This matters crucially for zero-knowledge proof systems. In these protocols, a prover claims that some word equals a specific codeword. The verifier cannot check all $n$ positions directly but can only randomly sample individual positions.

**Example verification scenario:** Suppose the prover claims that `0061` equals the codeword `0000`. Each query, the verifier picks a random position $i \in \{0,1,2,3\}$ and the prover must reveal that position's value:
- If $i = 0$ or $i = 1$: prover reveals `0` (looks good!)
- If $i = 2$ or $i = 3$: prover reveals `6` or `1` (caught!)

Each query has a $2/4 = 1/2$ probability of catching the cheating prover. To achieve security level $\varepsilon \approx 2^{-100}$, approximately 100 queries would be needed.

In general, when using a $(z/n, \varepsilon)$-proximity gap, each query has probability $z/n$ of detecting a malicious prover. **The larger we can make $z/n$, the fewer queries we need**, and the more efficient the proof system becomes.

### What Was Conjectured vs. What Was Proven

For Reed-Solomon codes with rate $1/2$ (a technical parameter measuring the code's information density):

**Previously proven bounds:**
- $z/n = 1/4$ is achievable with small $\varepsilon$ (requires approximately 240 queries)
- $z/n = (2-\sqrt{2})/2 \approx 0.293$ is achievable with larger $\varepsilon$ (requires approximately 200 queries)

**The capacity conjecture claimed:**
- $z/n = 1/2$ is achievable with small $\varepsilon$ (would require only approximately 100 queries)

**This paper's result:**
- The conjecture is **false**. The authors establish an upper bound showing $z/n$ is slightly below $1/2$, corresponding to approximately **103 queries** rather than 100.

While the difference may seem small, it represents a fundamental limitation. The conjecture predicted that we could achieve arbitrarily good proximity gaps approaching the code's rate, but the authors prove that a gap exists between what is achievable and what the conjecture promised.

### Practical Implications

The key question for the zero-knowledge proof community is whether to:

1. **Trust an "updated conjecture"** that adjusts the parameters down to match this paper's upper bound, or
2. **Return to proven bounds** and accept the higher query costs (approximately 200-240 queries instead of 100-103)

The conservative approach would be option 2, while practitioners willing to rely on refined conjectures might choose option 1. If future work proves the updated conjecture, systems could migrate back and benefit from the improved efficiency. However, the disproof of the original conjecture serves as a cautionary tale about relying too heavily on unproven optimistic assumptions in security-critical applications.

---

## 1. Main Result

The central contribution of this work is the construction of infinite families of Reed-Solomon codes that violate the capacity conjecture. For each positive integer $c^*$, the authors construct sequences of codes where the proximity error decays more slowly than the conjectured bound $n^{c^*}/q$.

:::spoiler **Theorem (Informal Statement)**
For every constant $c^* \geq 2$, there exists an infinite sequence of Reed-Solomon codes with block lengths $n \to \infty$ such that:

$$
\text{err}(C,z) > \frac{n^{c^*}}{q}
$$

This proves that no universal polynomial bound exists for proximity error.
:::

### 1.1 The Capacity Conjecture (Now Disproven)

The **BCIKS23 capacity conjecture** predicted that for Reed-Solomon codes with relative rate $\rho = k/n$ and relative shortfall $\eta = (n-k-z)/n$, the proximity error would satisfy:

$$
\text{err}(C,z) \leq \frac{1}{q} \cdot \frac{n^{c_2}}{(\rho \cdot \eta)^{c_1}}
$$

for some universal constants $c_1$ and $c_2$. The authors demonstrate that **no such universal constants exist** by constructing counterexamples for arbitrarily large $c^* = 2c_1 + c_2$.

:::warning
**Figure 1:** Conjectured Bound vs. Actual Proximity Error


The left panel shows the linear-scale comparison, while the right panel reveals the polynomial growth rate difference on log-log scale. The actual error decays as $n^{-1/6}$ while the conjecture predicts $n^{-1}$, leading to a ratio that grows as $n^{5/6} \to \infty$.
:::

---

## 2. Technical Approach

The proof strategy combines **probabilistic reasoning** with **precise combinatorial analysis**. The key insight is establishing a lower bound on proximity error through random word coverage.

### 2.1 Core Strategy

The authors establish that the proximity error is lower bounded by:

$$
\text{err}(C,z) \geq \frac{q-1}{q} \cdot \Pr_{u \leftarrow \mathbb{F}_q^n}[d(u,C) \leq z]
$$

This probability can be expressed as the coverage of the ambient space $\mathbb{F}_q^n$ by [Hamming balls](https://en.wikipedia.org/wiki/Hamming_distance) of radius $z$ centered at codewords. The challenge becomes accurately estimating this coverage while accounting for overlapping balls.

---

### 2.2 Novel Ball Volume Estimates

A key technical innovation is **Theorem 3.10**, which provides an asymptotically exact estimate for Hamming ball volumes.

:::success
**Key Innovation: Sharp Ball Volume Estimate**

Unlike classical [entropy-based bounds](https://en.wikipedia.org/wiki/Entropy_(information_theory)) that only give asymptotic rates, this new estimate achieves controllable accuracy:

$$
|B_q(0,z)| = \sqrt{\frac{n}{z}} \cdot \frac{n^{n-z} \cdot q^z \cdot e^{-\frac{(n-z)^2}{n} - \frac{z}{q}}}{(n-z)!} \cdot \left(1 + O\left(\frac{1}{z}, \frac{z}{q^2}, \frac{n}{q(n-z)}, \frac{(n-z)^2 \cdot z}{n^2}\right)\right)
$$

The ratio to the true volume can be driven arbitrarily close to unity for suitable parameter choices.
:::

This estimate becomes significantly sharper than classical bounds in certain parameter regimes and critically **avoids the $q$-ary entropy function**, making it more tractable for rigorous proofs.

#### Comparison with Classical Bounds

The following tables from **Example 3.11** demonstrate the accuracy improvement:

:::warning
**Table 1:** Classical Entropy Bounds vs. Theorem 3.10 (Small Parameters)

All values shown are **base-$q$ logarithms** of the ball volumes.
:::

| Case $q=365, n=23$ | $z=1$ | $z=4$ | $z=7$ | $z=10$ | $z=13$ | $z=16$ | $z=19$ | $z=22$ |
|:---|---:|---:|---:|---:|---:|---:|---:|---:|
| Ground truth | 1.5310 | 5.5387 | 9.1003 | 12.3601 | 15.3590 | 18.0969 | 20.5334 | 22.5264 |
| Entropy lower | 1.5243 | 5.5218 | 9.0819 | 12.3412 | 15.3398 | 18.0777 | 20.5148 | 22.5145 |
| Entropy upper | 1.6967 | 5.7993 | 9.3923 | 12.6642 | 15.6628 | 18.3881 | 20.7924 | 22.6870 |
| **Theorem 3.10** | 0.9091 | 4.7675 | 8.4147 | 11.8363 | 15.0114 | 17.9066 | 20.4604 | **22.5139** |

:::warning
**Table 2:** Where the New Estimate Beats Classical Bounds (Large $z/n$ ratio)
:::

| Case $q=365, n=365$ | $z=357$ | $z=358$ | $z=359$ | $z=360$ | $z=361$ | $z=362$ | $z=363$ | $z=364$ |
|:---|---:|---:|---:|---:|---:|---:|---:|---:|
| Ground truth | 363.043 | 363.401 | 363.736 | 364.046 | 364.327 | 364.572 | 364.774 | 364.922 |
| Entropy lower | 363.005 | 363.360 | 363.693 | 363.999 | 364.274 | 364.511 | 364.700 | 364.824 |
| Entropy upper | 363.355 | 363.700 | 364.019 | 364.310 | 364.567 | 364.779 | 364.934 | 365.000 |
| **Theorem 3.10** | **363.007** | **363.366** | **363.701** | **364.010** | **364.286** | **364.524** | **364.712** | **364.831** |

> :memo: **Note:** For high relative radius $z/n \approx 1$, Theorem 3.10's estimate becomes virtually exact, outperforming classical entropy bounds.

---

### 2.3 Intersection Analysis

The second technical pillar addresses the challenging problem of **ball intersections**.

When multiple Hamming balls overlap, naive union bound arguments overcount the covered space. The authors develop **Theorem 3.16**, which provides sharp estimates for the total mass covered by pairwise intersections of Hamming balls centered at different codewords.

:::info
**Theorem 3.16 (Simplified)**

For an [MDS code](https://en.wikipedia.org/wiki/Singleton_bound#MDS_codes) with ball radius $z \in [n/2, d]$:

$$
\sum_{w=d}^{n} |A_w| \cdot |B_q(0,z) \cap B_q(v,z)| = \binom{n}{n-z, n-z} \cdot q^{2z+k-n} \cdot \left(1 + O\left(\frac{(n-z) \cdot z^2}{q}, \frac{(n-z)^2}{2z-n+1}\right)\right)
$$

where $A_w$ denotes codewords of weight $w$.
:::

The analysis proceeds by observing that for an MDS code, the intersection structure depends only on the weight distribution of codewords. The authors bound the contribution from double-overlaps and show that for their parameter choices, this second-order correction term remains small relative to the first-order union bound.

This validates a pedagogical approximation where the balls are treated as **approximately independent**, with carefully quantified error terms.

:::warning
**Figure 2:** Hamming Ball Intersections on a Finite Field Lattice


This visualization shows Hamming balls (radius $z=1$) around codewords in $\mathbb{F}_5^2$ for an MDS code. Each color represents a different codeword's ball. Notice how ball boundaries touch (e.g., point $(0,1)$ belongs to both red and blue balls), but **no codeword enters another codeword's ball** since the minimum distance $d=2 > z=1$.
:::

---

## 3. Construction of Counterexample Families

The authors' construction fixes an arbitrary target constant $c^*$ and defines a family of codes indexed by growing block length $n$. The key insight is to let both the message length $k$ and the shortfall $h = n-k-z$ grow **sublinearly** with $n$.

### 3.1 Parameter Choices

For alphabet size $q(n) = n^{c^*+1}$, they set:

$$
\begin{aligned}
f(n) &= \lceil e \cdot n^{1/3} \rceil &\text{(shortfall)}\\
k(n) &= \left\lfloor\left(1 - \frac{2}{3(c^*+1)}\right) \cdot f(n)\right\rfloor &\text{(message length)}\\
z(n) &= n - f(n) &\text{(proximity parameter)}
\end{aligned}
$$

This ensures that both the relative rate $\rho$ and relative shortfall $\eta$ converge to zero:

$$
\rho = \frac{k(n)}{n} \to 0, \quad \eta = \frac{n-k-z}{n} = \frac{h}{n} \to 0
$$

### 3.2 Number-Theoretic Construction

A subtle [number-theoretic argument](https://en.wikipedia.org/wiki/Prime_gap) ensures that infinitely many valid instances exist where:
- $q(n)$ is a prime power (required for finite field construction)
- $k(n)$ is an integer (required for code dimension)

This relies on the distribution of primes in short intervals, invoking [Ingham's theorem (1937)](https://en.wikipedia.org/wiki/Prime_gap#Numerical_results) on prime gaps.

### 3.3 The Crucial Probability Calculation

The key calculation shows that the close word probability satisfies:

$$
\Pr_{u \leftarrow \mathbb{F}_q^n}[d(u,C) \leq z] \gtrsim \frac{n^{\frac{1}{3}f(n)}}{f(n)!}
$$

Using [Stirling's approximation](https://en.wikipedia.org/wiki/Stirling%27s_approximation) $n! \approx \sqrt{2\pi n} \cdot (n/e)^n$ and the chosen parameter relationships:

$$
\frac{n^{\frac{1}{3}f(n)}}{f(n)!} \approx n^{-1/6}
$$

Multiplying by $n$ (accounting for code size factor) gives $n^{5/6}$, which **grows to infinity**, violating any bound of the form $n^{c^*}/q = n^{-c^*}$ for sufficiently large $n$.

:::warning
**Figure 3:** Growth Rate Analysis


**Top panel:** The ratio between actual error and conjectured bound grows as $n^{5/6}$ for all $c^*$ values, eventually exceeding the critical threshold of 1.

**Bottom left:** Parameter construction showing how $k(n), f(n) = o(n)$, causing $\rho, \eta \to 0$.

**Bottom right:** Direct comparison of close word probabilities reveals the gap factor growing with $n$.
:::

---

## 4. Heuristic Motivation via Birthday Paradox

The authors provide valuable intuition by connecting their result to the [birthday paradox](https://en.wikipedia.org/wiki/Birthday_problem).

:::spoiler **Birthday Paradox Connection**
For the simplest case where:
- $k=1$ (repetition code)
- $z=n-2$ (one less than covering radius)

The probability of a random word being $z$-close to the code equals the probability of a birthday collision among $n$ people drawn from $q$ days, which behaves like $n^2/q$.
:::

The authors extend this intuition to general $k$ and $z$ by treating the problem as a **generalized occupancy problem**. The key insight is that when $k$ and $h$ are both small compared to $n$, the Hamming balls cover a disproportionately large fraction of the space.

### Handling Ball Intersections

The handling of ball intersections mirrors the [inclusion-exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) correction in the birthday problem. The authors assume approximate independence of membership indicators and truncate at second order:

$$
\Pr[d(u,C) \leq z] \approx |C| \cdot P(n,q,z) - \frac{|C|^2}{2} \cdot P(n,q,z)^2
$$

where $P(n,q,z) = \Pr[u \in B_q(0,z)]$. This proves sufficient for their parameter choices.

---

## 5. Implications for SNARK Security

The capacity conjecture played a crucial role in security analyses of [proximity testing protocols](https://eprint.iacr.org/2022/1216), particularly those underlying [FRI-based SNARKs](https://drops.dagstuhl.de/opus/volltexte/2018/9018/).

### 5.1 The Security Gap and Query Efficiency

These systems rely on the **proximity gap property** to ensure soundness: if a prover's claimed function is far from any valid codeword, then random linear combinations should rarely produce results close to the code.

**Query requirements and security levels:** In zero-knowledge proof protocols, each query to the prover has a certain probability of detecting a cheating prover. With a $(z/n, \varepsilon)$-proximity gap, each query succeeds in catching a malicious prover with probability approximately $z/n$. To achieve $100$ bits of security (failure probability $\varepsilon \approx 2^{-100}$), the number of required queries is approximately:

$$
\text{Queries needed} \approx \frac{100}{\log_2(z/n)} = \frac{-100}{\log_2(z/n)}
$$

The capacity conjecture suggested that $z/n \approx 1/2$ was achievable, which would require only $\lceil 100/\log_2(1/2) \rceil = 100$ queries. However, proven results show that:

- **Unique decoding regime:** $z/n = (1+\rho)/2$ achievable (for $\rho=1/2$: requires approximately **241 queries**)
- **List decoding regime:** $z/n = \sqrt{\rho}$ achievable with larger $\varepsilon$ (for $\rho=1/2$: requires approximately **200 queries**)
- **Capacity conjecture (now disproven):** claimed $z/n = \rho$ achievable (for $\rho=1/2$: would need only **100 queries**)
- **Random words regime (this paper):** establishes that $z/n$ is strictly below $\rho$ (for $\rho=1/2$: requires approximately **103 queries**)

**The fundamental question for practitioners:** Should zero-knowledge proof systems rely on an updated conjecture that matches this paper's upper bound, or should they return to proven bounds and accept the higher query cost?

The conservative approach prioritizes proven security guarantees over efficiency optimizations based on conjectures. If future research proves the updated conjecture (whether partially or fully), systems can migrate back to more efficient parameters and benefit from the improved performance. However, the failure of the original capacity conjecture demonstrates the risks of relying on optimistic unproven assumptions in security-critical applications.

### 5.2 Concrete Query Requirements

The following table compares query requirements across different security regimes:

:::warning
**Table 3:** Required Queries for 100-Bit Security

Assuming $\log_2(q) = 128$ (typical for deployed systems).
:::

| Regime → | [Unique Decoding](https://en.wikipedia.org/wiki/Decoding_methods#Unique_decoding) | [List Decoding](https://en.wikipedia.org/wiki/List_decoding) | **Random Words** | Capacity |
|:---|---:|---:|---:|---:|
| **Formula** | $\frac{-100}{\log_2\left(\frac{1+\rho}{2}\right)}$ | $\frac{-100}{\log_2(\sqrt{\rho})}$ | $\frac{-100}{\log_2\left(\rho+\frac{\log_2(e/\rho) \cdot \rho}{\log_2(q)}\right)}$ | $\frac{-100}{\log_2(\rho)}$ |
| $\rho=1/2$ | 240.94 | 200.00 | **102.80** | 100.00 |
| $\rho=1/4$ | 147.48 | 100.00 | **50.98** | 50.00 |
| $\rho=1/8$ | 120.47 | 66.67 | **33.89** | 33.33 |
| $\rho=1/16$ | 109.58 | 50.00 | **25.38** | 25.00 |
| $\rho=1/32$ | 104.65 | 40.00 | **20.29** | 20.00 |
| $\rho=1/64$ | 102.29 | 33.33 | **16.90** | 16.67 |

> :warning: **Example:** At relative rate $\rho = 1/2$, the random words analysis suggests approximately **103 queries** are needed for 100-bit security, compared to the **100 queries** that the capacity conjecture would indicate.

---

## 6. Amended Conjecture

Recognizing that their counterexamples exploit codes with **vanishing relative rate and shortfall**, the authors propose a restricted version that may remain true.

:::info
**Conjecture 5.1 (Amended Capacity Conjecture)**

For each fixed choice of positive constants $\rho_0, \eta_0 > 0$, there exist constants $c, K > 0$ (depending on $\rho_0$ and $\eta_0$) such that for sufficiently large $n$, if $k \geq \rho_0 \cdot n$ and $n-k-z \geq \eta_0 \cdot n$, then:

$$
\text{err}(C,z) \leq K \cdot \frac{n^c}{q}
$$
:::

This conservative amendment restricts attention to code families whose rates and shortfalls remain **bounded away from zero**, precisely excluding the parameter regime exploited by the counterexamples.

### 6.1 Authors' Assessment

The authors acknowledge **limited confidence** in even this restricted form and suggest that further restrictions on the relationships between $q$, $\eta$, $\rho$, and $n$ may ultimately prove necessary.

:::danger
:fire: **Critical Insight**

The fundamental lesson is that **asymptotic behavior in coding theory exhibits phase transitions** that universal polynomial bounds cannot capture.

Different parameter regimes require regime-specific analysis, and extrapolation from one regime to another can lead to significant security miscalculations.
:::

---

## 7. Methodological Contributions

Beyond the specific disproof, this work advances the technical toolkit available for analyzing codes in extreme parameter regimes.

### Sharp Volume Estimates

The ball volume estimate (Theorem 3.10) may find applications in other contexts where **precise rather than merely asymptotic bounds** are required. The controllable error terms make it suitable for rigorous security proofs.

### Intersection Analysis Techniques

The treatment of ball intersections via controlled error terms (Theorem 3.16), rather than crude union bounds, demonstrates how to make rigorous arguments that previously relied on heuristic independence assumptions. This "second-order" approach could be applied to other coverage problems in coding theory.

### Constructive Precision

The authors' explicit attention to number-theoretic constraints in constructing infinite families ensures that their results apply to **actual Reed-Solomon codes over prime power fields** rather than merely idealized mathematical objects. This attention to constructive detail strengthens the practical relevance of the theoretical findings.

---

## 8. Conclusion

This paper fundamentally revises our understanding of proximity testing for Reed-Solomon codes in low-rate regimes. The disproof of the capacity conjecture reveals that **universal polynomial bounds on proximity error do not exist**, necessitating more careful regime-specific analysis in security proofs.

### Implications for Practice

For practitioners deploying [FRI-based proof systems](https://eprint.iacr.org/2022/1216), the results underscore the importance of:

1. **Conservative parameter choices** that stay well above the random words cutoff
2. **Rigorous proven bounds** rather than conjectural ones
3. **Regime-specific analysis** rather than universal extrapolations

### Open Questions

The sharp combinatorial estimates developed here provide tools for such rigorous analysis, though significant work remains to fully characterize the proximity gap landscape across all parameter regimes. The amended conjecture offers a potential path forward, but its truth remains an open question requiring further investigation.

---

## References

:::info

Diamond, B. E., & Gruen, A. (2025). *On the Distribution of the Distances of Random Words*. **IACR ePrint Archive, Report 2025/2010**.

**PDF:** https://eprint.iacr.org/2025/2010.pdf

@misc{cryptoeprint:2025/2010,
      author = {Benjamin E. Diamond and Angus Gruen},
      title = {On the Distribution of the Distances of Random Words},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2010},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2010}
}

https://x.com/AngusGruen/status/1985006662281822573
:::

### Related Work

- **[BCIKS23]** Ben-Sasson, E., Carmon, D., Ishai, Y., Kopparty, S., & Saraf, S. (2023). Proximity Gaps for Reed-Solomon Codes. *Journal of the ACM*, 70(5), Article 33. https://dl.acm.org/doi/10.1145/3564246.3585114

- **[AHIV23]** Ames, S., Hazay, C., Ishai, Y., & Venkitasubramaniam, M. (2023). Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. *ACM Conference on Computer and Communications Security (CCS)*. https://eprint.iacr.org/2022/1608

- **FRI Protocol** Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Fast Reed-Solomon Interactive Oracle Proofs of Proximity. *ICALP 2018*. https://drops.dagstuhl.de/opus/volltexte/2018/9018/

---

<details>
<summary><b>Glossary of Key Terms</b></summary>

- **Proximity Gap:** The separation between the probability that a random word is close to a code versus the probability for structured (interleaved) pairs.

- **Covering Radius:** The minimum radius $R$ such that Hamming balls of radius $R$ centered at all codewords cover the entire space $\mathbb{F}_q^n$.

- **MDS Code:** Maximum Distance Separable code, achieving the [Singleton bound](https://en.wikipedia.org/wiki/Singleton_bound) $d = n - k + 1$.

- **Reed-Solomon Code:** A family of [error-correcting codes](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction) that are MDS and based on polynomial evaluation.

- **FRI (Fast Reed-Solomon IOP):** An [Interactive Oracle Proof](https://en.wikipedia.org/wiki/Proof_of_knowledge#Interactive_proof) protocol used in many modern SNARK constructions.

- **SNARK:** Succinct Non-Interactive Argument of Knowledge, a [zero-knowledge proof system](https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof) with short proofs and fast verification.

</details>

---

*Last updated: November 2025*
*Report compiled by: [Kurt Pan](https://kurtpan.xyz) @ [ZKPunk](https://zkpunk.pro)*

---