Privacy versus Safety: handling change

Here's how you can lose coins by backing up and restoring your wallet file:

Lets say you have one shiny 1,000 Bitcoin coin in your wallet (it's actually just a transaction for 1,000 bitcoins paid to a public key that's stored in your wallet).

You backup that file.

Now you spend 1 Bitcoin.  Your shiny 1,000 BTC coin is broken into 1BTC, plus 999BTC in change.  That change is given a new, different public key.

Now if you restore your wallet file, Bitcoin sees that the 1,000BTC coin has been spent-- 1BTC was sent somewhere, and the other 999BTC was sent somewhere else.  Because you don't have the key for the 999BTC, it has no idea that those coins belong to you.

So they're lost.

Trying out alternative policies for handling change on the TEST network would be a good idea, in my opinion.

Maybe change transactions should always get signed with the same public key, so you wouldn't lose coins when restoring your wallet... although that would give you less privacy because it would tend to tie all your transactions together.

Maybe your wallet should get initially populated with 100 "change" addresses, with one randomly chosen as needed.  And some super-geeky way of replacing them with another, new, 100 addresses.

Maybe there's an even better way of handling the "I lost BTC when I restored my wallet" problem; ideas?

We should queue up a supply of pre-made addresses in the wallet to use when a new address is needed.  They aren't very big, so it wouldn't hurt to have a lot of them.  This would more generally cover the case also where someone backs up, then requests a new address and receives a big payment with it.  Maybe there should be separate queues so one type of demand on addresses doesn't deplete it for the others.

The addresses would be created and stored in the normal place, but also listed on a separate list of created-but-never-used addresses.  When an address is requested, the address at the front of the never-used queue is handed out, and a new address is created and added to the back.

There's some kind of rescan in the block loading code that was made to repair the case where someone copied their wallet.dat.  I would need to check that the rescan handles the case of rediscovering received payments in blocks that were already received, but are forgotten because the wallet was restored.