fillippone


May 26, 2019, 02:10:00 PM Last edit: January 06, 2020, 10:15:52 AM by fillippone Merited by qwk (5), Welsh (4), CryptopreneurBrainboss (4), franckuestein (3), El duderino_ (3), redsn0w (2), LoyceV (2), Piggy (2), odolvlobo (1), vapourminer (1), JayJuanGee (1), ETFbitcoin (1), pooya87 (1), o_e_l_e_o (1), witcher_sense (1), Heisenberg_Hunter (1), RapTarX (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/aboutWow 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 hereLet’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!
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й





Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.



pooya87
Legendary
Offline
Activity: 1904
Merit: 2290
Remember tonight for it's the beginning of forever


May 26, 2019, 04:12:05 PM 

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 ^{0}<key<2 ^{1} send 0.001 BTC=$0.2 at the time 2 ^{1}<key<2 ^{2} send 0.002 BTC=$0.4 at the time 2 ^{2}<key<2 ^{3} send 0.003 BTC=$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 nitpicky but there are 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 private keys which is a little smaller than 2 ^{256}




fillippone


May 26, 2019, 05:02:00 PM Last edit: May 26, 2019, 05:14:19 PM by 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 ^{0}<key<2 ^{1} send 0.001 BTC=$0.2 at the time 2 ^{1}<key<2 ^{2} send 0.002 BTC=$0.4 at the time 2 ^{2}<key<2 ^{3} send 0.003 BTC=$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 nitpicky but there are 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 private keys which is a little smaller than 2 ^{256} 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
Legendary
Offline
Activity: 812
Merit: 3444
Decent


May 26, 2019, 07:38:07 PM 

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.





fillippone


May 27, 2019, 07:41:51 AM 

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
Activity: 1904
Merit: 2290
Remember tonight for it's the beginning of forever


May 27, 2019, 08:59:57 AM 

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


May 27, 2019, 09:57:27 AM 

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


May 27, 2019, 04:15:24 PM 

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


January 06, 2020, 09:32:54 AM Last edit: January 06, 2020, 10:15:18 AM by 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
Legendary
Offline
Activity: 1370
Merit: 1486





qwk
Donator
Legendary
Online
Activity: 2380
Merit: 2394
Shitcoin Minimalist


January 06, 2020, 02:42:10 PM 

I quickly discovered the Large Bitcoin Collider. https://lbc.cryptoguru.org/aboutWow 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.

All free men, wherever they may live, can use Bitcoin, and, therefore, as a free man, I take pride in the words "Ich bin ein Bitcoiner!"



pooya87
Legendary
Offline
Activity: 1904
Merit: 2290
Remember tonight for it's the beginning of forever


January 07, 2020, 03:48:58 AM 

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 ^{256} then that number is "converted" and "compressed" using one way operations to a smaller size (2 ^{160}). 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
Donator
Legendary
Online
Activity: 2380
Merit: 2394
Shitcoin Minimalist


January 07, 2020, 01:11:03 PM Last edit: January 07, 2020, 02:44:26 PM by qwk Merited by fillippone (2) 

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 ^{256} then that number is "converted" and "compressed" using one way operations to a smaller size (2 ^{160}). 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.

All free men, wherever they may live, can use Bitcoin, and, therefore, as a free man, I take pride in the words "Ich bin ein Bitcoiner!"



arulbero
Legendary
Offline
Activity: 1370
Merit: 1486

... 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


January 07, 2020, 01:35:41 PM Last edit: January 07, 2020, 01:46:26 PM by 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
Legendary
Offline
Activity: 1370
Merit: 1486

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
Donator
Legendary
Online
Activity: 2380
Merit: 2394
Shitcoin Minimalist


January 07, 2020, 02:23:27 PM 

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: 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/

All free men, wherever they may live, can use Bitcoin, and, therefore, as a free man, I take pride in the words "Ich bin ein Bitcoiner!"



Jean_Luc


January 07, 2020, 02:29:15 PM 

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
Legendary
Offline
Activity: 1370
Merit: 1486


January 07, 2020, 03:04:43 PM 

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/




