wallet: Track no-longer-spendable TXOs separately

achow101 commented at 6:40 pm on June 12, 2023: member

In #27286, the wallet keeps track of all of its transaction outputs, even if they are already spent or are otherwise unspendable. This TXO set is iterated for balance checking and coin selection preparation, which can still be slow for wallets that have had a lot of activity. This PR aims to improve the performance of such wallets by moving UTXOs that are definitely no longer spendable to a different map in the wallet so that far fewer TXOs need to be iterated for the aforementioned functions.

Unspendable TXOs (not to be confused with Unspent TXOs) are those which have a spending transaction that has been confirmed, or are no longer valid due to reorgs. TXOs that are spent in unconfirmed transactions remain in the primary TXO set, and are filtered out of balance and coin selection as before.

Depends on #27286

DrahtBot commented at 6:40 pm on June 12, 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/27865.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	remyers, murchandamus, jonatack

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:

#bitcoin-core/gui/872 (Menu action to export a watchonly wallet by achow101)
#32763 (wallet: Replace CWalletTx::mapValue and vOrderForm with explicit class members by achow101)
#32618 (wallet: Remove ISMINE_WATCHONLY and watchonly from RPCs by achow101)
#32523 (wallet: Remove watchonly behavior and isminetypes by achow101)
#32489 (wallet: Add exportwatchonlywallet RPC to export a watchonly version of a wallet by achow101)
#29415 (Broadcast own transactions only via short-lived Tor or I2P connections by vasild)
#29278 (Wallet: Add maxfeerate wallet startup option by ismaelsadeeq)
#29062 (Wallet: (Refactor) GetBalance to calculate used balance by BrandonOdiwuor)

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 Jun 12, 2023

DrahtBot added the label CI failed 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

achow101 force-pushed on Jun 28, 2023

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

achow101 commented at 9:32 pm on September 7, 2023: member

@t-bast You may be interested in this for very large wallets.

t-bast commented at 12:26 pm on September 11, 2023: contributor

Neat, thanks @achow101, @remyers will give that a try and will review the related PRs!

remyers commented at 7:49 pm on September 12, 2023: contributor

Concept ACK - on a large synthetic test wallet I’m seeing a 250x speed up.

I created a large wallet in regtest with many fanout style transactions - 100,000 blocks each creating 1000 utxos. There are only 117 utxos currently, but the wallet.dat file is 370M.

Using the same wallet.dat file and (transaction history) fundrawtransaction saw a substantial speedup: ~5 seconds using v25.99.0-a36134fcc7b4 ~20 milliseconds using v25.99.0-d9c4dcfe68c5 (latest wallet-unspent-txos)

I will try to recreate my large test wallet.dat file tomorrow so I can confirm the steps to reproduce it. Is there anything in particular I can do to help? Would you like more testing? code review?

NB: I had to export my original wallet descriptors and re-import them to work around the issue fixed in #27920. Before the export/import the wallet.dat file was 1.1G, but the speed of fundrawtransaction was 5 sec both in the original file and the tested one created via importing descriptors.

achow101 commented at 8:55 pm on September 12, 2023: member

Is there anything in particular I can do to help? Would you like more testing? code review?

