There are 2^256 private keys out there: how big is that number?

[fillippone]

Yesterday while browsing down the Bitcoin rabbit hole I stumbled on the infamous keys.lol website

https://keys.lol
(Warning: time sink!)

Basically it’s a website that randomly generates 128 private keys on each page, then checks the balance of the related addresses (compressed and uncompressed) on the blockchain reporting eventual positive balances or past transactions.

Wow!
If you find a positive balance in this client side generated pages, you are actually owner of the private keys, so you are legitimate owner of such balance, and nothing prevents you from transferring to your own wallet.

I spent a few hours on that website, generating thousands of private keys, of course without finding anything, not a single used address, let alone one with a balance.

Then, I started to think I could engineer a little bit the process, and speaking with some fellow users here in the forum, I thought we could have a script generating random private keys, then ask my own bitcoin node the balance in such address and eventually transfer any balance to my own wallet. Working in local should speed up a little bit the process, I thought.

I knew from start the  possibilities to find something were tiny, but I wanted to try because looking for balances and finding nothing, would reassure me that nobody could do the same with my own bitcoin so jealously held in my cold wallet.

While waiting for @babo to disclose his script, I thought to myself “Fillippone only pawn in the game of life”...how come nobody ever thought about that?

Back into the rabbit hole, I quickly discovered the Large Bitcoin Collider.

https://lbc.cryptoguru.org/about

Wow this is a serious project.
Basically thousands of distributed servers generating and checking 26 Trillions (!!!) of private keys on a daily basis.
Over the first three years, they managed to find 7 private keys. That’s a lot! I imagined the odds were much lower., but probably there is some kind of bug in some wallet utilising a suboptimal random number generator to create keys. (Further research needed here!)


Let’s quickly review a few numbers:
Number of private keys theoretically possible: 2^256 or roughly 10^77
Number of bitcoin addresses: 2^160
Number of private keys searched by Bitcoin collider: 2^160
Numbers of atoms in the universe: 10^78 to 10^82
Number of used Bitcoin addresses: 18,000,000

The number of private keys ACTUALLY possible, is a little bit smaller than 2^256, as specified here

Let’s work out a few examples.

• Suppose we have a billion active addresses, each of them with a positive balance: we know this is roughly 10^3 bigger than the actual number.
  Probably the number of atoms in the universe is 10^3 times bigger than the number of addresses, so it is fair to say that finding a private Key with a positive amount is roughly as likely as finding one of those atoms spread all over the whole visible universe.
  How big is a billions of atoms? According to this Quora answer, it’s smaller than an E.Coli bacteria. So guess taking this bacteria, shred at atomic level, distribute it in the universe and trying to find one of those an atoms. Pretty tough, isn’t it?
  
  
• Second example is from this article. Suppose we want to scan all private keys in search of a positive balance and suppose that each inhabitant of the earth has a scanning speed one billion times higher than twice the current computing power of the Bitcoin network, thus:
  * 10 billion people;
  * multiplied by one billion;
  * multiplied by twice the computing power of Bitcoin, about 100 thousand terahash per second;
  we obtain: 1,000,000,000,000*1,000,000,000*100,000*100,0000,000,000 = 10^10*10^9*10^5*10^12 = 10^36
  For simplicity, we rounded down ‘115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336’ to 10^77, and we obtained that, if we checked every single private key, in search of a positive balance, it would take 10^77/10^36 = 10^41 seconds, how many years would it be?
  Since there are about 31557600 seconds in a year, it corresponds to about 10^41/31557600 = 31^33 years, which is more or less 10^23 times the estimated age of the universe (currently estimated at 13.82 billion years), in short
  100,000,000,000,000,000,000,000, i.e. about 100 billion billion times the age of the universe.
  
  
• This video on how much secure is the SHA 256 algorithm.
   https://youtu.be/S9JGmA5_unY
  
  
• All previous example didn’t account for the energy involved in such calculations. Of course all those very powerful machines would need to be powered by some kind of energy. How much energy would be necessary? Well, a lot, according to this infographic:
  
  
  
  Link to Reddit
  
  

Other examples about how much it would take to randomly guess  a private key:

• Reddit: Time and energy required to brute-force a AES-256 encryption
  

Further references:

• This Bitcointalk thread on possible number of bitcoin addresses
  
• Mastering Bitcoin: Keys, Addresses
  

Other vey big numbers:

• 52!:It Starts with a Simple Deck of Playing Cards
  

Here are only a few examples, if you have additional resources or comment, don’t hesitate to post yours below and I will add to the list!



