Deterministic wallets

[old_engineer]

I like that this idea makes it more convenient to back up your wallet addresses, lessening chance of losing bitcoins through hard drive failure/fire/whatnot, but the proposed solution creates an unacceptable trade-off in that it's too easy for an attacker to compromise all future transactions.  If the attacker has access to a wallet just once, they can clear out the victims wallet at any future time, and at a time of their choosing when they believe they will get maximum value out of the wallet.  And when the attacker chooses to act, the victim will never know what hit them, or when the wallet was compromised - it could have been months or years in the past.  This seems scary to me, and would keep me from using the same wallet over a period of years.  Regularly creating new wallets rather defeats the purpose of the idea of a deterministic wallet that doesn't need multiple back-ups.

How about a middle ground: the client could pre-generate the next, say, 100 addresses, and then whenever a backup is performed, these pre-generated future addresses are also saved.  "New" addresses are actually being pulled from this pool of pre-generated addresses.  Enough addresses should be generated to cover, say, a month's worth of transactions, the maximum supported time between wallet backups (yes, some people only back up monthly).  Pre-generated addresses that were unused for a month would be discarded.  Exact number of pre-generated addresses would be set in Preferences page.

With this scheme, even if a hard drive fails right after receiving a transaction using a "new" (but actually pre-generated) address, the transaction address used would have already been backed up in the past month.  It would be kind of like the new video cameras that are always recording, overwriting their cache constantly, and when you press the button _after_ the action has happened, the previous 10 seconds of video in the cache is saved to memory. 

An attacker that compromises the wallet with pre-generated addresses would then want to act within a month since they could not compromise all future transactions as with the deterministic wallet.  This tighter coupling between the time of compromise and the wallet being emptied is a Good Thing for post-hoc failure analysis.  And if you transfer all of your coins to a "new" address, you can be guaranteed that your wallet is secure, even if someone finds, say, an old backup you forgot about and threw out in the trash.

This scheme also avoids the potential cryptographic problems of creating a seed address that might, just might, have a cryptographic vulnerability. Using a set of pre-generated addresses avoids this issue by using future randomness in generating future keys.

Finally, philosophically, I think wallets need to be living entities, and an immortal wallet is not a good idea.  I can't concisely explain the reasons why this is best besides the above example about the backup found in the trash.  There's a reason the PGP key system is designed to allow keys to expire, and all good security systems require occasional password changes.

[Luke-Jr]

How about a middle ground: the client could pre-generate the next, say, 100 addresses, and then whenever a backup is performed, these pre-generated future addresses are also saved.  "New" addresses are actually being pulled from this pool of pre-generated addresses.

It already does.

Finally, philosophically, I think wallets need to be living entities, and an immortal wallet is not a good idea.  I can't concisely explain the reasons why this is best besides the above example about the backup found in the trash.  There's a reason the PGP key system is designed to allow keys to expire, and all good security systems require occasional password changes.

Even after a PGP key has expired, you can simply edit it to extend the expiration date. Passwords on deterministic wallets can be changed like any other.

[old_engineer]

How about a middle ground: the client could pre-generate the next, say, 100 addresses, and then whenever a backup is performed, these pre-generated future addresses are also saved.  "New" addresses are actually being pulled from this pool of pre-generated addresses.

It already does.

Doh, it's like I read https://en.bitcoin.it/wiki/Securing_your_wallet many moons ago, forgot it, then wrote it back out again, thinking I was being original.  Squishy data storage (brains) aren't very good. http://www.htmlhelpcentral.com/messageboard/showthread.php?13363-Mind-Control-Magic-and-the-Value-of-Branding-Online

[elements]

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.

I am wondering the same thing: if the wallet is deterministic and you publish several public keys shouldn't it be possible to calculate the original private key? Especially regarding merchants, restaurants and such who most likely will publish a lot of keys. The more keys published the easier it should get to find the private key!

Or am I missing something?

[Sukrim]

As it is currently not (in realistic time) possible to get a private key to a public address, you are likely also not able to determine how these private keys might be linked together.

[JoelKatz]

I am wondering the same thing: if the wallet is deterministic and you publish several public keys shouldn't it be possible to calculate the original private key? Especially regarding merchants, restaurants and such who most likely will publish a lot of keys. The more keys published the easier it should get to find the private key!

Or am I missing something?

No, you are correct. But it doesn't matter. Here "easier" means that if you dedicated every computer on the planet to breaking a key, it might take a few dozen centuries rather than a few hundred centuries. In fact, the system is so strong, even if you released the master public key, allowing an attacker to generate as many related public keys as he wanted, it would still be impossible (for practical purposes) for him to compromise a single private key. (In fact, this scheme was originally developed with the idea of using it exactly that way.)

This is the interesting thing about public key cryptography. Attacks are always possible. Every conceivable compromise is doable in principle. So you can't just check if an attack is theoretically possible, you have to ask if it is practical.

