# Ova: A slightly better Nova
There has been a lot of recent development in accumulation/folding schemes. One of the primary goals is to reduce the size of this recursive circuit needed to verify the accumulation. This short note gives a small improvement on Nova that yields a recursive circuit of just 1 Group scalar multiplication and a constant number of hashes and field operations.

## Current state of folding schemes
There are several folding schemes. We give a brief overview of the current state of the art and their respective accumulation verifiers (which have to be implemented as part of the IVC circuit).

| Scheme | $\mathbb{G}$ exps | $\mathsf{H}$ and $\mathbb{F}$ ops | Supported degree| Multi acc.|
| -------- | -------- | -------- |-------- |-------- |
| Nova | 2 | $O(1)$ | 2 |No
|Protostar | 3 |$O(d)$ | $d$| No
|Protogalaxy | 1 | $O(\log(\ell) +d)$| $d$|Yes
| Mova | 1| $O(\log(\ell))$ | $2$| Yes
| Ova | 1| $O(1)$ | 2| No

The table displays several folding schemes and different components of the accumulation verifier cost: $\mathbb{G}$ ops measures the number of group scalar multiplications (usually the most expensive part of the circuit). $\mathsf{H}$ and $\mathbb{F}$ ops measures the number of field ops and the number/size of the hash computations. They tend to be the same. Here $\ell$ is the number of verification checks done in the circuit. Supported degree states what degree is supported by the scheme. Nova, Mova and Ova all support R1CS a degree 2 scheme that can implement addition and multiplication gates. Multi-acc says whether the scheme can be used to accumulate many accumulators into one and build PCD.
A variant of Protostar, Protogalaxy and Nova, all achieved accumulation schemes with only a single group operation. However, all these schemes require at least $\log(\ell)$ hashes, where $\ell$ is the number of constraints.
We present an improvement that only requires a constant number of hashes or equivalently halves the number of group operations done by the Nova accumulation verifier.

## Nova recap
Nova builds an accumulation scheme for R1CS in the following way.
Consider a group $\mathbb{G}$ with hard discrete logarithm and two sets of rangdom generators $\vec{G}\in\mathbb{G}^n$ and $\vec{H}\in \mathbb{H}^\ell$.
Consider the R1CS matrices $A\in \mathbb{F}^{(n+k)\times \ell},B \in \mathbb{F}^{(n+k)\times \ell},C \in \mathbb{F}^{(n+k)\times \ell}$. A fresh proof consists of an instance $\vec{x}\in \mathbb{F}^k$, commitment $W\in \mathbb{G}$ to a vector $\vec{w}\in \mathbb{F}^n$, such that $$A\cdot \vec{z} \circ B\cdot \vec{z} - C\cdot \vec{z}=0^\ell$$ for $\vec{z}=\vec{x}||\vec{w}$
and
$$W=\langle \vec{w},\vec{G}\rangle$$
Note that $\vec{x}$ consists of the public input and $1$ and is prepended to the witness $\vec{w}$ to form $\vec{z}$.

An accumulator consists of $W',E\in \mathbb{G},\vec{x}'\in\mathbb{F}^k, \vec{w}'\in \mathbb{F}^n$ and $\mu \in \mathbb{F}$ such that
$$\vec{e}\gets A\cdot \vec{z}' \circ B\cdot \vec{z}' -\mu \cdot C\cdot \vec{z}'$$

for $\vec{z}'=\vec{x}'||\vec{w}'$ and
$$W'=\langle \vec{w}',\vec{G}\rangle,\quad E=\langle \vec{e},\vec{H}\rangle$$

