Alternative terms: Induction; Accumulation scheme; Proof-carrying data
However, the computation of requires a length- multiexponentiation where is composed of the round challenges 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 notice that we can express as a commitment to a polynomial
where is a polynomial with degree
|Since is a commitment, it can be checked in an inner product argument. The verifier circuit witnesses and brings out as public inputs to the proof The next verifier instance checks using the inner product argument; this includes checking that evaluates at some random point to the expected value for the given challenges Recall from the previous section that this check only requires work. |
At the end of checking and the circuit is left with a new along with the challenges sampled for the check. To fully accept as valid, we should perform a linear-time computation of . Once again, we delay this computation by witnessing and bringing 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.