I was researching how to improve the speed of generating vanity addresses and I came up with two ideas:

The first was using a non-standard encoding of the public key. For example, if you use uncompressed public keys and you pad the x and y values with between 1 and 10 prefix zeros, you can create 100 different addresses which, when hashed by SHA256/RIPEMD160 will give you 100 different Base58 strings. The overhead of every pubkey will upto 20 bytes. To enumerate these addresses you only need to execute the hash functions and you don't need to compute elliptic curve operations (just one every 100 double-hashes).

But the problem with this approach is that, to redeem the funds of a previous output, you have to put in the script the non-standard encoding of the pubkey. This in turns presents two problems. First is that you need a patch for the client to do it, or do it manually with the RPC interface. The second problem is that beginning with version 0.8.3 of the Satoshi client, public keys are checked for canonical encoding. So the redeem transaction won't be relayed by the network anymore. You can still send it directly to a miner, but that's a huge limitation.

I wanted to do it in a way that could be as standard as possible. Then I came up with this idea:

Instead of generating normal vanity address, generate a P2SH vanity address for a script containing a 1-in-2 multisig transaction. The first public key is the user's "non-vanitized" pubkey key (that will be "vanitized") . The second pubkey is a nonce, in compressed public key format.
I call these addresses "P2SH/M", to differentiate from all other formats. P2SH/M addresses, as P2SH addresses, begin with the base58 digit "3".

This is how the address actually works in the scripts:

scriptpub: OP_HASH160 [20-byte-hash-value] OP_EQUAL
scriptsig:  OP_0 [non-vanitized-privkey-signature] {1 [non-vanitized-pubkey1] [nonce-key] 2 OP_CHECKMULTISIG}

Here [20-byte-hash-value] is equal to RIPEMD-160(SHA({1 [pubkey1] [nonce-key] 2 OP_CHECKMULTISIG}))


If a third party is generating vanity addresses, he can do on of two things to prove he doesn't have the private key associated with the nonce-pubkey:

1. The vanity-miner chooses the nonce to be higher than field p value.

He can use a nonce between FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F and 2^256.
So the X coordinate will be an invalid value of the field.
This nonces when interpreted as pubkeys will not be accepted by OpenSSL pubkey checker. Nevertheless they will be accepted as standard by Bitcoin client 0.8.3 and before. This is because IsCanonicalPubKey() does not check this.
Then the vanity-miner cannot create a valid private key of this invalid pubkey.
He will have 2^32 tries before the need to multiply the non-vanitized pubkey in order to be able to scan another 2^32 elements.

I really didn't like this idea, since maybe in the future the Core dev team may decide to add this check to  IsCanonicalPubKey()

2. The vanity-miner uses a 32-byte nonce that is a hash digest of a known sequence number.

Now the vanity-miner can prove that he didn't choose a specific nonce pubkey by showing the hash preimage. To find a private key a malicuius vanity-miner would need to break the pre-image resistance of the hash function or break ECDSA.

nonce-key = HASH(sequential-number)

After finding a nonce that hashes the script into a P2SH/M vanity address, the vanity-miner checks that the compressed nonce/point lies on the elliptic curve. If it does not, then keeps trying. If it does, then stops. The probability of not being in the elliptic curve is 1/2.

This method generates 100% standard valid and forever usable P2SH vanity addresses. We only need that clients evolve a little bit more to automatically handle paying/receiving from P2SH/multisig addresses.

Currently it can be done with the Satoshi client and the RPC interfase using validateaddress/addmultisigaddress/sendtoaddress/getrawtransaction/createrawtransaction/signrawtransaction.

Also the existence of the nonce does not degrade the performance of the Satoshi client when checking signatures, since the scriptsig signature will always match the first pubkey, so a check against the second nonce-pubkey won't be required.
The overhead in the transaction is of course very low, of about 35 bytes.

I think the current speedup using a GPU to mine P2SH/M is 20X if you're mining your own P2SH/M addresses or 10X if a third party mines them for you (maybe more, but this is an estimation).

This last idea is interesting since it can scan a 32-byte key space with only RIPEMD/SHA hash operations, so it can be performed efficiently in FPGA or ASIC, without the need for EC operations. So maybe we could mine vanity addresses with 2 more chosen prefix chars.

Best regards, Sergio.