Outsourcing vanity address generation

[Meni Rosenfeld]

Tools such as Vanitygen used to generate vanity addresses, Bitcoin addresses which follow a specific pattern, have been somewhat popular.

Generating a vanity address is a computationally intensive task, more so the more specific the pattern. It is conceivable that some people would like a vanity address but lack the appropriate hardware to generate it. Others may have the necessary hardware but not sufficient interest in an address. This suggests the need for a vanity market where clients outsource the production of addresses to generators for an agreed upon fee.

Ostensibly, this suffers from the problem of the need for secrecy - whoever generates the address has access to the corresponding private key, but the client who is to be the owner of the address must remain the sole person knowing the private key. This problem can be solved with some ECDSA magic of the kind discussed here.

The way it would work is this:

1. Client generates himself a single private key c and corresponding public key c*G. He also chooses a pattern P.
2. Client keeps c secret, but submits c*G and P to the generator.
3. Generator repeatedly generates a private key g, calculates g*c*G and checks if the address generated from the public key g*c*G matches the pattern P.
4. #3 is repeated until a match g is found.
5. Generator submits g to the client. The client uses g*c as a private key and g*c*G as the corresponding public key, which maps to the desired vanity address.
6. The generator, not knowing c or g*c, cannot claim coins from the generated address.

The procedure can be modified so that instead of using g*c as the private key and g*c*G as the public key, the private key will be g+c and the public key will be g*G+c*G. This is deemed less secure, but I believe is suitable for this application and may be less computationally expensive.

[1715034911]

1715034911

[1715034911]

1715034911

[BurtW]

As you may know I have given this a lot of thought (in other threads) and would like to be involved in this.  I will post a list of the issues later today.

[Gavin Andresen]

Just thinking out loud...

... but vanity addresses using 1-of-2 multisignature transactions and BIP 13's new bitcoin address format could be orders of magnitude easier to generate.

You'd start with a normal keypair.

And simply compute the hash of the public key and another, arbitrary, "I don't have the private key but I don't care" public key (in an "OP_1 <public_key> <don't care public key> OP_2 OP_CHECKMULTISIG" transaction type).

You'd always spend the funds sent to the vanity address using pk1.

No expensive ECDSA addition or multiplication required, just lots of SHA256/RIPEMD160 hashing and base58 encoding and string comparing.

-----------

Widespread use of the new pay-to-script address format will have to wait until "everybody" upgrades to support it, though. And it does make transactions larger (2 public keys instead of 1) than the find-the-right-private-key solution.

[mcorlett]

Subscribe.

Nice work Burt, Meni, and whomever else was involved in coming up with this.

[BurtW]

1-of-2 multisignature transactions and BIP 13's new bitcoin address format

Wow, that does sound a lot easier.

Are these features available now?  If not when are they expected to be available?

If you have it handy can you give me a link to the new bitcoin address format?

Edit, nevermind, found it https://en.bitcoin.it/wiki/BIP_0013

[BurtW]

So the creation of vanity addresses that start with 3 could still be distributed/outsourced using either the * or + shared key creation options mentioned in the OP.

1) Customer creates a key pair and sends out the public key to the vanity address miner(s).
2) The vanity address miner creates a second keypair
3) Then the miner creates the final public key by either adding the two public keys or by multiplying the miners private key and the customers public key
4) Using this final key the vanity address miner tries various randomly generated "filler" keys in the script until the hash of the script creates the desired vanity public script address.
5) The vanity address miner then turns over the second keypair they used plus the randomly generated "filler" key to the customer.

So once we start using this new public address scheme I expect we will be able to create much longer vanity addresses as the amount of computation per trial is greatly reduced.

[BurtW]

Just to make sure we are on the same page I am cross posting this description of the proposed algorithm:

To do this would take a new version of the vanitygen (and GPU version of vanitygen) that does all the proper calculations in order to create the proper script and proper hash of the script.

The nice thing is that each trial in the search for the vanity address would be much faster.  In this future system the algorithm is:

1) Create a valid keypair
2) Create a random invalid/bogus public key (basically a nonce).  Note the private key is unknown/unknowable
3) Create a valid "use one of these two keys" script with the valid public key and the bogus public key as the two parameters
4) Properly hash the script (much easier that a public key calculation)
5) Check for the vanity pattern, if it matches quit, otherwise go to step 2)

Note that each trial is now just the time it takes to generate a random number and take the hash of the script!

[Meni Rosenfeld]

As you may know I have given this a lot of thought (in other threads) and would like to be involved in this.  I will post a list of the issues later today.

I tried to search for prior mentions of this application but couldn't find any. Probably should have searched harder, I see now there are in the next-to-last page in the VanityGen thread.

So the creation of vanity addresses that start with 3 could still be distributed/outsourced using either the * or + shared key creation options mentioned in the OP.

