Bitcoin Forum

That shouldn't be very probable, should it?

I used Bitcoin Qt client, pressed "New address" button to generate the address, sent a small amount to it and then checked on blockchain.info if the transaction was registered. To my surprise there are two other transactions made over a year ago using that address.

https://blockchain.info/address/1J9UHx3q9D1ZxZ5KwV8VGWJd7ksyTJtLTB

It should not happen but there is nothing stopping it from happening.

Surely not, show us the transaction

This should be so astronomically unlikely as to never happen...

Was there any btc stored on that address from before you used it?

Wow this would be a first recorded case I am guessing. Can you share the public address?
Theoretically, there's nothing stopping an address collision but the chances are extremely slim especially at such an early stage in the lifecycle.

Updated my first post with the address.

I had to enter a unique label before creating the address and enter a pass phrase for the wallet, so I'm pretty sure it's not one of my old addresses.

I'm not suffering from any memory lapses or hallucinations either.

When you create an address does it leave a timestamp in your wallet, like when it's been created, so as I could double check it's a brand new one?

Thats actually due to a bug which is fixed in git: it asks for the pass phrase totally unnecessarily when you request a new address.
It is _always_ a old one from the keypool.

Open up the debug console (help->debug window->console), type in:

gettransaction 5aed0ce301ecd17b237be9bd0dda7fa8fb7e2eb7f453c2ca1f27de160a23c791

If it returns that old transaction then that key was already in the wallet when that transaction hit your client.

There are ages on keys too, but off the top of my head the only way I think you can get them is if you dumpwallet and IIRC thats only in git.

Other questions: have you restored a wallet from a backup at any point, used salvagewallet, or pywallet?

This.

Edit nvm, I see it now!

When I do this, I see some transaction info. I didn't restore my wallet.

Still, I don't understand what you mean by saying it's always an old address from the keypool.

When I press "New address" button does it generate a brand new address that no one used before?

Bitcoind always keeps a keypool with 100 (?) addresses which is pregenerates. Every time you request a new address it pulls it from this pool and adds a new one to the pool. The idea is to make backups more effective (but deterministic wallets such as Armory uses are way better for this).

Couldn't I hypothetically create a script that systematically generates bitcoin addresses from the pregenerate pool and have the script lookup the generated address to see if the wallet is active with a balance then choose to spend this into a new wallet address?

No, it should return an address your own wallet previously generated that you've never used before. Unclean shutdowns, wallet corruption, salvagewallet, or restoring a backup could cause it to issue an address to you twice, however.  I've never heard of a local replay before outside of these circumstances.

Can you look back through your records and confirm that

78f929d6fd5461cea8a64b1867cbc45b39c3119495b18aff313e9024c025092c was really a transaction paying you and/or
5aed0ce301ecd17b237be9bd0dda7fa8fb7e2eb7f453c2ca1f27de160a23c791 was really a transaction with you paying some place?

E.g. if you were selling coins at mtgox at that time, go look at your mtgox deposit records on 2012-07-07?

If this IS an actual collision...
Well, the next one probably won't be for a thousand years.

It‘s impossible.

It is statistically possible, but the possibilty is so small that we don't expect to really see it happens.

Are you *sure* you didn't own that address already?

If not, it is VASTLY more probable you (and however generated this address before) just unearthed a bug in bitcoin's PRNG. Could you give more details - which OS and OpenSSL you have installed?

I find it *extremely* hard to believe you actually caused a collision. Not now, not in a 1000 years.

My records go back to 2011 but I don't see any transactions made in Jun or Jul 2012 at all and I didn't use mtgox in 2012.

I also do not see any mention of those two other addresses involved in previous transactions in my wallet.

I will assume that some kind of glitch made the client to reuse that address twice, that's more probable than a collision I guess.

Thank you!

Bad number generator anyone? Is that the second time for Bitcoin QT? Are they just using whatever the operating system spits out with no additional randomness added?

Wow... didn't think it would ever happen

1. What OS and version of the client are you using? Could be a previously unknown bug in the random number generator.

2. Also, verify that you do own the private key to that address. Try to send that 0.1 BTC to another address of yours.

This.

Bad PRNG is more likely than collision. And we have had at least one corrupted RNG de-bugs thrown up by Bitcoin already, so it's got form.

OpenSSL on linux has had issues with generating weak keys in the past http://perimetergrid.com/wp/2008/05/17/ubuntudebian-crng-cracked-ssh-vulnerable/ .... and also it has been mentioned that introducing compromised code to produce weak keys via bad RNGs is an attack used by the spooks (for communication interception).

How well can OpenSSL ECC keys generation really be trusted? Does it depend on version of OpenSSL, use of underlying RNG, OS, etc? Is anyone testing this for bitcoin specific key generation?

