Maths Q1 - address to key ratio

[thirdprize]

Addresses are 30+ characters long and keys are 50+ characters long.  That means there can be a lot more keys than addresses.  Does anyone now how many valid there are of each?  Does this mean each valid address can be serviced by more than one key?  If so, how many per address?

[hosseinimr93]

There are 2²⁵⁶ valid private keys, 2²⁵⁶ valid public keys and 2¹⁶⁰ valid addresses.
Therefore, every address can be generated by 2⁹⁶ private keys and 2⁹⁶ public keys on average.

[BrewMaster]

There are 2²⁵⁶ valid private keys, 2²⁵⁶ valid public keys and 2¹⁶⁰ valid addresses.

actually there are a little less than 2²⁵⁶ valid private keys which are from 1 to N⁽¹⁾ (equal amount of public keys).
there are also virtually unlimited number of addresses because an address is the equivalent of a customized script. for example you can create both P2PKH and P2WPKH addresses from a single private key. then you can also create custom P2SH scripts in which you set any kind of script using that same private key.

⁽¹⁾ in hex FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
in decimal 115792089237316195423570985008687907852837564279074904382605163141518161494337

[ABCbits]

There are 2²⁵⁶ valid private keys, 2²⁵⁶ valid public keys and 2¹⁶⁰ valid addresses.

actually there are a little less than 2²⁵⁶ valid private keys which are from 1 to N⁽¹⁾ (equal amount of public keys).
there are also virtually unlimited number of addresses because an address is the equivalent of a customized script. for example you can create both P2PKH and P2WPKH addresses from a single private key. then you can also create custom P2SH scripts in which you set any kind of script using that same private key.

⁽¹⁾ in hex FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
in decimal 115792089237316195423570985008687907852837564279074904382605163141518161494337

If we're going to such detail, don't forget there are multiple public key representation (compressed, uncompressed & hybrid) & multiple address format (P2PK, P2PKH, P2SH, P2WPKH, P2WSH) where both P2SH and P2WSH address depends on the script itself, which makes the answer to OP question more complicated.

[thirdprize]

There are 2²⁵⁶ valid private keys, 2²⁵⁶ valid public keys and 2¹⁶⁰ valid addresses.
Therefore, every address can be generated by 2⁹⁶ private keys and 2⁹⁶ public keys on average.

Thanks.  So for any address there is going to be a very large number of keys with any particular character at any particular position.  That is what I wanted to know.

[thirdprize]

What if you could just narrow it down a bit.  Third character is in this range, fourth in this range, and so on.  Everyone quotes the unsolvable probabilities but what is a solvable probability given computing powers and botnets these days? 2^x?  What is x?

[BlackHatCoiner]

What if you could just narrow it down a bit.  Third character is in this range, fourth in this range, and so on.  Everyone quotes the unsolvable probabilities but what is a solvable probability given computing powers and botnets these days? 2^x?  What is x?

Are you asking what are the possibilities of successfully finding the private key of an address by brute forcing? If so, as @hosseinimr93 said, 1 in 2²⁵⁶. You can try calculating with custom computational power and see what are the odds.

The problem is that you don't know which of those keys generate the same address. If you had a list of 2⁹⁶ numbers that generate completely different addresses, then yes it would be easier to brute force, but you don't.

Specifically, if you had that list and a machine that performs 100 trillion ECDSA and SHA256 hashes per second it would take you 79,228,162,514,264 seconds to get all possible addresses' combinations.

which is equal with 1,320,469,375,237 minutes, 22,007,822,920 hours, 916,992,621 days, 30,566,420 months, 2,547,201 years. And remember, you don't have that list of special numbers.

[o_e_l_e_o]

What if you could just narrow it down a bit.  Third character is in this range, fourth in this range, and so on.

Characters of the private key? Well then your number of overall possibilities for the correct private key would simply be "number of possibilities for second character" * "number of possibilities for third character" * "number of possibilities for fourth character" * "number of possibilities for fifth character" * ... * "number of possibilities for the last character".

