Topic: New HD wallet that tolerates leakage of some child private keys (Read 3965 times)

ggutoski>

https://gist.github.com/dabura667/875bb2c159b219c18885

What about something like this?

Using convention, 2 keys are all that is needed to prevent leakage from a nearly unlimited amount of leaked keys.

Please give me any feedback. I am currently working on implementing in Python.

The paper quite clearly claims to introduce a new hierarchical wallet. It claims to solve problems that other hierarchical wallets have.
I agree with you that the paper doesn't actually specify a hierarchical wallet.

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.

The title of the short paper says "hierarchical", but it actually only specifies the non-hierarchical variant of the OP of the 2011 thread (https://bitcointalksearch.org/topic/deterministic-wallets-19137), without chaincodes.
With an hierarchical variant you can delegate the root of a sub-tree of the wallet's hierarchy to a third party, without giving this third party access to the other branches of the tree.

I don't understand what non-hierarchical variant you are talking about? Everything in the abstract and the OP refers to a hierarchical (HD) wallet.

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.

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.


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.

It's actually okay to do this so long as your keys are truly unrelated you never reuse keys!  I ... don't know why you would ever do this! but there is some madman that appears to be doing this on the Bitcoin blockchain.

(well, okay, I can give an example of why you might do this:  If I don't have to compute kG, I can do a signing operation in under 1 microsecond, or about 100x faster.  But its still darwin award grade stupid.)

The reason I brought it up is that it just to illustrate that the reduction argument wasn't complete. It's probably not possible to make it complete given the shortcomings for provable security for ECDSA in general, I wouldn't fault your paper for it; only to note that risk isn't _completely_ eliminated by the proof.

If I understand correctly, you're worried about some problem introduced by the confluence of the facts that (i) our child private keys are constructed by linear combinations of the master private keys, and (ii) each ECDSA signature reveals a linear equation involving the private key.  But, as you say, the information revealed in an ECDSA signature is masked by the random nonce so it's hard to see how this could be a problem.  And if the nonce is "secret but constant" than you're screwed anyway.

What we do have is that recovering the wallet's signing keys without access to any signatures is as hard as the 1MDLP for elliptic curves.

Other than that, I'm not sure how to respond.  This concern could apply to any use of ECDSA in which the keys are not truly random.  I guess in order to address it one would need to prove a general reduction from cracking ECDSA with arbitrary keys to cracking ECDSA with constraints on key selection.

Thanks!  Thanks again to everyone for the feedback.  It's a shame we didn't get your feedback back when this paper was under review.  I guess in the future we should post to bitcointalk.org before submitting.

We don't even really need a hash function for generating coefficients.  All we really need is some way to map a child index to a vector of coefficients in such a way that two distinct child indices are unlikely to map to the same coefficients.  Even if the coefficients are completely predictable, an adversary still has the problem of solving a system of t
This "flat" scheme is dumb anyway.  It really only applies when the master public keys are public knowledge, since they're always needed to generate descendants.  (Previous post edited to include this fact.)  In that case, all HD wallet trees are equivalent to a single-level tree in the sense that there's no significant difference between a depth-three child m/x/y/z and a depth-one child m/(xyz) where (xyz) is some way of encoding the three indices x,y,z into a single index.  (Hence the name "flat".)  In order for a multi-level hierarchy to be functionally distinct from a single-level hierarchy you need the property that each subtree can pretend to be its own separate tree and doesn't need to know anything about its ancestors (ie. the master public keys are no longer public knowledge).  But the "flat" scheme doesn't have this property.  I shouldn't have mentioned it.

I'm not sure exactly how this scheme would work but it's also very easy to break the public key derivation property when you start using hashes for the coefficients.
It's one of those problems were, when you solve one thing you break something else.

You're right.  That was a mistake on my part.  Sorry about that.  (Unfortunately, anyone who ever reads this thread forever after now needs to skim through that piece of stupidity.  That's the problem with fora.  Grr...)

What I said works if you reveal only the public keys for M/"0", M/"1", etc but not the private keys m/"0", m/"1".  If you want a multi-level hierarchy in the treasurer use case (in which everyone in the corporate ladder gets a private key) with this wallet then I see two options:

• [This point edited a bit after posting.]  If the master public keys are public knowledge anyway then you could just implement a "flat" or "simulated" hierarchy, meaning that the key m/x/y/z is a linear combination of the original n master keys d₁,...,d_n where the coefficients are derived from the hash of (x,y,z).  Note that a total of no more than n-1 private keys can be revealed from anywhere in the hierarchy.  That might seem bad but it's still an improvement on BIP32, where any one (non-hardened) private key from anywhere in the hierarchy can be combined with the master public key to break the wallet.
  
• 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.

well I've put some reading glasses on but I'm still trying to understand a couple of things


This is a fundamental part of the wallet so it must be pretty important to define it.


How can you give someone in a department their own set of master keys so that they can derive their own private keys without giving them the ability to derive the actual master keys?
 In your example above there are n master keys and you are using the first n child keys as the "master" keys for m/"0".
So if you are giving someone the master keys to m/"0" then you are in effect giving them the ability to solve for the actual master keys. I don't understand how you get around this.

Of course these might be stupid questions because I don't fully understand your system but any help in understanding it is appreciated.

just wait and see the btc flood moving up and down..with a cup of private keys :p

tl;dr

you give the Auditor A and R, but and you give only one key per branch to each department.
 
m/0/0/0 goes to dept A
m/0/1/0 goes to dept B
m/0/2/0 goes to dept C
 
so no one else on their branches knows the private keys, as m/0/x/y is not known where x is in the range [0, 2] and y is greater than 0.
 
If I'm the Auditor and I want to audit dept C:
 
Step1: Derive first level
s0 = H(0,A)
t0 = H(0,R)
 
A0 = s0*A
R0 = t0*R
 
X0 = A0 + R0
 
Step2: Derive second level
s0,2 = H(2,A0)
t0,2 = H(2,R0)
 
A0,2 = s0,2*A0
R0,2 = t0,2*R0
 
X0,2 = A0,2 + R0,2
 
Step3: Derive third level
s0,2,0 = H(0,A0,2)
t0,2,0 = H(0,R0,2)
 
A0,2,0 = s0,2,0*A0,2
R0,2,0 = t0,2,0*R0,2
 
X0,2,0 = A0,2,0 + R0,2,0
 
 
So A0,2,0 with R0,2,0 would be dept C's MPK used to generate keys below it. Also, Auditor can generate too... but knowing A, R, A0,2,0, R0,2,0, a0,2,0, and r0,2,0 should not allow the colluders to solve for r0,2, a0,2, a or r... at least I think so...
 
That is what I am wondering...
 
As long as direct parents with multiple (actually used) children never occur, it should be fine... I think.

Did you read the thread I linked? A generation methodology is written there.

Short answer: Every key, no matter where in the hierarchy, is ultimately a linear combination of the m master keys.  Thus, a total of m keys gathered from anywhere in the hierarchy is enough to break the wallet.

Less-short answer: We didn't even bother to explicitly define how one generates descendant keys beyond the first level.  One straightforward way to do it is as follows.  (m is overloaded; let n be the number of master keys.)  The first n child keys m/0 through m/n-1 are designated as the "master" keys for m/"0", the subsequent n child keys m/n through m/2n-1 are "master" keys for m/"1" and so on recursively.  So, for example, m/"0"/0 and m/"1"/0 are both linear combinations of the original n master keys d₁,...,d_n.

Thanks everyone for the comments.  It's great to receive such high quality feedback so promptly!  It's easier for me to post responses one at a time.  Here goes.


I certainly agree that

• You would need to be very careful applying this scheme for the purpose of fault tolerance.
• The wallet's utility is limited by the fact that you need to commit at the wallet's inception to a maximum amount of leak you're willing to tolerate over the life of the wallet.

But at the very least, you could protect against a one-off, black-swan event that leaks only a fixed number of keys.  It forces an attacker to compromise a bunch of keys---not just one.

Don't forget that there could be other uses of this wallet aside from fault tolerance (which admittedly isn't a killer app).  The treasurer-auditor is one, but I couldn't think of any others.

I'll reply to the second part of your comment later.  Cheers.

if they can expose the 'grand master' private key then they could ?

Question:

If one leak can be tolerated, why not just specify that the final branch should only use 0 as it's index. This way no two keys of the same direct parent are ever generated.

Ex.
Currently, wallet generation works like:
m/0'/0/0
m/0'/0/1
m/0'/0/2

m/0'/1/0
m/0'/1/1
m/0'/1/2

But if we can tolerate one leak per direct parent leak, why not?:
m/0/0/0/0
m/0/0/1/0
m/0/0/2/0

m/0/1/0/0
m/0/1/1/0
m/0/1/2/0

How could someone with M collude with anyone with two private keys if all private keys are of separate direct parents?