Deterministic wallets

[thanke]

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

Yes, if we did c_i=HMAC(cpar,i) then it would be advisable to do K_i=H(c_i)*Kpar instead of K_i=c_i*Kpar. "Proving the link" between K_par and K_i is a different thing (and might have a different purpose) than proving ownership of either of the privkeys. It proves that Kpar and K_i have the same owner, not that we are the owner. It's a feature (don't know a use case yet) that you don't need the privkeys for that. As you said, the required information is H(c_i) resp. I_L.

[1714057719]

1714057719

[1714057719]

1714057719

[1714057719]

1714057719

[thanke]

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

I am not convinced that we need a public derivation after a secret one. You are citing #122 for a use case:

it could give flexibility with scenarios that ErebusBat mentioned, something like person A giving person B that he trusts the ability to derive a branch (with privkeys) in his wallet, and then person B wishes to give an untrusted person C the ability to derive pubkeys in a sub-branch, so to enhance security he can break the homomophism link by doing type-1 derivation (person B couldn't have done the type-1 derivation if it was only possible at depth=1 of the "subaccounts", because he's not trustworthy enough to have access to that depth, and besides keeping the layout of extending the particular branch instead of starting a new subaccount could be useful for accounting and so on). Probably there would be more interesting use cases than this one, that I haven't thought of.

"Giving B the ability to derive a branch [by himself, on the fly] with privkeys" with type-2 is equivalent to handing A's privkey to B. Trusting someone should never go as far as handing over one's own privkey. That's not necessary either. Your case should be handled with type-1, giving B one derived privkey from which he can further derive whatever he wants. Seems to me an all-type-1 scenario, not a mixed one.

After all, I'm not convinced that the two derivation types should be mixed in one tree. It complicates the matter of backup and encryption of chaincodes vs export of privkeys that you brought up in recent posts. Why not separate them:

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i). Then the hierarchy is trivially possible without extended keys, without keeping track of chaincodes, etc. Secret derivation doesn't need to be part of BIP 32, whose focus is _hierarchical_ derivation, because the hierarchical property is trivial here.

2.) Do public derivation as before.

If you still want to mix them, and probably type-2 after type-1 is the only order that you need, then you can still turn a privkey into an extended one by self-seeding it: kpar -> (kpar,cpar=H(kpar)) and starting your type-2 derivation from there.

Any use case that is not covered?

About encryption of chaincodes (in type-2):
Since chaincodes are generally stored unencrypted, can the wallet tag each key that was type-2-derived and forbid export of its privkey?

[iddo]

I am not convinced that we need a public derivation after a secret one. You are citing #122 for a use case:

it could give flexibility with scenarios that ErebusBat mentioned, something like person A giving person B that he trusts the ability to derive a branch (with privkeys) in his wallet, and then person B wishes to give an untrusted person C the ability to derive pubkeys in a sub-branch, so to enhance security he can break the homomophism link by doing type-1 derivation (person B couldn't have done the type-1 derivation if it was only possible at depth=1 of the "subaccounts", because he's not trustworthy enough to have access to that depth, and besides keeping the layout of extending the particular branch instead of starting a new subaccount could be useful for accounting and so on). Probably there would be more interesting use cases than this one, that I haven't thought of.

"Giving B the ability to derive a branch [by himself, on the fly] with privkeys" with type-2 is equivalent to handing A's privkey to B. Trusting someone should never go as far as handing over one's own privkey.

There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.

That's not necessary either. Your case should be handled with type-1, giving B one derived privkey from which he can further derive whatever he wants.

Huh? Isn't that exactly the scenario that's discussed in post #122 ? And I tried to explain in post #122 why it can be useful that we don't confine ourselves to a wallet layout that allows type-1 derivations only from the (depth 0) master node to the (depth 1) subaccounts.

BTW, another reason not to confine the wallet layout is plausible deniability, meaning that when you reveal your decoy subwallet that you created via deniable encryption, it can have the same structure as the full wallet, i.e. the decoy wallet will have type-1 subaccounts of its own.

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i).

