descriptors: improve descriptor cache and cache xpubs

achow101 commented at 0:20 am on February 25, 2020: member

Improves the descriptor cache by changing it from a std::vector<unsigned char> to a newly introduced DescriptorCache class. Instead of serializing pubkeys and whatever else we would want to cache in a way that may not be backwards compatible, we instead create a DescriptorCache object and populate it. This object contains only an xpub cache. Since the only PubkeyProvider that used the cache is the BIP32PubkeyProvider we just have it store the xpubs instead of the pubkeys. This allows us to have both the parent xpub and the child xpubs in the same container. The map is keyed by KeyOriginInfo.

Sine we are caching CExtPubKeys in DescriptorCache, BIP32PubKeyProviders can use the cached parent xpubs to derive the children if unhardened derivation is used in the last step. This also means that we can still derive the keys for a BIP32PubkeyProvider that has hardened derivation steps. When combined with descriptor wallets, this should allow us to be able to import a descriptor with an xprv and hardened steps and still be able to derive from it. In that sense, this is an alternative to #18163

To test that this works, the tests have been updated to do an additional Expand at the i + 1 position. This expansion is not cached. We then do an ExpandFromCache at i + 1 and use the cache that was produced by the expansion at i. This way, we won’t have the child xpubs for i + 1 but we will have the parent xpubs. So this checks whether the parent xpubs are being stored and can be used to derive the child keys. Descriptors that have a hardened last step are skipped for this part of the test because that will always require private keys.

fanquake added the label Descriptors on Feb 25, 2020

DrahtBot commented at 2:20 am on February 25, 2020: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#16710 (build: Enable -Wsuggest-override if available by hebasto)
#16116 (Avoid unnecessary signing provider copies on descriptor expansion by Empact)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

in src/script/descriptor.h:26 in 13b5266656 outdated

21+
22+public:
23+    DescriptorCache() : m_pos_begin(0) {}
24+    DescriptorCache(int begin_pos) : m_pos_begin(begin_pos) {}
25+    bool CachePubKey(unsigned int cache_pos, const CPubKey& pubkey);
26+    bool GetCachedPubKey(unsigned int global_pos, unsigned int internal_pos, CPubKey& pubkey) const;

Sjors commented at 10:08 am on February 25, 2020:

global_pos and internal_pos could use documentation. Would it make sense to cache all pubkeys (for a given position) in one operation?

Sjors commented at 10:48 am on February 25, 2020: member

Concept ACK.

I’m seeing errors on Travis and locally:

0AssertionError: Unexpected stderr Assertion failed: (fValid), function GetPubKey, file key.cpp, line 185.

in src/script/descriptor.h:25 in 13b5266656 outdated

20+    std::vector<std::vector<CPubKey>> m_pubkey_cache;
21+
22+public:
23+    DescriptorCache() : m_pos_begin(0) {}
24+    DescriptorCache(int begin_pos) : m_pos_begin(begin_pos) {}
25+    bool CachePubKey(unsigned int cache_pos, const CPubKey& pubkey);

instagibbs commented at 1:54 pm on February 25, 2020:

nit: it’s named global_pos in the definition which lines up with GetCachedPubKey

in src/script/descriptor.h:19 in 13b5266656 outdated

