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.
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.
- 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
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.
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?
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
But, doing so breaks the binding property of the commitment, because instead of revealing value
8 and blinding factor
r, we could reveal
r+1 or any other value.
Therefore, we require a different method to include
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:
ris the blinding factor, and
r*Gis the public key point for
r(using G as generator point).
vis the value (coins) committed, and
v*His the public key point for
v(using H as generator point).
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.