BTC#: Elliptic Curves

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: Finite Fields in C#

Next: Elliptic Curve Point Addition »

Background

Chapter Two starts with a recap of some high-school maths, looking at the graphs of linear equations, quadratics, and cubics. This is worth reviewing, depending on how amazing or otherwise your high school maths was.

Elliptic Curves over Reals

There are many types of cubic curves beyond those we learned about in school. Elliptic curves are type of cubic curve that have the form

y2 = x3 + ax + b

Knowing this, we can fully define an elliptic curve with just the coefficients a and b.

For example, the elliptic curve used in bitcoin cryptography is called ‘secp256k1’, which is defined by the coefficients a = 0 and b = 7, giving

y2 = x3 + 7

EllipticCurveReal.png

The graphs of elliptic curves that we often see show the curves over real numbers. The Bitcoin wiki shows such a graph and then notes “that because secp256k1 is actually defined over the field Zp, its graph will in reality look like random scattered points, not anything like this.”

Elliptic Curves over Finite Fields

The reason we have points instead of a line is that the curve is only defined for values in the field, where x and y are integer values. The reason the points are all over the place is because in finite space the curve wraps around. Like in Pacman, where running off the right-hand side of the screen wraps you around to the left-hand side.

EllipticCurveWrapping.png

You can think of the graph as tiled, with tiles the size of the field order. Imagine the graph drawn on tiles of the appropriate size and then all the tiles overlaid on each other. You can see that the result is symmetrical around the middle of the y-axis but otherwise very hard to follow.

When we limit the values to the elements in the finite field we get the scatter of points described above. This is a graph of y2 = x3 – x in F61.

EllipticCurveFiniteField.png

The field order for the bitcoin curve is vastly bigger than the 61 shown here, so its graph is, as described by Andreas Antonopoulos in Mastering Bitcoin, “a much more complex pattern of dots on an unfathomably large grid.”

Point Code

I ended up doing two versions of the elliptic curve code. A version for the introductory code in this chapter, for getting to grips with elliptic curve point addition, and a second version that works with finite field elements that we look at in the next chapter. Song doesn’t do that in the book because Python’s dynamic type system makes it much easier to slide from one to another.

For this Chapter we’ll only worry about the simpler first case.

The first version (EllipticCurvePoint – see repo) takes integer parameters and implements equality and addition operators, as well as a method to check whether a point is on a given curve.

In the sample code, Song creates a Point class that takes both curve parameters (a, b) and point parameters (x, y) in its __init__ function and then raises an error if the point is not on the curve.

I’ve done something similar but extracted the PointIsOnCurve check as a separate method so it can be tested independently and used without raising exceptions.

public EllipticCurvePoint(int x, int? y, int a, int b)
{
    if (y.HasValue && !PointIsOnCurve(x, y.Value, a, b))
    {
        throw new ArgumentException($"Point ({x}, {y}) is not on the curve y^2 = x^3 + {a}x + {b}.");
    }
    X = x;
    Y = y;
    A = a;
    B = b;
}

I’ve made the y parameter nullable. Later on we’ll use this to represent “the point at infinity.” Needless to say this doesn’t come up in Python because any variable can be set to None.

public static bool PointIsOnCurve(int x, int y, int a, int b)
{
    return (int)Math.Pow(y, 2) == (int)Math.Pow(x, 3) + a * x + b;
}

Note the integer casts here. The Math.Pow() method takes and returns double. There’s an implicit conversion for the inbound arguments but the result needs to be explicitly cast back to an int.

The equality operator is implemented in a very similar way to what I did for the FiniteFieldElement class, so there’s no need to go over that again.

In the next post, we’ll look at the addition operator and what it means to add points on an elliptic curve.

« Previous: Finite Fields in C#

Next: Elliptic Curve Point Addition »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s