wallet: Enforce BDB btree levels and overflow item sizes #34959

achow101 commented at 8:51 PM on March 30, 2026: member

Alternative to #34946

BDB's overflow records include the total length of the data to be read from the overflow pages. If this length is impossible (larger than max page * page size), or if the data that we are reading exceeds the stated length, then throw an exception as this is an invalid BDB file. This prevents infinite looping if an overflow page makes a circular reference.

BDB BTrees also include the level in the tree that the page is supposed to be at. Leaf pages are always at level 1. Starting from the root page, we can validate that each child has a level one less than the parent, until we reach a leaf page with a level of 1. This also ensures that we cannot have circular internal page references.

DrahtBot added the label Wallet on Mar 30, 2026

DrahtBot commented at 8:51 PM on March 30, 2026: contributor

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

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

No conflicts as of last run.

DrahtBot added the label CI failed on Mar 30, 2026

DrahtBot commented at 11:23 PM on March 30, 2026: contributor

🚧 At least one of the CI tasks failed. <sub>Task macOS native, fuzz: https://github.com/bitcoin/bitcoin/actions/runs/23767143572/job/69249406422</sub> <sub>LLM reason (✨ experimental): Fuzz test failure: wallet_bdb_parser crashed with std::runtime_error (“BTree Leaf page is not at level 1”), exiting with code 1.</sub>

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

achow101 force-pushed on Mar 30, 2026

DrahtBot removed the label CI failed on Mar 31, 2026

instagibbs commented at 12:25 PM on March 31, 2026: member

This is a superset of my fix, including the other OOM issue? I can close mine.

achow101 commented at 5:40 PM on March 31, 2026: member

This is a superset of my fix, including the other OOM issue? I can close mine.

Should be

luke-jr commented at 4:23 PM on April 10, 2026: member

ab13438d83e38bd1aeca02fb8239b08c04a0447c commit description has a typo "legnth"

luke-jr referenced this in commit 4c6920ba6b on Apr 13, 2026

luke-jr referenced this in commit 09304e3d05 on Apr 13, 2026

luke-jr commented at 2:22 PM on April 14, 2026: member

bdbro fails tool_wallet/test_dump_very_large_records with this change (though CI passes because there's no way to test bdbro with it in Core master)

Traceback (most recent call last):
  File "test/functional/test_framework/test_framework.py", line 135, in main
    self.run_test()
    ~~~~~~~~~~~~~^^
  File "test/functional/tool_wallet.py", line 628, in run_test
    self.test_dump_very_large_records()
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^^
  File "test/functional/tool_wallet.py", line 542, in test_dump_very_large_records
    self.assert_tool_output("The dumpfile may contain private keys. To ensure the safety of your Bitcoin, do not share the dumpfile.\n", "-wallet=bigrecords", f"-dumpfile={wallet_dump}", "dump")
    ~~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "test/functional/tool_wallet.py", line 67, in assert_tool_output
    assert_equal(stderr, '')
    ~~~~~~~~~~~~^^^^^^^^^^^^
  File "test/functional/test_framework/util.py", line 77, in assert_equal
    raise AssertionError("not(%s)" % " == ".join(str(arg) for arg in (thing1, thing2) + args))
AssertionError: not(Overflow record has an impossible length
 == )

achow101 commented at 9:40 PM on April 15, 2026: member

bdbro fails tool_wallet/test_dump_very_large_records with this change (though CI passes because there's no way to test bdbro with it in Core master)

I am not observing this failure when this branch is backported to 29.x.

luke-jr referenced this in commit 7d07efad0a on Apr 16, 2026

luke-jr referenced this in commit b465c019f6 on Apr 16, 2026

luke-jr commented at 4:11 AM on April 16, 2026: member

Backport: https://github.com/bitcoin/bitcoin/compare/29.x...luke-jr:bitcoin:bdbro_enforce_levels_sizes-29.3-BUGGY

test/functional/tool_wallet.py --legacy-wallet --bdbro

in src/wallet/migrate.cpp:649 in 6368100e97 outdated

 646 |      while (pages.size() > 0) {
 647 | -        uint32_t curr_page = pages.back();
 648 | +        auto [curr_page, expected_level] = pages.back();
 649 |          // It turns out BDB completely ignores this last_page field and doesn't actually update it to the correct
 650 |          // last page. While we should be checking this, we can't.
 651 |          // This is left commented out as a reminder to not accidentally implement this in the future.

instagibbs commented at 2:23 PM on April 16, 2026:

I think this means we shouldn't be using inner_meta.last_page?

claude suggested "uint64_t max_data_size = static_cast<uint64_t>(outer_meta.last_page) * page_size"

achow101 commented at 5:02 PM on April 16, 2026:

It would seem so...

instagibbs commented at 5:06 PM on April 16, 2026:

still think you need to promote one of the operands to avoid overflow before storing in 64 bit? Am I wrong?

achow101 commented at 5:11 PM on April 16, 2026:

oops yeah

achow101 force-pushed on Apr 16, 2026

wallet, bdbro: Enforce overflow data lengths

The total length of the data in an overflow record is being given to us.
We should validate that the length is reasonable (fits in the total size
of the file), and to stop reading additional data if the amount of data
read exceeds the stated legnth. This prevents infinite looping behavior.

dc3a2b9c3b

wallet, bdbro: Validate btree page levels

BTree pages contain the level in the BTree that the page is supposed to
be at. The root starts at some level between 1 and 255, leaves are
always level 1. Internal pages must be a level that is one less than its
parent. Validating that pages are at their expected level (except for
the root page) enforces that no cycles can occur.

b2de59d486

achow101 force-pushed on Apr 16, 2026

DrahtBot added the label CI failed on Apr 16, 2026

luke-jr referenced this in commit 885a34eceb on Apr 16, 2026

luke-jr referenced this in commit 4dbbeead9a on Apr 16, 2026

DrahtBot removed the label CI failed on Apr 16, 2026