wallet: improve rescan performance 640%

pstratem commented at 12:38 pm on January 23, 2023: contributor

The BIP158 compact block filters make a compromise between performance and security by re-keying the filter for each block. That means every block requires re-hashing and re-sorting for every script pub key before matching against the filter.

To improve on the performance we can simply generate filters using per index random keys (rather than per filter keys). We don’t share these filters with any attacker so there is no security risk.

I don’t use synthetic benchmarks for this as we have only a single data set we’re ever processing.

On an arbitrary server: No filters: 132 minutes Block filters: 45 minutes Wallet filters: 7 minutes

DrahtBot commented at 12:38 pm on January 23, 2023: contributor

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

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#27419 (move-only: Extract common/args from util/system by TheCharlatan)
#26728 (wallet: Have the wallet store the key for automatically generated descriptors by achow101)
#25907 (wallet: rpc to add automatically generated descriptors by achow101)
#24539 (Add a “tx output spender” index by sstone)
#22341 (rpc: add getxpub by Sjors)

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.

pstratem force-pushed on Jan 23, 2023

pstratem renamed this:
~~Use per node keyed block filter to rescan wallet.~~
wallet: improve rescan performance 640%
on Jan 24, 2023

DrahtBot added the label Wallet on Jan 24, 2023

0xB10C commented at 2:43 pm on January 24, 2023: contributor

While a 640% performance improvement is nice, a PR of this size could probably include a bit more details explaining what you’ve changed and why you’ve changed it in the OP and the commit messages. This makes it easier for reviewers to approach and review your PR.

mzumsande commented at 4:26 pm on January 24, 2023: contributor

Could you elaborate about when it would be advisable use this new feature? As far as I understand, the cost for this optimization is that we’d need to build and store a new index for rescanning - which will also take time and consume permanent disk space (how much?). Am I right to think that activating this would mostly make sense in specific situations where you know that you will need to rescan frequently in the future?

aureleoules commented at 4:35 pm on January 24, 2023: member

which will also take time and consume permanent disk space (how much?).

On mainnet it takes 8.4G currently.

theStack commented at 5:33 pm on January 24, 2023: contributor

Agree with previous reviewers that a more detailled PR description would be very helpful. For providing more systematic benchmarking results, you could use the approach from #25957 (see table in the PR description and the linked functional test benchmark) as a starting point. IIRC you mentioned on IRC that the speedup only show on a quite high element set size, i.e. a large number of scriptPubKeys in the wallet’s keypool – would be very interesting to also benchmark this to get a feeling what type of wallet users (w.r.t. to tx frequency) would benefit the most from this optimization.

Am I right to think that activating this would mostly make sense in specific situations where you know that you will need to rescan frequently in the future?

Probably another potential (non-wallet) use-case for this index would be to speed up the scanblocks RPC.

Refactor GCSFilter::HashToRange into HashElement and RangeHashedElement. 9cfb3e056c

pstratem force-pushed on Jan 26, 2023

pstratem commented at 9:43 am on January 26, 2023: contributor

@0xB10C I’ve reorganized the commits to be easier to understand and written a small explanation. @mzumsande Building the wallet filter index is optional, user with many keys and/or many wallets would greatly benefit from the performance improvement. @theStack I did a benchmark against no filters and bip158 filters on the mainnet chain specifically because it’s really the only benchmark that matters.

pstratem force-pushed on Jan 26, 2023

pstratem commented at 10:29 am on January 26, 2023: contributor

@theStack a more useful performance benchmark is that im looking into improving the filter decoder since that’s about 50% of the cpu time

theStack commented at 11:30 am on January 26, 2023: contributor

@pstratem: The main idea of the benchmark would be to determine the performance dependent of the wallet’s keypool size. It’s rather unlikely that a freshly created wallet (creating 8000 keys with default settings) shows the same speed-up as one that is in heavily in use daily and has hundreds of thousands keys in the pool, e.g. an exchange. At the very least, it would be interesting to know the keypool size of the wallet you used for the results shown in the PR description.

pstratem commented at 11:42 am on January 26, 2023: contributor

@theStack the wallet I used had 10k keys, with more keys it will be slower since it does till have to do some processing for each key for each block.

edit: with 0 keys it’s 5.4 minutes

