decider for offchain verification

Overview: This section describes the Decider (compressed SNARK / final proof) for the non-ethereum use cases in which the verification of the Nova+CycleFold proofs is done offchain. For onchain Ethereum use cases, check out the decider-onchain section.

Setup

At the final stage of the Nova+CycleFold folding, after $d$ iterations, we have the committed instances ${u_{d}, U_{d}, U_{EC, d}}$ and their respective witnessess.

cyclefold diagram Diagram source: CycleFold paper (https://eprint.iacr.org/2023/1192.pdf). In the case of this document $d = i + 2$ , so $u_{i + 2} = u_{d}$ , $U_{i + 2} = U_{d}$ , $U_{EC, i + 2} = U_{EC, d}$ .

We work with a cycle of curves $E_{1}$ and $E_{2}$ , where $E_{1} . F_{r} = E_{2} . F_{q}$ and $E_{1} . F_{q} = E_{2} . F_{r}$ . We will use $F_{r}$ for referring to $E_{1} . F_{r} = E_{2} . F_{q}$ , and $F_{q}$ for referring to $E_{1} . F_{q} = E_{2} . F_{r}$ . The main circuit constraint field is $F_{r}$ , and $C_{EC}$ circuit constraint field is $F_{q}$ .

The $u_{d}$ and $U_{d}$ contain: ${\overline{E} \in E_{1}, \overline{W} \in E_{1}, u \in F_{r}, x \in F_{r}}$

And $U_{EC, d}$ contains: ${\overline{E} \in E_{2}, \overline{W} \in E_{2}, u \in F_{q}, x \in F_{q}^{n}}$

Decider high level checks

These are the same checks for both the Onchain & Offchain Deciders. The difference lays on how are performed.

check $N I FS . V (r, U_{n}, u_{n}, \overline{T}) = ? U_{n + 1}$
check that $u_{n} . \overline{E} = 0$ and $u_{n} . u = 1$
check that $u_{n} . x_{0} = H (n, z_{0}, z_{n}, U_{n})$ and $u_{n} . x_{1} = H (U_{EC, n})$
correct RelaxedR1CS relation of $U_{n + 1}, W_{n + 1}$ of the AugmentedFCircuit
check commitments of $U_{n + 1} . {\overline{E}, \overline{W}}$ with respect $W_{n + 1}$ (where $\overline{E}, \overline{W} \in E_{1}$ )
check the correct RelaxedR1CS relation of $U_{EC, n}, W_{EC, n}$ of the CycleFoldCircuit
check commitments of $U_{EC, n} . {\overline{E}, \overline{W}}$ with respect $W_{EC, n}$ (where $\overline{E}, \overline{W} \in E_{2}$ )

Offchain Decider approach

In the offchain case, since we can end up with proofs in both curves of the cycle, we try to fit all the computations natively in each curve respectively.

We use the same checks numbers as the ones used in the Onchain Decider in order to make the relation of the checks easier to follow.

Circuit1 $\in F r$ ( $E_{1} . F_{r}$ )

1.1: check that the given NIFS challenge $r$ is indeed well computed. This challenge is then used outside the circuit by the Verifier to compute NIFS.V obtaining $U_{i + 1}$
2: check that $u_{n} . \overline{E} = 0$ and $u_{n} . u = 1$
3: check that $u_{n} . x_{0} = H (n, z_{0}, z_{n}, U_{n})$ and $u_{n} . x_{1} = H (U_{EC, n})$
4: correct RelaxedR1CS relation of $U_{n + 1}, W_{n + 1}$ of the AugmentedFCircuit
5.1: Check correct computation of the CommitmentScheme challenges for $U_{n + 1}$ $c_{E} = H (U_{n + 1} . \overline{E} . {x, y}), c_{W} = H (U_{n + 1} . \overline{W} . {x, y})$ which we do through in-circuit Transcript.
5.2: check that the CommitmentScheme evaluations for $U_{n + 1}$ are correct
- $e v a l_{W} == p_{W} (c_{W})$
- $e v a l_{E} == p_{E} (c_{E})$
  where $p_{W}, p_{E} \in F [X]$ are the interpolated polynomials from $W_{i + 1} . W, W_{i + 1} . E$ respectively,
  ie. $p_{W} (x) = in t er p o l a t e (W_{i + 1} . W, 0)$ , where $0$ is zero-padding to the next power of 2 length, and $in t er p o l a t e ()$ interpolates a (unique) polynomial from the vector

Circuit2 $\in Fq$ ( $E_{2} . F_{r}$ )

6: correct RelaxedR1CS relation of $U_{EC, d}, W_{EC, d}$
7.1: Check correct computation of the CommitmentScheme challenges for $U_{EC}$ $c_{E} = H (U_{EC} . \overline{E} . {x, y}), c_{W} = H (U_{EC} . \overline{W} . {x, y})$ which we do through in-circuit Transcript.
7.2: check that the CommitmentScheme evaluations for $U_{EC}$ are correct
- $e v a l_{W} == p_{W} (c_{W})$
- $e v a l_{E} == p_{E} (c_{E})$
  where $p_{W}, p_{E} \in F [X]$ are the interpolated polynomials from $W_{i + 1} . W, W_{i + 1} . E$ respectively.

Outside the circuits

1.2. check $N I FS . V (r, U_{d}, u_{d}, \overline{T}) = ? U_{d + 1}$
5.3: Commitments verification of $U_{d + 1} . {\overline{E}, \overline{W}}$ with respect $W_{d + 1}$ (where $\overline{E}, \overline{W} \in E_{1}$ )
7.3: Commitments verification of $U_{EC, d} . {\overline{E}, \overline{W}}$ with respect $W_{EC, d}$ (where $\overline{E}, \overline{W} \in E_{2}$ )

Proving scheme

We could use a SNARK adapted to RelaxedR1CS, but before that is ready we use a regular R1CS SNARK and check the RelaxedR1CS relations in-circuit as described above. Two proofs are generated, one for each circuit over their respective curves of the cycle.

sonobe docs