Implement gap detection for deterministic wallets #8689

The minimal HD wallet implementation (#8035) changes the derivation scheme for new keys from random to deterministic. This guarantees that an old backup will be able to recreate all keys, and no money can be lost. However, recovery in this case is not trivial, as the wallet will not automatically "look forward" to see if future keys are being used.

The suggestion is to implement a "gap limit" as is called in other BIP32 derived standard, simply reusing the existing keypool. Whenever a key from the keypool is used in a received transaction, we should automatically mark it as used, and if possible replenish.

One difficulty is encrypted wallets. We are unable to replenish the keypool in case the wallet is encrypted. Options to deal with this are:

• Only warn the user in some way, that he may need to unlock the wallet and -rescan (doesn't play well with pruning).
• Stop syncing after the number of keys drops below a configurable number (the gap limit). This means no rescanning is needed, but it may be very annoying if there is a lot of chain to sync.
• Stop syncing the wallet but continue otherwise. This depends on having the wallet sync be made entirely independent from the node's sync (see discussion in http://www.erisian.com.au/meetbot/bitcoin-core-dev/2016/bitcoin-core-dev.2016-09-08-18.59.log.html), and also doesn't play well with pruning.
• Switch to non-hardered derivation at the last level of the path, allowing the computation of new keys without access to the encrypted key material.

For what it is worth, the standard gap limit is 20 across most implementations.

[...] Whenever a key from the keypool is used in a received transaction, we should automatically mark it as used, and if possible replenish.

I agree, we should do this. We already replenish the keypool after getting a key from the pool, though only in unencrypted wallets.

But I see significant issues regarding implementation of a "gap limit". Lets assume we would follow the BIP44 gap limit of 20 keys and someone does a restore of a HD wallet.dat backup created right after the creation of the wallet. We assume the seed in this wallet had received and sent plenty of transactions.

If we would reconstruct the transactions with a gap limit of 20, it would require plenty of rescans down to the blockheight where BIP32 was introduced (or down to the merge date of #8035). Performs utterly bad in conjunctions with pruning.

And if a user could wait a couple of days (could easily happen with a 1000tx+ wallet) until this process has completed, there are serious risks that some funds could not be reconstructed.

I guess we can also assume, if someone recovers from a backup, he or she very likely are going to sweep his funds to a new wallet (security aspect). Failed reconstruction of keys can result in permanent loss.

What if she or he had call more the twenty times getnewaddress without actually giving away these addresses but afterwards gave away some of the 20+ addresses which then had been used to receive coins (or maybe someone did click 20+ times on "receive coins" in the GUI).

I think we should clearly distinct between "import/reconstruct" and "normal operation". It doesn't hurt if we check against the keypool when we receive a transaction. But in general, the wallet does well know, when it did generate a seed and when it did use an existing, imported seed in order to generate the keypool.

Importing should result in a custom process to avoid lost funds. Also, we should and probably must ask the user for some additional information and warn him appropriately. Most users think restoring a wallet with a seed/xpriv will "reconstruct everything". What if they have used the seed in a different wallet using a different derivation scheme (like BIP44). They naively going to assume that these funds will be reconstructed and maybe sweep to a new wallet and throw away the "old backup".

TLTR?

1. I think we should clearly distinct between import/recover and normal operations.
2. We must warn/inform users when reconstructing fund for possible missed keys.
3. We should ask the user for some basic informations about the wallet size (gap limit) in order to reconstruct faster.
4. Reconstruction should result in using very large (1000+) lookup-windows and large gap limits, we should release(remove) the unused keys minus the gap limit at the upper end afterwards

[...] Whenever a key from the keypool is used in a received transaction, we should automatically mark it as used, and if possible replenish.

I agree, we should do this. We already replenish the keypool after getting a key from the pool, though only in unencrypted wallets.

We replenish the keypool after explicitly requesting a new key from it. This issue is about also doing that when we simply receive a transaction to a key from the keypool. AFAIK we do not mark such keys as used.

We replenish the keypool after explicitly requesting a new key from it. This issue is about also doing that when we simply receive a transaction to a key from the keypool. AFAIK we do not mark such keys as used.

Oh yes. I missed that point. Yes, we should do this. Though, as I already stated, I'm not sure if we should naively allow using an imported seed without running a custom reconstruction process in advanced (detecting key in the keypool used in incoming transactions smells after a hack).

Though, as I already stated, I'm not sure if we should naively allow using an imported seed without running a custom reconstruction process in advanced (detecting key in the keypool used in incoming transactions smells after a hack).

This is not about importing. It's about restoring a wallet.dat file from backup, and despite having a deterministic wallet, not recovering your incoming transactions made after the backup.

Right, this also happens when your server restores the disk to the state of a few days ago.

We should probably also mark any keys "in between" as used. I.e. any keys with a hdcounter less than the maximum hdcounter.

It's about restoring a wallet.dat file from backup, and despite having a deterministic wallet, not recovering your incoming transactions.

It is indeed hard to detect if the user is using a backup wallet.dat that was previously used in a newer version. Though we could recommend reconstruction if the wallet bestblock lacks significant behind the chain tip.

But I agree with @sipa, we should implement detecting keypool keys during the incoming transaction process.

It is indeed hard to detect if the user is using a backup wallet.dat that was previously used in a newer version.

What are you talking about? This has nothing to do with newer versions. It will very normally occur whenever you recover a backup.

Yes. I agree. I just meant that If you recover a wallet.dat there is a chance of detecting that you are using an "older" wallet.dat by comparing the wallets bestblock against the chaintip (but right, your node could be out-of-sync as well) which could lead to inform the user about doing an import/reconstruct (once we have a such feature).

Also agree with @MarcoFalke about marking the keys "in between" as used.

Is possible to make a wallet which checks another wallet If synchronization coincides before and after that wallet it is determined

Implemented mostly by #11022.