Merge bitcoin/bitcoin#23304: wallet: Derive inactive HD chains in additional places

c4d76c6faa3adf06f192649e169ca860ce420d30 tests: Tests for inactive HD chains (Andrew Chow)
8077862c5e8a3ed501f0baabc33536eb16922ceb wallet: Refactor TopUp to be able to top up inactive chains too (Andrew Chow)
70134eb34f58f0c572e7c3775e292d408f03b5ab wallet: Properly set hd chain counters when loading (Andrew Chow)
961b9e4e40019a87eaa11c8a9c3305870f7a6d75 wallet: Parse hdKeypath if key_origin is not available (Andrew Chow)
0652ee73ec880a66ec88bde007ee03c0b9d1b074 Add size check on meta.key_origin.path (Rob Fielding)

Pull request description:

  Currently inactive HD chains are only derived from at the time a key in that chain is found to have been used. However, at that time, the wallet may not be able to derive keys (e.g. it is locked). Currently we would just move on and not derive any new keys, however this could result in missing funds.

  This PR resolves this problem by adding memory only variables to `CHDChain` which track the highest known index. `TopUp` is modified to always try to top up the inactive HD chains, and this process will use the new variables to determine how much to top up. In this way, after an encrypted wallet is unlocked, the inactive HD chains will be topped up and hopefully funds will not be missed.

  Note that because these variables are not persisted to disk (because `CHDChain`s for inactive HD chains are not written to disk), if an encrypted wallet is not unlocked in the same session as a key from an inactive chain is found to be used, then it will not be topped up later unless more keys are found.

  Additionally, wallets which do not have upgraded key metadata will not derive any keys from inactive HD chains. This is resolved by using the derivation path string in `CKeyMetadata.hdKeypath` to determine what indexes to derive.

ACKs for top commit:
  laanwj:
    Code review ACK c4d76c6faa3adf06f192649e169ca860ce420d30

Tree-SHA512: b2b572ad7f1b1b2847edece09f7583543d63997e18ae32764e5a27ad608dd64b9bdb2d84ea27137894e986a8e82f047a3dba9c8015b74f5f179961911f0c4095

7 files changed, 234 insertions, 55 deletions

