There have been a lot of questions lately about additive vs. multiplicative, and how they work in oclvanitygen/oclvanityminer.  I'll try to answer them.

Oclvanityminer uses the additive method:

• Generate a random partial private key
• Calculate the associated partial public key
• Add the base public key to the partial public key to get the test public key
• Generate a large batch (~1M) of sequential addresses by successively adding the generator point to the test public key, and converting the points to addresses
• If a match is found, report the partial private key plus the number of times the test public key was incremented.  Otherwise, repeat the previous step

Sequential public keys in this scheme are generated by successively adding the generator point to the test public key.  In the multiplicative method, we would skip adding the base public key to the test key at the start, and use the base public key as the increment instead of the generator point.

If anyone really wants to use the multiplicative method instead, it's possible to modify oclvanityminer to do this by changing maybe 5-10 lines of code.  The performance difference would be negligible.

You are correct that oclvanityminer will search for addresses belonging to a single public key at a time.  I'm not sure how additive vs. multiplicative makes a difference in the ability to concurrently search for patterns using different base public keys.  For that matter, I'm not quite sure how to efficiently search for multiple patterns with different base public keys in the first place.

All these bounties have exposed a few bugs in oclvanityminer.  There were a handful of issues with the bounty list parser, and those have been fixed in git.  Another issue that also came up, the solve URL for vanity pool doesn't appear to accept POST requests.  It sends me back an error when I post something.  I changed oclvanityminer to use GET instead of POST for submitting solutions, and it seems to work.  I will post new binaries soon.

Edit: Pick up vanitygen 0.22

Ideas looking forward

It's possible to make vanity address mining much like regular bitcoin mining, in the sense of tracking the total work completed by each participant, and possibly distributing rewards to all participants rather than just the finder.  The idea would be, if somebody wants 1DanieLRH, post the bounty for 1Danie, and keep track of how many addresses each miner returns.  Eventually, a matching address will come back, and all of the partial matches will make it possible to determine the division of compute resources.

It also wouldn't hurt if the pool posted the portion of the bounty that will go to whoever solves it, rather than the amount paid by the customer.  It's a letdown to see a bounty for 0.1 BTC, and only receive 0.08 on completion.

It does rank bounties by reward/difficulty.  Choosing the 8 letter prefix is the best choice here, but not by much:


It will also group together bounties by public key.  When the 1Satoshi and 1satoshi bounties were both present, because they had the same public key, they would go into the same pattern set and would be searched for simultaneously.  Also, when dealing with bounties with the same public key, the aggregate reward/difficulty is used for decision making.  This would cause it to choose those two bounties together over the 1DaneiLRH bounty, if it were present.

Anyway, expect a new release in the next day or so that has an oclvanityminer64.exe.


You mean for the -a parameter?  It should accept a testnet address there.  Did it not accept one for you?  It is supposed to validate that what you enter for the -a parameter is a valid address of some sort, but it won't enforce a specific address type.


That's the right address.

Yes, please!  It should meet all the requirements.  One minor exception though, it looks like you specifically want 64-bit Windows binaries, but I only build the OpenCL pieces for 32-bit Windows.  This can be changed.


Indeed, determining a "difficulty" for a PCRE style regular expression is quite the can of worms.

It should be possible to design a subset of PCRE that can be converted directly into a bunch of prefixes, instead of having to execute the regular expression on each potentially matching address.  The idea would be to force the RE to start with a ^, disallow *, limit the length, and limit the resulting number of prefixes.  This would be a lot more expressive than a case-sensitive or case-insensitive prefix, and just as fast to search.  It would also solve the problem of executing REs on the GPU, as long as the RE isn't so complicated that it creates a search table that is too large to fit on the GPU.

One feature you may wish to consider adding to vanity pool, the ability to specify case-insensitivity in bounties.

