Deterministic wallets

[iddo]

thanke: the two properties that we were discussing are:

(1) deriving the chaincodes independently of the keys (in order to achieve the minor benefitial property in your use case), so for example you could replace the privkey in the master (root) node and still retain your old wallet layout with all your old chaincodes intact, just with new keys. Do you now agree with me that your proposal doesn't achieve this property when you also support type-1 derivation? Or do you still claim that with your scheme you can replace only the master key and retain the same exact tree structure with all the old chaincodes intact? You continue to tweak your proposal, which is good, but it makes it a little difficult for me to see what exactly your latest proposal achieves, especially in terms of practical use cases. If you agree with me regarding this property, then wouldn't you also agree that BIP32 is better simply because BIP32 uses all the available entropy and you use only some of the available entropy? Isn't it true that your type-1 derivation is essentially the same as the type-1 derivation in BIP32?

(2) whether leakage of one particular privkey (e.g. the attacker received one pubkey and managed to break it and discover the corresponding privkey) implies that the entire sub-tree rooted at this privkey also leaks, or the attacker must also obtain some private seed/chaincode to derive the sub-tree. With BIP32 you'd need the pubkey and chaincode to do type-2 derivations and compute all the pubkeys/chaincodes in the sub-tree, and you'd need the privkey and chaincode to derive the entire sub-tree. What is your claim regarding this property?

Maybe you should start a new page on the wiki and decribe your scheme with full details there?

A general question: do we expect that intermediate nodes actually use their privkey, which at the same time is the base for their children's privkey, on the blockchain? Or will only the leafs' privkeys get used on the blockchain?

Yes, the privkeys of intermediate nodes are also used. See for example the picture with default wallet layout in the BIP32 wiki page, where the subaccounts at depth 1 get extended as unbounded linear paths.

[thanke]

thanke: the two properties that we were discussing are:

(1) deriving the chaincodes independently of the keys (in order to achieve the minor benefitial property in your use case), so for example you could replace the privkey in the master (root) node and still retain your old wallet layout with all your old chaincodes intact, just with new keys. Do you now agree with me that your proposal doesn't achieve this property when you also support type-1 derivation? Or do you still claim that with your scheme you can replace only the master key and retain the same exact tree structure with all the old chaincodes intact?

Ok, let's go through this step by step. In #112 I proposed the modification to BIP32 that you are discussing here under (1), which consisted of removing the dependence of ci on Kpar, and said:

This question/suggestion is about the "public derivation".

At that point I was not even aware that type-I derivation was already concretely specified in BIP32. So my first proposal (from #112, not the later "tweaked" versions) should be read as modifying only the public derivation in CKD of BIP32, and leaving the secret derivation. Now how do you mean this question:

Do you now agree with me that your proposal doesn't achieve this property when you also support type-1 derivation?

Are you asking if I agree with

a) the modification of the public derivation is inconsistent with the secret derivation, so it's not possible to have them both?

or

b) a similar modification achieving a similar property is not possible for the secret derivation?

[iddo]

Are you asking if I agree with

a) the modification of the public derivation is inconsistent with the secret derivation, so it's not possible to have them both?

or

b) a similar modification achieving a similar property is not possible for the secret derivation?

I guess that (a) is similar to what I'm asking, it's not about post #112, it refers to the issues raised in post #168 in response to post #167.
I was trying to understand your latest proposal better by asking specific well-defined questions, the question was whether your scheme allows replacing just the master privkey and retain the entire wallet tree structure, so that all the old chaincodes remain intact, while supporting both type-1 and type-2 derivations? The answer to this question was "yes" with a scheme that supports only type-2 derivation.

I recommended that you write your full scheme in the wiki, because it's easier to make tweaks there than in forum posts.

[thanke]

Are you asking if I agree with

a) the modification of the public derivation is inconsistent with the secret derivation, so it's not possible to have them both?

or

b) a similar modification achieving a similar property is not possible for the secret derivation?

I guess that (a) is similar to what I'm asking, it's not about post #112, it refers to the issues raised in post #168 in response to post #167.
I was trying to understand your latest proposal better by asking specific well-defined questions, the question was whether your scheme allows replacing just the master privkey and retain the entire wallet tree structure, so that all the old chaincodes remain intact, while supporting both type-1 and type-2 derivations? The answer to this question was "yes" with a scheme that supports only type-2 derivation.