As mentioned, I don't like this idea because it violates property (2) of post #181, which would mean that if one particular privkey leaks then its entire subtree immediately leaks as well. This would make one aspect of HD wallets significantly less secure than the currently used random-independent wallets.

[thanke]

There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.

There is no type-2 derivation needed at all here, is there? Or you mean to divide your hot storage into hot stored privkeys and even hotter watch only wallets?

Do you agree that type-1 after type-2 is meaningless? I understand type-2 after type-1 will occur because type-1 usually happens from depth 0 to depth 1.

And I tried to explain in post #122 why it can be useful that we don't confine ourselves to a wallet layout that allows type-1 derivations only from the (depth 0) master node to the (depth 1) subaccounts.

That we don't confine? You wrote in #122:

As discussed, it's important to do the secret type-1 derivation from the master node (depth 0) to the subaccounts (depth 1), since if the master node leaks then the entire wallet leaks. So the derivation from depth 0 to depth 1 should be type-1 by default, and maybe if you wish to be extra safe (about preventing people from shooting themselves in the foot) then you should specify that type-2 derivation from depth 0 to depth 1 isn't allowed according to the BIP32 standard, and enforce that in the Satoshi client. BTW, with the updated BIP32, I guess that there's no need to save the initial entropy S in wallet.dat ?

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i).

As mentioned, I don't like this idea because it violates property (2) of post #181, which would mean that if one particular privkey leaks then its entire subtree immediately leaks as well. This would make one aspect of HD wallets significantly less secure than the currently used random-independent wallets.

Ok, got that.

[iddo]

There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.

There is no type-2 derivation needed at all here, is there? Or you mean to divide your hot storage into hot stored privkeys and even hotter watch only wallets?

There is. The default should always be type-2, since this way the user can have the client generate new receiving addresses (hashed pubkeys) for him, without decrypting his wallet in order to access his privkeys, and that's a safer behavior because users should access their privkeys only when it is absolutely needed. An important special case of receiving addresses is the addresses where the coin change goes to (see the internal keychain of BIP32).
Also, in the scenario of post #122 there's person C who is only allowed to generate pubkeys via type-2 in the subtree, for purposes like the ones described by ErebusBat in post #101

Do you agree that type-1 after type-2 is meaningless?

No, I don't. The idea of the "subaccounts" wallet layout is that it would be nice for users to have separate subtrees of unrelated operations. For example, one subaccount for personal finances and one subaccount for business expenditures/revenues. Now suppose that your "personal finances" subaccount becomes highly valuable because you received some large BTC payments there, and therefore you would like to separate this subaccount further, into hot storage and cold storage parts. You can do that via type-1 after type-2, so IMHO it's not meaningless. Of course, you could just start a whole new subaccount at depth 1 for that hot storage subtree that you wanted, but you would miss out on the potential "hierarchical" possibilities which some people could find useful in the way that they like to organize things. Moreover, for doing type-1 derivation at a node somewhere deep in the tree structure you only need to access the privkey of that particular node, rather than the privkey of the master node at depth 0, so this might be more secure (though not necessarily).
Another reason for type-1 after type-2 is the example with persons A,B,C in post #122
And maybe another reason is decoy subwallet for deniable encryption that starts at a node that's deeper than depth 1

That we don't confine? You wrote in #122:

As discussed, it's important to do the secret type-1 derivation from the master node (depth 0) to the subaccounts (depth 1), since if the master node leaks then the entire wallet leaks. So the derivation from depth 0 to depth 1 should be type-1 by default, and maybe if you wish to be extra safe (about preventing people from shooting themselves in the foot) then you should specify that type-2 derivation from depth 0 to depth 1 isn't allowed according to the BIP32 standard, and enforce that in the Satoshi client.

Yes, the confined version refers to posts #105 and #106, and the fully unconfined version is what BIP32 allows now. It's true that in post #122 I suggested to confine the current BIP32 a little bit by only allowing type-1 derivations from depth 0 to depth 1, so that (alternative) clients who state that they support BIP32 will have to disallow their users to shoot themselves in the foot. I think that we all agree that the Satoshi client should have type-1 from depth 0 to depth 1 by default, but perhaps we don't agree on whether type-2 from depth 0 to depth 1 should be strictly forbidden or not.

