Alexander R. Block
Georgetown University and University of Maryland

Zhiyong Fang
Texas A&M University

Jonathan Katz
University of Maryland

Justin Thaler
Georgetown University

Hendrik Waldner
University of Maryland

Yupeng Zhang
University of Illinois Urbana Champaign

Keywords:

Abstract

In recent years, efficient realizations of succinct non-interactive arguments of knowledge (SNARK) 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 on specific finite fields due to the use of the Reed-Solomon code and the fast Fourier transform algorithm.

In this work, we construct a code-based SNARK that does not rely on specific underlying fields; 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) by utilizing a new family of linear codes built from the recent expand-accumulate codes (CRYPTO '22). Our work generalizes these codes to operate over any finite field, and our main technical contribution is showing that, with high probability, these codes have constant rate and constant relative distance on any field, solving an open problem left in the previous paper. These properties are crucial to build efficient SNARKs.

To prove a statement of size M, the prover time of our SNARK is O(M log M), and the proof size is O(sqrt(M)). We demonstrate the concrete efficiency of our scheme empirically in the experiments. When proving the ECDSA verification on curve secp256k1, it only takes 0.23s to generate the proof, 2 orders of magnitude faster than SNARKs that are not field-agnostic. Comparing to Brakedown which is also field-agnostic, our proof size is 1.9–3.3× smaller due to the good distance of the error-correcting code, while introducing only a small overhead of 1.2× on the prover time.