If you think this thread or any other of my threads is worth being translated in your onw local board, please do! I will be happy to provide assistance!

Russian Translation by zasad@: 2 ^ 256 зaкpытыx ключeй

[pooya87]

Wow this is a serious project.
Basically thousands of distributed servers generating and checking 26 Trillions (!!!) of private keys on a daily basis.
Over the first three years, they managed to find 7 private keys. That’s a lot! I imagined the odds were much lower., but probably there is some kind of bug in some wallet utilising a suboptimal random number generator to create keys. (Further research needed here!)

that is technically incorrect.
they are not exactly finding private keys with balance, they are solving a puzzle. a long time ago (2015) in order to show the hugeness of the private key space (or maybe just for fun) someone created a "puzzle" where he chose keys in a certain smaller space and sent increasing amounts to each of those keys like this:
2⁰<key<2¹ send 0.001BTC=$0.2 at the time
2¹<key<2² send 0.002BTC=$0.4 at the time
2²<key<2³ send 0.003BTC=$0.6 at the time
and so on.
now, people to this day are still trying to solve that puzzle. so technically if you have a private key (which is impossible by the way) that is in one of those ranges they won't find that because they are only looking to solve that puzzle.

p.s. a bit nitpick-y but there are 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 private keys which is a little smaller than 2²⁵⁶

[fillippone]

that is technically incorrect.
they are not exactly finding private keys with balance, they are solving a puzzle. a long time ago (2015) in order to show the hugeness of the private key space (or maybe just for fun) someone created a "puzzle" where he chose keys in a certain smaller space and sent increasing amounts to each of those keys like this:
2⁰<key<2¹ send 0.001BTC=$0.2 at the time
2¹<key<2² send 0.002BTC=$0.4 at the time
2²<key<2³ send 0.003BTC=$0.6 at the time
and so on.
now, people to this day are still trying to solve that puzzle. so technically if you have a private key (which is impossible by the way) that is in one of those ranges they won't find that because they are only looking to solve that puzzle.

Well, this explain why they found so many keys: they weren’t looking for the whole space, but they knew “where to search”.
In the other hand they somewhat evolved, as they claim they are looking for the whole 2^160 addresses.

p.s. a bit nitpick-y but there are 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 private keys which is a little smaller than 2²⁵⁶

I know, actually the number reported in the post is not 2^256, but the decimal equivalent of 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140

I doublechecked with this message.
Anyway I edited the OP for clarity. Thanks

[o_e_l_e_o]

This is one of my old favorite examples which pops up from time to time in a variety of slightly different forms: https://czep.net/weblog/52cards.html. It is used to explain just how large 52! is - the number of possible permutations of shuffling a deck of cards. 52! works out to around 10^67, so several orders of magnitude less than 2^256 (~10^77). It essentially boils down to this:

Start at the equator. Take a single step every billion years. Once you complete the entire circumference, remove a single drop of water from the Pacific Ocean. Continue until the ocean is empty, then place a single piece of paper on the ground, refill the ocean, and start again. Once your stack of paper reaches the sun, throw it away, and start again. Repeat around 3000 times, and 52! seconds will have passed. You'd have to repeat that around 30 trillion times for 2^256 seconds.

[Syke]

If you build a Bremermann computer the size of Earth, you could crack a key in 2 minutes.

https://en.wikipedia.org/wiki/Bremermann%27s_limit

[fillippone]

If you build a Bremermann computer the size of Earth, you could crack a key in 2 minutes.

https://en.wikipedia.org/wiki/Bremermann%27s_limit

Nice, but while building that computer (if ever possibile to do so, it wouldn't be instantaneous, as even the Death Star wasn't built in a day!), Bitcoin could easily upgrade to 512 Bit security.
Satoshi stash would be probably be captured, flooding BTC with 1M "new" bitcoins. That would briefly disrupt the market, but the shock would be widely anticipated and so well absorbed.

[pooya87]

Bitcoin could easily upgrade to 512 Bit security.

If someday we "upgrade" bitcoin i don't think it would be to a bigger size curve (which the bigger keys come from) but i suppose it would be a migration to another different asymmetric cryptography algorithm instead of elliptic curve and keep it small at possibly the same 256 bit key size.

[fillippone]

Bitcoin could easily upgrade to 512 Bit security.

If someday we "upgrade" bitcoin i don't think it would be to a bigger size curve (which the bigger keys come from) but i suppose it would be a migration to another different asymmetric cryptography algorithm instead of elliptic curve and keep it small at possibly the same 256 bit key size.