diff --git a/src/wallet/scriptpubkeyman.cpp b/src/wallet/scriptpubkeyman.cpp
index 53f7b773b4..8633e7c62c 100644
--- a/src/wallet/scriptpubkeyman.cpp
+++ b/src/wallet/scriptpubkeyman.cpp
@@ -322,8 +322,6 @@ bool LegacyScriptPubKeyMan::TopUpInactiveHDChain(const CKeyID seed_id, int64_t i
 {
     LOCK(cs_KeyStore);
 
-    if (m_storage.IsLocked()) return false;
-
     auto it = m_inactive_hd_chains.find(seed_id);
     if (it == m_inactive_hd_chains.end()) {
         return false;
@@ -331,27 +329,14 @@ bool LegacyScriptPubKeyMan::TopUpInactiveHDChain(const CKeyID seed_id, int64_t i
 
     CHDChain& chain = it->second;
 
-    // Top up key pool
-    int64_t target_size = std::max(gArgs.GetIntArg("-keypool", DEFAULT_KEYPOOL_SIZE), (int64_t) 1);
-
-    // "size" of the keypools. Not really the size, actually the difference between index and the chain counter
-    // Since chain counter is 1 based and index is 0 based, one of them needs to be offset by 1.
-    int64_t kp_size = (internal ? chain.nInternalChainCounter : chain.nExternalChainCounter) - (index + 1);
+    if (internal) {
+        chain.m_next_internal_index = std::max(chain.m_next_internal_index, index + 1);
+    } else {
+        chain.m_next_external_index = std::max(chain.m_next_external_index, index + 1);
+    }
 
-    // make sure the keypool fits the user-selected target (-keypool)
-    int64_t missing = std::max(target_size - kp_size, (int64_t) 0);
+    TopUpChain(chain, 0);
 
-    if (missing > 0) {
-        WalletBatch batch(m_storage.GetDatabase());
-        for (int64_t i = missing; i > 0; --i) {
-            GenerateNewKey(batch, chain, internal);
-        }
-        if (internal) {
-            WalletLogPrintf("inactive seed with id %s added %d internal keys\n", HexStr(seed_id), missing);
-        } else {
-            WalletLogPrintf("inactive seed with id %s added %d keys\n", HexStr(seed_id), missing);
-        }
-    }
     return true;
 }
 
@@ -383,11 +368,26 @@ std::vector<WalletDestination> LegacyScriptPubKeyMan::MarkUnusedAddresses(const
         if (it != mapKeyMetadata.end()){
             CKeyMetadata meta = it->second;
             if (!meta.hd_seed_id.IsNull() && meta.hd_seed_id != m_hd_chain.seed_id) {
-                bool internal = (meta.key_origin.path[1] & ~BIP32_HARDENED_KEY_LIMIT) != 0;
-                int64_t index = meta.key_origin.path[2] & ~BIP32_HARDENED_KEY_LIMIT;
-
-                if (!TopUpInactiveHDChain(meta.hd_seed_id, index, internal)) {
-                    WalletLogPrintf("%s: Adding inactive seed keys failed\n", __func__);
+                std::vector<uint32_t> path;
+                if (meta.has_key_origin) {
+                    path = meta.key_origin.path;
+                } else if (!ParseHDKeypath(meta.hdKeypath, path)) {
+                    WalletLogPrintf("%s: Adding inactive seed keys failed, invalid hdKeypath: %s\n",
+                                    __func__,
+                                    meta.hdKeypath);
+                }
+                if (path.size() != 3) {
+                    WalletLogPrintf("%s: Adding inactive seed keys failed, invalid path size: %d, has_key_origin: %s\n",
+                                    __func__,
+                                    path.size(),
+                                    meta.has_key_origin);
+                } else {
+                    bool internal = (path[1] & ~BIP32_HARDENED_KEY_LIMIT) != 0;
+                    int64_t index = path[2] & ~BIP32_HARDENED_KEY_LIMIT;
+
+                    if (!TopUpInactiveHDChain(meta.hd_seed_id, index, internal)) {
+                        WalletLogPrintf("%s: Adding inactive seed keys failed\n", __func__);
+                    }
                 }
             }
         }
@@ -1265,44 +1265,69 @@ bool LegacyScriptPubKeyMan::TopUp(unsigned int kpSize)
     if (!CanGenerateKeys()) {
         return false;
     }
-    {
-        LOCK(cs_KeyStore);
 
-        if (m_storage.IsLocked()) return false;
+    if (!TopUpChain(m_hd_chain, kpSize)) {
+        return false;
+    }
+    for (auto& [chain_id, chain] : m_inactive_hd_chains) {
+        if (!TopUpChain(chain, kpSize)) {
+            return false;
+        }
+    }
+    NotifyCanGetAddressesChanged();
+    return true;
+}
 
-        // Top up key pool
-        unsigned int nTargetSize;
-        if (kpSize > 0)
-            nTargetSize = kpSize;
-        else
-            nTargetSize = std::max(gArgs.GetIntArg("-keypool", DEFAULT_KEYPOOL_SIZE), (int64_t) 0);
+bool LegacyScriptPubKeyMan::TopUpChain(CHDChain& chain, unsigned int kpSize)
+{
+    LOCK(cs_KeyStore);
 
-        // count amount of available keys (internal, external)
-        // make sure the keypool of external and internal keys fits the user selected target (-keypool)
-        int64_t missingExternal = std::max(std::max((int64_t) nTargetSize, (int64_t) 1) - (int64_t)setExternalKeyPool.size(), (int64_t) 0);
-        int64_t missingInternal = std::max(std::max((int64_t) nTargetSize, (int64_t) 1) - (int64_t)setInternalKeyPool.size(), (int64_t) 0);
+    if (m_storage.IsLocked()) return false;
 
-        if (!IsHDEnabled() || !m_storage.CanSupportFeature(FEATURE_HD_SPLIT))
-        {
-            // don't create extra internal keys
-            missingInternal = 0;
+    // Top up key pool
+    unsigned int nTargetSize;
+    if (kpSize > 0) {
+        nTargetSize = kpSize;
+    } else {
+        nTargetSize = std::max(gArgs.GetIntArg("-keypool", DEFAULT_KEYPOOL_SIZE), int64_t{0});
+    }
+    int64_t target = std::max((int64_t) nTargetSize, int64_t{1});
+
+    // count amount of available keys (internal, external)
+    // make sure the keypool of external and internal keys fits the user selected target (-keypool)
+    int64_t missingExternal;
+    int64_t missingInternal;
+    if (chain == m_hd_chain) {
+        missingExternal = std::max(target - (int64_t)setExternalKeyPool.size(), int64_t{0});
+        missingInternal = std::max(target - (int64_t)setInternalKeyPool.size(), int64_t{0});
+    } else {
+        missingExternal = std::max(target - (chain.nExternalChainCounter - chain.m_next_external_index), int64_t{0});
+        missingInternal = std::max(target - (chain.nInternalChainCounter - chain.m_next_internal_index), int64_t{0});
+    }
+
+    if (!IsHDEnabled() || !m_storage.CanSupportFeature(FEATURE_HD_SPLIT)) {
+        // don't create extra internal keys
+        missingInternal = 0;
+    }
+    bool internal = false;
+    WalletBatch batch(m_storage.GetDatabase());
+    for (int64_t i = missingInternal + missingExternal; i--;) {
+        if (i < missingInternal) {
+            internal = true;
         }
-        bool internal = false;
-        WalletBatch batch(m_storage.GetDatabase());
-        for (int64_t i = missingInternal + missingExternal; i--;)
-        {
-            if (i < missingInternal) {
-                internal = true;
-            }
 
-            CPubKey pubkey(GenerateNewKey(batch, m_hd_chain, internal));
+        CPubKey pubkey(GenerateNewKey(batch, chain, internal));
+        if (chain == m_hd_chain) {
             AddKeypoolPubkeyWithDB(pubkey, internal, batch);
         }
-        if (missingInternal + missingExternal > 0) {
+    }
+    if (missingInternal + missingExternal > 0) {
+        if (chain == m_hd_chain) {
             WalletLogPrintf("keypool added %d keys (%d internal), size=%u (%u internal)\n", missingInternal + missingExternal, missingInternal, setInternalKeyPool.size() + setExternalKeyPool.size() + set_pre_split_keypool.size(), setInternalKeyPool.size());
+        } else {
+            WalletLogPrintf("inactive seed with id %s added %d external keys, %d internal keys\n", HexStr(chain.seed_id), missingExternal, missingInternal);
         }
     }
-    NotifyCanGetAddressesChanged();
     return true;
 }
 
diff --git a/src/wallet/scriptpubkeyman.h b/src/wallet/scriptpubkeyman.h
index 6eda133771..ad924791af 100644
--- a/src/wallet/scriptpubkeyman.h
+++ b/src/wallet/scriptpubkeyman.h
@@ -355,6 +355,7 @@ private:
      */
     bool TopUpInactiveHDChain(const CKeyID seed_id, int64_t index, bool internal);
 
+    bool TopUpChain(CHDChain& chain, unsigned int size);
 public:
     using ScriptPubKeyMan::ScriptPubKeyMan;
 
diff --git a/src/wallet/walletdb.cpp b/src/wallet/walletdb.cpp
index 2d88b07146..6e100524a4 100644
--- a/src/wallet/walletdb.cpp
+++ b/src/wallet/walletdb.cpp
@@ -557,9 +557,9 @@ ReadKeyValue(CWallet* pwallet, CDataStream& ssKey, CDataStream& ssValue,
                 }
                 if (internal) {
                     chain.nVersion = CHDChain::VERSION_HD_CHAIN_SPLIT;
-                    chain.nInternalChainCounter = std::max(chain.nInternalChainCounter, index);
+                    chain.nInternalChainCounter = std::max(chain.nInternalChainCounter, index + 1);
                 } else {
-                    chain.nExternalChainCounter = std::max(chain.nExternalChainCounter, index);
+                    chain.nExternalChainCounter = std::max(chain.nExternalChainCounter, index + 1);
                 }
             }
         } else if (strType == DBKeys::WATCHMETA) {
diff --git a/src/wallet/walletdb.h b/src/wallet/walletdb.h
index 760019e76b..3dfe781d56 100644
--- a/src/wallet/walletdb.h
+++ b/src/wallet/walletdb.h
@@ -93,6 +93,8 @@ public:
     uint32_t nExternalChainCounter;
     uint32_t nInternalChainCounter;
     CKeyID seed_id; //!< seed hash160
+    int64_t m_next_external_index{0}; // Next index in the keypool to be used. Memory only.
+    int64_t m_next_internal_index{0}; // Next index in the keypool to be used. Memory only.
 
     static const int VERSION_HD_BASE        = 1;
     static const int VERSION_HD_CHAIN_SPLIT = 2;
diff --git a/test/functional/test_framework/test_node.py b/test/functional/test_framework/test_node.py
index 289e83579b..e56d4aa492 100755
--- a/test/functional/test_framework/test_node.py
+++ b/test/functional/test_framework/test_node.py
@@ -743,6 +743,9 @@ class RPCOverloadWrapper():
     def __getattr__(self, name):
         return getattr(self.rpc, name)
 
+    def createwallet_passthrough(self, *args, **kwargs):
+        return self.__getattr__("createwallet")(*args, **kwargs)
+
     def createwallet(self, wallet_name, disable_private_keys=None, blank=None, passphrase='', avoid_reuse=None, descriptors=None, load_on_startup=None, external_signer=None):
         if descriptors is None:
             descriptors = self.descriptors
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index 516e8be638..d15edcedd2 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -281,6 +281,7 @@ BASE_SCRIPTS = [
     'wallet_send.py --descriptors',
     'wallet_create_tx.py --descriptors',
     'wallet_taproot.py',
+    'wallet_inactive_hdchains.py',
     'p2p_fingerprint.py',
     'feature_uacomment.py',
     'feature_init.py',
diff --git a/test/functional/wallet_inactive_hdchains.py b/test/functional/wallet_inactive_hdchains.py
new file mode 100755
index 0000000000..e1dad00876
--- /dev/null
+++ b/test/functional/wallet_inactive_hdchains.py
@@ -0,0 +1,147 @@
+#!/usr/bin/env python3
+# Copyright (c) 2021 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""
+Test Inactive HD Chains.
+"""
+import os
+import shutil
+import time
+
+from test_framework.authproxy import JSONRPCException
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.wallet_util import (
+    get_generate_key,
+)
+
+
+class InactiveHDChainsTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.setup_clean_chain = True
+        self.num_nodes = 2
+        self.extra_args = [["-keypool=10"], ["-nowallet", "-keypool=10"]]
+
+    def skip_test_if_missing_module(self):
+        self.skip_if_no_wallet()
+        self.skip_if_no_bdb()
+        self.skip_if_no_previous_releases()
+
+    def setup_nodes(self):
+        self.add_nodes(self.num_nodes, extra_args=self.extra_args, versions=[
+            None,
+            170200, # 0.17.2 Does not have the key metadata upgrade
+        ])
+
+        self.start_nodes()
+        self.init_wallet(node=0)
+
+    def prepare_wallets(self, wallet_basename, encrypt=False):
+        self.nodes[0].createwallet(wallet_name=f"{wallet_basename}_base", descriptors=False, blank=True)
+        self.nodes[0].createwallet(wallet_name=f"{wallet_basename}_test", descriptors=False, blank=True)
+        base_wallet = self.nodes[0].get_wallet_rpc(f"{wallet_basename}_base")
+        test_wallet = self.nodes[0].get_wallet_rpc(f"{wallet_basename}_test")
+
+        # Setup both wallets with the same HD seed
+        seed = get_generate_key()
+        base_wallet.sethdseed(True, seed.privkey)
+        test_wallet.sethdseed(True, seed.privkey)
+
+        if encrypt:
+            # Encrypting will generate a new HD seed and flush the keypool
+            test_wallet.encryptwallet("pass")
+        else:
+            # Generate a new HD seed on the test wallet
+            test_wallet.sethdseed()
+
+        return base_wallet, test_wallet
+
+    def do_inactive_test(self, base_wallet, test_wallet, encrypt=False):
+        default = self.nodes[0].get_wallet_rpc(self.default_wallet_name)
+
+        # The first address should be known by both wallets.
+        addr1 = base_wallet.getnewaddress()
+        assert test_wallet.getaddressinfo(addr1)["ismine"]
+        # The address at index 9 is the first address that the test wallet will not know initially
+        for _ in range(0, 9):
+            base_wallet.getnewaddress()
+        addr2 = base_wallet.getnewaddress()
+        assert not test_wallet.getaddressinfo(addr2)["ismine"]
+
+        # Send to first address on the old seed
+        txid = default.sendtoaddress(addr1, 10)
+        self.generate(self.nodes[0], 1)
+
+        # Wait for the test wallet to see the transaction
+        while True:
+            try:
+                test_wallet.gettransaction(txid)
+                break
+            except JSONRPCException:
+                time.sleep(0.1)
+
+        if encrypt:
+            # The test wallet will not be able to generate the topped up keypool
+            # until it is unlocked. So it still should not know about the second address
+            assert not test_wallet.getaddressinfo(addr2)["ismine"]
+            test_wallet.walletpassphrase("pass", 1)
+
+        # The test wallet should now know about the second address as it
+        # should have generated it in the inactive chain's keypool
+        assert test_wallet.getaddressinfo(addr2)["ismine"]
+
+        # Send to second address on the old seed
+        txid = default.sendtoaddress(addr2, 10)
+        self.generate(self.nodes[0], 1)
+        test_wallet.gettransaction(txid)
+
+    def test_basic(self):
+        self.log.info("Test basic case for inactive HD chains")
+        self.do_inactive_test(*self.prepare_wallets("basic"))
+
+    def test_encrypted_wallet(self):
+        self.log.info("Test inactive HD chains when wallet is encrypted")
+        self.do_inactive_test(*self.prepare_wallets("enc", encrypt=True), encrypt=True)
+
+    def test_without_upgraded_keymeta(self):
+        # Test that it is possible to top up inactive hd chains even if there is no key origin
+        # in CKeyMetadata. This tests for the segfault reported in
+        # https://github.com/bitcoin/bitcoin/issues/21605
+        self.log.info("Test that topping up inactive HD chains does not need upgraded key origin")
+
+        self.nodes[0].createwallet(wallet_name="keymeta_base", descriptors=False, blank=True)
+        # Createwallet is overridden in the test framework so that the descriptor option can be filled
+        # depending on the test's cli args. However we don't want to do that when using old nodes that
+        # do not support descriptors. So we use the createwallet_passthrough function.
+        self.nodes[1].createwallet_passthrough(wallet_name="keymeta_test")
+        base_wallet = self.nodes[0].get_wallet_rpc("keymeta_base")
+        test_wallet = self.nodes[1].get_wallet_rpc("keymeta_test")
+
+        # Setup both wallets with the same HD seed
+        seed = get_generate_key()
+        base_wallet.sethdseed(True, seed.privkey)
+        test_wallet.sethdseed(True, seed.privkey)
+
+        # Encrypting will generate a new HD seed and flush the keypool
+        test_wallet.encryptwallet("pass")
+
+        # Copy test wallet to node 0
+        test_wallet.unloadwallet()
+        test_wallet_dir = os.path.join(self.nodes[1].datadir, "regtest/wallets/keymeta_test")
+        new_test_wallet_dir = os.path.join(self.nodes[0].datadir, "regtest/wallets/keymeta_test")
+        shutil.copytree(test_wallet_dir, new_test_wallet_dir)
+        self.nodes[0].loadwallet("keymeta_test")
+        test_wallet = self.nodes[0].get_wallet_rpc("keymeta_test")
+
+        self.do_inactive_test(base_wallet, test_wallet, encrypt=True)
+
+    def run_test(self):
+        self.generate(self.nodes[0], 101)
+
+        self.test_basic()
+        self.test_encrypted_wallet()
+        self.test_without_upgraded_keymeta()
+
+
+if __name__ == '__main__':
+    InactiveHDChainsTest().main()