Bitcoin’s signing algorithm: Intro to Finite Fields

Notes and analysis from Programming Bitcoin by Jimmy Song

This is my first post in a continuing series for people interested in Bitcoin at a software-design level such as a software engineer, mathematician or network security professional. The post will cover the material in chapter 1.

As an aspiring contributor to the Bitcoin open source project I have read many books and articles previously, including the terrific Mastering Bitcoin by Andreas Antonopoulos. Despite this I still don’t know my way around the code base at all and the math behind the crypto is not at all clear to me. I realized I needed either a scaled down blockchain coding project and/or a book with exercises and problem sets that could guide me through the concepts like a textbook.

I discovered Programming Bitcoin from watching Jimmy Song’s podcasts. He is a core contributor and tech evangelist for Bitcoin. I have never spoken to Jimmy and he is not aware that I am recommending his book, although I did talk to a scammer pretending to be him on Twitter. The book is available for free on GitHub, similar to Mastering Bitcoin, but I like to write in the book while I read to take notes, so I bought it on Amazon for ~$45.

I’ve picked Programming Bitcoin by Jimmy Song, and my first impression was very positive. The book has actual exercises and structured coding assignments plus full color diagrams! Then I noticed that by the last chapter your project can interact with the actual bitcoin network. Exciting!

The first three chapters cover the signing algorithm, ECDSA, used to show that the creator of a transaction is the same person that owns the coins being spent. It is a key feature of the bitcoin system.

Chapter 1 — Finite Fields

Finite fields are a system of rules overlaid onto a fixed set of numbers so that they can be treated like a full fledged number system. This will give us flexibility to do math over large numbers without fear of exploding beyond the bounds of our numeric variable types.

You may recall from school some other number systems like The Natural Numbers, which start with 1 and increase by whole numbers up to infinity (1,2,3…). These numbers are closed under addition because the sum of any two natural numbers is another natural number, but natural numbers have no additive inverse because they don’t have negative numbers. For this we need the Integers, these are natural numbers plus zero and the negatives (..,-1,0,1,..). Integers are also closed under addition but the inclusion of zero (also called the additive identity) forces the existence of negative numbers. I.e If the sum of a and b is zero than b must be the additive inverse, the integer that annihilates a.

To do addition over a finite number system we need addition to wrap around our numeric range like clock arithmetic, i.e. 1 hour past midnight is 1 o’clock not 13 o’clock. This is done using the modulus operator (%). Modulus takes two parameters, a % b, and outputs a value within the range [0,b). For our finite field we will use the same value for b always, so we know how many numbers are in our field, this is called the field’s order. Subtraction works similarly to addition but accepts negative values, exactly like negatives in clock arithmetic: 3 hours before 1 o’clock = 1–3 % 12 = 10 o’clock.

Multiplication over the finite field is defined as repeated application of addition. For example a * 3 is the same as a + a + a. Since we know addition is closed, multiplication is also closed.

Fields also have a multiplicative identity, 1, which allows us to define multiplicative inverses, a * b = 1 implies a = 1 / b. To see if this operation is closed let’s look at what happens when we multiply all the elements by 2 for a few different sized finite fields:

2 * (1, 2) % 2 = (1+1, 2+2) % 2 = (0, 0) % 2

2 * (1, 2, 3) % 3 = (1+1, 2+2, 3+3) % 3 = (2, 1, 0) % 3

2 * (1, 2, 3, 4) % 4 = (1+1, …, 4+4) % 4 = (2, 0, 2, 0) % 4

2 * (1, 2, 3, 4, 5) % 5 = (1+1, …, 5+5) % 5 = (2, 4, 1, 3, 0) % 5

2 * (1, 2, 3, 4, 5, 6) % 6 = (1+1, …, 6+6) % 6 = (2, 4, 0, 2, 4, 0) % 6

Notice that for sizes 2, 4 and 6 the resulting sets are missing some elements, like 1. When the result is one it means the products are inverses. Here you can see that 2 / 3 = 1 in mod 5 and 2 / 2 = 1 in mod 3 but in mod 2, mod 4 and mod 6 there is no such inverse, and consequently division is not closed for those sets.

The reason those sets are missing elements is because the size (or order) of the set and the multiplier have a common factor, 2. If instead the size is a prime number, it has no factors in common with any multiplier ensuring that it’s closed under division.

Provided that our set has a prime order how do you find the inverse without searching all of the possibilities? The answer is 1/a = a^(p-2) % p.

To see why we need to use Fermat’s Little Theorem: 1 = n^(p-1) % p. Divide both sides by n and simplify:

For example for prime 97 we can find the inverse of 17 by taking it to the 95th power: 1⁷⁹⁵ = 40, therefore 17 * 40 = 1.

Now we have shown closure for both addition and multiplication and their inverses, this completes the specification of our finite field.

In the next part we will cover chapter 2, which introduces the elliptic curve group and its operations.