Whoever posted the bounties for 1Satoshi and 1satoshi paid for two different addresses differing only in the case of the first letter.  It's entirely possible that that person simply wants that name on firstbits, and would rather pay for one case-insensitive address.  Also, at the reward offered for those bounties, finding a case-insensitive match would be very close to profitable, but finding either of the case-sensitive variants is not.

Or maybe not in this case, looks like 1satoshi is taken on firstbits.

The vanitygen suite now includes a program called oclvanityminer that is designed to work with this pool.  Please try it out!


I'm happy to throw what meager compute power I have at this.  However, the bounties for the above example would have to be about 10X what they are to be as lucrative as bitcoin mining at the current difficulty.

Interesting idea.  So, by ordering in bulk, you mean post multiple bounties with the same public key?  Then the mining client can run them all at the same time, and when deciding which bounties to go after, it should sum the cost-reward of all bounties with the same public key.

This thing enables a whole business model, and it's good for a bunch of reasons.  There won't be room for many sites like this, because the bounty will be held in a sort of escrow, and potential customers won't want to pay the bounty twice or three times.  So they'll pick the site with the most compute power.  The way it's shaping up, they'll also have to post a reward large enough to beat out the current top bounty on reward-to-difficulty in order to get their job prioritized.


I might have been too nitpicky about two URLs, that works fine, and it will do the job going forward.  However, how would you change it in a backward-compatible way to support something like a case-insensitivity flag?

If I had to design it from scratch though, maybe the bitcoin JSON-RPC model would be a good choice.


Yep that was me.  The payment did go through, and it shows up on block explorer.  My testnet client unfortunately didn't see it because the transaction is on testnet2 and my client is on testnet3.

The pool keeps 20%, or 1 tBTC?

Hi ThePiachu,

I really like what you've done with vanity pool!  This has a lot of potential.


You might want to overhaul this a little bit before it becomes more popular.  It ought to behave more like a standard web service, with one URL to do everything, rather than two.  And if you're going to use POST, the example code shouldn't put the parameters in a query string, it should use x-www-form-urlencoded.  But you already know all of this, and are just trying to look like an upstart, and I respect that.

Anyway, there is currently source code to a vanitygen derivative that implements a polling loop and other mining client features, and it is available on github.  Here's what it looks like:


Like other mining software, oclvanityminer must be given a URL to the bounty server, with the -u parameter.  This URL is a base URL to which the /getWork and /solve paths are appended.  It also requires an address to receive bounties, specified with the -a parameter, which is checked against typos and cut-and-paste errors.  The other parameters specify which OpenCL device to use, and are the same as oclvanitygen.

The miner follows the basic logic of mskwik's perl script -- it polls the server on regular intervals, and selects the best bounty based on difficulty and reward.  If the best bounty has changed since the last poll, it will reconfigure the OpenCL engine.  If no bounties are available, it will halt the OpenCL engine.

Indeed it found a match for "1Testo2" on vanitypooltest.appspot.com, which took a few hours on a cluster of AMD 5830s.  Unfortunately, while the address to receive the bounty passed validation, it wasn't valid in this case -- the bounty is in testnet coins, and the address is a regular net address.  The pool server replied with an error about the address not appearing to be valid, which is good, but it's unclear what the pool server did with the bounty.

The address miner has a few wrinkles left to be worked out and isn't formally released yet.  For anyone who wants to try it out, there is a win32 binary of the miner program posted here.

Are you referering to the nSequence field of transaction inputs?

I thought that was locked out.

This sounds very interesting.  I can see simple use cases like using one EC key both as a bitcoin account and for signing PGP messages.  Possibly using a bitcoin-disclosed public key to encrypt messages, if this is safe.  How else would integration be possible?

Another factor, GnuPG has yet to produce a stable release with support for EC keys.

Somebody who knows the source better than I can correct, but it looks like the output for "change" is inserted at a random position in the transaction.  See CWallet::CreateTransaction(), wallet.c:969.  So, there shouldn't be any deterministic clues.

