Getting into blockchain development can be intimidating. There’s a whole host of unusual terms that are thrown around, like “zero knowledge” and “merkle tree,” which not only look odd but are also not obvious. There are also additional terms that seem normal but have specific meanings in blockchain, like ‘transaction’, ‘block’ and ‘signature.’
There are many ‘blockchain 101’ tutorials out there, but they all focus on ‘what is a blockchain’ and the high-level descriptions of common terms. This series specifically focuses on the more technical underpinnings of blockchain networks, including elliptic curves and cryptography. To fully benefit from this series, we recommend taking the time to complete the exercises to get a deeper understanding of the concepts.
In today’s article, we’ll start with the foundational math. Our goal is to make you comfortable with finite and elliptical fields, prerequisites for understanding elliptical curve cryptography — the math behind blockchain.
Finite fields
Finite fields are an important concept in mathematics and are particularly crucial in computer science. Think of them as a set of integers. When you add any two numbers from this set, you get another number from the set. The same thing applies to subtraction, multiplication and division by any number other than 0. It may seem unusual that dividing two integers can result in another integer, but that’s part of the magic of finite fields, especially when the set is finite.
So let’s start with a fairly simple field:
𝔽19 = {0, 1, 2, … 18}
As you can see, this field contains exactly 19 integers that consist of every number between 0 and 18 inclusively. For various mathematical reasons, fields with a prime number of elements are the most interesting, which is why we chose 19 for this example. The field of order 19 is denoted 𝔽19. Fields of other orders are similarly denoted, with the order number as the subscript.
Addition and subtraction
We now have to define addition and subtraction in such a way that adding any two elements or subtracting any two elements results in another element within this set. We can do this with modulo arithmetic, using the order of the prime field (19).
𝔽19
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 𝔽19, we will always end up with another element in 𝔽19.
Exercise 1
Solve these equations in 𝔽31:
2 + 15 = ?
29 – 4 = ?
17 + 21 = ?
15 – 30 = ?
Answers (highlight to reveal): 17, 25 (aka 6), 7, 16
Multiplication
We can also define multiplication on a finite field using modulo arithmetic:
𝔽19
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 𝔽19 and still end up with another number in 𝔽19. It’s important to note that we end up with some counterintuitive results, like 7*3=2 and 11*11=7. Don’t worry too much about this as finite field math can be a bit counterintuitive compared to standard multiplication.
Exercise 2
- Solve these equations in 𝔽31:
24 * 19 = ?
17 * 3 = ?
55* 18 = ?
- Write a program to calculate 1*k, 2*k, 3*k, … 30*k for some k in 𝔽31. Notice anything about these sets?
- Write a program to calculate k30 for all k in 𝔽31. Notice anything?
Answers: (1. 13, 18, 29; 2. The sets are all equal to 𝔽31; 3. k30 is always 1 (except when the base is zero).
One quick note before we conclude our discussion on multiplication. The answer to question #2 in Exercise 2 above is why we choose prime fields. In a prime field, the numbers are essentially equivalent. However, in a composite field, the set 1*k, 2*k, 3*k…(n-1)*k may not necessarily be equivalent to the field itself.
Division
Division, in finite field mathematics, is simply defined as the inverse of multiplication.
𝔽19
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 counterintuitive results like ⅔ = 7, ¾=15 and 7/11=11. Once again, finite fields are somewhat counterintuitive 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:
n^p-1=1 mod p where p is prime
This is a beautiful outcome from number theory, known as Fermat’s Little Theorem. If you’re interested in convincing yourself this is true, there’s very interesting proof using necklaces in the Wikipedia article. In any case, this implies:
n^p-2=n^-1=1/n mod p where p is prime
This can help us learn how to do field division.
𝔽19
n^p-2= n^-1
2 / 3 = 2 * 3^–1= 2 * 3^17= 7
3 / 15 = 3 * 15^–1= 3 * 15^17= 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 3
- Solve these equations in 𝔽31:
3 / 24 = ? 17–3= ? 4–4* 11 = ?
- Write a program to calculate k/1, k/2, k/3, … k/30 for some k in 𝔽31. Notice anything about these sets?
Answers: 1. 4, 29, 13; 2. The sets are all equal to 𝔽31
Elliptical curves
To introduce elliptical curves, we’ll begin by looking at various equations from high school algebra. First, let’s take a look at a linear equation: y = mx + b
Figure 1.0
A slightly more complicated equation is the quadratic equation: y = ax2 + bx + c
Figure 1.1
And finally, the cubic equation looks like this: y = ax3 + bx2 + cx + d
Figure 1.2
An elliptical curve, to be quite frank, isn’t that different. The equation looks like this: y2=x3+ax+b
Figure 1.3
Figure 1.4
Notice that it’s less steep than the cubic or quadratic curves. Also, see that it’s mirrored over the x-axis. This mirroring occurs because the left side of the equation is y2, meaning that if y is a solution, -y is also a solution.
Bitcoin uses what’s known as the secp256k1 curve, whose equation is simply y2 = x3 + 7, and it looks like this:
Figure 2.0
Now, elliptical curves have an interesting property that we can define as point addition.
Figure 2.1
Point addition is based on the fact that a line defined by two points on the curve will intersect the curve a third time. Essentially, the operation is as shown in the diagram above. To add points P and Q, you find the third intersection point and then reflect over the x-axis.
Here’s an 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 by 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 the resulting line into the elliptical curve equation to solve for x:
(2x + 1)2 = x3+ 5x + 7 => x3– 4×2 + 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 known as a ‘group.’ In mathematics, a group 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 acts as the identity for the group. Commutativity is fairly straightforward, as two points form a line, and the order in which you choose them doesn’t matter.
Associativity can be seen below:
Figure 3.0
Figure 3.1
Exercise 4
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.
Answers: P1+P2=(7/9, 91/27)≈(0.7778, 3.3703)
Conclusion
Congrats! You’ve now learned the basics of finite fields and elliptical curves. While they may appear unrelated at first, we’ll combine these concepts to produce a very powerful cryptographic tool called Elliptical Curve Cryptography in our next discussion.
Considering a career in blockchain? Explore our open engineering roles.