If we're going for general scripts we don't even need these EC operations. Use an A & (B|C) transaction (that's possible, right?) where A is generated by the client, B is generated by the miner and C is filler.

Edit: A is what allows you to outsource the generation without doing EC addition/multiplication per attempt.

[BurtW]

Sorry, my posts above kind of got ahead of this thread.  There is a lot of history on this subject burried in the vanitygen thread and other threads.  The "holy grail" of the project is to be able to have multiple miners and have each miner searching for the patterns of all the customers at the same time.  That is why it appears I am doing unneeded work there.  I will dig up some of those old posts and get them moved over here.

Basically the idea is to combind all the keys from all the customers so you can do one trial and then check the result against all of the customer requests.  If you find the desired pattern for any one customer then you stop, give the result to that customer, and then the process starts again.

[deepceleron]

I have a new invention: unsolicited outsourced vanity address generation

It kind of works like this:

Address: 1Lukejrwhew7sj4TvWCKksaVo7aLpedHDt
Privkey: 5JB53xyWq9i81tBF2Tud9bpQwk1R2mjQA7gXNDHwp6QyiZC2T7K

[dayfall]

I have been generating vanity addresses for a long time.  No doubt I have some that people would want but not the ones I am looking for.  Oh well, I am hoping we can all get together and combine out computing power.  Untill then, does anyone know of a gpu generator that searches a user supplied dictionary all at once?  I think the one that exists now only does one word at a time.

[deepceleron]

..does anyone know of a gpu generator that searches a user supplied dictionary all at once?  I think the one that exists now only does one word at a time.

The answer belongs back on the vanitygen thread, but here's your option:
-f <file>     File containing list of patterns, one per line

oclvanitygen -k -f ListOfWords.txt -o FoundAddresses.txt

---
Steering things back on course:

"filler", as used above, would be a "nonce".

From a glance-through read, it would appear that one would only be able to generate addresses for a single client at a time. Am a wrong, that the hashing and checking will find an address that would work for just one client. Currently, you hash once and see if the public address has any matches from an arbitrary list. Without the benefit of mining vanity addresses for multiple clients while looking for your own too, with minimal performance penalty, it doesn't seem an endeavour worth pursuing.

The second concern would be how to deal with distribution and bounties; now I'm thinking maybe something could be done better than just posting wanted addresses in a forum.

[BurtW]

Ok here is the idea and the issue.

Add all of the public keys from all customers into a "grand total" public key.  If A, B, C, etc. represent the public keys of all the customers then T = A + B + C ...

Now for type 1 addresses:
  r represents a random private key
  X = r*G + T (or could be X = r*T) represents a trial
  Hash X
  Test against all patterns from all customers

For a type 3 address
  R represents a random pseudo public key
  Hash the script "T or R"
  Test against all patterns from all customers

When an address is found for customer Z

You now need to broadcast a request to all the customers and all the customers need to cooperate by sending their private keys to customer Z
Given their own private key and all of the private keys from all the other customers and finally either r or R from the miner the customer has all they need to create the vanity key pair and vanity address

Obviously customer cooperation required - but I think that can be solved.

The biggest issue is that if any one customer "goes away" and they never transmit their private key to Z the entire thing falls apart.

Assuming all goes well everyone generates new key pairs, sends out their new public keys to the miners and the process starts again.

[Meni Rosenfeld]

From a glance-through read, it would appear that one would only be able to generate addresses for a single client at a time. Am a wrong, that the hashing and checking will find an address that would work for just one client. Currently, you hash once and see if the public address has any matches from an arbitrary list.

This is a challenge. One possible approach (and again I hope I'm not reinventing the wheel) is to have a body of n arbiters which are assumed do not all collude. Each will generate a private key bi and public key Bi. The Bi's will be distributed among miners. The miner generates a pair d, D and tries different nonces C in the transaction script (B1 & B2 & ... & Bn) & (C | D) . If the resulting address matches a pattern, he informs the arbiters who the client is. He sends C to the client and each arbiter send his bi to the client. Each arbiter then deletes the key and generates a new pair to be used for the next completed address and broadcasts the public key to all miners. Then the only way to steal the funds is if all arbiters collude and share the client's keys.

Without the benefit of mining vanity addresses for multiple clients while looking for your own too, with minimal performance penalty, it doesn't seem an endeavour worth pursuing.

This endeavor is worth what its purchaser will pay for it. I can think of two main reasons to use vanity addresses:

1. Well, vanity - to show the world you have an intensional address with a harder pattern than other people. Then it doesn't matter at all how hard or easy it is, there will be a market of those who want harder than average.

2. To have a simple firstbits address - then generally you want the vanity pattern as short as possible while being unique. The length it takes to be unique is fixed, so if generating addresses is too easy there will be no market for generation since anyone can generate the required address.

So, harder generation is better for generators and for businesses wanting to protect their brand, indifferent for most other people.

[Meni Rosenfeld]

Obviously customer cooperation required - but I think that can be solved.

The biggest issue is that if any one customer "goes away" and they never transmit their private key to Z the entire thing falls apart.

This of course can be solved with a deposit system. A customer pays a deposit to a miner for including him in his search. If the customer defects the miner confiscates the deposit, and if the customer wants to quit (say, if someone found him an address) he gets the deposit back. The size of the deposit needs to cover the average cost of a squandered address. The deposit size can be reduced if the miner periodically quizzes the client, then the deposit only needs to equal the worth of the work between quizzes. This requires the client's system to be online at all times.

This will work much better if instead of direct interaction between clients and miners, there will be a small number of "vanity pools" which accept contracts from clients and keeps deposits, and distribute work to miners. Pools can build some sort of reputation so clients can feel safe keeping a deposit with them.

For a type 3 address
  R represents a random pseudo public key
  Hash the script "T or R"
  Test against all patterns from all customers

This needs to be "T & (P | R)" where P has a private key and R is a nonce. Otherwise the miner could maliciously generate R with a private key and steal the money.

[Gavin Andresen]

I hate to inject gloom and doom into a fun topic like vanity bitcoin addresses... but y'all should be aware that one of my longer-term goals for the Bitcoin system is to make bitcoin addresses disappear. I hope Bitcoin software 10 years from now tells users "You're about to pay 11 micro-Bitcoins to Amazon.com" and not "2mRwtf8blahblahblah". And I'm not alone, I know Mike Hearn feels strongly about making bitcoin addresses go away for ordinary users.

If you do spent lots of time creating The World's Best system for mining vanity bitcoin addresses, please don't be upset or surprised if you find it is obsolete when "Bitcoin 2017 Turbo++ Enhanced Edition" is released.

[Meni Rosenfeld]

I hate to inject gloom and doom into a fun topic like vanity bitcoin addresses... but y'all should be aware that one of my longer-term goals for the Bitcoin system is to make bitcoin addresses disappear.

This will make vanity addresses even better, they'll be like collector's items .

But I'm guessing the techniques we are developing here may have some use even if Bitcoin addresses as we know them become obsolete.

ETA: Also, if I understand correctly, some form of address will still be used as an implementation detail, but just won't be externalized to end users. In this sense they will be like IP addresses - nobody knows which IP they're visiting, but they still exist. I suspect that if one could get a "vanity IP address" there would be a market for that, so no reason Bitcoin addresses would be different.

So, gloom and doom injection thwarted .

[mcorlett]

I hate to inject gloom and doom into a fun topic like vanity bitcoin addresses... but y'all should be aware that one of my longer-term goals for the Bitcoin system is to make bitcoin addresses disappear. I hope Bitcoin software 10 years from now tells users "You're about to pay 11 micro-Bitcoins to Amazon.com" and not "2mRwtf8blahblahblah". And I'm not alone, I know Mike Hearn feels strongly about making bitcoin addresses go away for ordinary users.

So what's the game plan, more specifically?

[FreeMoney]

I hate to inject gloom and doom into a fun topic like vanity bitcoin addresses... but y'all should be aware that one of my longer-term goals for the Bitcoin system is to make bitcoin addresses disappear. I hope Bitcoin software 10 years from now tells users "You're about to pay 11 micro-Bitcoins to Amazon.com" and not "2mRwtf8blahblahblah". And I'm not alone, I know Mike Hearn feels strongly about making bitcoin addresses go away for ordinary users.

If you do spent lots of time creating The World's Best system for mining vanity bitcoin addresses, please don't be upset or surprised if you find it is obsolete when "Bitcoin 2017 Turbo++ Enhanced Edition" is released.

If you don't get to it maybe these ideas will give us 1amazonamazonamazonamazon5jw

:-)

[farfiman]

I hate to inject gloom and doom into a fun topic like vanity bitcoin addresses... but y'all should be aware that one of my longer-term goals for the Bitcoin system is to make bitcoin addresses disappear. I hope Bitcoin software 10 years from now tells users "You're about to pay 11 micro-Bitcoins to Amazon.com" and not "2mRwtf8blahblahblah". And I'm not alone, I know Mike Hearn feels strongly about making bitcoin addresses go away for ordinary users.

If you do spent lots of time creating The World's Best system for mining vanity bitcoin addresses, please don't be upset or surprised if you find it is obsolete when "Bitcoin 2017 Turbo++ Enhanced Edition" is released.

I really like those 3 really big hopes.

1)Bitcoin is still with us in 10 years
2)Amazon accepts bitcoin
3)You can buy something at amazon for micro-btc