Paper 2023/1255
A flexible Snark via the monomial basis
Abstract
We describe a pairingbased Snark with a universal updateable CRS that can be instantiated with any pairingfriendly curve endowed with a sufficiently large prime scalar field. We use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. In particular, the scheme can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1, BN254 and BLS12381. This allows us to largely circumvent the overhead of nonnative field arithmetic for succinct proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254 or BLS12381. The proof size is constant ($10$ $\mathbb{G}_1$, $20$ $\mathbb{F}_p$), as is the verification time, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the $10$ multiscalar multiplications in $\mathbb{G}_1$  with a combined MSM length of $22\cdot \mathrm{Circuit}$ and, to a lesser extent, the computation of a single sum of polynomial products over the prime scalar field via multimodular FFTs. The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{\text{Circuit} , \;\text{Table}\}.$ Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple *univariate* custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed in the sense that $$\sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(\text{Circuit}). $$ This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.
Note: Corrections/suggestions welcome
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 SnarkPlonknonnativepairingKZG
 Contact author(s)
 stevethakur01 @ gmail com
 History
 20230913: last of 5 revisions
 20230819: received
 See all versions
 Short URL
 https://ia.cr/2023/1255
 License

CC BYSA
BibTeX
@misc{cryptoeprint:2023/1255, author = {Steve Thakur}, title = {A flexible Snark via the monomial basis}, howpublished = {Cryptology ePrint Archive, Paper 2023/1255}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1255}}, url = {https://eprint.iacr.org/2023/1255} }