Topic: Large Bitcoin Collider (Collision Finders Pool) - page 6. (Read 193396 times)

The well-distributedness of ripemd160 is much more important! It is the last time we cross the deck.

A curious fact: even if sha-256 was well-distributed, the 2^257 public keys (compressed and uncompressed) would "hit" about 86.5% of the 2^256 possible 256 bit strings  (output of sha-256). From the compressed public keys we use today (2^256) we could get with sha-256 only the 63% of the possible 256 bit strings.

That means that some (very few) collisions happen already at sha-256 level.

Never say never...

What makes you pinpoint this to the well-distributedness of SHA-256? Why is everyone neglecting the poor RIPEMD-160? It needs attention too!

@RIPEMD160 Come here darling. No one loves you but me.

No, actually, I have multiple theories and I'm not married to any of them.  If the SHA-256 algo is indeed well-distributed, then yes, they are probably low-entropy original keys.  If SHA-256 is not well-distributed, then some or all of those non-puzzle hits could be collisions.  You're not going to tell me that you know for certain that SHA-256 is well-distributed.

We will never know....

More importantly, the crux of this conversation started with the 'intent' of the LBC, and that is very clearly to find collisions

No, I believe that the private key found is identical to the private key originally used, hence this is not a collision.  LBC just found the original private key.

I think we both agree that it is obviously possible for two keys to hash to the same Bitcoin address.  In fact, as we agreed, there are approximately 2⁹⁶ keys for every address so of course, yes, collisions are possible.

Where we disagree is:  you think that these private keys that were found by LBC are possible collisions.  I do not.

You can waste your time trying to prove that it was a collision.  It is your time to waste.  I am perfectly happy with the simple explanations I have given.  Your position (that they are collisions) is highly improbable.  My position is highly probable.  

How about we talk more specifically.  Exactly which private keys do you think are possible collisions?

I just don't understand what it is that people here think "collision" means.  The definition is precisely what you typed above.  Two keys that generate the same hash.  Does the euphemism of collision not register at all?  The address a found key opens was obviously created by another key right?  So if they can open an address then two keys exist!  Hence, collision   Sure, maybe they hit the actual key on some low-entropy addresses, but their mission statement isn't to find these low-entropy addresses, they are looking for duplicate keys.  Collisions!

Almost all Bitcoin addresses generated from private keys in the 2¹⁶⁰ through 2²⁵⁵ range will probably alias to Bitcoin addresses generated by private keys in the 2⁰ through 2¹⁵⁹ range by the definition of Bitcoin addresses.  So, no, they are not looking for "collisions" in that sense you suggest.  They just know they will find almost all the possible Bitcoin addresses by the time they reach 2¹⁵⁹ so they will not need to search 2¹⁶⁰ through 2²⁵⁵ once they have already searched 2⁰ through 2¹⁵⁹.

This is all a moot point anyway as getting to 2¹⁵⁹ is beyond their reach at the current time.

The LBC is publicly stating its mission to unlock coins in blockchains, therefore they're naturally in pursuit of "collisions".  You can reframe this precise pursuit as "iterating through the possible keys", but that is merely the literal action that fulfills the purpose of finding collisions.  Why is it necessary to resist the notion of 'collision searching' when it's merely a different spin on 'pursuing keys for known addresses'?  What they've posted are theoretical collisions by their own definition.  They state that they are looking for alternate keys in the 0 - 2^159 range to open addresses that may have been generated in the 2^160-up range.  If that isn't collision-seeking then I don't know what is. 

As to my "fraudulent" assertion, without the low-entropy addresses, it's supposed to be statistically damn-near impossible to find even 'one' key that could unlock any of the addresses they seek.  Therefore, the claiming of THREE working keys purports to one of the three hypothesis' I stated, one of them being that they were already known keys, which is fraud with the intent of portraying the LBC as more effective than it really is.  I'm not saying they are indeed lying about it, but this option can't be removed from the table.

ok, we agree on that, but you're also assuming that all hashes can be a product of a key, where I'm suggesting that we don't know just how many of the 'potential' hashes actually have a key.  In other words, the realm of hashes may be much smaller than we realize and this could be why so many keys appear to be working.

'blind-faith' refers to someone believing that an algorithm does what you're told it will do, without actually understanding every nuance of the algorithm.  Forgive me if I assume that you couldn't speak to the inner-workings of SHA-256, because without a doubt, most people couldn't begin to follow the methodology and motivations buried in it.  That being said, encryption history is littered with failed algorithms because someone found a flaw in it, completely neutralizing its efficacy.  Your denying of my hypothesis follows a very long line of people that were convinced that the status quo was also unbeatable, but were wrong.  You may be right, for now.

Undoubtedly in pursuit of the low entropy targets.

The LBC is not posting "collisions".  It is posting the private keys that contain or contained BTC.  Since they started at private key 1 and are iterating sequentially through the private keys your notion of "fraudulent" makes no sense.  Yes, someone can send BTC to an address created from a private key in the range being searched by LBC - and people have.  I would not consider that fraud by any definition I know.  LBC is not claiming to have found a collision.  They are only claiming to have found used addresses in the lower private key range they are searching.
 
If by hash you mean a Bitcoin address then there are approximately 2⁹⁶ private/public key pairs that map to every Bitcoin address.  This is a well known fact.  So, yes every hash has multiple keys, in fact approximately 2⁹⁶ keys.

If by "in blind faith" you mean "trust in the math of very large numbers, the laws of probability, and the integrity of SHA-256" then I do deny your hypothesis that this is anything other than a simple bad RNG, a code bug, or someone screwing around and putting BTC there to be found by LBC or something similar.

Probably not.  They are pretty set in their ways - their ways being start with private key 1, then try 2, then try 3, etc.