pstratem force-pushed on Jan 26, 2023

brunoerg commented at 9:52 am on January 27, 2023: contributor

Is it possible to see this performance improvement in any functional test?

Sjors commented at 2:36 pm on January 27, 2023: member

I agree with others above that this pull requests needs more explanation. The name “wallet” is also a bit confusing, since the basic block filter also used for wallets.

Can this be implemented with a new type of block filter, e.g. call it FAST, so that adding the index is a matter of -blockfilterindex=fast? That would probably make this PR smaller.

pstratem commented at 3:26 pm on January 28, 2023: contributor

@Sjors no it cannot

Can this be implemented with a new type of block filter, e.g. call it FAST, so that adding the index is a matter of -blockfilterindex=fast? That would probably make this PR smaller.

edit: to be clear that was the way i tried to do this initially a long time ago, it was a huge headache changing the disk format and storing the siphash keys

pstratem commented at 4:10 pm on January 28, 2023: contributor

@Sjors I’m not sure what else needs explaining, but I’m happy to explain things if i know what’s confusing.

pstratem commented at 7:41 am on January 29, 2023: contributor

Let me clarify some, basically I don’t think the BlockFilter/BlockFilterIndex interface can be reasonably changed to be fast. There’s a few issues (at least one of which is my fault).

The BlockFilter and BlockFilterIndex interfaces assume that the GCSFilter::Params can be generated just from the filter type and the block_hash. I previously tried changing these interfaces so that they didn’t make this assumption, but I found that to involve a lot of changes that were frankly just confusing.

The BlockFilter serialization matches the BIP157/158 serialization, but isn’t the serialization that I want for the wallet rescan index. Specifically the index ends up writing the block_hash twice and the filter_type to the flat file, both of which are implied when looking up the filter in the first place. (They waste disk space and decode time).

Lastly the BlockFilterIndex appends a sha256 hash to the end to check for disk corruption, this would be a significant cost (indeed the siphash that I’m using now is 10% of the total runtime, I’m going to replace it with a crc32c).

in src/blockfilter.cpp:50 in 9035eb95b2 outdated

45+    std::vector<uint64_t> ranged_elements;
46+    ranged_elements.reserve(m_hashed_elements.size());
47+    for (const uint64_t& hashed_element : m_hashed_elements) {
48+        ranged_elements.push_back(RangeHashedElement(hashed_element, F));
49+    }
50+    return ranged_elements;

achow101 commented at 7:23 pm on January 30, 2023:

In 9035eb95b286f0c28d402778118ac9eb10a840d5 “Introduce GCSFilter::QuerySet a cached hash query set for GCSFilter::MatchAny”

Should m_hashed_elements be sorted first, or ranged_elements be sorted afterwards? m_hashed_elements may not be sorted depending on which variation of insert was called earlier.

pstratem commented at 7:08 am on February 1, 2023:

m_hashed_elements needs to be sorted before it’s used in the comparison, whether it’s before or after being ranged doesn’t change the result, but does change the runtime (the range function doesn’t change the sort order of the list).

by doing the sort before ranging we only have to do it once per unique set of elements, which is a performance win.

it looks like i did mess up the initial commit, it’s fixed in the later commit that makes sorting explicit, I can squash most of that into the initial commit.

pstratem commented at 3:19 am on February 3, 2023:

I’ve broken out this change into it’s own commit with an explanation.

in src/index/walletfilterindex.cpp:30 in d7a50ae6a6 outdated

25+/** The pre-allocation chunk size for fltr?????.dat files */
26+constexpr unsigned int FLTR_FILE_CHUNK_SIZE = 0x100000; // 1 MiB
27+
28+// value for M explained https://github.com/sipa/writeups/tree/main/minimizing-golomb-filters
29+constexpr uint8_t WALLET_FILTER_P = 19;
30+constexpr uint32_t WALLET_FILTER_M = 784931; // 1.497137 * pow(2,WALLET_FILTER_P);

achow101 commented at 7:46 pm on January 30, 2023:

In d7a50ae6a64c15190781c40d34146d1a3eb01934 “Implement WalletFilterIndex.”

These already exist in src/blockfilter.h, I don’t think they need to be redefined.

pstratem commented at 7:11 am on February 1, 2023:

