Sigma proofs for Pedersen commitments arithmetic under different bases

Question

I was wondering if it's possible to prove an equality of openings between $3$ Pedersen commitments $P\cdot Q$ and $R$ when $P, Q, R$ have different commitment keys.

Suppose that commitment $R$ commits to $a+b$ and $P$ and $Q$ commit to $a$ and $b$ respectively. How can we prove, that $P$ and $Q$ combined commit to the same value as $R$ if we don't know relation betwen $(g_1, h_1)$ and $(g_2,h_2)$?

$P = g_1^ah_1^{r_1}$, $Q = g_2^b h_2^{r_2}$ and $R = g_3^{a+b}h_3^{r_3}$.

LegoSNARKs does something similar ($CP_{had}$), but I was curious if there is a solution with sigma protocols.

Answer 1

This is certainly possible using only standard Sigma-protocols and compose them together. But first, let's introduce the used standard Sigma-protocol building blocks:

1. Equality of committed values in two Pedersen commitments

Given Pedersen commitments $P=g_1^a h_1^{r_1} $ and $P'=g_2^{a'} h_2^{r_2} $, one can show in zero-knowledge using a Sigma-protocol that $a=a'$. Note, that all generators could potentially be different in the statement.

2. Equality of opening of two Pedersen commitments

Given Pedersen commitments $P=g_1^a h_1^{b} $ and $P'=g_2^{a'} h_2^{b'} $, one can show in zero-knowledge using a Sigma-protocol that $a=a'\land b=b'$. Note, that all generators could potentially be different in the statement.

3. Proving the conjunction of different statements using Sigma-protocols

Given several statements $\{\mathit{stmt_i}\}^{n}_{i=1}$, it is possible to prove their conjunction, i.e. $\wedge^{n}_{i=1} \mathit{stmt_i}$. In this case, for every statement the verifier samples the very same challenge value.

For a more thorough treatment on these building blocks, please refer to this post.

Now, it should be straightforward to devise a Sigma-protocol for your statement. Let's use the notation introduced in the question. First, prover computes $P'=g_3^a h_3^{r_1}$ and shows the equivalence of openings of $P'$ with $P$. It does the same for $Q'=g_3^b h_3^{r_2}$ and $Q$. Finally, prover can show the equality of committed values for the point $P'*Q'=g_3^{a+b} h_3^{r_1+r_2}$ and $R=g_3^{a+b} h_3^{r_3}$. The conjunction of these statements can also be easily proven by sampling the same challenge value for all the constituting Sigma-protocols.

Answer 2

I think it is possible to skip Q' and R' computation. The idea is practically the same as in István András Seres answer.

To prove that $P = g_1^ah_1^{r_1}$ and $Q=g_2^b h_2^{r_2}$ combined commit to the same value as $R = g_3^{a+b}h_3^{r_3}$ prover has to compute the following:

1. $z_1, z_2, z_3, z_4, z_5 \leftarrow Z^*$
2. $t_1 = g_1^{z_1}h_1^{z_2}$
3. $t_2 = g_3^{z_1 + z_4}h_3^{z_3}$
4. $t_3 = g_2^{z_4}h_2^{z_5}$
5. $c = Hash(g_1, g_2, g_3, h_1, h_2, h_3, P, Q, R, t_1, t_2, t_3)$
6. $s_1 = z_1 + a\cdot c$
7. $s_2 = z_2 + r_1 \cdot c$
8. $s_3 = z_3 + r_3 \cdot c$
9. $s_4 = z_4 + b \cdot c$
10. $s_5 = z_5 + r_2 \cdot c$
11. Output $t_1, t_2, t_3, s_1, s_2, s_3, s_4, s_5$

Verification:

1. $g_1^{s_1}h_1^{s_2} \stackrel{?}{=} P^c t_1$
2. $g_2^{s_4}h_2^{s_5} \stackrel{?}{=} Q^c t_3$
3. $g_3^{s_1 + s_4 } h_3^{s_3} \stackrel{?}{=} R^ct_2$

It should work, but I didn't write any proofs yet