Paper 2024/1871 Original: eprint.iacr.org/2024/1871 ↗

Field-Agnostic SNARKs from Expand-Accumulate Codes

Abstract

Efficient realizations of succinct non-interactive arguments of knowledge (SNARKs) have gained popularity due to their practical applications in various domains. Among existing schemes, those based on error-correcting codes are of particular interest because of their good concrete efficiency, transparent setup, and plausible post-quantum security. However, many existing code-based SNARKs suffer from the disadvantage that they only work over specific finite fields. In this work, we construct a code-based SNARK that does not rely on any specific underlying field; i.e., it is field-agnostic. Our construction follows the framework of Brakedown (CRYPTO '23) and builds a polynomial commitment scheme (and hence a SNARK) based on recently introduced expand-accumulate codes. Our work generalizes these codes to arbitrary finite fields; our main technical contribution is showing that, with high probability, these codes have constant rate and constant relative distance (crucial properties for building efficient SNARKs), solving an open problem from prior work. As a result of our work we obtain a SNARK where, for a statement of size $M$ , the prover time is $O(M \log M )$ and the proof size is $O(\sqrt{M} )$. Under reasonable conjectures, we obtain proofs thatt are $1.9\text{-}2.8\times$ smaller than the original Brakedown result (which is also field agnostic), while only introducing $20\%$ overhead in the prover time. Our work suggests that there is a rich tradeoff space in SNARK design offered by different codes, and indicates that a detailed study of such tradeoffs is warranted.