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}, \dots, 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}, \dots, u_{k})),$

where $g (X, u_{1}, \dots, u_{k}) := \prod_{i = 1}^{k} (u_{i} + u_{i}^{- 1} 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}, \dots, 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}, \dots, u_{k}))$ evaluates at some random point to the expected value for the given challenges $u_{1}, \dots, u_{k} .$ Recall from the previous section that this check only requires $lo g d$ work. At the end of checking $π$ and $G,$ the circuit is left with a new $G^{'},$ along with the $u_{1}^{'}, \dots, 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}^{'}, \dots, 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.

Since

G

is a commitment, it can be checked in an inner product argument. The verifier circuit witnesses

G

and brings

G, u_{1}, \dots, 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}, \dots, u_{k}))

evaluates at some random point to the expected value for the given challenges

u_{1}, \dots, u_{k} .

Recall from the previous section that this check only requires

lo g d

work.

At the end of checking

π

and

G,

the circuit is left with a new

G^{'},

along with the

u_{1}^{'}, \dots, 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}^{'}, \dots, 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.