Vanitygen: Vanity bitcoin address generator/miner [v0.22]

[runeks]

Regarding the wish to be able to do distributed vanity address generation, the thought came to me that this might already be possible, if your method, BTCurious, of securely generating another person's private key is functional.

Now I'm no expert on the Bitcoin script format used in transactions, so I can only say it seems to me that this is possible in theory. Someone with more knowledge in this area will be able to confirm or deny whether this is actually possible.

Say I want a fresh, new-and-shiny vanity address and I am willing to pay for it. I create a custom transaction that contains Pub1 (using the terminology in BTCurious's post) and the desired vanity pattern, and broadcast it to the network. To redeem this transaction, someone must provide a Priv2 and Pub2 where the left-most x bits (determined from the desired vanity pattern specified in the transaction) in the hash of Pub2 matches the vanity-pattern specified in the transaction.
If the prize for successfully finding a Pub2 and Priv2 that allows the transaction-creator to get his desired vanity address is big enough (probably meaning that the prize is greater than if someone had spent the time mining instead), someone will go for it, eventually find this key pair and broadcast a transaction containing them to the network, thus spending the prize included in the initial transaction, and making public the Priv2 key so the transaction-generator can get his much-wanted pretty address.
The user desiring a vanity address might include a time-out on his vanity address generation request (not sure if this is possible either), such that if no one successfully spends the transaction in y days, the transaction becomes invalid and the Bitcoins are not lost.

[BTCurious]

Interesting idea! I'm not sure if the transaction script is powerful enough to do this; it would have to be able to do conversions from private to public key, and (bit)string editing and matching and such. Apart from that, the funding would be locked until something is found. And you would still have to somehow tell people that you've got an open request. If a site is made that could search for multiple people at the same time, it should be no problem to make an address request and only actually pay upon delivery. I'll ask some people working on multiple key signing if it may be possible.

[BurtW]

My first assumption is that Bitcoin uses the standard public/private key infrastructure (PKI) - the same one used for SSL - because that is what I am familiar with.  However, since I have never actually read up on it this is just an assumption on my part.  Given that Bitcoin uses the same public/private keypair infrastructure as SSL then the paramters are all defined as follows:

p  = first very large random prime number
q  = second very large random prime number
n  = pq (also a very large number)
m = lcm {p−1, q−1} (lcm is the least common multiple)
r  = is a selected coprime with m (r>1 and r and m have no factors in common), most commonly set to 0x10001 = 65537
s  = the unique s such that rs ≡ 1 (mod m)

The public key is made up of n and r

The private key is made up of n, r, p, q and s (m and n can be calculated from p and q - see above, and all you really need is n and s to decrypt - see below)

Encryption of message M is defined as Encrypt(M) = Mc = (M ^ r) (mod n)

Decryption of the encrypted message Mc is defined as Decrypt(Mc) = M = (Mc ^ s) (mod n)

I thought this was pretty standard terminology but I found that http://en.wikipedia.org/wiki/RSA_(algorithm) has it slightly different:

p, q, n are the same.  They have φ(n) where I have m, e where I have r, and d where I have s.

[BTCurious]

Nope, it's a bit different.

An EC private key is any random integer smaller than the field size*. This can be used to calculate a public key, which is a point in the field (2 coordinates). The reverse calculation, finding the private key given the point in the field, is unfeasible, just like factoring pq into p and q in SSL is unfeasible. This is what makes both SSL and EC secure.

*If you add your random integer to the other person's, you can just do mod fieldsize, and get an integer anyway.

I don't know the exact details of the encryption and signing. I just know you need the private key for that.

Anyway, if I were to define the keys in parameters, it would be significantly simpler than in SSL:

(F = the field, with predefined parameters. Basically you can do the same thing on different fields, but all of bitcoin uses secp256k1, so we don't need to communicate these parameters to peers at all.)
p = any random number, smaller than Fp (Fp = the field size, basically the amount of distinct private keys that exist)
[x,y] = a coordinate in the field, which can be calculated from p. (There exist Fp [x,y] pairs, so every private key corresponds to exactly one unique [x,y] pair, I believe.)

p is the private key
[x,y] is the public key.

If you want to learn more about it: I learned most from this paper: http://www.secg.org/collateral/sec1_final.pdf
It's actually very readable, just make sure you ignore the stuff that's not relevant to you. The bitcoin curve used is a prime finite field (Fp), not a characteristic 2 finite field (F2m), so just ignore paragraphs about F2m.
The specific parameters on secp256k1 can be found in: http://www.secg.org/collateral/sec2_final.pdf

And a site that helps with visualisation is http://www.certicom.com/index.php/ecc-tutorial
They have some interactive applets, 's nice

[BurtW]

I have updated this post and fixed all the glaring/embarrassing mistakes I made.  Please let me know if you see any others.  Keeping in mind this is all finite field mathematics on an elliptical curve - which is "hard” - I think the algebra is pretty simple and may now even be correct:

Using G as the base point on the curve and p as the private key then the public key P is defined as simply P = pG.  Therefore, the algorithm is as simple as BTCurious says:

Person 1 hands out a public key and a vanity request (or list of vanity requests) to the "vanity address miners"

The vanity address miners do the following:

1) Generate a random test private key from the finite field, let’s call it t.
2) Calculate the corresponding public key but instead of calculating it from the base point G calculate it from Person 1's public key, simple:  T = tP
3) Hash and check the generated public key T against the vanity criteria, if it does not match any of them then go to step 1) if it matches one then continue to step 4)
4) Transmit the private key found (t) back to person 1 [t could be easily encrypted using P]
5) Person 1 can then calculate the vanity private key from the private key sent by the miner (t) and the private key they originally generated (p) as follows:  P = pG, V = tP so V = t(pG) and V = (tp)G so the vanity private key is t times p.
6) Then the corresponding key V = (tp)G = vG is the vanity public key!
7) Person 1 can simply hash and double check the public key found (V) and then pay person 2 for their help.

