Deterministic wallets

[ErebusBat]

Part of what I wrote above is nonsense I think, regarding the supposed "disadvantage", because I don't really see a practical use case where some 3rd-party should generate new pubkeys for someone elses wallet. So please disregard that. Also, I didn't understand why you consider what you said to be type-1, but nevermind.

Actually there are very good reasons for that to happen.  Two examples:

1) Payment processing.  A processor company could maintain the webpage and infrastructure but generate addresses ad-hoc from your chain-code.  The benefit is that you (as a merchant) don't have to wait. the funds hit your wallet and don't go through the payment processors. I think there is already ones that do this actually.

2) Website.  Your '3rd party' in this case would be your webserver; however it wouldn't hold any public keys so it is really the same thing as #1, you just happen to own both.  Because the webserver can generate keys ad infinitum you don't have to worry about running out or having it get compromised and your private keys out.

3-Bonus) Games & Public Affairs - Lets say bitlotto wanted to make all the payment addresses for the future available, he could publish the public details of the chain for anyone who cared and then you would know what payment address would be XYZ.  This is a fluff example really, but the point is once the tool is there then people will find creative uses for it.

[1714062754]

1714062754

[iddo]

Part of what I wrote above is nonsense I think, regarding the supposed "disadvantage", because I don't really see a practical use case where some 3rd-party should generate new pubkeys for someone elses wallet. So please disregard that. Also, I didn't understand why you consider what you said to be type-1, but nevermind.

Actually there are very good reasons for that to happen.  Two examples:

1) Payment processing.  A processor company could maintain the webpage and infrastructure but generate addresses ad-hoc from your chain-code.  The benefit is that you (as a merchant) don't have to wait. the funds hit your wallet and don't go through the payment processors. I think there is already ones that do this actually.

2) Website.  Your '3rd party' in this case would be your webserver; however it wouldn't hold any public keys so it is really the same thing as #1, you just happen to own both.  Because the webserver can generate keys ad infinitum you don't have to worry about running out or having it get compromised and your private keys out.

3-Bonus) Games & Public Affairs - Lets say bitlotto wanted to make all the payment addresses for the future available, he could publish the public details of the chain for anyone who cared and then you would know what payment address would be XYZ.  This is a fluff example really, but the point is once the tool is there then people will find creative uses for it.

