descriptors: improve descriptor cache and cache xpubs #18204

achow101 · 2020-02-25T00:20:41Z

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.

DrahtBot · 2020-02-25T02:20:47Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

build: Enable -Wsuggest-override if available #16710 (build: Enable -Wsuggest-override if available by hebasto)
Avoid unnecessary signing provider copies on descriptor expansion #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.

Sjors

Concept ACK.

I'm seeing errors on Travis and locally:

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

src/script/descriptor.h

instagibbs

this is getting importmulti test failures

src/script/descriptor.h

achow101 · 2020-02-25T20:10:07Z

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

achow101 · 2020-02-26T01:17:15Z

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.

Sjors

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.

src/script/keyorigin.h

src/test/descriptor_tests.cpp

src/script/descriptor.cpp

Sjors · 2020-02-26T15:45:35Z

src/script/descriptor.cpp

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

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

achow101 · 2020-02-26T17:59:24Z

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.

src/script/keyorigin.h

src/script/descriptor.h

promag · 2020-02-27T08:57:05Z

src/script/descriptor.cpp

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

Not at the moment: #18204 (comment)

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

Sjors

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 (76a355e), 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.

Sjors · 2020-02-27T13:41:22Z

src/script/descriptor.cpp

This CExtPubKey juggling still confuses me :-)

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

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

Sjors · 2020-02-27T13:46:43Z

src/script/descriptor.cpp

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

Sjors · 2020-02-27T13:48:10Z

src/script/descriptor.cpp

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

Sjors · 2020-02-27T13:50:53Z

src/script/descriptor.cpp

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

Sjors · 2020-02-27T13:54:23Z

src/script/descriptor.cpp

(one line up)

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

Sjors · 2020-02-27T13:56:18Z

src/script/descriptor.cpp

(above)

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

instagibbs · 2020-02-27T17:31:02Z

Unable to "review" at the moment due to github issues, but d90075e looks logically correct (will swing back here when back up and drop comments)

src/script/descriptor.h

src/script/keyorigin.h

instagibbs · 2020-02-27T14:21:08Z

src/script/keyorigin.h

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

src/script/descriptor.cpp

instagibbs · 2020-02-27T15:20:43Z

src/script/descriptor.cpp

any? The whole path has to be unhardened right?

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.

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

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

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.

I think I'm agreeing with you here.

achow101 · 2020-02-27T18:26:48Z

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 · 2020-02-28T11:58:30Z

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

Sjors

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.

src/script/descriptor.cpp

achow101 · 2020-02-28T21:59:49Z

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.

Sjors

~~That last commit may not be necessary if Topup() tries ExpandFromCache first: #16528 (comment) (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)

src/script/descriptor.cpp

instagibbs

code review ACK 196c976

src/script/descriptor.cpp

instagibbs · 2020-03-05T18:23:53Z

code review re-ACK d7b2411

Sjors

Code review ACK d7b241109f74b3c1c407929930e7d035cdcf60c9 modulo intermediate commit compile issue.

src/script/descriptor.h

src/script/descriptor.cpp

Sjors · 2020-03-06T12:06:53Z

src/script/descriptor.cpp

m_base_extkey could be a nice alternative

src/script/descriptor.cpp

Sjors · 2020-03-07T14:54:08Z

re-ACK 31304fc4f8f0d7870794d8c675831d8c73c959cb

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

…xpand 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.

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

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.

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.

instagibbs · 2020-03-09T20:52:27Z

code review re-re-ACK 09e2507

Sjors

re-ACK 09e2507

…xpubs 09e2507 Cache parent xpub inside of BIP32PubkeyProvider (Andrew Chow) deb791c Only cache xpubs that have a hardened last step (Andrew Chow) f76733e Cache the immediate derivation parent xpub (Andrew Chow) 58f54b6 Add DescriptorCache* read_cache and DescriptorCache* write_cache to Expand and GetPubKey (Andrew Chow) 66c2cad Rename BIP32PubkeyProvider.m_extkey to m_root_extkey (Andrew Chow) df55d44 Track the index of the key expression in PubkeyProvider (Andrew Chow) 474ea3b Introduce DescriptorCache struct which caches xpubs (Andrew Chow) Pull request description: 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 `CExtPubKey`s 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 bitcoin#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. ACKs for top commit: instagibbs: code review re-re-ACK bitcoin@09e2507 Sjors: re-ACK 09e2507 Tree-SHA512: 95c8d0092274cdf115ce39f6d49dec767679abf3758d5b9e418afc308deca9dc6f67167980195bcc036cd9c09890bbbb39ec1dacffbfacdc03efd72a7e23b276

Summary: Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [1/7] : bitcoin/bitcoin@474ea3b Depends on D8380 Test Plan: ninja all check Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8381

Summary: Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [2/7] : bitcoin/bitcoin@df55d44 Depends on D8381 Test Plan: ninja all check Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8382

Summary: Renaming clarifies that m_extkey is actually the root extkey that keys are derived from. Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [3/7] : bitcoin/bitcoin@66c2cad Depends on D8382 Test Plan: ninja all check Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8383

…xpand and GetPubKey Summary: 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. Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [4/7] : bitcoin/bitcoin@58f54b6 Depends on D8383 Test Plan: ninja all check Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8384

