Deterministic wallets

[netrin]

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?

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

[TierNolan]

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)

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.

[Stefan Thomas]

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

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.

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.

[gim]

I wanted to share some thoughts about how Webcoin is going to handle DWs.

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

[QuantumMechanic]

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

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.

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.

Am I correct in thinking that if you keep A a secret between you and a friend, and agree to use some agreed upon sequence of serial numbers (could this just be trivial and the same for everyone?), that they could have access to an infinite number of your public keys that can't be associated by an outsider?  Edit: lol I think you just said this in the last sentence.

If so, then it seems like it could enable people to interface in the client with a contacts list instead of ugly addresses, but without having to reuse them or manually request new ones all the time.

I guess one major problem would be losing the master private key, and having people continue to send to addresses derived from the associated public key.

This could be mitigated by having your contact instead for each transaction get the master public key from an (untrusted) online storage server who stores it encrypted to your private key and your contact's public key, and check that it hasn't changed.  That way if you lose your wallet, you can stop everyone from sending to it in one step by deleting the master public keys from your storage server, and restart it again by uploading new ones for each of your contacts, without having to notify them, since their client can just start the agreed upon serial number sequence anew if they notice that the master public key has been changed.

Edit: Damn, I read your post two days ago, and forgot to re-read it before responding.  I apologize for basically restating what you did.

[gmaxwell]

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.

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.

[Stefan Thomas]

You've missed a whole use case here:

Say I want to run a webserver that accepts paymets.

Actually, my post specifically mentions this use case:

To generate a new public key for the wallet, you need to know A, t and the next serial number to use.

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.

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.

[gmaxwell]

Actually, my post specifically mentions this use case:
[snip]
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.

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.

[Stefan Thomas]

I'd need to see a more concrete version of the chain version.

Good point, I should have been more specific. So here is the chain variation in detail.

Let s_n be the second part of the private key which the merchant's webserver generates.

The private and public keys are therefore:

b_n = a + s_n
B_n = A + s_n*G

The first hash s₀ is generated by the wallet as follows:

s₀ = SHA256(a i C)

i ... A 64-bit integer (LE) that starts at 0 and is incremented if the same wallet is used for more than one chain.
C ... Some constant, e.g. "BITCOIN_CHAINHASHSEED_gZ5hA5S7237RoJ" - this is the same globally for everybody.

The merchant then takes s₀, i and A and inputs them as settings on his webserver. The server initializes the transaction serial number n as 0. It is now ready to accept orders.

A user wants to do an order and pay in Bitcoins. The merchant server now runs through the following steps:

1. Increment n.

2. Generate new s_n:

s_n = SHA256(s_n-1 n C)

n ... The current serial number as a 64-bit integer (LE).
C ... Another constant, e.g. "BITCOIN_CHAINHASH_2bIyLHNXlHe77u" - this is the same globally for everybody.

3. Derive the public key B_n:

B_n = A + s_n*G

4. Create, output and store the Bitcoin address corresponding to B_n.

5. Securely delete s_n-1.

Note that storing the address in step 4 depends heavily on the specific use case. Here are a few examples:

(A) The server stores the address until the payment arrives and then sends the details of the order via email to the merchant at which point it deletes its own stored information about the order.

(B) The server doesn't store the address in plain text, but instead encrypts it with a public key and stores it like that. Every day the orders are downloaded, decrypted and processed on an offline system.

(C) The server stores the address until the payment arrives, then enables the user's account to access the digital content he/she has purchased. After that the server encrypts the address and other information related to the transaction with a public key and stores it for archival.

Implementation-wise we would probably wrap the chainhash stuff in a library that takes A as a configuration value and s₀ and n as initialization values and just spits out new addresses on demand. It would also provide utility functions to write data to the metadata storage like setDescription(chainSerial, transactionSerial, description). This information could be submitted to the wallet metadata using asymmetric encryption and later be retrieved by the wallet software and displayed in the list of transactions - similar to Bitcoin's address book feature.

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.