This is VERY COOL, very simple and will work as far as I can tell.

[BurtW]

I have also updated this post and fixed all the glaring/embarrassing mistakes I made.  Please let me know if you see any others.  Keeping in mind this is all finite field mathematics on an elliptical curve - which is "hard” - I think the algebra is pretty simple and may now even be correct.  Also note that this idea will not work (even with the stupid mistakes corrected).  I decided to leave it here instead of just deleting it because possibly kicking around this idea with everyone here may lead to an actual solution.

The "vanity address miners" get multiple customer requests which are a public key and a list of desired patterns:

Customer 0:  P0, pattern list 0
Customer 1:  P1, pattern list 1
Customer 2:  P2, pattern list 2
etc.

Then the miners each generate their own random public key, let’s call it M.

Then for each public key in the customer list calculate the following.  [This is where the idea breaks down because upon further more careful reading of the specification I found that even though the EC system used is based on a prime finite field the points on the elliptical curve form a group, not a field.  This means that multiplication (and division) of points on the curve is not defined – which is what I really needed to get the idea to work.]

m0 = M / P0
m1 = M / P1
m2 = M / P2
etc.

Then run ALL the customer requests at the same time from the starting public key point M. If one of the vanity patterns matches, let's assume it was one of the patterns from customer 1, then transmit the public key t times m1 [mini proof: V = tM, M = (m1)P1, V = t(m1)P1] back to customer 1.  Customer 1 can then calculate the vanity private key from their private key p1 as v1 = p1 times t times m1 and the vanity public key is V1 = (p1)t(m1)G

So, I did not solve the problem but I did make a stab at it

Burt Wagner (donations for trying to 1BurtWEejbnKeBRsvcydJvsNztB1bXV5iQ)

[BTCurious]

Then for each public key in the customer list calculate a private key distance between the two public keys:

m0 = P0 - M
m1 = P1 - M
m2 = P2 - M
etc.

This is impossible. The public keys aren't neatly ordered in line, so you can't calculate the private key difference between any two public keys. The problem is that it's impossible to know anything about the private key, given that there's only the public key…

Edit: If this was possible, I would just generate a private P_M, get the public key M, and then get person 1's private key by calculating P_M - m1 = P1

[BurtW]

I made my two posts and then went to play hockey.  We lost in OT (darn).  On the drive home I realized that I had made several very embarrassing basic algebra mistakes.  But hey, it is not very often that I get to dust off my math skills and actually use them – so I am a bit rusty.  I am fixing the mistakes I know of in my two previous posts.

[BurtW]

Then for each public key in the customer list calculate a private key distance between the two public keys:

m0 = P0 - M
m1 = P1 - M
m2 = P2 - M
etc.

This is impossible. The public keys aren't neatly ordered in line, so you can't calculate the private key difference between any two public keys. The problem is that it's impossible to know anything about the private key, given that there's only the public key…

Edit: If this was possible, I would just generate a private P_M, get the public key M, and then get person 1's private key by calculating P_M - m1 = P1

