Large Bitcoin Collider (Collision Finders Pool)

[Its_a_Meeeee]

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 I'll shut up and enjoy the show

[1714860970]

1714860970

[1714860970]

1714860970

[1714860970]

1714860970

[1714860970]

1714860970

[1714860970]

1714860970

[monsanto]

(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]

         
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

[Real-Duke]

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

[rico666]

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.  So privkey later...



Rico

[Its_a_Meeeee]

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 )
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 2² 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!  
What do you guys think?  

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 2¹⁶⁰ addresses. Each has two representations, which are interchangeable. Making it 2¹⁶¹ representations.
One private key calculation will have a chance of matching one of the representations of 1 / 2¹⁶⁰ twice. So probability per private key is 1 / 2¹⁵⁹. (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 

Phew, brain tingles :-)
Have fun with this mind twister

[unknownhostname]

f86b1dd782990bafba34c28c88d4c7ff9ce99641:c:priv:000000000000000000000000000000000000000000000000000a1835db9ff001 + 0xf87

[rico666]

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,

One could also formulate:
"There are 2¹⁶⁰ addresses. Each has two representations, which are interchangeable. Making it 2¹⁶¹ representations.

Nope. There is no way we could generate more than said 2¹⁶⁰ 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 2¹⁶⁰ 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 2⁹⁶ private keys to each address". (Which I now believe is not true, because there are actually 2⁹⁷ 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.  

And yes, looking at 2¹⁵⁹ private keys means we will compute 2¹⁶⁰ 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

[Its_a_Meeeee]

I reject and denounce myself  

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 2¹⁶⁰ addresses  
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  


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]

6b2749936df41b73239c1c823642c0a82af74ab6:c:priv:000000000000000000000000000000000000000000000000000a489a332ff001 + 0xfbf

[rico666]

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

2⁹⁷

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

Learning so much in this thread :-)

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


Rico

[unknownhostname]

f152befd8c60892eb296e937266bf9f3e38f2c5a:u:priv:000000000000000000000000000000000000000000000000000a78990f8ff001 + 0xfba

[Real-Duke]

f152befd8c60892eb296e937266bf9f3e38f2c5a:u:priv:000000000000000000000000000000000000000000000000000a78990f8ff001 + 0xfba

And our daily easter egg give us today 

[unknownhostname]

f9362f7da717b421680e31a0fdc61b8a6c7118ca:u:priv:000000000000000000000000000000000000000000000000000aaa676bdff001 + 0xfff

[TooDumbForBitcoin]

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.

[coinableS]

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 

[rico666]

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 

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.


Rico

[unknownhostname]

d328b3189f7d8f39ec758abbcf6ef6c3a92f9f4f:u:priv:000000000000000000000000000000000000000000000000000adbedc72ff001 + 0xfb2

[TooDumbForBitcoin]

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


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.

[josh5]

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