Hmm, I don't think that attack is possible - or I haven't understood it correctly. My chain consists of private information only. Having the public key and the serial number would not enable you to predict the next address. Curiously, even breaking ECC and finding out any number of b_n wouldn't give you access to s_n, because you'd still only have sums a + s_n with no way to solve for a.

More realistically, breaking into the server you could compromise the current s_n and the current serial number n, which would tell you how many transactions have taken place as well as predict any future addresses - both with respect to this specific chain. It would not allow you, however, to find out any of the previous addresses unless that information is still stored on the server in some other fashion.

Caveat: The chain serial i increases the dimensionality of the address space. If all metadata of the wallet is lost and we want to recover our money based on only the private master key a, we have to in theory try every n for every i. In practice, the user will likely have a small number of chains per wallet and/or know roughly how many he/she has. So the search would be limited to very small values for i. Given that a total loss of metadata is a worst case scenario and other types of backup are likely being used as well, a certain amount of computational work for the recovery procedure seems acceptable.

With Webcoin specifically we hope to eventually store the encrypted metadata in a DHT. At that point the deterministic wallet concept serves two goals: (1) Reducing the amount of data that needs to be stored (a serial number like i and n could be stored as a var_int, 1 to 9 bytes, compared to a private key (32 bytes) or even a public key (65 bytes)) and (2) Providing a "last resort" recovery mechanism if all else fails - namely by scanning for unspent outputs using the private master key.

[vermorel]

Bitcoin really ought to offer and default to using deterministic wallets.

Agreed very much. I was quite surprised to discover this feature after muddling through a lot of very geeky documentation. People can't be expected to comprehend this sort of quirks.

[hashcoin]

I just looked at OP but be aware when designing a scheme like this you must be very careful to use the correct cryptographic primitive.

The primitive you are looking for here is a http://en.wikipedia.org/wiki/Pseudorandom_function_family.
A http://en.wikipedia.org/wiki/Cryptographic_hash_function is NOT the same thing.  In particular, it is not true that given a hash function H, taking family F(K)(X) = H(K | X) will yield a PRF (perhaps, for a particular hash function, it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function).

PRFs are mainly used to construct other things and so may be unknown to you.  You likely do know something very similar, the "PRP" or Pseudorandom Permutation, which is like a PRF but which is indisinguishable from a random permutation by bounded adversaries (note the two are basically the same to an adversary, since they could never distinguish a random function from a random permutation anyway, as querying a random function on a reasonable number of places will never show two values mapping to the same).  PRPs are what applied crypto people call "Block ciphers".  So you can use a block cipher, e.g., AES, to do what you are trying to do.   But do NOT use a hash function, that is not what it is for.

Again I cannot stress enough how important it is that correct crypto primitives are used for their intended purposes.

[ByteCoin]

The primitive you are looking for here is a pseudorandom function.
A cryptographic hash function is NOT the same thing.  In particular, it is not true that given a hash function H, taking family F(K)(X) = H(K | X) will yield a PRF (perhaps, for a particular hash function, it will yield something nobody knows how to break, but its security is not provable assuming the security of the hash function).
...
Again I cannot stress enough how important it is that correct crypto primitives are used for their intended purposes.

So instead of using a hash we should be using a block cipher?

I presume that the difference between the two with the most practical impact is the presence of collisions in the former and the absence thereof in the latter.

I'm not really calling in to question the validity of what you say but, to make your point more obvious, could you give a realistic example of a situation in which using a hash function instead of a pseudorandom function gives noticable problems?

ByteCoin

[ben-abuya]

The primitive you are looking for here is a pseudorandom function.
A cryptographic hash function is NOT the same thing.  In particular, it is not true that given a hash function H, taking family F(K)(X) = H(K | X) will yield a PRF (perhaps, for a particular hash function, it will yield something nobody knows how to break, but its security is not provable assuming the security of the hash function).
...
Again I cannot stress enough how important it is that correct crypto primitives are used for their intended purposes.

So instead of using a hash we should be using a block cipher?

