# Recursion: Internal vrs External proofs

## Intro

with the advent of recursion there have been many schemes proposed. All these schemes have a notaion of an internal proof and an external proof. We have spent many years trying to find the best external proof.
More recently these proofs have been composed together to build recursion. Examples are Stark inside groth16, stark inside plonk, plonk inside plonk.

### What do exernal proofs look like
* constant or logirithim verifiers
* very small because need to be pass around or put on chain

### What kind of internal proofs do we want

* Prover that is very fast
* Should be efficient to arithmatize the verifier

You will notices that the differneces between interna and external proofs are quite big. It seems unlikely that the best internal proof also happenes to be a candidate external proof. Instead the best internal proofs that did not get traction due to proof time or verifier cost.

Here we propose paths to find the best internal proofs

## GKR / Hyrax / Libra

https://ethresear.ch/t/using-gkr-inside-a-snark-to-reduce-the-cost-of-hash-verification-down-to-3-constraints/7550/2 discusses using gkr inside groth16 to reduce the gas cost for mimc hashes.

https://ethresear.ch/t/prover-time-comparison-of-gkr-groth16-vs-groth16-for-proving-mimc-hashes/8373 they got 20x prover time reduction

### TODO

* Reimplment the gkr verifier in circom and halo2
* Benchmark the cost of both
* Deliver a ethresearch post for most efficient hash function prover time inside a snark
* Build a mimc circuit in GKR
* Estimate the GKR circuit cost GKR/ If feasible implement
* Estimate the GKR circuit cost for other intersting things / If feasible implment