From 582d6b51f865d98077d72422d15630a2a3c7d16e Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=97=E5=AE=87?= Date: Sun, 3 Nov 2024 12:51:58 +1100 Subject: [PATCH] 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`. --- crates/bitcoind_rpc/tests/test_emitter.rs | 1 + crates/chain/src/canonical_iter.rs | 249 +++++++++++++++++ crates/chain/src/lib.rs | 2 + crates/chain/src/tx_graph.rs | 258 +++++++++++++----- crates/chain/tests/common/tx_template.rs | 4 +- crates/chain/tests/test_indexed_tx_graph.rs | 47 ++-- crates/chain/tests/test_tx_graph.rs | 24 +- crates/chain/tests/test_tx_graph_conflicts.rs | 4 +- crates/wallet/src/test_utils.rs | 55 ++-- crates/wallet/src/wallet/mod.rs | 8 +- crates/wallet/tests/wallet.rs | 75 ++--- example-crates/example_cli/src/lib.rs | 36 +-- 12 files changed, 562 insertions(+), 201 deletions(-) create mode 100644 crates/chain/src/canonical_iter.rs diff --git a/crates/bitcoind_rpc/tests/test_emitter.rs b/crates/bitcoind_rpc/tests/test_emitter.rs index 8c41efc0..14b0c921 100644 --- a/crates/bitcoind_rpc/tests/test_emitter.rs +++ b/crates/bitcoind_rpc/tests/test_emitter.rs @@ -389,6 +389,7 @@ fn tx_can_become_unconfirmed_after_reorg() -> anyhow::Result<()> { assert_eq!( get_balance(&recv_chain, &recv_graph)?, Balance { + trusted_pending: SEND_AMOUNT * reorg_count as u64, confirmed: SEND_AMOUNT * (ADDITIONAL_COUNT - reorg_count) as u64, ..Balance::default() }, diff --git a/crates/chain/src/canonical_iter.rs b/crates/chain/src/canonical_iter.rs new file mode 100644 index 00000000..7077e472 --- /dev/null +++ b/crates/chain/src/canonical_iter.rs @@ -0,0 +1,249 @@ +use crate::collections::{hash_map, HashMap, HashSet, VecDeque}; +use crate::tx_graph::{TxAncestors, TxDescendants}; +use crate::{Anchor, ChainOracle, TxGraph}; +use alloc::boxed::Box; +use alloc::collections::BTreeSet; +use alloc::sync::Arc; +use bdk_core::BlockId; +use bitcoin::{Transaction, Txid}; + +/// Iterates over canonical txs. +pub struct CanonicalIter<'g, A, C> { + tx_graph: &'g TxGraph, + chain: &'g C, + chain_tip: BlockId, + + pending_anchored: Box, &'g BTreeSet)> + 'g>, + pending_last_seen: Box, u64)> + 'g>, + pending_remaining: VecDeque<(Txid, Arc, u32)>, + + canonical: HashMap, CanonicalReason)>, + not_canonical: HashSet, + + queue: VecDeque, +} + +impl<'g, A: Anchor, C: ChainOracle> CanonicalIter<'g, A, C> { + /// Constructs [`CanonicalIter`]. + pub fn new(tx_graph: &'g TxGraph, chain: &'g C, chain_tip: BlockId) -> Self { + let anchors = tx_graph.all_anchors(); + let pending_anchored = Box::new( + tx_graph + .txids_by_descending_anchor_height() + .filter_map(|(_, txid)| Some((txid, tx_graph.get_tx(txid)?, anchors.get(&txid)?))), + ); + let pending_last_seen = Box::new( + tx_graph + .txids_by_descending_last_seen() + .filter_map(|(last_seen, txid)| Some((txid, tx_graph.get_tx(txid)?, last_seen))), + ); + Self { + tx_graph, + chain, + chain_tip, + pending_anchored, + pending_last_seen, + pending_remaining: VecDeque::new(), + canonical: HashMap::new(), + not_canonical: HashSet::new(), + queue: VecDeque::new(), + } + } + + /// Whether this transaction is already canonicalized. + fn is_canonicalized(&self, txid: Txid) -> bool { + self.canonical.contains_key(&txid) || self.not_canonical.contains(&txid) + } + + /// Mark transaction as canonical if it is anchored in the best chain. + fn scan_anchors( + &mut self, + txid: Txid, + tx: Arc, + anchors: &BTreeSet, + ) -> Result<(), C::Error> { + for anchor in anchors { + let in_chain_opt = self + .chain + .is_block_in_chain(anchor.anchor_block(), self.chain_tip)?; + if in_chain_opt == Some(true) { + self.mark_canonical(tx, CanonicalReason::from_anchor(anchor.clone())); + return Ok(()); + } + } + // cannot determine + self.pending_remaining.push_back(( + txid, + tx, + anchors + .iter() + .last() + .unwrap() + .confirmation_height_upper_bound(), + )); + Ok(()) + } + + /// Marks a transaction and it's ancestors as canoncial. Mark all conflicts of these as + /// `not_canonical`. + fn mark_canonical(&mut self, tx: Arc, reason: CanonicalReason) { + let starting_txid = tx.compute_txid(); + let mut is_root = true; + TxAncestors::new_include_root( + self.tx_graph, + tx, + |_: usize, tx: Arc| -> Option<()> { + let this_txid = tx.compute_txid(); + let this_reason = if is_root { + is_root = false; + reason.clone() + } else { + reason.to_transitive(starting_txid) + }; + let canonical_entry = match self.canonical.entry(this_txid) { + // Already visited tx before, exit early. + hash_map::Entry::Occupied(_) => return None, + hash_map::Entry::Vacant(entry) => entry, + }; + // Any conflicts with a canonical tx can be added to `not_canonical`. Descendants + // of `not_canonical` txs can also be added to `not_canonical`. + for (_, conflict_txid) in self.tx_graph.direct_conflicts(&tx) { + TxDescendants::new_include_root( + self.tx_graph, + conflict_txid, + |_: usize, txid: Txid| -> Option<()> { + if self.not_canonical.insert(txid) { + Some(()) + } else { + None + } + }, + ) + .run_until_finished() + } + canonical_entry.insert((tx, this_reason)); + self.queue.push_back(this_txid); + Some(()) + }, + ) + .for_each(|_| {}) + } +} + +impl<'g, A: Anchor, C: ChainOracle> Iterator for CanonicalIter<'g, A, C> { + type Item = Result<(Txid, Arc, CanonicalReason), C::Error>; + + fn next(&mut self) -> Option { + loop { + if let Some(txid) = self.queue.pop_front() { + let (tx, reason) = self + .canonical + .get(&txid) + .cloned() + .expect("reason must exist"); + return Some(Ok((txid, tx, reason))); + } + + if let Some((txid, tx, anchors)) = self.pending_anchored.next() { + if !self.is_canonicalized(txid) { + if let Err(err) = self.scan_anchors(txid, tx, anchors) { + return Some(Err(err)); + } + } + continue; + } + + if let Some((txid, tx, last_seen)) = self.pending_last_seen.next() { + if !self.is_canonicalized(txid) { + let lsi = LastSeenIn::Mempool(last_seen); + self.mark_canonical(tx, CanonicalReason::from_last_seen(lsi)); + } + continue; + } + + if let Some((txid, tx, height)) = self.pending_remaining.pop_front() { + if !self.is_canonicalized(txid) { + let lsi = LastSeenIn::Block(height); + self.mark_canonical(tx, CanonicalReason::from_last_seen(lsi)); + } + continue; + } + + return None; + } + } +} + +/// Represents when and where a given transaction is last seen. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, core::hash::Hash)] +#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))] +pub enum LastSeenIn { + /// The transaction was last seen in a block of height. + Block(u32), + /// The transaction was last seen in the mempool at the given unix timestamp. + Mempool(u64), +} + +/// The reason why a transaction is canonical. +#[derive(Debug, Clone, PartialEq, Eq)] +pub enum CanonicalReason { + /// This transaction is anchored in the best chain by `A`, and therefore canonical. + Anchor { + /// The anchor that anchored the transaction in the chain. + anchor: A, + /// Whether the anchor is of the transaction's descendant. + descendant: Option, + }, + /// This transaction does not conflict with any other transaction with a more recent `last_seen` + /// value or one that is anchored in the best chain. + LastSeen { + /// The [`LastSeenIn`] value of the transaction. + last_seen: LastSeenIn, + /// Whether the [`LastSeenIn`] value is of the transaction's descendant. + descendant: Option, + }, +} + +impl CanonicalReason { + /// Constructs a [`CanonicalReason`] from an `anchor`. + pub fn from_anchor(anchor: A) -> Self { + Self::Anchor { + anchor, + descendant: None, + } + } + + /// Constructs a [`CanonicalReason`] from a `last_seen` value. + pub fn from_last_seen(last_seen: LastSeenIn) -> Self { + Self::LastSeen { + last_seen, + descendant: None, + } + } + + /// Contruct a new [`CanonicalReason`] from the original which is transitive to `descendant`. + /// + /// This signals that either the [`LastSeenIn`] or [`Anchor`] value belongs to the transaction's + /// descendant, but is transitively relevant. + pub fn to_transitive(&self, descendant: Txid) -> Self { + match self { + CanonicalReason::Anchor { anchor, .. } => Self::Anchor { + anchor: anchor.clone(), + descendant: Some(descendant), + }, + CanonicalReason::LastSeen { last_seen, .. } => Self::LastSeen { + last_seen: *last_seen, + descendant: Some(descendant), + }, + } + } + + /// This signals that either the [`LastSeenIn`] or [`Anchor`] value belongs to the transaction's + /// descendant. + pub fn descendant(&self) -> &Option { + match self { + CanonicalReason::Anchor { descendant, .. } => descendant, + CanonicalReason::LastSeen { descendant, .. } => descendant, + } + } +} diff --git a/crates/chain/src/lib.rs b/crates/chain/src/lib.rs index 557d5349..92a6d5c4 100644 --- a/crates/chain/src/lib.rs +++ b/crates/chain/src/lib.rs @@ -43,6 +43,8 @@ pub mod tx_graph; pub use tx_graph::TxGraph; mod chain_oracle; pub use chain_oracle::*; +mod canonical_iter; +pub use canonical_iter::*; #[doc(hidden)] pub mod example_utils; diff --git a/crates/chain/src/tx_graph.rs b/crates/chain/src/tx_graph.rs index f00ab9a8..0e7dd33f 100644 --- a/crates/chain/src/tx_graph.rs +++ b/crates/chain/src/tx_graph.rs @@ -94,10 +94,14 @@ use crate::collections::*; use crate::BlockId; +use crate::CanonicalIter; +use crate::CanonicalReason; +use crate::LastSeenIn; use crate::{Anchor, Balance, ChainOracle, ChainPosition, FullTxOut, Merge}; use alloc::collections::vec_deque::VecDeque; use alloc::sync::Arc; use alloc::vec::Vec; +use bdk_core::ConfirmationBlockTime; pub use bdk_core::TxUpdate; use bitcoin::{Amount, OutPoint, ScriptBuf, SignedAmount, Transaction, TxOut, Txid}; use core::fmt::{self, Formatter}; @@ -124,7 +128,7 @@ impl From> for TxUpdate { } } -impl From> for TxGraph { +impl From> for TxGraph { fn from(update: TxUpdate) -> Self { let mut graph = TxGraph::::default(); let _ = graph.apply_update_at(update, None); @@ -138,12 +142,15 @@ impl From> for TxGraph { /// /// [module-level documentation]: crate::tx_graph #[derive(Clone, Debug, PartialEq)] -pub struct TxGraph { +pub struct TxGraph { txs: HashMap, spends: BTreeMap>, anchors: HashMap>, last_seen: HashMap, + txs_by_highest_conf_heights: BTreeSet<(u32, Txid)>, + txs_by_last_seen: BTreeSet<(u64, Txid)>, + // The following fields exist so that methods can return references to empty sets. // FIXME: This can be removed once `HashSet::new` and `BTreeSet::new` are const fns. empty_outspends: HashSet, @@ -157,6 +164,8 @@ impl Default for TxGraph { spends: Default::default(), anchors: Default::default(), last_seen: Default::default(), + txs_by_highest_conf_heights: Default::default(), + txs_by_last_seen: Default::default(), empty_outspends: Default::default(), empty_anchors: Default::default(), } @@ -204,7 +213,7 @@ impl Default for TxNodeInternal { #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)] pub struct CanonicalTx<'a, T, A> { /// How the transaction is observed as (confirmed or unconfirmed). - pub chain_position: ChainPosition<&'a A>, + pub chain_position: ChainPosition, /// The transaction node (as part of the graph). pub tx_node: TxNode<'a, T, A>, } @@ -509,12 +518,12 @@ impl TxGraph { } } -impl TxGraph { +impl TxGraph { /// Transform the [`TxGraph`] to have [`Anchor`]s of another type. /// /// This takes in a closure of signature `FnMut(A) -> A2` which is called for each [`Anchor`] to /// transform it. - pub fn map_anchors(self, f: F) -> TxGraph + pub fn map_anchors(self, f: F) -> TxGraph where F: FnMut(A) -> A2, { @@ -627,8 +636,36 @@ impl TxGraph { /// The [`ChangeSet`] returned will be empty if graph already knows that `txid` exists in /// `anchor`. pub fn insert_anchor(&mut self, txid: Txid, anchor: A) -> ChangeSet { + let mut old_top_h = None; + let mut new_top_h = anchor.confirmation_height_upper_bound(); + + let is_changed = match self.anchors.entry(txid) { + hash_map::Entry::Occupied(mut e) => { + fn top_anchor_height(anchors: &BTreeSet) -> Option { + anchors + .iter() + .last() + .map(Anchor::confirmation_height_upper_bound) + } + old_top_h = top_anchor_height(e.get()); + let is_changed = e.get_mut().insert(anchor.clone()); + new_top_h = top_anchor_height(e.get()).expect("must have anchor"); + is_changed + } + hash_map::Entry::Vacant(e) => { + e.insert(core::iter::once(anchor.clone()).collect()); + true + } + }; + let mut changeset = ChangeSet::::default(); - if self.anchors.entry(txid).or_default().insert(anchor.clone()) { + if is_changed { + if old_top_h != Some(new_top_h) { + if let Some(prev_top_h) = old_top_h { + self.txs_by_highest_conf_heights.remove(&(prev_top_h, txid)); + } + self.txs_by_highest_conf_heights.insert((new_top_h, txid)); + } changeset.anchors.insert((anchor, txid)); } changeset @@ -638,10 +675,29 @@ impl TxGraph { /// /// Note that [`TxGraph`] only keeps track of the latest `seen_at`. pub fn insert_seen_at(&mut self, txid: Txid, seen_at: u64) -> ChangeSet { + let mut old_last_seen = None; + let is_changed = match self.last_seen.entry(txid) { + hash_map::Entry::Occupied(mut e) => { + let last_seen = e.get_mut(); + old_last_seen = Some(*last_seen); + let change = *last_seen < seen_at; + if change { + *last_seen = seen_at; + } + change + } + hash_map::Entry::Vacant(e) => { + e.insert(seen_at); + true + } + }; + let mut changeset = ChangeSet::::default(); - let last_seen = self.last_seen.entry(txid).or_default(); - if seen_at > *last_seen { - *last_seen = seen_at; + if is_changed { + if let Some(old_last_seen) = old_last_seen { + self.txs_by_last_seen.remove(&(old_last_seen, txid)); + } + self.txs_by_last_seen.insert((seen_at, txid)); changeset.last_seen.insert(txid, seen_at); } changeset @@ -971,15 +1027,51 @@ impl TxGraph { chain: &'a C, chain_tip: BlockId, ) -> impl Iterator, A>, C::Error>> { - self.full_txs().filter_map(move |tx| { - self.try_get_chain_position(chain, chain_tip, tx.txid) - .map(|v| { - v.map(|observed_in| CanonicalTx { - chain_position: observed_in, - tx_node: tx, - }) + self.canonical_iter(chain, chain_tip).flat_map(move |res| { + res.map(|(txid, _, canonical_reason)| { + let tx_node = self.get_tx_node(txid).expect("must contain tx"); + let chain_position = match canonical_reason { + CanonicalReason::Anchor { anchor, descendant } => match descendant { + Some(_) => { + let direct_anchor = tx_node + .anchors + .iter() + .find_map(|a| -> Option> { + match chain.is_block_in_chain(a.anchor_block(), chain_tip) { + Ok(Some(true)) => Some(Ok(a.clone())), + Ok(Some(false)) | Ok(None) => None, + Err(err) => Some(Err(err)), + } + }) + .transpose()?; + match direct_anchor { + Some(anchor) => ChainPosition::Confirmed { + anchor, + transitively: None, + }, + None => ChainPosition::Confirmed { + anchor, + transitively: descendant, + }, + } + } + None => ChainPosition::Confirmed { + anchor, + transitively: None, + }, + }, + CanonicalReason::LastSeen { last_seen, .. } => match last_seen { + LastSeenIn::Mempool(last_seen) => ChainPosition::Unconfirmed { + last_seen: Some(last_seen), + }, + LastSeenIn::Block(_) => ChainPosition::Unconfirmed { last_seen: None }, + }, + }; + Ok(CanonicalTx { + chain_position, + tx_node, }) - .transpose() + }) }) } @@ -994,7 +1086,7 @@ impl TxGraph { chain_tip: BlockId, ) -> impl Iterator, A>> { self.try_list_canonical_txs(chain, chain_tip) - .map(|r| r.expect("oracle is infallible")) + .map(|res| res.expect("infallible")) } /// Get a filtered list of outputs from the given `outpoints` that are in `chain` with @@ -1021,44 +1113,80 @@ impl TxGraph { chain: &'a C, chain_tip: BlockId, outpoints: impl IntoIterator + 'a, - ) -> impl Iterator), C::Error>> + 'a { - outpoints - .into_iter() - .map( - move |(spk_i, op)| -> Result)>, C::Error> { - let tx_node = match self.get_tx_node(op.txid) { - Some(n) => n, - None => return Ok(None), - }; - - let txout = match tx_node.tx.as_ref().output.get(op.vout as usize) { - Some(txout) => txout.clone(), - None => return Ok(None), - }; - - let chain_position = - match self.try_get_chain_position(chain, chain_tip, op.txid)? { - Some(pos) => pos.cloned(), - None => return Ok(None), - }; - - let spent_by = self - .try_get_chain_spend(chain, chain_tip, op)? - .map(|(a, txid)| (a.cloned(), txid)); - - Ok(Some(( - spk_i, - FullTxOut { - outpoint: op, - txout, - chain_position, - spent_by, - is_on_coinbase: tx_node.tx.is_coinbase(), - }, - ))) + ) -> Result)> + 'a, C::Error> { + let mut canon_txs = HashMap::, A>>::new(); + let mut canon_spends = HashMap::::new(); + for r in self.try_list_canonical_txs(chain, chain_tip) { + let canonical_tx = r?; + let txid = canonical_tx.tx_node.txid; + + if !canonical_tx.tx_node.tx.is_coinbase() { + for txin in &canonical_tx.tx_node.tx.input { + let _res = canon_spends.insert(txin.previous_output, txid); + assert!( + _res.is_none(), + "tried to replace {:?} with {:?}", + _res, + txid + ); + } + } + canon_txs.insert(txid, canonical_tx); + } + Ok(outpoints.into_iter().filter_map(move |(spk_i, outpoint)| { + let canon_tx = canon_txs.get(&outpoint.txid)?; + let txout = canon_tx + .tx_node + .tx + .output + .get(outpoint.vout as usize) + .cloned()?; + let chain_position = canon_tx.chain_position.clone(); + let spent_by = canon_spends.get(&outpoint).map(|spend_txid| { + let spend_tx = canon_txs + .get(spend_txid) + .cloned() + .expect("must be canonical"); + (spend_tx.chain_position, *spend_txid) + }); + let is_on_coinbase = canon_tx.tx_node.is_coinbase(); + Some(( + spk_i, + FullTxOut { + outpoint, + txout, + chain_position, + spent_by, + is_on_coinbase, }, - ) - .filter_map(Result::transpose) + )) + })) + } + + /// List txids by descending anchor height order. + /// + /// If multiple anchors exist for a txid, the highest anchor height will be used. Transactions + /// without anchors are excluded. + pub fn txids_by_descending_anchor_height( + &self, + ) -> impl ExactSizeIterator + '_ { + self.txs_by_highest_conf_heights.iter().copied().rev() + } + + /// List txids by descending last-seen order. + /// + /// Transactions without last-seens are excluded. + pub fn txids_by_descending_last_seen(&self) -> impl ExactSizeIterator + '_ { + self.txs_by_last_seen.iter().copied().rev() + } + + /// Returns a [`CanonicalIter`]. + pub fn canonical_iter<'a, C: ChainOracle>( + &'a self, + chain: &'a C, + chain_tip: BlockId, + ) -> CanonicalIter<'a, A, C> { + CanonicalIter::new(self, chain, chain_tip) } /// Get a filtered list of outputs from the given `outpoints` that are in `chain` with @@ -1074,7 +1202,7 @@ impl TxGraph { outpoints: impl IntoIterator + 'a, ) -> impl Iterator)> + 'a { self.try_filter_chain_txouts(chain, chain_tip, outpoints) - .map(|r| r.expect("oracle is infallible")) + .expect("oracle is infallible") } /// Get a filtered list of unspent outputs (UTXOs) from the given `outpoints` that are in @@ -1100,14 +1228,10 @@ impl TxGraph { chain: &'a C, chain_tip: BlockId, outpoints: impl IntoIterator + 'a, - ) -> impl Iterator), C::Error>> + 'a { - self.try_filter_chain_txouts(chain, chain_tip, outpoints) - .filter(|r| match r { - // keep unspents, drop spents - Ok((_, full_txo)) => full_txo.spent_by.is_none(), - // keep errors - Err(_) => true, - }) + ) -> Result)> + 'a, C::Error> { + Ok(self + .try_filter_chain_txouts(chain, chain_tip, outpoints)? + .filter(|(_, full_txo)| full_txo.spent_by.is_none())) } /// Get a filtered list of unspent outputs (UTXOs) from the given `outpoints` that are in @@ -1123,7 +1247,7 @@ impl TxGraph { txouts: impl IntoIterator + 'a, ) -> impl Iterator)> + 'a { self.try_filter_chain_unspents(chain, chain_tip, txouts) - .map(|r| r.expect("oracle is infallible")) + .expect("oracle is infallible") } /// Get the total balance of `outpoints` that are in `chain` of `chain_tip`. @@ -1150,9 +1274,7 @@ impl TxGraph { let mut untrusted_pending = Amount::ZERO; let mut confirmed = Amount::ZERO; - for res in self.try_filter_chain_unspents(chain, chain_tip, outpoints) { - let (spk_i, txout) = res?; - + for (spk_i, txout) in self.try_filter_chain_unspents(chain, chain_tip, outpoints)? { match &txout.chain_position { ChainPosition::Confirmed { .. } => { if txout.is_confirmed_and_spendable(chain_tip.height) { diff --git a/crates/chain/tests/common/tx_template.rs b/crates/chain/tests/common/tx_template.rs index 6ece64cb..0b0e2fd9 100644 --- a/crates/chain/tests/common/tx_template.rs +++ b/crates/chain/tests/common/tx_template.rs @@ -132,7 +132,9 @@ pub fn init_graph<'a, A: Anchor + Clone + 'a>( for anchor in tx_tmp.anchors.iter() { let _ = graph.insert_anchor(tx.compute_txid(), anchor.clone()); } - let _ = graph.insert_seen_at(tx.compute_txid(), tx_tmp.last_seen.unwrap_or(0)); + if let Some(last_seen) = tx_tmp.last_seen { + let _ = graph.insert_seen_at(tx.compute_txid(), last_seen); + } } (graph, spk_index, tx_ids) } diff --git a/crates/chain/tests/test_indexed_tx_graph.rs b/crates/chain/tests/test_indexed_tx_graph.rs index 1b3dff57..e37a639c 100644 --- a/crates/chain/tests/test_indexed_tx_graph.rs +++ b/crates/chain/tests/test_indexed_tx_graph.rs @@ -191,7 +191,7 @@ fn test_list_owned_txouts() { value: Amount::from_sat(70000), script_pubkey: trusted_spks[0].to_owned(), }], - ..new_tx(0) + ..new_tx(1) }; // tx2 is an incoming transaction received at untrusted keychain at block 1. @@ -200,7 +200,7 @@ fn test_list_owned_txouts() { value: Amount::from_sat(30000), script_pubkey: untrusted_spks[0].to_owned(), }], - ..new_tx(0) + ..new_tx(2) }; // tx3 spends tx2 and gives a change back in trusted keychain. Confirmed at Block 2. @@ -213,7 +213,7 @@ fn test_list_owned_txouts() { value: Amount::from_sat(10000), script_pubkey: trusted_spks[1].to_owned(), }], - ..new_tx(0) + ..new_tx(3) }; // tx4 is an external transaction receiving at untrusted keychain, unconfirmed. @@ -222,7 +222,7 @@ fn test_list_owned_txouts() { value: Amount::from_sat(20000), script_pubkey: untrusted_spks[1].to_owned(), }], - ..new_tx(0) + ..new_tx(4) }; // tx5 is an external transaction receiving at trusted keychain, unconfirmed. @@ -231,11 +231,12 @@ fn test_list_owned_txouts() { value: Amount::from_sat(15000), script_pubkey: trusted_spks[2].to_owned(), }], - ..new_tx(0) + ..new_tx(5) }; // tx6 is an unrelated transaction confirmed at 3. - let tx6 = new_tx(0); + // This won't be inserted because it is not relevant. + let tx6 = new_tx(6); // Insert transactions into graph with respective anchors // Insert unconfirmed txs with a last_seen timestamp @@ -293,7 +294,7 @@ fn test_list_owned_txouts() { let confirmed_txouts_txid = txouts .iter() .filter_map(|(_, full_txout)| { - if matches!(full_txout.chain_position, ChainPosition::Confirmed { .. }) { + if full_txout.chain_position.is_confirmed() { Some(full_txout.outpoint.txid) } else { None @@ -304,7 +305,7 @@ fn test_list_owned_txouts() { let unconfirmed_txouts_txid = txouts .iter() .filter_map(|(_, full_txout)| { - if matches!(full_txout.chain_position, ChainPosition::Unconfirmed { .. }) { + if !full_txout.chain_position.is_confirmed() { Some(full_txout.outpoint.txid) } else { None @@ -315,7 +316,7 @@ fn test_list_owned_txouts() { let confirmed_utxos_txid = utxos .iter() .filter_map(|(_, full_txout)| { - if matches!(full_txout.chain_position, ChainPosition::Confirmed { .. }) { + if full_txout.chain_position.is_confirmed() { Some(full_txout.outpoint.txid) } else { None @@ -326,7 +327,7 @@ fn test_list_owned_txouts() { let unconfirmed_utxos_txid = utxos .iter() .filter_map(|(_, full_txout)| { - if matches!(full_txout.chain_position, ChainPosition::Unconfirmed { .. }) { + if !full_txout.chain_position.is_confirmed() { Some(full_txout.outpoint.txid) } else { None @@ -360,20 +361,26 @@ fn test_list_owned_txouts() { assert_eq!(confirmed_txouts_txid, [tx1.compute_txid()].into()); assert_eq!( unconfirmed_txouts_txid, - [tx4.compute_txid(), tx5.compute_txid()].into() + [ + tx2.compute_txid(), + tx3.compute_txid(), + tx4.compute_txid(), + tx5.compute_txid() + ] + .into() ); assert_eq!(confirmed_utxos_txid, [tx1.compute_txid()].into()); assert_eq!( unconfirmed_utxos_txid, - [tx4.compute_txid(), tx5.compute_txid()].into() + [tx3.compute_txid(), tx4.compute_txid(), tx5.compute_txid()].into() ); assert_eq!( balance, Balance { immature: Amount::from_sat(70000), // immature coinbase - trusted_pending: Amount::from_sat(15000), // tx5 + trusted_pending: Amount::from_sat(25000), // tx3, tx5 untrusted_pending: Amount::from_sat(20000), // tx4 confirmed: Amount::ZERO // Nothing is confirmed yet } @@ -397,26 +404,23 @@ fn test_list_owned_txouts() { ); assert_eq!( unconfirmed_txouts_txid, - [tx4.compute_txid(), tx5.compute_txid()].into() + [tx3.compute_txid(), tx4.compute_txid(), tx5.compute_txid()].into() ); // tx2 gets into confirmed utxos set - assert_eq!( - confirmed_utxos_txid, - [tx1.compute_txid(), tx2.compute_txid()].into() - ); + assert_eq!(confirmed_utxos_txid, [tx1.compute_txid()].into()); assert_eq!( unconfirmed_utxos_txid, - [tx4.compute_txid(), tx5.compute_txid()].into() + [tx3.compute_txid(), tx4.compute_txid(), tx5.compute_txid()].into() ); assert_eq!( balance, Balance { immature: Amount::from_sat(70000), // immature coinbase - trusted_pending: Amount::from_sat(15000), // tx5 + trusted_pending: Amount::from_sat(25000), // tx3, tx5 untrusted_pending: Amount::from_sat(20000), // tx4 - confirmed: Amount::from_sat(30_000) // tx2 got confirmed + confirmed: Amount::from_sat(0) // tx2 got confirmed (but spent by 3) } ); } @@ -534,6 +538,7 @@ fn test_get_chain_position() { use bdk_chain::spk_txout::SpkTxOutIndex; use bdk_chain::BlockId; + #[derive(Debug)] struct TestCase { name: &'static str, tx: Transaction, diff --git a/crates/chain/tests/test_tx_graph.rs b/crates/chain/tests/test_tx_graph.rs index 8aff2d40..8f1634ba 100644 --- a/crates/chain/tests/test_tx_graph.rs +++ b/crates/chain/tests/test_tx_graph.rs @@ -185,7 +185,7 @@ fn insert_tx_graph_doesnt_count_coinbase_as_spent() { output: vec![], }; - let mut graph = TxGraph::<()>::default(); + let mut graph = TxGraph::::default(); let changeset = graph.insert_tx(tx); assert!(!changeset.is_empty()); assert!(graph.outspends(OutPoint::null()).is_empty()); @@ -216,8 +216,8 @@ fn insert_tx_graph_keeps_track_of_spend() { output: vec![], }; - let mut graph1 = TxGraph::<()>::default(); - let mut graph2 = TxGraph::<()>::default(); + let mut graph1 = TxGraph::::default(); + let mut graph2 = TxGraph::::default(); // insert in different order let _ = graph1.insert_tx(tx1.clone()); @@ -245,7 +245,7 @@ fn insert_tx_can_retrieve_full_tx_from_graph() { output: vec![TxOut::NULL], }; - let mut graph = TxGraph::<()>::default(); + let mut graph = TxGraph::::default(); let _ = graph.insert_tx(tx.clone()); assert_eq!( graph @@ -257,7 +257,7 @@ fn insert_tx_can_retrieve_full_tx_from_graph() { #[test] fn insert_tx_displaces_txouts() { - let mut tx_graph = TxGraph::<()>::default(); + let mut tx_graph = TxGraph::::default(); let tx = Transaction { version: transaction::Version::ONE, @@ -284,7 +284,7 @@ fn insert_tx_displaces_txouts() { #[test] fn insert_txout_does_not_displace_tx() { - let mut tx_graph = TxGraph::<()>::default(); + let mut tx_graph = TxGraph::::default(); let tx = Transaction { version: transaction::Version::ONE, lock_time: absolute::LockTime::ZERO, @@ -340,7 +340,7 @@ fn insert_txout_does_not_displace_tx() { #[test] fn test_calculate_fee() { - let mut graph = TxGraph::<()>::default(); + let mut graph = TxGraph::::default(); let intx1 = Transaction { version: transaction::Version::ONE, lock_time: absolute::LockTime::ZERO, @@ -694,7 +694,7 @@ fn test_conflicting_descendants() { let txid_a = tx_a.compute_txid(); let txid_b = tx_b.compute_txid(); - let mut graph = TxGraph::<()>::default(); + let mut graph = TxGraph::::default(); let _ = graph.insert_tx(tx_a); let _ = graph.insert_tx(tx_b); @@ -770,7 +770,7 @@ fn test_descendants_no_repeat() { }) .collect::>(); - let mut graph = TxGraph::<()>::default(); + let mut graph = TxGraph::::default(); let mut expected_txids = Vec::new(); // these are NOT descendants of `tx_a` @@ -1112,6 +1112,12 @@ fn call_map_anchors_with_non_deterministic_anchor() { pub non_deterministic_field: u32, } + impl Anchor for NonDeterministicAnchor { + fn anchor_block(&self) -> BlockId { + self.anchor_block + } + } + let template = [ TxTemplate { tx_name: "tx1", diff --git a/crates/chain/tests/test_tx_graph_conflicts.rs b/crates/chain/tests/test_tx_graph_conflicts.rs index 1f54c4b8..2e64e391 100644 --- a/crates/chain/tests/test_tx_graph_conflicts.rs +++ b/crates/chain/tests/test_tx_graph_conflicts.rs @@ -413,12 +413,13 @@ fn test_tx_conflict_handling() { inputs: &[TxInTemplate::Bogus], outputs: &[TxOutTemplate::new(10000, Some(0))], anchors: &[block_id!(1, "B")], - last_seen: None, + ..Default::default() }, TxTemplate { tx_name: "B", inputs: &[TxInTemplate::PrevTx("A", 0)], outputs: &[TxOutTemplate::new(20000, Some(1))], + last_seen: Some(2), ..Default::default() }, TxTemplate { @@ -432,6 +433,7 @@ fn test_tx_conflict_handling() { tx_name: "C", inputs: &[TxInTemplate::PrevTx("B'", 0)], outputs: &[TxOutTemplate::new(30000, Some(3))], + last_seen: Some(1), ..Default::default() }, ], diff --git a/crates/wallet/src/test_utils.rs b/crates/wallet/src/test_utils.rs index c69de620..7ad93e0c 100644 --- a/crates/wallet/src/test_utils.rs +++ b/crates/wallet/src/test_utils.rs @@ -4,7 +4,7 @@ use alloc::string::ToString; use alloc::sync::Arc; use core::str::FromStr; -use bdk_chain::{tx_graph, BlockId, ChainPosition, ConfirmationBlockTime}; +use bdk_chain::{tx_graph, BlockId, ConfirmationBlockTime}; use bitcoin::{ absolute, hashes::Hash, transaction, Address, Amount, BlockHash, FeeRate, Network, OutPoint, Transaction, TxIn, TxOut, Txid, @@ -224,32 +224,43 @@ pub fn feerate_unchecked(sat_vb: f64) -> FeeRate { FeeRate::from_sat_per_kwu(sat_kwu) } +/// Input parameter for [`receive_output`]. +pub enum ReceiveTo { + /// Receive tx to mempool at this `last_seen` timestamp. + Mempool(u64), + /// Receive tx to block with this anchor. + Block(ConfirmationBlockTime), +} + +impl From for ReceiveTo { + fn from(value: ConfirmationBlockTime) -> Self { + Self::Block(value) + } +} + /// Receive a tx output with the given value in the latest block pub fn receive_output_in_latest_block(wallet: &mut Wallet, value: u64) -> OutPoint { let latest_cp = wallet.latest_checkpoint(); let height = latest_cp.height(); - let anchor = if height == 0 { - ChainPosition::Unconfirmed { last_seen: Some(0) } - } else { - ChainPosition::Confirmed { - anchor: ConfirmationBlockTime { - block_id: latest_cp.block_id(), - confirmation_time: 0, - }, - transitively: None, - } - }; - receive_output(wallet, value, anchor) + assert!(height > 0, "cannot receive tx into genesis block"); + receive_output( + wallet, + value, + ConfirmationBlockTime { + block_id: latest_cp.block_id(), + confirmation_time: 0, + }, + ) } /// Receive a tx output with the given value and chain position pub fn receive_output( wallet: &mut Wallet, value: u64, - pos: ChainPosition, + receive_to: impl Into, ) -> OutPoint { let addr = wallet.next_unused_address(KeychainKind::External).address; - receive_output_to_address(wallet, addr, value, pos) + receive_output_to_address(wallet, addr, value, receive_to) } /// Receive a tx output to an address with the given value and chain position @@ -257,7 +268,7 @@ pub fn receive_output_to_address( wallet: &mut Wallet, addr: Address, value: u64, - pos: ChainPosition, + receive_to: impl Into, ) -> OutPoint { let tx = Transaction { version: transaction::Version::ONE, @@ -272,15 +283,9 @@ pub fn receive_output_to_address( let txid = tx.compute_txid(); insert_tx(wallet, tx); - match pos { - ChainPosition::Confirmed { anchor, .. } => { - insert_anchor(wallet, txid, anchor); - } - ChainPosition::Unconfirmed { last_seen } => { - if let Some(last_seen) = last_seen { - insert_seen_at(wallet, txid, last_seen); - } - } + match receive_to.into() { + ReceiveTo::Block(anchor) => insert_anchor(wallet, txid, anchor), + ReceiveTo::Mempool(last_seen) => insert_seen_at(wallet, txid, last_seen), } OutPoint { txid, vout: 0 } diff --git a/crates/wallet/src/wallet/mod.rs b/crates/wallet/src/wallet/mod.rs index e2e90502..9174ebab 100644 --- a/crates/wallet/src/wallet/mod.rs +++ b/crates/wallet/src/wallet/mod.rs @@ -1063,11 +1063,9 @@ impl Wallet { let graph = self.indexed_graph.graph(); Some(WalletTx { - chain_position: graph.get_chain_position( - &self.chain, - self.chain.tip().block_id(), - txid, - )?, + chain_position: graph + .get_chain_position(&self.chain, self.chain.tip().block_id(), txid)? + .cloned(), tx_node: graph.get_tx_node(txid)?, }) } diff --git a/crates/wallet/tests/wallet.rs b/crates/wallet/tests/wallet.rs index 4a53c350..4afb66e6 100644 --- a/crates/wallet/tests/wallet.rs +++ b/crates/wallet/tests/wallet.rs @@ -1223,7 +1223,7 @@ fn test_create_tx_add_utxo() { let txid = small_output_tx.compute_txid(); insert_tx(&mut wallet, small_output_tx); let anchor = ConfirmationBlockTime { - block_id: wallet.latest_checkpoint().block_id(), + block_id: wallet.latest_checkpoint().get(2000).unwrap().block_id(), confirmation_time: 200, }; insert_anchor(&mut wallet, txid, anchor); @@ -1270,7 +1270,7 @@ fn test_create_tx_manually_selected_insufficient() { let txid = small_output_tx.compute_txid(); insert_tx(&mut wallet, small_output_tx.clone()); let anchor = ConfirmationBlockTime { - block_id: wallet.latest_checkpoint().block_id(), + block_id: wallet.latest_checkpoint().get(2000).unwrap().block_id(), confirmation_time: 200, }; insert_anchor(&mut wallet, txid, anchor); @@ -1496,11 +1496,7 @@ fn test_create_tx_increment_change_index() { .create_wallet_no_persist() .unwrap(); // fund wallet - receive_output( - &mut wallet, - amount, - ChainPosition::Unconfirmed { last_seen: Some(0) }, - ); + receive_output(&mut wallet, amount, ReceiveTo::Mempool(0)); // create tx let mut builder = wallet.build_tx(); builder.add_recipient(recipient.clone(), Amount::from_sat(test.to_send)); @@ -2164,12 +2160,15 @@ fn test_bump_fee_remove_output_manually_selected_only() { }], }; + let position: ChainPosition = + wallet.transactions().last().unwrap().chain_position; insert_tx(&mut wallet, init_tx.clone()); - let anchor = ConfirmationBlockTime { - block_id: wallet.latest_checkpoint().block_id(), - confirmation_time: 200, - }; - insert_anchor(&mut wallet, init_tx.compute_txid(), anchor); + match position { + ChainPosition::Confirmed { anchor, .. } => { + insert_anchor(&mut wallet, init_tx.compute_txid(), anchor) + } + other => panic!("all wallet txs must be confirmed: {:?}", other), + } let outpoint = OutPoint { txid: init_tx.compute_txid(), @@ -2213,12 +2212,13 @@ fn test_bump_fee_add_input() { }], }; let txid = init_tx.compute_txid(); + let pos: ChainPosition = + wallet.transactions().last().unwrap().chain_position; insert_tx(&mut wallet, init_tx); - let anchor = ConfirmationBlockTime { - block_id: wallet.latest_checkpoint().block_id(), - confirmation_time: 200, - }; - insert_anchor(&mut wallet, txid, anchor); + match pos { + ChainPosition::Confirmed { anchor, .. } => insert_anchor(&mut wallet, txid, anchor), + other => panic!("all wallet txs must be confirmed: {:?}", other), + } let addr = Address::from_str("2N1Ffz3WaNzbeLFBb51xyFMHYSEUXcbiSoX") .unwrap() @@ -2605,11 +2605,7 @@ fn test_bump_fee_unconfirmed_inputs_only() { let psbt = builder.finish().unwrap(); // Now we receive one transaction with 0 confirmations. We won't be able to use that for // fee bumping, as it's still unconfirmed! - receive_output( - &mut wallet, - 25_000, - ChainPosition::Unconfirmed { last_seen: Some(0) }, - ); + receive_output(&mut wallet, 25_000, ReceiveTo::Mempool(0)); let mut tx = psbt.extract_tx().expect("failed to extract tx"); let txid = tx.compute_txid(); for txin in &mut tx.input { @@ -2634,11 +2630,7 @@ fn test_bump_fee_unconfirmed_input() { .assume_checked(); // We receive a tx with 0 confirmations, which will be used as an input // in the drain tx. - receive_output( - &mut wallet, - 25_000, - ChainPosition::Unconfirmed { last_seen: Some(0) }, - ); + receive_output(&mut wallet, 25_000, ReceiveTo::Mempool(0)); let mut builder = wallet.build_tx(); builder.drain_wallet().drain_to(addr.script_pubkey()); let psbt = builder.finish().unwrap(); @@ -3048,7 +3040,7 @@ fn test_next_unused_address() { assert_eq!(next_unused_addr.index, 0); // use the above address - receive_output_in_latest_block(&mut wallet, 25_000); + receive_output(&mut wallet, 25_000, ReceiveTo::Mempool(0)); assert_eq!( wallet @@ -4108,17 +4100,14 @@ fn test_keychains_with_overlapping_spks() { .last() .unwrap() .address; - let chain_position = ChainPosition::Confirmed { - anchor: ConfirmationBlockTime { - block_id: BlockId { - height: 2000, - hash: BlockHash::all_zeros(), - }, - confirmation_time: 0, + let anchor = ConfirmationBlockTime { + block_id: BlockId { + height: 2000, + hash: BlockHash::all_zeros(), }, - transitively: None, + confirmation_time: 0, }; - let _outpoint = receive_output_to_address(&mut wallet, addr, 8000, chain_position); + let _outpoint = receive_output_to_address(&mut wallet, addr, 8000, anchor); assert_eq!(wallet.balance().confirmed, Amount::from_sat(58000)); } @@ -4207,11 +4196,7 @@ fn single_descriptor_wallet_can_create_tx_and_receive_change() { .unwrap(); assert_eq!(wallet.keychains().count(), 1); let amt = Amount::from_sat(5_000); - receive_output( - &mut wallet, - 2 * amt.to_sat(), - ChainPosition::Unconfirmed { last_seen: Some(2) }, - ); + receive_output(&mut wallet, 2 * amt.to_sat(), ReceiveTo::Mempool(2)); // create spend tx that produces a change output let addr = Address::from_str("bcrt1qc6fweuf4xjvz4x3gx3t9e0fh4hvqyu2qw4wvxm") .unwrap() @@ -4237,11 +4222,7 @@ fn single_descriptor_wallet_can_create_tx_and_receive_change() { #[test] fn test_transactions_sort_by() { let (mut wallet, _txid) = get_funded_wallet_wpkh(); - receive_output( - &mut wallet, - 25_000, - ChainPosition::Unconfirmed { last_seen: Some(0) }, - ); + receive_output(&mut wallet, 25_000, ReceiveTo::Mempool(0)); // sort by chain position, unconfirmed then confirmed by descending block height let sorted_txs: Vec = diff --git a/example-crates/example_cli/src/lib.rs b/example-crates/example_cli/src/lib.rs index 6a97252f..8c17348b 100644 --- a/example-crates/example_cli/src/lib.rs +++ b/example-crates/example_cli/src/lib.rs @@ -421,12 +421,8 @@ pub fn planned_utxos( let outpoints = graph.index.outpoints(); graph .graph() - .try_filter_chain_unspents(chain, chain_tip, outpoints.iter().cloned()) - .filter_map(|r| -> Option> { - let (k, i, full_txo) = match r { - Err(err) => return Some(Err(err)), - Ok(((k, i), full_txo)) => (k, i, full_txo), - }; + .try_filter_chain_unspents(chain, chain_tip, outpoints.iter().cloned())? + .filter_map(|((k, i), full_txo)| -> Option> { let desc = graph .index .keychains() @@ -560,26 +556,18 @@ pub fn handle_commands( } => { let txouts = graph .graph() - .try_filter_chain_txouts(chain, chain_tip, outpoints.iter().cloned()) - .filter(|r| match r { - Ok((_, full_txo)) => match (spent, unspent) { - (true, false) => full_txo.spent_by.is_some(), - (false, true) => full_txo.spent_by.is_none(), - _ => true, - }, - // always keep errored items - Err(_) => true, + .try_filter_chain_txouts(chain, chain_tip, outpoints.iter().cloned())? + .filter(|(_, full_txo)| match (spent, unspent) { + (true, false) => full_txo.spent_by.is_some(), + (false, true) => full_txo.spent_by.is_none(), + _ => true, }) - .filter(|r| match r { - Ok((_, full_txo)) => match (confirmed, unconfirmed) { - (true, false) => full_txo.chain_position.is_confirmed(), - (false, true) => !full_txo.chain_position.is_confirmed(), - _ => true, - }, - // always keep errored items - Err(_) => true, + .filter(|(_, full_txo)| match (confirmed, unconfirmed) { + (true, false) => full_txo.chain_position.is_confirmed(), + (false, true) => !full_txo.chain_position.is_confirmed(), + _ => true, }) - .collect::, _>>()?; + .collect::>(); for (spk_i, full_txo) in txouts { let addr = Address::from_script(&full_txo.txout.script_pubkey, network)?; -- 2.49.0