How does vanitygen know when 100% is?

[tkbx]

I've been messing around with vanitygen lately, and I can't help but wonder: How does it know where "100%" is? If it's trying random addresses, how does it know that after a certain number, there's a 100% chance that it will find the address you want?

[TTBit]

I've been messing around with vanitygen lately, and I can't help but wonder: How does it know where "100%" is? If it's trying random addresses, how does it know that after a certain number, there's a 100% chance that it will find the address you want?

It doesn't of course. Haven't used vanitygen in a while, and think it gives out a probability of 50% to start with? if it guesses at a rate of X/second and the probability of success of each guess is Y, the chance of success in the next second is 1-(1-Y)**X.

example:
I'm thinking of a number between 1 and 10,000. You have 10,000 guesses per minute. (blah blah, assume i get to choose new number after each guess)

The chance you hit in the next minute is 1-(1-0.0001)^10000 = 63.21%. If you want the 50% mark, solve as ln(.5)/ln(.9999) = 6931.125 guesses. Since you guess at 10,000 per minute, the 50% mark is in 6931.125/10,000 minutes or 41.59 seconds

And that is what vanitygen puts out, 50% chance in the next 41.6 seconds. If it still acts the same way, once 41.59 seconds goes by, it says 75% chance in the next 41.59 seconds, but it really means 75% chance in 83.17 seconds from when you started.

[tkbx]

I've been messing around with vanitygen lately, and I can't help but wonder: How does it know where "100%" is? If it's trying random addresses, how does it know that after a certain number, there's a 100% chance that it will find the address you want?

It doesn't of course. Haven't used vanitygen in a while, and think it gives out a probability of 50% to start with? if it guesses at a rate of X/second and the probability of success of each guess is Y, the chance of success in the next second is 1-(1-Y)**X.

example:
I'm thinking of a number between 1 and 10,000. You have 10,000 guesses per minute. (blah blah, assume i get to choose new number after each guess)

The chance you hit in the next minute is 1-(1-0.0001)^10000 = 63.21%. If you want the 50% mark, solve as ln(.5)/ln(.9999) = 6931.125 guesses. Since you guess at 10,000 per minute, the 50% mark is in 6931.125/10,000 minutes or 41.59 seconds

And that is what vanitygen puts out, 50% chance in the next 41.6 seconds. If it still acts the same way, once 41.59 seconds goes by, it says 75% chance in the next 41.59 seconds, but it really means 75% chance in 83.17 seconds from when you started.

Right, I didn't think about that. Must go from 75 to 93.75 to 96.875 to 98.4375, and so on.

[gmaxwell]

The numbers vanity gives are just bogus.

There is a fixed low probablity of finding a solution. The probability does not go up the longer you've gone... the expected time remains at the initial expected time forever, its just that eventually you get a surprise solution.

[lucasjkr]

It shouldn't be too hard to figure out how many possible addresses there are that start witha prefix of a certain length. So it knows how big the key space is. And it can report what percentage if that space has been searched 

Compare the estimated times when trying to generate an address with 4 leading digits compared to one with, say, 12. The number of possibilities when search for a valid key when you're only specifying 4 digits is huge compared to one where you're specifying 12 digits, and the progress indicator zips along when searching for the larger space.

So, I don't think its reporting random numbers.

What sucks is that it doesn't seem to remember where it left off; if you abandon a search after checking 90% of the keys and start again later, it might end up checking all the keys it checked the first time again. Or at least that's what the documentation indicates.

[gmaxwell]

It shouldn't be too hard to figure out how many possible addresses there are that start witha prefix of a certain length. So it knows how big the key space is. And it can report what percentage if that space has been searched 

The space is ~2^256 it will never search more than a very very tiny sliver of the space. Additionally there may, in fact, be _no_ solutions to your query (even a simple one like 1zzzzz*, though that is unlikely).  Moreover, the search is randomized. Even if there were a solution, and even if you did evaluate ~2^256 points you may still have not found it (and in fact could search forever without finding it).

It's not incorrect to show a longer expected time for a prefix of 12 than 4, of course. But what is incorrect is an indication that goes _down_.  If it tells you it will take 1 hour to find an 8 character prefix, it should tell you that it expects 58 hours for 9 indeed.  But if you've spent a half hour on your 8 character search and still not found one, it should still be reporting 1 hour. Not 30 minutes.  Your probability of finding a solution is not appreciably increased by all the times you've failed to find one because the probability is independent (given cryptographic assumptions).