vm-ledger/crates/ledger-core/src/proof.rs

use serde::{Deserialize, Serialize};

use crate::entry::EntryHash;
use crate::merkle::{
    MerklePathItem, MerkleRoot, MerkleSide, leaf_hash, merkle_inclusion_path, node_hash,
};
use crate::storage::LedgerError;

pub const READ_PROOF_V0_FORMAT: &str = "civ-ledger-readproof-v0";

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ReadProofV0 {
    pub format: String,
    pub entry_hash_hex: String,
    pub entry_index: u64,
    pub entry_count: u64,
    pub checkpoint_merkle_root_hex: String,
    pub path: Vec<PathStepV0>,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PathStepV0 {
    pub sibling_side: SideV0,
    pub sibling_hash_hex: String,
}

#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum SideV0 {
    Left,
    Right,
}

impl ReadProofV0 {
    pub fn from_tree(leaves: &[EntryHash], index: usize) -> Result<Self, LedgerError> {
        let (root, path) = merkle_inclusion_path(leaves, index)
            .map_err(|e| LedgerError::InvalidLedger(format!("cannot build merkle proof: {}", e)))?;
        Ok(Self::new(leaves, index, root, path))
    }

    fn new(
        leaves: &[EntryHash],
        index: usize,
        root: MerkleRoot,
        path: Vec<MerklePathItem>,
    ) -> Self {
        Self {
            format: READ_PROOF_V0_FORMAT.to_string(),
            entry_hash_hex: hex_encode(&leaves[index]),
            entry_index: index as u64,
            entry_count: leaves.len() as u64,
            checkpoint_merkle_root_hex: hex_encode(&root),
            path: path.into_iter().map(step_from_merkle).collect(),
        }
    }
}

pub fn verify_read_proof_v0(proof: &ReadProofV0) -> Result<(), LedgerError> {
    if proof.format != READ_PROOF_V0_FORMAT {
        return Err(LedgerError::InvalidLedger(format!(
            "unsupported proof format: {}",
            proof.format
        )));
    }

    if proof.entry_count == 0 {
        return Err(LedgerError::InvalidLedger("entry_count must be > 0".into()));
    }

    if proof.entry_index >= proof.entry_count {
        return Err(LedgerError::InvalidLedger(
            "entry_index out of range".into(),
        ));
    }

    let expected_path_len = expected_merkle_path_len(proof.entry_count);
    if proof.path.len() != expected_path_len {
        return Err(LedgerError::InvalidLedger(format!(
            "unexpected merkle path length: expected {}, got {}",
            expected_path_len,
            proof.path.len()
        )));
    }

    let entry_hash: [u8; 32] = hex_decode_fixed(&proof.entry_hash_hex)?;
    let want_root: [u8; 32] = hex_decode_fixed(&proof.checkpoint_merkle_root_hex)?;

    let mut current = leaf_hash(&entry_hash);
    for step in &proof.path {
        let sibling: [u8; 32] = hex_decode_fixed(&step.sibling_hash_hex)?;
        current = match step.sibling_side {
            SideV0::Left => node_hash(&sibling, &current),
            SideV0::Right => node_hash(&current, &sibling),
        };
    }

    if current != want_root {
        return Err(LedgerError::InvalidLedger(
            "merkle proof does not match checkpoint root".into(),
        ));
    }
    Ok(())
}

fn step_from_merkle(item: MerklePathItem) -> PathStepV0 {
    let sibling_side = match item.sibling_side {
        MerkleSide::Left => SideV0::Left,
        MerkleSide::Right => SideV0::Right,
    };
    PathStepV0 {
        sibling_side,
        sibling_hash_hex: hex_encode(&item.sibling),
    }
}

fn expected_merkle_path_len(mut leaf_count: u64) -> usize {
    let mut depth = 0usize;
    while leaf_count > 1 {
        depth += 1;
        leaf_count = (leaf_count + 1) / 2;
    }
    depth
}

fn hex_encode(bytes: &[u8]) -> String {
    bytes.iter().map(|b| format!("{:02x}", b)).collect()
}

fn hex_decode_fixed<const N: usize>(s: &str) -> Result<[u8; N], LedgerError> {
    let s = s.trim();
    if s.len() != N * 2 {
        return Err(LedgerError::InvalidLedger(format!(
            "hex value must be {} bytes ({} hex chars), got {} chars",
            N,
            N * 2,
            s.len()
        )));
    }
    let mut out = [0u8; N];
    for i in 0..N {
        let idx = i * 2;
        out[i] = u8::from_str_radix(&s[idx..idx + 2], 16)
            .map_err(|_| LedgerError::InvalidLedger("invalid hex".into()))?;
    }
    Ok(out)
}