The answer is "yes" again, I think. Simply use (IL,IR) := HMAC(cpar,i) as proposed in #167 for both types of derivation and proceed as in BIP 32 (ki = I_L*kpar). It doesn't give any new property for the secret derivation as it does for the public one, but it doesn't break secret derivation either.

[thanke]

If you agree with me regarding this property, then wouldn't you also agree that BIP32 is better simply because BIP32 uses all the available entropy and you use only some of the available entropy?

Entropy above 256 bit should be irrelevant for deriving keys which are 256 bit. The seed for master node is 256 bit anyway, so even in BIP 32 the entropy of the whole (IL,IR) cannot exceed that.

Isn't it true that your type-1 derivation is essentially the same as the type-1 derivation in BIP32?

You mean the one of #180?

Maybe you should start a new page on the wiki and decribe your scheme with full details there?

If I start a wiki page then it would be about a new scheme written from scratch, not about small modifications to BIP 32. This would take me a while to think through, possibly till after the conference.

[thanke]

(2) whether leakage of one particular privkey (e.g. the attacker received one pubkey and managed to break it and discover the corresponding privkey) implies that the entire sub-tree rooted at this privkey also leaks, or the attacker must also obtain some private seed/chaincode to derive the sub-tree. With BIP32 you'd need the pubkey and chaincode to do type-2 derivations and compute all the pubkeys/chaincodes in the sub-tree, and you'd need the privkey and chaincode to derive the entire sub-tree. What is your claim regarding this property?

Yes, if you remove dependencies then an attacker needs less if something leaks. That's unavoidable. It's not clear though whether it matters or not. We need a rigorous definition of the properties that we use to evaluate/analyze/compare the different specs/proposals. Defining these properties is probably more important right now than new specs, and would be the first thing I put on a new wiki page.

[iddo]

Are you asking if I agree with

a) the modification of the public derivation is inconsistent with the secret derivation, so it's not possible to have them both?

or

b) a similar modification achieving a similar property is not possible for the secret derivation?

I guess that (a) is similar to what I'm asking, it's not about post #112, it refers to the issues raised in post #168 in response to post #167.
I was trying to understand your latest proposal better by asking specific well-defined questions, the question was whether your scheme allows replacing just the master privkey and retain the entire wallet tree structure, so that all the old chaincodes remain intact, while supporting both type-1 and type-2 derivations? The answer to this question was "yes" with a scheme that supports only type-2 derivation.

The answer is "yes" again, I think. Simply use (IL,IR) := HMAC(cpar,i) as proposed in #167 for both types of derivation and proceed as in BIP 32 (ki = I_L*kpar). It doesn't give any new property for the secret derivation as it does for the public one, but it doesn't break secret derivation either.

I don't see how the answer is "yes" if the property that we are trying to obtain with type-1 derivation is: assuming that all the chaincodes of the wallet are public, and the privkey k_i leaks, the attacker still cannot find the privkey k_par
This property holds for BIP32 type-1 derivation, but if you suggest here that c_i=hash(c_par,i) and k_i=f(c_i)*k_par then the attacker can solve k_i=f(c_i)*x and discover x=k_par (which he cannot do with BIP32, that's the whole point behind supporting type-1 derivation, see the discussion starting at post #104).
If the answer is "no", then I'm not sure whether your use case still applies.

[thanke]

Are you asking if I agree with

a) the modification of the public derivation is inconsistent with the secret derivation, so it's not possible to have them both?

or

b) a similar modification achieving a similar property is not possible for the secret derivation?

I guess that (a) is similar to what I'm asking, it's not about post #112, it refers to the issues raised in post #168 in response to post #167.
I was trying to understand your latest proposal better by asking specific well-defined questions, the question was whether your scheme allows replacing just the master privkey and retain the entire wallet tree structure, so that all the old chaincodes remain intact, while supporting both type-1 and type-2 derivations? The answer to this question was "yes" with a scheme that supports only type-2 derivation.

The answer is "yes" again, I think. Simply use (IL,IR) := HMAC(cpar,i) as proposed in #167 for both types of derivation and proceed as in BIP 32 (ki = I_L*kpar). It doesn't give any new property for the secret derivation as it does for the public one, but it doesn't break secret derivation either.

I don't see how the answer is "yes" if the property that we are trying to obtain with type-1 derivation is: assuming that all the chaincodes of the wallet are public, and the privkey k_i leaks, the attacker still cannot find the privkey k_par

