Quote from: adam3us on October 15, 2013, 01:48:20 PM

Quote from: adam3us on October 15, 2013, 01:00:38 PM

a limitation with key stretching is it incurs computational load on the client, which maybe a smart-phone or single desktop class machine. eg 16384 scrypt iterations are suggested in BIP 038, chosen to be fast enough to tolerate in javascript.

So it would be desirable to have a secure server offloadable KDF, which means a kind of blindable deterministic proof-of-work.

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02948.html

Quote from: adam3us topic=bitcoin-dev

Rivest et al in their time-lock puzzle paper is that it is easy to create work without doing the work during setup [...] avoid the javascript overhead issue that forces users to choose a weak iteration level.

eg create a 32-bit random salt, replace scrypt(i=16384, salt, pass) with scrypt(i=1,salt, pass) to be brute forced based on deleted salt. Immediate 2^32 = 4billion iteration salt without any significant setup cost.

Here's another related idea, not for brain-wallets but for password encrypted random key wallets. So above I described the symmetric time-lock approach (by deleting some of the salt to instantly create a brute force target).

As a requirement what you would actually like is to be able to type your password, stretch it a little bit (to be not too slow on your not-that-fast single CPU system which could be an offline netbook wallet), send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.

You would have to pay the miner something for this work eg 60c for 2^46 SHA256 iterations at whatever the bitcoin mining difficulty/reward cost is. (Its perhaps better with GPU friendly Scrypt to not compete for bitcoin security as GPU capacity is mostly unrelated to bitcoin (ASIC) capacity.)

At first I was thinking this would be very hard to arrange, but if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner. Until the salt is found the signature is of unkown validity because it is unclear whether or not it matches the public key or is a random forgery. Once salt is known the signature is cheaply validatable by anyone.

The user tries to type their password (or an attacker with a copy of their disk tries to grind their password). So they convert the password into a key and decrypt the encrypted wallet private key. However we remove any checksums so all private keys are equally plausible. The only way to verify the private key is to compute the public key and see if it is correct, however now this is an expensive operation to offload to an untrusted fast machine, or miners generally for a fee.

If the user guesses their password wrongly the miner will still collect a smaller fee (20c) for presenting a 45-bit collision with the address, whereas the full fee (40c) is available for a full match with the address. (This is necessary because there may exist 45-bit collisions on the real address and the others cant tell without redoing the full 46-bit address search). Note the work is at most 2^46 for the full match because it is a known solution, but could take longer for the 45-bit collision if there is no full match because the password is wrong.

The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen. Collecting the KDF fee is a bit insecure otherwise.

https://bitcointalk.org/index.php?topic=206303.15

In this way you get a stronger KDF than you have hardware for by paying a small KDF fee, with the benefit your password encrypted wallet becomes very expensive to grind. (Bearing in mind that if someone has your hard drive, all keys are "brain-wallets").

Or you could offload the KDF work from an offline wallet (which maybe a cheap slow old netbook) to a beefy less well secured network connected GPU desktop.

Bitcoin script doesnt have scrypt as a primitive (could be a useful function to add), so the proof has to involve hashes.

You could probably do all of this with existing P2SH without any new features (except for the committed transaction).

Not completely elegant but somewhat interesting and maybe leads to some other ideas.

(To pay the KDF fees the user needs an unprotected or simple (different) password protected wallet with a smaller balance).

Does not seem to be compatible with deterministic wallets at least as stated above.

Adam