Bitcoin Forum
October 21, 2017, 01:53:03 AM *
News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Detecting an address collision?  (Read 2173 times)
tkbx
Sr. Member
****
Offline Offline

Activity: 322



View Profile
October 12, 2013, 03:20:08 AM
 #1

I know that two people generating the same address (maliciously or accidentally) is about as likely as the Sun and the Moon instantaneously switching places, destroying the solar system. But, if it were to happen, is there any way to detect it so it can be observed?
1508550783
Hero Member
*
Offline Offline

Posts: 1508550783

View Profile Personal Message (Offline)

Ignore
1508550783
Reply with quote  #2

1508550783
Report to moderator
1508550783
Hero Member
*
Offline Offline

Posts: 1508550783

View Profile Personal Message (Offline)

Ignore
1508550783
Reply with quote  #2

1508550783
Report to moderator
1508550783
Hero Member
*
Offline Offline

Posts: 1508550783

View Profile Personal Message (Offline)

Ignore
1508550783
Reply with quote  #2

1508550783
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1508550783
Hero Member
*
Offline Offline

Posts: 1508550783

View Profile Personal Message (Offline)

Ignore
1508550783
Reply with quote  #2

1508550783
Report to moderator
1508550783
Hero Member
*
Offline Offline

Posts: 1508550783

View Profile Personal Message (Offline)

Ignore
1508550783
Reply with quote  #2

1508550783
Report to moderator
JoelKatz
Legendary
*
Offline Offline

Activity: 1582


Democracy is vulnerable to a 51% attack.


View Profile WWW
October 12, 2013, 03:21:58 AM
 #2

I know that two people generating the same address (maliciously or accidentally) is about as likely as the Sun and the Moon instantaneously switching places, destroying the solar system. But, if it were to happen, is there any way to detect it so it can be observed?
No known method. Any such mechanism operating on real physical computers would have a failure rate much higher than the probability of a real collision, so the vast majority of detected collisions would be so likely to be false positives, it wouldn't even be worth investigating them.

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
pand70
Sr. Member
****
Offline Offline

Activity: 476



View Profile
October 12, 2013, 03:38:58 AM
 #3

I know that two people generating the same address (maliciously or accidentally) is about as likely as the Sun and the Moon instantaneously switching places, destroying the solar system. But, if it were to happen, is there any way to detect it so it can be observed?

Well if it is to happen you 'll detect it instantly because the whole planet will become incinerated.

BurtW
Legendary
*
Offline Offline

Activity: 2058

All paid signature campaigns should be banned.


View Profile WWW
October 12, 2013, 04:03:36 AM
 #4

If you generate a new address and it already has BTC in it, or a history of BTC transactions, then you have a collision.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
dree12
Legendary
*
Offline Offline

Activity: 1246



View Profile
October 12, 2013, 04:14:10 AM
 #5

Address collisions are far from rare. In fact, they happen all the time. We've already seen and observed thousands, if not more, collisions merely in the past.

In general, randomly-generated addresses do not collide. However, a lot of addresses are not randomly-generated.

There collisions vary in type. Most of them are from using brainwallets with weak passwords. Accidental collisions of this type are possible, but the vast majority of these collisions results from a network of bots searching weak passwords to steal any money sent there. These bots are programmed to do just three things: make addresses, detect collisions, and steal money. Even accidental collisions from humans making new brainwallets with taken passwords are often detected, as the person who imports the wallet finds a sum already stored on it. So for this type of collision, to answer your question, detection or observation is certainly possible, and indeed practised all the time.

Some collisions are from exploiting weaknesses in random number generators. The android wallet glitch is a recent example of this phenomenon. Attackers who find these weaknesses, once again, do "random" address creation en masse and check each generated address for a collision. So, once again, collisions are not only possible to detect but actually actively being detected.

Address collisions of other types fall under the same reasoning. The vast majority of collisions has been and will continue to be from attackers and malicious users, and these users would not exist without a possibility of detecting the collision.

