Pedersen Commitments #

Pedersen commitments were originally described as part of Pedersen’s verifiable secret-sharing scheme in 1992. Section 3 of the Pedersen paper notes that the commitment scheme is “very similar” to a scheme proposed by Bos, Chaum, and Purdy in an unpublished set of notes proposing a voting system.

Pedersen commitments are simple. Committing to a value requires only two modular exponentiations and a multiplication. Because a random value is required for each commitment, commitments are non-deterministic. And, because Pedersen commitments rely heavily on group structure, they inherit a large number of useful properties that allow for useful operations and proofs for the committed values.

Pedersen’s original proposal described the commitment in terms of order-$q$ subgroups of $\zns{p}$, but we will describe it in more generic terms, as it is applicable to any group $G$ where the discrete logarithm problem is believed to be hard (such as elliptic curve groups).

Definition #

Start with a finite group $G$ of prime order $q$, where $q$ is suitably large. For instance, we can use an order-$q$ subgroup the multiplicative group $\zps$ where $q$ divides $p$, or an elliptic curve group or subgroup. Select two generators $g,h$ of $G$ such that $\log_{g}\left(h\right)$ is not known. The parameters of the commitment scheme are $\left(G,q,g,h\right)$.

To generate a commitment $c\in G$ to a secret integer $s$, where $0 < s < q$, randomly sample $\sampleN{t}{\varq}$ and compute:

$$ c = C_{g,h}\left(s,t\right)=g^{s}h^{t} $$

(When $g,h$ are clear from context, we can simply write $C\left(s,t\right)$.)

To open the commitment, simply reveal $s$ and $t$.

Intuition as to Why Pedersen Commitments are Binding #

Suppose Alice has sent Bob a commitment $c=C\left(s,t\right)$ to a value $s$. She now wants to cheat by sending Bob an opening for $c$ that corresponds to $s’\neq s$. In other words, she wants to break the binding property of Pedersen commitments.

That means Alice has to find $t’$ such that $g^{s’}h^{t’}=c$. Since $g^{s’}$ and $c$ are already fixed, Alice is left to solve $h^{t’}=cg^{-s’}$. In other words, she needs to compute $t’=\log_{h}\left(cg^{-s’}\right)$. Since the discrete logarithm problem is supposed to be hard in $G$, Alice will have a difficult time finding $t’$.

Before committing to a value, Alice can also look for distinct pairs $\left(s,t\right),\left(s’,t’\right)$ such that $C\left(s,t\right)=C\left(s’,t’\right)$, without regard for the specific values of $s$ and $s’$. This is also equivalent to computing a discrete logarithm in $G$. As the Pedersen paper points out: given $C\left(s,t\right)=C\left(s’,t’\right)$, where $s’\neq s$, then $t’\neq t$, and it is possible to compute the discrete logarithm of $h$ with respect to $g$:

$$ \log_{g}\left(h\right)=\frac{s-s’}{t’-t}\pmod{q} $$

To summarize, breaking the binding property of Pedersen commitments is equivalent to solving the discrete log problem.

Intuition as to Why Pedersen Commitments are Hiding #

Suppose Alice has sent Bob a commitment $c=C\left(s,t\right)$ to a value $s$. Bob wants to cheat by figuring out $s$, or at least something about $s$, from $c$.

Remember that $t$ is sampled uniformly at random, and so every value of $t$ is equally likely to be chosen, which means every value of $h^{t}$ is equally likely. Since $h$ is a generator of $G$, that means that $t$ “selects” every element of $G$ uniformly at random.

If Bob is able to gain any advantage in guessing the value of $s$ or $g^{s}$ from $c$, then he necessarily gains an advantage in guessing $t$ or $h^{t}$. However, $t$ is selected uniformly at random, so $h^{t}$ is a uniform random element of $G$. You can’t gain information about a uniform random distribution.

The Additive Property #

Given two commitments, $c_{1}=C\left(s_{1},t_{2}\right)=g^{s_{1}}h^{t_{1}}$ and $c_{2}=C\left(s_{2}, t_{2}\right)=g^{s_{2}}h^{t_{2}}$, the product of $c_{1}$ and $c_{2}$ is $g^{s_{1}+s_{2}}h^{t_{1}+t_{2}} = C\left(s_{1}+s_{2},t_{1}+t_{2}\right)$. That is, the product of any two Pedersen commitments is a commitment to the sum of the committed values.

