Getting into blockchain development can be pretty intimidating. There’s a whole host of weird terms that are thrown around like “coinbase” and “merkle root” that not only look odd, but are not obvious. Add to that additional terms that look normal, but mean something specific to blockchain like “transaction”, “block” and “signature”.
In this series of articles, I aim to give you a gentle introduction into the world of blockchain development, or what I call “Blockchain 101". It sounds like a university course and it’s meant to be about at that level. You can read the posts here and get something out of them, but to get the full benefit, take time to do the exercises so you can really get an understanding of what’s going on.
In today’s article, we’re going to start on the foundational math. Our goal is to get you comfortable with finite fields and elliptical fields, which is a prerequisite to elliptical curve cryptography - the math behind blockchain.
Finite Fields
Finite fields are an important construct in mathematics and especially important in computer science. Think of them as a set of integers. When you take any two numbers from this set and add them, you get another number from the set. Same thing with subtraction, multiplication and division by anything other than 0. It may seem strange that you can divide two integers and come up with another integer, but that’s part of the magic, especially when you have a finite set.
So let’s start with a fairly simple field:
F19 = {0, 1, 2, … 18}
As you can see, there are exactly 19 elements in this field that consists of every number between 0 and 18, inclusive. For various mathematical reasons, it turns out fields that have a prime number of elements are the most interesting, which is why we chose 19 here. The field of order 19 is denoted F19. Fields of other orders are denoted with the number as the subscript.
Addition and Subtraction
We now have to define addition and subtraction so that adding any two elements or subtracting any two elements results in another element in this set. We can do this with modulo arithmetic using the order of the prime field (19).
F19
11 + 6 = 17 % 19 = 17
17 - 6 = 11 % 19 = 11
8 + 14 = 22 % 19 = 3
4 - 12 = -8 % 19 = 11
As you can see, no matter which two elements we select from F19 we will always end up with another element in F19.
Exercise
Solve these equations in F31:
2 + 15 = ?
29 - 4 = ?
17 + 21 = ?
15 - 30 = ?
Answers: 17, 25, 7, 16
Multiplication
We can also define multiplication on a finite field using modulo arithmetic:
F19
2 * 4 = 8 % 19 = 8
7 * 3 = 21 % 19 = 2
15 * 4 = 60 % 19 = 3
11 * 11 = 121 % 19 = 7
Again, we can multiply any two numbers from F19 and end up with another number in F19. Note we end up with some counter-intuitive results, like 7*3=2 and 11*11=7. Don’t worry too much about that, as finite field math can be a bit counter-intuitive, coming from the world of normal multiplication.
Exercise
1. Solve these equations in F31:
24 * 19 = ? 173 = ? 55 * 18 = ?
2. Write a program to calculate 1*k, 2*k, 3*k, … 30*k for some k in F31. Notice anything about these sets?
3. Write a program to calculate k30 for all k in F31. Notice anything?
Answers: 1. 22, 15, 16; 2. The sets are all equal to F31; 3. k30 is always 1.
One quick note before we leave multiplication. The answer to #2 above is why we choose prime fields. The numbers in a prime field are basically equivalent whereas in a composite field, the set 1*k, 2*k, 3*k…(n-1)*k wouldn’t necessarily be equivalent to the field itself.
Division
Division, in finite field mathematics, is simply defined as the inverse of multiplication.
F19
2 * 4 = 8 => 8 / 4 = 2
7 * 3 = 2 => 2 / 3 = 7
15 * 4 = 3 => 3 / 4 = 15
11 * 11 = 7 => 7 / 11 = 11
As with multiplication, we have some really counter-intuitive results like ⅔ = 7, ¾=15 and 7/11=11. Once again, finite fields are somewhat counter-intuitive so please don’t worry about the weirdness of the results, but just how to calculate them. The more salient question is, how do we do the actual calculation?
Problem 3 of the last exercise gives us a clue. Generalizing a bit, we have:
np-1=1 mod p where p is prime
This is a beautiful result from number theory known as Fermat’s Little Theorem. If you care to convince yourself this is true, there’s a very interesting proof using necklaces in the Wikipedia article.
In any case, this implies:
np-2=n-1=1/n mod p where p is prime
This can help us learn how to do field division.
F19
np-2 = n-1
2 / 3 = 2 * 3-1 = 2 * 317 = 7
3 / 15 = 3 * 15-1 = 3 * 1517 = 4
Notice that we end up with the same result as before for ⅔. Incidentally, if you’re using python, there’s a very convenient function called “pow” which does modulo exponentiation:
Python: n-1 = pow(n, p-2, p)
Exercise
1. Solve these equations in F31:
3 / 24 = ? 17-3 = ? 4-4 * 11 = ?
2. Write a program to calculate k/1, k/2, k/3, … k/30 for some k in F31. Notice anything about these sets?
Answers: 1. 4, 29, 13; 2. The sets are all equal to F31
Elliptical Curves
To introduce elliptical curves, we’re going to start by looking at various equations from high school algebra. Let’s take a look first at a linear equation: y=mx+b
A slightly more complicated equation is the quadratic equation: y=ax2+bx+c
And finally, you have the cubic equation which looks like this: y=ax3+bx2+cx+d
An elliptical curve, to be quite frank, isn’t that different. The equation looks like this: y2=x3+ax+b
Notice that it’s less steep than the cubic or quadratic curves. Notice also that it’s a mirrored over the x-axis. This is because the left side of the equation is y2, making it so that if y is a solution -y is also a solution.
Bitcoin uses what’s called the secp256k1 curve, and that equation is simply y2=x3+7 and looks like this:
Now elliptical curves have an interesting property that we can define as point addition.
Point addition stems from the fact that a line defined by two points on this curve will intersect the curve a third time. Essentially, the operation is as described in the diagram above. To add P and Q, you find the third intersection point, then you reflect over the x-axis.
Here’s a solid example. Suppose the curve and points that we want to look at are these:
Curve: y2=x3+5x+7
P1=(2,5) P2=(3,7)
We can clearly see that P1 and P2 are on the curve:
52=25=23+5*2+7
72=49=33+5*3+7
We can calculate the line that P1 and P2 makes my calculating the slope and y-intercept:
y=mx+b => m=(y2-y1)/(x2-x1)=2
5=2*2+b => b=1 =>
y = 2x + 1
We can now plug in the resulting line into the elliptical curve equation to solve for x:
(2x+1)2 = x3+5x+7 => x3-4x2+x+6 = 0
(x,y) = (-1,-1), (2,5), (3,7)
We know (2,5) and (3,7) are P1 and P2, which means that (-1, -1) is the third point. We now flip that point over the x-axis to get the result:
P1 + P2 = (-1, 1)
Group Law
This process of figuring out the third point is a bit easier to codify this way:
Curve:y2=x3+ax+b
P1=(x1,y1) P2=(x2,y2) P1+P2=(x3,y3)
When x1≠x2:
s=(y2-y1)/(x2-x1)
x3=s2-x1-x2
y3=s(x1-x3)-y1
It turns out that this process gives us something called a group. A group in mathematics is a set of numbers and a single operation that’s closed, associative, commutative, invertible and has an identity. When we use point addition on all the points of an elliptical curve, we get a group. Note that for a line that’s perfectly vertical, there’s another point called the “point at infinity”, which also serves as the identity for the group. Commutativity should be fairly obvious as two points make a line and it doesn’t matter which order you choose them. Associativity can be seen here:
Exercise
For the curve y2 = x3 + 5x + 7, and the following points:
P1=(3,7), P2=(18,77)
Calculate (using the group laws):
P1+P2=?
Verify this point is on the curve.
Answer: P1+P2=(7/9, 91/27)≈(0.7778, 3.3703)
Conclusion
We’ve covered Finite Fields and Elliptical Curves. They may seem unrelated, but next time, we’ll combine them to produce a very powerful cryptographic tool called Elliptical Curve Cryptography.
Interested in working with these technologies (and more)? Join us!
