Quote from: ggutoski on January 08, 2015, 06:13:50 PM

If you really want to give each child a,b,c,... ability to reveal up to n_a,n_b,n_c,... private keys then you need at least 1+n_a+n_b+n_c+... master private keys. This isn't a problem if you're the top-level admin because you can generate the private keys deterministically. But if you're an auditor (who is only allowed to know the master public keys and needs to store them explicitly) then you could run into an exponential blow-up of public key size: if you want each node in a k-ary tree of depth d to be able to reveal up to n keys then you need something like (kn)^O(d) master keys.

You could follow BIP32 design and derive, for each child, m different tuples of coefficients hash(chaincode,i,j)=(a_{i,j,1},a_{i,j,2},...,a_{i,j,m}) where i is the index (i.e., tree path), and j runs from 1 to m too. This way we obtain m different pubkeys Q_i_1,Q_i_2,...,Q_i_m from the m pubkeys of the parent node Q_parent_1,Q_parent_2,...,Q_parent_m, for example Q_i_1 is a linear combination of the Q_parent_i pubkeys with (a_{i,1,1},a_{i,1,2},...,a_{i,1,m}) coefficients. Similarly to BIP32, you can use hash(chaincode,i,Q_parent_j) instead of hash(chaincode,i,j) to have more entropy.

This would mean that the granularity at each branch of the HD wallet is in multiplies of m, which would be a disadvantage with small branches and large m.

But the more important thing is that in practice it probably doesn't really accomplish anything, because if there's a security breach and some privkey of node i leaks, then most probably all the m privkeys at that node i leaked along with it. You could argue e.g. that against a theoretical crypto attack that computes a privkey from the pubkey in t time, you'll need to execute an attack of mt total time instead of t time, for a complete break of the HD wallet, but that isn't really interesting.

So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine.

Quote from: gmaxwell on January 07, 2015, 12:16:29 AM

So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.

To say that public key size is the problem here seems kind of vague, I think that the main deficiency is that you need to perform m elliptic curve exponentations to derive the next pubkey, instead of a single exponentation. So I'm not sure if the tradeoff between the extra complexity versus the supposed better security makes sense (with non-hierarchical variant), it depends on whether the security improvement is significant in practical scenarios.