wallet: Keep track of the wallet's own transaction outputs in memory

achow101 commented at 9:02 pm on March 20, 2023: member

Currently, the wallet is not actually aware about its own transaction outputs. Instead, it will iterate all of the transactions stored in mapWallet, and then all of the outputs of those transactions, in order to figure out what belongs to it for the purposes of coin selection and balance calculation. For balance calculation, there is caching that results in it only iterating all of the transactions, but not all of the outputs. However when the cache is dirty, everything is iterated. This is especially problematic for wallets that have a lot of transactions, or transactions that have a lot of unrelated outputs (as may occur with coinjoins or batched payments).

This PR helps to resolve this issue by making the wallet track all of the outputs that belong to it in a new member m_txos. Note that this includes outputs that may have already been spent. Both balance calculation (GetBalance) and coin selection (AvailableCoins) are updated to iterate m_txos. This is generally faster since it ignores all of the unrelated outputs, and it is not slower as in the worst case of wallets containing only single output transactions, it’s exactly the same number of outputs iterated.

m_txos is memory only, and it is populated during wallet loading. When each transaction is loaded, all of its outputs are checked to see if it is IsMine, and if so, an entry added to m_txos. When new transactions are received, the same procedure is done.

Since imports can change the IsMine status of a transaction (although they can only be “promoted” from watchonly to spendable), all of the import RPCs will be a bit slower as they re-iterate all transactions and all outputs to update m_txos.

Each output in m_txos is stored in a new WalletTXO class. This class contains references to the parent CWalletTx and the CTxOut itself. It also caches the IsMine value of the txout. This should be safe as IsMine should not change unless there are imports. This allows us to have additional performance improvements in places that use these WalletTXOs as they can use the cached IsMine rather than repeatedly calling IsMine which can be expensive.

The existing WalletBalance benchmark demonstrates the performance improvement that this PR makes. The existing WalletAvailableCoins benchmark doesn’t as all of the outputs used in that benchmark belong to the test wallet. I’ve updated that benchmark to have a bunch of unrelated outputs in each transaction so that the difference is demonstrated.

This is part of a larger project to have the wallet actually track and store a set of its UTXOs.

Built on #24914 as it requires loading the txs last in order for m_txos to be built correctly.

Benchmarks:

Master:

ns/op	op/s	err%	ins/op	bra/op	miss%	total	benchmark
92,245,141.50	10.84	0.1%	988,823,975.00	66,803,340.50	0.0%	2.04	`WalletAvailableCoins`
5,709.90	175,134.50	0.5%	80,968.24	25,539.15	0.1%	0.01	`WalletBalanceClean`
139,396.17	7,173.80	0.6%	1,383,390.50	430,276.86	0.0%	0.01	`WalletBalanceDirty`
5,055.80	197,792.47	0.3%	80,968.10	25,539.02	0.1%	0.01	`WalletBalanceMine`
9.79	102,152,396.19	0.1%	161.00	37.00	0.0%	0.01	`WalletBalanceWatch`
1,552,736.00	644.02	1.5%	20,316,315.80	618,545.80	0.6%	0.08	`WalletCreateTxUseOnlyPresetInputs`
114,114,732.00	8.76	0.5%	1,291,047,717.60	320,244,602.00	0.0%	6.30	`WalletCreateTxUsePresetInputsAndCoinSelection`
359,315,754.00	2.78	0.1%	4,339,447,818.00	136,619,757.00	0.7%	1.80	`WalletLoadingDescriptors`
98,230,601.00	10.18	0.1%	537,688,964.00	97,332,266.00	0.3%	0.49	`WalletLoadingLegacy`

PR:

ns/op	op/s	err%	ins/op	bra/op	miss%	total	benchmark
75,319,868.50	13.28	0.2%	863,758,229.00	30,892,593.00	0.2%	1.66	`WalletAvailableCoins`
2,367.62	422,364.95	1.0%	35,785.05	9,893.01	0.2%	0.01	`WalletBalanceClean`
2,685.58	372,359.55	0.2%	36,501.05	10,027.01	0.1%	0.01	`WalletBalanceDirty`
3,462.24	288,830.68	2.7%	35,785.06	9,893.01	0.3%	0.01	`WalletBalanceMine`
11.65	85,838,176.97	0.1%	180.00	42.00	0.0%	0.01	`WalletBalanceWatch`
1,563,092.60	639.76	1.5%	20,426,154.40	649,953.80	0.6%	0.09	`WalletCreateTxUseOnlyPresetInputs`
58,367,804.40	17.13	0.9%	587,164,005.00	107,905,843.80	0.1%	3.21	`WalletCreateTxUsePresetInputsAndCoinSelection`
365,302,636.00	2.74	0.2%	4,349,345,147.00	138,730,668.00	0.8%	1.83	`WalletLoadingDescriptors`
124,995,585.00	8.00	1.2%	801,998,316.00	103,210,721.00	0.3%	0.63	`WalletLoadingLegacy`

