zebrad/components/mempool/
storage.rs

1//! Mempool transaction storage.
2//!
3//! The main struct [`Storage`] holds verified and rejected transactions.
4//! [`Storage`] is effectively the data structure of the mempool. Convenient methods to
5//! manage it are included.
6//!
7//! [`Storage`] does not expose a service so it can only be used by other code directly.
8//! Only code inside the [`crate::components::mempool`] module has access to it.
9
10use std::{
11    collections::{HashMap, HashSet},
12    mem::size_of,
13    sync::Arc,
14    time::Duration,
15};
16
17use thiserror::Error;
18
19use zebra_chain::{
20    block::Height,
21    transaction::{self, Hash, Transaction, UnminedTx, UnminedTxId, VerifiedUnminedTx},
22    transparent,
23};
24use zebra_node_services::mempool::TransactionDependencies;
25
26use self::{eviction_list::EvictionList, verified_set::VerifiedSet};
27use super::{
28    config, downloads::TransactionDownloadVerifyError, pending_outputs::PendingOutputs,
29    MempoolError,
30};
31
32#[cfg(any(test, feature = "proptest-impl"))]
33use proptest_derive::Arbitrary;
34
35#[cfg(test)]
36pub mod tests;
37
38mod eviction_list;
39mod verified_set;
40
41/// The size limit for mempool transaction rejection lists per [ZIP-401].
42///
43/// > The size of RecentlyEvicted SHOULD never exceed `eviction_memory_entries`
44/// > entries, which is the constant 40000.
45///
46/// We use the specified value for all lists for consistency.
47///
48/// [ZIP-401]: https://zips.z.cash/zip-0401#specification
49pub(crate) const MAX_EVICTION_MEMORY_ENTRIES: usize = 40_000;
50
51/// Transactions rejected based on transaction authorizing data (scripts, proofs, signatures),
52/// or lock times. These rejections are only valid for the current tip.
53///
54/// Each committed block clears these rejections, because new blocks can supply missing inputs.
55#[derive(Error, Clone, Debug, PartialEq, Eq)]
56#[cfg_attr(any(test, feature = "proptest-impl"), derive(Arbitrary))]
57#[allow(dead_code)]
58pub enum ExactTipRejectionError {
59    #[error("transaction did not pass consensus validation: {0}")]
60    FailedVerification(#[from] zebra_consensus::error::TransactionError),
61}
62
63/// Transactions rejected based only on their effects (spends, outputs, transaction header).
64/// These rejections are only valid for the current tip.
65///
66/// Each committed block clears these rejections, because new blocks can evict other transactions.
67#[derive(Error, Clone, Debug, PartialEq, Eq)]
68#[cfg_attr(any(test, feature = "proptest-impl"), derive(Arbitrary))]
69#[allow(dead_code)]
70pub enum SameEffectsTipRejectionError {
71    #[error(
72        "transaction rejected because another transaction in the mempool has already spent some of \
73        its inputs"
74    )]
75    SpendConflict,
76
77    #[error(
78        "transaction rejected because it spends missing outputs from \
79        another transaction in the mempool"
80    )]
81    MissingOutput,
82}
83
84/// Transactions rejected based only on their effects (spends, outputs, transaction header).
85/// These rejections are valid while the current chain continues to grow.
86///
87/// Rollbacks and network upgrades clear these rejections, because they can lower the tip height,
88/// or change the consensus rules.
89#[derive(Error, Clone, Debug, PartialEq, Eq, Hash)]
90#[cfg_attr(any(test, feature = "proptest-impl"), derive(Arbitrary))]
91#[allow(dead_code)]
92pub enum SameEffectsChainRejectionError {
93    #[error("best chain tip has reached transaction expiry height")]
94    Expired,
95
96    #[error("transaction inputs were spent, or nullifiers were revealed, in the best chain")]
97    DuplicateSpend,
98
99    #[error("transaction was committed to the best chain")]
100    Mined,
101
102    /// Otherwise valid transaction removed from mempool due to [ZIP-401] random
103    /// eviction.
104    ///
105    /// Consensus rule:
106    /// > The txid (rather than the wtxid ...) is used even for version 5 transactions
107    ///
108    /// [ZIP-401]: https://zips.z.cash/zip-0401#specification
109    #[error("transaction evicted from the mempool due to ZIP-401 denial of service limits")]
110    RandomlyEvicted,
111}
112
113/// Storage error that combines all other specific error types.
114#[derive(Error, Clone, Debug, PartialEq, Eq)]
115#[cfg_attr(any(test, feature = "proptest-impl"), derive(Arbitrary))]
116#[allow(dead_code)]
117pub enum RejectionError {
118    #[error(transparent)]
119    ExactTip(#[from] ExactTipRejectionError),
120    #[error(transparent)]
121    SameEffectsTip(#[from] SameEffectsTipRejectionError),
122    #[error(transparent)]
123    SameEffectsChain(#[from] SameEffectsChainRejectionError),
124}
125
126/// Represents a set of transactions that have been removed from the mempool, either because
127/// they were mined, or because they were invalidated by another transaction that was mined.
128#[derive(Clone, Debug, PartialEq, Eq)]
129pub struct RemovedTransactionIds {
130    /// A list of ids for transactions that were removed mined onto the best chain.
131    pub mined: HashSet<UnminedTxId>,
132    /// A list of ids for transactions that were invalidated by other transactions
133    /// that were mined onto the best chain.
134    pub invalidated: HashSet<UnminedTxId>,
135}
136
137impl RemovedTransactionIds {
138    /// Returns the total number of transactions that were removed from the mempool.
139    pub fn total_len(&self) -> usize {
140        self.mined.len() + self.invalidated.len()
141    }
142}
143
144/// Hold mempool verified and rejected mempool transactions.
145pub struct Storage {
146    /// The set of verified transactions in the mempool.
147    verified: VerifiedSet,
148
149    /// The set of outpoints with pending requests for their associated transparent::Output.
150    pub(super) pending_outputs: PendingOutputs,
151
152    /// The set of transactions rejected due to bad authorizations, or for other
153    /// reasons, and their rejection reasons. These rejections only apply to the
154    /// current tip.
155    ///
156    /// Only transactions with the exact [`UnminedTxId`] are invalid.
157    tip_rejected_exact: HashMap<UnminedTxId, ExactTipRejectionError>,
158
159    /// A set of transactions rejected for their effects, and their rejection
160    /// reasons. These rejections only apply to the current tip.
161    ///
162    /// Any transaction with the same [`transaction::Hash`] is invalid.
163    tip_rejected_same_effects: HashMap<transaction::Hash, SameEffectsTipRejectionError>,
164
165    /// Sets of transactions rejected for their effects, keyed by rejection reason.
166    /// These rejections apply until a rollback or network upgrade.
167    ///
168    /// Any transaction with the same [`transaction::Hash`] is invalid.
169    ///
170    /// An [`EvictionList`] is used for both randomly evicted and expired
171    /// transactions, even if it is only needed for the evicted ones. This was
172    /// done just to simplify the existing code; there is no harm in having a
173    /// timeout for expired transactions too since re-checking expired
174    /// transactions is cheap.
175    // If this code is ever refactored and the lists are split in different
176    // fields, then we can use an `EvictionList` just for the evicted list.
177    chain_rejected_same_effects: HashMap<SameEffectsChainRejectionError, EvictionList>,
178
179    /// The mempool transaction eviction age limit.
180    /// Same as [`config::Config::eviction_memory_time`].
181    eviction_memory_time: Duration,
182
183    /// Max total cost of the verified mempool set, beyond which transactions
184    /// are evicted to make room.
185    tx_cost_limit: u64,
186}
187
188impl Drop for Storage {
189    fn drop(&mut self) {
190        self.clear();
191    }
192}
193
194impl Storage {
195    #[allow(clippy::field_reassign_with_default)]
196    pub(crate) fn new(config: &config::Config) -> Self {
197        Self {
198            tx_cost_limit: config.tx_cost_limit,
199            eviction_memory_time: config.eviction_memory_time,
200            verified: Default::default(),
201            pending_outputs: Default::default(),
202            tip_rejected_exact: Default::default(),
203            tip_rejected_same_effects: Default::default(),
204            chain_rejected_same_effects: Default::default(),
205        }
206    }
207
208    /// Insert a [`VerifiedUnminedTx`] into the mempool, caching any rejections.
209    ///
210    /// Accepts the [`VerifiedUnminedTx`] being inserted and `spent_mempool_outpoints`,
211    /// a list of transparent inputs of the provided [`VerifiedUnminedTx`] that were found
212    /// as newly created transparent outputs in the mempool during transaction verification.
213    ///
214    /// Returns an error if the mempool's verified transactions or rejection caches
215    /// prevent this transaction from being inserted.
216    /// These errors should not be propagated to peers, because the transactions are valid.
217    ///
218    /// If inserting this transaction evicts other transactions, they will be tracked
219    /// as [`SameEffectsChainRejectionError::RandomlyEvicted`].
220    #[allow(clippy::unwrap_in_result)]
221    pub fn insert(
222        &mut self,
223        tx: VerifiedUnminedTx,
224        spent_mempool_outpoints: Vec<transparent::OutPoint>,
225        height: Option<Height>,
226    ) -> Result<UnminedTxId, MempoolError> {
227        // # Security
228        //
229        // This method must call `reject`, rather than modifying the rejection lists directly.
230        let unmined_tx_id = tx.transaction.id;
231        let tx_id = unmined_tx_id.mined_id();
232
233        // First, check if we have a cached rejection for this transaction.
234        if let Some(error) = self.rejection_error(&unmined_tx_id) {
235            tracing::trace!(
236                ?tx_id,
237                ?error,
238                stored_transaction_count = ?self.verified.transaction_count(),
239                "returning cached error for transaction",
240            );
241
242            return Err(error);
243        }
244
245        // If `tx` is already in the mempool, we don't change anything.
246        //
247        // Security: transactions must not get refreshed by new queries,
248        // because that allows malicious peers to keep transactions live forever.
249        if self.verified.contains(&tx_id) {
250            tracing::trace!(
251                ?tx_id,
252                stored_transaction_count = ?self.verified.transaction_count(),
253                "returning InMempool error for transaction that is already in the mempool",
254            );
255
256            return Err(MempoolError::InMempool);
257        }
258
259        // Then, we try to insert into the pool. If this fails the transaction is rejected.
260        let mut result = Ok(unmined_tx_id);
261        if let Err(rejection_error) = self.verified.insert(
262            tx,
263            spent_mempool_outpoints,
264            &mut self.pending_outputs,
265            height,
266        ) {
267            tracing::debug!(
268                ?tx_id,
269                ?rejection_error,
270                stored_transaction_count = ?self.verified.transaction_count(),
271                "insertion error for transaction",
272            );
273
274            // We could return here, but we still want to check the mempool size
275            self.reject(unmined_tx_id, rejection_error.clone().into());
276            result = Err(rejection_error.into());
277        }
278
279        // Once inserted, we evict transactions over the pool size limit per [ZIP-401];
280        //
281        // > On receiving a transaction: (...)
282        // > Calculate its cost. If the total cost of transactions in the mempool including this
283        // > one would `exceed mempooltxcostlimit`, then the node MUST repeatedly call
284        // > EvictTransaction (with the new transaction included as a candidate to evict) until the
285        // > total cost does not exceed `mempooltxcostlimit`.
286        //
287        // 'EvictTransaction' is equivalent to [`VerifiedSet::evict_one()`] in
288        // our implementation.
289        //
290        // [ZIP-401]: https://zips.z.cash/zip-0401
291        while self.verified.total_cost() > self.tx_cost_limit {
292            // > EvictTransaction MUST do the following:
293            // > Select a random transaction to evict, with probability in direct proportion to
294            // > eviction weight. (...) Remove it from the mempool.
295            let victim_tx = self
296                .verified
297                .evict_one()
298                .expect("mempool is empty, but was expected to be full");
299
300            // > Add the txid and the current time to RecentlyEvicted, dropping the oldest entry in
301            // > RecentlyEvicted if necessary to keep it to at most `eviction_memory_entries entries`.
302            self.reject(
303                victim_tx.transaction.id,
304                SameEffectsChainRejectionError::RandomlyEvicted.into(),
305            );
306
307            // If this transaction gets evicted, set its result to the same error
308            if victim_tx.transaction.id == unmined_tx_id {
309                result = Err(SameEffectsChainRejectionError::RandomlyEvicted.into());
310            }
311        }
312
313        result
314    }
315
316    /// Remove transactions from the mempool via exact [`UnminedTxId`].
317    ///
318    /// For v5 transactions, transactions are matched by WTXID, using both the:
319    /// - non-malleable transaction ID, and
320    /// - authorizing data hash.
321    ///
322    /// This matches the exact transaction, with identical blockchain effects, signatures, and proofs.
323    ///
324    /// Returns the number of transactions which were removed.
325    ///
326    /// Removes from the 'verified' set, if present.
327    /// Maintains the order in which the other unmined transactions have been inserted into the mempool.
328    ///
329    /// Does not add or remove from the 'rejected' tracking set.
330    #[allow(dead_code)]
331    pub fn remove_exact(&mut self, exact_wtxids: &HashSet<UnminedTxId>) -> usize {
332        self.verified
333            .remove_all_that(|tx| exact_wtxids.contains(&tx.transaction.id))
334            .len()
335    }
336
337    /// Clears a list of mined transaction ids from the verified set's tracked transaction dependencies.
338    pub fn clear_mined_dependencies(&mut self, mined_ids: &HashSet<transaction::Hash>) {
339        self.verified.clear_mined_dependencies(mined_ids);
340    }
341
342    /// Reject and remove transactions from the mempool via non-malleable [`transaction::Hash`].
343    /// - For v5 transactions, transactions are matched by TXID,
344    ///   using only the non-malleable transaction ID.
345    ///   This matches any transaction with the same effect on the blockchain state,
346    ///   even if its signatures and proofs are different.
347    /// - Returns the number of transactions which were removed.
348    /// - Removes from the 'verified' set, if present.
349    ///   Maintains the order in which the other unmined transactions have been inserted into the mempool.
350    /// - Prunes `pending_outputs` of any closed channels.
351    ///
352    /// Reject and remove transactions from the mempool that contain any spent outpoints or revealed
353    /// nullifiers from the passed in `transactions`.
354    ///
355    /// Returns the number of transactions that were removed.
356    pub fn reject_and_remove_same_effects(
357        &mut self,
358        mined_ids: &HashSet<transaction::Hash>,
359        transactions: Vec<Arc<Transaction>>,
360    ) -> RemovedTransactionIds {
361        let removed_mined = self
362            .verified
363            .remove_all_that(|tx| mined_ids.contains(&tx.transaction.id.mined_id()));
364
365        let spent_outpoints: HashSet<_> = transactions
366            .iter()
367            .flat_map(|tx| tx.spent_outpoints())
368            .collect();
369        let sprout_nullifiers: HashSet<_> = transactions
370            .iter()
371            .flat_map(|transaction| transaction.sprout_nullifiers())
372            .collect();
373        let sapling_nullifiers: HashSet<_> = transactions
374            .iter()
375            .flat_map(|transaction| transaction.sapling_nullifiers())
376            .collect();
377        let orchard_nullifiers: HashSet<_> = transactions
378            .iter()
379            .flat_map(|transaction| transaction.orchard_nullifiers())
380            .collect();
381
382        let duplicate_spend_ids: HashSet<_> = self
383            .verified
384            .transactions()
385            .values()
386            .map(|tx| (tx.transaction.id, &tx.transaction.transaction))
387            .filter_map(|(tx_id, tx)| {
388                (tx.spent_outpoints()
389                    .any(|outpoint| spent_outpoints.contains(&outpoint))
390                    || tx
391                        .sprout_nullifiers()
392                        .any(|nullifier| sprout_nullifiers.contains(nullifier))
393                    || tx
394                        .sapling_nullifiers()
395                        .any(|nullifier| sapling_nullifiers.contains(nullifier))
396                    || tx
397                        .orchard_nullifiers()
398                        .any(|nullifier| orchard_nullifiers.contains(nullifier)))
399                .then_some(tx_id)
400            })
401            .collect();
402
403        let removed_duplicate_spend = self
404            .verified
405            .remove_all_that(|tx| duplicate_spend_ids.contains(&tx.transaction.id));
406
407        for &mined_id in mined_ids {
408            self.reject(
409                // the reject and rejection_error fns that store and check `SameEffectsChainRejectionError`s
410                // only use the mined id, so using `Legacy` ids will apply to v5 transactions as well.
411                UnminedTxId::Legacy(mined_id),
412                SameEffectsChainRejectionError::Mined.into(),
413            );
414        }
415
416        for duplicate_spend_id in duplicate_spend_ids {
417            self.reject(
418                duplicate_spend_id,
419                SameEffectsChainRejectionError::DuplicateSpend.into(),
420            );
421        }
422
423        self.pending_outputs.prune();
424
425        RemovedTransactionIds {
426            mined: removed_mined,
427            invalidated: removed_duplicate_spend,
428        }
429    }
430
431    /// Clears the whole mempool storage.
432    #[allow(dead_code)]
433    pub fn clear(&mut self) {
434        self.verified.clear();
435        self.tip_rejected_exact.clear();
436        self.pending_outputs.clear();
437        self.tip_rejected_same_effects.clear();
438        self.chain_rejected_same_effects.clear();
439        self.update_rejected_metrics();
440    }
441
442    /// Clears rejections that only apply to the current tip.
443    pub fn clear_tip_rejections(&mut self) {
444        self.tip_rejected_exact.clear();
445        self.tip_rejected_same_effects.clear();
446        self.update_rejected_metrics();
447    }
448
449    /// Clears rejections that only apply to the current tip.
450    ///
451    /// # Security
452    ///
453    /// This method must be called at the end of every method that adds rejections.
454    /// Otherwise, peers could make our reject lists use a lot of RAM.
455    fn limit_rejection_list_memory(&mut self) {
456        // These lists are an optimisation - it's ok to totally clear them as needed.
457        if self.tip_rejected_exact.len() > MAX_EVICTION_MEMORY_ENTRIES {
458            self.tip_rejected_exact.clear();
459        }
460        if self.tip_rejected_same_effects.len() > MAX_EVICTION_MEMORY_ENTRIES {
461            self.tip_rejected_same_effects.clear();
462        }
463        // `chain_rejected_same_effects` limits its size by itself
464        self.update_rejected_metrics();
465    }
466
467    /// Returns the set of [`UnminedTxId`]s in the mempool.
468    pub fn tx_ids(&self) -> impl Iterator<Item = UnminedTxId> + '_ {
469        self.transactions().values().map(|tx| tx.transaction.id)
470    }
471
472    /// Returns a reference to the [`HashMap`] of [`VerifiedUnminedTx`]s in the verified set.
473    ///
474    /// Each [`VerifiedUnminedTx`] contains an [`UnminedTx`],
475    /// and adds extra fields from the transaction verifier result.
476    pub fn transactions(&self) -> &HashMap<transaction::Hash, VerifiedUnminedTx> {
477        self.verified.transactions()
478    }
479
480    /// Returns a reference to the [`TransactionDependencies`] in the verified set.
481    pub fn transaction_dependencies(&self) -> &TransactionDependencies {
482        self.verified.transaction_dependencies()
483    }
484
485    /// Returns a [`transparent::Output`] created by a mempool transaction for the provided
486    /// [`transparent::OutPoint`] if one exists, or None otherwise.
487    pub fn created_output(&self, outpoint: &transparent::OutPoint) -> Option<transparent::Output> {
488        self.verified.created_output(outpoint)
489    }
490
491    /// Returns the number of transactions in the mempool.
492    #[allow(dead_code)]
493    pub fn transaction_count(&self) -> usize {
494        self.verified.transaction_count()
495    }
496
497    /// Returns the cost of the transactions in the mempool, according to ZIP-401.
498    #[allow(dead_code)]
499    pub fn total_cost(&self) -> u64 {
500        self.verified.total_cost()
501    }
502
503    /// Returns the total serialized size of the verified transactions in the set.
504    ///
505    /// See [`VerifiedSet::total_serialized_size()`] for details.
506    pub fn total_serialized_size(&self) -> usize {
507        self.verified.total_serialized_size()
508    }
509
510    /// Returns the set of [`UnminedTx`]es with exactly matching `tx_ids` in the
511    /// mempool.
512    ///
513    /// This matches the exact transaction, with identical blockchain effects,
514    /// signatures, and proofs.
515    pub fn transactions_exact(
516        &self,
517        tx_ids: HashSet<UnminedTxId>,
518    ) -> impl Iterator<Item = &UnminedTx> {
519        tx_ids.into_iter().filter_map(|tx_id| {
520            self.transactions()
521                .get(&tx_id.mined_id())
522                .map(|tx| &tx.transaction)
523        })
524    }
525
526    /// Returns the set of [`UnminedTx`]es with matching [`transaction::Hash`]es
527    /// in the mempool.
528    ///
529    /// This matches transactions with the same effects, regardless of
530    /// [`transaction::AuthDigest`].
531    pub fn transactions_same_effects(
532        &self,
533        tx_ids: HashSet<Hash>,
534    ) -> impl Iterator<Item = &UnminedTx> {
535        self.verified
536            .transactions()
537            .iter()
538            .filter(move |(tx_id, _)| tx_ids.contains(tx_id))
539            .map(|(_, tx)| &tx.transaction)
540    }
541
542    /// Returns a transaction and the transaction ids of its dependencies, if it is in the verified set.
543    pub fn transaction_with_deps(
544        &self,
545        tx_id: transaction::Hash,
546    ) -> Option<(VerifiedUnminedTx, HashSet<transaction::Hash>)> {
547        let tx = self.verified.transactions().get(&tx_id).cloned()?;
548        let deps = self
549            .verified
550            .transaction_dependencies()
551            .dependencies()
552            .get(&tx_id)
553            .cloned()
554            .unwrap_or_default();
555
556        Some((tx, deps))
557    }
558
559    /// Returns `true` if a transaction exactly matching an [`UnminedTxId`] is in
560    /// the mempool.
561    ///
562    /// This matches the exact transaction, with identical blockchain effects,
563    /// signatures, and proofs.
564    pub fn contains_transaction_exact(&self, tx_id: &transaction::Hash) -> bool {
565        self.verified.contains(tx_id)
566    }
567
568    /// Returns the number of rejected [`UnminedTxId`]s or [`transaction::Hash`]es.
569    ///
570    /// Transactions on multiple rejected lists are counted multiple times.
571    #[allow(dead_code)]
572    pub fn rejected_transaction_count(&mut self) -> usize {
573        self.tip_rejected_exact.len()
574            + self.tip_rejected_same_effects.len()
575            + self
576                .chain_rejected_same_effects
577                .iter_mut()
578                .map(|(_, map)| map.len())
579                .sum::<usize>()
580    }
581
582    /// Add a transaction to the rejected list for the given reason.
583    pub fn reject(&mut self, tx_id: UnminedTxId, reason: RejectionError) {
584        match reason {
585            RejectionError::ExactTip(e) => {
586                self.tip_rejected_exact.insert(tx_id, e);
587            }
588            RejectionError::SameEffectsTip(e) => {
589                self.tip_rejected_same_effects.insert(tx_id.mined_id(), e);
590            }
591            RejectionError::SameEffectsChain(e) => {
592                let eviction_memory_time = self.eviction_memory_time;
593                self.chain_rejected_same_effects
594                    .entry(e)
595                    .or_insert_with(|| {
596                        EvictionList::new(MAX_EVICTION_MEMORY_ENTRIES, eviction_memory_time)
597                    })
598                    .insert(tx_id.mined_id());
599            }
600        }
601        self.limit_rejection_list_memory();
602    }
603
604    /// Returns the rejection error if a transaction matching an [`UnminedTxId`]
605    /// is in any mempool rejected list.
606    ///
607    /// This matches transactions based on each rejection list's matching rule.
608    ///
609    /// Returns an arbitrary error if the transaction is in multiple lists.
610    pub fn rejection_error(&self, txid: &UnminedTxId) -> Option<MempoolError> {
611        if let Some(error) = self.tip_rejected_exact.get(txid) {
612            return Some(error.clone().into());
613        }
614
615        if let Some(error) = self.tip_rejected_same_effects.get(&txid.mined_id()) {
616            return Some(error.clone().into());
617        }
618
619        for (error, set) in self.chain_rejected_same_effects.iter() {
620            if set.contains_key(&txid.mined_id()) {
621                return Some(error.clone().into());
622            }
623        }
624
625        None
626    }
627
628    /// Returns the set of [`UnminedTxId`]s matching `tx_ids` in the rejected list.
629    ///
630    /// This matches transactions based on each rejection list's matching rule.
631    pub fn rejected_transactions(
632        &self,
633        tx_ids: HashSet<UnminedTxId>,
634    ) -> impl Iterator<Item = UnminedTxId> + '_ {
635        tx_ids
636            .into_iter()
637            .filter(move |txid| self.contains_rejected(txid))
638    }
639
640    /// Returns `true` if a transaction matching the supplied [`UnminedTxId`] is in
641    /// the mempool rejected list.
642    ///
643    /// This matches transactions based on each rejection list's matching rule.
644    pub fn contains_rejected(&self, txid: &UnminedTxId) -> bool {
645        self.rejection_error(txid).is_some()
646    }
647
648    /// Add a transaction that failed download and verification to the rejected list
649    /// if needed, depending on the reason for the failure.
650    pub fn reject_if_needed(&mut self, tx_id: UnminedTxId, e: TransactionDownloadVerifyError) {
651        match e {
652            // Rejecting a transaction already in state would speed up further
653            // download attempts without checking the state. However it would
654            // make the reject list grow forever.
655            //
656            // TODO: revisit after reviewing the rejected list cleanup criteria?
657            // TODO: if we decide to reject it, then we need to pass the block hash
658            // to State::Confirmed. This would require the zs::Response::Transaction
659            // to include the hash, which would need to be implemented.
660            TransactionDownloadVerifyError::InState |
661            // An unknown error in the state service, better do nothing
662            TransactionDownloadVerifyError::StateError(_) |
663            // If download failed, do nothing; the crawler will end up trying to
664            // download it again.
665            TransactionDownloadVerifyError::DownloadFailed(_) |
666            // If it was cancelled then a block was mined, or there was a network
667            // upgrade, etc. No reason to reject it.
668            TransactionDownloadVerifyError::Cancelled => {}
669
670            // Consensus verification failed. Reject transaction to avoid
671            // having to download and verify it again just for it to fail again.
672            TransactionDownloadVerifyError::Invalid { error, .. }  => {
673                self.reject(tx_id, ExactTipRejectionError::FailedVerification(error).into())
674            }
675        }
676    }
677
678    /// Remove transactions from the mempool if they have not been mined after a
679    /// specified height, per [ZIP-203].
680    ///
681    /// > Transactions will have a new field, nExpiryHeight, which will set the
682    /// > block height after which transactions will be removed from the mempool
683    /// > if they have not been mined.
684    ///
685    ///
686    /// [ZIP-203]: https://zips.z.cash/zip-0203#specification
687    pub fn remove_expired_transactions(
688        &mut self,
689        tip_height: zebra_chain::block::Height,
690    ) -> HashSet<UnminedTxId> {
691        let mut tx_ids = HashSet::new();
692        let mut unmined_tx_ids = HashSet::new();
693
694        for (&tx_id, tx) in self.transactions() {
695            if let Some(expiry_height) = tx.transaction.transaction.expiry_height() {
696                if tip_height >= expiry_height {
697                    tx_ids.insert(tx_id);
698                    unmined_tx_ids.insert(tx.transaction.id);
699                }
700            }
701        }
702
703        // expiry height is effecting data, so we match by non-malleable TXID
704        self.verified
705            .remove_all_that(|tx| tx_ids.contains(&tx.transaction.id.mined_id()));
706
707        // also reject it
708        for id in tx_ids {
709            self.reject(
710                // It's okay to omit the auth digest here as we know that `reject()` will always
711                // use mined ids for `SameEffectsChainRejectionError`s.
712                UnminedTxId::Legacy(id),
713                SameEffectsChainRejectionError::Expired.into(),
714            );
715        }
716
717        unmined_tx_ids
718    }
719
720    /// Check if transaction should be downloaded and/or verified.
721    ///
722    /// If it is already in the mempool (or in its rejected list)
723    /// then it shouldn't be downloaded/verified.
724    pub fn should_download_or_verify(&mut self, txid: UnminedTxId) -> Result<(), MempoolError> {
725        // Check if the transaction is already in the mempool.
726        if self.contains_transaction_exact(&txid.mined_id()) {
727            return Err(MempoolError::InMempool);
728        }
729        if let Some(error) = self.rejection_error(&txid) {
730            return Err(error);
731        }
732        Ok(())
733    }
734
735    /// Update metrics related to the rejected lists.
736    ///
737    /// Must be called every time the rejected lists change.
738    fn update_rejected_metrics(&mut self) {
739        metrics::gauge!("mempool.rejected.transaction.ids",)
740            .set(self.rejected_transaction_count() as f64);
741        // This is just an approximation.
742        // TODO: make it more accurate #2869
743        let item_size = size_of::<(transaction::Hash, SameEffectsTipRejectionError)>();
744        metrics::gauge!("mempool.rejected.transaction.ids.bytes",)
745            .set((self.rejected_transaction_count() * item_size) as f64);
746    }
747}