Restarting Vanitygen

Question

I want to create a bitcoin address which starts with a certain passphrase (1mathias, case insensitive). That idea came from this question, and I quite liked it. After some trouble making the file on my Mac, it finally worked.

mbpssd2:vanitygen-master mathias$ ./vanitygen -i -t 4 1Mathias
WARNING: Built with OpenSSL 0.9.8y 5 Feb 2013
WARNING: Use OpenSSL 1.0.0d+ for best performance
Difficulty: 26838491360
[235.42 Kkey/s][total 2888131518][Prob 10.2%][50% in 18.5h]

It is running for quite some time now, and I want to stop it, and continue with finding an address tomorrow. For what I understand, is 1 in that number addresses that fit my passphrase. So if I would choose '1' as passphrase, there would be 1. The percentage showing in terminal is the current generated (and rejected) addresses, compared to the total amount. So reaching 100% doesn't have anything related to finding an address. I can happen at 0.01%, or at 70% or at 8012%, if you are really unlucky (right?)

From the creator of vanitygen I found the following:

If I stop vanitygen when it reports 60% complete, how do I have it restart where it left off?

You don't need to. The percentage displayed just shows how probable it is that a match would be found in the session so far. If it finds your address with 5% on the display, you are extremely lucky. If it finds your address with 92% on the display, you are unlucky. If you stop vanitygen with 90% on the display, restart it, and it finds your address with 2% on the display, your first session was unlucky, but your second session was lucky

But that does not make sense. If I reach 100%, I am not completely sure that an address has popped up, fitting my passphrase. Is this correct? If I let the program run, and generate a billion addresses, not stopping when (or if) it hit my passphrase, it is even likely that it finds a correct one in the first thousand, as in the last thousand?

I'm quite sure I am right, but I might be missing something. I tried to bold the two areas where I am not sure of.

Answer 1

Vanitygen works like this:

1. Generate a random 256-bit integer to use as an ECDSA private key

2. Compute the corresponding public key

3. Compute the hash of the public key to find the address

4. Check if it matches the requested pattern (1Mathias in your case)

5. If yes, halt and output the private key; if no, start over at step 1

Notice that there is no state saved in this process, so you lose nothing in stopping and starting as much as you want. Each random private key has an equal probability of success; it doesn't matter how many you have already tried.

For a given number N of random private keys tried, one can compute the probability that (at least) one of them would succeed. This is the "percent" number that Vanitygen reports - it's not a percent completion! In the excerpt you show, it says that it has tried 2888131518 keys, and that mathematically, trying 2888131518 keys has a 10.2% chance of finding one that works. It also says that in 18.5 hours, it will have tried enough keys that the chance of success is 50%. This does not scale linearly! If you are unlucky and don't find a key for 37 hours, it won't say 100%; it will say 75%.

As an analogy, suppose you have an ordinary 6-sided die, and you want to roll it repeatedly until you get a 6. Your chances of succeeding with one roll are 1/6 (16.6%); your chances of succeeding within 10 rolls are 83%; your chances of succeeding within 100 rolls are 99.9999987%. But this number never gets to 100%; there is no number of rolls that will guarantee success. There is always some chance that, of all the rolls you made, none of them came up 6.

So the "percent" number reported by Vanitygen is never going to reach (much less exceed) 100%. It is simply intended to give you an estimate of how long the process might take, but since it is random, there can be no guarantees. If it gets very close to 100%, all you know is that you have been very unlucky; but your odds of success with each new key are exactly the same as they always were.