I've discussed this enough on IRC that I thought I ought to put it someplace more lasting.

Bitcoin really ought to offer and default to using deterministic wallets.   The additional security of the current pre-generated ones is fairly small considering how most people use bitcoin and the liability of harm due to insufficient backups and increased pressure to keep a single wallet online is enormous.

What is a deterministic wallet?  It's a wallet which you can backup once and it stays backed up forever because all future addresses are determined in advance. It can also be stripped down to a very small size which could be easily backed up on paper (e.g. with a QR code). This is in contrast to the current non-determinstic wallets where the keys are random but are precomputed ahead so that you're safe only if you backup at least every 100 get addresses or sends, and which grow large and harder to backup on paper over time.

I've found the backup behavior of the current wallets fairly difficulty to get even moderately technical people to understand. The current system provides enough safety to encourage complacency but not enough to make complacency acceptable.  The positive side of a non-determistic wallet is that it becomes "unstolen" over time but people are frequently reusing addresses and attackers will not act slowly regardless.

There are two types of deterministic wallet I'd like to discuss. I'll call them type-1 and type-2.

Type-1 is the most obvious kind:

The wallet stores a large random seed  S (which can be encrypted if the user uses wallet encryption)

Privatekey(type,n) is then simply set to H(n|S|type)  where H is an acceptable secure hash function and type can be set to different values for change addresses vs displayed addresses (so this distinction is preserved even if new wallet metadata is lost).

The system would generate some (maybe 1000 of each type) addresses ahead of the furthest it has observed on the network but only bother to store the addresses. The keys can be regenerated as needed.



Type-2 is a bit less obvious and understanding it requires you to know about a property of ECC keys, roughly:

A_public_key = A_private_key*point

Which means you can do:

B_public_key = A_public_key+B_secret*point
and have a new key which has a private key:
B_private_key = A_private_key+B_secret

So a type2 wallet stores:
Master_private_key
A large Random_seed S.

and keys are given by

Privatekey(type,n) = Master_private_key + H(n|S|type)

which works just like a type-1, the advantage of the type-2 is that you can separately secure the Master_private_key, but still generate new addresses with
Publickey(type,n) = Master_public_key + H(n|S|type)*point

This means that a e-commerce site could have the front end webserver with access to the public key and S, and someone who hacked the server could violate the confidentiality of the addresses in use (because he could enumerate all past and future addresses based on an infrequently changed public key) but couldn't actually steal any of they money sent to the addresses because he would have no access to the private keys.

This could also be used to allow getaddress to work in the client without having to provide a key (access to the TXN data in the wallet means that access to the wallet, even with private key encryption, screws your confidentiality)  which would avoid the problem of backups being endangered due to address depletion from hitting getaddress a lot between entering in the key.