Topic: Deterministic wallets - page 15. (Read 48389 times)

Sorry, — I shouldn't post at dark-am when I should be sleeping. The mixed case threw me, I saw that a was the initial private key and thought you were saying you were using it in the hash and I stopped reading. Sorry.

I'd need to see a more concrete version of the chain version. The simplest implementation with just H(prior-key|type|serialnumber) would be insecure because the serial number would not have enough entropy. e.g. I'd generate two addresses keys on your site, getting sequential serial numbers, then I'd send money to both and wait for you to spend it and disclose the public keys in the process,  then I'd search the space of likely serial numbers such that one address leads to the next.  Then I can generate all future public addresses.

In ten seconds I see a way to address that, but there may be a better one.

It seemed to me that the lack of cheap random access was a bit of a liability, but if the chaining variable is simply the prior key or address which you'd need to cache in any case to identify transactions, then this would be pretty good.

Actually, my post specifically mentions this use case:



You don't need a seed to generate addresses securely. Knowledge of A is enough to generate addresses and you don't need to have the master private key at all.

The only problem is that if the hacker has A, he knows all your addresses, so while he can't spend your money, he can see all your blockchain activity. If you extend your seed concept a bit you could use a changing seed, so that an attack would only compromise the current seed.

Going one step further, I've recently been thinking about using a hashing chain. I.e. the hashes no longer depend on A, but instead depend on the previous hash plus the serial number. Then you make the server forget each hash as soon as it's no longer needed. The first hash would be derived beforehand from the master private key in some fashion and is then part of the deployment package to the webserver. That way you can still generate all private and public keys from the master key (full determinism), but a hacker gaining access to the merchant's webserver would only be able to spy on future transactions, not past ones.

You've missed a whole use case here:

Say I want to run a webserver that accepts paymets. It needs to be able to generate addresses, but if it gets hacked, I don't want the hacker to be able to spend any of the incoming money.

By splitting the master private key and the seed used to generate the addresses, a RX only wallet can generate unlimited new addresses without having the ability to spend or any required communication with a separate secure wallet that can spend.  An attacker who stole the data on the webserver could only deanonymize payments.

Thats why I proposed it with a separate seed.

Perhaps not important for all uses, but pretty useful for this ecommerce one.

Nice! We need this everywhere.
Wallet's private data is 1 Random number, all the rest can be derived from it.

I wanted to share some thoughts about how Webcoin is going to handle DWs. I'll use the same symbols as TierNolan.

First of all, I don't see the need for a seed. Since the seed has to be stored with the private key anyway, you might as well regard it as part of the private key.

Next, the master private key should have a full 256-bits of entropy. So we use a random number 0 < a < 2²⁵⁶. Yes, it's a pain to type. In practice you'd normally use more convenient ways to transfer DWs, such as USB sticks, QR codes, etc.

(However, if your house just burnt down and you lost every backup but the printed hardcopy at your safety deposit box, I don't think having to type a very long password is going to concern you too much.)

Here is an example of a 256-bit number using base58 encoding:

"6QPCJCRhPSVoKL4hhLoqRuBEk4VYzAFMAC1GwQ7JbSR4"

In reality we'll also add a checksum and a version byte, similar to a Bitcoin address.

In our version, there is no seed, so we've been working with v(t, n) instead of v(n, t, s).

t ... type is included only for future use. Currently it is a zero-length string, i.e. it is omitted.
n ... serial is a 64 bit unsigned integer (LE).

So a new keypair b, B is generated as:

b = a + SHA256(A t n)
B = A + SHA256(A t n)*G

A is an ECPoint encoded using standard non-compressed form (0x04 x y)

To generate a new public key for the wallet, you need to know A, t and the next serial number to use.
To spend the coins on any of the addresses, you need to know a, t and the serial number.

During normal use, we assume that we have access to a metadata storage system. The metadata storage is retrievable using an access key SHA256(A "access"). It's contents are unencrypted, symmetrically encrypted or asymmetrically encrypted depending on the application. For example, a merchant server whose only job is generating addresses would encrypt metadata for those transactions using a public key and the wallet would retrieve it using the corresponding private key. That way, if the merchant server is compromised, privacy for previous transactions is still guaranteed.

If the metadata is lost for any reason, the user can use a recovery tool to get their coins back. The recovery tool needs a full database of unspent outputs in the block chain and will simply generate public keys using sequential serial numbers using the method above. Whenever it finds coins it will add an entry to a new metadata array.

Note: Using t will make coin recovery more difficult, because the recovery tool will have to a) know all values for t and b) separately scan them all. That's why we're more interested in keeping t an empty string for all normal use cases and using the metadata to synchronize what the next available serial number is.

The maximum number of addresses for one wallet is 2⁶⁴ or 18,446,744,073,709,551,616 (for each t).


Correct. I want to add one more: As long as the master public key A is secret, nobody can break the privacy of the other addresses.

Just to confirm my understanding.

Capital letter = point (used for public keys)
Lower letter = integer (used for private keys)

a = master private
A = master public

b = generated private
B = generated public

G = generation point (constant for curve)

v(n, t, s) = hash function
s = random seed
n = transaction/key id
t = type id

The standard rule is

A = a*G

We can generate a new private key using

b = a + v(n, t, s)

The corresponding public key is

B = b*G = (a+v)*G = a*G + v(n, t, s)*G

However, a*G is the master public key

B = A + v(n, t, s)*G

So, all of the public keys can be computed with just the master public key and S. 

n and t are assumed to be pretty small numbers.

The private keys are

b = a + v(n, t, s)

They need a (the master private key) to be generated, as well as all the other values.

As long as a and s are protected, the user can never be unable to spend his coins and as long as a is kept secret, nobody else can spend his coins.

Aside from the OP's deterministic minimums based on seeds, I would like to hope the current rand seed is based on cumulative data, the time, mouse and keyboard, threads, etc. I can't find the source but there are two headers files of interest: src/key.h and src/cryptopp/cryptlib.h the former making reference to EC_KEY_generate_key which might be related to the OpenSSL implementation: http://linux.die.net/man/3/ecdsa

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.

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.

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

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.

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.

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.

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.

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?

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.

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

+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

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.