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