Definition

Elliptic Curves are like many equations you’ve been seeing since pre-Algebra. They have y on one side and x on the other in some form. Elliptic Curves have a form like this:

y²=x³+ax+b

You’ve worked with other equations that look similar. For example, you probably learned the linear equation back in pre-Algebra:

y = mx + b

You may even remember that m here has the name slope and b, y-intercept. You can also graph linear equations like Figure 2-1:

Figure 2-1. Linear Equation

Similarly, you’re probably familiar with the quadratic equation and its graph (Figure 2-2):

y = ax²+bx+c

Figure 2-2. Quadratic Equation

And sometime around Algebra, you did even higher orders of x, something called the cubic equation and its graph (Figure 2-3):

y = ax³+bx²+cx+d

Figure 2-3. Cubic Equation

An Elliptic Curve isn’t all that different. The only real difference between the Elliptic Curve and the cubic curve above is the y² term on the left side. This has the effect of making the graph symmetric over the x-axis, shown in Figure 2-4:

Figure 2-4. Continuous Elliptic Curve

The Elliptic Curve is also less steep than the cubic curve. Again, this is because of the y² term on the left side. At times, the curve may even be disjoint like Figure 2-5:

Figure 2-5. Disjoint Elliptic Curve

If it helps, an Elliptic Curve can be though of as taking a cubic equation graph (Figure 2-6), taking only the part above the x-axis, flattening it out (Figure 2-7) and then mirroring the top half on the bottom half of the x-axis (Figure 2-8).

Figure 2-6. Step 1: A Cubic Equation

Figure 2-7. Step 2: Stretched Cubic Equation

Figure 2-8. Step 3: Reflected over the X-Axis

Specifically, the Elliptic Curve used in Bitcoin is called secp256k1 and it uses this particular equation:

y²=x³+7

The canonical form is y²=x³+ax+b so the curve is defined by the constants a=0, b=7. The curve looks like Figure 2-9:

Figure 2-9. secp256k1 Curve

Coding Elliptic Curves in Python

For a variety of reasons which will be made clear later, we are not interested in the curve itself, but specific points on the curve. For example, in the curve y²=x³+5x+7, we are interested in the coordinate (-1,1). We are thus going to define the class Point to be a point on a specific curve. The curve has the form y²=x³+ax+b, so we can define the curve with just the two numbers a and b.

class Point:

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

    def __eq__(self, other):  
        return self.x == other.x and self.y == other.y \
            and self.a == other.a and self.b == other.b

We check here that the point is actually on the curve.

Points are equal if and only if they are on the same curve and have the same coordinates

We can now create Point objects, and we will get an error if the point is not on the curve:

>>> from ecc import Point
>>> p1 = Point(-1, -1, 5, 7)
>>> p2 = Point(-1, -2, 5, 7)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "ecc.py", line 143, in __init__
    raise ValueError('({}, {}) is not on the curve'.format(self.x, self.y))
ValueError: (-1, -2) is not on the curve

In other words, __init__ will raise an exception when the point is not on the curve.

Point Addition

Elliptic Curves are useful because of something called Point Addition. Point Addition is where we can do an operation on two of the points on the curve and get a third point, also on the curve. This is called “addition” because the operation has a lot of the intuitions we associate with what we call “addition”. For example, Point Addition is commutative. That is, adding point A to point B is the same as adding point B to point A.

The way we define Point Addition is as follows. It turns out that for every Elliptic Curve, a line will intersect it at either 1 point (Figure 2-10) or 3 points (Figure 2-11), except for a couple of special cases.

Figure 2-10. Line intersects at only 1 point

Figure 2-11. Line intersects at 3 points

The two exceptions are when a line is tangent to the curve (Figure 2-13) and when a line is exactly vertical (Figure 2-12).

Figure 2-12. Line intersects at 2 points because it’s vertical

Figure 2-13. Line intersects at 2 points because it’s tangent to the curve

We will come back to these two cases later.

We can define point addition using the fact that lines intersect one or three times with the Elliptic Curve. Two points define a line, so since that line must intersect the curve at some point one more time. That third point reflected over the x-axis is the result of the point addition.

Like Finite Field Addition, we are going to define point addition. In our case, point addition is defined this way:

For any two points P₁=(x₁,y₁) and P₂=(x₂,y₂), we get P₁+P₂ by:

• Find the point intersecting the Elliptic Curve a third time by drawing a line through P₁ and P₂

• Reflect the resulting point over the x-axis

Visually, it looks like Figure 2-14:

Figure 2-14. Point Addition

We first draw a line through the two points we’re adding (A and B). The third intersection point is C. We then reflect that point over the x-axis, which puts us at the A+B point in Figure 2-14.

One of the properties that we are going to use is that point addition is not easily predictable. We can calculate point addition easily enough with a formula, but intuitively, the result of point addition can be almost anywhere given two points on the curve. Going back to Figure 2-14, A+B is to the right of both points, A+C would be somewhere between A and C on the x-axis, and B+C would be to the left of both points. In mathematics parlance, point addition is non-linear.

Math of Point Addition

“Addition” in the name Point Addition satisfies certain properties that we think of as addition, such as:

• Identity

• Commutativity

• Associativity

• Invertibiltiy

Identity here means that there’s a zero. That is, there exists some point (I) which when added to a point (A) results in A. We’ll call this point the point at infinity (reasons for this will become clear in a bit). That is:

I + A = A

This is also related to invertibility. For some point A, there’s some other point -A which results in the Identity point. That is:

A + (-A) = I

Visually, these are points opposite the x-axis on the curve (see Figure 2-15).

Figure 2-15. Vertical Line Intersection

This is why we call this point the point at infinity. We have one extra point in the Elliptic Curve which makes the vertical line intersect the curve a third time.

Commutativity means that A+B=B+A. This is obvious since the line going through A and B will intersect the curve a third time in the same place no matter the order.

Associativity means that (A+B) + C = A + (B+C). This isn’t obvious and is the reason for flipping over the x-axis.

Figure 2-16. (A+B)+C

Figure 2-17. A+(B+C)

You can see that in both Figure 2-16 and Figure 2-17, the final point is the same. While this doesn’t prove the associativity of point addition, the visual should at least give you the intuition that this is true.

To code point addition, we’re going to split it up into 3 steps:

1. Where the points are in a vertical line or using the Identity.

2. Where the points are not in a vertical line, but are different.

3. Where the two points are the same.

