bitcoindevkit / bitcoindevkit/coin-select
Benchmark ancestor-aware coin selection against Bitcoin Core
- 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