# Simple Introduction to Pedersen Commitments

Previously:
Part 1: Brief Introduction to Elliptic-curves

This is the 2nd part of Introduction to Mimblewimble.

Note: If you’ve never encountered cryptographic commitments before, don’t worry if the later sections here take you some time and effort to wrap your head around.

# Commitments

A commitment scheme is a cryptographic primitive that allows you to commit to a chosen value while keeping it hidden from others, with the ability to reveal the committed value later.

Properties:

• Hiding - Nobody but the committer can see or infer the actual value behind the commitment.
• Binding - The committer can’t change the value after the commitment is published.

ECC can be used to create a commitment. Let’s say we want to commit to the value `8`.

``````commit (8)  ->  8*G
``````

To everybody else, our commitment `8*G` just looks like a random point, and we publish it. Some time later we reveal our value.

``````reveal 8
``````

And now any observer could multiply our stated value 8, by the public point G and verify that their result is equal to the commitment we published ealier.

``````verify (8, commitment) == 8*G  ? --> True/False
``````

However, there’s a major issue. If our value is within a small range, which is typically the case, it’s simple for anybody to find out what value we committed to, even if we don’t reveal it; By trying out (brute-forcing) different values, they can find the one value that, when multiplied by `G` , matches the original commitment.

Say we’re betting on how many goals a team would score by the end of the year. Our guess is 23, and we commit to it by publishing the commitment `23*G`. Problem is, it would be trivial for anybody to uncover our guess simply by trying to commit to 1, 2, 3, 4 etc and checking each result if it’s equal to our commitment. In this case, our value will be revealed after only 23 simple steps.

What’s the solution?

## Blinding Factor

The issue is solved by adding a blinding factor `r`, which is a random 256-bit integer (range 0 to 2^256, same as a typical private key) used to blind the value so that it can’t be guessed and uncovered.

We could try adding the blinding factor by comitting `(8+r)*G` and then revealing `8` and `r`.
But, doing so breaks the binding property of the commitment, because instead of revealing value `8` and blinding factor `r`, we could reveal `7` and `r+1` or any other value.

Therefore, we require a different method to include `r`.

## Pedersen Commitments

Introducing G’s twin, H.

H is another generator point, distinct from G (note how it’s the next letter in the alphabet). Both are nothing-up-my-sleeve-points, meaning nobody knows `n` such that `n*G = H`. Using H we can blind the value while keeping the commitment binding.

``````r*G + v*H
``````

This specific form of commitment is called a Pedersen Commitment.

A Mimblewimble output is just a Pedersen Commitment, as we’ll soon see. Its values:

• `r` is the blinding factor, and `r*G` is the public key point for `r` (using G as generator point).
• `v` is the value (coins) committed, and `v*H` is the public key point for `v` (using H as generator point).

## Homomorphic Commitments

Commitments with homomorphic properties means you can perform calculations on encrypted values without decrypting them first. The result of the computation is a commitment which is identical to the result if the operations had been performed on the unencrypted values.

They allow us to do as follows:

• commit (x) ⇒ C1
• commit (y) ⇒ C2
• commit (x + y) ⇒ Z = C1 + C2

If we add two commitments to each other, the result would be an entirely new, valid commitment, which actually commits to the value `x + y`. So we’re able to perform a math operation (addition) unto encrypted data (commitments) while keeping the underlying values “intact”.

Elliptic curve commitments indeed have these homomorphic properties. We can do the following:

``````x*G + y*G => (x + y)*G
``````

Notice how we add two different curve points and the result is a different point, which is a commitment to the sum of the values we’re hiding.

Similarly, we can add up two Pedersen Commitments. First let’s create two of them:

• C1 = r1G + v1H
• C2 = r2G + v2H

The point Z (remember a commitment is simply a point on the curve) is the result of addition between points C1 and C2.

``````Z = C1 + C2
``````
``````Z = r1*G + r2*G + v1*H + v2*H
``````

We can then calculate what Z is:

``````Z = (r1 + r2)*G + (v1 + v2)*H
``````

Hence point Z is a pedersen commitment that is the sum of commitments C1 and C2.

This is the foundation for the Elliptic-curve algebra used in Mimblewimble to prove both ownership of outputs (coins) and non-inflation.

Feel free to ask any stupid question, this is a no judgement zone. 3rd part soon.

4 Likes

That’s a good introduction to Pedersen commitments.

I would replace by:

• commit (x) ⇒ C1
• commit (y) ⇒ C2
• commit (x + y) ⇒ Z = C1 + C2

I would replace by:

If v is within a small range, which is typically the case for coins’ values (in Grin the value of a coin needs to be contained between 0 and 2^64 - 1 to be able to build valid bulletproofs), it is quite simple for anybody to find out what value we commited to in a reasonable amount of time, even if we don’t reveal it; By trying out (brute-forcing) different values, and finally finding the one value that, when multiplied by `G`, matches the original commitment. This method would not be possible to perform if the value would be a random scalar instead, like a private key typically is (otherwise we would be able to crack Satoshi coins :))

I see what you mean, but I think this part might be slighlty confusing, `r*G` or `v*H` do not have specific names as far as I know in Pedersen commitments.

“We can do the following xG + yG => (x + y)*G”
I would add: and in fact `x*G + y*G = (x + y)*G`.

Given what is just above this part (the operartions of adding two Pedersen commitments), I would replace by:
This is the foundation for the (elliptic-curve) algebra used in Mimblewimble to prove both ownership of outputs (coins) and non-inflation.

You could say what you said at the beginning of the Pedersen commitment part: Pedersen commitiments are the foundation for Mimblewimble outputs.

Finally, you should start first by introducing Homomorphic commitments, and then introduce Pedersen commiments, since the latter are a special case of the former.

1 Like