DrahtBot commented at 9:02 pm on March 20, 2023: contributor

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

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/27286.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	remyers, jonatack
Stale ACK	ishaanam, murchandamus

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31353 (rpc, cli: add getbalances#total, and use it for -getinfo by jonatack)
#31250 (wallet: Disable creating and loading legacy wallets by achow101)
#30221 (wallet: Ensure best block matches wallet scan state by achow101)
#29062 (Wallet: (Refactor) GetBalance to calculate used balance by BrandonOdiwuor)
#28710 (Remove the legacy wallet and BDB dependency by achow101)
#26732 ([WIP] wallet: tx creation, don’t select outputs from txes that are being replaced by furszy)

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.

DrahtBot added the label Wallet on Mar 20, 2023

DrahtBot added the label Needs rebase on Apr 3, 2023

achow101 force-pushed on Apr 10, 2023

DrahtBot removed the label Needs rebase on Apr 10, 2023

achow101 force-pushed on Apr 10, 2023

DrahtBot added the label Needs rebase on Apr 11, 2023

achow101 force-pushed on Apr 11, 2023

DrahtBot removed the label Needs rebase on Apr 11, 2023

DrahtBot added the label Needs rebase on Apr 12, 2023

achow101 force-pushed on Apr 12, 2023

DrahtBot removed the label Needs rebase on Apr 12, 2023

DrahtBot added the label Needs rebase on May 1, 2023

achow101 force-pushed on May 1, 2023

DrahtBot removed the label Needs rebase on May 1, 2023

DrahtBot added the label CI failed on May 9, 2023

DrahtBot added the label Needs rebase on May 15, 2023

achow101 force-pushed on May 15, 2023

DrahtBot removed the label Needs rebase on May 15, 2023

DrahtBot removed the label CI failed on May 16, 2023

DrahtBot added the label Needs rebase on May 16, 2023

achow101 force-pushed on May 16, 2023

DrahtBot removed the label Needs rebase on May 16, 2023

DrahtBot added the label Needs rebase on May 18, 2023

achow101 force-pushed on May 19, 2023

DrahtBot removed the label Needs rebase on May 19, 2023

achow101 force-pushed on May 19, 2023

achow101 force-pushed on May 27, 2023

DrahtBot added the label Needs rebase on Jun 2, 2023

achow101 force-pushed on Jun 2, 2023

DrahtBot removed the label Needs rebase on Jun 2, 2023

DrahtBot added the label Needs rebase on Jun 12, 2023

achow101 force-pushed on Jun 12, 2023

DrahtBot removed the label Needs rebase on Jun 12, 2023

DrahtBot added the label Needs rebase on Jun 28, 2023

achow101 force-pushed on Jun 28, 2023

DrahtBot removed the label Needs rebase on Jun 28, 2023

murchandamus commented at 8:13 pm on July 6, 2023: contributor

Concept ACK

achow101 marked this as ready for review on Jul 10, 2023

in src/wallet/receive.cpp:262 in 68bb1463dc outdated

318-                ret.m_mine_untrusted_pending += tx_credit_mine;
319-                ret.m_watchonly_untrusted_pending += tx_credit_watchonly;
320+        for (const auto& [outpoint, txo] : wallet.GetTXOs()) {
321+            Assert(MoneyRange(txo.GetTxOut().nValue));
322+
323+            const bool is_trusted{CachedTxIsTrusted(wallet, txo.GetWalletTx(), trusted_parents)};

ishaanam commented at 6:51 pm on July 12, 2023:

In 68bb1463dc1f995fbfdb75d3acef625bde104275 “wallet: Change balance calculation to use m_txos "

nit:

0            const bool is_trusted{CachedTxIsTrusted(wallet, txo.GetWalletTx())};

& also remove the unused trusted_parents from above. (for GetAddressBalances as well)

achow101 commented at 6:35 pm on September 15, 2023:

Done

in src/wallet/receive.cpp:285 in 68bb1463dc outdated

341+                    ret.m_mine_immature += credit_mine;
342+                    ret.m_watchonly_immature += credit_watchonly;
343+                } else if (is_trusted && tx_depth >= min_depth) {
344+                    ret.m_mine_trusted += credit_mine;
345+                    ret.m_watchonly_trusted += credit_watchonly;
346+                } if (!is_trusted && tx_depth == 0 && txo.GetWalletTx().InMempool()) {

ishaanam commented at 5:10 pm on July 13, 2023:

In 68bb1463dc1f995fbfdb75d3acef625bde104275 " wallet: Change balance calculation to use m_txos "

nit: checking the tx depth is redundant here because if the transaction is TxStateMempool then GetTxDepthInMainChain will always return 0.

0                } if (!is_trusted && txo.GetWalletTx().InMempool()) {

achow101 commented at 6:35 pm on September 15, 2023:

Done

in src/wallet/wallet.h:508 in 3f3246efe2 outdated

479@@ -480,6 +480,7 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
480     const std::unordered_map<COutPoint, WalletTXO, SaltedOutpointHasher>& GetTXOs() const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet) { AssertLockHeld(cs_wallet); return m_txos; };
481 
482     void RefreshWalletTxTXOs(const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
483+    void RefreshWalletTXOs() EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

ishaanam commented at 5:27 pm on July 13, 2023:

In 3f3246efe299552e450362a03c61c602a168f7de “wallet: Recalculate the wallet’s txos after any imports "

Does this also need to be called during sethdseed and keypoolrefill.

achow101 commented at 6:38 pm on September 15, 2023:

Hmm, good point. The expected usage of these is that only new keys will be generated/added, so it shouldn’t have any effect on the existing transactions in the wallet. However, I suppose they could be used in a way that does result in existing txs having their IsMine changed. I’ve also added this to addmultisigaddress and newkeypool since they could be used in the same way.

in src/wallet/rpc/backup.cpp:634 in 3f3246efe2 outdated

630@@ -627,6 +631,7 @@ RPCHelpMan importwallet()
631 
632             progress++;
633         }
634+        pwallet->RefreshWalletTXOs();

ishaanam commented at 5:32 pm on July 13, 2023:

In https://github.com/bitcoin/bitcoin/commit/3f3246efe299552e450362a03c61c602a168f7de “wallet: Recalculate the wallet’s txos after any imports "

Is this needed if the wallet will rescan anyways?

achow101 commented at 6:38 pm on September 15, 2023:

The wallet may not rescan every transaction in the wallet since it does look at the given key birthdays.

in src/wallet/spend.cpp:352 in 881650ed31 outdated

297-        for (unsigned int i = 0; i < wtx.tx->vout.size(); i++) {
298-            const CTxOut& output = wtx.tx->vout[i];
299-            const COutPoint outpoint(wtxid, i);
300+        if (mine == ISMINE_NO) {
301+            continue;
302+        }

ishaanam commented at 5:47 pm on July 13, 2023:

In 881650ed319c6ed74e66ae56c34cdee93125231b " wallet: Use wallet’s TXO set in AvailableCoins "

Shouldn’t txos in m_txos never be ISMINE_NO?

0        assert(mine != ISMINE_NO);

achow101 commented at 6:39 pm on September 15, 2023:

Done

in src/wallet/spend.cpp:410 in 881650ed31 outdated

390-                is_from_p2sh = true;
391-            }
392+            tx_safe_cache[outpoint.hash] = {true, safeTx};
393+        }
394+        const auto& [tx_ok, tx_safe] = tx_safe_cache.at(outpoint.hash);
395+        Assert(tx_ok);

