https://en.m.wikipedia.org/wiki/Pigeonhole_principle
> On Mar 29, 2019, at 22:02, Eric Voskuil <eric@???> wrote:
>
> It’s called a hash collision when you generate a value that creates the same hash as another value. Hash collisions are inevitable when you take large data and squeeze it into a smaller value.
>
> e
>
>> On Mar 29, 2019, at 21:33, Mike Miller <mike@???> wrote:
>>
>>
>> I'm sorry, I'm very much a newbie here and I'm surely using the wrong terminology. Please forget I ever used the word "collision". Let's break it down in dumb words I can understand:
>>
>> (1) It is my understanding that there are just so many possible private keys that this "power of large numbers" is what secures my bitcoin, in effect. Again I may not be using precisely the right words, but that seems to be the gist of it. Ref:
>> - https://learnbtc.tech/PowerOfLargeNumber.jpg
>> - https://www.youtube.com/watch?v=ZloHVKk7DHk
>>
>> (2) Based on the idea in #1, I had the idea to use libbitcoin ("bx") to use "bx" to:
>> (a) generate a random private key
>> (b) derive a public key from said private key
>> (c) derive a bitcoin address from said public key
>> (d) check for any unspent inputs at said bitcoin address
>>
>> (3) The idea was that if I never found anything it made my nimble brain feel better about this crazy "big number" stuff, and thus feel better that my bitcoin is safe. (I understand this is rather silly, for a variety of reasons, but it was a fun experiment anyway).
>>
>> (4) I ran this in an infinite loop a zillion times for 18 months, and eventually one of the private keys "bx" generated mapped to an address that contained someone's bitcoin.
>>
>> (5) I was led to believe (due to the above links, for example) that the probability of this ever happening was like winning the PowerBall lottery a million times in a row, or something. So when my script turned up someone's bitcoin, it shocked me.
>>
>> (6) Given that the probability of what just happened is so low, it occurred to me that perhaps the "random" seed generated by "bx" isn't so random, or some other technical vulnerability that's above my pay grade. Maybe the person who owns the bitcoin I found also used a wallet or tool that employed libbitcoin or something similar, and due to the pseudorandom nature of it, the odds of my finding something were significantly increased. But even if that's true, it does frighten me a bit that some other schmuck like me, scripting out a few lines of code, can find and steal my bitcoin. (At this point I'm mostly trusting the random seed my Trezor generated for me for my BTC).
>>
>> (7) In my mind, the possibilities are (a) I just hit the Powerball a million times in a row and this would never again happen in my lifetime, or (b) something else I'm not technically able to conceive of.
>>
>> (8) Given that I'm using libbitcoin to generate my addresses for this exercise, I thought to bring this to your attention on this mailing list. I'm not technical enough to posit that there's anything wrong with libbitcoin, so please don't think that's what I'm claiming here. I haven't a clue.
>>
>> I hope this helps clear things up. Mainly I'm looking for someone to tell me why I shouldn't be nervous about what happened.
>>
>> Thanks.
>>
>> -Mike
>>
>>
>>> On Fri, Mar 29, 2019 at 7:45 AM Neill Miller <neillm@???> wrote:
>>> Hello,
>>>
>>> I believe Mike's claim is that using 'bx seed' he generated a random
>>> number, converted to a private key and found a bitcoin balance there.
>>>
>>> While likely as unlikely, it's not exactly the same as an address
>>> collision, where a hash of some different public key collides via hash
>>> function with a duplicate address.
>>>
>>> Mike, can you clarify? The "address collision" subject does make me
>>> wonder if it's the latter and I've misinterpreted.
>>>
>>> -Neill.
>>>
>>> On Fri, Mar 29, 2019 at 01:00:35PM +0700, Eric Voskuil wrote:
>>> > It is possible for you to prove hash collision once the output is spent by its owner. Simply obtain the public key from the input script and then show that your public key also hashes to the same value.
>>> >
>>> > The probability of you having found a collision are much higher than you having found the same public key, and if the keys don’t match you indeed probably found a collision.
>>> >
>>> > e
>>> >
>>> > > On Mar 29, 2019, at 06:29, Mike Miller <mike@???> wrote:
>>> > >
>>> > > Hmm, I had a feeling someone might question the veracity of my claim. And you're right, there's no wait for me to prove it happened. I'm rather shocked about it, personally, given the probabilities involved. I'm no expert on these matters, and thought I'd bring it to your attention in case there was some sort of vulnerability. If not, I think I'll go and spread my bitcoin around a bit more thinly given that "guessing" a private key appears to be possible. More baskets for my eggs, as it were.
>>> > >
>>> > > -Mike
>>> > >
>>> > >
>>> > >> On Thu, Mar 28, 2019 at 7:20 PM Eric Voskuil <eric@???> wrote:
>>> > >> Libbitcoin seeding wouldn’t contribute to an increased likelihood of finding a hash collision. For example, a poor seeding algorithm, such as one that less-than-randomly duplicates values, would only make finding a collision *less* likely. The best approach for collision finding may be to just increment from zero (ie avoiding duplicates).
>>> > >>
>>> > >> Unfortunately it’s impossible to verify this claim, so I’d take it with a bit of salt. On the other hand hash collisions do happen. It’s just a matter of probability.
>>> > >>
>>> > >> e
>>> > >>
>>> > >> > On Mar 29, 2019, at 05:43, Neill Miller <neillm@???> wrote:
>>> > >> >
>>> > >> > Hello Mike,
>>> > >> >
>>> > >> > Interesting find!
>>> > >> >
>>> > >> > It's true that the "bx seed" command provides psuedo-random numbers
>>> > >> > provided by the OS. The intent of all libbitcoin commands is to never
>>> > >> > generate randomness internally where necessary (and to rather accept
>>> > >> > randomness as an input where needed), but "bx seed" is an exception,
>>> > >> > mostly for example purposes. To be clear, we don't recommend using it
>>> > >> > for strong cryptographic purposes (of which generating Bitcoin private
>>> > >> > keys is one such example).
>>> > >> >
>>> > >> > It is quite possible that's a reason for the collision, or at least
>>> > >> > that's my best guess at the moment.
>>> > >> >
>>> > >> > That said, I have run similar sorts of programs (more optimized than
>>> > >> > what's shown) for extended periods of time in the past out of
>>> > >> > curiosity and also to 'convince' myself of the same thing you were
>>> > >> > thinking about, and never produced a result like yours. I know we're
>>> > >> > not the only ones who have tried this as well :-)
>>> > >> >
>>> > >> > -Neill.
>>> > >> >
>>> > >> >> On Thu, Mar 28, 2019 at 05:32:27PM -0400, Mike Miller wrote:
>>> > >> >> Approximately 18 months ago I became fascinated with the magic of extremely
>>> > >> >> large numbers and that this is basically what's protecting my bitcoin.
>>> > >> >>
>>> > >> >> e.g. https://learnbtc.tech/PowerOfLargeNumber.jpg
>>> > >> >>
>>> > >> >> In an effort to somewhat "prove" this to myself, I whipped up a script to
>>> > >> >> run an endless loop generating random public/private keypairs (using the
>>> > >> >> libbitcoin library) and checking the received "balance" at each address,
>>> > >> >> and to email me if anything was found. Naturally this script never seemed
>>> > >> >> to "find" any bitcoin. This was comforting to me, as it meant that my
>>> > >> >> bitcoin was relatively safe from others doing the same thing.
>>> > >> >>
>>> > >> >> The meat of the loop is:
>>> > >> >>
>>> > >> >> $bx = '/usr/local/bin/bx'
>>> > >> >> $private_key = `$bx seed | $bx ec-new|$bx ec-to-wif`
>>> > >> >> $public_key = `$bx wif-to-public $private_key`
>>> > >> >> $address = `$bx ec-to-address $public_key`
>>> > >> >> $balance = `$bx fetch-balance $address`
>>> > >> >>
>>> > >> >> I completely forgot about this script, but it's been running all this time
>>> > >> >> (~18 months), just running in an infinite loop on my desktop linux box.
>>> > >> >> This morning I woke up to a surprise email that something had been found.
>>> > >> >>
>>> > >> >> balance
>>> > >> >> {
>>> > >> >> address 1CeuzQcb5pmM1PmyoDgV5rfPsJDkAY8ScR
>>> > >> >> received 1965000
>>> > >> >> spent 0
>>> > >> >> }
>>> > >> >>
>>> > >> >>
>>> > >> >> I used electrum to "import" the associated private key to verify this
>>> > >> >> amount was accessible. But I didn't move it -- of course I don't want to
>>> > >> >> steal the poor guy's BTC.
>>> > >> >>
>>> > >> >> I'm a little bit blown away here. I thought the known universe would hit
>>> > >> >> end of life before finding anything. If I can get this lucky finding a
>>> > >> >> needle in a haystack with few lines of Perl code, I don't feel quite as
>>> > >> >> safe about my bitcoin.
>>> > >> >>
>>> > >> >> Or might this mean that, despite the fact that it took 18 months to produce
>>> > >> >> a collision, there might be something nonrandom about the seeding mechanism?
>>> > >> >>
>>> > >> >> It says mine is Version: 4.0.0, which was the latest version at that time.
>>> > >> >>
>>> > >> >> Thoughts?
>>> > >> >>
>>> > >> >> -Mike
>>> > >> >
>>> > >> >> _______________________________________________
>>> > >> >> Libbitcoin mailing list
>>> > >> >> Libbitcoin@???
>>> > >> >> https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/libbitcoin
>>> > >> >
>>> > >> > _______________________________________________
>>> > >> > Libbitcoin mailing list
>>> > >> > Libbitcoin@???
>>> > >> > https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/libbitcoin
>>> > >> _______________________________________________
>>> > >> Libbitcoin mailing list
>>> > >> Libbitcoin@???
>>> > >> https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/libbitcoin
::
Re: [Libbitcoin] address collision?
