From 3ef6ed866d364d6f8c9136d0b6696f2b90e572be Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=97=E5=AE=87?= Date: Fri, 6 Feb 2026 15:19:50 +0000 Subject: [PATCH] feat(chain)!: Add `ApplyBlockError` for `prev_blockhash` validation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Introduce `ApplyBlockError` enum with two variants: - `MissingGenesis`: genesis block is missing or would be altered - `PrevBlockhashMismatch`: block's `prev_blockhash` doesn't match expected This replaces `MissingGenesisError` in several `LocalChain` methods: - `from_blocks` - `from_changeset` - `apply_changeset` Also adds test cases for `merge_chains` with `prev_blockhash` scenarios: - Update displaces invalid block below point of agreement - Update fills gap with matching `prev_blockhash` - Cascading eviction through multiple blocks 🤖 Generated with [Claude Code](https://claude.com/claude-code) Co-Authored-By: Claude --- crates/chain/src/local_chain.rs | 101 ++++++++++++++++++++----- crates/chain/tests/test_local_chain.rs | 98 ++++++++++++++++++++++++ crates/core/src/checkpoint.rs | 6 +- 3 files changed, 181 insertions(+), 24 deletions(-) diff --git a/crates/chain/src/local_chain.rs b/crates/chain/src/local_chain.rs index fd99e2ed..4e92e94d 100644 --- a/crates/chain/src/local_chain.rs +++ b/crates/chain/src/local_chain.rs @@ -15,7 +15,7 @@ use bitcoin::BlockHash; fn apply_changeset_to_checkpoint( mut init_cp: CheckPoint, changeset: &ChangeSet, -) -> Result, MissingGenesisError> +) -> Result, ApplyBlockError> where D: ToBlockHash + fmt::Debug + Clone, { @@ -48,7 +48,11 @@ where let new_tip = match base { Some(base) => base .extend(extension) - .expect("extension is strictly greater than base"), + // Since `extension` is in height order, the only failure case is `prev_blockhash` + // mismatch. + .map_err(|last_cp| ApplyBlockError::PrevBlockhashMismatch { + expected: last_cp.block_id(), + })?, None => LocalChain::from_blocks(extension)?.tip(), }; init_cp = new_tip; @@ -251,22 +255,27 @@ where /// /// The [`BTreeMap`] enforces the height order. However, the caller must ensure the blocks are /// all of the same chain. - pub fn from_blocks(blocks: BTreeMap) -> Result { + pub fn from_blocks(blocks: BTreeMap) -> Result { if !blocks.contains_key(&0) { - return Err(MissingGenesisError); + return Err(ApplyBlockError::MissingGenesis); } - Ok(Self { - tip: CheckPoint::from_blocks(blocks).expect("blocks must be in order"), - }) + CheckPoint::from_blocks(blocks) + .map(|tip| Self { tip }) + .map_err(|err| { + let last_cp = err.expect("must have atleast one block (genesis)"); + ApplyBlockError::PrevBlockhashMismatch { + expected: last_cp.block_id(), + } + }) } /// Construct a [`LocalChain`] from an initial `changeset`. - pub fn from_changeset(changeset: ChangeSet) -> Result { + pub fn from_changeset(changeset: ChangeSet) -> Result { let genesis_entry = changeset.blocks.get(&0).cloned().flatten(); let genesis_data = match genesis_entry { Some(data) => data, - None => return Err(MissingGenesisError), + None => return Err(ApplyBlockError::MissingGenesis), }; let (mut chain, _) = Self::from_genesis(genesis_data); @@ -310,7 +319,7 @@ where } /// Apply the given `changeset`. - pub fn apply_changeset(&mut self, changeset: &ChangeSet) -> Result<(), MissingGenesisError> { + pub fn apply_changeset(&mut self, changeset: &ChangeSet) -> Result<(), ApplyBlockError> { let old_tip = self.tip.clone(); let new_tip = apply_changeset_to_checkpoint(old_tip, changeset)?; self.tip = new_tip; @@ -485,6 +494,35 @@ impl FromIterator<(u32, D)> for ChangeSet { } } +/// Error when applying blocks to a local chain. +#[derive(Clone, Debug, PartialEq)] +pub enum ApplyBlockError { + /// Genesis block is missing or would be altered. + MissingGenesis, + /// Block's `prev_blockhash` doesn't match the expected block. + PrevBlockhashMismatch { + /// The block that `prev_blockhash` should reference. + expected: BlockId, + }, +} + +impl core::fmt::Display for ApplyBlockError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + ApplyBlockError::MissingGenesis => { + write!(f, "genesis block is missing or would be altered") + } + ApplyBlockError::PrevBlockhashMismatch { expected } => write!( + f, + "`prev_blockhash` doesn't match block at height {} ({})", + expected.height, expected.hash + ), + } + } +} + +impl core::error::Error for ApplyBlockError {} + /// An error which occurs when a [`LocalChain`] is constructed without a genesis checkpoint. #[derive(Clone, Debug, PartialEq)] pub struct MissingGenesisError; @@ -592,6 +630,30 @@ fn merge_chains( where D: ToBlockHash + fmt::Debug + Clone, { + // Apply the changeset to produce the final merged chain. + // + // `PrevBlockhashMismatch` should never happen because the merge iteration detects + // `prev_blockhash` conflicts and resolves them by invalidating conflicting blocks (setting + // them to `None` in the changeset) before we reach this point. + fn finish( + original_tip: CheckPoint, + changeset: ChangeSet, + ) -> Result<(CheckPoint, ChangeSet), CannotConnectError> + where + D: ToBlockHash + fmt::Debug + Clone, + { + let new_tip = apply_changeset_to_checkpoint(original_tip, &changeset).map_err(|err| { + debug_assert!( + matches!(err, ApplyBlockError::MissingGenesis), + "PrevBlockhashMismatch should never happen" + ); + CannotConnectError { + try_include_height: 0, + } + })?; + Ok((new_tip, changeset)) + } + let mut changeset = ChangeSet::::default(); let mut orig = original_tip.entry_iter(); @@ -676,11 +738,13 @@ where if is_update_height_superset_of_original { return Ok((update_tip, changeset)); } else { - let new_tip = apply_changeset_to_checkpoint(original_tip, &changeset) - .map_err(|_| CannotConnectError { - try_include_height: 0, - })?; - return Ok((new_tip, changeset)); + return finish(original_tip, changeset); + } + } + // Update placeholder with real data (if necessary). + if let Some(u_data) = u.data_ref() { + if o.is_placeholder() { + changeset.blocks.insert(u.height(), Some(u_data.clone())); } } } else { @@ -715,10 +779,5 @@ where } } - let new_tip = apply_changeset_to_checkpoint(original_tip, &changeset).map_err(|_| { - CannotConnectError { - try_include_height: 0, - } - })?; - Ok((new_tip, changeset)) + finish(original_tip, changeset) } diff --git a/crates/chain/tests/test_local_chain.rs b/crates/chain/tests/test_local_chain.rs index 33f64073..109ac5f5 100644 --- a/crates/chain/tests/test_local_chain.rs +++ b/crates/chain/tests/test_local_chain.rs @@ -1062,6 +1062,14 @@ fn merge_chains_with_prev_blockhash() { hash: hash!("B'"), prev_hash: hash!("A"), }; + let block_a_alt = TestBlock { + hash: hash!("A_alt"), + prev_hash: hash!("_"), + }; + let block_d = TestBlock { + hash: hash!("D"), + prev_hash: hash!("C"), + }; [ // Test: prev_blockhash can invalidate blocks in the original chain @@ -1195,6 +1203,96 @@ fn merge_chains_with_prev_blockhash() { try_include_height: 1, }), }, + // Test: update displaces invalid block below point of agreement + // + // ```text + // | 0 | 1 | 2 | 4 | + // chain | _ C(prev=B) D + // update | _ A D + // result | _ A D + // ``` + // + // Both chains agree on D at height 4. Chain has C at height 2 with `prev_blockhash = B`, + // but no B exists. Update introduces A at height 1, which displaces C because + // C's `prev_blockhash` ("B") doesn't match A's hash ("A"). + // + // Note: This can only happen if chains are constructed incorrectly. + TestLocalChain { + name: "update displaces invalid block below point of agreement", + chain: LocalChain::from_blocks( + [(0, block_genesis), (2, block_c), (4, block_d_linked)].into(), + ) + .unwrap(), + update: CheckPoint::from_blocks([ + (0, block_genesis), + (1, block_a), + (4, block_d_linked), + ]) + .unwrap(), + exp: ExpectedResult::Ok { + changeset: &[(1, Some(block_a)), (2, None)], + init_changeset: &[ + (0, Some(block_genesis)), + (1, Some(block_a)), + (4, Some(block_d_linked)), + ], + }, + }, + // Test: update fills gap with matching prev_blockhash + // + // ```text + // | 0 | 1 | 2 | + // chain | _ B(prev=A) + // update | _ A B + // result | _ A B + // ``` + // + // Chain has gap at height 1. Update provides A which matches B's `prev_blockhash`. + // The chains connect perfectly. + TestLocalChain { + name: "update fills gap with matching prev_blockhash", + chain: LocalChain::from_blocks([(0, block_genesis), (2, block_b)].into()).unwrap(), + update: CheckPoint::from_blocks([(0, block_genesis), (1, block_a), (2, block_b)]) + .unwrap(), + exp: ExpectedResult::Ok { + changeset: &[(1, Some(block_a))], + init_changeset: &[ + (0, Some(block_genesis)), + (1, Some(block_a)), + (2, Some(block_b)), + ], + }, + }, + // Test: cascading eviction through multiple blocks + // + // ```text + // | 0 | 1 | 2 | 3 | 4 | + // chain | _ A B(prev=A) C(prev=B) D(prev=C) + // update | _ A_alt + // result | _ A_alt + // ``` + // + // Update replaces A with A_alt. B's `prev_blockhash = A` doesn't match A_alt, + // so B is evicted. C and D depend on B via prev_blockhash, so they cascade evict. + TestLocalChain { + name: "cascading eviction through multiple blocks", + chain: LocalChain::from_blocks( + [ + (0, block_genesis), + (1, block_a), + (2, block_b), + (3, block_c), + (4, block_d), + ] + .into(), + ) + .unwrap(), + update: CheckPoint::from_blocks([(0, block_genesis), (1, block_a_alt)]).unwrap(), + exp: ExpectedResult::Ok { + changeset: &[(1, Some(block_a_alt)), (2, None), (3, None), (4, None)], + init_changeset: &[(0, Some(block_genesis)), (1, Some(block_a_alt))], + }, + }, ] .into_iter() .for_each(TestLocalChain::run); diff --git a/crates/core/src/checkpoint.rs b/crates/core/src/checkpoint.rs index 8d7a60ed..842949b4 100644 --- a/crates/core/src/checkpoint.rs +++ b/crates/core/src/checkpoint.rs @@ -284,13 +284,13 @@ where /// Construct from an iterator of block data. /// /// Returns `Err(None)` if `blocks` doesn't yield any data. If the blocks are not in ascending - /// height order, then returns an `Err(..)` containing the last checkpoint that would have been - /// extended. + /// height order, or there are any `prev_blockhash` mismatches, then returns an `Err(..)` + /// containing the last checkpoint that would have been extended. pub fn from_blocks(blocks: impl IntoIterator) -> Result> { let mut blocks = blocks.into_iter(); let (height, data) = blocks.next().ok_or(None)?; let mut cp = CheckPoint::new(height, data); - cp = cp.extend(blocks)?; + cp = cp.extend(blocks).map_err(Some)?; Ok(cp) } -- 2.49.0