It might make sense to change these values from the BASIC filter values, changing P =32 improves the false positive rate from 1 in 784,931 to 1 in 6,430,154,452 for a trade off of 68% larger filters.

It also might make sense to make it a configuration option when the filters are generated, the value could easily be stored in the index leveldb instead of being a constant.

in src/index/walletfilterindex.h:17 in d7a50ae6a6 outdated

12+#include <index/base.h>
13+#include <util/hasher.h>
14+
15+static constexpr bool DEFAULT_WALLETFILTERINDEX{false};
16+
17+class WalletFilterIndex final : public BaseIndex

achow101 commented at 7:55 pm on January 30, 2023:

In d7a50ae6a64c15190781c40d34146d1a3eb01934 “Implement WalletFilterIndex.”

Several of these functions are identical between WalletFilterIndex and BlockFilterIndex. Could these be refactored and deduplicated?

pstratem commented at 7:21 am on February 1, 2023:

WalletFilterIndex::CustomCommit, WalletFilterElements, and DBHashKey are all candidates.

WalletFilterElements and DBHashKey I can certainly refactor to consolidate the logic.

The CustomCommit method though seems like it would end up adding a bunch of complexity to reuse with very little benefit.

in test/functional/wallet_faster_rescan.py:23 in 523b709546 outdated

18+KEYPOOL_SIZE = 100   # smaller than default size to speed-up test
19+NUM_DESCRIPTORS = 9  # number of descriptors (8 default ranged ones + 1 fixed non-ranged one)
20+NUM_BLOCKS = 6       # number of blocks to mine
21+
22+
23+class WalletFasterRescanTest(BitcoinTestFramework):

achow101 commented at 7:57 pm on January 30, 2023:

In 523b7095462c7aa8e2ba2b1110938ac9a2aa3c4d " test: add test for faster rescan using block filters (top-up detection)"

This test is a literally a copy of wallet_fast_rescan.py. I think it would be better to just extend wallet_fast_rescan.py to run its tests twice, once with -blockfilterindex and a second time with -walletfilterindex. If we want parallelism in the test runner, could also add a CLI option to the test to run it with either of those indexes.

pstratem commented at 7:24 am on February 1, 2023:

I think I can do that, but I haven’t written many of the functional tests so that might take some trial and error.

in src/blockfilter.cpp:161 in ec165ea941 outdated

