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