Deterministic wallets

[Pieter Wuille]

If K_i = (i*c_par)*K_par then you get the same phenomenon, right? The difference would be (i-i')*c_par*K_par, which is recognizable if (K_par,c_par) is reused.

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

[1714974903]

1714974903

[1714974903]

1714974903

[1714974903]

1714974903

[1714974903]

1714974903

[grau]

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

I thought the advantage of this proposal would be to have a wallet that is able to provide

1. a high number of keys to support privacy
2. does not require regular backup, at least to avoid key loss.

If serialization format (that is the ultimate backup) fails to deliver enough information to recreate all keys that might have output in a practical time span, then it fails the second goal.

If you would add a maximum sequence to the serialization of the extended key then backups would only be needed if a new extended child key is created (sub account), or if the maximum is exhausted and need to be increased to retain the same privacy level.

The client could also warn of loss of privacy and re-use already used keys if hitting the maximum sequence of already known keys, until the user increases the maximum and creates a backup.

[iddo]

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.

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

Assume you lost your wallet storing the unspent transactions, but you have the root key for the BIP32 generator from a cold store. Theoretically nothing is lost since you can scan the block chain for all outputs that can be spent with descendants of the root key, but practically you are not able to do this if you do not know what sequences were used.

Therefore you either have to backup the sequences used or simpler set a limit to them in beforehand that is a practicable magnitude for a scan.

As Pieter mentioned in the link that I gave you, it should be very practical to scan in mostly all cases of wallet layouts, the branching factor and depth are quite tiny.

The assumption there is that if a key with a sequence number is not on the block chain, then higher sequences were not used, right?

I think that would not hold. A shop usually offers unique addresses to receive payment for individual orders. Some orders never get paid, therefore their key will not be present in the block chain, however keys with higher sequence number might be. A reconstruction of the wallet would fail at such a gap.

Right, good point.

I still believe that for the default wallet layout (subaccounts at level 1 and linear path for each subaccount) and for other non-pathological layouts, you could let your computer run for a couple of hours and retrieve all your privkeys, because the depths of the branches (including branches that have keys that were never active on the blockchain) would be quite small.

I'd say that if the user chooses a peculiar wallet layout, then it's up to him to consider whether future backups might be important.

Furthermore, the client software could let you do "public-insensitive" backup that contains just your wallet layout (just the indices i, or the indices i and the pubkeys) which doesn't contain any sensitive info (chaincodes and privkeys), so you could backup just the layout from time to time, if you wish to be extra safe.

[grau]

I still believe that for the default wallet layout (subaccounts at level 1 and linear path for each subaccount) and for other non-pathological layouts, you could let your computer run for a couple of hours and retrieve all your privkeys, because the depths of the branches (including branches that have keys that were never active on the blockchain) would be quite small.

I guess a couple of hours will not cut it. Even if you have an UTXO indexed by keys (that is not even the case for the Satoshi client), it is still prohibitive to scan 2^32 possible generated keys. I believe that you either store what much smaller subset was potentially used, or you can not practically reconstruct the set of keys used, which defeats a purpose of the proposal, that is not to have the need of regular backups.

[thanke]

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

I expect additive and multiplicative derivation to be equivalent in all "theoretical" aspects of security and anonymity. By "theoretical" I mean disregarding timing attacks, complexity, etc.

I've seen people (not only newbies) confuse the discrete log problem with computing n-th roots. The latter problem is easy: from n*K and n you can compute K. This kind of confusion may lead people to wrongly assume that it was impossible to infer K_par from c_i*K_par and c_i, and they would take this as some sort of "anonymity feature" of multiplicative derivation. With additive derivation everybody can see immediately that K_par can be inferred from K_par + c_i*G and c_i.

This would be an argument for additive derivation: it can fool less users, or its properties (and non-properties) are easier to explain.

[iddo]

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

Scenario is this: Server A is holding (K_par,c_par). Server B is being set-up in a different location and is supposed to hold (K_i,c_i). All chaincodes are to be kept secret by the servers holding them, i.e. c_par shall only be known to A (not B) and c_i shall only be known to A and B (no third party). It is irrelevant here who knows K_par and K_i. So B does not derive anything itself. Instead, A does the derivation of (K_i,c_i) and sends the result to B. Of course, the communication of A to B must be authenticated. The point is that on top of that at least c_i must (in the general case) be sent in encrypted form.

So in this scenario, why wouldn't you need to send c_i in encrypted form with your proposal?

[Pieter Wuille]

I still believe that for the default wallet layout (subaccounts at level 1 and linear path for each subaccount) and for other non-pathological layouts, you could let your computer run for a couple of hours and retrieve all your privkeys, because the depths of the branches (including branches that have keys that were never active on the blockchain) would be quite small.

I guess a couple of hours will not cut it. Even if you have an UTXO indexed by keys (that is not even the case for the Satoshi client), it is still prohibitive to scan 2^32 possible generated keys. I believe that you either store what much smaller subset was potentially used, or you can not practically reconstruct the set of keys used, which defeats a purpose of the proposal, that is not to have the need of regular backups.

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.

[iddo]

Seems to me that additive vs multiplicative derivation is not the point. Instead it's about how i and c_par are combined. Using c_par^i instead of i*c_par looks different at first sight.

I don't think that c_par^i would give you pseudorandom keypairs. These thought experiments didn't explicitly specify how to derive c_i from c_par, but it appears that you would be claiming that the sequence ((c_{i-1})^i for consecutive i=1,2,3,... is indistinguishable from random data, which isn't true. If we cannot argue that the sequence is pseudorandom, then we cannot prove that we're secure against related-key attacks. So the bottom line is that we'd have to stick with HMAC-SHA2 anyway...

[iddo]

I still believe that for the default wallet layout (subaccounts at level 1 and linear path for each subaccount) and for other non-pathological layouts, you could let your computer run for a couple of hours and retrieve all your privkeys, because the depths of the branches (including branches that have keys that were never active on the blockchain) would be quite small.

I guess a couple of hours will not cut it. Even if you have an UTXO indexed by keys (that is not even the case for the Satoshi client), it is still prohibitive to scan 2^32 possible generated keys. I believe that you either store what much smaller subset was potentially used, or you can not practically reconstruct the set of keys used, which defeats a purpose of the proposal, that is not to have the need of regular backups.

Where does the 2^32 figure come from? I thought that we're talking about a user who has a backup of the master node, and he just needs to scan his subaccount (depth 1) branches to a reasonable depth (say 10000 or 100000 or 1000000 payment addresses in each subaccount, assuming that the user didn't have more than 1 million customers). Why would such a task take 2^32 time?

[grau]

Where does the 2^32 figure come from?

The proposal does not require consecutive generation of the keys but defines a 32 bit integer as index.

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.

An answer could be: re-use keys. This reduces privacy, but it does not have to be without prior warning: e.g. the client could warn if 90% of key interval is used that the interval should be increased and wallet backup created to avoid reduced privacy as pool exhausted.

I see that the look ahead scan you describe would also practically work (provided increasing not random indices are used), but like the maximum better because it supports the use case of an audit as the serialized key would provide the set of potentially used keys without heuristics involving the block chain content.

[iddo]

Where does the 2^32 figure come from?

The proposal does not require consecutive generation of the keys but defines a 32 bit integer as index.

Sure, but I was talking about the default wallet layout, with consecutive indices (1,2,3,...) for each subaccount.
And I believe that other layouts that users might choose to use would be just as easy to scan.

[grau]

Where does the 2^32 figure come from?

The proposal does not require consecutive generation of the keys but defines a 32 bit integer as index.

Sure, but I was talking about the default wallet layout, with consecutive indices (1,2,3,...) for each subaccount.
And I believe that other layouts that users might choose to use would be just as easy to scan.

Keys generated within a single sub account might also use any random index.

[thanke]

Scenario is this: Server A is holding (K_par,c_par). Server B is being set-up in a different location and is supposed to hold (K_i,c_i). All chaincodes are to be kept secret by the servers holding them, i.e. c_par shall only be known to A (not B) and c_i shall only be known to A and B (no third party). It is irrelevant here who knows K_par and K_i. So B does not derive anything itself. Instead, A does the derivation of (K_i,c_i) and sends the result to B. Of course, the communication of A to B must be authenticated. The point is that on top of that at least c_i must (in the general case) be sent in encrypted form.

So in this scenario, why wouldn't you need to send c_i in encrypted form with your proposal?

In the scenario itself you always need to send c_i, and if you send c_i then it has to be encrypted. I am assuming that the scenario above has been completed and, at a later time, A wants to establish a second tree of pubkeys (for a different purpose, or update). First of all, I made a mistake in my proposal. It should be

Code:

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

so neither of IL,ci=IR depends on Kpar. Let's assume multiplicative derivation, i.e. K_i=I_L*K_par.
In the above scenario I forgot to say that B knows "his" I_L, i.e. the I_L for which K_i=I_L*K_par. This implies that B knows K_par (before, I said this was irrelevant - its not). In fact, I assume K_par is allowed to be public. With this proposal, A creates a new K'_par and sends it to B, and B computes K'_i=I_L*K'_par, re-using his I_L. We do not need an encryption simply because c_i is not re-transmitted, only K'_par is. And I argue that K'_par does not need to be encrypted.

[grau]

The time point a key was created would (if serialized) also greatly aid the reconstruction of the wallet since it would reduce the scan to blocks after that time point.

[thanke]

I expect additive and multiplicative derivation to be equivalent in all "theoretical" aspects of security and anonymity. By "theoretical" I mean disregarding timing attacks, complexity, etc.

Maybe this was too fast. If we re-use multipliers with different pubkeys there seems to be a difference. Consider

Code:

K_i=I_L*K_par, K'_i=I_L*K'_par

vs

Code:

K_i=I_L*G+K_par, K'_i=I_L*G+K'_par

Assume all these pubkeys appear on the blockchain. By computing all differences of all pairs of pubkeys on the blockchain an attacker who does not know I_L can link the pair (K_i,K'_i) to (K_par,K'_par) in the second scheme because K_i-K'_i=K_par-K'_par, but not in the first scheme where K_i-K'_i=I_L*(K_par-K'_par).