[Pieter Wuille]

Hey iddo & thanke,

I love how thoroughly you've been discussing this, though I must admit I haven't read the through entire discussion.

I've updated the specification to use addition instead of multiplication, but now I'd like to make the BIP32 specification final soon.

So my questions are:

• Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?
• Is there a reason to disallow secret derivation after public derivation?

If not, I'd like the current version to be final.

Grau: The thread has progressed quite a bit since your comment, but I agree it makes sense to have a set of "guidelines for wallet behaviour" that will make working with these wallets easier, though in no way required.

[iddo]

Hello Pieter,

• Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?

The supposed use case is described in post #167,#172,#176 (edit: to be self-contained here, the use case is that A gives B some pubkey and the corresponding chaincode so that B could derive the subsequent pubkeys via type-2, then A creates a new keypair and gives the new pubkey to B, to be used with the same old chaincode, therefore there's no need to send a new chaincode via eavesdropping-resistant communication, but the communication still has to be authenticated otherwise anyone could impersonate A). I personally don't think that this use case resembles something that would arise frequently in practice, but even if thanke or anyone disagrees with my assessment, the following two issues remain: (1) we can support pretty much the same exact use case with BIP32, just with one extra session of secure communication between the two parties, in which a new chaincode is sent, and (2) so far we haven't come up with a way to achieve thanke's goal without losing other properties that are more desirable (except maybe if we bloat the wallet with two separate chaincodes for each key), namely type-1/type-2 mixing and the necessity to know the chaincode in addition to the privkey in order to derive its subtree.

It seems to me that the issues that thanke raised proved to be be a good sanity check that shows that the BIP32 design is good. Maybe thanke could improve on his ideas, but even if he does, the use case seems rather insignificant as far as I can see, and I believe that it's more important to finalize BIP32 as soon as possible.

• Is there a reason to disallow secret derivation after public derivation?

