Google Drive
Gist
Clipboard
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.
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 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:
The verifier receives \((\vec{x},\vec{x}',W,W',E,\mu,T)\) as input and computes
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.
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:
The accumulation verifier receives \((\vec{x},\vec{x}',W,W',\mu)\) as input
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 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\).
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\).
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.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe