Bitcoin Forum
April 25, 2014, 07:37:09 AM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2  All
  Print  
Author Topic: Bitcoin Address Collisions  (Read 7982 times)
NewLibertyStandard
Sr. Member
****
Offline Offline

Activity: 252



View Profile WWW

Ignore
February 23, 2010, 03:46:44 AM
 #1

Although extremely unlikely, what would happen if two Bitcoin clients generated the same Bitcoin address? Would payments be delivered to whichever client encountered the payment first? If there is a mechanism in place to prevent such collisions, please explain it.

Treazant: A Fullever Rewarding Bitcoin - Backup Your Wallet TODAY to Double Your Money! - Dual Currency Donation Address: 1Dnvwj3hAGSwFPMnkJZvi3KnaqksRPa74p

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

Posts: 1398411429

View Profile Personal Message (Offline)

Ignore
1398411429
Reply with quote  #2

1398411429
Report to moderator
1398411429
Hero Member
*
Offline Offline

Posts: 1398411429

View Profile Personal Message (Offline)

Ignore
1398411429
Reply with quote  #2

1398411429
Report to moderator
1398411429
Hero Member
*
Offline Offline

Posts: 1398411429

View Profile Personal Message (Offline)

Ignore
1398411429
Reply with quote  #2

1398411429
Report to moderator
ec
Newbie
*
Offline Offline

Activity: 7


View Profile WWW

Ignore
February 23, 2010, 08:25:17 AM
 #2

For two addresses to be equal, two identical private/public elliptical curve (ec Smiley) keys have to be generated. Without looking at the source code, let's assume the probability for this is 2^(-128) for a keyspace of 128 bits. See here for a perspective on how probable it is with a 122 bit collision.

However, if something similar to the Debian ssl-scandal happens, similar keys could indeed be generated. The effect of an individual generating an existing key, is (if I understand it correctly) in effect to make a copy of wallet.dat. Not good at all, but not devastating for all the members of the p2p network.
NewLibertyStandard
Sr. Member
****
Offline Offline

Activity: 252



View Profile WWW

Ignore
February 23, 2010, 09:22:47 AM
 #3

Are you referring to the private key which is generated the first time a person runs Bitcoin? If someone were to successfully duplicate someone else's key then after they downloaded all the blocks, they would have the same balance as the person with the original key. That's what you're saying, right?

I was referring to the custom Bitcoin addresses which you can label with the name of the person who is going to send you bitcoins so that you know from whom the payment came. I think these addresses are generated from the private key mentioned previously. I'm wondering about collisions because although they are very unique, they are easily generated over and over again by all by all bitcoin clients.

Treazant: A Fullever Rewarding Bitcoin - Backup Your Wallet TODAY to Double Your Money! - Dual Currency Donation Address: 1Dnvwj3hAGSwFPMnkJZvi3KnaqksRPa74p
ec
Newbie
*
Offline Offline

Activity: 7


View Profile WWW

Ignore
February 23, 2010, 04:17:56 PM
 #4

Are you referring to the private key which is generated the first time a person runs Bitcoin? If someone were to successfully duplicate someone else's key then after they downloaded all the blocks, they would have the same balance as the person with the original key. That's what you're saying, right?

Yes, that is correct. They would share the wallet, and it becomes a race on spending the money first.

I was referring to the custom Bitcoin addresses which you can label with the name of the person who is going to send you bitcoins so that you know from whom the payment came. I think these addresses are generated from the private key mentioned previously. I'm wondering about collisions because although they are very unique, they are easily generated over and over again by all by all bitcoin clients.

If I read the source code correctly, keys are always made in pairs. That means, every address has an associated private key. When you click "New Address", you call GenerateKey in main.cpp, which generates a new key pair. So the duplicate address is ultimately a duplicate public key. Which is very unlikely.

While keys still are "easily generated", you should have to generate a whole lot of keys before a collision. While I am not certain, it seems that the keys generated have a space of 256 bits, which is a lot more than the 122 bits put in perspective in the wikipedia article on uuids. Remember, 123 bits have half the probability of collision as 122 bit, 124 half of that again etc.
satoshi
Founder
Sr. Member
*
Offline Offline

Activity: 364


View Profile

