Bitcoin Forum
April 21, 2018, 07:50:50 PM *
News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 [45] 46 47 48 49 50 51 52 53 54 55 56 »
  Print  
Author Topic: Large Bitcoin Collider (Collision Finders Pool)  (Read 163277 times)
Its_a_Meeeee
Newbie
*
Offline Offline

Activity: 6
Merit: 0


View Profile
April 12, 2017, 04:44:11 PM
 #881

Regarding wheather we assume 160 bit space or 159 (half of it).

The idea to "only" need to search in half of the 160-bit output space of addresses arises because we generate both,
compressed and uncompressed addresses for each private key guess.

Q: I don't know about that process. Is it more like this:

private_key --*some process*--> uncompressed-address
         |
         --*some other process*--> compressed-address
         
or like this:

private_key --*some process*--> uncompressed-address --*some other process*--> compressed-address


I would argue no search-space reduction can be achieved if the process is the later one.
So IMO the statement on the page "X bits of 160bits" is correct.

Regarding the probabilty calculations i guess arulbero is in a higher dimension than me Cheesy I'll shut up and enjoy the show Lips sealed
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
monsanto
Legendary
*
Offline Offline

Activity: 1186
Merit: 1002


..like bright metal on a sullen ground.


View Profile
April 12, 2017, 04:59:26 PM
 #882

(31 + 16,4) - 135,2  -->  -87,8 --> 0,0000000000000000000000000037116

I didn't count the 51 bits of the so far searched space, but i think it is more or less the same ...

2 orders of magnitude...
because %

0.000000000000000000000000003711
0.000000000000000000000000401596% <--- correct number (online)


So to sum up - how is this number going to be bigger?

  • With more addresses with funds on them
  • In time, as more space is searched
  • With higher search speed

From what I can see, the number of addresses with funds has the most effect at the moment.


Rico

I love reading about this stuff! Unfortunately I don't understand it all yet, but someday.  I'll just keep working on it.

As I understand it then the "successes" so far were only possible because the hit addresses lacked true randomness or something? I'm trying to understand how exactly those addresses are found.  I understand how some brain wallets were found but not these. I guess your search algorithm specifically targets certain kinds of addresses.

Keep up the good work.
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
April 12, 2017, 06:11:00 PM
 #883

         
or like this:

private_key --*some process*--> uncompressed-address --*some other process*--> compressed-address

I would argue no search-space reduction can be achieved if the process is the later one.
So IMO the statement on the page "X bits of 160bits" is correct.

It is more like

Code:
private_key --*some process*--> uncompressed-pubkey -> *very negligible process* -> compressed-pubkey
                                            |                                             |
                                   hash160 process                                 hash160 process
                                            v                                             v
                                  uncompressed-address                            compressed-address

With the current CPU/GPU hybrid architecture, we would have exact the same keyrate if we just computed one of these.

edit: The CPU clients would be faster computing just one of them (preferably the compressed one), which is what e.g. vanitygen does.
but, they would only be faster nominally (keyrate), not factually, as they would need to perform 2 EC arithmetic computations for 2 addresses. So the overall "address-rate" would be lower.



Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Real-Duke
Legendary
*
Offline Offline

Activity: 1162
Merit: 1014


Bitcore (BTX) - Airdrops every Monday


View Profile
April 12, 2017, 06:44:04 PM
 #884

6a50c257a1e7d3712f035059d7d2bf4809360b46:c:priv:0000000000000000000000000000000000000000000000000008f1ce137ff001+0xfe9
My Bounty found from yesterday morning, just for the records  Wink
Thanks to SlarkBoy!

           ▀██▄ ▄██▀
            ▐█████▌
           ▄███▀███▄
         ▄████▄  ▀███▄
       ▄███▀ ▀██▄  ▀███▄
     ▄███▀  ▄█████▄  ▀███▄
   ▄███▀  ▄███▀ ▀███▄  ▀███▄
  ███▀  ▄████▌   ▐████▄  ▀███
 ███   ██▀  ██▄ ▄██  ▀██   ███
███   ███  ███   ███  ███   ███
███   ███   ███████   ███   ███
 ███   ███▄▄       ▄▄███   ███
  ███▄   ▀▀█████████▀▀   ▄███
   ▀████▄▄           ▄▄████▀
      ▀▀███████████████▀▀
DeepOnion★  Anonymity Guaranteed
★  Anonymous and Untraceable
★  Guard Your Privacy
      ▄▄██████████▄▄
    ▄███▀▀      ▀▀█▀   ▄▄
   ███▀              ▄███
  ███              ▄███▀   ▄▄
 ███▌  ▄▄▄▄      ▄███▀   ▄███
▐███  ██████   ▄███▀   ▄███▀
███▌ ███  ███▄███▀   ▄███▀
███▌ ███   ████▀   ▄███▀
███▌  ███   █▀   ▄███▀  ███
▐███   ███     ▄███▀   ███
 ███▌   ███  ▄███▀     ███
  ███    ██████▀      ███
   ███▄             ▄███
    ▀███▄▄       ▄▄███▀
      ▀▀███████████▀▀
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
April 12, 2017, 07:09:27 PM
 #885

And user Coinpiet found https://blockchain.info/de/address/e426d197698e06bdfe851a873a4a1bbd1f2d726e today.

Lucky newbie: https://lbc.cryptoguru.org/stats/PeterPC_Bitcoin

He is still fighting with claiming the funds.  Wink So privkey later...



Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Its_a_Meeeee
Newbie
*
Offline Offline

Activity: 6
Merit: 0


View Profile
April 12, 2017, 08:04:17 PM
 #886

Congrats Real-Duke & Newbie^^

Ok Rico, from the way you describe the process I derive following information pieces.

EDIT: for clarity. When I say "have 4 addresses in the filter" I mean 4 unique addresses and 8 representations thereof (2 each)

1) As I assumed the compressed address is simply a way of displaying one uncompressed address in another way.
==> It means that it is a bijective mapping of the address to another encoding / format.
As in: https://en.wikipedia.org/wiki/Bijection

2)
a)It definitely makes sense to calculate both addresses for a private key and check against the filters,
   just to make sure we cover 100% of all addresses that are funded (if we should ever get to the end of 160 bits Cheesy)
b)On the contrary this does not mean that you check two private keys, just two representations(!) of the public key.

->Checking only the compressed or uncompressed address format would allow for a collision to go by undetected,
   because you basically have a 50% chance of the original private key being used / funded through either of the formats,
   thus not appearing in your bloom filter.

->Now reducing the search space to 159 bits, effectively halving it, reduces the collision amount that you can expect to find accordingly and you
   could expect to match about half of all addresses in your filter +/- variance. (while producing half of all possible addresses)

->By checking only one however, and opening up for undetected collisions as mentioned above, you should then only expect about 25% of all addresses to be matched.
(while still having to produce half of all addresses for this lesser gain.)

->In Order to produce all addresses you still have to go through 160 bit of search space.
 -->In Order to match all addresses you can not reduce the search space and have to check against both formats.

->The probability of matching just one produce (the next one) to an address in the filter should then (kinda simply) be:

1 / ( (2**159) / 1 ), for the case we have a single address in the filter, in both its representations.

1 / ( (2**159) / 2 ), for the case we have two address in the filter, totaling  4 representations.

1 / ( (2**159) / (2**159) ) = 1/1 = 100% (as logically expected), for the case that we would check against a filter containing all possible entries.

So the needed formula is:
1 / ( (2**159) / (Number_Of_Entries_In_Filter) )
This is then scale able with something like X Mkey/s and 24h, to approximate daily probability.

Important here is that this is plain, without the progressive nature that's built into the LBC.
Again I am not sure about the need for conditional calculations (might arrive at the same result).
Because simply put each done calculation just reduces the remaining search space.
1 / ( (2**159 - Progression_Value) / (Number_Of_Entries_In_Filter) )

Imagine the extreme scenario, we find all (lets say we had only 22 for simplcity) addresses in the very last 4 private keys that we search.
The formula must result in 1 (100%) at the point where only 4 private keys are left and 2**159 - 4 have been searched.
Let's see:
1 / ( (2**159 - (2**159 - 4)) / (4) )
1 / ( 4 / 4 )
= 1 !

