wallet: Reset reused transactions cache

fjahr commented at 0:50 am on January 2, 2020: member

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.

fanquake requested review from achow101 on Jan 2, 2020

fanquake added the label Wallet on Jan 2, 2020

fanquake requested review from instagibbs on Jan 2, 2020

fanquake requested review from kallewoof on Jan 2, 2020

DrahtBot commented at 5:27 am on January 2, 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:

#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.

in src/wallet/wallet.cpp:717 in 88a4e47fed outdated

709@@ -710,7 +710,12 @@ void CWallet::SetUsedDestinationState(WalletBatch& batch, const uint256& hash, u
710     if (ExtractDestination(srctx->tx->vout[n].scriptPubKey, dst)) {
711         if (IsMine(dst)) {
712             if (used && !GetDestData(dst, "used", nullptr)) {
713-                AddDestData(batch, dst, "used", "p"); // p for "present", opposite of absent (null)
714+                // p for "present", opposite of absent (null)
715+                if (AddDestData(batch, dst, "used", "p")) {
716+                    // mark all other outputs to the same destination as dirty
717+                    // so they pick up the new "used" state as quickly as possible
718+                    MarkDestinationTransactionsDirty(dst);

promag commented at 4:04 pm on January 2, 2020:

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

promag commented at 4:58 pm on January 2, 2020: member

Concept ACK.

in src/wallet/wallet.cpp:3179 in 88a4e47fed outdated

3156+
3157+            if (!ExtractDestination(wtx.tx->vout[i].scriptPubKey, dst))
3158+                continue;
3159+
3160+            if (target_dst == dst) {
3161+                wtx.MarkDirty();

instagibbs commented at 8:08 pm on January 2, 2020:

you can break here.

kallewoof commented at 6:40 am on January 3, 2020:

Won’t that skip 2nd+ reuse?

kallewoof commented at 6:42 am on January 3, 2020:

Could probably simplify to

0if (ExtractDestination(wtx.tx->vout[i].scriptPubKey, dst) && target_dst == dst) {

achow101 commented at 4:45 pm on January 3, 2020:

The entire transaction will have its balances recomputed, so it doesn’t matter if another output in the same tx reuses.

fjahr commented at 5:59 pm on January 6, 2020:

done

fjahr commented at 5:59 pm on January 6, 2020:

done

instagibbs commented at 8:09 pm on January 2, 2020: member

concept ACK

in src/wallet/wallet.cpp:3146 in 88a4e47fed outdated

3142@@ -3138,6 +3143,27 @@ int64_t CWallet::GetOldestKeyPoolTime()
3143     return oldestKey;
3144 }
3145 
3146+void CWallet::MarkDestinationTransactionsDirty(const CTxDestination target_dst)

kallewoof commented at 6:39 am on January 3, 2020:

Can do const CTxDestination& to avoid unnecessary copy, I think.

fjahr commented at 5:57 pm on January 6, 2020:

done

in src/wallet/wallet.cpp:3154 in 88a4e47fed outdated

3149+
3150+    for (auto& entry : mapWallet) {
3151+        CWalletTx& wtx = entry.second;
3152+
3153+        for (unsigned int i = 0; i < wtx.tx->vout.size(); i++)
3154+        {

kallewoof commented at 6:40 am on January 3, 2020:

Nit: { on same line as for; ++i over i++.

fjahr commented at 5:57 pm on January 6, 2020:

done

kallewoof commented at 6:46 am on January 3, 2020: member

LGTM with a few nits

kallewoof commented at 6:48 am on January 3, 2020: member

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

promag commented at 12:02 pm on January 3, 2020: member

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 commented at 12:20 pm on January 3, 2020: member

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

in src/wallet/wallet.cpp:3174 in 88a4e47fed outdated

3147+{
3148+    LOCK(cs_wallet);
3149+
3150+    for (auto& entry : mapWallet) {
3151+        CWalletTx& wtx = entry.second;
3152+

promag commented at 12:34 pm on January 3, 2020:

nit, it could skip this wtx if already dirty, but not sure that’s easy to know.

fjahr commented at 5:59 pm on January 6, 2020:

true, but since MarkDirty just resets several values I think it’s not so easy.

achow101 commented at 10:28 pm on January 6, 2020:

0bool dirty = false;
1for (int i = 0; i < AMOUNTTYPE_ENUM_ELEMENTS; ++i) {
2    dirty |= wtx.m_amounts[i].m_cached.none();
3|
4if (dirty) continue;

should work.

CachableAmount has std::bitset m_cached which sets various bits when something is cached. If no bits are set (checked with none()), nothing is cached so it is dirty and can thus be skipped.

promag commented at 11:26 pm on January 6, 2020:

@achow101 nice, and what about fChangeCached?

Maybe this can be done next to not scope creep, could also add a bool CWalletTx::m_is_dirty to avoid going thru m_amounts.

achow101 commented at 0:06 am on January 7, 2020:

fChangeCached is only for computing the change amounts and isn’t used by GetCachableAmount which is what we care about for marking a tx as dirty. I agree that we should follow that same model and have a variable to indicate whether the tx is marked dirty.

promag commented at 1:44 pm on January 7, 2020:

Actually shouldn’t the check be &= wtx.m_amounts[i].m_cached.none()? If all amounts are empty then no need to extract+markdirty?

promag commented at 1:11 am on January 8, 2020:

I agree that we should follow that same model and have a variable to indicate whether the tx is marked dirty. @achow101 done in #17889.

fjahr commented at 5:44 pm on January 8, 2020:

Implement it, as @promag noted the check actually needed to look that all the cached values are reset, so I did that and restructed it a bit as well.

promag commented at 8:43 pm on January 8, 2020:

I think you could revert this latest change considering what’s done in #17889.

promag commented at 12:41 pm on January 3, 2020: member

@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.

kallewoof commented at 12:52 pm on January 3, 2020: member

@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 commented at 4:53 pm on January 3, 2020: member

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 commented at 4:55 pm on January 3, 2020: member

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 commented at 5:08 pm on January 3, 2020: member

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 commented at 5:31 pm on January 3, 2020: member

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.

fanquake added the label Waiting for author on Jan 4, 2020

fjahr force-pushed on Jan 6, 2020

in src/wallet/wallet.cpp:707 in f4473aafc5 outdated

703@@ -704,18 +704,24 @@ void CWallet::SetUsedDestinationState(WalletBatch& batch, const uint256& hash, u
704 {
705     AssertLockHeld(cs_wallet);
706     const CWalletTx* srctx = GetWalletTx(hash);
707+    std::set<CTxDestination> tx_destinations;

promag commented at 6:01 pm on January 6, 2020:

This must be an argument, like std::set<CTxDestination>& tx_destinations. In the call site you do

0    if (IsWalletFlagSet(WALLET_FLAG_AVOID_REUSE)) {
1        // Mark used destinations
2        std::set<CTxDestination> tx_destinations;
3        for (const CTxIn& txin : wtxIn.tx->vin) {
4            const COutPoint& op = txin.prevout;
5            SetUsedDestinationState(batch, op.hash, op.n, true, tx_destinations);
6        }
7        MarkDestinationsDirty(tx_destinations);
8    }

And remove MarkDestinationsDirty call from here.

fjahr commented at 7:02 pm on January 6, 2020:

fixed

fjahr commented at 6:02 pm on January 6, 2020: member

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.

in src/wallet/wallet.cpp:722 in f4473aafc5 outdated

718                 EraseDestData(batch, dst, "used");
719             }
720         }
721     }
722+
723+    // Mark all other outputs to the same destination dirty so

instagibbs commented at 6:03 pm on January 6, 2020:

Move this comment to the function declaration in the header

fjahr commented at 7:02 pm on January 6, 2020:

done, also reworded it to be more general

fjahr force-pushed on Jan 6, 2020

in src/wallet/wallet.cpp:720 in 88291a582b outdated

716             } else if (!used && GetDestData(dst, "used", nullptr)) {
717                 EraseDestData(batch, dst, "used");
718             }
719         }
720     }
721+

achow101 commented at 10:06 pm on January 6, 2020:

nit: extra line

fjahr commented at 5:45 pm on January 8, 2020:

fixed

achow101 commented at 10:29 pm on January 6, 2020: member

ACK 88291a582b24a54be2b67f965096f4fad78e77b7

in src/wallet/wallet.cpp:713 in 88291a582b outdated

709@@ -710,12 +710,14 @@ void CWallet::SetUsedDestinationState(WalletBatch& batch, const uint256& hash, u
710     if (ExtractDestination(srctx->tx->vout[n].scriptPubKey, dst)) {
711         if (IsMine(dst)) {
712             if (used && !GetDestData(dst, "used", nullptr)) {
713-                AddDestData(batch, dst, "used", "p"); // p for "present", opposite of absent (null)
714+                if (AddDestData(batch, dst, "used", "p")) // p for "present", opposite of absent (null)

promag commented at 11:15 pm on January 6, 2020:

nit, add {}.

fjahr commented at 5:45 pm on January 8, 2020:

done

in src/wallet/wallet.h:968 in 88291a582b outdated

960@@ -961,6 +961,12 @@ class CWallet final : public WalletStorage, private interfaces::Chain::Notificat
961 
962     std::set<CTxDestination> GetLabelAddresses(const std::string& label) const;
963 
964+    /**
965+     * Mark all outputs in a destination dirty so their cache is
966+     * reset and does not return outdated information.
967+     */
968+    void MarkDestinationsDirty(const std::set<CTxDestination>& destinations);

promag commented at 11:32 pm on January 6, 2020:

Add annotation EXCLUSIVE_LOCKS_REQUIRED(cs_wallet) and remove recursive lock in L3149.

fjahr commented at 5:45 pm on January 8, 2020:

done

DrahtBot added the label Needs rebase on Jan 7, 2020

fjahr force-pushed on Jan 8, 2020

fjahr commented at 5:49 pm on January 8, 2020: member

Rebased and addressed feedback.

DrahtBot removed the label Needs rebase on Jan 8, 2020

achow101 commented at 6:57 pm on January 8, 2020: member

ACK 7618ea2cc02042cd20c633de9d29c34b5a1179b0

Just suggested changes and rebase since last review.

promag commented at 9:10 pm on January 8, 2020: member

I think you could revert latest change regarding amount caches considering what’s done in #17889.

fjahr force-pushed on Jan 8, 2020

fjahr commented at 10:32 pm on January 8, 2020: member

I think you could revert latest change regarding amount caches considering what’s done in #17889.

Removed skipping dirty tx again to make it a more coherent change together with #17889. Sorry @achow101 .

promag commented at 10:42 am on January 9, 2020: member

Code review ACK 9e98d6cdf025fbda99a81ab1cecff21f1e45e234.

achow101 commented at 3:45 pm on January 9, 2020: member

ACK 9e98d6cdf025fbda99a81ab1cecff21f1e45e234

fanquake removed the label Waiting for author on Jan 10, 2020

fanquake requested review from instagibbs on Jan 10, 2020

fanquake requested review from kallewoof on Jan 10, 2020

in test/functional/wallet_avoidreuse.py:289 in 9e98d6cdf0 outdated

284+        self.nodes[1].sendtoaddress(ret_addr, 5)
285+
286+        # getbalances and listunspent should show the remaining outputs
287+        # in the reused address as used/reused
288+        assert_unspent(self.nodes[1], total_count=2, total_sum=6, reused_count=1, reused_sum=1)
289+        assert_balances(self.nodes[1], mine={"used": 1, "trusted": 5})

kallewoof commented at 1:32 am on January 10, 2020:

Why is reused sum 1 and not 6? All of the UTXOs should be counted as reused except the change back to self (if any?).

Also assert_balances should be ~all used, no?

fjahr commented at 6:00 pm on January 10, 2020:

There are 11 outputs of 1 BTC at the address and 10 are summed up in a group (OUTPUT_GROUP_MAX_ENTRIES) which is then being used for the inputs. So only one output of 1 BTC is left at the address, 5 BTC have been sent to ret_addr and 5 BTC are in a change address which is trusted (total_sum=6).

kallewoof commented at 1:38 am on January 11, 2020:

You’re right. Thanks for explaining.

kallewoof commented at 1:40 am on January 11, 2020: member

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

 0# 2 btc per send
 1
 2# Master:
 3#
 4# UTXO count    Total Time      Transactions    Time per transaction
 5# 100           00:57           160             0.356
 6# 500           00:56           160             0.350
 7# 1000          01:09           160             0.431
 8# 2000          01:11           160             0.444
 9# 5000          01:55           160             0.719
10
11# With patch:
12#
13# UTXO count    Total Time      Transactions    Time per transaction
14# 100           01:05           160             0.406
15# 500           00:56           160             0.350
16# 1000          01:00           160             0.375
17# 2000          01:22           160             0.513
18# 5000          02:14           160             0.838
19
20# 1/20th of balance per send, gen per 10 tx
21
22# Master:
23#
24# UTXO count    Total Time      Transactions    Time per transaction
25# 100           01:05           160             0.406
26# 500           01:00           160             0.375
27# 1000          01:06           160             0.800
28# 2000          01:03           160             0.394
29# 5000          01:21           160             0.900
30
31# With patch:
32#
33# UTXO count    Total Time      Transactions    Time per transaction
34# 100           01:01           160             0.381
35# 500           00:59           160             0.369
36# 1000          01:02           160             0.388
37# 2000          01:06           160             0.800
38# 5000          01:40           160             0.625

in src/wallet/wallet.h:970 in 9e98d6cdf0 outdated

962@@ -963,6 +963,12 @@ class CWallet final : public WalletStorage, private interfaces::Chain::Notificat
963 
964     std::set<CTxDestination> GetLabelAddresses(const std::string& label) const;
965 
966+    /**
967+     * Mark all outputs in a destination dirty so their cache is
968+     * reset and does not return outdated information.
969+     */
970+    void MarkDestinationsDirty(const std::set<CTxDestination>& destinations) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

kallewoof commented at 1:44 am on January 11, 2020:

The comment should be updated to reflect the fact there are now multiple destinations.

fjahr commented at 12:42 pm on January 13, 2020:

thanks, updated

kallewoof commented at 1:45 am on January 11, 2020: member

Code reviewed, looks good aside from outdated comment.

wallet: Reset reused transactions cache

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.

6fc554f591

fjahr force-pushed on Jan 13, 2020

fjahr commented at 12:43 pm on January 13, 2020: member

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 commented at 10:40 am on January 14, 2020: member

ACK 6fc554f591d8ea1681b8bb25aa12da8d4f023f66.

fanquake requested review from kallewoof on Jan 14, 2020

fanquake requested review from achow101 on Jan 14, 2020

kallewoof commented at 11:27 am on January 14, 2020: member

Code review re-ACK 6fc554f591d8ea1681b8bb25aa12da8d4f023f66

kallewoof approved

achow101 approved

achow101 commented at 4:54 pm on January 14, 2020: member

Re-ACK 6fc554f591d8ea1681b8bb25aa12da8d4f023f66

meshcollider commented at 9:08 am on January 15, 2020: contributor

Code review ACK 6fc554f591d8ea1681b8bb25aa12da8d4f023f66

Thanks!

meshcollider referenced this in commit ac61ec9da6 on Jan 15, 2020

meshcollider merged this on Jan 15, 2020

meshcollider closed this on Jan 15, 2020

sidhujag referenced this in commit a1b399c72d on Jan 15, 2020

fanquake commented at 11:41 am on January 29, 2020: member

@meshcollider does this need backporting to 0.19?

luke-jr referenced this in commit f11872cbf4 on Feb 6, 2020

fanquake commented at 6:12 am on February 6, 2020: member

Being backported in #18083.

laanwj referenced this in commit 4755037d45 on Feb 10, 2020

MarkLTZ referenced this in commit 2e6abb1507 on Mar 13, 2020

MarkLTZ referenced this in commit ece88bae51 on Mar 13, 2020

meshcollider referenced this in commit c189bfd260 on Apr 17, 2020

sidhujag referenced this in commit 155d8bdac1 on Apr 17, 2020

jasonbcox referenced this in commit 31dc3e9d90 on Oct 7, 2020

sidhujag referenced this in commit 6376dfd958 on Nov 10, 2020

Munkybooty referenced this in commit e16b702861 on Dec 9, 2021

DrahtBot locked this on Feb 15, 2022

wallet: Reset reused transactions cache #17843

Conflicts