Once you have that number then you need to work out how many times you can perform elliptic curve multiplication, SHA-256, RIPEMD-160, and then two more SHA-256s each second, to turn each private key in to an address. DaveF made some benchmarks for doing this a couple of years ago: https://bitcointalk.org/index.php?topic=5112311.msg50823897#msg50823897. With the top end GPUs on the market - GeForce RTX 2080 Super/Ti - you are looking at about 2 - 2.5 billion keys per second.

Are you asking what are the possibilities of successfully finding the private key of an address by brute forcing? If so, as @hosseinimr93 said, 1 in 2²⁵⁶.

It's actually 1 in 2¹⁶⁰, on average, since there are 2⁹⁶ private keys per address, on average.

Specifically, if you had that list and a machine that performs 100 trillion ECDSA and SHA256 hashes per second

It is elliptic curve multiplication, not ECDSA, that is needed here, and there are more hashes required than just a single SHA-256 as I've outlined above.

[thirdprize]

Are you asking what are the possibilities of successfully finding the private key of an address by brute forcing? If so, as @hosseinimr93 said, 1 in 2²⁵⁶. You can try calculating with custom computational power and see what are the odds.

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force? 

[o_e_l_e_o]

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force?

Well, we can work out a rough idea. Let:

x = number of addresses you can derive from their respective private keys each second
y = length of time in seconds you are willing to wait

Given that a private key has 64 characters, then the number of possibilities for each character would then be given by the 64th root of the product of these two numbers, so ⁶⁴√(x*y)

For example

Let's say you are running a GeForce RTX 2080 Ti, which can turn 2.5 billion private keys in to their corresponding addresses each second, and you are willing to let this run for two weeks. 14 days * 24 hours * 60 minutes * 60 seconds * 2.5 billion = 3.024*10¹⁵ private keys. The 64th root of this number is 1.745, so you wouldn't even be able to exhaust the search space of 2 characters per position in 2 weeks.

2⁶⁴ is 1.845*10¹⁹, so again running your GeForce RTX 2080 Ti and checking 2.5 billion keys per second, it would take you ~234 years to check all combinations, or ~117 years if you wanted a 50% chance of finding the correct key.

[BlackHatCoiner]

It's actually 1 in 2¹⁶⁰, on average, since there are 2⁹⁶ private keys per address, on average.

I was wrong about that. Yes, it's actually 1 in 2¹⁶⁰.

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force?

First of all let's define the private key's format. Is it going to be hexadecimal or WIF? ^{[the difference]}
Secondly what do you mean by saying crackable by brute force? Are we trying to find his private key or a private key that unlocks his address?
If we assume that you want his private key and that his private key is hexadecimal then a character of the fifth position isn't going to help you. You still have almost 2²⁵² different combinations. (for every hex character you remove you have 2⁴ less combinations)

If you want to find a private key that unlocks his address then, as @o_e_l_e_o wrote, you have 1 in 2¹⁶⁰ on average. To cut a long story short, if he doesn't give you at least 25 hexadecimal characters of his private key then you have less possibilities of finding it than succeeding on an address' brute force.

Knowing 25 hex characters and their positions is 16 times easier than 2¹⁶⁰. It's 1 in 2¹⁵⁶. Still impossible, but easier than the stupidly enormous range of [1, 2¹⁶⁰].

@thirdprize, note that we use the phrase "on average". There may be addresses like this one: 1111111111111111111114oLvT2 that have no private keys that unlock them. Every address most likely has more than 1 billion, but you can't prove it if you don't try all the possible combinations. It is quite funny to think that there are so many numbers that unlock you 69 bitcoins, but no one knows them. And that happens because most of us can't imagine the largeness of 2¹⁶⁰.

^{[the difference]}
Example of a private key in hexadecimal:

Code:

