category
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-
subgroups of , but we will describe it in more generic terms, as it is applicable to any group where the discrete logarithm problem is believed to be hard (such as elliptic curve groups).Definition #
Start with a finite group
of prime order , where is suitably large. For instance, we can use an order- subgroup the multiplicative group where divides , or an elliptic curve group or subgroup. Select two generators of such that is not known. The parameters of the commitment scheme are .To generate a commitment
to a secret integer , where , randomly sample and compute:
(When
are clear from context, we can simply write .)To open the commitment, simply reveal
and .Intuition as to Why Pedersen Commitments are Binding #
Suppose Alice has sent Bob a commitment
to a value . She now wants to cheat by sending Bob an opening for that corresponds to . In other words, she wants to break the binding property of Pedersen commitments.That means Alice has to find
such that . Since and are already fixed, Alice is left to solve . In other words, she needs to compute . Since the discrete logarithm problem is supposed to be hard in , Alice will have a difficult time finding .Before committing to a value, Alice can also look for distinct pairs
such that , without regard for the specific values of and . This is also equivalent to computing a discrete logarithm in . As the Pedersen paper points out: given , where , then , and it is possible to compute the discrete logarithm of with respect to :
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
to a value . Bob wants to cheat by figuring out , or at least something about , from .Remember that
is sampled uniformly at random, and so every value of is equally likely to be chosen, which means every value of is equally likely. Since is a generator of , that means that “selects” every element of uniformly at random.If Bob is able to gain any advantage in guessing the value of
or from , then he necessarily gains an advantage in guessing or . However, is selected uniformly at random, so is a uniform random element of . You can’t gain information about a uniform random distribution.The Additive Property #
Given two commitments,
and , the product of and is . 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;
.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
, Alice can demonstrate to Bob that she knows and without revealing either or . This is a useful protocol for protecting against the additive properties of Pedersen commitments being used maliciously. The protocol works as follows: