Topic: Large Bitcoin Collider (Collision Finders Pool) - page 16. (Read 193143 times)

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


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.


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


Rico

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

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

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,


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

f86b1dd782990bafba34c28c88d4c7ff9ce99641:c:priv:000000000000000000000000000000000000000000000000000a1835db9ff001 + 0xf87

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

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

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

It is more like


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

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.

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

You have a different idea (different from mine) of the situation:

you think that there are 2^135 addresses (space search) and that there is surely the address you are looking for. If this is the model, you cannot use the geometric distribution, because it admit you could never find that address.

Probability 1/2^135 doesn't mean that you will get surely your address after 2^135 tries.

But if you want to think in this way, I wrote this formula :

https://www.dropbox.com/s/bulinnhroay5cg2/Probability%20of%201%20collision%20for%20k.pdf?dl=0


EDIT: I made a mistake, I computed another probability 
 
Use your formula. Shame we have lost 10-15 "0" in 1 day!!! 

This is how I see it now:

* we assume our total_search_space is 2^{159 - lb(num_adr)} ~ 2^135.17 (total until 1st collision)
* search_space_to_do = total_search_space - search_space_done
* Probability for the next key to be a collision is 1 / search_space_to_do
* The sum of the next-key probabilities for the keys done (estimated) in the following 24h is the probability we want to display.

For simplicity, we can assume linear behavior of the probabilities within the next 24h, therefore the sum is

1/2 * (probability of the last key in the 24h + probability of the 1st key in the 24h) * keys done in the 24h

If anyone has a different opinion, I will implement a rand(very low number) and finito!  

Going to implement the above now.


Rico

It would not be faster (like it would by 0.00000001%) than what we are doing now by looking at ALL
addresses. The probability to find a collision for ANY of these (currently ~ 15 million) addresses
is currently under discussion as you can see above. Let's call it X.

The probability of finding one specific in these 15 million is ... well ... X/15million.


Rico

That sounds like the equivalent of searching for an entire address in vanitygen.  I don't know the exact probability but you'll probably need multiple universes.

Is it possible to technically focus only on 1  btc address ?

What are the probability mathematically to find the private key ?

Yes, it is right.



You have to use Bayes' theorem and/or conditional probability. Give me some time, I think about it.

And that may also not be right, because it could be "51.32 of 159" (keys vs. addresses)
Or "51.32 of 135.2" (until 1st collision)
or "51.32 of X" (if we have good estimates if and how the SHA256 and RIPEMD160 functions are not Uniform.

Pick one.


Rico

Yes arulbero you are right thanks!

I misunderstood the expression of the number there.
I think what you want to show/express on the page is the chance of collision in the daily (approximated) workload, right?
I was more focused on the progressive chance which would answer the question: "what chance did we have so far".
The answer is also on the page: "search space covered:    51.32 of 160 bits" 

Got what i wanted!

That seems right. So:

We have 2^135.2 Bernoulli trials, where we - for simplicity now - claim, that the probability to observe the event "collision" is 1 after all these trials were done. Ok?

So: 1 - (1 - p)^k for the number we want to show. Yes?

k is the number of trials left to do (that's our 2^space - 2^done)

and probability is simply 1/2^space. Yes?

Can someone check/confirm so I can hack that in?


Rico