Best way to calculate difficulty of generating specific vanity address?

Question

I'm now working at small tool, which purpose is to calculate difficulty (like number of attempts) of getting vanity address, like vanitygen (https://github.com/samr7/vanitygen) does. I've read some materials (https://en.bitcoin.it/wiki/Vanitygen#Difficulty_of_finding_a_vanity) and now i'm wondering about exact algorithm of how such calculation must be proceeded. There is no precise answer in the article at bitcoin.it wiki, so a look through the sources of vanitygen and ended up with some very basic ideas:

• All addresses are in a nutshell base58 numbers which can be converted to biginteger if needed.
• There is one final "biggest" address (like biggest number in the end of some range)
• Vanity address is any address from the range of addresses (if we think about them as numbers), that starts with specific pattern.

So what is the best way of finding difficulty of getting specified vanity address? I ended up with such idea:

1. Find the biggest possible address and convert it to bigint.
2. Find addresses range for given vanity pattern. First of all find the biggest possible address in the range by adding z to the end of the pattern while it is smaller than biggest possible address. Then to get smallest address in range i decided to add 1 (base58 representation for 0) to the vanity patter and i failed to determine when i must stop. Clearly address could not be longer than 34 symbols, but when i must stop? I think that i must take length of the biggest address in the range and that will be the same length for the smallest. But please, correct me if i'm wrong.
3. When we have range of addresses, we can calculate it's length by subtracting smallest one from biggest one and then divide biggest possible address by range length and the result will be our difficulty.

So is it all correct? What shall i do when pattern starts with "1"?

What additional materials you can suggest to read?

Answer 1

So things turned out to be a little bit different. But now i have a solution, that seems to be workable and adequate. Original task was to calculate difficult of finding specific vanity address (like vanitygen does).

Difficult is basically number_of_all_possible_addresses / number_of_addresses_with_vanity_prefix rate.

So, for example if we have only dec addresses between 0 and 9999, difficult for finding vanity address, that starts with "1" will be 10, because 10000 is the number of all possible addresses and only addresses from 1000..1999 will match, so there are 1000 of them.

With bitcoin addresses things are little bit more complicated, but principal is the same.

First let's find out how bitcoin address is formed: in a nutshell there is a couple of steps, that are important for our task:

1. Take one 0x00 byte (that will be first byte of address to represent it's version)
2. Take ripemd160 result (20 bytes, 160 bits).
3. Take first four bytes of sha256(sha256(ripemd160)) as checksum
4. Concatenate 0x00+ 20 bytes of ripemd + 4 bytes of sha256 of sha256 of ripemd
5. Now you get a 25-byte long something which you must treat as a long integer. We will call this number a "proto-address".
6. Base58Check it (but this is not very important now) and result will be the bitcoin Address.

However, what is important is understanding of the fact, that we can change only ripemd part. That leads us to two conclusions: first is that there are only 2^160 bitcoin addresses and second is a little bit more complicated.

Let's find answer to an important question: If A and B are numbers that starts with the same digit and there is an X such as A < X < B does it mean that X starts with the same digit? If A is 1000 and B is 1999 - yes it does. X can be any number from 1001 to 1998. But what if A is 100 and B is 10000? X can be any number between them and it must not start with the same digit. So A, X and B must have the same digit in the beginning only if they have equal number of digits. Keep it in mind, it is important.

Let's figure out, what is vanity address and what is base58 encoding.

Base58 is like base16 and base2 and base10 and like every other base. Symbol "A" for example is "A" in base58 and 0x09 in base16 or 9 in base10. That is a good point to start.

Let's decide that our address starts with "1A". We know that address is basically an integer of 25 bytes. What is "1A"? It is a "1A" in base58 and 0009 in base10. Or just 9.

That means that every number, which can be divided by 58 and will have a quotient equal to "9" will give us an "A" symbol during base58. For example 522/58 == 9. 30276/58/58 == 9. But not only those numbers will end up with 9, but these ones too:

• 9*58 + 58 -1
• 9*58^2 + 58^2 - 1
• 9*58^3 + 58^3 -1
• or just any (9 + 1)*58^N -1 number

So the formula is for the beginning of the range:

prefix*58^n

for the end of the range:

(prefix + 1)*58^n -1

Here comes an idea: we must find all ranges of numbers that will meet those requirements:

1. Number in the beginning of range and number in the end of range have equal number of digits
2. Lengths of these numbers must be equal to the length of proto-address. This is important because we must have an integer 25 bytes long that starts with a zero byte, it is the law!
3. Their values must be less than 2^192, because leading byte is always 00 and we have only 25 bytes, which leaves us with only 24 bytes or 192 bits which value we can change.

When we find all these ranges, we can find, how many numbers there are in the range by simply subtracting beginning of the range from ending of the range. The sum of all lengths of our ranges will be how many possible proto-addresses we can get.

But this is not the end. As we remember, proto-addresses are just all possible big numbers so not all of them can be converted to valid bitcoin addresses. But it is very simple to calculate how many of them can. Answer is 1/256^4. Why?

Because when we are generating bitcoin address, all we can change is the result of ripemd which gives us 20 bytes. Other 4 bytes are just checksum. Easy way to think about it is that we can have 2^192 proto-addresses and only 2^160 of them will be valid, because we can have only 2^160 valid bitcoin addresses. This gives us a 1/256^4 rate.

Final part: take sum of all our ranges lengths, divide it by 256^4 and this will be number of all possible bitcoin addresses with given vanity. Just divide 2^160 by this number and this will be the result.

Lets illustrate it by finding difficult of A prefix.

A is just 9. Ok, lets find out all ranges, that will give us 9 as a quotient. 522 - 579 30276 - 33639 1756008 - 1951119 ....... we must go and go until length of our numbers will not reach 24 bytes (mind the leading 00 byte) ........ 41735950621193504130037849728691446275009901558579068928 - 46373278467992782366708721920768273638899890620643409919

Both this numbers have length of 24 bytes. This is our first range. Next is

2420685136029223239542195284264103883950574290397585997824 - 2689650151143581377269105871404559871056193655997317775359

This numbers also are 24 bytes long.

Next pair will be 140399737889694947893447326487318025269133308843059987873792 and 155999708766327719881608140541464472521259232047844430970879

Both are larger than 2^192 so now we must stop. lets sum our results:

46373278467992782366708721920768273638899890620643409919 - 41735950621193504130037849728691446275009901558579068928 + 2689650151143581377269105871404559871056193655997317775359 - 2420685136029223239542195284264103883950574290397585997824 = 273602342961157415963581459332532814469509354661796118526

This is how many possible proto-addresses we can have. But do not forget to divide it by 156^4 and get: 63703009616853067642911677093369144589991624155

And this is how many possible bitcoin addresses we can have. Now just divide 2^160 by this number and the result will be 22

This is difficulty for prefix "A" or "1A". Now let's talk about some special cases. What you must check, when working with ranges is:

• length. Length of range must be equal to the length of proto-address and you must count all suitable ranges.
• 2^192. if end of the range is more than 2^192 you must cut this range from the top by value of 2^192 - proto-address can't be larger than 2^192. Also remember that beginning of the range must be always less than 2^192 (if not that does not make any sense).

What about special cases? Like patterns that start with more than one "1"? it is a little bit tricky, but not very complicated. "1" is a special case in base58 cos it is equal to 0. That means, when there are some "1"s in the beginning - all this bytes must be zeroed and can not be used. So our proto-address, if we want to start it with two "1" must have two zero bytes in the beginning. Like 0000XXXX.... if we want to have 111 we must leave 3 bytes as zero bytes in the beginning and so on.

What does it mean? Each 1 will cut one byte from our proto-address, so it will cut length of our possible biggest proto-address number by 8 bits or by one byte. That will make it 256 times harder to find and one byte shorter.

Like if we want to have 11 in the beginning we will have only 23 bytes to generate our ranges and if we want to have 1111 it will give us only 21 byte. So our ranges will be much smaller and difficult will be much higher. And obviously it is not possible to find any address if we have more than 19 "1" in the pattern, cos we must leave something to the ripemd result :)

If pattern starts only with 111, just count number of "1" and assume that beginning of range is 0 and end of range is 2^(200-8*number_of_1's) because we have only 200 bits for proto-address and some of them must be zeroed in case of our 111(1)-like pattern.

if we have pattern like 11(1)X(X) where X is non-zero symbol, just short max possible proto-address by number of bytes equal to number of 1's and do ordinary calculations.

Answer 2

Here is my solution which works fine for most cases, except contains only 1-s and very long prefixes:

function complexityForBtcAddressPrefixWithLength(bytes prefix, uint length) public pure returns(uint) {
    require(prefix.length >= length);

    uint8[128] memory unbase58 = [
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 
        255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 255, 255, 255, 255, 255, 255, 
        255, 9, 10, 11, 12, 13, 14, 15, 16, 255, 17, 18, 19, 20, 21, 255, 
        22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 255, 255, 255, 255, 255,
        255, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 255, 44, 45, 46,
        47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 255, 255, 255, 255, 255
    ];

    uint leadingOnes = countBtcAddressLeadingOnes(prefix, length);

    uint256 prefixValue = 0;
    uint256 prefix1 = 1;
    for (uint i = 0; i < length; i++) {
        uint index = uint(prefix[i]);
        require(index != 255);
        prefixValue = prefixValue * 58 + unbase58[index];
        prefix1 *= 58;
    }

    uint256 top = (uint256(1) << (200 - 8*leadingOnes));
    uint256 total = 0;
    uint256 prefixMin = prefixValue;
    uint256 diff = 0;
    for (uint digits = 1; prefix1/58 < (1 << 192); digits++) {
        prefix1 *= 58;
        prefixMin *= 58;
        prefixValue = prefixValue * 58 + 57;

        diff = 0;
        if (prefixValue >= top) {
            diff += prefixValue - top;
        }
        if (prefixMin < (top >> 8)) {
            diff += (top >> 8) - prefixMin;
        }

        if ((58 ** digits) >= diff) {
            total += (58 ** digits) - diff;
        }
    }

    if (prefixMin == 0) { // if prefix is contains only ones: 111111
        // NEED TO FIX BUG HERE!!!
        total = (58 ** (digits - 1)) - diff;
    }

    return (1 << 192) / total;
}

function countBtcAddressLeadingOnes(bytes prefix, uint length) public pure returns(uint) {
    uint leadingOnes = 1;
    for (uint j = 0; j < length && prefix[j] == 49; j++) {
        leadingOnes = j + 1;
    }
    return leadingOnes;
}

Here are my successful tests:

makeIt('1AAAAA', 259627881);
makeIt('1QLbz6', 259627881);
makeIt('1QLbz7', 837596142);
makeIt('1QLbz8', 15318045009);
makeIt('1aaaaa', 15318045009);
makeIt('1zzzzz', 15318045009);
makeIt('111ABC', 15318045009);
makeIt('1111ZZ', 888446610538);
makeIt('111111X', 50656515217834);

makeIt('1B', 22);
makeIt('1Bi', 1330);
makeIt('1Bit', 77178);
makeIt('1Bitc', 4476342);
makeIt('1Bitco', 259627881);
makeIt('1Bitcoi', 15058417127);
makeIt('1Bitcoin', 873388193410);
makeIt('1BitcoinEater', "573254251836560363813");

And wrong tests:

makeIt('111111', 1099511627776);
makeIt('1111111', 281474976710656);
makeIt('1BitcoinEaterAddress', "1265736312036992302053249573170410");

With errors:

Contract: VanityBTC should test difficulty for 111111:

  AssertionError: expected '1103823438081' to equal '1099511627776'
  + expected - actual

  -1103823438081
  +1099511627776

Contract: VanityBTC should test difficulty for 1111111:

  AssertionError: expected '282578800148737' to equal '281474976710656'
  + expected - actual

  -282578800148737
  +281474976710656

Contract: VanityBTC should test difficulty for 1BitcoinEaterAddress:

  AssertionError: expected '1.265736312036992302053249062715592e+33' to equal '1.26573631203699230205324957317041e+33'
  + expected - actual

  -1.265736312036992302053249062715592e+33
  +1.26573631203699230205324957317041e+33