bitcoindevkit / bitcoindevkit/coin-select

Benchmark ancestor-aware coin selection against Bitcoin Core

Open
#67 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
18
Forks
14
PR merge metrics
No merged PRs in 30d

Description

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

Contributor guide

No contributing guide indexed for this repository

Research direction

Read the existing ancestor-aware LowestFee benchmark entry points, then inspect Bitcoin Core's wallet/coinselection primitives and the crate's Rust selection flow. Use the proposed shared fixtures for both kernel and native-flow tracks with the stated budget. Done means one reproducible command emits runtime, node, completion, selection, and package-quality results, with a smoke fixture and documented pinned Core revision.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, rust
Domain
performance, testing-qa
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.