Abstract
We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of $n$ source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by $6 \log n$ target group exponentiations. Proofs are of size $6 \log n$ target group elements, computed using $6n$ pairings and $4n$ exponentiations in each source group.
We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, $O(\sqrt{d})$ prover complexity for degree $d$ polynomials (not including the cost to evaluate the polynomial), and a CRS of size $O(\sqrt{d})$. Concretely, this means that for $d=2^{28}$, producing an evaluation proof in our protocol is $76\times$ faster than doing so in the KZG \cite{KateZG10} commitment scheme, and the CRS in our protocol is $1,000\times$ smaller: $13$MB vs $13$GB for KZG. This gap only grows as the degree increases. Our polynomial commitment scheme is applicable to both univariate and bivariate polynomials.
As a second application, we introduce an argument for aggregating $n$ $\mathsf{Groth16}$ zkSNARKs into an $O(\log n)$ sized proof. Our protocol is significantly more efficient than aggregating these SNARKs via recursive composition \cite{BoweCGMMW20}: we can aggregate about $130,000$ proofs in $25$min, while in the same time recursive composition aggregates just $90$ proofs.
Finally, we show how to apply our aggregation protocol to construct a low-memory SNARK for machine computations. For a computation that requires time $T$ and space $S$, our SNARK produces proofs in time $O(T)$ and space $O(S+T)$, which is significantly more space and time efficient than a monolithic SNARK, which requires space and time $O(S \cdot T)$.