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