TL;DR? Yes.
genjix
Legendary
*
expert
Offline Offline

Activity: 1232


View Profile
October 12, 2013, 05:31:45 AM
 #6

Yeah cool but we all know he meant randomly. OP, only if the 2 people also spent Bitcoins from that address and put different public keys in their inputs. Then we'd hash them to the same address, be like holy fuck, just accept fate and then forget the incident as an oddity. Generating the same public key by chance: no way unless the alg (as dree said) sucks.
Sword Smith
Sr. Member
****
Offline Offline

Activity: 364


Sirius Money - Sirius about Bitcoin


View Profile WWW
October 12, 2013, 05:01:23 PM
 #7

If you have a computer searching for an address collission (lots of RAM and SHA256-optimized ASIC), you should be able to generate an address collission. Assuming that ECDSA, SHA256, and ripeMD160 are perfect in that they have a homogenous sample space, there are 2160 different addresses. So for a 50 % chance of a coillission, you only need sqrt(2160) = 280 addresses. That is about 1024 which is "only" a million billion billion addresses and at 160 bit per address that requires 160 million billion gigabytes of storage. I expect these hash and memory requirements will be reached in my lifetime. But for a collission to be useful, there needs to be bitcoins in the address. Assume there are (or will be) 1.5*1010 addresses (two per person on the earth) with bitcoins on them then you need to look through 1.5*1048 / (1.5*1010) = 1038 to have a 50 % (plus/minus) chance of finding an address with bitcoins on it. And this might never be accomplished. 1038 is one hundred billion billion billion billion addresses.

dree12
Legendary
*
Offline Offline

Activity: 1246



View Profile
October 12, 2013, 05:05:14 PM
 #8

If you have a computer searching for an address collission (lots of RAM and SHA256-optimized ASIC), you should be able to generate an address collission. Assuming that SHA256 and ripeMD160 are perfect in that they have a homogenous sample space, there are 2160 different addresses. So for a 50 % chance of a coillission, you only need sqrt(2160) = 280 addresses. That is about 1024 which is "only" a million billion gigahashes. I expect these hash and memory requirements will be reached in my lifetime.

You can certainly generate 280 addresses with hardware available in a decade, but you need to store them to be able to detect a collision. Not going to happen in the next 20 years. So you can assure yourself that you have generated a collision with 99.999999999% certainty, but you won't be able to publish the two private keys which led to that collision.
Sword Smith
Sr. Member
****
Offline Offline

Activity: 364


Sirius Money - Sirius about Bitcoin


View Profile WWW
October 12, 2013, 05:07:38 PM
 #9

If you have a computer searching for an address collission (lots of RAM and SHA256-optimized ASIC), you should be able to generate an address collission. Assuming that SHA256 and ripeMD160 are perfect in that they have a homogenous sample space, there are 2160 different addresses. So for a 50 % chance of a coillission, you only need sqrt(2160) = 280 addresses. That is about 1024 which is "only" a million billion gigahashes. I expect these hash and memory requirements will be reached in my lifetime.

You can certainly generate 280 addresses with hardware available in a decade, but you need to store them to be able to detect a collision. Not going to happen in the next 20 years. So you can assure yourself that you have generated a collision with 99.999999999% certainty, but you won't be able to publish the two private keys which led to that collision.
You are of course right. I edited my answer to elaborated on that point. You would probably have to store the addresses in the RAM though but I still contend that it is likely to happen, or be possible, in my lifetime.

johnscoin
Member
**
Offline Offline

Activity: 105


View Profile
October 12, 2013, 06:11:08 PM
 #10

That Is what I am also concerned
jl2012
Legendary
*
Offline Offline

Activity: 1694


View Profile
October 12, 2013, 08:07:44 PM
 #11

I know that two people generating the same address (maliciously or accidentally) is about as likely as the Sun and the Moon instantaneously switching places, destroying the solar system.

No, with so-called "brain wallet", it may not be that rare.

