So, you want to guess a valid Bitcoin private key?
If you’re thinking that trying to guess a valid Bitcoin private key is a great way to spend the time on a slow Sunday afternoon, this article might blow your mind.
Versione italiana dell’articolo qui.
What is a private key?
A private key is simply a 256-bit integer. For convenience, it is often represented in hexadecimal format, which is a sequence of 64 characters, consisting of the digits from 0 to 9 and the characters from ‘a’ to ‘f’. For example, the sequence:
66d891b6fddc51e50d1ef6a00be4e2ca934b96df5ca0883f7cc0ce4fd6921e31
is a Bitcoin private key in hexadecimal format. This private key (generated randomly) is all you need to spend your bitcoins.
The delicacy of the private key
As you can imagine, the problem of generating a valid private key is of considerable importance from a security standpoint: anyone who possesses a valid private key can dispose of the funds (Unspent Transaction Outputs or UTXOs) that it controls at their own discretion. This also applies to a malicious actor who is able to intercept or guess a private key that should control a non-zero balance, as it would immediately become spendable under the helpless eyes of the legitimate owner.
Intercepting and guessing a private key are two sides of the same risk: while in the first case good practices for safe custody of private keys come to the rescue, which we will not discuss here, since I have discussed them in depth in my book Bitcoin e Criptovalute on the road (in italian), in the second case all the beauty and elegance of mathematics comes to our aid, as we are about to discover.
Mathematics to the rescue
The probability of guessing a valid Bitcoin private key is 1 in 2²⁵⁶. Said like that, it might seem like a relatively simple task. But you might be very surprised to learn how futile such an attempt would be.
To give you a visual representation of how tiny that probability is, let’s start with an everyday object that we are all very familiar with: a simple deck of 52 playing cards. Suppose you want to shuffle a deck of playing cards in a slightly unusual way: take one card randomly from the 52 available and place it on the table, then take another card at random from the 51 remaining and place it on top of the first, then a third from the 50 that remain, and so on.
Since one less card remains to be drawn from the deck with each card drawn, a deck of 52 cards has 52 × 51 × 50 × … × 1 = 52! (52 factorial) possible combinations, a number equal to 8.0658 × 10⁶⁷. This is a truly enormous number: consider that the age of the universe is estimated to be around 4.32 × 10¹⁷ seconds (about 13.9 billion years). In other words, the sequence of cards that we will have obtained after we have finished shuffling the deck will be unique in the entire history of the universe and will remain so for a long time!
Let’s do a mental exercise
Just looking at it that way, no human mind can really comprehend how big this number is. I therefore invite you to do a mental exercise¹: imagine having a timer set to count down from this number of seconds: 8,0658 × 10⁶⁷. At this point, in the hope of seeing the timer reach 0, you go to the equator and take a step. Then, you wait a billion years, and take another step. Another billion years, another step, until you have completed a first lap of the Earth. Once the lap is complete, take a drop of water from the Pacific Ocean and pour it into a sufficiently large red bucket. Another lap around the equator (remember to wait a billion years between each step, don’t cheat!), another drop in the bucket. And so on, until you have emptied the entire Pacific Ocean (707 million cubic kilometers of water). Once you have done this, put aside a sheet of paper. In the end, empty the full bucket back into the Pacific.
Now, start again with a second lap around the equator, always waiting a billion years between each step. Once the lap is complete, take a drop from the Pacific and continue with a new lap around the equator, until you have drained the entire Pacific Ocean again to the last drop. Now, take a second sheet of paper and put it on top of the first; finally, empty the full bucket back into the Pacific.
Continue this process until the stack of paper sheets reaches the Sun.
In your opinion, how many remaining seconds will the timer show at this point? You probably think that it’s not long now. Well, at this point, the timer would still show 8,0632 × 10⁶⁷ seconds! The three most significant digits have not even changed. Now you also understand why in the beginning we had to use four decimal places to express the number 52! To reach just a third of the countdown, we would need to create not one, but a thousand stacks of paper from Earth to the Sun.
How to spend the remaining two-thirds of time?
After all this, shuffle your deck of cards and deal yourself 5 cards at random every billion years. When you get a royal flush (A, K, Q, J, and 10, all of the same suit), an event that occurs approximately 1 in 650,000 hands, buy a lottery ticket. If the ticket is a jackpot winner, take a grain of sand and throw it into the Grand Canyon. When you have filled the Grand Canyon to the brim, extract 600 grains (about 1 oz) of limestone rock from Mount Everest. When you have leveled Everest, empty the Grand Canyon and start over. For 256 times. Only at this point, the timer will show zero seconds remaining.
Does that sound feasible?
At this point, let’s rewind the tape, to when you were still trying to empty the Pacific Ocean for the first time. You may be surprised (if you had any remaining surprise after reading this article), but, probably, all the stars in the Universe will have already gone out before you could have poured the equivalent of a handful of swimming pools into your red bucket.
Now, keep in mind that 8,0658 × 10⁶⁷ is about 30 times smaller than our 2²⁵⁶.
In other words: if you had managed to generate a private key per second for the entire time it takes to level Mount Everest for the 256th time, you would have generated only one-thirtieth of the possible Bitcoin private keys. But we haven’t considered the time it takes to verify if each generated private key is valid, meaning that it can actually control funds.
How much computing power is needed?
At this point, you might think:
okay, but if I have enough computing power, maybe I can shorten this time by several orders of magnitude.
Okay, let’s try.
2²⁵⁶ can be decomposed as 2³² × 2³² × … 2³², that is, 2³² multiplied by itself 8 times. Each term 2³² is approximately equal to 4 billion. A modern GPU can easily perform 1 billion calculations per second. Let’s imagine then packing a machine with 4 GPUs, each capable of performing 1 billion calculations per second². So far, no problem, but this is only one of the eight levels of multiplication. There are still seven others left.
To perform the second level of calculations, we would need 4 billion of these GPUs. And already at this point things start to get slightly complicated. It is estimated that even Google has between 1 and 9 million servers in its data centers. We can therefore assume that it takes a thousand Google to complete the second level of calculations.
Now we have to perform the third level of multiplications. Earth has about 8 billion people, so let’s imagine giving about half of the Earth’s population the computing power of 1000 Google, or if we prefer, to give each Earthling the computing power of 500 Google and have each one independently perform 2³² × 2³² calculations per second. But the road is still long.
To perform the fourth level of multiplications, we need 4 billion such equipped Earths. It is estimated that the Milky Way contains between 100 and 400 billion stars, so we can imagine that 1% of the stars in our galaxy contain a copy of Earth where each of the 8 billion inhabitants has access to the computing power of 500 Google. We are just halfway through the sequence.
For the fifth level of multiplications, we must imagine 4 billion such galaxies, or, if we prefer, 40 million galaxies in which every single existing star has its own Earth as we have described it. An immense supercomputer capable of 2¹⁶⁰ calculations per second.
To perform the sixth level of calculations, we would need to have… 4 billion of these supercomputers.
As we move up to the seventh level, let’s let this enormous cluster of supercomputers continuously calculate Bitcoin private keys for 4 billion seconds, or about 127 years.
Well, given all of these premises, the eighth level tells us that the probability that a single one of that enormous number of private keys generated is a valid Bitcoin private key is 1 in 4 billion.
Do you really wanna try?
¹ This mental exercise was originally proposed by Scott Cszepiel.
² There are specialized machines, known as ASICs, capable of performing hundreds of billions (1 billion = 1000 million) of calculations per second, but the basic concept does not change.
Follow me on my Facebook Page.
