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 with efficient encoding over arbitrary fields. Although extensively studied in prior work, existing distance guarantees are weak, and practical instantiations have relied on conjectured results. We prove that EA codes with exact-weight expansion matrices, over sufficiently large fields, achieve a rate--distance tradeoff that approaches the Singleton bound with high probability, resolving these conjectures. Building on this result, we construct \textsf{Flare}, a field-agnostic polynomial commitment scheme based on EA codes. At its core is an efficient IOPP for EA codes that leverages code switching. For statements of size $M$, \textsf{Flare} achieves $O(M\log M)$ prover time and $O(\lambda\log^2 M)$ proof size, improving upon the $O(\sqrt{\lambda M})$ proof size of prior constructions based on EA codes (Block et al., CRYPTO 2024). Comprehensive evaluations show that \textsf{Flare} achieves compact proofs while maintaining competitive prover efficiency. For proving circuits of size $2^{22}$, \textsf{Flare} produces the smallest proofs of approximately $16$~MiB. Compared with BaseFold (Zeilberger et al., CRYPTO 2024) and ERA (Baweja et al., ASIACRYPT 2026), it reduces proof size by $1.66\times$ and $1.47\times$, respectively, while maintaining comparable prover efficiency. Compared with Brakedown (Golovnev et al., CRYPTO 2023), \textsf{Flare} produces $4.85\times$ smaller proofs at the cost of only a $1.50\times$ slower prover.