Paper 2023/1255

A flexible Snark via the monomial basis

Abstract

We describe a pairing-based Snark with a universal updateable CRS that can be instantiated with any pairing-friendly 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 BLS12-381. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254 or BLS12-381. 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$ multi-scalar 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