zebra_node_services/mempool/
transaction_dependencies.rs

Help
1//! Representation of mempool transactions' dependencies on other transactions in the mempool.
2
3use std::collections::{HashMap, HashSet};
4
5use zebra_chain::{transaction, transparent};
6
7/// Representation of mempool transactions' dependencies on other transactions in the mempool.
8#[derive(Default, Debug, Clone)]
9pub struct TransactionDependencies {
10    /// Lists of mempool transaction ids that create UTXOs spent by
11    /// a mempool transaction. Used during block template construction
12    /// to exclude transactions from block templates unless all of the
13    /// transactions they depend on have been included.
14    ///
15    /// # Note
16    ///
17    /// Dependencies that have been mined into blocks are not removed here until those blocks have
18    /// been committed to the best chain. Dependencies that have been committed onto side chains, or
19    /// which are in the verification pipeline but have not yet been committed to the best chain,
20    /// are not removed here unless and until they arrive in the best chain, and the mempool is polled.
21    dependencies: HashMap<transaction::Hash, HashSet<transaction::Hash>>,
22
23    /// Lists of transaction ids in the mempool that spend UTXOs created
24    /// by a transaction in the mempool, e.g. tx1 -> set(tx2, tx3, tx4) where
25    /// tx2, tx3, and tx4 spend outputs created by tx1.
26    dependents: HashMap<transaction::Hash, HashSet<transaction::Hash>>,
27}
28
29impl TransactionDependencies {
30    /// Adds a transaction that spends outputs created by other transactions in the mempool
31    /// as a dependent of those transactions, and adds the transactions that created the outputs
32    /// spent by the dependent transaction as dependencies of the dependent transaction.
33    ///
34    /// # Correctness
35    ///
36    /// It's the caller's responsibility to ensure that there are no cyclical dependencies.
37    ///
38    /// The transaction verifier will wait until the spent output of a transaction has been added to the verified set,
39    /// so its `AwaitOutput` requests will timeout if there is a cyclical dependency.
40    pub fn add(
41        &mut self,
42        dependent: transaction::Hash,
43        spent_mempool_outpoints: Vec<transparent::OutPoint>,
44    ) {
45        for &spent_mempool_outpoint in &spent_mempool_outpoints {
46            self.dependents
47                .entry(spent_mempool_outpoint.hash)
48                .or_default()
49                .insert(dependent);
50        }
51
52        // Only add an entries to `dependencies` for transactions that spend unmined outputs so it
53        // can be used to handle transactions with dependencies differently during block production.
54        if !spent_mempool_outpoints.is_empty() {
55            self.dependencies.insert(
56                dependent,
57                spent_mempool_outpoints
58                    .into_iter()
59                    .map(|outpoint| outpoint.hash)
60                    .collect(),
61            );
62        }
63    }
64
65    /// Removes all dependents for a list of mined transaction ids and removes the mined transaction ids
66    /// from the dependencies of their dependents.
67    pub fn clear_mined_dependencies(&mut self, mined_ids: &HashSet<transaction::Hash>) {
68        for mined_tx_id in mined_ids {
69            for dependent_id in self.dependents.remove(mined_tx_id).unwrap_or_default() {
70                let Some(dependencies) = self.dependencies.get_mut(&dependent_id) else {
71                    // TODO: Move this struct to zebra-chain and log a warning here.
72                    continue;
73                };
74
75                // TODO: Move this struct to zebra-chain and log a warning here if the dependency was not found.
76                let _ = dependencies.remove(&dependent_id);
77            }
78        }
79    }
80
81    /// Removes the hash of a transaction in the mempool and the hashes of any transactions
82    /// that are tracked as being directly or indirectly dependent on that transaction from
83    /// this [`TransactionDependencies`].
84    ///
85    /// Returns a list of transaction hashes that were being tracked as dependents of the
86    /// provided transaction hash.
87    pub fn remove_all(&mut self, &tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
88        let mut all_dependents = HashSet::new();
89        let mut current_level_dependents: HashSet<_> = [tx_hash].into();
90
91        while !current_level_dependents.is_empty() {
92            current_level_dependents = current_level_dependents
93                .iter()
94                .flat_map(|dep| {
95                    self.dependencies.remove(dep);
96                    self.dependents.remove(dep).unwrap_or_default()
97                })
98                .collect();
99
100            all_dependents.extend(&current_level_dependents);
101        }
102
103        all_dependents
104    }
105
106    /// Returns a list of hashes of transactions that directly depend on the transaction for `tx_hash`.
107    pub fn direct_dependents(&self, tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
108        self.dependents.get(tx_hash).cloned().unwrap_or_default()
109    }
110
111    /// Returns a list of hashes of transactions that are direct dependencies of the transaction for `tx_hash`.
112    pub fn direct_dependencies(&self, tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
113        self.dependencies.get(tx_hash).cloned().unwrap_or_default()
114    }
115
116    /// Clear the maps of transaction dependencies.
117    pub fn clear(&mut self) {
118        self.dependencies.clear();
119        self.dependents.clear();
120    }
121
122    /// Returns the map of transaction's dependencies
123    pub fn dependencies(&self) -> &HashMap<transaction::Hash, HashSet<transaction::Hash>> {
124        &self.dependencies
125    }
126
127    /// Returns the map of transaction's dependents
128    pub fn dependents(&self) -> &HashMap<transaction::Hash, HashSet<transaction::Hash>> {
129        &self.dependents
130    }
131}
zebra_node_services/mempool/transaction_dependencies.rs

zebra_node_services/mempool/
transaction_dependencies.rs
