calimero_node_primitives/sync/
hash_comparison.rs

1//! HashComparison sync types (CIP §4 - State Machine, STATE-BASED branch).
2//!
3//! Types for Merkle tree traversal and hash-based synchronization.
4
5use std::collections::HashSet;
6
7use borsh::{BorshDeserialize, BorshSerialize};
8
9// Re-export the unified CrdtType from primitives (consolidated per issue #1912)
10pub use calimero_primitives::crdt::CrdtType;
11
12// =============================================================================
13// Constants
14// =============================================================================
15
16/// Maximum nodes per response to prevent memory exhaustion.
17///
18/// Limits the size of `TreeNodeResponse::nodes` to prevent DoS attacks
19/// from malicious peers sending oversized responses.
20pub const MAX_NODES_PER_RESPONSE: usize = 1000;
21
22/// Maximum children per node (typical Merkle trees use binary or small fanout).
23///
24/// This limit prevents memory exhaustion from malicious nodes with excessive children.
25pub const MAX_CHILDREN_PER_NODE: usize = 256;
26
27/// Maximum size for leaf value data (1 MB).
28///
29/// Prevents memory exhaustion from malicious peers sending oversized leaf values.
30/// This should be sufficient for most entity data while protecting against DoS.
31pub const MAX_LEAF_VALUE_SIZE: usize = 1_048_576;
32
33/// Maximum allowed tree depth for traversal requests.
34///
35/// This limit prevents resource exhaustion from malicious peers requesting
36/// extremely deep traversals. Most practical Merkle trees have depth < 32.
37pub const MAX_TREE_DEPTH: usize = 64;
38
39// =============================================================================
40// Tree Node Request/Response
41// =============================================================================
42
43/// Request to traverse the Merkle tree for hash comparison.
44///
45/// Used for recursive tree traversal to identify differing entities.
46/// Start at root, request children, compare hashes, recurse on differences.
47#[derive(Clone, Debug, PartialEq, BorshSerialize, BorshDeserialize)]
48pub struct TreeNodeRequest {
49    /// ID of the node to request (root hash or internal node hash).
50    pub node_id: [u8; 32],
51
52    /// Maximum depth to traverse from this node.
53    ///
54    /// This field is private to enforce validation. Use constructors and accessors:
55    /// - `new()` / `with_depth()` - create requests with validated depth
56    /// - `depth()` - get clamped value (always <= MAX_TREE_DEPTH)
57    ///
58    /// This prevents DoS attacks where an attacker sends a request with an
59    /// extremely large depth value to cause resource exhaustion.
60    max_depth: Option<usize>,
61}
62
63impl TreeNodeRequest {
64    /// Create a request for a specific node.
65    #[must_use]
66    pub fn new(node_id: [u8; 32]) -> Self {
67        Self {
68            node_id,
69            max_depth: None,
70        }
71    }
72
73    /// Create a request with depth limit.
74    #[must_use]
75    pub fn with_depth(node_id: [u8; 32], max_depth: usize) -> Self {
76        Self {
77            node_id,
78            // Clamp to MAX_TREE_DEPTH to prevent resource exhaustion
79            max_depth: Some(max_depth.min(MAX_TREE_DEPTH)),
80        }
81    }
82
83    /// Create a request for the root node.
84    #[must_use]
85    pub fn root(root_hash: [u8; 32]) -> Self {
86        Self::new(root_hash)
87    }
88
89    /// Get the validated depth limit.
90    ///
91    /// Always clamps to MAX_TREE_DEPTH, even if raw field was set to a larger
92    /// value (e.g., via deserialization from an untrusted source).
93    ///
94    /// Use this instead of accessing `max_depth` directly when processing requests.
95    #[must_use]
96    pub fn depth(&self) -> Option<usize> {
97        self.max_depth.map(|d| d.min(MAX_TREE_DEPTH))
98    }
99}
100
101/// Response containing tree nodes for hash comparison.
102#[derive(Clone, Debug, PartialEq, BorshSerialize, BorshDeserialize)]
103pub struct TreeNodeResponse {
104    /// Nodes in the requested subtree.
105    ///
106    /// Limited to MAX_NODES_PER_RESPONSE entries. Use `is_valid()` to check
107    /// bounds after deserialization from untrusted sources.
108    pub nodes: Vec<TreeNode>,
109
110    /// True if the requested node was not found.
111    pub not_found: bool,
112}
113
114impl TreeNodeResponse {
115    /// Create a response with nodes.
116    #[must_use]
117    pub fn new(nodes: Vec<TreeNode>) -> Self {
118        Self {
119            nodes,
120            not_found: false,
121        }
122    }
123
124    /// Create a not-found response.
125    #[must_use]
126    pub fn not_found() -> Self {
127        Self {
128            nodes: vec![],
129            not_found: true,
130        }
131    }
132
133    /// Check if response contains any leaf nodes.
134    #[must_use]
135    pub fn has_leaves(&self) -> bool {
136        self.nodes.iter().any(|n| n.is_leaf())
137    }
138
139    /// Get an iterator over leaf nodes in response.
140    ///
141    /// Returns an iterator rather than allocating a Vec, which is more
142    /// efficient for single-pass iteration.
143    pub fn leaves(&self) -> impl Iterator<Item = &TreeNode> {
144        self.nodes.iter().filter(|n| n.is_leaf())
145    }
146
147    /// Check if response is within valid bounds.
148    ///
149    /// Call this after deserializing from untrusted sources to prevent
150    /// memory exhaustion attacks. Validates both response size and all
151    /// contained nodes.
152    #[must_use]
153    pub fn is_valid(&self) -> bool {
154        self.nodes.len() <= MAX_NODES_PER_RESPONSE && self.nodes.iter().all(TreeNode::is_valid)
155    }
156}
157
158// =============================================================================
159// Tree Node
160// =============================================================================
161
162/// A node in the Merkle tree.
163///
164/// Can be either an internal node (has children) or a leaf node (has data).
165#[derive(Clone, Debug, PartialEq, BorshSerialize, BorshDeserialize)]
166pub struct TreeNode {
167    /// Node ID - stable identifier derived from the node's position/key in the tree.
168    ///
169    /// For internal nodes: typically hash of path or concatenation of child keys.
170    /// For leaf nodes: typically hash of the entity key.
171    /// This ID remains stable even when content changes.
172    pub id: [u8; 32],
173
174    /// Merkle hash - changes when subtree content changes.
175    ///
176    /// For internal nodes: hash of all children's hashes (propagates changes up).
177    /// For leaf nodes: hash of the leaf data (key + value + metadata).
178    /// Used for efficient comparison: if hashes match, subtrees are identical.
179    pub hash: [u8; 32],
180
181    /// Child node IDs (empty for leaf nodes).
182    ///
183    /// Typically limited to MAX_CHILDREN_PER_NODE. Use `is_valid()` to check
184    /// bounds after deserialization from untrusted sources.
185    pub children: Vec<[u8; 32]>,
186
187    /// Leaf data (present only for leaf nodes).
188    pub leaf_data: Option<TreeLeafData>,
189}
190
191impl TreeNode {
192    /// Create an internal node.
193    #[must_use]
194    pub fn internal(id: [u8; 32], hash: [u8; 32], children: Vec<[u8; 32]>) -> Self {
195        Self {
196            id,
197            hash,
198            children,
199            leaf_data: None,
200        }
201    }
202
203    /// Create a leaf node.
204    #[must_use]
205    pub fn leaf(id: [u8; 32], hash: [u8; 32], data: TreeLeafData) -> Self {
206        Self {
207            id,
208            hash,
209            children: vec![],
210            leaf_data: Some(data),
211        }
212    }
213
214    /// Check if node is within valid bounds and structurally valid.
215    ///
216    /// Call this after deserializing from untrusted sources.
217    /// Validates:
218    /// - Children count within MAX_CHILDREN_PER_NODE
219    /// - Structural invariant: must have exactly one of children OR leaf_data
220    /// - Leaf data validity (value size within limits)
221    #[must_use]
222    pub fn is_valid(&self) -> bool {
223        // Check children count
224        if self.children.len() > MAX_CHILDREN_PER_NODE {
225            return false;
226        }
227
228        // Check structural invariant: must have exactly one of children or data
229        // - Internal nodes: non-empty children, no leaf_data
230        // - Leaf nodes: empty children, has leaf_data
231        let has_children = !self.children.is_empty();
232        let has_data = self.leaf_data.is_some();
233        if has_children == has_data {
234            // Invalid: either both present (ambiguous) or both absent (empty)
235            return false;
236        }
237
238        // Validate leaf data if present
239        if let Some(ref leaf_data) = self.leaf_data {
240            if !leaf_data.is_valid() {
241                return false;
242            }
243        }
244
245        true
246    }
247
248    /// Check if this is a leaf node.
249    #[must_use]
250    pub fn is_leaf(&self) -> bool {
251        self.leaf_data.is_some()
252    }
253
254    /// Check if this is an internal node.
255    #[must_use]
256    pub fn is_internal(&self) -> bool {
257        self.leaf_data.is_none()
258    }
259
260    /// Get number of children (0 for leaf nodes).
261    #[must_use]
262    pub fn child_count(&self) -> usize {
263        self.children.len()
264    }
265}
266
267// =============================================================================
268// Tree Leaf Data
269// =============================================================================
270
271/// Data stored at a leaf node (entity).
272///
273/// Contains ALL information needed for CRDT merge on the receiving side.
274/// CRITICAL: `metadata` MUST include `crdt_type` for proper merge.
275#[derive(Clone, Debug, PartialEq, BorshSerialize, BorshDeserialize)]
276pub struct TreeLeafData {
277    /// Entity key (unique identifier within collection).
278    pub key: [u8; 32],
279
280    /// Serialized entity value.
281    pub value: Vec<u8>,
282
283    /// Entity metadata including crdt_type.
284    /// CRITICAL: Must be included for CRDT merge to work correctly.
285    pub metadata: LeafMetadata,
286}
287
288impl TreeLeafData {
289    /// Create leaf data.
290    #[must_use]
291    pub fn new(key: [u8; 32], value: Vec<u8>, metadata: LeafMetadata) -> Self {
292        Self {
293            key,
294            value,
295            metadata,
296        }
297    }
298
299    /// Check if leaf data is within valid bounds.
300    ///
301    /// Call this after deserializing from untrusted sources.
302    #[must_use]
303    pub fn is_valid(&self) -> bool {
304        self.value.len() <= MAX_LEAF_VALUE_SIZE
305    }
306}
307
308/// Metadata for a leaf entity.
309///
310/// Minimal metadata needed for CRDT merge during sync.
311///
312/// This is a wire-protocol-optimized subset of `calimero_storage::Metadata`.
313/// It contains only the fields needed for sync operations, avoiding larger
314/// fields like `field_name: String` that aren't needed over the wire.
315///
316/// When receiving entities, implementations should map this to/from the
317/// storage layer's `Metadata` type.
318#[derive(Clone, Debug, PartialEq, BorshSerialize, BorshDeserialize)]
319pub struct LeafMetadata {
320    /// CRDT type for proper merge semantics.
321    pub crdt_type: CrdtType,
322
323    /// HLC timestamp of last modification.
324    pub hlc_timestamp: u64,
325
326    /// Version counter (for some CRDT types).
327    pub version: u64,
328
329    /// Collection ID this entity belongs to.
330    pub collection_id: [u8; 32],
331
332    /// Optional parent entity ID (for nested structures).
333    pub parent_id: Option<[u8; 32]>,
334}
335
336impl LeafMetadata {
337    /// Create metadata with required fields.
338    #[must_use]
339    pub fn new(crdt_type: CrdtType, hlc_timestamp: u64, collection_id: [u8; 32]) -> Self {
340        Self {
341            crdt_type,
342            hlc_timestamp,
343            version: 0,
344            collection_id,
345            parent_id: None,
346        }
347    }
348
349    /// Set version.
350    #[must_use]
351    pub fn with_version(mut self, version: u64) -> Self {
352        self.version = version;
353        self
354    }
355
356    /// Set parent ID.
357    #[must_use]
358    pub fn with_parent(mut self, parent_id: [u8; 32]) -> Self {
359        self.parent_id = Some(parent_id);
360        self
361    }
362}
363
364// =============================================================================
365// Tree Compare Result
366// =============================================================================
367
368/// Result of comparing two tree nodes.
369///
370/// Used for Merkle tree traversal during HashComparison sync.
371/// Identifies which children need further traversal in both directions.
372///
373/// Note: Borsh derives are included for consistency with other sync types and
374/// potential future use in batched comparison responses over the wire.
375#[derive(Clone, Debug, PartialEq, BorshSerialize, BorshDeserialize)]
376pub enum TreeCompareResult {
377    /// Hashes match - no sync needed for this subtree.
378    Equal,
379    /// Hashes differ - need to recurse or fetch leaf.
380    ///
381    /// For internal nodes: lists children to recurse into.
382    /// For leaf nodes: all vecs will be empty, but Different still indicates
383    /// that the leaf data needs to be fetched and merged bidirectionally.
384    Different {
385        /// IDs of children in remote but not in local (need to fetch).
386        remote_only_children: Vec<[u8; 32]>,
387        /// IDs of children in local but not in remote (for bidirectional sync).
388        local_only_children: Vec<[u8; 32]>,
389        /// IDs of children present on both sides that need recursive comparison.
390        /// These are the primary candidates for recursion when parent hashes differ.
391        common_children: Vec<[u8; 32]>,
392    },
393    /// Local node missing - need to fetch from remote.
394    LocalMissing,
395    /// Remote node missing - local has data that remote doesn't.
396    /// For bidirectional sync, this means we may need to push to remote.
397    RemoteMissing,
398}
399
400impl TreeCompareResult {
401    /// Check if sync (pull from remote) is needed.
402    ///
403    /// Returns true if local needs data from remote.
404    #[must_use]
405    pub fn needs_sync(&self) -> bool {
406        !matches!(self, Self::Equal | Self::RemoteMissing)
407    }
408
409    /// Check if push (send to remote) is needed for bidirectional sync.
410    ///
411    /// Returns true if local has data that remote doesn't:
412    /// - `RemoteMissing`: entire local subtree needs pushing
413    /// - `Different` with `local_only_children`: those children need pushing
414    /// - `Different` with all empty vecs: this is a **leaf node comparison** where
415    ///   hashes differ, meaning local leaf data needs pushing for CRDT merge
416    #[must_use]
417    pub fn needs_push(&self) -> bool {
418        match self {
419            Self::RemoteMissing => true,
420            Self::Different {
421                remote_only_children,
422                local_only_children,
423                common_children,
424            } => {
425                // Push needed if we have local-only children
426                if !local_only_children.is_empty() {
427                    return true;
428                }
429                // Leaf node detection: when all child vecs are empty but hashes differed,
430                // we compared two leaf nodes with different content. The local leaf data
431                // needs to be pushed for bidirectional CRDT merge.
432                remote_only_children.is_empty() && common_children.is_empty()
433            }
434            _ => false,
435        }
436    }
437}
438
439// =============================================================================
440// Compare Function
441// =============================================================================
442
443/// Compare local and remote tree nodes.
444///
445/// Returns which children (if any) need further traversal in both directions.
446/// This supports bidirectional sync where both nodes may have unique data.
447///
448/// # Arguments
449/// * `local` - Local tree node, or None if not present locally
450/// * `remote` - Remote tree node, or None if not present on remote
451///
452/// # Precondition
453/// When both nodes are present, they must represent the same tree position
454/// (i.e., have matching IDs). Comparing nodes at different positions is a
455/// caller bug and will trigger a debug assertion.
456///
457/// # Returns
458/// * `Equal` - Hashes match, no sync needed
459/// * `Different` - Hashes differ, contains children needing traversal
460/// * `LocalMissing` - Need to fetch from remote
461/// * `RemoteMissing` - Local has data remote doesn't (for bidirectional push)
462#[must_use]
463pub fn compare_tree_nodes(
464    local: Option<&TreeNode>,
465    remote: Option<&TreeNode>,
466) -> TreeCompareResult {
467    match (local, remote) {
468        (None, None) => TreeCompareResult::Equal,
469        (None, Some(_)) => TreeCompareResult::LocalMissing,
470        (Some(_), None) => TreeCompareResult::RemoteMissing,
471        (Some(local_node), Some(remote_node)) => {
472            // Verify precondition: nodes must represent the same tree position
473            debug_assert_eq!(
474                local_node.id, remote_node.id,
475                "compare_tree_nodes called with nodes at different tree positions"
476            );
477
478            if local_node.hash == remote_node.hash {
479                TreeCompareResult::Equal
480            } else {
481                // Use HashSet for O(1) lookups instead of O(n) Vec::contains
482                let local_children: HashSet<&[u8; 32]> = local_node.children.iter().collect();
483                let remote_children: HashSet<&[u8; 32]> = remote_node.children.iter().collect();
484
485                // Children in remote but not in local (need to fetch)
486                let remote_only_children: Vec<[u8; 32]> = remote_node
487                    .children
488                    .iter()
489                    .filter(|child_id| !local_children.contains(child_id))
490                    .copied()
491                    .collect();
492
493                // Children in local but not in remote (for bidirectional sync)
494                let local_only_children: Vec<[u8; 32]> = local_node
495                    .children
496                    .iter()
497                    .filter(|child_id| !remote_children.contains(child_id))
498                    .copied()
499                    .collect();
500
501                // Children present on both sides - these are the primary candidates
502                // for recursive comparison when parent hashes differ
503                let common_children: Vec<[u8; 32]> = local_node
504                    .children
505                    .iter()
506                    .filter(|child_id| remote_children.contains(child_id))
507                    .copied()
508                    .collect();
509
510                TreeCompareResult::Different {
511                    remote_only_children,
512                    local_only_children,
513                    common_children,
514                }
515            }
516        }
517    }
518}
519
520// =============================================================================
521// Tests
522// =============================================================================
523
524#[cfg(test)]
525mod tests {
526    use super::*;
527
528    #[test]
529    fn test_tree_node_request_roundtrip() {
530        let request = TreeNodeRequest::with_depth([1; 32], 3);
531
532        let encoded = borsh::to_vec(&request).expect("serialize");
533        let decoded: TreeNodeRequest = borsh::from_slice(&encoded).expect("deserialize");
534
535        assert_eq!(request, decoded);
536        assert_eq!(decoded.max_depth, Some(3));
537    }
538
539    #[test]
540    fn test_tree_node_request_root() {
541        let root_hash = [42; 32];
542        let request = TreeNodeRequest::root(root_hash);
543
544        assert_eq!(request.node_id, root_hash);
545        assert!(request.max_depth.is_none());
546    }
547
548    #[test]
549    fn test_tree_node_internal() {
550        let node = TreeNode::internal([1; 32], [2; 32], vec![[3; 32], [4; 32]]);
551
552        assert!(node.is_internal());
553        assert!(!node.is_leaf());
554        assert_eq!(node.child_count(), 2);
555        assert!(node.leaf_data.is_none());
556    }
557
558    #[test]
559    fn test_tree_node_leaf() {
560        let metadata = LeafMetadata::new(CrdtType::lww_register("test"), 12345, [5; 32]);
561        let leaf_data = TreeLeafData::new([1; 32], vec![1, 2, 3], metadata);
562        let node = TreeNode::leaf([2; 32], [3; 32], leaf_data);
563
564        assert!(node.is_leaf());
565        assert!(!node.is_internal());
566        assert_eq!(node.child_count(), 0);
567        assert!(node.leaf_data.is_some());
568    }
569
570    #[test]
571    fn test_tree_node_roundtrip() {
572        let metadata = LeafMetadata::new(CrdtType::unordered_map("String", "u64"), 999, [6; 32])
573            .with_version(5)
574            .with_parent([7; 32]);
575        let leaf_data = TreeLeafData::new([1; 32], vec![4, 5, 6], metadata);
576        let node = TreeNode::leaf([2; 32], [3; 32], leaf_data);
577
578        let encoded = borsh::to_vec(&node).expect("serialize");
579        let decoded: TreeNode = borsh::from_slice(&encoded).expect("deserialize");
580
581        assert_eq!(node, decoded);
582    }
583
584    #[test]
585    fn test_tree_node_response_roundtrip() {
586        let internal = TreeNode::internal([1; 32], [2; 32], vec![[3; 32]]);
587        let metadata = LeafMetadata::new(CrdtType::Rga, 100, [4; 32]);
588        let leaf_data = TreeLeafData::new([5; 32], vec![7, 8, 9], metadata);
589        let leaf = TreeNode::leaf([6; 32], [7; 32], leaf_data);
590
591        let response = TreeNodeResponse::new(vec![internal, leaf]);
592
593        let encoded = borsh::to_vec(&response).expect("serialize");
594        let decoded: TreeNodeResponse = borsh::from_slice(&encoded).expect("deserialize");
595
596        assert_eq!(response, decoded);
597        assert!(decoded.has_leaves());
598        assert_eq!(decoded.leaves().count(), 1);
599    }
600
601    #[test]
602    fn test_tree_node_response_not_found() {
603        let response = TreeNodeResponse::not_found();
604
605        assert!(response.not_found);
606        assert!(response.nodes.is_empty());
607        assert!(!response.has_leaves());
608    }
609
610    #[test]
611    fn test_leaf_metadata_builder() {
612        let metadata = LeafMetadata::new(CrdtType::PnCounter, 500, [1; 32])
613            .with_version(10)
614            .with_parent([2; 32]);
615
616        assert_eq!(metadata.crdt_type, CrdtType::PnCounter);
617        assert_eq!(metadata.hlc_timestamp, 500);
618        assert_eq!(metadata.version, 10);
619        assert_eq!(metadata.parent_id, Some([2; 32]));
620    }
621
622    #[test]
623    fn test_crdt_type_variants() {
624        let types = vec![
625            CrdtType::lww_register("test"),
626            CrdtType::GCounter,
627            CrdtType::PnCounter,
628            CrdtType::Rga,
629            CrdtType::unordered_map("String", "u64"),
630            CrdtType::unordered_set("String"),
631            CrdtType::vector("u64"),
632            CrdtType::UserStorage,
633            CrdtType::FrozenStorage,
634            CrdtType::Custom("test".to_string()),
635        ];
636
637        for crdt_type in types {
638            let encoded = borsh::to_vec(&crdt_type).expect("serialize");
639            let decoded: CrdtType = borsh::from_slice(&encoded).expect("deserialize");
640            assert_eq!(crdt_type, decoded);
641        }
642    }
643
644    #[test]
645    fn test_compare_tree_nodes_equal() {
646        let local = TreeNode::internal([1; 32], [99; 32], vec![[2; 32]]);
647        let remote = TreeNode::internal([1; 32], [99; 32], vec![[2; 32]]);
648
649        let result = compare_tree_nodes(Some(&local), Some(&remote));
650        assert_eq!(result, TreeCompareResult::Equal);
651        assert!(!result.needs_sync());
652    }
653
654    #[test]
655    fn test_compare_tree_nodes_local_missing() {
656        let remote = TreeNode::internal([1; 32], [2; 32], vec![[3; 32]]);
657
658        let result = compare_tree_nodes(None, Some(&remote));
659        assert_eq!(result, TreeCompareResult::LocalMissing);
660        assert!(result.needs_sync());
661    }
662
663    #[test]
664    fn test_compare_tree_nodes_different() {
665        let local = TreeNode::internal([1; 32], [10; 32], vec![[2; 32]]);
666        let remote = TreeNode::internal([1; 32], [20; 32], vec![[2; 32], [3; 32]]);
667
668        let result = compare_tree_nodes(Some(&local), Some(&remote));
669
670        match &result {
671            TreeCompareResult::Different {
672                remote_only_children,
673                local_only_children: _,
674                common_children,
675            } => {
676                // [3; 32] is in remote but not in local
677                assert!(remote_only_children.contains(&[3; 32]));
678                // [2; 32] is common to both sides
679                assert!(common_children.contains(&[2; 32]));
680            }
681            _ => panic!("Expected Different result"),
682        }
683        assert!(result.needs_sync());
684    }
685
686    #[test]
687    fn test_tree_compare_result_needs_sync() {
688        assert!(!TreeCompareResult::Equal.needs_sync());
689        assert!(!TreeCompareResult::RemoteMissing.needs_sync());
690        assert!(TreeCompareResult::LocalMissing.needs_sync());
691        assert!(TreeCompareResult::Different {
692            remote_only_children: vec![],
693            local_only_children: vec![],
694            common_children: vec![],
695        }
696        .needs_sync());
697    }
698
699    #[test]
700    fn test_tree_compare_result_roundtrip() {
701        let variants = vec![
702            TreeCompareResult::Equal,
703            TreeCompareResult::LocalMissing,
704            TreeCompareResult::RemoteMissing,
705            TreeCompareResult::Different {
706                remote_only_children: vec![[1; 32], [2; 32]],
707                local_only_children: vec![[3; 32]],
708                common_children: vec![[4; 32], [5; 32], [6; 32]],
709            },
710            TreeCompareResult::Different {
711                remote_only_children: vec![],
712                local_only_children: vec![],
713                common_children: vec![],
714            },
715        ];
716
717        for original in variants {
718            let encoded = borsh::to_vec(&original).expect("encode");
719            let decoded: TreeCompareResult = borsh::from_slice(&encoded).expect("decode");
720            assert_eq!(original, decoded);
721        }
722    }
723
724    #[test]
725    fn test_compare_tree_nodes_leaf_content_differs() {
726        let local_metadata = LeafMetadata::new(CrdtType::lww_register("test"), 100, [1; 32]);
727        let local_leaf = TreeLeafData::new([10; 32], vec![1, 2, 3], local_metadata);
728        let local = TreeNode::leaf([1; 32], [100; 32], local_leaf);
729
730        let remote_metadata = LeafMetadata::new(CrdtType::lww_register("test"), 200, [1; 32]);
731        let remote_leaf = TreeLeafData::new([10; 32], vec![4, 5, 6], remote_metadata);
732        let remote = TreeNode::leaf([1; 32], [200; 32], remote_leaf);
733
734        let result = compare_tree_nodes(Some(&local), Some(&remote));
735
736        match &result {
737            TreeCompareResult::Different {
738                remote_only_children,
739                local_only_children,
740                common_children,
741            } => {
742                assert!(remote_only_children.is_empty());
743                assert!(local_only_children.is_empty());
744                assert!(common_children.is_empty());
745            }
746            _ => panic!("Expected Different result for leaves with different content"),
747        }
748        assert!(result.needs_sync());
749        assert!(result.needs_push());
750    }
751
752    #[test]
753    fn test_compare_tree_nodes_remote_missing() {
754        let local = TreeNode::internal([1; 32], [2; 32], vec![[3; 32]]);
755
756        let result = compare_tree_nodes(Some(&local), None);
757        assert_eq!(result, TreeCompareResult::RemoteMissing);
758        assert!(!result.needs_sync());
759    }
760
761    #[test]
762    fn test_compare_tree_nodes_local_only_children() {
763        let local = TreeNode::internal([1; 32], [10; 32], vec![[2; 32], [3; 32], [4; 32]]);
764        let remote = TreeNode::internal([1; 32], [20; 32], vec![[2; 32], [5; 32]]);
765
766        let result = compare_tree_nodes(Some(&local), Some(&remote));
767
768        match &result {
769            TreeCompareResult::Different {
770                remote_only_children,
771                local_only_children,
772                common_children,
773            } => {
774                assert!(remote_only_children.contains(&[5; 32]));
775                assert!(local_only_children.contains(&[3; 32]));
776                assert!(local_only_children.contains(&[4; 32]));
777                assert!(common_children.contains(&[2; 32]));
778            }
779            _ => panic!("Expected Different result"),
780        }
781    }
782
783    #[test]
784    fn test_tree_node_request_max_depth_validation() {
785        // Constructors should clamp to MAX_TREE_DEPTH
786        let request = TreeNodeRequest::with_depth([1; 32], MAX_TREE_DEPTH);
787        assert_eq!(request.depth(), Some(MAX_TREE_DEPTH));
788
789        // Excessive depth should be clamped by constructor
790        let excessive = TreeNodeRequest::with_depth([1; 32], MAX_TREE_DEPTH + 100);
791        assert_eq!(excessive.depth(), Some(MAX_TREE_DEPTH));
792    }
793
794    #[test]
795    fn test_tree_node_request_depth_accessor() {
796        // depth() returns None when no depth is set
797        let request_none = TreeNodeRequest::new([1; 32]);
798        assert_eq!(request_none.depth(), None);
799
800        // depth() returns Some with clamped value when set
801        let request_with_depth = TreeNodeRequest::with_depth([1; 32], 5);
802        assert_eq!(request_with_depth.depth(), Some(5));
803    }
804
805    #[test]
806    fn test_tree_node_request_depth_clamping_on_deserialize() {
807        // Simulate an attacker sending a malicious request with excessive depth
808        // by manually constructing the serialized bytes with a huge max_depth value
809        let node_id = [1u8; 32];
810        let malicious_depth: usize = usize::MAX;
811
812        // Create a request and serialize it
813        let mut bytes = Vec::new();
814        // node_id: 32 bytes
815        bytes.extend_from_slice(&node_id);
816        // max_depth: Option<usize> - 1 byte tag (Some = 1) + usize (8 bytes on 64-bit)
817        bytes.push(1); // Some variant
818        bytes.extend_from_slice(&malicious_depth.to_le_bytes());
819
820        // Deserialize the malicious request
821        let request: TreeNodeRequest = borsh::from_slice(&bytes).expect("deserialize");
822
823        // The depth() accessor should clamp to MAX_TREE_DEPTH
824        assert_eq!(
825            request.depth(),
826            Some(MAX_TREE_DEPTH),
827            "depth() must clamp deserialized values to MAX_TREE_DEPTH"
828        );
829    }
830
831    #[test]
832    fn test_tree_node_request_private_field_enforces_validation() {
833        // This test documents that max_depth is private and cannot be set directly
834        // The only ways to create a TreeNodeRequest are:
835        // 1. TreeNodeRequest::new() - no depth limit
836        // 2. TreeNodeRequest::with_depth() - clamped depth limit
837        // 3. Deserialization - depth() accessor clamps when read
838
839        // Verify new() creates request without depth limit
840        let no_depth = TreeNodeRequest::new([0; 32]);
841        assert_eq!(no_depth.depth(), None);
842
843        // Verify with_depth() clamps excessive values
844        let clamped = TreeNodeRequest::with_depth([0; 32], 999_999);
845        assert_eq!(clamped.depth(), Some(MAX_TREE_DEPTH));
846
847        // Verify reasonable values pass through
848        let reasonable = TreeNodeRequest::with_depth([0; 32], 3);
849        assert_eq!(reasonable.depth(), Some(3));
850    }
851
852    #[test]
853    fn test_tree_node_response_validation() {
854        let valid_response =
855            TreeNodeResponse::new(vec![TreeNode::internal([1; 32], [2; 32], vec![[3; 32]])]);
856        assert!(valid_response.is_valid());
857
858        let metadata = LeafMetadata::new(CrdtType::lww_register("test"), 100, [1; 32]);
859        let leaf_data = TreeLeafData::new([10; 32], vec![1, 2, 3], metadata);
860        let leaf_response =
861            TreeNodeResponse::new(vec![TreeNode::leaf([1; 32], [2; 32], leaf_data)]);
862        assert!(leaf_response.is_valid());
863
864        let mut nodes = Vec::new();
865        for i in 0..MAX_NODES_PER_RESPONSE {
866            let id = [i as u8; 32];
867            nodes.push(TreeNode::internal(id, id, vec![[0; 32]]));
868        }
869        let at_limit = TreeNodeResponse::new(nodes);
870        assert!(at_limit.is_valid());
871    }
872
873    #[test]
874    fn test_tree_node_validation() {
875        let valid = TreeNode::internal([1; 32], [2; 32], vec![[3; 32], [4; 32]]);
876        assert!(valid.is_valid());
877
878        let children: Vec<[u8; 32]> = (0..MAX_CHILDREN_PER_NODE).map(|i| [i as u8; 32]).collect();
879        let at_limit = TreeNode::internal([1; 32], [2; 32], children);
880        assert!(at_limit.is_valid());
881
882        let over_children: Vec<[u8; 32]> =
883            (0..=MAX_CHILDREN_PER_NODE).map(|i| [i as u8; 32]).collect();
884        let over_limit = TreeNode::internal([1; 32], [2; 32], over_children);
885        assert!(!over_limit.is_valid());
886
887        let metadata = LeafMetadata::new(CrdtType::lww_register("test"), 100, [1; 32]);
888        let leaf_data = TreeLeafData::new([10; 32], vec![1, 2, 3], metadata);
889        let invalid_node = TreeNode {
890            id: [1; 32],
891            hash: [2; 32],
892            children: vec![[3; 32]],
893            leaf_data: Some(leaf_data),
894        };
895        assert!(!invalid_node.is_valid());
896
897        let valid_metadata = LeafMetadata::new(CrdtType::lww_register("test"), 100, [1; 32]);
898        let valid_leaf_data = TreeLeafData::new([10; 32], vec![1, 2, 3], valid_metadata);
899        let valid_leaf = TreeNode::leaf([1; 32], [2; 32], valid_leaf_data);
900        assert!(valid_leaf.is_valid());
901
902        let empty_node = TreeNode::internal([1; 32], [2; 32], vec![]);
903        assert!(!empty_node.is_valid());
904    }
905
906    #[test]
907    fn test_tree_node_response_validation_over_limit() {
908        let mut nodes = Vec::new();
909        for i in 0..=MAX_NODES_PER_RESPONSE {
910            let id = [i as u8; 32];
911            nodes.push(TreeNode::internal(id, id, vec![[0; 32]]));
912        }
913        let over_limit = TreeNodeResponse::new(nodes);
914        assert!(!over_limit.is_valid());
915
916        let over_children: Vec<[u8; 32]> =
917            (0..=MAX_CHILDREN_PER_NODE).map(|i| [i as u8; 32]).collect();
918        let invalid_node = TreeNode::internal([1; 32], [2; 32], over_children);
919        let response_with_invalid = TreeNodeResponse::new(vec![invalid_node]);
920        assert!(!response_with_invalid.is_valid());
921
922        let empty_node = TreeNode::internal([1; 32], [2; 32], vec![]);
923        let response_with_empty = TreeNodeResponse::new(vec![empty_node]);
924        assert!(!response_with_empty.is_valid());
925    }
926
927    #[test]
928    fn test_tree_leaf_data_validation() {
929        let metadata = LeafMetadata::new(CrdtType::lww_register("test"), 100, [1; 32]);
930
931        let valid = TreeLeafData::new([1; 32], vec![1, 2, 3], metadata.clone());
932        assert!(valid.is_valid());
933
934        let at_limit_value = vec![0u8; MAX_LEAF_VALUE_SIZE];
935        let at_limit = TreeLeafData::new([1; 32], at_limit_value, metadata.clone());
936        assert!(at_limit.is_valid());
937
938        let over_limit_value = vec![0u8; MAX_LEAF_VALUE_SIZE + 1];
939        let over_limit = TreeLeafData::new([1; 32], over_limit_value, metadata);
940        assert!(!over_limit.is_valid());
941    }
942
943    #[test]
944    fn test_tree_compare_result_needs_push() {
945        assert!(TreeCompareResult::RemoteMissing.needs_push());
946
947        let with_local_only = TreeCompareResult::Different {
948            remote_only_children: vec![],
949            local_only_children: vec![[1; 32]],
950            common_children: vec![],
951        };
952        assert!(with_local_only.needs_push());
953
954        let with_remote_only = TreeCompareResult::Different {
955            remote_only_children: vec![[1; 32]],
956            local_only_children: vec![],
957            common_children: vec![],
958        };
959        assert!(!with_remote_only.needs_push());
960
961        let with_common_only = TreeCompareResult::Different {
962            remote_only_children: vec![],
963            local_only_children: vec![],
964            common_children: vec![[1; 32]],
965        };
966        assert!(!with_common_only.needs_push());
967
968        let differing_leaves = TreeCompareResult::Different {
969            remote_only_children: vec![],
970            local_only_children: vec![],
971            common_children: vec![],
972        };
973        assert!(differing_leaves.needs_push());
974
975        assert!(!TreeCompareResult::Equal.needs_push());
976        assert!(!TreeCompareResult::LocalMissing.needs_push());
977    }
978}
calimero_node_primitives/sync/hash_comparison.rs

calimero_node_primitives/sync/
hash_comparison.rs