Very cool, the web interface auto-fill works beautifully.

I tried running it with Python 2.4.  It kinda works.  The biggest issue I ran into, the json module does not appear to exist in Python 2.4.  According to the docs on python.org, json would appear to have been introduced in 2.6.

The primary goal of this format is to create something like PKCS#8/RFC5958.  PKCS#8 is the format commonly used to store SSL/TLS private keys, in password-protected form or otherwise.  It is a very flexible format with metadata describing of the type of private key, and the PBKDF parameters and block cipher used to encrypt it.

It's possible to convert an exported bitcoin private key in the base-58 format to and from PKCS#8.  In PKCS#8, the built-in password-protection feature can be applied to the private key.  Also, if a bitcoin key were to be imported into some other non-bitcoin application for whatever reason, perhaps as a signing key, PKCS#8 would be the best bet as an import format.

It's also possible to take a PKCS#8 representation and produce a reduced mapping that assumes certain parameters.  If we assume the use of the SECG 256k1 EC curve, a set of of PBKDF2 parameters, and the use of AES with a specific key size, the representation can be smaller.  Unfortunately, due to RFC5915, there is a practical lower limit on the size of any reduced format.  For bitcoin private keys, this is close to 135 bytes, and it includes numerous details that, for our purposes, aren't necessary or can be assumed.  This is unwieldy large.

The next step of evolution from PKCS#8 might work as follows.

privkey = Minimal EC private key representation, 32 bytes long
param = Parameter descriptor byte.  This is an index into a predefined list of parameter groups, perhaps like:

• 0: SECG 256k1 key, PBKDF2, HMAC-SHA256, 8-byte salt, 4096 iterations, AES-256-CBC
• 1: SECG 256k1 key, PBKDF2, HMAC-SHA256, 8-byte salt, 4096 iterations, Camellia-256-CBC
• 2: SECG 256k1 key, PBKDF2, HMAC-SHA256, 8-byte salt, 16384 iterations, AES-256-CBC
• etc..

pbhash = Hash function from parameter list
cipher = Block cipher function from parameter list
salt = Random salt value of size described in parameter list
iter = PBKDF iteration count described in parameter list
pbkey = PBKDF2(password, salt, pbhash, iter)
protkey = param | cipher(privkey, pbkey) | salt

This would handle the cryptography in the most conservative, commonly-used way, and should not make anyone nervous, or at least, not any more nervous than PKCS#8.  It would also make the format easily adaptable to new block ciphers and key derivation functions.  The smallest representation using AES would be 58 bytes long, and would convert to an 83-character base-58 string.  This is much more compact than a PKCS#8 interoperable format, but I still think it's too long.

Swapping around means storing a private key outside of a wallet.dat, either to be imported into another wallet.dat or another bitcoin client implementation.  It's an interchange format, not a specific wallet implementation.

The format proposed here is an extension that allows an exported private key to be password-protected.  Naturally, if it is to be interchangeable with another bitcoin wallet or another implementation, it shouldn't/can't be protected using the same password or master key as the wallet from which it came (if that wallet is encrypted).  The initial use case is to allow someone to use vanitygen to generate an address, and securely store the private key until it is later imported into a client.

Anyway, I think this proposal is orthogonal to the encryption of wallet.dat.

If you would rather this format follow the same password-derivation and encryption scheme as the master keys of the bitcoin wallet encryption system, that's certainly possible.  They're already quite similar, and until pixelglow came out and recommended PBKDF2, they both used EVP_BytesToKey().  I don't think the use cases between the wallet master key and a password-protected export format are quite the same though.

Absolutely!  The goal is to handle the keying independently and not depend on the master key of a specific encrypted wallet.  So, if it were used for exporting, it wouldn't be as convenient as "backupwallet," and at least one export password would be required.  But it could be implemented to be more convenient than dumpwallet + GPG.


