Bitcoin Forum

Douglas Stebila and I recently posted a new paper on hierarchical deterministic wallets:
http://eprint.iacr.org/2014/998
(To appear in Financial Cryptography 2015.)

Custom summary for bitcointalk.org

---

As observed by Vitalik (http://bitcoinmagazine.com/8396/deterministic-wallets-advantages-flaw/) and many others, it is possible to recover the master private key of a BIP32-compliant wallet from the mater public key and any (non-hardened) child private key.  From what I gather, many people think that this vulnerability is unavoidable.  However, we came up with a HD wallet that is secure even if up to m-1 child private keys are leaked at a cost of storing m master public keys, for any choice of m.

How it works:
Instead of one master private and public key we have m master private keys d₁,...,d_m and public keys Q₁,...,Q_m.  (The master private keys can be derived deterministically, so there's no need to store all m of them, but the master public keys must be stored explicitly.)  The ith child public key is a linear combination of the Q_i where the coefficients are determined by the hash of i (possibly concatenated with some seed, which may or may not include wallet-specific info such as the Q_i.)  The ith child private key is derived similarly from the d_i.

Security:
Anyone who can recover all m of the master private keys---even with knowledge of up to m-1 master or child private keys---can also solve the so-called "one more" discrete log problem.  Since that problem is believed to be intractable, so too must be the task of breaking our wallet.  See the paper for further details and caveats.

At an intuitive level, an adversary who learns any one master or child private key has learned only a linear combination of the m master private keys, which reduces the dimension of the space of all possible master private key combinations by at most one, and so m such keys are required to break the wallet.

Fallout:
Admittedly, this is not an earth-shattering discovery.  But it does enable a combined treasurer-auditor use case that is impossible with BIP32 wallets:

Auditor:  A company could reveal its master public key to auditors or regulators, thereby allowing for extremely detailed oversight with near-negligible overhead costs.
Treasurer:  The treasurer of a large company could create child key pairs for each department within the company, allowing each department head to control its budget without granting him/her access to the funds allocated to other departments.

With BIP32 wallets, a collusion between the auditor and a department manager could run off with all the company’s funds.  Our new HD wallet eliminates this vulnerability provided that the number m of master keys exceeds the number t of departments in the company.

Thanks for your attention.  Cheers.
-Gus Gutoski

This is explicitly called out in the specification, it is not folkore or a revelation. :)

Very interesting observation!

Though it's arguably more fragile in one sense that you may think you can release a private key securely but really you cannot because if you leak too much you are broken. It's difficult to write software which will only act a small non-zero number of times e.g. it crashes and forgets that it's already performed one disclosure, certainly the user cannot be counted on to remember such things.  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.

Your security argument rests on 1MDLP, but we actually use these keys in the context of ECDSA. Inability to solve the DLP (or 1MDLP) does not provably result in the security of ECDSA, and ECDSA reveals another (random) linear relationship with the keys in question; it's concealable that it could undermine the security of the scheme. For example, imagine if the nonce were secrete but constant.  Off the cuff, I do not see a reason that this is problematic for the security of your construction. Though in an abundance of caution we specifically constructed BIP32 to avoid constant any linear relationship out of concern for potential interactions with ECDSA which we were unable to prove did not exist.

https://bitcointalk.org/index.php?topic=819424.0

related proposal

Would your method be compromised if only, say, m/0/0 and m/1/0 private keys were known?

Perhaps the 1 leaked key protected methodology would be good if we could separate each used key below it's own path (not sharing the same direct parent with any other generated key)

I'm a bit confused in your paper, in the description of your wallet, because d is used to represent master private keys and child private keys.

I can't figure out if this is a new hd wallet or just lots of old hd wallets that would each, individually, be susceptible to the same attacks that you are trying to avoid?

EDIT sorry, I've got bad eyesight, I missed the hat on top of the letter, I'll read it again and see if I can understand it :)

Excellent idea!  People have asked about this kind
of thing in the past.  The use-case is really important
for the future of Bitcoin.

Can you please help me understand how this would be useful in practice? The amount of tolerated leak is linear in the size of the scriptpubkey. Just giving a party random address also achieves that. Using the homomorphic derivation is attractive for cases where the linear size is not acceptable.

Clearly, the use cases presented in the paper are compelling.

I don't fully understand your question due to a lack
of technical expertise, but it sounds like
you are saying the leakage would still be too great
to be practical?

The paper says:


My understanding was that there was until now,
zero tolerance of any leakage of private keys
in an HD.  If that is incorrect or there
are better ways to do it, please clarify.

That is not correct in all scenarios.  Private keys can either be hardened or normal.  Hardened private keys can not leak the parent key.    Even with unhardened private keys the leak of the key alone is insufficient to leak the parent as well.  You need to leak a child private key AND parent public key to compromise the parent private key.

hi DT!

Yes, I was aware of that; I did read the paper and
this appears to be relevant:

That isn't as large of a limitation as you might be thinking, at least not in most applications.  The hardened keys are used to produce the major "branches" and then unhardened keys are used to leafs.  There aren't many scenarios where you would compromise just a few but not too many of the leaf keys AND not also compromise the parent (branch) key at the same time.   Still the OP is an interesting academic concept but I agree with gmaxwell in that scenarios where it would provide additional security is limited.

Thanks for explanation... I get it and agree.

I jumped the gun and was thinking it would
protect a lot more leakage.  My initial comment
was referring to the fact that people have
expressed desire for higher security when
sharing a public key for auditing purposes.

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?

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

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.

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.

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

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.

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

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


I've copy and pasted above from section 4 of the paper but some of the symbols have changed so you might have to refer to the original paper
Anyway I don't really understand exactly how this m-tuple is derived, can someone write out an explicit example


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.

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.

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

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<m linear equations in m unknowns.  (See "Remark 1" at the end of the paper.)

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.

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

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.

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.

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.

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.

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://bitcointalk.org/index.php?topic=19137.0), 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.

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

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.