I presume that the difference between the two with the most practical impact is the presence of collisions in the former and the absence thereof in the latter.

I'm not really calling in to question the validity of what you say but, to make your point more obvious, could you give a realistic example of a situation in which using a hash function instead of a pseudorandom function gives noticable problems?

ByteCoin

I'm no cryptographer, but hashcoin said "it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function". So the problem isn't that there's a known weakness, but that it's not provably secure, as PRF is, assuming the security of the function.

[Stefan Thomas]

The primitive you are looking for here is a http://en.wikipedia.org/wiki/Pseudorandom_function_family.
A http://en.wikipedia.org/wiki/Cryptographic_hash_function is NOT the same thing.  In particular, it is not true that given a hash function H, taking family F(K)(X) = H(K | X) will yield a PRF (perhaps, for a particular hash function, it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function).

Yep, you're correct. I'll update my posts to use SHA-256 with HMAC, which is used as a PRF in IPSec, TLS, DKSPP, etc.

[JoelKatz]

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?

No. Because it's the secret keys that are correlated and an attacker would only have the public keys.

Even if he did have some secret keys, it wouldn't matter. This attack would be possible in theory but impossible in practice because the scheme is specifically designed to make it impractical. (It's not particularly hard to do that. Both schemes proposed use well-known methods to prevent this even if an attacker had some private keys somehow.)

Of course, if the seed gets out, all future keys are compromised.

[netrin]

This is a fascinating thread, and although the maths often fly over my head, I'm earnestly trying to keep up. Please correct me if I have been derailed from the very beginning, the goal is to base an entire infinitely expandable wallet on a single seed. While subsequent data (generated keys, transaction references, etc) could be stored with a wallet, all that is critically necessary to back up is this (what?) 100 byte seed. Everything else can be regenerated ad nauseum.

[JoelKatz]

If this mechanism is being seriously considered, someone needs to make sure it's not encumbered by a patent. I remember when I first heard the notion of a "family of public keys" such that a single private key would allow deriving the corresponding family of private keys, I seem to recall it being patented. That was at least three years ago, I think, so it may not even be covered any more.

[gmaxwell]

If this mechanism is being seriously considered, someone needs to make sure it's not encumbered by a patent. I remember when I first heard the notion of a "family of public keys" such that a single private key would allow deriving the corresponding family of private keys, I seem to recall it being patented. That was at least three years ago, I think, so it may not even be covered any more.

FWIW, I may be filing a patent on this, so I'll report back if I find anything problematic.

If I do so, I will be offering it under terms no more restrictive than the Xiph.Org patent license: https://datatracker.ietf.org/ipr/1524/  (e.g. a free license to anyone who doesn't conduct patent litigation against bitcoin users)
 

[Xephan]

FWIW, I may be filing a patent on this, so I'll report back if I find anything problematic.

If I do so, I will be offering it under terms no more restrictive than the Xiph.Org patent license: https://datatracker.ietf.org/ipr/1524/  (e.g. a free license to anyone who doesn't conduct patent litigation against bitcoin users)
 

I'm curious, are you allowed to file a patent AFTER discussing it in a public forum? I was informed, perhaps wrongly, that if I had intentions of patenting something, prior to actual filing I should never disclose it in public or discuss it without making clear it is confidential, otherwise it would render the idea inadmissable.

[old_engineer]

FWIW, I may be filing a patent on this, so I'll report back if I find anything problematic.

If I do so, I will be offering it under terms no more restrictive than the Xiph.Org patent license: https://datatracker.ietf.org/ipr/1524/  (e.g. a free license to anyone who doesn't conduct patent litigation against bitcoin users)
 

I'm curious, are you allowed to file a patent AFTER discussing it in a public forum? I was informed, perhaps wrongly, that if I had intentions of patenting something, prior to actual filing I should never disclose it in public or discuss it without making clear it is confidential, otherwise it would render the idea inadmissable.

It depends on the country, in the US you have 1 year to file after demonstrating your invention in public.