Benchmark ancestor-aware coin selection against Bitcoin Core

[evanlinjin]

Why

We have benchmarks for ancestor-aware LowestFee, but no apples-to-apples comparison with Bitcoin Core.

The implementations make different tradeoffs:

• Core's search uses each UTXO's individual ancestor bump fee, then discounts overlapping ancestry after a result is found.
• coin-select nets the ancestor union while searching, so shared-ancestor synergy can affect which branches are explored.
• Core uses bounded DFS and a portfolio of algorithms; this crate uses a metric-driven priority-queue BnB with a caller-selected round limit.

Without a shared workload and objective, comparing wall-clock numbers would be misleading.

Proposed benchmark

Build a fixture-driven harness with two tracks:

1. Search-kernel comparison

Run both BnB implementations with the same changeless objective, candidates, target, effective feerate, maximum weight, and 100,000-node budget. This isolates traversal and pruning efficiency.

2. Wallet-outcome comparison

Run each implementation's native selection flow and compare the resulting transaction/package quality. This acknowledges that Core's algorithm portfolio and this crate's LowestFee metric do not optimize exactly the same objective.

Pin the Bitcoin Core commit used by the harness so results remain reproducible.

Shared fixtures

Use a simple checked-in format (JSON is fine) describing:

• candidate ID, value, child input weight, and script/input type
• confirmed or unconfirmed parent transaction
• ancestor graph with transaction ID, weight, fee, and parents
• target output value/weight
• target and long-term feerates
• change output/spend weights
• optional child max_weight
• search budget and deterministic seed

Include these datasets at sizes 20, 50, 100, and 200:

• no ancestry (control)
• private ancestry
• shared ancestry
• nested/transitive ancestry
• overpaying ancestors subsidizing underpaying ancestors
• wallet-shaped mixed values and input types
• adversarial shared-ancestor cases where summing individual bump fees hides a good selection

Disable address grouping for the kernel comparison so one fixture candidate maps to one Core OutputGroup. Document every semantic conversion made by either adapter.

Record

For every run, emit machine-readable results containing:

• wall-clock time
• selections/nodes evaluated
• whether the search exhausted the tree or hit its budget
• selected candidate IDs
• child weight and child fee
• combined ancestor bump fee
• total package fee
• objective score/waste
• peak memory, if practical

Report solution-quality differences separately from runtime differences. In particular, flag cases where both runners finish but select different packages, and verify each result against the fixture's ancestor union.

Implementation shape

• Add a small Bitcoin Core C++ benchmark executable or test target using wallet/coinselection primitives and a fixture adapter.
• Add a Rust runner for the same fixtures.
• Add a top-level script that builds both pinned revisions, runs the matrix, and writes CSV/JSON plus a short Markdown summary.
• Keep a small smoke fixture in CI; run the full benchmark manually or on a dedicated benchmark job.

Done when

• One documented command reproduces both runners on the same machine.
• The Core revision, compiler settings, warm-up, sample count, and search budget are recorded.
• Kernel comparisons use the same objective and termination budget.
• Native-flow comparisons clearly label their different objectives.
• Results include runtime, nodes, completion status, and package-quality metrics.
• At least one overlapping-ancestry fixture checks whether Core's post-selection bump discount and this crate's in-search union lead to different selections.

Related: #24, #64, #65