12@@ -13,6 +13,18 @@
13 
14 #include <vector>
15 
16+// Cache for pre-computed descriptor things
17+class DescriptorCache {
18+private:
19+    unsigned int m_pos_begin;

instagibbs commented at 1:55 pm on February 25, 2020:

this needs a description as well

instagibbs commented at 4:01 pm on February 25, 2020: member

this is getting importmulti test failures

achow101 force-pushed on Feb 25, 2020

achow101 commented at 8:10 pm on February 25, 2020: member

Fixed the assertion. Travis seems to be seeing a memory leak but I’m having trouble figuring out where that is.

achow101 force-pushed on Feb 26, 2020

achow101 commented at 1:17 am on February 26, 2020: member

I’ve reworked how the caching works to get rid of the global_pos and internal_pos stuff.

Instead of having ExpandHelper go through the cache and find the pubkeys, we pass the cache into the PubkeyProviders and let them do the cache lookups. Since really only BIP32PubkeyProvider uses the cache, we can get rid of the position stuff by having it store only xpubs in a map. So for all derived keys, we store their KeyOriginInfo and xpub so that later the BIP32PubkeyProvider can look them up. The last parent is still being stored so that additional derivation can occur.

This consolidates cache reads and writes and encapsulates them in the classes that actually use the cache.

in src/script/keyorigin.h:27 in 6df2a7a0e1 outdated

22+    {
23+        for (int i = 0; i < 4; ++i) {
24+            if (a.fingerprint[i] < b.fingerprint[i]) return true;
25+            if (a.fingerprint[i] > b.fingerprint[i]) return false;
26+        }
27+        if (a.path.size() < b.path.size()) return true;

Sjors commented at 2:40 pm on February 26, 2020:

We should compare path elements first (max(a.path.size(), b.path.size())) and size after.

Since std::map<KeyOriginInfo, CExtPubKey> m_xpubs is serialised, I’d prefer to tidy up the ordering. Whether this matters depends on how you rebase https://github.com/bitcoin/bitcoin/pull/16528/commits/35bb585b28e5de43553bfd52d2257db9400199be, if it remains a blob or becomes multiple entries keyed by origin.

achow101 commented at 5:56 pm on February 26, 2020:

Done

in src/test/descriptor_tests.cpp:156 in a544f0e745 outdated

154 
155+            // Make sure we can expand using cached xpubs for unhardened derivation
156+            if (!(flags & DERIVE_HARDENED)) {
157+                // Evaluate the descriptor at i + 1
158+                FlatSigningProvider script_provider1, script_provider_cached1;
159+                std::vector<CScript> spks1, spks_cached1;

Sjors commented at 3:09 pm on February 26, 2020:

nit: maybe rename spks_cached1 to spks1_from_cache

achow101 commented at 5:56 pm on February 26, 2020:

Done

in src/test/descriptor_tests.cpp:159 in a544f0e745 outdated

157+                // Evaluate the descriptor at i + 1
158+                FlatSigningProvider script_provider1, script_provider_cached1;
159+                std::vector<CScript> spks1, spks_cached1;
160+                BOOST_CHECK((t ? parse_priv : parse_pub)->Expand(i + 1, key_provider, spks1, script_provider1, nullptr));
161+
162+                // Try again but use the old cache. The old cache won't have the pubkeys, but will have the parent xpub for derivation.

Sjors commented at 3:12 pm on February 26, 2020:

but use the cache generated while expanding i. This cache won't have the pubkeys for i + 1, but

achow101 commented at 5:56 pm on February 26, 2020:

Done

in src/script/descriptor.cpp:265 in a544f0e745 outdated

261@@ -262,6 +262,16 @@ class BIP32PubkeyProvider final : public PubkeyProvider
262         return true;
263     }
264 
265+    // Derives the last xpub

Sjors commented at 3:19 pm on February 26, 2020:

xpub or xpriv, unless you neuter it at the end and have it return a CExtPubKey&

achow101 commented at 5:56 pm on February 26, 2020:

Changed to xprv

in src/script/descriptor.cpp:327 in a544f0e745 outdated

332+            }
333+            *key = extkey.pubkey;
334+            if (write_cache && !read_cache) {
335+                if (!write_cache->CacheExtPubKey(info_out, extkey)) return false;
336+                // Only cache parent if there is any unhardened derivation
337+                if (m_derive == DeriveType::UNHARDENED && !write_cache->CacheExtPubKey(parent_info, parent)) return false;

Sjors commented at 3:45 pm on February 26, 2020:

Is it worth skipping the parent write once it’s done?

achow101 commented at 5:41 pm on February 26, 2020:

A lookup is just as expensive as an insertion, so I don’t think so.

Sjors commented at 3:49 pm on February 26, 2020: member

a544f0e7459f346a1bf129c9dc978fe46c6abf73 looks correct. Much clearer than before, but still some confusing bits.

I find the separation of 4f24907f4007b2786ee39dcb8d6f86e52494db10 a6feb5d1aee6ae08b87029561873471cdd62a36a confusing, with the ExpandFromCache signature changing in two steps.

Switching from pubkeys to xpubs plus origin info increases the cache size by ~40 bytes per key, or 240 KB for a typical descriptor wallet with change & receive for three output types, with the first 1000 keys expanded. That’s probably acceptable, though maybe the serialization could be optimized to leave out the chain code for “leaf” keys (meh, complexity).

This could be a good time to rename m_derive to m_range_derive to make it clear that this refers to whether a given (final?) path element is (hardened) ranged or not.

achow101 force-pushed on Feb 26, 2020

achow101 commented at 5:59 pm on February 26, 2020: member

I’ve squashed the middle three commits together (the ones that just changed to using DescriptorCache) so that the signature of Expand and ExpandHelper don’t change so many times.

Switching from pubkeys to xpubs plus origin info increases the cache size by ~40 bytes per key, or 240 KB for a typical descriptor wallet with change & receive for three output types, with the first 1000 keys expanded. That’s probably acceptable, though maybe the serialization could be optimized to leave out the chain code for “leaf” keys (meh, complexity).

We could do what I did originally and have a pubkey cache, but I felt that to be unnecessary. We would still be storing KeyOriginInfo.

This could be a good time to rename m_derive to m_range_derive to make it clear that this refers to whether a given (final?) path element is (hardened) ranged or not.

Why? I find it to be clear.

in src/script/keyorigin.h:33 in 08186b12ce outdated

28+        for (unsigned int i = 0; i < min; ++i) {
29+            if (a.path.at(i) < b.path.at(i)) return true;
30+            if (a.path.at(i) > b.path.at(i)) return false;
31+        }
32+        if (a.path.size() < b.path.size()) return true;
33+        if (a.path.size() > b.path.size()) return false;

promag commented at 10:39 pm on February 26, 2020:

Can be removed.

achow101 commented at 2:05 am on February 27, 2020:

Done

in src/script/descriptor.h:22 in 08186b12ce outdated

17+class DescriptorCache {
18+private:
19+    std::map<KeyOriginInfo, CExtPubKey> m_xpubs;
20+
21+public:
22+    bool CacheExtPubKey(const KeyOriginInfo& origin_info, const CExtPubKey& xpub);

promag commented at 10:43 pm on February 26, 2020:

Will this return false in a follow up change?

achow101 commented at 2:05 am on February 27, 2020:

No. I’ve made it void

achow101 force-pushed on Feb 27, 2020

in src/script/descriptor.cpp:1094 in d90075e586 outdated

1060@@ -1050,3 +1061,16 @@ std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const Signing
1061 {
1062     return InferScript(script, ParseScriptContext::TOP, provider);
1063 }
1064+
1065+void DescriptorCache::CacheExtPubKey(const KeyOriginInfo& origin_info, const CExtPubKey& xpub)
1066+{
1067+    m_xpubs[origin_info] = xpub;

promag commented at 8:57 am on February 27, 2020:

Does it make sense to assert(m_xpubs.count(origin_info) == 0)?

Sjors commented at 1:08 pm on February 27, 2020:

Not at the moment: #18204 (review)

promag commented at 6:30 pm on February 27, 2020:

Performance penalty aside, makes sense to assert it’s the same xpub if already cached?

in src/script/descriptor.cpp:302 in d90075e586 outdated

299-            if (IsHardened()) {
300-                CKey priv_key;
301-                if (!GetPrivKey(pos, arg, priv_key)) return false;
302-                *key = priv_key.GetPubKey();
303+            CExtPubKey extkey = m_extkey;
304+            CExtPubKey parent = extkey;

Sjors commented at 1:41 pm on February 27, 2020:

This CExtPubKey juggling still confuses me :-)

I added some comments for my own sanity. Will probably need to read this again later.

0CExtPubKey extkey_out = m_extkey;    // to hold extended key for *key (m/.../k)
1CExtPubKey extkey_parent = m_extkey; // to hold extended key for the parent of *key (m/.../k/pos)

in src/script/descriptor.cpp:306 in d90075e586 outdated

303+            CExtPubKey extkey = m_extkey;
304+            CExtPubKey parent = extkey;
305+            if (read_cache) {
306+                if (!read_cache->GetCachedExtPubKey(info_out, extkey)) {
307+                    if (m_derive == DeriveType::HARDENED) return false;
308+                    // Try to get the derivation parent

Sjors commented at 1:46 pm on February 27, 2020:

0// Check if the parent at m/.../k is cached

in src/script/descriptor.cpp:312 in d90075e586 outdated

309+                    if (!read_cache->GetCachedExtPubKey(parent_info, parent)) return false;
310+                    assert(m_derive == DeriveType::UNHARDENED);
311+                    parent.Derive(extkey, pos);
312+                }
313+            } else if (IsHardened()) {
314+                CExtKey xprv;

Sjors commented at 1:48 pm on February 27, 2020:

0// Get the extended private key at m/.../k

in src/script/descriptor.cpp:314 in d90075e586 outdated

311+                    parent.Derive(extkey, pos);
312+                }
313+            } else if (IsHardened()) {
314+                CExtKey xprv;
315+                if (!GetDerivedExtKey(arg, xprv)) return false;
316+                parent = xprv.Neuter();

Sjors commented at 1:50 pm on February 27, 2020:

0// Get the extended public key at m/.../k/i or m/.../k/i'

in src/script/descriptor.cpp:320 in d90075e586 outdated

320             } else {
321-                // TODO: optimize by caching
322-                CExtPubKey extkey = m_extkey;
323                 for (auto entry : m_path) {
324-                    extkey.Derive(extkey, entry);
325+                    parent.Derive(parent, entry);

Sjors commented at 1:54 pm on February 27, 2020:

(one line up)

0// Set parent to the extended public key at m/.../k

in src/script/descriptor.cpp:322 in d90075e586 outdated

323                 for (auto entry : m_path) {
324-                    extkey.Derive(extkey, entry);
325+                    parent.Derive(parent, entry);
326                 }
327-                if (m_derive == DeriveType::UNHARDENED) extkey.Derive(extkey, pos);
328+                extkey = parent;

Sjors commented at 1:56 pm on February 27, 2020:

(above)

0// If this is not a ranged descriptor, we return the public key at `m/.../k`, otherwise at `m/.../k/i

Sjors commented at 1:58 pm on February 27, 2020: member

We could do what I did originally and have a pubkey cache, but I felt that to be unnecessary.

That’s fine. Unless future benchmarks show that DescriptorScriptPubKeyMan::TopUp() is particularly slow (https://github.com/bitcoin/bitcoin/pull/16528/commits/76a355eff5b55df6951d21e66f4558ee26f244f4), compared to the other work that happens when loading a wallet.

Can you move 568a90f908313466f5a57c46dc3a16cc01117f70 and 23aef1932c7f8f580928eac595ad3928f306ae35 from #15528 to here? 568a90f908313466f5a57c46dc3a16cc01117f70 could use a test to show that nothing is added to cache.

in src/script/descriptor.h:58 in 0837211a38 outdated

19+    std::map<KeyOriginInfo, CExtPubKey> m_xpubs;
20+
21+public:
22+    void CacheExtPubKey(const KeyOriginInfo& origin_info, const CExtPubKey& xpub);
23+    bool GetCachedExtPubKey(const KeyOriginInfo& origin_info, CExtPubKey& xpub) const;
24+};

instagibbs commented at 2:00 pm on February 27, 2020:

much clearer now :+1:

in src/script/keyorigin.h:23 in 0837211a38 outdated

17@@ -18,6 +18,21 @@ struct KeyOriginInfo
18         return std::equal(std::begin(a.fingerprint), std::end(a.fingerprint), std::begin(b.fingerprint)) && a.path == b.path;
19     }
20 
21+    friend bool operator<(const KeyOriginInfo& a, const KeyOriginInfo& b)
22+    {
23+        for (int i = 0; i < 4; ++i) {

instagibbs commented at 2:18 pm on February 27, 2020:

I made this complaint long ago but I’d really prefer some constant for 4 being littered everywhere.

sipa commented at 2:18 am on March 4, 2020:

You can probably write this more readably as:

0if (std::lexicographic_compare(std::begin(a.fingerprint), std::end(a.fingerprint), std::begin(b.fingerprint), std::end(b.fingerprint)) return true;
1if (std::lexicographic_compare(std::begin(b.fingerprint), std::end(b.fingerprint), std::begin(a.fingerprint), std::end(a.fingerprint)) return false;

etc., which also avoids the magic 4 number.

achow101 commented at 3:20 am on March 4, 2020:

Done

in src/script/keyorigin.h:21 in 0837211a38 outdated

17@@ -18,6 +18,21 @@ struct KeyOriginInfo
18         return std::equal(std::begin(a.fingerprint), std::end(a.fingerprint), std::begin(b.fingerprint)) && a.path == b.path;
19     }
20 
21+    friend bool operator<(const KeyOriginInfo& a, const KeyOriginInfo& b)

instagibbs commented at 2:21 pm on February 27, 2020:

future work: Noticed there are no unit tests for KeyOriginInfo, would be nice to have

in src/script/descriptor.cpp:159 in db007ea44f outdated

152@@ -153,7 +153,7 @@ struct PubkeyProvider
153     virtual ~PubkeyProvider() = default;
154 
155     /** Derive a public key. If key==nullptr, only info is desired. */
156-    virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const = 0;
157+    virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const = 0;

instagibbs commented at 2:29 pm on February 27, 2020:

A few words on the new optional args?

achow101 commented at 6:25 pm on February 27, 2020:

Added some comments.

in src/script/descriptor.cpp:329 in d90075e586 outdated

325                 assert(m_derive != DeriveType::HARDENED);
326             }
327             *key = extkey.pubkey;
328             if (write_cache && !read_cache) {
329                 write_cache->CacheExtPubKey(info_out, extkey);
330+                // Only cache parent if there is any unhardened derivation

instagibbs commented at 3:20 pm on February 27, 2020:

any? The whole path has to be unhardened right?

achow101 commented at 6:21 pm on February 27, 2020:

Just the last range step. The range derivation type has to be unhardened or none. This means it either ends with * or with an absolute path. There can be hardened steps in between, and even have the last step be hardened if it is not a range.

This thing about a non-ranged path is kind of a hack to make sure that we cache the pubkey for descriptors that have keys like xprv../1'. We have some examples of this in the tests.

Sjors commented at 6:42 pm on February 27, 2020:

Just to clarify, there’s no test for this AFAIK, but xpriv/../*/... isn’t allowed, right?

instagibbs commented at 7:00 pm on February 27, 2020:

I see, so we don’t do any intermediate caching if we can always generate from “root” anyways with pubkey.

achow101 commented at 7:05 pm on February 27, 2020:

Just to clarify, there’s no test for this AFAIK, but xpriv/../*/... isn’t allowed, right?

Yes. Maybe we should add a CheckUnparsable for that.

I see, so we don’t do any intermediate caching if we can always generate from “root” anyways with pubkey.

Actually no. We always cache if there are xpubs. If the descriptor has just an xpub, e.g. wpkh(xpub...), we actually would cache that xpub. If it were wpkh(xpub.../0), we would cache the derived xpub. Same if it is hardened.

instagibbs commented at 7:09 pm on February 27, 2020:

I think I’m agreeing with you here.

instagibbs commented at 5:31 pm on February 27, 2020: member

Unable to “review” at the moment due to github issues, but https://github.com/bitcoin/bitcoin/pull/18204/commits/d90075e586b2a4b1fbc1c511d662c0b918023595 looks logically correct (will swing back here when back up and drop comments)

achow101 force-pushed on Feb 27, 2020

achow101 commented at 6:26 pm on February 27, 2020: member

Can you move 568a90f and 23aef19 from #16528 to here? 568a90f could use a test to show that nothing is added to cache.

Done. Also squashed a bit and added tests.

Sjors commented at 11:58 am on February 28, 2020: member

Travis and AppVeyor didn’t run. Probably because of the Github problems yesterday. It might help to force push some trivial change.

in src/script/descriptor.cpp:298 in b434a87699 outdated

292+    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
293     {
294+        KeyOriginInfo info_out;
295+        CKeyID keyid = m_extkey.pubkey.GetID();
296+        std::copy(keyid.begin(), keyid.begin() + sizeof(info_out.fingerprint), info_out.fingerprint);
297+        info_out.path = m_path;

Sjors commented at 12:37 pm on February 28, 2020:

0// For a ranged descriptor, add derivation step to path, otherwise return public key at current depth.

achow101 commented at 7:35 pm on February 28, 2020:

Added

in src/script/descriptor.cpp:286 in b434a87699 outdated

264@@ -262,6 +265,16 @@ class BIP32PubkeyProvider final : public PubkeyProvider
265         return true;
266     }
267 
268+    // Derives the last xprv
269+    bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv) const
270+    {
271+        if (!GetExtKey(arg, xprv)) return false;
272+        for (auto entry : m_path) {
273+            xprv.Derive(xprv, entry);

Sjors commented at 12:47 pm on February 28, 2020:

nit: assert Derive() succeeds

achow101 commented at 7:35 pm on February 28, 2020:

Done here and elsewhere.

in src/script/descriptor.cpp:306 in b434a87699 outdated

306+            if (read_cache) {
307+                if (!read_cache->GetCachedExtPubKey(info_out, extkey)) return false;
308+            } else if (IsHardened()) {
309+                CExtKey xprv;
310+                if (!GetDerivedExtKey(arg, xprv)) return false;
311+                if (m_derive == DeriveType::UNHARDENED) xprv.Derive(xprv, pos);

Sjors commented at 12:47 pm on February 28, 2020:

nit: assert Derive() succeeds

in src/script/descriptor.cpp:293 in b434a87699 outdated

287@@ -275,29 +288,37 @@ class BIP32PubkeyProvider final : public PubkeyProvider
288     BIP32PubkeyProvider(const CExtPubKey& extkey, KeyPath path, DeriveType derive) : m_extkey(extkey), m_path(std::move(path)), m_derive(derive) {}
289     bool IsRange() const override { return m_derive != DeriveType::NO; }
290     size_t GetSize() const override { return 33; }
291-    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const override
292+    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
293     {
294+        KeyOriginInfo info_out;

Sjors commented at 12:52 pm on February 28, 2020:

You don’t need this temporary variable anymore, suggest renaming info to info_out instead.

achow101 commented at 6:21 pm on February 28, 2020:

We want to avoid modifying info in case later steps fail.

instagibbs commented at 6:26 pm on February 28, 2020:

might be worth a comment(took me a bit to convince myself what it was doing)

Sjors commented at 6:51 pm on February 28, 2020:

Then we need another test, because everything passed when I changed that.

achow101 commented at 7:34 pm on February 28, 2020:

I added a comment. I don’t think a test is useful. Everything still passes because ExpandHelper does the same thing. Just keeping it for belt-and-suspenders.

in src/script/descriptor.cpp:155 in b434a87699 outdated

151@@ -152,8 +152,11 @@ struct PubkeyProvider
152 {
153     virtual ~PubkeyProvider() = default;
154 
155-    /** Derive a public key. If key==nullptr, only info is desired. */
156-    virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const = 0;
157+    /** Derive a public key. If key==nullptr, only info is desired.

Sjors commented at 1:04 pm on February 28, 2020:

CPubKey* key can be a reference now, and you can drop if(key) in a few places. The nullptr was only used for caching individual pubkeys.

achow101 commented at 7:35 pm on February 28, 2020:

Done

Sjors commented at 1:05 pm on February 28, 2020: member

Keeping you busy :-)

I like the progression in the commits now: b434a8769956573b2ee8eaa2b4826f0e82d39f1f maintains the existing behaviour of caching individual pub keys, except that it switches to xpubs. The next commits then reduce the amount of stuff cached.

achow101 force-pushed on Feb 28, 2020

achow101 commented at 9:59 pm on February 28, 2020: member

I’ve added another commit to internally cache that parent xpub inside of BIP32PubkeyProvider so the Expand doesn’t constantly re-derive the same xpub.

in src/script/descriptor.cpp:314 in 384562930a outdated

324+            if (!read_cache->GetCachedExtPubKey(info_out, extkey)) {
325+                if (m_derive == DeriveType::HARDENED) return false;
326+                // Try to get the derivation parent
327+                if (!read_cache->GetCachedExtPubKey(parent_info, parent)) return false;
328+                assert(m_derive == DeriveType::UNHARDENED);
329+                assert(parent.Derive(extkey, pos));

Sjors commented at 8:21 am on February 29, 2020:

Thanks for adding the asserts, but now they violate “Assertions should not have side-effects”: https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#general-c

achow101 commented at 6:51 pm on March 2, 2020:

Removed the asserts then.

achow101 commented at 7:02 pm on March 3, 2020:

I’ve added asserts in that shouldn’t have side effects.

in src/script/descriptor.cpp:323 in 2f04cc4c50 outdated

306         CExtPubKey extkey = m_extkey;
307+        CExtPubKey parent = extkey;
308         if (read_cache) {
309-            if (!read_cache->GetCachedExtPubKey(info_out, extkey)) return false;
310+            if (!read_cache->GetCachedExtPubKey(info_out, extkey)) {
311+                if (m_derive == DeriveType::HARDENED) return false;

Sjors commented at 8:35 am on February 29, 2020:

In 2f04cc4c50a9ef94f6e67d97ea552e7b6e03cec7 : maybe change to m_derive != DeriveType:: UNHARDENED for readability, since there’s no point in calling GetCachedExtPubKey(parent_info for DeriveType:: NONE, because parent_info == info_out in that case.

achow101 commented at 6:51 pm on March 2, 2020:

Done

in src/script/descriptor.cpp:312 in 2f04cc4c50 outdated

309-            if (!read_cache->GetCachedExtPubKey(info_out, extkey)) return false;
310+            if (!read_cache->GetCachedExtPubKey(info_out, extkey)) {
311+                if (m_derive == DeriveType::HARDENED) return false;
312+                // Try to get the derivation parent
313+                if (!read_cache->GetCachedExtPubKey(parent_info, parent)) return false;
314+                assert(m_derive == DeriveType::UNHARDENED);

Sjors commented at 8:37 am on February 29, 2020:

With my previous suggestion this assert would go away.

achow101 commented at 6:52 pm on March 2, 2020:

Done

Sjors commented at 10:20 am on February 29, 2020: member

~~That last commit may not be necessary if Topup() tries ExpandFromCache first: #16528 (review) (but if I’m wrong about that, then it’s fine to keep it).~~ (nvm, there are plenty of other places where Expand() is used, e.g. importdescriptors, deriveaddresses)

in src/script/descriptor.cpp:292 in 384562930a outdated

288@@ -275,29 +289,57 @@ class BIP32PubkeyProvider final : public PubkeyProvider
289     BIP32PubkeyProvider(const CExtPubKey& extkey, KeyPath path, DeriveType derive) : m_extkey(extkey), m_path(std::move(path)), m_derive(derive) {}
290     bool IsRange() const override { return m_derive != DeriveType::NO; }
291     size_t GetSize() const override { return 33; }
292-    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const override
293+    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override

Sjors commented at 4:43 pm on February 29, 2020:

The exclusive use of either read_cache or write_cache trips me up. A reminder like assert(!(read_cache && write_cache)); may be helpful.

achow101 commented at 5:50 pm on March 2, 2020:

I don’t think exclusive use is really needed or enforced.

Sjors commented at 6:40 pm on March 2, 2020:

All tests pass if I put the assert there. That implies we’re not testing mixed use.

achow101 commented at 6:44 pm on March 2, 2020:

Yes, it is currently not possible to have mixed use, but I don’t think we should enforce non-mixed use. This should work regardless of mixed use and I don’t want to make it such that mixed use is not an intended use case.

Sjors commented at 5:56 pm on March 3, 2020:

Maybe add the assert, with a comment above it along the lines of // Mixed use of read_cache and write_cache should be possible, but is currently untested? (or just the comment)

achow101 commented at 6:42 pm on March 3, 2020:

I really don’t think it is necessary to have an assert here.

instagibbs commented at 9:23 pm on March 3, 2020:

It’s gotta be documented at least.

achow101 commented at 11:14 pm on March 3, 2020:

I’ve mentioned it in the comment for GetPubKey in PubkeyProvider.

in src/script/descriptor.cpp:337 in 384562930a outdated

352-        if (m_derive == DeriveType::UNHARDENED) info.path.push_back((uint32_t)pos);
353-        if (m_derive == DeriveType::HARDENED) info.path.push_back(((uint32_t)pos) | 0x80000000L);
354+        key = extkey.pubkey;
355+        if (!m_cached_xpub.pubkey.IsValid() && m_derive != DeriveType::HARDENED) m_cached_xpub = parent;
356+        if (write_cache && !read_cache) {
357+            write_cache->CacheExtPubKey(info_out, extkey, true);

Sjors commented at 4:54 pm on February 29, 2020:

The skip_unhardened argument of CacheExtPubKey is a nett confusion increase for me, try:

0// Cache parent instead of child if there is any unhardened derivation
1if (m_derive != DeriveType::HARDENED) {
2  write_cache->CacheExtPubKey(parent_info, parent);
3} else if (info_out.path.size() > 0) {
4  write_cache->CacheExtPubKey(info_out, extkey);
5}

achow101 commented at 6:52 pm on March 2, 2020:

Done. Removed skip_unhardened.

in src/script/descriptor.cpp:328 in 384562930a outdated

325+                if (m_derive == DeriveType::HARDENED) return false;
326+                // Try to get the derivation parent
327+                if (!read_cache->GetCachedExtPubKey(parent_info, parent)) return false;
328+                assert(m_derive == DeriveType::UNHARDENED);
329+                assert(parent.Derive(extkey, pos));
330+            }

Sjors commented at 5:13 pm on February 29, 2020:

0// If we don't have a read_cache, we have a write_cache

Sjors approved

Sjors commented at 5:23 pm on February 29, 2020: member

Code review ACK 384562930a48474f337224b0355b6fd08784c375 modulo assert side effects. Above and below some last suggestions to improve readability.

achow101 force-pushed on Mar 2, 2020

achow101 force-pushed on Mar 3, 2020

Sjors commented at 7:16 pm on March 3, 2020: member

Code review re-ACK 1373d9d885fdc671a7538f9ea6410582bcaee1d5

instagibbs commented at 9:27 pm on March 3, 2020: member

The logic seems correct, but only once I did my own little refactorings to make it more understandable what everything was doing: https://github.com/instagibbs/bitcoin/commit/9c169165cbfb1565c28b8969733351e5611db6ac

I’m willing to ACK the logic as-is, but I find it extremely opaque and would immediately open up a PR with these changes.

achow101 force-pushed on Mar 3, 2020

achow101 commented at 10:53 pm on March 3, 2020: member

I’ve pulled in @instagibbs suggested changes with only one small modification.

achow101 force-pushed on Mar 3, 2020

instagibbs commented at 0:32 am on March 4, 2020: member

code review ACK https://github.com/bitcoin/bitcoin/pull/18204/commits/1c20f259cf8f406254989d4ecca1c52d858209ae

thanks for pulling in most the suggestions!

fanquake requested review from Sjors on Mar 4, 2020

in src/script/keyorigin.h:27 in f2bcabc410 outdated

22+    {
23+        for (int i = 0; i < 4; ++i) {
24+            if (a.fingerprint[i] < b.fingerprint[i]) return true;
25+            if (a.fingerprint[i] > b.fingerprint[i]) return false;
26+        }
27+        unsigned int min = std::min(a.path.size(), b.path.size());

sipa commented at 2:21 am on March 4, 2020:

Same here:

0if (std::lexicographic_compare(std::begin(a.path), std::end(a.path), std::begin(b.path), std::end(b.path)) return true;
1if (std::lexicographic_compare(std::begin(b.path), std::end(b.path), std::begin(a.path), std::end(a.path)) return false;

Which also avoids manually comparing lengths.

achow101 commented at 3:20 am on March 4, 2020:

Done

in src/script/descriptor.cpp:262 in 169d5a1891 outdated

245@@ -246,18 +246,19 @@ enum class DeriveType {
246 /** An object representing a parsed extended public key in a descriptor. */
247 class BIP32PubkeyProvider final : public PubkeyProvider
248 {
249-    CExtPubKey m_extkey;
250+    // Root xpub, path, and final derivation step type being used, if any
251+    CExtPubKey m_root_extkey;

sipa commented at 2:29 am on March 4, 2020:

It’s not necessarily the root, right? For example in [012345678/0']xpub.../0/1 this variable would correspond to the 2nd level intermediary node.

achow101 commented at 3:08 am on March 4, 2020:

Sure, but it’s easier to just call this the root and it’s the root key that we do all our later derivation from.

Sjors commented at 12:06 pm on March 6, 2020:

m_base_extkey could be a nice alternative

achow101 commented at 11:36 pm on March 6, 2020:

I think there’s enough bikeshedding in this pr :/

in src/script/descriptor.h:19 in f2bcabc410 outdated

12@@ -13,6 +13,17 @@
13 
14 #include <vector>
15 
16+// Cache for pre-computed descriptor things
17+class DescriptorCache {
18+private:
19+    std::map<KeyOriginInfo, CExtPubKey> m_xpubs;

sipa commented at 2:48 am on March 4, 2020:

Shouldn’t this be a multimap? There can be collisions in the fingerprint + all subsequent path elements.

achow101 commented at 3:12 am on March 4, 2020:

I think that’s extremely unlikely. It would require several thousand xpubs in the descriptor itself. I think we have a few other places where we assume origin info don’t colide.

sipa commented at 6:01 am on March 4, 2020:

With 93 entries there is a 1 in a million chance for a collision… I agree it’s low, but it’s not so low that it is negligible, and certainly not so low that one couldn’t grind a descriptor to intentionally cause a collision.

This makes me wonder if using KeyOriginInfo as key is the right approach. In theory, it should be sufficient to just key by the index of the key expression in the descriptor, right? As the descriptor is constant, and the cache is specific to one descriptor, that would uniquely identify what the entry is for.

instagibbs commented at 2:06 pm on March 4, 2020:

index of the key expression in the descriptor

the what?

sipa commented at 3:57 pm on March 4, 2020:

Every descriptor consists of some functions that combine the output of key expressions (pubkeys, xpubs, origin info, derivation paths, …). We can assign the successive key expressions numbers 0, 1, 2, … and use those index positions as key in the map (which would then become a std::map<int, CExtPubKey>).

achow101 commented at 4:53 pm on March 4, 2020:

I don’t really like using the position to index into the cache. It requires the PubkeyProviders to know their position within the descriptor when it really doesn’t matter to them.

If this was changed to a multimap, how would we decide which xpub to use in the event that there is a collision?

sipa commented at 5:19 pm on March 4, 2020:

I think that’s not a useful argument. If the current way the code works makes it hard to implement the right solution, the code should be changed. It seems to me that using position is the more concise, exact, and efficient way of doing it, and ignoring current code architecture it also seems the simplest, so I think it would be preferable.

You’re right that a multimap wouldn’t work. Using a KeyOriginInfo to identify the record is inherently lossy - a better solution is just not throwing it away at all.

instagibbs commented at 5:20 pm on March 4, 2020:

@achow101 well it requires the user/builder of the cache to know each pubkey position, at least, right?

in src/script/descriptor.cpp:200 in c0dcb53537 outdated

186@@ -183,9 +187,9 @@ class OriginPubkeyProvider final : public PubkeyProvider
187 
188 public:
189     OriginPubkeyProvider(KeyOriginInfo info, std::unique_ptr<PubkeyProvider> provider) : m_origin(std::move(info)), m_provider(std::move(provider)) {}
190-    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const override
191+    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
192     {
193-        if (!m_provider->GetPubKey(pos, arg, key, info)) return false;
194+        if (!m_provider->GetPubKey(pos, arg, key, info, read_cache, write_cache)) return false;

sipa commented at 2:49 am on March 4, 2020:

Shouldn’t the entry with overridden origin info be stored in the write cache here?

achow101 commented at 3:17 am on March 4, 2020:

I don’t think it would be useful to do that since we aren’t reading from the cache here.

achow101 force-pushed on Mar 4, 2020

achow101 commented at 9:03 pm on March 4, 2020: member

I’ve changed the cache back to using position, but this time with unordered_maps instead of a vector. This requires using two maps, one for the derived keys, and one for the parent xpubs.

To facilitate this, PubkeyProviders will now store their position in the descriptor. This position is established during parsing.

Also dropped the commit for GetNotCached.

in src/script/descriptor.h:21 in 6a6f3f6673 outdated

12@@ -13,6 +13,46 @@
13 
14 #include <vector>
15 
16+using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
17+
18+// Cache for pre-computed descriptor things
19+class DescriptorCache {
20+private:
21+    std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs; // Map key expression indexes to a map of derivation indexes to xpubs

Sjors commented at 10:51 am on March 5, 2020:

It would be more readable to map this the other way around:

0// Map key expression index to xpub
1using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
2
3// Map derivation index to ExtPubKeyMap
4std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs;

achow101 commented at 4:13 pm on March 5, 2020:

I think that’s really inefficient. In most cases, that would mean a map for every single derived xpub, and that map just has one element. In the current mapping, it’s only two maps.

instagibbs commented at 4:15 pm on March 5, 2020:

I found the code as-is completely understandable fwiw. Maybe suggest a renaming/rewording somewhere?

instagibbs commented at 4:16 pm on March 5, 2020:

maybe just make it more visual: map: key expression index -> key derivation index -> xpub

achow101 commented at 4:50 pm on March 5, 2020:

I’ve clarified the comment.

Sjors commented at 11:13 am on March 5, 2020: member

New approach-ACK.

Nit: “clariiesy” in 26f8ddf3183843d6e8a9ec62378010aaecf8edfe commit description

You might be able to avoid the complexity of e7e8333 Cache parent xpub inside of BIP32PubkeyProvider, by unifying Expand() and ExpandFromCache(). They could take single read_write_cache argument. You could then move the cache update code from https://github.com/bitcoin/bitcoin/pull/16528/files?file-filters%5B%5D=.cpp#diff-5462ceb8a760a507152ab8b76bd48774R1690-R1719 to Expand(). When no cache argument is provided, fall back to an internal cache.

in src/script/descriptor.h:18 in e7e8333fbb outdated

12@@ -13,6 +13,46 @@
13 
14 #include <vector>
15 
16+using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
17+
18+// Cache for pre-computed descriptor things

instagibbs commented at 2:32 pm on March 5, 2020:

Suggested reword:

// Cache for a single descriptor’s derived extended pubkeys

achow101 commented at 4:50 pm on March 5, 2020:

Done

in src/script/descriptor.h:34 in e7e8333fbb outdated

29+     */
30+    void CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub);
31+    /** Retrieve a cached parent xpub
32+     *
33+     * @param[in] key_exp_pos Position of the key expression within the descriptor
34+     * @param[in] der_index Derivation index of the xpub

instagibbs commented at 2:34 pm on March 5, 2020:

this doesn’t appear to exist

achow101 commented at 4:50 pm on March 5, 2020:

Fixed

in src/script/descriptor.h:35 in e7e8333fbb outdated

30+    void CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub);
31+    /** Retrieve a cached parent xpub
32+     *
33+     * @param[in] key_exp_pos Position of the key expression within the descriptor
34+     * @param[in] der_index Derivation index of the xpub
35+     * @param[in] xpub The CExtPubKey to cache

instagibbs commented at 2:34 pm on March 5, 2020:

@param[out] xpub The CExtPubKey to get from cache

achow101 commented at 4:50 pm on March 5, 2020:

Done

in src/script/descriptor.h:49 in e7e8333fbb outdated

44+    void CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub);
45+    /** Retrieve a cached xpub derived at an index
46+     *
47+     * @param[in] key_exp_pos Position of the key expression within the descriptor
48+     * @param[in] der_index Derivation index of the xpub
49+     * @param[in] xpub The CExtPubKey to cache

instagibbs commented at 2:37 pm on March 5, 2020:

@param[out] xpub The CExtPubKey to get from cache

achow101 commented at 4:50 pm on March 5, 2020:

Done

in src/script/descriptor.cpp:154 in e7e8333fbb outdated

149@@ -150,10 +150,21 @@ typedef std::vector<uint32_t> KeyPath;
150 /** Interface for public key objects in descriptors. */
151 struct PubkeyProvider
152 {
153+protected:
154+    //! Index of this key expression in the descriptor

instagibbs commented at 2:39 pm on March 5, 2020:

A quick example wouldn’t hurt(I was confused), which would also show what index it starts at :)

achow101 commented at 4:51 pm on March 5, 2020:

I added an example to the comment.

in src/script/descriptor.cpp:155 in e7e8333fbb outdated

149@@ -150,10 +150,21 @@ typedef std::vector<uint32_t> KeyPath;
150 /** Interface for public key objects in descriptors. */
151 struct PubkeyProvider
152 {
153+protected:
154+    //! Index of this key expression in the descriptor
155+    uint32_t m_exp_index;

instagibbs commented at 2:45 pm on March 5, 2020:

bikeshed: m_expr_index disallows my brain from guessing random words like expect, expub(??? thanks brain)

achow101 commented at 4:51 pm on March 5, 2020:

Done

in src/script/descriptor.cpp:312 in e7e8333fbb outdated

323+        CKeyID keyid = m_root_extkey.pubkey.GetID();
324+        std::copy(keyid.begin(), keyid.begin() + sizeof(parent_info.fingerprint), parent_info.fingerprint);
325+        parent_info.path = m_path;
326+
327+        // Info of the derived key itself which is copied out upon successful completion
328+        KeyOriginInfo child_info_out_tmp = parent_info;

instagibbs commented at 3:00 pm on March 5, 2020:

apologies for re-litigating variable naming after making you change it once: it’s either child or “parent” depending on the derivation, same with child_extkey and child_info_out, maybe just rename everything final_*?

Reviewing the latest changes made me realize my folly of naming it this way.

achow101 commented at 4:51 pm on March 5, 2020:

Done

in src/script/descriptor.cpp:845 in e7e8333fbb outdated

842+    return MakeUnique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider));
843 }
844 
845 /** Parse a script in a particular context. */
846-std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
847+std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)

instagibbs commented at 3:08 pm on March 5, 2020:

In what situations would you like to start with non-0 index?

achow101 commented at 4:21 pm on March 5, 2020:

None, but this is recursive.

instagibbs commented at 4:24 pm on March 5, 2020:

Ah! Duh.

Sjors commented at 12:03 pm on March 6, 2020:

Only multi and sortedmulti can cause key_exp_index to be non-zero, and those don’t recurse. You could make uint32_t key_exp_index local to just that if branch, and hardcode 0 in all other calls to ParsePubkey(0.

However with an eye on miniscript, we do expect to support scripts inside threshold, so might as well be ready for that.

achow101 commented at 11:37 pm on March 6, 2020:

I was intending for this to be generic so that it would work with future changes to descriptors, including miniscript. So I think I will leave it as is.

instagibbs commented at 3:08 pm on March 5, 2020: member

new approach ACK, changes make sense

achow101 force-pushed on Mar 5, 2020

in src/script/descriptor.cpp:318 in 196c9765ea outdated

329+        KeyOriginInfo final_info_out_tmp = parent_info;
330+        if (m_derive == DeriveType::UNHARDENED) final_info_out_tmp.path.push_back((uint32_t)pos);
331+        if (m_derive == DeriveType::HARDENED) final_info_out_tmp.path.push_back(((uint32_t)pos) | 0x80000000L);
332+
333+        // Derive keys or fetch them from cache
334+        CExtPubKey child_extkey = m_root_extkey;

instagibbs commented at 5:56 pm on March 5, 2020:

Was also thinking changing this to final_extkey as well for same reason.

achow101 commented at 6:21 pm on March 5, 2020:

Done

instagibbs approved

instagibbs commented at 5:57 pm on March 5, 2020: member

code review ACK https://github.com/bitcoin/bitcoin/pull/18204/commits/196c9765eaa88120964cfb1a81362f37a24ced9b

achow101 force-pushed on Mar 5, 2020

instagibbs commented at 6:23 pm on March 5, 2020: member

code review re-ACK https://github.com/bitcoin/bitcoin/pull/18204/commits/d7b241109f74b3c1c407929930e7d035cdcf60c9

in src/script/descriptor.h:18 in a4a887fa06 outdated

12@@ -13,6 +13,45 @@
13 
14 #include <vector>
15 
16+using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
17+
18+// Cache for single descriptor's derived extended pubkeys

Sjors commented at 11:19 am on March 6, 2020:

Nit, to get doxygen to pick this up:

0/** Cache for single descriptor's derived extended pubkeys */

achow101 commented at 2:44 pm on March 7, 2020:

Done

in src/script/descriptor.h:21 in a4a887fa06 outdated

12@@ -13,6 +13,45 @@
13 
14 #include <vector>
15 
16+using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
17+
18+// Cache for single descriptor's derived extended pubkeys
19+class DescriptorCache {
20+private:
21+    std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs; // Map key expression index -> map of (key derivation index -> xpub)

Sjors commented at 11:19 am on March 6, 2020:

0/** Map key expression index -> map of (key derivation index -> xpub) */

achow101 commented at 2:44 pm on March 7, 2020:

Done

Sjors commented at 2:53 pm on March 7, 2020:

It needs to be on the line above, otherwise this happens:

achow101 commented at 3:13 pm on March 7, 2020:

Fixed

in src/script/descriptor.h:22 in a4a887fa06 outdated

17+
18+// Cache for single descriptor's derived extended pubkeys
19+class DescriptorCache {
20+private:
21+    std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs; // Map key expression index -> map of (key derivation index -> xpub)
22+    ExtPubKeyMap m_parent_xpubs; // Map key expression index -> parent xpub

Sjors commented at 11:20 am on March 6, 2020:

0/** Map key expression index -> parent xpub */

achow101 commented at 2:44 pm on March 7, 2020:

Done

in src/script/descriptor.h:55 in a4a887fa06 outdated

47+     * @param[in] der_index Derivation index of the xpub
48+     * @param[in] xpub The CExtPubKey to get from cache
49+     */
50+    bool GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const;
51+
52+    const ExtPubKeyMap GetCachedParentExtPubKeys() const;

Sjors commented at 11:23 am on March 6, 2020:

0    /** Retrieve all cached parent xpubs */

achow101 commented at 2:44 pm on March 7, 2020:

Done

in src/script/descriptor.h:57 in a4a887fa06 outdated

48+     * @param[in] xpub The CExtPubKey to get from cache
49+     */
50+    bool GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const;
51+
52+    const ExtPubKeyMap GetCachedParentExtPubKeys() const;
53+    const std::unordered_map<uint32_t, ExtPubKeyMap> GetCachedDerivedExtPubKeys() const;

Sjors commented at 11:23 am on March 6, 2020:

0    /** Retrieve all cached final xpubs */

achow101 commented at 2:44 pm on March 7, 2020:

Done

in src/script/descriptor.cpp:351 in e4262c4565 outdated

344@@ -345,10 +345,11 @@ class BIP32PubkeyProvider final : public PubkeyProvider
345         key_out = final_extkey.pubkey;
346 
347         if (write_cache) {
348-            write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey);
349             // Only cache parent if there is any unhardened derivation
350             if (m_derive != DeriveType::HARDENED) {
351                 write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey);
352+            } else if (child_info_out.path.size() > 0) {

Sjors commented at 1:25 pm on March 6, 2020:

e4262c45655b4f79ddfd9905db66dc44b8f5148c doesn’t compile (child_info_out is renamed in In d7b241109f74b3c1c407929930e7d035cdcf60c9 to child_info_out`)

achow101 commented at 2:45 pm on March 7, 2020:

Fixed

Sjors commented at 1:27 pm on March 6, 2020: member

Code review ACK d7b241109f74b3c1c407929930e7d035cdcf60c9 modulo intermediate commit compile issue.

achow101 force-pushed on Mar 7, 2020

Sjors commented at 2:54 pm on March 7, 2020: member

re-ACK 31304fc4f8f0d7870794d8c675831d8c73c959cb

Introduce DescriptorCache struct which caches xpubs 474ea3b927

Track the index of the key expression in PubkeyProvider df55d44d0d

Rename BIP32PubkeyProvider.m_extkey to m_root_extkey

Renaming clarifies that m_extkey is actually the root
extkey that keys are derived from.

66c2cadc91

Add DescriptorCache* read_cache and DescriptorCache* write_cache to Expand and GetPubKey

Have Expand, ExpandFromCache, and ExpandHelper take additional DescriptorCache
parameters. These are then passed into PubkeyProvider::GetPubKey which
also takes them as arguments.

Reading and writing to the cache is pushed down into GetPubKey. The old cache where
pubkeys are serialized to a vector is completely removed and instead xpubs are being
cached in DescriptorCache.

58f54b686f

Cache the immediate derivation parent xpub

If unhardened derivation is used, cache the immediate derivation
parent xpub and use it for unhardened derivation

f76733eda5

Only cache xpubs that have a hardened last step

Also adds tests for this:
For ranged descriptors with unhardened derivation, we expect to
find parent keys in the cache but no child keys.

For descriptors containing an xpub but do not have unhardened derivation
(i.e. hardened derivation or single xpub with or without derivation),
we expect to find all of the keys in the cache, and the same
number of keys in the cache as in the SigningProvider.

For everything else (no xpub), nothing should be cached at all.

deb791c7ba

Cache parent xpub inside of BIP32PubkeyProvider

Optimize Expand by having BIP32PubkeyProvider also cache the parent
(or only) xpub within itself. Since Expand does not provide a read
cache, it is useful to internally cache this xpub to avoid re-deriving
the same xpub.

09e25071f4

achow101 force-pushed on Mar 7, 2020

instagibbs commented at 8:52 pm on March 9, 2020: member

code review re-re-ACK https://github.com/bitcoin/bitcoin/pull/18204/commits/09e25071f40c564af08a1386c39c4f2d8eb484b6

fanquake requested review from Sjors on Mar 10, 2020

Sjors approved

Sjors commented at 1:29 pm on March 10, 2020: member

re-ACK 09e25071f40c564af08a1386c39c4f2d8eb484b6

fanquake requested review from sipa on Mar 10, 2020

laanwj merged this on Mar 13, 2020

laanwj closed this on Mar 13, 2020

sidhujag referenced this in commit 9ac84dd1a1 on Mar 14, 2020

sidhujag referenced this in commit 2f115a38a8 on Nov 10, 2020

jasonbcox referenced this in commit 4edde51940 on Nov 13, 2020

jasonbcox referenced this in commit 74509ddd8a on Nov 13, 2020

jasonbcox referenced this in commit ca0a03351c on Nov 13, 2020

jasonbcox referenced this in commit 0653494400 on Nov 13, 2020

jasonbcox referenced this in commit f0c9183495 on Nov 13, 2020

deadalnix referenced this in commit 3a378ee5ce on Nov 13, 2020

deadalnix referenced this in commit ec5a073bd0 on Nov 13, 2020

DrahtBot locked this on Feb 15, 2022

descriptors: improve descriptor cache and cache xpubs #18204

Conflicts