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- $U_{n + 1}$ is the correct folding of $U_n, u_n$, i.e., $NIFS.V(r, U_n, u_n, \overline{T}) = U_{n + 1}$.
22- $R_{r1cs}(W_{n + 1}, U_{n + 1}) = 1$:
23  - The running instance $U_{n + 1}$ and witness $W_{n + 1}$ satisfy (relaxed) $r1cs$.
24  - The commitments in $U_{n + 1}$ (i.e., $U_{n+1}.\{ \overline{E}, \overline{W} \} \in E_1$) open to the values in $W_{n + 1}$ (i.e., $W_{n+1}.\{ E, W \}$).
25- $R_{r1cs_{EC}}(W_{EC, n}, U_{EC, n})$:
26  - The CycleFold instance $U_{EC, n}$ and witness $W_{EC, n}$ satisfy (relaxed) $r1cs_{EC}$.
27  - The commitments in $U_{EC, n}$ (i.e., $U_{EC,n}.\{ \overline{E}, \overline{W} \} \in E_2$) open to the values in $W_{EC, n}$ (i.e., $W_{EC, n}.\{ E, W \}$).
28- $u_n$ is valid:
29  - $u_n.x$ contains the correct hash of the initial and final states, i.e., $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
30  - $u_n$ is indeed an incoming instance, i.e., $u_n.\overline{E}=0$ and $u_n.u=1$.
31
32> **Note**: These are the same checks for both the Onchain & Offchain Deciders. The difference lays on how are performed.
33
34## Offchain Decider approach
35In 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.
36
37> 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.
38
39#### Circuit1 $\in Fr$ ($E_1.F_r$)
40
41- 1: Enforce $U_{n+1}$ and $W_{n+1}$ satisfy $r1cs$, the RelaxedR1CS relation of the AugmentedFCircuit
42- 2: Check that $u_n.\overline{E}=0$ and $u_n.u=1$
43- 3: Check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
44- 6.1: Partially enforce that $U_{n + 1}$ is the correct folding of $U_n, u_n$
45    - By partially, we mean that only field elements in $U_{n + 1}$ are checked, while the group elements (i.e., commitments) are not, as they are in $E_1$ and are expensive non-native operations.
46- 7.1: Check correct computation of the KZG challenges
47    $$c_E = H(\overline{E}.\{x,y\}),~~c_W = H(\overline{W}.\{x,y\})$$
48    which we do through in-circuit Transcript.
49- 7.2: Check that the KZG evaluations are correct
50    - $eval_W == p_W(c_W)$
51    - $eval_E == p_E(c_E)$
52    <br>where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively.
53    <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
54
55#### Circuit2 $\in Fq$ ($E_2.F_r$)
56
57Note that in onchain decider, step 4 (Pedersen commitments verification of $U_{EC,n}.\{ \overline{E}, \overline{W} \}$) is checked in-circuit, necessitating `~5M` constraints.
58
59In the case of offchain decider, we aim to reduce the number of constraints for commitment verification for CycleFold instances.
60To this end, we apply the same approach as in step 7 of the onchain decider for checking commitments in primary instances.
61That is, we now use KZG commitments as well for the CycleFold instances, enabling us to separate expensive parts in commitments verification from the circuit.
62
63Below are checks for the Circuit2:
64
65- 4.1: Check correct computation of the KZG challenges for $U_{EC}$
66$$c_E = H(U_{EC}.\overline{E}.\{x,y\}),~~c_W = H(U_{EC}.\overline{W}.\{x,y\})$$
67which we do through in-circuit Transcript.
68- 4.2: check that the KZG evaluations for $U_{EC}$ are correct
69    - $eval_W == p_W(c_W)$
70    - $eval_E == p_E(c_E)$
71    <br>where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively.
72- 5: Enforce $U_{EC,n}$ and $W_{EC,n}$ satisfy $r1cs_{EC}$, the RelaxedR1CS relation of the CycleFoldCircuit
73    - This check becomes native because the constraint system is now over $F_q$.
74
75#### Outside the circuits
76
77- 6.2. Check the commitments in $U_{n + 1}$ are the correct folding of those in $U_n, u_n$
78- 7.3: Verify the KZG proofs with respect to the commitments $U_{n + 1}.\{ \overline{E}, \overline{W} \} \in E_1$ and the challenges $c_E, c_W$.
79- 4.3: Verify the KZG proofs with respect to the commitments $U_{EC,n}.\{ \overline{E}, \overline{W} \} \in E_2$ and the challenges $c_E, c_W$.
80
81
82## Proving scheme
83We 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.
84Two proofs are generated, one for each circuit over their respective curves of the cycle.