4

It seems really random. 1d is 1353, 1L is 22, 11 is 256, 11L is 78508, 11x is 78508, 111 is 65536, 112 is is 1335, 113 is 1330, 114 is 1330, 1L1 is 1330. I thought it was 58 to the power of the number of digits. Why isn't it?

5

There are two parts to this.

First is leading 1s. A leading 1 represents a 0 byte i.e. 8 bits. This means that for every additional 1 you prefix your search string with the difficulty increases by 256 (2^8). You can see this easily by checking the difficulty of prefixes 1, 11, 111 etc.

Second is other characters. Here the difficulty changes depending on how many bits you are specifying, because as your value is converted from base58 to an integer value and from there to a power of 2. Depending on your second number in your 2-digit prefix the difficulty will move around a bit (plus there will be rounding errors). Again, easy to see with prefixes of 12 and 1z (which are 1 and 57 in base58 encoding, respectively).

Once you get past all of that you should find that your 58 to the power of the number of digits comes in to play. For example the difficulty of 1234 should be 58 times the difficulty of 123.

| improve this answer | |
  • "For example the difficulty of 1234 should be 58 times the difficulty of 123." It's not. 1353 * 58 != 78508. Even if you compare 12345678 and 123456789, you'll find it's not exactly a factor of 58 – Nick ODell Apr 9 '13 at 23:37
  • As mentioned, there are rounding errors because difficulties are calculated using integer values (and the calculation multiplies integers so the error compounds as you increase the size of the prefix). – jgm Apr 9 '13 at 23:54
  • Ah. So the difficulty reported by vanitygen is inaccurate? – Nick ODell Apr 9 '13 at 23:56
  • I wouldn't label it as inaccurate; it's a minor rounding error that's less than 0.05% in the most egregious case, and that's only when it really doesn't matter because the absolute numbers are so small. – jgm Apr 10 '13 at 0:01
  • 1
    Non case sensitive. It says that the probability of finding 1L is the same as finding 1m OR 1M. That seems a little odd to me. – lurf jurv Apr 23 '13 at 14:39
0

@jgm's answer is unfortunately wrong. Adding one character does not multiply the difficulty by 58, though it is a good approximation. (The part on 1s at the beginning are correct, consecutive 1s only at the beginning are a special case, an exception)

If the smallest address were

111111111111111111...111111

and the largest address were

1zzzzzzzzzzzzzzzzz...zzzzzz

and those addresses were of equal lengths, he would be correct.

In other words, if I told you I've chosen a random number between 0 and 99, the probability of the first digit being 3 would be 10%. But if I choose a number between 0 and 36, the probability of the first digit being 3 would be much lower than 0, 1 or 2. Welcome to the world of base conversions.

How Vanity address generators pattern matchers work:

(Let's just ignore the prefix byte 0x00 which gives the 1 in the beginning of addresses)

In batches, it will generate a random private key and its corresponding public key hash. We'll add the four bytes of checksum at the end. Then we Base58 encode it and check if its prefix matches.

Recall that Base58 encode is a base conversion from base256 to Base58 (plus the special treatment of the 1 at the beginning). So instead of Base58 encoding every calculated public key + 4-byte-checksum, we can find the binary number ranges of the expected prefix. Thus if public key + 4-byte-checksum is in that binary range (comparing large binary numbers is quick), then it's Base58 encode will yield an address with that prefix.

Suppose we want 1PA. The smallest Base58 character is 1, the largest is z. To find the range, we can inspect the smallest and largest numbers in Base58, and convert them to binary.

Is 1PA111111111111111111111 our lower limit (same reasoning as a large number starting with 1320 could be 1320000)? No, if we apply Base58 decode to it, we can see it has 19 bytes. So we add 1s until we get one that decodes to 24 bytes:

1PA111111111111111111111111111111 is our lower limit.

So 1PAzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz is our upper limit? It decodes to 24 bytes. Yes!

Are we done? No. What if we added one more 1 to our lower limit:

1PA1111111111111111111111111111111 still decodes to 24 bytes.

same for 1PAzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz. So this address has two ranges? Vanitygen adds sizes of ranges and divides the total number of ranges by their sum and rounds down.

There is also a second group of prefixes, those who who have only one range. (For example 1Qa111111111111111111111111111111; adding one 1: doesn't decode to 24 bytes but to 25 bytes)

How do we know if there are one or two ranges?

Supervanitygen's approach is the most simple one: compare with 1QLbz7JHiBTspS962RLKV8GndWFw. If the first character of our prefix is lower, then it'll have two prefixes. If ours is comes later in the Base58 alphabet it'll have one prefix. If same, compare the next character. Ones with two ranges are easier to find, but never those two ranges are equal in length.

The prefix subsets (1Q, 1QL, 1QLb) of 1QLbz7JHiBTspS962RLKV8GndWFw are an absolutely mess to work with. For example for the prefix 1QLbz7, the longer lower range is 1QLbz71111111111111111111111111111, so the corresponding higher range should be 1QLbz7zzzzzzzzzzzzzzzzzzzzzzzzzzzz, right? No, it's 1QLbz7Hzzzzzzzzzzzzzzzzzzzzzzzzzzz. I had to write a binary tree just for this prefix in my (dirty and useless) range generator implementation.

But why can there be at most two ranges? It's about adding 1s, which is the same as multiplying by 58. If we have a 01 byte for example, 58 would still be a byte, but we can't multiply by 58 once again; that would definitely increase the number of bytes by 1. On the other hand, some prefixes have 1 range because for example the byte 20 can't be multiplied by 58 without introducing another byte. Think of those bytes as the most significant bytes.

For example 1QLa (has two ranges, just below the one range boundary)'s ranges are (this time the result of base58 decode):

lower 0x0469... upper 0x0469... lower 0xfffe upper 0xffff

Notice that 0x0469 which is {4, 120}, when multiplied by 58 (ignore the rest, next few bytes which affect through multiplication carry) 232,105, the most significant byte is really close to 255.

About 40% of prefixes have 2 ranges.

Now, think of those addresses who start with 1. Overall, there are so many edge cases that multiplying by 58 to calculate difficulty is no good.

Addresses in other coins and testnets have network bytes other than 0x00. So they can have at most one range. Why? To multiply by 58 one has to multiply the network byte too; as a result the network byte is invalid.

TL;DR There are three things that make difficulty calculation complex:

  • Leading 1s are treated differently.
  • Public key hashes/public key hashes + checksums are in binary. So there are 2^20 of them. 2^20 isn't a power of 58, so the largest address won't be "1zzzzzzzzz...." but something longer than an address which could be filled with z. Same reasoning as the 36 example in the beginning.
  • Some prefixes have two ranges instead of one, with different address lengths.
| improve this answer | |

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.