But, if it were to happen, is there any way to detect it so it can be observed?


It's just like using one wallet.dat on 2 computers: both and see and spend the balance of the address.

If you still do not understand, import this key to your bitcoin client: 5KJvsngHeMpm884wtkJNzQGaCErckhHJBGFsvd3VyK5qMZXj3hS (you'd better use an empty wallet to try this)

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Sword Smith
Sr. Member
****
Offline Offline

Activity: 364


Sirius Money - Sirius about Bitcoin


View Profile WWW
October 12, 2013, 09:11:59 PM
 #12



No, with so-called "brain wallet", it may not be that rare.

But, if it were to happen, is there any way to detect it so it can be observed?


It's just like using one wallet.dat on 2 computers: both and see and spend the balance of the address.

If you still do not understand, import this key to your bitcoin client: 5KJvsngHeMpm884wtkJNzQGaCErckhHJBGFsvd3VyK5qMZXj3hS (you'd better use an empty wallet to try this)
Ahh. SHA256("correct horse battery staple") Smiley

I once made a very insecure address, something like SHA256("make me money ASAP") and asked a friend to test it by sending a tiny amount. He sent 3.5 BTC! Lucky for me, it was unused at the time and no one else was sitting with the private key. That, however, taught me that the entropy of all addresses should always be at least 170 bit. No exceptions.

Sword Smith
Sr. Member
****
Offline Offline

Activity: 364


Sirius Money - Sirius about Bitcoin


View Profile WWW
October 14, 2013, 08:59:11 PM
 #13

Can anyone explain to me what would happen in the following (highly theoretical event)?

An address with public key "pubkey1" belongs to an address "add1" and "user 1" sends bitcoins from this address and thus publishes "pubkey1". Another user, "user 2" generates another private key which gives "pubkey2" but it just happens that the corresponding address to this "pubkey2" happens to be "add1". "User 2" then sees that there is already bitcoins in "add1" and tries to spend these bitcoins. Can "user 2" spend from this address without "pubkey1" which has already been published, or is the public key "locked in" when bitcoins are sent from the address the first time?

My guess is that "user 2" would be able to spend the bitcoins on "add1" even though the public key is different than the one already used for this address. Do anyone know?

JoelKatz
Legendary
*
Offline Offline

Activity: 1582


Democracy is vulnerable to a 51% attack.


View Profile WWW
October 14, 2013, 09:45:02 PM
 #14

My guess is that "user 2" would be able to spend the bitcoins on "add1" even though the public key is different than the one already used for this address. Do anyone know?
Yes, that's correct. The test is whether the hash is correct, and it is.

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
Sword Smith
Sr. Member
****
Offline Offline

Activity: 364


Sirius Money - Sirius about Bitcoin


View Profile WWW
October 14, 2013, 09:50:46 PM
 #15

My guess is that "user 2" would be able to spend the bitcoins on "add1" even though the public key is different than the one already used for this address. Do anyone know?
Yes, that's correct. The test is whether the hash is correct, and it is.
Ok. But the old public key ("pubkey1") is still stored somewhere in the blockchain but the clients would just ignore this inconsistency?

gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
October 14, 2013, 10:03:07 PM
 #16

Ok. But the old public key ("pubkey1") is still stored somewhere in the blockchain but the clients would just ignore this inconsistency?
The node may not even have that data at all.  It's not an inconsistency. The scriptpubkey in the spent transaction required you to satisfy certain rules, and the transaction did.

Bitcoin will not be compromised
Sword Smith
Sr. Member
****
Offline Offline

Activity: 364


Sirius Money - Sirius about Bitcoin


View Profile WWW
October 14, 2013, 10:08:28 PM
 #17

Ok. But the old public key ("pubkey1") is still stored somewhere in the blockchain but the clients would just ignore this inconsistency?
The node may not even have that data at all.  It's not an inconsistency. The scriptpubkey in the spent transaction required you to satisfy certain rules, and the transaction did.
Got it. Thanks for the answer.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!