Bitcoin Forum
March 19, 2024, 11:39:00 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: Bitcoin Address Collisions  (Read 23878 times)
NewLibertyStandard (OP)
Sr. Member
****
Offline Offline

Activity: 252
Merit: 268



View Profile WWW
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
Every time a block is mined, a certain amount of BTC (called the subsidy) is created out of thin air and given to the miner. The subsidy halves every four years and will reach 0 in about 130 years.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1710848340
Hero Member
*
Offline Offline

Posts: 1710848340

View Profile Personal Message (Offline)

Ignore
1710848340
Reply with quote  #2

1710848340
Report to moderator
1710848340
Hero Member
*
Offline Offline

Posts: 1710848340

View Profile Personal Message (Offline)

Ignore
1710848340
Reply with quote  #2

1710848340
Report to moderator
1710848340
Hero Member
*
Offline Offline

Posts: 1710848340

View Profile Personal Message (Offline)

Ignore
1710848340
Reply with quote  #2

1710848340
Report to moderator
ec
Newbie
*
Offline Offline

Activity: 7
Merit: 66


View Profile WWW
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 (OP)
Sr. Member
****
Offline Offline

Activity: 252
Merit: 268



View Profile WWW
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
Merit: 66


View Profile WWW
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
Merit: 6610


View Profile
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 (OP)
Sr. Member
****
Offline Offline

Activity: 252
Merit: 268



View Profile WWW
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
Merit: 6610


View Profile
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
Merit: 10



View Profile
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
Legendary
*
Offline Offline

Activity: 2772
Merit: 1019



View Profile
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)

PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0  3F39 FC49 2362 F9B7 0769
matt.collier
Member
**
Offline Offline

Activity: 105
Merit: 10



View Profile
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
Legendary
*
Offline Offline

Activity: 1302
Merit: 1024



View Profile
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.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
error
Hero Member
*****
Offline Offline

Activity: 588
Merit: 500



View Profile
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.

3KzNGwzRZ6SimWuFAgh4TnXzHpruHMZmV8
RustyShackleford
Newbie
*
Offline Offline

Activity: 43
Merit: 0



View Profile
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
Merit: 10



View Profile
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
Legendary
*
Offline Offline

Activity: 5138
Merit: 12565


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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Gavin Andresen
Legendary
*
Offline Offline

Activity: 1652
Merit: 2164


Chief Scientist


View Profile WWW
May 23, 2011, 02:48:29 PM
Last edit: May 24, 2011, 08:38:20 AM by gavinandresen
 #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).

How often do you get the chance to work on a potentially world-changing project?
da2ce7
Legendary
*
Offline Offline

Activity: 1222
Merit: 1016


Live and Let Live


View Profile
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.

One off NP-Hard.
error
Hero Member
*****
Offline Offline

Activity: 588
Merit: 500



View Profile
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.

3KzNGwzRZ6SimWuFAgh4TnXzHpruHMZmV8
molecular
Donator
Legendary
*
Offline Offline

Activity: 2772
Merit: 1019



View Profile
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.

PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0  3F39 FC49 2362 F9B7 0769
Luke490
Newbie
*
Offline Offline

Activity: 7
Merit: 0


View Profile
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:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!