Author

Topic: Bitcoin address and hash theory questions (Read 2043 times)

legendary
Activity: 3472
Merit: 4801
April 01, 2013, 09:56:21 AM
#4
- snip -
What is the maximum number of private addresses?

2^96  --  https://bitcointalksearch.org/topic/how-many-possibly-bitcoin-addresses-are-there-exactly-and-how-long-does-it-24268

and "almsot 2^256"   --   https://en.bitcoin.it/wiki/Private_key
- snip -

I assume you mean private keys (not private addresses, there is no such thing).  In that case:

https://en.bitcoin.it/wiki/Private_key

What is the maximum number of public addresses?

Only max found is 2^192 from  --   https://en.bitcoin.it/wiki/Private_key

25 byte public address  minus 1 byte for 00 hardcoded first byte  --  2 ^ ( 24*8 )

The limiting factor is the RIPEMD-160 hash.  Since the output of this hash is a 160 bit number, the maximum possible number of unique public addresses is 2160.



Has it been proven that there will be no hash-collisions where 2 private addresses share the same public address?


No info found.

With nearly 2256 possible private keys and only 2160 public addresses, it can be safely assumed that hash-collisions where 2 private addresses share the same public address will exist in the sets of all possibilities.  The odds of any individual encountering such a collision are so small as to make it practically impossible.



What is the process to create a private and public address ?

The address creation process looks like a random private first, then generate public address from the private...

https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses

  • Random private key
  • ECDSA with the secp256k1 curve to find public key
  • SHA-256 public key
  • RIPEMD-160 result from SHA-256
  • Add a version byte to RIPEMD-160 result
  • Add a 4-byte checksum to RIPEMD-160 result
  • Convert to Base58Check format
newbie
Activity: 53
Merit: 0

I have done a bit of homework and have a CS/math degree.  My field is not crypto, but I know about fields, groups, graph theory and SHA-256.  Any answers, review or corrections of my questions would be appreciated.

Has it been proven that there will be no hash-collisions where 2 private addresses share the same public address?
See below.

What is the process to create a private and public address ?

The address creation process looks like a random private first, then generate public address from the private...

It looks like there are Process to create a public address from a private address:

3 SHA-256 hashes and 1 RIPEMD-160 hash, plus some other simple manipulation.

https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
I would describe it more as one SHA-256 hash then one RIPEMD-160 hash.  It's the 160-bit RIPEM hash that is presumed to be unique.  The other two SHA-256 hashes are for computing a 32-bit checksum for the 160-bit hash.  This is so typographical errors in an address won't cause a transfer to go to the bit-bucket.  (bitcoin-bucket?)  [There's about a 1 in 4 billion chance a random syntactically correct sequence of bytes will be accepted as a valid address.

private key --> ECDSA --> public key --> [SHA-256] --> [RIPEM-160] --> (pre-checksum) address


On address collisions:  There is no proof that collisions cannot occur.

If our hashes are perfect, there is no way to steer a particular public key to a particular 160-bit hash.  The birthday paradox says we will have to encode about 2^80 public keys before we have a 50% chance of an address collision.

Weaknesses have been found in many hash algorithms.  But, since the input to RIPEM is not under our direct control (input to RIPEM is an output from SHA-256), I think the chances of manipulating the inputs to RIPEM to deliberately produce a collision are low.

Can we get collisions in the SHA-256 output?  The birthday paradox says we will have to encode about 2^128 public keys before we have a 50% chance of a collision in the SHA-256 output.

We do have direct control over the inputs to SHA-256.  While there are cases of two distinct inputs producing identical MD5 (128-bit) outputs, I am not aware of that feat having been performed for SHA-256.

Even if two SHA-256 hashes are found to be identical, the input to SHA-256 was a public key.  At this point, the answer to your question is "yes".  Two private addresses share the same public address.  There remains the problem of converting your hand-crafted public key into a private key that you can spend.  We know it exists, but you can't figure it out any better than you can figure out anybody else's private key from their public key.

IMHO, there are more potential attack vectors aimed at public keys than most other security aspects of Bitcoin.  A fatal flaw in RIPEM could lead to an attack against addresses.  A fatal flaw in SHA-256 could lead to an attack against addresses (and other components of Bitcoin).  And a fatal flaw in ECDSA would be fatal to Bitcoin as we know it.  I'm not too worried.  But ask me again in 20 years.
jr. member
Activity: 42
Merit: 11
First of all, you are mixing "keys" and "addresses".
There is only one kind of address, and it's derived from public key.
Maximum number of different addresses is 2^160 (as it's 160 bits long).
96 is difference between 256 (public key length) and 160 (address length).
So, there are 2^96 times more public keys then addresses.
Now, it's technically feasible to create collision for bit strings < 70 bits. Not feasible for 160, and even in several decades.
newbie
Activity: 28
Merit: 0

I have done a bit of homework and have a CS/math degree.  My field is not crypto, but I know about fields, groups, graph theory and SHA-256.  Any answers, review or corrections of my questions would be appreciated.

What is the maximum number of private addresses?

2^96  --  https://bitcointalksearch.org/topic/how-many-possibly-bitcoin-addresses-are-there-exactly-and-how-long-does-it-24268

and "almsot 2^256"   --   https://en.bitcoin.it/wiki/Private_key


What is the maximum number of public addresses?

Only max found is 2^192 from  --   https://en.bitcoin.it/wiki/Private_key

25 byte public address  minus 1 byte for 00 hardcoded first byte  --  2 ^ ( 24*8 )


Has it been proven that there will be no hash-collisions where 2 private addresses share the same public address?


No info found.


What is the process to create a private and public address ?

The address creation process looks like a random private first, then generate public address from the private...

It looks like there are Process to create a public address from a private address:

3 SHA-256 hashes and 1 RIPEMD-160 hash, plus some other simple manipulation.

https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses


Assuming a public key is generated from a private key, how does it computationally compare to block creation?

Creating a block needs 2x SHA-256.
Creating a public key needs 3x SHA-256 + 1 RIPEMD-160.
RIPEMD-160 is 2xMD4 hash, each of which is less than or equal to a SHA-256  hash

Thus a public key is ~ 5 hashes and a block is ~2 hashes.
Jump to: