Paper 2026/1782

EA Codes Approaching Singleton Bound (with Application to Field-Agnostic SNARKs)

Abstract

SNARKs based on error-correcting codes require codes that simultaneously support fast encoding and large relative distance. Reed--Solomon codes achieve the optimal rate--distance tradeoff given by the Singleton bound, but their fast encoding relies on FFT-friendly fields, limiting their applicability to field-agnostic constructions. In this work, we revisit expand--accumulate (EA) codes, a simple family of linear codes that admit efficient encoding over arbitrary fields. We prove strong distance guarantees for EA codes whose sparse expansion matrix is sampled from the exact-weight ensemble. Over sufficiently large finite fields, we show that these codes achieve a rate--distance tradeoff arbitrarily close to the Singleton bound with high probability, resolving conjectures from prior work. Building on these results, we construct \textsf{Flare}, a new field-agnostic polynomial commitment scheme based on EA codes. Our construction develops an efficient IOP for the constrained relation of EA codes and combines it with code switching and random linear folding for interleaved codes. For statements of size $M$, \textsf{Flare} achieves $O(M\log M)$ prover time and $O(\log^2 M)$ proof size, improving upon the $O(\sqrt{M})$ proof size of prior constructions based on EA codes.