Topic: Deterministic wallets - page 12. (Read 48389 times)

This is a use-case that isn't captured in BIP 0032 and I think should be.

The "main" way we associate addresses with a single identity is when those addresses are used as multiple inputs in a transaction.  We certainly could form separate transactions while using a single input for each but if all those transactions are being sent to the same address at roughly the same time, the assumption could still be made that those addresses were all associated with a single identity.

With BIP 0032, the client could instead generate multiple transactions to unique derived public addresses.  This would go a significant way towards removing this particular information leak.

I agree there it's certainly neat to see the chain code derivation as separate, but without clear use case, I think it just complicates matters - both for implementations and for humans who need to learn how it works.

The current proposal has the advantage that keys always (assuming no collisions) come in triples: (privkey, pubkey, chaincode), so you only need a single identifier per key. Separating the chain code means that you need two identifiers, and both can be combined arbitrarily.

I don't really see what you mean by "to combine them into a pair, if they may get separated upon export anyway" - there's just an extended private key and an extended public key. If you never export an extended public key, the whole scheme works as a type-1 derivation. Sure, for actual leaf nodes the extended part isn't used, but as the chain code never gets revealed to the network, this shouldn't harm.

Ok, this is going to be rather vague and it remains to be discussed if you gain anything. But I'll try to make some points.

It's more modular to have a derivation of chaincodes alone. The derivation is basically a "hierarchical" pseudo random number generator. It takes a 256bit seed (the master chaincode) and produces a tree of random 256bit numbers (the derived chaincodes). This may have other uses. Such a hierarchical PRNG can be abstracted from this particular application. Why deal with pairs of a number and a curve point if you can just deal with numbers? We would get three trees of privkeys, pubkeys and random numbers, respectively. The first two trees are obtained by multiplying their root with the third tree, from the top down. I find this easier to comprehend than one tree of privkeys and one tree of pairs.

I think of a pubkey as something that can always be made public. A chaincode you may want to keep secret under certain circumstances. Philosophically, its counter-intuitive to combine them into a pair, if they may get separated upon export anyway.

Not sure if there are applications, but maybe someone wants use the same keypair with more than one chaincode. Then it seems natural to separate them. What about using the same chaincode tree with more than one master keypair? If chaincodes are to be kept secret then pushing the chaincodes to all sub-level entities becomes an issue (=non-trivial work). Suppose the root entity wants to update its keypair. Having them separated there is no need to re-distribute chaincodes. Just publish the new master pubkey and the entities on sub-levels can recursively update their pubkeys (level by level).

SHA256 is already used. Re-using it instead of SHA512 is one less primitive and less code to rely on.

If you're not interested in using any of the features of the type-2 derivation, consider the extended public key the same way you'd consider a private key. It is not observable by the network, so if you don't reveal it, it is yours alone. This essentially turns the scheme in a type-1 derivation (you derive extended privkey from extended privkey).

What do you gain by not using all available data? I consider using one 512-bit hash much more elegant than doing several 256-bit hashes.

I would imagine this is the case for any website that needs the ability to generate new 2nd-level codes on the fly, since you wouldn't want to put the private keys on a public-facing server, such as if a public donation page handed out unique extended public keys for improved anonymity.

We only need a key hierarchy as in BIP32 (chaincodes on >=two levels) if we are required to derive 2nd-level chaincodes from 1st-level chaincodes because, for some reason, it is infeasible to derive 2nd-level chaincodes from 1st-level privkeys. To make it clear that we do, let's add this to your example:

• your withdrawals shall all go to savings addresses for which you will not want to access the privkey (1st-level) for a certain time frame (say years)
• within that timeframe you expect to sign up with different exchanges, each of which you want to equip with its own pubkey and chaincode (2nd-level)
  

Now a BIP32 specific question:
Why are the child chaincodes derived from both the parent pubkey and the parent chaincode rather than just from the parent chaincode alone? What about this derivation:
K_n:=H(c_par||n)*K_par
c_n:=H(H(c_par||n))
where H is some cryptographic hash. Looks easier to me and doesn't require 512 bit digests. Am I missing some point?

Another use case for key hierarchies is shopping sites. When I create an account on Bitmit they should assign me an extended public key that my client saves in order to create all future payment addresses. This provides two advantages:

