fips_core/protocol/
tree.rs

1//! TreeAnnounce message: spanning tree state propagation.
2
3use super::error::ProtocolError;
4use super::link::LinkMessageType;
5use crate::NodeAddr;
6use crate::tree::{CoordEntry, ParentDeclaration, TreeCoordinate, TreeError};
7use secp256k1::schnorr::Signature;
8
9/// Spanning tree announcement carrying parent declaration and ancestry.
10///
11/// Sent to peers to propagate tree state. The declaration proves the
12/// sender's parent selection; the ancestry provides path to root for
13/// routing decisions.
14#[derive(Clone, Debug)]
15pub struct TreeAnnounce {
16    /// The sender's parent declaration.
17    pub declaration: ParentDeclaration,
18    /// Full ancestry from sender to root.
19    pub ancestry: TreeCoordinate,
20}
21
22impl TreeAnnounce {
23    /// TreeAnnounce wire format version 1.
24    pub const VERSION_1: u8 = 0x01;
25
26    /// Minimum payload size (after msg_type stripped by dispatcher):
27    /// version(1) + sequence(8) + timestamp(8) + parent(16) + ancestry_count(2) + signature(64) = 99
28    const MIN_PAYLOAD_SIZE: usize = 99;
29
30    /// Create a new TreeAnnounce message.
31    pub fn new(declaration: ParentDeclaration, ancestry: TreeCoordinate) -> Self {
32        Self {
33            declaration,
34            ancestry,
35        }
36    }
37
38    /// Validate that the ancestry is structurally consistent with the signed
39    /// declaration.
40    ///
41    /// Expected properties:
42    /// - the first ancestry entry is the declaring node's `node_addr`
43    /// - a root declaration has exactly one ancestry entry
44    /// - a non-root declaration has at least two ancestry entries
45    /// - for a non-root declaration, the second ancestry entry matches `parent_id`
46    /// - the final ancestry entry is the advertised root
47    /// - the advertised root is the smallest `node_addr` in the ancestry
48    pub fn validate_semantics(&self) -> Result<(), TreeError> {
49        let entries = self.ancestry.entries();
50        let declared_node = *self.declaration.node_addr();
51        let declared_parent = *self.declaration.parent_id();
52
53        if entries[0].node_addr != declared_node {
54            return Err(TreeError::AncestryNodeMismatch {
55                declared: declared_node,
56                ancestry: entries[0].node_addr,
57            });
58        }
59
60        if self.declaration.is_root() {
61            if entries.len() != 1 {
62                return Err(TreeError::RootDeclarationMismatch);
63            }
64        } else {
65            let ancestry_parent = entries.get(1).ok_or(TreeError::AncestryTooShort)?.node_addr;
66            if ancestry_parent != declared_parent {
67                return Err(TreeError::AncestryParentMismatch {
68                    declared: declared_parent,
69                    ancestry: ancestry_parent,
70                });
71            }
72        }
73
74        let advertised_root = *self.ancestry.root_id();
75        let minimum = entries
76            .iter()
77            .map(|entry| entry.node_addr)
78            .min()
79            .expect("TreeCoordinate is never empty");
80        if advertised_root != minimum {
81            return Err(TreeError::AncestryRootNotMinimum {
82                advertised: advertised_root,
83                minimum,
84            });
85        }
86
87        Ok(())
88    }
89
90    /// Encode as link-layer plaintext (includes msg_type byte).
91    ///
92    /// The declaration must be signed. The encoded format is:
93    /// ```text
94    /// [0x10][version:1][sequence:8 LE][timestamp:8 LE][parent:16]
95    /// [ancestry_count:2 LE][entries:32×n][signature:64]
96    /// ```
97    pub fn encode(&self) -> Result<Vec<u8>, ProtocolError> {
98        let signature = self
99            .declaration
100            .signature()
101            .ok_or(ProtocolError::InvalidSignature)?;
102
103        let entries = self.ancestry.entries();
104        let ancestry_count = entries.len() as u16;
105        let size = 1 + Self::MIN_PAYLOAD_SIZE + entries.len() * CoordEntry::WIRE_SIZE;
106        let mut buf = Vec::with_capacity(size);
107
108        // msg_type
109        buf.push(LinkMessageType::TreeAnnounce.to_byte());
110        // version
111        buf.push(Self::VERSION_1);
112        // sequence (8 LE)
113        buf.extend_from_slice(&self.declaration.sequence().to_le_bytes());
114        // timestamp (8 LE)
115        buf.extend_from_slice(&self.declaration.timestamp().to_le_bytes());
116        // parent (16)
117        buf.extend_from_slice(self.declaration.parent_id().as_bytes());
118        // ancestry_count (2 LE)
119        buf.extend_from_slice(&ancestry_count.to_le_bytes());
120        // ancestry entries (32 bytes each)
121        for entry in entries {
122            buf.extend_from_slice(entry.node_addr.as_bytes()); // 16
123            buf.extend_from_slice(&entry.sequence.to_le_bytes()); // 8
124            buf.extend_from_slice(&entry.timestamp.to_le_bytes()); // 8
125        }
126        // outer signature (64)
127        buf.extend_from_slice(signature.as_ref());
128
129        Ok(buf)
130    }
131
132    /// Decode from link-layer payload (after msg_type byte stripped by dispatcher).
133    ///
134    /// The payload starts with the version byte.
135    pub fn decode(payload: &[u8]) -> Result<Self, ProtocolError> {
136        if payload.len() < Self::MIN_PAYLOAD_SIZE {
137            return Err(ProtocolError::MessageTooShort {
138                expected: Self::MIN_PAYLOAD_SIZE,
139                got: payload.len(),
140            });
141        }
142
143        let mut pos = 0;
144
145        // version
146        let version = payload[pos];
147        pos += 1;
148        if version != Self::VERSION_1 {
149            return Err(ProtocolError::UnsupportedVersion(version));
150        }
151
152        // sequence (8 LE)
153        let sequence = u64::from_le_bytes(
154            payload[pos..pos + 8]
155                .try_into()
156                .map_err(|_| ProtocolError::Malformed("bad sequence".into()))?,
157        );
158        pos += 8;
159
160        // timestamp (8 LE)
161        let timestamp = u64::from_le_bytes(
162            payload[pos..pos + 8]
163                .try_into()
164                .map_err(|_| ProtocolError::Malformed("bad timestamp".into()))?,
165        );
166        pos += 8;
167
168        // parent (16)
169        let parent = NodeAddr::from_bytes(
170            payload[pos..pos + 16]
171                .try_into()
172                .map_err(|_| ProtocolError::Malformed("bad parent".into()))?,
173        );
174        pos += 16;
175
176        // ancestry_count (2 LE)
177        let ancestry_count = u16::from_le_bytes(
178            payload[pos..pos + 2]
179                .try_into()
180                .map_err(|_| ProtocolError::Malformed("bad ancestry count".into()))?,
181        ) as usize;
182        pos += 2;
183
184        // Validate remaining length: entries + signature
185        let expected_remaining = ancestry_count * CoordEntry::WIRE_SIZE + 64;
186        if payload.len() - pos < expected_remaining {
187            return Err(ProtocolError::MessageTooShort {
188                expected: pos + expected_remaining,
189                got: payload.len(),
190            });
191        }
192
193        // ancestry entries (32 bytes each)
194        let mut entries = Vec::with_capacity(ancestry_count);
195        for _ in 0..ancestry_count {
196            let node_addr = NodeAddr::from_bytes(
197                payload[pos..pos + 16]
198                    .try_into()
199                    .map_err(|_| ProtocolError::Malformed("bad entry node_addr".into()))?,
200            );
201            pos += 16;
202            let entry_seq = u64::from_le_bytes(
203                payload[pos..pos + 8]
204                    .try_into()
205                    .map_err(|_| ProtocolError::Malformed("bad entry sequence".into()))?,
206            );
207            pos += 8;
208            let entry_ts = u64::from_le_bytes(
209                payload[pos..pos + 8]
210                    .try_into()
211                    .map_err(|_| ProtocolError::Malformed("bad entry timestamp".into()))?,
212            );
213            pos += 8;
214            entries.push(CoordEntry::new(node_addr, entry_seq, entry_ts));
215        }
216
217        // signature (64)
218        let sig_bytes: [u8; 64] = payload[pos..pos + 64]
219            .try_into()
220            .map_err(|_| ProtocolError::Malformed("bad signature".into()))?;
221        let signature =
222            Signature::from_slice(&sig_bytes).map_err(|_| ProtocolError::InvalidSignature)?;
223
224        // The first entry's node_addr is the declaring node
225        if entries.is_empty() {
226            return Err(ProtocolError::Malformed(
227                "ancestry must have at least one entry".into(),
228            ));
229        }
230        let node_addr = entries[0].node_addr;
231
232        let declaration =
233            ParentDeclaration::with_signature(node_addr, parent, sequence, timestamp, signature);
234
235        let ancestry = TreeCoordinate::new(entries)
236            .map_err(|e| ProtocolError::Malformed(format!("bad ancestry: {}", e)))?;
237
238        Ok(Self {
239            declaration,
240            ancestry,
241        })
242    }
243}
244
245#[cfg(test)]
246mod tests {
247    use super::*;
248
249    fn make_node_addr(val: u8) -> NodeAddr {
250        let mut bytes = [0u8; 16];
251        bytes[0] = val;
252        NodeAddr::from_bytes(bytes)
253    }
254
255    fn make_coords(ids: &[u8]) -> TreeCoordinate {
256        TreeCoordinate::from_addrs(ids.iter().map(|&v| make_node_addr(v)).collect()).unwrap()
257    }
258
259    #[test]
260    fn test_tree_announce() {
261        let node = make_node_addr(1);
262        let parent = make_node_addr(2);
263        let decl = ParentDeclaration::new(node, parent, 1, 1000);
264        let ancestry = make_coords(&[1, 2, 0]);
265
266        let announce = TreeAnnounce::new(decl, ancestry);
267
268        assert_eq!(announce.declaration.node_addr(), &node);
269        assert_eq!(announce.ancestry.depth(), 2);
270    }
271
272    #[test]
273    fn test_tree_announce_encode_decode_root() {
274        use crate::identity::Identity;
275
276        let identity = Identity::generate();
277        let node_addr = *identity.node_addr();
278
279        // Root declaration: parent == self
280        let mut decl = ParentDeclaration::new(node_addr, node_addr, 1, 5000);
281        decl.sign(&identity).unwrap();
282
283        // Root ancestry: just the root itself
284        let ancestry = TreeCoordinate::new(vec![CoordEntry::new(node_addr, 1, 5000)]).unwrap();
285
286        let announce = TreeAnnounce::new(decl, ancestry);
287        let encoded = announce.encode().unwrap();
288
289        // msg_type (1) + version (1) + seq (8) + ts (8) + parent (16) + count (2) + 1 entry (32) + sig (64) = 132
290        assert_eq!(encoded.len(), 132);
291        assert_eq!(encoded[0], 0x10); // LinkMessageType::TreeAnnounce
292
293        // Decode strips msg_type byte (as dispatcher does)
294        let decoded = TreeAnnounce::decode(&encoded[1..]).unwrap();
295
296        assert_eq!(decoded.declaration.node_addr(), &node_addr);
297        assert_eq!(decoded.declaration.parent_id(), &node_addr);
298        assert_eq!(decoded.declaration.sequence(), 1);
299        assert_eq!(decoded.declaration.timestamp(), 5000);
300        assert!(decoded.declaration.is_root());
301        assert!(decoded.declaration.is_signed());
302        assert_eq!(decoded.ancestry.depth(), 0); // root has depth 0
303        assert_eq!(decoded.ancestry.entries().len(), 1);
304        assert_eq!(decoded.ancestry.entries()[0].node_addr, node_addr);
305        assert_eq!(decoded.ancestry.entries()[0].sequence, 1);
306        assert_eq!(decoded.ancestry.entries()[0].timestamp, 5000);
307    }
308
309    #[test]
310    fn test_tree_announce_encode_decode_depth3() {
311        use crate::identity::Identity;
312
313        let identity = Identity::generate();
314        let node_addr = *identity.node_addr();
315        let parent = make_node_addr(2);
316        let grandparent = make_node_addr(3);
317        let root = make_node_addr(4);
318
319        let mut decl = ParentDeclaration::new(node_addr, parent, 5, 10000);
320        decl.sign(&identity).unwrap();
321
322        let ancestry = TreeCoordinate::new(vec![
323            CoordEntry::new(node_addr, 5, 10000),
324            CoordEntry::new(parent, 4, 9000),
325            CoordEntry::new(grandparent, 3, 8000),
326            CoordEntry::new(root, 2, 7000),
327        ])
328        .unwrap();
329
330        let announce = TreeAnnounce::new(decl, ancestry);
331        let encoded = announce.encode().unwrap();
332
333        // 1 + 99 + 4*32 = 228
334        assert_eq!(encoded.len(), 228);
335
336        let decoded = TreeAnnounce::decode(&encoded[1..]).unwrap();
337
338        assert_eq!(decoded.declaration.node_addr(), &node_addr);
339        assert_eq!(decoded.declaration.parent_id(), &parent);
340        assert_eq!(decoded.declaration.sequence(), 5);
341        assert_eq!(decoded.declaration.timestamp(), 10000);
342        assert!(!decoded.declaration.is_root());
343        assert_eq!(decoded.ancestry.depth(), 3);
344        assert_eq!(decoded.ancestry.entries().len(), 4);
345
346        // Verify all entries preserved
347        let entries = decoded.ancestry.entries();
348        assert_eq!(entries[0].node_addr, node_addr);
349        assert_eq!(entries[0].sequence, 5);
350        assert_eq!(entries[1].node_addr, parent);
351        assert_eq!(entries[1].sequence, 4);
352        assert_eq!(entries[2].node_addr, grandparent);
353        assert_eq!(entries[2].timestamp, 8000);
354        assert_eq!(entries[3].node_addr, root);
355        assert_eq!(entries[3].timestamp, 7000);
356
357        // Root ID is last entry
358        assert_eq!(decoded.ancestry.root_id(), &root);
359    }
360
361    #[test]
362    fn test_tree_announce_decode_unsupported_version() {
363        use crate::identity::Identity;
364
365        let identity = Identity::generate();
366        let node_addr = *identity.node_addr();
367
368        let mut decl = ParentDeclaration::new(node_addr, node_addr, 1, 1000);
369        decl.sign(&identity).unwrap();
370
371        let ancestry = TreeCoordinate::new(vec![CoordEntry::new(node_addr, 1, 1000)]).unwrap();
372        let announce = TreeAnnounce::new(decl, ancestry);
373        let mut encoded = announce.encode().unwrap();
374
375        // Corrupt version byte (byte index 1, after msg_type)
376        encoded[1] = 0xFF;
377
378        let result = TreeAnnounce::decode(&encoded[1..]);
379        assert!(matches!(
380            result,
381            Err(ProtocolError::UnsupportedVersion(0xFF))
382        ));
383    }
384
385    #[test]
386    fn test_tree_announce_decode_truncated() {
387        // Way too short
388        let result = TreeAnnounce::decode(&[0x01]);
389        assert!(matches!(
390            result,
391            Err(ProtocolError::MessageTooShort { expected: 99, .. })
392        ));
393
394        // Just under minimum (98 bytes)
395        let short = vec![0u8; 98];
396        let result = TreeAnnounce::decode(&short);
397        assert!(matches!(
398            result,
399            Err(ProtocolError::MessageTooShort { expected: 99, .. })
400        ));
401    }
402
403    #[test]
404    fn test_tree_announce_decode_ancestry_count_mismatch() {
405        use crate::identity::Identity;
406
407        let identity = Identity::generate();
408        let node_addr = *identity.node_addr();
409
410        let mut decl = ParentDeclaration::new(node_addr, node_addr, 1, 1000);
411        decl.sign(&identity).unwrap();
412
413        let ancestry = TreeCoordinate::new(vec![CoordEntry::new(node_addr, 1, 1000)]).unwrap();
414        let announce = TreeAnnounce::new(decl, ancestry);
415        let mut encoded = announce.encode().unwrap();
416
417        // The ancestry_count is at offset: 1 (msg_type) + 1 (version) + 8 (seq) + 8 (ts) + 16 (parent) = 34
418        // Set ancestry_count to 5 but we only have 1 entry's worth of data
419        encoded[34] = 5;
420        encoded[35] = 0;
421
422        let result = TreeAnnounce::decode(&encoded[1..]);
423        assert!(matches!(result, Err(ProtocolError::MessageTooShort { .. })));
424    }
425
426    #[test]
427    fn test_tree_announce_encode_unsigned_fails() {
428        let node = make_node_addr(1);
429        let decl = ParentDeclaration::new(node, node, 1, 1000);
430        let ancestry = make_coords(&[1, 0]);
431
432        let announce = TreeAnnounce::new(decl, ancestry);
433        let result = announce.encode();
434        assert!(matches!(result, Err(ProtocolError::InvalidSignature)));
435    }
436
437    /// Tests that a well-formed non-root ancestry is accepted.
438    #[test]
439    fn test_tree_announce_validate_semantics_accepts_valid_non_root() {
440        use crate::identity::Identity;
441
442        // Regenerate until the random identity's node_addr is numerically
443        // larger than both fixed parent (02:..) and root (01:..), so the
444        // root-minimum invariant holds deterministically.
445        let identity = loop {
446            let id = Identity::generate();
447            if id.node_addr().as_bytes()[0] > 1 {
448                break id;
449            }
450        };
451        let node_addr = *identity.node_addr();
452        let parent = make_node_addr(2);
453        let root = make_node_addr(1);
454
455        let mut decl = ParentDeclaration::new(node_addr, parent, 5, 1000);
456        decl.sign(&identity).unwrap();
457
458        let ancestry = TreeCoordinate::new(vec![
459            CoordEntry::new(node_addr, 5, 1000),
460            CoordEntry::new(parent, 4, 900),
461            CoordEntry::new(root, 3, 800),
462        ])
463        .unwrap();
464
465        let announce = TreeAnnounce::new(decl, ancestry);
466        assert!(announce.validate_semantics().is_ok());
467    }
468
469    /// Tests that an ancestry is rejected if the final node_addr is not the smallest entry in the path.
470    #[test]
471    fn test_tree_announce_validate_semantics_rejects_non_minimal_root() {
472        use crate::identity::Identity;
473
474        let identity = Identity::generate();
475        let node_addr = *identity.node_addr();
476        let smaller = make_node_addr(0);
477        let advertised_root = make_node_addr(1);
478
479        let mut decl = ParentDeclaration::new(node_addr, smaller, 5, 1000);
480        decl.sign(&identity).unwrap();
481
482        let ancestry = TreeCoordinate::new(vec![
483            CoordEntry::new(node_addr, 5, 1000),
484            CoordEntry::new(smaller, 4, 900),
485            CoordEntry::new(advertised_root, 3, 800),
486        ])
487        .unwrap();
488
489        let announce = TreeAnnounce::new(decl, ancestry);
490        assert!(matches!(
491            announce.validate_semantics(),
492            Err(TreeError::AncestryRootNotMinimum {
493                advertised,
494                minimum,
495            }) if advertised == advertised_root && minimum == smaller
496        ));
497    }
498
499    /// Tests that an ancestry is rejected if the first ancestry hop does not match the signed parent_id.
500    #[test]
501    fn test_tree_announce_validate_semantics_rejects_parent_mismatch() {
502        use crate::identity::Identity;
503
504        let identity = Identity::generate();
505        let node_addr = *identity.node_addr();
506        let declared_parent = make_node_addr(2);
507        let ancestry_parent = make_node_addr(3);
508
509        let mut decl = ParentDeclaration::new(node_addr, declared_parent, 5, 1000);
510        decl.sign(&identity).unwrap();
511
512        let ancestry = TreeCoordinate::new(vec![
513            CoordEntry::new(node_addr, 5, 1000),
514            CoordEntry::new(ancestry_parent, 4, 900),
515            CoordEntry::new(make_node_addr(1), 3, 800),
516        ])
517        .unwrap();
518
519        let announce = TreeAnnounce::new(decl, ancestry);
520        assert!(matches!(
521            announce.validate_semantics(),
522            Err(TreeError::AncestryParentMismatch {
523                declared,
524                ancestry,
525            }) if declared == declared_parent && ancestry == ancestry_parent
526        ));
527    }
528
529    /// Tests that an ancestry is rejected if the first path entry does not match the signed sender node_addr.
530    #[test]
531    fn test_tree_announce_validate_semantics_rejects_sender_mismatch() {
532        use crate::identity::Identity;
533
534        let identity = Identity::generate();
535        let node_addr = *identity.node_addr();
536        let ancestry_sender = make_node_addr(9);
537        let parent = make_node_addr(2);
538
539        let mut decl = ParentDeclaration::new(node_addr, parent, 5, 1000);
540        decl.sign(&identity).unwrap();
541
542        let ancestry = TreeCoordinate::new(vec![
543            CoordEntry::new(ancestry_sender, 5, 1000),
544            CoordEntry::new(parent, 4, 900),
545            CoordEntry::new(make_node_addr(1), 3, 800),
546        ])
547        .unwrap();
548
549        let announce = TreeAnnounce::new(decl, ancestry);
550        assert!(matches!(
551            announce.validate_semantics(),
552            Err(TreeError::AncestryNodeMismatch {
553                declared,
554                ancestry,
555            }) if declared == node_addr && ancestry == ancestry_sender
556        ));
557    }
558
559    /// Tests that a self-root declaration is rejected if its ancestry contains extra ancestors.
560    #[test]
561    fn test_tree_announce_validate_semantics_rejects_root_with_ancestors() {
562        use crate::identity::Identity;
563
564        let identity = Identity::generate();
565        let node_addr = *identity.node_addr();
566
567        let mut decl = ParentDeclaration::self_root(node_addr, 5, 1000);
568        decl.sign(&identity).unwrap();
569
570        let ancestry = TreeCoordinate::new(vec![
571            CoordEntry::new(node_addr, 5, 1000),
572            CoordEntry::new(make_node_addr(0), 4, 900),
573        ])
574        .unwrap();
575
576        let announce = TreeAnnounce::new(decl, ancestry);
577        assert!(matches!(
578            announce.validate_semantics(),
579            Err(TreeError::RootDeclarationMismatch)
580        ));
581    }
582}
fips_core/protocol/tree.rs

fips_core/protocol/
tree.rs
