# Recursive SNARK I

## SNARK Recap
* $S(C)$ --> public parameters $(pp, vp)$ for prover and verifier.
* $P(pp, x, w)$ --> proof $\pi$
* $V(vp, x, \pi)$ --> accept or reject

## Why do we recursive SNARK?

There are multiple SNARK proof system and each of them has their advantage and disadvantage.

For example, *groth16* could generate a **short proof**, yet the prover time is quite long ($O(n \log{n})$, as we call it **quasilinear**).Another example is *FRI-based proofs*, which has a **faster proof** but larger proof.

So, what if we could build a faster prover with a short proof? It turned out that recursive SNARK is able to **combine the advantages of 2 SNARKs and abandon the drawbacks of the SNARKs**.

## 2 Level SANRK recursion

> There are 2 proof system (SNARKs) in the recursive system
1. inner prover P1
* $(S, P, V)$
* input: $x$ (statement) and $w$ (witness)
* output: $\pi$ (proof of witness)
2. outer prover P2
* $(S', P', V')$
* input: $\pi$, $vp$ (public parameter from P1)
* output: $\pi'$ (**proof of knowledge of a proof**)

The main idea of recursive SNARKs is to generate **a proof of knowledge of another proof**. In other words, the final Verfier2 (V2) would **prove the knowledge of a proof that witness** $w$ **is a valid statement for** $x$.

## 1st Application: proof compression


> This is a 2 Level recursive SNARK structure of proof compression.

The main target is to build a system with **fast prover and short proof**. Here, P1 is a SNARK with fast prover & verifier with large proof and P2 is a much slower prover yet the final proof is much smaller.

By doing so, we can compress the large proof from P1, making it the witness in P2, and finally generate a smaller proof for V2 to verify.

The point needs to be noticed: since V1 has a larger circuit for verifying, we need V2 to be a smaller circuit to speed up the verification.

### Is this sound?
first we would fix a circuit C: $\mathbb{F^{n}} \times \mathbb{F^{m}} \rightarrow \mathbb{F}$ and let $(pp, vp) \leftarrow S(C)$
> Recap: a SNARK $(S, P, V)$ is knowledge sound for $C$ (circuit) if : for every poly-time prover $A$ there is a ploy-time extractor $E$ s.t. for all statement $y \in \mathbb{F^{n}}$:
> $Pr[C(y, w) = 0: w \leftarrow E(pp, y)] \geq Pr[V(vp, y, A(pp, y)) = yes] - \epsilon$
* left: E extract a valid witness of y
* right: adversary A outputs a convincing proof for y

#### Prove this
1. Let $C'((vp, x), \pi)$ be the circuit $[V(vp, x, \pi) == yes]$.
2. Let $A$ be a convincing prover for $(S', P', V')$ with respect to $C'$.

now we have to build a extractor which outputs $w \in \mathbb{F^{m}}$ s.t. $C(x, w) = 0$. (what we want the left side do).

For a given $x \in \mathbb{F^{n}}$ and $vp$, our extractor does:
1. 1st step: $(X', P', V')$ is knowledge sound for $C'$
* There's a Extractor $E'$ that extracts a witness $\pi$ from $A$ s.t. $V(vp, x, \pi) = yes$
* Which means $E'$ extracts a valid proof $\pi$ from $A$.
2. 2nd step:
* There's a Extractor $E$ that extracts a witness $w$ s.t. $C(x, w) = 0$ (Constraint)
* Which means $E$ extracts a valid witness $w$.

The success probability of this: (let $w$ be the extracted witness):
$$
Pr[C(x, w) = 0] \geq Pr[\pi' \leftarrow A(pp, x)\ is\ a\ convincing\ proof] - \epsilon' - \epsilon
$$

### Summary in compress proof

## Incrementally Verifiable Computation (IVC)
> Nova, SuperNova uses this as their recursive method.

### What is IVC?


Consider this kind of recursion is using a long computation done by iterating a function $F$.

* input: $(w_1, w_2, ..., w_n)$
* ouput: $s_n$

The goal of this is to generate a final output $s_n$ and proof $\pi_n$ and **only verify once in the final verifier to prove the proof** $\pi_n$ with $s_n$,** which implies that** $w_1, w_2, ... w_n$ **are all valid**.

### High Level

The high level idea of IVC:
Every step outputs a proof $(\pi_i)$ that the computation is correct till this point $(s_0 \to s_i)$.

More specifically, for step $i$, the prover outputs $s_i$ and proof $\pi_i$ that proves prover **has a witness** $(s_{i-1}, w_{i}, \pi_{i-1})$ s.t.
1. $F(s_{i-1}, w_i) = s_i$
2. $V(vp, ({i-1}, s_0, s_{i-1}, \pi_{i-1})) = yes$: the proof of $prover_i$ knows former proofs/ witness and they are valid.


What the prover does in every step:
input:
* $vp$: verify parameter
* $i-1$: last index
* $s_0$: primary input
* $s_{i-1}$: output from last step
* $\pi_{i-1}$: proof from last step

output:
* $vp$: still the same
* $i$: current index
* $s_0$: primary input
* $s_i$: current output
* $\pi_i$: current proof

final step:
* generate a proof $\pi_n$ with the statement inputs $(vp, n, s_0, s_n)$ into the Verifying Circuit to check if the proof is valid or not.

What proof ($\pi_i$) in every step stands for the **proof that I know this witness would satidfy the statement s.t. function** $F()$ **output is correct and this witness is accepted by the previous verifier**.

### Is this knowledge sound?

Extractor would take previous witness and proof to check the validation of the witness. Then, we would need to run extractor $n-1$ times to check to first proof $\pi_0$, first witness $w_0$ through function $F()$.

## Reference
- [ZKP MOOC lecture 10](https://youtu.be/0LW-qeVe6QI?si=FEnAcrhynJDxDILP)