Fraudulent was a reference to the credibility of the posted collisions on the LBC trophy page.  Someone may have just posted their known keys, though this strikes me as very unlikely

I'm merely suggesting that your hypothesis isn't the only hypothesis.  It may be that hashing algorithms don't uniformly distribute the results across the full spectrum of possible hash values, leading to the notion that a hash can have multiple keys.  If we shifted the LBC's testing range into a higher range of bits, then any further unverified collisions would support the hypothesis that the hashing algorithm is faulty.  At this time, we have no way to distinguish low-entropy key artifacts from hashing algorithm artifacts.  You can choose to deny my hypothesis in blind faith, but the SHA-256 algorithm for example, is a gnarly beast with lots of gears and levers; would be pretty hard to ascertain the biases it introduces into the results.  

If there's any way to compel the LBC to shift to a different range of keys, we could possibly put this to rest

Yes, I understand that.  I guess what I am really trying to say is that with the entropy of the private key found by LBC so obviously defective the likely and obvious scenario is that this was a defective RNG or bug in the private key generation.  So, why all the fuss over this as a possible collision?  Makes no sense to me.  Just sounds like a bunch of people off on a tangent.

If we found a private key capable of unlocking funds on a address, there would be only 2 possibilities to be sure we have found a real collision:

1) the owner of the address sends us its private key, and that key is different from ours

2) the address has already exposed its public key on the blockchain (there is a transaction from that address to another); in this case it would be trivial to verify if our public key and that public key are different or not. We could have a collision even if we don't know the other private key.

In each case by "collision" we mean 2 different public keys (and then 2 different private keys) with the same hash160.

These addresses contained BTC.  LBC has proved beyond a shadow of a doubt that the entropy of the private key used to generate these addresses was extremely, defectively, low.  This has absolutely nothing to do with the hashing algorithm.  Hashing has to do with the calculation of the public Bitcoin address after the private key is selected and after the public key has been calculated from the private key.

Since the private key found was extremely defective the only rational explanation is that the private key found by LBC is the actual private key that was used to generate the public key which was then hashed (by perfectly adequate hashing algorithms) to the public Bitcoin address.  Whether the random number generator was defective or this was done on purpose cannot be established.  BTW people writing code have been known to make mistakes and screw up their random number generators in many ways.

The private key is the private key.  I am having a hard time understanding how this has anything to do with hashing or collisions, whether "fraudulent" or not, whatever that means.

I've been mulling the likelihood of a poor entropy source and this just seems unlikely to me, unless it was intentional.  Someone with a full understanding of entropy would have intentionally sidestepped the common algorithms for generating addresses.  I'm also concerned that this explanation will become the indisputable answer to any collision found.  It may be that the LBC needs to shift its focus away from the 0 - 2^159 range and maybe move up that 160-bit window a few digits just to possibly dissuade these rationalizations.

In summary, here are the possible explanations that I see:

1) the collisions are outright fraudulent
2) they're a product of low entropy key generators (disprovable/provable by moving the LBC test range higher)
3) hashing algorithms are not as well-distributing as we believe them to be, causing multiplicity in working keys per address

Is this LBC real and mathematically provable? How do I participate and get rewarded?

Nobody knows if the 3 addresses with bitcoins we found so far are collisions. Given that the probability to get a real collision so soon is very very very low, my guess is that they aren't real collision, but only addresses generated by a poor entropy source. In that cases I think we have found simply the "original" private keys used to generate that addresses. The problem is that the owners didn't show up.

I totally agree that proof of a collision requires two keys, but given the difficulty of procuring such, does it inherently mean we categorically dismiss unverified collisions?  That's rather draconian, particularly since this LBC experiment is the first means by which we can actually verify some of the assumptions the world has placed upon the efficacy of hashing algorithms. 

I swear I've read somewhere that money was returned to someone as a result of this process, but I can't find that reference now.  It does appear that nobody has proffered up those original keys though, based upon what leads LBC's website offer.  Thus, I'm grasping at straws on bitcointalk to see if there is such evidence.  Failing evidence, and instituting the blind faith in the quality of hashing algorithms, it appears as if those purported 3 unverified collisions were fraudulent.  That's hard to digest given the number of people involved, but probably not impossible with a smoke and mirrors show. 

If anyone can add legitimacy to those unverified collisions, please do contribute.

Just to be clear - what is necessary to show that any meaningful collision happened, is to publish 2 different(!) private keys that create the same address: one key initially used by whoever owns/owned these funds and the new one found by LBC. If you want to troll them, just waste a few spam transactions on a some keys that will be found by the pool soon. Anyone can do that, it just costs a little money.

It would be a waste of time and effort though, especially on such an endeavor...

What do you mean, returned? There was no money returned so far...

Yes, the majority of those were related to the puzzle, but there were three apparently legitimate collisions on that trophy page where the funds were possibly returned to the owner, thus we might have access to both private keys.  I'm speaking specifically to those.  And I define "collision" as finding a key that hashes to a known address, not necessarily requiring evidence of the original key that generated that address.  I'd rather call something an "unverified collision" than a "non-collision" in the absence of proof, so that the proper scrutiny can be placed on it instead of just dismissed, because the implications of it being legitimate are industrially profound.

There were 0 "collisions", just 54 private keys that are meant to be brute-forced by the author of the Puzzle transaction. You can see the found private keys here: https://lbc.cryptoguru.org/trophies.

Hey folks.  Huge debate on XRPChat about the credibility of the LBC collisions on the trophy page (https://www.xrpchat.com/topic/12998-is-ripple-vulnerable-to-a-collision-attack/).  For those collisions where money was returned to the original owner, could we see both the owner's and discovered private keys so that we can verify the legitimacy of the collisions?