Topic: How does vanitygen find a pattern? (Read 528 times)

If you are tired of random, mysterious addresses generated by regular Bitcoin clients, you can use vanitygen to create a more personalized address. Add unique talent when you tell people to send bitcoins to 1stDownqyMHHqnDPRSfiZ5GXJ8Gk9dbjL. Alternatively, vanitygen can be used to generate random addresses offline.

Vanitygen accepts as input a pattern, or list of patterns to search for, and returns a list of addresses and private keys. Vanitygen's search is probabilistic, and the amount of time it takes to find this pattern depends on how complex the picture is, the speed of your computer, and whether you are lucky.

The example below illustrates a vanitygen session. This is typical and takes about 10 seconds to complete using my Core 2 Duo E6600 CPU on x86-64 Linux:

Code:
$ ./vanitygen 1Boat
Difficulty: 4476342
Template: 1Boat
Address: 1BoatSLRHtKNngkdXEeobR76b53LETtpyT
Privkey: 5J4XJRyLVgzbXEgh8VNi4qovLzxRftzMd8a18KkdXv4EqAwX3tS

Vanitygen includes components for performing an address search per processor (vanitygen) and your OpenCL-compatible graphics processor (oclvanitygen). Both can be built from a source, and both are included in the Windows binary package. There is also an oclvanityminer, vanity mining address of the client.

The way to look at this problem is the same as "How does Bitcoin find a new block", the answer is it looks for a new block with a leading number of 'zeros', now the time estimate to find that block is well known, thus say bitcoin can be tuned to find a block every ten-minutes at a predicted current hash-rate.

Now lets say your 'vanity coin' wants to be led by 3-zero's "000", then the hash-ALGO can randomly generate private-keys and keep churning until a '000' lead address is found, now it turns out that 3-zeros is rather quick say on a normal computer you can find that number in 20 minutes, for '0' [ one character ] its just a few seconds.

Say you want "FUCK", or "FUCKYOU" as your lead, now 4 might require a GPU card, and the 7 letter lead might require the GPU and 24 hours.

With bitcoin hashing, where there are 10's of thousands of miners,  they might find a block that has a number led by 32 zero's every ten minutes, but your talking about an astronomical hash-rate of every miner on earth.

Vanity-Gen has several algo's to find pattern's, they use a brute force compare, and also a sort-tree, as vanity-gen can not only generate one 'vanity address', but can generate 1,000's, that are in a particular order, so deciding how you want vanity-gen to 'find a pattern', is up to you the user, if you really want to understand all the algo's that vanity-gen uses to find patterns, then you need to READ THE SOURCE.

Finding a pattern is what is known as the 'grep' problem, or standard pattern matching algo's in sedgewick, It's not clear here if the question is 'how does vanity gen work', or 'how are patterns found'

In normal use of vanity-gen, its quite simple, the engine feeds a seed to ECDSA randomly to generate block of say 2048 private keys, those keys are converted to public-keys, then to hashed btc-addresss, and then a 'strcmp()' [ C algo library ], checks to see if that calculated address is led by your wanted N character's. If a match is found, then VG kicks out the private-address, public-key, and btc-public-address to YOU the user.

Now if your vanity-keys are a very complex hierarchy, then VG has GLUE that allows it to find an entire tree of VG addresses, but I  assume that 99% of VG users, are just generating one time vanity-addresses like 'EatMe'

First you need to know how the 8 bit (byte 00) + 160 bit (ripemd160) + 32 bit (checksum) of an address are encoded in base58 : https://bitcoin.stackexchange.com/questions/48586/best-way-to-calculate-difficulty-of-generating-specific-vanity-address

You got so far some inaccurate answers.
 
For each 22 addresses there is an address that starts with 1A, so we say that the difficulty of the prefix 1A is 22 (= number of addresses you have to generate on average to get a match).
Instead the difficulty of the prefix 11 is 256, i.e. 11xxx addresses are less than 1/10th of the 1Axxx addresses.

The formula 58^n is not correct at all, because the 58 characters don't have the same chance of happening.


How does vanitygen compute the probability?

Let's do an example with 1A prefix. Let T be the target set of the addresses 1Axxxxx. To get on average 1 match we have to generate 22 addresses.

Smaller is the target, bigger is the difficulty to hitting it and viceversa.