Coding Point Addition

We first handle the identity, or the point at infinity. Since we can’t easily use infinity in Python, we’ll use the None value instead. What we want is this to work:

>>> from ecc import Point
>>> p1 = Point(-1, -1, 5, 7)
>>> p2 = Point(-1, 1, 5, 7)
>>> inf = Point(None, None, 5, 7)
>>> print(p1 + inf)
Point(-1,-1)_5_7
>>> print(inf + p2)
Point(-1,1)_5_7
>>> print(p1 + p2)
Point(infinity)

In order to make this work, we have to do two things:

First, we have to adjust the __init__ method slightly so it doesn’t check that the curve equation is satisfied when we have the point at infinity. Second, we have to overload the addition operator or __add__ as we did with the FieldElement class.

class Point:

    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y
        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('Points {}, {} are not on the same curve'.format(self, other))

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

x-coordinate and y-coordinate being None is how we signify the point at infinity. Note that the next if statement will fail if we don’t return here.

We overload the + operator here

self.x being None means that self is the point at infinity, or the additive identity. Thus, we return other

self.x being None means that other is the point at infinity, or the additive identity. Thus, we return self

Point Addition for when x₁≠x₂

Now that we’ve covered the vertical line, we’re now proceeding to when the points are different. When we have points where the x’s differ, we can add using a fairly simple formula. To help with intuition, we’ll first find the slope created by the two points. You can figure this out using a formula from pre-Algebra:

• P₁=(x₁,y₁), P₂=(x₂,y₂), P₃=(x₃,y₃)

• P₁+P₂=P₃

• s=(y₂-y₁)/(x₂-x₁)

This is the slope and we can use the slope to calculate x₃. Once we know x₃, we can calculate y₃. P₃ can be derived using this formula:

• x₃=s²-x₁-x₂

• y₃=s(x₁-x₃)-y₁

Remember that y₃ is the reflection over the x-axis.

Coding Point Addition for when x₁≠x₂

We now code this into our library. That means we have to adjust the __add__ method to handle the case where x₁≠x₂. We have the formulas:

• s=(y₂-y₁)/(x₂-x₁)

• x₃=s²-x₁-x₂

• y₃=s(x₁-x₃)-y₁

At the end of the method, we return an instance of the class Point using self.__class__ to make subclassing easier..

Point Addition for when P₁=P₂

When the x coordinates are the same and the y coordinate is different, we have the situation where the points are opposite each other over the x-axis. We know that this means:

P₁=-P₂ or P₁+P₂=I

We’ve already handled this in Exercise 3.

What happens when P₁=P₂? Visually, we have to calculate the line that’s tangent to the curve at P₁ and find the point at which the line intersects the curve. The situation looks like this as we saw before (see Figure 2-18):

Figure 2-18. Line that’s tangent to the curve

Once again, we’ll find the slope of the tangent point.

• P₁=(x₁,y₁), P₃=(x₃,y₃)

• P₁+P₁=P₃

• s=(3x₁²+a)/(2y₁)

The rest of the formula goes through as before, except x₁=x₂, so we can combine them:

• x₃=s²-2x₁

• y₃=s(x₁-x₃)-y₁

Coding Point Addition for when P₁=P₂

We adjust the __add__ method to account for this particular case. We have the formulas, we now implement them.

• s=(3x₁²+a)/(2y₁)

• x₃=s²-2x₁

• y₃=s(x₁-x₃)-y₁

Coding One More Exception

There is one more exception and this involves the case where the tangent line is vertical (Figure 2-19):

Figure 2-19. Vertical and Tangent to the curve

This can only happen if P₁=P₂ and the y-coordinate is 0, in which case the slope calculation will end up with a 0 in the denominator.

We handle this with a special case:

class Point:
    ...
    def __add__(self, other):
    	...
	if self == other and self.y == 0 * self.x:  
	    return self.__class__(None, None, self.a, self.b)

If the two points are equal and the y coordinate is zero, we return the point at infinity.

Conclusion

We’ve covered what Elliptic Curves are, how they work and how to do point addition. We now combine the concepts from Chapter 1 and Chapter 2 to learn Elliptic Curve Cryptography in Chapter 3.

Elliptic Curves over Reals

We discussed in Chapter 2 what an Elliptic Curve looks like visually because we were plotting the curve over real numbers. Specifically, it’s not just integers or even rational numbers, but all real numbers. Pi, sqrt(2), e+7th root of 19, etc are all part of real numbers.

This worked because real numbers are also a field. Note unlike a finite field, there are an infinite number of real numbers, but otherwise the same properties hold:

1. If a and b are in the set, a+b and a⋅b are in the set.

2. The additive identity, 0 exists and has the property a + 0 = a.

3. The multiplicative identity, 1 exists and has the property a ⋅ 1 = a.

4. If a is in the set, -a is in the set, which is defined as the value that makes a + (-a) = 0.

5. If a is in the set and is not 0, a^-1 is in the set, which is defined as the value that makes a ⋅ a^-1 = 1.

Clearly, all of these are true as normal addition and multiplication apply for the first part, additive and multiplicative identities 0 and 1 exist, -x is the additive inverse and 1/x is the multiplicative inverse.

Real numbers are easy to plot and we can see the a graph over reals visually. For example, y²=x³+7 can be plotted like Figure 3-1:

Figure 3-1. secp256k1 over real numbers

It turns out we can use the point addition equations over any field, including the Finite Fields we learned in Chapter 1. The only difference is that we have to use the addition/subtraction/multiplication/division as defined in Chapter 1, not the “normal” versions that the real numbers use.

Elliptic Curves over Finite Fields

So what does an Elliptic Curve over a Finite Field look like? Let’s look at the equation y²=x³+7 over F₁₀₃. We can verify that the point (17,64) is on the curve by calculating both sides of the equation:

• y²=64²%103=79

• x³+7=(17³+7)%103=79

We’ve verified that the point is on the curve using Finite Field math.

Because we’re evaluating the equation over a Finite Field, the plot of the equation looks vastly different (Figure 3-2):

Figure 3-2. Elliptic Curve over a Finite Field

As you can see, it’s very much a scattershot of points and there’s no smooth curve here. This is not surprising since the points are discrete. About the only pattern is that the curve is symmetric right around the middle, which is due to the y² term. The graph is not symmetric over the x-axis as in the curve over reals, but about half-way up the y-axis due to there not being negative numbers in a Finite Field.

