11

I've generated 10000-50000 key pairs using Chrome Bit Kit app or www.bitaddress.org and have noticed the scarcity of public keys which begin with 1S and/or 1s.

Why is this the case?

  • 1
    Shall I consider myself lucky? I created my wallet yesterday and I got one starting with 1s. – janosrusiczki Dec 9 '13 at 12:39
  • Yes, you should. But it is not like winning against hugely unfavorable odds; getting 1a... is just as likely as getting 1s..., which is only about 59 times less likely than getting 1A... – pyramids Dec 9 '13 at 12:54
  • Correction: I estimated 59 from the output of the vanitygen tool. Having added the math to my answer below, I suspect that was really trying to tell me a factor 58 from a crude estimation based on the maximum possible length (reduced by one symbol). The real factor is probably closer to 40 = 23.34 * 58 / (58-24). – pyramids Jan 27 '14 at 4:16
13
+50

When I read pyramids' answer, I was very skeptical. It didn't really seem right to me that addresses generated from a hash (in this case from a public key) would have anything but a random distribution. To test out the distribution of addresses, I downloaded the dataset linked to in this forum thread and counted up how many times addresses appeared. There are something like 2.4 million real addresses in this dataset, so I figured it would give me a pretty decent sample size. Sure enough, pyramids was right, I ended up with a count something like this:

Address Distribution

As it turns out, you are much more likely to see an address where the second character is 2-Q than anything else. After some research, it turns out that the reason why this is the case is fairly subtle, and requires some background on how addresses are generated. The technical details of how an address is generated are here and here, but the tl;dr is this:

  1. Hash your public key first with SHA-256, and then with RIPEMD-160.
  2. Add a version number and checksum to the above.
  3. Convert the bytes of this value from step 2 to an integer.
  4. Convert the number from step 3 to a base 58 encoded string.

NOTE: The stuff below this statement is very heavily edited from what my original answer was. The original answer was based on some personal research I had done and it turns out that I got it wrong. Thanks to @MeniRosenfeld for correcting me in a comment.

Step number 3 above is where the bias towards addresses starting with characters between 2 and Q is introduced. The data that you have after step 2 is 25 bytes long, but because of the version number that is pre-pended is fixed (0x00 for the Main Network), there are only 24 bytes that add to the integer you produce. With 24 bytes of data, you will never get a number big enough to generate an address where the second character is anything greater than Q. If however, those 24 bytes produce an integer that is less than ~2.6896e56 you can actually base58 encode it in 33 characters instead of 34 during step 4. When you have numbers this size, there is room available to have a number that will generate an address where the second character is any of the characters between 2 and z. Therefore, the reason that it is much more rare to get one of these numbers is that there are simply fewer of them. The addresses that have a second character between R and z can only be addresses that are 33 characters long while the others can be any address that is 34 characters long or any of the addresses that are 33 characters that have a second character between 2 and Q. This is skewed even further by the fact that there are 58 times more addresses with 34 characters than 33 due to the additional length.

It should also be noted that because of the way base58 encoding works, every extra empty byte present at the beginning of the data in step 3 ends up as a 1 added to the beginning of the final address. Therefore, the first bin on the graph doesn't fit in with the others because it is where all addresses of length between 32 and 27 ended up.

  • These aren't addresses which start with a version byte of 0x01. It's the other way around - these are addresses where the pubkey hash has a few more zeros after the 0 version byte, so you get a shorter address. Within these shorter addresses 1s is possible, but there are only 1/58 as many addresses which are 1 character shorter. – Meni Rosenfeld Jan 26 '14 at 23:46
  • Great answer! Just one minor correction: You always have 25 binary bytes in a public bitcoin address, of which the first is always zero. That translates into 34 (or rarely 33 or even less) symbols in the base-58-encoded address. – pyramids Jan 27 '14 at 4:11
  • 1
    @pyramids - Thanks, I've edited my answer to clear some of this up. Your number is a little off, however. Most addresses are 34 characters, and they can be anywhere between 34 and 27 characters long. See en.bitcoin.it/wiki/Address. – TwentyMiles Jan 27 '14 at 4:16
  • Yes, you're right. – pyramids Jan 27 '14 at 4:18
5

Very few bitcoin addresses map to addresses with any lower-case initial letter (after the 1) or any upper-case letter that comes after Q in the alphabet. All the bitcoin-base-58 encoding characters before Q and except 1 are at least almost equally frequent, and all those after Q as well but far less frequent, with Q being in-between and 1 being even less frequent. This is because a randomly generated address you may use is essentially a base-58 number of what is not only a nearly randomly distributed hash, but also has a certain structure given by the version byte.

You don't have to do any base-58 conversion yourself to get the probabilities. I used the vanitygen tool to give me estimates for the (inverse) probability that a randomly generated address ends up on a slot starting with 1P, 1Q, 1R, etc.

UPDATE:

Actually, it is fun to do a quick base-58 calculation. A public bitcoin address is a base-58 encoding of 25 binary bytes, of which the first is zero and completely encoded in the starting "1" of an address. The rest is based on a cryptographic hash and hence uniformly distributed between 0 and 256^24 - 1, which is approximately 23.34 * 58^32. If the number for your address is 58^32 or greater, we need 33 symbols after the initial "1" in your bitcoin address, and only the first 23 symbols (symbols "2" through "Q" since the symbol "1" is special, signifying a zero in bitcoin-base-58) can occur as second symbol in your bitcoin address.

Only in the rare case (probability 1/23.34) that your address needs fewer symbols can you even get a second character other than "2" through "Q", and then you get an even distribution between all base-58 symbols except "1" which, again, is special.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.