bitcoindevkit / bitcoindevkit/coin-select

LowestFee: tighten the BnB bound when candidates have unconfirmed ancestors

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

## Background

Branch and bound (BnB) walks a tree of possible coin selections. At each node it asks the metric for a **bound**: the lowest score anything in this part of the tree could possibly reach. If that bound is already worse than the best answer found so far, the whole branch is skipped.

Two rules follow from that:

- A **tighter** (higher) bound prunes more, so the search is faster.
- A bound that is **too high** — above a score that really is reachable down that branch — makes BnB throw away the true best answer. Bounds must never do this. The word for "never too high" is *admissible*.

## Current state (after #64)

When a problem has unconfirmed ancestors, `LowestFee::bound` gives up its tight reasoning and returns a plain floor:

```
fee_floor = max( rate·(child weight) + ancestor_bump_lower_bound,
absolute fee,
RBF minimum )
```

The rest is switched off, because the tight path leans on two assumptions that ancestors break:

1. *"Selecting more never un-funds a selection."* False — a coin can drag in an unconfirmed parent whose bump costs more than the coin is worth.
2. *"A candidate costs its own weight."* False — a coin sharing an already-paid-for ancestor is cheaper than it looks; a coin dragging its own unpaid chain is dearer.

## Why it matters

Same candidates, ancestry declared vs not:

| problem | rounds |
| --- | --- |
| n=14, no ancestry (tight path) | 3304 |
| n=14, with ancestry | 6945 |
| n=16, no ancestry (tight path) | 8000 |
| n=16, with ancestry | 13769 |

Roughly **2× the work**. Answers are correct, just slower. (Not perfectly controlled — the optima differ because ancestors genuinely cost more — so read it as a rough ceiling on the headroom.)

## Plan

**1. Marginal cost helper.** Add "what would adding candidate `i` cost this selection *right now*?" = its own input weight priced at the target rate, plus the **extra** ancestor bump it brings given what is already dragged in. Cheap thanks to the private/shared split from #64: for privately reachable ancestors the delta is a fixed per-candidate pair; only shared ones need a lookup.

**2. Value-shortfall relaxation.** Rebuild the "resize" idea on marginal cost instead of raw value-per-weight: walk unselected candidates by best marginal value per marginal cost until funded, then allow a fractional slice of the last one. The ordering is only a heuristic once ancestors exist, so this step must **never** return `None` (see step 4).

**3. Funded-node bound.** Today a funded node's own score is not used, because a descendant can owe *less* (an ancestor that overpays nets against the deficit). Use `score − maximum reachable surplus` instead — the surplus figure already exists as `ancestor_bump_lower_bound`. Admissible, and much closer than the floor.

**4. Leave the `None` prunes off unless proven.** `select_iter().find(is_funded)?` returning `None` claims "nothing in this subtree can be funded". That is invalid when funding is not monotone, so it stays disabled.

## Watch out

#56 reports that the existing resize relaxation is **already inadmissible on master** (the greedy prefix's segwit corrections inflate `ideal_fee`). Re-enabling it for ancestors must not inherit that bug. Fixing #56 first, or building step 2 on marginal costs, both sidestep it.

## Done when

- The proptests in `tests/ancestor.rs` stay green: every bound ≤ every descendant score, `None` really means no solution in the subtree, and BnB == brute force. These catch exactly this class of mistake — three of them failed when the bound was deliberately made too tight.
- `run_bnb_lowest_fee_ancestors/{private,shared}/{20,50,100}` (benches added in #64) drop, closing most of the ~2× gap. Rough target: within ~1.2× of the no-ancestor path.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with LowestFee::bound and the ancestor handling introduced by #64. Read tests/ancestor.rs and run its proptests before changing the bound; the work is done when admissibility and BnB-versus-brute-force checks stay green, while the ancestor benchmarks approach the stated performance target.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
fintech-quant
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.