What’s amazing is that we can use the same point addition equations with the addition, subtraction, multiplication, division and exponentiation as we defined them for Finite Fields and everything still works. This may seem surprising, but abstract math has regularities like this despite being different than the traditional modes of calculation you may be familiar with.

Coding Elliptic Curves over Finite Fields

Because we defined an Elliptic Curve point and we defined the +, - ,* and / operators for Finite Fields, we can combine the two classes to create Elliptic Curve points over a Finite Field.

>>> from ecc import FieldElement, Point
>>> a = FieldElement(num=0, prime=223)
>>> b = FieldElement(num=7, prime=223)
>>> x = FieldElement(num=192, prime=223)
>>> y = FieldElement(num=105, prime=223)
>>> p1 = Point(x, y, a, b)
>>> print(p1)
Point(FieldElement_223(192),FieldElement_223(105))_FieldElement_223(0)_FieldElement_223(7)

When initializing Point, we will run through this part of the code:

class Point:

    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y
        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))

The addition (+), multiplication (*), exponentiation (**) and equality (!=) here use the __add__, __mul__, __pow__ and __ne__ methods from FiniteField respectively and not the integer equivalents. Being able to do the same equation but with different definitions for the basic arithmetic operators is how we construct an Elliptic Curve Cryptography library.

We’ve already coded the two classes that we need to implement Elliptic Curve points over a Finite Field. However, to check our work, it will be useful to create a test suite. We will do this using the results of Exercise 2.

class ECCTest(TestCase):

    def test_on_curve(self):
        prime = 223
        a = FieldElement(0, prime)
        b = FieldElement(7, prime)
        valid_points = ((192, 105), (17, 56), (1, 193))
        invalid_points = ((200, 119), (42, 99))
        for x_raw, y_raw in valid_points:
            x = FieldElement(x_raw, prime)
            y = FieldElement(y_raw, prime)
            Point(x, y, a, b)  
        for x_raw, y_raw in invalid_points:
            x = FieldElement(x_raw, prime)
            y = FieldElement(y_raw, prime)
            with self.assertRaises(ValueError):
                Point(x, y, a, b)  

We pass in FieldElement objects into the Point class for initialization. This will, in turn, use all the overloaded math operations in FieldElement

We can now run this test like so:

>>> import ecc
>>> from helper import run  
>>> run(ecc.ECCTest('test_on_curve'))
.
----------------------------------------------------------------------
Ran 1 test in 0.001s

OK

helper is a module with some very useful utility functions, including the ability to run unit tests individually.

Point Addition over Finite Fields

We can use all the same equations over Finite Fields, including the linear equation:

y=mx+b

It turns out that a “line” in a Finite Field is not quite what you’d expect (Figure 3-3):

Figure 3-3. Line over a Finite Field

The equation nevertheless works and we can calculate what y should be for a given x.

Remarkably, point addition works over Finite Fields as well. This is because the Elliptic Curve point addition works over all fields! The same exact formulas we used to calculate point addition over reals work over Finite Fields. Specifically:

when x₁≠x₂:

• P₁=(x₁,y₁), P₂=(x₂,y₂), P₃=(x₃,y₃)

• P₁+P₂=P₃

• s=(y₂-y₁)/(x₂-x₁)

• x₃=s²-x₁-x₂

• y₃=s(x₁-x₃)-y₁

when P₁=P₂:

• P₁=(x₁,y₁), P₃=(x₃,y₃)

• P₁+P₁=P₃

• s=(3x₁²+a)/(2y₁)

• x₃=s²-2x₁

• y₃=s(x₁-x₃)-y₁

All of the equations for Elliptic Curves work over Finite Fields and that sets us up to create some cryptographic primitives.

Coding Point Addition over Finite Fields

Because we coded FieldElement in such a way as to define __add__, __sub__, __mul__, __truediv__, __pow__, __eq__ and __ne__, we can simply initialize Point with FieldElement objects and point addition will work:

>>> from ecc import FieldElement, Point
>>> prime = 223
>>> a = FieldElement(num=0, prime=prime)
>>> b = FieldElement(num=7, prime=prime)
>>> x1 = FieldElement(num=192, prime=prime)
>>> y1 = FieldElement(num=105, prime=prime)
>>> x2 = FieldElement(num=17, prime=prime)
>>> y2 = FieldElement(num=56, prime=prime)
>>> p1 = Point(x1, y1, a, b)
>>> p2 = Point(x2, y2, a, b)
>>> print(p1+p2)
Point(FieldElement_223(170),FieldElement_223(142))_FieldElement_223(0)_FieldElement_223(7)

Scalar multiplication for Elliptic Curves

Because we can add a point to itself, we can introduce some new notation:

(170,142) + (170,142) = 2⋅(170,142)

Similarly, because we have associativity, we can actually add the point again:

2⋅(170,142) + (170,142) = 3⋅(170, 142)

We can do this as many times as we want. This is what we call Scalar Multiplication. That is, we have a scalar number in front of the point. We can do this because we have defined point addition and point addition is associative.

One property of scalar multiplication is that it’s really hard to predict without calculating (see Figure 3-4):

Figure 3-4. Scalar Multiplication Results for y²=x³+7 over F₂₂₃ for point (170,142)

Each point is labeled by how many times we’ve added the point. You can see that this is a complete scattershot. This is because point addition is non-linear and not easy to calculate. Performing scalar multiplication is straightforward, but doing the opposite, Point division, is not.

This is called the Discrete Log problem and is the basis of Elliptic Curve Cryptography.

Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, point at infinity is the additive identity or 0). If we imagine a point G and scalar multiply until we get the point at infinity, we end up with a set:

{ G, 2G, 3G, 4G, … nG } where nG=0

It turns out that this set is called a Group and because n is finite, we have a Finite Group (or more specifically a Finite Cyclic Group). Groups are interesting mathematically because they behave a lot like addition:

G+4G=5G or aG+bG=(a+b)G

When we combine the fact that scalar multiplication is easy to go in one direction but hard in the other and the mathematical properties of a Group, we have exactly what we need for Elliptic Curve Cryptography.

Scalar Multiplication Redux

Scalar Multiplication is adding the same point to itself some number of times. The key making scalar multiplication into Public Key Cryptography is the fact that scalar multiplication on Elliptic Curves is very hard to reverse. Note the previous exercise. Most likely, you calculated the point s⋅(47,71) in F₂₂₃ for s from 1 until 21. Here are the results:

>>> from ecc import FieldElement, Point
>>> prime = 223
>>> a = FieldElement(0, prime)
>>> b = FieldElement(7, prime)
>>> x = FieldElement(47, prime)
>>> y = FieldElement(71, prime)
>>> p = Point(x, y, a, b)
>>> for s in range(1,21):
...     result = s*p
...     print('{}*(47,71)=({},{})'.format(s,result.x.num,result.y.num))
1*(47,71)=(47,71)
2*(47,71)=(36,111)
3*(47,71)=(15,137)
4*(47,71)=(194,51)
5*(47,71)=(126,96)
6*(47,71)=(139,137)
7*(47,71)=(92,47)
8*(47,71)=(116,55)
9*(47,71)=(69,86)
10*(47,71)=(154,150)
11*(47,71)=(154,73)
12*(47,71)=(69,137)
13*(47,71)=(116,168)
14*(47,71)=(92,176)
15*(47,71)=(139,86)
16*(47,71)=(126,127)
17*(47,71)=(194,172)
18*(47,71)=(15,86)
19*(47,71)=(36,112)
20*(47,71)=(47,152)

If we look closely at the numbers, there’s no real discernible pattern to the scalar multiplication. The x-coordinates don’t always increase or decrease and neither do the y-coordinates. About the only pattern is that between 10 and 11, the x-coordinates are equal (10 and 11 have the same x, as do 9 and 12, 8 and 13 and so on). This is due to the fact that 21⋅(47,71)=0.

Scalar multiplication looks really random and that’s what gives this equation asymmetry. An asymmetric problem is one that’s easy to calculate in one direction, but hard to reverse. For example, it’s easy enough to calculate 12⋅(47,71). But if we were presented this:

s⋅(47,71)=(194,172)

Would you be able to solve for s? We can look up the table above, but that’s because we have a small group. We’ll see later that when we have numbers that are a lot larger, Discrete Log becomes an intractable problem.

Mathematical Groups

The preceding math (Finite Fields, Elliptic Curves, combining the two), was really to bring us to this point. What we really want to generate for the purposes of Public Key Cryptography are Finite Cyclic Groups and it turns out that if we take a Generator Point from an Elliptic Curve over a Finite Field, we can generate a Finite Cyclic Group.

Unlike fields, groups have only a single operation. In our case, Point Addition is our operation. We also have a few other properties like closure, invertibility, commutativity and associativity. Lastly, we need the identity.

Let’s look at each property.

Identity

If you haven’t guessed by now, the identity is defined as the point at infinity, which is guaranteed to be in the group since we generate the group when we get to the point at infinity. So:

0 + A = A

We call 0 the point at infinity because visually, it’s the point that exists to help the math work out (Figure 3-5):

Figure 3-5. Vertical Line “intersects” a third time at the point at infinity

Invertibility

Visually, invertibility is easy to see (Figure 3-6):

Figure 3-6. Each point is invertible by taking the reflection over the x-axis

Mathematically, we know that if aG is in the group, (n-a)G is also in the group. You can add them together to get aG+(n-a)G=(a+n-a)G=nG=0.

Commutativity

We know from Point Addition that A+B=B+A (Figure 3-7):

Figure 3-7. The Line through the points doesn’t change

This means that aG+bG=bG+aG, which proves commutativity.

Associativity

We know from Point Addition that A+(B+C)=(A+B)+C (see Figure 3-8 and 3-9)

Figure 3-8. (A+B)+C

Figure 3-9. A+(B+C)

Thus, aG+(bG+cG)=(aG+bG)+cG proving associativity.

Coding Scalar Multiplication

What we’re trying to do with the last exercise is this:

>>> from ecc import FieldElement, Point
>>> prime = 223
>>> a = FieldElement(0, prime)
>>> b = FieldElement(7, prime)
>>> x = FieldElement(15, prime)
>>> y = FieldElement(86, prime)
>>> p = Point(x, y, a, b)
>>> print(7*p)
Point(infinity)

We want to be able to scalar multiply the point with some number. Thankfully, there’s a method in Python called __rmul__ that can be used to override the front multiplication. A naive implementation looks something like this:

class Point:
    ...
    def __rmul__(self, coefficient):
        product = self.__class__(None, None, self.a, self.b) 
        for _ in range(coefficient): 
            product += self
        return product

We start the product at 0, which in the case of Point Addition is the point at infinity.

We loop coefficient times and add the point each time

This is fine for small coefficients, but what if we have a very large coefficient? That is, a number that’s so large that we won’t be able to get out of this loop in a reasonable amount of time? For example, a coefficient of 1 trillion is going to take a really long time.

There’s a really cool technique called binary expansion that allows us to perform multiplication in log2(n) loops, which dramatically reduces the calculation time for large numbers. For example, 1 trillion is 40 bits in binary, so we only have to loop 40 times for a number that’s generally considered very large.

class Point:
    ...
    def __rmul__(self, coefficient):
        coef = coefficient
        current = self  
        result = self.__class__(None, None, self.a, self.b)  
        while coef:
            if coef & 1:  
                result += current
            current += current  
            coef >>= 1
        return result  

current represents the point that’s at the current bit. First time through the loop it represents 1*self, the second time, it will be 2*self, third time, 4*self, then 8*self and so on. We double the point each time. In binary the coefficients are 1, 10, 100, 1000, 10000, etc.

We start the result at 0, or the point at infinity.

We are looking at whether the right-most bit is a 1. If it is, then we add the value of the current bit.

We need to double the point until we’re past how big the coefficient can be.

We bit shift the coefficient to the right.

This is an advanced technique and if you don’t understand bitwise operators, think of representing the coefficient in binary and only adding the point where there are 1’s.

With __add__ and __rmul__, we can start defining some more complicated Elliptic Curves.

Defining the curve for Bitcoin

While we’ve been using relatively small primes for the sake of examples, we are not restricted to such small numbers. Small primes mean that we can use a computer to search through the entire Group. If the group has a size of 301, the computer can easily do 301 computations to reverse scalar multiplication or break Discrete Log.

But what if we made the prime larger? It turns out that we can choose much larger primes than we’ve been using. The security of Elliptic Curve Cryptography depends on computers not being able to go through the an appreciable fraction of the group.

An Elliptic Curve for Public Key Cryptography is defined with the following parameters:

• We specify the a and b of the curve y²=x³+ax+b.

