mdcs_merkle/
node.rs

1//! Merkle node definition and builder.
2//!
3//! Each node in the Merkle-DAG contains:
4//! - A content identifier (CID) computed from its contents
5//! - References to parent nodes (causal predecessors)
6//! - A payload (delta-group or snapshot)
7//! - A logical timestamp
8
9use crate::hash::{Hash, Hasher};
10use serde::{Deserialize, Serialize};
11
12/// The payload carried by a Merkle node.
13#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
14pub enum Payload {
15    /// Genesis node - the root of the DAG.
16    Genesis,
17
18    /// A delta-group containing incremental state changes.
19    /// The bytes are a serialized delta from the δ-CRDT layer.
20    Delta(Vec<u8>),
21
22    /// A snapshot of the full state at a point in time.
23    /// Used for compaction and bootstrapping new replicas.
24    Snapshot(Vec<u8>),
25}
26
27impl Payload {
28    /// Create a genesis payload.
29    pub fn genesis() -> Self {
30        Payload::Genesis
31    }
32
33    /// Create a delta payload from serialized bytes.
34    pub fn delta(data: Vec<u8>) -> Self {
35        Payload::Delta(data)
36    }
37
38    /// Create a snapshot payload from serialized bytes.
39    pub fn snapshot(data: Vec<u8>) -> Self {
40        Payload::Snapshot(data)
41    }
42
43    /// Check if this is a genesis payload.
44    pub fn is_genesis(&self) -> bool {
45        matches!(self, Payload::Genesis)
46    }
47
48    /// Check if this is a delta payload.
49    pub fn is_delta(&self) -> bool {
50        matches!(self, Payload::Delta(_))
51    }
52
53    /// Check if this is a snapshot payload.
54    pub fn is_snapshot(&self) -> bool {
55        matches!(self, Payload::Snapshot(_))
56    }
57
58    /// Get the payload data as bytes (returns empty slice for Genesis).
59    pub fn as_bytes(&self) -> &[u8] {
60        match self {
61            Payload::Genesis => &[],
62            Payload::Delta(data) => data,
63            Payload::Snapshot(data) => data,
64        }
65    }
66
67    /// Get the payload type as a byte for hashing.
68    fn type_byte(&self) -> u8 {
69        match self {
70            Payload::Genesis => 0,
71            Payload::Delta(_) => 1,
72            Payload::Snapshot(_) => 2,
73        }
74    }
75}
76
77/// A node in the Merkle-DAG representing a causal event.
78///
79/// The node's CID is computed from its contents, making it content-addressed
80/// and tamper-proof. Any change to the node's data would change its CID.
81#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
82pub struct MerkleNode {
83    /// Content identifier - SHA-256 hash of the node's contents.
84    /// This is computed when the node is built.
85    pub cid: Hash,
86
87    /// Hashes of parent nodes (causal predecessors).
88    /// Empty for genesis nodes.
89    pub parents: Vec<Hash>,
90
91    /// The payload carried by this node.
92    pub payload: Payload,
93
94    /// Logical timestamp (monotonically increasing per replica).
95    pub timestamp: u64,
96
97    /// The replica that created this node.
98    pub creator: String,
99}
100
101impl MerkleNode {
102    /// Check if this is a genesis node.
103    pub fn is_genesis(&self) -> bool {
104        self.parents.is_empty() && self.payload.is_genesis()
105    }
106
107    /// Check if this node is a descendant of another (has it as ancestor).
108    /// Note: This only checks direct parents, not transitive ancestry.
109    pub fn has_parent(&self, cid: &Hash) -> bool {
110        self.parents.contains(cid)
111    }
112
113    /// Get the number of parents (branching factor for this node).
114    pub fn parent_count(&self) -> usize {
115        self.parents.len()
116    }
117
118    /// Compute the CID for a node with the given contents.
119    /// This is used by the builder to generate the CID.
120    fn compute_cid(parents: &[Hash], payload: &Payload, timestamp: u64, creator: &str) -> Hash {
121        let mut hasher = Hasher::new();
122
123        // Hash the number of parents
124        hasher.update(&(parents.len() as u64).to_le_bytes());
125
126        // Hash each parent CID (sorted for determinism)
127        let mut sorted_parents = parents.to_vec();
128        sorted_parents.sort();
129        for parent in &sorted_parents {
130            hasher.update(parent.as_bytes());
131        }
132
133        // Hash the payload type and data
134        hasher.update(&[payload.type_byte()]);
135        hasher.update(payload.as_bytes());
136
137        // Hash the timestamp
138        hasher.update(&timestamp.to_le_bytes());
139
140        // Hash the creator
141        hasher.update(creator.as_bytes());
142
143        hasher.finalize()
144    }
145
146    /// Verify that the CID matches the node's contents.
147    pub fn verify(&self) -> bool {
148        let computed =
149            Self::compute_cid(&self.parents, &self.payload, self.timestamp, &self.creator);
150        computed == self.cid
151    }
152}
153
154/// Builder for creating Merkle nodes.
155#[derive(Clone, Debug, Default)]
156pub struct NodeBuilder {
157    parents: Vec<Hash>,
158    payload: Option<Payload>,
159    timestamp: u64,
160    creator: String,
161}
162
163impl NodeBuilder {
164    /// Create a new node builder.
165    pub fn new() -> Self {
166        NodeBuilder {
167            parents: Vec::new(),
168            payload: None,
169            timestamp: 0,
170            creator: String::new(),
171        }
172    }
173
174    /// Set the parent nodes.
175    pub fn with_parents(mut self, parents: Vec<Hash>) -> Self {
176        self.parents = parents;
177        self
178    }
179
180    /// Add a single parent node.
181    pub fn with_parent(mut self, parent: Hash) -> Self {
182        self.parents.push(parent);
183        self
184    }
185
186    /// Set the payload.
187    pub fn with_payload(mut self, payload: Payload) -> Self {
188        self.payload = Some(payload);
189        self
190    }
191
192    /// Set the logical timestamp.
193    pub fn with_timestamp(mut self, timestamp: u64) -> Self {
194        self.timestamp = timestamp;
195        self
196    }
197
198    /// Set the creator replica ID.
199    pub fn with_creator(mut self, creator: impl Into<String>) -> Self {
200        self.creator = creator.into();
201        self
202    }
203
204    /// Build the node, computing its CID.
205    pub fn build(self) -> MerkleNode {
206        let payload = self.payload.unwrap_or(Payload::Genesis);
207        let cid = MerkleNode::compute_cid(&self.parents, &payload, self.timestamp, &self.creator);
208
209        MerkleNode {
210            cid,
211            parents: self.parents,
212            payload,
213            timestamp: self.timestamp,
214            creator: self.creator,
215        }
216    }
217
218    /// Build a genesis node for a replica.
219    pub fn genesis(creator: impl Into<String>) -> MerkleNode {
220        NodeBuilder::new()
221            .with_payload(Payload::Genesis)
222            .with_timestamp(0)
223            .with_creator(creator)
224            .build()
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231
232    #[test]
233    fn test_genesis_node() {
234        let node = NodeBuilder::genesis("replica_1");
235        assert!(node.is_genesis());
236        assert!(node.parents.is_empty());
237        assert!(node.payload.is_genesis());
238        assert!(node.verify());
239    }
240
241    #[test]
242    fn test_delta_node() {
243        let genesis = NodeBuilder::genesis("replica_1");
244
245        let delta = NodeBuilder::new()
246            .with_parent(genesis.cid)
247            .with_payload(Payload::delta(vec![1, 2, 3]))
248            .with_timestamp(1)
249            .with_creator("replica_1")
250            .build();
251
252        assert!(!delta.is_genesis());
253        assert!(delta.has_parent(&genesis.cid));
254        assert!(delta.payload.is_delta());
255        assert!(delta.verify());
256    }
257
258    #[test]
259    fn test_cid_deterministic() {
260        let node1 = NodeBuilder::new()
261            .with_payload(Payload::delta(vec![1, 2, 3]))
262            .with_timestamp(42)
263            .with_creator("test")
264            .build();
265
266        let node2 = NodeBuilder::new()
267            .with_payload(Payload::delta(vec![1, 2, 3]))
268            .with_timestamp(42)
269            .with_creator("test")
270            .build();
271
272        assert_eq!(node1.cid, node2.cid);
273    }
274
275    #[test]
276    fn test_cid_changes_with_content() {
277        let node1 = NodeBuilder::new()
278            .with_payload(Payload::delta(vec![1, 2, 3]))
279            .with_timestamp(42)
280            .with_creator("test")
281            .build();
282
283        let node2 = NodeBuilder::new()
284            .with_payload(Payload::delta(vec![4, 5, 6]))
285            .with_timestamp(42)
286            .with_creator("test")
287            .build();
288
289        assert_ne!(node1.cid, node2.cid);
290    }
291
292    #[test]
293    fn test_concurrent_parents() {
294        let genesis = NodeBuilder::genesis("replica_1");
295
296        // Two concurrent branches
297        let branch_a = NodeBuilder::new()
298            .with_parent(genesis.cid)
299            .with_payload(Payload::delta(b"branch_a".to_vec()))
300            .with_timestamp(1)
301            .with_creator("replica_1")
302            .build();
303
304        let branch_b = NodeBuilder::new()
305            .with_parent(genesis.cid)
306            .with_payload(Payload::delta(b"branch_b".to_vec()))
307            .with_timestamp(1)
308            .with_creator("replica_2")
309            .build();
310
311        // Merge node with multiple parents
312        let merge = NodeBuilder::new()
313            .with_parents(vec![branch_a.cid, branch_b.cid])
314            .with_payload(Payload::delta(b"merge".to_vec()))
315            .with_timestamp(2)
316            .with_creator("replica_1")
317            .build();
318
319        assert_eq!(merge.parent_count(), 2);
320        assert!(merge.has_parent(&branch_a.cid));
321        assert!(merge.has_parent(&branch_b.cid));
322        assert!(merge.verify());
323    }
324
325    #[test]
326    fn test_snapshot_node() {
327        let genesis = NodeBuilder::genesis("replica_1");
328
329        let snapshot = NodeBuilder::new()
330            .with_parent(genesis.cid)
331            .with_payload(Payload::snapshot(b"full state".to_vec()))
332            .with_timestamp(100)
333            .with_creator("replica_1")
334            .build();
335
336        assert!(snapshot.payload.is_snapshot());
337        assert!(snapshot.verify());
338    }
339
340    #[test]
341    fn test_verify_tampered_node() {
342        let mut node = NodeBuilder::new()
343            .with_payload(Payload::delta(vec![1, 2, 3]))
344            .with_timestamp(42)
345            .with_creator("test")
346            .build();
347
348        // Tamper with the payload
349        node.payload = Payload::delta(vec![9, 9, 9]);
350
351        // Verification should fail
352        assert!(!node.verify());
353    }
354}
mdcs_merkle/node.rs

mdcs_merkle/
node.rs