You are correct in that my post was totally incorrect and that my idea will not work.  But, in my defense, as a side note, point addition and point subtraction are defined for the elliptical curve group.  Unfortunately it turns out that I actually need point multiplication/division to be able to get the idea to work and those operations are not defined.

[BurtW]

Final post from me for tonight (promise).  As BTCurious pointed out if I could do what I need to do in order to get my idea for the solution to the "multiple customer problem" to work then I could also simply calculate any private key from the knowledge of the public key (and the base point).  So, I am actually wondering if my idea could in fact be used as the basis for some sort of proof that the "multiple customer problem" cannot be solved.  Well, at least we know for sure it cannot be solved by my approach so I am giving up trying to solve it for now and going to bed.

[BTCurious]

Yup, your edit for the process (between two people) is correct now.

One small addition: An alternative to multiplying the two private keys, you could also make a scheme where you would add the two private keys. In my imagination, adding of bignums is easier than multiplying. In practice, you're using a bignum library (or python) anyway, so it doesn't really matter.

For completeness, here's the script with adding of private keys, instead of multiplying:

Using G as the base point on the curve and p as the private key then the public key P is defined as simply P = pG.  Therefore, the algorithm is as simple as BTCurious says:

Person 1 hands out a public key and a vanity request (or list of vanity requests) to the "vanity address miners"

The vanity address miners do the following:

1) Generate a random test private key from the finite field, let’s call it t.
2) Calculate the corresponding public key and add Person 1's public key, simple:  T = tG + P
3) Hash and check the generated public key T against the vanity criteria, if it does not match any of them then go to step 1) if it matches one then continue to step 4)
4) Transmit the private key found (t) back to person 1 [t could be easily encrypted using P]
5) Person 1 can then calculate the vanity private key from the private key sent by the miner (t) and the private key they originally generated (p) as follows:  P = pG, V = tG + P so V = tG + pG and V = (t+p)G so the vanity private key is t plus p.
6) Then the corresponding key V = (t+p)G = vG is the vanity public key!
7) Person 1 can simply hash and double check the public key found (V) and then pay person 2 for their help.

This is VERY COOL, very simple and will work as far as I can tell.

So yeah

Anyway

Final post from me for tonight (promise).  As BTCurious pointed out if I could do what I need to do in order to get my idea for the solution to the "multiple customer problem" to work then I could also simply calculate any private key from the knowledge of the public key (and the base point).  So, I am actually wondering if my idea could in fact be used as the basis for some sort of proof that the "multiple customer problem" cannot be solved.  Well, at least we know for sure it cannot be solved by my approach so I am giving up trying to solve it for now and going to bed.

Well, there's the trivial solution of just having N people, and then when person x's address is found, asking the other N-x people for their private keys.* Ideally you don't want to contact the other N-x people at all, but this seems impossible.

Imagine this was possible. Then, when a vanity address was found, I (as a host, or the person searching for addresses) would give all the information I have to the relevant customer. The customer would then calculate the vanity's privkey.
If this is possible, then I (as a malicious host (remember, we want a scheme where no one has to trust me)) can also act as a customer to my own service, I can duplicate the information I send to the vanity customer, send it to myself as a (fake) customer, and also calculate the private address.

The only way this could be made to work, is if somehow the vanityness of the address was involved, meaning the resulting private key could only be calculated by the person who actually submitted the vanity request. I wouldn't quite know how to do this. But then still, I could pretend to submit a shorter vanity address for every vanity address my customers submit.

So I think this scheme is impossible.

*The "trivial solution" is very possible, and may not be a bad idea. It just requires some coordination, and it requires people to leave their tool running. The tool could either be a program that does nothing, except respond to a getPrivateKey request from the rest, every now and then, or it could be an active searcher, helping in the search for the vanity addresses^¶. A proof of work principle could be employed, similar to coin mining°, to give these active searchers a share of the fees for the vanity address.
Ideally this could be done nearly identical to p2pool, but I know nothing of p2pool, so screw that, and just put in a "host", through which all communication is conducted. One problem is offline node detection though: When someone exits their program, everyone needs to start calculating from a new sum-public-point, which does not include that offline node's private key anymore.

°Imagine sending in every time you find an address that starts with 1111111, and its corresponding private key. The host would have to keep a list of seen 1111111 addresses though, to prevent cheating. Not ideal… may require more consideration. Alternatively, just pay the full fee to the person who found the vanity address. This is easier, but makes the payout more lottery-like. When there's lots of vanity requests, this doesn't matter.

