Skip to main content

hyprstream_pds/
mst.rs

1//! Merkle Search Tree (MST) — the atproto repo's per-account record store.
2//!
3//! The MST (Auvolat & Taïani, SRDS 2019) is a binary-tree-of-blocks keyed by
4//! string record keys (`<collection>/<rkey>` paths — ONE tree per account repo
5//! spans all of its collections). Its defining
6//! property is that the **shape of the tree is a deterministic function of the
7//! key set** — independent of insertion order — so two hosts with the same
8//! records compute the same root CID. This is what makes the repo
9//! consensus-free: any host can rebuild the tree and verify a peer's root.
10//!
11//! # Structure (matches the atproto reference)
12//!
13//! Each MST node is a [`NodeData`] block encoded as DAG-CBOR:
14//!
15//! ```text
16//! NodeData {
17//!   l: Option<Cid>,                 // leftmost subtree (key space < first key)
18//!   e: [TreeEntry {                 // entries, in ascending key order
19//!     p: usize,                     // shared-prefix length with previous key
20//!     k: Vec<u8>,                   // remainder of this key (suffix after the prefix)
21//!     v: Cid,                       // the record this entry addresses
22//!     t: Option<Cid>,               // right subtree (keys in (this_key, next_key))
23//!   }]
24//! }
25//! ```
26//!
27//! A node lives at a **level** (height). The level of a key is the number of
28//! trailing zero bits in `sha256("<collection>/<rkey>")` — so roughly 1/2 of
29//! keys are level-0 leaves, 1/4 are level-1, etc. Insertion walks down the tree
30//! by level, splitting subtrees when a key's level matches the current node's.
31//!
32//! # CID
33//!
34//! Each node's CID is `CIDv1 dag-cbor` over its canonical DAG-CBOR bytes. The
35//! **MST root CID** is the commit's `data` field.
36
37use 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
46/// Full record key as carried in the MST: `<collection>/<rkey>`, e.g.
47/// `ai.hyprstream.model/3zztslq4be52u`. The MST orders by these UTF-8 bytes.
48fn 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
56/// Compute the MST level (height) of a record key: the number of trailing zero
57/// bits in `sha256(key)`, capped at 31 (avoids pathological deep trees).
58///
59/// This is the atproto convention — it spreads keys across levels so the tree
60/// stays balanced as a function of the key set, not insertion order.
61fn key_level(key: &str) -> u32 {
62    use sha2::{Digest, Sha256};
63    let digest = Sha256::digest(key.as_bytes());
64    // Count trailing zero bits across the 32-byte digest (big-endian bit order:
65    // the LAST bit of the LAST byte is the least-significant trailing zero).
66    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
81/// Compute the protocol MST layer for a public AT Protocol record key.
82///
83/// AT Protocol derives layers from the number of leading zero bits in the
84/// SHA-256 key hash, using two leading bits per layer. This is deliberately
85/// separate from the native tree's trailing-zero convention.
86fn 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// (key_level is private; tests that need it live in this module and see it directly.)
102
103// ── TreeEntry / NodeData (the on-the-wire DAG-CBOR shapes) ──────────────────
104
105/// One entry in an MST node.
106#[derive(Clone, Debug, Eq, PartialEq)]
107pub struct TreeEntry {
108    /// Prefix count: number of leading bytes this key shares with the previous
109    /// key at this level (0 for the first entry). Compression to keep nodes small.
110    pub p: usize,
111    /// Remainder of the key (suffix after the shared prefix), as UTF-8 bytes.
112    pub k: Vec<u8>,
113    /// CID of the record block this entry addresses.
114    pub v: Cid,
115    /// Right subtree: the subtree of keys strictly between this key and the
116    /// next entry's key, at a level one lower than this node. `None` if empty.
117    pub t: Option<Cid>,
118}
119
120/// An MST node — the unit addressed by a CID.
121#[derive(Clone, Debug, Eq, PartialEq)]
122pub struct NodeData {
123    /// Leftmost subtree (keys less than the first entry's key), one level lower.
124    /// `None` if empty.
125    pub l: Option<Cid>,
126    /// Entries, in ascending key order.
127    pub e: Vec<TreeEntry>,
128}
129
130impl NodeData {
131    /// Encode to canonical DAG-CBOR bytes and return its CIDv1 dag-cbor CID.
132    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    /// Public AT Protocol serialization. The existing native format remains
141    /// the default for already-signed artifacts.
142    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        // Keep the wire bytes tied to the value used for projection.  The
153        // public decoder is canonical today; retaining this explicit check
154        // prevents a future normalizer change from silently changing the MST
155        // node bytes and therefore its CID.
156        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    /// Public DAG-CBOR nodes are a frozen wire shape.  Dropping an unknown
170    /// field would produce a different canonical encoding and therefore a
171    /// different CID, so reject it before projecting into [`NodeData`].
172    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        // atproto node shape: { l: Option<Link>, e: [{p,k,v,t}, ...] }
185        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// ── The in-memory MST ───────────────────────────────────────────────────────
258
259/// An in-memory MST over an account repo's records (all collections, keyed by
260/// `<collection>/<rkey>`).
261///
262/// Internally this is a recursive structure of [`Node`]s, each at a `level`.
263/// The tree shape depends only on the (key → record-CID) map, not insertion
264/// order, so any host with the same records builds the same root.
265#[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    /// An empty MST root (level 0, no entries).
281    pub fn empty() -> Self {
282        Node {
283            level: 0,
284            l: None,
285            entries: Vec::new(),
286        }
287    }
288
289    /// Build an MST from a `key → record CID` map. The collection name is used
290    /// to form the full record keys (`<collection>/<rkey>`).
291    ///
292    /// The resulting tree shape is a pure function of the key set — independent
293    /// of insertion order — because each key's level (and thus its position in
294    /// the tree) is `trailing_zero_bits(sha256(key))`.
295    pub fn from_records(collection: &str, records: &BTreeMap<Tid, Cid>) -> Self {
296        // Sorted keys (BTreeMap over Tid already gives ascending rkey order; we
297        // form the full `<collection>/<rkey>` strings and build from there).
298        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    /// Build an MST from already-formed full record keys (`"<collection>/<rkey>"`)
306    /// to record CID.
307    ///
308    /// Unlike [`Self::from_records`] (single collection, keyed by [`Tid`]), this
309    /// accepts keys spanning *multiple* collections in one tree — the real
310    /// atproto shape (one MST per account repo, not per collection; a repo's
311    /// records live at keys like `ai.hyprstream.model/<rkey>` and
312    /// `ai.hyprstream.placement.node/<rkey>` side by side in the same tree).
313    /// A directory walker enumerates a collection's records by filtering
314    /// entries whose key starts with `"<collection>/"`.
315    pub fn from_keyed_records(records: &BTreeMap<String, Cid>) -> Self {
316        Self::from_keyed_records_with_level(records, key_level)
317    }
318
319    /// Build an MST using the public AT Protocol layer function. The native
320    /// [`Self::from_keyed_records`] constructor remains unchanged for native
321    /// artifacts; callers producing public roots should use this constructor.
322    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        // The root level is the maximum key level (so every key is at or below
335        // the root). Building top-down from here keeps subtrees well-formed.
336        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    /// Recursively build a subtree at `level` from the given sorted
341    /// `(key, cid)` list. Precondition: every key in `keys` has `key_level <= level`.
342    ///
343    /// Invariants:
344    /// - Keys with `key_level == level` become direct entries of this node.
345    /// - Runs of keys with `key_level < level` become left (`l`) / right (`t`)
346    ///   subtrees, each built at `level - 1`.
347    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            // (level == u32::MAX guard is unreachable in practice — key_level is
355            // capped at 31 — but defends against a future uncapped hasher.)
356            return node;
357        }
358
359        // Split `keys` into alternating low-level runs and level-`level` anchors.
360        // Walk the list, and whenever we hit an anchor, flush the low-level run
361        // preceding it: that run becomes the PREVIOUS entry's right subtree `t`,
362        // or the leftmost subtree `l` if there is no previous entry yet.
363        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                // Flush the low-level run [low_start, i) as a subtree.
368                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; // leading run → leftmost subtree
376                } else if let Some(last) = node.entries.last_mut() {
377                    // Low-level runs strictly between two anchors belong to the
378                    // earlier anchor's right child.
379                    last.right = subtree;
380                }
381                // Push this anchor as an entry (right subtree to be filled later).
382                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        // Trailing low-level run after the last anchor → that anchor's right subtree.
392        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                // No anchor at this level at all — the whole run is below level.
399                // Reachable only when the caller passed keys all strictly below
400                // `level`; re-root into the leftmost subtree at level-1.
401                node.l = subtree;
402            }
403        }
404        node
405    }
406
407    /// Serialize this subtree to a [`NodeData`] (resolving child CIDs recursively),
408    /// returning the [`NodeData`] and the list of all node blocks (for CAR export).
409    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        // Resolve left subtree first.
418        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        // Resolve entries (and their right subtrees).
425        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    /// The root CID of this MST (CIDv1 dag-cbor over the root node's bytes).
447    pub fn root_cid(&self) -> Cid {
448        let (data, _blocks) = self.to_node_data_with_blocks();
449        data.cid()
450    }
451
452    /// All node blocks in the tree (including the root), as `(cid, NodeData)`.
453    /// Useful for full-repo CAR export.
454    pub fn all_blocks(&self) -> Vec<(Cid, NodeData)> {
455        let (_data, blocks) = self.to_node_data_with_blocks();
456        blocks
457    }
458
459    /// Serialize this tree with public AT Protocol node ordering and CIDs.
460    pub fn to_node_data_with_blocks_atproto(&self) -> Result<(NodeData, Vec<(Cid, NodeData)>)> {
461        // A native Node may have been built with the native layer function.
462        // Rebuild from its complete key set before public serialization so the
463        // resulting topology follows the AT Protocol layer rule.
464        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    /// Build an inclusion proof whose node CIDs use public AT serialization.
530    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    /// Compute the MST path (inclusion proof) for `rkey`: the chain of
579    /// `(NodeData, entry_index)` pairs from the root down to the entry whose
580    /// key matches, plus the sibling-subtree CIDs needed to verify the chain.
581    ///
582    /// Returns `None` if the rkey is not present.
583    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        // Each step records THIS node's data plus where to descend next. The
592        // verifier walks the chain: step[0]'s node CID must equal the claimed
593        // root; each subsequent step's node CID must equal the pointer named by
594        // the previous step's descent hint.
595        let node_data = self.to_node_data_rec(&mut Vec::new());
596        // If this node has a left subtree and the target is below the first
597        // entry's key (or the node has no entries), the target lives in `l`.
598        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        // Find the matching entry, or the entry whose right subtree contains the target.
610        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            // Is target between this entry's key and the next entry's key (or end)?
616            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; // target falls in an empty gap
627            }
628        }
629        None
630    }
631}
632
633/// One step of an MST inclusion proof.
634#[derive(Clone, Debug)]
635pub enum ProofStep {
636    /// The target was found at `entry_index` in this node.
637    FoundAt(NodeData, usize),
638    /// The target is in the right subtree of `entry_index`; descend through it.
639    ThroughEntry(NodeData, usize),
640    /// The target is in the leftmost subtree; descend into it.
641    LeftSubtree(NodeData),
642}
643
644/// An MST inclusion proof for a single record.
645#[derive(Clone, Debug)]
646pub struct Proof {
647    /// Ordered steps from root to the matching entry.
648    pub path: Vec<ProofStep>,
649}
650
651impl Proof {
652    /// Verify this proof against a `root_cid` and the expected `record_cid`.
653    ///
654    /// Walks each step, recomputing each node's CID from its [`NodeData`] and
655    /// confirming it matches the parent step's named child pointer (or, for the
656    /// first step, the claimed `root_cid`). The terminal `FoundAt` step's entry
657    /// value must equal `record_cid`.
658    ///
659    /// Returns `Ok(())` on success. The caller already knows the target rkey
660    /// (they asked for it), so we don't reconstruct it from prefix-compression —
661    /// the value-CID check plus the CID chain is the load-bearing guarantee.
662    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    /// Verify an inclusion proof using public AT Protocol node serialization.
667    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; // CID the *current* node must have
677        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            // Recompute this node's CID and verify against the expectation.
686            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                // First step — must match the claimed root.
694                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; // terminal
706                }
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
742/// Length of the longest shared *byte* prefix between `prev` (optional) and `key`.
743fn 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        // Same key set, different BTreeMap construction — same root CID.
780        // (BTreeMap is already sorted, so this confirms determinism; the real
781        // insertion-order invariance is a consequence of the tree being a pure
782        // function of the key set, not insertion order.)
783        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            // Insert into b at disjoint microsecond offsets, then rebuild — the
789            // root depends only on the *keys*, so identical key sets must agree.
790            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        // Verify a proof exists and verifies for EVERY key (catches descent
825        // bugs across left-child, right-child, and terminal-FoundAt paths).
826        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        // A different record's CID must fail verification.
853        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        // A repo's MST spans multiple collections side by side — build one
863        // directly from full keys (no single `collection` argument) and confirm
864        // every entry's key + value round-trips through the node blocks.
865        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        // Walk all node blocks and collect every entry's (key, value) — cross
882        // check against the input map by reconstructing keys the same way the
883        // directory walker will (see hyprstream-discovery's placement_index).
884        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        // Public serialization must also rebuild a native tree's topology.
937        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        // A bogus root CID must fail.
1002        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}