4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.