Security: As long as one does not go undetected during the initial account setup, a MITM attack can not redirect payments to the attacker's addresses since my client already knows where to send payments.

Anonymity: To the extent possible I don't want to use outputs from different addresses as inputs in a single transaction. If I need to pay Bitmit 10 BTC but all I have are two 6 BTC outputs on different addresses I can use two transactions to complete the sale by sending 6 BTC to address k and 4 BTC to address k+1. Now it will be more difficult for a third party to examine the blockchain and determine that the same individual controls both addresses.

Sorry, I mean private keys, not public keys

Answer is yes to all of them.
(Assuming that all pubkeys are also known, not only chaincodes, so in fact all extended pubkeys are known. I thought this is what you meant to ask.)

I feel confused.

For deterministic wallets allowing generation of public keys without private keys, the chain code must be included in the watch-only wallet. Therefore, the chain code have to be kept online. In the following discussion, I assume the chain code(s) are known to the public.

In Armory, if someone knows the private key of sequence number x, he will be able to determine all private keys with sequence number > x, but not for those sequence number
Here are my questions for BIP32:

Assuming all chain codes are known, if private key m/i/j is known, :

1. are every private keys under m/i/j known? (I think the answer is yes)

2. are every private keys under m/i/j+1 known? (The answer should be yes if it followed the Armory model)

3. are every private keys under m/i/j-1 known? (The answer should be no if it followed the Armory model)

4. are every private keys under m/i known?

5. are every private keys under m/i+1 known?

6. are every private keys under m/i-1 known?

7. is the m known?

I listed one in an earlier post. If I'm going to buy Bitcoins on an exchange I'd like to be able to give the exchange an extended public key so that they can automatically generate new withdrawal addresses without further interaction. Similar I'd like the exchange to give me an extended public key so that my HD-aware client can automatically generate the next unique deposit address every time I want to add Bitcoins to my account.

If Wikileaks wants to receive donations without allowing a third party to monitor how much they have received or who the donors are they could use an BIP32 HD wallet. Every visitor who requests a donation address gets an extended public key instead of a regular public key, so now the donor can generate his own unique donation addresses without needing to visit the Wikileaks web page every time.

Clients that understand HD wallets could be configured to store a counter in the address book entry of each extended public key and to by default automatically send to a unique address when that entry is selected by the user.

Agree.


"the secret seed in itself can only derive pubkeys" should be "the secret seed in itself can only derive relations (in the sense of differences) between pubkeys and relations between privkeys".
"unless the attacker also gains access to the additional (master) privkey secret" should be "unless the attacker also gains access to a privkey (master or derived)".


Depends on how you see it. If I want to generate new pubkeys without accessing my privkeys it means that, securitywise, I want to treat my secret seed differently (i.e. less secure) than my privkeys. To me this is the same as having a 3rd party generate them (and having access to my secret seed).


This mode could be a "self-seeded" mode, where the chaincode is not inherited from some parent key but is a hash of the privkey. Then it suffices to backup the privkey alone. And yes, this should probably be the default, and an inherited chaincode should not only be used on explicit request.


Maybe two seeds are enough, one inherited, one self-seed (=hash of privkey).

I think that there's some confusion here, type-2 should always be more secure than type-1, for any kind of user.

With type-1, the secret seed derives the actual privkeys, therefore if the secret seed is compromised then all of your privkeys leak.

With type-2, if the hash derivation function includes the secret seed as one of the concatenated inputs (as in the OP of this thread), then the secret seed in itself can only derive pubkeys, and unless the attacker also gains access to the additional (master) privkey secret, all your privkeys are still provably secure.

The disadvantage of having the secret seed as one of the concatenated inputs of the derivation function is that the 3rd-party couldn't generate new pubkeys on its own, without knowing the secret seed. But the other advantages of type-2 still hold, namely that the owner of the wallet can generate new pubkeys without accessing (decrypting) his privkeys, and that for backup purposes you only need to store your master privkey and secret seed (this is an advantage over the regular random-independent wallet, not over type-1 wallet).