Summary: If unhardened derivation is used, cache the immediate derivation parent xpub and use it for unhardened derivation Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [5/7] : bitcoin/bitcoin@f76733e Depends on D8384 and D8385 Test Plan: ninja all check Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8386

Summary: 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. Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [6/7] : bitcoin/bitcoin@deb791c Depends on D8386 Test Plan: ninja all check Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8387

Summary: 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. Backport of Core [[bitcoin/bitcoin#18204 | PR18204]] part [7/7] : bitcoin/bitcoin@09e2507 Depends on D8387 Test Plan: ninja all check-all Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D8388

fanquake added the Descriptors label Feb 25, 2020

This was referenced Feb 25, 2020

descriptors: Use xpub at last hardened step if possible #18163

Closed

[BIP 174] Implement serialization support for GLOBAL_XPUB field. #16463

Closed

Avoid unnecessary signing provider copies on descriptor expansion #16116

Closed

Sjors reviewed Feb 25, 2020

View reviewed changes

src/script/descriptor.h Outdated Show resolved Hide resolved

instagibbs reviewed Feb 25, 2020

View reviewed changes

src/script/descriptor.h Outdated Show resolved Hide resolved

src/script/descriptor.h Outdated Show resolved Hide resolved

achow101 force-pushed the desc-xpub-cache branch from a10bb99 to 6e9fc0c Compare February 25, 2020 18:22

achow101 force-pushed the desc-xpub-cache branch from 6e9fc0c to a544f0e Compare February 26, 2020 01:14

DrahtBot mentioned this pull request Feb 26, 2020

build: Enable -Wsuggest-override if available #16710

Merged

Sjors reviewed Feb 26, 2020

View reviewed changes

achow101 force-pushed the desc-xpub-cache branch from a544f0e to 08186b1 Compare February 26, 2020 17:56

promag reviewed Feb 26, 2020

View reviewed changes

src/script/keyorigin.h Outdated Show resolved Hide resolved

src/script/descriptor.h Outdated Show resolved Hide resolved

achow101 mentioned this pull request Feb 27, 2020

Native Descriptor Wallets using DescriptorScriptPubKeyMan #16528

Merged

achow101 force-pushed the desc-xpub-cache branch from 08186b1 to d90075e Compare February 27, 2020 02:05

promag reviewed Feb 27, 2020

View reviewed changes

Sjors reviewed Feb 27, 2020

View reviewed changes

instagibbs reviewed Feb 27, 2020

View reviewed changes

achow101 force-pushed the desc-xpub-cache branch 2 times, most recently from 2be7987 to 31cd940 Compare February 27, 2020 18:25

Sjors reviewed Feb 28, 2020

View reviewed changes

achow101 force-pushed the desc-xpub-cache branch from 31cd940 to a492402 Compare February 28, 2020 19:34

Sjors reviewed Feb 29, 2020

View reviewed changes

src/script/descriptor.cpp Outdated Show resolved Hide resolved

src/script/descriptor.cpp Outdated Show resolved Hide resolved

src/script/descriptor.cpp Outdated Show resolved Hide resolved

instagibbs approved these changes Mar 5, 2020

View reviewed changes

src/script/descriptor.cpp Outdated Show resolved Hide resolved

achow101 force-pushed the desc-xpub-cache branch from 196c976 to d7b2411 Compare March 5, 2020 18:21

Sjors reviewed Mar 6, 2020

View reviewed changes

achow101 force-pushed the desc-xpub-cache branch from d7b2411 to 31304fc Compare March 7, 2020 14:44

achow101 added 7 commits March 7, 2020 10:13

Introduce DescriptorCache struct which caches xpubs

474ea3b

Track the index of the key expression in PubkeyProvider

df55d44

Rename BIP32PubkeyProvider.m_extkey to m_root_extkey

66c2cad

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

Cache the immediate derivation parent xpub

f76733e

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

Cache parent xpub inside of BIP32PubkeyProvider

09e2507

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.

achow101 force-pushed the desc-xpub-cache branch from 31304fc to 09e2507 Compare March 7, 2020 15:14

fanquake requested a review from Sjors March 10, 2020 01:47

Sjors approved these changes Mar 10, 2020

View reviewed changes

fanquake requested a review from sipa March 10, 2020 23:49

laanwj merged commit 7f8176a into bitcoin:master Mar 13, 2020

MarkLTZ mentioned this pull request Apr 4, 2020

Bitcoin PR tracking litecoinz-core/litecoinz#14

Closed

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

descriptors: improve descriptor cache and cache xpubs #18204

descriptors: improve descriptor cache and cache xpubs #18204

Uh oh!

Conversation

achow101 commented Feb 25, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Feb 25, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

Sjors left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

achow101 commented Feb 25, 2020

Uh oh!

achow101 commented Feb 26, 2020

Uh oh!

Sjors left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 commented Feb 26, 2020

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Sjors left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

instagibbs commented Feb 27, 2020

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 Feb 27, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 commented Feb 25, 2020 •

edited

Loading

DrahtBot commented Feb 25, 2020 •

edited

Loading

Sjors left a comment •

edited

Loading

achow101 Feb 27, 2020 •

edited

Loading

Sjors commented Feb 28, 2020 •

edited

Loading

Sjors left a comment •

edited

Loading

Sjors left a comment •

edited

Loading

Sjors commented Mar 7, 2020 •

edited

Loading