wallet: Replace mapWallet and wtxOrdered with a boost::multi_index #35716

The wallet needs to access transactions both by txid, and by insertion order into the wallet. mapWallet was the main container for the wallet transactions, and it was keyed by txid. wtxOrdered was a secondary container which was keyed by order, and held pointers to the CWalletTx objects stored in mapWallet. These are replaced by a new boost multi index which indexes on txid and insertion order, allowing us to get rid of the 2 separate containers, and holding raw pointers to CWalletTx.

This depends on #35501 for the CWalletTx constructor changes that are necessary for this.

<!--e57a25ab6845829454e8d69fc972939a-->

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

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage & Benchmarks

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

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline and AI policy for information on the review process.

If your review is incorrectly listed, please copy-paste <code>&lt;!--meta-tag:bot-skip--&gt;</code> into the comment that the bot should ignore.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #35662 (script: make txdata non-default-constructible by l0rinc)
• #35501 (wallet: store all witness variants of a transaction by achow101)
• #35294 (wallet: Update tx chain state during loading during AttachChain instead of before by achow101)
• #35151 (wallet, follow-up: Refactor IsSpent to use HowSpent by musaHaruna)
• #34909 (wallet, refactor: modularise wallet by extracting out legacy wallet migration by rkrux)
• #34872 (wallet: fix mixed-input transaction accounting in history RPCs by w0xlt)
• #34681 (wallet: move rescan logic into ChainScanner and wallet/scan by Eunovo)
• #34400 (wallet: parallel fast rescan (approx 8x speed up with 8 threads) by Eunovo)
• #34371 (wallet: allow importprunedfunds for spending transactions by 8144225309)
• #33034 (wallet: Store transactions in a separate sqlite table by achow101)
• #30343 (wallet, logging: Replace WalletLogPrintf() with LogInfo() by ryanofsky)
• #29278 (Wallet: Add maxfeerate wallet startup option by ismaelsadeeq)
• #27865 (wallet: Track no-longer-spendable TXOs separately by achow101)

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.

<!--5faf32d7da4f0f540f40219e4f7537a3-->

LLM Linter (✨ experimental)

Possible typos and grammar issues:

• # Update listtransctions' output from old nodes to be compatible -> # Update listtransactions' output from old nodes to be compatible [misspelled word in a comment]

Possible places where named args for integral literals may be used (e.g. func(x, /*named_arg=*/0) in C++, and func(x, named_arg=0) in Python):

• ListTransactions(*pwallet, *it, 0, true, ret, filter_label); in src/wallet/rpc/transactions.cpp
• ListTransactions(wallet, tx, 0, true, transactions, filter_label, include_change); in src/wallet/rpc/transactions.cpp
• ListTransactions(wallet, *wtx, -100000000, true, removed, filter_label, include_change); in src/wallet/rpc/transactions.cpp

^{2026-07-14 17:57:16}

<!--85328a0da195eb286784d51f73fa0af9-->

🚧 At least one of the CI tasks failed. _{Task test ancestor commits: https://github.com/bitcoin/bitcoin/actions/runs/29296252667/job/86970309393} _{LLM reason (✨ experimental): CI failed because the fuzz build (src/test/fuzz/spend.cpp) stopped with a Clang -Werror,-Wunused-variable error for an unused txid variable.}

<details><summary>Hints</summary>

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.

</details>

Concept ACK. multi_index seems like the right thing to use here. Since this doesn't leak into consensus/node, I don't see the harm in spreading the dependency to wallet.

Getting rid of multi_index for the kernel will require something that essentially re-implements its functionality, and I don't see anything new here that would complicate that implementation.

Note that I'm biased: I'm currently working on such a re-implementation that I hope to propose for v33.

I do have a few requests to make my life easier though.

Firstly, please specify an index for each operation, as opposed to just using m_txs. What happens behind the scenes in that case is that the first index is used, which is not at all obvious to reviewers. In my rewrite I'm hoping to drop the implicit first index functionality and require an index for each call, as that greatly simplifies the implementation.

For ex, rather than m_txs.find(hash) use m_txs.get<index_by_txid>().find(hash). That also means adding the tag for the txid index, which is currently missing.

To simplify that, in wallet.h, you can do:

WalletTxs m_txs;
WalletTxs::index<index_by_txid>& m_txs_by_txid;
WalletTxs::index<index_by_pos>& m_txs_by_pos;

And in the constructor:

m_txs_by_txid(m_txs.get<index_by_txid>());
m_txs_by_pos(m_txs.get<m_txs_by_pos>());

Then everywhere you would use m_txs, use m_txs_by_txid or m_txs_by_pos instead. That makes the intent much more clear.

Here's an example of the mempool conversion to work that way (though I used indices rather than tags, which is uglier): https://github.com/theuni/bitcoin/commit/b58ab92f9d6b231967328f560701d42710e04b92 .

Secondly, please use extract/insert rather than modify. The former is compatible with the std container apis and has familiar (and much simpler) semantics wrt re-insertion failure. I was planning on removing our existing modify calls for the same reason, so it'd be nice to not be adding more in the meantime.