# Recursive Proving

Recursive proof verify a proof that checks the correctness of **all previous proofs**. This creates a chain/tree of proofs that can be compressed into a single, succinct proof, enabling efficient verification of complex or sequential computations.

## How to Create a Proof from Another Proof

We show how to generate a new proof (Cur_Proof) to validate a prior proof (Pre_Proof). The prior proof Pre_Proof itself ensures the correctness of some computation, which could either be a verification algorithm or an initial arithmetic computation.


To validate a previous proof, the proof (Pre_Proof) is treated as a witness, and the computation/circuit is the **verification algorithm** V that the Pre_Verifier runs. Thus, creating a new proof (Cur_Proof) for this circuit V verifies the validity of the previous proof (Pre_Proof).

## Use cases of Recursive Proving

**Aggregation and Parallel Proof Generation.** Proof sizes can often be large, so it is beneficial to create short proofs for efficient verification. Recursive proving techniques allow a proof to validate the validity of other proofs, effectively compressing multiple layers of computation into a single compact proof.

This approach not only reduces verification complexity but also allows for distributed proof generation. Individual proofs can be generated in parallel and then recursively combined into one aggregate proof, ensuring both scalability and efficiency in proof systems.

*Caption: [Aggregate proofs into a single proof](https://ethresear.ch/t/reducing-the-verification-cost-of-a-snark-through-hierarchical-aggregation/5128)*

:::warning
Two verification algorithms are encoded as a circuit:
- V(earlierProof_1,z_1)=1
- V(earlierProof_2,z_2)=1
where z_1 and z_2 are public instances.
:::
**IVC (Incrementally Verifiable Computation) Chain.** Proofs can also be incrementally updated, which may cause the computation to grow beyond available memory. Recursive proving techniques address this by creating a proof that not only validates the new proof but also incorporates all existing proofs. This eliminates the need to re-verify previous proofs repeatedly, enabling scalability and maintaining efficiency as the number of proofs grows.

Suppose we have a function $F$ to prove for $i\in\{0,1,...,n-1\}$:
$$z_{i+1}=F(z_i,w_i)$$
where $z_i$ is the public instance and $w_i$ is the witness for step $i$.


Given $z_i, w_i$ and $\pi_{i}$, [IVC](https://eprint.iacr.org/2021/370.pdf) allows a prover to produce a proof $\pi_{i+1}$ for $z_{i+1}$. This proof not only verifies that $z_{i+1}=F(z_i,w_i)$, but also proves that the previous proof $\pi_{i}$ is valid. By induction, the finial proof $\pi_n$ serves as a compact verification that all intermediate steps are correct. Specifically, it proves that $z_{i+1}=F(z_i,w_i)$ for all $i\in\{0,1,...,n-1\}$, ensuring the correctness of the entire computation chain.

*Caption: [IVC chain](https://scryptplatform.medium.com/recursive-zero-knowledge-proofs-27f2d934f953)*

:::warning
$F$ and the verification algorithm are encoded as the circuit:
- $z_{i+1}=F(z_i,w_i)$
- $V(\pi_i,z_i)=1$
:::

## Practical Considerations for Verification Algorithms

TODO

## References

- [Recursive SNARKs and IVC](https://medium.com/veridise/introduction-to-nova-and-zk-folding-schemes-4ef717574484)
- [Recursive Zero-Knowledge Proofs](https://scryptplatform.medium.com/recursive-zero-knowledge-proofs-27f2d934f953)
- [Nova: Recursive Zero-Knowledge Arguments from Folding Schemes](https://eprint.iacr.org/2021/370.pdf)