IMHO absolutely not, because I see practical use cases for doing it (posts #122, #203, #205), and I don't see any reason to disallow it.


Few last things before you finalize BIP32: If I understand correctly, the length extension attack on SHA2 is irrelevant here, because of the HMAC ? It could be an interesting idea to replace SHA2 with SHA3 anyway, depending on who you believe (link). And regarding the initial seed, I suppose that you could specify that the maximal entropy that makes sense is 512 bits.

[leijurv]

Wouldn't it just be simpler to add the base point incrementally? Why not just start out with a private and public key, store the private one securely, then just keep on adding the base point to the public key to get new addresses.

[iddo]

Wouldn't it just be simpler to add the base point incrementally? Why not just start out with a private and public key, store the private one securely, then just keep on adding the base point to the public key to get new addresses.

Are you suggesting k_i=k_par+1, K_i=K_par+G ?
Then the keygen isn't pseudorandom (post #62), if one privkey leaks then the entire wallet immediately leaks too, and there's no hierarchical derivation.

[leijurv]

Wouldn't it just be simpler to add the base point incrementally? Why not just start out with a private and public key, store the private one securely, then just keep on adding the base point to the public key to get new addresses.

Are you suggesting k_i=k_par+1, K_i=K_par+G ?
Then the keygen isn't pseudorandom (post #62), if one privkey leaks then the entire wallet immediately leaks too, and there's no hierarchical derivation.

Ah. I see. Nevermind what I said.

[thanke]

I've updated the specification to use addition instead of multiplication, but now I'd like to make the BIP32 specification final soon.

A few remarks before finalization, taking into account and drawing from the long discussion with iddo:

1. Can we reserve more than one bit of the number i for different kind of derivations, not only the highest bit? This would allow addition other kinds of derivations or tweaks of existing ones in the future.

2. Additive vs multiplicative: I don't know what your status is regarding constant-time implementations. But unless timing attacks discredit the multiplicative variant, I would stay with it because of the issue raised in #155. Note that #155 is a non-issue as long as you can guarantee that no I_L is ever reused. If you can't guarantee that, in particular if you wanted to allow the re-use of chaincodes, then multiplicative would be mandatory.

3. I am having an issue with the type-1 derivation. In current BIP 32 both types of derivation first produce an I_L in their own way and then set k_i := I_L * k_par (or + instead of *). For type-1 I_L depends on k_par. Isn't it cleaner for type-1 if k_i is the direct output of a HMAC? Why the additional multiplication with k_par? This is unnecessarily complicated compared to setting (k_i,c_i) := HMAC(kpar,cpar,i). iddo phrased the desired property for type-1: "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". It is counter-intuitive to this property that a number I_L with k_i = I_L * k_par is even computed. Besides k_i and k_par, I_L is one more (unnecessary) thing that an implementation has to prevent from being swapped out to disk.

4. A further suggestion for type-1 on top of 3.: (k_i,c_i) := HMAC(S,i) where S := HMAC(kpar,cpar). This achieves that k_i=func(kpar,cpar,i) as before. Plus it has the following properties:
- storing S there is no need to decrypt kpar when deriving children (the new advantage of this)
- children cannot be derived from kpar alone (iddo insisted on this property)
- children cannot be derived from cpar alone (we assume cpar is stored unencrypted)
Storing S is of course optional. The common (default) use would be just to recompute it each time.

5. It is certainly possible to do everything with HMAC-SHA256 alone. For instance, if you need two values like (I_L,I_R) you can do I_L=HMAC(secret,0) and I_L=HMAC(secret,1). The question is, does it reduce dependencies of the code, code review, etc. to be worthwhile? Or does it matter here that SHA256 has by now become the best-tested hash function in the world?     

6. BIP 32 should, for each derivation type, explicitly list all properties that it claims to achieve. So that wallet implementers can rely on these properties instead of digging into the details of the definitions. 

7. I understand that it is not the concern of BIP 32 to specify how clients handle extended pubkeys. However, since this is important for security there should be some guidelines, possibly in a separate document. For example, I am thinking of an "export bit" for extended keys. A type-2 derived extended key would get this bit set for lifetime, and it would prohibit the export of its privkey.

• Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?

The supposed use case is described in post #167,#172,#176 (edit: to be self-contained here, the use case is that A gives B some pubkey and the corresponding chaincode so that B could derive the subsequent pubkeys via type-2, then A creates a new keypair and gives the new pubkey to B, to be used with the same old chaincode, therefore there's no need to send a new chaincode via eavesdropping-resistant communication, but the communication still has to be authenticated otherwise anyone could impersonate A).

Let me elaborate on this use case. Think of many B's, for example A is a telcom corp and the B's are millions of dealers in every village on the planet. Each B knows its I_L which is considered as B's random name, issued by A, used to identify B. Now if A publishing a (signed) new root pubkey, this is a single, identical piece of information required by all B's. No individual piece of information is required to be exchanged with each B. The scenario is mainly intended for when the new root pubkey is completely unrelated to the old root pubkey, for example if a new owner takes over A. Think of A's root pubkey being published in a certificate of some PKI. Then each B can download it from keyservers. Regardless of encryption, this is a significantly different kind of communication than of each node in the tree getting updated from its parent.

After all, I am still in favor of type-2 in the form of (I_L,I_R) := HMAC(c_par,i), k_i := I_L*k_par, c_i := I_R. The two reasons are: 1) it allows something new without breaking anything old, 2) it simplifies the definition.

• Is there a reason to disallow secret derivation after public derivation?