Correct, but why exactly are we trying to obtain this property with type-1 derivation? In BIP 32 type-1 the chaincode cpar is completely useless without kpar (unlike in type-2) so why would you assume that the chaincode is public? Just keep it together with the privkey. I see now, you probably want both types of derivation to be possible at each node, and the problem is then that we use the same chaincode for both types, so you cannot make it public for type-2 and keep it secret for type-1 at the same time. So you would need to carry two chaincodes, one for each derivation type (one of the chaincodes can replace the privkey as in #180, so it would still be a pair, not a triple). To summarize: yes, the proposal from #167 doesn't work well in "mixed" trees where both types of derivation occur. Wanting that property in mixed trees requires an additional tweak to type-1 derivation.

This property holds for BIP32 type-1 derivation, but if you suggest here that c_i=hash(c_par,i) and k_i=f(c_i)*k_par then the attacker can solve k_i=f(c_i)*x and discover x=k_par (which he cannot do with BIP32, that's the whole point behind supporting type-1 derivation, see the discussion starting at post #104).
If the answer is "no", then I'm not sure whether your use case still applies.

Without additional tweaks, "injecting" a new master keypair would only work for all-type-2 trees. Not very nice. Strictly speaking my use case "scenario" was all-type-2 though.

Another general question: do we have any use cases for mixed trees? Should we even allow them?

[iddo]

Another general question: do we have any use cases for mixed trees? Should we even allow them?

The reason is security, when only type-2 is used we get that leakage of any one privkey somewhere in the wallet tree structure implies that all the other privkeys of the wallet also leak, see posts #105, #106, #122

[iddo]

(one of the chaincodes can replace the privkey as in #180, so it would still be a pair, not a triple)

But if it's a pair then property (2) of post #181 fails.

[iddo]

thanke: regarding your scheme and use case where the chaincodes and keys are unlinked, we should have noticed that if c_i=hash(c_par,i) and K_i=c_i*K_par then anyone could take the pubkeys K_par,K_i and solve x*K_par=K_i to discover the supposedly secret chaincode x=c_i, meaning that all the chaincodes would leak trivially. Though it's not an irreconcilable issue, simply take any OWF hash2 and derive the child key via K_i=hash2(c_i)*K_par, just note that the added complexity of hash2 cannot be avoided.
Obviously BIP32 was also designed to prevent this issue, and when discussing the additive variant with Pieter we considered the closely related issue of whether the leakage of I_L*G could be exploited (the answer appears to be "no" even if I_L itself leaks).

[iddo]

IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed. One possible remedy (external to BIP32) is to encourage users to do the right thing by offering a GUI menu option that backups the entire wallet with deniable encryption, and recommend to the user to put only this kind of backup in public places. This can be implemented by creating a designated subaccount at depth 1 for this purpose, e.g. with index 0, and encrypting the secondary wallet with decoy passphrase by having this subaccount as its root node. Another way to select the fake root is by traversing the wallet tree structure via random walk until we reach a subtree that holds less coins than some threshold, but then we might need to somehow tag this subtree's root node in the real wallet, otherwise many more coins could be transferred to this subtree in the future.

[iddo]

@iddo: have a look at https://bitcointalk.org/index.php?topic=102349.0

This is even nicer than I first realized, because the GUI can let the user choose a minimal desired strength, and it'd work by dismissing all seed attempts that fall below the desired strength. So for example if the user chooses minimal strength of 15 leading 0 bits, then it will defeat attackers who only try to brute-force seeds that have up to 14 leading 0 bits.

Maybe the client should benchmark the CPU (GPU?) speed to derive the maximal cutoff strength and minimal recommended strength, and allow the user to override the minimal/maximal strengths if he wishes to obtain greater security.

I guess that the dictionary shouldn't be hardcoded, so users could plug in different dictionaries instead of the default dictionary, which would give security through obscurity (e.g. dictionaries in different languages).

BTW these self-descriptive strengthened keys should probably also be used with the AES wallet encryption that we have now, not just for HD brainwallets. Though maybe the client should have an hidden option to disable it (i.e. both when encrypting and when decrypting the wallet), to be backward compatible with previously encrypted wallets, and for (advanced? dumb?) users who don't want to memorize the dictionary postfix.

[thanke]

thanke: regarding your scheme and use case where the chaincodes and keys are unlinked, we should have noticed that if c_i=hash(c_par,i) and K_i=c_i*K_par then anyone could take the pubkeys K_par,K_i and solve x*K_par=K_i to discover the supposedly secret chaincode x=c_i, meaning that all the chaincodes would leak trivially.

No, solving K_i=x*K_par for x is the discrete log problem.

Though it's not an irreconcilable issue, simply take any OWF hash2 and derive the child key via K_i=hash2(c_i)*K_par, just note that the added complexity of hash2 cannot be avoided.
Obviously BIP32 was also designed to prevent this issue, and when discussing the additive variant with Pieter we considered the closely related issue of whether the leakage of I_L*G could be exploited (the answer appears to be "no" even if I_L itself leaks).

There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

A property that (seemingly) hasn't been discussed is the provability of the link. You want to be able to prove that a given child belongs to a give parent, without de-anonymizing the other children (the siblings), i.e. without revealing the chaincode. In current BIP 32 this can be done by revealing I_L. As you note, I_L is already a "second hash".

[thanke]

IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed.

What's your assumption here? That a user stores his full wallet in the cloud, including privkeys, in encrypted form? Is the worry just about deniability?

[iddo]

No, solving K_i=x*K_par for x is the discrete log problem.

Oops, you're right, apologies.
And it will still be DLP even if you use the additive variant: K_i=K_par+G*c_i

[iddo]

IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed.

What's your assumption here? That a user stores his full wallet in the cloud, including privkeys, in encrypted form? Is the worry just about deniability?

As Pieter said in post #103, the encrypted wallet.dat should only encrypt the privkeys. We currently advise users to add another layer of symmetric encryption (e.g. with GPG or 7zip) before storing the wallet on the cloud, because of privacy concerns (otherwise your total wallet balance and addresses will be exposed). Still for example after the wallet non-encryption bug was discovered (CVE-2011-4447), IIRC there were claims of stolen coins from wallet.dat files that were stored on dropbox (possibly by dropbox administrators), etc., meaning that users do store wallet.dat files in public places, without the advised extra layer of encryption.

My suggestion is to have deniable encryption in order to incentivize users to be prudent, by offering them a desirable feature which would be built into the client.

[iddo]

There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?

[thanke]

There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?

BIP 32 is doing this just fine, no extra hash required because x is already a hash of the chaincode:
HMAC(cpar,i). This was just a thought experiment. If x was cpar+i for instance then we couldn't prove the link by revealing cpar+i without revealing cpar and de-anonymizing all siblings. If x was cpar+i you could still come up with a zero-knowledge proof that you know x. If anyone knows x with K'=x*K then we can be convinced that K' was derived from K. Again, just thought experiments.

[iddo]

There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?

BIP 32 is doing this just fine, no extra hash required because x is already a hash of the chaincode:
HMAC(cpar,i). This was just a thought experiment. If x was cpar+i for instance then we couldn't prove the link by revealing cpar+i without revealing cpar and de-anonymizing all siblings. If x was cpar+i you could still come up with a zero-knowledge proof that you know x. If anyone knows x with K'=x*K then we can be convinced that K' was derived from K. Again, just thought experiments.

Yes obviously c_par+i is terrible, not only because revealing/leakage of c_i implies leakage of its parent c_par, but also simply because the privkeys wouldn't be pseudorandom, so we could attack such a scheme by knowing just the public signatures (transactions).

But HMAC(cpar,i) isn't BIP32, it's your scheme where the keys and chaincodes are unlinked. With BIP32, even if you discover from K_par,K_i the x that solves K_i=x*K_par you still haven't obtained the chaincode, only I_L. With your scheme, if you discover x then you do obtain the chaincode, but since discovering x is ECDLP, we're still safe.

A property that (seemingly) hasn't been discussed is the provability of the link. You want to be able to prove that a given child belongs to a give parent, without de-anonymizing the other children (the siblings), i.e. without revealing the chaincode. In current BIP 32 this can be done by revealing I_L. As you note, I_L is already a "second hash".

Right, BIP32 allows us to have this property.
So you're saying that if we wish to get this property with your scheme, we will have to use the extra hash i.e. K_i=hash2(c_i)*K_par, to prove that a child belongs to a parent by revealing hash2(c_i) ?
I'm not sure what the use case would be, and maybe the usefulness is only in terms of efficiency (instead of signing messages with k_par and k_i to prove that you own K_par and K_i) ?