## Recursion

Alternative terms: Induction; Accumulation scheme; Proof-carrying data

However, the computation of $G$ requires a length-$2_{k}$ multiexponentiation $⟨G,s⟩,$ where $s$ is composed of the round challenges $u_{1},⋯,u_{k}$ arranged in a binary counting structure. This is the linear-time computation that we want to amortise across a batch of proof instances. Instead of computing $G,$ notice that we can express $G$ as a commitment to a polynomial

$G=Commit(σ,g(X,u_{1},⋯,u_{k})),$

where $g(X,u_{1},⋯,u_{k}):=∏_{i=1}(u_{i}+u_{i}X_{2_{i−1}})$ is a polynomial with degree $2_{k}−1.$

Since $G$ is a commitment, it can be checked in an inner product argument. The verifier circuit witnesses $G$ and brings $G,u_{1},⋯,u_{k}$ out as public inputs to the proof $π.$ The next verifier instance checks $π$ using the inner product argument; this includes checking that $G=Commit(g(X,u_{1},⋯,u_{k}))$ evaluates at some random point to the expected value for the given challenges $u_{1},⋯,u_{k}.$ Recall from the previous section that this check only requires $gd$ work. At the end of checking $π$ and $G,$ the circuit is left with a new $G_{′},$ along with the $u_{1},⋯,u_{k}$ challenges sampled for the check. To fully accept $π$ as valid, we should perform a linear-time computation of $G_{′}=⟨G,s_{′}⟩$. Once again, we delay this computation by witnessing $G_{′}$ and bringing $G_{′},u_{1},⋯,u_{k}$ out as public inputs to the proof $π_{′}.$ This goes on from one proof instance to the next, until we are satisfied with the size of our batch of proofs. We finally perform a single linear-time computation, thus deciding the validity of the whole batch. |

We recall from the section Cycles of curves that we can instantiate this protocol over a two-cycle, where a proof produced by one curve is efficiently verified in the circuit of the other curve. However, some of these verifier checks can actually be efficiently performed in the native circuit; these are "deferred" to the next native circuit (see diagram below) instead of being immediately passed over to the other curve.