zebra_state/service/
non_finalized_state.rs

1//! Non-finalized chain state management as defined by [RFC0005]
2//!
3//! [RFC0005]: https://zebra.zfnd.org/dev/rfcs/0005-state-updates.html
4
5use std::{
6    collections::{BTreeSet, HashMap},
7    mem,
8    path::PathBuf,
9    sync::Arc,
10};
11
12use indexmap::IndexMap;
13use tokio::sync::watch;
14use zebra_chain::{
15    block::{self, Block, Hash, Height},
16    parameters::Network,
17    sprout::{self},
18    transparent,
19};
20
21use crate::{
22    constants::{MAX_INVALIDATED_BLOCKS, MAX_NON_FINALIZED_CHAIN_FORKS},
23    error::ReconsiderError,
24    request::{ContextuallyVerifiedBlock, FinalizableBlock},
25    service::{check, finalized_state::ZebraDb},
26    BoxError, SemanticallyVerifiedBlock, ValidateContextError, WatchReceiver,
27};
28
29mod backup;
30mod chain;
31
32#[cfg(test)]
33pub(crate) use backup::MIN_DURATION_BETWEEN_BACKUP_UPDATES;
34
35#[cfg(test)]
36mod tests;
37
38pub(crate) use chain::{Chain, SpendingTransactionId};
39
40/// The state of the chains in memory, including queued blocks.
41///
42/// Clones of the non-finalized state contain independent copies of the chains.
43/// This is different from `FinalizedState::clone()`,
44/// which returns a shared reference to the database.
45///
46/// Most chain data is clone-on-write using [`Arc`].
47pub struct NonFinalizedState {
48    // Chain Data
49    //
50    /// Verified, non-finalized chains, in ascending work order.
51    ///
52    /// The best chain is [`NonFinalizedState::best_chain()`], or `chain_iter().next()`.
53    /// Using `chain_set.last()` or `chain_set.iter().next_back()` is deprecated,
54    /// callers should migrate to `chain_iter().next()`.
55    chain_set: BTreeSet<Arc<Chain>>,
56
57    /// Blocks that have been invalidated in, and removed from, the non finalized
58    /// state.
59    invalidated_blocks: IndexMap<Height, Arc<Vec<ContextuallyVerifiedBlock>>>,
60
61    // Configuration
62    //
63    /// The configured Zcash network.
64    pub network: Network,
65
66    // Diagnostics
67    //
68    /// Configures the non-finalized state to count metrics.
69    ///
70    /// Used for skipping metrics and progress bars when testing block proposals
71    /// with a commit to a cloned non-finalized state.
72    //
73    // TODO: make this field private and set it via an argument to NonFinalizedState::new()
74    should_count_metrics: bool,
75
76    /// Number of chain forks transmitter.
77    #[cfg(feature = "progress-bar")]
78    chain_count_bar: Option<howudoin::Tx>,
79
80    /// A chain fork length transmitter for each [`Chain`] in [`chain_set`](Self.chain_set).
81    ///
82    /// Because `chain_set` contains `Arc<Chain>`s, it is difficult to update the metrics state
83    /// on each chain. ([`Arc`]s are read-only, and we don't want to clone them just for metrics.)
84    #[cfg(feature = "progress-bar")]
85    chain_fork_length_bars: Vec<howudoin::Tx>,
86}
87
88impl std::fmt::Debug for NonFinalizedState {
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        let mut f = f.debug_struct("NonFinalizedState");
91
92        f.field("chain_set", &self.chain_set)
93            .field("network", &self.network);
94
95        f.field("should_count_metrics", &self.should_count_metrics);
96
97        f.finish()
98    }
99}
100
101impl Clone for NonFinalizedState {
102    fn clone(&self) -> Self {
103        Self {
104            chain_set: self.chain_set.clone(),
105            network: self.network.clone(),
106            invalidated_blocks: self.invalidated_blocks.clone(),
107            should_count_metrics: self.should_count_metrics,
108            // Don't track progress in clones.
109            #[cfg(feature = "progress-bar")]
110            chain_count_bar: None,
111            #[cfg(feature = "progress-bar")]
112            chain_fork_length_bars: Vec::new(),
113        }
114    }
115}
116
117impl NonFinalizedState {
118    /// Returns a new non-finalized state for `network`.
119    pub fn new(network: &Network) -> NonFinalizedState {
120        NonFinalizedState {
121            chain_set: Default::default(),
122            network: network.clone(),
123            invalidated_blocks: Default::default(),
124            should_count_metrics: true,
125            #[cfg(feature = "progress-bar")]
126            chain_count_bar: None,
127            #[cfg(feature = "progress-bar")]
128            chain_fork_length_bars: Vec::new(),
129        }
130    }
131
132    /// Accepts an optional path to the non-finalized state backup directory and a handle to the database.
133    ///
134    /// If a backup directory path is provided:
135    /// - Creates a new backup directory at the provided path if none exists,
136    /// - Restores non-finalized blocks from the backup directory, if any, and
137    /// - Spawns a task that updates the non-finalized backup cache with
138    ///   the latest non-finalized state sent to the returned watch channel.
139    ///
140    /// Returns the non-finalized state with a watch channel sender and receiver.
141    pub async fn with_backup(
142        self,
143        backup_dir_path: Option<PathBuf>,
144        finalized_state: &ZebraDb,
145        should_restore_backup: bool,
146    ) -> (
147        Self,
148        watch::Sender<NonFinalizedState>,
149        WatchReceiver<NonFinalizedState>,
150    ) {
151        let with_watch_channel = |non_finalized_state: NonFinalizedState| {
152            let (sender, receiver) = watch::channel(non_finalized_state.clone());
153            (non_finalized_state, sender, WatchReceiver::new(receiver))
154        };
155
156        let Some(backup_dir_path) = backup_dir_path else {
157            return with_watch_channel(self);
158        };
159
160        tracing::info!(
161            ?backup_dir_path,
162            "restoring non-finalized blocks from backup and spawning backup task"
163        );
164
165        let non_finalized_state = {
166            let backup_dir_path = backup_dir_path.clone();
167            let finalized_state = finalized_state.clone();
168            tokio::task::spawn_blocking(move || {
169                // Create a new backup directory if none exists
170                std::fs::create_dir_all(&backup_dir_path)
171                    .expect("failed to create non-finalized state backup directory");
172
173                if should_restore_backup {
174                    backup::restore_backup(self, &backup_dir_path, &finalized_state)
175                } else {
176                    self
177                }
178            })
179            .await
180            .expect("failed to join blocking task")
181        };
182
183        let (non_finalized_state, sender, receiver) = with_watch_channel(non_finalized_state);
184
185        tokio::spawn(backup::run_backup_task(receiver.clone(), backup_dir_path));
186
187        if !non_finalized_state.is_chain_set_empty() {
188            let num_blocks_restored = non_finalized_state
189                .best_chain()
190                .expect("must have best chain if chain set is not empty")
191                .len();
192
193            tracing::info!(
194                ?num_blocks_restored,
195                "restored blocks from non-finalized backup cache"
196            );
197        }
198
199        (non_finalized_state, sender, receiver)
200    }
201
202    /// Is the internal state of `self` the same as `other`?
203    ///
204    /// [`Chain`] has a custom [`Eq`] implementation based on proof of work,
205    /// which is used to select the best chain. So we can't derive [`Eq`] for [`NonFinalizedState`].
206    ///
207    /// Unlike the custom trait impl, this method returns `true` if the entire internal state
208    /// of two non-finalized states is equal.
209    ///
210    /// If the internal states are different, it returns `false`,
211    /// even if the chains and blocks are equal.
212    #[cfg(any(test, feature = "proptest-impl"))]
213    #[allow(dead_code)]
214    pub fn eq_internal_state(&self, other: &NonFinalizedState) -> bool {
215        // this method must be updated every time a consensus-critical field is added to NonFinalizedState
216        // (diagnostic fields can be ignored)
217
218        self.chain_set.len() == other.chain_set.len()
219            && self
220                .chain_set
221                .iter()
222                .zip(other.chain_set.iter())
223                .all(|(self_chain, other_chain)| self_chain.eq_internal_state(other_chain))
224            && self.network == other.network
225    }
226
227    /// Returns an iterator over the non-finalized chains, with the best chain first.
228    //
229    // TODO: replace chain_set.iter().rev() with this method
230    pub fn chain_iter(&self) -> impl Iterator<Item = &Arc<Chain>> {
231        self.chain_set.iter().rev()
232    }
233
234    /// Insert `chain` into `self.chain_set`, apply `chain_filter` to the chains,
235    /// then limit the number of tracked chains.
236    fn insert_with<F>(&mut self, chain: Arc<Chain>, chain_filter: F)
237    where
238        F: FnOnce(&mut BTreeSet<Arc<Chain>>),
239    {
240        self.chain_set.insert(chain);
241
242        chain_filter(&mut self.chain_set);
243
244        while self.chain_set.len() > MAX_NON_FINALIZED_CHAIN_FORKS {
245            // The first chain is the chain with the lowest work.
246            self.chain_set.pop_first();
247        }
248
249        self.update_metrics_bars();
250    }
251
252    /// Insert `chain` into `self.chain_set`, then limit the number of tracked chains.
253    fn insert(&mut self, chain: Arc<Chain>) {
254        self.insert_with(chain, |_ignored_chain| { /* no filter */ })
255    }
256
257    /// Finalize the lowest height block in the non-finalized portion of the best
258    /// chain and update all side-chains to match.
259    pub fn finalize(&mut self) -> FinalizableBlock {
260        // Chain::cmp uses the partial cumulative work, and the hash of the tip block.
261        // Neither of these fields has interior mutability.
262        // (And when the tip block is dropped for a chain, the chain is also dropped.)
263        #[allow(clippy::mutable_key_type)]
264        let chains = mem::take(&mut self.chain_set);
265        let mut chains = chains.into_iter();
266
267        // extract best chain
268        let mut best_chain = chains.next_back().expect("there's at least one chain");
269
270        // clone if required
271        let mut_best_chain = Arc::make_mut(&mut best_chain);
272
273        // extract the rest into side_chains so they can be mutated
274        let side_chains = chains;
275
276        // Pop the lowest height block from the best chain to be finalized, and
277        // also obtain its associated treestate.
278        let (best_chain_root, root_treestate) = mut_best_chain.pop_root();
279
280        // add best_chain back to `self.chain_set`
281        if !best_chain.is_empty() {
282            self.insert(best_chain);
283        }
284
285        // for each remaining chain in side_chains
286        for mut side_chain in side_chains.rev() {
287            if side_chain.non_finalized_root_hash() != best_chain_root.hash {
288                // If we popped the root, the chain would be empty or orphaned,
289                // so just drop it now.
290                drop(side_chain);
291
292                continue;
293            }
294
295            // otherwise, the popped root block is the same as the finalizing block
296
297            // clone if required
298            let mut_side_chain = Arc::make_mut(&mut side_chain);
299
300            // remove the first block from `chain`
301            let (side_chain_root, _treestate) = mut_side_chain.pop_root();
302            assert_eq!(side_chain_root.hash, best_chain_root.hash);
303
304            // add the chain back to `self.chain_set`
305            self.insert(side_chain);
306        }
307
308        // Remove all invalidated_blocks at or below the finalized height
309        self.invalidated_blocks
310            .retain(|height, _blocks| *height >= best_chain_root.height);
311
312        self.update_metrics_for_chains();
313
314        // Add the treestate to the finalized block.
315        FinalizableBlock::new(best_chain_root, root_treestate)
316    }
317
318    /// Commit block to the non-finalized state, on top of:
319    /// - an existing chain's tip, or
320    /// - a newly forked chain.
321    #[tracing::instrument(level = "debug", skip(self, finalized_state, prepared))]
322    pub fn commit_block(
323        &mut self,
324        prepared: SemanticallyVerifiedBlock,
325        finalized_state: &ZebraDb,
326    ) -> Result<(), ValidateContextError> {
327        let parent_hash = prepared.block.header.previous_block_hash;
328        let (height, hash) = (prepared.height, prepared.hash);
329
330        let parent_chain = self.parent_chain(parent_hash)?;
331
332        // If the block is invalid, return the error,
333        // and drop the cloned parent Arc, or newly created chain fork.
334        let modified_chain = self.validate_and_commit(parent_chain, prepared, finalized_state)?;
335
336        // If the block is valid:
337        // - add the new chain fork or updated chain to the set of recent chains
338        // - remove the parent chain, if it was in the chain set
339        //   (if it was a newly created fork, it won't be in the chain set)
340        self.insert_with(modified_chain, |chain_set| {
341            chain_set.retain(|chain| chain.non_finalized_tip_hash() != parent_hash)
342        });
343
344        self.update_metrics_for_committed_block(height, hash);
345
346        Ok(())
347    }
348
349    /// Invalidate block with hash `block_hash` and all descendants from the non-finalized state. Insert
350    /// the new chain into the chain_set and discard the previous.
351    #[allow(clippy::unwrap_in_result)]
352    pub fn invalidate_block(&mut self, block_hash: Hash) -> Result<block::Hash, BoxError> {
353        let Some(chain) = self.find_chain(|chain| chain.contains_block_hash(block_hash)) else {
354            return Err("block hash not found in any non-finalized chain".into());
355        };
356
357        let invalidated_blocks = if chain.non_finalized_root_hash() == block_hash {
358            self.chain_set.remove(&chain);
359            chain.blocks.values().cloned().collect()
360        } else {
361            let (new_chain, invalidated_blocks) = chain
362                .invalidate_block(block_hash)
363                .expect("already checked that chain contains hash");
364
365            // Add the new chain fork or updated chain to the set of recent chains, and
366            // remove the chain containing the hash of the block from chain set
367            self.insert_with(Arc::new(new_chain.clone()), |chain_set| {
368                chain_set.retain(|c| !c.contains_block_hash(block_hash))
369            });
370
371            invalidated_blocks
372        };
373
374        // TODO: Allow for invalidating multiple block hashes at a given height (#9552).
375        self.invalidated_blocks.insert(
376            invalidated_blocks
377                .first()
378                .expect("should not be empty")
379                .clone()
380                .height,
381            Arc::new(invalidated_blocks),
382        );
383
384        while self.invalidated_blocks.len() > MAX_INVALIDATED_BLOCKS {
385            self.invalidated_blocks.shift_remove_index(0);
386        }
387
388        self.update_metrics_for_chains();
389        self.update_metrics_bars();
390
391        Ok(block_hash)
392    }
393
394    /// Reconsiders a previously invalidated block and its descendants into the non-finalized state
395    /// based on a block_hash. Reconsidered blocks are inserted into the previous chain and re-inserted
396    /// into the chain_set.
397    pub fn reconsider_block(
398        &mut self,
399        block_hash: block::Hash,
400        finalized_state: &ZebraDb,
401    ) -> Result<Vec<block::Hash>, ReconsiderError> {
402        // Get the invalidated blocks that were invalidated by the given block_hash
403        let height = self
404            .invalidated_blocks
405            .iter()
406            .find_map(|(height, blocks)| {
407                if blocks.first()?.hash == block_hash {
408                    Some(height)
409                } else {
410                    None
411                }
412            })
413            .ok_or(ReconsiderError::MissingInvalidatedBlock(block_hash))?;
414
415        let invalidated_blocks = Arc::unwrap_or_clone(
416            self.invalidated_blocks
417                .clone()
418                .shift_remove(height)
419                .ok_or(ReconsiderError::MissingInvalidatedBlock(block_hash))?,
420        );
421
422        let invalidated_block_hashes = invalidated_blocks
423            .iter()
424            .map(|block| block.hash)
425            .collect::<Vec<_>>();
426
427        // Find and fork the parent chain of the invalidated_root. Update the parent chain
428        // with the invalidated_descendants
429        let invalidated_root = invalidated_blocks
430            .first()
431            .ok_or(ReconsiderError::InvalidatedBlocksEmpty)?;
432
433        let root_parent_hash = invalidated_root.block.header.previous_block_hash;
434
435        // If the parent is the tip of the finalized_state we create a new chain and insert it
436        // into the non finalized state
437        let chain_result = if root_parent_hash == finalized_state.finalized_tip_hash() {
438            let chain = Chain::new(
439                &self.network,
440                finalized_state
441                    .finalized_tip_height()
442                    .ok_or(ReconsiderError::ParentChainNotFound(block_hash))?,
443                finalized_state.sprout_tree_for_tip(),
444                finalized_state.sapling_tree_for_tip(),
445                finalized_state.orchard_tree_for_tip(),
446                finalized_state.history_tree(),
447                finalized_state.finalized_value_pool(),
448            );
449            Arc::new(chain)
450        } else {
451            // The parent is not the finalized_tip and still exist in the NonFinalizedState
452            // or else we return an error due to the parent not existing in the NonFinalizedState
453            self.parent_chain(root_parent_hash)
454                .map_err(|_| ReconsiderError::ParentChainNotFound(block_hash))?
455        };
456
457        let mut modified_chain = Arc::unwrap_or_clone(chain_result);
458        for block in invalidated_blocks {
459            modified_chain = modified_chain.push(block)?;
460        }
461
462        let (height, hash) = modified_chain.non_finalized_tip();
463
464        // Only track invalidated_blocks that are not yet finalized. Once blocks are finalized (below the best_chain_root_height)
465        // we can discard the block.
466        if let Some(best_chain_root_height) = finalized_state.finalized_tip_height() {
467            self.invalidated_blocks
468                .retain(|height, _blocks| *height >= best_chain_root_height);
469        }
470
471        self.insert_with(Arc::new(modified_chain), |chain_set| {
472            chain_set.retain(|chain| chain.non_finalized_tip_hash() != root_parent_hash)
473        });
474
475        self.update_metrics_for_committed_block(height, hash);
476
477        Ok(invalidated_block_hashes)
478    }
479
480    /// Commit block to the non-finalized state as a new chain where its parent
481    /// is the finalized tip.
482    #[tracing::instrument(level = "debug", skip(self, finalized_state, prepared))]
483    #[allow(clippy::unwrap_in_result)]
484    pub fn commit_new_chain(
485        &mut self,
486        prepared: SemanticallyVerifiedBlock,
487        finalized_state: &ZebraDb,
488    ) -> Result<(), ValidateContextError> {
489        let finalized_tip_height = finalized_state.finalized_tip_height();
490
491        // TODO: fix tests that don't initialize the finalized state
492        #[cfg(not(test))]
493        let finalized_tip_height = finalized_tip_height.expect("finalized state contains blocks");
494        #[cfg(test)]
495        let finalized_tip_height = finalized_tip_height.unwrap_or(zebra_chain::block::Height(0));
496
497        let chain = Chain::new(
498            &self.network,
499            finalized_tip_height,
500            finalized_state.sprout_tree_for_tip(),
501            finalized_state.sapling_tree_for_tip(),
502            finalized_state.orchard_tree_for_tip(),
503            finalized_state.history_tree(),
504            finalized_state.finalized_value_pool(),
505        );
506
507        let (height, hash) = (prepared.height, prepared.hash);
508
509        // If the block is invalid, return the error, and drop the newly created chain fork
510        let chain = self.validate_and_commit(Arc::new(chain), prepared, finalized_state)?;
511
512        // If the block is valid, add the new chain fork to the set of recent chains.
513        self.insert(chain);
514        self.update_metrics_for_committed_block(height, hash);
515
516        Ok(())
517    }
518
519    /// Contextually validate `prepared` using `finalized_state`.
520    /// If validation succeeds, push `prepared` onto `new_chain`.
521    ///
522    /// `new_chain` should start as a clone of the parent chain fork,
523    /// or the finalized tip.
524    #[tracing::instrument(level = "debug", skip(self, finalized_state, new_chain))]
525    fn validate_and_commit(
526        &self,
527        new_chain: Arc<Chain>,
528        prepared: SemanticallyVerifiedBlock,
529        finalized_state: &ZebraDb,
530    ) -> Result<Arc<Chain>, ValidateContextError> {
531        if self.invalidated_blocks.contains_key(&prepared.height) {
532            return Err(ValidateContextError::BlockPreviouslyInvalidated {
533                block_hash: prepared.hash,
534            });
535        }
536
537        // Reads from disk
538        //
539        // TODO: if these disk reads show up in profiles, run them in parallel, using std::thread::spawn()
540        let spent_utxos = check::utxo::transparent_spend(
541            &prepared,
542            &new_chain.unspent_utxos(),
543            &new_chain.spent_utxos,
544            finalized_state,
545        )?;
546
547        // Reads from disk
548        check::anchors::block_sapling_orchard_anchors_refer_to_final_treestates(
549            finalized_state,
550            &new_chain,
551            &prepared,
552        )?;
553
554        // Reads from disk
555        let sprout_final_treestates = check::anchors::block_fetch_sprout_final_treestates(
556            finalized_state,
557            &new_chain,
558            &prepared,
559        );
560
561        // Quick check that doesn't read from disk
562        let contextual = ContextuallyVerifiedBlock::with_block_and_spent_utxos(
563            prepared.clone(),
564            spent_utxos.clone(),
565        )
566        .map_err(|value_balance_error| {
567            ValidateContextError::CalculateBlockChainValueChange {
568                value_balance_error,
569                height: prepared.height,
570                block_hash: prepared.hash,
571                transaction_count: prepared.block.transactions.len(),
572                spent_utxo_count: spent_utxos.len(),
573            }
574        })?;
575
576        Self::validate_and_update_parallel(new_chain, contextual, sprout_final_treestates)
577    }
578
579    /// Validate `contextual` and update `new_chain`, doing CPU-intensive work in parallel batches.
580    #[allow(clippy::unwrap_in_result)]
581    #[tracing::instrument(skip(new_chain, sprout_final_treestates))]
582    fn validate_and_update_parallel(
583        new_chain: Arc<Chain>,
584        contextual: ContextuallyVerifiedBlock,
585        sprout_final_treestates: HashMap<sprout::tree::Root, Arc<sprout::tree::NoteCommitmentTree>>,
586    ) -> Result<Arc<Chain>, ValidateContextError> {
587        let mut block_commitment_result = None;
588        let mut sprout_anchor_result = None;
589        let mut chain_push_result = None;
590
591        // Clone function arguments for different threads
592        let block = contextual.block.clone();
593        let network = new_chain.network();
594        let history_tree = new_chain.history_block_commitment_tree();
595
596        let block2 = contextual.block.clone();
597        let height = contextual.height;
598        let transaction_hashes = contextual.transaction_hashes.clone();
599
600        rayon::in_place_scope_fifo(|scope| {
601            scope.spawn_fifo(|_scope| {
602                block_commitment_result = Some(check::block_commitment_is_valid_for_chain_history(
603                    block,
604                    &network,
605                    &history_tree,
606                ));
607            });
608
609            scope.spawn_fifo(|_scope| {
610                sprout_anchor_result =
611                    Some(check::anchors::block_sprout_anchors_refer_to_treestates(
612                        sprout_final_treestates,
613                        block2,
614                        transaction_hashes,
615                        height,
616                    ));
617            });
618
619            // We're pretty sure the new block is valid,
620            // so clone the inner chain if needed, then add the new block.
621            //
622            // Pushing a block onto a Chain can launch additional parallel batches.
623            // TODO: should we pass _scope into Chain::push()?
624            scope.spawn_fifo(|_scope| {
625                // TODO: Replace with Arc::unwrap_or_clone() when it stabilises:
626                // https://github.com/rust-lang/rust/issues/93610
627                let new_chain = Arc::try_unwrap(new_chain)
628                    .unwrap_or_else(|shared_chain| (*shared_chain).clone());
629                chain_push_result = Some(new_chain.push(contextual).map(Arc::new));
630            });
631        });
632
633        // Don't return the updated Chain unless all the parallel results were Ok
634        block_commitment_result.expect("scope has finished")?;
635        sprout_anchor_result.expect("scope has finished")?;
636
637        chain_push_result.expect("scope has finished")
638    }
639
640    /// Returns the length of the non-finalized portion of the current best chain
641    /// or `None` if the best chain has no blocks.
642    pub fn best_chain_len(&self) -> Option<u32> {
643        // This `as` can't overflow because the number of blocks in the chain is limited to i32::MAX,
644        // and the non-finalized chain is further limited by the fork length (slightly over 100 blocks).
645        Some(self.best_chain()?.blocks.len() as u32)
646    }
647
648    /// Returns the root height of the non-finalized state, if the non-finalized state is not empty.
649    pub fn root_height(&self) -> Option<block::Height> {
650        self.best_chain()
651            .map(|chain| chain.non_finalized_root_height())
652    }
653
654    /// Returns `true` if `hash` is contained in the non-finalized portion of any
655    /// known chain.
656    #[allow(dead_code)]
657    pub fn any_chain_contains(&self, hash: &block::Hash) -> bool {
658        self.chain_set
659            .iter()
660            .rev()
661            .any(|chain| chain.height_by_hash.contains_key(hash))
662    }
663
664    /// Returns the first chain satisfying the given predicate.
665    ///
666    /// If multiple chains satisfy the predicate, returns the chain with the highest difficulty.
667    /// (Using the tip block hash tie-breaker.)
668    pub fn find_chain<P>(&self, mut predicate: P) -> Option<Arc<Chain>>
669    where
670        P: FnMut(&Chain) -> bool,
671    {
672        // Reverse the iteration order, to find highest difficulty chains first.
673        self.chain_set
674            .iter()
675            .rev()
676            .find(|chain| predicate(chain))
677            .cloned()
678    }
679
680    /// Returns the [`transparent::Utxo`] pointed to by the given
681    /// [`transparent::OutPoint`] if it is present in any chain.
682    ///
683    /// UTXOs are returned regardless of whether they have been spent.
684    pub fn any_utxo(&self, outpoint: &transparent::OutPoint) -> Option<transparent::Utxo> {
685        self.chain_set
686            .iter()
687            .rev()
688            .find_map(|chain| chain.created_utxo(outpoint))
689    }
690
691    /// Returns the `block` with the given hash in any chain.
692    #[allow(dead_code)]
693    pub fn any_block_by_hash(&self, hash: block::Hash) -> Option<Arc<Block>> {
694        // This performs efficiently because the number of chains is limited to 10.
695        for chain in self.chain_set.iter().rev() {
696            if let Some(prepared) = chain
697                .height_by_hash
698                .get(&hash)
699                .and_then(|height| chain.blocks.get(height))
700            {
701                return Some(prepared.block.clone());
702            }
703        }
704
705        None
706    }
707
708    /// Returns the previous block hash for the given block hash in any chain.
709    #[allow(dead_code)]
710    pub fn any_prev_block_hash_for_hash(&self, hash: block::Hash) -> Option<block::Hash> {
711        // This performs efficiently because the blocks are in memory.
712        self.any_block_by_hash(hash)
713            .map(|block| block.header.previous_block_hash)
714    }
715
716    /// Returns the hash for a given `block::Height` if it is present in the best chain.
717    #[allow(dead_code)]
718    pub fn best_hash(&self, height: block::Height) -> Option<block::Hash> {
719        self.best_chain()?
720            .blocks
721            .get(&height)
722            .map(|prepared| prepared.hash)
723    }
724
725    /// Returns the tip of the best chain.
726    #[allow(dead_code)]
727    pub fn best_tip(&self) -> Option<(block::Height, block::Hash)> {
728        let best_chain = self.best_chain()?;
729        let height = best_chain.non_finalized_tip_height();
730        let hash = best_chain.non_finalized_tip_hash();
731
732        Some((height, hash))
733    }
734
735    /// Returns the block at the tip of the best chain.
736    #[allow(dead_code)]
737    pub fn best_tip_block(&self) -> Option<&ContextuallyVerifiedBlock> {
738        let best_chain = self.best_chain()?;
739
740        best_chain.tip_block()
741    }
742
743    /// Returns the height of `hash` in the best chain.
744    #[allow(dead_code)]
745    pub fn best_height_by_hash(&self, hash: block::Hash) -> Option<block::Height> {
746        let best_chain = self.best_chain()?;
747        let height = *best_chain.height_by_hash.get(&hash)?;
748        Some(height)
749    }
750
751    /// Returns the height of `hash` in any chain.
752    #[allow(dead_code)]
753    pub fn any_height_by_hash(&self, hash: block::Hash) -> Option<block::Height> {
754        for chain in self.chain_set.iter().rev() {
755            if let Some(height) = chain.height_by_hash.get(&hash) {
756                return Some(*height);
757            }
758        }
759
760        None
761    }
762
763    /// Returns `true` if the best chain contains `sprout_nullifier`.
764    #[cfg(any(test, feature = "proptest-impl"))]
765    #[allow(dead_code)]
766    pub fn best_contains_sprout_nullifier(&self, sprout_nullifier: &sprout::Nullifier) -> bool {
767        self.best_chain()
768            .map(|best_chain| best_chain.sprout_nullifiers.contains_key(sprout_nullifier))
769            .unwrap_or(false)
770    }
771
772    /// Returns `true` if the best chain contains `sapling_nullifier`.
773    #[cfg(any(test, feature = "proptest-impl"))]
774    #[allow(dead_code)]
775    pub fn best_contains_sapling_nullifier(
776        &self,
777        sapling_nullifier: &zebra_chain::sapling::Nullifier,
778    ) -> bool {
779        self.best_chain()
780            .map(|best_chain| {
781                best_chain
782                    .sapling_nullifiers
783                    .contains_key(sapling_nullifier)
784            })
785            .unwrap_or(false)
786    }
787
788    /// Returns `true` if the best chain contains `orchard_nullifier`.
789    #[cfg(any(test, feature = "proptest-impl"))]
790    #[allow(dead_code)]
791    pub fn best_contains_orchard_nullifier(
792        &self,
793        orchard_nullifier: &zebra_chain::orchard::Nullifier,
794    ) -> bool {
795        self.best_chain()
796            .map(|best_chain| {
797                best_chain
798                    .orchard_nullifiers
799                    .contains_key(orchard_nullifier)
800            })
801            .unwrap_or(false)
802    }
803
804    /// Return the non-finalized portion of the current best chain.
805    pub fn best_chain(&self) -> Option<&Arc<Chain>> {
806        self.chain_iter().next()
807    }
808
809    /// Return the number of chains.
810    pub fn chain_count(&self) -> usize {
811        self.chain_set.len()
812    }
813
814    /// Returns true if this [`NonFinalizedState`] contains no chains.
815    pub fn is_chain_set_empty(&self) -> bool {
816        self.chain_count() == 0
817    }
818
819    /// Return the invalidated blocks.
820    pub fn invalidated_blocks(&self) -> IndexMap<Height, Arc<Vec<ContextuallyVerifiedBlock>>> {
821        self.invalidated_blocks.clone()
822    }
823
824    /// Return the chain whose tip block hash is `parent_hash`.
825    ///
826    /// The chain can be an existing chain in the non-finalized state, or a freshly
827    /// created fork.
828    fn parent_chain(&self, parent_hash: block::Hash) -> Result<Arc<Chain>, ValidateContextError> {
829        match self.find_chain(|chain| chain.non_finalized_tip_hash() == parent_hash) {
830            // Clone the existing Arc<Chain> in the non-finalized state
831            Some(chain) => Ok(chain.clone()),
832            // Create a new fork
833            None => {
834                // Check the lowest difficulty chains first,
835                // because the fork could be closer to their tip.
836                let fork_chain = self
837                    .chain_set
838                    .iter()
839                    .rev()
840                    .find_map(|chain| chain.fork(parent_hash))
841                    .ok_or(ValidateContextError::NotReadyToBeCommitted)?;
842
843                Ok(Arc::new(fork_chain))
844            }
845        }
846    }
847
848    /// Should this `NonFinalizedState` instance track metrics and progress bars?
849    fn should_count_metrics(&self) -> bool {
850        self.should_count_metrics
851    }
852
853    /// Update the metrics after `block` is committed
854    fn update_metrics_for_committed_block(&self, height: block::Height, hash: block::Hash) {
855        if !self.should_count_metrics() {
856            return;
857        }
858
859        metrics::counter!("state.memory.committed.block.count").increment(1);
860        metrics::gauge!("state.memory.committed.block.height").set(height.0 as f64);
861
862        if self
863            .best_chain()
864            .expect("metrics are only updated after initialization")
865            .non_finalized_tip_hash()
866            == hash
867        {
868            metrics::counter!("state.memory.best.committed.block.count").increment(1);
869            metrics::gauge!("state.memory.best.committed.block.height").set(height.0 as f64);
870        }
871
872        self.update_metrics_for_chains();
873    }
874
875    /// Update the metrics after `self.chain_set` is modified
876    fn update_metrics_for_chains(&self) {
877        if !self.should_count_metrics() {
878            return;
879        }
880
881        metrics::gauge!("state.memory.chain.count").set(self.chain_set.len() as f64);
882        metrics::gauge!("state.memory.best.chain.length",)
883            .set(self.best_chain_len().unwrap_or_default() as f64);
884    }
885
886    /// Update the progress bars after any chain is modified.
887    /// This includes both chain forks and committed blocks.
888    fn update_metrics_bars(&mut self) {
889        // TODO: make chain_count_bar interior mutable, move to update_metrics_for_committed_block()
890
891        if !self.should_count_metrics() {
892            #[allow(clippy::needless_return)]
893            return;
894        }
895
896        #[cfg(feature = "progress-bar")]
897        {
898            use std::cmp::Ordering::*;
899
900            if matches!(howudoin::cancelled(), Some(true)) {
901                self.disable_metrics();
902                return;
903            }
904
905            // Update the chain count bar
906            if self.chain_count_bar.is_none() {
907                self.chain_count_bar = Some(howudoin::new_root().label("Chain Forks"));
908            }
909
910            let chain_count_bar = self
911                .chain_count_bar
912                .as_ref()
913                .expect("just initialized if missing");
914            let finalized_tip_height = self
915                .best_chain()
916                .map(|chain| chain.non_finalized_root_height().0 - 1);
917
918            chain_count_bar.set_pos(u64::try_from(self.chain_count()).expect("fits in u64"));
919            // .set_len(u64::try_from(MAX_NON_FINALIZED_CHAIN_FORKS).expect("fits in u64"));
920
921            if let Some(finalized_tip_height) = finalized_tip_height {
922                chain_count_bar.desc(format!("Finalized Root {finalized_tip_height}"));
923            }
924
925            // Update each chain length bar, creating or deleting bars as needed
926            let prev_length_bars = self.chain_fork_length_bars.len();
927
928            match self.chain_count().cmp(&prev_length_bars) {
929                Greater => self
930                    .chain_fork_length_bars
931                    .resize_with(self.chain_count(), || {
932                        howudoin::new_with_parent(chain_count_bar.id())
933                    }),
934                Less => {
935                    let redundant_bars = self.chain_fork_length_bars.split_off(self.chain_count());
936                    for bar in redundant_bars {
937                        bar.close();
938                    }
939                }
940                Equal => {}
941            }
942
943            // It doesn't matter what chain the bar was previously used for,
944            // because we update everything based on the latest chain in that position.
945            for (chain_length_bar, chain) in
946                std::iter::zip(self.chain_fork_length_bars.iter(), self.chain_iter())
947            {
948                let fork_height = chain
949                    .last_fork_height
950                    .unwrap_or_else(|| chain.non_finalized_tip_height())
951                    .0;
952
953                // We need to initialize and set all the values of the bar here, because:
954                // - the bar might have been newly created, or
955                // - the chain this bar was previously assigned to might have changed position.
956                chain_length_bar
957                    .label(format!("Fork {fork_height}"))
958                    .set_pos(u64::try_from(chain.len()).expect("fits in u64"));
959                // TODO: should this be MAX_BLOCK_REORG_HEIGHT?
960                // .set_len(u64::from(
961                //     zebra_chain::transparent::MIN_TRANSPARENT_COINBASE_MATURITY,
962                // ));
963
964                // TODO: store work in the finalized state for each height (#7109),
965                //       and show the full chain work here, like `zcashd` (#7110)
966                //
967                // For now, we don't show any work here, see the deleted code in PR #7087.
968                let mut desc = String::new();
969
970                if let Some(recent_fork_height) = chain.recent_fork_height() {
971                    let recent_fork_length = chain
972                        .recent_fork_length()
973                        .expect("just checked recent fork height");
974
975                    let mut plural = "s";
976                    if recent_fork_length == 1 {
977                        plural = "";
978                    }
979
980                    desc.push_str(&format!(
981                        " at {recent_fork_height:?} + {recent_fork_length} block{plural}"
982                    ));
983                }
984
985                chain_length_bar.desc(desc);
986            }
987        }
988    }
989
990    /// Stop tracking metrics for this non-finalized state and all its chains.
991    pub fn disable_metrics(&mut self) {
992        self.should_count_metrics = false;
993
994        #[cfg(feature = "progress-bar")]
995        {
996            let count_bar = self.chain_count_bar.take().into_iter();
997            let fork_bars = self.chain_fork_length_bars.drain(..);
998            count_bar.chain(fork_bars).for_each(howudoin::Tx::close);
999        }
1000    }
1001}
1002
1003impl Drop for NonFinalizedState {
1004    fn drop(&mut self) {
1005        self.disable_metrics();
1006    }
1007}