Paper 2023/788
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 runtime, 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 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 \( \mathbf{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. At the moment, Panther Protocol's Rust implementation in a 570-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 32 seconds for a million gate circuit on a 64 vCPU AWS machine.
Note: Corrections/suggestions welcome
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- SnarkPlonknon-native field arithmeticKZG10pairings
- Contact author(s)
- stevethakur01 @ gmail com
- History
- 2023-07-30: last of 11 revisions
- 2023-05-30: received
- See all versions
- Short URL
- https://ia.cr/2023/788
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/788, author = {Steve Thakur}, title = {A flexible Snark via the monomial basis}, howpublished = {Cryptology ePrint Archive, Paper 2023/788}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/788}}, url = {https://eprint.iacr.org/2023/788} }