# Pedersen Commitment

#### Protocol Description

**Setup**

Let $$G$$ be a (multiplicative) cyclic group of prime order for which the Discrete Logarithm problem is intractable. The key generation procedure publishes randomly chosen generators $$g, h ∈ G$$, which serve as both the commitment key and verification key.

**Commit**

To commit to a number $$m ∈ {0, . . . , |G| − 1}$$, committer picks a random $$z ∈ {0, . . . , |G| − 1}$$ and sends $$c = g^m · h^z$$.

**Open**

To open a commitment $$c$$, committer sends $$(m, z)$$. Verifier checks that $$c = g^m · h^z$$.

**Properties of the commitment:**

* perfect hiding
* computational binding

#### Additive Homomorphism

One important property of Pedersen commitments is that they are additively homomorphic. This means that the verifier can take two commitments $$c\_1$$ and $$c\_2$$, to values $$m\_1, m\_2 ∈ {0, . . . , |G| − 1}$$ (with $$m\_1, m\_2$$ known to the committer but not to the verifier), and the verifier on its own can derive a commitment $$c\_3$$ to $$m\_3 = m\_1 + m\_2$$, such that the prover is able to open $$c\_3$$ to $$m\_3$$. This is done by simply letting $$c\_3 = c\_1 · c\_2$$. As for “opening information” provided by the prover, if $$c\_1 = h^{m\_1} · g^{z\_1}$$ and $$c\_2 = h^{m\_2} · g^{z\_2}$$, then $$c\_3 = h^{m\_1+m\_2} · g^{z\_1+z\_2}$$, so the opening information for $$c\_3$$ is simply $$(m\_1 + m\_2, z\_1 + z\_2)$$. In summary, Pedersen commitments over a multiplicative group $$G$$ are additively homomorphic, with addition of messages corresponds to group-multiplication of commitments.

#### Perfect HVZK Proof of Knowledge of Opening

It is possible to the prover to prove that it knows how to open a commitment $$c$$ to some value, without actually opening the commitment.

**Protocol**

1. Let $$G$$ be a (multiplicative) cyclic group of prime order over which the Discrete Logarithm relation is hard, with randomly chosen generators $$g$$ and $$h$$.
2. Input is $$c = g^m · h^z$$. Prover knows $$m$$ and $$z$$, Verifier only knows $$c, g, h$$.
3. Prover picks $$d, r ∈ {0, . . . , |G| − 1}$$ and sends to verifier $$a = g^d · h^r$$.
4. Verifier sends challenge $$e$$ chosen at random from $${0, . . . , |G| − 1}$$.
5. Prover sends $$m' = me + d$$ and $$z' = ze + r$$
6. Verifier checks that $$g^{m'}· h^{z'} = c^e · a$$

**Properties of the protocol:**

* perfect completeness
* special soundness
* perfect HVZK

#### Establishing A Product Relationship Between Committed Values

Suppose the committer sends commitments $$(c\_1, c\_2, c\_3)$$ that is claimed to be a commitments to values $$(m\_1, m\_2, m\_1 · m\_2)$$. Pedersen commitments are not multiplicatively homomorphic but it is possible to the prover to prove to the verifier that $$c\_3$$ indeed commits to $$m\_1 · m\_2$$, without actually opening up $$c\_3$$ and thereby revealing $$m\_1 · m\_2$$.

**Protocol**

1. Let $$G$$ be a (multiplicative) cyclic group of prime order over which the Discrete Logarithm relation is hard.
2. Input is $$c\_i = g^{m\_i} · h^{r\_i}$$ for $$i ∈ {1, 2, 3}$$ such that $$m\_3 = m\_1 · m\_2 \mod |G|$$.
3. Prover knows $$m\_i$$ and $$r\_i$$ for all $$i ∈ {1, 2, 3}$$, verifier only knows $$c\_1, c\_2, c\_3, g, h$$.
4. Prover picks $$b\_1, . . . , b\_5 ∈ {0, . . . , |G| − 1}$$ and sends to verifier three values:

$$
α ← g^{b\_1} · h^{b\_2}, β ← g^{b\_3} · h^{b\_4}, γ ← c\_1^{b\_3} · h^{b\_5}.
$$

5. Verifier sends challenge $$e$$ chosen at random from $${0, . . . , |G| − 1}$$.
6. Prover sends:

$$
z\_1 ← b\_1 + e · m\_1, \ z\_2 ← b\_2 + e · r\_1, \ z\_3 ← b\_3 + e · m\_2, \ z\_4 ← b\_4 + e · r\_2, \ z\_5 ← b\_5 + e · (r\_3 − r\_1m\_2).
$$

7. Verifier checks that the following three equalities hold:

$$
g^{z\_1} · h^{z\_2} = α · c\_1^{e}, \ g^{z\_3} · h^{z\_4} = β · c\_2^e, \ c\_1^{z\_3} · h^{z\_5} = γ · c\_3^e.
$$

**Properties of the protocol:**

* perfect completeness
* special soundness
* perfect HVZK
