Welcome to the resource topic for 2023/1255
Title:
A flexible Snark via the monomial basis
Authors: Steve Thakur
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.
ePrint: https://eprint.iacr.org/2023/1255
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .