Bitcoin Forum
December 17, 2017, 01:19:28 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: How does vanitygen know when 100% is?  (Read 1287 times)
tkbx
Sr. Member
****
Offline Offline

Activity: 322



View Profile
October 19, 2013, 02:07:00 AM
 #1

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?
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513473568
Hero Member
*
Offline Offline

Posts: 1513473568

View Profile Personal Message (Offline)

Ignore
1513473568
Reply with quote  #2

1513473568
Report to moderator
1513473568
Hero Member
*
Offline Offline

Posts: 1513473568

View Profile Personal Message (Offline)

Ignore
1513473568
Reply with quote  #2

1513473568
Report to moderator
TTBit
Legendary
*
Offline Offline

Activity: 1136


View Profile
October 19, 2013, 02:38:54 AM
 #2

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 Offline

Activity: 322



View Profile
October 19, 2013, 02:59:55 AM
 #3

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
*
qt
Offline Offline

Activity: 2366



View Profile
October 19, 2013, 03:10:33 AM
 #4

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

Bitcoin will not be compromised
lucasjkr
Hero Member
*****
Offline Offline

Activity: 644


View Profile
October 19, 2013, 10:11:55 PM
 #5

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
*
qt
Offline Offline

Activity: 2366



View Profile
October 20, 2013, 01:31:07 AM
 #6

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]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!