Had a bit of a shower thought the other day about a fully decentralised vanity address request/redemption scheme. Basically, people could post their vanity address requests to the blockchain, by sending to a p2sh address, that somehow (begin handwaving) also encodes the requesters public key, and the desired address pattern. (/handwave)

The redeemer / finder of a vanity address would both publish their findings to the blockchain and claim the reward by providing a script + input that (begin handwaving) checks that the supplied private key yields a public key which, when combined with the requesters pubkey, compressed and base58 check encoded, results in an address matching the requesters address pattern. The script could also have a backdoor setup by the requester that allows them to reclaim funds, in case nobody is able to mine the vanity address after a sufficient amount of time. (/handwave)

Of course, there's a whole swathe of problems that prevent this from ever coming to fruition:

* the script is far too complex to ever encode using bitcoin's script primitives
* if it could be scripted, miners would most likely not bother with them, unless a hefty fee is levied
* the requester would need to broadcast the redemption script off the chain, so it's not really completely decentralised...

Might make for an interesting side chain project I guess