One can easily generate vanity addresses for Bitcoin, but they can take quite awhile to generate. Outsourcing that process to someone with a strong mining rig is an option, but then one runs into the risk of the person generating the address using it without our knowledge to steal our coins. Is it possible to generate vanity addresses in such a manner so as to make it impossible for anyone to steal your private keys?
From what it appears, yes, it is possible, and quite simple really to outsource vanity address creation to a third party without risking anything.
Bitcoin addresses are created from ECDSA keypairs. Their property is that if you take two private keys and add them together (with appropriate modulo operations), the sum will map to a public key that is the same one as one would obtain by adding the two public keys corresponding to the private keys.
This means that in order to outsource vanity key generation, one can create an ECDSA keypair, store the private key safely, and give out the public key to other people. They would then proceed to generate ECDSA keypairs, summing the generated public keys to the one provided by you, and checking whether they map to the appropriate vanity address. If it does, they need only to give you the appropriate private key, which you then need to add to your secret private key in order to obtain the private key that maps itself to the vanity address.
JoelKatz explained it in his post, and I went ahead and implemented a "vanity pool" that enables such outsourcing. Moreover, I also created a simple testing suite for playing with combining the ECDSA keypairs. Currently there are no "split key vanity miners" available, nor any offline solutions for this problem, but they can follow shortly.
Thanks to Elliptic Curve cryptography, a third party doesn't need to know the private key to generate a vanity address, as JoelKatz describes here:
I'll be talking about the details.
An ECC public key is of the form
G is the generator point (a curve parameter) and
d is your private key (must be between
prime order-1 inclusive)
d can't be found without brute-forcing points, if you know the public key (
The goal is to make someone find an appropriate
Hash(dG) is in the expected range.
So, you'll need to be keeping a part of
d to yourself, and then combine it. How?
For all methods, the beginning is the same:
You calculate some
d_1 and keep it to yourself, while sharing
To start with, let's review the properties of EC points.
(d_1)G + (d_2)G = (d_1 + d_2)G
(d_1)(kG) = (k * d_1)G
Method 1) Additive
This is the method used by Vanitygen, and it's way more popular than the others.
A bounty hunter tries many random
d_2 values that make
Hash((d_2)G + (d_1)G) in the expected pattern range. If the hunter succeeds, he sends
d_2 to the bounty giver (either public or private). Now the vanity "assigner" can combine
d_2 to create the final private & public keys.
(d_1 + d_2)G can also be calculated by third parties, which means other people will be able to track his/her payments. (because
d_2 can be shared by the bounty hunter,
G is already known, and
(d_1)G was published by the assigner, so
(d_2)G + ((d_1)G)) This also applies to all known methods.
Method 2) Multiplicative
This is used rarely.
Now that the bounty hunter wanted
Hash((d_1 + d_2)G) in the expected pattern range, he wanted something different, and used a different way to do trustless vanity generation.
The innovative bounty hunter calculates a
d_2 value, by brute-forcing
Hash(d_2((d_1)G)): He computes multiples of
(d_1)G and checks them.
Now, do you understand that
d_2 must be between
prime order-1, also in this method? (Hint: What's the meaning of the prime order?)
It uses the fact that
d_2((d_1)G) = (d_2 * d_1)G (with appropriate modulo operations)
Method 3: Combined
I've never seen this mentioned anywhere. It's not very useful.
Simple: The bounty hunter finds
d_3 values such that
Hash((d_1 * d_2)G + (d_3)G) is in the expected pattern range. This is more complex, because it has two variables. No research has been made on this. At first glance, it looks slower, but there's nothing that stops the vanity miner from fixing