# Pedersen Commitment Scheme

## 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}$:

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

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

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

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

$c = vG + rH$

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:

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

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

$c = vG + rH$

The goal now is to find the values $v'$ and $r'$ such that $c = vG + rH = v'G + r'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 $H$ ($\log_G(H)$) allows us to calculate the secret $x$:

$\log_G(H) = \frac{(v - v')}{(r' - r)} = x$

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