ishaanam commented at 7:09 pm on July 13, 2023:

In https://github.com/bitcoin/bitcoin/commit/881650ed319c6ed74e66ae56c34cdee93125231b " wallet: Use wallet’s TXO set in AvailableCoins "

Can’t tx_ok still be false at this point if a transaction that has a depth of 0 and is not in the mempool has two txos that belong to the wallet? Since then when the first txo is evaluated, a {false, false} entry will be created for that transaction hash, and then when the second txo is evaluated, that entry will be used because the mempool check will be skipped?

achow101 commented at 6:39 pm on September 15, 2023:

Good point, changed to an if.

ishaanam commented at 1:38 am on October 16, 2023:

Looking at this again, I think I mislead you here. In the scenario I described above, tx_ok won’t be false at this point, because if a {false, false} entry has already been created for a txid, then it would not reach this point because it would already get removed here (https://github.com/bitcoin/bitcoin/pull/27286/commits/9315bb7872210dc767dfd7ea01febb13fca5525b#diff-6e06b309cd494ef5da4e78aa0929a980767edd12342137f268b9219167064d13R328-R329)

achow101 commented at 10:15 pm on October 16, 2023:

Indeed. I’ve left the if there anyways as a belt-and-suspenders, and changed it to also Assume.

ishaanam commented at 7:54 pm on July 13, 2023: contributor

Concept ACK

Still working on reviewing this, but here are some initial things. Thanks for breaking it up into twelve commits, it makes it easy to review.

ishaanam commented at 10:57 pm on July 20, 2023: contributor

The commit message for 68bb1463dc1f995fbfdb75d3acef625bde104275 should be updated because now that #27145 has gotten merged, the described issue has already been fixed.

DrahtBot added the label Needs rebase on Sep 6, 2023

achow101 force-pushed on Sep 7, 2023

DrahtBot removed the label Needs rebase on Sep 7, 2023

DrahtBot added the label Needs rebase on Sep 14, 2023

achow101 force-pushed on Sep 14, 2023

DrahtBot removed the label Needs rebase on Sep 14, 2023

DrahtBot added the label CI failed on Sep 15, 2023

remyers commented at 10:01 am on September 15, 2023: contributor

Concept ACK

My preliminary testing confirmed that this PR will significantly speed up common operations like fundrawtransaction on wallets with many years of transaction history. A single fundrawtransaction RPC call that took 5 sec on a simulated large wallet now takes 50ms. Services providers with large wallets that need to make many RPC calls per minute will benefit from reduced lock contention on cs_wallet; for example, LSPs using bitcoin core wallets like Eclair.

Caching the wallet’s tx outputs in memory seems like a straight forward solution as long as the cache of tx outs in m_txos are always updated (or regenerated) if the underlying set of wallet txs in mapWallet or the m_spk_managers change.

remyers commented at 10:50 am on September 15, 2023: contributor

Exposing RefreshWalletTXOs() as a public method puts the responsibility of knowing when it should be called outside of the CWallet scope. What do you think about making it private and clearing m_txos (or adding a new flag) to trigger RefreshWalletTXOs() at query time?

This alternate approach would require GetTXO(const COutPoint& outpoint) and GetTXOs() to first call RefreshWalletTXOs() if m_txos is empty. There are only a few methods that change m_spk_managers that would need to clear m_txos to trigger a one time RefreshWalletTXOs():

ImportPrivKeys
ImportPublicKeys
ImportScriptPubKeys
AddScriptPubKeyMan

It’s also only a small set of places where keys are imported in backup.cpp, so the question of leaving RefreshWalletTXOs() public might just be a matter of which approach would be less foot-gunny in the future and if there are disadvantages to delaying the regeneration of txos.

I think you can safely make RefreshWalletTxTXOs(const CWalletTx& wtx) a private method now though because it is only called by wallet methods that add a wtx to mapWallet like LoadToWallet and AddToWallet.

achow101 commented at 4:40 pm on September 15, 2023: member

Exposing RefreshWalletTXOs() as a public method puts the responsibility of knowing when it should be called outside of the CWallet scope. What do you think about making it private and clearing m_txos (or adding a new flag) to trigger RefreshWalletTXOs() at query time?

I’m not sure that’s meaningfully different. The caller still needs to know when to clear m_txos in order to trigger a future RefreshWalletTXOs(). The way it is now also provides a better UX as the slow part of refreshing the TXOs occurs during slow import operations rather than the first time those TXOs are needed after the import.

achow101 force-pushed on Sep 15, 2023

DrahtBot removed the label CI failed on Sep 15, 2023

remyers commented at 8:38 am on September 16, 2023: contributor

I’m not sure that’s meaningfully different. The caller still needs to know when to clear m_txos in order to trigger a future RefreshWalletTXOs(). The way it is now also provides a better UX as the slow part of refreshing the TXOs occurs during slow import operations rather than the first time those TXOs are needed after the import.

Just to clarify, I mean that a reviewer, but not method caller, would need to make sure every method in CWallet that invalidates m_txos also clears it. I agree with your point though that forcing the refresh at import time makes sense. I also notice that there are a number of places where a ScriptPubKeyMan gets added or updated outside of CWallet, so I understand now why it’s not really possible to make RefreshWalletTXOs() something internal to CWallet.

in test/functional/wallet_abandonconflict.py:235 in fdf3ab0579 outdated

230@@ -231,7 +231,8 @@ def run_test(self):
231         assert_equal(newbalance, balance + Decimal("20"))
232         balance = newbalance
233 
234-        # Invalidate the block with the double spend. B & C's 10 BTC outputs should no longer be available
235+        # Invalidate the block with the double spend and both B and C's 10 BTC output should no longer be available
236+        # AB1 and ABC2's outputs are also not available since neither of those txs are in the mempool

ishaanam commented at 0:44 am on October 16, 2023:

In fdf3ab0579be6d6f2be31907e3451a830e25291e “wallet: Change balance calculation to use m_txos “:

nit: This no longer needs to be changed in this commit.

achow101 commented at 10:14 pm on October 16, 2023:

Done

in src/wallet/wallet.h:508 in d7b3603822 outdated

503@@ -504,6 +504,7 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
504     const std::unordered_map<COutPoint, WalletTXO, SaltedOutpointHasher>& GetTXOs() const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet) { AssertLockHeld(cs_wallet); return m_txos; };
505 
506     void RefreshWalletTxTXOs(const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
507+    void RefreshWalletTXOs() EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

ishaanam commented at 0:54 am on October 16, 2023:

In d7b3603822663fbc713970bf37dc010904aaa583 “wallet: Recalculate the wallet’s txos after any imports “:

RefreshWalletTXOs looks similar to RefreshWalletTxTXOs and it is not immediately clear what the distinction is without actually reading the functions. I would suggest s/RefreshWalletTXOs/RefreshAllTXOs (putting “Wallet” seems redundant here because the method belongs to wallet anyways, and GetTXOs doesn’t mention “Wallet” in the function name).

achow101 commented at 10:14 pm on October 16, 2023:

Renamed as suggested.

ishaanam commented at 12:06 pm on October 16, 2023: contributor

ACK 9199832d4440a875a150aa3ba3bc1bc201d3fd72

I’ve reviewed everything but the tests and benchmarks.

DrahtBot requested review from murchandamus on Oct 16, 2023

DrahtBot added the label Needs rebase on Oct 16, 2023

achow101 force-pushed on Oct 16, 2023

DrahtBot added the label CI failed on Oct 16, 2023

DrahtBot removed the label Needs rebase on Oct 16, 2023

achow101 force-pushed on Oct 23, 2023

in src/bench/wallet_create_tx.cpp:58 in 9292951f0c outdated

54     coinbase_tx.vout[1].nValue = 1 * COIN;
55+
56+    // Fill the coinbase with outputs that don't belong to the wallet in order to benchmark
57+    // AvailableCoins' behavior with unnecessary TXOs
58+    for (int i = 0; i < 50; ++i) {
59+        coinbase_tx.vout.push_back(CTxOut(1 * COIN / 50, CScript(OP_TRUE)));

maflcko commented at 7:51 am on October 24, 2023:

0bench/wallet_create_tx.cpp:58:26: error: use emplace_back instead of push_back [modernize-use-emplace,-warnings-as-errors]
1   58 |         coinbase_tx.vout.push_back(CTxOut(1 * COIN / 50, CScript(OP_TRUE)));
2      |                          ^~~~~~~~~~~~~~~~~                               ~
3      |                          emplace_back(

achow101 commented at 3:41 pm on October 24, 2023:

Done

achow101 force-pushed on Oct 24, 2023

DrahtBot removed the label CI failed on Oct 25, 2023

DrahtBot added the label Needs rebase on Oct 29, 2023

in src/wallet/receive.cpp:216 in b2790645e9 outdated

255@@ -256,6 +256,10 @@ bool CachedTxIsFromMe(const CWallet& wallet, const CWalletTx& wtx, const isminef
256 bool CachedTxIsTrusted(const CWallet& wallet, const CWalletTx& wtx, std::set<uint256>& trusted_parents)
257 {
258     AssertLockHeld(wallet.cs_wallet);
259+
260+    // This wtx is already trusted
261+    if (trusted_parents.count(wtx.GetHash()) > 0) return true;

murchandamus commented at 8:39 pm on October 30, 2023:

How would that ever happen? Wouldn’t we only have seen a trusted_parent before if we received two outputs from the same transaction?

achow101 commented at 11:21 pm on October 30, 2023:

Yes, and that does happen, e.g. send to self transactions. The tests also do this a lot.

murchandamus commented at 7:09 pm on March 11, 2024:

In 0283525d64a28c79f4588ef0a71bd280b2fc7768 (wallet: Exit IsTrustedTx early if wtx is already in trusted_parents):

0    if (trusted_parents.contains(wtx.GetHash())) return true;

achow101 commented at 2:53 pm on March 12, 2024:

Done

in src/wallet/receive.cpp:309 in 73bff03d1f outdated

358 
359-            if (wallet.IsTxImmatureCoinBase(wtx))
360-                continue;
361+            CTxDestination addr;
362+            Assume(wallet.IsMine(txo.GetTxOut()));
363+            if(!ExtractDestination(txo.GetTxOut().scriptPubKey, addr)) continue;

murchandamus commented at 8:49 pm on October 30, 2023:

Wouldn’t this mean that we don’t count P2PK outputs to our balance in combination with the changes to “Destinations” for Silent Payments?

achow101 commented at 9:33 pm on October 30, 2023:

Yes, P2PK is not an address type.

in src/wallet/wallet.cpp:1594 in c91b1de218 outdated

1554@@ -1555,16 +1555,10 @@ void CWallet::BlockUntilSyncedToCurrentChain() const {
1555 // and a not-"is mine" (according to the filter) input.
1556 CAmount CWallet::GetDebit(const CTxIn &txin, const isminefilter& filter) const

murchandamus commented at 8:58 pm on October 30, 2023:

What does GetDebit do? The explanation in wallet.h is also self-referential:

0 769     /**
1 770      * Returns amount of debit if the input matches the
2 771      * filter, otherwise returns 0
3 772      */

Does this just get the amount for an input that matches the filter criteria?

achow101 commented at 9:36 pm on October 30, 2023:

“Debit” refers to the amount leaving the wallet, assuming the UTXO spent by the input matches the filter. “Debit” operates on a transaction’s inputs, while “credit” operates on the outputs.

achow101 force-pushed on Nov 13, 2023

DrahtBot removed the label Needs rebase on Nov 13, 2023

DrahtBot added the label Needs rebase on Nov 24, 2023

achow101 force-pushed on Nov 28, 2023

DrahtBot removed the label Needs rebase on Nov 28, 2023

DrahtBot added the label Needs rebase on Dec 8, 2023

achow101 force-pushed on Dec 8, 2023

DrahtBot removed the label Needs rebase on Dec 8, 2023

DrahtBot added the label Needs rebase on Dec 11, 2023

achow101 force-pushed on Dec 11, 2023

DrahtBot removed the label Needs rebase on Dec 11, 2023

DrahtBot added the label Needs rebase on Dec 12, 2023

achow101 force-pushed on Dec 19, 2023

DrahtBot removed the label Needs rebase on Dec 19, 2023

in src/wallet/spend.cpp:341 in 91e4f19f66 outdated

366-        // accepted.
367-        if (nDepth == 0 && wtx.mapValue.count("replaces_txid")) {
368-            safeTx = false;
369-        }
370+        if (wallet.IsSpent(outpoint))
371+            continue;

murchandamus commented at 7:32 pm on December 28, 2023:

I have the impression that m_txos is also used to look up information on old transactions and we therefore want to keep all transaction outputs the wallet ever had.

Would it perhaps make sense to also have a reduced set that only keeps the potentially unspent TXOs? I could see a wallet that participates in a few dozen transactions every day have magnitudes more TXOs than UTXOs. So perhaps the work the wallet has to perform every time it builds a transaction could be shortcut by storing e.g. m_is_mature_spent on WalletTXO which could be set to true when the transaction spending an output has 100 confirmations, and then either separately keeping a list of all TXOs that are not m_is_mature_spent or at least iterate over them more quickly directly on the basis of that member, without needing to have complex reorg handling to keep this collection up to date.

murchandamus commented at 7:39 pm on December 28, 2023:

Ah, nevermind, I just saw https://github.com/bitcoin/bitcoin/pull/27865

murchandamus commented at 7:38 pm on December 28, 2023: contributor

ACK 0c0022311a0cffc4c03b3763c9b60f93ede13687

While I am pretty sure that the reorg logic should handle any transactions getting added or removed from the wallet, it might be useful to add a test that the m_txos set would be correct after a reorg, if that’s not obvious.

DrahtBot requested review from ishaanam on Dec 28, 2023

in src/wallet/receive.cpp:284 in 0c0022311a outdated

291+                    ret.m_mine_immature += credit_mine;
292+                    ret.m_watchonly_immature += credit_watchonly;
293+                } else if (is_trusted && tx_depth >= min_depth) {
294+                    ret.m_mine_trusted += credit_mine;
295+                    ret.m_watchonly_trusted += credit_watchonly;
296+                } if (!is_trusted && txo.GetWalletTx().InMempool()) {

aureleoules commented at 5:02 am on January 3, 2024:

Seems like a hazard

0                } else if (!is_trusted && txo.GetWalletTx().InMempool()) {

achow101 commented at 9:05 pm on January 4, 2024:

Good catch, fixed.

in src/wallet/spend.cpp:357 in 0c0022311a outdated

405+            continue;
406 
407-            // Skip manually selected coins (the caller can fetch them directly)
408-            if (coinControl && coinControl->HasSelected() && coinControl->IsSelected(outpoint))
409-                continue;
410+        if (tx_safe_cache.count(outpoint.hash) == 0 ) {

aureleoules commented at 5:25 am on January 3, 2024:

nit: Could use contains (and other places too)

0        if (!tx_safe_cache.contains(outpoint.hash)) {

achow101 commented at 9:05 pm on January 4, 2024:

Done

achow101 force-pushed on Jan 4, 2024

DrahtBot added the label CI failed on Jan 13, 2024

murchandamus commented at 3:26 pm on January 24, 2024: contributor

ReACK https://github.com/bitcoin/bitcoin/commit/39f0ab3e126704b30f7ed2b86690f60b631d2ec4 compared to my prior review, there are only the changes mentioned in response to @aureleoules.

DrahtBot added the label Needs rebase on Feb 3, 2024

achow101 force-pushed on Feb 8, 2024

DrahtBot removed the label Needs rebase on Feb 8, 2024

DrahtBot removed the label CI failed on Feb 9, 2024

DrahtBot added the label Needs rebase on Feb 20, 2024

achow101 force-pushed on Feb 20, 2024

DrahtBot removed the label Needs rebase on Feb 20, 2024

in src/wallet/wallet.cpp:1146 in 20cec0c84b outdated

1142@@ -1143,6 +1143,9 @@ CWalletTx* CWallet::AddToWallet(CTransactionRef tx, const TxState& state, const
1143     // Break debit/credit balance caches:
1144     wtx.MarkDirty();
1145 
1146+    // Get the outputs that belong to the wallet

murchandamus commented at 7:00 pm on March 11, 2024:

In 20cec0c84bbe783ddfc0c9b6c3ce1cb45f93385e (wallet: Keep track of transaction outputs owned by the wallet):

0    // Cache the outputs that belong to the wallet on the wallet’s transactions

achow101 commented at 2:52 pm on March 12, 2024:

Changed to “cache”.

“on the wallet’s transactions” does not make the comment a valid English sentence, so I’m not sure what meaning you were trying to get across.

murchandamus commented at 5:33 pm on March 20, 2024:

I think I wanted to express that this function operates only on the transactions that the wallet tracks already.

in src/wallet/wallet.cpp:4489 in 20cec0c84b outdated

4484+        isminetype ismine = IsMine(txout);
4485+        if (ismine == ISMINE_NO) {
4486+            continue;
4487+        }
4488+        COutPoint outpoint(wtx.GetHash(), i);
4489+        if (m_txos.count(outpoint) > 0) {

murchandamus commented at 7:03 pm on March 11, 2024:

In 20cec0c84bbe783ddfc0c9b6c3ce1cb45f93385e (wallet: Keep track of transaction outputs owned by the wallet):

0        if (m_txos.contains(outpoint)) {

achow101 commented at 2:52 pm on March 12, 2024:

Done

in src/wallet/wallet.h:428 in 20cec0c84b outdated

424@@ -425,6 +425,9 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
425     //! Cache of descriptor ScriptPubKeys used for IsMine. Maps ScriptPubKey to set of spkms
426     std::unordered_map<CScript, std::vector<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks;
427 
428+    //! Set of transaction outputs owned by this wallet

murchandamus commented at 7:05 pm on March 11, 2024:

In 20cec0c84bbe783ddfc0c9b6c3ce1cb45f93385e (wallet: Keep track of transaction outputs owned by the wallet):

0    //! Set of spent and unspent transaction outputs owned by this wallet

achow101 commented at 2:53 pm on March 12, 2024:

Done

in src/wallet/receive.cpp:255 in b217f576a5 outdated

297@@ -297,27 +298,40 @@ bool CachedTxIsTrusted(const CWallet& wallet, const CWalletTx& wtx)
298 Balance GetBalance(const CWallet& wallet, const int min_depth, bool avoid_reuse)
299 {
300     Balance ret;
301-    isminefilter reuse_filter = avoid_reuse ? ISMINE_NO : ISMINE_USED;
302+    bool allow_used_addresses = !avoid_reuse || !wallet.IsWalletFlagSet(WALLET_FLAG_AVOID_REUSE);

murchandamus commented at 7:37 pm on March 11, 2024:

In b217f576a5f284ac7261986ee6ec9334bbbdbbc6 (wallet: Change balance calculation to use m_txos):

I dug into this line, because I was wondering whether this line changed the behavior, but found that in src/wallet/receive.cpp in CachedTxGetAvailableCredit(…) the reuse_filter was used to derive the same resulting allow_used_addresses on basis of the filter and WALLET_FLAG_AVOID_REUSE. So, I’m thinking now that this change is not a change in behavior. It would perhaps help future reviewers if the commit message mentioned why this change is valid and doesn’t change the behavior.

achow101 commented at 2:53 pm on March 12, 2024:

Mentioned in the commit message.

in src/wallet/wallet.cpp:4645 in 20cec0c84b outdated

4488+        COutPoint outpoint(wtx.GetHash(), i);
4489+        if (m_txos.count(outpoint) > 0) {
4490+            m_txos.at(outpoint).SetIsMine(ismine);
4491+        } else {
4492+            m_txos.emplace(outpoint, WalletTXO{wtx, txout, ismine});
4493+        }

murchandamus commented at 7:47 pm on March 11, 2024:

In 20cec0c84bbe783ddfc0c9b6c3ce1cb45f93385e (wallet: Keep track of transaction outputs owned by the wallet):

A few commits later, you use wallet.IsSpent(outpoint) to check whether a TXO is still available for spending. Why can’t we just do store the outcome of wallet.IsSpent(outpoint) here as well?

achow101 commented at 2:27 pm on March 12, 2024:

Outputs don’t always stay spent. Replacements, reorgs, and eviction could all make a transaction no longer be “IsSpent”, so checking that here would require a lot of other structural changes to ensure that it is correct.

Storing the value of IsSpent could be an alternative to #27865, however I would still leave that for a followup. Any change that tries to actually have a proper UTXO set for the wallet can have unexpected side effects and/or things we didn’t notice so I want to keep that separate for now. This PR is to setup for that by making the wallet operate on a TXO set.

in src/wallet/receive.cpp:264 in b217f576a5 outdated

321+            Assert(MoneyRange(txo.GetTxOut().nValue));
322+
323+            const bool is_trusted{CachedTxIsTrusted(wallet, txo.GetWalletTx())};
324+            const int tx_depth{wallet.GetTxDepthInMainChain(txo.GetWalletTx())};
325+
326+            if (!wallet.IsSpent(outpoint) && (allow_used_addresses || !wallet.IsSpentKey(txo.GetTxOut().scriptPubKey))) {

murchandamus commented at 7:51 pm on March 11, 2024:

In b217f576a5f284ac7261986ee6ec9334bbbdbbc6 (wallet: Change balance calculation to use m_txos):

Instead of wallet.IsSpentKey(…) couldn’t you just check here if txo.GetIsMine() has the ISMINE_USED bit set?

achow101 commented at 2:37 pm on March 12, 2024:

ISMINE_USED is not actually an isminetype that is returned by IsMine, so it will not be set in the txo.GetIsMine()’s result. It’s really just a hack for it to be an isminetype so it can be passed as part of various ismine filters, but these always check that separately from the actual IsMine result.

in src/wallet/receive.cpp:274 in b217f576a5 outdated

331+                    credit_mine = txo.GetTxOut().nValue;
332+                } else if (txo.GetIsMine() == ISMINE_WATCH_ONLY) {
333+                    credit_watchonly = txo.GetTxOut().nValue;
334+                } else {
335+                    // We shouldn't see any other isminetypes
336+                    Assume(false);

murchandamus commented at 7:54 pm on March 11, 2024:

In b217f576a5f284ac7261986ee6ec9334bbbdbbc6 (wallet: Change balance calculation to use m_txos):

I was wondering if we could see ISMINE_SPENDABLE | ISMINE_USED or ISMINE_WATCH_ONLY | ISMINE_USED here.

achow101 commented at 2:37 pm on March 12, 2024:

No. ISMINE_USED is never actually returned from IsMine.

in src/wallet/receive.cpp:277 in b217f576a5 outdated

334+                } else {
335+                    // We shouldn't see any other isminetypes
336+                    Assume(false);
337+                }
338+
339+                // Set the amounts in the return object

murchandamus commented at 8:13 pm on March 11, 2024:

In b217f576a5f284ac7261986ee6ec9334bbbdbbc6 (wallet: Change balance calculation to use m_txos):

It seems to me that the below should be matching replacements here, but previously every TXO in this loop got added to …_untrusted_pending, and now only TXOs of unconfirmed untrusted transactions, and immature coinbase transactions get added to …_untrusted_pending. Doesn’t this commit change the balances we would be returning?

 0- if (is_trusted && tx_depth >= min_depth) {
 1-     ret.m_mine_trusted += tx_credit_mine;
 2-     ret.m_watchonly_trusted += tx_credit_watchonly;
 3- if (!is_trusted && tx_depth == 0 && wtx.InMempool()) {
 4-     ret.m_mine_untrusted_pending += tx_credit_mine;
 5-     ret.m_watchonly_untrusted_pending += tx_credit_watchonly;
 6- }
 7- ret.m_mine_immature += CachedTxGetImmatureCredit(wallet, wtx, ISMINE_SPENDABLE);
 8- ret.m_watchonly_immature += CachedTxGetImmatureCredit(wallet, wtx, ISMINE_WATCH_ONLY);
 9+ // Set the amounts in the return object
10+ if (wallet.IsTxImmatureCoinBase(txo.GetWalletTx()) && wallet.IsTxInMainChain(txo.GetWalletTx())) {
11+     ret.m_mine_immature += credit_mine;
12+     ret.m_watchonly_immature += credit_watchonly;
13+ } else if (is_trusted && tx_depth >= min_depth) {
14+     ret.m_mine_trusted += credit_mine;
15+     ret.m_watchonly_trusted += credit_watchonly;
16+ } else if (!is_trusted && txo.GetWalletTx().InMempool()) {
17+     ret.m_mine_untrusted_pending += credit_mine;
18+     ret.m_watchonly_untrusted_pending += credit_watchonly;
19+ }

achow101 commented at 2:44 pm on March 12, 2024:

Can you be more specific as to what kind of transaction you think would result in a different balance? Nothing in this PR should change behavior.

in test/functional/wallet_balance.py:399 in 900f95cd56 outdated

396+        assert_equal(balances["mine"]["trusted"], amount)
397+
398+        # Don't rescan to make sure that the import updates the wallet txos
399+        wallet.importprivkey(privkey=import_key2.privkey, rescan=False)
400+        balances = wallet.getbalances()
401+        assert_equal(balances["mine"]["trusted"], amount * 2)

murchandamus commented at 8:20 pm on March 11, 2024:

In 900f95cd56951f5e0f0d0f3a93c09d1fb0bc5787 (test: Test for balance update due to watchonly becoming spendable):

Do I understand right that discovering this TXO without a rescan only works because the transaction was already in our mapWallet?

achow101 commented at 2:45 pm on March 12, 2024:

That is correct.

in src/wallet/spend.cpp:323 in c88832eca5 outdated

319@@ -320,137 +320,145 @@ CoinsResult AvailableCoins(const CWallet& wallet,
320     std::vector<COutPoint> outpoints;
321 
322     std::set<uint256> trusted_parents;
323-    for (const auto& entry : wallet.mapWallet)
324-    {
325-        const uint256& txid = entry.first;
326-        const CWalletTx& wtx = entry.second;
327+    // Cache for whether each tx passes the tx checks (first bool), and whether the transaction is "safe" (second bool)

murchandamus commented at 8:29 pm on March 11, 2024:

In c88832eca5df0a391a4a68c73b6fc123f9af2f4b (wallet: Use wallet’s TXO set in AvailableCoins):

What are the “tx checks” that are being passed? It seems to me me that it refers to TXs either having been sent by ourselves that are not involved in an RBF process or TXs with sufficient confirmations that we rely on them. Either way, it would be nice if this comment were a bit more elaborate than just mentioning “tx checks”. Also, the relationship to safe_tx could be made a bit clearer in this code block.

Perhaps something along the lines of:

0    // Cache for each transaction whether we consider its outputs acceptable for spending (first bool), and whether the transaction is considered "safe" (second bool).
1    // A transaction’s outputs are considered acceptable for spending when <elaborate>
2    // A transaction is considered safe when <elaborate>

Alternatively or additionally if the CachedTxIsTrusted(…) functions had a bit more documentation in either src/wallet/receive.h or src/wallet/receive.cpp.

achow101 commented at 2:51 pm on March 12, 2024:

The checks are already explained in detail below where they are actually checked. “tx checks” just refers to the checks that occur per tx rather than per output. I don’t think it is useful to duplicate the explanations here as well.

I’ve added a comment that should make it easier to find where the tx checks are performed so you can read the comments that already exist.

achow101 force-pushed on Mar 12, 2024

DrahtBot added the label CI failed on Mar 14, 2024

DrahtBot removed the label CI failed on Mar 19, 2024

DrahtBot added the label Needs rebase on Mar 27, 2024

achow101 force-pushed on Mar 29, 2024

DrahtBot removed the label Needs rebase on Mar 29, 2024

achow101 force-pushed on Jun 6, 2024

DrahtBot added the label CI failed on Jul 5, 2024

achow101 force-pushed on Jul 9, 2024

achow101 commented at 11:37 pm on July 9, 2024: member

Rebased for silent merge conflict.

DrahtBot removed the label CI failed on Jul 10, 2024

DrahtBot added the label Needs rebase on Jul 11, 2024

achow101 force-pushed on Jul 22, 2024

DrahtBot removed the label Needs rebase on Jul 22, 2024

in src/wallet/wallet.h:513 in d6f67e97b7 outdated

509@@ -507,6 +510,8 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
510 
511     std::set<uint256> GetTxConflicts(const CWalletTx& wtx) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
512 
513+    void RefreshWalletTxTXOs(const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

murchandamus commented at 2:16 pm on August 7, 2024:

In d6f67e97b7ec0b5fdc39e5ad52e0c03dd0e03fd1 wallet: Keep track of transaction outputs owned by the wallet:

It would have helped me if this function had some documentation. Also, “Wallet transaction transaction outputs” feels a bit redundant, and the name RefreshWalletTxTXOs(…) is extremely similar to RefreshAllTXOs() that gets introduced in the later commit “wallet: Recalculate the wallet’s txos after any imports”. If you have to touch this again, perhaps consider calling this function CacheWalletTXOs?

0    /** Processes one wallet transaction and caches outputs that belong to our wallet. */
1    void RefreshWalletTxTXOs(const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

achow101 commented at 12:14 pm on October 16, 2024:

Done

in src/wallet/wallet.h:519 in 9d3762913b outdated

512@@ -513,6 +513,7 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
513     const std::unordered_map<COutPoint, WalletTXO, SaltedOutpointHasher>& GetTXOs() const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet) { AssertLockHeld(cs_wallet); return m_txos; };
514 
515     void RefreshWalletTxTXOs(const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
516+    void RefreshAllTXOs() EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

murchandamus commented at 5:30 pm on August 7, 2024:

In 9d3762913ba02d1f6cd3b42889c2c3b31f03e90c “wallet: Recalculate the wallet’s txos after any imports”:

Perhaps add a documentation comment here along the lines of:

0    /** Inspects every wallet transaction and caches all outputs that belong to our wallet. */
1    void RefreshAllTXOs() EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

achow101 commented at 12:14 pm on October 16, 2024:

Done

murchandamus commented at 6:06 pm on August 8, 2024: contributor

ReACK 3b6ac646ffea930ae7d8c5d93acaba3587cc9dcd

DrahtBot added the label Needs rebase on Aug 27, 2024

achow101 force-pushed on Aug 29, 2024

DrahtBot removed the label Needs rebase on Aug 29, 2024

achow101 requested review from murchandamus on Oct 15, 2024

achow101 force-pushed on Oct 16, 2024

DrahtBot added the label Needs rebase on Oct 24, 2024

walletdb: Load Txs last

Need to load txs last so that IsMine works.

9848611d10

wallet: Keep track of transaction outputs owned by the wallet

When loading transactions to the wallet, check the outputs, and keep
track of the ones that are IsMine.

af8e6221c6

wallet: Exit IsTrustedTx early if wtx is already in trusted_parents 326b7c59e7

wallet: Change balance calculation to use m_txos

Since we track the outputs owned by the wallet with m_txos, we can now
calculate the balance of the wallet by iterating m_txos and summing up
the amounts of the unspent txos.

As ISMINE_USED is not an actual isminetype that we attach to outputs and
was just passed into `CachedTxGetAvailableCredit` for convenience, we
pull the same determining logic from that function into `GetBalances` in
order to preserve existing behavior.

c088e9b699

wallet: Recalculate the wallet's txos after any imports 1b2dc9cec2

test: Test for balance update due to watchonly becoming spendable 016f08cf67

wallet: Use wallet's TXO set in AvailableCoins

Instead of iterating every transaction and every output stored in wallet
when trying to figure out what outputs can be spent, iterate the TXO set
which should be a lot smaller.

e2e0fcd5db

wallet: Retrieve TXO directly in FetchSelectedInputs

Instead of searching mapWallet for the preselected inputs, search
m_txos.

wallet_fundrawtransaction.py spends external inputs and needs the change
output to also belong to the test wallet for the oversized tx test.

961d0f4845

wallet: Recompute wallet TXOs after descriptor migration

When a legacy wallet has been migrated to contain descriptors, but
before the transactions have been updated to match, we need to recompute
the wallet TXOs so that the transaction update will work correctly.

79a35663f0

wallet: Have GetDebit use the wallet's TXO set

Instead of looking up the previous tx in mapWallet, and then calling
IsMine on the specified output, use the TXO set and its cached IsMine
value.

933a550af5

wallet: Remove unused CachedTxGet{Available,Immature}Credit

These two functions are no longer used as GetBalances now uses the TXO
set rather than per-tx cached balances

36743a5ee1

bench: Have AvailableCoins benchmark include a lot of unrelated utxos

One of the main issues with AvailableCoins is its performance when txs
have unrelated outputs, so update the benchmark to check the performance
of that.

48545bdb3b

achow101 force-pushed on Oct 24, 2024

DrahtBot removed the label Needs rebase on Oct 24, 2024

DrahtBot added the label CI failed on Oct 25, 2024

DrahtBot removed the label CI failed on Oct 25, 2024

jonatack commented at 12:33 pm on November 26, 2024: member

Concept ACK, if this patchset can meaningfully improve performance and reliably refresh wallet utxos to keep the in-memory cache in sync.

wallet: Keep track of the wallet’s own transaction outputs in memory #27286

Benchmarks:

Code Coverage & Benchmarks

Reviews

Conflicts