To me a "valid" address is one that has a private key.
The checksum verification of an address does not warrant that a private key exist for that address.
Hence my post above: the point represented by the public key MUST be on the ellptic currve.
In short,
1/you can random type an address with a valid checksum
2/ funds can be sent to that address because miners will get it on the blockchain
3/Nobody will ever spend those funds again because there is no private key for that address: the bitcoins on that address are lost for ever
Topic: What are the chances of an address collision? and what happens when it does? - page 4. (Read 22436 times)
August 30, 2012, 01:47:54 AM
August 29, 2012, 04:07:17 PM
Not to hijack the thread, cuz i'm sure other people will read and be curious abut his too: But can some one quickly explain why its also very unlikely to accidentally type a valid Bitcoin address. They are 33 (32 unique) case-sensitive alpha-numeric digits (Base 58). Only a subset of all possible combinations are valid addresses. What is the method and explanation for this?
The address contains a 32 bit checksum. So a typo will most likely result in a bad checksum. Node compute the checksum to ensure the address is valid so "most" typos will simply produce an invalid address which will be rejected by your client, other nodes, and miners. In theory you could create a sequence of typos that also produces a valid but incorrect address but the odds are roughly 1 in 4 billion.
Quote
Can some one also explain how if a public address is a sha hash of a public key, how can an address be signed by the owner of the privkey, if the public address can't be reversed into the full public key (the key pairs are 256 bit ECDSA right? Should be loner than 32 characters).
Technically the address isn't signed. A message is signed by the private key. The signature can be verified by the public key. The signature contains the public key. The address can be verified by recreating it from the public key.
August 29, 2012, 03:11:35 PM
Not to hijack the thread, cuz i'm sure other people will read and be curious abut his too: But can some one quickly explain why its also very unlikely to accidentally type a valid Bitcoin address. They are 33 (32 unique) case-sensitive alpha-numeric digits (Base 58). Only a subset of all possible combinations are valid addresses. What is the method and explanation for this?
Can some one also explain how if a public address is a sha hash of a public key, how can an address be signed by the owner of the privkey, if the public address can't be reversed into the full public key (the key pairs are 256 bit ECDSA right? Should be loner than 32 characters).
Since a bitcoin public key is in fact a pair of coordinates for a point on the elliptic curve, it's not surprising that only a subset of the possible address strings happen to be a hash of valid coordinates.
Plus there is a checksum attached to it.
It would be a miracle to random type a valid bitcoin address.
August 29, 2012, 02:43:30 PM
An address collision would be a SHA256 collision
And if you find a SHA256 collision then bitcoin is the last of our problem
And if you find a SHA256 collision then bitcoin is the last of our problem
Technically it would be a RIPEMD160(SHA256(SHA256())) collision. Not nitpicking, it's an important distinction given that the last step in that process yields 2^160 possible addresses instead of 2^256. 96 bits of keyspace ain't no joke son.
Not to hijack the thread, cuz i'm sure other people will read and be curious abut his too: But can some one quickly explain why its also very unlikely to accidentally type a valid Bitcoin address. They are 33 (32 unique) case-sensitive alpha-numeric digits (Base 58). Only a subset of all possible combinations are valid addresses. What is the method and explanation for this?
Can some one also explain how if a public address is a sha hash of a public key, how can an address be signed by the owner of the privkey, if the public address can't be reversed into the full public key (the key pairs are 256 bit ECDSA right? Should be loner than 32 characters).
August 29, 2012, 02:02:59 PM
But probability also says, I could have a success on my first run? isn't it?
Yes, especially if you do all the calculations very very deliberately and careful by hand with paper and pencil. 
August 29, 2012, 01:51:58 PM
But probability also says, I could have a success on my first run? isn't it?
Yes. You should play the lottery.
August 29, 2012, 01:15:54 PM
Oh duh, it's the Base58Check that does that part.
August 29, 2012, 01:15:07 PM
Yes but that is just the formatting. The address is still a 160 bit hash of the public key (plus some version info & checksums) expressed as a modified Base58 string.
August 29, 2012, 01:12:04 PM
Quote
Technically it would be a RIPEMD160(SHA256(SHA256())) collision. Not nitpicking, it's an important distinction given that the last step in that process yields 2^160 possible addresses instead of 2^256. 96 bits of keyspace ain't no joke son.
Don't we also discard uppercase I's and lowercase L's and O's and zeroes?
August 29, 2012, 01:08:58 PM
When we get faster than light travel and trillions of people across the galaxy each need thousands of addresses it is still unlikely. After millions of years when it eventually happens, the average amount in the address will be far far less than 1 satoshi.
August 29, 2012, 01:07:20 PM
But probability also says, I could have a success on my first run? isn't it?
It's a lot more likely that you're struck by lightning or a meteor. So get your priorities straight and worry about that.
and even if you are EXTREMELY lucky and hit a collision , chances are there will be zero coins in it. Most addresses are used once ( or a few times ) and have nothing in them...
August 29, 2012, 01:04:03 PM
An address collision would be a SHA256 collision
And if you find a SHA256 collision then bitcoin is the last of our problem
And if you find a SHA256 collision then bitcoin is the last of our problem
Technically it would be a RIPEMD160(SHA256(SHA256())) collision. Not nitpicking, it's an important distinction given that the last step in that process yields 2^160 possible addresses instead of 2^256. 96 bits of keyspace ain't no joke son.
August 29, 2012, 12:58:22 PM
An address collision would be a SHA256 collision
And if you find a SHA256 collision then bitcoin is the last of our problem
And if you find a SHA256 collision then bitcoin is the last of our problem
August 29, 2012, 12:52:13 PM
Generating the addresses is one thing....
What if checking the balance for each and every key takes just as long? It might take 10x as long.
What if checking the balance for each and every key takes just as long? It might take 10x as long.
August 29, 2012, 12:50:59 PM
approximately 3,720 to 1
August 29, 2012, 12:47:58 PM
You are, however, much better off generating collisions on various deterministic wallets like brainwallets etc... there are plenty of people out there who do not get it why some passwords/keys must be strong.
If lucky you will teach some punks a good lesson BTW.
If lucky you will teach some punks a good lesson BTW.
August 29, 2012, 12:47:26 PM
Every time this questions pops up people start flooding the board with zeros. Scientific notation people!
That's because most folks who don't already understand how big 2^160 is also don't understand how small 3e-38 is. The zeroes drive the point home.
August 29, 2012, 12:44:45 PM
So finding a collision on your first try is roughly equivalent to being hit by lightning 16,540,000,000,000,000,000,000,000 times per second for an entire year or winning the lottery 830,000,000,000,000,000,000,000,000,000 times.
August 29, 2012, 12:42:52 PM
Chance are negligible. If collision occurs with a funded address, attacker you can transfer funds elsewhere.
Chances are still negligible when 1 billion people are using it? also can't I just run some kind of bots, that randomly generate addresses to see if
they have funds in them?
Yes, chances remain negligible. You could run your bot, but it'd be a waste of electricity. Chances are you'd wait the lifetime of the universe before finding a collision.
But probability also says, I could have a success on my first run? isn't it?
Sure, you could absolutely find a success on your first run, but let's apply probability to your scenario.
Let's say there are a billion people using 10 addresses each for 10 billion total addresses.
This means that each address you generate has a (1/2^160)*10,000,000,000 possibility of holding a balance, giving your first attempt a 0.0000000000000000000000000000000000000684% chance of finding a collision on your first attempt.
You are correct in stating that with each try it will either happen or it won't, there is no in-between state, and you're correct in stating that it's possible. It's also bad news for the account holder that a collision would give you control of those funds.
Comparatively speaking, your odds of being struck by lightning in a given calendar year are about 1 in 280,000. The odds of winning my local lottery are about 1 in 176,000,000. So finding a collision on your first try is roughly equivalent to being hit by lightning 16,540,000,000,000,000,000,000,000 times per second for an entire year or winning the lottery 830,000,000,000,000,000,000,000,000,000 times.
If you find a collision I would stay indoors and play the lottery.
August 29, 2012, 12:37:36 PM
But probability also says, I could have a success on my first run? isn't it?
It's a lot more likely that you're struck by lightning or a meteor. So get your priorities straight and worry about that.
Jump to: