Chain engineer Erik Rykwalder wrote an educational blog post yesterday, The Math Behind Bitcoin . Specifically, Erik concisely explains some of the fundamentals of Elliptic Curve Digital Signature Algorithm (ECDSA). When the term “key”, “key pair” or “private/public key” is used in Bitcoin it means an ECDSA key pair. These keys are mathematically linked and can be used to encrypt and decrypt data.
Bitcoin needs a bit more than just ECDSA key pairs to transfer ownership of bitcoins, however. Core developer Gregory Maxwell dropped by the Reddit post to explain some of those subtleties. As nullc mentions, Erik does a great job explaining ECDSA, but let’s take a look at how it fits into Bitcoin.
Algorithms: THE Math Behind Bitcoin
An algorithm is a process or a procedure for making calculations. They’re not always intimidating scribblings mapped across multiple chalkboards in college classrooms. y = mx + b is the line drawing algorithm from algebra. It’s not very intimidating at all.
Algorithms are like machines. Data goes in, and the algorithm does some work, and data comes out. ECDSA is all of the “y = mx + b” mathematics that goes into creating Bitcoin key pairs.
RelatedNews
As Erik explains,
[ECDSA]… a process that uses an elliptic curve and a finite field to “sign” data
He does a great job of defining the math. In practical terms, we’re drawing a big squiggly line on a graph within certain limits.
The line is an elliptic curve:
Also practically, the finite field is a graph or cartesian plane. The thing our math teachers made us draw the y = mx + b lines on. Finite fields are modular. Points that fall outside the size of the graph wrap around until they do.
To create a new key pair the elliptic curve is plotted across the finite field. A line is drawn across the curve such that it intersects three points on the curve. Bitcoin defines the formula for the curve and the parameters of the field so that every user has the same graph. The parameters used in Bitcoin’s elliptic curve, and finite field are defined as secp256k1.
A private key is any number between 1 and
1852673427797059126777135760139006525645401028465198470121682610264290583909392
or
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
or
1111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111110101110101010111011
0111001110011010101111010010001010000000111011101111111101001001011110100
01100110100000011011001000001010000010000
Between 1 and 2^256. The spot where the line originates on the graph is the base point. Multiply the base point by the private key and you have a public key. The base point does not change, one public key maps to one private key.
This part is important. Bitcoin has an enormous field.
There are 10^82 atoms in the universe. If you made the entire Universe our finite field and you drew a giant elliptic curve through it, each “point” in the universe would about 300 square atoms. At that size, each cell in your body takes up the space of 1,150,000,000 Bitcoin key pairs.
Also read: “Bill Gates: “Bitcoin Technology is Key”
10^82 / 2^256 = 86362
sqrt(86362) ~ 300
10^14 / 86362 = 1.15 * 10^9
That’s alotta keys
Trying to brute force every private key would be like mapping out every 300 square atom block in the universe. Yeah, that’s a silly thing to do.
There’s more! There’s something called Landauer’s principle that talks about the theoretical smallest amount of energy required to store a bit of data. There’s a lot more of math involved, and I’m pretty sure the laws of thermodynamics come into play.
In short, here is an ancient chart:
Let’s just say the heat death of the universe is in 10^120 years. A 25 GPU password cracker does about 350,000,000,000 hashes a second. It’s not the same algorithm, but let’s pretend we have oclVanityGen commanding those 25 GPUs and for fantasy sake say it goes just as fast.
1852673427797059126777135760139006525645401028465198470121682610264290583909392 / 350,000,000 =
5293352650848740362220387886111447216129717224100000000000000000000000 years
or
5 * 10^69 years
(And about 4000 years to calculate 1 human worth of private keys)
There’s a possibility of seeing a completely random Big Bang happening in 10^59 years. By that time humans will have transcended physical form and money will be indistinguishable from the tools of cavemen – if it is remembered at all.
Addresses
A Bitcoin Address looks like this: 181TK6dMSy88SvjN1mmoDkjB9TmvXRqCCv
The address is not a public key. An Address is an RIPEMD-160 hash of an SHA256 hash of a public key. SHA256 and RIPEMD-160 are also algorithms. Unlike ECDSA, which is used to generate key pairs, RIPEMD-160 generates a hash. Think of an algorithm like a machine. You put in “stuff” and, hopefully, new “stuff” comes out.
A simple example of a hash
Every letter has a value of its position in the alphabet. A = 1; B = 2, etc.
Our hash algorithm is this:
for i=0 to len(word):
h = h + (i + letter_value)
So for the word “ABC” using our hash would be:
Loop for ‘A’
h = 0 + (0 + 1)
Loop ‘B’
h = 1 + (1 + 2)
‘C’
h = 4 + (2 + 3)
h = 9
‘ABC’ hashes to 9. Of course, RIPEMD is much more sophisticated.
RIPEMD uses your public key to create a hash. A bitcoin address is smaller than a public key. That introduces another term, collisions. When two unique inputs give the same output in a hash algorithm, it’s called a collision. In the above example, the word ‘C’ has the same output as ‘AA’. Using an enormous numbers, and a strong algorithm reduces collisions. But for Bitcoin it’s because we’re turning large numbers in to smaller numbers.
For Bitcoin, there are so many possible keys that collisions are astronomically unlikely. Furthermore, since there are only 21M bitcoins only a very miniscule fraction of keys can even claim a balance. So even if someone were to generate a key pair that collides with another – an astronomical feat – the other key likely wouldn’t have a balance.
How It Actually Works
Your private key is kept secret. This is the key that unlocks funds owed to you in the Bitcoin block chain.
Bitcoin has a scripting system that is used to define the parameters necessary to spend bitcoins. When you build a transaction in addition to referencing previous transactions you’ve received, it contains a script with your private key’s signature and the matching public key. This is used to prove the provided public key matches the private key used to make the signature.
Also read: Bitcoin Price Up: Breaks $400
If that public key hashes (RIPEMD160) to the Bitcoin Address in a previously unclaimed transaction, it can be spent. That’s a high-level view of some of the ways Bitcoin uses cryptography.
Everyone interested in Bitcoin should stop over at the Chain blog and read Erik’s post. Even if the underlying math isn’t what attracts you to Bitcoin read it for fun. His explanation is a great lesson in how to explain an esoteric concept.
What do you think? Comment below!
Images from Wikimedia Commons and Shutterstock.
