# Groth16 aggregation with public input trick

## Regular Groth 16

### CRS

* Random $\tau$ chosen during trusted setup as well as $\alpha$, $\beta$
* $n$ is number of gates.
* $u_i$, $v_i$ and $w_i$ are the QAP polynomials created from the R1CS circuit

$SRS = \{g_1^\alpha\, g_1^\beta, g_1^\delta, \{\{ g_1^{\tau^i}\}, \{g_1^{\alpha \tau^i}\}, \{g_1^{\beta \tau^i}\}\}_{i=0}^{n-1}, \{g_1^{\beta u_i(\tau) + \alpha v_i(\tau) + w_i(\tau)}\}_{i=0}^n\}, \{g^{\frac{\tau^it(x)}{\delta}}\}_{i=0}^{n-1},\\g_2^\beta, g_2^\delta, \{g_2^{\tau ^i}\}_{i=0}^{n-1}\}$

### Prover

**Settings**:
* Regular proof is $\pi = (A, B, C)$.
* $l+1$ is number of public inputs (+1 as first public input is "1" in R1CS)
* Vector of public inputs $\phi = (a_0, \dots, a_{l})$

**Extension**:
Prover computes the regular proof and computes the following additionally
* $S = g_1^{\sum_{i=0}^{l} a_i (\beta u_i(\tau) + \alpha v_i(\tau) + w_i(\tau))}$
* Derive random challenge $z = H(\phi, \pi, S)$
* Compute the three following elements.
* $U = g_2^{\sum_{i=0}^l a_i ( \frac{u_i(\tau) - u_i(z)}{\tau - z})}$
* $V = g_2^{\sum_{i=0}^l a_i ( \frac{v_i(\tau) - v_i(z)}{\tau - z})}$
* $W = g_2^{\sum_{i=0}^l a_i ( \frac{w_i(\tau) - w_i(z)}{\tau - z})}$

* Proof is $(\pi, S, U , V , W)$

### Verifier

* Compute the following three elements $u_z, v_z, w_z \in \mathbb{F_r}$:
* $u_z = \sum_{i=0}^l u_i(z)$
* $v_z = \sum_{i=0}^l v_i(z)$
* $w_z = \sum_{i=0}^l w_i(z)$
* Check **as usual**
* $e(A,B) = e(g_1^\alpha, g_2^\beta)e(S,g2)e(C,g2^\delta)$
* Check public input construction
* $e(Sg_1^{-\beta u_z -\alpha v_z -w_z},g_2) = e(g_1^{\beta \tau - \beta z}, U)e(g_1^{\alpha \tau - \alpha z},V)e(g_1^{\tau - z},W)$
* These computations are done using the CRS