1. Introduction

1-1. Problem

Let $\bold{A}=(A_0,\cdots,A_{m-1})\in\mathbb{G}1^m$ and $\bold{B}=(B_0,\cdots,B{m-1})\in\mathbb{G}_2^m$.
TIPP problem: Consider the following outsourcing of computation:

$$ \bold{A}*\bold{B}=\prod _{i=0}^{m-1}e(A_i,B_i)=? $$
A client (verifier) outsources this computation to a server (prover).
- The prover’s proof length must be sublinear to $m$.
- The verifier’s verification cost must be sublinear to $m$.

SRS setup (updatable)
- $2m$ elements in $\mathbb{G}_1$ and $\mathbb{G}_2$
Transcript length
- P→V: $O(\log_2(m))$ elements in $\mathbb{G}_T$
  - $6\log_2(m)$ elements in $\mathbb{G}_T$ as intermediate proofs.
  - $O(1)$ elements in $\mathbb{G}_1$ and $\mathbb{G}_2$, respectively, as KZG opening proofs.
- V→P: $O(\log_2(m))$ elements in $\mathbb{F}$
  - $\log_2(m)$ random challenges in $\mathbb{F}$
Verifier computation
- 7 pairings
- $6\log_2(m)$ exponentiation in $\mathbb{G}_T$
- $2\log_2(m)$ multiplication and addition in $\mathbb{F}$

Recall a Groth16 statement: $(\text{crs},D,\pi)$, where
- $\text{crs}$ is a list of setup keys in $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_T$, generated by a TTP, including
  - proving keys,
  - verifying keys such as $e([\alpha]_1,[\beta]_2)$, $[\delta]_2$, $[\gamma]_2$
- $D\in\mathbb{G}_1$ is an instance, generated by the verifier, and
- $\pi=(A,B,C)\in\mathbb{G}_1\times\mathbb{G}_2\times\mathbb{G}_1$ is a proof, generated by the prover.
- Recall Groth16’s verification:
$$ e(A,B)=e([\alpha]_1,[\beta]_2)e(C,[\delta]_2)e(D,[\gamma]_2). $$
Consider multiple Groth16 statements: $(\text{crs}_i,D_i,\pi_i)$ for $i=0,\cdots,m-1$.
- Multiple Groth16 verification equations can be aggregated by a random $r\in\mathbb{F}$ as follow,
  
  $$ \prod_{i=0}^{m-1}e(r^iA_i,B_i)=\prod_{i=0}^{m-1}e([\alpha_i]_1,[\beta_i]2)^{r^i}\prod{i=0}^{m-1}e(r^iC_i,[\delta_i]2)\prod{i=0}^{m-1}e(r^iD_i,[\gamma_i]_2) $$
- By letting $G'_i=r^iG_i$ for $G_i\in\{A_i,C_i,D_i\}$, this becomes a TIPP problem.