Vanitygen: Impossible addresses?

Question

I'm currently attempting to modify Vanitygen to suit a particular purpose. However, I'm running into an issue with "impossible" addresses. For example, from the stock Vanitygen available on Github I get this output:

./vanitygen -T mR
Prefix 'mR' not possible
Hint: valid testnet addresses begin with "m" or "n"

While the following works:

./vanitygen -T m
Difficulty: 1
Pattern: m
Address: mh8e8yUtsmhCm6PTkuHV85ozEV5iNibmbp
Privkey: ***************(doesn't matter)

I get similar results for this set of options:

./vanitygen -F script 3Ro
Prefix '3Ro' not possible
Hint: valid bitcoin script addresses begin with a "3"

and

./vanitygen -F script 3R
Difficulty: 836
Pattern: 3R
P2SHAddress: 3R1jUHTrESWgCC812LrgwHErc9Y3UL7XeL
Address: *********(doesn't matter)
Privkey: *********(doesn't matter)

So, I'm trying to determine why Vanitygen is saying that these particular prefixes are not possible. For both of these failures, the failure occurs within get_prefix_ranges(). However, this isn't a programming question, necessarily. What I'm trying to uncover is some underlying principle that I may be missing that would render these particular prefixes impossible.

Perhaps a couple of questions may help me answer this myself:

When Base58Check encoding the version+publickey+checksum, how exactly is the encoding processed? Is the input broken into 6-byte words and then converted into Base58 format (seems implausible because you could theoretically have something like 111111 (binary) in the checksum that would be > 58). Or, is the whole version+pubkey+checksum converted to a BigNumber and then essentially Mod 58'd for each character.

If the latter is the case (which seems probable), in what order does this occur? Using the example of 80FAFBFC (2163932156 decimal):

x = 2163932156
result[0] = x % 58 = 6
x = floor(x / 58) = 37309175
result[1] = x % 58 = 37
x = floor(x / 58) = 643261
result[2] = x % 58 = 41
x = floor(x / 58) = 11090
result[3] = x % 58 = 12
x = floor(x / 58) = 191
result[4] = x % 58 = 17
x = floor(x / 58) = 3
result[5] = 3

result = [6, 37, 41, 12, 17, 3]
Convert to Base58 values:
result = [7,  e,  i,  D,  J, 4]

Would the result be displayed as: 7eiDJ4 or 4JDie7?

Answer 1

This is due to the "version" byte and the way bitcoin addresses are made with base58.

The procedure is pretty straightforward:

1. the version byte
2. the RIPEMD160 of the SHA256 (known as HASH160) of the sec format of the public key (don't worry too much about this part, just know it's 20 bytes long)
3. the checksum (4 bytes long)

Concatenate these and you have a 1 + 20 + 4 = 25 byte string which then gets encoded into a base58 string to form the bitcoin address. Note that parts 2 or 3 can be pretty much anything, but the version byte is specific to the network.

For your case, the version byte of testnet is 0x6f.

The documented procedure for calculating base58 is here.

Here is a simple python program to demonstrate how this is done:

alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
def b58(x):
    a = ""
    while x > 0:
        x, r = divmod(x,58)
        a += alphabet[r]
    return a[::-1]
print b58(0x6f0000000000000000000000000000000000000000)
print b58(0x6fffffffffffffffffffffffffffffffffffffffff)

The result of this program is this:

mfWxJ45yp2SFn7UciZyNpvDKrzbhuzkU7H
n4rZHAPGXCu8bYchjzJhK3V7VVredELJRc

That is actually the range of possible addresses within testnet. This is because anything before mfWxJ45yp2SFn7UciZyNpvDKrzbhuzkU7H would result in the first byte being 0x6e and anything after n4rZHAPGXCu8bYchjzJhK3V7VVredELJRc would result in the first byte being 0x70. Running vanitygen should confirm:

$ vanitygen -T mfWxJ3
Prefix 'mfWxJ3' not possible
$ vanitygen -T mfWxJ4
[...]

It's important to keep the version number in mind when generating vanity addresses for this reason.