Pedersen Commitment Scheme

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 $E$ that is of order $q$. The curve has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

In our example Alice will commit to a value $v$ 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 = xG$ on the Elliptic Curve $E$ of which both don’t know the secret value $x$ that was used to derive $H$ (i.e. no one knows $\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 $H$, Alice can start and define the value $v$ she wants to commit to. In our case Alice samples that value randomly from $\mathbb{Z}$:

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

The commitment $c$ will be the value $v$ multiplied by the generator $G$ to which $r$ multiplied by $H$ is added:

Note that the addition of $rH$ acts as a mask to ensure that $c$ looks like a random value to Bob.

Alice can now send the commitment $c$ to Bob.

Bob can verify that she indeed committed to $v$ by requesting access to $v$ and $r$ and checking if:

Why it works

The first thing to note is that the randomly sampled $r$ value that’s multiplied by $H$ acts as a mask to ensure that $c$ 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 $x$ such that $H = xG$ is unknown to both Alice and Bob, it’s impossible for Alice to commit to a value $v$ (in combination with $r$) while later on convincing Bob that she committed to a value $v'$ (in combination with $r'$).

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 $x$ is known

As mentioned above, it’s critical to guarantee that $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 $v$ with an $r$ has been made which according to the protocol results in:

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

Taking the logarithm of $H$ ($\log_G(H)$) allows us to calculate the secret $x$:

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

Resources

• Wikipedia - Commitment Scheme
• RareSkills - What are Pedersen Commitments and How They Work
• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography