zakura-state 11.0.0

//! Consensus critical contextual checks

use std::{borrow::Borrow, sync::Arc};

use zakura_chain::{
    amount::{NegativeAllowed, NonNegative},
    block::{
        self, merkle::AuthDataRoot, Block, ChainHistoryBlockTxAuthCommitmentHash, CommitmentError,
    },
    history_tree::HistoryTree,
    parameters::{Network, NetworkUpgrade},
    value_balance::ValueBalance,
    work::difficulty::CompactDifficulty,
};

use crate::{
    service::{
        block_iter::any_chain_ancestor_iter,
        check::difficulty::pow_adjustment_block_span_for_height, finalized_state::ZakuraDb,
        non_finalized_state::NonFinalizedState,
    },
    BoxError, SemanticallyVerifiedBlock, ValidateContextError,
};

// use self as check
use super::check;

// These types are used in doc links
#[allow(unused_imports)]
use crate::service::non_finalized_state::Chain;

pub(crate) mod anchors;
pub(crate) mod difficulty;
pub(crate) mod nullifier;
pub(crate) mod utxo;

#[cfg(feature = "internal-bench")]
#[doc(hidden)]
pub use utxo::remaining_transaction_value;

pub use utxo::transparent_coinbase_spend;

#[cfg(test)]
mod tests;

pub(crate) use difficulty::AdjustedDifficulty;

/// Checks that the block at `height` does not make the ZIP 234 NSM value balance negative.
///
/// `value_pools` are the chain value pools before the block, and `block_value_pool_change`
/// is the block's change to them.
///
/// # Consensus
///
/// > [NU7 onward] If NsmValueBalance(height) would become negative in the block chain
/// > created as a result of accepting a block at height, then all nodes MUST reject the
/// > block as invalid.
///
/// The rule holds from NU7, not from the later reissuance start height. Between the two
/// no block claims a bonus, so nothing there can drive the balance negative, but matching
/// the draft costs nothing and leaves one rule instead of two.
///
/// Check before adding pools so an overdraw reports this consensus rule.
#[allow(clippy::unwrap_in_result)]
pub(crate) fn nsm_value_balance_is_non_negative(
    network: &Network,
    height: block::Height,
    value_pools: &ValueBalance<NonNegative>,
    block_value_pool_change: &ValueBalance<NegativeAllowed>,
) -> Result<(), ValidateContextError> {
    let nu7_active = NetworkUpgrade::Nu7
        .activation_height(network)
        .is_some_and(|nu7| height >= nu7);

    if !nu7_active {
        return Ok(());
    }

    let balance_before = value_pools.nsm_value_balance_amount();
    let balance_change = block_value_pool_change.nsm_value_balance_amount();

    let balance_after = (balance_before + balance_change).map_err(|_| {
        ValidateContextError::NegativeNsmValueBalance {
            height,
            balance_before,
            balance_change,
        }
    })?;

    if balance_after.zatoshis() < 0 {
        return Err(ValidateContextError::NegativeNsmValueBalance {
            height,
            balance_before,
            balance_change,
        });
    }

    Ok(())
}

/// Returns the most recent difficulty-context entries that validating a block at
/// `candidate_height` reads.
///
/// The candidate block's upgrade selects the averaging window, so ZIP 218 widens
/// this context at NU7.
pub(crate) fn difficulty_context<C: IntoIterator>(
    network: &Network,
    candidate_height: block::Height,
    context: C,
) -> Vec<C::Item> {
    context
        .into_iter()
        .take(pow_adjustment_block_span_for_height(
            network,
            candidate_height,
        ))
        .collect()
}

/// Check that the semantically verified block is contextually valid for `network`,
/// based on the `finalized_tip_height` and `relevant_headers`.
///
/// This function performs checks that require a small number of recent blocks,
/// including previous hash, previous height, and block difficulty.
///
/// The relevant headers are the ancestors of `block`, starting with its parent at
/// `parent_height`. Only headers are read, because the difficulty context spans
/// up to `MAX_POW_ADJUSTMENT_BLOCK_SPAN` blocks and only needs their difficulty and time.
#[tracing::instrument(skip(semantically_verified, finalized_tip_height, relevant_headers))]
pub(crate) fn block_is_valid_for_recent_chain<C>(
    semantically_verified: &SemanticallyVerifiedBlock,
    network: &Network,
    finalized_tip_height: Option<block::Height>,
    parent_height: Option<block::Height>,
    relevant_headers: C,
) -> Result<(), ValidateContextError>
where
    C: IntoIterator,
    C::Item: Borrow<block::Header>,
{
    block_is_valid_for_recent_chain_data(
        &semantically_verified.block,
        semantically_verified.height,
        network,
        finalized_tip_height,
        parent_height,
        relevant_headers,
    )
}

/// Checks the recent-chain rules required for prepared mined-block relay.
pub(crate) fn block_is_valid_for_recent_chain_data<C>(
    candidate_block: &Block,
    candidate_height: block::Height,
    network: &Network,
    finalized_tip_height: Option<block::Height>,
    parent_height: Option<block::Height>,
    relevant_headers: C,
) -> Result<(), ValidateContextError>
where
    C: IntoIterator,
    C::Item: Borrow<block::Header>,
{
    let finalized_tip_height = finalized_tip_height
        .expect("finalized state must contain at least one block to do contextual validation");
    check::block_is_not_orphaned(finalized_tip_height, candidate_height)?;

    let relevant_headers = difficulty_context(network, candidate_height, relevant_headers);

    let Some(parent_height) = parent_height.filter(|_| !relevant_headers.is_empty()) else {
        warn!(
            ?candidate_height,
            ?finalized_tip_height,
            "state must contain parent block to do contextual validation"
        );

        return Err(ValidateContextError::NotReadyToBeCommitted);
    };

    check::height_one_more_than_parent_height(parent_height, candidate_height)?;

    // skip this check during tests if we don't have enough blocks in the chain
    // process_queued also checks the chain length, so we can skip this assertion during testing
    // (tests that want to check this code should use the correct number of blocks)
    //
    // TODO: accept a NotReadyToBeCommitted error in those tests instead
    #[cfg(test)]
    if relevant_headers.len() < pow_adjustment_block_span_for_height(network, candidate_height) {
        return Ok(());
    }

    // In production, blocks without enough context are invalid.
    //
    // The BlockVerifierRouter makes sure that the first 1 million blocks (or more) are
    // checkpoint verified. The state queues and block write task make sure that blocks are
    // committed in strict height order. But this function is only called on semantically
    // verified blocks, so there will be at least 1 million blocks in the state when it is
    // called. So this error should never happen on Mainnet or the default Testnet.
    //
    // It's okay to use a relevant chain shorter than the adjustment span, because
    // the MedianTime function uses height 0 if passed a negative height by the ActualTimespan function:
    // > ActualTimespan(height : N) := MedianTime(height) − MedianTime(height − PoWAveragingWindow)
    // > MedianTime(height : N) := median([[ nTime(𝑖) for 𝑖 from max(0, height − PoWMedianBlockSpan) up to height − 1 ]])
    // and the MeanTarget function only requires the past `PoWAveragingWindow` (17) blocks for heights above 17,
    // > PoWLimit, if height ≤ PoWAveragingWindow
    // > ([ToTarget(nBits(𝑖)) for 𝑖 from height−PoWAveragingWindow up to height−1]) otherwise
    //
    // See the 'Difficulty Adjustment' section (page 132) in the Zcash specification.
    #[cfg(not(test))]
    if relevant_headers.is_empty() {
        return Err(ValidateContextError::NotReadyToBeCommitted);
    }

    let relevant_data = relevant_headers
        .iter()
        .map(|header| (header.borrow().difficulty_threshold, header.borrow().time));
    let difficulty_adjustment =
        AdjustedDifficulty::new_from_block(candidate_block, network, relevant_data)
            .map_err(|_| ValidateContextError::NotReadyToBeCommitted)?;
    check::difficulty_threshold_and_time_are_valid(
        candidate_block.header.difficulty_threshold,
        difficulty_adjustment,
    )?;

    Ok(())
}

/// Check that a header is contextually valid for `network`, using the previous
/// header height and recent held header data.
#[tracing::instrument(skip(candidate_header, network, relevant_headers))]
#[cfg(test)]
pub(crate) fn header_is_valid_for_recent_chain<C>(
    candidate_header: &block::Header,
    previous_block_height: block::Height,
    network: &Network,
    relevant_headers: C,
) -> Result<(), ValidateContextError>
where
    C: IntoIterator<Item = (CompactDifficulty, chrono::DateTime<chrono::Utc>)>,
{
    let candidate_height = previous_block_height
        .next()
        .map_err(|_| ValidateContextError::NotReadyToBeCommitted)?;
    let relevant_headers = difficulty_context(network, candidate_height, relevant_headers);

    let difficulty_adjustment = AdjustedDifficulty::new_from_header_time(
        candidate_header.time,
        previous_block_height,
        network,
        relevant_headers,
    )
    .map_err(|_| ValidateContextError::NotReadyToBeCommitted)?;

    check::difficulty_threshold_and_time_are_valid(
        candidate_header.difficulty_threshold,
        difficulty_adjustment,
    )?;

    Ok(())
}

/// Check that `block` is contextually valid for `network`, using
/// the `history_tree` up to and including the previous block.
#[tracing::instrument(skip(block, history_tree))]
pub(crate) fn block_commitment_is_valid_for_chain_history(
    block: Arc<Block>,
    network: &Network,
    history_tree: &HistoryTree,
    precomputed_auth_data_root: Option<AuthDataRoot>,
) -> Result<(), ValidateContextError> {
    match block.commitment(network)? {
        block::Commitment::PreSaplingReserved(_)
        | block::Commitment::FinalSaplingRoot(_)
        | block::Commitment::ChainHistoryActivationReserved => {
            // # Consensus
            //
            // > [Sapling and Blossom only, pre-Heartwood] hashLightClientRoot MUST
            // > be LEBS2OSP_{256}(rt^{Sapling}) where rt^{Sapling} is the root of
            // > the Sapling note commitment tree for the final Sapling treestate of
            // > this block .
            //
            // https://zips.z.cash/protocol/protocol.pdf#blockheader
            //
            // We don't need to validate this rule since we checkpoint on Canopy.
            //
            // We also don't need to do anything in the other cases.
            Ok(())
        }
        block::Commitment::ChainHistoryRoot(actual_history_tree_root) => {
            // # Consensus
            //
            // > [Heartwood and Canopy only, pre-NU5] hashLightClientRoot MUST be set to the
            // > hashChainHistoryRoot for this block , as specified in [ZIP-221].
            //
            // https://zips.z.cash/protocol/protocol.pdf#blockheader
            //
            // The network is checked by [`Block::commitment`] above; it will only
            // return the chain history root if it's Heartwood or Canopy.
            let history_tree_root = history_tree
                .hash()
                .expect("the history tree of the previous block must exist since the current block has a ChainHistoryRoot");
            if actual_history_tree_root == history_tree_root {
                Ok(())
            } else {
                Err(ValidateContextError::InvalidBlockCommitment(
                    CommitmentError::InvalidChainHistoryRoot {
                        actual: actual_history_tree_root.into(),
                        expected: history_tree_root.into(),
                    },
                ))
            }
        }
        block::Commitment::ChainHistoryBlockTxAuthCommitment(actual_hash_block_commitments) => {
            // # Consensus
            //
            // > [NU5 onward] hashBlockCommitments MUST be set to the value of
            // > hashBlockCommitments for this block, as specified in [ZIP-244].
            //
            // The network is checked by [`Block::commitment`] above; it will only
            // return the block commitments if it's NU5 onward.
            let history_tree_root = history_tree
                .hash()
                .or_else(|| {
                    (NetworkUpgrade::Heartwood.activation_height(network)
                        == block.coinbase_height())
                    .then_some(block::CHAIN_HISTORY_ACTIVATION_RESERVED.into())
                })
                .expect(
                    "the history tree of the previous block must exist \
                 since the current block has a ChainHistoryBlockTxAuthCommitment",
                );
            let auth_data_root =
                precomputed_auth_data_root.unwrap_or_else(|| block.auth_data_root());
            let hash_block_commitments = ChainHistoryBlockTxAuthCommitmentHash::from_commitments(
                &history_tree_root,
                &auth_data_root,
            );

            if actual_hash_block_commitments == hash_block_commitments {
                Ok(())
            } else {
                Err(ValidateContextError::InvalidBlockCommitment(
                    CommitmentError::InvalidChainHistoryBlockTxAuthCommitment {
                        actual: actual_hash_block_commitments.into(),
                        expected: hash_block_commitments.into(),
                    },
                ))
            }
        }
    }
}

