Skip to main content

clm_rust_core/layer2/
merkle.rs

1//! Layer 2: Merkle Tree, Membership Proofs, and Directory Ingestion.
2//! Canonical Path: kernel/clm_rust_core/src/layer2/merkle.rs
3//! Parity: TypeScript `src/layer2/merkleTree.ts`, Python `clm/layer2/merkle.py`
4
5use std::collections::BTreeMap;
6use serde::{Deserialize, Serialize};
7
8#[cfg(any(feature = "native", feature = "db"))]
9pub use crate::directory_ingest::{directory_fs_scan, directory_to_db};
10
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub struct TreeFileEntry {
13    pub path: String,
14    pub data: Vec<u8>,
15}
16
17#[derive(Debug, Clone, Serialize, Deserialize)]
18pub struct MerkleNode {
19    pub name: String,
20    pub path: String,
21    pub hash: String,
22    pub is_directory: bool,
23    pub size_bytes: usize,
24    pub children: Option<Vec<MerkleNode>>,
25    #[serde(skip_serializing_if = "Option::is_none")]
26    pub content_bytes: Option<Vec<u8>>,
27}
28
29#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
30pub struct ManifestEntryDescriptor {
31    pub name: String,
32    pub hash: String,
33    #[serde(rename = "isDirectory")]
34    pub is_directory: bool,
35    #[serde(rename = "sizeBytes")]
36    pub size_bytes: usize,
37}
38
39#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
40pub struct ManifestProofStep {
41    pub name: String,
42    pub path: String,
43    #[serde(rename = "manifestHash")]
44    pub manifest_hash: String,
45    pub entries: Vec<ManifestEntryDescriptor>,
46}
47
48#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
49pub struct MembershipProof {
50    #[serde(rename = "rootHash")]
51    pub root_hash: String,
52    pub path: String,
53    #[serde(rename = "targetHash")]
54    pub target_hash: String,
55    pub chain: Vec<ManifestProofStep>,
56}
57
58fn compute_hash_prefixed(data: &[u8], algorithm: &str) -> String {
59    let algo = algorithm.trim().to_lowercase().replace("-", "");
60    if algo == "blake3" {
61        format!("blake3:{}", blake3::hash(data).to_hex())
62    } else if algo == "sha256" {
63        use sha2::{Digest, Sha256};
64        let mut hasher = Sha256::new();
65        hasher.update(data);
66        format!("sha256:{}", hex::encode(hasher.finalize()))
67    } else {
68        format!("{}:{}", algo, blake3::hash(data).to_hex())
69    }
70}
71
72struct InternalNode {
73    name: String,
74    path: String,
75    is_directory: bool,
76    data: Option<Vec<u8>>,
77    children: BTreeMap<String, InternalNode>,
78}
79
80pub fn build_merkle_tree_from_entries(
81    entries: &[TreeFileEntry],
82    algorithm: Option<&str>,
83) -> MerkleNode {
84    let algo = algorithm.unwrap_or("blake3");
85    let mut root = InternalNode {
86        name: String::new(),
87        path: String::new(),
88        is_directory: true,
89        data: None,
90        children: BTreeMap::new(),
91    };
92
93    for entry in entries {
94        let clean = entry.path.trim_start_matches('/');
95        let segments: Vec<&str> = clean.split('/').filter(|s| !s.is_empty()).collect();
96        let mut curr = &mut root;
97        for (i, seg) in segments.iter().enumerate() {
98            let is_leaf = i == segments.len() - 1;
99            let sub_path = segments[..=i].join("/");
100            curr = curr.children.entry(seg.to_string()).or_insert_with(|| InternalNode {
101                name: seg.to_string(),
102                path: sub_path,
103                is_directory: !is_leaf,
104                data: if is_leaf { Some(entry.data.clone()) } else { None },
105                children: BTreeMap::new(),
106            });
107        }
108    }
109
110    fn finalize(node: InternalNode, algo: &str) -> MerkleNode {
111        if !node.is_directory && node.data.is_some() {
112            let data = node.data.unwrap();
113            let hash = compute_hash_prefixed(&data, algo);
114            return MerkleNode {
115                name: node.name,
116                path: node.path,
117                hash,
118                is_directory: false,
119                size_bytes: data.len(),
120                children: None,
121                content_bytes: Some(data),
122            };
123        }
124
125        let mut child_keys: Vec<String> = node.children.keys().cloned().collect();
126        child_keys.sort_by(|a, b| {
127            a.to_lowercase().cmp(&b.to_lowercase()).then_with(|| a.cmp(b))
128        });
129
130        let mut finalized_children = Vec::new();
131        let mut total_size = 0;
132        let mut mut_children = node.children;
133
134        for k in child_keys {
135            if let Some(child_node) = mut_children.remove(&k) {
136                let finalized = finalize(child_node, algo);
137                total_size += finalized.size_bytes;
138                finalized_children.push(finalized);
139            }
140        }
141
142        let mut manifest_lines = Vec::new();
143        for c in &finalized_children {
144            manifest_lines.push(format!(
145                "{}:{}:{}:{}",
146                c.name,
147                c.hash,
148                if c.is_directory { "dir" } else { "file" },
149                c.size_bytes
150            ));
151        }
152        let mut manifest_str = manifest_lines.join("\n");
153        if !manifest_lines.is_empty() {
154            manifest_str.push('\n');
155        }
156        let dir_hash = compute_hash_prefixed(manifest_str.as_bytes(), algo);
157
158        MerkleNode {
159            name: if node.name.is_empty() { "root".to_string() } else { node.name },
160            path: node.path,
161            hash: dir_hash,
162            is_directory: true,
163            size_bytes: total_size,
164            children: Some(finalized_children),
165            content_bytes: None,
166        }
167    }
168
169    finalize(root, algo)
170}
171
172pub fn verify_merkle_integrity(node: &MerkleNode) -> bool {
173    let algo = node.hash.split(':').next().unwrap_or("blake3");
174    if !node.is_directory {
175        let Some(ref content) = node.content_bytes else {
176            return false;
177        };
178        return compute_hash_prefixed(content, algo) == node.hash;
179    }
180
181    let Some(ref children) = node.children else {
182        return false;
183    };
184
185    for child in children {
186        if !child.hash.contains(':') {
187            return false;
188        }
189        if !verify_merkle_integrity(child) {
190            return false;
191        }
192    }
193
194    let mut manifest_lines = Vec::new();
195    for c in children {
196        manifest_lines.push(format!(
197            "{}:{}:{}:{}",
198            c.name,
199            c.hash,
200            if c.is_directory { "dir" } else { "file" },
201            c.size_bytes
202        ));
203    }
204    let mut manifest_str = manifest_lines.join("\n");
205    if !manifest_lines.is_empty() {
206        manifest_str.push('\n');
207    }
208    compute_hash_prefixed(manifest_str.as_bytes(), algo) == node.hash
209}
210
211pub fn prove_membership(root: &MerkleNode, target_path: &str) -> Option<MembershipProof> {
212    let clean = target_path.trim_start_matches('/').trim_end_matches('/');
213    let segments: Vec<&str> = clean.split('/').filter(|s| !s.is_empty()).collect();
214    if segments.is_empty() {
215        return None;
216    }
217
218    let mut chain = Vec::new();
219    let mut curr = root;
220
221    for (i, seg) in segments.iter().enumerate() {
222        let is_leaf = i == segments.len() - 1;
223        let children = curr.children.as_ref()?;
224
225        let entries: Vec<ManifestEntryDescriptor> = children
226            .iter()
227            .map(|c| ManifestEntryDescriptor {
228                name: c.name.clone(),
229                hash: c.hash.clone(),
230                is_directory: c.is_directory,
231                size_bytes: c.size_bytes,
232            })
233            .collect();
234
235        chain.push(ManifestProofStep {
236            name: if curr.name.is_empty() { "root".to_string() } else { curr.name.clone() },
237            path: curr.path.clone(),
238            manifest_hash: curr.hash.clone(),
239            entries,
240        });
241
242        let child = children.iter().find(|c| c.name == *seg)?;
243        if is_leaf {
244            return Some(MembershipProof {
245                root_hash: root.hash.clone(),
246                path: clean.to_string(),
247                target_hash: child.hash.clone(),
248                chain,
249            });
250        }
251
252        if !child.is_directory {
253            return None;
254        }
255        curr = child;
256    }
257
258    None
259}
260
261pub fn verify_membership(proof: &MembershipProof) -> bool {
262    if proof.chain.is_empty() {
263        return false;
264    }
265
266    if proof.chain[0].manifest_hash != proof.root_hash {
267        return false;
268    }
269
270    for (i, step) in proof.chain.iter().enumerate() {
271        let mut sorted_entries = step.entries.clone();
272        sorted_entries.sort_by(|a, b| {
273            a.name.to_lowercase().cmp(&b.name.to_lowercase()).then_with(|| a.name.cmp(&b.name))
274        });
275
276        let mut lines = Vec::new();
277        for e in &sorted_entries {
278            lines.push(format!(
279                "{}:{}:{}:{}",
280                e.name,
281                e.hash,
282                if e.is_directory { "dir" } else { "file" },
283                e.size_bytes
284            ));
285        }
286        let mut data = lines.join("\n");
287        if !lines.is_empty() {
288            data.push('\n');
289        }
290
291        let algo = step.manifest_hash.split(':').next().unwrap_or("blake3");
292        let computed = compute_hash_prefixed(data.as_bytes(), algo);
293        if computed != step.manifest_hash {
294            return false;
295        }
296
297        if i < proof.chain.len() - 1 {
298            let next_step = &proof.chain[i + 1];
299            let entry = step.entries.iter().find(|e| e.name == next_step.name);
300            match entry {
301                Some(e) if e.is_directory && e.hash == next_step.manifest_hash => {}
302                _ => return false,
303            }
304        } else {
305            let leaf_name = proof.path.split('/').next_back().unwrap_or("");
306            let entry = step.entries.iter().find(|e| e.name == leaf_name);
307            match entry {
308                Some(e) if e.hash == proof.target_hash => {}
309                _ => return false,
310            }
311        }
312    }
313
314    true
315}