(That whole crap fight over ECC not going into RH-derivative linux OpenSLL module makes me smell smoke ... maybe it was never about the patent non-problem?)

Edit: https://www.schneier.com/blog/archives/2008/05/random_number_b.html (https://www.schneier.com/blog/archives/2008/05/random_number_b.html)

History doesn't repeat but it sure does rhyme sometimes ...

Wasn't there a reward being offered to the first person to do this?

It's called address trawling, but if you could wrap your head around how statistically improbable you are to find a wallet with a balance, even scanning millions of addresses per second, you'd go buy a lotto ticket instead.

It is so improbable that if it really happened it's alarming...

This, please verify the ownership.

Yep, looks like he owns it ... shit this is not good for Bitcoin Qt :(

If true talk about no bueno...no bueno whatsoever!

A coredev should look into this ASAP...

Bad PRNG or user error
/thread

Finally it means that two address owners share the same address with different private keys. Then where are tansfers going to ?

Anyone with a private key to a public address can spend coins transferred to that address. If two people hold a private key with the same public address, they can both spend the coins.

It doesn't mean this

Guys could you please actually read the thread before posting? This is not a bad PRNG and NOT an address collision. This is a problem with the OP's wallet. It is recycling old addresses he has already used:

This is the one thing that can't happen.

It didn't happen  ;D

hmm this sort of act is what causes me to download the original qt client.  Now I'm on the hunt to build a script IDK about the statistics anymore.

Why not ? When I use https://www.bitaddress.org (https://www.bitaddress.org) offline it can theoretically produce the same addresses. Is there anything preventing this szenario ?

I can theoretically be teleported to Mars because of quantum tunelling
Would you respond "Why not ?Is there anything preventing this szenario ?" to someone telling me "it can't happen" ?

My bet is Bitcoin-Qt went haywire and used a change address. ::)  For whoever asked the keypool size is 100  ;) but it can be changed by the user.

@OP: did your wallet balance increase when you generated that address? If not, then it's a previous address of yours. If it did, err, wow…

it's impossible* to generate an address already used.

what happened here is that the user had already used the address for a change address sending a transaction, or mining - and when he clicked 'generate' it just assigned that.

I repeat - it's impossible* for this to happen.

Will

* practically impossible - i.e. 1 in 2^160 which is less chance that you entering every lottery worldwide every week since lotteries were invented and winning the jackpot each time.

You just drew that out of your ass right now, didnt you?   :D

yup!  Totally out of my ass, because I know that it's not possible to comprehend odds so astronomical as 2^160 so anything I can write down will be more likely.

Will

It wouldn't have. That isn't how the software works. This is why doing a gettransaction is a pretty useful: had it just generated an address that was used before the wallet wouldn't know about any of the transactions. But in this case it did.
What am I?  Chopped liver?

In any case, people need to relax. See my prior post. This looks like he managed to get an address out of key-pool twice, e.g. due to some error in losing the write that marked the key spent after an unclean shutdown. (Or pilot error of some kind, e.g. generate a new one, then mis-click on the copy and copy an old one instead)

IT IS POSSIBLE to generate address which is already used when you use weak passphrase to generate private key.
This already happened because the flaw in Android random number genretator.
Another example is brainwallet (http://brainwallet.org/). Just look at 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T (https://blockchain.info/address/1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T), This address is in hundreds wallets belonging to different people.

If the 50 BTC was not your transaction, then it's a collision. 

LOL, Zeroday is mixing up brainwallets with passphrases as seeds and the password used for encrypting the wallet in Bitcoin-QT :)

Incidentally, don't add this address to your own wallet just to test it.  I can assure you this is a really bad idea, because, well. . .just because.

I think he could throw in getting struck by lightning on the way to the convenience store to purchase each winning ticket, then getting struck by lightning again on the way back home, every time, and still be within tolerances.

iirc 1 in 2^160 is correct. Therefore I don't really believe this topic. Interesting though, although there is no way to prove anything either way :)


Edit:

May be this image helps clarify this for some people:

https://i.imgur.com/vCkuFAY.jpeg

I think it's somewhat less, actually, because of the birthday problem.  It's not the odds of a 160 bit hash colliding with one arbitrary address, but with every currently existing address.  The odds are still astronomical but would require estimating the number of currently existing addresses in use.

ETA:  This being the odds of us ever "seeing" a collision.  It's also entirely possible there would be a collision but it would never even be noticed, because either the other "owner" of the address never used it, or because the new "owner" never bothered checking.  (Possible but, of course, very, very unlikely.)

Fck'n saved! Nice one!

Ente

2^161

Wow!  Did it on my first try!

I meant exactly passphrase as seed, not the password of Bitcoin-QT which is obviously not involved in the generation of private key.