• We specify the prime of the Finite Field, p.

• We specify the x and y coordinates of the generator point G

• We specify the order of the group generated by G, n.

These numbers are known publicly and together form the cryptographic curve. There are many cryptographic curves and they have different security/convenience trade-offs, but the one we’re most interested in is the one Bitcoin uses: secp256k1. The parameters for secp256k1 are these:

• a = 0, b = 7, making the equation y²=x³+7

• p = 2²⁵⁶-2³²-977

• G_x =

0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

• G_y =

0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

• n =

0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

G_x refers to the x-coordinate of the point G and G_y the y-coordinate. The numbers starting with 0x indicate a hexadecimal number.

There are a few things to notice about this curve.

First, the equation is relatively simple. Many curves have a and b that are much bigger. secp256k1 has a really simple equation.

Second, p is really, really close to 2²⁵⁶. This means that most numbers under 2²⁵⁶ are in the prime field and thus, any point on the curve has x and y-coordinates that are expressible in 256-bits each. n is also very close to 2²⁵⁶. This means any scalar multiple can also be expressed in 256 bits.

Third, 2²⁵⁶ is a really big number (See the How Big is 2²⁵⁶). Amazingly, any number below 2²⁵⁶ can be stored in 32 bytes. This means that we can store the private key relatively easily.

>>> gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
>>> p = 2**256 - 2**32 - 977
>>> print(gy**2 % p == (gx**3 + 7) % p)
True

>>> from ecc import FieldElement, Point
>>> gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
>>> p = 2**256 - 2**32 - 977
>>> n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
>>> x = FieldElement(gx, p)
>>> y = FieldElement(gy, p)
>>> seven = FieldElement(7, p)
>>> zero = FieldElement(0, p)
>>> G = Point(x, y, zero, seven)
>>> print(n*G)
Point(infinity)

P = 2**256 - 2**32 - 977
...
class S256Field(FieldElement):

    def __init__(self, num, prime=None):
        super().__init__(num=num, prime=P)

    def __repr__(self):
        return '{:x}'.format(self.num).zfill(64)

A = 0
B = 7
...
class S256Point(Point):

    def __init__(self, x, y, a=None, b=None):
        a, b = S256Field(A), S256Field(B)
        if type(x) == int:
            super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)
        else:
            super().__init__(x=x, y=y, a=a, b=b)  

N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
...
class S256Point(Point):
    ...
    def __rmul__(self, coefficient):
        coef = coefficient % N  
        return super().__rmul__(coef)