IMHO absolutely not, because I see practical use cases for doing it (posts #122, #203, #205), and I don't see any reason to disallow it.

I think iddo is right. Secret derivation after public derivation allows a wallet implementation to be absolutely strict about the export bit. Because if the user desires to export the privkey of a type-2 derived extended key, then the wallet would just do a secret derivation and export the privkey of the result of that.

[iddo]

• Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?

The supposed use case is described in post #167,#172,#176 (edit: to be self-contained here, the use case is that A gives B some pubkey and the corresponding chaincode so that B could derive the subsequent pubkeys via type-2, then A creates a new keypair and gives the new pubkey to B, to be used with the same old chaincode, therefore there's no need to send a new chaincode via eavesdropping-resistant communication, but the communication still has to be authenticated otherwise anyone could impersonate A).

Let me elaborate on this use case. Think of many B's, for example A is a telcom corp and the B's are millions of dealers in every village on the planet. Each B knows its I_L which is considered as B's random name, issued by A, used to identify B. Now if A publishing a (signed) new root pubkey, this is a single, identical piece of information required by all B's. No individual piece of information is required to be exchanged with each B. The scenario is mainly intended for when the new root pubkey is completely unrelated to the old root pubkey, for example if a new owner takes over A. Think of A's root pubkey being published in a certificate of some PKI. Then each B can download it from keyservers. Regardless of encryption, this is a significantly different kind of communication than of each node in the tree getting updated from its parent.

That could indeed be nice, but still it's probably not a big deal if A also creates a new root chaincode and sends it to all the B's, especially if this root replacement would typically be a one-time important event, as opposed to frequent events. Also, if A and the B's knew in advance that they would need to support this kind of secure communication, then they can use something like attribute based encryption, and thereby have a solution which is completely external to BIP32 and achieves the same properties that you seek, and it's also more flexible because it could be used by A and the B's to exchange other kinds of data instead of just the chaincode.

And I'm not so sure that the properties that you seek come without risks: it appears that in the scenario that you described the stakes are raised, in the sense that if an attacker succeeds in forging A's signature for the root pubkey, then the attacker can cause huge damage with just one forged signature.

After all, I am still in favor of type-2 in the form of (I_L,I_R) := HMAC(c_par,i), k_i := I_L*k_par, c_i := I_R. The two reasons are: 1) it allows something new without breaking anything old, 2) it simplifies the definition.

Doesn't it break type-1 derivations?

Edit: OK, after looking at your (3) and (4) above, I see that you don't break type-1 derivation, you just break the property that'd have the same old chaincodes after replacing the root keypair, because the type-1 derivations will result in new chaincodes.

Edit2: You're hiding the output size of the HMAC there, it should be 512 bits, and if c_i=I_R is 256 bits then you feed less than optimal entropy into the hash function, so the lengths don't work as well as they could. Please write your proposed type-2 HMAC derivation more clearly?

Edit3: I mentioned in post #123 that we possibly do gain more security when the chaincodes also depend on the pubkeys, because usually just the hashed address of a pubkey is publicly known (until the coins get spent). Do you disagree?

[iddo]

2. Additive vs multiplicative: I don't know what your status is regarding constant-time implementations. But unless timing attacks discredit the multiplicative variant, I would stay with it because of the issue raised in #155. Note that #155 is a non-issue as long as you can guarantee that no I_L is ever reused. If you can't guarantee that, in particular if you wanted to allow the re-use of chaincodes, then multiplicative would be mandatory.

I haven't noticed post #155, it's difficult to keep track of all the posts in this long thread:)

Suppose that's I'm a user of BIP32 and I wish to re-use some I_L, how could I do it?
It appears that this concern is with regard to a non-issue, because we cannot reuse I_L with BIP32 ? And even if we could, we'd only lose privacy, not security.
I'm not sure whether the speedup that we obtain with the additive variant is significant. If it is, then I guess that it's better to implement the faster version, especially for heavy users such as online wallet servers, e.g. the MtGox wallet. Maybe it'd also be helpful for smartphones etc.
About side-channel attacks, I don't think that there's any significant difference between I_L*k_par and I_L+k_par ?

[thanke]

[..] it's difficult to keep track of all the posts in this long thread:)

Right  , so why again was this:

After all, I am still in favor of type-2 in the form of (I_L,I_R) := HMAC(c_par,i), k_i := I_L*k_par, c_i := I_R. The two reasons are: 1) it allows something new without breaking anything old, 2) it simplifies the definition.

Doesn't it break type-1 derivations?

Of course, type-1 would be left at (I_L,I_R) := func(cpar,kpar,i).

