Topic: Deterministic wallets - page 7. (Read 48413 times)

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.


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?

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.

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.

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.


You mean the one of #180?


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.

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

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

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?


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.

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?



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.

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

BIP32 type-2 derivation:

BIP32 type-1 derivation:

Your proposed type-2 derivation:

Your proposed type-1 derivation:

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.

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


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

(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]

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.

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.


I don't understand.


Yes, a single I would suffice.


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


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


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


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

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

@iddo: have a look at https://bitcointalksearch.org/topic/self-descriptive-strengthened-keying-a-standard-for-deriving-keys-from-seeds-102349

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.

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?

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.

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.

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.