Bitcoin Forum
October 21, 2019, 06:51:13 PM *
News: Latest Bitcoin Core release: 0.18.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: There are 2^256 private keys out there: how big is that number?  (Read 353 times)
fillippone
Hero Member
*****
Offline Offline

Activity: 490
Merit: 1430


Legendary Member Wannabe


View Profile
May 26, 2019, 02:10:00 PM
Last edit: May 28, 2019, 10:05:59 AM by fillippone
 #1

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:

Further references:


Other vey big numbers:

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!

1571683873
Hero Member
*
Offline Offline

Posts: 1571683873

View Profile Personal Message (Offline)

Ignore
1571683873
Reply with quote  #2

1571683873
Report to moderator
1571683873
Hero Member
*
Offline Offline

Posts: 1571683873

View Profile Personal Message (Offline)

Ignore
1571683873
Reply with quote  #2

1571683873
Report to moderator
1571683873
Hero Member
*
Offline Offline

Posts: 1571683873

View Profile Personal Message (Offline)

Ignore
1571683873
Reply with quote  #2

1571683873
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1571683873
Hero Member
*
Offline Offline

Posts: 1571683873

View Profile Personal Message (Offline)

Ignore
1571683873
Reply with quote  #2

1571683873
Report to moderator
pooya87
Legendary
*
Offline Offline

Activity: 1792
Merit: 1975


Remember tonight for it's the beginning of forever


View Profile
May 26, 2019, 04:12:05 PM
Merited by bones261 (2), LoyceV (2), vapourminer (1), ETFbitcoin (1), fillippone (1)
 #2

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:
20<key<21 send 0.001BTC=$0.2 at the time
21<key<22 send 0.002BTC=$0.4 at the time
22<key<23 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 2256 Tongue

fillippone
Hero Member
*****
Offline Offline

Activity: 490
Merit: 1430


Legendary Member Wannabe


View Profile
May 26, 2019, 05:02:00 PM
Last edit: May 26, 2019, 05:14:19 PM by fillippone
 #3


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:
20<key<21 send 0.001BTC=$0.2 at the time
21<key<22 send 0.002BTC=$0.4 at the time
22<key<23 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 2256 Tongue

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
Hero Member
*****
Offline Offline

Activity: 714
Merit: 2904


Decent


View Profile
May 26, 2019, 07:38:07 PM
Merited by franckuestein (3), ETFbitcoin (1), fillippone (1)
 #4

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
Legendary
*
Offline Offline

Activity: 3122
Merit: 1037


View Profile
May 27, 2019, 06:55:26 AM
Merited by fillippone (1)
 #5

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

Buy & Hold
fillippone
Hero Member
*****
Offline Offline

Activity: 490
Merit: 1430


Legendary Member Wannabe


View Profile
May 27, 2019, 07:41:51 AM
 #6

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
Legendary
*
Offline Offline

Activity: 1792
Merit: 1975


Remember tonight for it's the beginning of forever


View Profile
May 27, 2019, 08:59:57 AM
 #7

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
Hero Member
*****
Offline Offline

Activity: 490
Merit: 1430


Legendary Member Wannabe


View Profile
May 27, 2019, 09:57:27 AM
 #8

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
Hero Member
*****
Offline Offline

Activity: 490
Merit: 1430


Legendary Member Wannabe


View Profile
May 27, 2019, 04:15:24 PM
 #9

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



Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!