The accumulation scheme takes a fresh proof and an accumulator and produces a new accumulator using the following algorithm:
1. Define $z(X)=\vec{x}'||\vec{w}' + X\cdot \vec{x}||\vec{w}\in \mathbb{F}^{n+k}[X]$.
2. Define $\mu'(X)\gets \mu +X\in \mathbb{F}[X]$
2. Define $e(X)=A\cdot z(X)\circ B\cdot z(X)-\mu'(X)\cdot C\cdot z(X)$. Note that $e(X)\in \mathbb{F}^\ell[X]$ is a degree $2$ polynomial but the highest coefficient is $0$.
3. Let $\vec{t}=A\cdot \vec{z}\circ B\cdot \vec{z}'+A\cdot \vec{z}'\circ B\cdot \vec{z}-C\cdot (\mu\cdot \vec{z}+\vec{z}')\in \mathbb{F}^\ell$ be the degree 1 coefficient of $e(X)$.
4. Compute $T\gets \langle \vec{t},\vec{H}\rangle\in \mathbb{G}$
5. Compute $\alpha\gets \mathsf{H}(\vec{x},\vec{x}',W,W',E,\mu,T)$ ($\mathsf{H}$ is modeled as a random oracle)
6. Compute $\vec{x}''\gets \vec{x}' + \alpha \vec{x}$
6. Compute $\vec{w}''\gets \vec{w}'+\alpha \vec{w}$
7. Compute $\mu'\gets \mu+\alpha$
7. Compute $W''\gets W'+\alpha W$
7. Compute $E'\gets E + \alpha\cdot T$
8. Output $\vec{x},\vec{x}',W'',E',\mu',\vec{w},T$

The verifier receives $(\vec{x},\vec{x}',W,W',E,\mu,T)$ as input and computes
1. $\alpha\gets \mathsf{H}(\vec{x},\vec{x}',W,W',E,\mu,T)$
2. $\vec{x}''\gets \vec{x}' + \alpha\cdot \vec{x}$
2. $W''\gets W'+\alpha\cdot W$
3. $E'\gets E + \alpha\cdot T$
4. $\mu'\gets \mu +\alpha$
5. Output $(\vec{x}'',W'',E',\mu')$ as the new accumulator instance

## Ova
Ova is a slight modification to Nova that shaves off 1 group operation and a few hashes. The key idea is that we can commit to $T$ and $W$ in one commitment. This slightly breaks the abstraction between the IVC scheme and the accumulation scheme. We assume that the accumulation prover receives $\vec{w}$ as input which proves the current step of the computation and that the *previous* accumulation was performed correctly. Note that $\vec{w}$ can be generated without being aware of $\vec{t}$ or $\alpha$. Alternatively the accumulation prover can receive the commitment to $\vec{w}$ as input and add to it the commitment to $\vec{t}$. This yields a commitment to the concatenated vector $\vec{w}||\vec{t}$. This works because both $W$ and $T$ are multiplied by the same challenge $\alpha$ in Nova.

### Construction
We assume that the discrete log between $\vec{G}$ and $\vec{H}$ is hard to compute.

Fresh proofs are as in Nova. Accumulators consists of a single commitment $W'\in \mathbb{G}$, an instance vector $\vec{x}'\in\mathbb{F}^k$, a vector $\vec{w}'\in \mathbb{F}^n$ and a scalar $\mu \in \mathbb{F}$, such that
$$\vec{e}\gets A \cdot \vec{z}' \circ B \cdot \vec{z}' - \mu \cdot C \cdot \vec{z}'$$
for $\vec{z}'=\vec{x}'||\vec{w}'$,
and
$$W'=\langle \vec{w}'||\vec{e},\vec{G}||\vec{H}\rangle $$

The accumulation prover operates as follows:

1. Receive $\vec{x},\vec{w}$ as input
2. Compute $\vec{t}$ as in Nova
3. Compute $W=\langle\vec{w}||\vec{t},\vec{G}||\vec{H}\rangle$
4. Compute $\alpha \gets \mathsf{H}(\vec{x},\vec{x}',W,W',\mu)$
4. $\vec{x}''\gets \vec{x}'+\alpha \vec{x}$
5. $W''\gets W'+\alpha W$
5. $\vec{w}''\gets \vec{w}' +\alpha\cdot \vec{w}$
6. $\mu'\gets \mu+ \alpha$
7. Output $\vec{x},\vec{x}',W,W'',\mu',\vec{w}''$

The accumulation verifier receives $(\vec{x},\vec{x}',W,W',\mu)$ as input
1. Compute $\alpha \gets \mathsf{H}(\vec{x},\vec{x}',W,W',\mu)$
2. Compute $\vec{x}''\gets \vec{x}'+\alpha\cdot \vec{x}$
2. Compute $W''\gets W'+\alpha\cdot W$
3. Compute $\mu'\gets \mu + \alpha$
4. Output $(\vec{x}'',W'',\mu')$

The decider receives a commitment $W\in\mathbb{G}$, an instance vector $\vec{x}\in \mathbb{F}^k$, a witness vector $\vec{w}\in\mathbb{F}^n$ and a scalar $\mu\in\mathbb{F}$ and computes $\vec{t}=A\cdot \vec{z} \circ B\cdot \vec{z}-\mu\cdot C\cdot\vec{z}\in\mathbb{F}^\ell$ for $\vec{z}=\vec{x}||\vec{w}$, and checks that $\langle\vec{w}||\vec{t},\vec{G}||\vec{H}\rangle=W$

### Completeness sketch
Completeness holds as the scheme is identical to Nova but using the same commitment for $\vec{t}$ and $\vec{w}$ which are both multiplied by the same challenge $\alpha$.
### Soundness sketch
We show that the underlying interactive scheme is $2$-special-sound (using a Protostar analysis).
Let $R1CS(\mu,\vec{x},\vec{w})=A\cdot \vec{z} \circ B\cdot \vec{z} -\mu\cdot C \cdot \vec{z}$.
Given two transcripts $(W,W',\mu,\alpha_1,\vec{x}_1,\vec{w}_1)$ and $(W,W',\mu,\alpha_2,\vec{x}_2,\vec{w}_2)$
such that
$$W+\alpha_i W'=\langle \vec{w}_i||R1CS(\mu+\alpha_i,\vec{z}_i),\vec{G}||\vec{H}\rangle$$ for $i=1,2$ for $\vec{z}_i=\vec{x}_i||\vec{w}_i$
We can use these to compute openings for $W$ and $W'$, i.e.:
$$W=\langle\vec{w}||t,\vec{G}||\vec{H}\rangle$$

$$W'=\langle\vec{w}'||t',\vec{G}||\vec{H}\rangle$$

Given a third accepting transcript we have that $R1CS(\mu+\alpha_i,\vec{z}'+\alpha_i\cdot \vec{z})=\vec{t}'+\alpha_i \cdot t$ for $i\in\{1,2,3\}$, otherwise one can find a non zero vector $\vec{a}\in\mathbb{F}^{n+\ell}$, such that $\langle\vec{a},\vec{G}||\vec{H}\rangle=\vec{0}$, which breaks the DLOG assumption in $\mathbb{G}$.
Since R1CS is $\ell$ degree $2$ functions this shows that they hold for any $\alpha$, i.e. $R1CS(\mu+X,\vec{z}'+X\cdot \vec{z})=\vec{t}'+X \cdot t$ for $i\in\{1,2,3\}$
This implies that $R1CS(\mu,\vec{z}')=\vec{t}'$ and $R1CS(1,\vec{z})=0$.

## Applications
Ova yields an IVC scheme through standard compilers (e.g. BCLMS). Interestingly, it does not yield a PCD scheme. PCD is the extension of IVC from line graphs to arbitrary dags. A key limitation is that Ova takes advantage of the fact that there is exactly one proof with error term $\vec{0}$ and one accumulator.

On the other hand, Ova, likely, has the smallest recursion overhead of any known scheme. An interesting application would be to Cyclefold (https://eprint.iacr.org/2023/1192) where a small R1CS circuit for computing group operations is paired with a more expressive circuit that computes the underlying predicate. Insted of using Nova to compute the group-expoentiation circuit one could use Ova. Cyclefold reports about 10k group operations for implementing the Nova verifier in an R1CS instance. This could be reduced by almost 50% using Ova.