This also allows for scalar multiplication through exponentiation; $C\left(x,y\right)^{n}=C\left(nx,ny\right)$.

This additive property can be incredibly useful. It allows for a variety of operations to be performed on committed values before revealing them. Systems like Bulletproofs, for instance, exploit this property of the Pedersen scheme to commit to entire vectors of values at once, aggregating the commitments into a single value.

Useful Algorithms and Properties of Pedersen Commitments #

Proof of Knowledge of Secret #

Given a commitment $A=C_{g,h}\left(x,y\right)=g^{x}h^{y}$, Alice can demonstrate to Bob that she knows $x$ and $y$ without revealing either $x$ or $y$. This is a useful protocol for protecting against the additive properties of Pedersen commitments being used maliciously. The protocol works as follows:

This works because:

$$ g^{s_{1}}h^{s_{2}}=g^{xk+t_{1}}h^{yk+t_{2}}=g^{xk}h^{yk}g^{t_{1}}h^{t_{2}}=\left(g^{x}h^{y}\right)^{k}T=A^{k}T $$

This is secure because, in order to trick Bob, Alice needs to break the discrete log problem.

A straightforward application of the Fiat-Shamir transform can turn this into a non-interactive proof. If Alice selects $k=\hash{g\Vert h\Vert A\Vert T}$, where the output of $\hash{}$ has the same bit length as $q$, she can proceed as though $k$ were selected uniformly at random. Bob can compute $k$ in the same way, and verify the rest of the proof from there.

An Easy Proof of Equal Commitments #

Given two commitments to a secret $s$ using the same set of generators, call them $c_{1}=C\left(s,t_{1}\right)$ and $c_{2}=C\left(s,t_{2}\right)$, where $t_{2}\neq t_{1}$, Alice can easily show that both $c_{1}$ and $c_{2}$ commit to the same value. The simplest way, given by Pedersen, is for Alice to reveal $r=t_{1}-t_{2}\pmod{q}$ to Bob.

This works because Bob can check that

$$ c_{1}c_{2}^{-1}=g^{s}h^{t_{1}}g^{-s}h^{-t_{2}}=g^{s-s}h^{t_{1}-t_{2}}=h^{t_{1}-t_{2}}=h^{r} $$

Proof of Equal Commitments with Different Binding Generators #

Suppose Alice has $c_{1}=C_{g_{1},h}\left(s,t_{1}\right)$ and $c_{2}=C_{g_{2},h}\left(s,t_{2}\right)$, possibly with $g_{1}\neq g_{2}$. Alice can prove to Bob that $c_{1}$ and $c_{2}$ commit to the same value.

Alice starts by selecting random integers $\sampleN{r_{1},r_{2},r_{3}}{\varq}$, then computing $c_{3}=C_{g_{1},h}\left(r_{1},r_{2}\right)=g_{1}^{r_{1}}h^{r_{2}}$ and $c_{4}=C_{g_{2},h}\left(r_{1},r_{3}\right)=g_{2}^{r_{1}}h^{r_{3}}$. She sends $c_{3},c_{4}$ to Bob.

Bob selects a random challenge value $\sampleN{k}{\varq}$ and sends it to Alice.

Alice computes $z_{1}=ks+r_{1}$, $z_{2}=kt_{1}+r_{2}$, and $z_{3}=kt_{2}+r_{3}$ in $\mathbb{Z}_{q}$ and sends $z_{1},z_{2},z_{3}$ to Bob.

Bob then checks that $c_{3}c_{1}^{k}=C_{g_{1},h}\left(z_{1},z_{2}\right)$ and $c_{4}c_{2}^{k}=C_{g_{2},h}\left(z_{1},z_{3}\right)$. If the condition holds, Bob accepts the proof as valid.

This works because:

$$ c_{3}c_{1}^{k}=\left(g_{1}^{r_{1}}h^{r_{2}}\right)\left(g_{1}^{s}h^{t_{1}}\right)^{k}=g_{1}^{r_{1}}h^{r_{2}}g_{1}^{ks}h^{kt_{1}}=g_{1}^{ks+r_{1}}h^{kt_{1}+r_{2}}=g_{1}^{z_{1}}h^{z_{2}}=C_{g_{1},h}\left(z_{1},z_{2}\right) $$

and

