Bitcoin Forum
October 20, 2018, 10:42:51 PM
 Welcome, Guest. Please login or register.
 News: Make sure you are not using versions of Bitcoin Core other than 0.17.0 [Torrent], 0.16.3, 0.15.2, or 0.14.3. More info.
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: How does vanitygen know when 100% is?  (Read 1301 times)
tkbx
Sr. Member

Offline

Activity: 350
Merit: 250

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

Offline

Posts: 1540075371

Ignore
 1540075371

1540075371
 Report to moderator
1540075371
Hero Member

Offline

Posts: 1540075371

Ignore
 1540075371

1540075371
 Report to moderator
1540075371
Hero Member

Offline

Posts: 1540075371

Ignore
 1540075371

1540075371
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1540075371
Hero Member

Offline

Posts: 1540075371

Ignore
 1540075371

1540075371
 Report to moderator
1540075371
Hero Member

Offline

Posts: 1540075371

Ignore
 1540075371

1540075371
 Report to moderator
TTBit
Legendary

Offline

Activity: 1136
Merit: 1000

 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
Sr. Member

Offline

Activity: 350
Merit: 250

 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: 2534
Merit: 1550

 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.

Bitcoin will not be compromised
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: 2534
Merit: 1550

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

Bitcoin will not be compromised
 Pages: [1]
 « previous topic next topic »
Jump to:

Sponsored by , a Bitcoin-accepting VPN.