Thanks!  I posted a note to the list and referenced that thread.

Excellent!!

Pixelglow, you really seem to know your stuff, are you a pro??

The PBKDF that I've been using isn't exactly PKCS#5 v1, it's actually OpenSSL's EVP_BytesToKey().  It's similar but will produce arbitrarily large key material.  Otherwise, there certainly wouldn't be enough key material for an AES IV using SHA256.

Regardless, using PBKDF2 with an HMAC function would seem to be a very desirable change, and also appears to be very easy to get with OpenSSL.

Regarding pwcheck, the use of an HMAC function there with some additional key material also seems like the appropriate tool for the job, more so than my hacked-together mess.  Can't really say no to that either.

Would you recommend HMAC-SHA1 over HMAC-SHA256?

Somebody smart said that a work is finished not when everything that can be added to it has been added, but when everything that can be removed has been removed.  AES may fit into this category.  However, other similar password-protection schemes, including bitcoin's built-in wallet encryption, also use AES for fixed-size private keys, and it's nerve-racking to replace it with XOR, even though it may be the correct thing to do.

Thank you very much!!

You make some very good points about this.

In terms of the purpose of the salt, what would be the usage model for any sort of precomputed table for this problem?  It seems like it would be limited to creating a list of AES keys derived from possible passwords, each of which would have to be tested, still requiring exponential time in the length of the password, but allowing the attacker to circumvent running the expensive PBKDF function for each test.  Is there something sneaker and more devious that an attacker could do with this particular problem?  I don't think this is like trying to build a table for a hash function, where the outputs depend on only the password and the salt, in which case the attacker can index the outputs to the inputs and build a true lookup table or a rainbow table.

Anyway, if that's true, then at 48 bytes per AES key + IV, and 2^32 salt variations of each, the attacker would need to be able to store 192GB per precomputed password.  At least, without some clever way of compressing the keys.  That is a lot easier than 2^64 variants of each, but still seems intractable.

The tradeoff to having four extra bytes of hash would be six extra characters in the encoded output.  Example side-by-side is below:

PAYxy8B9zhSGpbyC7Z29KRS7rsPzAcTF3zSPmyAigbAJYamt9GmNwsFT9E95dGfp6Ri
3W3qzi2Sow4o7LP7jwwnrmqiiGxyMcwLdubKxYhNy4J63eigN3jz7avYqSWfGwxz3nMDDXwwc

Edit: It's possible, using a smaller value for the type byte, to reduce it to five extra characters.

Your point about weakness mitigation is well taken though, and the tradeoff may be worth it.


The PBKDF function here requires 8192 rounds of the SHA256 hash function, so it should already be a lot more expensive than computing the bitcoin address and looking it up in a list.  Even if the attacker was using a table, having to do an EC operation as often as every 2^8 keys probably won't cause a big slowdown.  But, it will make the password cracker a bit more complicated.

For the one person who gets a letter of their password wrong, and is unlucky enough to have it silently accepted and mapped to the wrong account, and either the bitcoin address isn't known or isn't compared to the expected value, they better hope the password-protected version of their key wasn't discarded.

This is a very good point.  Segmentation like this is something that regular bitcoin addresses could benefit from as well -- typing in 34 characters is difficult enough.

So, the password-protected key above could look something like:

PAYxy8-B9zhSG-pbyC7Z-29KRS7-rsPzAc-TF3zSP-myAigb-AJYamt-9GmNws-FT9E95-dGfp6Ri

And the address:

1Hackn-YhLRpt-tqGAiB-ew1fQA-KRGnMo-rkxk

The breaks sure make it easy to remember where you left off, and they're a heck of a lot easier to transcribe to and from paper, or between screens!  But, the password-protected key now only barely fits into an 80-column terminal, and with anything prefixed at the beginning of the line, it will overflow.   

Maybe this idea deserves its own thread.