bdk_chain/
canonical_iter.rs

1use crate::collections::{HashMap, HashSet, VecDeque};
2use crate::tx_graph::{TxAncestors, TxDescendants};
3use crate::{Anchor, ChainOracle, TxGraph};
4use alloc::boxed::Box;
5use alloc::collections::BTreeSet;
6use alloc::sync::Arc;
7use alloc::vec::Vec;
8use bdk_core::BlockId;
9use bitcoin::{Transaction, Txid};
10
11type CanonicalMap<A> = HashMap<Txid, (Arc<Transaction>, CanonicalReason<A>)>;
12type NotCanonicalSet = HashSet<Txid>;
13
14/// Modifies the canonicalization algorithm.
15#[derive(Debug, Default, Clone)]
16pub struct CanonicalizationParams {
17    /// Transactions that will supercede all other transactions.
18    ///
19    /// In case of conflicting transactions within `assume_canonical`, transactions that appear
20    /// later in the list (have higher index) have precedence.
21    pub assume_canonical: Vec<Txid>,
22}
23
24/// Iterates over canonical txs.
25pub struct CanonicalIter<'g, A, C> {
26    tx_graph: &'g TxGraph<A>,
27    chain: &'g C,
28    chain_tip: BlockId,
29
30    unprocessed_assumed_txs: Box<dyn Iterator<Item = (Txid, Arc<Transaction>)> + 'g>,
31    unprocessed_anchored_txs:
32        Box<dyn Iterator<Item = (Txid, Arc<Transaction>, &'g BTreeSet<A>)> + 'g>,
33    unprocessed_seen_txs: Box<dyn Iterator<Item = (Txid, Arc<Transaction>, u64)> + 'g>,
34    unprocessed_leftover_txs: VecDeque<(Txid, Arc<Transaction>, u32)>,
35
36    canonical: CanonicalMap<A>,
37    not_canonical: NotCanonicalSet,
38
39    queue: VecDeque<Txid>,
40}
41
42impl<'g, A: Anchor, C: ChainOracle> CanonicalIter<'g, A, C> {
43    /// Constructs [`CanonicalIter`].
44    pub fn new(
45        tx_graph: &'g TxGraph<A>,
46        chain: &'g C,
47        chain_tip: BlockId,
48        params: CanonicalizationParams,
49    ) -> Self {
50        let anchors = tx_graph.all_anchors();
51        let unprocessed_assumed_txs = Box::new(
52            params
53                .assume_canonical
54                .into_iter()
55                .rev()
56                .filter_map(|txid| Some((txid, tx_graph.get_tx(txid)?))),
57        );
58        let unprocessed_anchored_txs = Box::new(
59            tx_graph
60                .txids_by_descending_anchor_height()
61                .filter_map(|(_, txid)| Some((txid, tx_graph.get_tx(txid)?, anchors.get(&txid)?))),
62        );
63        let unprocessed_seen_txs = Box::new(
64            tx_graph
65                .txids_by_descending_last_seen()
66                .filter_map(|(last_seen, txid)| Some((txid, tx_graph.get_tx(txid)?, last_seen))),
67        );
68        Self {
69            tx_graph,
70            chain,
71            chain_tip,
72            unprocessed_assumed_txs,
73            unprocessed_anchored_txs,
74            unprocessed_seen_txs,
75            unprocessed_leftover_txs: VecDeque::new(),
76            canonical: HashMap::new(),
77            not_canonical: HashSet::new(),
78            queue: VecDeque::new(),
79        }
80    }
81
82    /// Whether this transaction is already canonicalized.
83    fn is_canonicalized(&self, txid: Txid) -> bool {
84        self.canonical.contains_key(&txid) || self.not_canonical.contains(&txid)
85    }
86
87    /// Mark transaction as canonical if it is anchored in the best chain.
88    fn scan_anchors(
89        &mut self,
90        txid: Txid,
91        tx: Arc<Transaction>,
92        anchors: &BTreeSet<A>,
93    ) -> Result<(), C::Error> {
94        for anchor in anchors {
95            let in_chain_opt = self
96                .chain
97                .is_block_in_chain(anchor.anchor_block(), self.chain_tip)?;
98            if in_chain_opt == Some(true) {
99                self.mark_canonical(txid, tx, CanonicalReason::from_anchor(anchor.clone()));
100                return Ok(());
101            }
102        }
103        // cannot determine
104        self.unprocessed_leftover_txs.push_back((
105            txid,
106            tx,
107            anchors
108                .iter()
109                .last()
110                .expect(
111                    "tx taken from `unprocessed_txs_with_anchors` so it must atleast have an anchor",
112                )
113                .confirmation_height_upper_bound(),
114        ));
115        Ok(())
116    }
117
118    /// Marks `tx` and it's ancestors as canonical and mark all conflicts of these as
119    /// `not_canonical`.
120    ///
121    /// The exception is when it is discovered that `tx` double spends itself (i.e. two of it's
122    /// inputs conflict with each other), then no changes will be made.
123    ///
124    /// The logic works by having two loops where one is nested in another.
125    /// * The outer loop iterates through ancestors of `tx` (including `tx`). We can transitively
126    ///   assume that all ancestors of `tx` are also canonical.
127    /// * The inner loop loops through conflicts of ancestors of `tx`. Any descendants of conflicts
128    ///   are also conflicts and are transitively considered non-canonical.
129    ///
130    /// If the inner loop ends up marking `tx` as non-canonical, then we know that it double spends
131    /// itself.
132    fn mark_canonical(&mut self, txid: Txid, tx: Arc<Transaction>, reason: CanonicalReason<A>) {
133        let starting_txid = txid;
134        let mut is_starting_tx = true;
135
136        // We keep track of changes made so far so that we can undo it later in case we detect that
137        // `tx` double spends itself.
138        let mut detected_self_double_spend = false;
139        let mut undo_not_canonical = Vec::<Txid>::new();
140
141        // `staged_queue` doubles as the `undo_canonical` data.
142        let staged_queue = TxAncestors::new_include_root(
143            self.tx_graph,
144            tx,
145            |_: usize, tx: Arc<Transaction>| -> Option<Txid> {
146                let this_txid = tx.compute_txid();
147                let this_reason = if is_starting_tx {
148                    is_starting_tx = false;
149                    reason.clone()
150                } else {
151                    reason.to_transitive(starting_txid)
152                };
153
154                use crate::collections::hash_map::Entry;
155                let canonical_entry = match self.canonical.entry(this_txid) {
156                    // Already visited tx before, exit early.
157                    Entry::Occupied(_) => return None,
158                    Entry::Vacant(entry) => entry,
159                };
160
161                // Any conflicts with a canonical tx can be added to `not_canonical`. Descendants
162                // of `not_canonical` txs can also be added to `not_canonical`.
163                for (_, conflict_txid) in self.tx_graph.direct_conflicts(&tx) {
164                    TxDescendants::new_include_root(
165                        self.tx_graph,
166                        conflict_txid,
167                        |_: usize, txid: Txid| -> Option<()> {
168                            if self.not_canonical.insert(txid) {
169                                undo_not_canonical.push(txid);
170                                Some(())
171                            } else {
172                                None
173                            }
174                        },
175                    )
176                    .run_until_finished()
177                }
178
179                if self.not_canonical.contains(&this_txid) {
180                    // Early exit if self-double-spend is detected.
181                    detected_self_double_spend = true;
182                    return None;
183                }
184                canonical_entry.insert((tx, this_reason));
185                Some(this_txid)
186            },
187        )
188        .collect::<Vec<Txid>>();
189
190        if detected_self_double_spend {
191            for txid in staged_queue {
192                self.canonical.remove(&txid);
193            }
194            for txid in undo_not_canonical {
195                self.not_canonical.remove(&txid);
196            }
197        } else {
198            self.queue.extend(staged_queue);
199        }
200    }
201}
202
203impl<A: Anchor, C: ChainOracle> Iterator for CanonicalIter<'_, A, C> {
204    type Item = Result<(Txid, Arc<Transaction>, CanonicalReason<A>), C::Error>;
205
206    fn next(&mut self) -> Option<Self::Item> {
207        loop {
208            if let Some(txid) = self.queue.pop_front() {
209                let (tx, reason) = self
210                    .canonical
211                    .get(&txid)
212                    .cloned()
213                    .expect("reason must exist");
214                return Some(Ok((txid, tx, reason)));
215            }
216
217            if let Some((txid, tx)) = self.unprocessed_assumed_txs.next() {
218                if !self.is_canonicalized(txid) {
219                    self.mark_canonical(txid, tx, CanonicalReason::assumed());
220                }
221            }
222
223            if let Some((txid, tx, anchors)) = self.unprocessed_anchored_txs.next() {
224                if !self.is_canonicalized(txid) {
225                    if let Err(err) = self.scan_anchors(txid, tx, anchors) {
226                        return Some(Err(err));
227                    }
228                }
229                continue;
230            }
231
232            if let Some((txid, tx, last_seen)) = self.unprocessed_seen_txs.next() {
233                debug_assert!(
234                    !tx.is_coinbase(),
235                    "Coinbase txs must not have `last_seen` (in mempool) value"
236                );
237                if !self.is_canonicalized(txid) {
238                    let observed_in = ObservedIn::Mempool(last_seen);
239                    self.mark_canonical(txid, tx, CanonicalReason::from_observed_in(observed_in));
240                }
241                continue;
242            }
243
244            if let Some((txid, tx, height)) = self.unprocessed_leftover_txs.pop_front() {
245                if !self.is_canonicalized(txid) && !tx.is_coinbase() {
246                    let observed_in = ObservedIn::Block(height);
247                    self.mark_canonical(txid, tx, CanonicalReason::from_observed_in(observed_in));
248                }
249                continue;
250            }
251
252            return None;
253        }
254    }
255}
256
257/// Represents when and where a transaction was last observed in.
258#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
259pub enum ObservedIn {
260    /// The transaction was last observed in a block of height.
261    Block(u32),
262    /// The transaction was last observed in the mempool at the given unix timestamp.
263    Mempool(u64),
264}
265
266/// The reason why a transaction is canonical.
267#[derive(Debug, Clone, PartialEq, Eq)]
268pub enum CanonicalReason<A> {
269    /// This transaction is explicitly assumed to be canonical by the caller, superceding all other
270    /// canonicalization rules.
271    Assumed {
272        /// Whether it is a descendant that is assumed to be canonical.
273        descendant: Option<Txid>,
274    },
275    /// This transaction is anchored in the best chain by `A`, and therefore canonical.
276    Anchor {
277        /// The anchor that anchored the transaction in the chain.
278        anchor: A,
279        /// Whether the anchor is of the transaction's descendant.
280        descendant: Option<Txid>,
281    },
282    /// This transaction does not conflict with any other transaction with a more recent
283    /// [`ObservedIn`] value or one that is anchored in the best chain.
284    ObservedIn {
285        /// The [`ObservedIn`] value of the transaction.
286        observed_in: ObservedIn,
287        /// Whether the [`ObservedIn`] value is of the transaction's descendant.
288        descendant: Option<Txid>,
289    },
290}
291
292impl<A: Clone> CanonicalReason<A> {
293    /// Constructs a [`CanonicalReason`] for a transaction that is assumed to supercede all other
294    /// transactions.
295    pub fn assumed() -> Self {
296        Self::Assumed { descendant: None }
297    }
298
299    /// Constructs a [`CanonicalReason`] from an `anchor`.
300    pub fn from_anchor(anchor: A) -> Self {
301        Self::Anchor {
302            anchor,
303            descendant: None,
304        }
305    }
306
307    /// Constructs a [`CanonicalReason`] from an `observed_in` value.
308    pub fn from_observed_in(observed_in: ObservedIn) -> Self {
309        Self::ObservedIn {
310            observed_in,
311            descendant: None,
312        }
313    }
314
315    /// Contruct a new [`CanonicalReason`] from the original which is transitive to `descendant`.
316    ///
317    /// This signals that either the [`ObservedIn`] or [`Anchor`] value belongs to the transaction's
318    /// descendant, but is transitively relevant.
319    pub fn to_transitive(&self, descendant: Txid) -> Self {
320        match self {
321            CanonicalReason::Assumed { .. } => Self::Assumed {
322                descendant: Some(descendant),
323            },
324            CanonicalReason::Anchor { anchor, .. } => Self::Anchor {
325                anchor: anchor.clone(),
326                descendant: Some(descendant),
327            },
328            CanonicalReason::ObservedIn { observed_in, .. } => Self::ObservedIn {
329                observed_in: *observed_in,
330                descendant: Some(descendant),
331            },
332        }
333    }
334
335    /// This signals that either the [`ObservedIn`] or [`Anchor`] value belongs to the transaction's
336    /// descendant.
337    pub fn descendant(&self) -> &Option<Txid> {
338        match self {
339            CanonicalReason::Assumed { descendant, .. } => descendant,
340            CanonicalReason::Anchor { descendant, .. } => descendant,
341            CanonicalReason::ObservedIn { descendant, .. } => descendant,
342        }
343    }
344}
bdk_chain/canonical_iter.rs

bdk_chain/
canonical_iter.rs
