check_next_block.rs
1 // Copyright (c) 2019-2025 Alpha-Delta Network Inc. 2 // This file is part of the alphavm 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 super::*; 17 18 use crate::{narwhal::BatchHeader, puzzle::SolutionID}; 19 20 use anyhow::{Context, bail}; 21 22 /// Wrapper for a block that has a valid subDAG, but where the block header, 23 /// solutions, and transmissions have not been verified yet. 24 /// 25 /// This type is created by `Ledger::check_block_subdag` and consumed by `Ledger::check_block_content`. 26 #[derive(Clone, PartialEq, Eq)] 27 pub struct PendingBlock<N: Network>(Block<N>); 28 29 impl<N: Network> Deref for PendingBlock<N> { 30 type Target = Block<N>; 31 32 fn deref(&self) -> &Block<N> { 33 &self.0 34 } 35 } 36 37 impl<N: Network> Debug for PendingBlock<N> { 38 fn fmt(&self, f: &mut Formatter) -> fmt::Result { 39 write!(f, "PendingBlock {{ height: {}, hash: {} }}", self.height(), self.hash()) 40 } 41 } 42 43 /// Error returned by [`Self::check_block_subdag`] and [`Self::check_block_subdag_inner`]. 44 /// 45 /// This allows parsing for begning errors, such as the block already existing in the ledger. 46 #[derive(thiserror::Error, Debug)] 47 pub enum CheckBlockError<N: Network> { 48 #[error("Block with hash {hash} already exists in the ledger")] 49 BlockAlreadyExists { hash: N::BlockHash }, 50 #[error("Block has invalid height. Expected {expected}, but got {actual}")] 51 InvalidHeight { expected: u32, actual: u32 }, 52 #[error("Block has invalid hash")] 53 InvalidHash, 54 /// An error related to the given prefix of pending blocks. 55 #[error("The prefix as an error at index {index} - {error:?}")] 56 InvalidPrefix { index: usize, error: Box<CheckBlockError<N>> }, 57 #[error("The block contains solution '{solution_id}', but it already exists in the ledger")] 58 SolutionAlreadyExists { solution_id: SolutionID<N> }, 59 #[error("Failed to speculate over unconfirmed transactions - {inner}")] 60 SpeculationFailed { inner: anyhow::Error }, 61 #[error("Failed to verify block - {inner}")] 62 VerificationFailed { inner: anyhow::Error }, 63 #[error("Prover '{prover_address}' has reached their solution limit for the current epoch")] 64 SolutionLimitReached { prover_address: Address<N> }, 65 #[error("The previous block should contain solution '{solution_id}', but it does not exist in the ledger")] 66 PreviousSolutionNotFound { solution_id: SolutionID<N> }, 67 #[error("The previous block should contain solution '{transaction_id}', but it does not exist in the ledger")] 68 PreviousTransactionNotFound { transaction_id: N::TransactionID }, 69 #[error(transparent)] 70 Other(#[from] anyhow::Error), 71 } 72 73 impl<N: Network> CheckBlockError<N> { 74 pub fn into_anyhow(self) -> anyhow::Error { 75 match self { 76 Self::Other(err) => err, 77 _ => anyhow::anyhow!("{self:?}"), 78 } 79 } 80 } 81 82 impl<N: Network, C: ConsensusStorage<N>> Ledger<N, C> { 83 /// Checks that the subDAG in a given block is valid, but does not fully verify the block. 84 /// 85 /// # Arguments 86 /// * `block` - The block to check. 87 /// * `prefix` - A sequence of blocks between the block to check and the current height of the ledger. 88 /// 89 /// # Returns 90 /// * On success, a [`PendingBlock`] representing the block that was checked. Once the prefix of this block has been fully added to the ledger, 91 /// the [`PendingBlock`] can then be passed to [`Self::check_block_content`] to fully verify it. 92 /// * On failure, a [`CheckBlockError`] describing the reason the block was rejected. 93 /// 94 /// # Notes 95 /// * This does *not* check that the header of the block is correct or execute/verify any of the transmissions contained within it. 96 /// * In most cases, you want to use [`Self::check_next_block`] instead to perform a full verification. 97 /// * This will reject any blocks with a height <= the current height and any blocks with a height >= the current height + GC. 98 /// For the former, a valid block already exists and,for the latter, the comittee is still unknown. 99 /// * This function executes atomically, in that there is guaranteed to be no concurrent updates to the ledger during its execution. 100 /// However there are no ordering guarantees *between* multiple invocations of this function, [`Self::check_block_content`] and [`Self::advance_to_next_block`]. 101 pub fn check_block_subdag( 102 &self, 103 block: Block<N>, 104 prefix: &[PendingBlock<N>], 105 ) -> Result<PendingBlock<N>, CheckBlockError<N>> { 106 self.check_block_subdag_inner(&block, prefix)?; 107 Ok(PendingBlock(block)) 108 } 109 110 fn check_block_subdag_inner(&self, block: &Block<N>, prefix: &[PendingBlock<N>]) -> Result<(), CheckBlockError<N>> { 111 // Grab a lock to the latest_block in the ledger, to prevent concurrent writes to the ledger, 112 // and to ensure that this check is atomic. 113 let latest_block = self.current_block.read(); 114 115 // First check that the heights and hashes of the pending block sequence and of the new block are correct. 116 // The hash checks should be redundant, but we perform them out of extra caution. 117 let mut expected_height = latest_block.height() + 1; 118 for (index, prefix_block) in prefix.iter().enumerate() { 119 if prefix_block.height() != expected_height { 120 return Err(CheckBlockError::InvalidPrefix { 121 index, 122 error: Box::new(CheckBlockError::InvalidHeight { 123 expected: expected_height, 124 actual: prefix_block.height(), 125 }), 126 }); 127 } 128 129 if self.contains_block_hash(&prefix_block.hash())? { 130 return Err(CheckBlockError::InvalidPrefix { 131 index, 132 error: Box::new(CheckBlockError::BlockAlreadyExists { hash: prefix_block.hash() }), 133 }); 134 } 135 136 expected_height += 1; 137 } 138 139 if self.contains_block_hash(&block.hash())? { 140 return Err(CheckBlockError::BlockAlreadyExists { hash: block.hash() }); 141 } 142 143 if block.height() != expected_height { 144 return Err(CheckBlockError::InvalidHeight { expected: expected_height, actual: block.height() }); 145 } 146 147 // Ensure the certificates in the block subdag have met quorum requirements. 148 self.check_block_subdag_quorum(block)?; 149 150 // Determine if the block subdag is correctly constructed and is not a combination of multiple subdags. 151 self.check_block_subdag_atomicity(block)?; 152 153 // Ensure that all leaves of the subdag point to valid batches in other subdags/blocks. 154 self.check_block_subdag_leaves(block, prefix)?; 155 156 Ok(()) 157 } 158 159 /// Checks the given block is a valid next block with regard to the current state/height of the Ledger. 160 /// 161 /// # Panics 162 /// This function panics if called from an async context. 163 pub fn check_next_block<R: CryptoRng + Rng>(&self, block: &Block<N>, rng: &mut R) -> Result<()> { 164 self.check_block_subdag_inner(block, &[]).map_err(|err| err.into_anyhow())?; 165 self.check_block_content_inner(block, rng).map_err(|err| err.into_anyhow())?; 166 167 Ok(()) 168 } 169 170 /// Takes a pending block and performs the remaining checks to full verify it. 171 /// 172 /// # Arguments 173 /// This takes a [`PendingBlock`] as input, which is the output of a successful call to [`Self::check_block_subdag`]. 174 /// The latter already verified the block's DAG and certificate signatures. 175 /// 176 /// # Return Value 177 /// This returns a [`Block`] on success representing the fully verified block. 178 /// 179 /// # Notes 180 /// - This check can only succeed for pending blocks that are a direct successor of the latest block in the ledger. 181 /// - Execution of this function is atomic, and there is guaranteed to be no concurrent update to the ledger during its execution. 182 /// - Even though this function may return `Ok(block)`, advancing the ledger to this block may still fail, if there was an update to the ledger 183 /// *between* calling `check_block_content` and `advance_to_next_block`. 184 /// If your implementation requires atomicity across these two steps, you need to implement your own locking mechanism. 185 /// 186 /// # Panics 187 /// This function panics if called from an async context. 188 pub fn check_block_content<R: CryptoRng + Rng>( 189 &self, 190 block: PendingBlock<N>, 191 rng: &mut R, 192 ) -> Result<Block<N>, CheckBlockError<N>> { 193 self.check_block_content_inner(&block.0, rng)?; 194 Ok(block.0) 195 } 196 197 /// # Panics 198 /// This function panics if called from an async context. 199 fn check_block_content_inner<R: CryptoRng + Rng>( 200 &self, 201 block: &Block<N>, 202 rng: &mut R, 203 ) -> Result<(), CheckBlockError<N>> { 204 let latest_block = self.current_block.read(); 205 206 // Ensure, again, that the ledger has not advanced yet. This prevents cryptic errors form appearing during the block check. 207 if block.height() != latest_block.height() + 1 { 208 return Err(CheckBlockError::InvalidHeight { expected: latest_block.height() + 1, actual: block.height() }); 209 } 210 211 // Ensure the solutions do not already exist. 212 for solution_id in block.solutions().solution_ids() { 213 if self.contains_solution_id(solution_id)? { 214 return Err(CheckBlockError::SolutionAlreadyExists { solution_id: *solution_id }); 215 } 216 } 217 218 // Determine if the block timestamp should be included. 219 let block_timestamp = (block.height() >= N::CONSENSUS_HEIGHT(ConsensusVersion::V12).unwrap_or_default()) 220 .then_some(block.timestamp()); 221 // Construct the finalize state. 222 let state = FinalizeGlobalState::new::<N>( 223 block.round(), 224 block.height(), 225 block_timestamp, 226 block.cumulative_weight(), 227 block.cumulative_proof_target(), 228 block.previous_hash(), 229 )?; 230 231 // Ensure speculation over the unconfirmed transactions is correct and ensure each transaction is well-formed and unique. 232 let time_since_last_block = block.timestamp().saturating_sub(self.latest_timestamp()); 233 let ratified_finalize_operations = self.vm.check_speculate( 234 state, 235 time_since_last_block, 236 block.ratifications(), 237 block.solutions(), 238 block.transactions(), 239 rng, 240 )?; 241 242 // Retrieve the committee lookback. 243 let committee_lookback = self 244 .get_committee_lookback_for_round(block.round())? 245 .ok_or(anyhow!("Failed to fetch committee lookback for round {}", block.round()))?; 246 247 // Retrieve the previous committee lookback. 248 let previous_committee_lookback = { 249 // Calculate the penultimate round, which is the round before the anchor round. 250 let penultimate_round = block.round().saturating_sub(1); 251 // Output the committee lookback for the penultimate round. 252 self.get_committee_lookback_for_round(penultimate_round)? 253 .ok_or(anyhow!("Failed to fetch committee lookback for round {penultimate_round}"))? 254 }; 255 256 // Ensure the block is correct. 257 let (expected_existing_solution_ids, expected_existing_transaction_ids) = block 258 .verify( 259 &latest_block, 260 self.latest_state_root(), 261 &previous_committee_lookback, 262 &committee_lookback, 263 self.puzzle(), 264 self.latest_epoch_hash()?, 265 OffsetDateTime::now_utc().unix_timestamp(), 266 ratified_finalize_operations, 267 ) 268 .map_err(|err| CheckBlockError::VerificationFailed { inner: err })?; 269 270 // Ensure that the provers are within their stake bounds. 271 if let Some(solutions) = block.solutions().deref() { 272 let mut accepted_solutions: IndexMap<Address<N>, u64> = IndexMap::new(); 273 for solution in solutions.values() { 274 let prover_address = solution.address(); 275 let num_accepted_solutions = *accepted_solutions.get(&prover_address).unwrap_or(&0); 276 // Check if the prover has reached their solution limit. 277 if self.is_solution_limit_reached(&prover_address, num_accepted_solutions) { 278 return Err(CheckBlockError::SolutionLimitReached { prover_address }); 279 } 280 // Track the already accepted solutions. 281 *accepted_solutions.entry(prover_address).or_insert(0) += 1; 282 } 283 } 284 285 // Ensure that each existing solution ID from the block exists in the ledger. 286 for existing_solution_id in expected_existing_solution_ids { 287 if !self.contains_solution_id(&existing_solution_id)? { 288 return Err(CheckBlockError::PreviousSolutionNotFound { solution_id: existing_solution_id }); 289 } 290 } 291 292 // Ensure that each existing transaction ID from the block exists in the ledger. 293 for existing_transaction_id in expected_existing_transaction_ids { 294 if !self.contains_transaction_id(&existing_transaction_id)? { 295 return Err(CheckBlockError::PreviousTransactionNotFound { transaction_id: existing_transaction_id }); 296 } 297 } 298 299 Ok(()) 300 } 301 302 /// Check that leaves in the subdag point to batches in other blocks that are valid. 303 /// 304 // 305 /// # Arguments 306 /// * `block` - The block to check. 307 /// * `prefix` - A sequence of [`PendingBlock`]s between the block to check and the current height of the ledger. 308 /// 309 /// # Notes 310 /// This only checks that leaves point to valid batch in the previous round, and *not* hat the batches are signed correctly 311 /// or that the edges are valid, as those checks already happened when the node received the batch. 312 fn check_block_subdag_leaves(&self, block: &Block<N>, prefix: &[PendingBlock<N>]) -> Result<()> { 313 // Check if the block has a subdag. 314 let Authority::Quorum(subdag) = block.authority() else { 315 return Ok(()); 316 }; 317 318 let previous_certs: HashSet<_> = prefix 319 .iter() 320 .filter_map(|block| match block.authority() { 321 Authority::Quorum(subdag) => Some(subdag.certificate_ids()), 322 Authority::Beacon(_) => None, 323 }) 324 .flatten() 325 .collect(); 326 327 // Store the IDs of all certificates in this subDAG. 328 // This allows determining which edges point to other subDAGs/blocks. 329 let subdag_certs: HashSet<_> = subdag.certificate_ids().collect(); 330 331 // Generate a set of all external certificates this subDAG references. 332 // If multiple certificates reference the same external certificate, the id and round number will be 333 // identical and the set will contain only one entry for the external certificate. 334 let leaf_edges: HashSet<_> = subdag 335 .certificates() 336 .flat_map(|cert| cert.previous_certificate_ids().iter().map(|prev_id| (cert.round() - 1, prev_id))) 337 .filter(|(_, prev_id)| !subdag_certs.contains(prev_id)) 338 .collect(); 339 340 cfg_iter!(leaf_edges).try_for_each(|(prev_round, prev_id)| { 341 if prev_round + (BatchHeader::<N>::MAX_GC_ROUNDS as u64) - 1 <= block.round() { 342 // If the previous round is at the end of GC, we cannot (and do not need to) verify the next batch. 343 // For this leaf we are at the maximum length of the DAG, so any following batches are not allowed 344 // to be part of the block and, thus, a malicious actor cannot remove them. 345 return Ok::<(), Error>(()); 346 } 347 348 // Ensure that the certificate is associated with a previous block. 349 if !previous_certs.contains(prev_id) && !self.vm.block_store().contains_block_for_certificate(prev_id)? { 350 bail!( 351 "Batch(es) in the block point(s) to a certificate {prev_id} in round {prev_round} that is not associated with a previous block" 352 ) 353 } 354 355 Ok(()) 356 }) 357 } 358 359 /// Check that the certificates in the block subdag have met quorum requirements. 360 /// 361 /// Called by [`Self::check_block_subdag`] 362 fn check_block_subdag_quorum(&self, block: &Block<N>) -> Result<()> { 363 // Check if the block has a subdag. 364 let subdag = match block.authority() { 365 Authority::Quorum(subdag) => subdag, 366 _ => return Ok(()), 367 }; 368 369 // Check that all certificates on each round have met quorum requirements. 370 cfg_iter!(subdag).try_for_each(|(round, certificates)| { 371 // Retrieve the committee lookback for the round. 372 let committee_lookback = self 373 .get_committee_lookback_for_round(*round) 374 .with_context(|| format!("Failed to get committee lookback for round {round}"))? 375 .ok_or_else(|| anyhow!("No committee lookback for round {round}"))?; 376 377 // Check that each certificate for this round has met quorum requirements. 378 // Note that we do not need to check the quorum requirement for the previous certificates 379 // because that is done during construction in `BatchCertificate::new`. 380 cfg_iter!(certificates).try_for_each(|certificate| { 381 // Collect the certificate signers. 382 let mut signers: HashSet<_> = 383 certificate.signatures().map(|signature| signature.to_address()).collect(); 384 // Append the certificate author. 385 signers.insert(certificate.author()); 386 387 // Ensure that the signers of the certificate reach the quorum threshold. 388 ensure!( 389 committee_lookback.is_quorum_threshold_reached(&signers), 390 "Certificate '{}' for round {round} does not meet quorum requirements", 391 certificate.id() 392 ); 393 394 Ok::<_, Error>(()) 395 })?; 396 397 Ok::<_, Error>(()) 398 })?; 399 400 Ok(()) 401 } 402 403 /// Checks that the block subdag can not be split into multiple valid subdags. 404 /// 405 /// Called by [`Self::check_block_subdag`] 406 fn check_block_subdag_atomicity(&self, block: &Block<N>) -> Result<()> { 407 // Returns `true` if there is a path from the previous certificate to the current certificate. 408 fn is_linked<N: Network>( 409 subdag: &Subdag<N>, 410 previous_certificate: &BatchCertificate<N>, 411 current_certificate: &BatchCertificate<N>, 412 ) -> Result<bool> { 413 // Initialize the list containing the traversal. 414 let mut traversal = vec![current_certificate]; 415 // Iterate over the rounds from the current certificate to the previous certificate. 416 for round in (previous_certificate.round()..current_certificate.round()).rev() { 417 // Retrieve all of the certificates for this past round. 418 let certificates = subdag.get(&round).ok_or(anyhow!("No certificates found for round {round}"))?; 419 // Filter the certificates to only include those that are in the traversal. 420 traversal = certificates 421 .into_iter() 422 .filter(|p| traversal.iter().any(|c| c.previous_certificate_ids().contains(&p.id()))) 423 .collect(); 424 } 425 Ok(traversal.contains(&previous_certificate)) 426 } 427 428 // Check if the block has a subdag. 429 let subdag = match block.authority() { 430 Authority::Quorum(subdag) => subdag, 431 _ => return Ok(()), 432 }; 433 434 // Iterate over the rounds to find possible leader certificates. 435 for round in (self.latest_round().saturating_add(2)..=subdag.anchor_round().saturating_sub(2)).rev().step_by(2) 436 { 437 // Retrieve the previous committee lookback. 438 let previous_committee_lookback = self 439 .get_committee_lookback_for_round(round)? 440 .ok_or_else(|| anyhow!("No committee lookback found for round {round}"))?; 441 442 // Compute the leader for the commit round. 443 let computed_leader = previous_committee_lookback 444 .get_leader(round) 445 .with_context(|| format!("Failed to compute leader for round {round}"))?; 446 447 // Retrieve the previous leader certificates. 448 let previous_certificate = match subdag.get(&round).and_then(|certificates| { 449 certificates.iter().find(|certificate| certificate.author() == computed_leader) 450 }) { 451 Some(cert) => cert, 452 None => continue, 453 }; 454 455 // Determine if there is a path between the previous certificate and the subdag's leader certificate. 456 if is_linked(subdag, previous_certificate, subdag.leader_certificate())? { 457 bail!( 458 "The previous certificate should not be linked to the current certificate in block {}", 459 block.height() 460 ); 461 } 462 } 463 464 Ok(()) 465 } 466 }