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