Welcome to the resource topic for 2023/788
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 and BN254. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of statements in these base fields. These include proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254.
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.
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}|\}.
When the scalar field has low 2-adicity - as is inevitably the case with any outer curve to Ed25519, secp256k1 or BN254 - we use the Schonhage-Strassen algorithm or the multimodular FFT algorithm to compute the sum of polynomial products that occurs in one of the steps of the proof generation. Despite the small (but discernible) slowdown compared to polynomial products in FFT-friendly fields, we empirically found that the MSMs dominate the proof generation time. To that end, we have included some benchmarks for polynomial products in FFT-unfriendly fields.
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 576-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 45 seconds for a million gate circuit on a 64 vCPU AWS machine.
ePrint: https://eprint.iacr.org/2023/788
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 .