Bitcoin’s signing algorithm: Intro to the Elliptic Curve Group

Notes and analysis from Programming Bitcoin by Jimmy Song

This is post will cover the material in chapter 2.

In part one that we created a field, which I said was similar to a number system because it has two closed operations over its elements. This chapter is about a different kind of algebraic structure, called a group. Groups have only addition and subtraction, so no multiplication or division.

This post will introduce the elliptic curve group over the real numbers, E(ℝ). Technically the group works over any field. In the next post we will use finite fields with elliptic curves and see how they work together to power bitcoin’s digital signatures.

Elliptic curves can be thought of as a cubic polynomial (y = x³ + …) except that the upper half is reflected over the lower half. The actual definition is as follows:

The set of all points in the plane satisfying y² = x³ + ax + b over the projective plane.

The curve should additionally have a non-zero determinant, i.e. 4a³ + 27b² ≠ 0 , to avoid “singular points”, geometrically these appear as cusps, self-intersections or isolated points. You can see a cusp in the third column of the image below. Algebraically these lead to discontinuities and division-by-zero so they are typically discarded.

The underlying cubics on top row followed by elliptic form on bottom row. (sources here and here)

What is the projective plane?

The projective plane can be thought of as the Euclidean plane plus some extra “points at infinity”. The “projection” part comes from the idea that shapes on the plane are literally projections of shapes living on the surface of a sphere. Imagine drawing pictures on a lampshade to see what the corresponding shadow looks like on your wall. In math this is called stereographic projection, the lampshade is a sphere centered at the origin with a radius of 1. The wall is an infinite plane located one unit up in the direction of the Z-axis. Curves living on the surface of the sphere are projected out onto the plane. These projections will eventually intersect the plane unless they are perfectly horizontal, i.e. parallel to the plane.

From the perspective of the plane these are called points at infinity and collectively they form a equatorial ring around the sphere called the line at infinity. When a curve crosses this line, the corresponding projected curve will approach positive infinity from one side and negative infinity from the other. In this way, we say that the closure of the projective plane includes the regular Euclidean plane, ℝ², plus infinity.

Unit sphere with curve projected onto the plane (source)

More Info: These videos gives a much better explanation of projective geometry and its history. Also here is a page of different functions in projective space that you can move around in 3D.

How do elliptic curves form a group?

Let point addition on an elliptic curve be defined as:

Let R = -(P + Q) for collinear points P, Q and R

That’s it! Because of the projective plane, all the cases with infinity and duplicate points are handled by the same rule.

To show why this works, consider these two properties of elliptic curves

1. Provided any two points on curve C, a third point on C will exist collinear to the first two.
2. The negation of a point P, is it’s reflection over the x axis.

The first follows from Bézout’s theorem which states that the number of intersections between two curves is equal to the product of the “degree” of the curves, e.g., a line x¹ and a cubic x³ implies 3 points of intersection.

The second makes sense because (-y)² is the same as y². Also note that inverses have the same x value.

Since R and -R have the same y-coordinate the points line-up vertically. So there is no third intersection point on the Euclidean plane, only in projective space. Here the vertical line and curve intersect at a point at infinity. We call this the additive identity, 0, since it annihilates additive inverses (R and -R).

To verify this identity property check to see if P + 0 = P. Indeed it does, -P is collinear so the negative of -P is P by the addition rule. This can be written as P + Q + R = 0 since (P + Q) + R = (-R) + R = 0 for collinear points P, Q, R.

Now consider a few different cases:

1. P + Q + R = 0 where all points are distinct and no inverses or points on the x-axis.
2. One point is counted twice, P + Q + Q = 0, the other point is not -P. Here the line crosses the curve at exactly one other point. This is the tangent line at that point.
3. Two of the points are inverses of each other. The third point must be 0 because the sum of inverses is its own inverse.
4. Finally if P is on the y-axis then it is it’s own inverse and the third point is 0. Therefore P + P + 0 = 0.

Special cases of elliptic curve point addition. (source)

Commutativity, p + q = q + p, can be shown by property 1. The third intersection point is the same regardless of whether it crosses at p first or q first.

Associativity, (p + q) + r = p + (q + r), is difficult to prove. The book gives a couple diagrams (figures 16 and 17 from the chapter) to give you some intuition.

Honestly I don’t know why this proof isn’t a sufficient:

Compute from both sides separately to show that they end up with the same value. Starting with the left hand side of the associative rule substitute -(p+q) for r, resulting terms directly cancel out leaving 0.

(p + q) + r = (p + q) + -(p+q) = 0

Looking at the right hand side we can again substitute r with -(p+q):

p + (q + r) = p + (q + -(p+q))

Next swap the terms and distribute the negation (left as exercise for the reader) and cancel neighboring additive inverses and discard additive identities:

= p + (q + -(q+p)) = p + (q + -q + -p) = p + (0 + -p) = p + -p = 0

□

Finally the book chapter derives the closed form equations for computing addition over each of the special cases described above.

Closed form point addition equations

Case 1: Three distinct points, none of which are opposite, P + Q + R

In order to compute the x and y of the new point we need to embed the equation of a line with the equation of the curve. The point-slope equation of a line is this:

y = s(x - x₁) - y₁, where s = 𝚫y/𝚫x = (y₂ - y₁)/(x₂ - x₁)

Plug both of those into the elliptic curve and simplify:

y² = (s(x - x₁) + y₁)² = x³ + ax + b

= x³ - s²x² + (a + 2s²x₁ — 2sy₁)x + (b — s²x₁² + 2sx₁y₁ — y₁²) = 0

We also know that x₁, x₂, and x₃ are points on the curve therefore:

(x — x₁)(x — x₂)(x — x₃) = 0

= x³ — (x₁ + x₂ + x₃)x² + (x₁x₂ + x₁x₃ + x₂x₃)x — x₁x₂x₃ = 0

The x² coefficient can be replaced with -s2 due to Vieta’s formula. Combining the above two equations (both equal zero), we cancel the x³ and x² terms and simplify.

Solving for x₃ we get: x³ = s² — x₁ — x₂, which plugs back into the line equation to get y₃ = -(s(x₃ — x₁) + y₁) = s(x₁ — x₃) — y₁.

Case 2: Double point + non-zero point, P + P + Q

Here P₁ + P₂ = 0 and y₁ ≠ y₂ ≠ 0. We have to use the derivative of the curve to get its instantaneous slope at point 1: y² = x³ + ax + b — > dy/dx = (3x² + a) / 2y₁

x₃ = s²–2x₁, y₃ = s(x₁ — x₃) — y₁, where s = (3x₁² + a) / 2y₁

Case 3: Opposite but distinct points, has vertical tangent, P + -P + Q

Here P₁ + P₂ = 0 and y₁ ≠ y₂ ≠ 0. Therefore (x₃, y₃) = (∞, ∞) which is the point at infinity, 0.

Case 4: Double point at y=0, has a vertical tangent, P + P + 0

Here P₁ = P₂ and y₁ = y₂ = 0. The third point is 0 and it’s negative is also 0.Therefore (x₃, y₃) = (∞, ∞) which is again the point at infinity, 0

This concludes the description of the elliptic curve group over the field of real numbers. In the next part we will show how to combine these curves with finite fields to generate the one-way function and see how it is used in Bitcoin for digitally signing transactions.