Post
Topic
Board Development & Technical Discussion
Re: New HD wallet that tolerates leakage of some child private keys
by
iddo
on 29/01/2015, 18:57:01 UTC
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.
You use multi-exp which is not N times slower, and wnaf with some big tables on each of your points, so it's only a couple adds even if your coefficients are big. libsecp256k1 on a fast laptop does something like 70k ecdsa verifies per second, and that involves a multiexp on two points (and a number of other expensive operations: a modinv for s and a sqrt to recover the pubkey). So, I don't see why you'd consider that an issue even with hundreds of points.  The reason I cited size is that the advantage of the homomorphic derivation over independent keys at all is size, and having to grow the pubkey linearly in use (to be secure in the worst case) erodes that improvement.

Hmm wnaf="window non-adjacent form", some more efficient representation it seems, I had to google that... I wasn't aware of these fast multi-exp methods, cool.

I'm trying to see if I understand why you say that the pubkey size needs to grow: with an efficient multi-exp as you suggest, we can for example extend BIP32 to make a new child node in the tree hierarchy so that the branch that starts at this child is a non-hierarchical variant with secret sharing of m keys, so that if one (or several) privkeys leak in this branch then all the other privkeys are still secure. But for this we'll need to store m pubkeys at this new child node, which implies the size growth? That's the idea? Maybe that's still a nice extension, because it'd be optional, and even if you prune these m pubkeys they can still be re-derived later from the master privkey, just like non-homomorphic type-1 "subaccounts" can be re-derived from the master privkey.