Works beautifully!  Cheesy
What do you guys think?  Huh

SUMMARY:

I think checking both formats is mandatory since we don't want anything go by undetected, period :-)

Since uncompressed to compressed is an encoding process not evolving the private key it is unrelated to the search space coverage.
But related to collision chance. (on the homepage described as" the effective search space until something is found")

One could also formulate:
"There are 2160 addresses. Each has two representations, which are interchangeable. Making it 2161 representations.
One private key calculation will have a chance of matching one of the representations of 1 / 2160 twice. So probability per private key is 1 / 2159. (non progressive)"

If you want to display the probability of the pool forefront on the page my suggested formula should do the trick.
If you really want to display a good estimation, or even just scaled up from current speed, for a 24h based probability you will need a math professor at your disposal  Wink

Phew, brain tingles :-)
Have fun with this mind twister
unknownhostname
Member
**
Offline Offline

Activity: 61
Merit: 10


View Profile
April 12, 2017, 10:30:29 PM
 #887

f86b1dd782990bafba34c28c88d4c7ff9ce99641:c:priv:000000000000000000000000000000000000000000000000000a1835db9ff001 + 0xf87
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
April 13, 2017, 05:47:36 AM
 #888

Ok Rico, from the way you describe the process I derive following information pieces.

EDIT: for clarity. When I say "have 4 addresses in the filter" I mean 4 unique addresses and 8 representations thereof (2 each)

When we have - as of now - 15.6 mio addresses in the filter, it's 15.6 mio addresses (not 15M x 2, or x 4). Unique addresses some of which are based on compressed and some of which are based on uncompressed public keys.

Now - for brevity - instead of this "is based on", we'll just talk of compressed and uncompressed addresses. All we need to know for now, that there is two P2PKH addresses per private key (said compressed and uncompressed).

If we create these from 2^159 private keys, we get 2^160 addresses. Period. The question (but left for another discussion) is if/how far these are unique addresses.

Now why this magic 160 all the time? Because RIPEMD160. The 160 is the number of bits in its output. As RIPEMD160 is the last piece in the chain of computing an address, it's output matters (and nothing else).

Therefore,

Quote
One could also formulate:
"There are 2160 addresses. Each has two representations, which are interchangeable. Making it 2161 representations.

Nope. There is no way we could generate more than said 2160 addresses. Be it with compressed alone, with uncompressed alone, or with both. In fact, even if we generated compressed and uncompressed for all (nearly) 2^256 private keys, (generating 2^257 hash160 in the process) -> we still would end up with at most 2160 addresses.

So this is the limit. There is no more. This discrepancy between the number of possible private keys and the number of possible addresses is the reason for this "there are about 296 private keys to each address". (Which I now believe is not true, because there are actually 297 private keys to each address, but this is also for another discussion)

If we look at an address (the hash160), we cannot see if it is a compressed (c) or uncompressed (u) one. The information is not there.
Therefore, we may have 4 types of collisions:  c-c, u-u, c-u/u-c

c-c: We generate a compressed address with key x and it collides with a compressed address made from key y
u-u: We generate an uncompressed address with key x and it collides with an uncompressed address made from key y
c-u: We generate a compressed address with key x and it collides with an uncompressed address made from key y
u-c: We generate an uncompressed address with key x and it collides with a compressed address made from key y

At the moment - because we are generating both types and because we have both types in the filter, we are potentially catching all these 4 types of collisions. So yes: doing uncompressed and compressed is mandatory.  Smiley

And yes, looking at 2159 private keys means we will compute 2160 addresses. They may not be unique though. This is under investigation and not necessarily a bad thing for us. Not unique = there are collisions.


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Its_a_Meeeee
Newbie
*
Offline Offline

Activity: 6
Merit: 0


View Profile
April 13, 2017, 05:48:34 AM
 #889

I reject and denounce myself   Angry

After a night of research I found, that this thread somewhere along the way introduced to me the concept of uncompressed and compressed addresses,
which I've had never heard of before, and really threw me for a loop.

I also found that there are no such addresses.
It is allowed however, to represent/store/use your public key in a compressed version of its full length!

This is shocking to me. It allows every private key to control TWO of all of the 2160 addresses  Shocked
Another fact I just didn't realize so far.

Now that would also mean there are possible collisions (adding to the ones LBC is already looking for).
private_key_UNO resolves to public_key_uncompressed_A and public_key_compressed_A

Do I understand it correctly, that now there could exist another private key resolving to either one of those?
private_key_DUO resolves to public_key_uncompressed_X and public_key_compressed_A
or
private_key_DUO resolves to public_key_uncompressed_A and public_key_compressed_X


Holy crap! Collision inception.
I feel like I don't know my coins at all right now  Roll Eyes


EDIT:
Hi Rico seems we posted rather synced ;-)
I will enjoy your post with a nice cup of coffee.
Learning so much in this thread :-)

unknownhostname
Member
**
Offline Offline

Activity: 61
Merit: 10


View Profile
April 13, 2017, 07:07:22 AM
 #890

6b2749936df41b73239c1c823642c0a82af74ab6:c:priv:000000000000000000000000000000000000000000000000000a489a332ff001 + 0xfbf
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
April 13, 2017, 07:36:09 AM
 #891

Now that would also mean there are possible collisions (adding to the ones LBC is already looking for).
private_key_UNO resolves to public_key_uncompressed_A and public_key_compressed_A

Do I understand it correctly, that now there could exist another private key resolving to either one of those?
private_key_DUO resolves to public_key_uncompressed_X and public_key_compressed_A
or
private_key_DUO resolves to public_key_uncompressed_A and public_key_compressed_X

Not only could, but most certainly does. Actually - on average - as much as

297

private keys could exist that resolve to ONE particular address (no matter if compressed or uncompressed). 296 of these via the compressed route, 296 of these via the uncompressed route.

Quote
Learning so much in this thread :-)

Me too - and then there are people who claim this is not beneficial.  Wink


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
unknownhostname
Member
**
Offline Offline

Activity: 61
Merit: 10


View Profile
April 13, 2017, 10:27:46 AM
 #892

f152befd8c60892eb296e937266bf9f3e38f2c5a:u:priv:000000000000000000000000000000000000000000000000000a78990f8ff001 + 0xfba
Real-Duke
Legendary
*
Offline Offline

Activity: 1162
Merit: 1014


Bitcore (BTX) - Airdrops every Monday


View Profile
April 13, 2017, 10:41:59 AM
 #893

f152befd8c60892eb296e937266bf9f3e38f2c5a:u:priv:000000000000000000000000000000000000000000000000000a78990f8ff001 + 0xfba
And our daily easter egg give us today  Wink

           ▀██▄ ▄██▀
            ▐█████▌
           ▄███▀███▄
         ▄████▄  ▀███▄
       ▄███▀ ▀██▄  ▀███▄
     ▄███▀  ▄█████▄  ▀███▄
   ▄███▀  ▄███▀ ▀███▄  ▀███▄
  ███▀  ▄████▌   ▐████▄  ▀███
 ███   ██▀  ██▄ ▄██  ▀██   ███
███   ███  ███   ███  ███   ███
███   ███   ███████   ███   ███
 ███   ███▄▄       ▄▄███   ███
  ███▄   ▀▀█████████▀▀   ▄███
   ▀████▄▄           ▄▄████▀
      ▀▀███████████████▀▀
DeepOnion★  Anonymity Guaranteed
★  Anonymous and Untraceable
★  Guard Your Privacy
      ▄▄██████████▄▄
    ▄███▀▀      ▀▀█▀   ▄▄
   ███▀              ▄███
  ███              ▄███▀   ▄▄
 ███▌  ▄▄▄▄      ▄███▀   ▄███
▐███  ██████   ▄███▀   ▄███▀
███▌ ███  ███▄███▀   ▄███▀
███▌ ███   ████▀   ▄███▀
███▌  ███   █▀   ▄███▀  ███
▐███   ███     ▄███▀   ███
 ███▌   ███  ▄███▀     ███
  ███    ██████▀      ███
   ███▄             ▄███
    ▀███▄▄       ▄▄███▀
      ▀▀███████████▀▀
unknownhostname
Member
**
Offline Offline

Activity: 61
Merit: 10