Well then, if there are practical use cases where you should want to give some 3rd-party (that you don't trust) the ability to create new pubkey addresses for your wallet, then it can be done with BIP32 by giving the 3rd-party the relevant chaincode.
However, if that 3rd-party manages to obtain a single privkey of yours, then all your other privkeys will also leak.

So if we can reasonably expect that such use cases will be common in the future, then maybe the BIP32 design gives users too much of an opportunity to shoot themselves in the foot? Instead, if the derivation function would be one-way (like in Armory), then only the branch starting with the chaincode that you gave the 3rd-party could be compromised. Maybe there could be two wallet modes, one less secure mode that derives keys in a reversible way (when the chaincode is known) as in the current BIP32 design, and another more secure mode that derives keys via OWF? Maybe you should be able to use the different modes in different branches of your wallet file?

[Pieter Wuille]

So if we can reasonably expect that such use cases will be common in the future, then maybe the BIP32 design gives users too much of an opportunity to shoot themselves in the foot? Instead, if the derivation function would be one-way (like in Armory), then only the branch starting with the chaincode that you gave the 3rd-party could be compromised. Maybe there could be two wallet modes, one less secure mode that derives keys in a reversible way (when the chaincode is known) as in the current BIP32 design, and another more secure mode that derives keys via OWF? Maybe you should be able to use the different modes in different branches of your wallet file?

I would personally very much like to limit the number of variations we need to consider. You are right that there are security risks when a user can obtain a parent extended public key, and a child secret key, but I do not see a way to avoid this, except by dropping the ability to do public derivation. However, when client software does not expose a chain code ever, the whole sceme is effectively type-1, in the sens that it derives private data from private data (and knowing the public key gives you 0 information about the child key); it's a weirdly complicated randomization function, but it still is one.

Now for the encryption case: I envisioned chain codes as not being encrypted, as that prevents the wallet from functioning without decryption whatsoever (as opposed to just decrypting private keys when needing to do a spend). This does mean that if someone who got a child private key from you is able to steal a parent chain code, you are fucked. My only answer to this right now, is that giving someone a private key already implies a degree of trust (you're sharing private keys, so you're sharing the ability to spend the same coins). However, if you trust them enough not to steal your wallet, why not trust them with the keys in the first place.

Regarding using addition instead of multiplication: we switched to multiplication at some point, but I can't remember why - the only thing it adds is removing the ability to compute I_L from a parent and a child pubkey, which doesn't seem to gain you anything.

[iddo]

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

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

That appears to be false, see post #56 and this post.

So if we can reasonably expect that such use cases will be common in the future, then maybe the BIP32 design gives users too much of an opportunity to shoot themselves in the foot? Instead, if the derivation function would be one-way (like in Armory), then only the branch starting with the chaincode that you gave the 3rd-party could be compromised. Maybe there could be two wallet modes, one less secure mode that derives keys in a reversible way (when the chaincode is known) as in the current BIP32 design, and another more secure mode that derives keys via OWF? Maybe you should be able to use the different modes in different branches of your wallet file?

I would personally very much like to limit the number of variations we need to consider. You are right that there are security risks when a user can obtain a parent extended public key, and a child secret key, but I do not see a way to avoid this, except by dropping the ability to do public derivation.

Right, the post above by jl2012 confused me. There seems to be an inherent contradiction between key homomorphism and leakage of the ancestor privkeys, in the sense that if some privkey k_i is compromised (and all the chaincodes and pubkeys of the wallet are public) then we have that I_L=HMAC(c_par, K_par||i) is known, and we can solve I_L * x = k_i (mod n) and obtain the privkey x=k_par

Maybe another signatures scheme (instead of elliptic curves) could allow both key homomorphism and one-way derivation (in the sense that k_i wouldn't reveal k_par), I don't know. But we're not planning to move away from ECC anytime soon, certainly not just for deterministic wallets, so in practice it wouldn't matter. So far the only thing that I can think of is the straightforward option of allowing the user to encrypt the chaincodes (maybe with a "minor" password as I mentioned above) if he wishes to be less exposed to security risks.

However, when client software does not expose a chain code ever, the whole sceme is effectively type-1, in the sens that it derives private data from private data (and knowing the public key gives you 0 information about the child key); it's a weirdly complicated randomization function, but it still is one.

I'm still not exactly sure what you mean by "client software does not expose a chain code ever". Suppose for example that the user stores his wallet.dat file on the cloud (e.g. dropbox), if the chaincodes aren't encrypted then they are exposed, no? So the user assumed that he's safe to store the wallet on the cloud because the privkeys are encrypted, but if a single privkey leaks somehow then all his other privkeys also leak, which isn't the case with the regular random-independent wallets.

Regarding using addition instead of multiplication: we switched to multiplication at some point, but I can't remember why - the only thing it adds is removing the ability to compute I_L from a parent and a child pubkey, which doesn't seem to gain you anything.

With the additive variant, don't you get I_L*G from parent and a child pubkeys, rather than I_L itself? I'm still not sure what are the advantages of the multiplicative variant.


Given the (supposedly) practical use cases that ErebusBat mentioned, I urge you to get more peer reviews regarding these security concerns where we might allow users to shoot themselves in the foot more easily, before you deploy BIP 32 in the official client.

[gmaxwell]

An alternative might be to change the scheme so that the main trunk of a deterministic wallet does not have the homomorphism, only further branches from that do.  This would greatly confine the leakage there, and also make it more intuitive: leaking the private key for any "subaccount" (or whatever you want to call it) leaks that subaccount.  This may be a way to get both properties.

But the homomorphism is really important and enables many valuable use-cases. Right now the need to have private keys online to accept payments is actively getting people robbed. The need to have static addresses for donations and reoccurring payments is actively and materially compromising privacy.   The reversible privkey leaks are only applicable to a subset of cases where people would otherwise be robbed completely.

[iddo]

An alternative might be to change the scheme so that the main trunk of a deterministic wallet does not have the homomorphism, only further branches from that do.  This would greatly confine the leakage there, and also make it more intuitive: leaking the private key for any "subaccount" (or whatever you want to call it) leaks that subaccount.  This may be a way to get both properties.

I like this idea. And in fact, with this idea of yours we can still preserve the important property where your initial wallet.dat backup can always restore all your future privkeys, including privkeys that belong to a "non-homomorphic" subaccount that you created after your initial backup: instead of doing HMAC-SHA512(key="Bitcoin seed", msg=S) to derive the master privkey and master chaincode as BIP32 specifies, we can do HMAC-SHA512(key="seed #i", msg=S) to derive master privkey&chaincode for each subaccount #i, and since the random seed S is stored encrypted and SHA2 is a one-way function, this is secure in the sense that leakage in subaccount #i_0 doesn't compromise any subaccount #j for j!=i_0 (the user will need to provide his wallet password when he wishes to create a new subaccount, which is fine).

But the homomorphism is really important and enables many valuable use-cases. Right now the need to have private keys online to accept payments is actively getting people robbed. The need to have static addresses for donations and reoccurring payments is actively and materially compromising privacy.   The reversible privkey leaks are only applicable to a subset of cases where people would otherwise be robbed completely.

Yes, I wholeheartedly agree that type-2 derivation is really great and that its benefits vastly outweigh the potential risks.
All that I'm trying to get across is that wherever we can make design decisions that minimize the possibilities of users shooting themselves in the foot, it's a good thing to do it, instead of assuming that the users will be prudent and then telling some user who lost his coins that he had to read the "fine print" on the risks that key homomorphism.

[NickGlazkov]

I was looking at bitaddress.org 's brain wallet feature. It takes in a passphrase and generates a private key/public address.

Could the same algorithm be used to create a whole series. If the passphrase as "Bla Bla" could you make the seed to create the next address "Bla Bla1" and then do "Bla Bla2".... to create an infinite series of addresses?

Is there any flaw that anyone sees in using the algorithm in bitaddress to do this (if not I might submit a patch to add this feature).

Does Armory use the same passphrase->seed algorithm that bitaddress does (are they compatible)? Is there a reason?

Also, has anyone figured out a method to take some seed that can just generate public addresses on an exposed merchant server that would have a private seed on a secure machine that could generate the corresponding private keys? Does anyone have any code in any language to do this?

[etotheipi]

Also, has anyone figured out a method to take some seed that can just generate public addresses on an exposed merchant server that would have a private seed on a secure machine that could generate the corresponding private keys? Does anyone have any code in any language to do this?

That's exactly what Armory does.  See the Offline wallet tutorial.  All private keys are on computer that never touches the internet.  Watching-only wallet on online computer only contains public keys.  Both wallets are really the same wallet, generate the exact same semi-infinite sequence of addresses, but anyone getting ahold of the watching-only wallet cannot take the funds.

[grau]

Also, has anyone figured out a method to take some seed that can just generate public addresses on an exposed merchant server that would have a private seed on a secure machine that could generate the corresponding private keys? Does anyone have any code in any language to do this?

You may use bits of proof's BIP32 implementation in:

https://github.com/bitsofproof/supernode/blob/master/api/src/main/java/com/bitsofproof/supernode/api/DefaultKeyGenerator.java

that re-generates the exact same key with a given sequence number from extended private or only the extended public key.
It also supports key hierarchies, so you may use key co-ordinates of any dimension.

You see an example use of the public and private key generator in the unit test below:

https://github.com/bitsofproof/supernode/blob/master/api/src/test/java/com/bitsofproof/supernode/api/KeyGeneratorTest.java

[Pieter Wuille]

Hello all,

I've made some changes to BIP32 to deal with the issue of revealing a master key by exposing both public parent and private child. The change is important (the child key derivation function changes), but it's maximally compatible with the previous version. In short, it means you can now select whether you want "public derivation" (the older, type-2 style) or "secret derivation" (safer, type-1) in each step, and the default wallet structure uses secret derivation for deriving account keys from the master key. This means that a leak of a secret account key (or below) cannot result in revealing the master secret.

As I don't like encumbering the key derivation with information about wallet structures, the derivation type is not hardcoded but can be selected at each stage individually.

Any comments from iddo, or other people?

[thanke]

Regarding using addition instead of multiplication: we switched to multiplication at some point, but I can't remember why - the only thing it adds is removing the ability to compute I_L from a parent and a child pubkey, which doesn't seem to gain you anything.

With the additive variant, don't you get I_L*G from parent and a child pubkeys, rather than I_L itself? I'm still not sure what are the advantages of the multiplicative variant.

The additive version would be faster because the "fast exponentiation" algorithm that computes I_L*G can use pre-computed values of x*G for small x. I believe OpenSSL does something like that.

Not saying that speed should be of any concern here, though..

[thanke]

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?

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.

Seeing that some interna of BIP 32 are being re-discussed, I would like to bump this comment of mine from several month ago. Sorry for repeating myself, but I thought that new applications or use cases, and therefore new opinions, might have come up in the meantime. This question/suggestion is about the "public derivation". Instead of

Code:

I = HMAC-SHA512(Key=cpar, Data=Kpar || i) (with Kpar = kpar*G, EC multiplication)
Split I into two 32-byte sequences, IL and IR.
ki is equal to IL*kpar (mod n).
ci is equal to IR. 

why don't we use

Code:

IL = HMAC-SHA256(cpar,Kpar||i)
IR = HMAC-SHA256(cpar,i)

the difference being that ci depends only on cpar and i (as before) but not on Kpar anymore.

[EDIT] Correction. I meant that the entire I does not depend on Kpar:

Code:

(IL,IR) = I = HMAC-SHA512(cpar,i)

[/EDIT]

The advantage that I see with having ci independent of Kpar is that it opens up the possibility of updating all extended pubkeys in the tree (by updating the root extended pubkey) without touching the chaincodes.

Consider a hierarchy of servers where each server holds the extended pubkey corresponding to its position in the hierarchy. Note what is required when a server B receives his extended pubkey from the higher level server A. In the communication between A and B the pubkey-part of B's extended pubkey has to be authenticated (if B uses the wrong pubkey, money sent to it will be lost) whereas the chaincode-part has to be encrypted (by default chaincodes are to kept secret). In an update throughout the whole tree we could spare us the encryption part of that communication (if ci was indepent of Kpar) because the chaincodes remain unchanged.

Countering the above cited comment: what do we gain by having ci depend on Kpar?

[Pieter Wuille]

Countering the above cited comment: what do we gain by having ci depend on Kpar?

I really don't like the complexity of maintaining essentially two independent sets of information. It means software has to deal with any combination, and tree nodes need identifiers for both the key and chaincode part.

In addition, keys and chaincodes are cheap - just 32 bytes. I don't really see the benefit of being able to keep one identical while updating the other.

Perhaps there are specific use cases, but you'll have to be more concrete to convince me about that. Right now, I think it just complicates reasoning and implementation.

[thanke]

Countering the above cited comment: what do we gain by having ci depend on Kpar?

I really don't like the complexity of maintaining essentially two independent sets of information. It means software has to deal with any combination, and tree nodes need identifiers for both the key and chaincode part.

You don't need to maintain two independent sets of information. With this last post I didn't mean to go as far as I meant to go in my post from december (where I actually did suggest to separate them in two independent sets). In fact all the infrastructure for extended pubkeys can stay as it is. This is just a slight modification to the derivation function (removing the parameter Kpar from some input) and leaves everything else untouched. In particular, the infrastructure handling extended pubkeys is untouched. The "updating" feature doesn't need to be implemented, it's nothing more than a future option for if a use case comes up.

Right now, I think it just complicates reasoning and implementation.

It doesn't complicate implementation because I consider it a trivial change. It doesn't complicate reasoning because the user won't even notice this change. Nothing of what we explain to end users of BIP32 needs to be altered.

My question is: do we lose anything substantial by giving up dependency of ci on Kpar? Securitywise, anonymitywise, etc?

If not then I would vote for leaving that door open.

In addition, keys and chaincodes are cheap - just 32 bytes. I don't really see the benefit of being able to keep one identical while updating the other.

While probably infrequent, updating won't be an uncommon scenario. The benefit that I pointed out (and the only one I see at the moment) is that we spare us an encryption-requirement when passing around the updates (there is still an authentication-requirement).

[Pieter Wuille]

It doesn't complicate implementation because I consider it a trivial change. It doesn't complicate reasoning because the user won't even notice this change. Nothing of what we explain to end users of BIP32 needs to be altered.

I don't mean implementation of the key derivation code - that's a trivial change indeed. I mean wallet maintenance code that deals with importing keys, detecting parent-child relations between imported nodes, backups and recovery, creating new nodes when used ones are found on the network, .... It just seems so much easier to me when key/pubkey/chaincode are part of an immutable whole, identified using just their address.

[thanke]

It doesn't complicate implementation because I consider it a trivial change. It doesn't complicate reasoning because the user won't even notice this change. Nothing of what we explain to end users of BIP32 needs to be altered.

I don't mean implementation of the key derivation code - that's a trivial change indeed. I mean wallet maintenance code that deals with importing keys, detecting parent-child relations between imported nodes, backups and recovery, creating new nodes when used ones are found on the network, .... It just seems so much easier to me when key/pubkey/chaincode are part of an immutable whole, identified using just their address.

Maybe I'm overlooking something and should read the code.. but how does modifying an inner function keep you from treating key/pubkey/chaincode as an immutable whole? I agree that they should be treated as such. When you mention import, detection, backup, recovery, etc. do you mean these are just too many places that require modification, or they are each substantially more involved than the derivation code?

[Pieter Wuille]

Maybe I'm overlooking something and should read the code.. but how does modifying an inner function keep you from treating key/pubkey/chaincode as an immutable whole? I agree that they should be treated as such. When you mention import, detection, backup, recovery, etc. do you mean these are just too many places that require modification, or they are each substantially more involved than the derivation code?

None of that code has been written. I just mean that not being able to assume "if the address is the same, key/chaincode/pubkey are the same" complicates things, both for implementations that need to be aware of things like "someone is importing a tree node, we already have the address, but the chaincode was updated, however old children derived from still use the old chaincode... what if one of those old nodes gets used on the network, do we create a new one using the old or using the new chaincode". I'm not sure about you, but it makes it terribly complicated for me to think about even what the correct behaviour would need to be, in many edge cases.

Your use case doesn't convince me to add that complication, both for those who need to implement it, and those who are going to use it.

[grau]

Any comments from iddo, or other people?

I suggest to set and serialize maximum i for each extended key. Such serialized string would define the wallet keys without the need of a regular backup until maximum number of keys not exceeded.
It would also facilitate audit since the set of possible descendants of a key would be of a practicable size. Also the bloom filter could be precomputed for SPVs including all possible addresses derivable.

[Pieter Wuille]

I suggest to set and serialize maximum i for each extended key. Such serialized string would define the wallet keys without the need of a regular backup until maximum number of keys not exceeded.
It would also facilitate audit since the set of possible descendants of a key would be of a practicable size. Also the bloom filter could be precomputed for SPVs including all possible addresses derivable.

I'm not convinced. Part of the point is to be able to generate more keys on the fly as needed, without all of them being known in advance, or even be known how many there are.

[thanke]

Maybe I'm overlooking something and should read the code.. but how does modifying an inner function keep you from treating key/pubkey/chaincode as an immutable whole? I agree that they should be treated as such. When you mention import, detection, backup, recovery, etc. do you mean these are just too many places that require modification, or they are each substantially more involved than the derivation code?

None of that code has been written. I just mean that not being able to assume "if the address is the same, key/chaincode/pubkey are the same" complicates things, both for implementations that need to be aware of things like "someone is importing a tree node, we already have the address, but the chaincode was updated, however old children derived from still use the old chaincode... what if one of those old nodes gets used on the network, do we create a new one using the old or using the new chaincode". I'm not sure about you, but it makes it terribly complicated for me to think about even what the correct behaviour would need to be, in many edge cases.

Your use case doesn't convince me to add that complication, both for those who need to implement it, and those who are going to use it.

Well, ok, see the problem with updating chaincodes. But luckily I intended to update only pubkeys, not chaincodes, mainly because I don't see a point in updating chaincodes. If you prohibit updating chaincodes then you have the nice side consequence that your bijection between addresses and triples (key/chaincode/pubkey) is maintained.

Think of an update as importing a completely new (key/chaincode/pubkey)=address. The coincidence that there are two such triples with the same chaincode should be irrelevant for the implementation. I don't expect "update" to be implemented in mainline nor even to be mentioned in BIP32. If someone ever wants to implement "updates" it can be done with an external script that makes RPCs to import the new extended pubkey. It seems to me that the problems you describe are the problems of that person who decides to implement updates in the future, not the problems of implementing BIP32 now (without "updates").