amareleo_node_sync/
block_locators.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkOS library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use snarkvm::prelude::{FromBytes, IoResult, Network, Read, ToBytes, Write, error, has_duplicates};
17
18use anyhow::{Result, bail, ensure};
19use indexmap::{IndexMap, indexmap};
20use serde::{Deserialize, Serialize};
21use std::collections::{BTreeMap, btree_map::IntoIter};
22
23/// The number of recent blocks (near tip).
24pub const NUM_RECENT_BLOCKS: usize = 100; // 100 blocks
25/// The interval between recent blocks.
26const RECENT_INTERVAL: u32 = 1; // 1 block intervals
27/// The interval between block checkpoints.
28pub const CHECKPOINT_INTERVAL: u32 = 10_000; // 10,000 block intervals
29
30/// Block locator maps.
31///
32/// This data structure is used by validators to advertise the blocks that
33/// they have and can provide to other validators to help them sync.
34/// Periodically, each validator broadcasts a [`PrimaryPing`],
35/// which contains a `BlockLocators` instance.
36/// Recall that blocks are indexed by their `u32` height, starting with 0 for the genesis block.
37/// The keys of the `recents` and `checkpoints` maps are the block heights;
38/// the values of the maps are the corresponding block hashes.
39///
40/// If a validator has `N` blocks, the `recents` and `checkpoints` maps are as follows:
41/// - The `recents` map contains entries for blocks at heights
42///   `N - 1 - (NUM_RECENT_BLOCKS - 1) * RECENT_INTERVAL`,
43///   `N - 1 - (NUM_RECENT_BLOCKS - 2) * RECENT_INTERVAL`,
44///   ...,
45///   `N - 1`.
46///   If any of the just listed heights are negative, there are no entries for them of course,
47///   and the `recents` map has fewer than `NUM_RECENT_BLOCKS` entries.
48///   If `RECENT_INTERVAL` is 1, the `recents` map contains entries
49///   for the last `NUM_RECENT_BLOCKS` blocks, i.e. from `N - NUM_RECENT_BLOCKS` to `N - 1`;
50///   if additionally `N < NUM_RECENT_BLOCKS`, the `recents` map contains
51///   entries for all the blocks, from `0` to `N - 1`.
52/// - The `checkpoints` map contains an entry for every `CHECKPOINT_INTERVAL`-th block,
53///   starting with 0 and not exceeding `N`, i.e. it has entries for blocks
54///   `0`, `CHECKPOINT_INTERVAL`, `2 * CHECKPOINT_INTERVAL`, ..., `k * CHECKPOINT_INTERVAL`,
55///   where `k` is the maximum integer such that `k * CHECKPOINT_INTERVAL <= N`.
56///
57/// The `recents` and `checkpoints` maps may have overlapping entries,
58/// e.g. if `N-1` is a multiple of `CHECKPOINT_INTERVAL`;
59/// but if `CHECKPOINT_INTERVAL` is much larger than `NUM_RECENT_BLOCKS`,
60/// there is no overlap most of the time.
61///
62/// We call `BlockLocators` with the form described above 'well-formed'.
63///
64/// Well-formed `BlockLocators` instances are built by [`BlockSync::get_block_locators()`].
65/// When a `BlockLocators` instance is received (in a [`PrimaryPing`]) by a validator,
66/// the maps may not be well-formed (if the sending validator is faulty),
67/// but the receiving validator ensures that they are well-formed
68/// by calling [`BlockLocators::ensure_is_valid()`] from [`BlockLocators::new()`],
69/// when deserializing in [`BlockLocators::read_le()`].
70/// So this well-formedness is an invariant of `BlockLocators` instances.
71#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
72pub struct BlockLocators<N: Network> {
73    /// The map of recent blocks.
74    pub recents: IndexMap<u32, N::BlockHash>,
75    /// The map of block checkpoints.
76    pub checkpoints: IndexMap<u32, N::BlockHash>,
77}
78
79impl<N: Network> BlockLocators<N> {
80    /// Initializes a new instance of the block locators, checking the validity of the block locators.
81    pub fn new(recents: IndexMap<u32, N::BlockHash>, checkpoints: IndexMap<u32, N::BlockHash>) -> Result<Self> {
82        // Construct the block locators.
83        let locators = Self { recents, checkpoints };
84        // Ensure the block locators are well-formed.
85        locators.ensure_is_valid()?;
86        // Return the block locators.
87        Ok(locators)
88    }
89
90    /// Initializes a new instance of the block locators, without checking the validity of the block locators.
91    /// This is only used for testing; note that it is non-public.
92    #[cfg(test)]
93    fn new_unchecked(recents: IndexMap<u32, N::BlockHash>, checkpoints: IndexMap<u32, N::BlockHash>) -> Self {
94        Self { recents, checkpoints }
95    }
96
97    /// Initializes a new genesis instance of the block locators.
98    pub fn new_genesis(genesis_hash: N::BlockHash) -> Self {
99        Self { recents: indexmap![0 => genesis_hash], checkpoints: indexmap![0 => genesis_hash] }
100    }
101}
102
103impl<N: Network> IntoIterator for BlockLocators<N> {
104    type IntoIter = IntoIter<u32, N::BlockHash>;
105    type Item = (u32, N::BlockHash);
106
107    // TODO (howardwu): Consider using `BTreeMap::from_par_iter` if it is more performant.
108    //  Check by sorting 300-1000 items and comparing the performance.
109    //  (https://docs.rs/indexmap/latest/indexmap/map/struct.IndexMap.html#method.from_par_iter)
110    fn into_iter(self) -> Self::IntoIter {
111        BTreeMap::from_iter(self.checkpoints.into_iter().chain(self.recents)).into_iter()
112    }
113}
114
115impl<N: Network> BlockLocators<N> {
116    /// Returns the latest locator height.
117    pub fn latest_locator_height(&self) -> u32 {
118        self.recents.keys().last().copied().unwrap_or_default()
119    }
120
121    /// Returns the block hash for the given block height, if it exists.
122    pub fn get_hash(&self, height: u32) -> Option<N::BlockHash> {
123        self.recents.get(&height).copied().or_else(|| self.checkpoints.get(&height).copied())
124    }
125
126    /// Returns `true` if the block locators are well-formed.
127    pub fn is_valid(&self) -> bool {
128        // Ensure the block locators are well-formed.
129        if let Err(_error) = self.ensure_is_valid() {
130            // guard_warn!("Block locators are invalid: {_error}");
131            return false;
132        }
133        true
134    }
135
136    /// Returns `true` if the given block locators are consistent with this one.
137    /// This function assumes the given block locators are well-formed.
138    pub fn is_consistent_with(&self, other: &Self) -> bool {
139        // Ensure the block locators are consistent with the previous ones.
140        if let Err(_error) = self.ensure_is_consistent_with(other) {
141            // guard_warn!("Inconsistent block locators: {_error}");
142            return false;
143        }
144        true
145    }
146
147    /// Checks that this block locators instance is well-formed.
148    pub fn ensure_is_valid(&self) -> Result<()> {
149        // Ensure the block locators are well-formed.
150        Self::check_block_locators(&self.recents, &self.checkpoints)
151    }
152
153    /// Returns `true` if the given block locators are consistent with this one.
154    /// This function assumes the given block locators are well-formed.
155    pub fn ensure_is_consistent_with(&self, other: &Self) -> Result<()> {
156        Self::check_consistent_block_locators(self, other)
157    }
158}
159
160impl<N: Network> BlockLocators<N> {
161    /// Checks the old and new block locators share a consistent view of block history.
162    /// This function assumes the given block locators are well-formed.
163    pub fn check_consistent_block_locators(
164        old_locators: &BlockLocators<N>,
165        new_locators: &BlockLocators<N>,
166    ) -> Result<()> {
167        // For the overlapping recent blocks, ensure their block hashes match.
168        for (height, hash) in new_locators.recents.iter() {
169            if let Some(recent_hash) = old_locators.recents.get(height) {
170                if recent_hash != hash {
171                    bail!("Recent block hash mismatch at height {height}")
172                }
173            }
174        }
175        // For the overlapping block checkpoints, ensure their block hashes match.
176        for (height, hash) in new_locators.checkpoints.iter() {
177            if let Some(checkpoint_hash) = old_locators.checkpoints.get(height) {
178                if checkpoint_hash != hash {
179                    bail!("Block checkpoint hash mismatch for height {height}")
180                }
181            }
182        }
183        Ok(())
184    }
185
186    /// Checks that the block locators are well-formed.
187    pub fn check_block_locators(
188        recents: &IndexMap<u32, N::BlockHash>,
189        checkpoints: &IndexMap<u32, N::BlockHash>,
190    ) -> Result<()> {
191        // Ensure the recent blocks are well-formed.
192        let last_recent_height = Self::check_recent_blocks(recents)?;
193        // Ensure the block checkpoints are well-formed.
194        let last_checkpoint_height = Self::check_block_checkpoints(checkpoints)?;
195
196        // Ensure that `last_checkpoint_height` is
197        // the largest multiple of `CHECKPOINT_INTERVAL` that does not exceed `last_recent_height`.
198        // That is, we must have
199        // `last_checkpoint_height <= last_recent_height < last_checkpoint_height + CHECKPOINT_INTERVAL`.
200        // Although we do not expect to run out of `u32` for block heights,
201        // `last_checkpoint_height` is an untrusted value that may come from a faulty validator,
202        // and thus we use a saturating addition;
203        // only a faulty validator would send block locators with such high block heights,
204        // under the assumption that the blockchain is always well below the `u32` limit for heights.
205        if !(last_checkpoint_height..last_checkpoint_height.saturating_add(CHECKPOINT_INTERVAL))
206            .contains(&last_recent_height)
207        {
208            bail!(
209                "Last checkpoint height ({last_checkpoint_height}) is not the largest multiple of \
210                 {CHECKPOINT_INTERVAL} that does not exceed the last recent height ({last_recent_height})"
211            )
212        }
213
214        // Ensure that if the recents and checkpoints maps overlap, they agree on the hash:
215        // we calculate the distance from the last recent to the last checkpoint;
216        // if that distance is `NUM_RECENT_BLOCKS` or more, there is no overlap;
217        // otherwise, the overlap is at the last checkpoint,
218        // which is exactly at the last recent height minus its distance from the last checkpoint.
219        // All of this also works if the last checkpoint is 0:
220        // in this case, there is an overlap (at 0) exactly when the last recent height,
221        // which is the same as its distance from the last checkpoint (0),
222        // is less than `NUM_RECENT_BLOCKS`.
223        // All of this only works if `NUM_RECENT_BLOCKS < CHECKPOINT_INTERVAL`,
224        // because it is only under this condition that there is at most one overlapping height.
225        // TODO: generalize check for RECENT_INTERVAL > 1, or remove this comment if we hardwire that to 1
226        let last_recent_to_last_checkpoint_distance = last_recent_height % CHECKPOINT_INTERVAL;
227        if last_recent_to_last_checkpoint_distance < NUM_RECENT_BLOCKS as u32 {
228            let common = last_recent_height - last_recent_to_last_checkpoint_distance;
229            if recents.get(&common).unwrap() != checkpoints.get(&common).unwrap() {
230                bail!("Recent block hash and checkpoint hash mismatch at height {common}")
231            }
232        }
233
234        Ok(())
235    }
236
237    /// Checks the recent blocks, returning the last block height from the map.
238    ///
239    /// This function checks the following:
240    /// 1. The map is not empty.
241    /// 2. The map is at the correct interval.
242    /// 3. The map is at the correct height.
243    /// 4. The map is in the correct order.
244    /// 5. The map does not contain too many entries.
245    fn check_recent_blocks(recents: &IndexMap<u32, N::BlockHash>) -> Result<u32> {
246        // Ensure the number of recent blocks is at least 1.
247        if recents.is_empty() {
248            bail!("There must be at least 1 recent block")
249        }
250        // Ensure the number of recent blocks is at most NUM_RECENT_BLOCKS.
251        // This redundant check ensures we early exit if the number of recent blocks is too large.
252        if recents.len() > NUM_RECENT_BLOCKS {
253            bail!("There can be at most {NUM_RECENT_BLOCKS} blocks in the map")
254        }
255
256        // Ensure the given recent blocks increment in height, and at the correct interval.
257        let mut last_height = 0;
258        for (i, current_height) in recents.keys().enumerate() {
259            if i == 0 && recents.len() < NUM_RECENT_BLOCKS && *current_height > 0 {
260                bail!("Ledgers under {NUM_RECENT_BLOCKS} blocks must have the first recent block at height 0")
261            }
262            if i > 0 && *current_height <= last_height {
263                bail!("Recent blocks must increment in height")
264            }
265            if i > 0 && *current_height - last_height != RECENT_INTERVAL {
266                bail!("Recent blocks must increment by {RECENT_INTERVAL}")
267            }
268            last_height = *current_height;
269        }
270
271        // At this point, if last_height < NUM_RECENT_BLOCKS`,
272        // we know that the `recents` map consists of exactly block heights from 0 to last_height,
273        // because the loop above has ensured that the first entry is for height 0,
274        // and at the end of the loop `last_height` is the last key in `recents`,
275        // and all the keys in `recents` are consecutive in increments of 1.
276        // So the `recents` map consists of NUM_RECENT_BLOCKS or fewer entries.
277
278        // If last height >= NUM_RECENT_BLOCKS, ensure the number of recent blocks matches NUM_RECENT_BLOCKS.
279        // TODO: generalize check for RECENT_INTERVAL > 1, or remove this comment if we hardwire that to 1
280        if last_height >= NUM_RECENT_BLOCKS as u32 && recents.len() != NUM_RECENT_BLOCKS {
281            bail!("Number of recent blocks must match {NUM_RECENT_BLOCKS}")
282        }
283
284        // Ensure the block hashes are unique.
285        if has_duplicates(recents.values()) {
286            bail!("Recent block hashes must be unique")
287        }
288
289        Ok(last_height)
290    }
291
292    /// Checks the block checkpoints, returning the last block height from the checkpoints.
293    ///
294    /// This function checks the following:
295    /// 1. The block checkpoints are not empty.
296    /// 2. The block checkpoints are at the correct interval.
297    /// 3. The block checkpoints are at the correct height.
298    /// 4. The block checkpoints are in the correct order.
299    fn check_block_checkpoints(checkpoints: &IndexMap<u32, N::BlockHash>) -> Result<u32> {
300        // Ensure the block checkpoints are not empty.
301        ensure!(!checkpoints.is_empty(), "There must be at least 1 block checkpoint");
302
303        // Ensure the given checkpoints increment in height, and at the correct interval.
304        let mut last_height = 0;
305        for (i, current_height) in checkpoints.keys().enumerate() {
306            if i == 0 && *current_height != 0 {
307                bail!("First block checkpoint must be at height 0")
308            }
309            if i > 0 && *current_height <= last_height {
310                bail!("Block checkpoints must increment in height")
311            }
312            if i > 0 && *current_height - last_height != CHECKPOINT_INTERVAL {
313                bail!("Block checkpoints must increment by {CHECKPOINT_INTERVAL}")
314            }
315            last_height = *current_height;
316        }
317
318        // Ensure the block hashes are unique.
319        if has_duplicates(checkpoints.values()) {
320            bail!("Block checkpoints must be unique")
321        }
322
323        Ok(last_height)
324    }
325}
326
327impl<N: Network> FromBytes for BlockLocators<N> {
328    fn read_le<R: Read>(mut reader: R) -> IoResult<Self> {
329        // Read the number of recent block hashes.
330        let num_recents = u32::read_le(&mut reader)?;
331        // Read the recent block hashes.
332        let mut recents = IndexMap::new();
333        for _ in 0..num_recents {
334            let height = u32::read_le(&mut reader)?;
335            let hash = N::BlockHash::read_le(&mut reader)?;
336            recents.insert(height, hash);
337        }
338
339        // Read the number of checkpoints.
340        let num_checkpoints = u32::read_le(&mut reader)?;
341        // Read the checkpoints.
342        let mut checkpoints = IndexMap::new();
343        for _ in 0..num_checkpoints {
344            let height = u32::read_le(&mut reader)?;
345            let hash = N::BlockHash::read_le(&mut reader)?;
346            checkpoints.insert(height, hash);
347        }
348
349        Self::new(recents, checkpoints).map_err(error)
350    }
351}
352
353impl<N: Network> ToBytes for BlockLocators<N> {
354    fn write_le<W: Write>(&self, mut writer: W) -> IoResult<()> {
355        // Write the number of recent block hashes.
356        u32::try_from(self.recents.len()).map_err(error)?.write_le(&mut writer)?;
357        // Write the recent block hashes.
358        for (height, hash) in &self.recents {
359            height.write_le(&mut writer)?;
360            hash.write_le(&mut writer)?;
361        }
362
363        // Write the number of checkpoints.
364        u32::try_from(self.checkpoints.len()).map_err(error)?.write_le(&mut writer)?;
365        // Write the checkpoints.
366        for (height, hash) in &self.checkpoints {
367            height.write_le(&mut writer)?;
368            hash.write_le(&mut writer)?;
369        }
370        Ok(())
371    }
372}
373
374#[cfg(any(test, feature = "test"))]
375pub mod test_helpers {
376    use super::*;
377    use snarkvm::prelude::Field;
378
379    type CurrentNetwork = snarkvm::prelude::MainnetV0;
380
381    /// Simulates a block locator at the given height.
382    ///
383    /// The returned block locator is checked to be well-formed.
384    pub fn sample_block_locators(height: u32) -> BlockLocators<CurrentNetwork> {
385        // Create the recent locators.
386        let mut recents = IndexMap::new();
387        let recents_range = match height < NUM_RECENT_BLOCKS as u32 {
388            true => 0..=height,
389            false => (height - NUM_RECENT_BLOCKS as u32 + 1)..=height,
390        };
391        for i in recents_range {
392            recents.insert(i, (Field::<CurrentNetwork>::from_u32(i)).into());
393        }
394
395        // Create the checkpoint locators.
396        let mut checkpoints = IndexMap::new();
397        for i in (0..=height).step_by(CHECKPOINT_INTERVAL as usize) {
398            checkpoints.insert(i, (Field::<CurrentNetwork>::from_u32(i)).into());
399        }
400
401        // Construct the block locators.
402        BlockLocators::new(recents, checkpoints).unwrap()
403    }
404
405    /// Simulates a block locator at the given height, with a fork within NUM_RECENT_BLOCKS of the given height.
406    ///
407    /// The returned block locator is checked to be well-formed.
408    pub fn sample_block_locators_with_fork(height: u32, fork_height: u32) -> BlockLocators<CurrentNetwork> {
409        assert!(fork_height <= height, "Fork height must be less than or equal to the given height");
410        assert!(
411            height - fork_height < NUM_RECENT_BLOCKS as u32,
412            "Fork must be within NUM_RECENT_BLOCKS of the given height"
413        );
414
415        // Create the recent locators.
416        let mut recents = IndexMap::new();
417        let recents_range = match height < NUM_RECENT_BLOCKS as u32 {
418            true => 0..=height,
419            false => (height - NUM_RECENT_BLOCKS as u32 + 1)..=height,
420        };
421        for i in recents_range {
422            if i >= fork_height {
423                recents.insert(i, (-Field::<CurrentNetwork>::from_u32(i)).into());
424            } else {
425                recents.insert(i, (Field::<CurrentNetwork>::from_u32(i)).into());
426            }
427        }
428
429        // Create the checkpoint locators.
430        let mut checkpoints = IndexMap::new();
431        for i in (0..=height).step_by(CHECKPOINT_INTERVAL as usize) {
432            checkpoints.insert(i, (Field::<CurrentNetwork>::from_u32(i)).into());
433        }
434
435        // Construct the block locators.
436        BlockLocators::new(recents, checkpoints).unwrap()
437    }
438
439    /// A test to ensure that the sample block locators are valid.
440    #[test]
441    fn test_sample_block_locators() {
442        for expected_height in 0..=100_001u32 {
443            println!("Testing height - {expected_height}");
444
445            let expected_num_checkpoints = (expected_height / CHECKPOINT_INTERVAL) + 1;
446            let expected_num_recents = match expected_height < NUM_RECENT_BLOCKS as u32 {
447                true => expected_height + 1,
448                false => NUM_RECENT_BLOCKS as u32,
449            };
450
451            let block_locators = sample_block_locators(expected_height);
452            assert_eq!(block_locators.checkpoints.len(), expected_num_checkpoints as usize);
453            assert_eq!(block_locators.recents.len(), expected_num_recents as usize);
454            assert_eq!(block_locators.latest_locator_height(), expected_height);
455            // Note that `sample_block_locators` always returns well-formed block locators,
456            // so we don't need to check `is_valid()` here.
457        }
458    }
459}
460
461#[cfg(test)]
462mod tests {
463    use super::*;
464    use snarkvm::prelude::Field;
465
466    use core::ops::Range;
467
468    type CurrentNetwork = snarkvm::prelude::MainnetV0;
469
470    /// Simulates block locators for a ledger within the given `heights` range.
471    fn check_is_valid(checkpoints: IndexMap<u32, <CurrentNetwork as Network>::BlockHash>, heights: Range<u32>) {
472        for height in heights {
473            let mut recents = IndexMap::new();
474            for i in 0..NUM_RECENT_BLOCKS as u32 {
475                recents.insert(height + i, (Field::<CurrentNetwork>::from_u32(height + i)).into());
476
477                let block_locators =
478                    BlockLocators::<CurrentNetwork>::new_unchecked(recents.clone(), checkpoints.clone());
479                if height == 0 && recents.len() < NUM_RECENT_BLOCKS {
480                    // For the first NUM_RECENT_BLOCKS, ensure NUM_RECENT_BLOCKS - 1 or less is valid.
481                    block_locators.ensure_is_valid().unwrap();
482                } else if recents.len() < NUM_RECENT_BLOCKS {
483                    // After the first NUM_RECENT_BLOCKS blocks from genesis, ensure NUM_RECENT_BLOCKS - 1 or less is not valid.
484                    block_locators.ensure_is_valid().unwrap_err();
485                } else {
486                    // After the first NUM_RECENT_BLOCKS blocks from genesis, ensure NUM_RECENT_BLOCKS is valid.
487                    block_locators.ensure_is_valid().unwrap();
488                }
489            }
490            // Ensure NUM_RECENT_BLOCKS + 1 is not valid.
491            recents.insert(
492                height + NUM_RECENT_BLOCKS as u32,
493                (Field::<CurrentNetwork>::from_u32(height + NUM_RECENT_BLOCKS as u32)).into(),
494            );
495            let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(recents.clone(), checkpoints.clone());
496            block_locators.ensure_is_valid().unwrap_err();
497        }
498    }
499
500    /// Simulates block locators for a ledger within the given `heights` range.
501    fn check_is_consistent(
502        checkpoints: IndexMap<u32, <CurrentNetwork as Network>::BlockHash>,
503        heights: Range<u32>,
504        genesis_locators: BlockLocators<CurrentNetwork>,
505        second_locators: BlockLocators<CurrentNetwork>,
506    ) {
507        for height in heights {
508            let mut recents = IndexMap::new();
509            for i in 0..NUM_RECENT_BLOCKS as u32 {
510                recents.insert(height + i, (Field::<CurrentNetwork>::from_u32(height + i)).into());
511
512                let block_locators =
513                    BlockLocators::<CurrentNetwork>::new_unchecked(recents.clone(), checkpoints.clone());
514                block_locators.ensure_is_consistent_with(&block_locators).unwrap();
515
516                // Only test consistency when the block locators are valid to begin with.
517                let is_first_num_recents_blocks = height == 0 && recents.len() < NUM_RECENT_BLOCKS;
518                let is_num_recents_blocks = recents.len() == NUM_RECENT_BLOCKS;
519                if is_first_num_recents_blocks || is_num_recents_blocks {
520                    // Ensure the block locators are consistent with the genesis block locators.
521                    genesis_locators.ensure_is_consistent_with(&block_locators).unwrap();
522                    block_locators.ensure_is_consistent_with(&genesis_locators).unwrap();
523
524                    // Ensure the block locators are consistent with the block locators with two recent blocks.
525                    second_locators.ensure_is_consistent_with(&block_locators).unwrap();
526                    block_locators.ensure_is_consistent_with(&second_locators).unwrap();
527                }
528            }
529        }
530    }
531
532    #[test]
533    fn test_ensure_is_valid() {
534        let zero: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(0)).into();
535        let checkpoint_1: <CurrentNetwork as Network>::BlockHash =
536            (Field::<CurrentNetwork>::from_u32(CHECKPOINT_INTERVAL)).into();
537
538        // Ensure the block locators are valid.
539        for height in 0..10 {
540            let block_locators = test_helpers::sample_block_locators(height);
541            block_locators.ensure_is_valid().unwrap();
542        }
543
544        // Ensure the first NUM_RECENT blocks are valid.
545        let checkpoints = IndexMap::from([(0, zero)]);
546        let mut recents = IndexMap::new();
547        for i in 0..NUM_RECENT_BLOCKS {
548            recents.insert(i as u32, (Field::<CurrentNetwork>::from_u32(i as u32)).into());
549            let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(recents.clone(), checkpoints.clone());
550            block_locators.ensure_is_valid().unwrap();
551        }
552        // Ensure NUM_RECENT_BLOCKS + 1 is not valid.
553        recents.insert(NUM_RECENT_BLOCKS as u32, (Field::<CurrentNetwork>::from_u32(NUM_RECENT_BLOCKS as u32)).into());
554        let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(recents.clone(), checkpoints);
555        block_locators.ensure_is_valid().unwrap_err();
556
557        // Ensure block locators before the second checkpoint are valid.
558        let checkpoints = IndexMap::from([(0, zero)]);
559        check_is_valid(checkpoints, 0..(CHECKPOINT_INTERVAL - NUM_RECENT_BLOCKS as u32));
560
561        // Ensure the block locators after the second checkpoint are valid.
562        let checkpoints = IndexMap::from([(0, zero), (CHECKPOINT_INTERVAL, checkpoint_1)]);
563        check_is_valid(
564            checkpoints,
565            (CHECKPOINT_INTERVAL - NUM_RECENT_BLOCKS as u32 + 1)..(CHECKPOINT_INTERVAL * 2 - NUM_RECENT_BLOCKS as u32),
566        );
567    }
568
569    #[test]
570    fn test_ensure_is_valid_fails() {
571        let zero: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(0)).into();
572        let one: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(1)).into();
573
574        // Ensure an empty block locators is not valid.
575        let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(Default::default(), Default::default());
576        block_locators.ensure_is_valid().unwrap_err();
577
578        // Ensure internally-mismatching genesis block locators is not valid.
579        let block_locators =
580            BlockLocators::<CurrentNetwork>::new_unchecked(IndexMap::from([(0, zero)]), IndexMap::from([(0, one)]));
581        block_locators.ensure_is_valid().unwrap_err();
582
583        // Ensure internally-mismatching genesis block locators is not valid.
584        let block_locators =
585            BlockLocators::<CurrentNetwork>::new_unchecked(IndexMap::from([(0, one)]), IndexMap::from([(0, zero)]));
586        block_locators.ensure_is_valid().unwrap_err();
587
588        // Ensure internally-mismatching block locators with two recent blocks is not valid.
589        let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(
590            IndexMap::from([(0, one), (1, zero)]),
591            IndexMap::from([(0, zero)]),
592        );
593        block_locators.ensure_is_valid().unwrap_err();
594
595        // Ensure duplicate recent block hashes are not valid.
596        let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(
597            IndexMap::from([(0, zero), (1, zero)]),
598            IndexMap::from([(0, zero)]),
599        );
600        block_locators.ensure_is_valid().unwrap_err();
601
602        // Ensure insufficient checkpoints are not valid.
603        let mut recents = IndexMap::new();
604        for i in 0..NUM_RECENT_BLOCKS {
605            recents.insert(10_000 + i as u32, (Field::<CurrentNetwork>::from_u32(i as u32)).into());
606        }
607        let block_locators = BlockLocators::<CurrentNetwork>::new_unchecked(recents, IndexMap::from([(0, zero)]));
608        block_locators.ensure_is_valid().unwrap_err();
609    }
610
611    #[test]
612    fn test_ensure_is_consistent_with() {
613        let zero: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(0)).into();
614        let one: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(1)).into();
615
616        let genesis_locators =
617            BlockLocators::<CurrentNetwork>::new_unchecked(IndexMap::from([(0, zero)]), IndexMap::from([(0, zero)]));
618        let second_locators = BlockLocators::<CurrentNetwork>::new_unchecked(
619            IndexMap::from([(0, zero), (1, one)]),
620            IndexMap::from([(0, zero)]),
621        );
622
623        // Ensure genesis block locators is consistent with genesis block locators.
624        genesis_locators.ensure_is_consistent_with(&genesis_locators).unwrap();
625
626        // Ensure genesis block locators is consistent with block locators with two recent blocks.
627        genesis_locators.ensure_is_consistent_with(&second_locators).unwrap();
628        second_locators.ensure_is_consistent_with(&genesis_locators).unwrap();
629
630        // Ensure the block locators before the second checkpoint are valid.
631        let checkpoints = IndexMap::from([(0, Default::default())]);
632        check_is_consistent(
633            checkpoints,
634            0..(CHECKPOINT_INTERVAL - NUM_RECENT_BLOCKS as u32),
635            genesis_locators.clone(),
636            second_locators.clone(),
637        );
638
639        // Ensure the block locators after the second checkpoint are valid.
640        let checkpoints = IndexMap::from([(0, Default::default()), (CHECKPOINT_INTERVAL, Default::default())]);
641        check_is_consistent(
642            checkpoints,
643            (CHECKPOINT_INTERVAL - NUM_RECENT_BLOCKS as u32)..(CHECKPOINT_INTERVAL * 2 - NUM_RECENT_BLOCKS as u32),
644            genesis_locators,
645            second_locators,
646        );
647    }
648
649    #[test]
650    fn test_ensure_is_consistent_with_fails() {
651        let zero: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(0)).into();
652        let one: <CurrentNetwork as Network>::BlockHash = (Field::<CurrentNetwork>::from_u32(1)).into();
653
654        let genesis_locators =
655            BlockLocators::<CurrentNetwork>::new(IndexMap::from([(0, zero)]), IndexMap::from([(0, zero)])).unwrap();
656        let second_locators =
657            BlockLocators::<CurrentNetwork>::new(IndexMap::from([(0, zero), (1, one)]), IndexMap::from([(0, zero)]))
658                .unwrap();
659
660        let wrong_genesis_locators =
661            BlockLocators::<CurrentNetwork>::new(IndexMap::from([(0, one)]), IndexMap::from([(0, one)])).unwrap();
662        let wrong_second_locators =
663            BlockLocators::<CurrentNetwork>::new(IndexMap::from([(0, one), (1, zero)]), IndexMap::from([(0, one)]))
664                .unwrap();
665
666        genesis_locators.ensure_is_consistent_with(&wrong_genesis_locators).unwrap_err();
667        wrong_genesis_locators.ensure_is_consistent_with(&genesis_locators).unwrap_err();
668
669        genesis_locators.ensure_is_consistent_with(&wrong_second_locators).unwrap_err();
670        wrong_second_locators.ensure_is_consistent_with(&genesis_locators).unwrap_err();
671
672        second_locators.ensure_is_consistent_with(&wrong_genesis_locators).unwrap_err();
673        wrong_genesis_locators.ensure_is_consistent_with(&second_locators).unwrap_err();
674
675        second_locators.ensure_is_consistent_with(&wrong_second_locators).unwrap_err();
676        wrong_second_locators.ensure_is_consistent_with(&second_locators).unwrap_err();
677    }
678}
amareleo_node_sync/block_locators.rs

amareleo_node_sync/
block_locators.rs
