[RFD] Bitcoin Deterministic wallet

[da2ce7]

The use of bitcoin requires that either users store their private data in a ‘wallet file’ in clear text or encrypted, this wallet file still needs protection.

However, there is only one sort of information within the wallet file that is important… the private keys.

Currently the private keys are generated from random data.  However, there is nothing stopping us creating these same keys deterministically.

This is what I propose:


Bitcoin should have the option to ‘load a deterministic wallet.’

Creating the Deterministic Wallet:

1.  User enters a new password (of good quality) into the ‘load/create a deterministic wallet’ dialogue:

Code:

A = sha256 ( password )

B(x) = sha256 ( x )

C(x) = sha256 ( A + B(x) )

Find x, where C(x) < 0x00000000FFFF0000000000000000000000000000000000000000000000000000

(x starts from 0, and increases)

 
2.  Bitcoin then supplies the user with a nonce, base58(x), that the user can supply to both:

   a.  save time in finding the nonce again

   b.  check if the password – nonce combo is correct

3.  Bitcoin then generates 1000 (or more at the users option) addresses:

Code:

D = C(x) , where x = nonce

Key1 made from sha256(D)

Key2 made from sha256(sha256(D))

…

4.  The bitcoin client then rescans the block chain for any transactions based upon the newly generated keys.

5.  Upon close, the bitcoin client forgets everything, including the password. (optionally we have a setting for the software to store the nonce for convenience)
 

This system means that if the user keeps the password secret (and, optionally, nonce to save time/check correct entry).  The there is NO RECORD or DIGITAL DATA that needs to be kept on any computer (other than the block chain).

This is far more secure than the current system… It is also resistant to brute-force attack, as there is a fair effort required to check through various password.

Edit:  The Goal of this system is so that anyone can use their wallet on any computer   no need to backup anything.

[da2ce7]

Please note!  This is not to 'replace' traditional wallets... but to complement them as an option.

[da2ce7]

Possible better password strengthening function than sha256

http://www.tarsnap.com/scrypt/scrypt.pdf

http://www.tarsnap.com/scrypt/scrypt-1.1.6.tgz

Thanks gmaxwell!

[publickeyhash]

Find x, where C(x) < 0x00000000FFFF0000000000000000000000000000000000000000000000000000

This requires to bruteforce 4 bytes = 32 bits ?

[Garrett Burgwardt]

Seems to me this would just allow attackers to guess people's passwords and thus be able to steal wallets rather easily.

[joan]

I'm not sure I understood the idea correctly, if two users happen to use the same password, won't it generate the same private keys ?
Not only you'd need a strong password, but also a unique one.

[da2ce7]

Find x, where C(x) < 0x00000000FFFF0000000000000000000000000000000000000000000000000000

This requires to bruteforce 4 bytes = 32 bits ?

I believe that it is the same difficulty as a standard difficulty of 1

Seems to me this would just allow attackers to guess people's passwords and thus be able to steal wallets rather easily.

Yes... but the point is that people use strong passwords (weak passwords are weak).  It is also very expensive to check passwords if the as the password strengthening function takes a bit of time to compute.

[da2ce7]

I'm not sure I understood the idea correctly, if two users happen to use the same password, won't it generate the same private keys ?

That is the point... you use a random-strong password... I guess you cannot have your cake and eat it.

I mean, if you want a system that works no-matter what computer you decide to use the password on... swapping computers will be nothing more than using your password on a different computer.

[publickeyhash]

Seems to me this would just allow attackers to guess people's passwords and thus be able to steal wallets rather easily.

I completely agree if the nonce was deterministic (not exactly a nonce at all!)

Find x, where C(x) < 0x00000000FFFF0000000000000000000000000000000000000000000000000000

(x starts from 0, and increases)

Thus x is a direct function of password. Thus as Garrett pointed out, guess a password and the algorithm will create the account, moreover: lots of average users would accidentally end up sharing the same password/account.

The idea seems fine if x was a random secret number.

[Garrett Burgwardt]

I'm not sure I understood the idea correctly, if two users happen to use the same password, won't it generate the same private keys ?

That is the point... you use a random-strong password... I guess you cannot have your cake and eat it.

I mean, if you want a system that works no-matter what computer you decide to use the password on... swapping computers will be nothing more than using your password on a different computer.

The only way I see this working is if you use a 20+ characters password with tons of different symbols, etc.

Even then, I'd not use it.

[publickeyhash]

Quote from: joan on Today at 03:39:08 pm
I'm not sure I understood the idea correctly, if two users happen to use the same password, won't it generate the same private keys ?


That is the point... you use a random-strong password... I guess you cannot have your cake and eat it.

I mean, if you want a system that works no-matter what computer you decide to use the password on... swapping computers will be nothing more than using your password on a different computer.

so you see this as a feature of the system? forcing people to use strong passwords on pain of losing/sharing money? its an interesting concept
I have never heard of a strong correlation between mutual interests and mutual passwords.... but I can imagine people using concepts of interest as their password (sex/...)

but then why bother with x at all? deriving the private keys from password alone would be just as well...

[da2ce7]

The idea seems fine if x was a random secret number.

