Merge #18836: wallet: upgradewallet fixes and additional tests

5f9c0b6360215636cfa62a70d3a70f1feb3977ab wallet: Remove -upgradewallet from dummywallet (MarcoFalke)
a314271f08215feba53ead27096ac7fda34acb3c test: Remove unused wallet.dat (MarcoFalke)
bf7635963c03203e7189ddaa56c6b086a0108cbf tests: Test specific upgradewallet scenarios and that upgrades work (Andrew Chow)
4b418a9decc3e855ee4b0bbf9e61121c8e9904e5 test: Add test_framework/bdb.py module for inspecting bdb files (Andrew Chow)
092fc434854f881330771a93a1280ac67b1d3549 tests: Add a sha256sum_file function to util (Andrew Chow)
0bd995aa19be65b0dd23df1df571c71428c2bc32 wallet: upgrade the CHDChain version number when upgrading to split hd (Andrew Chow)
8e32e1c41c995e832e643f605d35a7aa112837e6 wallet: remove nWalletMaxVersion (Andrew Chow)
bd7398cc6258c258e9f4411c50630ec4a552341b wallet: have ScriptPubKeyMan::Upgrade check against the new version (Andrew Chow)
5f720544f34dedf75b063b962845fa8eca604514 wallet: Add GetClosestWalletFeature function (Andrew Chow)
842ae3842df489f1b8d68e67a234788966218184 wallet: Add utility method for CanSupportFeature (Andrew Chow)

Pull request description:

  This PR cleans up the wallet upgrade mechanism a bit, fixes some probably bugs, and adds more test cases.

  The `nWalletMaxVersion` member variable has been removed as it made `CanSupportFeature` unintuitive and was causing a couple of bugs. The reason this was introduced originally was to allow a wallet upgrade to only occur when the new feature is first used. While this makes sense for the old `-upgradewallet` option, for an RPC, this does not quite make sense. It's more intuitive for an upgrade to occur if possible if the `upgradewallet` RPC is used as that's an explicit request to upgrade a particular wallet to a newer version. `nWalletMaxVersion` was only relevant for upgrades to `FEATURE_WALLETCRYPT` and `FEATURE_COMPRPUBKEY` both of which are incredibly old features. So for such wallets, the behavior of `upgradewallet` will be that the feature is enabled immediately without the wallet needing to be encrypted at that time (note that `FEATURE_WALLETCRYPT` indicates support for encryption, not that the wallet is encrypted) or for a new key to be generated.

  `CanSupportFeature` would previously indicate whether we could upgrade to `nWalletMaxVersion` not just whether the current wallet version supported a feature. While this property was being used to determine whether we should upgrade to HD and HD chain split, it was also causing a few bugs. Determining whether we should upgrade to HD or HD chain split is resolved by passing into `ScriptPubKeyMan::Upgrade` the version we are upgrading to and checking against that. By removing `nWalletMaxVersion` we also fix a bug where you could upgrade to HD chain split without the pre-split keypool.

  `nWalletMaxVersion` was also the version that was being reported by `getwalletinfo` which meant that the version reported was not always consistent across restarts as it depended on whether `upgradewallet` was used. Additionally to make the wallet versions consistent with actually supported versions, instead of just setting the wallet version to whatever is given to `upgradewallet`, we normalize the version number to the closest supported version number. For example, if given 150000, we would store and report 139900.

  Another bug where CHDChain was not being upgraded to the version supporting HD chain split is also fixed by this PR.

  Lastly several more tests have been added. Some refactoring to the test was made to make these tests easier. These tests check specific upgrading scenarios, such as from non-HD (version 60000) to HD to pre-split keypool. Although not specifically related to `upgradewallet`, `UpgradeKeyMetadata` is now being tested too.

  Part of the new tests is checking that the wallet files are identical before and after failed upgrades. To facilitate this, a utility function `sha256sum_file` has been added. Another part of the tests is to examine the wallet file itself to ensure that the records in the wallet.dat file have been correctly modified. So a new `bdb.py` module has been added to deserialize the BDB db of the wallet.dat file. This format isn't explicitly documented anywhere, but the code and comments in BDB's source code in file `dbinc/db_page.h` describe it. This module just dumps all of the fields into a dict.