[Pieter Wuille]

Keys generated within a single sub account might also use any random index.

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

[etotheipi]

Keys generated within a single sub account might also use any random index.

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

grau, I think the part you are missing is that there is a "convention" tied in with BIP 32.  You could do arbitrary things with BIP 32, and use key gaps of 1,000,000 keys, or use arbitrary 32-byte strings for your child indices, or go deeper than three levels.

But a "standard" implementation of BIP 32 will not do that.  BIP 32 specifies a set of tools that let you do all these arbitrarily complex things, but also describes a convention that avoids the problems you are talking about.  Don't skip wallets, don't use arbitrary 32-byte IDs, don't go past level 3.  If you violate any of these things, you won't be compatible with other implementations of BIP 32, and you'll be forced to address all the problems you are bringing up.  

Look at BIP 32 as a flexible, extensible language for addresses tress and also a prescription for using that is generally accepted.  By generally accepted, I mean that if you follow this prescription, you should be able to import your root private key into Armory, Bitcoin-Qt, Electrum, Multibit, etc, and it will work.  

EDIT: But the simplicity and flexibility of the design allows for us to expand into more complicated things, later, or for devs to do their own "proprietary" deviation of this prescription, and not have to come up with a whole new deterministic wallet algorithm (if they don't mind being incompatible with other apps). 

[grau]

Keys generated within a single sub account might also use any random index.

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

grau, I think the part you are missing is that there is a "convention" tied in with BIP 32. 

I think the proposal misses to make these conventions explicit, and I tried to point out what problems this imposes. In fact I would want to go further, not calling them conventions but be explicit part of the "standard".

The suggestions I made would put further limits on how the proposal is used for the sake of better scan performance and simpler backup procedures.

[CIYAM]

This does strike me as heading towards "over-engineering" - I think the simpler it can be kept the better.

Great designs *allow* for extension but don't try and be everything to everyone all at once.

[Pieter Wuille]

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