csv-adapter-core 0.1.1

//! Commitment Chain Verification
//!
//! Walks a chain of commitments from present back to genesis,
//! verifying that each commitment's `previous_commitment` field
//! matches the hash of the prior commitment.
//!
//! ## Overview
//!
//! Each commitment in a contract's history references the previous
//! commitment via its `previous_commitment` field. This forms a
//! hash chain:
//!
//! ```text
//! Genesis Commitment (previous_commitment = 0)
//!   ↓ hash
//! Commitment 1 (previous_commitment = hash(genesis))
//!   ↓ hash
//! Commitment 2 (previous_commitment = hash(commitment_1))
//!   ↓ hash
//! Latest Commitment
//! ```
//!
//! The commitment chain walker verifies:
//! 1. Each commitment's `previous_commitment` matches the hash of the prior commitment
//! 2. The chain traces back to a genesis commitment (previous_commitment = zero hash)
//! 3. No commitments are missing in the sequence
//! 4. All commitments belong to the same contract (contract_id consistency)

use alloc::vec::Vec;

use crate::commitment::Commitment;
use crate::hash::Hash;

/// Result of commitment chain verification.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ChainVerificationResult {
    /// The ordered chain of commitments (genesis → latest)
    pub chain: Vec<Commitment>,
    /// The genesis commitment (first in the chain)
    pub genesis: Commitment,
    /// The latest commitment (last in the chain)
    pub latest: Commitment,
    /// Total number of commitments in the chain
    pub length: usize,
    /// The contract ID that all commitments belong to
    pub contract_id: Hash,
}

/// Errors that can occur during commitment chain verification.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[allow(missing_docs)]
pub enum ChainError {
    #[error("Empty commitment chain")]
    EmptyChain,
    #[error("Chain does not start at genesis (first commitment has non-zero previous_commitment)")]
    NotGenesis,
    #[error(
        "Commitment chain broken at index {index}: expected previous {expected}, got {actual}"
    )]
    BrokenChain {
        index: usize,
        expected: Hash,
        actual: Hash,
    },
    #[error("Commitment at index {index} has inconsistent contract_id: expected {expected}, got {actual}")]
    ContractIdMismatch {
        index: usize,
        expected: Hash,
        actual: Hash,
    },
    #[error("Duplicate commitment found at index {index}")]
    DuplicateCommitment { index: usize },
    #[error("Cycle detected in commitment chain at index {index}")]
    CycleDetected { index: usize },
}

/// Verifies a commitment chain from a collection of commitments.
///
/// This function takes a set of commitments and attempts to reconstruct
/// and verify the commitment chain by following the `previous_commitment`
/// references.
///
/// # Arguments
/// * `commitments` - A collection of commitments to verify
/// * `latest_commitment_hash` - The hash of the latest commitment (starting point)
///
/// # Returns
/// A `ChainVerificationResult` if the chain is valid, or a `ChainError` if invalid.
pub fn verify_commitment_chain(
    commitments: &[Commitment],
    latest_commitment_hash: Hash,
) -> Result<ChainVerificationResult, ChainError> {
    if commitments.is_empty() {
        return Err(ChainError::EmptyChain);
    }

    // Build a map from commitment hash to commitment
    let mut commitment_map: alloc::collections::BTreeMap<Hash, &Commitment> =
        alloc::collections::BTreeMap::new();

    for commitment in commitments {
        let hash = commitment.hash();
        commitment_map.insert(hash, commitment);
    }

    // Start from the latest commitment and walk backwards
    let mut chain: Vec<Commitment> = Vec::new();
    let mut seen: alloc::collections::BTreeSet<Hash> = alloc::collections::BTreeSet::new();
    let mut current_hash = latest_commitment_hash;

    loop {
        // Check for cycles
        if seen.contains(&current_hash) {
            return Err(ChainError::CycleDetected { index: chain.len() });
        }
        seen.insert(current_hash);

        // Find the commitment with this hash
        let commitment =
            commitment_map
                .get(&current_hash)
                .ok_or_else(|| ChainError::BrokenChain {
                    index: chain.len(),
                    expected: current_hash,
                    actual: Hash::new([0u8; 32]),
                })?;

        // Check for duplicates
        if chain.iter().any(|c: &Commitment| c.hash() == current_hash) {
            return Err(ChainError::DuplicateCommitment { index: chain.len() });
        }

        chain.push((**commitment).clone());

        // Check if this is the genesis commitment
        let previous = commitment.previous_commitment;
        if previous == Hash::new([0u8; 32]) {
            // This is genesis - we've completed the chain
            break;
        }

        // Move to the previous commitment
        current_hash = previous;
    }

    // Verify the first commitment is actually genesis
    let genesis = chain.last().ok_or(ChainError::EmptyChain)?;

    if genesis.previous_commitment != Hash::new([0u8; 32]) {
        return Err(ChainError::NotGenesis);
    }

    // Verify all commitments have the same contract_id
    let contract_id = genesis.contract_id;
    for (i, commitment) in chain.iter().enumerate() {
        if commitment.contract_id != contract_id {
            return Err(ChainError::ContractIdMismatch {
                index: i,
                expected: contract_id,
                actual: commitment.contract_id,
            });
        }
    }

    // Reverse the chain so it's in chronological order (genesis → latest)
    chain.reverse();

    let genesis_commitment = chain.first().unwrap().clone();
    let latest_commitment = chain.last().unwrap().clone();
    let chain_length = chain.len();

    Ok(ChainVerificationResult {
        chain,
        genesis: genesis_commitment,
        latest: latest_commitment,
        length: chain_length,
        contract_id,
    })
}

/// Verifies a pre-ordered commitment chain.
///
/// This is a simpler version that assumes the commitments are already
/// in chronological order (genesis first, latest last).
///
/// # Arguments
/// * `ordered_commitments` - Commitments in chronological order
///
/// # Returns
/// A `ChainVerificationResult` if valid, or a `ChainError` if invalid.
pub fn verify_ordered_commitment_chain(
    ordered_commitments: &[Commitment],
) -> Result<ChainVerificationResult, ChainError> {
    if ordered_commitments.is_empty() {
        return Err(ChainError::EmptyChain);
    }

    // Verify the chain links
    for i in 1..ordered_commitments.len() {
        let current = &ordered_commitments[i];
        let previous = &ordered_commitments[i - 1];

        // Current's previous_commitment should match previous's hash
        let expected_previous = previous.hash();
        if current.previous_commitment != expected_previous {
            return Err(ChainError::BrokenChain {
                index: i,
                expected: expected_previous,
                actual: current.previous_commitment,
            });
        }

        // Verify contract_id consistency
        if current.contract_id != previous.contract_id {
            return Err(ChainError::ContractIdMismatch {
                index: i,
                expected: previous.contract_id,
                actual: current.contract_id,
            });
        }
    }

    // Verify first is genesis
    if ordered_commitments.first().unwrap().previous_commitment != Hash::new([0u8; 32]) {
        return Err(ChainError::NotGenesis);
    }

    // Check for duplicates
    let mut seen = alloc::collections::BTreeSet::new();
    for (i, commitment) in ordered_commitments.iter().enumerate() {
        let hash = commitment.hash();
        if !seen.insert(hash) {
            return Err(ChainError::DuplicateCommitment { index: i });
        }
    }

    let genesis = ordered_commitments.first().unwrap().clone();
    let latest = ordered_commitments.last().unwrap().clone();
    let contract_id = genesis.contract_id;

    Ok(ChainVerificationResult {
        chain: ordered_commitments.to_vec(),
        genesis,
        latest,
        length: ordered_commitments.len(),
        contract_id,
    })
}

/// Computes the expected hash of the previous commitment given a commitment.
///
/// This is a helper to verify that a commitment correctly references
/// its predecessor.
pub fn verify_commitment_link(
    previous_commitment: &Commitment,
    current_commitment: &Commitment,
) -> Result<(), ChainError> {
    let expected = previous_commitment.hash();
    let actual = current_commitment.previous_commitment;

    if expected != actual {
        return Err(ChainError::BrokenChain {
            index: 0,
            expected,
            actual,
        });
    }

    // Verify contract_id consistency
    if previous_commitment.contract_id != current_commitment.contract_id {
        return Err(ChainError::ContractIdMismatch {
            index: 0,
            expected: previous_commitment.contract_id,
            actual: current_commitment.contract_id,
        });
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::commitment::Commitment;
    use crate::seal::SealRef;

    fn make_genesis_commitment(contract_id: Hash) -> Commitment {
        let domain = [0u8; 32];
        let seal = SealRef::new(vec![0x01], None).unwrap();
        Commitment::simple(
            contract_id,
            Hash::new([0u8; 32]), // Genesis has zero previous_commitment
            Hash::new([0u8; 32]),
            &seal,
            domain,
        )
    }

    fn make_commitment(contract_id: Hash, previous_commitment: Hash, seal_id: u8) -> Commitment {
        let domain = [0u8; 32];
        let seal = SealRef::new(vec![seal_id], None).unwrap();
        Commitment::simple(
            contract_id,
            previous_commitment,
            Hash::new([0u8; 32]),
            &seal,
            domain,
        )
    }

    #[test]
    fn test_verify_ordered_chain_valid() {
        let contract_id = Hash::new([0xAB; 32]);
        let genesis = make_genesis_commitment(contract_id);
        let c1 = make_commitment(contract_id, genesis.hash(), 0x02);
        let c2 = make_commitment(contract_id, c1.hash(), 0x03);

        let result = verify_ordered_commitment_chain(&[genesis.clone(), c1.clone(), c2.clone()]);
        assert!(result.is_ok());

        let result = result.unwrap();
        assert_eq!(result.length, 3);
        assert_eq!(result.genesis.hash(), genesis.hash());
        assert_eq!(result.latest.hash(), c2.hash());
        assert_eq!(result.contract_id, contract_id);
    }

    #[test]
    fn test_verify_ordered_chain_broken_link() {
        let contract_id = Hash::new([0xAB; 32]);
        let genesis = make_genesis_commitment(contract_id);
        let c1 = make_commitment(contract_id, genesis.hash(), 0x02);
        // c2 references a wrong previous commitment
        let c2 = make_commitment(contract_id, Hash::new([0xFF; 32]), 0x03);

        let result = verify_ordered_commitment_chain(&[genesis, c1, c2]);
        assert!(result.is_err());
        assert!(matches!(
            result.unwrap_err(),
            ChainError::BrokenChain { .. }
        ));
    }

    #[test]
    fn test_verify_ordered_chain_not_genesis() {
        let contract_id = Hash::new([0xAB; 32]);
        // First commitment is not genesis (has non-zero previous)
        let c1 = make_commitment(contract_id, Hash::new([0x01; 32]), 0x01);
        let c2 = make_commitment(contract_id, c1.hash(), 0x02);

        let result = verify_ordered_commitment_chain(&[c1, c2]);
        assert!(result.is_err());
        assert!(matches!(result.unwrap_err(), ChainError::NotGenesis));
    }

    #[test]
    fn test_verify_ordered_chain_contract_id_mismatch() {
        let contract_id_1 = Hash::new([0xAB; 32]);
        let contract_id_2 = Hash::new([0xCD; 32]);

        let genesis = make_genesis_commitment(contract_id_1);
        // c1 has different contract_id
        let c1 = make_commitment(contract_id_2, genesis.hash(), 0x02);

        let result = verify_ordered_commitment_chain(&[genesis, c1]);
        assert!(result.is_err());
        assert!(matches!(
            result.unwrap_err(),
            ChainError::ContractIdMismatch { .. }
        ));
    }

    #[test]
    fn test_verify_ordered_chain_empty() {
        let result = verify_ordered_commitment_chain(&[]);
        assert!(result.is_err());
        assert!(matches!(result.unwrap_err(), ChainError::EmptyChain));
    }

    #[test]
    fn test_verify_ordered_chain_single_genesis() {
        let contract_id = Hash::new([0xAB; 32]);
        let genesis = make_genesis_commitment(contract_id);

        let result = verify_ordered_commitment_chain(&[genesis.clone()]);
        assert!(result.is_ok());

        let result = result.unwrap();
        assert_eq!(result.length, 1);
        assert_eq!(result.genesis.hash(), genesis.hash());
        assert_eq!(result.latest.hash(), genesis.hash());
    }

    #[test]
    fn test_verify_ordered_chain_duplicates() {
        let contract_id = Hash::new([0xAB; 32]);
        let genesis = make_genesis_commitment(contract_id);
        let c1 = make_commitment(contract_id, genesis.hash(), 0x02);

        // Duplicate c1 in the chain
        let result = verify_ordered_commitment_chain(&[genesis.clone(), c1.clone(), c1.clone()]);
        // The chain will fail at index 2 because c1's hash doesn't match c1's previous_commitment
        // Actually c1.clone() twice means the third element has c1's previous_commitment pointing to genesis
        // but the second element IS c1, so this creates a broken chain, not a duplicate
        // To properly test duplicates, we need a valid chain with the same commitment appearing twice
        assert!(result.is_err()); // Should fail for either BrokenChain or DuplicateCommitment
    }

    #[test]
    fn test_verify_commitment_link_valid() {
        let contract_id = Hash::new([0xAB; 32]);
        let genesis = make_genesis_commitment(contract_id);
        let c1 = make_commitment(contract_id, genesis.hash(), 0x02);

        assert!(verify_commitment_link(&genesis, &c1).is_ok());
    }

    #[test]
    fn test_verify_commitment_link_broken() {
        let contract_id = Hash::new([0xAB; 32]);
        let genesis = make_genesis_commitment(contract_id);
        let c1 = make_commitment(contract_id, Hash::new([0xFF; 32]), 0x02);

        assert!(verify_commitment_link(&genesis, &c1).is_err());
    }

    #[test]
    fn test_long_chain_verification() {
        let contract_id = Hash::new([0xAB; 32]);
        let mut commitments = Vec::new();

        // Create a chain of 50 commitments
        let genesis = make_genesis_commitment(contract_id);
        commitments.push(genesis.clone());

        let mut previous = genesis;
        for i in 1..50 {
            let c = make_commitment(contract_id, previous.hash(), (i + 1) as u8);
            commitments.push(c.clone());
            previous = c;
        }

        let result = verify_ordered_commitment_chain(&commitments);
        assert!(result.is_ok());
        assert_eq!(result.unwrap().length, 50);
    }
}