G = S256Point(
    0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
    0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

>>> from ecc import G, N
>>> print(N*G)
S256Point(infinity)

Public Key Cryptography

Finally, we have the tools that we need to do Public Key Cryptography operations. The key operation that we need is P=eG which is an asymmetric equation. We can easily compute P when we know e and G, but we cannot easily compute e when we know P and G. This is the Discrete Log Problem described earlier.

The difficulty of Discrete Log will be essential to understanding signing and verification algorithms.

Generally, we call e the Private Key and P the Public Key. We’ll note here that the private key is a single 256-bit number and the public key is a coordinate (x,y) where x and y are each 256-bit numbers.

Signing and Verification

To set up the motivation for why signing and verification exists, imagine this scenario. You want to prove that you are a really good archer, like at the level where you can hit any target you want within 500 yards as opposed to being able to hit any single target.

Now if someone could observe you and interact with you, proving this would be easy. Perhaps they would position your son 400 yards away with an apple on his head and challenge you to hit that apple with an arrow. You, being a very good archer, do this and prove your expertise. The target, if specified by the challenger, makes your archery skill easy to verify.

Unfortunately, this doesn’t scale very well. If, for example you wanted to prove this to 10 people, you would have to shoot 10 different arrows at 10 different targets from 10 different challenges. You could try to do something like have 10 people watch you shoot a single arrow, but since they can’t all choose the target, they can never be sure that you’re not just good at hitting one particular target instead of an arbitrary target. What we want is something that you can do once, requires no interaction but still proves that you are indeed, a good archer that can hit any target.

If, for example, you shot an arrow into a target of your choosing, then the people observing afterwards won’t necessarily be convinced. After all, you may be a sneaky person that paints the target around wherever your arrow happened to land. So what can you do?

Here’s a very clever thing you can do. Inscribe the tip of the arrow with the position of the target that you’re hitting (“apple on top of my son’s head”) and then hit that target with your arrow. Now anyone seeing the target can take an x-ray machine and look at the tip of the embedded arrow and see that the tip indeed says exactly where it was going to hit. The tip clearly had to be inscribed before the arrow was shot, so this can prove you are indeed a good archer (provided the actual target isn’t just one that you’ve practiced over and over).

This is the same technique we’re using with signing and verification, except what we’re proving isn’t that we’re good archers, but that we know a secret number. We want to prove possession of the secret without revealing the secret itself. We do this by putting the target into our calculation and hitting that target.

Ultimately this is going to be used in Transactions which will prove that the rightful owners of the secrets are spending the Bitcoins.

>>> from ecc import S256Point, G, N
>>> z = 0xbc62d4b80d9e36da29c16c5d4d9f11731f36052c72401a76c23c0fb5a9b74423
>>> r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6
>>> s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec
>>> px = 0x04519fac3d910ca7e7138f7013706f619fa8f033e6ec6e09370ea38cee6a7574
>>> py = 0x82b51eab8c27c66e26c858a079bcdf4f1ada34cec420cafc7eac1a42216fb6c4
>>> point = S256Point(px, py)
>>> s_inv = pow(s, N-2, N)  
>>> u = z * s_inv % N  
>>> v = r * s_inv % N  
>>> print((u*G + v*point).x.num == r)  
True

P = (0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c,
     0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34)

# signature 1
z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60
r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395
s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4

# signature 2
z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d
r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c
s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6

class Signature:

    def __init__(self, r, s):
        self.r = r
        self.s = s

    def __repr__(self):
        return 'Signature({:x},{:x})'.format(self.r, self.s)

class S256Point(Point):
    ...
    def verify(self, z, sig):
        s_inv = pow(sig.s, N - 2, N)  
        u = z * s_inv % N  
        v = sig.r * s_inv % N  
        total = u * G + v * self  
        return total.x.num == sig.r  

>>> from ecc import S256Point, G, N
>>> from helper import hash256
>>> e = int.from_bytes(hash256(b'my secret'), 'big')  
>>> z = int.from_bytes(hash256(b'my message'), 'big')  
>>> k = 1234567890  
>>> r = (k*G).x.num  
>>> k_inv = pow(k, N-2, N)
>>> s = (z+r*e) * k_inv % N  
>>> point = e*G  
>>> print(point)
S256Point(028d003eab2e428d11983f3e97c3fa0addf3b42740df0d211795ffb3be2f6c52, \
0ae987b9ec6ea159c78cb2a937ed89096fb218d9e7594f02b547526d8cd309e2)
>>> print(hex(z))
0x231c6f3d980a6b0fb7152f85cee7eb52bf92433d9919b9c5218cb08e79cce78
>>> print(hex(r))
0x2b698a0f0a4041b77e63488ad48c23e8e8838dd1fb7520408b121697b782ef22
>>> print(hex(s))
0xbb14e602ef9e3f872e25fad328466b34e6734b7a0fcd58b1eb635447ffae8cb9

e = 12345
z = int.from_bytes(hash256('Programming Bitcoin!'), 'big')

class PrivateKey:

    def __init__(self, secret):
        self.secret = secret
        self.point = secret * G  

    def hex(self):
        return '{:x}'.format(self.secret).zfill(64)

from random import randint
...
class PrivateKey:
...
    def sign(self, z):
        k = randint(0, N)  
        r = (k*G).x.num  
        k_inv = pow(k, N-2, N)  
        s = (z + r*self.secret) * k_inv % N  
        if s > N/2:  
            s = N - s
        return Signature(r, s) 

Conclusion

We’ve covered Elliptic Curve Cryptography and we can now prove that we know a secret by signing something and we can also verify that the person with the secret actually signed a message. Even if you don’t read another page in this book, you’ve learned to implement what was once considered “weapons grade munitions” (see https://en.wikipedia.org/wiki/Export_of_cryptography_from_the_United_States). This is a major step in your journey and will be essential for the rest of the book!

We now turn to serializing a lot of these structures so that we can store them on disk and send them over the network.

Uncompressed SEC format

We’ll start with the S256Point class which is the public key class. Recall that the public key in Elliptic Curve Cryptography is really a coordinate in the form of (x,y). How can we serialize this data?

It turns out there’s already a standard for serializing ECDSA public keys called SEC. SEC stands for Standards for Efficient Cryptography and as the word “Efficient” in the name suggests, it’s got minimal overhead. There are two forms of SEC format that we need to be concerned with and the first is the uncompressed SEC format and the second compressed SEC format.

Here is how the uncompressed SEC format for a given point P=(x,y) is generated:

1. Start with the prefix byte which is 0x04.

2. Next, append the x-coordinate in 32 bytes as a Big-Endian integer.

3. Next, append the y-coordinate in 32 bytes as a Big-Endian integer.

The uncompressed SEC format is in Figure 4-1:

Figure 4-1. Uncompressed SEC Format

Creating the uncompressed SEC format serialization is pretty straightforward. The trickiest part being converting a 256-bit number into 32 bytes, Big-Endian. Here’s how this is done in code:

class S256Point(Point):
...
    def sec(self):
        '''returns the binary version of the sec format'''
	return b'\x04' + self.x.num.to_bytes(32, 'big') \
            + self.y.num.to_bytes(32, 'big')  

In Python 3, you can convert a number to bytes using the to_bytes method. The first argument is how many bytes it should take up and the second argument is the endianness (see Big and Little Endian).

Compressed SEC Format

Recall that for any x-coordinate, there are at most two y-coordinates due to the y² term in the elliptic curve equation (Figure 4-2):

Figure 4-2. The two possible values for y are where this vertical line intersects the curve.

It turns out that even over a Finite Field, we have the same symmetry.

This is because for any (x,y) that satisfies y²=x³+ax+b, (x,-y) also satisfies the equation. Furthermore, in a Finite Field, -y (mod p) = p - y. Or more accurately, if (x,y) satisfies the elliptic curve equation, (x,p-y) also satisfies the equation. These are the only two solutions for a given x as shown above, so if we know x, we know y-coordinate has to be either y or p-y.

Since p is a prime number greater than 2, we know that p is odd. Thus, if y is even, p-y (odd minus even) will be odd. If y is odd, p-y will be even. In other words, between y and p-y exactly one will be even and one will be odd. This is something we can use to our advantage to shorten the Uncompressed SEC Format. We can provide the x-coordinate and the even-ness of the y-coordinate. We call this the Compressed SEC format because of how the y-coordinate is compressed into a single byte (namely, whether it’s even or odd).

Here is the serialization of the Compressed SEC format for a given point P=(x,y):

1. Start with the prefix byte. If y is even, it’s 0x02, otherwise it’s 0x03.

2. Next, append the x-coordinate in 32 bytes as a Big-Endian integer.

The Compressed SEC format is in Figure 4-3:

Figure 4-3. Compressed SEC Format

Again, the procedure is pretty straightforward. We can update the sec method to handle compressed SEC keys.

class S256Point(Point):
...
    def sec(self, compressed=True):
        '''returns the binary version of the SEC format'''
        if compressed:
            if self.y.num % 2 == 0:
                return b'\x02' + self.x.num.to_bytes(32, 'big')
            else:
                return b'\x03' + self.x.num.to_bytes(32, 'big')
        else:
            return b'\x04' + self.x.num.to_bytes(32, 'big') + \
                self.y.num.to_bytes(32, 'big')

The big advantage of the Compressed SEC format is that it only takes up 33 bytes instead of 65 bytes. This is a big savings when amortized over millions of transactions.

At this point, you may be wondering how you can analytically calculate y given the x-coordinate. This requires us to calculate a square-root in a Finite Field.

Stated mathematically:

Find w such that w² = v when we know v.

It turns out that if the Finite Field prime p % 4 = 3, we can do this rather easily. Here’s how.

First, we know:

p % 4 == 3

Which implies

(p + 1) % 4 == 0

That is (p+1)/4 is an integer.

By definition,

w² = v

We are looking for a formula to calculate w. From Fermat’s Little Theorem:

w^p-1 % p = 1

Which means:

w²=w²⋅1=w²⋅w^p-1=w^(p+1)

Since p is odd (recall p is prime), we know we can divide (p+1) by two and still get an integer implying

w=w^(p+1)/2

Now we can use (p+1)/4 being an integer this way:

w=w^(p+1)/2=w^2(p+1)/4=(w²)^(p+1)/4=v^(p+1)/4

So our formula for finding the square root becomes:

if w² = v and p % 4 = 3, w = v^(p+1)/4

It turns out that the p used in secp256k1 is such that p % 4 == 3, so we can use this formula:

• w²=v

• w=v^(p+1)/4

That will be one of the two possible w’s the other will be p-w. This is due to taking the square root means that both the positive and negative will work.

We can add this as a general method in the S256Field

class S256Field(FieldElement):
...
    def sqrt(self):
        return self**((P + 1) // 4)

When we get a serialized SEC pubkey, we can write a parse method to figure out which y we need:

class S256Point:
...
    @classmethod
    def parse(self, sec_bin):
        '''returns a Point object from a SEC binary (not hex)'''
        if sec_bin[0] == 4:  
            x = int.from_bytes(sec_bin[1:33], 'big')
            y = int.from_bytes(sec_bin[33:65], 'big')
            return S256Point(x=x, y=y)
        is_even = sec_bin[0] == 2  
        x = S256Field(int.from_bytes(sec_bin[1:], 'big'))
        # right side of the equation y^2 = x^3 + 7
        alpha = x**3 + S256Field(B)
        # solve for left side
        beta = alpha.sqrt()  
        if beta.num % 2 == 0:  
            even_beta = beta
            odd_beta = S256Field(P - beta.num)
        else:
            even_beta = S256Field(P - beta.num)
            odd_beta = beta
        if is_even:
            return S256Point(x, even_beta)
        else:
            return S256Point(x, odd_beta)

The uncompressed is pretty straightforward.

The evenness of the y-coordinate is given in the first byte.

We take the square-root of the right side of the Elliptic Curve equation to get the y.

Determine evenness and return the correct point.

DER Signatures

Another class that we need to learn to serialize is Signature. Much like the SEC format, it needs to encode two different numbers, r and s. Unfortunately, unlike S256Point, Signature cannot be compressed as s cannot be derived solely from r.

The standard for serializing signatures (and lots of other things, for that matter) is called DER format. DER stands for Distinguished Encoding Rules and was used by Satoshi to serialize signatures. This was most likely because the standard was already defined in 2008, supported in the OpenSSL library (used in Bitcoin at the time) and was easy enough to adopt, rather than creating a new standard.

DER Signature format is defined like this:

1. Start with the 0x30 byte

2. Encode the length of the rest of the signature (usually 0x44 or 0x45) and append

3. Append the marker byte 0x02

4. Encode r as a Big-Endian integer, but prepend with 0x00 byte if r’s first byte >= 0x80. Prepend the resulting length to r. Add this to the result.

5. Append the marker byte 0x02

6. Encode s as a Big-Endian integer, but prepend with 0x00 byte if s’s first byte >= 0x80. Prepend the resulting length to s. Add this to the result.

The rules for #4 and #6 with the first byte starting with something greater than or equal to 0x80 is because DER is a general encoding and allows for negative numbers to be encoded. The first bit being 1 means that the number is negative. All numbers in an ECDSA signature are positive, so we have to prepend with 0x00 if the first bit is zero which is equivalent to first byte >= 0x80.

The DER format is in Figure 4-4:

Figure 4-4. DER Format

Because we know r is a 256-bit integer, r will be at most 32-bytes expressed as Big-Endian. It’s also possible the first byte could be >= 0x80, so part 4 can be at most 33-bytes. However, if r is a relatively small number, it could be less than 32 bytes. Same goes for s and part 6.

Here’s how this is coded in Python:

class Signature:
...
    def der(self):
        rbin = self.r.to_bytes(32, byteorder='big')
        # remove all null bytes at the beginning
        rbin = rbin.lstrip(b'\x00')
        # if rbin has a high bit, add a \x00
        if rbin[0] & 0x80:
            rbin = b'\x00' + rbin
        result = bytes([2, len(rbin)]) + rbin  
        sbin = self.s.to_bytes(32, byteorder='big')
        # remove all null bytes at the beginning
        sbin = sbin.lstrip(b'\x00')
        # if sbin has a high bit, add a \x00
        if sbin[0] & 0x80:
            sbin = b'\x00' + sbin
        result += bytes([2, len(sbin)]) + sbin
        return bytes([0x30, len(result)]) + result

In Python 3, you can convert a list of numbers to the byte equivalents using bytes([some_integer1, some_integer2])

Overall, this is an inefficient way to encode r and s as there are at least 4 bytes that aren’t strictly necessary.

Base58

In the early days of Bitcoin, Bitcoins were assigned to Public Keys specified in SEC format (uncompressed) and then were redeemed using DER signatures. For reasons we’ll get to in Chapter 6, using this particular very simple Script turned to be both wasteful for storing UTXOs and a little less secure than the Scripts in more prominent use now. For now, we’ll go through what addresses are and how they are encoded.

Transmitting your Public Key

In order for Alice to pay Bob, she has to know where to send the money. This is true not just in Bitcoin, but any method of payment. Since Bitcoin is a digital bearer instrument, the address can be something like a public key in a public key cryptography scheme. Unfortunately, SEC format, especially uncompressed is a bit long (65 or 33 bytes). Furthermore, the 65 or 33 bytes are in binary format, not something that’s easy to read, at least raw.

There are three major considerations. The first is that the public key be readable (easy to hand write and not too difficult to mistake say over the phone). The second is that it’s short (not be so long that it’s cumbersome). The third is that it’s secure (harder to make mistakes).

So how do we get readability, compression and security? If we express the SEC format in hexadecimal (4 bits per character), it’s double the length (130 or 66 characters). Can we do better?

We can use something like Base64 which can express 6 bits per character and becomes 87 characters for uncompressed SEC and 44 characters for compressed SEC. Unfortunately, Base64 is prone to mistakes as a lot of letters and numbers look similar (0 and O, l and I, - and _). If we remove these characters, we can have something that’s got good readability and decent compression (around 5.86 bits per character). Lastly, we can add a checksum at the end to ensure that mistakes are easy to detect.

This construction is called Base58. Instead of hexadecimal (base 16) or Base64, we’re encoding numbers in Base58.

The actual mechanics of doing the Base58 encoding are as follows.

All numbers, upper case letters and lower case letters are utilized except for the aforementioned 0/O and l/I. That leaves us with 10 + 26 + 26 - 4 = 58. Each of these characters represents a digit in base 58. We can encode with a function that does exactly this:

BASE58_ALPHABET = b'123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
...
def encode_base58(s):
    count = 0
    for c in s:  
        if c == 0:
            count += 1
        else:
            break
    prefix = b'1' * count
    num = int.from_bytes(s, 'big')
    result = bytearray()
    while num > 0:  
        num, mod = divmod(num, 58)
        result.insert(0, BASE58_ALPHABET[mod])
    return prefix + bytes(result)  

The purpose of this loop is to determine how many of the bytes at the front are 0 bytes. We want to add them back at the end.

This is the loop that figures out what Base58 digit to use.

Finally, we prepend all the zeros that we counted at the front because otherwise, they wouldn’t show up as prefixed 1’s. This annoyingly happens with pay-to-pubkey-hash (p2pkh). More on that in Chapter 6.

This function will take any bytes in Python 3 and convert it to Base58.

Address Format

The 264 bits from a compressed SEC format is still a bit too long, not to mention a bit less secure (see Chapter 6). To both shorten and increase security, we can use the ripemd160 hash to reduce the size to a 20-byte hash.

By not using the SEC format directly, we can go from 33 bytes to 20 bytes, shortening the address significantly. Here is how a Bitcoin address is created:

1. For mainnet addresses, start with the prefix 0x00, for testnet 0x6f.

2. Take the SEC format (compressed or uncompressed) and do a sha256 operation followed by the ripemd160 hash operation, the combination which is called a hash160 operation.

3. Combine the prefix from #1 and resulting hash from #2

4. Do a hash256 of the result from #3 and get the first 4 bytes.

5. Take the combination of #3 and #4 and encode in Base58.

Step 4 of this process is called the checksum. We can do steps 4 and 5 in one go this way:

def encode_base58_checksum(s):
    return encode_base58(s + hash256(s)[:4]).decode('ascii')  

Note that the .decode('ascii') part is necessary to convert from Python 3 bytes to a Python 3 string.

The process of doing a sha256 operation followed by a ripemd160 operation is called a hash160 operation in Bitcoin. We can implement this in helper.py.

def hash160(s):
    '''sha256 followed by ripemd160'''
    return hashlib.new('ripemd160', hashlib.sha256(s).digest()).digest()  

Note that hashlib.sha256(s).digest() does the sha256 and the wrapper around it does the ripemd160.

We can also update S256Point to with hash160 and address methods.

class S256Point:
...
    def hash160(self, compressed=True):
        return hash160(self.sec(compressed))

    def address(self, compressed=True, testnet=False):
        '''Returns the address string'''
        h160 = self.hash160(compressed)
        if testnet:
            prefix = b'\x6f'
        else:
            prefix = b'\x00'
        return encode_base58_checksum(prefix + h160)

WIF Format

The Private Key in our case is a 256-bit number. Generally, we are not going to need to serialize our secret that often as it doesn’t get broadcast (that would be a bad idea!). That said, there are instances where we may want to transfer your private key from one wallet to another, for example, from a paper wallet to a software wallet.

For this purpose, there is a format called WIF, which stands for Wallet Import Format. WIF is a serialization of the private key that’s meant to be human-readable. WIF uses the same Base58 encoding that addresses use.

Here is how the WIF format is created:

1. For mainnet private keys, start with the prefix 0x80, for testnet 0xef.

2. Encode the secret in 32-byte Big-Endian.

3. If the SEC format used for the public key address was compressed add a suffix of 0x01.

4. Combine the prefix from #1, serialized secret from #2 and suffix from #3

5. Do a hash256 of the result from #4 and get the first 4 bytes.

6. Take the combination of #4 and #5 and encode in Base58.

We can now create the wif method on the PrivateKey class.

class PrivateKey
...
    def wif(self, compressed=True, testnet=False):
        secret_bytes = self.secret.to_bytes(32, 'big')
        if testnet:
            prefix = b'\xef'
        else:
            prefix = b'\x80'
        if compressed:
            suffix = b'\x01'
        else:
            suffix = b''
        return encode_base58_checksum(prefix + secret_bytes + suffix)

Big and Little Endian Redux

It will be very useful to know how Big and Little Endian are done in Python as the next few chapters will be parsing and serializing numbers to and from Big/Little Endian quite a bit. In particular, Satoshi used a lot of Little-Endian for Bitcoin and unfortunately, there’s no easy-to-learn rule for where Little-Endian is used and where Big-Endian is used. Recall that SEC format uses Big-Endian encoding as do addresses and WIF. From Chapter 5 onward, we will use Little-Endian encoding a lot more. For this reason, we turn to the next two exercises. The last exercise of this section is to create a testnet address for yourself.

Conclusion

In this chapter we learned how to serialize a lot of different structures that we created in the previous chapters. We now turn to Transactions which we can parse and understand.

Transaction Components

At a high level, a Transaction really only has 4 components. They are:

1. Version

2. Inputs

3. Outputs

4. Locktime

A general overview of these fields might be helpful. Version indicates what additional features the transaction uses, Inputs define what Bitcoins are being spent, Outputs define where the Bitcoins are going and Locktime defines when this Transaction starts being valid. We’ll go through each component in depth.

Figure 5-1 shows a hexadecimal dump of a typical transaction that shows which parts are which.

Figure 5-1. Transaction Components, Version, Inputs, Output and Locktime

The differently highlighted parts represent Version, Inputs, Outputs and Locktime respectively.

With this in mind, we can start constructing the Transaction class, which we’ll call Tx:

class Tx:

    def __init__(self, version, tx_ins, tx_outs, locktime, testnet=False):
        self.version = version
        self.tx_ins = tx_ins  
        self.tx_outs = tx_outs
        self.locktime = locktime
        self.testnet = testnet  

    def __repr__(self):
        tx_ins = ''
        for tx_in in self.tx_ins:
            tx_ins += tx_in.__repr__() + '\n'
        tx_outs = ''
        for tx_out in self.tx_outs:
            tx_outs += tx_out.__repr__() + '\n'
        return 'tx: {}\nversion: {}\ntx_ins:\n{}tx_outs:\n{}locktime: {}'.format(
            self.id(),
            self.version,
            tx_ins,
            tx_outs,
            self.locktime,
        )

    def id(self):  
        '''Human-readable hexadecimal of the transaction hash'''
        return self.hash().hex()

    def hash(self):  
        '''Binary hash of the legacy serialization'''
        return hash256(self.serialize())[::-1]