clm-kernel 0.0.13

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Layer 2: Merkle Tree, Membership Proofs, and Directory Ingestion.
//! Canonical Path: kernel/clm_rust_core/src/layer2/merkle.rs
//! Parity: TypeScript `src/layer2/merkleTree.ts`, Python `clm/layer2/merkle.py`

use std::collections::BTreeMap;
use serde::{Deserialize, Serialize};

#[cfg(any(feature = "native", feature = "db"))]
pub use crate::directory_ingest::{directory_fs_scan, directory_to_db};

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct TreeFileEntry {
    pub path: String,
    pub data: Vec<u8>,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct MerkleNode {
    pub name: String,
    pub path: String,
    pub hash: String,
    pub is_directory: bool,
    pub size_bytes: usize,
    pub children: Option<Vec<MerkleNode>>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub content_bytes: Option<Vec<u8>>,
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ManifestEntryDescriptor {
    pub name: String,
    pub hash: String,
    #[serde(rename = "isDirectory")]
    pub is_directory: bool,
    #[serde(rename = "sizeBytes")]
    pub size_bytes: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ManifestProofStep {
    pub name: String,
    pub path: String,
    #[serde(rename = "manifestHash")]
    pub manifest_hash: String,
    pub entries: Vec<ManifestEntryDescriptor>,
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MembershipProof {
    #[serde(rename = "rootHash")]
    pub root_hash: String,
    pub path: String,
    #[serde(rename = "targetHash")]
    pub target_hash: String,
    pub chain: Vec<ManifestProofStep>,
}

fn compute_hash_prefixed(data: &[u8], algorithm: &str) -> String {
    let algo = algorithm.trim().to_lowercase().replace("-", "");
    if algo == "blake3" {
        format!("blake3:{}", blake3::hash(data).to_hex())
    } else if algo == "sha256" {
        use sha2::{Digest, Sha256};
        let mut hasher = Sha256::new();
        hasher.update(data);
        format!("sha256:{}", hex::encode(hasher.finalize()))
    } else {
        format!("{}:{}", algo, blake3::hash(data).to_hex())
    }
}

struct InternalNode {
    name: String,
    path: String,
    is_directory: bool,
    data: Option<Vec<u8>>,
    children: BTreeMap<String, InternalNode>,
}

pub fn build_merkle_tree_from_entries(
    entries: &[TreeFileEntry],
    algorithm: Option<&str>,
) -> MerkleNode {
    let algo = algorithm.unwrap_or("blake3");
    let mut root = InternalNode {
        name: String::new(),
        path: String::new(),
        is_directory: true,
        data: None,
        children: BTreeMap::new(),
    };

    for entry in entries {
        let clean = entry.path.trim_start_matches('/');
        let segments: Vec<&str> = clean.split('/').filter(|s| !s.is_empty()).collect();
        let mut curr = &mut root;
        for (i, seg) in segments.iter().enumerate() {
            let is_leaf = i == segments.len() - 1;
            let sub_path = segments[..=i].join("/");
            curr = curr.children.entry(seg.to_string()).or_insert_with(|| InternalNode {
                name: seg.to_string(),
                path: sub_path,
                is_directory: !is_leaf,
                data: if is_leaf { Some(entry.data.clone()) } else { None },
                children: BTreeMap::new(),
            });
        }
    }

    fn finalize(node: InternalNode, algo: &str) -> MerkleNode {
        if !node.is_directory && node.data.is_some() {
            let data = node.data.unwrap();
            let hash = compute_hash_prefixed(&data, algo);
            return MerkleNode {
                name: node.name,
                path: node.path,
                hash,
                is_directory: false,
                size_bytes: data.len(),
                children: None,
                content_bytes: Some(data),
            };
        }

        let mut child_keys: Vec<String> = node.children.keys().cloned().collect();
        child_keys.sort_by(|a, b| {
            a.to_lowercase().cmp(&b.to_lowercase()).then_with(|| a.cmp(b))
        });

        let mut finalized_children = Vec::new();
        let mut total_size = 0;
        let mut mut_children = node.children;

        for k in child_keys {
            if let Some(child_node) = mut_children.remove(&k) {
                let finalized = finalize(child_node, algo);
                total_size += finalized.size_bytes;
                finalized_children.push(finalized);
            }
        }

        let mut manifest_lines = Vec::new();
        for c in &finalized_children {
            manifest_lines.push(format!(
                "{}:{}:{}:{}",
                c.name,
                c.hash,
                if c.is_directory { "dir" } else { "file" },
                c.size_bytes
            ));
        }
        let mut manifest_str = manifest_lines.join("\n");
        if !manifest_lines.is_empty() {
            manifest_str.push('\n');
        }
        let dir_hash = compute_hash_prefixed(manifest_str.as_bytes(), algo);

        MerkleNode {
            name: if node.name.is_empty() { "root".to_string() } else { node.name },
            path: node.path,
            hash: dir_hash,
            is_directory: true,
            size_bytes: total_size,
            children: Some(finalized_children),
            content_bytes: None,
        }
    }

    finalize(root, algo)
}

pub fn verify_merkle_integrity(node: &MerkleNode) -> bool {
    let algo = node.hash.split(':').next().unwrap_or("blake3");
    if !node.is_directory {
        let Some(ref content) = node.content_bytes else {
            return false;
        };
        return compute_hash_prefixed(content, algo) == node.hash;
    }

    let Some(ref children) = node.children else {
        return false;
    };

    for child in children {
        if !child.hash.contains(':') {
            return false;
        }
        if !verify_merkle_integrity(child) {
            return false;
        }
    }

    let mut manifest_lines = Vec::new();
    for c in children {
        manifest_lines.push(format!(
            "{}:{}:{}:{}",
            c.name,
            c.hash,
            if c.is_directory { "dir" } else { "file" },
            c.size_bytes
        ));
    }
    let mut manifest_str = manifest_lines.join("\n");
    if !manifest_lines.is_empty() {
        manifest_str.push('\n');
    }
    compute_hash_prefixed(manifest_str.as_bytes(), algo) == node.hash
}

pub fn prove_membership(root: &MerkleNode, target_path: &str) -> Option<MembershipProof> {
    let clean = target_path.trim_start_matches('/').trim_end_matches('/');
    let segments: Vec<&str> = clean.split('/').filter(|s| !s.is_empty()).collect();
    if segments.is_empty() {
        return None;
    }

    let mut chain = Vec::new();
    let mut curr = root;

    for (i, seg) in segments.iter().enumerate() {
        let is_leaf = i == segments.len() - 1;
        let children = curr.children.as_ref()?;

        let entries: Vec<ManifestEntryDescriptor> = children
            .iter()
            .map(|c| ManifestEntryDescriptor {
                name: c.name.clone(),
                hash: c.hash.clone(),
                is_directory: c.is_directory,
                size_bytes: c.size_bytes,
            })
            .collect();

        chain.push(ManifestProofStep {
            name: if curr.name.is_empty() { "root".to_string() } else { curr.name.clone() },
            path: curr.path.clone(),
            manifest_hash: curr.hash.clone(),
            entries,
        });

        let child = children.iter().find(|c| c.name == *seg)?;
        if is_leaf {
            return Some(MembershipProof {
                root_hash: root.hash.clone(),
                path: clean.to_string(),
                target_hash: child.hash.clone(),
                chain,
            });
        }

        if !child.is_directory {
            return None;
        }
        curr = child;
    }

    None
}

pub fn verify_membership(proof: &MembershipProof) -> bool {
    if proof.chain.is_empty() {
        return false;
    }

    if proof.chain[0].manifest_hash != proof.root_hash {
        return false;
    }

    for (i, step) in proof.chain.iter().enumerate() {
        let mut sorted_entries = step.entries.clone();
        sorted_entries.sort_by(|a, b| {
            a.name.to_lowercase().cmp(&b.name.to_lowercase()).then_with(|| a.name.cmp(&b.name))
        });

        let mut lines = Vec::new();
        for e in &sorted_entries {
            lines.push(format!(
                "{}:{}:{}:{}",
                e.name,
                e.hash,
                if e.is_directory { "dir" } else { "file" },
                e.size_bytes
            ));
        }
        let mut data = lines.join("\n");
        if !lines.is_empty() {
            data.push('\n');
        }

        let algo = step.manifest_hash.split(':').next().unwrap_or("blake3");
        let computed = compute_hash_prefixed(data.as_bytes(), algo);
        if computed != step.manifest_hash {
            return false;
        }

        if i < proof.chain.len() - 1 {
            let next_step = &proof.chain[i + 1];
            let entry = step.entries.iter().find(|e| e.name == next_step.name);
            match entry {
                Some(e) if e.is_directory && e.hash == next_step.manifest_hash => {}
                _ => return false,
            }
        } else {
            let leaf_name = proof.path.split('/').next_back().unwrap_or("");
            let entry = step.entries.iter().find(|e| e.name == leaf_name);
            match entry {
                Some(e) if e.hash == proof.target_hash => {}
                _ => return false,
            }
        }
    }

    true
}