$$ c_{4}c^{k}_{2}=\left(g_{2}^{r_{1}}h^{r_{3}}\right)\left(g_{2}^{s}h^{t_{2}}\right)^{k}=g_{2}^{r_{1}}h^{r_{3}}g_{2}^{ks}h^{kt_{2}}=g_{2}^{ks+r_{1}}h^{kt_{2}+r_{3}}=g_{2}^{z_{1}}h^{z_{3}}=C_{g_{2},h}\left(z_{1},z_{3}\right) $$

In diagram form: #

Again, this can be made non-interactive through the use of a Fiat-Shamir transform. Alice can use $k=\hash{g_{1}\Vert g_{2}\Vert h\Vert c_{1}\Vert c_{2}\Vert c_{3}\Vert c_{4}}$, again selecting a hash so that $k$ and $q$ have the same bit length.

While this construction is more complicated, it has the benefit of allowing for commitments to be made when $g_{1}\neq g_{2}$.

Proof of Squared Commitments #

We can use the equality of commitments proof above to commit to both a secret $s$ and its square.

Suppose Alice has a random $t_{1}$ and corresponding commitment $c_{1}=C_{g,h}\left(s,t_{1}\right)=g^{s}h^{t_{1}}$. Alice can select a random $t_{2}$ and compute $c_{2}=C_{c_{1},h}\left(s,t_{2}\right)=\left(c_{1}\right)^{s}h^{t_{2}}$

Note that $c_{2}=C_{c_{1},h}\left(s,t_{2}\right)=\left(c_{1}\right)^{s}h^{t_{2}}=\left(g^{s}h^{t_{1}}\right)^{s}h^{t_{2}}=g^{s^{2}}h^{st_{1}+t_{2}}=C_{g,h}\left(s^{2},st_{1}+t_{2}\right)$, so $c_{2}$ is a commitment to $s^{2}$ in base $g$.

Once $c_{1}$ has been generated, Alice can easily generate $c_{2}$, provide both values to Bob, and use the equality proof above to demonstrate that $c_{2}$ commits to the square of the value committed to by $c_{1}$.

Security Considerations #

Generator Selection #

Suppose that a Alice knows $l=\log_{g}\left(h\right)$ and has a commitment $c=C\left(s,t\right)=g^{s}h^{t}$.

Then Alice can rewrite the commitment as $c=g^{s}h^{t}$ as $c=g^{s}\left(g^{l}\right)^{t}=g^{s}g^{tl}=g^{s+tl}$. Let $s’=s+l$ and $t’=t-1$. She can the fraudulently “open” the commitment $c$ by sending $\left(s’,t’\right)$. This will appear as a valid opening to Bob, since:

$$ g^{s’}h^{t’}=g^{s+1}\left(g^{l}\right)^{t - 1}=g^{s+l}g^{l\left(t-1\right)}=g^{s+l}g^{tl-l}=g^{s+tl}=g^{s+tl}=c $$

If the discrete logarithm of $h$ with respect to $g$ is known to Alice (or if an insecure group is chosen that makes computing the discrete log easy), the binding property is lost.

This is why it is important to ensure that generators $g$ and $h$ are selected independently. Ideally, $g$ and $h$ should be chosen independently from one another using a nothing-up-my-sleeve construction. For instance, $g$ and $h$ can be selected using an agreed-upon PRF and algorithm D.3.1 from the ANSI X9.62 standard (“Finding a Point on an Elliptic Curve”).

Random Number Generator Issues #

In selecting the hiding value $\sampleN{t}{\varq}$, it is important that $t$ be truly uniform.

Suppose there is an attack on the process used to generate $t$, and we have a set of commitments $c_{1}, c_{2},\ldots,c_{n}$ to secrets $s_{1},s_{2},\ldots,s_{n}$, not necessarily distinct. An attacker can then attack each $h^{t_{i}}$ and recover the corresponding values for $g^{s_{i}}$. From this, the attacker can quickly identify repeated commitments to the same value. In cases where commitments are suspected of having a simple linear relationship (e.g. $s_{i}=k\cdot s_{j}$ or $s_{i}=s_{j} + k$ for some known value of $k$), these relationships can be recovered as well by examining $g^{s_{i}}g^{k}$ and $\left(g^{s_{i}}\right)^{k}$.

References #

• [Pedersen91] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing (1991).

• [ANSIX962] ANS X9.62-1998, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) (1998).