Paper 2024/1220
Mova: Nova folding without committing to error terms
Abstract
We present Mova, a folding scheme for R1CS instances that does not require committing to error or cross terms, nor makes use of the sumcheck protocol. We compute concrete costs and provide benchmarks showing that, for reasonable parameter choices, Mova's Prover is about $5$ to $10$ times faster than Nova's Prover, and about $1.05$ to $1.3$ times faster than Hypernova's Prover (applied to R1CS instances) -- assuming the R1CS witness vector contains only small elements. Mova's Verifier has a similar cost as Hypernova's Verifier, but Mova has the advantage of having only $3$ rounds of communication, while Hypernova has a logarithmic number of rounds. Mova, which is based on the Nova folding scheme, manages to avoid committing to Nova's so-called error term $E$ and cross term $T$ by replacing said commitments with evaluations of the Multilinear Extension (MLE) of $E$ and $T$ at a random point sampled by the Verifier. A key observation used in Mova's soundness proofs is that $E$ is implicitly committed by a commitment to the input-witness vector $Z$, since $E=(A\cdot Z)\circ (B\cdot Z) -u (C\cdot Z)$. We also note that ProtoGalaxy [EG23] can be specialized to a R1CS folding scheme with similar properties. Some of our further contributions are that 1) Mova is described with a language that sheds new insights into the topic of "Nova-style folding"; 2) we provide concrete costs, benchmarks, and optimizations for the Prover; 3) we describe how to fold two accumulated instances (which is important for applications in Proof Carrying Data); and 4) provide non-trivial knowledge soundness proofs in the context of multilinear polynomials.
Note: Updated IACR's abstract and lowered Hypernova's costs
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Zero-knowledgeSNARKFolding schemeNova
- Contact author(s)
-
nikolaos @ nethermind io
albert @ nethermind io
ignacio @ nethermind io
ilia @ nethermind io - History
- 2024-08-13: last of 7 revisions
- 2024-07-31: received
- See all versions
- Short URL
- https://ia.cr/2024/1220
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1220, author = {Nikolaos Dimitriou and Albert Garreta and Ignacio Manzur and Ilia Vlasov}, title = {Mova: Nova folding without committing to error terms}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1220}, year = {2024}, url = {https://eprint.iacr.org/2024/1220} }