1//! The set of verified transactions in the mempool.
23use std::{
4 borrow::Cow,
5 collections::{HashMap, HashSet},
6 hash::Hash,
7};
89use zebra_chain::{
10 block::Height,
11 orchard, sapling, sprout,
12 transaction::{self, UnminedTx, UnminedTxId, VerifiedUnminedTx},
13 transparent,
14};
15use zebra_node_services::mempool::TransactionDependencies;
1617use crate::components::mempool::pending_outputs::PendingOutputs;
1819use super::super::SameEffectsTipRejectionError;
2021// Imports for doc links
22#[allow(unused_imports)]
23use zebra_chain::transaction::MEMPOOL_TRANSACTION_COST_THRESHOLD;
2425/// 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.
39transactions: HashMap<transaction::Hash, VerifiedUnminedTx>,
4041/// A map of dependencies between transactions in the mempool that
42 /// spend or create outputs of other transactions in the mempool.
43transaction_dependencies: TransactionDependencies,
4445/// The [`transparent::Output`]s created by verified transactions in the mempool.
46 ///
47 /// These outputs may be spent by other transactions in the mempool.
48created_outputs: HashMap<transparent::OutPoint, transparent::Output>,
4950/// The total size of the transactions in the mempool if they were
51 /// serialized.
52transactions_serialized_size: usize,
5354/// The total cost of the verified transactions in the set.
55total_cost: u64,
5657/// The set of spent out points by the verified transactions.
58spent_outpoints: HashSet<transparent::OutPoint>,
5960/// The set of revealed Sprout nullifiers.
61sprout_nullifiers: HashSet<sprout::Nullifier>,
6263/// The set of revealed Sapling nullifiers.
64sapling_nullifiers: HashSet<sapling::Nullifier>,
6566/// The set of revealed Orchard nullifiers.
67orchard_nullifiers: HashSet<orchard::Nullifier>,
68}
6970impl Drop for VerifiedSet {
71fn drop(&mut self) {
72// zero the metrics on drop
73self.clear()
74 }
75}
7677impl VerifiedSet {
78/// Returns a reference to the [`HashMap`] of [`VerifiedUnminedTx`]s in the set.
79pub fn transactions(&self) -> &HashMap<transaction::Hash, VerifiedUnminedTx> {
80&self.transactions
81 }
8283/// Returns a reference to the [`TransactionDependencies`] in the set.
84pub fn transaction_dependencies(&self) -> &TransactionDependencies {
85&self.transaction_dependencies
86 }
8788/// Returns a [`transparent::Output`] created by a mempool transaction for the provided
89 /// [`transparent::OutPoint`] if one exists, or None otherwise.
90pub fn created_output(&self, outpoint: &transparent::OutPoint) -> Option<transparent::Output> {
91self.created_outputs.get(outpoint).cloned()
92 }
9394/// Returns the number of verified transactions in the set.
95pub fn transaction_count(&self) -> usize {
96self.transactions.len()
97 }
9899/// Returns the total cost of the verified transactions in the set.
100 ///
101 /// [ZIP-401]: https://zips.z.cash/zip-0401
102pub fn total_cost(&self) -> u64 {
103self.total_cost
104 }
105106/// 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`].
110pub fn total_serialized_size(&self) -> usize {
111self.transactions_serialized_size
112 }
113114/// Returns `true` if the set of verified transactions contains the transaction with the
115 /// specified [`transaction::Hash`].
116pub fn contains(&self, id: &transaction::Hash) -> bool {
117self.transactions.contains_key(id)
118 }
119120/// Clear the set of verified transactions.
121 ///
122 /// Also clears all internal caches.
123pub fn clear(&mut self) {
124self.transactions.clear();
125self.transaction_dependencies.clear();
126self.spent_outpoints.clear();
127self.sprout_nullifiers.clear();
128self.sapling_nullifiers.clear();
129self.orchard_nullifiers.clear();
130self.created_outputs.clear();
131self.transactions_serialized_size = 0;
132self.total_cost = 0;
133self.update_metrics();
134 }
135136/// 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.
143pub fn insert(
144&mut self,
145mut transaction: VerifiedUnminedTx,
146 spent_mempool_outpoints: Vec<transparent::OutPoint>,
147 pending_outputs: &mut PendingOutputs,
148 height: Option<Height>,
149 ) -> Result<(), SameEffectsTipRejectionError> {
150if self.has_spend_conflicts(&transaction.transaction) {
151return Err(SameEffectsTipRejectionError::SpendConflict);
152 }
153154// 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.
157for outpoint in &spent_mempool_outpoints {
158if !self.created_outputs.contains_key(outpoint) {
159return Err(SameEffectsTipRejectionError::MissingOutput);
160 }
161 }
162163let tx_id = transaction.transaction.id.mined_id();
164self.transaction_dependencies
165 .add(tx_id, spent_mempool_outpoints);
166167// Inserts the transaction's outputs into the internal caches and responds to pending output requests.
168let tx = &transaction.transaction.transaction;
169for (index, output) in tx.outputs().iter().cloned().enumerate() {
170let outpoint = transparent::OutPoint::from_usize(tx_id, index);
171self.created_outputs.insert(outpoint, output.clone());
172 pending_outputs.respond(&outpoint, output)
173 }
174self.spent_outpoints.extend(tx.spent_outpoints());
175self.sprout_nullifiers.extend(tx.sprout_nullifiers());
176self.sapling_nullifiers.extend(tx.sapling_nullifiers());
177self.orchard_nullifiers.extend(tx.orchard_nullifiers());
178179self.transactions_serialized_size += transaction.transaction.size;
180self.total_cost += transaction.cost();
181 transaction.time = Some(chrono::Utc::now());
182 transaction.height = height;
183self.transactions.insert(tx_id, transaction);
184185self.update_metrics();
186187Ok(())
188 }
189190/// 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)]
213pub fn evict_one(&mut self) -> Option<VerifiedUnminedTx> {
214use rand::distributions::{Distribution, WeightedIndex};
215use rand::prelude::thread_rng;
216217let (keys, weights): (Vec<transaction::Hash>, Vec<u64>) = self
218.transactions
219 .iter()
220 .map(|(&tx_id, tx)| (tx_id, tx.eviction_weight()))
221 .unzip();
222223let dist = WeightedIndex::new(weights).expect(
224"there is at least one weight, all weights are non-negative, and the total is positive",
225 );
226227let key_to_remove = keys
228 .get(dist.sample(&mut thread_rng()))
229 .expect("should have a key at every index in the distribution");
230231// Removes the randomly selected transaction and all of its dependents from the set,
232 // then returns just the randomly selected transaction
233self.remove(key_to_remove).pop()
234 }
235236/// Clears a list of mined transaction ids from the lists of dependencies for
237 /// any other transactions in the mempool and removes their dependents.
238pub fn clear_mined_dependencies(&mut self, mined_ids: &HashSet<transaction::Hash>) {
239self.transaction_dependencies
240 .clear_mined_dependencies(mined_ids);
241 }
242243/// Removes all transactions in the set that match the `predicate`.
244 ///
245 /// Returns the amount of transactions removed.
246pub fn remove_all_that(
247&mut self,
248 predicate: impl Fn(&VerifiedUnminedTx) -> bool,
249 ) -> HashSet<UnminedTxId> {
250let keys_to_remove: Vec<_> = self
251.transactions
252 .iter()
253 .filter_map(|(&tx_id, tx)| predicate(tx).then_some(tx_id))
254 .collect();
255256let mut removed_transactions = HashSet::new();
257258for key_to_remove in keys_to_remove {
259 removed_transactions.extend(
260self.remove(&key_to_remove)
261 .into_iter()
262 .map(|tx| tx.transaction.id),
263 );
264 }
265266 removed_transactions
267 }
268269/// Accepts a transaction id for a transaction to remove from the verified set.
270 ///
271 /// Removes the transaction and any transactions that directly or indirectly
272 /// depend on it from the set.
273 ///
274 /// Returns a list of transactions that have been removed with the target transaction
275 /// as the last item.
276 ///
277 /// Also removes the outputs of any removed transactions from the internal caches.
278fn remove(&mut self, key_to_remove: &transaction::Hash) -> Vec<VerifiedUnminedTx> {
279let removed_transactions: Vec<_> = self
280.transaction_dependencies
281 .remove_all(key_to_remove)
282 .iter()
283 .chain(std::iter::once(key_to_remove))
284 .map(|key_to_remove| {
285let removed_tx = self
286.transactions
287 .remove(key_to_remove)
288 .expect("invalid transaction key");
289290self.transactions_serialized_size -= removed_tx.transaction.size;
291self.total_cost -= removed_tx.cost();
292self.remove_outputs(&removed_tx.transaction);
293294 removed_tx
295 })
296 .collect();
297298self.update_metrics();
299 removed_transactions
300 }
301302/// Returns `true` if the given `transaction` has any spend conflicts with transactions in the
303 /// mempool.
304 ///
305 /// Two transactions have a spend conflict if they spend the same UTXO or if they reveal the
306 /// same nullifier.
307fn has_spend_conflicts(&self, unmined_tx: &UnminedTx) -> bool {
308let tx = &unmined_tx.transaction;
309310Self::has_conflicts(&self.spent_outpoints, tx.spent_outpoints())
311 || Self::has_conflicts(&self.sprout_nullifiers, tx.sprout_nullifiers().copied())
312 || Self::has_conflicts(&self.sapling_nullifiers, tx.sapling_nullifiers().copied())
313 || Self::has_conflicts(&self.orchard_nullifiers, tx.orchard_nullifiers().copied())
314 }
315316/// Removes the tracked transaction outputs from the mempool.
317fn remove_outputs(&mut self, unmined_tx: &UnminedTx) {
318let tx = &unmined_tx.transaction;
319320for index in 0..tx.outputs().len() {
321self.created_outputs
322 .remove(&transparent::OutPoint::from_usize(
323 unmined_tx.id.mined_id(),
324 index,
325 ));
326 }
327328let spent_outpoints = tx.spent_outpoints().map(Cow::Owned);
329let sprout_nullifiers = tx.sprout_nullifiers().map(Cow::Borrowed);
330let sapling_nullifiers = tx.sapling_nullifiers().map(Cow::Borrowed);
331let orchard_nullifiers = tx.orchard_nullifiers().map(Cow::Borrowed);
332333Self::remove_from_set(&mut self.spent_outpoints, spent_outpoints);
334Self::remove_from_set(&mut self.sprout_nullifiers, sprout_nullifiers);
335Self::remove_from_set(&mut self.sapling_nullifiers, sapling_nullifiers);
336Self::remove_from_set(&mut self.orchard_nullifiers, orchard_nullifiers);
337 }
338339/// Returns `true` if the two sets have common items.
340fn has_conflicts<T>(set: &HashSet<T>, mut list: impl Iterator<Item = T>) -> bool
341where
342T: Eq + Hash,
343 {
344 list.any(|item| set.contains(&item))
345 }
346347/// Removes some items from a [`HashSet`].
348 ///
349 /// Each item in the list of `items` should be wrapped in a [`Cow`]. This allows this generic
350 /// method to support both borrowed and owned items.
351fn remove_from_set<'t, T>(set: &mut HashSet<T>, items: impl IntoIterator<Item = Cow<'t, T>>)
352where
353T: Clone + Eq + Hash + 't,
354 {
355for item in items {
356 set.remove(&item);
357 }
358 }
359360fn update_metrics(&mut self) {
361// Track the sum of unpaid actions within each transaction (as they are subject to the
362 // unpaid action limit). Transactions that have weight >= 1 have no unpaid actions by
363 // definition.
364let mut unpaid_actions_with_weight_lt20pct = 0;
365let mut unpaid_actions_with_weight_lt40pct = 0;
366let mut unpaid_actions_with_weight_lt60pct = 0;
367let mut unpaid_actions_with_weight_lt80pct = 0;
368let mut unpaid_actions_with_weight_lt1 = 0;
369370// Track the total number of paid actions across all transactions in the mempool. This
371 // added to the bucketed unpaid actions above is equal to the total number of conventional
372 // actions in the mempool.
373let mut paid_actions = 0;
374375// Track the sum of transaction sizes (the metric by which they are mainly limited) across
376 // several buckets.
377let mut size_with_weight_lt1 = 0;
378let mut size_with_weight_eq1 = 0;
379let mut size_with_weight_gt1 = 0;
380let mut size_with_weight_gt2 = 0;
381let mut size_with_weight_gt3 = 0;
382383for entry in self.transactions().values() {
384 paid_actions += entry.conventional_actions - entry.unpaid_actions;
385386if entry.fee_weight_ratio > 3.0 {
387 size_with_weight_gt3 += entry.transaction.size;
388 } else if entry.fee_weight_ratio > 2.0 {
389 size_with_weight_gt2 += entry.transaction.size;
390 } else if entry.fee_weight_ratio > 1.0 {
391 size_with_weight_gt1 += entry.transaction.size;
392 } else if entry.fee_weight_ratio == 1.0 {
393 size_with_weight_eq1 += entry.transaction.size;
394 } else {
395 size_with_weight_lt1 += entry.transaction.size;
396if entry.fee_weight_ratio < 0.2 {
397 unpaid_actions_with_weight_lt20pct += entry.unpaid_actions;
398 } else if entry.fee_weight_ratio < 0.4 {
399 unpaid_actions_with_weight_lt40pct += entry.unpaid_actions;
400 } else if entry.fee_weight_ratio < 0.6 {
401 unpaid_actions_with_weight_lt60pct += entry.unpaid_actions;
402 } else if entry.fee_weight_ratio < 0.8 {
403 unpaid_actions_with_weight_lt80pct += entry.unpaid_actions;
404 } else {
405 unpaid_actions_with_weight_lt1 += entry.unpaid_actions;
406 }
407 }
408 }
409410metrics::gauge!(
411"zcash.mempool.actions.unpaid",
412"bk" => "< 0.2",
413 )
414 .set(unpaid_actions_with_weight_lt20pct as f64);
415metrics::gauge!(
416"zcash.mempool.actions.unpaid",
417"bk" => "< 0.4",
418 )
419 .set(unpaid_actions_with_weight_lt40pct as f64);
420metrics::gauge!(
421"zcash.mempool.actions.unpaid",
422"bk" => "< 0.6",
423 )
424 .set(unpaid_actions_with_weight_lt60pct as f64);
425metrics::gauge!(
426"zcash.mempool.actions.unpaid",
427"bk" => "< 0.8",
428 )
429 .set(unpaid_actions_with_weight_lt80pct as f64);
430metrics::gauge!(
431"zcash.mempool.actions.unpaid",
432"bk" => "< 1",
433 )
434 .set(unpaid_actions_with_weight_lt1 as f64);
435metrics::gauge!("zcash.mempool.actions.paid").set(paid_actions as f64);
436metrics::gauge!("zcash.mempool.size.transactions",).set(self.transaction_count() as f64);
437metrics::gauge!(
438"zcash.mempool.size.weighted",
439"bk" => "< 1",
440 )
441 .set(size_with_weight_lt1 as f64);
442metrics::gauge!(
443"zcash.mempool.size.weighted",
444"bk" => "1",
445 )
446 .set(size_with_weight_eq1 as f64);
447metrics::gauge!(
448"zcash.mempool.size.weighted",
449"bk" => "> 1",
450 )
451 .set(size_with_weight_gt1 as f64);
452metrics::gauge!(
453"zcash.mempool.size.weighted",
454"bk" => "> 2",
455 )
456 .set(size_with_weight_gt2 as f64);
457metrics::gauge!(
458"zcash.mempool.size.weighted",
459"bk" => "> 3",
460 )
461 .set(size_with_weight_gt3 as f64);
462metrics::gauge!("zcash.mempool.size.bytes",).set(self.transactions_serialized_size as f64);
463metrics::gauge!("zcash.mempool.cost.bytes").set(self.total_cost as f64);
464 }
465}