View Profile
April 13, 2017, 06:46:42 PM
 #894

f9362f7da717b421680e31a0fdc61b8a6c7118ca:u:priv:000000000000000000000000000000000000000000000000000aaa676bdff001 + 0xfff
TooDumbForBitcoin
Legendary
*
Offline Offline

Activity: 1344
Merit: 1001



View Profile
April 13, 2017, 10:45:56 PM
 #895

https://motherboard.vice.com/en_us/article/the-large-bitcoin-collider-is-generating-trillions-of-keys-and-breaking-into-wallets

Next, Oprah!!  (Does she still have a show?)

Hey, Rico, don't forget all us little people.

█████
████████████
█████████████████
██
████████████████
███████████████████
███████████████████████
█████
██████████████████
██████████████████████
██████████████████████
█████████████████████
█████
███████████████████
█████
█████████████████
███████████████████
███
███████████████
████████████
██
█████
cashbet

██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
♦ PLAYER PROTECTION ♥ TRUST AND TRANSPARENCY ♠ REDUCED FEES ♣


██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
♛ FACEBOOK  ♚ LINKEDIN  ♝ TELEGRAM ♜
coinableS
Legendary
*
Offline Offline

Activity: 1064
Merit: 1000



View Profile WWW
April 14, 2017, 12:46:02 AM
 #896

Glad to see this is still going. I come to check this thread every so often, it's always a good read. Wondering if Rico is going to start a multisig one next  Cheesy

rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
April 14, 2017, 05:57:15 AM
 #897

Glad to see this is still going. I come to check this thread every so often, it's always a good read. Wondering if Rico is going to start a multisig one next  Cheesy

All Multisig hash160 have been part of the bloom filter we check against for the past month or so.

@TooDumbForBitcoin

About the Motherboard article: No matter how hard one tries, there's always some precision lost in these articles, so "experts" should take them with a grain of salt. Effectively it's just a superficial introduction to the broader public. It's my contribution so scribes also get something to do for a living. Wink


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
unknownhostname
Member
**
Offline Offline

Activity: 61
Merit: 10


View Profile
April 14, 2017, 07:39:42 AM
 #898

d328b3189f7d8f39ec758abbcf6ef6c3a92f9f4f:u:priv:000000000000000000000000000000000000000000000000000adbedc72ff001 + 0xfb2
TooDumbForBitcoin
Legendary
*
Offline Offline

Activity: 1344
Merit: 1001



View Profile
April 14, 2017, 10:55:33 AM
 #899


@TooDumbForBitcoin

About the Motherboard article: No matter how hard one tries, there's always some precision lost in these articles, so "experts" should take them with a grain of salt. Effectively it's just a superficial introduction to the broader public. It's my contribution so scribes also get something to do for a living. Wink


Rico

It's usually sobering for me to read a "MSM" article about a subject I know a little more about, relative to the general reading audience.  Extrapolating the inaccuracies one notices in areas of their own expertise to all "MSM" articles makes one realize that "MSM" articles are generally poor sources for unbiased or technically accurate reporting.


█████
████████████
█████████████████
██
████████████████
███████████████████
███████████████████████
█████
██████████████████
██████████████████████
██████████████████████
█████████████████████
█████
███████████████████
█████
█████████████████
███████████████████
███
███████████████
████████████
██
█████
cashbet

██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
♦ PLAYER PROTECTION ♥ TRUST AND TRANSPARENCY ♠ REDUCED FEES ♣


██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
██████
  ██
██████
██  ██
♛ FACEBOOK  ♚ LINKEDIN  ♝ TELEGRAM ♜
josh5
Newbie
*
Offline Offline

Activity: 5
Merit: 0


View Profile
April 14, 2017, 01:20:43 PM
 #900

Quick question, please excuse my ignorance on this ... I've searched everywhere and can't really find an answer.

If (hopefully when) I receive my found.txt with the priv key in hex, how do I convert that to a WIF?
Is there something simple I'm completely missing here? I'm terrible at math so hopefully there's a tool to do this.

Watch out unknownhostname .. I'm coming for ya ... very, very slowly albeit Smiley
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 [45] 46 47 48 49 50 51 52 53 54 55 56 »
  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!