Deterministic wallets

[gmaxwell]

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.

[1714120135]

1714120135

[gim]

The purpose is clear and definitely appealing.

Type-2 might indeed be a good implementation, but I don't think I understand Type-1.
You would use H(n|S|type) to seed a keypair generation? Isn't the data too small for that purpose?
Or H would not be the usual kind of hash function, maybe a symmetric cypher?

[gmaxwell]

The purpose is clear and definitely appealing.

Type-2 might indeed be a good implementation, but I don't think I understand Type-1.
You would use H(n|S|type) to seed a keypair generation? Isn't the data too small for that purpose?
Or H would not be the usual kind of hash function, maybe a symmetric cypher?

ECC != RSA. You only need as much data is in a private key to create one.

[willphase]

I like this idea.

Will

[ShadowOfHarbringer]

Definately worth of inclusion.
+1

[Basiley]

"in general" session-based components/"smoking crypto" in crypto-systems are nice to strengthen them w/o overhead increase and used by military from WWII era.
so, IMO, its[impact] worth code grow.

[westkybitcoins]

I like this idea. A lot. I'm not a cryptologist but I can't think of any downside to this other than one possible (if unlikely) one: what if generating 1000 addresses past the last one seen in the chain isn't enough? After all, a user can generate then discard an arbitrary number of addresses for use, but the code as described would only look for the first 1000 addresses past the last one seen (I assume it would initially look for any of the first 1000 addresses.) But then even this could be handled by a "look for more of my addresses" button that looks for the next 1000 addresses.

Lack of backwards-compatibilty of the new wallets might be an issue, but surely not a significant one (especially if the clients using deterministic wallets would still be able to read and continue growing older wallets.)

So, yeah, no obvious downside that I can see. Who do I pay to get this into a client?

[je_bailey]

Just a small question. Wouldn't this make it easier for an unauthorized individual to make a copy of the wallet and then use it at an arbitrary date in the future to access and steal any coins in it?

[gmaxwell]

Just a small question. Wouldn't this make it easier for an unauthorized individual to make a copy of the wallet and then use it at an arbitrary date in the future to access and steal any coins in it?

Yep. That is the compromise.  The current wallets unsteal themselves.

My arguments:
(0) In spite of recent concerns, I think that loss is a greater risk for most users than theft.
(1) People frequently reuse addresses today, this eliminates the unstealing advantage.
[And, in fact, someone on IRC was just asking about changing the client to send change back to the original address in order to make backups more effective]
(2) Encryption makes theft less likely than it has been
(3) Thieves know about the unstealing property and will already act fast enough if coin is available.  If you're about to receive a lot of new coin you could start a new deterministic wallet. Also after compromising your machine once the thieves will likely leave backdoors in any-case.

If the interface allowed you to have multiple deterministic wallets at once (or just multiple key-heads in a single wallet) you could periodically trigger the creation of a new one in order to get the forward privacy, and you could do this in time with your backup schedule so you're not left surprised by a backup that failed to grab all your addresses.

[wumpus]

+1

sounds like a good idea, it should be an option (truly paranoid people will probably disable it) but I have no problem with it being on by default

[netrin]

+1

I think this is a great idea. Indeed I've suggested it myself several times, here and in the github threads. I like the idea of having minimal sized keys (none of the transaction history) in the wallet. Further, the wallet should 'optionally' cycle through the pre-generated keys. A user should be able to have a wallet with a single key. In fact, I would prefer a wallet as simply a directory (or plain text file) containing individual keys.

In my own use case, I create new wallets often. Deterministic wallets would simplify my backup use cases and make me a lot less paranoid. As it is, I feel the wallet is far too much of a black box. Predictability will go a long way to help bitcoins gain traction.

[Enzo]

The idea of a master key is very good.
It is already used by programs such passwordmaker (open source) which i use with great satisfaction.
Anyway i think that periodically is necessary to create a new set of keys, that is a new wallet to which transfer all the funds, discarding the old wallet: we can never be sure if a certain wallet is compromised or not.
This operation, in my opinion should be executed before every backup and in case we use a master key we should generate a new one.

[Luke-Jr]

Is it possible to make the pubkeys separately deterministic from the private keys, and have multiple chains of them? My thought is that this would be nice to allow receive-only bitcoinds for services-- they can call getnewaddress to get a unique destination address, and listtransactions can still show what they received, but they don't have the private keys to send the funds. The other servers could have the "root keys" needed to track all the other servers' transactions, so listtransations on any server would show the data for all the servers. Finally, only the super-secure wallet would have the data needed to generate the private keys and actually spend the funds.

I presume multiple chains is merely a simple matter of implementation, but I'm not sure whether deterministic pubkeys matching privkeys is possible?

[just_someguy]

Is it possible to make the pubkeys separately deterministic from the private keys, and have multiple chains of them? My thought is that this would be nice to allow receive-only bitcoinds for services-- they can call getnewaddress to get a unique destination address, and listtransactions can still show what they received, but they don't have the private keys to send the funds.

This would be cool. I'm assuming given two known public keys for an individual the relationship cannot be reverse engineered?
If so that would not be a good thing.

[storr]

Am I right that if use seed encryption, then the same  large random seed  S can be used by backup many wallets simultaneosly? One wallet for each password.

[w1R903]

Not a cryptographer, but I like this idea.  In fact, this is how I had assumed Bitcoin was implemented before I read the technical information.  A lot of important web services will need this feature to function effectively and securely.

[netrin]

One of the advantages of the deterministic wallet is that they can be backed up offline and any copy is as good as any other no matter how old. One of the reasons we want to do this is to protect our bitcoins for posterity, or at least so we can sleep well at night.

So it seems just as important to me to be able to secure a wallet 100% offline. I should be able to send a transaction without ever exposing my wallet to the network. It should be possible to create a 'send file'. In other words, I should be able to use my offline deterministic wallet to sign a transaction, then separately (and perhaps physically) take the transaction to another machine that is on the network and execute the transaction without the wallet.

[ben-abuya]

One of the advantages of the deterministic wallet is that they can be backed up offline and any copy is as good as any other no matter how old. One of the reasons we want to do this is to protect our bitcoins for posterity, or at least so we can sleep well at night.

So it seems just as important to me to be able to secure a wallet 100% offline. I should be able to send a transaction without ever exposing my wallet to the network. It should be possible to create a 'send file'. In other words, I should be able to use my offline deterministic wallet to sign a transaction, then separately (and perhaps physically) take the transaction to another machine that is on the network and execute the transaction without the wallet.

We discussed that here: http://forum.bitcoin.org/index.php?topic=19080.msg263715#msg263715

[asdf]

Excuse me if I'm being a noob, but as I understand this system, it's basically generating many keys in a deterministic way from a single backed-up seed. Doesn't this make it possible for anyone with multiple public keys generated from the same seed to do some sort of correlation attack and discover the seed?

Again, I'm not a cryptographer and could be way off the mark here. I think it's a fantastic idea, if it is indeed secure.

[TierNolan]

Excuse me if I'm being a noob, but as I understand this system, it's basically generating many keys in a deterministic way from a single backed-up seed. Doesn't this make it possible for anyone with multiple public keys generated from the same seed to do some sort of correlation attack and discover the seed?

It should be hard.  The more info you provide, the easier it gets.

The biggest weakness is likely the initial password.  If that is complex enough, then it should be OK.