(Shouldn't be too hard) Where vanitygen checks if the random address starts with the expected pattern?

Question

I've been trying the find the code in Vanitygen that does checks whether the generated address starts with the expected pattern.

Vanitygen repo: https://github.com/samr7/vanitygen

What I currently know:

• vg_output_match_console is called when the generated address starts with the expected pattern.

• vg_exec_context_calc_address generates the address as a byte array, which is probably used.

• get_prefix_ranges finds the range of the bignum of the address we want to generate, such that all bignums in that range start with the expected prefix.

• vg_encode_address generates the address in Base58, however is run only at the end.

• vg_prefix_avl_search seems to be an important part (that does what?)

Answer 1

Recall that vanitygen allows you to list several patterns and search for addresses that match any of them. It looks to me like for each prefix, we compute the range of hash160 values that, after base58 encoding, would match the desired prefix. (Conveniently, the checksum only affects the end of the address, so we don't have to worry about it.) These ranges are put into an AVL tree. Then vg_prefix_avl_search takes a generated hash160 and searches the tree to see whether it matches any of the desired ranges. Note this means that base58 encoding doesn't actually have to be done at all for addresses that won't match.

If we are in regex matching mode instead, then the relevant code is in vg_regex_test which is pretty straightforward: compute the base58 encoding and match against the given regexes.