Feel free to submit a pull request to replace build-msw.txt with this!

@iddo: have a look at https://bitcointalk.org/index.php?topic=102349.0

He wants to generate a k_par/K_par indepedently from BIP32 derivation, and "inject" it into an existing key tree, updating the keys that are derived from it, while retaining the chain codes (I think).

I'm not convinced about the use case, and IMHO allowing this overwriting of keys makes things harder to reason about. We're not explicitly depending on chain codes to be unique across keys, as far as I can tell though.

If you have a reason to deviate, do so. If you don't have a reason to deviate, don't.

I'm just saying that applications and their expectations will differ, and it is unreasonable that they will all behave in the same way to the smallest detail. And that's just fine.

I feel that how different applications deal with backups and recovery is such a detail. Perhaps it makes sense to add a section with recommendations about this, but I can't expect everyone to follow them. An application may just start with a new seed after a time and tell the user to make a new backup. It may keep track of the necessary gap to do a scanning recovery, and warn the user when some maximal configured gap is exceeded. It may rely on a local fast-accessible indexed UTXO to search a huge amount of addresses. It may automatically backup the highest used indexes to dropbox. I don't think we know the best practices here, so I don't see a reason to fix them.

I don't want to specify how wallet software should work.

That's just complicating things for yourself, but yes, you can.

My purpose for BIP32 was indeed to make using many keys viable, and not needing frequent backup. That means backups must protect you against loss of coins. It doesn't mean it should be trivial to restore from  a backup, or to reduce your wallet to the blockchain.

When recovering from a backup, use some lookahead like 100 or 1000 keys when scanning (depending on the purpose). If a gap larger than the lookahead is used, I'm sure you'll notice transactions/money is missing after some date. Just retry with a larger lookahead and you're fine. Also note that a large lookahead is only necessary for external subaccounts (so not for change addresses, as you don't expect gaps there at all).

Alternatively, an automatic and low-privacy-risky backup with just the maximal indexes can be used as well, as like iddo suggests. I'm not sure that's necessary in practice though.

The reason I don't like putting a maximum index in the serialized form is because that doesn't tell you what to do when you run out of indices.

You're right. Even here, addition doesn't really change anything.

I was wrong about this, as the problem of key exposure doesn't really exist for public key derivation, where these operations are required. It doesn't hold for chaincodes either, as these aren't tweaked.

This makes me wonder whether it's still worth changing, though the implementation complexity argument still holds.

I don't think storing the maximal branching inside the serialized format is the right way to go. That doesn't mean wallets can't keep such information separately, but the problem is that you'll always hit more cases that aren't covered. Will you have separate limits of public and private derivation? Will you limit the number of levels below a node? The specific branching factors of all of these nodes? What if someone wants to use a non-standard more complex structure? Inherently, how the tree structure is used as a wallet, and how keys are picked in it, depends on implementation anyway.

For example, say you do this, and limit only at the direct level what the largest index of a subnode is. You're giving out addresses to pay to, a unique one for each invoice. Some are never paid, so you end up with gaps. At some point, you reach the maximal index. What now? Will you switch to a new account? Create an extra tree level? Tell the user to create a new backup? All those problems occur are exactly the same for the case where you didn't know the maximum index, but did have a maximal gap. When it gets exceeded, tell the user his gap is now larger and he needs a new backup.

I say this is all implementation specific, and doesn't belong in the serialization.

Can you specify what information your are assuming your attacker has? Does he know c_par and is just scanning all pubkeys he gets to see for a difference of c_par*G? Or how does his "detection" work?
[/quote]

Sure. I assume the attacker can only observe the blockchain. For any transaction with multiple inputs, he subtracts the pubkeys used in any pair of inputs. If he finds two transactions that result in the same difference, they are very likely keys that are generated from the same extended parent (the difference would be (i-i')*c_par*G. Note that he can't find c_par or i or i' itself, just a likelyhood that c_par is the same. Also note that this doesn't work in the real scheme as not i*c_par but HMAC-SHA512(key=c_par, msg=K_par || i) is used, which guarantees no tweak will be reused.

This was just a thought experiment to see how much we'd have to weaken the construction before the add-vs-multiply makes any difference.

Nothing, timing coincidence.


OpenSSL's ECDSA_sign probably guarantees this (I haven't verified), but as generic EC multiplication isn't required by ECDSA_sign (only by ECDSA_verify), it's not guaranteed to have a constant-time version (and a variant-time one is certainly faster).

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?

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.

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.

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.

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.

Some old versions of bitcoinjs and Armory are known to have produced non-DER signatures, but both authors are aware of this, and fixed their code more than half a year ago, afaik.

I mailed him personally about it, but didn't get an answer (yet).

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?