Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Bitcoin addresses are RIPEMD-160 hashes of the public portion of a public/private ECDSA keypair (along with an abbreviated hash of the hash to provide a check code, as @pulpspy notes in a comment). They are generally base-58-encoded. See Address - Bitcoin

In Vanity bitcoin addresses: a new way to keep your CPU busy, user "ByteCoin" says he can create and sell "vanity" bitcoin addresses (like 1ByteCoinsUNJun4KL3HSt1NfFdXpzoRTy) for people. Furthermore he says he can use a handshake algorithm to do so without actually getting access to the associated private key (and thus without being able to spend bitcoins which are sent to the address).

What is a fast algorithm for creating vanity bitcoin addresses? Can they in fact be created and sold in a secure way?

share|improve this question
    
The article first says that addresses are simply the output of a hash, but then later says that they include some error correction which means they are not merely the output of a hash? –  PulpSpy Jul 13 '11 at 20:23
1  
I see now that it is addr = (ver||RIPEMD-160(SHA-256(key)))||(SHA-256(SHA-256((ver||RIPEMD-160(SHA-256(key))‌​)))) where ver is version and key is the public key and the second component is only the first 4 bytes. –  PulpSpy Jul 13 '11 at 20:49
    
Thanks @pulpspy for completing that description. That makes it more expensive if you want to be able to find vanity in the check code part - 4 hashes for one address... –  nealmcb Jul 13 '11 at 21:11

1 Answer 1

up vote 16 down vote accepted

I don't believe that there's any way to generate the vanity hashes without iterating. In base 58, there's $\log_2(58) \approx 5.858$ bits per letter, so fixing 8 letters would need in average $58^8/2 = 2^{\log_2(58)·8}/2 \approx 2^{46}$ iterations. Note that Bitcoin addresses always start with a 1 by convention (this comes from the version field), and the next character in the base 58 representation is usually among "23456789ABCDEFGHJKLMNPQR" (not the full 58 character set), which halves the number of tries once more (if your wished starting character is in this set, otherwise it gets impossible). If you allow your vanity string to appear anywhere in the hash, you can divide this number again by 25, leading to $2^{40.5}$ iterations (on average) (which also are quite good parallelizable).

Also, the actual example he gave had an "s" rather than an "i" in the vanity "ByteCoins" part, so the odds of that are a bit greater (i.e. the needed time is even smaller).

However, you can do it securely (i.e. without the service gaining access to your private key):

Let the user generate a private key, $a$, and submit the corresponding public key, $a·B$ (where $B$ is the base point of the group). The service can then generate public keys as $a·B + x·B$, where $x$ is incremented to generate different public keys.

Actually, if you have $a·B +x·B$, then $a·B + (x+1)·B = (a·B + x·B)+B$, i.e. you need only one EC point addition (of the base point) and the necessary hashes for each try.

Then, by telling the user x, the user has private key $a+x$ with public key $(a+x)·B$ and $H((a+x)·B)$ has the required property, if the service did its job.

share|improve this answer
    
It would be possible to greatly improve the efficiency if you can find something in the preimage to tweak that does not require additional mathematical operations to be performed on it before hashing. However without an exact specification of the address generation, it is hard to say if there are any other fields or formatting that can be tweaked. –  PulpSpy Jul 13 '11 at 20:37
1  
I see now the link to the spec, although not a spec of the exact formatting of the ECDSA key. Addresses contain a "version" field. If this is not checked or used by the clients, you could iterate on it (maybe in addition to the share of the secret key since version is only a byte) with only the cost of the hash (instead of a point multiplication, addition, and hash) per iteration. –  PulpSpy Jul 13 '11 at 20:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.