Bitcoin Forum
December 07, 2016, 08:45:43 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 »  All
  Print  
Author Topic: Deterministic wallets  (Read 39593 times)
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2030



View Profile
June 18, 2011, 09:27:29 PM
 #1

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.

1481100343
Hero Member
*
Offline Offline

Posts: 1481100343

View Profile Personal Message (Offline)

Ignore
1481100343
Reply with quote  #2

1481100343
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481100343
Hero Member
*
Offline Offline

Posts: 1481100343

View Profile Personal Message (Offline)

Ignore
1481100343
Reply with quote  #2

1481100343
Report to moderator
1481100343
Hero Member
*
Offline Offline

Posts: 1481100343

View Profile Personal Message (Offline)

Ignore
1481100343
Reply with quote  #2

1481100343
Report to moderator
gim
Member
**
Offline Offline

Activity: 90


View Profile
June 19, 2011, 12:11:46 AM
 #2

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
Moderator
Legendary
*
qt
Offline Offline

Activity: 2030



View Profile
June 19, 2011, 06:03:49 AM
 #3

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile
June 19, 2011, 10:15:51 AM
 #4

I like this idea.

Will

ShadowOfHarbringer
Legendary
*
Offline Offline

Activity: 1470


Bringing Legendary Har® to you since 1952


View Profile
June 19, 2011, 09:27:57 PM
 #5

Definately worth of inclusion.
+1

Basiley
Jr. Member
*
Offline Offline

Activity: 42


View Profile
June 19, 2011, 10:55:10 PM
 #6

"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
Legendary
*
Offline Offline

Activity: 980

Firstbits: Compromised. Thanks, Android!


View Profile
June 21, 2011, 01:15:41 PM
 #7

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?

Bitcoin is the ultimate freedom test. It tells you who is giving lip service and who genuinely believes in it.
...
...
In the future, books that summarize the history of money will have a line that says, “and then came bitcoin.” It is the economic singularity. And we are living in it now. - Ryan Dickherber
...
...
ATTENTION BFL MINING NEWBS: Just got your Jalapenos in? Wondering how to get the most value for the least hassle? Give BitMinter a try! It's a smaller pool with a fair & low-fee payment method, lots of statistical feedback, and it's easier than EasyMiner! (Yes, we want your hashing power, but seriously, it IS the easiest pool to use! Sign up in seconds to try it!)
...
...
The idea that deflation causes hoarding (to any problematic degree) is a lie used to justify theft of value from your savings.
je_bailey
Newbie
*
Offline Offline

Activity: 18


View Profile WWW
June 21, 2011, 03:22:06 PM
 #8

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?


Jason Bailey
Developer/Designer
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2030



View Profile
June 23, 2011, 04:18:42 PM
 #9

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
Hero Member
*****
qt
Offline Offline

Activity: 798

No Maps for These Territories


View Profile
June 23, 2011, 06:40:44 PM
 #10

+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

Bitcoin Core developer [PGP] Warning: For most, coin loss is a larger risk than coin theft. A disk can die any time. Regularly back up your wallet through FileBackup Wallet to an external storage or the (encrypted!) cloud. Use a separate offline wallet for storing larger amounts.
netrin
Sr. Member
****
Offline Offline

Activity: 322


FirstBits: 168Bc


View Profile
June 23, 2011, 10:36:11 PM
 #11

+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.

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
Enzo
Newbie
*
Offline Offline

Activity: 14


View Profile
June 24, 2011, 04:21:37 PM
 #12

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
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
June 25, 2011, 09:37:25 PM
 #13

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
Full Member
***
Offline Offline

Activity: 125


View Profile
June 26, 2011, 02:45:14 AM
 #14

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
Newbie
*
Offline Offline

Activity: 16


View Profile
June 26, 2011, 11:14:04 PM
 #15

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
Full Member
***
Offline Offline

Activity: 218


View Profile
June 27, 2011, 01:48:32 PM
 #16

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.

4096R/F5EA0017
netrin
Sr. Member
****
Offline Offline

Activity: 322


FirstBits: 168Bc


View Profile
June 28, 2011, 10:21:04 PM
 #17

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.

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
ben-abuya
Sr. Member
****
Offline Offline

Activity: 323



View Profile WWW
June 28, 2011, 10:29:02 PM
 #18

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

http://lamassubtc.com/
Lamassu Bitcoin Ventures
asdf
Hero Member
*****
Offline Offline

Activity: 527


View Profile
June 29, 2011, 12:00:10 AM
 #19

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
Legendary
*
Offline Offline

Activity: 1036


View Profile
June 29, 2011, 01:19:25 AM
 #20

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Pages: [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!