152@@ -158,9 +153,9 @@ bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
153         while (true) {
154             if (hashes_index == size) {
155                 return false;
156-            } else if (element_hashes[hashes_index] == value) {
157+            } else if (RangeHashedElement(element_hashes[hashes_index]) == value) {
158                 return true;
159-            } else if (element_hashes[hashes_index] > value) {
160+            } else if (RangeHashedElement(element_hashes[hashes_index]) > value) {

achow101 commented at 8:19 pm on January 30, 2023:

In ec165ea9412bd2ac2b524209512fe248ce45cf07 “Truncate the hashed elements into range inside MatchInternal”

Is it possible for the sort order after the truncation to be different from the order before?

pstratem commented at 7:36 am on February 1, 2023:

No the truncation doesn’t change the sort order, the fast range function is just (x*n) » 64, the order of which is always going to be the same as the order of x.

Doing the Range inside the MatchInternal means we don’t have to make a copy of the array.

achow101 commented at 9:29 pm on January 30, 2023: member

getindexinfo needs to be updated to include the wallet filter index.

I’m not entirely convinced that the extra effort to implement and maintain an index of filters for wallet use only is actually worth the benefit. While this does significantly improve the rescan time, it’s not clear how often people rescan to make this worthwhile. Rescanning shouldn’t be done all that frequently, so this might not end up being all that useful? It’d certainly be less of an issue if the index could be deduplicated with the block filter index.

in src/Makefile.am:466 in 050716c48d outdated

462@@ -463,6 +463,7 @@ endif
463 libbitcoin_wallet_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) $(BOOST_CPPFLAGS) $(BDB_CPPFLAGS) $(SQLITE_CFLAGS)
464 libbitcoin_wallet_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
465 libbitcoin_wallet_a_SOURCES = \
466+  blockfilter.cpp \

achow101 commented at 9:38 pm on January 30, 2023:

In 050716c48d703424dc94fde9d7f987b55cbff6a9 “Use wallet filter during rescan if available.”

I feel like there’s a better way to do this, but I’m not familiar enough with build systems to suggest one. Perhaps @fanquake might have an idea?

pstratem commented at 7:38 am on February 1, 2023:

yes this felt kind of wrong but I didn’t see another way to achieve the result. suggestions definitely wanted.

pstratem commented at 7:06 am on February 1, 2023: contributor

@achow101 These filters can be used for everything we use the other block filters for, I’ve only implemented the wallet query because that’s the biggest win I see, but there’s no reason they couldn’t be used everywhere else (where there might be similar speed ups available).

maybe I should change the name of the index, FixedBlockFilterIndex ?

Introduce GCSFilter::QuerySet a cached hash query set for GCSFilter::MatchAny

Caching the hashed and sorted elements allows for a substantially faster
GCSFilter::MatchAny. We will use this later for faster wallet rescans.

105388178b

Introduce GCSFilter::MatchAny that supports QuerySet ba2b802e00

pstratem force-pushed on Feb 1, 2023

Implement WalletFilterIndex.

This index is very similar to the BIP158 compact block filter indexes with the
key difference that the siphash key is random per node rather than per block.

The static key makes it possible to build a pre-hashed, pre-sorted query set
for very fast scanning of block filters.

1d1f56bf6e

Add walletfilterindex chain interfaces. ec25a4060c

pstratem force-pushed on Feb 1, 2023

Simplify filter lookup interface to only require the block_hash. 1dd3d54ebf

Use wallet filter during rescan if available. 23175726e8

rpc: doc: mention rescan speedup using walletfilterindex=1 in affected wallet RPCs d45788d19c

pstratem force-pushed on Feb 1, 2023

Eliminate BuildHashedSet to make logic more flexible for future changes. 04ccb5eb92

Move the RangeHashedElement call into MatchInternal.

Previously we hashed, ranged, and then sorted. Now we're hashing, sorting,
and then ranging. This is ok because the order of the hashed elements
will always match the order of the ranged hashed elements.

This avoids a copy of the hashed elements being made.

5db1244993

pstratem force-pushed on Feb 2, 2023

DrahtBot added the label Needs rebase on Apr 21, 2023

DrahtBot commented at 10:28 am on April 21, 2023: contributor

🐙 This pull request conflicts with the target branch and needs rebase.

achow101 requested review from josibake on Apr 25, 2023

achow101 requested review from Sjors on Apr 25, 2023

josibake commented at 12:37 pm on May 1, 2023: contributor

Concept -0

While this may be very useful for certain wallet usage patterns, this doesn’t seem generally useful for all wallets, which makes it hard to justify the review/complexity/maintenance burden.

@achow101 These filters can be used for everything we use the other block filters for, I’ve only implemented the wallet query because that’s the biggest win I see, but there’s no reason they couldn’t be used everywhere else (where there might be similar speed ups available).

Wallet rescans and serving BIP158 filters are the only use cases for the block filter index that I’m aware of. If you have other examples, it would be great to enumerate them.

maybe I should change the name of the index, FixedBlockFilterIndex ?

Rather than make a new index, if there are ways to improve the existing BlockFilter index, I think that would be much better as we would be improving two existing use cases without needing to maintain a new index.

Overall, while there is clearly an improvement over using the existing BlockFilter index for wallet rescans, I think wallet rescans with the existing index are “good enough” and adding an extra index provides diminishing returns.

furszy commented at 12:42 pm on May 1, 2023: member

Rather than make a new index, if there are ways to improve the existing BlockFilter index, I think that would be much better as we would be improving two existing use cases without needing to maintain a new index. @josibake, orthogonal topic but check #26966 and #27006 :).

DrahtBot commented at 0:06 am on July 30, 2023: contributor

There hasn’t been much activity lately and the patch still needs rebase. What is the status here?

Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
Is it no longer relevant? ➡️ Please close.
Did the author lose interest or time to work on this? ➡️ Please close it and mark it ‘Up for grabs’ with the label, so that it can be picked up in the future.

achow101 commented at 4:02 pm on September 20, 2023: member

This PR does not seem to have conceptual support. Please leave a comment if you would like this to be reopened.

achow101 closed this on Sep 20, 2023

wallet: improve rescan performance 640% #26951

Reviews

Conflicts