zebra_chain/chain_tip/network_chain_tip_height_estimator.rs
1//! A module with helper code to estimate the network chain tip's height.
2
3use std::vec;
4
5use chrono::{DateTime, Duration, Utc};
6
7use crate::{
8 block::{self, HeightDiff},
9 parameters::{Network, NetworkUpgrade},
10};
11
12/// A type used to estimate the chain tip height at a given time.
13///
14/// The estimation is based on a known block time and height for a block. The estimator will then
15/// handle any target spacing changes to extrapolate the provided information into a target time
16/// and obtain an estimation for the height at that time.
17///
18/// # Usage
19///
20/// 1. Use [`NetworkChainTipHeightEstimator::new`] to create and initialize a new instance with the
21/// information about a known block.
22/// 2. Use [`NetworkChainTipHeightEstimator::estimate_height_at`] to obtain a height estimation for
23/// a given instant.
24#[derive(Debug)]
25pub struct NetworkChainTipHeightEstimator {
26 current_block_time: DateTime<Utc>,
27 current_height: block::Height,
28 current_target_spacing: Duration,
29 next_target_spacings: vec::IntoIter<(block::Height, Duration)>,
30}
31
32impl NetworkChainTipHeightEstimator {
33 /// Create a [`NetworkChainTipHeightEstimator`] and initialize it with the information to use
34 /// for calculating a chain height estimate.
35 ///
36 /// The provided information (`current_block_time`, `current_height` and `network`) **must**
37 /// refer to the same block.
38 ///
39 /// # Implementation details
40 ///
41 /// The `network` is used to obtain a list of target spacings used in different sections of the
42 /// block chain. The first section is used as a starting point.
43 pub fn new(
44 current_block_time: DateTime<Utc>,
45 current_height: block::Height,
46 network: &Network,
47 ) -> Self {
48 let mut target_spacings = NetworkUpgrade::target_spacings(network);
49 let (_genesis_height, initial_target_spacing) =
50 target_spacings.next().expect("No target spacings were set");
51
52 NetworkChainTipHeightEstimator {
53 current_block_time,
54 current_height,
55 current_target_spacing: initial_target_spacing,
56 // TODO: Remove the `Vec` allocation once existential `impl Trait`s are available.
57 next_target_spacings: target_spacings.collect::<Vec<_>>().into_iter(),
58 }
59 }
60
61 /// Estimate the network chain tip height at the provided `target_time`.
62 ///
63 /// # Implementation details
64 ///
65 /// The `current_block_time` and the `current_height` is advanced to the end of each section
66 /// that has a different target spacing time. Once the `current_block_time` passes the
67 /// `target_time`, the last active target spacing time is used to calculate the final height
68 /// estimation.
69 pub fn estimate_height_at(mut self, target_time: DateTime<Utc>) -> block::Height {
70 while let Some((change_height, next_target_spacing)) = self.next_target_spacings.next() {
71 self.estimate_up_to(change_height);
72
73 if self.current_block_time >= target_time {
74 break;
75 }
76
77 self.current_target_spacing = next_target_spacing;
78 }
79
80 self.estimate_height_at_with_current_target_spacing(target_time)
81 }
82
83 /// Advance the `current_block_time` and `current_height` to the next change in target spacing
84 /// time.
85 ///
86 /// The `current_height` is advanced to `max_height` (if it's not already past that height).
87 /// The amount of blocks advanced is then used to extrapolate the amount to advance the
88 /// `current_block_time`.
89 fn estimate_up_to(&mut self, max_height: block::Height) {
90 let remaining_blocks = max_height - self.current_height;
91
92 if remaining_blocks > 0 {
93 let target_spacing_seconds = self.current_target_spacing.num_seconds();
94 let time_to_activation = Duration::seconds(remaining_blocks * target_spacing_seconds);
95 self.current_block_time += time_to_activation;
96 self.current_height = max_height;
97 }
98 }
99
100 /// Calculate an estimate for the chain height using the `current_target_spacing`.
101 ///
102 /// Using the difference between the `target_time` and the `current_block_time` and the
103 /// `current_target_spacing`, the number of blocks to reach the `target_time` from the
104 /// `current_block_time` is calculated. The value is added to the `current_height` to calculate
105 /// the final estimate.
106 fn estimate_height_at_with_current_target_spacing(
107 self,
108 target_time: DateTime<Utc>,
109 ) -> block::Height {
110 let time_difference = target_time - self.current_block_time;
111 let mut time_difference_seconds = time_difference.num_seconds();
112
113 if time_difference_seconds < 0 {
114 // Undo the rounding towards negative infinity done by `chrono::Duration`, which yields
115 // an incorrect value for the dividend of the division.
116 //
117 // (See https://docs.rs/time/0.1.44/src/time/duration.rs.html#166-173)
118 time_difference_seconds -= 1;
119 }
120
121 // Euclidean division is used so that the number is rounded towards negative infinity,
122 // so that fractionary values always round down to the previous height when going back
123 // in time (i.e., when the dividend is negative). This works because the divisor (the
124 // target spacing) is always positive.
125 let block_difference: HeightDiff =
126 time_difference_seconds.div_euclid(self.current_target_spacing.num_seconds());
127
128 let current_height_as_diff = HeightDiff::from(self.current_height.0);
129
130 if let Some(height_estimate) = self.current_height + block_difference {
131 height_estimate
132 } else if current_height_as_diff + block_difference < 0 {
133 // Gracefully handle attempting to estimate a block before genesis. This can happen if
134 // the local time is set incorrectly to a time too far in the past.
135 block::Height(0)
136 } else {
137 // Gracefully handle attempting to estimate a block at a very large height. This can
138 // happen if the local time is set incorrectly to a time too far in the future.
139 block::Height::MAX
140 }
141 }
142}