zebrad/components/mempool/storage/
verified_set.rs

1//! The set of verified transactions in the mempool.
2
3use std::{
4    borrow::Cow,
5    collections::{HashMap, HashSet},
6    hash::Hash,
7};
8
9use zebra_chain::{
10    block::Height,
11    orchard, sapling, sprout,
12    transaction::{self, UnminedTx, VerifiedUnminedTx},
13    transparent,
14};
15use zebra_node_services::mempool::TransactionDependencies;
16
17use crate::components::mempool::pending_outputs::PendingOutputs;
18
19use super::super::SameEffectsTipRejectionError;
20
21// Imports for doc links
22#[allow(unused_imports)]
23use zebra_chain::transaction::MEMPOOL_TRANSACTION_COST_THRESHOLD;
24
25/// The set of verified transactions stored in the mempool.
26///
27/// This also caches the all the spent outputs from the transactions in the mempool. The spent
28/// outputs include:
29///
30/// - the dependencies of transactions that spent the outputs of other transactions in the mempool
31/// - the outputs of transactions in the mempool
32/// - the transparent outpoints spent by transactions in the mempool
33/// - the Sprout nullifiers revealed by transactions in the mempool
34/// - the Sapling nullifiers revealed by transactions in the mempool
35/// - the Orchard nullifiers revealed by transactions in the mempool
36#[derive(Default)]
37pub struct VerifiedSet {
38    /// The set of verified transactions in the mempool.
39    transactions: HashMap<transaction::Hash, VerifiedUnminedTx>,
40
41    /// A map of dependencies between transactions in the mempool that
42    /// spend or create outputs of other transactions in the mempool.
43    transaction_dependencies: TransactionDependencies,
44
45    /// The [`transparent::Output`]s created by verified transactions in the mempool.
46    ///
47    /// These outputs may be spent by other transactions in the mempool.
48    created_outputs: HashMap<transparent::OutPoint, transparent::Output>,
49
50    /// The total size of the transactions in the mempool if they were
51    /// serialized.
52    transactions_serialized_size: usize,
53
54    /// The total cost of the verified transactions in the set.
55    total_cost: u64,
56
57    /// The set of spent out points by the verified transactions.
58    spent_outpoints: HashSet<transparent::OutPoint>,
59
60    /// The set of revealed Sprout nullifiers.
61    sprout_nullifiers: HashSet<sprout::Nullifier>,
62
63    /// The set of revealed Sapling nullifiers.
64    sapling_nullifiers: HashSet<sapling::Nullifier>,
65
66    /// The set of revealed Orchard nullifiers.
67    orchard_nullifiers: HashSet<orchard::Nullifier>,
68}
69
70impl Drop for VerifiedSet {
71    fn drop(&mut self) {
72        // zero the metrics on drop
73        self.clear()
74    }
75}
76
77impl VerifiedSet {
78    /// Returns a reference to the [`HashMap`] of [`VerifiedUnminedTx`]s in the set.
79    pub fn transactions(&self) -> &HashMap<transaction::Hash, VerifiedUnminedTx> {
80        &self.transactions
81    }
82
83    /// Returns a reference to the [`TransactionDependencies`] in the set.
84    pub fn transaction_dependencies(&self) -> &TransactionDependencies {
85        &self.transaction_dependencies
86    }
87
88    /// Returns a [`transparent::Output`] created by a mempool transaction for the provided
89    /// [`transparent::OutPoint`] if one exists, or None otherwise.
90    pub fn created_output(&self, outpoint: &transparent::OutPoint) -> Option<transparent::Output> {
91        self.created_outputs.get(outpoint).cloned()
92    }
93
94    /// Returns the number of verified transactions in the set.
95    pub fn transaction_count(&self) -> usize {
96        self.transactions.len()
97    }
98
99    /// Returns the total cost of the verified transactions in the set.
100    ///
101    /// [ZIP-401]: https://zips.z.cash/zip-0401
102    pub fn total_cost(&self) -> u64 {
103        self.total_cost
104    }
105
106    /// Returns the total serialized size of the verified transactions in the set.
107    ///
108    /// This can be less than the total cost, because the minimum transaction cost
109    /// is based on the [`MEMPOOL_TRANSACTION_COST_THRESHOLD`].
110    pub fn total_serialized_size(&self) -> usize {
111        self.transactions_serialized_size
112    }
113
114    /// Returns `true` if the set of verified transactions contains the transaction with the
115    /// specified [`transaction::Hash`].
116    pub fn contains(&self, id: &transaction::Hash) -> bool {
117        self.transactions.contains_key(id)
118    }
119
120    /// Clear the set of verified transactions.
121    ///
122    /// Also clears all internal caches.
123    pub fn clear(&mut self) {
124        self.transactions.clear();
125        self.transaction_dependencies.clear();
126        self.spent_outpoints.clear();
127        self.sprout_nullifiers.clear();
128        self.sapling_nullifiers.clear();
129        self.orchard_nullifiers.clear();
130        self.created_outputs.clear();
131        self.transactions_serialized_size = 0;
132        self.total_cost = 0;
133        self.update_metrics();
134    }
135
136    /// Insert a `transaction` into the set.
137    ///
138    /// Returns an error if the `transaction` has spend conflicts with any other transaction
139    /// already in the set.
140    ///
141    /// Two transactions have a spend conflict if they spend the same UTXO or if they reveal the
142    /// same nullifier.
143    pub fn insert(
144        &mut self,
145        mut transaction: VerifiedUnminedTx,
146        spent_mempool_outpoints: Vec<transparent::OutPoint>,
147        pending_outputs: &mut PendingOutputs,
148        height: Option<Height>,
149    ) -> Result<(), SameEffectsTipRejectionError> {
150        if self.has_spend_conflicts(&transaction.transaction) {
151            return Err(SameEffectsTipRejectionError::SpendConflict);
152        }
153
154        // This likely only needs to check that the transaction hash of the outpoint is still in the mempool,
155        // but it's likely rare that a transaction spends multiple transparent outputs of
156        // a single transaction in practice.
157        for outpoint in &spent_mempool_outpoints {
158            if !self.created_outputs.contains_key(outpoint) {
159                return Err(SameEffectsTipRejectionError::MissingOutput);
160            }
161        }
162
163        let tx_id = transaction.transaction.id.mined_id();
164        self.transaction_dependencies
165            .add(tx_id, spent_mempool_outpoints);
166
167        // Inserts the transaction's outputs into the internal caches and responds to pending output requests.
168        let tx = &transaction.transaction.transaction;
169        for (index, output) in tx.outputs().iter().cloned().enumerate() {
170            let outpoint = transparent::OutPoint::from_usize(tx_id, index);
171            self.created_outputs.insert(outpoint, output.clone());
172            pending_outputs.respond(&outpoint, output)
173        }
174        self.spent_outpoints.extend(tx.spent_outpoints());
175        self.sprout_nullifiers.extend(tx.sprout_nullifiers());
176        self.sapling_nullifiers.extend(tx.sapling_nullifiers());
177        self.orchard_nullifiers.extend(tx.orchard_nullifiers());
178
179        self.transactions_serialized_size += transaction.transaction.size;
180        self.total_cost += transaction.cost();
181        transaction.time = Some(chrono::Utc::now());
182        transaction.height = height;
183        self.transactions.insert(tx_id, transaction);
184
185        self.update_metrics();
186
187        Ok(())
188    }
189
190    /// Evict one transaction and any transactions that directly or indirectly depend on
191    /// its outputs from the set, returns the victim transaction and any dependent transactions.
192    ///
193    /// Removes a transaction with probability in direct proportion to the
194    /// eviction weight, as per [ZIP-401].
195    ///
196    /// Consensus rule:
197    ///
198    /// > Each transaction also has an eviction weight, which is cost +
199    /// > low_fee_penalty, where low_fee_penalty is 16000 if the transaction pays
200    /// > a fee less than the conventional fee, otherwise 0. The conventional fee
201    /// > is currently defined as 1000 zatoshis
202    ///
203    /// # Note
204    ///
205    /// Collecting and calculating weights is O(n). But in practice n is limited
206    /// to 20,000 (mempooltxcostlimit/min(cost)), so the actual cost shouldn't
207    /// be too bad.
208    ///
209    /// This function is equivalent to `EvictTransaction` in [ZIP-401].
210    ///
211    /// [ZIP-401]: https://zips.z.cash/zip-0401
212    #[allow(clippy::unwrap_in_result)]
213    pub fn evict_one(&mut self) -> Option<VerifiedUnminedTx> {
214        use rand::distributions::{Distribution, WeightedIndex};
215        use rand::prelude::thread_rng;
216
217        let (keys, weights): (Vec<transaction::Hash>, Vec<u64>) = self
218            .transactions
219            .iter()
220            .map(|(&tx_id, tx)| (tx_id, tx.eviction_weight()))
221            .unzip();
222
223        let dist = WeightedIndex::new(weights).expect(
224            "there is at least one weight, all weights are non-negative, and the total is positive",
225        );
226
227        let key_to_remove = keys
228            .get(dist.sample(&mut thread_rng()))
229            .expect("should have a key at every index in the distribution");
230
231        // Removes the randomly selected transaction and all of its dependents from the set,
232        // then returns just the randomly selected transaction
233        self.remove(key_to_remove).pop()
234    }
235
236    /// Clears a list of mined transaction ids from the lists of dependencies for
237    /// any other transactions in the mempool and removes their dependents.
238    pub fn clear_mined_dependencies(&mut self, mined_ids: &HashSet<transaction::Hash>) {
239        self.transaction_dependencies
240            .clear_mined_dependencies(mined_ids);
241    }
242
243    /// Removes all transactions in the set that match the `predicate`.
244    ///
245    /// Returns the amount of transactions removed.
246    pub fn remove_all_that(&mut self, predicate: impl Fn(&VerifiedUnminedTx) -> bool) -> usize {
247        let keys_to_remove: Vec<_> = self
248            .transactions
249            .iter()
250            .filter_map(|(&tx_id, tx)| predicate(tx).then_some(tx_id))
251            .collect();
252
253        let mut removed_count = 0;
254
255        for key_to_remove in keys_to_remove {
256            removed_count += self.remove(&key_to_remove).len();
257        }
258
259        removed_count
260    }
261
262    /// Accepts a transaction id for a transaction to remove from the verified set.
263    ///
264    /// Removes the transaction and any transactions that directly or indirectly
265    /// depend on it from the set.
266    ///
267    /// Returns a list of transactions that have been removed with the target transaction
268    /// as the last item.
269    ///
270    /// Also removes the outputs of any removed transactions from the internal caches.
271    fn remove(&mut self, key_to_remove: &transaction::Hash) -> Vec<VerifiedUnminedTx> {
272        let removed_transactions: Vec<_> = self
273            .transaction_dependencies
274            .remove_all(key_to_remove)
275            .iter()
276            .chain(std::iter::once(key_to_remove))
277            .map(|key_to_remove| {
278                let removed_tx = self
279                    .transactions
280                    .remove(key_to_remove)
281                    .expect("invalid transaction key");
282
283                self.transactions_serialized_size -= removed_tx.transaction.size;
284                self.total_cost -= removed_tx.cost();
285                self.remove_outputs(&removed_tx.transaction);
286
287                removed_tx
288            })
289            .collect();
290
291        self.update_metrics();
292        removed_transactions
293    }
294
295    /// Returns `true` if the given `transaction` has any spend conflicts with transactions in the
296    /// mempool.
297    ///
298    /// Two transactions have a spend conflict if they spend the same UTXO or if they reveal the
299    /// same nullifier.
300    fn has_spend_conflicts(&self, unmined_tx: &UnminedTx) -> bool {
301        let tx = &unmined_tx.transaction;
302
303        Self::has_conflicts(&self.spent_outpoints, tx.spent_outpoints())
304            || Self::has_conflicts(&self.sprout_nullifiers, tx.sprout_nullifiers().copied())
305            || Self::has_conflicts(&self.sapling_nullifiers, tx.sapling_nullifiers().copied())
306            || Self::has_conflicts(&self.orchard_nullifiers, tx.orchard_nullifiers().copied())
307    }
308
309    /// Removes the tracked transaction outputs from the mempool.
310    fn remove_outputs(&mut self, unmined_tx: &UnminedTx) {
311        let tx = &unmined_tx.transaction;
312
313        for index in 0..tx.outputs().len() {
314            self.created_outputs
315                .remove(&transparent::OutPoint::from_usize(
316                    unmined_tx.id.mined_id(),
317                    index,
318                ));
319        }
320
321        let spent_outpoints = tx.spent_outpoints().map(Cow::Owned);
322        let sprout_nullifiers = tx.sprout_nullifiers().map(Cow::Borrowed);
323        let sapling_nullifiers = tx.sapling_nullifiers().map(Cow::Borrowed);
324        let orchard_nullifiers = tx.orchard_nullifiers().map(Cow::Borrowed);
325
326        Self::remove_from_set(&mut self.spent_outpoints, spent_outpoints);
327        Self::remove_from_set(&mut self.sprout_nullifiers, sprout_nullifiers);
328        Self::remove_from_set(&mut self.sapling_nullifiers, sapling_nullifiers);
329        Self::remove_from_set(&mut self.orchard_nullifiers, orchard_nullifiers);
330    }
331
332    /// Returns `true` if the two sets have common items.
333    fn has_conflicts<T>(set: &HashSet<T>, mut list: impl Iterator<Item = T>) -> bool
334    where
335        T: Eq + Hash,
336    {
337        list.any(|item| set.contains(&item))
338    }
339
340    /// Removes some items from a [`HashSet`].
341    ///
342    /// Each item in the list of `items` should be wrapped in a [`Cow`]. This allows this generic
343    /// method to support both borrowed and owned items.
344    fn remove_from_set<'t, T>(set: &mut HashSet<T>, items: impl IntoIterator<Item = Cow<'t, T>>)
345    where
346        T: Clone + Eq + Hash + 't,
347    {
348        for item in items {
349            set.remove(&item);
350        }
351    }
352
353    fn update_metrics(&mut self) {
354        // Track the sum of unpaid actions within each transaction (as they are subject to the
355        // unpaid action limit). Transactions that have weight >= 1 have no unpaid actions by
356        // definition.
357        let mut unpaid_actions_with_weight_lt20pct = 0;
358        let mut unpaid_actions_with_weight_lt40pct = 0;
359        let mut unpaid_actions_with_weight_lt60pct = 0;
360        let mut unpaid_actions_with_weight_lt80pct = 0;
361        let mut unpaid_actions_with_weight_lt1 = 0;
362
363        // Track the total number of paid actions across all transactions in the mempool. This
364        // added to the bucketed unpaid actions above is equal to the total number of conventional
365        // actions in the mempool.
366        let mut paid_actions = 0;
367
368        // Track the sum of transaction sizes (the metric by which they are mainly limited) across
369        // several buckets.
370        let mut size_with_weight_lt1 = 0;
371        let mut size_with_weight_eq1 = 0;
372        let mut size_with_weight_gt1 = 0;
373        let mut size_with_weight_gt2 = 0;
374        let mut size_with_weight_gt3 = 0;
375
376        for entry in self.transactions().values() {
377            paid_actions += entry.conventional_actions - entry.unpaid_actions;
378
379            if entry.fee_weight_ratio > 3.0 {
380                size_with_weight_gt3 += entry.transaction.size;
381            } else if entry.fee_weight_ratio > 2.0 {
382                size_with_weight_gt2 += entry.transaction.size;
383            } else if entry.fee_weight_ratio > 1.0 {
384                size_with_weight_gt1 += entry.transaction.size;
385            } else if entry.fee_weight_ratio == 1.0 {
386                size_with_weight_eq1 += entry.transaction.size;
387            } else {
388                size_with_weight_lt1 += entry.transaction.size;
389                if entry.fee_weight_ratio < 0.2 {
390                    unpaid_actions_with_weight_lt20pct += entry.unpaid_actions;
391                } else if entry.fee_weight_ratio < 0.4 {
392                    unpaid_actions_with_weight_lt40pct += entry.unpaid_actions;
393                } else if entry.fee_weight_ratio < 0.6 {
394                    unpaid_actions_with_weight_lt60pct += entry.unpaid_actions;
395                } else if entry.fee_weight_ratio < 0.8 {
396                    unpaid_actions_with_weight_lt80pct += entry.unpaid_actions;
397                } else {
398                    unpaid_actions_with_weight_lt1 += entry.unpaid_actions;
399                }
400            }
401        }
402
403        metrics::gauge!(
404            "zcash.mempool.actions.unpaid",
405            "bk" => "< 0.2",
406        )
407        .set(unpaid_actions_with_weight_lt20pct as f64);
408        metrics::gauge!(
409            "zcash.mempool.actions.unpaid",
410            "bk" => "< 0.4",
411        )
412        .set(unpaid_actions_with_weight_lt40pct as f64);
413        metrics::gauge!(
414            "zcash.mempool.actions.unpaid",
415            "bk" => "< 0.6",
416        )
417        .set(unpaid_actions_with_weight_lt60pct as f64);
418        metrics::gauge!(
419            "zcash.mempool.actions.unpaid",
420            "bk" => "< 0.8",
421        )
422        .set(unpaid_actions_with_weight_lt80pct as f64);
423        metrics::gauge!(
424            "zcash.mempool.actions.unpaid",
425            "bk" => "< 1",
426        )
427        .set(unpaid_actions_with_weight_lt1 as f64);
428        metrics::gauge!("zcash.mempool.actions.paid").set(paid_actions as f64);
429        metrics::gauge!("zcash.mempool.size.transactions",).set(self.transaction_count() as f64);
430        metrics::gauge!(
431            "zcash.mempool.size.weighted",
432            "bk" => "< 1",
433        )
434        .set(size_with_weight_lt1 as f64);
435        metrics::gauge!(
436            "zcash.mempool.size.weighted",
437            "bk" => "1",
438        )
439        .set(size_with_weight_eq1 as f64);
440        metrics::gauge!(
441            "zcash.mempool.size.weighted",
442            "bk" => "> 1",
443        )
444        .set(size_with_weight_gt1 as f64);
445        metrics::gauge!(
446            "zcash.mempool.size.weighted",
447            "bk" => "> 2",
448        )
449        .set(size_with_weight_gt2 as f64);
450        metrics::gauge!(
451            "zcash.mempool.size.weighted",
452            "bk" => "> 3",
453        )
454        .set(size_with_weight_gt3 as f64);
455        metrics::gauge!("zcash.mempool.size.bytes",).set(self.transactions_serialized_size as f64);
456        metrics::gauge!("zcash.mempool.cost.bytes").set(self.total_cost as f64);
457    }
458}