f08eeac154 fix(chain): let the indexer decide how far to rescan (LLFourn)
Pull request description:
### Description
`IndexedTxGraph::reindex` was a single pass over `TxGraph::full_txs`, which iterates a `HashMap`. That made it **nondeterministic**: the same graph reindexed twice could produce two different `last_revealed` results.
Each match inside `KeychainTxOutIndex::_index_txout` bumps `last_revealed` and then calls `replenish_inner_index`, whose stop index is `last_revealed + 1 + lookahead`. So a match *widens the derived window the remaining outputs are judged against*. An output far enough out to need that widening was skipped if it happened to be visited first, and no pass revisited it.
Concretely, with `lookahead` 1000 and an empty frontier the derived set is `0..1001`. Given one tx paying index 900 and another paying 1850: visited 900-first, the window grows to 1901 and both are found; visited 1850-first, 1850 is missed and stays missed. Same inputs, different index, decided by `HashMap` iteration order.
The usual objection — that callers should reveal before reindexing — does not hold. The lookahead exists precisely to catch indices the persisted frontier does not know about: a restored wallet, another signer on the same descriptor, an externally built PSBT paying one of our far indices. Whenever the lookahead does its job the frontier moves mid-walk, so the order dependence is present in the intended use, not just in misuse.
### The change
Add `Indexer::rescan`, handed the whole `TxGraph` and returning the indexing it produced:
```rust
fn rescan<A>(&mut self, graph: &TxGraph<A>) -> Self::ChangeSet
where
Self::ChangeSet: Merge,
```
The default implementation offers every full transaction and floating output to `index_tx` / `index_txout` exactly once — all an indexer needs when what it recognizes is fixed up front — and `IndexedTxGraph::reindex` becomes a call to it. `KeychainTxOutIndex` overrides it and looks repeatedly, stopping when a pass leaves its revealed frontier unmoved.
Whether to look more than once belongs to the indexer, because the indexer is the only thing that knows whether its recognition set can still grow. Two things follow from putting it there rather than in `IndexedTxGraph`:
- **An indexer that does not widen what it matches is walked exactly once**, as today. `SpkTxOutIndex` is unaffected. There is no convergence requirement imposed on implementors, and no way for a third-party indexer to be spun forever by a loop it never asked for.
- **`KeychainTxOutIndex` can key the loop on its own frontier** rather than on whether a changeset came back empty. That matters: the changeset also carries staged spk cache entries, which move *without* the frontier moving. A `changeset.is_empty()` loop therefore spends an extra full walk on the ordinary restore path. I measured this — with `persist_spks = true`, restoring via `from_changeset` with a correct frontier takes **1 pass** keyed on the frontier versus **2** keyed on changeset emptiness.
### Notes to the reviewers
**On the test shape.** The regression test uses **one** transaction with two of our outputs rather than two transactions. A two-transaction test would depend on graph walk order — the very thing that is unreliable — and so would pass a single-pass implementation about half the time, which is a test that fails to fail. `index_tx` walks `tx.output`, a `Vec`, in vout order, so a single tx paying a far index at vout 0 and a near one at vout 1, against an empty frontier, misses the far output on every pass on every run. It is deterministic by construction; I verified it fails against the old implementation on five consecutive runs (`left: Some(9)`, `right: Some(15)`).
**On cost.** `KeychainTxOutIndex::rescan` re-walks the whole graph per look, so it is O(looks × txs), with looks bounded by the number of distinct frontier advances plus one. Measured: the settled/restore case is 1 look; the recovery case in the test (empty frontier, far output only reachable after the near one lands) is 3. Making a later look re-examine only the outputs that did not already match would need the indexer to say *what* to re-offer rather than just *whether*, which is a bigger change than this fix.
**Trait change.** `rescan` is a defaulted method, so existing `Indexer` implementations keep compiling unchanged. It is generic over the anchor `A`, which makes `Indexer` no longer object-safe — nothing in the workspace uses `dyn Indexer`.
**Known adjacent gap, not addressed here.** `index_tx_graph_changeset` — used by `insert_tx`, `insert_txout`, `apply_update` and `apply_block_relevant` — is still a single pass and has the same order dependence. Feeding the one-transaction case above through `insert_tx` yields `last_revealed = Some(9)` and only one of the two outpoints, so a live wallet can drop the far UTXO until the next restart re-runs `reindex`. It needs the incremental paths to go through the same mechanism rather than their own copy; I kept this PR to `reindex` to stay reviewable, and am happy to follow up.
### Changelog notice
- Added: `Indexer::rescan`, which indexes an entire `TxGraph` and lets an implementation decide how many looks that takes. Defaulted, so existing implementations are unaffected.
- Fixed: `IndexedTxGraph::reindex` no longer depends on `HashMap` iteration order. It previously made a single pass and could miss outputs at derivation indices that only came into range after another output in the same walk advanced the lookahead; `KeychainTxOutIndex` now looks until its revealed frontier stops moving.
### Checklists
#### All Submissions:
* [x] I followed the [contribution guidelines](https://github.com/bitcoindevkit/bdk/blob/master/CONTRIBUTING.md)
#### New Features:
* [x] I've added tests for the new feature
* [x] I've added docs for the new feature
#### Bugfixes:
* [ ] This pull request breaks the existing API
* [x] I've added tests to reproduce the issue which are now passing
ACKs for top commit:
evanlinjin:
ACK f08eeac154
Tree-SHA512: 0c5496805655a2c0f060e26bacd05a48adb2866961a9b785b53b444572a5b2e7f78ad0ddbcb737a308be5e1958bb0c49c09ed1e56fb30d029e06661f9e10a953
The bdk libraries aim to provide well engineered and reviewed components for Bitcoin wallets and other applications.
They are built upon the excellent rust-bitcoin and rust-miniscript crates.
Architecture
The workspace in this repository contains several crates in the /crates directory:
Persistence backend for storing chain data in a single file. Intended for testing and development purposes, not for production.
The bdk_wallet repository and crate contains a higher level Wallet type that depends on the above lower-level mechanism crates.
Security Policy
To report a security issue, please refer to the security policy.
Minimum Supported Rust Version (MSRV)
The following BDK crates maintains a MSRV of 1.85.0. To build these crates with the MSRV of 1.85.0 you will need to pin dependencies by running the pin-msrv.sh script.
bdk_core
bdk_chain
bdk_bitcoind_rpc
bdk_esplora
bdk_file_store
bdk_electrum
Just
This project has a justfile for easy command running. You must have just installed.
Unless you explicitly state otherwise, any contribution intentionally
submitted for inclusion in the work by you, as defined in the Apache-2.0
license, shall be dual licensed as above, without any additional terms or
conditions.
acc06e5322
