Simple Introduction to Pedersen Commitments

1

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
2

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
3

Thanks kurt, glad to have your feedback! Followed most of your suggestions.