Sure, I do hope so. I was only pointing out a very simple yet effective (not efficient, thou) defence against such machine is aldready avaliable: hence the threat from such scenario is not credible.

[fillippone]

This is one of my old favorite examples which pops up from time to time in a variety of slightly different forms: https://czep.net/weblog/52cards.html.

I am dumb, but I cannot reproduce all the computation with Excel.
 I get right to the point of the last iteration 1000x, then results diverge.
I hope it is excel messing up with exp notations.
Btw I found a nice animation on the same example:
https://www.youtube.com/watch?v=0DSclqnnC2s

[fillippone]

This thread has been translated in Russian by zasad@

2 ^ 256 зaкpытыx ключeй

If you think this thread or any other of my threads is worth being translated in your onw local board, please do! I will be happy to provide assistance!

[arulbero]

Another way to look at  2^256 number:

https://btckeygen.com/


(thread --> https://bitcointalk.org/index.php?topic=5187401.0)

[qwk]

I quickly discovered the Large Bitcoin Collider.

https://lbc.cryptoguru.org/about

Wow this is a serious project.
Basically thousands of distributed servers generating and checking 26 Trillions (!!!) of private keys on a daily basis.
Over the first three years, they managed to find 7 private keys. That’s a lot! I imagined the odds were much lower., but probably there is some kind of bug in some wallet utilising a suboptimal random number generator to create keys.

A few basic comments on the LBC.
For starters, I'd like to point out that I personally am convinced that the LBC is a huge waste of time, effort, energy and money.
It has no academic value whatsoever, is unlikely to yield any results that contradict common understanding of cryptography and will not determine any empirically establishable "constants of nature".


When you're using Bitcoin, what you are basically doing is play a game.
The game is "I'm thinking of a random number, if you can guess it, here's a dollar".

To make it easy, I can start with "I'm thinking of a number between one and ten".
Your chances of getting that dollar are 10 per cent.

In a harder game, I'll think of a number between one and one thousand.
To make it a challenge, I'll ask you to donate 1 US cent for every guess to a good cause.
A dollar will yield 100 guesses, so your chances of even making you dollar back are only 10 per cent.

Now, in Bitcoin, I'm thinking of a number between one and 2^160 (in fact, it's a little less, but let's not delve into technical details too much).
For a single guess, I want you to donate a tiny amount of computing power, i.e. electrical energy to, well, thermodynamics (because that energy is obviously wasted).


But in Bitcoin, there are actually more than just two players.
I may ask for a number between one and 2^160, but others just ask for a number between one and ten.
If you guess "nine", your chances of getting their number right are ten per cent, but at the same time, you also have a (much slighter) chance of guessing my number right (I could have used "nine" as well, it's in the space of 2^160, after all).


And that is what the LBC does.
It doesn't guess random numbers in the range of 2^160, but rather numbers in the range of one to ten, then 11 to 100, then 101 to 1000, etc.
All the time, it's obviously also guessing numbers in the wider range of 2^160.
For the LBC to claim that it's guessing numbers in that range is pretty far fetched, though.

Now, the collisions the LBC found so far were all in those much narrower search ranges, they have nothing to do whatsoever with collisions in the wider space of 2^160, other than that they inadvertently lie in that range as well.

[pooya87]

Now, in Bitcoin, I'm thinking of a number between one and 2^160 (in fact, it's a little less, but let's not delve into technical details too much).

a good analogy with the "guessing the number" thing, but there is a tiny mistake here. that "number" that we choose in bitcoin (aka private key) is between 1 and a little less than 2²⁵⁶ then that number is "converted" and "compressed" using one way operations to a smaller size (2¹⁶⁰).
in other words when someone is guessing the number they still have to perform those two time consuming operations to a get a result and compare it with yours.

[qwk]

Now, in Bitcoin, I'm thinking of a number between one and 2^160 (in fact, it's a little less, but let's not delve into technical details too much).

there is a tiny mistake here. that "number" that we choose in bitcoin (aka private key) is between 1 and a little less than 2²⁵⁶ then that number is "converted" and "compressed" using one way operations to a smaller size (2¹⁶⁰).

It's actually a little more complicated than that.
There is (AFAIK) no really good answer to how many "guesses" we're talking about in this "game".
There are indeed 2^256 private keys (or slightly less), but they translate to a "mere" 2^160 addresses.
More than one private key translates to one address, but it's not as simple as saying "x private keys translate to one address".
HD wallets have further complicated the question of "how many guesses".
This is why I have settled for the lower boundary of 2^160 whenever I explain the probability of guessing a private key.
This is also why I specifically didn't want to delve into the technical details too much


Here's another snippet of wisdom from when I'm trying to explain the odds of guessing a private key:
Cheat code to convert 2^x to 10^x: reduce the exponent by 3 or 4 (2^3 = 8; 2^4 = 16)

2^160 is (roughly) the same as a 1 with 156 48 zeros.
Now imagine a Billion people, that's a 1 with 9 zeros.
Now imagine each of those people guessing a Billion times.
That's a 1 with 18 zeros guesses.
You've only managed to reduce the original 1 with 156 48 zeros down to a 1 with 138 30 zeros.
The chances of guessing the right number are still 1 in a 1 with 138 30 zeros.

Even that is technically not completely correct, but it gives people a better idea of what size of numbers we're talking about.
It's easy to continue with things like "let them take a billion guesses every second for a billion seconds" etc.

In short: always convert to base 10 numbers when talking to "normal" people.
They don't understand base 2.

Once people understand what it takes to reduce a number with 156 48 zeros down to a manageable size, they usually begin to comprehend why "I'm thinking of a random number" is actually a very safe way to store your Bitcoins.

[arulbero]

...
Here's another snippet of wisdom from when I'm trying to explain the odds of guessing a private key:
Cheat code to convert 2^x to 10^x: reduce the exponent by 3 or 4 (2^3 = 8; 2^4 = 16)

2^160 is (roughly) the same as a 1 with 156 zeros.

No.  You have to divide 160 by 3 or 4.

2^160  = 1461501637330902918203684832716283019655932542976

like 1 with 48 zeroes.

[fillippone]

Once people understand what it takes to reduce a number with 156 zeros down to a manageable size, they usually begin to comprehend why "I'm thinking of a random number" is actually a very safe way to store your Bitcoins.

This is actually the point of this whole thread!

...
Here's another snippet of wisdom from when I'm trying to explain the odds of guessing a private key:
Cheat code to convert 2^x to 10^x: reduce the exponent by 3 or 4 (2^3 = 8; 2^4 = 16)

2^160 is (roughly) the same as a 1 with 156 zeros.

No.  You have to divide 160 by 3 or 4.

2^160  = 1461501637330902918203684832716283019655932542976

like 1 with 48 zeroes.

After a thoroughful research I can confirm @arulbero result:

[arulbero]

Once people understand what it takes to reduce a number with 156 zeros down to a manageable size, they usually begin to comprehend why "I'm thinking of a random number" is actually a very safe way to store your Bitcoins.

This is actually the point of this whole thread!

But:

1) the real measure of how random is an address is 2^160, not 2^256, because there are 2^96 different private keys for the same address

2) if you reveal your public key, it takes only about 2^128 guesses (just to simplify) to steal your bitcoins

