Bitcoin Forum
June 21, 2024, 12:00:49 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1]
1  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 13, 2017, 01:49:07 PM
No disrespect to RIPEMD-160, I'm just a one-hash kind of guy

I believe that the findings of the LBC are too easily dismissed as low-entropy original key hits, and the real benefit of this project is being lost.  If full entropy key ranges were explored (all bits utilized in the keys), then any collisions discovered would portend to a weakness in the hash's distribution, and hence blockchains would be considerably more exposed than currently thought.  Is this not the overarching intent of the LBC?  Or is it to chase low-hanging fruit while spooking people with the notion that addresses are crackable?
2  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 13, 2017, 05:13:32 AM
The address a found key opens was obviously created by another key right?
Where we disagree is:  you think that these private keys that were found by LBC are possible collisions.  I do not.

...

How about we talk more specifically.  Exactly which private keys do you think are possible collisions?
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
3  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 13, 2017, 04:01:59 AM
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.

Almost all Bitcoin addresses generated from private keys in the 2160 through 2255 range will probably alias to Bitcoin addresses generated by private keys in the 20 through 2159 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 2159 so they will not need to search 2160 through 2255 once they have already searched 20 through 2159.

This is all a moot point anyway as getting to 2159 is beyond their reach at the current time.

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 Smiley  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! Smiley
4  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 12, 2017, 11:10:18 PM
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.
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.

If by hash you mean a Bitcoin address then there are approximately 296 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 296 keys.
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.

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

If there's any way to compel the LBC to shift to a different range of keys, we could possibly put this to rest
Probably not.  They are pretty set in their ways - their ways being start with private key 1, then try 2, then try 3, etc.
Undoubtedly in pursuit of the low entropy targets.
5  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 12, 2017, 08:54:34 PM
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.

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
6  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 12, 2017, 07:01:03 PM
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'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
7  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 12, 2017, 05:41:06 PM
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.
8  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 12, 2017, 04:28:21 PM
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.
9  Bitcoin / Project Development / Re: Large Bitcoin Collider (Collision Finders Pool) on: December 12, 2017, 03:33:32 PM
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?
Pages: [1]
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!