# How does vanitygen calculate difficulty?

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?

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.

• "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
• 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

@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)

`111111111111111111...111111`

`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 `1`s 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.