zebra_node_services/mempool/transaction_dependencies.rs
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 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 dependencies.remove(mined_tx_id);
77 if dependencies.is_empty() {
78 self.dependencies.remove(&dependent_id);
79 }
80 }
81 }
82 }
83
84 /// Removes the hash of a transaction in the mempool and the hashes of any transactions
85 /// that are tracked as being directly or indirectly dependent on that transaction from
86 /// this [`TransactionDependencies`].
87 ///
88 /// Returns a list of transaction hashes that were being tracked as dependents of the
89 /// provided transaction hash.
90 pub fn remove_all(&mut self, &tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
91 let mut all_dependents = HashSet::new();
92 let mut current_level_dependents: HashSet<_> = [tx_hash].into();
93
94 while !current_level_dependents.is_empty() {
95 current_level_dependents = current_level_dependents
96 .iter()
97 .flat_map(|dependent| {
98 for dependency in self.dependencies.remove(dependent).unwrap_or_default() {
99 let Some(dependents_of_dependency) = self.dependents.get_mut(&dependency)
100 else {
101 continue;
102 };
103
104 dependents_of_dependency.remove(dependent);
105 if dependents_of_dependency.is_empty() {
106 self.dependents.remove(&dependency);
107 }
108 }
109
110 self.dependents.remove(dependent).unwrap_or_default()
111 })
112 .collect();
113
114 all_dependents.extend(¤t_level_dependents);
115 }
116
117 all_dependents
118 }
119
120 /// Returns a list of hashes of transactions that directly depend on the transaction for `tx_hash`.
121 pub fn direct_dependents(&self, tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
122 self.dependents.get(tx_hash).cloned().unwrap_or_default()
123 }
124
125 /// Returns a list of hashes of transactions that are direct dependencies of the transaction for `tx_hash`.
126 pub fn direct_dependencies(&self, tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
127 self.dependencies.get(tx_hash).cloned().unwrap_or_default()
128 }
129
130 /// Clear the maps of transaction dependencies.
131 pub fn clear(&mut self) {
132 self.dependencies.clear();
133 self.dependents.clear();
134 }
135
136 /// Returns the map of transaction's dependencies
137 pub fn dependencies(&self) -> &HashMap<transaction::Hash, HashSet<transaction::Hash>> {
138 &self.dependencies
139 }
140
141 /// Returns the map of transaction's dependents
142 pub fn dependents(&self) -> &HashMap<transaction::Hash, HashSet<transaction::Hash>> {
143 &self.dependents
144 }
145}