^¶If these searchers have no requests, then they don't need to add their public point to the sum-public-point. This helps, because you also don't need to detect it going offline, he can stop whenever he wants.

[ByteCoin]

Solution:
1) Each party publishes their pattern list.
2) Each party generates a keypair and publishes the public key.
3) Everyone adds all the public key points together to get a common public key.
4) Everone searches from that point in some suitable fashion to avoid duplicating work until one of the patterns is matched.
5) The matching offset and all the other private keys are sent to the lucky "owner" of that pattern.
6) Cross off that pattern and go to 2.

A suitable searching strategy for n people would be as follows:
Agree on a numbering x of participants from 0 to n-1 inclusive.
Agree on a batch size m.
Each participant calculates m affine curve points (x+i*n)G where i runs from 0 to m-1 inclusive.
Each participant adds the common public key to each of the above m points, does a bulk inverse, hashes and checks for pattern matches.
If no match is found then the common public key is incremented by mnG and then the last step is repeated.

ByteCoin

[BTCurious]

Solution:
1) Each party publishes their pattern list.
2) Each party generates a keypair and publishes the public key.
3) Everyone adds all the public key points together to get a common public key.
4) Everone searches from that point in some suitable fashion to avoid duplicating work until one of the patterns is matched.
5) The matching offset and all the other private keys are sent to the lucky "owner" of that pattern.
6) Cross off that pattern and go to 2.

Yeah, that's roughly what I meant, however, when one of the "everyone" is suddenly disconnected, then point 5 can't be done anymore. So, as soon as there's a disconnection, all users need to generate the new common public key. But then you need to detect someone disconnecting, somehow.

[ByteCoin]

So, as soon as there's a disconnection, all users need to generate the new common public key. But then you need to detect someone disconnecting, somehow.

As soon as someone stops participating, the common public key is recalculated without theirs. To detect this each participant needs to send everyone else some sort of keep-alive signal signed with their private key every minute or so. This is an obvious solution.

ByteCoin

[runeks]

Interesting idea! I'm not sure if the transaction script is powerful enough to do this; it would have to be able to do conversions from private to public key, and (bit)string editing and matching and such. Apart from that, the funding would be locked until something is found. And you would still have to somehow tell people that you've got an open request. If a site is made that could search for multiple people at the same time, it should be no problem to make an address request and only actually pay upon delivery. I'll ask some people working on multiple key signing if it may be possible.

As far as I can tell, the only thing the transaction script would have to do is convert the actual public key (Pub2) into a Bitcoin address.
The transaction script can do that using OP_HASH160 as far as I can tell.
Assuming the vanity address only needs to match a certain prefix, ie. the start of the address matches "xxx", then a simple binary AND operation should be able to tell if the first x bits in the address matches the pattern that is specified in the original vanity address generation request transaction.
If we want to be able to find vanity addresses that match patterns in any position in the address, it would be a bit more complex, but still doable I think. Matching multiple patterns, or even a Regular Expression is a lot harder, but since using a reg ex slows down oclvanitygen considerably anyway, this probably isn't a going to be fulfilled, unless it's very simple. And if it is very simple, multiple, simpler transactions could be made instead.

Yes the reward that would go to whomever finds the valid address is locked until someone finds it. I haven't been able to find out whether it's possible to create a transaction that "times out" after a certain period, so that the reward is not lost in case no one can or wants to find the vanity pattern specified in the transaction.

Regarding telling people that I have a vanity address that they should search for; the Bitcoin network will propagate the vanity address generation transaction (VAGT from now on) to all nodes (like it will with all other transactions), and a special Bitcoin client will need to be run that can detect these special transactions and present them to a user who wishes to use compute power to try to find vanity addresses in exchange for Bitcoins. This client would leverage the technology of the original Bitcoin client (connecting to peers to get transactions, downloading the block chain etc.) but would only look for VAGTs and present them to the user:

Code:

One incoming vanity address generation request received:
Pattern: "1cheeses"
Using the hardware of this computer, this request will take, on average, 5.5 hours to find.
[A]ccept    [D]eny

This special client would then run oclvanitygen, oclvanitygen would run until the pattern is found and report the Priv2,Pub2 key-pair to the client, which would then create a transaction in the network that spends the reward by providing the Pub2 that, when converted into a Bitcoin address, matches the pre-defined pattern that was in the VAGT.
A website could easily be made where the back-end is this special client, and any user can go to the website, type in her desired vanity address pattern, deposit x Bitcoins and the website back-end creates the aforementioned transaction on the network and returns the result to the website user, when or if it receives one.

