Digital Signatures and Bitcoin
Bitcoin works on a trustless system where each and every transaction needs to be verified. All information on each Bitcoin transfer is cross-checked and confirmed. The blockchain knows how much each wallet has at all times. For all intents and purposes, you are allowed to spend the Bitcoin in a wallet when you know the password [private key] to that wallet.
But if all information is public, how do you prove you own the Bitcoin without revealing your password? How could you prove you have the password without showing the password?
You don’t have to, digital signatures found a way to fix the issue.
Digital signatures, Elliptic Curve Digital Signature Algorithms [ECDSA] for Bitcoin, allow for public verification of ownership while keeping your password private. ECDSA creates a public-private key pair where the private key is the password to the account and the public key is used for verification. Knowing the public key does not reveal the private key, but how?
Trap Door Functions – The Magic in ECDSA
A trap door function is easy to calculate and impossible to reverse. ECDSA creates a trapdoor function by using elliptic math. Elliptic math only has ‘point addition’ and ‘point multiplication’, and public keys are created by point multiplying the private key.
There is no such thing as ‘point subtraction’ or ‘point division’. Therefore, ECDSA functions are innately one-way, or have a trap door built in. Point multiplication is possible and point division, the reverse, is impossible. Point multiplying the private key to get a public key is easy, you can’t point divide the public key to get the private key.
Though it seems strange, this works because ‘point addition’ and ‘point multiplication’ are not true ‘addition’ or ‘multiplication’. Instead, they relate to how lines pass through elliptic curves.
How do you Point Add and Multiply?
Elliptic curves have a property where any line that intersects them in 2 points will always intersect a 3rd point. This allows for two points to be ‘added’ by finding the 3rd point along the line the first two points define. Point multiplication happens when a line is tangent to the elliptic curve. Let’s get into it with some examples:
Background on Elliptic Curves
Elliptic curves have a general form of:
y2= x3+ ax+b
and this is what they can look like:
Bitcoin uses an elliptic curve with a = 0 & b = 7 and looks a little like this:
Back to the Math - Point Addition
Point addition in ECDSA is defined as:
P + Q + R = 0
To add, pick 2 points on the curve (let’s say P and Q) and find the line they define:
The 3rd point the line crosses is R:
However, this just gets us P + Q + R = 0. We want P + Q = ‘something’ (which is P + Q = -R). The ‘negative’ of a point is the mirror of the point, and elliptic curves just happen to be symmetric about the x-axis:
As such, point addition is the process of finding the line that your two points define, and then finding the mirror of the 3rd point intersected by the line. Not completely different than simple addition =)
Point Multiplication - AKA Point Doubling
Point multiplication is a special case of point addition. If a line is tangent to the curve, then it will only intersect in 2 locations. This as the same characteristic as if P = Q, or 2P = -R. This is also known as ‘point doubling’:
Generating Public-Private Keys
In ECDSA, a private key is simply a random number. The public key is found by multiplying the ‘base point’ by the private key. The base point is defined by whichever kind of ECDSA you are using (Bitcoin uses secp256k1 [Section 2.4.1]).
To see how this works, let’s take a look at an example. Let’s use 9 as a private key:
Public = Private * Base → R = 9P
Again, as there is no point division, this is a one-way function. It is relatively easy to get the public key, but impossible to calculate the private key from the public key.
However, in elliptic math, we cannot straight up multiply a point by 9. We need to break down 9 into a series of point doublings and point additions:
9P = P + 8P = P + 2(4P) = P + 2(2(2P)))
To multiply by 9 is really to do 3 sets of point doubling and a point addition.
This calculator lets you just multiply and does all of this in the background. However, this is what it is doing in the background: (choosing a random base point ‘P’):
As you can see, the point we are calculating tends to bounce around the curve a lot. This makes Public-Private key pair generation similar to billiards.
Consider a billiards table with just a single ball. We both see where it starts (the base point), and then I hit it around in secret for a bit. We can both see the ending location (public key), but only I know how many times I hit it to get there (private key). Just because you know where the ball started and stopped doesn’t mean you know how many times I hit it.
The only way to crack the public-private key is through brute force, or ‘guess and check’. This means working through each possible private key and finding its public key. This could be done, but the number of possible private keys in Bitcoin is insane. The number is easily written as 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 which is roughly equal to 12 followed by 76 zeroes. Interestingly enough, this number is close to the number of atoms in the universe.
Ok, one last math point before working through an example.
A Short Look at Finite Fields
Computers like to work with whole numbers, and doing point addition and multiplication leads to not whole numbers rather quickly. To solve this, ECDSA puts elliptic curves onto finite fields. This basically transforms the curve into a series of points that are made of whole numbers. The mechanics of point addition and multiplication stay the same. One obvious difference in finite fields is that lines behave like those video game where you go out the to and show up at the bottom.
The other thing to be aware of is that finite fields use something called ‘modular math’. This is basically that same thing as time addition. 6 o’clock + 13 hours = 7 o’clock is the same as 6 + 13 mod 12 = 7. Further 6 + 5 mod 12 = 11, 6 + 6 mod 12 = 0, and 2 + 27 mod 12 = 5.
Finite fields are used so that computers can work ECDSA in whole numbers, and modular math is used so that counters in computer don’t overflow (partly because the numbers in real ECDSA are so massive).
The Process of Signing Data
The basic process of singing data goes like this:
- Choose a private key
- Create a public key
- Create the data you want to sign
- ‘Sign’ the data by combining the data with your private key to find a point on an elliptic curve
Signature verification then compares your data and signature to your public key with a clever math trick. If they match, then consider yourself verified!
Actual Bitcoin ECDSA parameters are large (like size of the universe large), so we will use some smaller numbers:
- a = 0 & b = 7 – the defining characteristic of the elliptic curve (These are actually the same as Bitcoin’s).
- P = 97 – The Prime Modulus. This goes into deciding how many points are on the finite field
- N = 79 – the number of points on the finite field
- Base point = (5,36) – The starting location for most of the math.
For reference, the finite field for all of these calculations looks like this (with base point P):
Finding the Public Key
Let’s use 9 as our private key since it worked well last time. The public key is found by multiplying the base point by the private key:
Public = 9 * Base →
Public = Base + 2(2(2 * Base)))
This is what the 3 point doublings and the single addition look like on a finite field:
So, doing the math:
Public = (5,36) + 2(2(2 * (5,36)))) →
Public = (5,36) + 2(2 * (96,43)) →
Public = (5,36) + 2 * (63,45) →
Public = (5,36) + (56,76) →
Public = (1,28)
Our public key is the point (1,28) or ‘128’ for short. Now that we have our public-private key pair, we can sign our data.
Let the Signatures Begin!
Normally, you sign the hash of your data. As Bitcoin’s hashes are large numbers (see SHA-256), we’re just going to sign the number 2 instead.
Like the public key, the signed data is represented by another point, (r,s). The first step in signing data, believe it or not, is to pick a random number. This number, k, will only be used for this signature and should not be repeated (Sony repeated their k value and they got hacked big time). Bitcoin’s software handles the generation of k for you, so no need to really worry about it.
Side note: the combination of k, a complete unknown, and the billiard’s effect of elliptic point addition is the strength of ECDSA.
Lets use k = 4. 4 is a good solid random number.
k is treated just like a private key and a point is found by multiplying the base point by k:
(x,y) = k * Base →
(x,y) = 4 * (5,36) →
(x,y) = (63,45)
Now, using (x,y), n, k, our data, and the private key we can find (r,s), the signature.
r is easy:
r = x mod n →
r = 63 mod 79 →
s requires a bit more math:
s = k-1 * (data + r * Private) mod n →
s = 4-1 * (2 + 63 * 9) mod 79 →
Inverses are a little weird in modular math. A number’s inverse needs to follow this:
Number’s Inverse * Number mod n = 1
So the inverse of 4 would be 20, as 4 * 20 = 80 and 80 mod 79 = 1. Here’s a calculator that does it all for you =)
s = 20 * (569) mod 79 →
s = 11380 mod 79 →
s = 4
(If either r or s were to equal 0, then we’d need to pick another k)
The signature for our data, 2, is (63,4). Cool. Now you send it to someone and they want to verify that it came from you. How does that work?
Signature Verification Without the Private Key
To verify that the signature, a new point is calculated (x2 , y2) using the Base Point, your Public Key, the Data, and the Signature. The signature is confirmed if r is equal to x2. But why exactly does this work?
Because x2 and r are the same if the public key used to find x2 belongs to the private key used to find r. Here’s how:
This is the equation used to find (x2 , y2):
(x2 , y2) = u1 * Base + u2 * Public
u1 and u2 are found with these:
u1 = data * s-1 mod n
u1 = r * s-1 mod n
We know that the public key is just the base point times the private key…
(x2 , y2) = u1 * Base + u2 * (Private * Base)
and we can expand u1 and u2….
(x2 , y2) = (data * s-1) * Base + (r * s-1) * Private * Base mod n
collecting like terms….
(x2 , y2) = (data + r * Private) * s-1 * Base mod n
and replacing s with its definition above.
(x2 , y2) = (data + r * Private) * (k-1)-1 * (data + r * Private)-1 * Base mod n
The inverses cancel out and we are left this:
(x2 , y2) = k * Base mod n
Which is the same equation used to find r in the first place:
(x,y) = k * Base mod n → r = x
Which is a pretty neat and a clever trick.
Proceeding with calculating the example:
u1 = data * s-1 mod n →
u1 = 2 * 4-1 mod 79 →
u1 = 40
u2 = r * s-1 mod n →
u2 = 63 * 4-1 mod 79 →
u2 = 75
(x2 , y2) = u1 * Base + u2 * Public →
(x2 , y2) = 40 * (5,36) + 75 * (1,28) →
(x2 , y2) = (82,30) + (67,78) →
(x2 , y2) = (63,45)
x2 = 63, and r = 63. Consider our signature verified.
Signing Off on ECDSA
That is the basic idea behind ECDSA, and digital signatures in general. You create a private-public key pair (through a trap door function), and then ‘sign’ your data using the private key and another unknown random number. As the public and private keys are tied together, anyone and everyone can verify the signature without you exposing your private key.
In this the blockchain can remain trustless yet ownership can be retained.
Who knew math could be so cool? If you want to play around with Bitcoin’s ECDSA, check here!