]> Untitled Git - bdk/commit
feat(chain)!: `O(n)` canonicalization algorithm
author志宇 <hello@evanlinjin.me>
Sun, 3 Nov 2024 01:51:58 +0000 (12:51 +1100)
committer志宇 <hello@evanlinjin.me>
Tue, 10 Dec 2024 10:39:23 +0000 (21:39 +1100)
commit582d6b51f865d98077d72422d15630a2a3c7d16e
treedf23142a6c7708ba12f09ac198a0b0730a57e393
parentf6192a615a7aea2ca9bdcca199356ea4d0386ce1
feat(chain)!: `O(n)` canonicalization algorithm

This is an O(n) algorithm to determine the canonical set of txids.

* Run 1: Iterate txs with anchors, starting from highest anchor height
  txs.
* Run 2: Iterate txs with last-seen values, starting from highest
  last-seen values.
* Run 3: Iterate txs that are remaining from run 1 which are not
  anchored in the best chain.

Since all transitively-anchored txs are added to the `canonical` set in
run 1, and anything that conflicts to anchored txs are already added to
`not_canonial`, we can guarantee that run 2 will not traverse anything
that directly or indirectly conflicts anything that is anchored.

Run 3 is needed in case a tx does not have a last-seen value, but is
seen in a conflicting chain.

`TxGraph` is updated to include indexes `txids_by_anchor_height` and
`txids_by_last_seen`. These are populated by the `insert_anchor` and
`insert_seen_at` methods. Generic constaints needed to be tightened as
these methods need to be aware of the anchor height to create
`LastSeenIn`.
12 files changed:
crates/bitcoind_rpc/tests/test_emitter.rs
crates/chain/src/canonical_iter.rs [new file with mode: 0644]
crates/chain/src/lib.rs
crates/chain/src/tx_graph.rs
crates/chain/tests/common/tx_template.rs
crates/chain/tests/test_indexed_tx_graph.rs
crates/chain/tests/test_tx_graph.rs
crates/chain/tests/test_tx_graph_conflicts.rs
crates/wallet/src/test_utils.rs
crates/wallet/src/wallet/mod.rs
crates/wallet/tests/wallet.rs
example-crates/example_cli/src/lib.rs