Deterministic wallets

[grau]

I don't want to specify how wallet software should work.

OK, you do not want to specify but expect that they follow conventions.
I give up arguing for being explicit, and will also follow those conventions just as if they were specified.

[CIYAM]

I give up arguing for being explicit, and will also follow those conventions just as if they were specified.

Please don't - we really need to work together to get the conventions and specifications at least "singing from the same hymn book".

(maybe "guidelines" to go along with the specifications?)

[Pieter Wuille]

I don't want to specify how wallet software should work.

OK, you do not want to specify but expect that they follow conventions.
I give up arguing for being explicit, and will also follow those conventions just as if they were specified.

If you have a reason to deviate, do so. If you don't have a reason to deviate, don't.

I'm just saying that applications and their expectations will differ, and it is unreasonable that they will all behave in the same way to the smallest detail. And that's just fine.

I feel that how different applications deal with backups and recovery is such a detail. Perhaps it makes sense to add a section with recommendations about this, but I can't expect everyone to follow them. An application may just start with a new seed after a time and tell the user to make a new backup. It may keep track of the necessary gap to do a scanning recovery, and warn the user when some maximal configured gap is exceeded. It may rely on a local fast-accessible indexed UTXO to search a huge amount of addresses. It may automatically backup the highest used indexes to dropbox. I don't think we know the best practices here, so I don't see a reason to fix them.

[grau]

I give up arguing for being explicit, and will also follow those conventions just as if they were specified.

Please don't - we really need to work together to get the conventions and specifications at least "singing from the same hymn book".

(maybe "guidelines" to go along with the specifications?)

No worries. I am willing to comply with what is written into the proposal. I tried to include more, if not applicable for the spec, then lets add a recommendations section enumerating, that:

1. use consecutive indexes at generation
2. record highest generated index per level
3. do not use more than 3 levels
4. record time point an extend key (level) was created

Any other?

I actually implemented the spec as close as it can get here: (not yet merged to main of bits of proof):

https://github.com/bitsofproof/supernode/blob/lean/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java

[grau]

And here are the unit test cases

https://github.com/bitsofproof/supernode/blob/lean/api/src/test/resources/ExtendedKey.json

of serialization both production and test, using two hierarchy levels and indices 0x80000000, 0x80000001, 0, 1

[iddo]

Scenario is this: Server A is holding (K_par,c_par). Server B is being set-up in a different location and is supposed to hold (K_i,c_i). All chaincodes are to be kept secret by the servers holding them, i.e. c_par shall only be known to A (not B) and c_i shall only be known to A and B (no third party). It is irrelevant here who knows K_par and K_i. So B does not derive anything itself. Instead, A does the derivation of (K_i,c_i) and sends the result to B. Of course, the communication of A to B must be authenticated. The point is that on top of that at least c_i must (in the general case) be sent in encrypted form.

So in this scenario, why wouldn't you need to send c_i in encrypted form with your proposal?

In the scenario itself you always need to send c_i, and if you send c_i then it has to be encrypted. I am assuming that the scenario above has been completed and, at a later time, A wants to establish a second tree of pubkeys (for a different purpose, or update). First of all, I made a mistake in my proposal. It should be

Code:

(IL,IR) = HMAC-SHA512(cpar,i)

so neither of IL,ci=IR depends on Kpar. Let's assume multiplicative derivation, i.e. K_i=I_L*K_par.
In the above scenario I forgot to say that B knows "his" I_L, i.e. the I_L for which K_i=I_L*K_par. This implies that B knows K_par (before, I said this was irrelevant - its not). In fact, I assume K_par is allowed to be public. With this proposal, A creates a new K'_par and sends it to B, and B computes K'_i=I_L*K'_par, re-using his I_L. We do not need an encryption simply because c_i is not re-transmitted, only K'_par is. And I argue that K'_par does not need to be encrypted.

