Is each Ethereum address shared by (theoretically) 2 ** 96 private keys?

Question

Summary

This is an extended question to How are ethereum addresses generated?.

In Ethereum, a private key is 256-bit long, but an address is only 160-bit long. By "Pigeonhole Principle", it guarantees that some unique private keys map to the same address. Theoretically, 2 ** 96 unique private keys maps to one address on average.

Question

If 2 private keys map to the same address, do they both gain access to the same address? Can they both used to transfer Ether from that address to another?

Details

According to @tayvano's answer, a private key is 256-bit long, and any 256-bit string is a valid private key:

Every single string of 64 hex are, hypothetically, an Ethereum private key that will access an account.

Therefore, there are 2 ** 256 valid private keys (the key space is 2 ** 256).

A public key is 512-bit long. However, since each of them is derived from its own private key, there are only 2 ** 256 valid public key, and thus the key space is 2 ** 256.

The public key is then feed as the input of Keccak-256 (pre-standard SHA3) hash algorithm. The output of Keccak-256 is a 256-bit string, therefore it could be treated as a one-to-one mapping in key space. (The hash space is 2 ** 256)

However, an Ethereum address is obtained from the least significant 160-bit of the Keccak-256 hash. This cuts the key space to 2 ** 160.

As a result, the process of generating an address from a private key is a function of a 256-bit value to a 160-bit value, which guarantees duplicates.

You may be interested

• What if I had the private key that had the public address of a contract?
• Are addresses between different networks (testnet) interchangeable?

Answer 1

Your calculations are right, except there aren't exactly 2^256 private keys -- there are "FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141" (this number is named N in the ETH source code, and is the order of the generator of the elliptic curve secp256k1, from which Ethereum key pairs are generated).

In answer to your question, yes, private keys mapping to the same address will both be able to spend the money in that address on a first come first served basis. They will create the same public key, which the ECDSA verification algorithm is performed against, and so signatures generated by either private key will verify against the same address!

In go-ethereum/accounts/key.go, we have a private key generated from S256 which is secp256k1's curve, meaning they will be less than N be default.

func newKeyFromECDSA(privateKeyECDSA *ecdsa.PrivateKey) *Key {
    id := uuid.NewRandom()
    key := &Key{
        Id:         id,
        Address:    crypto.PubkeyToAddress(privateKeyECDSA.PublicKey),
        PrivateKey: privateKeyECDSA,
    }
    return key
}

func newKey(rand io.Reader) (*Key, error) {
    privateKeyECDSA, err := ecdsa.GenerateKey(secp256k1.S256(), rand)
    if err != nil {
        return nil, err
    }
    return newKeyFromECDSA(privateKeyECDSA), nil
}

go-ethereum/crypto/secp256k1/secp256 also generates the key pairs in accordance with secp2656k1 albeit in a slightly different way :)

Cool illustrative explanation for what N really is and why 2 keys will be able to spend money from the same account

Imagine private keys are miles driven in your car, and public keys are number of miles on your car's odometer. If the odometer rolls over from 999,999 to 000,000, a person with miles driven = 1,000,001 will have the same 'public key', and hence the same address, as a person with miles driven = 1.

EC group arithmetic is surprisingly similar to this, but rather than 999,999, we have the seemingly arbitrary number given above! Due to this property, even with your different 'private keys', you will be able to create signatures that verify against the same public key, and hence spend ETH from the same address!!

Boring math explanation

Private keys are 256 bit numbers, and to calculate the public key from a private key you multiply by the generator, g, of the elliptic curve group. The generator in use is defined in the parameters of the secp256k1 libraries being used in ETH. It itself is also an elliptic curve point, and as elliptic curves are cyclic, there exists an n such that n.g = 1 (this is called the generator order).

With this equation we can see that if we had a private key k with k>n, we would have k.g = (k-n).g = k'.g, for a k' that is possibly someone else's private key! So we have keys generated at random modulo n, rather than 2^256.

Answer 2

My revised answer to the main headline question is that inevitably there are 2^96 keys that will produce colliding addresses because the limit on the address space is 2^160, and keyspace is nearly 2^256. So even though each distinct public key and resulting Keccak hash digest maps distinctly to just one private key, given the use of Keccak in the address formatting stages the pigeonhole principle applies and creates the potential for a collision of the trailing 160-bits for two different hash digests that share the last 160 bits, more on those assumptions below:

For any valid distinct private key (between 1 and n-1, where n = '0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141' as per curve secp256k1, a 'distinct' public key will be generated (after applying the Generator point to wrap around the curve) and thus there is no potential for collisions as no two differing private keys could map to the same public key.

The official ethereum repo on Github has a library named eth-keys for Python which generates private keys and has error-checking in place to make sure the secret exponent is less than n.

Regarding address collisions:

If the first assumption above is true, then the odds of two different public keys, producing a Keccak_256 digest that has identical trailing 160 bits, would comparable (although less probable) to trying to find any two random strings via brute-force search which would produce identical 160 trailing-bits in their respective hash digests.

Such partial Kecccak_256 hash digest collisions should certainly exist despite the impractical odds of finding one that long, comparable to an ethereum vanity address generator trying to generate all 40 characters to a specific requirement (i.e. 40 1's or the following perfectly valid address that no one is likely ever going to generate a key for without a strong enough quantum computer '0xFEEDFEEDFEEDFEEDFEEDFEEDFEEDFEEDFEEDFEED')) which would have a difficulty of 1461501637330902918203684832716283019655932542976 equal to 2^160 or 16^40 (i.e. having to brute-force search that many combinations to find one such vanity address).

While it is still unfeasible enough (My estimate is 2**160) to find two Keccak_256 hex digests that have the same trailing 40 hex characters for any two random pre-images, this case would require to find two differing ethereum public keys (as pre-images) that hash to two distinct Keccak_256 digests which share the same 40 trailing hex characters.

Therefore, the pigeonhole principle is applicable - but not to the curve itself, as there are n potential private keys that map distinctly to n public keys, (keyspace is 2^256-432420386565659656852420866390673177326, less some invalid ones like all 0's), without any single collisions, but instead there is inevitably collisions on derived addresses (as the distinct address space is 2^160, I am not sure theoretically how many such partial collisions may exist on Keccak_256 digests (So I posting that part on crypto.stackexchange for a deeper dive).

Idea: One way this could be resolved is if the entire Keccak Digest was used as the ethereum address, although the tradeoff could be that there would be consequences on gas costs and other loss of efficiencies such as requiring more data storage as the blockchain would get bloated for each address by 96 bits and all related account transactions (and such an increase would add up to kilobytes, gigabytes, terabytes of difference quickly).