Bitcoin Forum

No description! ;D
If you understand the question then only, I'd consider your answer right. :P

A public address X will map to a private Key Y

RIPEMD-160(SHA-256(Y))  =  X

Some addresses (X) will have multiple (Y) that will work due to "collisions" in the hash algorithm.

RIPEMD-160(SHA-256(Y  ))  =  X
RIPEMD-160(SHA-256(Y1))  =  X
RIPEMD-160(SHA-256(Y2))  =  X
... maybe more

The chances of finding/generating these collisions is astranomically small, maybe some other member might know the actual chances?

Yes a single ECDSA Public key correspondences to a privite key this is due to the Elliptic property using finite field and point addition. makes it unique. 

However after the Key is hashed to a base58 i do have my skepticism, as probability of collision is possible but that would be like getting hit by a lightning sitting in a Faraday cage.  (Note i have not looked into this probability, just my assumption)

there are ~2^256 private keys
and only 2^160 addresses

so, there are about 2^96 private keys for each address.

OMG !!! Is it so ? I can transfer a fund out of an address using 2^96 private keys ?

No, only a modest number >= 1 out of the 2^256 priv keys will map to any given public key address.

The fact that multiple will map is due to "collisions" in the hash func.

We do not need to match public key! And it is not "given" to us by funding transaction!.
Funding transaction gives us 20-byte address which is "somefunc (privkey)"
And we have 32-byte space to find privkeys.

In average.
But it is quite difficult to find a privkey which will converts to the given address :)

yes, I corrected my above post.

but just to make clear:


no, the number of private keys that will unlock any given public address is MUCH less than 2^96

I don't know the average number, somebody probably does though?

Yes, the property of collision resitance means there will only be one private key that maps to any particular public key

Why?
There are ~2^256 private keys
The address is some kind of hash function of private key
So we do a map from 2^256 values to 2^160 hashes
If the hash function is really good - we will receive the same hash value for ~2^96 different private keys (sometimes slightly more, sometimes slightly less)

Hmmmm... I see what you are saying, sorry for my prior misunderstanding amaclin :P

Of course! There are only 160 bits of public addresses space.

To understand with an extreme example: If there were only 2 bits of address space then only 4 possible public addresses, and of course no matter what hash func you apply to 256 bits, it would have to reduce down to 1 of those 4 public addresses. So in this example you could hash any random 256 bit privkey and ~ 1 in 4 times hit a winner.

=========================

So I stand corrected:

On average ~2^96 private keys will unlock any single address.  :o

The effective privkey space one needs to search is "only"  ~2^160 before you get a hit on average. Perhaps a few bits less due to collisions.

But it's not like we can just chop off 96 bits from privkey space before we search, valid privkeys will be scattered "randomly" throughout the 256 bit space.

=========================

And lets think of some ways to increase the chances of unlocking some coin:

One could check against the list of the richest 2^16 (64k) addresses, further reducing the number of hashes required to 144 bits.

With average luck you would hit jackpot when ~50% through search, so 1 bit less = 143 bits.

To try 2^143 hashes at 10TH/s ~=
35,357,599,566,417,147,294,418 Years.

Universe age ~=
13,798,000,000 years

So still very safe against logical brute force attack.

Wrong (same as I was)

Even with a perfect hash function that has no collisions:

~2^96 private keys will map to a given public address.

Sorry. My English is much worse than my math skills  ;D

Your English is great! I was just a dunce ;D

Dude, you're Russian.  ;D
Now, I know reason for your awesomeness.

But he has no post history in Russian section !!!

From my understanding,

Does 'X' public address always have 'Y' private key - no
Does 'Y' private key always have 'X' public address - yes

Unless u mention X > Y or X = Y or X < Y , the above statements are void IMO.

X and Y are not numbers, but strings

well... that way Satvik's statement stands correct.