# Sigma proofs for Pedersen commitments arithmetic under different bases

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.

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.

1. 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.

1. 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.

• Hmm, I think we can skip Q' and P' computation by combining the proofs together Sep 8, 2020 at 13:33
• Couldn't fit the idea in the comment, so I posted it as an answer instead Sep 8, 2020 at 14:00

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