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        generation.lag(head) <= self.history
98    }
99
100    /// Returns a fresh generation for the canonical pivot under `head`.
101    ///
102    /// A candidate that is not eligible falls back to the head distance; `None` means no candidate
103    /// can anchor a sync yet.
104    pub fn select(
105        &self,
106        provider: &impl HeaderProvider,
107        head: u64,
108        finalized: Option<u64>,
109    ) -> Result<Option<SnapGeneration>, SnapSyncError> {
110        let preferred = self.pivot_block(head, finalized);
111        let fallback =
112            head.checked_sub(self.head_distance).filter(|block| Some(*block) != preferred);
113        for block_number in preferred.into_iter().chain(fallback) {
114            let Some(header) = provider.sealed_header(block_number)? else { continue };
115            if header.block_access_list_hash().is_some() {
116                return Ok(Some(SnapGeneration::new(header.num_hash(), header.state_root())))
117            }
118        }
119        Ok(None)
120    }
121
122    /// Returns whether an interrupted generation is still worth finishing under `head`.
123    ///
124    /// A fully downloaded generation only needs its trie rebuilt, so it always is.
125    pub const fn is_finishable(&self, generation: SnapGeneration, head: u64) -> bool {
126        matches!(generation.phase(), SnapPhase::Trie) || self.is_catchable(generation, head)
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        assert_eq!(generation.phase(), SnapPhase::Accounts);
149    }
150
151    #[test]
152    fn a_recent_finalized_block_is_anchored_to_instead_of_the_head_distance() {
153        let headers = chain(Some(0));
154        let expected = headers[1].clone();
155        let provider = provider_with(headers);
156
157        let generation = policy().select(&provider, 3, Some(1)).unwrap().unwrap();
158
159        assert_eq!(generation.target().number, 1);
160        assert_eq!(generation.target().hash, expected.hash_slow());
161    }
162
163    #[test]
164    fn finality_stalled_outside_the_advance_window_falls_back_to_the_head_distance() {
165        let headers = chain(Some(0));
166        let fallback = headers[2].clone();
167        let provider = provider_with(headers);
168        // A finalized block two behind the head is outside this policy's advance window.
169        let policy = policy().with_advance_after(1);
170
171        let generation = policy.select(&provider, 3, Some(1)).unwrap().unwrap();
172
173        // HEAD-1, not the stale finalized block 1.
174        assert_eq!(generation.target().number, 2);
175        assert_eq!(generation.target().hash, fallback.hash_slow());
176    }
177
178    #[test]
179    fn an_ineligible_finalized_pivot_falls_back_to_the_head_distance() {
180        // Block access lists only start at block 2, so the finalized block predates activation.
181        let headers = chain(Some(2));
182        let fallback = headers[2].clone();
183        let provider = provider_with(headers);
184
185        let generation = policy().select(&provider, 3, Some(1)).unwrap().unwrap();
186
187        // HEAD-1, rather than waiting for finality to reach activation.
188        assert_eq!(generation.target().number, 2);
189        assert_eq!(generation.target().hash, fallback.hash_slow());
190    }
191
192    #[test]
193    fn pivot_without_a_bal_commitment_is_not_selectable() {
194        let provider = provider_with(chain(Some(3)));
195
196        assert_eq!(policy().select(&provider, 3, None).unwrap(), None);
197        // Neither the finalized anchor nor the fallback carries a commitment.
198        assert_eq!(policy().select(&provider, 3, Some(1)).unwrap(), None);
199    }
200
201    #[test]
202    fn pivot_beyond_downloaded_headers_is_not_selectable() {
203        let provider = provider_with(chain(Some(0)));
204
205        assert_eq!(policy().select(&provider, 9, None).unwrap(), None);
206    }
207
208    #[test]
209    fn chain_shorter_than_the_head_distance_has_no_pivot() {
210        let provider = provider_with(chain(Some(0)));
211
212        assert_eq!(policy().with_head_distance(4).select(&provider, 0, None).unwrap(), None);
213    }
214
215    #[test]
216    fn a_pivot_lagging_past_the_advance_window_is_re_anchored() {
217        let policy = policy();
218        let generation = SnapGeneration::new(BlockNumHash::new(0, B256::ZERO), B256::ZERO);
219
220        assert!(!policy.needs_advance(generation, 4));
221        assert!(policy.needs_advance(generation, 5));
222    }
223
224    #[test]
225    fn generation_outside_the_bal_window_is_not_finishable() {
226        let headers = chain(Some(0));
227        let anchor = headers[1].clone();
228        let provider = provider_with(headers);
229        let generation =
230            SnapGeneration::new(BlockNumHash::new(1, anchor.hash_slow()), anchor.state_root);
231        let policy = policy();
232
233        assert!(generation.is_canonical(&provider).unwrap());
234        assert!(policy.is_finishable(generation, 9));
235        assert!(!policy.is_finishable(generation, 10));
236    }
237
238    #[test]
239    fn downloaded_state_finishes_outside_the_bal_window() {
240        let anchor = chain(Some(0))[1].clone();
241        let generation =
242            SnapGeneration::new(BlockNumHash::new(1, anchor.hash_slow()), anchor.state_root)
243                .with_phase(SnapPhase::Trie);
244
245        assert!(policy().is_finishable(generation, 1_000));
246    }
247
248    #[test]
249    fn reorged_anchor_is_not_canonical() {
250        let provider = provider_with(chain(Some(0)));
251        let generation =
252            SnapGeneration::new(BlockNumHash::new(1, B256::repeat_byte(0xff)), B256::ZERO);
253
254        assert!(!generation.is_canonical(&provider).unwrap());
255    }
256}
reth_snap_sync/pivot.rs

reth_snap_sync/
pivot.rs
