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?
asked Dec 9, 2013 at 12:02
-
1Shall I consider myself lucky? I created my wallet yesterday and I got one starting with 1s.– janosrusiczkiCommented Dec 9, 2013 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...– user6049Commented Dec 9, 2013 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).– user6049Commented Jan 27, 2014 at 4:16
Add a comment
|
2 Answers
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:
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:
- Hash your public key first with SHA-256, and then with RIPEMD-160.
- Add a version number and checksum to the above.
- Convert the bytes of this value from step 2 to an integer.
- 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. Commented Jan 26, 2014 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.– user6049Commented Jan 27, 2014 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. Commented Jan 27, 2014 at 4:16
-
Yes, you're right.– user6049Commented Jan 27, 2014 at 4:18
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.