Paper 2019/1177

Proofs for Inner Pairing Products and Applications

Benedikt Bünz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, and Psi Vesely

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 $$ source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by $$ target group exponentiations. Proofs are of size $$ target group elements, computed using $$ pairings and $$ exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, $$ prover complexity for degree $$ polynomials (not including the cost to evaluate the polynomial), and a CRS of size $$. Concretely, this means that for $$, producing an evaluation proof in our protocol is $$ faster than doing so in the KZG commitment scheme, and the CRS in our protocol is $$ smaller: $$MB vs $$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 $$ $$ zkSNARKs into an $$ sized proof. Our protocol is significantly more efficient than aggregating these SNARKs via recursive composition (BCGMMW20): we can aggregate about $$ proofs in $$min, while in the same time recursive composition aggregates just $$ 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 $$ and space $$, our SNARK produces proofs in space $$, which is significantly more space efficient than a monolithic SNARK, which requires space $$.

Note: Major update. Better presentation, full implementation and evaluation