If BIP 0032 doesn't include an option to have a secret as one of the inputs of the hash derivation function, then I think that this kind of mode should be added to BIP 0032. This could even be the default, if we're worried about scenarios where users aren't careful and compromise a branch in their key hierarchy. We might wish to give users the option to have different secret seeds for particular branches in the key hierarchy, and store all these seeds in the wallet file (and warn the user that he needs to backup his wallet when he creates a new seed).

Correct. It is the chaincode that you gave away which determines (or limits) the "damage" that a leaked private key does. If you give away the chaincode of m/0/0 to someone then that person knows how all private keys below m/0/0 are linked to the private key of m/0/0. Consequently, if any private key below m/0/0 leaks to that person, say of m/0/0/42, then that person can compute the private key of m/0/0 and from that the private key of all m/0/0/x.. in the branch of m/0/0 including siblings of m/0/0/42. However, assuming you didn't give away other chaincodes, that person cannot compute the private key of m/0 or m/0/1.

I don't think that type-2 deterministic wallets should be the default in any client, because users have to think and care about what they export from their wallets (chaincodes, extended pubkeys, private keys) and how they secure the exported data. Type-1 deterministic wallets seem to be a more suitable default. If type-2 wallets were default then the average user should not be given the opportunity to export chaincodes. So there should be no "extended pubkeys" ("pub" suggesting that they can be exported) but only "extended privkeys".

As far as key hierarchies go, do we have any significant application for it yet? I would really like to be convinced that we absolutely need them.

So what is this about?

I understood this to mean if the attacker knows the extended public key (which includes the chain code) of a node, and any one of the associated private keys, then the attacker can also recover all the sibling private keys. Is this not correct?

If the attacker a single private key and the same key's chaincode, m/i/j/k, he can only determine m/i/j/k/X.  You can't reverse the chain or get to other chains, or even determine "brothers" in the same chain.  You can only traverse down a separate chain specific to that key (which is not ever used in BIP 32 wallets, by default)

I'm still not sure about the answer to my original question. As BIP34 is currently written, if an attacker knows the chain code associated with m/0/0 and knows one of the private keys in the series m/0/0/0...k series can also he recover the private key of any other branch in the tree, or does m/1, m/2, etc use a different chain code that can't be derived from the m/0 chain code alone?

The difference in security model between deterministic and non-deterministic wallets is really quite tiny in practice.  There's very few situations where that difference is the results in devastating compromise with a deterministic wallet, that wouldn't also be devastating to a randomized wallet.  And then that is compounded by the fact that there's very few situations where an attacker would get one private key but not the others:  they usually get nothing, or they get everything.  In terms of users revealing private keys from their wallet -- that is a practice that just shouldn't happen.  If they are doing that, then yes, the deterministic wallet is less safe, but the user is exercising poor judgment and likely to compromise themselves other ways (they should be educated about this).

The reason why the security difference is effectively small between a compromise of either system, is because existing Bitcoin-Qt wallet behavior of pregenerating a pool of 100 addresses actually makes the two very similar.  Sure, the Bitcoin-Qt wallet "unsteals" itself after some amount of time, but that time may be very far in the future when the user actually gets through those 100 and starts generating more.  Most of the coin-stealing will occur with the coins already available in the wallet, since there's no guarantee that coins will be added or removed from the wallet in the future to risk losing them if the user spends them.  Perhaps if the attacker knows some information about the user and knows they will be receiving coins in 3 months from now and want to wait for that to occur then the randomized wallet is preferred (for the user)... but then that is effectively a targeted attack, which is expected to be much more difficult to deal with, anyway.

In reality, the biggest risk to the average user is not time-staggered wallet theft, but loss of coins from HDD loss or wallet corruption.  The ability to make a single backup, ever, far outweighs so many other risks faced by regular users.  That's not to say the randomized key model is inferior for all use cases, but the default very clearly should be deterministic one (let knowledgeable users who understand the various factors make the decision to change from the default).

+1 for type-2 deterministic wallets

As currently proposed, if you have the master public key you can, in principle, iterate over the serial number to generate all possible addresses. However, there is no hard upper bound on the serial number, or the sizes of any gaps in the sequence of used addresses. Would it be possible to include some identifying information--in particular, the serial number--in the address itself, so that one could easily check whether a given address matches a known master public key without scanning through all possible serial numbers? Or is the address format too inflexible for that?