related idea, not for brain-wallets but for password encrypted random key wallets. [...]
type your password [... decrypt your private key, make a signature and...] 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.
[...] 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. [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
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.
Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.
Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ), S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).
User deletes y, Q and A and k-bits of salt.
User publishes extended address E and receives funds on it.
When user wants to spend funds (or an attacker who has the users hard drive), he types his password and computes K'=Scrypt(password), and computes a candidate private key x'=AES-Dec(K',X). The candidate (non-extended) public key is Q'=x'*G. The user cant tell if this is the right password (right private key x' nor right public key Q') the work to brute force k-bits of salt is much more CPU power than he has.
User publishes (R, S, ECDSA(x',tx)); anyone can compute Q' from the signature, and see that the signature is valid, but it takes work to discover if R is derivable from Q'. Thats the work the miner does as follows: the miner tries to find salt in the defined (advertised) search space such that either H2(H(salt'),Q') == R (because the password is correct) or if the password is wrong the miner finds salt'*Q' == R mod 2^k (ie last k bits match). If the password is right the miner does not publish salt, only publishes H(salt') and signs with salt as private key to R in order to claim the full reward (40c+20c). If the password is wrong (miner did not find full match within search space) miner signs with salt' but as H2(H(salt'),Q') != R he can only claim 20c.
Unlike before it is not possible for other miners to take the solution and assign the fee to themselves so the KDF miner does not need to be a bitcoin miner (to include his own fee collection into a block), nor does he have to use committed transactions for security.
Adam