# Making Groth16 Vector-Commit-and-prove transparently

Our general approach consists of combining Caulk and Groth16. Caulk can prove subvector opening using a (non zero-knowledge) given a commitment $c_\text{caulk}$ to the subvector.
Here we describe a way to link the commitment $c_\text{caulk} = \sum_i \left( g^{\mu_i(s)} \right)^{u_i}$ to a subvector $u_1, \dots, u_\ell$ to a Groth16 proof.
Our setting below is not concerned with hiding.
### Standard Groth16 proof
Recall that verification of a proof $\pi = (A,B,C)$ in Groth16 boils down to an equation of this type.

$$
e(A,B) = e(g^\alpha, g^\beta)\cdot e(c_u, h^\gamma )\cdot e(C, h^\delta)
$$

where $c_u = \prod_{i=1}^\ell S^ {u_j}_j$ and $(g^\alpha, g^\beta, h^\gamma, h^\delta)$ and the $S_j$-s are in the SRS.

### Extended proof
We want to avoid communication complexity linear in the size of $u$. In order to do that, instead of the verifier computing $c_u$ itself, we let them receive it together with a proof that this is the correct commitment with respect to $c_\text{caulk}$.
This proof can consist of a proof of Pedersen equality, that is it shows knowledge of $\vec{u}$ that opens two commitments in two different basis.
In our case the bases are the $S_j$-s for $c_u$ and $(g^{\mu_1(s)}, \dots, g^{\mu_\ell(s)})$ for $c_\text{caulk}$.

### Instantations
We can obtain a proof of logarithmic size and linear verification using techniques from [compressed Sigma Protocols](https://eprint.iacr.org/2020/152).

A concrete instantiation is the one from the [ECLIPSE](https://eprint.iacr.org/2021/934.pdf) paper for the special case of $\ell=1$ (where $\ell$ is the one in the figure and not the size of the subvector $\vec{u}$). All the figures below are from the Eclipse paper. The whole protocol consists of the one in Fig. 2 compressed to the approach in Fig. 3.



### Amortizing communication complexity
A logarithmic communication complexity is still unacceptable in several cases.
We can plausibly amortize it and perform $m$ commitment linking proofs all at once with a communication complexity of $O(\log{(m\ell)})$ instead of $O(m\log{(\ell)})$.