At this moment the hash rate of bitcoin network is about 2^67 hashes/s, i.e. about 2^92 hashes/year.

Generating a hash is faster (so far) than generate an address from a private key, it's just to have an idea of what size of numbers we're talking about.

We would need a computation power 2^36 bigger than the current entire network to crack an address in 1 year. It would take 36 consecutive doublings to get that power.

[qwk]

Cheat code to convert 2^x to 10^x: reduce the exponent by 3 or 4 (2^3 = 8; 2^4 = 16)

No.  You have to divide 160 by 3 or 4.

Right, my bad
I actually use dice in my examples, i.e. 6^62 ~ 2^160.
That's why I sometimes carry a big bag of dice around


Example from my FAQ (in German, sorry)

62 dice rolls in a row (guaranteed to be random*):
4 2 1 5 1 6 4 3 4 4 3 4 1 3 3 5 5 6 3 4 4 2 4 2 3 3 3 6 4 5 6 5 3 2 3 1 5 6 3 1 5 4 3 3 3 3 3 2 5 5 6 1 2 1 3 4 6 6 5 4 2 6

Or in binary:

Code:

1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1
0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1
0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 1
0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0

*

https://xkcd.com/221/

[Jean_Luc]

At this moment the hash rate of bitcoin network is about 2^67 hashes/s, i.e. about 2^92 hashes/year.

The BTC network power is quite impressive !
Considering having the same power dedicated to address calculation, it would require few hours to find an address collision (2 private keys with the same address).

[arulbero]

At this moment the hash rate of bitcoin network is about 2^67 hashes/s, i.e. about 2^92 hashes/year.

The BTC network power is quite impressive !
Considering having the same power dedicated to address calculation, it would require few hours to find an address collision (2 private keys with the same address).

I know only a cpu program to find an address collision:

https://www.reddit.com/r/Bitcoin/comments/34hjph/generating_partial_address_collisions_using_the/