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. For reasonable parameter choices, Mova's Prover is about $5$ to $10$ times faster than Nova's Prover, and about $1.5$ 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 $4$ 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 $\mathbf{E}$ and cross term $\mathbf{T}$ by replacing said commitments with evaluations of the Multilinear Extension (MLE) of $\mathbf{E}$ and $\mathbf{T}$ at a random point sampled by the Verifier. A key observation used in Mova's soundness proofs is that $\mathbf{E}$ is implicitly committed by a commitment to the input-witness vector $\mathbf{Z}$, since $\mathbf{E}=(A\cdot\mathbf{Z})\circ (B\cdot\mathbf{Z}) -u (C\cdot \mathbf{Z})$.
Note: Slightly lowered Hypernova's costs. Reworded "further work" section and title. Fixed typos.
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-02: last of 3 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},
note = {\url{https://eprint.iacr.org/2024/1220}},
url = {https://eprint.iacr.org/2024/1220}
}
