bitcoindevkit / bitcoindevkit/bdk

Expose a display-oriented canonical transaction ordering (newest-first, DAG-consistent)

Open
#2,247 0 comments 2 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
1.1k
Forks
483
Avg merge
20d 3h
Merged PRs (30d)
3

Description

### Describe the enhancement

`CanonicalView`'s topological ordering (#2201 / #2219) gives **parent-before-child** order — the right primitive for dependency-sensitive consumers (e.g. rebroadcast). But a wallet UI needs the *display* order, which is a different thing:

- **newest-first** — unconfirmed first, then confirmed by descending height, and
- **DAG-consistent** — a parent must never appear *above* its own child.

There's currently no first-class API for that, so apps hand-roll it: typically `list_ordered_canonical_txs(..)` (or the canonical set) collected, `reverse()`d, then a stable `sort_by_key(|tx| Reverse(tx.chain_position))`. That is *chain-position-primary with topology only as an equal-key tiebreak*, and it breaks the DAG invariant in a real edge case:

`ChainPosition::Ord` orders unconfirmed txs by `first_seen` / `last_seen`, with `None` sorting **last**. So an **unconfirmed ancestor with `first_seen = None`** compares *after* a child with `first_seen = Some(_)`; under `Reverse` the parent then sorts **above** its child — a visible DAG violation in the transaction list. The keys differ, so a stable topological tiebreak cannot repair it.

### Use case

Rendering a wallet's transaction history: newest activity on top, but never a spend shown above the transaction it spends. This is what most wallet front-ends display. (It came up concretely in a Frostsnap transaction-list ordering fix — frostsnap/frostsnap#503 / #516.)

### Proposal / questions

The composite is implementable from data already exposed — Kahn's algorithm over the **reversed** spend DAG with a `Reverse(ChainPosition)` priority queue for ready nodes yields child-before-parent while ordering otherwise-unconstrained transactions newest-first (the mirror of what #2219 does in the forward direction). So a couple of options:

1. **Expose a display-oriented ordering directly** — e.g. a newest-first / `rev()`-style variant of the `CanonicalView` iterator, with a documented DAG-consistency guarantee (a parent never precedes its child).
2. **Document how to derive it** from `CanonicalView` — in particular, does reversing #2219's `DoubleEndedIterator` yield a DAG-consistent newest-first order in all cases, including the `first_seen = None` ancestor above? If so, a short doc note + example would close the gap.

Relates to #2201 / #2219.

Contributor guide

Open the contributing guide

Research direction

Start with CanonicalView and the ordering introduced in #2201/#2219; inspect how reversing or iterating the canonical DAG handles an unconfirmed ancestor with first_seen=None. Decide whether to expose a reverse display-order API or document the derivation, and finish with coverage of the child-before-parent guarantee and newest-first behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
api
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.