New HD wallet that tolerates leakage of some child private keys

[ggutoski]

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

[gmaxwell]

As observed by Vitalik and many others

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

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.

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.

[dabura667]

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)

[Crowex]

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

[jonald_fyookball]

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

[gmaxwell]

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.

[jonald_fyookball]

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:

Specifically, an organization with t
departments is safe from a collusion between the
auditor and all department managers if it uses our HD wallet with parameter
m > t

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.

[DeathAndTaxes]

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.

[jonald_fyookball]

hi DT!

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

Unfortunately, those hardened keys lack the master public key property: their
public keys cannot be generated from the master public key.

[DeathAndTaxes]

Unfortunately, those hardened keys lack the master public key property: their
public keys cannot be generated from the master public key.

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.

[jonald_fyookball]

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.

[dabura667]

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?

[jonald_fyookball]

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

[ggutoski]

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.

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.

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.

[ggutoski]

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.

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.

[dabura667]

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.

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.

[dabura667]

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.

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.

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.

[Arnab biswas]

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

[Crowex]

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

In what follows the hash function hash(i, s) 7→ (α1, . . . , αm) produces an
m-tuple of integers modulo p

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

Less-short answer: We didn't even bother to explicitly define how one generates descendant keys beyond the first level.

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

  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.

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.

[ggutoski]

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?

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.