Ever wanted to understand how Grin works, but the math scared you off? I felt the same. In this 3 part series I’ll take you step-by-step through the process of understanding Mimblewimble once and for all (hint: it’s not as scary as it seems).
This is the 1st part of Introduction to Mimblewimble (It currently sits idly in the new docs, read by almost no-one).
Let’s go. Start fucking reading.
Elliptic Curve Cryptography
Mimblewimble relies entirely on Elliptic-curve cryptography (ECC), an approach to public-key cryptography. Put simply, given an algebraic curve of the form
y^2 = x^3 + ax + b, pairs of private and public keys can be derived. Picking a private key and computing its correspnding public key is trivial, but the reverse operation
public key -> private key is called the discrete logarithm problem, and is considered to be computationally infeasible.
Let’s review the basics.
These are the relevant mathematical operations we can do on Elliptic-curve points.
- Addition - Given two points, we can add them to one another (or subtract) and the result would be a new point on the curve.
- Multiplication - Given a point, we can multiply it any number of times.
Given three aligned points P, Q and R, their sum is always 0. We treat this as an inherent property of elliptic curves.
P + Q + R = 0
We can then write it as:
P + Q = -R
So that adding the two points P and Q results in -R, the inverse of R.
If we draw a line passing through P and Q, this line will cross a third point on the curve, R (so that P, Q and R are aligned). If we take the inverse of this point, which is simply the one symmetric to it about the x-axis, we have found the result of adding two curve points, P + Q. Let’s illustrate:
In other words, addition of points is basically hopping around on the curve to a different, seemingly random point; It looks random unless you know the exact operation performed to reach it.
We can’t multiply a point by another point, but we can multiply a point by a number (scalar). Multiplying point P by scalar
k would simply require adding point P onto it self
k times. This operation is easily demonstrated by assigning
k=2 so that
k*P = P+P. To illustrate how it would look like on the curve, we draw a tangent line. You can imagine that the line intersects three points, whereas two of them are P, such that:
P + P = -R
8*P for e.g. wouldn’t take 8 operations, but only 3; you can find
2*P, then add it onto itself, and then add
4*P onto itself, for the final result of
An ECC system defines a publicly known constant curve point called the generator point, G. The generator point is used to compute any public key. A key pair consists of:
- Private key k – A randomly chosen 256-bit integer (scalar).
- Public key P – An Elliptic-curve point derived by multiplying generator point G by the private key.
And more clearly, a public key (of private key
k) is as follows:
P = k*G
This is easy to compute.
But, if everybody knows points P and G, can they find out what
k is? The answer is no; The difficulty of getting from one point to another is precisely the definition of the Elliptic curve discrete logarithm problem.
Note: The specific Elliptic curve that Grin employs is rust-secp256k1 (y^2^ = x^3^ + 7) using Schnorr signature scheme.
Feel free to ask any stupid question, this is a no judgement zone. 2nd part soon.