Paper 2019/1177

Proofs for Inner Pairing Products and Applications

Benedikt Bünz and Mary Maller and Pratyush Mishra and Noah Vesely

Abstract

We present a generalized inner product argument and demonstrate its applications to pairing-based languages. As a first instantiation, we introduce a statistically sound proof for the product of $n$ pairings given public source group elements. This protocol enables outsourcing many pairing equation checks to an untrusted prover. Proofs are $2 \log n$ target group elements, computed using $2n$ pairings and $n$ exponentiations in each source group. There is no setup. The verifier work is dominated by two multi-exponentiations of size $n$ which require time $O(n/\log n)$. Asymptotically, verification is thus faster than computing the $n$ Miller loops that dominate the pairing product computation; indeed, our implementation demonstrates a $8 \times$ speedup for a million pairings. Next, 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 log-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 show how this argument can be used to aggregate $n$ Groth16 zkSNARKs into an $O(\log n)$ proof, presenting a more efficient alternative to recursive composition of SNARKs. Using a combination of our techniques, we build a polynomial commitment scheme with logarithmic communication and $O(\sqrt{d})$ prover complexity for degree $d$ polynomials (not including the cost to evaluate the polynomial). With a public-coin setup the verifier runs in $O(\sqrt{d})$ time, and with an SRS the verifier runs in $O(\log d)$ time.