[ByteCoin]

I'd like to direct you to a proposal which could be seen as implementing a type 2 deterministic wallet on funder's clients. The hash function in this case is choosing the x coordinate of an elliptic curve multiply in a similar fashion to ECDSA.

I believe that this would satisfy the goals of a deterministic wallet and have a number of other fairly obvious beneficial effects.

ByteCoin

[cypherdoc]

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

can someone explain this to me?

[etotheipi]

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

can someone explain this to me?

If someone steals your wallet, they get all your old addresses and the next 100, but no more.  When you start using addresses, the key pool keeps getting refilled with random addresses based on the random number generator on your computer.  The attacker will generate different (and thus useless) addresses.   Therefore, if someone steals your wallet, it "unsteals" itself after you go through 100 addresses.

Since the point of deterministic wallets is to produce the same sequences of addresses every time, the attacker will always generate the exact same addresses until the end of time.  They have permanently stolen your wallet, and could wait years before executing an attack, if they knew you were going to keep using it.

However, I'm of the opinion that this is basically irrelevant.  The severity of attacks on both types are not much different, and many cases they are the same -- because if the attacker has access to your system to steal it, they can install a process to continue stealing your wallet.  I firmly believe that users' not having sufficient backups is a tremendously more significant risk to their wallets.  As such, deterministic wallets are superior since they only require one backup at time of creation.

[Stefan Thomas]

However, I'm of the opinion that this is basically irrelevant.  The severity of attacks on both types are not much different, and many cases they are the same -- because if the attacker has access to your system to steal it, they can install a process to continue stealing your wallet.  I firmly believe that users' not having sufficient backups is a tremendously more significant risk to their wallets.  As such, deterministic wallets are superior since they only require one backup at time of creation.

I agree. If an attacker has access to your system and you don't notice it, he can continue to download new copies of the wallet and if you do notice it, you can generate a new wallet and transfer your money over. So the ability of current wallets to unsteal themselves only applies if:

• The attacker waits rather than stealing your wallet's current contents.
• You unknowingly/accidentally fix the hole he/she used to break into your computer.
• You use up ~100 addresses before the attacker notices he/she no longer has access to your machine.

In high-security scenarios, a better alternative than a set of pregenerated addresses would be to simply create entirely new wallets from time to time. Whether these are deterministic or not makes no difference at that point.

At the same time for normal users a deterministic wallet makes it much easier to protect against a whole range of data loss scenarios. It's much easier to have secure, long-term backups if you don't have to constantly update the backed-up data. As long as it is implemented well, it should be just as secure against theft and much more secure against loss.

[cypherdoc]

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

can someone explain this to me?

If someone steals your wallet, they get all your old addresses and the next 100, but no more.  When you start using addresses, the key pool keeps getting refilled with random addresses based on the random number generator on your computer.  The attacker will generate different (and thus useless) addresses.   Therefore, if someone steals your wallet, it "unsteals" itself after you go through 100 addresses.

Since the point of deterministic wallets is to produce the same sequences of addresses every time, the attacker will always generate the exact same addresses until the end of time.  They have permanently stolen your wallet, and could wait years before executing an attack, if they knew you were going to keep using it.

However, I'm of the opinion that this is basically irrelevant.  The severity of attacks on both types are not much different, and many cases they are the same -- because if the attacker has access to your system to steal it, they can install a process to continue stealing your wallet.  I firmly believe that users' not having sufficient backups is a tremendously more significant risk to their wallets.  As such, deterministic wallets are superior since they only require one backup at time of creation.

so this paper backup i generated from Armory consists of a Root Key and a Chain Code.  is the Root Key the same as the Master Private Key discussed here earlier?  whats the Chain Code and where is the Seed?

[etotheipi]

so this paper backup i generated from Armory consists of a Root Key and a Chain Code.  is the Root Key the same as the Master Private Key discussed here earlier?  whats the Chain Code and where is the Seed?

The "root key" is a Bitcoin address that serves as the "root node" of the deterministic wallet.  All other addresses are based on it.  The chaincode is another 32-byte number that helps you get from PrivKey(i) to PrivKey(i+1) or PubKey(i) to PubKey(i+1).    In order to have "type 2" deterministic wallets, you will need to be multiply the priv/pub keys by a number... so the chaincode is used to create that number.

As described by gmaxwell, you could easily use lots of different chaincodes to create different address "branches".  Right now, in Armory, there is only one chaincode per wallet.  But you could could add multiple chaincodes to create multiple "branches" that would then appear unrelated -- i.e. you could give someone a watching-only wallet with the first chaincode, another person with a different chaincode but same root public key -- they'll generate two completely different address chains even though they both have the same root public key.  You can generate all private keys in both, but the two people will not be able to generate or even recognize addresses on the other branch.

[cypherdoc]