Suppose that's I'm a user of BIP32 and I wish to re-use some I_L, how could I do it?
It appears that this concern is with regard to a non-issue, because we cannot reuse I_L with BIP32 ? And even if we could, we'd only lose privacy, not security.
I'm not sure whether the speedup that we obtain with the additive variant is significant. If it is, then I guess that it's better to implement the faster version, especially for heavy users such as online wallet servers, e.g. the MtGox wallet. Maybe it'd also be helpful for smartphones etc.
About side-channel attacks, I don't think that there's any significant difference between I_L*k_par and I_L+k_par ?

True, it's a non-issue with BIP32 as it stands, as long as nobody tries to re-use I_L by some non-spec behaviour.
It seems the decisive argument between additive and multiplicative is protection against timing-attacks, probably Pieter can comment on that. If both can be implemented in constant time I would go with multiplicative.

[iddo]

Doesn't it break type-1 derivations?

Of course, type-1 would be left at (I_L,I_R) := func(cpar,kpar,i).

Apologies, please see my edited post there.

Suppose that's I'm a user of BIP32 and I wish to re-use some I_L, how could I do it?
It appears that this concern is with regard to a non-issue, because we cannot reuse I_L with BIP32 ? And even if we could, we'd only lose privacy, not security.
I'm not sure whether the speedup that we obtain with the additive variant is significant. If it is, then I guess that it's better to implement the faster version, especially for heavy users such as online wallet servers, e.g. the MtGox wallet. Maybe it'd also be helpful for smartphones etc.
About side-channel attacks, I don't think that there's any significant difference between I_L*k_par and I_L+k_par ?

True, it's a non-issue with BIP32 as it stands, as long as nobody tries to re-use I_L by some non-spec behaviour.
It seems the decisive argument between additive and multiplicative is protection against timing-attacks, probably Pieter can comment on that. If both can be implemented in constant time I would go with multiplicative.

If some hacker tries to re-use I_L because of some peculiar reason, and loses privacy (not security) as a result, I could live with that...
I don't think that there could be any timing attacks if the privkey derivation is just I_L*k_par or I_L+k_par, Pieter already commented on timing attacks in post #140

[iddo]

3. Isn't it cleaner for type-1 if k_i is the direct output of a HMAC?

Yes, it seems better to do k_i=I_L instead of k_i=k_par+I_L (mod n)

4. A further suggestion for type-1 on top of 3.: (k_i,c_i) := HMAC(S,i) where S := HMAC(kpar,cpar). This achieves that k_i=func(kpar,cpar,i) as before. Plus it has the following properties:
- storing S there is no need to decrypt kpar when deriving children (the new advantage of this)
- children cannot be derived from kpar alone (iddo insisted on this property)
- children cannot be derived from cpar alone (we assume cpar is stored unencrypted)
Storing S is of course optional. The common (default) use would be just to recompute it each time.

On the one hand you say that it's advantageous only if we store S, and on the other hand you recommend to recompute S each time?
Basically if we always store S then it means that when we derive a new privkey then only the child privkey (not the parent privkey) will be in memory? But the user will still need to provide his AES passphrase to encrypt the child privkey, so I don't think that we gain much with this idea?

5. It is certainly possible to do everything with HMAC-SHA256 alone. For instance, if you need two values like (I_L,I_R) you can do I_L=HMAC(secret,0) and I_L=HMAC(secret,1). The question is, does it reduce dependencies of the code, code review, etc. to be worthwhile? Or does it matter here that SHA256 has by now become the best-tested hash function in the world?     

If you have an actual reason to doubt SHA512 then I think that resorting to SHA256 shouldn't help you sleep better at nights.

[thanke]

Edit2: You're hiding the output size of the HMAC there, it should be 512 bits, and if c_i=I_R is 256 bits then you feed less than optimal entropy into the hash function, so the lengths don't work as well as they could. Please write your proposed type-2 HMAC derivation more clearly?

This was intentional, it should be trivial to fill in the corrent sizes once everything else is settled.

Edit3: I mentioned in post #123 that we possibly do gain more security when the chaincodes also depend on the pubkeys, because usually just the hashed address of a pubkey is publicly known (until the coins get spent). Do you disagree?

