Topic: Deterministic wallets - page 10. (Read 48261 times)

We actually just had a discussion about this, and I'm in favor of changing this. The proposal would be:

• k_i = k_par + I_L
• K_i = K_par + I_L*G

I've been holding back on changing this, as speed wasn't a priority really. However, it is a lot easier to do the required operations for public derivation in constant time, than for the multiplicative case, which means it's easier to secure against timing attacks (and we are, very intensively, dealing with private material here). Also, it means you only need almost the same primitives as needed for ECDSA in the first place.

It is not less secure, as you still need to solve the ECDLP to find I_L from I_L*G (=the public key, which is exposed). Assuming a weaker version of the scheme, where it's just K_i = K_par + (i*c_par)*G, and assuming there is a transaction with inputs corresponding to i values i1 and i1+1, and a transaction with values i2 and i2+1, an attacker could detect these were created by someone using the same chain code twice. This would not be possible in the multiplicative version, and also not in the real scheme where the 'tweak' I_L is computed using an HMAC.

Anyone objects to changing this?

It's described by gmaxwell in the OP of this thread.
As currently in BIP32 you would still have I=HMAC-SHA512(Key=c_par, Data=K_par || i)
And then:
k_i=k_par+I_L
K_i=K_par+G*I_L
c_i=I_R

Can someone precisely specify the additive variant of the CKD function?  I'm fairly certain I know, but I don't want to end up missing a detail and evaluating something else.

I'm still hoping to hear some explanation on why the multiplicative variant is advantageous.
It seems to me that it makes sense to re-consider this issue before BIP32 is finalized.

Huh? Why would regular backups be needed? The major advantage of deterministic wallets is that backups aren't needed (see here).

I'm not sure that I understood your use case, could you please explain the exact scenario more clearly? if you had an ancestor chaincode and pubkey, then you can derive the descendant chaincode and there's no necessity to encrypt and send it to you, and if you don't have any ancestor chaincode then an encrypted chaincode must be sent to you, no?

Maybe we do gain some security by having ci depend on Kpar, because commonly just the hashed address of Kpar is published (until the coins get spent).

Very nice, I like your BIP32 modifications with type-1/type-2 derivation according to the highest bit of the index. it could give flexibility with scenarios that ErebusBat mentioned, something like person A giving person B that he trusts the ability to derive a branch (with privkeys) in his wallet, and then person B wishes to give an untrusted person C the ability to derive pubkeys in a sub-branch, so to enhance security he can break the homomophism link by doing type-1 derivation (person B couldn't have done the type-1 derivation if it was only possible at depth=1 of the "subaccounts", because he's not trustworthy enough to have access to that depth, and besides keeping the layout of extending the particular branch instead of starting a new subaccount could be useful for accounting and so on). Probably there would be more interesting use cases than this one, that I haven't thought of.

I suppose that with this updated BIP32, some of the complexity will be transferred to the people who should do GUI design for wallet layouts

As discussed, it's important to do the secret type-1 derivation from the master node (depth 0) to the subaccounts (depth 1), since if the master node leaks then the entire wallet leaks. So the derivation from depth 0 to depth 1 should be type-1 by default, and maybe if you wish to be extra safe (about preventing people from shooting themselves in the foot) then you should specify that type-2 derivation from depth 0 to depth 1 isn't allowed according to the BIP32 standard, and enforce that in the Satoshi client. BTW, with the updated BIP32, I guess that there's no need to save the initial entropy S in wallet.dat ?

There are use cases where knowing all possible keys (or addresses) in advance is an advantage. I mentioned two: audit and bloom filter computation. The limit could be optional with default 2^31 as is by the definition.

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

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.

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.

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.

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?

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.

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.


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.


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

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.

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
why don't we use
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:
[/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?

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

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?

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