so this paper backup i generated from Armory consists of a Root Key and a Chain Code.  is the Root Key the same as the Master Private Key discussed here earlier?  whats the Chain Code and where is the Seed?

The "root key" is a Bitcoin address that serves as the "root node" of the deterministic wallet.  All other addresses are based on it.  The chaincode is another 32-byte number that helps you get from PrivKey(i) to PrivKey(i+1) or PubKey(i) to PubKey(i+1).    In order to have "type 2" deterministic wallets, you will need to be multiply the priv/pub keys by a number... so the chaincode is used to create that number.

As described by gmaxwell, you could easily use lots of different chaincodes to create different address "branches".  Right now, in Armory, there is only one chaincode per wallet.  But you could could add multiple chaincodes to create multiple "branches" that would then appear unrelated -- i.e. you could give someone a watching-only wallet with the first chaincode, another person with a different chaincode but same root public key -- they'll generate two completely different address chains even though they both have the same root public key.  You can generate all private keys in both, but the two people will not be able to generate or even recognize addresses on the other branch.

what does the QR code represent?

[etotheipi]

what does the QR code represent?

The QR code is the exact same data, but in a QR code.  The primary goal was that you could use the paper backup as both a backup, and a means to transfer a wallet to your smartphone, just by scanning it (there are currently no Bitcoin apps that leverage my wallet format, but I'm getting help to work on one, now).  But it would also be useful if you have a webcam setup for scanning QR codes -- it'll pick up the exact same letters as shown on the page, and you can just copy the text into the "paper backup import" dialog.

For anyone in this thread who has no idea what I'm talking about, the paper backup looks like this:

[cypherdoc]

what does the QR code represent?

The QR code is the exact same data, but in a QR code.  The primary goal was that you could use the paper backup as both a backup, and a means to transfer a wallet to your smartphone, just by scanning it (there are currently no Bitcoin Android apps that leverage my wallet format, but I'm getting help to work on one, now).  But it would also be useful if you have a webcam setup for scanning QR codes -- it'll pick up the exact same letters as shown on the page, and you can just copy the text into the "paper backup import" dialog.

For anyone in this thread who has no idea what I'm talking about, the paper backup looks like this:

so how do u get priv/pub keypairs out of the root key/Bitcoin address?

[etotheipi]

so how do u get priv/pub keypairs out of the root key/Bitcoin address?

I picked a sub-optimal construction, and wished I had talked to gmaxwell and sipa before I commmitted myself to it, because I like theirs better.  However, there's nothing wrong with what I did, it's just that it can be a little slow, and theirs has some nice properties (like random access).  I will be adding support for their method in Armory and deprecating mine (eventually).  Until then, here is both algorithms:

Let the root address be considered keyIndex=0, C be the chaincode, and O be the order of the elliptic curve group:

Mine:
M = doubleSHA256(PublicKey(i)) XOR C
PrivKey(i+1) = (PrivKey(i) * M) mod O


gmaxwell and sipa use HMAC construction; || represents concatenation
PrivKey(n) = SHA256( C || SHA256(C || PubKey(0) || n) )

[mila]

I'm interested in deterministic wallets especially how to generate pools of addresses
with the parameter range from-to
I want to have addresses generated on the server side (and not saving the private keys there), offering users unique addresses (tipping jar/donations, sales, etc) while not exposing the public keys to any network.
I found bitaddress script has some limited support for deterministic wallets but I can't use it effectively yet.

[etotheipi]

I'm interested in deterministic wallets especially how to generate pools of addresses
with the parameter range from-to
I want to have addresses generated on the server side (and not saving the private keys there), offering users unique addresses (tipping jar/donations, sales, etc) while not exposing the public keys to any network.
I found bitaddress script has some limited support for deterministic wallets but I can't use it effectively yet.

Mila,

Look at Armory.  It provides exactly what you describe:  keep the full wallet somewhere else (maybe not even touching the internet), create a watching-only copy of it (no private keys), and use that on your website to distribute addresses.  There is no JSON-RPC interface to it (yet!), but I could help you produce a straightforward script along the lines of "getAnotherAddress.py" that will read your watching-only wallet fie, and return the next unused address.

If you want more information, see the presentation on my webpage:  Using Offline Wallets in Armory.  That doesn't show you exactly what to press, but it explains how the process works.  Please PM me if you want help setting it up

This is one of the reasons I created watching-only wallets -- risk-free webservers.  I hope you get some benefit out of it!

[btc_artist]

Good work eto.  I think deterministic wallets should be considered for the reference implementation as well.

[etotheipi]

Good work eto.  I think deterministic wallets should be considered for the reference implementation as well.

Actually, they are.  Sipa has a test branch implementing the deterministic wallets I described above (the HMAC version)... though it will probably a little while before it gets fully tested and merged.   Once that happens, I will add support to Armory for it.