If Kpar is used as a parent then it will be a rather "static" object, so that Kpar will likely be used for spending during the lifetime of c_i. Plus when you compute a derived key you would need the pubkey and the chaincode at the same time anyway. Besides that, I disagree based on the general picture: pubkey=public, chaincode=anonymity, privkey=funds, which I like and find easy to sell and easy to argue about.

But your concern reveals a weakness in our general concept. That's also why I once asked if intermediate keys are to be used on the blockchain at all. Because re-using pubkeys on the blockchain is generally not encouraged. Intermediate nodes can avoid that by reserving one child key branch (i=0) for themselves and using that instead of their "own" key.

4. A further suggestion for type-1 on top of 3.: (k_i,c_i) := HMAC(S,i) where S := HMAC(kpar,cpar). This achieves that k_i=func(kpar,cpar,i) as before. Plus it has the following properties:
- storing S there is no need to decrypt kpar when deriving children (the new advantage of this)
- children cannot be derived from kpar alone (iddo insisted on this property)
- children cannot be derived from cpar alone (we assume cpar is stored unencrypted)
Storing S is of course optional. The common (default) use would be just to recompute it each time.

On the one hand you say that it's advantageous only if we store S, and on the other hand you recommend to recompute S each time?
Basically if we always store S then it means that when we derive a new privkey then only the child privkey (not the parent privkey) will be in memory? But the user will still need to provide his AES passphrase to encrypt the child privkey, so I don't think that we gain much with this idea?

Correct, that's why I wouldn't bother with storing S in the reference implementation. We also don't want to complicate extended keys further, their structure shall remain unchanged, they are just pairs.
Storing S is more of an option for an advanced user, who wants to store S on a different machine than k_par for some reason, and encrypts the k_i with a different key than he encrypts k_par with. As a result of this, parent and child funds are completely separated, whereas before parent funds required a subset (kpar) of the information needed for child funds (kpar and cpar).

If you have an actual reason to doubt SHA512 then I think that resorting to SHA256 shouldn't help you sleep better at nights.

True. What about reducing code dependencies? Is that irrelevant?

[iddo]

Edit3: I mentioned in post #123 that we possibly do gain more security when the chaincodes also depend on the pubkeys, because usually just the hashed address of a pubkey is publicly known (until the coins get spent). Do you disagree?

If Kpar is used as a parent then it will be a rather "static" object, so that Kpar will likely be used for spending during the lifetime of c_i. Plus when you compute a derived key you would need the pubkey and the chaincode at the same time anyway. Besides that, I disagree based on the general picture: pubkey=public, chaincode=anonymity, privkey=funds, which I like and find easy to sell and easy to argue about.

My only point was that usually hash(pubkey)=public rather than pubkey=public, so if for example the attacker somehow obtained the privkey k_5 and the chaincode c_1 but only knows the corresponding hash(K_1) then with your scheme he can derive c_2,c_3,c_4,c_5 and then derive the entire subtree of k_5, while with BIP32 he couldn't do it unless the coins of K_1 get spent and K_1 is revealed on the blockchain. Similarly with regard to privacy concerns, if the attacker obtained just c_1 then he could derive c_2,c_3,...,c_i until reaching two consecutive pubkeys that were revealed on the blockchain, which he would detect by testing G*f(c_i)+K_i==K_{i+1}, and therefore know the subtree of all future pubkeys from here (as opposed to BIP32 where the attacker only has c_1 and hash(K_1) and therefore cannot do anything because he cannot derive any other chaincodes).

With chaincode=anonymity I think that you meant that "leakage of a chaincode"=="loss of anonymity", not that the chaincodes themselves contribute to anonymity? The purpose of the chaincodes is hierarchical derivations, in particular the ability to delegate/share a subtree with another person, and perhaps greater security when we only need to access the relevant chaincode instead of the master seed. Are there other purposes that I'm missing?

But your concern reveals a weakness in our general concept. That's also why I once asked if intermediate keys are to be used on the blockchain at all. Because re-using pubkeys on the blockchain is generally not encouraged. Intermediate nodes can avoid that by reserving one child key branch (i=0) for themselves and using that instead of their "own" key.

