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