What do you mean by "A creates a new K'_par and sends it to B" ?
Do you mean that A uses c_parpar to compute HMAC-SHA512(c_parpar,i') to get I_L' and I_R' and derive K'_par from I_L' ? If so, B wouldn't have I_L' and I_R', so the encrypted I_R' has to be sent to B ? If I misunderstood then please try to explain it a bit more clearly?
Also, what you're describing isn't exactly a "use case", could you please elaborate on the practical objective that we'd achieve here?

[thanke]

Scenario is this: Server A is holding (K_par,c_par). Server B is being set-up in a different location and is supposed to hold (K_i,c_i). All chaincodes are to be kept secret by the servers holding them, i.e. c_par shall only be known to A (not B) and c_i shall only be known to A and B (no third party). It is irrelevant here who knows K_par and K_i. So B does not derive anything itself. Instead, A does the derivation of (K_i,c_i) and sends the result to B. Of course, the communication of A to B must be authenticated. The point is that on top of that at least c_i must (in the general case) be sent in encrypted form.

So in this scenario, why wouldn't you need to send c_i in encrypted form with your proposal?

In the scenario itself you always need to send c_i, and if you send c_i then it has to be encrypted. I am assuming that the scenario above has been completed and, at a later time, A wants to establish a second tree of pubkeys (for a different purpose, or update). First of all, I made a mistake in my proposal. It should be

Code:

(IL,IR) = HMAC-SHA512(cpar,i)

so neither of IL,ci=IR depends on Kpar. Let's assume multiplicative derivation, i.e. K_i=I_L*K_par.
In the above scenario I forgot to say that B knows "his" I_L, i.e. the I_L for which K_i=I_L*K_par. This implies that B knows K_par (before, I said this was irrelevant - its not). In fact, I assume K_par is allowed to be public. With this proposal, A creates a new K'_par and sends it to B, and B computes K'_i=I_L*K'_par, re-using his I_L. We do not need an encryption simply because c_i is not re-transmitted, only K'_par is. And I argue that K'_par does not need to be encrypted.

What do you mean by "A creates a new K'_par and sends it to B" ?
Do you mean that A uses c_parpar to compute HMAC-SHA512(c_parpar,i') to get I_L' and I_R' and derive K'_par from I_L' ? If so, B wouldn't have I_L' and I_R', so the encrypted I_R' has to be sent to B ? If I misunderstood then please try to explain it a bit more clearly?
Also, what you're describing isn't exactly a "use case", could you please elaborate on the practical objective that we'd achieve here?

It doesn't matter how K'_par is created by A, whether deterministically or not. The point is that B reuses the same I_L (or I'_L=I_L) to derive K'_i as he did to derive K_i.

This isn't exactly a use case, true. It is just something that is possible if I is independent of K_par. I still have to see an argument why I should depend on K_par. There may well be some arguments but I haven't seen any yet.

If you want a use case: A has (Kpar,cpar) and publishes Kpar. B instantiates itself and contacts A: "I want to be your sales agent". A increments i for the new agent, computes I = HMAC-SHA512(cpar,i), sends I to B (encrypted and authenticated communication). Now B is fully instantiated. B considers I as his random "name" that A has chosen for him. A has a table of number-name pairs (i,I). This table can be fully reconstructed from cpar. B can derive his public key K_i that he will work with by himself, from his "name" I and the public Kpar. Later in time A may come up with a new line of business, which required separate accounting. That's when A creates a new K'par (deterministally or not, as he choses). A publishes K'par. But A doesn't want to create new "names" for his sales agents. The sales agents that choose to participate in the new business line can start right away without further communication with A. They just derive their K'i from K'par and their name I.

[iddo]

This isn't exactly a use case, true. It is just something that is possible if I is independent of K_par. I still have to see an argument why I should depend on K_par. There may well be some arguments but I haven't seen any yet.

Well, one argument why we should depend on K_par is that with the updated BIP32 we allow either type-1
 or type-2 derivation from the current node.
With your proposal we will have a tree of hashchains c_i=hash(c_par,i) where you derive deterministically the keypair (k_i,K_i) from each c_i (BTW I'm not sure why you'd want to split I to I_L and I_R instead of having single 256-bits I that's used both for deriving the current keypair and the next chaincode), so indeed it gives the benefit over the OP because you can share some c_i in the middle of the hashchain with another person.
But if you unlink the chaincodes and from the keys, then you canot disallow type-2 derivation when the input to the CKD is just the pseudorandom hash value c_i, meaning that logically k_i=CKD(k_par,c_i), unless you could tag c_i somehow, or enforce the derivation type via CKD(k_par,c_par,i) as BIP32 does now, but then the property that the chaincodes and keys are unlinked becomes problematic.
In general, if the chaincodes and keys are unlinked then you could prepare an entire wallet layout starting from a master chaincode without any keys, and then for each master privkey that you plug in you would get different keys in the tree. I'm not so sure whether having the ability to do such things is a good idea.

It doesn't matter how K'_par is created by A, whether deterministically or not. The point is that B reuses the same I_L (or I'_L=I_L) to derive K'_i as he did to derive K_i.

This isn't exactly a use case, true. It is just something that is possible if I is independent of K_par. I still have to see an argument why I should depend on K_par. There may well be some arguments but I haven't seen any yet.

If you want a use case: A has (Kpar,cpar) and publishes Kpar. B instantiates itself and contacts A: "I want to be your sales agent". A increments i for the new agent, computes I = HMAC-SHA512(cpar,i), sends I to B (encrypted and authenticated communication). Now B is fully instantiated. B considers I as his random "name" that A has chosen for him. A has a table of number-name pairs (i,I). This table can be fully reconstructed from cpar. B can derive his public key K_i that he will work with by himself, from his "name" I and the public Kpar. Later in time A may come up with a new line of business, which required separate accounting. That's when A creates a new K'par (deterministally or not, as he choses). A publishes K'par. But A doesn't want to create new "names" for his sales agents. The sales agents that choose to participate in the new business line can start right away without further communication with A. They just derive their K'i from K'par and their name I.

I still don't see how exactly it could be that "A creates a new K'par" and follow the same old hashchain of chaincodes with the new K'par, since if we use (say) the multiplicative variant then there's a correspondence between the keys and chaincodes, so the chaincode that created Kpar doesn't create K'par, and if K'par is created with a different chaincode then the subsequent hashchain would also be different. I think that your proposal is simply missing the relevant details on how wallet structures can be created. If you fully specify what exactly is allowed to be created in wallet.dat, and then show how your practical use case applies, then it'd be easier for us to consider your ideas.

[Pieter Wuille]

I still don't see how exactly it could be that "A creates a new K'par" and follow the same old hashchain of chaincodes with the new K'par, since if we use (say) the multiplicative variant then there's a correspondence between the keys and chaincodes, so the chaincode that created Kpar doesn't create K'par, and if K'par is created with a different chaincode then the subsequent hashchain would also be different. I think that your proposal is simply missing the relevant details on how wallet structures can be created. If you fully specify what exactly is allowed to be created in wallet.dat, and then show how your practical use case applies, then it'd be easier for us to consider your ideas.

He wants to generate a k_par/K_par indepedently from BIP32 derivation, and "inject" it into an existing key tree, updating the keys that are derived from it, while retaining the chain codes (I think).

I'm not convinced about the use case, and IMHO allowing this overwriting of keys makes things harder to reason about. We're not explicitly depending on chain codes to be unique across keys, as far as I can tell though.

[iddo]

I still don't see how exactly it could be that "A creates a new K'par" and follow the same old hashchain of chaincodes with the new K'par, since if we use (say) the multiplicative variant then there's a correspondence between the keys and chaincodes, so the chaincode that created Kpar doesn't create K'par, and if K'par is created with a different chaincode then the subsequent hashchain would also be different. I think that your proposal is simply missing the relevant details on how wallet structures can be created. If you fully specify what exactly is allowed to be created in wallet.dat, and then show how your practical use case applies, then it'd be easier for us to consider your ideas.

He wants to generate a k_par/K_par indepedently from BIP32 derivation, and "inject" it into an existing key tree, updating the keys that are derived from it, while retaining the chain codes (I think).

I'm not convinced about the use case, and IMHO allowing this overwriting of keys makes things harder to reason about. We're not explicitly depending on chain codes to be unique across keys, as far as I can tell though.

I see, though maybe he wishes to inject the new keypair as a parallel path that would co-exist in the wallet, instead of overwriting the old keypair, meaning that all the previous keys will still be retained. In other words, we can regard this injection as creating a fresh master privkey somewhere in the middle of the tree structure (which implies that we now must backup the wallet), and use the old chaincodes with this fresh master privkey too.

[tmbp]

People are already loosing thousands of dollars by just getting their private key compromised do you really want people to be loosing tens of thousands by getting their deterministic wallet compromised? You must consider the nature of humans when introducing such technologies, even Bitcoin itself is perhaps already too chaostic and unpredictable for most people.

[iddo]

thanke, the only reason to unlink the chaincodes from the keys is to avoid the secure communication needed for sending another chaincode in the use case that you described, or do you have other use cases as well? If that's the only reason then it isn't much, as chaincode leakage without privkey leakage gives nothing to the attacker (e.g. you even said in post #76 that if chaincode is given to 3rd-party to generate new pubkeys then you don't regard the chaincode as sensitive data), and we opted to deal with possible leakage of privkeys by allowing type-1 derivation to break the homomorphism link. Anyhow, establishing secure communication to send a new chaincode in your use case isn't such a big deal, unless you demonstrate how to wrap this use case in some system that requires intensive use of re-transmiting encrypted chaincodes, or something else along these lines?

[iddo]

Another issue that's external to BIP32, but related to users shooting themselves in the foot, is how the initial entropy S can be created. Obviously, by default it's very important that S would be created from random bits, but we should consider whether to also allow users to input a string/passphrase and derive the master node from it. That implies that the user could restore his entire HD wallet via a passphrase, and advanced users could choose for example scrypt(passphrase, #iterations) as input for deriving the master node. Maybe this should be an advanced option that's hidden by default (maybe you'd even have to patch and recompile the client for it), otherwise attackers could attempt dictionary attacks and steal coins. However, if the Satoshi client won't allow this option at all then it's likely that sooner or later someone else will create a modified version of the client (similarly to the version without mandatory transaction fees) and call it "HD Brainwallet 2.0" or something, so I think that it's a good idea to consider what's the safest way to include this option in the Satoshi client. Maybe the best way is a hidden option that can be activated via a command-line argument, where the user may input a string of minimum #chars (for example 64 hex chars is the output size of sha256sum), which means that this way different users will choose different hashing algorithms (instead of using a single algorithm that the client would provide), so the attackers' task will be more difficult. Note that using the AES wallet encryption passphrase as the passphrase for deriving the master node should be highly discouraged, because attackers don't need to have access to the wallet.dat file in order to do dictionary attacks on HD wallet passphrases.

[Pieter Wuille]

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

[willphase]

People are already loosing thousands of dollars by just getting their private key compromised do you really want people to be loosing tens of thousands by getting their deterministic wallet compromised? You must consider the nature of humans when introducing such technologies, even Bitcoin itself is perhaps already too chaostic and unpredictable for most people.

people are already losing a lot of bitcoins through the misunderstanding of Change addresses, so it's a balance that has to be struck here.  I think a good solution would make it hard for people (even non-computer literate people) to lose any bitcoins by a combination of deterministic keys (to prevent loss due to change address mistakes) and mandatory secure passphrases/better UI to secure wallets.

Will

[thanke]

I still don't see how exactly it could be that "A creates a new K'par" and follow the same old hashchain of chaincodes with the new K'par, since if we use (say) the multiplicative variant then there's a correspondence between the keys and chaincodes, so the chaincode that created Kpar doesn't create K'par, and if K'par is created with a different chaincode then the subsequent hashchain would also be different. I think that your proposal is simply missing the relevant details on how wallet structures can be created. If you fully specify what exactly is allowed to be created in wallet.dat, and then show how your practical use case applies, then it'd be easier for us to consider your ideas.

He wants to generate a k_par/K_par indepedently from BIP32 derivation, and "inject" it into an existing key tree, updating the keys that are derived from it, while retaining the chain codes (I think).

I'm not convinced about the use case, and IMHO allowing this overwriting of keys makes things harder to reason about. We're not explicitly depending on chain codes to be unique across keys, as far as I can tell though.

I see, though maybe he wishes to inject the new keypair as a parallel path that would co-exist in the wallet, instead of overwriting the old keypair, meaning that all the previous keys will still be retained. In other words, we can regard this injection as creating a fresh master privkey somewhere in the middle of the tree structure (which implies that we now must backup the wallet), and use the old chaincodes with this fresh master privkey too.

Yes, exactly. The term "update" was confusing, as I didn't mean to overwrite anything. Instead, new extended keypairs (or keytriples) are to be created at all nodes. This is why details about wallet structures should not matter. As I said in #120, how to import a new extended keypair (that coincidentally shares its chaincode with an existing extended keypair) should be left out of BIP32 and its initial implementation. 

I intended to take a fresh master pubkey only at the root of the tree, but of course you can do this at any node because every node is itself a root. Whether a new backup is required depends on how the fresh master pubkey is created, something I didn't specify.

This isn't exactly a use case, true. It is just something that is possible if I is independent of K_par. I still have to see an argument why I should depend on K_par. There may well be some arguments but I haven't seen any yet.

Well, one argument why we should depend on K_par is that with the updated BIP32 we allow either type-1
 or type-2 derivation from the current node.

I don't understand.

With your proposal we will have a tree of hashchains c_i=hash(c_par,i) where you derive deterministically the keypair (k_i,K_i) from each c_i (BTW I'm not sure why you'd want to split I to I_L and I_R instead of having single 256-bits I that's used both for deriving the current keypair and the next chaincode), so indeed it gives the benefit over the OP because you can share some c_i in the middle of the hashchain with another person.

Yes, a single I would suffice.

But if you unlink the chaincodes and from the keys, then you canot disallow type-2 derivation when the input to the CKD is just the pseudorandom hash value c_i, meaning that logically k_i=CKD(k_par,c_i), unless you could tag c_i somehow, or enforce the derivation type via CKD(k_par,c_par,i) as BIP32 does now, but then the property that the chaincodes and keys are unlinked becomes problematic.

Isn't this just a notational problem in BIP32 where CKD is said to be a function of (kpar,cpar,i) while kpar is not required if the highest bit of i is 0? I'll say more about type-1 derivation in another post..

In general, if the chaincodes and keys are unlinked then you could prepare an entire wallet layout starting from a master chaincode without any keys, and then for each master privkey that you plug in you would get different keys in the tree. I'm not so sure whether having the ability to do such things is a good idea.

This is what we should discuss. I argue that its not a bad idea, so we should pave the way for it (not implement it).

thanke, the only reason to unlink the chaincodes from the keys is to avoid the secure communication needed for sending another chaincode in the use case that you described, or do you have other use cases as well?

In fact, if A publishes his new K'_par on a bulletin board then no direct communication between A and B is required at all. So maybe the advantage is better phrased like this: There is one piece of information (K'_par) required for all children B_i (agents) of A, not an individual piece (c_i,K_i) for each of them. (This is of course after initially each B_i has once received its individual c_i.) You can argue that each B_i could just be told to switch to a new subkey of his, say from K_i/1 to K_i/2, when a new business line requires separate accounting. But K_i/1 and K_i/2 have the same root owner. So this scenario would be for when a new root owner is established. Hollywood-style: mafia boss A gets "replaced" by mafia boss A', all his "agents" start working for A' without ever meeting him. Maybe you were right saying "I'm not so sure whether having the ability to do such things is a good idea." 

If that's the only reason then it isn't much, [..]

It may not be much but we can get it for free.

[iddo]

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

Nice. If I understand the proposal correctly, a particular seed that the user chooses all by himself would have a low probability to work in this scheme, so the computer will try to generate dictionary-style seeds for the user, and after less than 256 attempts on average a suitable seed will be found, and it'd have the nice checksum and variable-strength properties. BTW, if you're not convinced that scrypt is a good idea here, see casascius' 10 BTC 4 U 2 STEAL thread.

With regard to seeds for HD wallets (and elsewhere), obviously if the computer alone just generates the dictionary-style seeds then it will be a total disaster, because the attackers will also let the computer generate these seeds and thereby steal brainwallets. So the option in the Satoshi client should let the user input his my_very_long_and_secure_passphrase, and then concatenate the dictionary-style attempts to create the resulting checksum/varstrength seed. This means that the user will have to memorize the my_very_long_and_secure_passphrase+dictionary_style_postfix string if he wishes to restore his HD brainwallet from memory. This option will also take care of my previous suggestion to allow 'security through obscurity' by letting advanced users create the seed by running their secret hashing algorithm, for example scrypt(md5(md5(passphrase)), #9876 iterations) or whatever, because they could use their hashed output as the my_very_long_and_secure_passphrase input for this scheme.

I suppose that by default the Satoshi client should just create a new HD wallet (without asking the user anything) from truly random entropy, and then advise the user to encrypt and backup the wallet.dat file. I recommend that the option to create an HD brainwallet should be enabled only via an obscure command-line argument, to minimize the probability of users shooting themselves in the foot.

[thanke]

About the two derivation types: We don't really need two cases of derivation in CKD. We can use the first one (the public one) for both. Whether your derivation is secret or public depends entirely on what you do with cpar. Keep cpar secret (tie it with kpar) and your derivation is secret, make cpar public (tie it with Kpar) and your derivation is public. This matter can be left out of CKD and can be handled by the wallet.

Of course, strictly speaking you don't need chaincodes for secret derivation, they could be derived directly from kpar with something like ki=HMAC(kpar,i).

What about this: At the root node we have to initialize cpar somehow. The current spec says that kpar and cpar at the root node are both initialized simultaneously from the same seed S. Redefine the initialization of cpar to

Code:

cpar := H(kpar)

kpar is still initialized from the seed S, but cpar is now a function of kpar. Then define CKD(Kpar,cpar,i) like this:

Code:

I := HMAC(cpar,i)
c_i := H(I)
K_i := I*Kpar
return (c_i,K_i)

(Obviously, k_i = I*kpar.)

Given (k,K,c) and i, the wallet calls CKD(K,c,i) if the highest bit of i is 0, which is the "public" variant because it doesn't require k, and CKD(K,H(k),i) if the highest bit of i is 1, which is the "secret" variant because it requires k. Doesn't this look cleaner than what we have now?
Note that the "secret" variant doesn't use the c from the triple (k,K,c).

In a sense at each node we get to choose whether to use the chaincode that was given to the node from above (call it the "external" chaincode) or the "self-seeded" chaincode. The root node obviously has to be self-seeded and carries no external chaincode. Any conventional keypair can be a root, as any conventional keypair can be self-seeded. An extended keypair is a conventional one plus an external chaincode.
External chaincodes are thought of as being tied to the pubkey and are therefore used for public derivation. Self-seeded chaincodes are derived directly from the private key and are therefore used for secret derivation. Self-seeded chaincodes are not explicitly stored (so they cannot leak), they are recomputed from the private key when needed.

BTW, if the "secret" variant is the default then it should correspond to 0 as the highest bit of i.

[EDIT] After a small change to the above the root extended key (k,K,c) now is consistent with the other nodes. The root looks like it is derived from the base point with I=k, but with an unknown i and with an unknown chaincode associated with the base point.
[/EDIT]

[iddo]

thanke, let's see if I understand correctly the outlining dependencies when we compare BIP32 with your latest proposal:

BIP32 type-2 derivation:

c_i=f(K_par,c_par,i)
k_i=f(k_par,c_par,i)
K_i=f(K_par,c_par,i)

BIP32 type-1 derivation:

c_i=f(k_par,c_par,i)
k_i=f(k_par,c_par,i)
K_i=f(k_i)=f(k_par,c_par,i)

Your proposed type-2 derivation:

c_i=f(c_par,i)
k_i=f(k_par,c_i)=f(k_par,c_par,i)
K_i=f(K_par,c_i)=f(K_par,c_par,i)

Your proposed type-1 derivation:

c_i=f(k_par,i)
k_i=f(k_par,c_i)=f(k_par,i)
K_i=f(K_par,c_i)=f(k_par,i)

As we discussed in post #75 and #76, I don't like your type-1 derivation here because it doesn't depend on the additional secret chaincode (a.k.a. seed), which means that if one particular privkey leaks while the rightful owner of that privkey derived child keys via type-1, then the attacker will also know the entire sub-tree that's rooted at that particular privkey.
If you change your proposal so that type-1 derivation also depends on c_par, then the type-1 derivation will become similar to BIP32, and we will be left with considering why your type-2 derivation is supposed to be superior to BIP32 in that case.
That's probably not the only issue that should be examined, just the issue that I noticed first.

[thanke]

Nice overview about the dependencies. thanks.

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?

As we discussed in post #75 and #76, I don't like your type-1 derivation here because it doesn't depend on the additional secret chaincode (a.k.a. seed), which means that if one particular privkey leaks while the rightful owner of that privkey derived child keys via type-1, then the attacker will also know the entire sub-tree that's rooted at that particular privkey.

From you posts (including #75/76) I understand that you want each node to have a privkey and a seed (for child derivation) and they should be independent in the sense that if one leaks then not necessarily the other. For instance, you want that the owner can derive children from the seed without accessing (decrypting) the privkey. Possibly you also want it the other way around, to be able to access the privkey without decrypting the seed. So what you really want is two independent seeds at each node (one of them is the node's own privkey, lets also call also it a "seed" here). This is trivially done with my proposal for type-1. Simply interpret the k's as seeds instead of privkey (they are the same thing, just different "purposes"). A node that owns k takes HMAC(k,0) for his own privkey and HMAC(k,1) for his seed to derive his children from. Then seed and privkey are independent, at least on "their" level (without knowing k). The node can store only k; or the node can erase k after it stored privkey and seed independently according to the node's security model; or the node may never have learned k because the parent node transmitted only privkey and seed but not k.

Think of this as a tree where at each node something (the node's own privkey) branches "off to the side" and the information "branching off" is not required to go deeper down. Of course, it's still a tree. Another picture is that each node spans two levels and actually consists of a subtree a 3-node subtree  /\ where one branch ends (is a leaf) and the other possibly extends down deeper.

What this boils down to is a hierarchical PRNG of seeds. BTW, such a cryptographic structure can nicely unify type-1 and type-2 derivation because they can both directly build on it, according to the above proposals. In type-1 privkeys are actually privkeys, in type-2 privkeys are multipliers to the parents pubkey. This would leave us with only one cryptographic structure to define and reason about.