wallet: Fast rescan with BIP157 block filters by maflcko · Pull Request #15845 · bitcoin/bitcoin

maflcko · 2019-04-18T18:40:45Z

Use BIP157 block filters if they are available to speed up rescans

gmaxwell · 2019-04-18T18:44:57Z

Concept ACK

jnewbery · 2019-04-18T18:53:46Z

Concept ACK

sipa · 2019-04-18T18:54:04Z

Just because we know about a script does not imply we're watching it I believe.

Sure, but I'd rather err on the safe side of scanning a block too much than missing a block (and thus lose coins)

jonasschnelli · 2019-04-18T18:58:49Z

Nice! That was quick.
Concept ACK

jonasschnelli · 2019-04-18T20:14:06Z

Some rough benchmarks

{
"start_height": 0,
"stop_height": 572152
}

real 4m23.596s

A simple wallet,... filtered out roughly 2900 blocks and scanned them.

DrahtBot · 2019-04-19T22:20:20Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17384 (test: Create new test library by MarcoFalke)
#16528 ([WIP] Native Descriptor Wallets (take 2) by achow101)
#16442 (Serve BIP 157 compact filters by jimpo)

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.

Coverage

Coverage	Change (pull 15845, 77e593bc79216175fa4c2fd05278bf1b7e4c7146)	Reference (master, `56376f3`)
Lines	+0.0064 %	87.5552 %
Functions	-0.0143 %	84.6451 %
Branches	+0.0017 %	51.5534 %

^{Updated at: 2019-04-19T22:20:19.826705.}

jimpo

Yay, Concept ACK.

Comments:

I noticed there are lots of false positive hits because DEFAULT_KEYPOOL_SIZE is 1,000, with is multiplied by like 2 or 4 (I forget) with all of the scriptPubKey variants added for a key. Why is the default keypool size so large?
The scanning might be faster using the method to batch fetch filters, LookupFilterRange. It's probably not worth the additional complexity in the wallet and chain interface code though.

jimpo · 2019-04-19T23:11:46Z

Maybe make the BlockFilterType a parameter here?

Will there ever be a filter different from the basic filter?

instagibbs · 2019-04-20T19:06:54Z

@jimpo

Why is the default keypool size so large?

IIRC this makes it much less likely typical usage will hit a case when an encrypted wallet runs out of viable keys and starts to miss funds during a sync(since it currently doesn't pause a sync and ask the user for password).

instagibbs · 2019-04-20T19:07:19Z

and the obligatory concept ACK!

gmaxwell · 2019-04-20T20:00:30Z

Why is the default keypool size so large?

It isn't. It's small... the whole concept of 'gap' scanning is fairly broken and easily results in funds loss... e.g. when a user hands out multiple addresses to people who haven't used them yet. The brokenness can be largely addressed by setting the lookahead pretty far.

In some prelim testing this appears to be slower than just rescanning the block files directly with a specialized parser. :(

sipa · 2019-04-20T20:36:16Z

@gmaxwell What specialized parser are you comparing to? Does it include the time to match all outputs/inputs to a set of 6000 sPKs?

sipa · 2019-04-20T20:42:21Z

@jimpo 2 keypools (external and change), each 1000 keys, each key 3 sPKs (p2pkh, p2sh-p2wpkh, native p2wpkh), so I expect 6000 entries to match against.

gmaxwell · 2019-05-11T19:56:09Z

@gmaxwell modified copy of the old scanner from bitcoin talk, doesn't check the inputs. I think the main issue is that rehashing all addresses for each block sequentially is pegging a single core and limiting the speed.

maflcko · 2019-11-05T13:43:25Z

Thanks for the review @mzumsande , @luke-jr , @jkczyz . Addressed all your feedback in the latest push

Talkless · 2019-11-06T17:32:41Z

+        const BlockFilterIndex* block_filter_index = GetBlockFilterIndex(BlockFilterType::BASIC);
+        if (!block_filter_index) return {};
+        BlockFilter filter;
+        const CBlockIndex* index;


This could lock even smaller block of code:

{ LOCK(cs_main); index = LookupBlockIndex(hash); } if (!index) return {};

Or maybe you would care to use ES.28: Use lambdas for complex initialization, especially of const variables guideline (note const for index pointer itself):

const CBlockIndex* const index = [&]{ LOCK(cs_main); return LookupBlockIndex(hash); }(); if (!index) return {};

Talkless · 2019-11-06T17:34:05Z

    }
+    Optional<bool> filterMatchesAny(const uint256& hash, const GCSFilter::ElementSet& filter_set) override
+    {
+        const BlockFilterIndex* block_filter_index = GetBlockFilterIndex(BlockFilterType::BASIC);


Looks like the pointer itself could be even const too:
const BlockFilterIndex* const block_filter_index = ...

jnewbery · 2019-11-06T16:38:22Z

-/** Returns the generated coin */
+/** Returns the generated coin (output at index 0 in the coinbase tx) */
 CTxIn MineBlock(const CScript& coinbase_scriptPubKey);
+/** Returns the generated coins (output at index 0 in the coinbase tx), or nothing if the block was invalid */


s/coins/coin/

I also don't like the (mis)use of the word coin here, which is generally understood to mean a utxo. These functions return a CTxIn that points to the first coinbase output.

jnewbery · 2019-11-06T18:50:06Z

    WalletLogPrintf("Rescan started from block %s...\n", start_block.ToString());

+    uint256 block_hash = start_block;
+    const auto filter_set = GetLegacyScriptPubKeyMan()->GetAllRelevantScriptPubKeys();


Setting the filter_set outside the rescan loop means that this doesn't get updated when the keypool is topped up. That means that any payments to an address beyond the first 1000 will be missed on rescan.

jnewbery · 2019-11-06T18:53:45Z

I think as well as fixing the bug here: #15845 (comment), it'd be useful to add a test that would catch cases like this, where a rescan exhausts the keypool.

fa0a731 test: Add RegTestingSetup to setup_common (MarcoFalke) fa54b3e test: move-only ComputeFilter to src/test/lib/blockfilter (MarcoFalke) Pull request description: The default chain for `TestingSetup` is the main chain. However, any test that wants to mine blocks on demand needs to switch to regtest. This is done manually and in-line right now. Fix that by creating an explicit `RegTestingSetup` and use it where appropriate. Also, add a move-only commit to move `ComputeFilter` into the newly created unit test library. Both commits are part of bitcoin#15845, but split up because they are useful on their own. ACKs for top commit: practicalswift: ACK fa0a731 -- diff looks correct Tree-SHA512: 02b9765580b355ed8d1be555f8ae11fa6e3d575f5cb177bbdda0319378837e29de5555c126c477dc8a1e8a5be47335afdcff152cf2dea2fbdd1a988ddde3689b

DrahtBot · 2019-11-07T14:28:10Z

Needs rebase

luke-jr · 2019-11-11T16:13:45Z

+{
+    LOCK(cs_KeyStore);
+    GCSFilter::ElementSet ret;
+    for (const auto& k : mapKeys) {


What about mapCryptedKeys? I don't think mapKeys is used on encrypted wallets?

What about mapCryptedKeys? I don't think mapKeys is used on encrypted wallets?

Yes, this should just loop over mapCryptedKeys as well. mapKeys should be empty in encryped wallets.

This function in general does not match everything that IsMine would match.In particular it doesn't enumerate all possible combinations of multisig policies with all combinations of pubkeys or all of the weird nested scripts that are possible. There probably needs to be a release note that if you have some weird and non-standard script stuff, the fast rescan won't see those things.

Such a warning makes sense; people with such wallets will presumably understand. And descriptor wallets won't have this problem.

IsMine itself won't test weird combinations. I don't see why fast rescan shouldn't be able to check for everything IsMine does... users shouldn't be exposed to internal implementation details like this.

jnewbery · 2020-05-08T01:04:02Z

@MarcoFalke - do you mind documenting the problems with this approach, so people who find this PR in future know why you closed it?

maflcko · 2020-05-08T11:20:02Z

I don't think there are any problems with this approach, once this and this is addressed.

As pointed out here multisig should work just fine, but I haven't had the time or interest to look into this, so I closed it.

taken from bitcoin#15845

fa0a731 test: Add RegTestingSetup to setup_common (MarcoFalke) fa54b3e test: move-only ComputeFilter to src/test/lib/blockfilter (MarcoFalke) Pull request description: The default chain for `TestingSetup` is the main chain. However, any test that wants to mine blocks on demand needs to switch to regtest. This is done manually and in-line right now. Fix that by creating an explicit `RegTestingSetup` and use it where appropriate. Also, add a move-only commit to move `ComputeFilter` into the newly created unit test library. Both commits are part of bitcoin#15845, but split up because they are useful on their own. ACKs for top commit: practicalswift: ACK fa0a731 -- diff looks correct Tree-SHA512: 02b9765580b355ed8d1be555f8ae11fa6e3d575f5cb177bbdda0319378837e29de5555c126c477dc8a1e8a5be47335afdcff152cf2dea2fbdd1a988ddde3689b

sipa reviewed Apr 18, 2019

View reviewed changes

Comment thread src/wallet/wallet.cpp Outdated

sipa reviewed Apr 18, 2019

View reviewed changes

DrahtBot added Utils/log/libs UTXO Db and Indexes Wallet labels Apr 18, 2019

maflcko removed the Utils/log/libs label Apr 18, 2019

maflcko force-pushed the 1904-walletFastRescan branch 3 times, most recently from a0aa855 to 106e7c9 Compare April 19, 2019 14:35

jimpo reviewed Apr 19, 2019

View reviewed changes

maflcko force-pushed the 1904-walletFastRescan branch 5 times, most recently from 3ddbb2a to abcddec Compare April 24, 2019 17:34

DrahtBot added the Needs rebase label Apr 27, 2019

maflcko force-pushed the 1904-walletFastRescan branch from abcddec to 474f9b9 Compare May 17, 2019 16:11

DrahtBot removed the Needs rebase label May 17, 2019

maflcko force-pushed the 1904-walletFastRescan branch from 474f9b9 to 5c9bbcf Compare May 24, 2019 11:06

maflcko force-pushed the 1904-walletFastRescan branch from ce61001 to 7b024b8 Compare November 5, 2019 13:19

MarcoFalke added 2 commits November 5, 2019 08:24

wallet: Add method to get element set for blockfilters

fa99419

wallet: Rescan with blockfilters

faee7b6

maflcko force-pushed the 1904-walletFastRescan branch from 7b024b8 to faee7b6 Compare November 5, 2019 13:40

Talkless reviewed Nov 6, 2019

View reviewed changes

jnewbery reviewed Nov 6, 2019

View reviewed changes

DrahtBot added the Needs rebase label Nov 7, 2019

luke-jr reviewed Nov 11, 2019

View reviewed changes

braydonf mentioned this pull request Mar 25, 2020

Wallet synchronization with indexes bcoin-org/bcoin#944

Open

maflcko closed this May 7, 2020

maflcko deleted the 1904-walletFastRescan branch May 7, 2020 23:20

maflcko added the Up for grabs label May 7, 2020

maflcko mentioned this pull request May 30, 2020

[WIP] wallet: use BlockFilterIndex in ScanForWalletTransactions #19116

Closed

pstratem pushed a commit to pstratem/bitcoin that referenced this pull request May 31, 2020

chain: add filterMatchesAny to chain interface

b59f89b

taken from bitcoin#15845

pstratem pushed a commit to pstratem/bitcoin that referenced this pull request Jun 6, 2020

chain: add filterMatchesAny to chain interface

9daf59d

taken from bitcoin#15845

maflcko removed the Up for grabs label Jun 30, 2020

andronoob mentioned this pull request Jul 28, 2020

Prune locks #19463

Closed

jamesob mentioned this pull request Oct 10, 2021

Add scanblocks RPC call #20664

Closed

maflcko mentioned this pull request Dec 10, 2021

Make rescans faster #23727

Closed

4 tasks

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

maflcko added the Up for grabs label Mar 21, 2022

fanquake removed Up for grabs Needs rebase labels Aug 30, 2022

Uh oh!

Conversation

maflcko commented Apr 18, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gmaxwell commented Apr 18, 2019

Uh oh!

Uh oh!

jnewbery commented Apr 18, 2019

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonasschnelli commented Apr 18, 2019

Uh oh!

jonasschnelli commented Apr 18, 2019

Uh oh!

DrahtBot commented Apr 19, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Coverage

Uh oh!

jimpo left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

instagibbs commented Apr 20, 2019

Uh oh!

instagibbs commented Apr 20, 2019

Uh oh!

gmaxwell commented Apr 20, 2019

Uh oh!

sipa commented Apr 20, 2019

Uh oh!

sipa commented Apr 20, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gmaxwell commented May 11, 2019

Uh oh!

maflcko commented Nov 5, 2019

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jnewbery commented Nov 6, 2019

Uh oh!

DrahtBot commented Nov 7, 2019

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!

jnewbery commented May 8, 2020

Uh oh!

maflcko commented May 8, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

maflcko commented Apr 18, 2019 •

edited

Loading

DrahtBot commented Apr 19, 2019 •

edited

Loading

sipa commented Apr 20, 2019 •

edited

Loading