Vac’s ZK-meeting on (2/9/2024) will involve a discussion on Mova. This thread is to provide a brief explanation of Mova prior to the meeting, and to potentially lead to discussion that can be continued during and after the meeting.
Mova Notes
This document describes Mova. Mova is a modification of Nova that replaces the error term commitment with an evaluation of the multilinear extension of the error term.
Mova has been implemented in Rust and compared to Hypernova and Nova. Based on Nethermind’s findings, it appears that Mova has a significant time advantage over Nova and Hypernova.
Disclaimer: The paper for Mova is written in terms of reductions of knowledge. Reductions of knowledge, to my knowledge, has only been formally discussed in the original paper that introduced it. These are specialized interactive ‘protocols’ with the output space being (potentially) different than \{\mathsf{accept}, \mathsf{reject}\}. Reductions of knowledge can be used to iteratively construct an interactive protocol (or folding argument) in an iterative manner. This is what Mova does with reductions of knowledge.
For the of this document, I will describe Mova without explicitly discussing reductions.
Key Observation about Nova
An instance of R1CS, ({\bf{x}}; {\bf{w}}), satifies the equation (A\cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) = C\cdot{\bf{z}} where the vector {\bf{z}} is given by {\bf{z}} = ({\bf{w}}, {\bf{x}}, 1). Nova considers a relaxation of R1CS that introduces an error vector {\bf{e}} and a scalar u: (A\cdot {\bf{z}}) \circ (B \circ {\bf{z}}) = u(C\cdot {\bf{z}}) + {\bf{e}}. In particular, Nova is a folding argument on the committed version of R1CS. This requires the Prover to commit to the error vector {\bf{e}} and the witness vector {\bf{w}}.
Mova points out that the error vector {\bf{e}} does not need a commitment. This is because {\bf{e}} is implicitly committed to by the commitment to the vector {\bf{w}} since {\bf{e}} = (A\cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) - u(C \cdot {\bf{z}}). As such, Mova removes the commitment for {\bf{e}} and replaces it with an evaluation of the multilinear extension given by the vector {\bf{e}}.
That is, Mova considers the relation:
\mathcal{R}_{mR1CS} := \left\{ \begin{array}{l|l}({\bf{pp}}_{mR1CS}, \mathbb{x} := ({\bf{x}},v,u,W, {\bf{r}}); \mathbb{w} := {\bf{w}}, {\bf{e}}, s) &
{\bf{x}} \in \mathbb{F}^{\ell}, {\bf{w}} \in \mathbb{F}^{m-\ell-1}, {\bf{e}} \in \mathbb{F}^{m}, u,s \in \mathbb{F}\\
&(A \cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) = u(C \cdot {\bf{z}}) + {\bf{e}} \; \text{ for}\\
&{\bf{z}} := ({\bf{w}}, {\bf{x}}, u), \mathsf{mle}_{{\bf{e}}}({\bf{r}}) = u\\
& W = \mathsf{com}({\bf{w}}, s)
\end{array} \right\}.
Variables
We assume the matrices A,B, C are m \times m matrices with at most n = \Omega(m) nonzero entries. The variable \ell denotes the number of public parameters. Since {\bf{z}} = ({\bf{w}},{\bf{x}},u) \in \mathbb{F}^m, the witness vector {\bf{w}} is of length m-\ell-1.
Mova Design
Mova is designed using composition of reductions of knowledge. For the ease of understanding, I’ll surpress the reductions. Instead, I’ll focus on general steps. High level view,
- We show that each R1CS instance can be mapped to a mR1CS.
- Given two mR1CS instances, we can make sure both of these instances share the same random point for evaluation.
- Given two mR1CS instances that share the same random point evaluation, we can fold these instances together into a single mR1CS instance.
I present these steps in detail in the reverse order. The reason for the reverse order is because I think it makes more sense to understand the purpose of the previous step.
Step 3
Suppose that we have two instances of mR1CS that share the same evaluation point {\bf{r}}. That is, we have the statements ({\bf{x}}_1, v_1, u_1, W_1, {\bf{r}}_1) and ({\bf{x}}_2, v_2, u_2, W_2, {\bf{r}}_2) where (A\cdot {\bf{z}}_1) \circ (B \cdot {\bf{z}}_1) = u_1 C \cdot {\bf{z}}_1 + {\bf{e}}_1 and (A\cdot {\bf{z}}_2) \circ (B \cdot {\bf{z}}_2) = u_2 C \cdot {\bf{z}}_2 + {\bf{e}}_2 for vectors {\bf{z}}_i := ({\bf{w}}_i, {\bf{x}}_i, u_i) and error vectors {\bf{e}}_1, {\bf{e}}_2. Note that W_1, W_2 \in \mathbb{G}_1 are commitments to the vectors {\bf{w}}_1 and {\bf{w}}_2.
Step 2
We saw that in Step 3 that two instances of mR1CS so that their evaluation vectors are the same can be folded into a single instance of mR1CS. In this section, we will show how we can take two instances of mR1CS that have distinct evaluation vectors, {\bf{r}}_1 and {\bf{r}}_2, and map these to two instances of mR1CS with that share the same evaluation vector {\bf{r}}.
This is done by using a common trick used in GKR to collapse two evaluations to a shared evaluation point. Specifically, we construct a line between the two points {\bf{r}}_1 and {\bf{r}}_2. Let \ell: \mathbb{F} \rightarrow \mathbb{F}^{\log(m)} be such a line where \ell(0) = {\bf{r}}_1 and \ell(1) = {\bf{r}}_2. Ultimately, the Verifier will select a challenge \beta \in \mathbb{F} so that both the Verifier and Prover can compute the new evaluation vector {\bf{r}} := \ell(\beta). However, before we can do this, it is necessary to provide a framework so that the Verifier can compute the updated to the values v_1 and v_2.
This is done as follows:
- The Prover constructs the functions h_1, h_2: \mathbb{F} \rightarrow \mathbb{F} defined by h_1(X) := \mathsf{mle}_{\bf{e}_1}(\ell(X)) and h_2(X) := \mathsf{mle}_{\bf{e}_2}(\ell(X)). The Prover sends these polynomials to the Verifier. We note that h_1 and h_2 are at most degree \log(m). Hence, the communication of these univariate polynomials (without using a polynomial commitment scheme) is 2\log(m).
- The Verifier checks h_1(0) \stackrel{?}{=} v_1 and h_2(1) \stackrel{?}{=} v_2. If either of these identities fail, then the Verifier aborts. Provided these checks hold, the Verifier selects a random point \beta \in \mathbb{F}, and shares \beta with the Prover.
- The challenge point \beta is used to compute the shared evaluation point {\bf{r}} := \ell(\beta). Additionally, both the Prover and Verifier can compute the updated evaluations v'_1 and v'_2 by v_1' := \mathsf{mle}_{\bf{e}_1}({\bf{r}}) \text{ and } v_2' := \mathsf{mle}_{\bf{e}_2}({\bf{r}}).
At the end of this interaction, the Prover and Verifier both possess two instances of mR1CS with the shared evaluation vector {\bf{r}}:
({\bf{pp}}_{mR1CS}, \mathbb{x}_1 := ({\bf{x}}_1,v'_1,u_1,W_1, {\bf{r}}); \mathbb{w}_1 := {\bf{w}}_1, {\bf{e}}_1, s_1) \text{ and }
({\bf{pp}}_{mR1CS}, \mathbb{x}_2 := ({\bf{x}}_2,v'_2,u_1,W_2, {\bf{r}}); \mathbb{w}_2 := {\bf{w}}_2, {\bf{e}}_2, s_2)
Step 1
Now, we want to map an instance of R1CS to an instance of mR1CS. Recall:
\mathcal{R}_{R1CS} := \left\{ \begin{array}{l|l}({\bf{pp}}_{R1CS}, \mathbb{x} := {\bf{x}}; \mathbb{w} := {\bf{w}}) &
{\bf{x}} \in \mathbb{F}^{\ell}, {\bf{w}} \in \mathbb{F}^{m-\ell-1},\\
&(A \cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) = C \cdot {\bf{z}} \; \text{ for}\\
&{\bf{z}} := ({\bf{w}}, {\bf{x}}, 1)
\end{array} \right\}
\mathcal{R}_{mR1CS} := \left\{ \begin{array}{l|l}({\bf{pp}}_{mR1CS}, \mathbb{x} := ({\bf{x}},v,u,W, {\bf{r}}); \mathbb{w} := {\bf{w}}, {\bf{e}}, s) &
{\bf{x}} \in \mathbb{F}^{\ell}, {\bf{w}} \in \mathbb{F}^{m-\ell-1}, {\bf{e}} \in \mathbb{F}^{m}, u,s \in \mathbb{F}\\
&(A \cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) = u(C \cdot {\bf{z}}) + {\bf{e}} \; \text{ for}\\
&{\bf{z}} := ({\bf{w}}, {\bf{x}}, u), \mathsf{mle}_{{\bf{e}}}({\bf{r}}) = u\\
& W = \mathsf{com}({\bf{w}}, s)
\end{array} \right\}.
Now, to do this, we need to generate the scalars u,v, group element W and vector {\bf{r}}. This is fairly straightforward:
- Prover computes a commitment for the vector {\bf{w}}: for a random scalar s \in \mathbb{F}, compute
W := \mathsf{com}({\bf{w}}, s).
The Prover sends W to the Verifier. - The Verifier selects a random evaluation vector {\bf{r}} \in \mathbb{F}^{\log(m)}. The Verifier sends the vector {\bf{r}} to the Prover.
- Note that an instance of R1CS satisfies the equation (A \cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) = C \cdot {\bf{z}} is equivalent to the mR1CS equation (A \cdot {\bf{z}}) \circ (B \cdot {\bf{z}}) = u(C \cdot {\bf{z}}) + {\bf{e}} when u = 1 and the error vector {\bf{e}} is the zero vector. Since the multilinear extension of the zero vector is identitically zero, both the Prover and the Verifier can set v = 0.
Moreover, Prover and Verifier can independently set u = 1 and v = 0 without any communication.
Complexity
| P | V | Rounds | |
|---|---|---|---|
| Nova | 3n+5m \; \mathbb{F} 2 \; \mathbb{G} \text{ ops,} \; 2 \; \mathbb{G} \text { exp}, Vector commitment of length m Commitment to {\bf{w}}. |
2\ell \; \mathbb{F} 2 \; \mathbb{G} \; \text{ops.,} \; 2 \; \mathbb{G} \; \text{exp} |
1 |
| Hypernova | 5n+14m+O(\sqrt{m}) \; \mathbb{F} 1 \mathbb{G} \; \text{op.,} \; 1 \; \mathbb{G}\;\text{exp} Commitment to {\bf{w}}. |
2\ell+O(\log(m)) \; \mathbb{F} 1 \; \mathbb{G} \; \text{op.}, \; 1 \; \mathbb{G} \; \text{exp} |
\log(m)+O(1) |
| Mova | 3n+12m+ 3\log(m)\; \mathbb{F} 1 \mathbb{G} \text{op.}, \; 1 \; \mathbb{G} \text{exp} Commitment to {\bf{w}} |
2\ell+7 \log(m) + 5 \; \mathbb{F} 1 \; \mathbb{G} \; \text{op.}, \; 1 \; \mathbb{G} \; \text{exp} |
3 |
The experimental evaluations provided in Mova are quite interesting as it shows a significant time savings over Nova and Hypernova.