How to determine valid vanity address prefixes for any starting net byte?

Question

Question inspired by this.

There are some combinations letters that will never produce a valid vanity address prefix for various network bytes. For example, for net byte of 52 (Namecoin), one cannot create addresses starting with

Na, Nb, Nc, Nd, Ne, Nf, Ng, Nh, Ni, Nj, Nk, Nm, Nn, No, Np, Nq, Nr, Ns, Nt, Nu, Nv, Nw, Nx, Ny, Nz, NL, NM, NN, NP, NQ, NR, NS, NT, NU, NV, NW, NX, NY, NZ

Given websites like Vanity Pool that outsource vanity address creation, creating a blacklist of address prefixes for every net byte would be a complicated task. How can one determine a valid range of address prefixes that can be created with any given net byte?

Answer 1

Casascius' Bitcoin Address Utility includes a Base58 calculator. You can input into it the lowest and highest values to encode to obtain the lowest and highest strings.

For example, to get the lowest Namecoin address, start with the hex representation of its network byte 52, which is 34, and add 40 zeroes (representing the 160 bits of the public key hash in hex). The result is MvaNCeVyvP6ZXYFWGpKaDX9ujEQ418F7sm. Likewise, to get the highest string use 34 followed by 40 f's, giving NKuyBkoGdZZSLyPbJEetheRhMjezbtjJCf.

Only 34-character strings which are between these two, in lexicographic ordering, can be valid Namecoin addresses. The ordering of the characters is compatible with ASCII, 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz, and thus most programming environments should be able to check the address with the built-in string comparison functions.

Specifically, the first 2 characters can only be one of the combinations between Mv and NK, which are Mv, Mw, Mx, My, Mz, N1, N2, N3, N4, N5, N6, N7, N8, N9, NA, NB, NC, ND, NE, NF, NG, NH, NJ and NK.

A more general approach is to decode the address into a number, and verify that the result is composed of the required version byte followed by any n bits (where n is the bit length of the encoded data, 160 in the case of a receiving address).