/// Returns `ValidateContextError::OrphanedBlock` if the height of the given
/// block is less than or equal to the finalized tip height.
fn block_is_not_orphaned(
    finalized_tip_height: block::Height,
    candidate_height: block::Height,
) -> Result<(), ValidateContextError> {
    if candidate_height <= finalized_tip_height {
        Err(ValidateContextError::OrphanedBlock {
            candidate_height,
            finalized_tip_height,
        })
    } else {
        Ok(())
    }
}

/// Returns `ValidateContextError::NonSequentialBlock` if the block height isn't
/// equal to the parent_height+1.
fn height_one_more_than_parent_height(
    parent_height: block::Height,
    candidate_height: block::Height,
) -> Result<(), ValidateContextError> {
    if parent_height + 1 != Some(candidate_height) {
        Err(ValidateContextError::NonSequentialBlock {
            candidate_height,
            parent_height,
        })
    } else {
        Ok(())
    }
}

/// Validate the time and `difficulty_threshold` from a candidate block's
/// header.
///
/// Uses the `difficulty_adjustment` context for the block to:
///   * check that the candidate block's time is within the valid range,
///     based on the network and  candidate height, and
///   * check that the expected difficulty is equal to the block's
///     `difficulty_threshold`.
///
/// These checks are performed together, because the time field is used to
/// calculate the expected difficulty adjustment.
pub(crate) fn difficulty_threshold_and_time_are_valid(
    difficulty_threshold: CompactDifficulty,
    difficulty_adjustment: AdjustedDifficulty,
) -> Result<(), ValidateContextError> {
    zakura_header_chain::validate_contextual_difficulty_and_time(
        difficulty_threshold,
        difficulty_adjustment,
    )
    .map_err(|error| match error {
        zakura_header_chain::ContextualValidationError::TimeTooEarly {
            candidate_time,
            median_time_past,
        } => ValidateContextError::TimeTooEarly {
            candidate_time,
            median_time_past,
        },
        zakura_header_chain::ContextualValidationError::TimeTooLate {
            candidate_time,
            block_time_max,
        } => ValidateContextError::TimeTooLate {
            candidate_time,
            block_time_max,
        },
        zakura_header_chain::ContextualValidationError::InvalidDifficultyThreshold {
            difficulty_threshold,
            expected_difficulty,
        } => ValidateContextError::InvalidDifficultyThreshold {
            difficulty_threshold,
            expected_difficulty,
        },
    })
}

/// Check if zebra is following a legacy chain and return an error if so.
///
/// `nu5_activation_height` should be `NetworkUpgrade::Nu5.activation_height(network)`, and
/// `max_legacy_chain_blocks` should be [`MAX_LEGACY_CHAIN_BLOCKS`](crate::constants::MAX_LEGACY_CHAIN_BLOCKS).
/// They are only changed from the defaults for testing.
pub(crate) fn legacy_chain<I>(
    nu5_activation_height: block::Height,
    ancestors: I,
    network: &Network,
    max_legacy_chain_blocks: usize,
) -> Result<(), BoxError>
where
    I: Iterator<Item = Arc<Block>>,
{
    let mut ancestors = ancestors.peekable();
    let tip_height = ancestors.peek().and_then(|block| block.coinbase_height());

    for (index, block) in ancestors.enumerate() {
        // Stop checking if the chain reaches Canopy. We won't find any more V5 transactions,
        // so the rest of our checks are useless.
        //
        // If the cached tip is close to NU5 activation, but there aren't any V5 transactions in the
        // chain yet, we could reach MAX_BLOCKS_TO_CHECK in Canopy, and incorrectly return an error.
        if block
            .coinbase_height()
            .expect("valid blocks have coinbase heights")
            < nu5_activation_height
        {
            return Ok(());
        }

        // If we are past our NU5 activation height, but there are no V5 transactions in recent blocks,
        // the last Zebra instance that updated this cached state had no NU5 activation height.
        if index >= max_legacy_chain_blocks {
            return Err(format!(
                "could not find any transactions in recent blocks: \
                 checked {index} blocks back from {:?}",
                tip_height.expect("database contains valid blocks"),
            )
            .into());
        }

        // If a transaction `network_upgrade` field is different from the network upgrade calculated
        // using our activation heights, the Zebra instance that verified those blocks had different
        // network upgrade heights.
        block
            .check_transaction_network_upgrade_consistency(network)
            .map_err(|error| {
                format!("inconsistent network upgrade found in transaction: {error:?}")
            })?;

        // If we find at least one transaction with a valid `network_upgrade` field, the Zebra instance that
        // verified those blocks used the same network upgrade heights. (Up to this point in the chain.)
        let has_network_upgrade = block
            .transactions
            .iter()
            .find_map(|trans| trans.network_upgrade())
            .is_some();
        if has_network_upgrade {
            return Ok(());
        }
    }

    Ok(())
}

/// Perform initial contextual validity checks for the configured network,
/// based on the committed finalized and non-finalized state.
///
/// Additional contextual validity checks are performed by the non-finalized [`Chain`].
pub(crate) fn initial_contextual_validity(
    finalized_state: &ZakuraDb,
    non_finalized_state: &NonFinalizedState,
    semantically_verified: &SemanticallyVerifiedBlock,
) -> Result<(), ValidateContextError> {
    let relevant_headers = any_chain_ancestor_iter::<block::Header>(
        non_finalized_state,
        finalized_state,
        semantically_verified.block.header.previous_block_hash,
    );
    let parent_height = relevant_headers.height;

    // Security: check proof of work before any other checks
    check::block_is_valid_for_recent_chain(
        semantically_verified,
        &non_finalized_state.network,
        finalized_state.finalized_tip_height(),
        parent_height,
        relevant_headers,
    )?;

    check::nullifier::no_duplicates_in_finalized_chain(semantically_verified, finalized_state)?;

    Ok(())
}

#[cfg(test)]
mod nsm_value_balance_boundary_tests {
    use super::*;
    use zakura_chain::{
        amount::{Amount, MAX_MONEY},
        parameters::testnet::{ConfiguredActivationHeights, RegtestParameters},
    };

    #[test]
    fn rejection_matrix_covers_activation_sign_and_arithmetic_limits() {
        let network = Network::new_regtest(RegtestParameters {
            activation_heights: ConfiguredActivationHeights {
                nu7: Some(2),
                ..Default::default()
            },
            test_nsm_reissuance_height: Some(block::Height(3)),
            ..Default::default()
        });
        for height in [1, 2, 3, 4] {
            for before in [-MAX_MONEY, -1, 0, 1, MAX_MONEY] {
                for delta in [-MAX_MONEY, -1, 0, 1, MAX_MONEY] {
                    let mut pools = ValueBalance::<NonNegative>::zero();
                    pools.set_nsm_value_balance_amount(Amount::try_from(before).unwrap());
                    let mut change = ValueBalance::<NegativeAllowed>::zero();
                    change.set_nsm_value_balance_amount(Amount::try_from(delta).unwrap());
                    let result = nsm_value_balance_is_non_negative(
                        &network,
                        block::Height(height),
                        &pools,
                        &change,
                    );
                    let sum = i128::from(before) + i128::from(delta);
                    // Rejection starts at NU7, before the reissuance height.
                    let reject = height >= 2 && !(0..=i128::from(MAX_MONEY)).contains(&sum);
                    assert_eq!(
                        result.is_err(),
                        reject,
                        "height {height}, before {before}, delta {delta}"
                    );
                    assert_eq!(i64::from(pools.nsm_value_balance_amount()), before);
                    assert_eq!(i64::from(change.nsm_value_balance_amount()), delta);
                }
            }
        }
    }
}