Bitcoin Forum

from what I have read,

a private key is a 256 bit binary number.

private key ----------elliptic curve multiplication-----> public key

public key -----------sha256 + ripemd160 -----------> public key hash

public key hash -------base58 check encoding------> bitcoin address

now according to the above,

2²⁵⁶ private keys are possible
since elliptic curve multiplication produces a unique public key from each private key, an equal number of corresponding public keys are also possible. But, since the public key goes through RIPEMD160, the public key hash has only 20 bytes or 160 bits. Hence only 2¹⁶⁰ bitcoin addresses are possible. Does this mean that each bitcoin address may be associated with more than one private key? Since, if each of 2²⁵⁶ public keys produce only 2¹⁶⁰ hashes this means more than one public key produces the same public key hash.

I would appreciate if an expert could clarify this matter ?

Yes, that is correct.

A valid private key is not 2**256, it is between 1 and FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, which is the order n of G on the Koblitz curve secp256k1 used in Bitcoin.
The chance of a random 2**256 number not being on the curve is 1 in 267776665566007192515705986938822075895 or so, so pretty much the same thing as 2²⁵⁶ for casual discussion.

As you surmised, any given Bitcoin address is expected to have about 2⁹⁶ possible public/private keys.

There are probably 2¹⁶⁰ Bitcoin addresses, but there is no proof that they all exist, and statistics about the chances they all exist aren't informed about how oracle-like ripemd160 might be when it is streamed 160+96 bits.

I expect the hash test is first is to avoid unnecessary resource consumption. If the hash of the public key doesn't match, it won't even try to verify the signature.

If two public keys can share an address, a signature from the respective private key is still required to actually spend funds, no?

P2SH might be worse off because of HASH160. P2PKH still requires an OP_CHECKSIG, whereas if you find a script tailored to you that collides with a script-hash address, you could spend those funds using your version of the script. Either case still requires a SHA256 collision however, making this prospect unlikely.

When I send you money, I am only sending it to a Bitcoin address; I don't know your public key. Any public key that hashes to that Bitcoin address can spend the money.

Of course, even if there were 21 trillion addresses each having one satoshi in them (more than the maximum number of bitcoins that will ever exist), the odds are impossible-1 that you will ever be able to spend money for a Bitcoin address and key you didn't generate yourself.

I know that.


But this is wrong. The public key is provided in the scriptSig, and that's what signatures are checked against. It's also how the hash is checked in the first place.

You can find a public key that collides with the hash, and pass the first part of a p2pkh script. If the hash passes, all that's left is <sig> <pub> OP_CHECKSIG, which still wouldn't pass with the dodgy key.

Bitcoin address balances are in the form of previous unspent transaction output (UXTO) payments they have received. A standard Bitcoin UXTO that would be in a wallet is a "pay to pubkey-hash", where money is sent to the RIPEMD160(SHA256()) hash of the public key (this pubKeyHash is the same thing as a Bitcoin address, without the Base58 encoding making it pretty). The output script in this UXTO defines the procedures that must be met to spend the money.

A pay to pubkey-hash output script has instructions that basically say: if you can provide a pubkey, and the hash of that pubkey is the Bitcoin address included in the script, then you can spend the bitcoins with a message signed by the keypair.

The output script doesn't care that you use a particular pubkey out of the many that might exist that create the same pubkey-hash, only that the hash (address) matches. The spender is the one that is sending the pubkey to the network, saying in effect with their transaction "this is bitcoins I am allowed to spend - here I'm signing a message with the instructions to spend it, and since you don't have the pubkey yet to cryptographically verify my signature, I'm providing the one I used to sign the message".

Of course the signature has to be valid and the pubkey has to match the bitcoin address, but that is assumed.

The original generation of 50 BTCs from mining was a pay-to-pubkey script. To spend those, you had to have the correct key.

deepceleron is correct.

The public key is indeed provided in the scriptSig, but this is not what signatures are checked against.

The scriptSig (containing the signature and the public key in P2PKH) is provided by the spender. It is the scriptPubKey in the output of the transaction that is being spent from that does the checking.

In the case of P2PKH, the scriptPubKey makes no mention of the public key - just the address.

Glad to know that.

I am not very good at math, but given a private key, is there any mathematical way to find other private keys that share the same public key?

two different private keys will never share the same public key. What is implied by the above quote is that many different private keys may share the same public key hash, which is not the same thing as the public key. I am not a cryptography expert, but I am 99% sure the answer to your question is no, if you actually meant public key hash.

I am a cryptography expert, and I AM 100% sure.

If the hash does what it's supposed to do, then having a privKey that hashes to a particular value will give you absolutely no advantage in finding another key that hashes to that value. 

That said, there are hashes like MD5, which don't do what they're supposed to do anymore because somebody figured out a way to attack it that gives hash collisions on demand.  Ripemd160 could eventually become such a hash if somebody figures out a good way to attack it.

The odds are against it though.