wallet: Reset reused transactions cache #17843

fjahr · 2020-01-02T00:50:16Z

Fixes #17603 (together with #17824)

getbalances is using the cache within GetAvailableCredit under certain conditions here. For a wallet with avoid_reuse activated this can lead to inconsistent reporting of used transactions/balances between getbalances and listunspent as pointed out in #17603. When an address is reused before the first transaction is spending from this address, the cache is not updated even after the transaction is sent. This means the remaining outputs at the reused address are not showing up as used in getbalances.

With this change, any newly incoming transaction belonging to the wallet marks all the other outputs at the same address as dirty.

DrahtBot · 2020-01-02T05:27:25Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17889 (wallet: Improve CWallet:MarkDestinationsDirty by promag)
#17838 (test: test the >10 UTXO case for output groups by kallewoof)
#17824 (wallet: Improve coin selection for destination groups >10 by fjahr)
#9381 (Remove CWalletTx merging logic from AddToWallet by ryanofsky)

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.

promag

Concept ACK.

promag · 2020-01-02T16:04:40Z

src/wallet/wallet.cpp

+                if (AddDestData(batch, dst, "used", "p")) {
+                    // mark all other outputs to the same destination as dirty
+                    // so they pick up the new "used" state as quickly as possible
+                    MarkDestinationTransactionsDirty(dst);


Looks like we should have std::multimap<CTxDestination, CWalletTx*>?

instagibbs

concept ACK

src/wallet/wallet.cpp

kallewoof

LGTM with a few nits

src/wallet/wallet.cpp

kallewoof · 2020-01-03T06:48:08Z

Github spazzing out, but #17843 (comment) is in response to @instagibbs suggestion to break. I think breaking would skip over any remaining UTXO:s sent to the same address.

promag

I think current approach is really bad - SetUsedDestinationState is called for each spent TXO which in turn will iterate all wallet transaction outputs.

I see 2 options to improve:

have an index like std::multimap<CTxDestination, CWalletTx*>
accumulate all CTxDestination to be marked dirty and then iterate the wallet transactions just once.

kallewoof · 2020-01-03T12:20:50Z

@promag You may be right. Would love to see worst case scenario analysis (is this O(n) or O(n^2) or worse?).

promag

@kallewoof I think it's O(n). Problem is that for big wallets, all transaction outputs will be scanned as much as the input count of the new transaction.

src/wallet/wallet.cpp

kallewoof · 2020-01-03T12:52:45Z

@kallewoof I think it's O(n). Problem is that for big wallets, all transaction outputs will be scanned as much as the input count of the new transaction.

So if n is wallet size and m is input count, this would be O(nm). That's pretty bad, but honestly don't think it's a huge deal. I could be wrong, though.

instagibbs · 2020-01-03T16:53:47Z

This might make a good topic for IRC meeting. I think making this slower is ok provided it's opt-in, which it appears to be based on the required avoid_reuse wallet flag guarding SetUsedDestinationState. An algorithmic cleanup is of course encouraged.

achow101 · 2020-01-03T16:55:13Z

I agree with @promag. I think we should use std::unordered_multimap and accumulate the destinations so that it can all be done with one iteration over the fewest CWalletTxs needed. O(nm) can be pretty slow. We already know that for large wallets, things that do this kind of iteration can take a while so I think we should try to avoid further iteration like this, especially in something that will be called as frequently as every incoming transaction.

promag · 2020-01-03T17:08:24Z

I also think it's fine to improve in a follow up and have the fix merged. In that case I'd just change this to do as suggested:

accumulate all CTxDestination to be marked dirty and then iterate the wallet transactions just once.

which is pretty simple.

fjahr · 2020-01-03T17:31:02Z

Thanks for the feedback everyone! I can improve the PR as suggested by @promag shortly, no need to have a separate follow-up for that. But a further improvement using an index could be a follow-up.

fjahr · 2020-01-06T18:02:46Z

Pushed update including most of the feedback and implementing the simpler solution suggestion by @promag:

accumulate all CTxDestination to be marked dirty and then iterate the wallet transactions just once.

src/wallet/wallet.cpp

achow101

ACK 88291a5

src/wallet/wallet.cpp

src/wallet/wallet.h

fjahr · 2020-01-08T17:49:05Z

Rebased and addressed feedback.

kallewoof

Code reviewed, looks good aside from outdated comment.

src/wallet/wallet.h

If a destination is reused we mark the cache of the other transactions going to that destination dirty so they are not accidentally reported as trusted when the cache is hit.

fjahr · 2020-01-13T12:43:36Z

I did some rough benchmarks to see how this would affect biggish wallets, and am not seeing any significant drops in performance:

Thanks a lot for running these!

Pushed update to outdated comment.

promag

ACK 6fc554f.

kallewoof · 2020-01-14T11:27:45Z

Code review re-ACK 6fc554f

achow101

Re-ACK 6fc554f

meshcollider

Code review ACK 6fc554f

Thanks!

6fc554f wallet: Reset reused transactions cache (Fabian Jahr) Pull request description: Fixes #17603 (together with #17824) `getbalances` is using the cache within `GetAvailableCredit` under certain conditions [here](https://github.com/bitcoin/bitcoin/blob/35fff5be60e853455abc24713481544e91adfedb/src/wallet/wallet.cpp#L1826). For a wallet with `avoid_reuse` activated this can lead to inconsistent reporting of `used` transactions/balances between `getbalances` and `listunspent` as pointed out in #17603. When an address is reused before the first transaction is spending from this address, the cache is not updated even after the transaction is sent. This means the remaining outputs at the reused address are not showing up as `used` in `getbalances`. With this change, any newly incoming transaction belonging to the wallet marks all the other outputs at the same address as dirty. ACKs for top commit: kallewoof: Code review re-ACK 6fc554f promag: ACK 6fc554f. achow101: Re-ACK 6fc554f meshcollider: Code review ACK 6fc554f Tree-SHA512: c4cad2c752176d16d77b4a4202291d20baddf9f27250896a40274d74a6945e0f6b34be04c2f9b1b2e756d3ac669b794969df8f82a98e0b16f10e92f276649ea2

6fc554f wallet: Reset reused transactions cache (Fabian Jahr) Pull request description: Fixes bitcoin#17603 (together with bitcoin#17824) `getbalances` is using the cache within `GetAvailableCredit` under certain conditions [here](https://github.com/bitcoin/bitcoin/blob/35fff5be60e853455abc24713481544e91adfedb/src/wallet/wallet.cpp#L1826). For a wallet with `avoid_reuse` activated this can lead to inconsistent reporting of `used` transactions/balances between `getbalances` and `listunspent` as pointed out in bitcoin#17603. When an address is reused before the first transaction is spending from this address, the cache is not updated even after the transaction is sent. This means the remaining outputs at the reused address are not showing up as `used` in `getbalances`. With this change, any newly incoming transaction belonging to the wallet marks all the other outputs at the same address as dirty. ACKs for top commit: kallewoof: Code review re-ACK 6fc554f promag: ACK 6fc554f. achow101: Re-ACK 6fc554f meshcollider: Code review ACK 6fc554f Tree-SHA512: c4cad2c752176d16d77b4a4202291d20baddf9f27250896a40274d74a6945e0f6b34be04c2f9b1b2e756d3ac669b794969df8f82a98e0b16f10e92f276649ea2

fanquake · 2020-01-29T11:41:32Z

@meshcollider does this need backporting to 0.19?

If a destination is reused we mark the cache of the other transactions going to that destination dirty so they are not accidentally reported as trusted when the cache is hit. Github-Pull: bitcoin#17843 Rebased-From: 6fc554f

fanquake · 2020-02-06T06:12:33Z

Being backported in #18083.

f11872c wallet: Reset reused transactions cache (Fabian Jahr) Pull request description: Backport of #17843 Required porting to pre-`WalletBatch` ACKs for top commit: kallewoof: Code review ACK f11872c laanwj: code review ACK f11872c meshcollider: utACK f11872c Tree-SHA512: 5cf5f136d1eafb0783c2e6799e3675ebc50997ebb56b379d8a198ac35eb3b32f6b98656760a8b1c821eeac665eb80efb1723dd4e9eb58d2b4d45c4674499bedf

[0.19] Backports bitcoin#17858 Unbreak build with Boost 1.72.0 bitcoin#17654 cli: fix Fatal LevelDB error when specifying -blockfilterindex=basic twice bitcoin#17687 rpc: require second argument only for scantxoutset start action bitcoin#17728 wallet: Fix origfee return for bumpfee with feerate arg bitcoin#17643 test: fix "bitcoind already running" warnings on macOS bitcoin#17488 net: Log to net category for exceptions in ProcessMessages bitcoin#17762 Updates to appveyor config for VS2019 and Qt5.9.8 + msvc project fixes bitcoin#17364 Appveyor improvement - text file for vcpkg package list bitcoin#17416 Update msvc build for Visual Studio 2019 v16.4 bitcoin#17736 scripts: fix symbol-check & security-check argument passing bitcoin#17857 qt: Periodic translations update for 0.19 branch IsUsedDestination should count any known single-key address bitcoin#17621 init: Stop indexes on shutdown after ChainStateFlushed callback. bitcoin#17897 qt: Translations update pre-rc1 wallet: Reset reused transactions cache bitcoin#17843 Squashed 'src/univalue/' changes from 7890db9..98261b1 0.19: Update univalue subtree bitcoin#18100 qt: Pre-rc2 translations update

[0.19] Backports bitcoin#17858 Unbreak build with Boost 1.72.0 bitcoin#17654 cli: fix Fatal LevelDB error when specifying -blockfilterindex=basic twice bitcoin#17687 rpc: require second argument only for scantxoutset start action bitcoin#17728 wallet: Fix origfee return for bumpfee with feerate arg bitcoin#17643 test: fix "bitcoind already running" warnings on macOS bitcoin#17488 net: Log to net category for exceptions in ProcessMessages bitcoin#17762 Updates to appveyor config for VS2019 and Qt5.9.8 + msvc project fixes bitcoin#17364 Appveyor improvement - text file for vcpkg package list bitcoin#17416 Update msvc build for Visual Studio 2019 v16.4 bitcoin#17736 scripts: fix symbol-check & security-check argument passing bitcoin#17857 qt: Periodic translations update for 0.19 branch IsUsedDestination should count any known single-key address bitcoin#17621 init: Stop indexes on shutdown after ChainStateFlushed callback. bitcoin#17897 qt: Translations update pre-rc1 wallet: Reset reused transactions cache bitcoin#17843 Squashed 'src/univalue/' changes from 7890db9..98261b1 0.19: Update univalue subtree bitcoin#18100 qt: Pre-rc2 translations update [0.19] Further 0.19 backports bitcoin#18218 build: don't embed a build-id when building libdmg-hfsplus bitcoin#18004

a2324e4 test: Improve naming and logging of avoid_reuse tests (Fabian Jahr) 1abbdac wallet: Prefer full destination groups in coin selection (Fabian Jahr) Pull request description: Fixes #17603 (together with #17843) In the case of destination groups of >10 outputs existing in a wallet with `avoid_reuse` enabled, the grouping algorithm is adding left-over outputs as an "incomplete" group to the list of groups even when a full group has already been added. This leads to the strange behavior that if there are >10 outputs for a destination the transaction spending from that will effectively use `len(outputs) % 10` as inputs for that transaction. From the original PR and the code comment I understand the correct behavior should be the usage of 10 outputs. I opted for minimal changes in the current code although there maybe optimizations possible for cases with >20 outputs on a destination this sounds like too much of an edge case right now. ACKs for top commit: jonatack: Re-ACK a2324e4 achow101: ACK a2324e4 kallewoof: ACK a2324e4 meshcollider: Tested ACK a2324e4 (verified the new test fails on master without this change) Tree-SHA512: 4743779c5d469fcd16df5baf166024b1d3c8eaca151df1e8281b71df62b29541cf7bfee3f8ab48d83e3b34c9256e53fd38a7b146a54c79f9caa44cce3636971a

…election a2324e4 test: Improve naming and logging of avoid_reuse tests (Fabian Jahr) 1abbdac wallet: Prefer full destination groups in coin selection (Fabian Jahr) Pull request description: Fixes bitcoin#17603 (together with bitcoin#17843) In the case of destination groups of >10 outputs existing in a wallet with `avoid_reuse` enabled, the grouping algorithm is adding left-over outputs as an "incomplete" group to the list of groups even when a full group has already been added. This leads to the strange behavior that if there are >10 outputs for a destination the transaction spending from that will effectively use `len(outputs) % 10` as inputs for that transaction. From the original PR and the code comment I understand the correct behavior should be the usage of 10 outputs. I opted for minimal changes in the current code although there maybe optimizations possible for cases with >20 outputs on a destination this sounds like too much of an edge case right now. ACKs for top commit: jonatack: Re-ACK a2324e4 achow101: ACK a2324e4 kallewoof: ACK a2324e4 meshcollider: Tested ACK a2324e4 (verified the new test fails on master without this change) Tree-SHA512: 4743779c5d469fcd16df5baf166024b1d3c8eaca151df1e8281b71df62b29541cf7bfee3f8ab48d83e3b34c9256e53fd38a7b146a54c79f9caa44cce3636971a

Summary: If a destination is reused we mark the cache of the other transactions going to that destination dirty so they are not accidentally reported as trusted when the cache is hit. --- Backport of Core [[bitcoin/bitcoin#17843 | PR17843]] Test Plan: ninja check check-functional Reviewers: #bitcoin_abc, deadalnix Reviewed By: #bitcoin_abc, deadalnix Differential Revision: https://reviews.bitcoinabc.org/D7685

6fc554f wallet: Reset reused transactions cache (Fabian Jahr) Pull request description: Fixes bitcoin#17603 (together with bitcoin#17824) `getbalances` is using the cache within `GetAvailableCredit` under certain conditions [here](https://github.com/bitcoin/bitcoin/blob/35fff5be60e853455abc24713481544e91adfedb/src/wallet/wallet.cpp#L1826). For a wallet with `avoid_reuse` activated this can lead to inconsistent reporting of `used` transactions/balances between `getbalances` and `listunspent` as pointed out in bitcoin#17603. When an address is reused before the first transaction is spending from this address, the cache is not updated even after the transaction is sent. This means the remaining outputs at the reused address are not showing up as `used` in `getbalances`. With this change, any newly incoming transaction belonging to the wallet marks all the other outputs at the same address as dirty. ACKs for top commit: kallewoof: Code review re-ACK 6fc554f promag: ACK 6fc554f. achow101: Re-ACK 6fc554f meshcollider: Code review ACK 6fc554f Tree-SHA512: c4cad2c752176d16d77b4a4202291d20baddf9f27250896a40274d74a6945e0f6b34be04c2f9b1b2e756d3ac669b794969df8f82a98e0b16f10e92f276649ea2

f11872c wallet: Reset reused transactions cache (Fabian Jahr) Pull request description: Backport of bitcoin#17843 Required porting to pre-`WalletBatch` ACKs for top commit: kallewoof: Code review ACK f11872c laanwj: code review ACK f11872c meshcollider: utACK f11872c Tree-SHA512: 5cf5f136d1eafb0783c2e6799e3675ebc50997ebb56b379d8a198ac35eb3b32f6b98656760a8b1c821eeac665eb80efb1723dd4e9eb58d2b4d45c4674499bedf

fjahr mentioned this pull request Jan 2, 2020

wallet: Prefer full destination groups in coin selection #17824

Merged

fanquake requested a review from achow101 January 2, 2020 00:51

fanquake added the Wallet label Jan 2, 2020

fanquake requested review from instagibbs and kallewoof January 2, 2020 00:52

promag reviewed Jan 2, 2020

View reviewed changes

instagibbs reviewed Jan 2, 2020

View reviewed changes

src/wallet/wallet.cpp Show resolved Hide resolved

kallewoof reviewed Jan 3, 2020

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Show resolved Hide resolved

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Show resolved Hide resolved

promag reviewed Jan 3, 2020

View reviewed changes

src/wallet/wallet.cpp Show resolved Hide resolved

fanquake added the Waiting for author label Jan 4, 2020

fjahr force-pushed the getbalances branch from 88a4e47 to f4473aa Compare January 6, 2020 17:57

promag reviewed Jan 6, 2020

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

instagibbs reviewed Jan 6, 2020

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

fjahr force-pushed the getbalances branch from f4473aa to 88291a5 Compare January 6, 2020 19:01

achow101 reviewed Jan 6, 2020

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Show resolved Hide resolved

promag reviewed Jan 6, 2020

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Show resolved Hide resolved

src/wallet/wallet.h Outdated Show resolved Hide resolved

promag mentioned this pull request Jan 7, 2020

wallet: Improve CWallet:MarkDestinationsDirty #17889

Merged

DrahtBot added the Needs rebase label Jan 7, 2020

fjahr force-pushed the getbalances branch from 88291a5 to 7618ea2 Compare January 8, 2020 17:39

kallewoof reviewed Jan 11, 2020

View reviewed changes

src/wallet/wallet.h Show resolved Hide resolved

wallet: Reset reused transactions cache

6fc554f

If a destination is reused we mark the cache of the other transactions going to that destination dirty so they are not accidentally reported as trusted when the cache is hit.

fjahr force-pushed the getbalances branch from 9e98d6c to 6fc554f Compare January 13, 2020 12:41

promag reviewed Jan 14, 2020

View reviewed changes

fanquake requested review from kallewoof and achow101 January 14, 2020 10:42

kallewoof approved these changes Jan 14, 2020

View reviewed changes

achow101 approved these changes Jan 14, 2020

View reviewed changes

meshcollider reviewed Jan 15, 2020

View reviewed changes

meshcollider merged commit 6fc554f into bitcoin:master Jan 15, 2020

kallewoof mentioned this pull request Jan 15, 2020

test: test the >10 UTXO case for output groups #17838

Closed

Sjors mentioned this pull request Jan 17, 2020

Make ScriptPubKeyMan an actual interface and the wallet to have multiple #17261

Merged

luke-jr mentioned this pull request Feb 6, 2020

[0.19] wallet: Reset reused transactions cache #18083

Merged

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

wallet: Reset reused transactions cache #17843

wallet: Reset reused transactions cache #17843

Uh oh!

Conversation

fjahr commented Jan 2, 2020

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

promag Jan 2, 2020

Choose a reason for hiding this comment

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kallewoof left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

kallewoof commented Jan 3, 2020

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

kallewoof commented Jan 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kallewoof commented Jan 3, 2020

Uh oh!

instagibbs commented Jan 3, 2020

Uh oh!

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

Uh oh!

Uh oh!

promag commented Jan 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fjahr commented Jan 3, 2020

Uh oh!

fjahr commented Jan 6, 2020

Uh oh!

Uh oh!

Uh oh!

achow101 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

fjahr commented Jan 8, 2020

Uh oh!

kallewoof left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

fjahr commented Jan 13, 2020

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

kallewoof commented Jan 14, 2020

Uh oh!

achow101 left a comment

Choose a reason for hiding this comment

Uh oh!

meshcollider left a comment

DrahtBot commented Jan 2, 2020 •

edited

Loading

kallewoof commented Jan 3, 2020 •

edited

Loading

achow101 commented Jan 3, 2020 •

edited

Loading

promag commented Jan 3, 2020 •

edited

Loading