If x was a random secret number, there is something that MUST be remembered, why not just add the random number to your own password... the point of the nounce is to:

1.  save time (this means that we can use a much stronger password strengthening function, if we are not doing it every time, this makes searching through passwords much slower for an attacker... but not slow for a regular user that remembers their nonce)

2.  check if the user didn't mistype the password.


We SHOULD provide a option where the user put a 'account name' and 'some random number'  that is mixed into the password. A in a standard way... however these options should be optional.

It is the user's fault if they use an insecure password... like anything we should do the best we can to warn the user that they are being stupid... (eg a weak password)... but shouldn't stop them being stupid.

[joan]

I really like the idea of being able to store the private key (or something to rebuild it) in my head though.
My concern is about the increased risk of collision in the much reduced keyspace.

[da2ce7]

The only way I see this working is if you use a 20+ characters password with tons of different symbols, etc.

Even then, I'd not use it.

There is nothing stopping the user from writing down a password.

I'd personalty recommend passwords like:

"da2ce7 is super sexy and a mad dog, I like to eat!!! cows are cool!!"

something like that nobody else would make... and and since brute-forcing is so hard... it is infeasible to make through a search.

[publickeyhash]

assuming that you want to allow colliding accounts/passwords if the user is dumb enough to to use "sex" as his password...

why do you need x at all?

I think x is simply a kind of salt (which does need to be remembered, by you (really not a salt but second half of the password) or the computer (fixed location computer salt))

your prescription for finding x is deterministic as a function of password. In effect, you are just applying a croocked form of SHA256.
Occams razor, if it does not add security leave it behind, and simply use SHA256(password) if you really want the same passwords to generate the same accounts...

[speeder]

Why not use a... user and password?


Instead of using password and nonce, with user and password, you can calculate the wallet from it.

It is somewhat insecure if someone guess your stuff? Well... yes. But it is very convenience, nice and would solve some bitcoin problems (like, how you spend bitcoins easily while away from your computer and not trusting in a company to do that for you).


The only problem that I cannot think around right now, is collision.

[Anonymous]

Why not plugin to keepass to let you generate a large secure password for your wallet ?

http://keepass.info/help/v1_dev/plg_keyprov.html

[TierNolan]

I wonder if this would work well when combined with a majority secured wallet.dat

A shared secret allows you to split a secret into n pieces and it can be recovered as long as you have k of the n pieces.  k and n can be set to anything desired.

For example, if you split the secret into 5 pieces and set k to 3, then you could only recover the secret with 3 of the 5 files.

Each of the shares is the same size as the original file.

This would allow a user to split their wallet "seed" over 5 locations.  As long as at least 3 of them remain secure, then the wallet is secure and recoverable.

The problem is that every time you make a transaction with the default client, it writes to the wallet.dat file.  This means you have to collect all 5 pieces together, spend the money and then redistribute the 5 new pieces.  This is a massive hassle.

If this process is not performed correctly every time, it could cause the wallet.dat file to be unrecoverable.

With a deterministic wallet, you could make the password a few thousand bytes long if you wanted and protect it using the secret sharing method.

Alternatively, you could make the password a hard to guess/remember password and then distribute the shares to the 5 locations.  If you ever forget your password, you can recover it with 3 of the 5 shares.

This wouldn't even necessarily require that the default client is updated.  A utility could work entirely by updating the wallet.dat file.

It would require a utility that can generate a wallet.dat file with a few hundred unused keys from the deterministic program.  I assume that if there are free keys, the standard client uses them?

The method would be only a little hassle for the user.

Utility

read list of public keys in use for this wallet (stored in plain-text*).
run the deterministic wallet generator and generate a wallet containing the keys matching the public keys and also 100 additional keys.**

Default client

Start the default client
send your money (change will be sent to one of the 100 generated keys**)
Only perform a few transactions***
Close the client

Utility
Have the utility scan the wallet.dat file and write any used public keys back to the public keys file.*****

This could be scripted

utility -gen-wallet.dat -f pub_key_file_list -n 5 -s1 share1.dat -s3 share3.dat -s4 share4.dat -o /path/to/wallet.dat
bitcoin
utility -extract-keys -f /path/to/wallet.dat -o pub_key_file

The actual wallet.dat could be a link to a random disk, so it would clear when you remove power.

ln -s /path/to/ramdisk/wallet.dat ~/bitcoin/wallet.dat

I think this will cause overwrites to be redirected to the link target right?

*: This can also be determined from the block chain
**: This wallet should be written to a RAM drive
***: This is correct right?  The wallet won't generate a key if there are spare ones available in the wallet
****: It is critical that the spare keys are not exhausted
*****: Even if this is messed up, you can still get the keys back due to *

The main thing that could go wrong is if the client generated new keys.

[da2ce7]

Should check out what Stefan is developing for bitcoinjs.  Using a bitcoin master key.

[bitplane]

I like this idea and agree with da2ce7. I would prefer an email address and strong password to generate the key as this would further reduce the potential for collisions.

It would be really nice to have a client-side script (either browser plugin or self-hosted javascript) that can query a web service to get your balance from an email/password combo