Bitcoin Forum
December 02, 2022, 11:24:47 PM
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: How does vanitygen know when 100% is?  (Read 1345 times)
tkbx (OP)
Sr. Member

Offline

Activity: 350
Merit: 251

 October 19, 2013, 02:07:00 AM

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?
1670023487
Hero Member

Offline

Posts: 1670023487

Ignore
 1670023487

1670023487
 Report to moderator
1670023487
Hero Member

Offline

Posts: 1670023487

Ignore
 1670023487

1670023487
 Report to moderator
"You Asked For Change, We Gave You Coins" -- casascius
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
TTBit
Legendary

Offline

Activity: 1136
Merit: 1001

 October 19, 2013, 02:38:54 AM

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.

good judgment comes from experience, and experience comes from bad judgment
tkbx (OP)
Sr. Member

Offline

Activity: 350
Merit: 251

 October 19, 2013, 02:59:55 AM

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
Moderator
Legendary

Offline

Activity: 3822
Merit: 7211

 October 19, 2013, 03:10:33 AM

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
Hero Member

Offline

Activity: 644
Merit: 500

 October 19, 2013, 10:11:55 PM

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
Moderator
Legendary

Offline

Activity: 3822
Merit: 7211

 October 20, 2013, 01:31:07 AM

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).

 Pages: [1]