Most Bitcoin implementations skip over the mathematical details - for good reason! The gory details are not for the faint of heart! However, those who dare wade through the myriad equations, gain unparalleled clarity of the underlying concepts. I myself emerged on the other side, marveling at the beauty of the math behind Bitcoin; fascinated by the elegance of the implementation. I wonder why schools never discuss real-world use-cases such as this.
Throughout this article, I will be assuming basic understanding of Bitcoin and the blockchain. If you are new to Bitcoin or the concept of a blockchain, you should rather start off with few of the several non-mathematical treatments available online.
Ownership of Bitcoin
Bitcoins only exist as “transactions” (transfer of value from one address to another) in the blockchain. Each transaction can be traced back to one or more transactions where the bitcoins originated - generated by the system. To own a certain amount of bitcoins means possessing the ability to be able to transfer ownership (and hence, the bitcoins themselves) to another address. The sender must create a “digitally signed” transaction, which, if verified by others (the entire network can participate in this process), is added to the blockchain for all of eternity. This is where ECDSA comes in.
Elliptic Curve Digital Signature Algorithm is used to create digital signatures for data. A digital signature is similar to its real world counterpart - easy to read and identify the owner, but impossible to forge.
An elliptic curve is of the form:
y^2 = x^3 + ax + b
Bitcoin sets a=0, b=7
Properties of the Elliptic Curve
- If a line intersects two points on the curve, it will intersect exactly one more point
- A line tangent to the curve will intersect exactly one point on the curve
What about vertical lines (slope = INF)? Note that the slope of the elliptic curve goes on increasing beyond the point of inflection (the point where the direction of curvature changes). It can be implied from this that the slope becomes INF at some point. Hence, it can be said that a vertical line intersects the curve at INF.
Adding two points on the curve, ie: P1 + P2 = P3
If the line P1 P2 intersects the curve at point P3’ (from property #1 above), then P3 is the reflection of P3’ on the x-axis:
The line P1P2 is described by:
Where, the slope of the line is:
Plugging the value of y in the elliptic curve equation:
We arrive at a polynomial equation of the third degree. And,
With x3 known, we need y3:
Note: The point P3(x3, y3) is actually the reflection of P3’(x3, y3’)
Adding the same point to itself: P1 + P1 = P2
The tangent at point P1 intersects the curve at a point P2’ (from property #2). The reflection of point P2’ on the x-axis gives us P2:
We can use the results from point addition:
The slope of the tangent can be found by differentiation:
Hat-tip to Baidyanath for helping me understand this part!
Multiplying a point P by a number k:
R = k * P
This can be broken down into a point doubling and addition steps. Example:
3 * P = P + P + P = P + (P + P)
3P was thus broken down into one point-addition and one point-doubling step.
Elliptic Curve in Finite Fields
A finite field is a set of finite elements. To define our elliptic curve over a finite field:
- Limit values to integers instead of real numbers
- Compute all results modulo p; where p is a prime number
- Follow modular arithmetic for all operations
So, if our elliptic curve is
y^2 = x^3 + 10x
In context of a finite field, with p = 67, it becomes:
y^2 = (x^3 + 10x) mod 67
The plot of the curve changes significantly, but the characteristic properties are retained:
Note the unmistakable symmetry with respect to y=p/2. What previously was a continuous curve is now a set of disjoint points in the xy-plane
Parameters of the Elliptic Curve
The elliptic curve is described by certain parameters:
- the elliptic curve equation, defined by the coefficients (a, b)
- prime modulo p
- base point
Bitcoin uses Secp256k1 which defines the parameters as:
y^2 = x^3 + 7Prime modulo
2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2FPoint of Origin (G)
04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Creating the Private and Public Key pair
The private key is a randomly chosen 20-byte number. The public key is a point on the bitcoin elliptic curve generated from the point multiplication of G with the private key.
K(pub) = K(pvt) * G
Signing a message
1. Select a random number k such that 1 <= k <= n-1
2. Calculate the point P = k * G. That point's x value will represent R
3. Calculate S like so:
S = k^-1 (z + Kpvt * R) mod p
Where z is the SHA256 hash of the message, p is the prime modulo, Kpvt is the private key and k is the random number from step 1 above.
k^-1 is the modular multiplicative inverse of k
The pair (R, S) together form the digital signature.
Verifying a signature
To verify a digital signature (R, S), you need the public key and the curve parameters. Plug the values in this equation:
P = S^-1 * z * G + S^-1 * R * Kpub
If the singature is valid, the x coordinate of point P will be equal to R.
More to come
- Why this works
- Worked out example