Skip to content

Pedersen Commitment Scheme

Table of contents

Open Table of contents

What it is

A commitment scheme is a mechanism that ensures that a value a user has chosen can’t be changed afterwards.

Commitment schemes need to adhere to two properties:

  1. The value one has committed to has to remain hidden (i.e. given a commitment, one can’t determine the value that was committed to)
  2. The value one has committed to can’t be altered once the commitment was generated

How it works

The Pedersen Commitment Scheme presented here is based on Elliptic Curve Cryptography.

We’ll be using an Elliptic Curve EE that is of order qq. The curve has a generator GG. All calculations are done mod q\bmod\ q if not stated otherwise.

In our example Alice will commit to a value vv whereas Bob verifies that Alice did in fact commit to such value.

As a prerequisite, Alice and Bob need to agree on a point H=xGH = xG on the Elliptic Curve EE of which both don’t know the secret value xx that was used to derive HH (i.e. no one knows logG(H)\log_G(H)).

If this invariant can’t be ensured, then commitments can be forged. More on that later.

Once Alice and Bob agreed on HH, Alice can start and define the value vv she wants to commit to. In our case Alice samples that value randomly from Z\mathbb{Z}:

v$Zv \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}

Next up, Alice generates rr by sampling a random value from Zq\mathbb{Z}_q:

r$Zqr \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

The commitment cc will be the value vv multiplied by the generator GG to which rr multiplied by HH is added:

c=vG+rHc = vG + rH

Note that the addition of rHrH acts as a mask to ensure that cc looks like a random value to Bob.

Alice can now send the commitment cc to Bob.

Bob can verify that she indeed committed to vv by requesting access to vv and rr and checking if:

vG+rH=?cvG + rH \overset{?}{=} c

Pedersen Commitment Scheme

Why it works

The first thing to note is that the randomly sampled rr value that’s multiplied by HH acts as a mask to ensure that cc looks like a random value to Bob.

This implementation detail guarantees that the aforementioned property #1 of zero information leakage for commitment schemes is ensured.

Because the value xx such that H=xGH = xG is unknown to both Alice and Bob, it’s impossible for Alice to commit to a value vv (in combination with rr) while later on convincing Bob that she committed to a value vv' (in combination with rr').

This guarantee ensures that the aforementioned property #2 of commitment schemes (once a value is committed to, it can’t be changed) is covered.

When xx is known

As mentioned above, it’s critical to guarantee that x=logG(H)x = \log_G(H) is unknown to both Alice, and Bob as otherwise commitments can be forged.

The following is an outline why that is from a mathematical point-of-view.

Let’s assume that a commitment to a value vv with an rr has been made which according to the protocol results in:

c=vG+rHc = vG + rH

The goal now is to find the values vv' and rr' such that c=vG+rH=vG+rHc = vG + rH = v'G + r'H:

c=vG+rH=vG+rHvGrH=vGvG=rHrH=(vv)G=(rr)H÷(rr)=(vv)(rr)G=H\begin{aligned} c &= vG + rH = v'G + r'H && \mid -v'G -rH \\ &= vG - v'G = r'H - rH \\ &= (v - v')G = (r' - r)H && \mid \div (r' - r) \\ &= \frac{(v - v')}{(r' - r)}G = H \end{aligned}

Taking the logarithm of HH (logG(H)\log_G(H)) allows us to calculate the secret xx:

logG(H)=(vv)(rr)=x\log_G(H) = \frac{(v - v')}{(r' - r)} = x

As the equation shows, the committer would be able to recover logG(H)\log_G(H).