The prerequisite PR (#27286) will need review and testing before this can be merged. That should also provide some speed up.

remyers commented at 9:53 am on September 13, 2023: contributor

The prerequisite PR (#27286) will need review and testing before this can be merged. That should also provide some speed up.

Will do. I’m getting 400-500ms for the same test using just #27286, so indeed also ~100x speed-up.

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

achow101 force-pushed on Sep 15, 2023

DrahtBot added the label Needs rebase on Sep 19, 2023

achow101 force-pushed on Sep 27, 2023

DrahtBot removed the label Needs rebase on Sep 27, 2023

DrahtBot added the label Needs rebase on Oct 16, 2023

achow101 force-pushed on Oct 16, 2023

DrahtBot removed the label Needs rebase on Oct 16, 2023

DrahtBot added the label Needs rebase on Oct 23, 2023

achow101 force-pushed on Oct 24, 2023

DrahtBot removed the label Needs rebase on Oct 24, 2023

achow101 force-pushed on Oct 24, 2023

DrahtBot added the label Needs rebase on Oct 29, 2023

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 15, 2023

achow101 force-pushed on Nov 15, 2023

DrahtBot removed the label Needs rebase on Nov 15, 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

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

Concept ACK

DrahtBot added the label Needs rebase on Feb 3, 2024

achow101 force-pushed on Feb 3, 2024

DrahtBot removed the label Needs rebase on Feb 3, 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 21, 2024

DrahtBot added the label Needs rebase on Mar 27, 2024

achow101 force-pushed on Apr 1, 2024

DrahtBot removed the label Needs rebase on Apr 1, 2024

DrahtBot added the label Needs rebase on Apr 8, 2024

achow101 force-pushed on Apr 25, 2024

DrahtBot removed the label Needs rebase on Apr 25, 2024

achow101 force-pushed on Jun 6, 2024

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 force-pushed on Sep 10, 2024

DrahtBot added the label Needs rebase on Oct 24, 2024

achow101 force-pushed on Oct 24, 2024

DrahtBot removed the label Needs rebase on Oct 25, 2024

achow101 force-pushed on Oct 28, 2024

DrahtBot removed the label CI failed on Oct 28, 2024

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

Concept ACK, pending #27286, if this improves performance for wallets with many transactions.

DrahtBot added the label Needs rebase on Mar 13, 2025

achow101 force-pushed on Apr 10, 2025

DrahtBot removed the label Needs rebase on Apr 10, 2025

DrahtBot added the label Needs rebase on Apr 25, 2025

achow101 force-pushed on Apr 25, 2025

DrahtBot removed the label Needs rebase on Apr 25, 2025

DrahtBot added the label Needs rebase on May 7, 2025

achow101 force-pushed on May 7, 2025

DrahtBot removed the label Needs rebase on May 7, 2025

achow101 force-pushed on May 7, 2025

DrahtBot added the label Needs rebase on May 14, 2025

achow101 force-pushed on May 15, 2025

DrahtBot removed the label Needs rebase on May 15, 2025

achow101 force-pushed on May 16, 2025

DrahtBot added the label Needs rebase on May 16, 2025

achow101 force-pushed on May 16, 2025

DrahtBot removed the label Needs rebase on May 16, 2025

achow101 force-pushed on May 16, 2025

DrahtBot added the label CI failed on May 19, 2025

achow101 force-pushed on May 19, 2025

DrahtBot removed the label CI failed on May 19, 2025

DrahtBot added the label Needs rebase on May 19, 2025

achow101 force-pushed on May 20, 2025

DrahtBot removed the label Needs rebase on May 20, 2025

DrahtBot added the label Needs rebase on May 21, 2025

achow101 force-pushed on May 21, 2025

DrahtBot removed the label Needs rebase on May 21, 2025

DrahtBot added the label Needs rebase on May 30, 2025

achow101 force-pushed on May 30, 2025

DrahtBot removed the label Needs rebase on May 30, 2025

in src/wallet/test/util.cpp:26 in 9554a4d79a outdated

27-    }
28+    bilingual_str error;
29+    std::vector<bilingual_str> warnings;
30+    auto wallet = CWallet::Create(context, "", CreateMockableWalletDatabase(), WALLET_FLAG_DESCRIPTORS, error, warnings);
31+
32+    // Allow the fallback fee with it's default

maflcko commented at 7:17 am on June 2, 2025:

“with it’s default” -> “with its default” [“it’s” is a contraction of “it is,” but here the possessive “its” is required]

achow101 commented at 7:37 pm on June 2, 2025:

Fixed

achow101 force-pushed on Jun 2, 2025

DrahtBot added the label Needs rebase on Jun 25, 2025

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.

e02f2d331c

wallet: MarkDirty after AddWalletDescriptor

After adding a wallet descriptor (typically by import), mark all balance
caches dirty. This allows transactions that the wallet already knows
about that have outputs that are now ISMINE_SPENDABLE after the import
to actually be shown in balance calculations. Legacy wallet imports
would do this, but importdescriptors did not.

8222341d4f

test: Test for balance update due to untracked output becoming spendable 5cc32ee2a7

walletdb: Load Txs last

Need to load txs last so that IsMine works.

0f269bc48c

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.

ae0876ec42

wallet: Exit IsTrustedTx early if wtx is already in trusted_parents ae888c38d0

wallet: Recalculate the wallet's txos after any imports 96e7a89c5e

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.

dde7cbe105

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.

c1801b78f1

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.

764016eb22

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.

17d453cb3a

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.

49675de035

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

215e5999e2

wallet: Store the TxState in each WalletTXO as well 17605c515e

wallet: Get the depth in main chain for a TxState 981b8c73cd

wallet: Get the coinbase maturity state for a TXO and TxState 455058b142

wallet: Use WalletTXO stored state and coinbase rather than wtx f36802e54e

walletdb: Move ReorderTransactions to immediately after loading txs

Perform the transaction reorder upgrade immediately after loading txs
instead of waiting for the end of loading.

8937d700aa

wallet: Add m_from_me to cache "from me" status

m_from_me is used to track whether a transaction is "from me", i.e. has
any inputs which belong to the wallet.

04b129a9ac

wallet: Replace CachedTxIsFromMe with direct m_from_me lookup

Instead of looking at the cached amounts or searching every input of a
transaction each time we want to determine whether it is "from me", use
m_from_me  which stores this value for us.

6d43f8b895

achow101 force-pushed on Jun 27, 2025

DrahtBot added the label CI failed on Jun 27, 2025

DrahtBot commented at 3:08 am on June 27, 2025: contributor

🚧 At least one of the CI tasks failed. Task lint: https://github.com/bitcoin/bitcoin/runs/44895352538 LLM reason (✨ experimental): The failure is caused by a Python lint error due to an unused variable in the wallet_backwards_compatibility.py test.

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

DrahtBot removed the label Needs rebase on Jun 27, 2025

achow101 force-pushed on Jun 27, 2025

wallet: Store a copy of m_from_me in WalletTXOs and use for "from me"

Since we need to know whether the transaction that creates a WalletTXO
is "from me", we should store this state in the WalletTXO too, copied
from its parent CWalletTx.

930ebccadb

wallet: Have WalletTXOs also store parent tx time

WalletTXOs need to know their parent tx's timestamp for AvailableCoins
to work.

151a0223cb

wallet: Make CWalletTx::m_state private with {get,set}ters b76608b542

wallet: have CWalletTx also be aware of it's WalletTXOs 8a6838b921

wallet: Also update a CWalletTx's WalletTXOs states

When the state of a CWalletTx changes, we need to change the state in
the WalletTXOs too.

c088d90521

wallet: Remove unused WalletTXO::GetWalletTx() f9eecdbb70

wallet: Have IsSpent take a min_conf

A min_conf parameter is added to IsSpent so that it can set a
confirmation threshold for whether something is considered spent.

17e46ddf0f

wallet: Iterate block txs in reverse on blockDisconnected

When a block is disconnected, we need to process the transactions in
reverse order so that the wallet's TXO set is updated in the correct
order.

aaba6e0dce

wallet, tests: Have CreateSyncedWallet use CWallet::Create

CWallet::Create will properly connect the wallet to the chain, so we
should be doing that rather than ad-hoc chain connection.

e2732033db

wallet: Move definintely unusable TXOs to a separate container

Definitely unusable TXOs are those that are spent by a confirmed
transaction or were produced by a now conflicted transaction. However,
we still need them for GetDebit, so we store them in a separate
m_unusable_txos container. MarkConflicted, AbandonTransaction, and
loading (via PruneSpentTXOs) will ensure that these unusable TXOs are
properly moved.

856f58cfda

achow101 force-pushed on Jun 27, 2025

DrahtBot removed the label CI failed on Jun 28, 2025

wallet: Track no-longer-spendable TXOs separately #27865

Code Coverage & Benchmarks

Reviews

Conflicts