Regarding ByteCoin's proposal: why would we need to coordinate anything? Can't each worker just start at a random point, and the probability that two will work on the same keys will be extremely small?

[ByteCoin]

As far as I can tell, the only thing the transaction script would have to do is convert the actual public key (Pub2) into a Bitcoin address.

So the goal is to be able to buy a vanity address by crafting a transaction. It's easy enough to reward someone for finding a certain vanity address as explained by runeks but the act of claiming the reward should enable the person offering the reward to generate the private key associated with the vanity address.

To do this, the rewarding transaction must be spendable by providing a number which, when used to multiply the generator, yields a point which when added to a specified public key point yields a new public key point which hashes to a value that gives the required vanity address. Firstly, it seems hard to have a point multiplication routine in a script without looping constructs. I can see how it's possible to do in space roughly log₂ of the vanity difficulty. Secondly, implementing EC arithmetic in scripts would also be verbose. Thirdly, you'd have to that appropriate precautions to stop relayers from stripping your solution out of your transaction and claiming it for themselves.  

Finally, there is a way of generating time-limited transactions without nLockTime or a third party but it requires a couple of rounds of interaction and is extremely wasteful of computer time when used over long durations.

Regarding ByteCoin's proposal: why would we need to coordinate anything? Can't each worker just start at a random point, and the probability that two will work on the same keys will be extremely small?

Yes that works better.

ByteCoin

[runeks]

^ I blatantly admit to knowing very little about EC cryptography, so I was going off BTCurious' explanation which I took to mean that the search for a vanity address can be offloaded entirely to a untrusted third party, and the result needed to generate the private key for the vanity address can be made public without revealing the resulting private key.

Now I apparently didn't read the second paragraph very well, but if this means that an exchange must take place after each unsuccessful generation of a private/public key pair in search for a vanity address, it will obviously make this method unfeasible.

(The explanation assumes you know something about EC cryptography)
Person 1 makes a private key Priv1, and calculates the public key Pub1. Person 2 gets Pub1, creates a new private key Priv2, and adds (EC source point) * Priv2 to it, creating Pub2. Now, if Pub2 hashes to a nice vanity address Vnice, then Person 2 sends Priv2 to Person 1. Person 1 then adds Priv1 to Priv2, getting Privnice.

This is a way for Person 2 to help generating an address for Person 1. At the same time, Person 2 can search for his own stuff, and if he finds one of his own vanity targets first, he will instead request Priv1 from Person 1. Now Person 1 doesn't know Privnice. For further search, both Persons generate a new random private key, and they start over.

[ByteCoin]

Now I apparently didn't read the second paragraph very well, but if this means that an exchange must take place after each unsuccessful generation of a private/public key pair in search for a vanity address, it will obviously make this method unfeasible.

In an obvious extension of the method you quoted and also the slightly more general but essentially identical method I posted, no exchanges are required (apart from a keep-alive signal if desired) until a successful match has been found. Once all but the new vanity address owner's private keys have been revealed, new public keys must be distributed to securely search for new vanity addresses.

Pooled vanity address generation seems completely feasible.

ByteCoin

[BurtW]

So, as soon as there's a disconnection, all users need to generate the new common public key. But then you need to detect someone disconnecting, somehow.

As soon as someone stops participating, the common public key is recalculated without theirs. To detect this each participant needs to send everyone else some sort of keep-alive signal signed with their private key every minute or so. This is an obvious solution.

ByteCoin

First, I like the "adding keys" solution better than my "muliplying keys" solution so I suggest we go that route.

It seems to me there is a workable solution here all we need to do is solve a few logistical issues!  Fun.  Going off line is kind of a nasty issue in that from the time one participant goes off line to the time this is detected and the common starting point is recalculated the efforts of the entire network of participants is wasted.  I think there are two separate "going off line" use cases.

1) a participant decides to shut down for whatever reason - in this case an "I am going to stop participating" message could be broadcast.
2) a participant goes offline without a message (power failure, etc.) - in this case we want a mechanism to detect this as soon as possible and get back on track

In a peer-to-peer implementation could't we have each node monitor just it's connected nodes and then broadcast a "node X went offline" to the entire network as soon as it detects one of it's peers has gone offline?

[runeks]

So if I got this right:
If person A wants me to search for a vanity address for him, but I would also like to search for vanity addresses for n other people simultaneously, the result that I find, with which person A can generate his desired vanity address, is only usable to person A if he has a certain piece of information from all these n other people?