Duplicate private keys can also be generated if there is some flaw in seed generation like it was on Android.

it keeps happening?lol

anything is possible, i wonder if you could bruteforce an old addy into someone elses client throught compromised hijack?

all address are unique you cant generate the same address

read op he just did!!!  :o

Wrong.  All addresses are probably unique, to a high degree of probability and it is entirely possible to generate the same address, especially using a method like brainwallet with a poor passphrase, or using a broken PRNG.  There is absolutely nothing other than chance preventing generating the same address, assuming robust PRNG.

Somethings up with this post.

OP said he sent small amount to address but that was timestamped on 10/20 yet the OP is on 10/19? Is that a UTC thing or is he BS'ing?

I suggest he proves to us he controls the private key for this address by publicly making another tx to this of 0.123 and then immediately redeeming.

Thats not the right way to ask someone to do that, the right way would be to ask them to perform a signmessage (file->signmessage plug in the address, and "this is alikim on bitcointalk", and post the signature and the exact message used). But I don't see any reason to doubt that this address is the OPs. I suspect you have your local timezone set in the forum, his post appears to be >10 minutes after the transaction to me.

Why was this moved back out of the technical support area?  Is the purpose of this thread to spread (apparent misplaced, see my prior posts) concerns or is it actually to figure out whats up technically?

Do we actually know what happened?

Proving he controls the private key proves nothing. As gmaxwell said there is no reason to doubt he owns the address. He could also be trolling us all, having knowingly used the address in the past. Since we're talking about the likelihood of explanations that is yet another one more likely than a collision and also a bad PRNG in Bitcoin-qt I'd say. No offense to the OP of course. Just an objective observation.

See the thread. The transaction was already in his wallet (thats what the gettransaction checks for), which wouldn't have been possible if a duplicate address had just been generated.  We don't know what exactly happened but there are several other hypothesis which are more consistent with the facts than there being an actual duplicate address generated.

E.g. a unclean wallet shutdown made it miss flagging that address as used, thus resulting in it handing it out again, or a mouse mis-targeting resulted in the OP generating an address but then copying another.

Also, now that the newly received coin has been spent we can see that both the new instance and old instance used the same public key (03a97dfbd26061494c9369cd469f8422f7c5f16e4fd6b4da42e42138e711f7fd6f), which means that it's 256 bits involved, not just 160. (E.g. if your hypothesis was a chance collision the probability of that is now 79,228,162,514,264,337,593,543,950,336 times lower than before we knew for sure that he was using the same public keys).

A collision didn't happen here, I'd stake my life on it gladly.  With respect to a bad PRNG, things are possible, but the code in Bitcoin-qt has been audited by many people (including myself personally) and that seems unlikely (also, if it were to happen, considering the design I would expect consecutive duplicate addresses and not just one).

I added it (well I added the correct horse battery staple one but I'm assuming zeroday's talking about it) and lost the ability to listunspent :). pywallet to the rescue…

You could but it would be a huge waste of time and resources. 

 ::)

http://t.imgbox.com/abmz5QMq.jpg (http://imgbox.com/abmz5QMq)

Told you it was a bad idea ;-)  And yes, I was also talking about the correct battery horse staple one.  The one with the sample sentence from the Brainwallet article in the wiki is pretty similar.

Ah no, this was a couple of weeks ago. Your advice came too late :).

this plus the fact that the OP doesn't seem to want to prove he owns the address answers the question for me.

The odds for duplicate address aren't "only" 1 in 2^160. It's similar to the birthday paradox, where it only takes 23 people for a 50% probability

Sure, but there are only 365 possible birth dates. Not 2^160 ;) (which is more than 2.74 * 2^157 times as much)

yes but whos is keeping a tally on current Bitcoin users and of those how many have many instances!~then the bot address exploiter/sniffers,,, double spending hybrids dust generation blah blah blah Gavin will save us!  ;D

If gmaxwell is willing to type something like this in the forum I'm pretty sure he feels so strongly for a reason. I'm breathing a sigh of relief that's for sure!

*Have to say it was also refreshing to see how many veteran's and coredev's jumped on this immediately...gives me a great deal of confidence in bitcoin as a whole given the level of quality and attention to detail being given 24/7.

Yes, but there are also more than 23 addresses in use.

The odds are 1 - ((2^160-1)/2^160) * ((2^160-2)/2^160) * ((2^160-3)/2^160) * ((2^160-4)/2^160) * ... repeating for the # of addresses already generated

The answer to this has nothing to do with faith or how people feel, but with a numeric library

posting to keep updates on this thread. What actually happened? If the OP made a 50 BTC transaction on that address, shouldn't he remember? Thats a large amount, even in 2012.

U r kind of a celebrity now. One day I'll create a thread titled "I know a guy who generated an address that already existed".