Programming Blockchain Part 1:
Understanding Public Key Cryptography
I recently had the pleasure of attending Jimmy Song’s Programming Blockchain seminar in Austin, TX. Jimmy is a Bitcoin Core Contributor who has dedicated a large portion of his time teaching blockchain to engineers. As the space continues to gain momentum, engineers who have taken Jimmy’s course will be well-equipped to build tomorrow’s blockchain projects.
Jimmy’s curriculum is incredibly thorough. He starts with the magic of elliptic curve cryptography, guides you through creating your own transactions, introduces you to Script processing, and much more. Over the course of the seminar, students learn these topics while building their own Bitcoin library in Python.
After completing the course, I felt overwhelmed by all of this content, but I’m excited to share some of the things I’ve learned!
Operating Over Prime Fields
The first thing we’ll learn about are prime fields. Prime fields are a subset of finite fields — finite sets of numbers which are closed under addition, subtraction, multiplication, and division — such that the number of elements in the set is a prime number. Operating over prime fields is fairly straightforward using the modulo operator (%). For example, addition over the prime field F19 {0, 1, 2… 18} would solve as follows.
8 + 14 : F19 => (8 + 14) % 19 = 3
Similarly, for multiplication and exponentiation in the same prime field F19,
7 * 3 : F19 => (7 * 3) % 19 = 2
and
11³ : F19 => (11 * 11 * 11) % 19 = 1
Division is not as straightforward and needs something called Fermat’s Little Theorem to solve. Given integer n and prime number p,
n^(p-1) = 1
With this theorem, we can then deduce the following.
1/n = n^-1 = n^-1 * n^(p-1) = n^(p-2)
Thus, we can turn division over prime fields into a multiplication problem. For example, division over the prime field F19 would solve as follows.
2/3 = 2 * 1/3 = 2 * 3^(19–2) = 2 * 3¹⁷ = 7
Elliptic Curves
Hold onto what we just learned about operating over prime fields. It’ll come back once we understand elliptic curves.
Elliptic curves are defined by the following equation.
y² = x³ + ax + b
Bitcoin uses a particular elliptic curve known as Secp256k1.
y² = x³ + 7
Point Addition
Elliptic curves are useful because of this concept known as point addition. On an elliptic curve, take a line which intersects twice at point P and point Q. It must then intersect a third time at point R. With point addition, we know that the sum of P and Q is the mirror of R.
Group Law for Point at Infinity
Point addition for elliptic curves has a property very similar to the identity property of addition. If we treat the point (infinity, infinity) as 0, we can create a mathematical group.
(x1, y1) = (x1, y1) + (infinity, infinity)
(x1,y1) + (x1, -y1) = (infinity, infinity)
Putting It All Together
Let’s now combine what we’ve learned about operations over prime fields with elliptic curves and point addition.
If we take the Secp256k1 curve and the prime field F137, we can verify that the point (73, 128) is indeed on the curve by plugging it into the formula y² = x³ + 7 and using operations over prime fields. We can also use these operations to attempt point addition.
(73, 128) + (73, 128) = (103, 76)
Generating Groups
Some interesting things happen here. Let’s define (73, 128) as generator point G. We already showed that G + G = (103, 76). If we continue to add G, we will eventually reach the point at infinity. In other words,
n * G = (infinity, infinity)
We can call the sums of G (G, G + G, G + G + G, etc…) a finite group and n the order of the group.
Discrete Log Problem
Imagine now a group where the order is huge, say 2²⁵⁶. Given an elliptic curve over a prime field and a random point G, for some scalar s where s is now the order of the group, we can find point P with the equation
P = s * G
Seems simple, but this little equation uncovers a phenomenon known as the Discrete Log Problem. It turns out that given point G and scalar s, it’s very easy to calculate point P. However, given point G and point P, it’s nearly impossible to find scalar s.
To prove this, let’s look at an example. Given G = 3 and P = 13, let’s solve for s. This gives us the equation 3^s = 13 over the prime field F17. One possible solution is s = 4; however, another solution is s = 20. In fact, any form of s = 4 + 16n is a valid solution.
Public Key Cryptography
This is the foundation of Public Key Cryptography where s is your private key and P is your public key, represented by a point (x, y). This is the special sauce behind all of Bitcoin! We can share our public keys as much as we want, but as long as your private key remains a secret, security is kept intact.
Now What?
That was a lot of math! To get into blockchain programming, you don’t have to be a math whiz. (It just helps us understand what’s going on behind the scenes.) In Part 2, I’ll cover more hands-on topics such as addresses, transactions, and Script processing. Stay tuned!
