1use std::collections::BTreeMap;
38
39use anyhow::{ensure, Result};
40
41use crate::atproto_cbor::AtprotoRecordKey;
42use crate::cid::Cid;
43use crate::dag_cbor::DagCbor;
44use crate::tid::Tid;
45
46fn record_key(collection: &str, rkey: Tid) -> String {
49 format!("{collection}/{rkey}")
50}
51
52fn public_record_key(collection: &str, rkey: &AtprotoRecordKey) -> String {
53 format!("{collection}/{}", rkey.as_str())
54}
55
56fn key_level(key: &str) -> u32 {
62 use sha2::{Digest, Sha256};
63 let digest = Sha256::digest(key.as_bytes());
64 let mut zeros = 0u32;
67 for &byte in digest.iter().rev() {
68 if byte == 0 {
69 zeros += 8;
70 if zeros >= 31 {
71 return 31;
72 }
73 } else {
74 zeros += byte.trailing_zeros();
75 break;
76 }
77 }
78 zeros.min(31)
79}
80
81fn atproto_key_level(key: &str) -> u32 {
87 use sha2::{Digest, Sha256};
88 let digest = Sha256::digest(key.as_bytes());
89 let mut leading = 0u32;
90 for &byte in digest.iter() {
91 if byte == 0 {
92 leading += 8;
93 } else {
94 leading += byte.leading_zeros();
95 break;
96 }
97 }
98 (leading / 2).min(31)
99}
100
101#[derive(Clone, Debug, Eq, PartialEq)]
107pub struct TreeEntry {
108 pub p: usize,
111 pub k: Vec<u8>,
113 pub v: Cid,
115 pub t: Option<Cid>,
118}
119
120#[derive(Clone, Debug, Eq, PartialEq)]
122pub struct NodeData {
123 pub l: Option<Cid>,
126 pub e: Vec<TreeEntry>,
128}
129
130impl NodeData {
131 pub fn encode(&self) -> Vec<u8> {
133 self.to_value().encode()
134 }
135
136 pub fn cid(&self) -> Cid {
137 Cid::from_dag_cbor(&self.encode())
138 }
139
140 pub fn encode_atproto(&self) -> Result<Vec<u8>> {
143 crate::atproto_cbor::encode(&self.to_value())
144 }
145
146 pub fn cid_atproto(&self) -> Result<Cid> {
147 Ok(Cid::from_dag_cbor(&self.encode_atproto()?))
148 }
149
150 pub fn from_atproto_dag_cbor(bytes: &[u8]) -> Result<Self> {
151 let value = crate::atproto_cbor::decode(bytes)?;
152 ensure!(
157 crate::atproto_cbor::encode(&value)? == bytes,
158 "ATProto MST bytes are not canonical"
159 );
160 Self::reject_unknown_fields(&value, &["l", "e"], "MST node")?;
161 if let Some(entries) = value.get("e") {
162 for entry in entries.as_list()? {
163 Self::reject_unknown_fields(entry, &["p", "k", "v", "t"], "MST entry")?;
164 }
165 }
166 Self::from_value(&value)
167 }
168
169 fn reject_unknown_fields(value: &DagCbor, allowed: &[&str], what: &str) -> Result<()> {
173 for (key, _) in value.as_map()? {
174 let key = match key {
175 DagCbor::Text(key) => key.as_str(),
176 _ => return Err(anyhow::anyhow!("{what} has a non-text field key")),
177 };
178 ensure!(allowed.contains(&key), "{what} has unknown field {key:?}");
179 }
180 Ok(())
181 }
182
183 pub fn to_value(&self) -> DagCbor {
184 let entries: Vec<DagCbor> = self
186 .e
187 .iter()
188 .map(|entry| {
189 DagCbor::str_map([
190 ("p", DagCbor::Unsigned(entry.p as u64)),
191 ("k", DagCbor::Bytes(entry.k.clone())),
192 ("v", DagCbor::Link(entry.v)),
193 (
194 "t",
195 match &entry.t {
196 Some(c) => DagCbor::Link(*c),
197 None => DagCbor::Null,
198 },
199 ),
200 ])
201 })
202 .collect();
203 DagCbor::str_map([
204 (
205 "l",
206 match &self.l {
207 Some(c) => DagCbor::Link(*c),
208 None => DagCbor::Null,
209 },
210 ),
211 ("e", DagCbor::List(entries)),
212 ])
213 }
214
215 pub fn from_value(value: &DagCbor) -> Result<Self> {
216 let l_val = value
217 .get("l")
218 .ok_or_else(|| anyhow::anyhow!("MST node missing 'l'"))?;
219 let l = if l_val.is_null() {
220 None
221 } else {
222 Some(*l_val.as_link()?)
223 };
224 let e_val = value
225 .get("e")
226 .ok_or_else(|| anyhow::anyhow!("MST node missing 'e'"))?;
227 let e_items = e_val.as_list()?;
228 let mut e = Vec::with_capacity(e_items.len());
229 for item in e_items {
230 let p = item
231 .get("p")
232 .ok_or_else(|| anyhow::anyhow!("entry missing 'p'"))?
233 .as_unsigned()? as usize;
234 let k = item
235 .get("k")
236 .ok_or_else(|| anyhow::anyhow!("entry missing 'k'"))?
237 .as_bytes()?
238 .to_vec();
239 let v = *item
240 .get("v")
241 .ok_or_else(|| anyhow::anyhow!("entry missing 'v'"))?
242 .as_link()?;
243 let t_val = item
244 .get("t")
245 .ok_or_else(|| anyhow::anyhow!("entry missing 't'"))?;
246 let t = if t_val.is_null() {
247 None
248 } else {
249 Some(*t_val.as_link()?)
250 };
251 e.push(TreeEntry { p, k, v, t });
252 }
253 Ok(NodeData { l, e })
254 }
255}
256
257#[derive(Clone, Debug, Eq, PartialEq)]
266pub struct Node {
267 pub level: u32,
268 pub l: Option<Box<Node>>,
269 pub entries: Vec<NodeEntry>,
270}
271
272#[derive(Clone, Debug, Eq, PartialEq)]
273pub struct NodeEntry {
274 pub key: String,
275 pub value: Cid,
276 pub right: Option<Box<Node>>,
277}
278
279impl Node {
280 pub fn empty() -> Self {
282 Node {
283 level: 0,
284 l: None,
285 entries: Vec::new(),
286 }
287 }
288
289 pub fn from_records(collection: &str, records: &BTreeMap<Tid, Cid>) -> Self {
296 let keyed: BTreeMap<String, Cid> = records
299 .iter()
300 .map(|(tid, cid)| (record_key(collection, *tid), *cid))
301 .collect();
302 Self::from_keyed_records(&keyed)
303 }
304
305 pub fn from_keyed_records(records: &BTreeMap<String, Cid>) -> Self {
316 Self::from_keyed_records_with_level(records, key_level)
317 }
318
319 pub fn from_keyed_records_atproto(records: &BTreeMap<String, Cid>) -> Self {
323 Self::from_keyed_records_with_level(records, atproto_key_level)
324 }
325
326 fn from_keyed_records_with_level(
327 records: &BTreeMap<String, Cid>,
328 level_fn: fn(&str) -> u32,
329 ) -> Self {
330 let keys: Vec<(String, Cid)> = records.iter().map(|(k, v)| (k.clone(), *v)).collect();
331 if keys.is_empty() {
332 return Node::empty();
333 }
334 let max_level = keys.iter().map(|(k, _)| level_fn(k)).max().unwrap_or(0);
337 Self::build_subtree(max_level, &keys, level_fn)
338 }
339
340 fn build_subtree(level: u32, keys: &[(String, Cid)], level_fn: fn(&str) -> u32) -> Self {
348 let mut node = Node {
349 level,
350 l: None,
351 entries: Vec::new(),
352 };
353 if keys.is_empty() || level == u32::MAX {
354 return node;
357 }
358
359 let mut have_anchor = false;
364 let mut low_start: usize = 0;
365 for (i, (k, _)) in keys.iter().enumerate() {
366 if level_fn(k) == level {
367 let run = &keys[low_start..i];
369 let subtree = if run.is_empty() {
370 None
371 } else {
372 Some(Box::new(Self::build_subtree(level - 1, run, level_fn)))
373 };
374 if !have_anchor {
375 node.l = subtree; } else if let Some(last) = node.entries.last_mut() {
377 last.right = subtree;
380 }
381 node.entries.push(NodeEntry {
383 key: keys[i].0.clone(),
384 value: keys[i].1,
385 right: None,
386 });
387 have_anchor = true;
388 low_start = i + 1;
389 }
390 }
391 let trailing = &keys[low_start..];
393 if !trailing.is_empty() {
394 let subtree = Some(Box::new(Self::build_subtree(level - 1, trailing, level_fn)));
395 if let Some(last) = node.entries.last_mut() {
396 last.right = subtree;
397 } else {
398 node.l = subtree;
402 }
403 }
404 node
405 }
406
407 pub fn to_node_data_with_blocks(&self) -> (NodeData, Vec<(Cid, NodeData)>) {
410 let mut blocks: Vec<(Cid, NodeData)> = Vec::new();
411 let data = self.to_node_data_rec(&mut blocks);
412 blocks.push((data.cid(), data.clone()));
413 (data, blocks)
414 }
415
416 fn to_node_data_rec(&self, blocks: &mut Vec<(Cid, NodeData)>) -> NodeData {
417 let l = self.l.as_ref().map(|child| {
419 let child_data = child.to_node_data_rec(blocks);
420 let cid = child_data.cid();
421 blocks.push((cid, child_data));
422 cid
423 });
424 let mut entries = Vec::with_capacity(self.entries.len());
426 for (idx, entry) in self.entries.iter().enumerate() {
427 let p = shared_prefix_len(
428 self.entries
429 .get(idx.wrapping_sub(1))
430 .map(|e| e.key.as_str()),
431 &entry.key,
432 );
433 let k = entry.key.as_bytes()[p..].to_vec();
434 let v = entry.value;
435 let t = entry.right.as_ref().map(|child| {
436 let child_data = child.to_node_data_rec(blocks);
437 let cid = child_data.cid();
438 blocks.push((cid, child_data));
439 cid
440 });
441 entries.push(TreeEntry { p, k, v, t });
442 }
443 NodeData { l, e: entries }
444 }
445
446 pub fn root_cid(&self) -> Cid {
448 let (data, _blocks) = self.to_node_data_with_blocks();
449 data.cid()
450 }
451
452 pub fn all_blocks(&self) -> Vec<(Cid, NodeData)> {
455 let (_data, blocks) = self.to_node_data_with_blocks();
456 blocks
457 }
458
459 pub fn to_node_data_with_blocks_atproto(&self) -> Result<(NodeData, Vec<(Cid, NodeData)>)> {
461 let mut records = BTreeMap::new();
465 self.collect_keyed_records(&mut records);
466 Self::from_keyed_records_atproto(&records).to_node_data_with_blocks_atproto_current()
467 }
468
469 fn to_node_data_with_blocks_atproto_current(&self) -> Result<(NodeData, Vec<(Cid, NodeData)>)> {
470 let mut blocks = Vec::new();
471 let data = self.to_node_data_atproto_rec(&mut blocks)?;
472 let cid = data.cid_atproto()?;
473 blocks.push((cid, data.clone()));
474 Ok((data, blocks))
475 }
476
477 fn collect_keyed_records(&self, records: &mut BTreeMap<String, Cid>) {
478 if let Some(left) = &self.l {
479 left.collect_keyed_records(records);
480 }
481 for entry in &self.entries {
482 records.insert(entry.key.clone(), entry.value);
483 if let Some(right) = &entry.right {
484 right.collect_keyed_records(records);
485 }
486 }
487 }
488
489 fn to_node_data_atproto_rec(&self, blocks: &mut Vec<(Cid, NodeData)>) -> Result<NodeData> {
490 let l = self
491 .l
492 .as_ref()
493 .map(|child| -> Result<Cid> {
494 let child_data = child.to_node_data_atproto_rec(blocks)?;
495 let cid = child_data.cid_atproto()?;
496 blocks.push((cid, child_data));
497 Ok(cid)
498 })
499 .transpose()?;
500 let mut entries = Vec::with_capacity(self.entries.len());
501 for (idx, entry) in self.entries.iter().enumerate() {
502 let p = shared_prefix_len(
503 self.entries
504 .get(idx.wrapping_sub(1))
505 .map(|e| e.key.as_str()),
506 &entry.key,
507 );
508 let k = entry.key.as_bytes()[p..].to_vec();
509 let t = entry
510 .right
511 .as_ref()
512 .map(|child| -> Result<Cid> {
513 let child_data = child.to_node_data_atproto_rec(blocks)?;
514 let cid = child_data.cid_atproto()?;
515 blocks.push((cid, child_data));
516 Ok(cid)
517 })
518 .transpose()?;
519 entries.push(TreeEntry {
520 p,
521 k,
522 v: entry.value,
523 t,
524 });
525 }
526 Ok(NodeData { l, e: entries })
527 }
528
529 pub fn proof_atproto<K>(&self, collection: &str, rkey: K) -> Option<Proof>
531 where
532 K: Into<AtprotoRecordKey>,
533 {
534 let rkey: AtprotoRecordKey = rkey.into();
535 let target = public_record_key(collection, &rkey);
536 let mut records = BTreeMap::new();
537 self.collect_keyed_records(&mut records);
538 let tree = Self::from_keyed_records_atproto(&records);
539 let mut path = Vec::new();
540 tree.proof_rec_atproto(&target, &mut path).ok()?;
541 Some(Proof { path })
542 }
543
544 fn proof_rec_atproto(&self, target: &str, path: &mut Vec<ProofStep>) -> Result<()> {
545 let node_data = self.to_node_data_atproto_rec(&mut Vec::new())?;
546 if let Some(left) = &self.l {
547 let below_first = self
548 .entries
549 .first()
550 .map(|e| target < e.key.as_str())
551 .unwrap_or(true);
552 if below_first {
553 path.push(ProofStep::LeftSubtree(node_data));
554 return left.proof_rec_atproto(target, path);
555 }
556 }
557 for (i, entry) in self.entries.iter().enumerate() {
558 if entry.key == target {
559 path.push(ProofStep::FoundAt(node_data, i));
560 return Ok(());
561 }
562 let next_key = self.entries.get(i + 1).map(|e| e.key.as_str());
563 let in_range = match next_key {
564 Some(nk) => entry.key.as_str() < target && target < nk,
565 None => entry.key.as_str() < target,
566 };
567 if in_range {
568 if let Some(right) = &entry.right {
569 path.push(ProofStep::ThroughEntry(node_data, i));
570 return right.proof_rec_atproto(target, path);
571 }
572 return Err(anyhow::anyhow!("target is not present"));
573 }
574 }
575 Err(anyhow::anyhow!("target is not present"))
576 }
577
578 pub fn proof(&self, collection: &str, rkey: &Tid) -> Option<Proof> {
584 let target = record_key(collection, *rkey);
585 let mut path = Vec::new();
586 self.proof_rec(&target, &mut path)?;
587 Some(Proof { path })
588 }
589
590 fn proof_rec(&self, target: &str, path: &mut Vec<ProofStep>) -> Option<()> {
591 let node_data = self.to_node_data_rec(&mut Vec::new());
596 if let Some(left) = &self.l {
599 let below_first = self
600 .entries
601 .first()
602 .map(|e| target < e.key.as_str())
603 .unwrap_or(true);
604 if below_first {
605 path.push(ProofStep::LeftSubtree(node_data));
606 return left.proof_rec(target, path);
607 }
608 }
609 for (i, entry) in self.entries.iter().enumerate() {
611 if entry.key == target {
612 path.push(ProofStep::FoundAt(node_data, i));
613 return Some(());
614 }
615 let next_key = self.entries.get(i + 1).map(|e| e.key.as_str());
617 let in_range = match next_key {
618 Some(nk) => entry.key.as_str() < target && target < nk,
619 None => entry.key.as_str() < target,
620 };
621 if in_range {
622 if let Some(right) = &entry.right {
623 path.push(ProofStep::ThroughEntry(node_data, i));
624 return right.proof_rec(target, path);
625 }
626 return None; }
628 }
629 None
630 }
631}
632
633#[derive(Clone, Debug)]
635pub enum ProofStep {
636 FoundAt(NodeData, usize),
638 ThroughEntry(NodeData, usize),
640 LeftSubtree(NodeData),
642}
643
644#[derive(Clone, Debug)]
646pub struct Proof {
647 pub path: Vec<ProofStep>,
649}
650
651impl Proof {
652 pub fn verify(&self, root_cid: &Cid, record_cid: &Cid) -> Result<()> {
663 self.verify_with(root_cid, record_cid, |data| Ok(data.cid()))
664 }
665
666 pub fn verify_atproto(&self, root_cid: &Cid, record_cid: &Cid) -> Result<()> {
668 self.verify_with(root_cid, record_cid, NodeData::cid_atproto)
669 }
670
671 fn verify_with<F>(&self, root_cid: &Cid, record_cid: &Cid, cid_for: F) -> Result<()>
672 where
673 F: Fn(&NodeData) -> Result<Cid>,
674 {
675 ensure!(!self.path.is_empty(), "empty MST proof");
676 let mut expected_cid: Option<Cid> = None; let mut found_value: Option<Cid> = None;
678
679 for (idx, step) in self.path.iter().enumerate() {
680 let (data, entry_hint): (&NodeData, ProofKind) = match step {
681 ProofStep::FoundAt(d, i) => (d, ProofKind::Found(*i)),
682 ProofStep::ThroughEntry(d, i) => (d, ProofKind::Through(*i)),
683 ProofStep::LeftSubtree(d) => (d, ProofKind::Left),
684 };
685 let node_cid = cid_for(data)?;
687 if let Some(ref want) = expected_cid {
688 ensure!(
689 node_cid == *want,
690 "MST proof: node CID mismatch at step {idx} (expected {want}, got {node_cid})"
691 );
692 } else {
693 ensure!(
695 node_cid == *root_cid,
696 "MST proof: root CID mismatch (expected {root_cid}, got {node_cid})"
697 );
698 }
699 match entry_hint {
700 ProofKind::Found(i) => {
701 let entry = data.e.get(i).ok_or_else(|| {
702 anyhow::anyhow!("MST proof: entry index {i} out of range")
703 })?;
704 found_value = Some(entry.v);
705 expected_cid = None; }
707 ProofKind::Through(i) => {
708 let entry = data.e.get(i).ok_or_else(|| {
709 anyhow::anyhow!("MST proof: entry index {i} out of range")
710 })?;
711 let t = entry.t.ok_or_else(|| {
712 anyhow::anyhow!("MST proof: descent expects a right subtree")
713 })?;
714 expected_cid = Some(t);
715 }
716 ProofKind::Left => {
717 let l = data.l.ok_or_else(|| {
718 anyhow::anyhow!("MST proof: descent expects a left subtree")
719 })?;
720 expected_cid = Some(l);
721 }
722 }
723 }
724
725 let value =
726 found_value.ok_or_else(|| anyhow::anyhow!("MST proof: no terminal FoundAt step"))?;
727 ensure!(
728 value == *record_cid,
729 "MST proof: entry value {value} does not match record CID {record_cid}"
730 );
731 Ok(())
732 }
733}
734
735#[derive(Clone, Copy)]
736enum ProofKind {
737 Found(usize),
738 Through(usize),
739 Left,
740}
741
742fn shared_prefix_len(prev: Option<&str>, key: &str) -> usize {
744 match prev {
745 None => 0,
746 Some(p) => p
747 .bytes()
748 .zip(key.bytes())
749 .take_while(|(a, b)| a == b)
750 .count(),
751 }
752}
753
754#[cfg(test)]
755mod tests {
756 #![allow(
757 clippy::unwrap_used,
758 clippy::expect_used,
759 clippy::indexing_slicing,
760 clippy::panic
761 )]
762 use super::*;
763 use crate::record::ModelRecord;
764 use crate::tid::Tid;
765
766 fn make_record(i: u64) -> (Tid, ModelRecord) {
767 let tid = Tid::from_micros(1_700_000_000_000_000 + i, i as u16);
768 let rec = ModelRecord::new(
769 "at://did:web:alice.example.com",
770 format!("bafyreiexampleoid{i:020}"),
771 "2026-06-23T12:34:56.789Z",
772 )
773 .expect("record");
774 (tid, rec)
775 }
776
777 #[test]
778 fn mst_root_independent_of_insertion_order() {
779 let mut a = BTreeMap::new();
784 let mut b = BTreeMap::new();
785 for i in 0..6 {
786 let (tid, rec) = make_record(i);
787 a.insert(tid, rec.cid());
788 b.insert(tid, rec.cid());
791 }
792 let tree_a = Node::from_records(crate::record::COLLECTION_NSID, &a);
793 let tree_b = Node::from_records(crate::record::COLLECTION_NSID, &b);
794 assert_eq!(
795 tree_a.root_cid(),
796 tree_b.root_cid(),
797 "MST root must be insertion-order-independent"
798 );
799 }
800
801 #[test]
802 fn mst_add_record_changes_root() {
803 let mut recs = BTreeMap::new();
804 let (t0, r0) = make_record(0);
805 recs.insert(t0, r0.cid());
806 let root0 = Node::from_records(crate::record::COLLECTION_NSID, &recs).root_cid();
807
808 let (t1, r1) = make_record(1);
809 recs.insert(t1, r1.cid());
810 let root1 = Node::from_records(crate::record::COLLECTION_NSID, &recs).root_cid();
811 assert_ne!(root0, root1, "adding a record must change the root CID");
812 }
813
814 #[test]
815 fn mst_proof_round_trip() {
816 let mut recs = BTreeMap::new();
817 for i in 0..8 {
818 let (tid, rec) = make_record(i);
819 recs.insert(tid, rec.cid());
820 }
821 let tree = Node::from_records(crate::record::COLLECTION_NSID, &recs);
822 let root = tree.root_cid();
823
824 for (k, target_tid) in recs.keys().enumerate() {
827 let target_cid = recs.get(target_tid).copied().expect("cid");
828 let proof = match tree.proof(crate::record::COLLECTION_NSID, target_tid) {
829 Some(p) => p,
830 None => {
831 panic!("no proof for key {k} (tid={target_tid})");
832 }
833 };
834 proof.verify(&root, &target_cid).expect("proof verifies");
835 }
836 }
837
838 #[test]
839 fn mst_proof_detects_wrong_record() {
840 let mut recs = BTreeMap::new();
841 for i in 0..4 {
842 let (tid, rec) = make_record(i);
843 recs.insert(tid, rec.cid());
844 }
845 let tree = Node::from_records(crate::record::COLLECTION_NSID, &recs);
846 let root = tree.root_cid();
847 let target_tid = recs.keys().next().copied().expect("key");
848 let proof = tree
849 .proof(crate::record::COLLECTION_NSID, &target_tid)
850 .expect("proof");
851
852 let wrong = make_record(99).1.cid();
854 assert!(
855 proof.verify(&root, &wrong).is_err(),
856 "proof must reject a wrong record"
857 );
858 }
859
860 #[test]
861 fn mst_from_keyed_records_mixes_collections() {
862 let mut keyed: BTreeMap<String, Cid> = BTreeMap::new();
866 for i in 0..4u64 {
867 let (tid, rec) = make_record(i);
868 keyed.insert(
869 format!("{}/{}", crate::record::COLLECTION_NSID, tid.encode()),
870 rec.cid(),
871 );
872 }
873 for i in 0..3u64 {
874 let cid = Cid::from_dag_cbor(format!("placement-node-{i}").as_bytes());
875 keyed.insert(format!("ai.hyprstream.placement.node/synthetic-{i}"), cid);
876 }
877 let tree = Node::from_keyed_records(&keyed);
878 let (root_data, blocks) = tree.to_node_data_with_blocks();
879 assert_eq!(root_data.cid(), tree.root_cid());
880
881 let block_map: BTreeMap<Cid, NodeData> = blocks.into_iter().collect();
885 let mut found: BTreeMap<String, Cid> = BTreeMap::new();
886 fn walk(cid: Cid, blocks: &BTreeMap<Cid, NodeData>, out: &mut BTreeMap<String, Cid>) {
887 let data = blocks.get(&cid).expect("block present");
888 if let Some(l) = data.l {
889 walk(l, blocks, out);
890 }
891 let mut prev: Option<String> = None;
892 for entry in &data.e {
893 let key = match &prev {
894 Some(p) => {
895 let take = entry.p.min(p.len());
896 let mut full = p.as_bytes()[..take].to_vec();
897 full.extend_from_slice(&entry.k);
898 String::from_utf8(full).expect("utf8 key")
899 }
900 None => String::from_utf8(entry.k.clone()).expect("utf8 key"),
901 };
902 out.insert(key.clone(), entry.v);
903 prev = Some(key);
904 if let Some(t) = entry.t {
905 walk(t, blocks, out);
906 }
907 }
908 }
909 walk(tree.root_cid(), &block_map, &mut found);
910 assert_eq!(
911 found, keyed,
912 "walked entries must match the input key set exactly"
913 );
914 }
915
916 #[test]
917 fn public_mst_uses_protocol_layer_function() {
918 let keyed: BTreeMap<String, Cid> = (1..=32)
919 .map(|i| {
920 (
921 format!("app.bsky.feed.post/{i:013}"),
922 Cid::from_dag_cbor(format!("record-{i}").as_bytes()),
923 )
924 })
925 .collect();
926 let native = Node::from_keyed_records(&keyed);
927 let public = Node::from_keyed_records_atproto(&keyed);
928 let expected_level = keyed
929 .keys()
930 .map(|key| atproto_key_level(key))
931 .max()
932 .unwrap_or(0);
933 assert_eq!(public.level, expected_level);
934 assert_ne!(native.level, public.level);
935
936 let (serialized, _) = native.to_node_data_with_blocks_atproto().unwrap();
938 let (expected, _) = public.to_node_data_with_blocks_atproto_current().unwrap();
939 assert_eq!(serialized, expected);
940 }
941
942 #[test]
943 fn public_mst_rejects_unknown_node_fields() {
944 let value = DagCbor::str_map([
945 ("e", DagCbor::List(Vec::new())),
946 ("l", DagCbor::Null),
947 ("future", DagCbor::Text("must-not-be-dropped".to_owned())),
948 ]);
949 let bytes = crate::atproto_cbor::encode(&value).expect("encode public node");
950 let error = NodeData::from_atproto_dag_cbor(&bytes).expect_err("unknown node field");
951 assert!(error.to_string().contains("unknown field"));
952 }
953
954 #[test]
955 fn public_mst_rejects_unknown_entry_fields() {
956 let cid = Cid::from_dag_cbor(b"record");
957 let value = DagCbor::str_map([
958 ("l", DagCbor::Null),
959 (
960 "e",
961 DagCbor::List(vec![DagCbor::str_map([
962 ("p", DagCbor::Unsigned(0)),
963 ("k", DagCbor::Bytes(b"app.bsky.feed.post/1".to_vec())),
964 ("v", DagCbor::Link(cid)),
965 ("t", DagCbor::Null),
966 ("future", DagCbor::Bool(true)),
967 ])]),
968 ),
969 ]);
970 let bytes = crate::atproto_cbor::encode(&value).expect("encode public node");
971 let error = NodeData::from_atproto_dag_cbor(&bytes).expect_err("unknown entry field");
972 assert!(error.to_string().contains("unknown field"));
973 }
974
975 #[test]
976 fn public_mst_preserves_canonical_bytes_on_decode() {
977 let value = DagCbor::str_map([("l", DagCbor::Null), ("e", DagCbor::List(Vec::new()))]);
978 let bytes = crate::atproto_cbor::encode(&value).expect("encode public node");
979 let node = NodeData::from_atproto_dag_cbor(&bytes).expect("decode public node");
980 assert_eq!(
981 crate::atproto_cbor::encode(&node.to_value()).expect("re-encode public node"),
982 bytes,
983 "public MST decode must preserve canonical bytes and CID"
984 );
985 }
986
987 #[test]
988 fn mst_proof_detects_tampered_root() {
989 let mut recs = BTreeMap::new();
990 for i in 0..4 {
991 let (tid, rec) = make_record(i);
992 recs.insert(tid, rec.cid());
993 }
994 let tree = Node::from_records(crate::record::COLLECTION_NSID, &recs);
995 let target_tid = recs.keys().next().copied().expect("key");
996 let target_cid = recs.get(&target_tid).copied().expect("cid");
997 let proof = tree
998 .proof(crate::record::COLLECTION_NSID, &target_tid)
999 .expect("proof");
1000
1001 let bogus = Cid::from_dag_cbor(b"not the root");
1003 assert!(
1004 proof.verify(&bogus, &target_cid).is_err(),
1005 "proof must reject a tampered root"
1006 );
1007 }
1008}