1# decider for offchain verification
 2
 3**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.
 4For onchain Ethereum use cases, check out the [decider-onchain section](decider_onchain.md).
 5
 6## Setup
 7At 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.
 8
 9![cyclefold diagram](/imgs/cyclefold-paper-diagram.jpg)
10<span style="padding:20px;">*Diagram source: CycleFold paper ([https://eprint.iacr.org/2023/1192.pdf](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}$.*</span>
11
12We 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$.
13We 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$.
14The main circuit constraint field is $F_r$, and $C_{EC}$ circuit constraint field is $F_q$.
15
16The $u_d$ and $U_d$ contain: $\{ \overline{E} \in E_1, \overline{W} \in E_1, u \in F_r, x \in F_r \}$
17
18And $U_{EC,d}$ contains: $\{ \overline{E} \in E_2, \overline{W} \in E_2, u \in F_q, x \in F_q^n \}$
19
20## Decider high level checks
21*These are the same checks for both the Onchain & Offchain Deciders. The difference lays on how are performed.*
22
231. check $NIFS.V(r, U_n, u_n, \overline{T}) \stackrel{?}{=} U_{n+1}$
242. check that $u_n.\overline{E}=0$ and $u_n.u=1$
253. check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
264. correct RelaxedR1CS relation of $U_{n+1}, W_{n+1}$ of the AugmentedFCircuit
275. check commitments of $U_{n+1}.\{ \overline{E}, \overline{W} \}$ with respect $W_{n+1}$ (where $\overline{E}, \overline{W} \in E_1$)
286. check the correct RelaxedR1CS relation of $U_{EC,n}, W_{EC,n}$ of the CycleFoldCircuit
297. check commitments of $U_{EC,n}.\{ \overline{E}, \overline{W} \}$ with respect $W_{EC,n}$ (where $\overline{E},\overline{W} \in E_2$)
30
31## Offchain Decider approach
32In 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.
33
34> We use the same checks numbers as the ones used in the [Onchain Decider](nova-decider-onchain.md) in order to make the relation of the checks easier to follow.
35
36#### Circuit1 $\in Fr$ ($E_1.F_r$)
37
38- 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}$
39- 2: check that $u_n.\overline{E}=0$ and $u_n.u=1$
40- 3: check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
41- 4: correct RelaxedR1CS relation of $U_{n+1}, W_{n+1}$ of the AugmentedFCircuit
42- 5.1: Check correct computation of the CommitmentScheme challenges for $U_{n+1}$
43    $$c_E = H(U_{n+1}.\overline{E}.\{x,y\}),~~c_W = H(U_{n+1}.\overline{W}.\{x,y\})$$
44    which we do through in-circuit Transcript.
45- 5.2: check that the CommitmentScheme evaluations for $U_{n+1}$ are correct
46    - $eval_W == p_W(c_W)$
47    - $eval_E == p_E(c_E)$
48    <br>where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively,
49    <br> ie. $p_W(x) = interpolate(W_{i+1}.W, 0)$, where $0$ is zero-padding to the next power of 2 length, and $interpolate()$ interpolates a (unique) polynomial from the vector
50
51#### Circuit2 $\in Fq$ ($E_2.F_r$)
52
53- 6: correct RelaxedR1CS relation of $U_{EC,d}, W_{EC,d}$
54- 7.1: Check correct computation of the CommitmentScheme challenges for $U_{EC}$
55    $$c_E = H(U_{EC}.\overline{E}.\{x,y\}),~~c_W = H(U_{EC}.\overline{W}.\{x,y\})$$
56    which we do through in-circuit Transcript.
57- 7.2: check that the CommitmentScheme evaluations for $U_{EC}$ are correct
58    - $eval_W == p_W(c_W)$
59    - $eval_E == p_E(c_E)$
60    <br>where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively.
61
62#### Outside the circuits
63
64- 1.2. check $NIFS.V(r, U_d, u_d, \overline{T}) \stackrel{?}{=} U_{d+1}$
65- 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$)
66- 7.3: Commitments verification of $U_{EC,d}.\{ \overline{E}, \overline{W} \}$ with respect $W_{EC,d}$ 
67(where $\overline{E},\overline{W} \in E_2$)
68
69## Proving scheme
70We 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.
71Two proofs are generated, one for each circuit over their respective curves of the cycle.