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, SnapPhase, SnapSyncError};
14use alloy_eip7928::BAL_RETENTION_PERIOD_SLOTS;
15use reth_primitives_traits::AlloyBlockHeader;
16use reth_storage_api::HeaderProvider;
17
18// EIP-8189's example anchor, matching go-ethereum's `fsMinFullBlocks`.
19const 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 block access lists `generation` still needs remain servable.
94    ///
95    /// Once they are not, its state cannot be carried forward and the attempt has to restart.
96    pub const fn is_catchable(&self, generation: SnapGeneration, head: u64) -> bool {
97        self.is_catchable_from(generation.target().number, head)
98    }
99
100    /// Returns whether the list of the block after `applied` remains servable under `head`.
101    ///
102    /// Catch-up continues from the last applied block, which trails the pivot while lists are
103    /// missing, so an attempt whose pivot is recent can still need an expired list.
104    pub const fn is_catchable_from(&self, applied: u64, head: u64) -> bool {
105        head.saturating_sub(applied) <= self.history
106    }
107
108    /// Returns a fresh generation for the canonical pivot under `head`.
109    ///
110    /// A candidate that is not eligible falls back to the head distance; `None` means no candidate
111    /// can anchor a sync yet.
112    pub fn select(
113        &self,
114        provider: &impl HeaderProvider,
115        head: u64,
116        finalized: Option<u64>,
117    ) -> Result<Option<SnapGeneration>, SnapSyncError> {
118        let preferred = self.pivot_block(head, finalized);
119        let fallback =
120            head.checked_sub(self.head_distance).filter(|block| Some(*block) != preferred);
121        for block_number in preferred.into_iter().chain(fallback) {
122            let Some(header) = provider.sealed_header(block_number)? else { continue };
123            if header.block_access_list_hash().is_some() {
124                return Ok(Some(SnapGeneration::new(header.num_hash(), header.state_root())))
125            }
126        }
127        Ok(None)
128    }
129
130    /// Returns whether an interrupted generation is still worth finishing under `head`.
131    ///
132    /// A fully downloaded generation only needs its trie rebuilt, so it always is.
133    pub const fn is_finishable(&self, generation: SnapGeneration, head: u64) -> bool {
134        matches!(generation.phase(), SnapPhase::Trie) || self.is_catchable(generation, head)
135    }
136
137    /// Returns whether the lists of blocks a reorg orphaned after `ancestor` are still worth
138    /// waiting for under `head`, since peers may keep lists only for canonical blocks.
139    pub const fn awaits_orphaned_lists(&self, ancestor: u64, head: u64) -> bool {
140        head.saturating_sub(ancestor) <= SERVED_STATE_WINDOW
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use crate::test_utils::{chain, policy, provider_with};
148    use alloy_eips::BlockNumHash;
149    use alloy_primitives::B256;
150
151    #[test]
152    fn selects_the_bal_capable_pivot_behind_the_head() {
153        let headers = chain(Some(0));
154        let expected = headers[2].clone();
155        let provider = provider_with(headers);
156
157        let generation = policy().select(&provider, 3, None).unwrap().unwrap();
158
159        assert_eq!(generation.target().number, 2);
160        assert_eq!(generation.target().hash, expected.hash_slow());
161        assert_eq!(generation.state_root(), expected.state_root);
162        assert_eq!(generation.phase(), SnapPhase::Accounts);
163    }
164
165    #[test]
166    fn a_recent_finalized_block_is_anchored_to_instead_of_the_head_distance() {
167        let headers = chain(Some(0));
168        let expected = headers[1].clone();
169        let provider = provider_with(headers);
170
171        let generation = policy().select(&provider, 3, Some(1)).unwrap().unwrap();
172
173        assert_eq!(generation.target().number, 1);
174        assert_eq!(generation.target().hash, expected.hash_slow());
175    }
176
177    #[test]
178    fn finality_stalled_outside_the_advance_window_falls_back_to_the_head_distance() {
179        let headers = chain(Some(0));
180        let fallback = headers[2].clone();
181        let provider = provider_with(headers);
182        // A finalized block two behind the head is outside this policy's advance window.
183        let policy = policy().with_advance_after(1);
184
185        let generation = policy.select(&provider, 3, Some(1)).unwrap().unwrap();
186
187        // HEAD-1, not the stale finalized block 1.
188        assert_eq!(generation.target().number, 2);
189        assert_eq!(generation.target().hash, fallback.hash_slow());
190    }
191
192    #[test]
193    fn an_ineligible_finalized_pivot_falls_back_to_the_head_distance() {
194        // Block access lists only start at block 2, so the finalized block predates activation.
195        let headers = chain(Some(2));
196        let fallback = headers[2].clone();
197        let provider = provider_with(headers);
198
199        let generation = policy().select(&provider, 3, Some(1)).unwrap().unwrap();
200
201        // HEAD-1, rather than waiting for finality to reach activation.
202        assert_eq!(generation.target().number, 2);
203        assert_eq!(generation.target().hash, fallback.hash_slow());
204    }
205
206    #[test]
207    fn pivot_without_a_bal_commitment_is_not_selectable() {
208        let provider = provider_with(chain(Some(3)));
209
210        assert_eq!(policy().select(&provider, 3, None).unwrap(), None);
211        // Neither the finalized anchor nor the fallback carries a commitment.
212        assert_eq!(policy().select(&provider, 3, Some(1)).unwrap(), None);
213    }
214
215    #[test]
216    fn pivot_beyond_downloaded_headers_is_not_selectable() {
217        let provider = provider_with(chain(Some(0)));
218
219        assert_eq!(policy().select(&provider, 9, None).unwrap(), None);
220    }
221
222    #[test]
223    fn chain_shorter_than_the_head_distance_has_no_pivot() {
224        let provider = provider_with(chain(Some(0)));
225
226        assert_eq!(policy().with_head_distance(4).select(&provider, 0, None).unwrap(), None);
227    }
228
229    #[test]
230    fn a_pivot_lagging_past_the_advance_window_is_re_anchored() {
231        let policy = policy();
232        let generation = SnapGeneration::new(BlockNumHash::new(0, B256::ZERO), B256::ZERO);
233
234        assert!(!policy.needs_advance(generation, 4));
235        assert!(policy.needs_advance(generation, 5));
236    }
237
238    #[test]
239    fn generation_outside_the_bal_window_is_not_finishable() {
240        let headers = chain(Some(0));
241        let anchor = headers[1].clone();
242        let provider = provider_with(headers);
243        let generation =
244            SnapGeneration::new(BlockNumHash::new(1, anchor.hash_slow()), anchor.state_root);
245        let policy = policy();
246
247        assert!(generation.is_canonical(&provider).unwrap());
248        assert!(policy.is_finishable(generation, 9));
249        assert!(!policy.is_finishable(generation, 10));
250    }
251
252    #[test]
253    fn downloaded_state_finishes_outside_the_bal_window() {
254        let anchor = chain(Some(0))[1].clone();
255        let generation =
256            SnapGeneration::new(BlockNumHash::new(1, anchor.hash_slow()), anchor.state_root)
257                .with_phase(SnapPhase::Trie);
258
259        assert!(policy().is_finishable(generation, 1_000));
260    }
261
262    #[test]
263    fn reorged_anchor_is_not_canonical() {
264        let provider = provider_with(chain(Some(0)));
265        let generation =
266            SnapGeneration::new(BlockNumHash::new(1, B256::repeat_byte(0xff)), B256::ZERO);
267
268        assert!(!generation.is_canonical(&provider).unwrap());
269    }
270}
reth_snap_sync/pivot.rs

reth_snap_sync/
pivot.rs
