Paper 2026/939

More Efficient SNARKs via Quasi-Abelian Codes: Faster, Smaller, and Field-Agnostic

Abstract

Linear error-correcting codes play a crucial role in building practical non-interactive arguments of knowledge (SNARKs) with transparent setup, and plausible post-quantum security. Basically, the key to practical efficiency is a linear code with a concretely fast encoding and a high minimum distance. However, to date, none of the candidate codes achieves the best of the two worlds: codes with provable high minimum distance, e.g., Reed-Solomon codes, suffer from quasi-linear time encoding, while linear-time encodable codes, e.g., Spielman's code, have low provable minimum distance. In this work, we resolve this problem by explicitly constructing a family of Quasi-Abelian (QA) codes over {\em arbitrarily} large prime fields with concretely high minimum distance and practically efficient encoding algorithms. At the heart of our technical contribution is a fine-grained analysis on the concrete minimum distance of random QA codes of rank $1$ and index $c$ over group ring $\mathbb{F}_p[\mathbb{Z}_2^n]$. We show that in practical regimes it attains the well-known Gilbert-Varshamov bound up to a small constant gap $n/(c\log_2{p})$. Concretely, with probability $\ge1-2^{-127}$, our random QA code over a $128$-bit sized prime field with $n=20$, achieves relative minimum distance at least $0.4142,0.6070,0.7040$ for code rate $1/2,1/3,1/4$, respectively. In comparison, Spielman's code only achieves a minimum distance $0.1$ for code rate $1/2$ in the same setting by the state-of-the-art analyses. We give practically efficient encoding algorithms for QA code over $\mathbb{F}_p[\mathbb{Z}_2^n]$ by leveraging Walsh-Hadamard Transform. Specifically, for code length $c\cdot 2^n$ and rate $1/c$, our encoding only needs $cn\cdot 2^n$ additions/subtractions and $(c-1)\cdot 2^n$ multiplications over $\Fp$, which turns out to be concretely faster than Spielman's code. For encoding a message of length $2^{20}$ over a $256$-bit prime field, our QA code with rate $1/2$ only takes $250$ ms, while Spielman's code with rate $0.65, 1/2$ needs $410$ ms, $890$ ms, respectively. We then follow the framework of Brakedown (CRYPTO 2023) to build SNARKs over large prime fields from QA codes. For proving ECDSA verification over the scalar field of Curve25519 ($\approx 2^{16}$ constraints), our SNARK needs only $1.44$ second in proving, $0.08$ second in verification, and a proof size of $3.2$ MB. In comparison, Brakedown needs $1.6$ second, $0.24$ second, and $7.48$ MB, respectively.