reth_snap_sync/
pivot.rs

1//! Chooses the canonical block a snap generation is anchored to.
2//!
3//! [EIP-8189](https://eips.ethereum.org/EIPS/eip-8189#synchronization-algorithm) pivot selection
4//! anchors synchronization at a block "sufficiently behind the chain head [...] to reduce the
5//! likelihood of P being reorged while remaining recent enough that serving peers still hold its
6//! state in memory". Those two pressures are what this policy balances: too close to the head and
7//! the anchor is reorged, too far and no peer will serve its state.
8//!
9//! Two choices depart from the EIP's example: a finalized block is preferred as the anchor when one
10//! is available, and re-anchoring starts once a pivot lags by 96 blocks rather than at the edge of
11//! the window peers still serve state for.
12
13use crate::{SnapGeneration, SnapSyncError};
14use alloy_eip7928::BAL_RETENTION_PERIOD_SLOTS;
15use reth_primitives_traits::AlloyBlockHeader;
16use reth_storage_api::HeaderProvider;
17
18/// Blocks behind the head a generation is anchored to when no finalized block is available
19pub const DEFAULT_HEAD_DISTANCE: u64 = 64;
20
21// Blocks of state history a serving peer is assumed to still hold, mirroring reth's own
22// `SNAPSHOT_STATE_RETENTION`.
23const SERVED_STATE_WINDOW: u64 = 128;
24
25// Re-anchor before the pivot reaches the edge of that window, so ranges in flight do not fail
26// against a root peers just dropped.
27const DEFAULT_ADVANCE_AFTER: u64 = SERVED_STATE_WINDOW - DEFAULT_HEAD_DISTANCE / 2;
28
29/// Distance and history bounds that decide where a generation is anchored.
30#[derive(Clone, Copy, Debug, Eq, PartialEq)]
31pub struct SnapPivotPolicy {
32    // Blocks behind the head to anchor at when no finalized block is available.
33    head_distance: u64,
34    // Pivot lag that triggers re-anchoring while ranges are still downloading.
35    advance_after: u64,
36    // Blocks of block access list history a peer is assumed to still serve.
37    history: u64,
38}
39
40impl Default for SnapPivotPolicy {
41    fn default() -> Self {
42        Self {
43            head_distance: DEFAULT_HEAD_DISTANCE,
44            advance_after: DEFAULT_ADVANCE_AFTER,
45            history: BAL_RETENTION_PERIOD_SLOTS,
46        }
47    }
48}
49
50impl SnapPivotPolicy {
51    /// Returns this policy anchoring `head_distance` blocks behind the head.
52    pub const fn with_head_distance(mut self, head_distance: u64) -> Self {
53        self.head_distance = head_distance;
54        self
55    }
56
57    /// Returns this policy re-anchoring once a pivot lags by `advance_after` blocks.
58    pub const fn with_advance_after(mut self, advance_after: u64) -> Self {
59        self.advance_after = advance_after;
60        self
61    }
62
63    /// Returns this policy assuming `history` blocks of block access lists remain servable.
64    ///
65    /// Defaults to the full EIP-7928 retention period, since applying lists beats downloading the
66    /// state again.
67    pub const fn with_history(mut self, history: u64) -> Self {
68        self.history = history;
69        self
70    }
71
72    /// Returns the block a pivot anchored under `head` targets.
73    ///
74    /// Prefers a finalized block that peers still serve state for, since it cannot be reorged, and
75    /// falls back to the head distance.
76    pub const fn pivot_block(&self, head: u64, finalized: Option<u64>) -> Option<u64> {
77        if let Some(finalized) = finalized &&
78            head.saturating_sub(finalized) <= self.advance_after
79        {
80            return Some(finalized)
81        }
82        head.checked_sub(self.head_distance)
83    }
84
85    /// Returns whether `generation` should be re-anchored under `head`.
86    ///
87    /// Advancing stays far cheaper than restarting, so this triggers well before peers stop
88    /// serving the old root.
89    pub const fn needs_advance(&self, generation: SnapGeneration, head: u64) -> bool {
90        generation.lag(head) > self.advance_after
91    }
92
93    /// Returns whether the list of the block after `applied` remains servable under `head`.
94    ///
95    /// Catch-up continues from the last applied block, which trails the pivot while lists are
96    /// missing, so an attempt whose pivot is recent can still need an expired list.
97    pub const fn is_catchable_from(&self, applied: u64, head: u64) -> bool {
98        head.saturating_sub(applied) <= self.history
99    }
100
101    /// Returns a fresh generation for the canonical pivot under `head`.
102    ///
103    /// A candidate that is not eligible falls back to the head distance; `None` means no candidate
104    /// can anchor a sync yet.
105    pub fn select(
106        &self,
107        provider: &impl HeaderProvider,
108        head: u64,
109        finalized: Option<u64>,
110    ) -> Result<Option<SnapGeneration>, SnapSyncError> {
111        let preferred = self.pivot_block(head, finalized);
112        let fallback =
113            head.checked_sub(self.head_distance).filter(|block| Some(*block) != preferred);
114        for block_number in preferred.into_iter().chain(fallback) {
115            let Some(header) = provider.sealed_header(block_number)? else { continue };
116            if header.block_access_list_hash().is_some() {
117                return Ok(Some(SnapGeneration::new(header.num_hash(), header.state_root())))
118            }
119        }
120        Ok(None)
121    }
122
123    /// Returns whether the lists of blocks a reorg orphaned after `ancestor` are still worth
124    /// waiting for under `head`, since peers may keep lists only for canonical blocks.
125    pub const fn awaits_orphaned_lists(&self, ancestor: u64, head: u64) -> bool {
126        head.saturating_sub(ancestor) <= SERVED_STATE_WINDOW
127    }
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crate::test_utils::{chain, policy, provider_with};
134    use alloy_eips::BlockNumHash;
135    use alloy_primitives::B256;
136
137    #[test]
138    fn selects_the_bal_capable_pivot_behind_the_head() {
139        let headers = chain(Some(0));
140        let expected = headers[2].clone();
141        let provider = provider_with(headers);
142
143        let generation = policy().select(&provider, 3, None).unwrap().unwrap();
144
145        assert_eq!(generation.target().number, 2);
146        assert_eq!(generation.target().hash, expected.hash_slow());
147        assert_eq!(generation.state_root(), expected.state_root);
148    }
149
150    #[test]
151    fn a_recent_finalized_block_is_anchored_to_instead_of_the_head_distance() {
152        let headers = chain(Some(0));
153        let expected = headers[1].clone();
154        let provider = provider_with(headers);
155
156        let generation = policy().select(&provider, 3, Some(1)).unwrap().unwrap();
157
158        assert_eq!(generation.target().number, 1);
159        assert_eq!(generation.target().hash, expected.hash_slow());
160    }
161
162    #[test]
163    fn finality_stalled_outside_the_advance_window_falls_back_to_the_head_distance() {
164        let headers = chain(Some(0));
165        let fallback = headers[2].clone();
166        let provider = provider_with(headers);
167        // A finalized block two behind the head is outside this policy's advance window.
168        let policy = policy().with_advance_after(1);
169
170        let generation = policy.select(&provider, 3, Some(1)).unwrap().unwrap();
171
172        // HEAD-1, not the stale finalized block 1.
173        assert_eq!(generation.target().number, 2);
174        assert_eq!(generation.target().hash, fallback.hash_slow());
175    }
176
177    #[test]
178    fn an_ineligible_finalized_pivot_falls_back_to_the_head_distance() {
179        // Block access lists only start at block 2, so the finalized block predates activation.
180        let headers = chain(Some(2));
181        let fallback = headers[2].clone();
182        let provider = provider_with(headers);
183
184        let generation = policy().select(&provider, 3, Some(1)).unwrap().unwrap();
185
186        // HEAD-1, rather than waiting for finality to reach activation.
187        assert_eq!(generation.target().number, 2);
188        assert_eq!(generation.target().hash, fallback.hash_slow());
189    }
190
191    #[test]
192    fn pivot_without_a_block_access_list_hash_is_not_selectable() {
193        let provider = provider_with(chain(Some(3)));
194
195        assert_eq!(policy().select(&provider, 3, None).unwrap(), None);
196        // Neither the finalized anchor nor the fallback carries a block access list hash.
197        assert_eq!(policy().select(&provider, 3, Some(1)).unwrap(), None);
198    }
199
200    #[test]
201    fn pivot_beyond_downloaded_headers_is_not_selectable() {
202        let provider = provider_with(chain(Some(0)));
203
204        assert_eq!(policy().select(&provider, 9, None).unwrap(), None);
205    }
206
207    #[test]
208    fn chain_shorter_than_the_head_distance_has_no_pivot() {
209        let provider = provider_with(chain(Some(0)));
210
211        assert_eq!(policy().with_head_distance(4).select(&provider, 0, None).unwrap(), None);
212    }
213
214    #[test]
215    fn a_pivot_lagging_past_the_advance_window_is_re_anchored() {
216        let policy = policy();
217        let generation = SnapGeneration::new(BlockNumHash::new(0, B256::ZERO), B256::ZERO);
218
219        assert!(!policy.needs_advance(generation, 4));
220        assert!(policy.needs_advance(generation, 5));
221    }
222
223    #[test]
224    fn generation_outside_the_bal_window_is_not_catchable() {
225        let policy = policy();
226
227        assert!(policy.is_catchable_from(1, 9));
228        assert!(!policy.is_catchable_from(1, 10));
229    }
230}
reth_snap_sync/pivot.rs

reth_snap_sync/
pivot.rs