Which concern?
I failed to understand how using only the keys of leaf nodes is related to not re-using keys on the blockchain. The key gets re-used when you receive more than one payment to the same receiving address, how is that related to the hierarchical layout of the wallet?

[thanke]

Edit3: I mentioned in post #123 that we possibly do gain more security when the chaincodes also depend on the pubkeys, because usually just the hashed address of a pubkey is publicly known (until the coins get spent). Do you disagree?

If Kpar is used as a parent then it will be a rather "static" object, so that Kpar will likely be used for spending during the lifetime of c_i. Plus when you compute a derived key you would need the pubkey and the chaincode at the same time anyway. Besides that, I disagree based on the general picture: pubkey=public, chaincode=anonymity, privkey=funds, which I like and find easy to sell and easy to argue about.

My only point was that usually hash(pubkey)=public rather than pubkey=public, so if for example the attacker somehow obtained the privkey k_5 and the chaincode c_1 but only knows the corresponding hash(K_1) then with your scheme he can derive c_2,c_3,c_4,c_5 and then derive the entire subtree of k_5, while with BIP32 he couldn't do it unless the coins of K_1 get spent and K_1 is revealed on the blockchain.

Yes, I understood your point. My point is that K_1 is so static (valid for the lifetime of the tree rooted at K_1) that it will get revealed on the blockchain rather soon. To avoid your attack the user would have to empty the whole subtree rooted at K_1 before ever using spending from K_1. That is not realistic.

With chaincode=anonymity I think that you meant that "leakage of a chaincode"=="loss of anonymity", not that the chaincodes themselves contribute to anonymity? The purpose of the chaincodes is hierarchical derivations, in particular the ability to delegate/share a subtree with another person, and perhaps greater security when we only need to access the relevant chaincode instead of the master seed. Are there other purposes that I'm missing?

Yes, agree, these are the purposes.

But your concern reveals a weakness in our general concept. That's also why I once asked if intermediate keys are to be used on the blockchain at all. Because re-using pubkeys on the blockchain is generally not encouraged. Intermediate nodes can avoid that by reserving one child key branch (i=0) for themselves and using that instead of their "own" key.

Which concern?
I failed to understand how using only the keys of leaf nodes is related to not re-using keys on the blockchain. The key gets re-used when you receive more than one payment to the same receiving address, how is that related to the hierarchical layout of the wallet?

Your concern about a privacy loss if cpar leaks and Kpar has been used for spending.

It is generally discouraged to receive more than one payment to the same address. One reason is anonymity (not only the receiver's, also the payer's anonymity), the other reason is that if you have two outputs to the same address, you're unlikely to spend them both at the same time, so the public key will be revealed before you get to spend the second output. I am saying that this general guideline is not compatible with using intermediate tree nodes for receiving, because an intermediate node is too "static" (it roots a subtree which probably has a significant lifetime). Only leafs are suitable "one-time objects".

[iddo]

3. Isn't it cleaner for type-1 if k_i is the direct output of a HMAC?

Yes, it seems better to do k_i=I_L instead of k_i=k_par+I_L (mod n)

If I'm guessing correctly, the reason that BIP32 specifies that for I_L>=n that resulting keypair is invalid is because we would like to have the privkey chosen uniformly at random from the valid range, so if we take I_L modulo n then the smaller privkey values will have a little bit higher probability?

Edit: instead of specifying that k_i is invalid, we could specify for example k_i=SHA256(I_L) in this case (and invoke SHA256 again if k_i is still invalid, and so on), so that we couldn't have forced gaps in the indices of the HD wallet? But if the probability is less than 1/2^127 then specifying that i is invalid is also fine.

I still agree with thanke that for type-1 derivation it makes slightly more sense to have k_i=I_L and specify that k_i is invalid if I_L=0 or I_L>=n, rather than to have k_i=k_par+I_L (mod n) and specify that k_i is invalid if I_L>=n. Note that the OP of this thread also specifies for type-1 that "Privatekey(type,n) is then simply set to H(n|S|type)". With k_i=I_L we could still treat d=k_i-k_par as the difference, so d*G+K_par is the corresponding pubkey, in case this d in needed for compatibility with type-2 in some possible context.