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

$$\begin{gathered} 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 }^{i}t(x)}{\delta }}{\}}_{i=0}^{n-1}, \\ {g}_2^{\beta },g_2^{\delta },\{g_2^{{\tau }^i}{\}}_{i=0}^{n-1}\} \end{gathered}$$

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
  $\varphi =(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(\varphi ,\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}}_{\mathbb{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,g{2}^{\delta })$
• Check public input construction
  • $e(S{g}_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