10X Faster Vanity addresses (P2SH/M)

[Sergio_Demian_Lerner]

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.

[Sergio_Demian_Lerner]

Note that with Luke-Jr patch https://github.com/samr7/vanitygen/pull/10 of the vanitygen miner, a few lines of extra code and a few changes, and you can implement the P2SH/M miner in 5 minutes.

[jl2012]

For option 2 do you mean the nonce would be something like HASH(1), HASH(2), HASH(3)........?

So why not simply use 1, 2, 3...... as the pubkey?

[TierNolan]

The main point is to shift it from ECC to hashing right?

Adding a nonce switches key generation from EC multiplication to hashing.

I wonder if in the future "1SomeWebsite" addresses would be seen as better than "MSomeWebsite", if only because they are more expensive to produce.

[gmaxwell]

Sure, thats how luke generated that 3P14159 address... but kinda lame in that it makes your spending transactions bigger (= higher costs and extra crap added to the blockchain).

I wonder if in the future "1SomeWebsite" addresses would be seen as better than "MSomeWebsite", if only because they are more expensive to produce.

Both are kinda awful: the kind of person who might care about your distinction would recognize that either form tells the whole world the party to go after to learn more about those funds, and would presumably prefer to deal with someone not screwing up everyone's privacy.

[Sergio_Demian_Lerner]

For option 2 do you mean the nonce would be something like HASH(1), HASH(2), HASH(3)........?

So why not simply use 1, 2, 3...... as the pubkey?

Because a third party mining vanity addresses for you would need to prove to you that he didn't choose the pubkey using ECC (and knows the private key).
If you have a hash pre-image, that's a proof.
Also a simple sequence like 1,2,3 may end up in a weak case of a pubkey (I'm unsure if ECDSA has weak keys).

If you mine for yourself, then you can count simply as you said, but it would be better to choose the sequence starting from a random 32-byte value.

[Sergio_Demian_Lerner]

Sure, thats how luke generated that 3P14159 address... but kinda lame in that it makes your spending transactions bigger (= higher costs and extra crap added to the blockchain).

At the end it's a financial decision: if you want to use a long vanity address either you pay 20 times more in advance, or you pay a little more each time you receive a transaction.

[jl2012]

For option 2 do you mean the nonce would be something like HASH(1), HASH(2), HASH(3)........?

So why not simply use 1, 2, 3...... as the pubkey?

Because a third party mining vanity addresses for you would need to prove to you that he didn't choose the pubkey using ECC (and knows the private key).
If you have a hash pre-image, that's a proof.
Also a simple sequence like 1,2,3 may end up in a weak case of a pubkey (I'm unsure if ECDSA has weak keys).

If you mine for yourself, then you can count simply as you said, but it would be better to choose the sequence starting from a random 32-byte value.

So the customer can simply generate a big random number X, and request the miner to scan from X to X + 2^32. I can't see why this is weaker than hash of something

[n4ru]

Note that with Luke-Jr patch https://github.com/samr7/vanitygen/pull/10 of the vanitygen miner, a few lines of extra code and a few changes, and you can implement the P2SH/M miner in 5 minutes.

Care to share the full source/patch? I'm not good enough to be able to implement it myself.

[dudeami]

Just use the branch the pull request references:

https://github.com/luke-jr/vanitygen/tree/e2a0e0ba138464ce96b733f8990b75b60f05a367

Edit: That is if the patches are already there. If they are not, no dice :p

[Sergio_Demian_Lerner]

Note that with Luke-Jr patch https://github.com/samr7/vanitygen/pull/10 of the vanitygen miner, a few lines of extra code and a few changes, and you can implement the P2SH/M miner in 5 minutes.

Care to share the full source/patch? I'm not good enough to be able to implement it myself.

I didn't implemented it. I'm too busy.
But Luke-Jr implemented something that is very very close. You can modify it easily: maybe 5 lines of code is enough.

[jl2012]

For option 2 do you mean the nonce would be something like HASH(1), HASH(2), HASH(3)........?

So why not simply use 1, 2, 3...... as the pubkey?

Because a third party mining vanity addresses for you would need to prove to you that he didn't choose the pubkey using ECC (and knows the private key).
If you have a hash pre-image, that's a proof.
Also a simple sequence like 1,2,3 may end up in a weak case of a pubkey (I'm unsure if ECDSA has weak keys).

If you mine for yourself, then you can count simply as you said, but it would be better to choose the sequence starting from a random 32-byte value.

Just realize this could be done in a completely trust-free way. The customer will provide 2 public keys, and request the miner to produce a 2-of-3 multisig address. The drawback is a bigger scriptSig is needed