Ignore
February 23, 2010, 04:26:09 PM
 #5

There's a separate public/private keypair for every bitcoin address.  You don't have a single private key that unlocks everything.  Bitcoin addresses are a 160-bit hash of the public key, everything else in the system is 256-bit.

If there was a collision, the collider could spend any money sent to that address.  Just money sent to that address, not the whole wallet.

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block.  You could have got a lot more money by generating blocks.

The random seed is very thorough.  On Windows, it uses all the performance monitor data that measures every bit of disk performance, network card metrics, cpu time, paging etc. since your computer started.  Linux has a built-in entropy collector.  Adding to that, every time you move your mouse inside the Bitcoin window you're generating entropy, and entropy is captured from the timing of disk ops.
NewLibertyStandard
Sr. Member
****
Offline Offline

Activity: 252



View Profile WWW

Ignore
February 23, 2010, 07:04:47 PM
 #6

Thanks for the explanation. I think it all makes sense.

Are generated bitcoins encrypted with whichever address is currently displayed in the main Bitcoin window? I may have mentioned this in an email message quite a while ago, but it would be cool for some very future version to allow people to see which of their bitcoins are encrypted with which of their addresses.

Treazant: A Fullever Rewarding Bitcoin - Backup Your Wallet TODAY to Double Your Money! - Dual Currency Donation Address: 1Dnvwj3hAGSwFPMnkJZvi3KnaqksRPa74p
satoshi
Founder
Sr. Member
*
Offline Offline

Activity: 364


View Profile

Ignore
February 23, 2010, 10:24:00 PM
 #7

Are generated bitcoins encrypted with whichever address is currently displayed in the main Bitcoin window?
No, each generated transaction uses a new, single-use address.

Nothing uses the address in the main window, it's just there for convenience for you to copy.  0.2.5 has a "New..." button next to it to make it easy to change each time you use it.
matt.collier
Member
**
Offline Offline

Activity: 105



View Profile

Ignore
May 22, 2011, 03:28:33 PM
 #8

Are we using a 160 bit hash (which provides for the possibility of a collision) vs a 224/256 bit hash (no possibility of a collision) so that bitcoin addresses can be shorter in length?  If so, is it possible for us to transition to using a 256 bit hash at some later date?

I don't buy the argument that it's TOO computationally expensive to intentionally create a collision.  We have already seen the use of GPUs radically alter the bitcoin mining paradigm.  In the future, we may well see devices designed specifically for the task of performing hashing functions.  Perhaps those devices already exist. 

Why build the opportunity for fraud into bitcoin?  I don't think we need to be concerned about the  number of characters of a bitcoin address when we're copying and pasting them or using QR codes anway.
molecular
Donator
Hero Member
*
Offline Offline

Activity: 1190



View Profile

Ignore
May 22, 2011, 04:32:11 PM
 #9

Are we using a 160 bit hash (which provides for the possibility of a collision) vs a 224/256 bit hash (no possibility of a collision) so that bitcoin addresses can be shorter in length?  If so, is it possible for us to transition to using a 256 bit hash at some later date?

I don't buy the argument that it's TOO computationally expensive to intentionally create a collision.  We have already seen the use of GPUs radically alter the bitcoin mining paradigm.  In the future, we may well see devices designed specifically for the task of performing hashing functions.  Perhaps those devices already exist. 

Why build the opportunity for fraud into bitcoin?  I don't think we need to be concerned about the  number of characters of a bitcoin address when we're copying and pasting them or using QR codes anway.

Don't worry, "If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block.". This means, if you have a computer that is 1 million times as powerfull as all current miners combined, it will still take an average of 1,618,542,460,620,902,128,345,579,373 years to generate a collision.

Even if Moores law holds true in the most generous way, we still have over 100 years left before this becomes feasable.

And also: yes, devices designed specifically for performing bitcoin mining exist (Artforz had himself some ASICs (custom chips) made)

matt.collier
Member
**
Offline Offline

Activity: 105



View Profile

Ignore
May 22, 2011, 05:24:53 PM
 #10

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions?  Will we be able to move to a 224/256 bit hash if and when the need arises, even if it's 100 years from now?
kjj
Hero Member
*****
Offline Offline

Activity: 1036


Bitcoin Foundation - Lifetime Member


View Profile

Ignore
May 22, 2011, 07:05:48 PM
 #11

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions?  Will we be able to move to a 224/256 bit hash if and when the need arises, even if it's 100 years from now?

You could use 4096 bit hashes, and still get a freak accident in 5 minutes.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
error
Sr. Member
****
Offline Offline

Activity: 462



View Profile

Ignore
May 22, 2011, 07:21:04 PM
 #12

It's far more likely that every single miner on the network will all find a block at exactly the same time.

15UFyv6kfWgq83Pp3yhXPr8rknv9m6581W
RustyShackleford
Jr. Member
*
Offline Offline

Activity: 42



View Profile

Ignore
May 22, 2011, 07:42:42 PM
 #13

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions?  Will we be able to move to a 224/256 bit hash if and when the need arises, even if it's 100 years from now?

I'm not a programmer, I don't work on bitcoin code, but I do understand how both of those things work. I'm going to say "yes". It might take everyone moving to Bitcoind v2.1.744 in the year 2121; but it really doesn't sound THAT difficult.
matt.collier
Member
**
Offline Offline

Activity: 105



View Profile

Ignore
May 22, 2011, 08:02:58 PM
 #14

In 2006, the NIST made this recommendation:

Quote
Federal agencies should stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010.

http://csrc.nist.gov/groups/ST/hash/policy.html
http://en.wikipedia.org/wiki/SHA-2

If an electronic currency isn't an "application that requires collision resistance", I don't know what is.
theymos
Administrator
Hero Member
*
Offline Offline

Activity: 1540


View Profile
May 23, 2011, 06:33:35 AM
 #15

In 2006, the NIST made this recommendation:

Quote
Federal agencies should stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010.

http://csrc.nist.gov/groups/ST/hash/policy.html
http://en.wikipedia.org/wiki/SHA-2

If an electronic currency isn't an "application that requires collision resistance", I don't know what is.

That recommendation was made because SHA-1 is cryptographically weak. RIPEMD-160 is generally considered to be about equal in strength to truncated SHA-2.

Gavin Andresen
Hero Member
*****
Offline Offline

Activity: 1330


Chief Scientist


View Profile WWW

Ignore
May 23, 2011, 02:48:29 PM
 #16

RE: moving to another hashing algorithm for bitcoin addresses:

Did you read what Satoshi wrote?

If you want to make money, you are far, far, far, far, far, far better off using your hardware to generate blocks than trying to find a bitcoin address collision and steal bitcoins.  Potential address collisions are not a weakness, and switching to another algorithm would be just busy-work for us developers who should be spending time on REAL weaknesses (like figuring out how to make bitcoin more secure against trojans and viruses).

Will I see you in Amsterdam?
  http://bitcoin2014.com/
da2ce7
Hero Member
*****
Offline Offline

Activity: 1022


Live and Let Live


View Profile

Ignore
May 24, 2011, 06:09:59 AM
 #17

Instead of stopping the address collisions, we should focus on *every other doomsday scenario* because they are all way more likely.

Banking Software? I develop it: Open-Transactions
       Windows Open-Transactions Builds
error
Sr. Member
****
Offline Offline

Activity: 462



View Profile

Ignore
May 24, 2011, 06:23:46 AM
 #18

I wonder if I could just set my GPU to generating all possible addresses... no wait, that won't work.

15UFyv6kfWgq83Pp3yhXPr8rknv9m6581W
molecular
Donator
Hero Member
*
Offline Offline

Activity: 1190



View Profile

Ignore
May 24, 2011, 08:24:16 PM
 #19

I wonder if I could just set my GPU to generating all possible addresses... no wait, that won't work.

It'll work fine. You can even proove it will finish. It'll just take a loooong time.

Luke490
Newbie
*
Offline Offline

Activity: 7


View Profile

Ignore
June 09, 2011, 06:15:21 AM
 #20

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block.  You could have got a lot more money by generating blocks.

What if your network of computers already generated and tested all the possible blocks?
Sure the address haystack of possibilities is much bigger and harder to test... but if the other haystack(block generating) has bean fully counted what else is there to do?
Pages: [1] 2  All
  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!