Let me rephrase this: difficulty * size of target = search space, in our case a small difficulty and therefore a big target ( it's easy to hit this target!):

number of keys we have to use (= numbers of addresses we have to generate to get on average 1 match) * number of addresses in T = 2^160 possible addresses.

Every time we try a new private key, we have 1 chance over 22 to hit our target set T (the probability is 1/22). At every roll then we don't hit the set T with probability 1 - 1/22. If we use k private keys, we don't hit T with probability (21/22)^k.
The probability of hitting T in k trials is then:

P = 1 - (21/22)^k

https://en.wikipedia.org/wiki/Geometric_distribution


If we want to have :

a 50% chance, 1 - (21/22)^k = 0.50 --> k = log(0.50)/log(21/22) = 14.9 tries (not 11!)

a 64% chance, 1 - (21/22)^k = 0.64  --> k = log(0.36)/log(21/22) = 22.0 tries

a 75% chance, 1 - (21/22)^k = 0.75  --> k = log(0.25)/log(21/22) = 29.8 tries (not 11!)

a 90% chance, 1 - (21/22)^k = 0.90  --> k = log(0.10)/log(21/22) = 49.5 tries

a 95.5% chance, 1 - (21/22)^k = 0.955  --> k = log(0.045)/log(21/22) = 66.7 tries (3 times 22!!)

a 99% chance,  1 - (21/22)^k = 0.99  --> k = log(0.01)/log(21/22) = 99 tries

and so on (100% only for k -> infinity).


On average it takes 22 tries to get 1 match, but if you do 22 tries only once you will have only a 64% chance to get a match!

And vanitygen computes right the probability to find a match in the particular sequence you are running, vanitygen doesn't compute anything "on average".

Thanks arulbero for saying what I wanted to add

No it's not:
I'm not saying the chance per roll increases, I'm saying the total chance increases. To make a casino example: the gambler's fallacy would be to expect a red ball after 10 black balls. It's a very human expectation to expe, and it's a fallacy because the human brain is looking for patterns even when they don't exist.
What I'm saying is that you'll get a red ball eventually if you keep trying long enough.

LoyceV is right.
The chance of your next roll is always 16.667%, but if you try 100 times instead of 5 your chance to get 1 (once or more) will be closer to 100% (1-(5/6)^100 against 1-(5/6)^5).

After n tries, P("do not get 1") = (5/6)^n  --> P("get 1 once or more") = 1 - (5/6)^n, and when you increase n (n -> infinity) then P -> 1. So this sentence:


is correct.

Example: I bet you 1.000.000 $ on this game: if I roll a dice 5 times and I got 1, you give me 1.000 $, otherwise I give you 1.000.000 $. Do you think it is a fair game? And if I rolled instead the dice 1000 times would be the game the same (=same odds)?
The game would be the same (from the point of view of the odds) only if after 995 rolls I didn't get a 1, then game 1 = game 2.

That's the classic gambler's fallacy right there... Assuming you are using "fair" dice, the chance is always 16.667%. It never increases and it never decreases, regardless of the number of rolls made.

It is not the number to have a 50% chance. It is the average number needed to find the correct key.

The correct amount of tries until you find the suitable private key (on average) is 2.207.984.167.552 (58^X with X = 7).
The amount of keys to have a 50% chance (on average) would be 1.103.992.083.776 (58^X / 2 with X = 7)


I have mentioned that's the average (multiple times). Is there anything else which you think is wrong (even slightly)? 

I'll (slightly) go against bob123's answer here: that number doesn't give you all possible combinations (it also gives you duplicate (wrong) combinations). Without doing the math, I guess it's the number of combinations you need to try for 50% chance of getting the right one.

Imagine a base6 system instead of base58, with numbers 1,2,3,4,5,6 (a dice). Say you want to roll a 1. No matter how often you roll, there's never a guarantee you'll get a 1. But you know the chance of your next roll is always 16.667%, and the more times you try, the more likely it becomes to roll a 1 eventually.

Basically, yes.

But you also could have found the private key to that address after your first or second key.
But on average, yes. You need to calculate that many keys to find an address with a prefix of 7 chars.

Since there is quite some good hardware available currently, this doesn't take too much time.

Thanks to both of you @HereTiK and @bob123.

Sorry I get what you mean now by 58 chars, I was thinking the wrong way.

I just thought there might be some specific way to branch the search out to get the desired goal in the end.

If you take my own address for example : 1KingZeeW97uLvngcUA3R6QJx18Fn78ddb

You're basically telling me that I need this many keys 2.207.984.167.552, -at least- to run through every possible combination of 7-letter words, and maybe land into the pattern I want.

While I do believe now that there probably isn't a better way, this just looks like a very awkward Hoyle's fallacy to me...

58 is correct because bob123's calculations are based on the address being in encoded in Base58, not on the address being 34 characters long (the last couple characters being a checksum and thus mostly irrelevant for generating a vanity address anyway).

So what bob123 means is that if you want 1 (one) specific character (out of the 58 that Base58 gives us) you'll have to calculate 58 private keys on average to get the result you want (you could be lucky and hit on the first try, you could be unlucky and take forever). If you want to get 2 (two) specific characters (in the specific order you defined) you'll have to calculate 58 * 58 private keys on average to get the result you want. etc. etc.

I don't know how this specific vanitygen works in terms of displaying the estimated time.
But searching randomly is the best approach (You can't get better than randomly searching; searching successively would create vulnerabilities since those private keys wouldn't even be close to random anymore).

Calculating the maximum amount of time and the time it takes to have a 50% probability is the same for all vanity address generator.





34 (more or less) is the length of the address. But the set of possible characters is 58 (addresses are encoded in base58). The charset is:





If you want to have 1 (specific) out of 58 characters at the first position, you need to generate 58 private keys (which will result in 58 addresses starting with different characters ON AVERAGE, since the hash function is producing a pseudo-random output).

For 2 chars, you need to create 58 * 58 addresses (which also means creating 58*58 private keys) to get your desired prefix (again: on average).

Therefore it is: 58^X with a prefix of X chars to find the correct private key / address. And for a 50% probability (how it is displayed in another vanitygen (not sure about the name currently)) you'll have to divide it by 2.
Therefore (58^X) / 2 for a 50% probability.





It doesn't get you any closer.

You are just calculating a massive amount of private keys (and addresses) until you have found one with the desired prefix.
There is no elimination at all.

You can compare it to calculating the probability of having 10 times a 6 in a row when rolling a dice.

You can not predict when you will have those 10 6's in a row. But you can mathematical estimate a number of rolls to get a 50% probability (it gets boring, i know.. but: on average).


So, vanitygens DO randomly generate private keys. They estimate that you need Y private keys (and therefore addresses) generated until you have found your desired one.

@bob123 Thanks for the answer! A few things I have to question..


Are you sure? I thought it showed worst case scenario time? I'm talking about samr7's vanitygen. I know it might take a lot less if you get lucky, but it shouldn't go above that time. It calculates the time to reach 100% probability of getting a specific pattern.


You mean 34? The pattern is inside the address, not the private key! I'm going to edit your maths in the next quote.


See this part I don't understand. How are you calculating all this? The pattern is in the output, not the input.

You could generate a private key, get an output of 1SomeBTCAddressxxxxxxxxxxxxx, generating just the neighbor of that key, will give you a completely different output.

See what I dont understand is how does calculating n number of private keys, gets you closer to generating your wanted private key. How does the process of elimination go? If it were truly random then we'd just be blindly generating random keys constantly.

In fact, it is randomly generating private keys, trying to find a private key which results in an address with the desired prefix.

The estimated time can be calculated using stochastic. Note that this time is always an average. There is never a guarantee that you'll find your desired private key in the estimated time.
It might take 1 second or 10 years.

Since the hashing function is generating a pseudo-random output, you can calculate how much private keys needs to be generated to find an address with a specific prefix (on average!).

To be more precise:
There are 58 different characters inside an address. To find a private key which results in an address with the prefix of 1 chosen character, you'll need to calculate 24 (= 58 / 2) private keys to have a 50% probability.
To get an address with a prefix of 2 chosen chars, you'll need to calculate 1682 (= 58 * 58 / 2) private keys ( to have a 50 % chance of finding a suitable private key).

The formula for X chosen chars (with a 50% probability) is:

Can anyone explain to me the concept or link me some source that explains how can vanitygen find a pattern in an unreversible hash?

It's clearly following some search pattern that isn't just trying out random private keys and hoping to find the desired pattern. People can let it run for weeks to find a 8-char pattern for example. And it'll slowly display the probability percentage until it finds one. I'd like to know the maths behind that if anyone can give me a clue, cheers.