e1398ffab41618b4c63313912d2c407e57c60feeb799544503e0aeca8c5aede1

Example of a private key in WIF (Wallet Import Format):

Code:

L4mX2hsUq4LFbMmAomWHCARAuMkzTuAZjmGCQsvmny1aahRE1Aie

(The above works only on mainnet)

A WIF is nothing but the original hex private key encoded in base58 plus some other technical stuff like version byte and checksum. This code shows exactly how we end up with a WIF:

Code:

privatekey = "e1398ffab41618b4c63313912d2c407e57c60feeb799544503e0aeca8c5aede1"
extended = "80" + privatekey + "01"
extendedchecksum = extended + checksum(extended)
wif = base58_encode(extendedchecksum)

// wif is "L4mX2hsUq4LFbMmAomWHCARAuMkzTuAZjmGCQsvmny1aahRE1Aie"

You can read more about the WIF here: https://learnmeabitcoin.com/technical/wif

P.S, o_e_l_e_o is faster.

[j2002ba2]

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force? 

Assuming known legacy address, wif private key contains 85 characters, first is always "5", second one of "H", "J", "K", leaving us with 83 characters. Let's assume the second character is know. When we have 4 possibilities for each character, there are 2¹⁶⁶ possible combinations. Direct brute forcing has been solved for private keys with 2⁶³ possibilities up to now.

We could accelerate the calculations a bit, by dropping the checksum characters (last 5), and doing checksum on the rest. This drops the complexity to 2¹⁵⁶.

If the public key of the address is known (i.e. spent from, or signed with), then it's "easier" to do Pollard Rho on it - complexity is only 2¹²⁸.

With 2 possibilities per character, the complexity is 2⁷⁸, so few billions of dollars, many years, and giga-watt-hours later it could be cracked.

[o_e_l_e_o]

You still have almost 2²⁵² different combinations.

Minor correction: If you have 4 possibilities for one character in a 64 character private key, then the total number of possibilities is 2²⁵⁴. If you knew for certain one character in the key, then you would have 2²⁵² possibilities.

There may be addresses like this one: 1111111111111111111114oLvT2 that have no private keys that unlocks them.

Another correction: This address does have a private key. In fact, it has many. It is just that nobody knows what any of them are (or at least, as far as we know nobody knows what any of them are). That address is generated from a RIPEMD-160 of:

Code:

0000000000000000000000000000000000000000

Any private key which produces a public key, which when hashed with SHA-256 then RIPEMD-160 produces the above number, would be able to spend coins at that address.

[BlackHatCoiner]

Any private key which produces a public key, which when hashed with SHA-256 then RIPEMD-160 produces the above number, would be able to spend coins at that address.

I didn't say the opposite. I said it may. It may also have none, it's just extremely unlikely.

Minor correction: If you have 4 possibilities for one character in a 64 character private key, then the total number of possibilities is 2²⁵⁴. If you knew for certain one character in the key, then you would have 2²⁵² possibilities.

Why do you have 4 possibilities for one character? Isn't it 16? (0-F). I don't get this.

Actually this needs a correction:

(for every hex character you remove you have 2⁴ times less combinations)

[o_e_l_e_o]

Why do you have 4 possibilities for one character? Isn't it 16? (0-F). I don't get this.

You are right that each character can be one of 16 possibilities, from 0-F, and you are right that if you know one character then then instead of it being 16⁶⁴ = 2²⁵⁶ combinations it is 16⁶³ = 2²⁵² combinations.

My point was that OP had asked what would happen if the person gave you a number of different options for a character - "eg, for the fifth position is either 1, 3, f or a". In that case, instead of that position having 2⁴ possibilities, it instead has 2² possibilities, so the total number of possibilities would reduce from 2²⁵⁶ to 2²⁵⁴. Given that, even if you only had 4 possibilities for every character in the key, you would still be left with 2¹²⁸ possibilities overall, which is still impossible to even consider brute forcing.