跳转到主要内容

热门内容

今日:


总体:


最近浏览:


Chinese, Simplified

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-
q

subgroups of
Zp

, 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
Zp

where
q

divides
p

, or an elliptic curve group or subgroup. Select two generators
g,h

of
G

such that
logg(h)

is not known. The parameters of the commitment scheme are
(G,q,g,h)

.

To generate a commitment
cG

to a secret integer
s

, where
0<s<q

, randomly sample
t$Zq

and compute:


c=Cg,h(s,t)=gsht

(When
g,h

are clear from context, we can simply write
C(s,t)

.)

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(s,t)

to a value
s

. She now wants to cheat by sending Bob an opening for
c

that corresponds to
ss

. In other words, she wants to break the binding property of Pedersen commitments.

That means Alice has to find
t

such that
gsht=c

. Since
gs

and
c

are already fixed, Alice is left to solve
ht=cgs

. In other words, she needs to compute
t=logh(cgs)

. 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
(s,t),(s,t)

such that
C(s,t)=C(s,t)

, 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(s,t)=C(s,t)

, where
ss

, then
tt

, and it is possible to compute the discrete logarithm of
h

with respect to
g

:


logg(h)=sstt(modq)

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(s,t)

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
ht

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
gs

from
c

, then he necessarily gains an advantage in guessing
t

or
ht

. However,
t

is selected uniformly at random, so
ht

is a uniform random element of
G

. You can’t gain information about a uniform random distribution.

The Additive Property #

Given two commitments,
c1=C(s1,t2)=gs1ht1

and
c2=C(s2,t2)=gs2ht2

, the product of
c1

and
c2

is
gs1+s2ht1+t2=C(s1+s2,t1+t2)

. 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(x,y)n=C(nx,ny)

.

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=Cg,h(x,y)=gxhy

, 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: