This is a read note of Programming Bitcoin Ch02: Elliptic Curves.

1 Definition

Elliptic curves have a form like this: y ** 2 = x ** 3 + ax + b. The left side square of y makes the curve symmetric over the x-axis. The secp256k1 elliptic curve used in bitcoin uses the equation y ** 2 = x ** 3 + 7.

A point is a pair of (x, y) that is on a specific curve defined by (a, b). For example, (-1, -1) is a point of y ** 2 = x ** 3 + 5x + 7.

2 Point Addition

Point addition is an operation that has a lot of the properties, such as communtative, of the addition operation in math.

For every elliptic curve, a line will intersect it at either one point or three points, except in a couple of special cases that a line intersects it at two points. Two special cases are vertical lines and tangent lines.

Except the special cases, two points form a line that must intersect the curve the third time. The third point reflected over the x-axis is the result of the point addition. For different values of A and B, A + B could be a point on the left, on the right or between both points.

Properties of point addition are:

  • Identity: the point at infinity. I + A = A
  • Invertibility: A + (-A) = I
  • Commutativity: A + B = B + A
  • Associativity: (A + B) + C = A + (B + C). It is the reason that the addition operation flips over the x-axis.

The operation needs to process five cases: a point is the identity point, two different points are in a vertical line, two different different points not in a vertical line, two points are same and y = 0 (left tangent), two points are same and y != 0.

The opearation are defined as the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Point:
    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y

        # an infinity point
        if self.x is None and self.y is None:
            return

        if self.y ** 2 != self.x ** 3 + a * x + b:
            raise ValueError("({}, {}) is not on the curve".format(x, y))

    def __add__(self, other):
        if self.a != other.a or self.b != other.b:
            raise TypeError(f"Points {self}, {other} are not on the same curve")

        if self.x is None:
            return other
        if other.x is None:
            return self

        if self.x == other.x and self.y != other.y:
            return self.__class__(None, None, self.a, self.b)

        if self.x != other.x or self.y != other.y:
            s = (other.y - self.y) / (other.x - self.x)
            x3 = s * s - self.x - other.x
            y3 = s * (self.x - x3) - self.y
            return self.__class__(x3, -y3, self.a, self.b)
        elif self.y != 0:
            s = (3 * self.x * self.x + self.a) / (2 * self.y)
            x3 = s * s - 2 * self.x
            y3 = s * (self.x - x3) - self.y
            return self.__class__(x3, -y3, self.a, self.b)
        else:
            return self.__class__(None, None, self.a, self.b)