ACKs for top commit:
  MarcoFalke:
    approach ACK 5f9c0b6360
  laanwj:
    Code review ACK 5f9c0b6360215636cfa62a70d3a70f1feb3977ab
  jonatack:
    ACK 5f9c0b6360215636cfa62a70d3a70f1feb3977ab, approach seems fine, code review, only skimmed the test changes but they look well done, rebased on current master, debug built and verified the `wallet_upgradewallet.py` test runs green both before and after running `test/get_previous_releases.py -b v0.19.1 v0.18.1 v0.17.2 v0.16.3 v0.15.2`

Tree-SHA512: 7c4ebf420850d596a586cb6dd7f2ef39c6477847d12d105fcd362abb07f2a8aa4f7afc5bfd36cbc8b8c72fcdd1de8d2d3f16ad8e8ba736b6f4f31f133fe5feba

2 files changed, 161 insertions, 0 deletions

diff --git a/test/functional/test_framework/bdb.py b/test/functional/test_framework/bdb.py
new file mode 100644
index 0000000000..9de358aa0a
--- /dev/null
+++ b/test/functional/test_framework/bdb.py
@@ -0,0 +1,152 @@
+#!/usr/bin/env python3
+# Copyright (c) 2020 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""
+Utilities for working directly with the wallet's BDB database file
+
+This is specific to the configuration of BDB used in this project:
+    - pagesize: 4096 bytes
+    - Outer database contains single subdatabase named 'main'
+    - btree
+    - btree leaf pages
+
+Each key-value pair is two entries in a btree leaf. The first is the key, the one that follows
+is the value. And so on. Note that the entry data is itself not in the correct order. Instead
+entry offsets are stored in the correct order and those offsets are needed to then retrieve
+the data itself.
+
+Page format can be found in BDB source code dbinc/db_page.h
+This only implements the deserialization of btree metadata pages and normal btree pages. Overflow
+pages are not implemented but may be needed in the future if dealing with wallets with large
+transactions.
+
+`db_dump -da wallet.dat` is useful to see the data in a wallet.dat BDB file
+"""
+
+import binascii
+import struct
+
+# Important constants
+PAGESIZE = 4096
+OUTER_META_PAGE = 0
+INNER_META_PAGE = 2
+
+# Page type values
+BTREE_INTERNAL = 3
+BTREE_LEAF = 5
+BTREE_META = 9
+
+# Some magic numbers for sanity checking
+BTREE_MAGIC = 0x053162
+DB_VERSION = 9
+
+# Deserializes a leaf page into a dict.
+# Btree internal pages have the same header, for those, return None.
+# For the btree leaf pages, deserialize them and put all the data into a dict
+def dump_leaf_page(data):
+    page_info = {}
+    page_header = data[0:26]
+    _, pgno, prev_pgno, next_pgno, entries, hf_offset, level, pg_type = struct.unpack('QIIIHHBB', page_header)
+    page_info['pgno'] = pgno
+    page_info['prev_pgno'] = prev_pgno
+    page_info['next_pgno'] = next_pgno
+    page_info['entries'] = entries
+    page_info['hf_offset'] = hf_offset
+    page_info['level'] = level
+    page_info['pg_type'] = pg_type
+    page_info['entry_offsets'] = struct.unpack('{}H'.format(entries), data[26:26 + entries * 2])
+    page_info['entries'] = []
+
+    if pg_type == BTREE_INTERNAL:
+        # Skip internal pages. These are the internal nodes of the btree and don't contain anything relevant to us
+        return None
+
+    assert pg_type == BTREE_LEAF, 'A non-btree leaf page has been encountered while dumping leaves'
+
+    for i in range(0, entries):
+        offset = page_info['entry_offsets'][i]
+        entry = {'offset': offset}
+        page_data_header = data[offset:offset + 3]
+        e_len, pg_type = struct.unpack('HB', page_data_header)
+        entry['len'] = e_len
+        entry['pg_type'] = pg_type
+        entry['data'] = data[offset + 3:offset + 3 + e_len]
+        page_info['entries'].append(entry)
+
+    return page_info
+
+# Deserializes a btree metadata page into a dict.
+# Does a simple sanity check on the magic value, type, and version
+def dump_meta_page(page):
+    # metadata page
+    # general metadata
+    metadata = {}
+    meta_page = page[0:72]
+    _, pgno, magic, version, pagesize, encrypt_alg, pg_type, metaflags, _, free, last_pgno, nparts, key_count, record_count, flags, uid = struct.unpack('QIIIIBBBBIIIIII20s', meta_page)
+    metadata['pgno'] = pgno
+    metadata['magic'] = magic
+    metadata['version'] = version
+    metadata['pagesize'] = pagesize
+    metadata['encrypt_alg'] = encrypt_alg
+    metadata['pg_type'] = pg_type
+    metadata['metaflags'] = metaflags
+    metadata['free'] = free
+    metadata['last_pgno'] = last_pgno
+    metadata['nparts'] = nparts
+    metadata['key_count'] = key_count
+    metadata['record_count'] = record_count
+    metadata['flags'] = flags
+    metadata['uid'] = binascii.hexlify(uid)
+
+    assert magic == BTREE_MAGIC, 'bdb magic does not match bdb btree magic'
+    assert pg_type == BTREE_META, 'Metadata page is not a btree metadata page'
+    assert version == DB_VERSION, 'Database too new'
+
+    # btree metadata
+    btree_meta_page = page[72:512]
+    _, minkey, re_len, re_pad, root, _, crypto_magic, _, iv, chksum = struct.unpack('IIIII368sI12s16s20s', btree_meta_page)
+    metadata['minkey'] = minkey
+    metadata['re_len'] = re_len
+    metadata['re_pad'] = re_pad
+    metadata['root'] = root
+    metadata['crypto_magic'] = crypto_magic
+    metadata['iv'] = binascii.hexlify(iv)
+    metadata['chksum'] = binascii.hexlify(chksum)
+    return metadata
+
+# Given the dict from dump_leaf_page, get the key-value pairs and put them into a dict
+def extract_kv_pairs(page_data):
+    out = {}
+    last_key = None
+    for i, entry in enumerate(page_data['entries']):
+        # By virtue of these all being pairs, even number entries are keys, and odd are values
+        if i % 2 == 0:
+            out[entry['data']] = b''
+            last_key = entry['data']
+        else:
+            out[last_key] = entry['data']
+    return out
+
+# Extract the key-value pairs of the BDB file given in filename
+def dump_bdb_kv(filename):
+    # Read in the BDB file and start deserializing it
+    pages = []
+    with open(filename, 'rb') as f:
+        data = f.read(PAGESIZE)
+        while len(data) > 0:
+            pages.append(data)
+            data = f.read(PAGESIZE)
+
+    # Sanity check the meta pages
+    dump_meta_page(pages[OUTER_META_PAGE])
+    dump_meta_page(pages[INNER_META_PAGE])
+
+    # Fetch the kv pairs from the leaf pages
+    kv = {}
+    for i in range(3, len(pages)):
+        info = dump_leaf_page(pages[i])
+        if info is not None:
+            info_kv = extract_kv_pairs(info)
+            kv = {**kv, **info_kv}
+    return kv
diff --git a/test/functional/test_framework/util.py b/test/functional/test_framework/util.py
index 3356f1ab10..62ff5c6e33 100644
--- a/test/functional/test_framework/util.py
+++ b/test/functional/test_framework/util.py
@@ -8,6 +8,7 @@ from base64 import b64encode
 from binascii import unhexlify
 from decimal import Decimal, ROUND_DOWN
 from subprocess import CalledProcessError
+import hashlib
 import inspect
 import json
 import logging
@@ -260,6 +261,14 @@ def wait_until_helper(predicate, *, attempts=float('inf'), timeout=float('inf'),
         raise AssertionError("Predicate {} not true after {} seconds".format(predicate_source, timeout))
     raise RuntimeError('Unreachable')
 
+def sha256sum_file(filename):
+    h = hashlib.sha256()
+    with open(filename, 'rb') as f:
+        d = f.read(4096)
+        while len(d) > 0:
+            h.update(d)
+            d = f.read(4096)
+    return h.digest()
 
 # RPC/P2P connection constants and functions
 ############################################