Skip to main content

hyprstream_discovery/
placement_index.rs

1//! P1 placement directory — record ingestion + in-process index (#524).
2//!
3//! Day-1 ingestion is **polled `RecordResolver` reads**, not a firehose/moq_event
4//! tail (that's explicitly out of scope — a day-2 ticket). Given a node DID, we
5//! call [`crate::RecordResolver::resolve_repo`], parse the returned CARv1 blob
6//! (`hyprstream_pds::car::parse_car_v1`), walk the repo's MST from the commit's
7//! `data` root, and decode every `ai.hyprstream.placement.{node,workload,group,
8//! groupItem}` record we find into an in-process index.
9//!
10//! # Trust posture — verified-by-construction ingest (#932)
11//!
12//! Membership is becoming a load-bearing input (scheduler capacity partitions
13//! today; group ledger / spend authorization tomorrow — #924/#925), so the
14//! index no longer trusts an ingested record graph merely because a resolver
15//! handed it over. Ingest is **verified by construction**: the resolver must
16//! provide the DID's currently-published `#atproto` verification slots
17//! ([`RecordResolver::resolve_verifying_keys`]), [`PlacementIndex::ingest_did`]
18//! verifies the repo CAR's commit signature against the bounded live set, and missing key material
19//! fails closed. Ingest also **content-binds every CAR block to its declared CID**.
20//! The commit block, each MST node, and each record block have their CID recomputed from their bytes and
21//! checked against the CID the CAR / parent declared for them (mirroring
22//! `hyprstream_pds::mst::Proof::verify`) — *before* any record enters the
23//! index. The signature alone is not sufficient: `Commit::verify` only signs
24//! the commit's own bytes (which name the MST root CID), so without per-block
25//! CID binding an attacker could replay a genuine signed commit with
26//! substituted MST-node/record blocks and forge membership; the content-bind
27//! check closes that. A repo whose commit signature fails verification, whose
28//! `commit.did` is not the requested DID, or whose any block's recomputed CID
29//! ≠ its declared CID is refused — it cannot reach the derived indices, so it
30//! cannot produce membership or any other fact derived from
31//! [`PlacementIndex::is_member`]. This makes verification a property of the
32//! index itself, not a caller obligation.
33//!
34//! `Ok(None)` is never permission to skip authentication. A foreign DID whose
35//! did:web HTTPS / did:plc document cannot yet be resolved is rejected until
36//! that resolution path is wired (tracked with #1123). This keeps the placement
37//! trust boundary fail closed.
38//!
39//! # Group membership — bidirectional consent
40//!
41//! A node is *effectively* a member of a group only when **both** sides agree:
42//! the group owner published a `GroupItemRecord{group, subject}` naming the
43//! node, **and** the node's own `NodeRecord.groups` lists that group's at-uri
44//! (explicit node-side consent). Neither claim alone is membership — see
45//! [`PlacementIndex::is_member`].
46//!
47//! Group membership is exposed to `queryCandidates`' label-selector matching as
48//! a **synthetic label**, not a schema change: for every group a node is an
49//! effective member of, the index adds a label `("group/<group-at-uri>", "true")`
50//! to that node's effective label set (see [`PlacementIndex::effective_labels`]).
51//! Each group gets its own unique label *key* (rather than several `("group",
52//! X)` pairs under one shared key) because [`crate::scheduling::LabelSelector`]
53//! looks up the *first* entry matching a key (the k8s label model: one value per
54//! key) — multiple same-keyed pairs would only ever let the first one be
55//! evaluated, silently breaking multi-group membership. A caller checks
56//! membership in group `G` with `LabelSelector::new(format!("group/{G}"),
57//! SelectorOp::Exists, vec![])`.
58
59use std::collections::{HashMap, HashSet};
60
61use anyhow::{anyhow, ensure, Result};
62use parking_lot::RwLock;
63
64use hyprstream_pds::car::parse_car_v1;
65use hyprstream_pds::cid::Cid;
66use hyprstream_pds::commit::Commit;
67use hyprstream_pds::dag_cbor::DagCbor;
68use hyprstream_pds::mst::NodeData;
69use hyprstream_pds::placement::{group, group_item, node, workload};
70use hyprstream_pds::placement::{GroupItemRecord, GroupRecord, NodeRecord, WorkloadRecord};
71
72use crate::RecordResolver;
73
74/// One node's durable (non-volatile) placement facts, decoded from its
75/// `ai.hyprstream.placement.node` record.
76#[derive(Debug, Clone, Default)]
77pub struct NodeFacts {
78    /// at-uri of the `NodeRecord` itself (`at://<did>/ai.hyprstream.placement.node/<rkey>`).
79    pub record_uri: String,
80    /// Declared `{key, value}` labels.
81    pub labels: Vec<(String, String)>,
82    /// Declared capacity (k8s-quantity strings) — NOT live/allocatable.
83    /// `queryCandidates` uses the *live* liveness report for resource matching,
84    /// never this durable declaration (see the module docs on trust posture).
85    pub declared_resources: Vec<(String, String)>,
86    /// at-uris of groups this node's own record *consents* to.
87    pub consented_groups: Vec<String>,
88}
89
90/// One decoded `ai.hyprstream.placement.group` record's facts.
91#[derive(Debug, Clone)]
92struct GroupFacts {
93    #[allow(dead_code)] // carried for future group-scoped listing; unused by queryCandidates today
94    name: String,
95    #[allow(dead_code)]
96    owner_did: String,
97}
98
99/// Everything ingested from one DID's repo CAR in the most recent poll. Kept
100/// so a re-poll can *replace* (not merge-forever-append) that DID's
101/// contribution to the derived indices — a group/groupItem record deleted
102/// upstream must be able to disappear from the index on the next poll.
103#[derive(Debug, Clone, Default)]
104struct DidSnapshot {
105    node: Option<NodeFacts>,
106    groups: Vec<(String, String, String)>, // (group at-uri, name, owner_did)
107    group_items: Vec<GroupItemRecord>,
108    /// Decoded but not indexed further (day-1 scope; see module docs).
109    workload_count: usize,
110}
111
112/// In-process placement directory index. Rebuilt by polling
113/// [`RecordResolver::resolve_repo`] for a bootstrap set of node DIDs (day-1
114/// ingestion — see the module docs). Read from the `queryCandidates` request
115/// path; written by the poller. `parking_lot::RwLock` mirrors the precedent
116/// already used for `DiscoveryService`'s other in-memory maps.
117#[derive(Default)]
118pub struct PlacementIndex {
119    state: RwLock<PlacementState>,
120}
121
122#[derive(Default)]
123struct PlacementState {
124    /// Per-DID last-ingested snapshot (the source of truth for re-poll replace
125    /// semantics).
126    raw: HashMap<String, DidSnapshot>,
127    /// Derived: node DID -> facts. Recomputed after every ingest.
128    nodes: HashMap<String, NodeFacts>,
129    /// Derived: group at-uri -> facts.
130    groups: HashMap<String, GroupFacts>,
131    /// Derived: group at-uri -> DIDs the group OWNER claims as members
132    /// (`GroupItemRecord.subject`). Effective membership additionally requires
133    /// the node's own consent — see [`Self::is_member`].
134    group_claims: HashMap<String, Vec<String>>,
135}
136
137impl PlacementIndex {
138    /// Capacity-test fixture for an already verified/warm projection. Admission
139    /// itself is exercised separately with real signed repository fixtures.
140    #[cfg(all(test, not(target_arch = "wasm32"), feature = "valkey"))]
141    pub(crate) fn seed_warm_node_for_test(&self, did: String, facts: NodeFacts) {
142        self.state.write().nodes.insert(did, facts);
143    }
144
145    pub fn new() -> Self {
146        Self::default()
147    }
148
149    /// Poll `did`'s repo via `resolver` and (re-)ingest its placement records,
150    /// replacing whatever this DID contributed on a previous poll.
151    ///
152    /// `Ok(())` with no visible effect when the DID has no stored repo (nothing
153    /// to ingest) or its repo carries no placement records — this is not an
154    /// error, just an empty directory entry.
155    ///
156    /// **Verified by construction (#932, #918):** the resolver MUST supply a
157    /// verification slots for `did` ([`RecordResolver::resolve_verifying_keys`]); if it
158    /// cannot, the repo is **rejected** (fail closed) — its records never reach
159    /// the derived indices. Every CAR block is always content-bound to its
160    /// declared CID. A repo that fails signature verification — or whose
161    /// `commit.did` is not `did` — is refused, and this returns `Err` (the
162    /// caller — `handle_report_node_liveness` — logs and continues; liveness is
163    /// still recorded).
164    ///
165    /// The production resolver currently returns `None` for both the local
166    /// node's mismatched `did:key` authority (#1124) and foreign DIDs (no DID-
167    /// document fetch is wired yet). Those repos are rejected rather than
168    /// silently ingested unverified. Foreign resolution is tracked with #1123.
169    pub async fn ingest_did(&self, resolver: &dyn RecordResolver, did: &str) -> Result<()> {
170        let repo = match resolver.resolve_repo(did).await {
171            Ok(repo) => repo,
172            Err(e) => {
173                self.clear_did(did);
174                return Err(anyhow!("resolve_repo({did}) failed: {e}"));
175            }
176        };
177        let Some(repo) = repo else {
178            // No repo stored for this DID — clear any stale contribution and stop.
179            self.clear_did(did);
180            return Ok(());
181        };
182        // Resolve the bounded `#atproto` slots currently published for `did`.
183        // FAIL CLOSED when no key can be established — a foreign/stale/bad DID
184        // document must not silently ingest unverified records.
185        let verify_keys = match resolver.resolve_verifying_keys(did).await {
186            Ok(Some(keys)) => keys,
187            Ok(None) => {
188                self.clear_did(did);
189                return Err(anyhow!(
190                    "no #atproto verifying key resolved for {did} — refusing to ingest \
191                     unverified (fail closed). Foreign-DID resolution is not yet wired, \
192                     and the local did:key/did:web authority mismatch is tracked by #1124."
193                ));
194            }
195            Err(e) => {
196                self.clear_did(did);
197                return Err(anyhow!("resolve_verifying_keys({did}) failed: {e}"));
198            }
199        };
200        // Decode and signature-verify the CAR *before* touching the index.
201        let snapshot = match Self::decode_repo_car(did, &repo.car, &verify_keys) {
202            Ok(snap) => snap,
203            Err(e) => {
204                self.clear_did(did);
205                return Err(e);
206            }
207        };
208        let mut state = self.state.write();
209        state.raw.insert(did.to_owned(), snapshot);
210        Self::recompute_derived(&mut state);
211        Ok(())
212    }
213
214    fn clear_did(&self, did: &str) {
215        let mut state = self.state.write();
216        state.raw.remove(did);
217        Self::recompute_derived(&mut state);
218    }
219
220    /// Parse a repo CARv1 blob and decode every `ai.hyprstream.placement.*`
221    /// record reachable from the commit's MST root into a [`DidSnapshot`].
222    ///
223    /// Every CAR block is content-bound to its declared CID. The CAR's commit
224    /// signature is verified against the currently-live `verify_keys` via
225    /// [`Commit::verify_against_published_keys`] (the
226    /// verified-by-construction gate of #932): the
227    /// head commit may be signed by the active key or an explicitly bounded
228    /// drain/lead overlap key. The commit
229    /// block, each MST node, and each record block have their CID recomputed
230    /// from their bytes and checked against the CID the CAR/parent declared for
231    /// them before they are trusted (mirrors `hyprstream_pds::mst::Proof::verify`,
232    /// which recomputes every node CID). A signature alone is not enough:
233    /// `Commit::verify` only signs the commit's own bytes (which name the MST
234    /// root CID), so without per-block binding an attacker could replay a
235    /// genuine signed commit with substituted MST-node/record blocks and forge
236    /// membership. A recomputed-CID ≠ declared-CID mismatch returns `Err` (the
237    /// caller refuses to ingest). There is no unauthenticated decode path.
238    fn decode_repo_car(
239        did: &str,
240        car: &[u8],
241        verify_keys: &hyprstream_pds::commit::PublishedAtprotoKeys,
242    ) -> Result<DidSnapshot> {
243        let (roots, blocks) = parse_car_v1(car)?;
244        ensure!(
245            roots.len() == 1,
246            "repo CAR for {did} must have exactly one commit root (got {})",
247            roots.len()
248        );
249        let root_cid = *roots
250            .first()
251            .ok_or_else(|| anyhow!("repo CAR for {did} has no root"))?;
252        let mut block_map = HashMap::with_capacity(blocks.len());
253        for (cid, bytes) in blocks {
254            verify_block_cid(did, cid, &bytes, "CAR")?;
255            ensure!(
256                block_map.insert(cid, bytes).is_none(),
257                "repo CAR for {did} contains duplicate block CID {cid}"
258            );
259        }
260        let commit_bytes = block_map
261            .get(&root_cid)
262            .ok_or_else(|| anyhow!("repo CAR for {did} missing its commit block"))?;
263        let commit = Commit::from_dag_cbor(commit_bytes)?;
264        // A validly-signed repo for DID A must not be replayable under DID B:
265        // even a commit whose signature verifies under the presented key is
266        // refused if its `did` is not the one we were asked to ingest.
267        ensure!(
268            commit.did == did,
269            "repo CAR for {did} carries a commit for a different DID {}",
270            commit.did
271        );
272        commit
273            .verify_against_published_keys(verify_keys, chrono::Utc::now().timestamp())
274            .map_err(|e| anyhow!("repo CAR for {did} failed commit-signature verification: {e}"))?;
275
276        let mut entries = Vec::new();
277        walk_mst(commit.data, &block_map, &mut entries, did)?;
278
279        let mut snapshot = DidSnapshot::default();
280        for (key, record_cid) in entries {
281            let (collection, _rkey) = key
282                .split_once('/')
283                .ok_or_else(|| anyhow!("repo CAR for {did} has malformed MST key {key:?}"))?;
284            let bytes = block_map.get(&record_cid).ok_or_else(|| {
285                anyhow!("repo CAR for {did} missing record block {record_cid} referenced by MST key {key}")
286            })?;
287
288            if collection == node::COLLECTION_NSID {
289                let rec = NodeRecord::from_dag_cbor(bytes)
290                    .map_err(|e| anyhow!("invalid {collection} record at {key}: {e}"))?;
291                snapshot.node = Some(NodeFacts {
292                    record_uri: format!("at://{did}/{key}"),
293                    labels: rec.labels.into_iter().map(|l| (l.key, l.value)).collect(),
294                    declared_resources: rec
295                        .resources
296                        .into_iter()
297                        .map(|r| (r.name, r.capacity))
298                        .collect(),
299                    consented_groups: rec.groups,
300                });
301            } else if collection == group::COLLECTION_NSID {
302                let rec = GroupRecord::from_dag_cbor(bytes)
303                    .map_err(|e| anyhow!("invalid {collection} record at {key}: {e}"))?;
304                let uri = format!("at://{did}/{key}");
305                snapshot.groups.push((uri, rec.name, rec.owner_did));
306            } else if collection == group_item::COLLECTION_NSID {
307                let rec = GroupItemRecord::from_dag_cbor(bytes)
308                    .map_err(|e| anyhow!("invalid {collection} record at {key}: {e}"))?;
309                let (group_did, group_collection) = parse_group_uri(&rec.group)?;
310                ensure!(
311                    group_did == commit.did && group_collection == group::COLLECTION_NSID,
312                    "repo CAR for {did} contains group item for a group it does not own: {}",
313                    rec.group
314                );
315                snapshot.group_items.push(rec);
316            } else if collection == workload::COLLECTION_NSID {
317                // Decoded for completeness per #524 P1 scope; workload placement
318                // decisions aren't consumed by queryCandidates (day-1 scope).
319                WorkloadRecord::from_dag_cbor(bytes)
320                    .map_err(|e| anyhow!("invalid {collection} record at {key}: {e}"))?;
321                snapshot.workload_count += 1;
322            }
323        }
324        Ok(snapshot)
325    }
326
327    /// Rebuild the derived (nodes / groups / group_claims) maps from `raw` in
328    /// full. Simple full-rebuild rather than incremental patching — correct by
329    /// construction (a deleted upstream record can't leak forever) and cheap at
330    /// fleet scale; this is an index refresh, not a hot path.
331    fn recompute_derived(state: &mut PlacementState) {
332        let mut nodes = HashMap::new();
333        let mut groups = HashMap::new();
334        let mut claims: HashMap<String, Vec<String>> = HashMap::new();
335        for (did, snap) in &state.raw {
336            if let Some(n) = &snap.node {
337                nodes.insert(did.clone(), n.clone());
338            }
339            for (uri, name, owner_did) in &snap.groups {
340                groups.insert(
341                    uri.clone(),
342                    GroupFacts {
343                        name: name.clone(),
344                        owner_did: owner_did.clone(),
345                    },
346                );
347            }
348            for item in &snap.group_items {
349                claims
350                    .entry(item.group.clone())
351                    .or_default()
352                    .push(item.subject.clone());
353            }
354        }
355        state.nodes = nodes;
356        state.groups = groups;
357        state.group_claims = claims;
358    }
359
360    /// All node DIDs currently known to the index (have an ingested
361    /// `NodeRecord`).
362    pub fn known_node_dids(&self) -> Vec<String> {
363        self.state.read().nodes.keys().cloned().collect()
364    }
365
366    /// The at-uri of `did`'s `NodeRecord`, if known.
367    pub fn record_uri(&self, did: &str) -> Option<String> {
368        self.state
369            .read()
370            .nodes
371            .get(did)
372            .map(|f| f.record_uri.clone())
373    }
374
375    /// Whether `node_did` is an *effective* (bidirectional-consent) member of
376    /// `group_uri`: the group owner must have published a `GroupItemRecord`
377    /// naming this node, **and** the node's own `NodeRecord.groups` must list
378    /// this group. Either claim alone is not membership.
379    ///
380    /// **Trust statement (#932):** membership facts returned here are always
381    /// content-bound and signature-verified. A `GroupItemRecord` / `NodeRecord`
382    /// whose repo CAR commit failed
383    /// signature verification against the resolver-provided `#atproto` key,
384    /// whose `commit.did` is not the
385    /// requested DID, **or whose any block's recomputed CID ≠ its declared CID**
386    /// never entered the index, so it cannot back a `true` result. The per-block
387    /// CID binding is what stops a replayed genuine signed commit carrying
388    /// substituted blocks from forging membership. See the module trust-posture
389    /// docs for the verified-by-construction, fail-closed ingest gate.
390    pub fn is_member(&self, node_did: &str, group_uri: &str) -> bool {
391        let state = self.state.read();
392        let node_consents = state
393            .nodes
394            .get(node_did)
395            .is_some_and(|f| f.consented_groups.iter().any(|g| g == group_uri));
396        if !node_consents {
397            return false;
398        }
399        state
400            .group_claims
401            .get(group_uri)
402            .is_some_and(|members| members.iter().any(|m| m == node_did))
403    }
404
405    /// A node's effective label set for selector matching: its declared
406    /// `NodeRecord.labels` plus one synthetic `("group/<uri>", "true")` label
407    /// per group it is an *effective* (bidirectional-consent) member of. See
408    /// the module docs for why group membership uses a per-group label key.
409    pub fn effective_labels(&self, node_did: &str) -> Vec<(String, String)> {
410        let state = self.state.read();
411        let (mut labels, consented_groups) = match state.nodes.get(node_did) {
412            Some(f) => (f.labels.clone(), f.consented_groups.clone()),
413            None => return Vec::new(),
414        };
415        for group_uri in &consented_groups {
416            if state
417                .group_claims
418                .get(group_uri)
419                .is_some_and(|members| members.iter().any(|m| m == node_did))
420            {
421                labels.push((format!("group/{group_uri}"), "true".to_owned()));
422            }
423        }
424        labels
425    }
426
427    /// A node's declared (durable) capacity — NOT the live/allocatable figure
428    /// `queryCandidates` matches resource requests against. Exposed mainly for
429    /// tests / introspection.
430    pub fn declared_resources(&self, node_did: &str) -> Vec<(String, String)> {
431        self.state
432            .read()
433            .nodes
434            .get(node_did)
435            .map(|f| f.declared_resources.clone())
436            .unwrap_or_default()
437    }
438}
439
440/// Hard ceiling on the number of MST node visits per repo-CAR walk. An
441/// untrusted CAR is not a well-formed tree by assumption: it can be
442/// DAG-shaped (many `l`/`t` links pointing at the same child) or cyclic, so a
443/// depth bound alone does not bound total work — a poisoned CAR could fan out
444/// to visit the same subtrees exponentially, or loop forever. The `visited`
445/// CID set makes the walk terminate (a node is expanded at most once); this
446/// budget is the belt-and-suspenders ceiling that caps total node visits even
447/// against a broad-but-acyclic adversarial CAR, and is chosen well above any
448/// legitimate repo's node count.
449const MST_MAX_NODE_VISITS: usize = 1 << 20; // 1,048,576 nodes
450
451fn parse_group_uri(uri: &str) -> Result<(&str, &str)> {
452    let rest = uri
453        .strip_prefix("at://")
454        .ok_or_else(|| anyhow!("group URI must start with at://: {uri:?}"))?;
455    let mut parts = rest.split('/');
456    let did = parts.next().filter(|part| !part.is_empty());
457    let collection = parts.next().filter(|part| !part.is_empty());
458    let rkey = parts.next().filter(|part| !part.is_empty());
459    ensure!(
460        did.is_some() && collection.is_some() && rkey.is_some() && parts.next().is_none(),
461        "group URI must be at://<did>/<collection>/<rkey>: {uri:?}"
462    );
463    Ok((did.unwrap_or_default(), collection.unwrap_or_default()))
464}
465
466/// Recompute a block's CID from its bytes and confirm it matches the CID its
467/// container (the CAR root list, a parent MST node's child pointer, or an MST
468/// entry value) declared for it. A mismatch means the bytes were substituted
469/// under a genuine CID — the whole ingest is rejected (fail closed). Mirrors
470/// `hyprstream_pds::mst::Proof::verify`, which recomputes every node CID rather
471/// than trusting the declared one.
472fn verify_block_cid(did: &str, declared: Cid, bytes: &[u8], kind: &str) -> Result<()> {
473    let actual = Cid::from_dag_cbor(bytes);
474    ensure!(
475        actual == declared,
476        "repo CAR for {did}: {kind} block content/CID mismatch (declared {declared}, recomputed {actual})"
477    );
478    Ok(())
479}
480
481/// Maximum MST depth permitted during a walk. Real atproto MSTs are shallow
482/// (a node splits every 2 leading key-characters, so a 256-char key caps depth
483/// near 128); this bound just defends a CAR shaped to stack-overflow the
484/// recursive walk (an attacker-supplied cyclic-ish pointer chain).
485const MST_MAX_DEPTH: usize = 1024;
486
487/// Enumerate every `(full_key, record_cid)` entry reachable from an MST node,
488/// depth-first in key order: left subtree, then each entry (recursing into its
489/// right subtree before the next entry). Mirrors the encode side
490/// (`Node::to_node_data_rec` in `hyprstream_pds::mst`) exactly, including its
491/// prefix-compression convention: `entry.p` compresses against the *previous
492/// entry within this same node* only (resets to 0 at the first entry of every
493/// node) — never against a key from a different node.
494///
495/// **Untrusted-ingest safety (#932):** `visited` records every node CID already
496/// expanded so a DAG-shaped or cyclic CAR cannot revisit the same subtree, and
497/// `budget` is a decrementing total-visit ceiling. Either guard trips a
498/// fail-closed `Err` — the whole CAR is rejected rather than partially
499/// ingested, so no derived membership fact is produced from an adversarial
500/// graph.
501///
502fn walk_mst(
503    node_cid: Cid,
504    blocks: &HashMap<Cid, Vec<u8>>,
505    out: &mut Vec<(String, Cid)>,
506    did: &str,
507) -> Result<()> {
508    let mut visited = HashSet::new();
509    let mut budget = MST_MAX_NODE_VISITS;
510    walk_mst_inner(node_cid, blocks, out, did, 0, &mut visited, &mut budget)
511}
512
513fn walk_mst_inner(
514    node_cid: Cid,
515    blocks: &HashMap<Cid, Vec<u8>>,
516    out: &mut Vec<(String, Cid)>,
517    did: &str,
518    depth: usize,
519    visited: &mut HashSet<Cid>,
520    budget: &mut usize,
521) -> Result<()> {
522    ensure!(
523        depth <= MST_MAX_DEPTH,
524        "MST walk for {did} exceeded max depth {MST_MAX_DEPTH} (possible CAR stack-overflow DoS)"
525    );
526    ensure!(
527        *budget > 0,
528        "MST walk exceeded the {MST_MAX_NODE_VISITS}-node visit budget (adversarial repo CAR?)"
529    );
530    *budget -= 1;
531    ensure!(
532        visited.insert(node_cid),
533        "MST node {node_cid} is reachable more than once (non-tree repo CAR); refusing ingest"
534    );
535    let bytes = blocks
536        .get(&node_cid)
537        .ok_or_else(|| anyhow!("MST node {node_cid} missing from repo CAR blocks"))?;
538    let value = DagCbor::decode(bytes)?;
539    let data = NodeData::from_value(&value)?;
540
541    if let Some(left) = data.l {
542        walk_mst_inner(left, blocks, out, did, depth + 1, visited, budget)?;
543    }
544    let mut prev_key: Option<String> = None;
545    for entry in &data.e {
546        let key = match &prev_key {
547            Some(prev) => {
548                let prev_bytes = prev.as_bytes();
549                let take = entry.p.min(prev_bytes.len());
550                let mut full = prev_bytes[..take].to_vec();
551                full.extend_from_slice(&entry.k);
552                String::from_utf8(full).map_err(|e| anyhow!("MST entry key is not utf8: {e}"))?
553            }
554            None => String::from_utf8(entry.k.clone())
555                .map_err(|e| anyhow!("MST entry key is not utf8: {e}"))?,
556        };
557        out.push((key.clone(), entry.v));
558        prev_key = Some(key);
559        if let Some(right) = entry.t {
560            walk_mst_inner(right, blocks, out, did, depth + 1, visited, budget)?;
561        }
562    }
563    Ok(())
564}
565
566#[cfg(test)]
567#[allow(clippy::unwrap_used, clippy::expect_used, clippy::indexing_slicing)]
568mod tests {
569    use super::*;
570    use std::collections::BTreeMap;
571
572    use async_trait::async_trait;
573    use hyprstream_pds::car::{build_car_v1, parse_car_v1};
574    use hyprstream_pds::commit::UnsignedCommit;
575    use hyprstream_pds::mst::Node;
576    use hyprstream_pds::tid::Tid;
577    use p256::ecdsa::{SigningKey as P256SigningKey, VerifyingKey as P256VerifyingKey};
578
579    use crate::service::RecordCarData;
580
581    const NODE_DID: &str = "did:web:node1.example.com";
582    const OWNER_DID: &str = "did:web:owner.example.com";
583
584    /// Build a repo CARv1 for `did` from a set of already-encoded `(full_key,
585    /// dag_cbor_bytes)` records (mixed collections OK — the repo MST spans all
586    /// of them, matching real atproto repos), returning the CAR bytes **and**
587    /// the `#atproto` verifying key the commit was signed with (so the test
588    /// resolver can hand it to the verified-by-construction ingest gate).
589    fn repo_car(did: &str, records: &[(String, Vec<u8>)]) -> (Vec<u8>, P256VerifyingKey) {
590        let signing_key = P256SigningKey::random(&mut rand::rngs::OsRng);
591        repo_car_with_key(did, records, signing_key)
592    }
593
594    /// Like [`repo_car`] but signs the commit with a caller-supplied key — used
595    /// by the #918 rotation tests to sign with a now-drained key.
596    fn repo_car_with_key(
597        did: &str,
598        records: &[(String, Vec<u8>)],
599        signing_key: P256SigningKey,
600    ) -> (Vec<u8>, P256VerifyingKey) {
601        let verifying_key = P256VerifyingKey::from(&signing_key);
602        let mut keyed: BTreeMap<String, Cid> = BTreeMap::new();
603        let mut record_blocks: Vec<(Cid, Vec<u8>)> = Vec::new();
604        for (key, bytes) in records {
605            let cid = Cid::from_dag_cbor(bytes);
606            keyed.insert(key.clone(), cid);
607            record_blocks.push((cid, bytes.clone()));
608        }
609        let tree = Node::from_keyed_records(&keyed);
610        let root = tree.root_cid();
611        let (_root_data, node_blocks) = tree.to_node_data_with_blocks();
612        let unsigned = UnsignedCommit::new(did.to_owned(), root, Tid::now(), None);
613        let commit = hyprstream_pds::commit::Commit::sign(&unsigned, &signing_key);
614
615        let mut blocks: Vec<(Cid, Vec<u8>)> = vec![(commit.cid(), commit.to_dag_cbor())];
616        for (cid, data) in node_blocks {
617            blocks.push((cid, data.encode()));
618        }
619        blocks.extend(record_blocks);
620        (build_car_v1(&[commit.cid()], &blocks), verifying_key)
621    }
622
623    fn node_record_key(rkey: &str) -> String {
624        format!("{}/{rkey}", node::COLLECTION_NSID)
625    }
626    fn group_record_key(rkey: &str) -> String {
627        format!("{}/{rkey}", group::COLLECTION_NSID)
628    }
629    fn group_item_record_key(rkey: &str) -> String {
630        format!("{}/{rkey}", group_item::COLLECTION_NSID)
631    }
632
633    /// A resolver serving fixed, per-DID repo CARs (built with real records)
634    /// and the `#atproto` verifying key each was signed with — so the
635    /// verified-by-construction ingest gate is armed in tests.
636    struct FixedResolver {
637        repos: HashMap<String, (Vec<u8>, P256VerifyingKey)>,
638    }
639
640    #[async_trait(?Send)]
641    impl RecordResolver for FixedResolver {
642        async fn resolve_record(
643            &self,
644            _did: &str,
645            _collection: &str,
646            _rkey: &str,
647        ) -> Result<Option<RecordCarData>> {
648            Ok(None)
649        }
650        async fn resolve_repo(&self, did: &str) -> Result<Option<RecordCarData>> {
651            Ok(self.repos.get(did).map(|(car, _vk)| RecordCarData {
652                uri: format!("at://{did}"),
653                car: car.clone(),
654            }))
655        }
656        async fn resolve_verifying_key(&self, did: &str) -> Result<Option<P256VerifyingKey>> {
657            Ok(self.repos.get(did).map(|(_car, vk)| *vk))
658        }
659    }
660
661    fn sample_node_record(groups: Vec<String>) -> NodeRecord {
662        NodeRecord::new(
663            format!("at://{NODE_DID}"),
664            vec![node::Label {
665                key: "zone".into(),
666                value: "us-east".into(),
667            }],
668            vec![node::Resource {
669                name: "nvidia.com/gpu".into(),
670                capacity: "8".into(),
671            }],
672            groups,
673            "2026-06-23T12:34:56.789Z",
674        )
675        .unwrap()
676    }
677
678    #[tokio::test]
679    async fn ingest_decodes_node_record_labels_and_resources() {
680        let rec = sample_node_record(vec![]);
681        let car = repo_car(NODE_DID, &[(node_record_key("3a"), rec.to_dag_cbor())]);
682        let resolver = FixedResolver {
683            repos: HashMap::from([(NODE_DID.to_owned(), car)]),
684        };
685        let index = PlacementIndex::new();
686        index.ingest_did(&resolver, NODE_DID).await.unwrap();
687
688        assert_eq!(index.known_node_dids(), vec![NODE_DID.to_owned()]);
689        assert_eq!(
690            index.record_uri(NODE_DID).as_deref(),
691            Some(format!("at://{NODE_DID}/{}", node_record_key("3a")).as_str())
692        );
693        let labels = index.effective_labels(NODE_DID);
694        assert!(labels.contains(&("zone".to_owned(), "us-east".to_owned())));
695        assert_eq!(
696            index.declared_resources(NODE_DID),
697            vec![("nvidia.com/gpu".to_owned(), "8".to_owned())]
698        );
699    }
700
701    #[tokio::test]
702    async fn ingest_missing_repo_is_not_an_error_and_yields_no_node() {
703        let resolver = FixedResolver {
704            repos: HashMap::new(),
705        };
706        let index = PlacementIndex::new();
707        index.ingest_did(&resolver, NODE_DID).await.unwrap();
708        assert!(index.known_node_dids().is_empty());
709    }
710
711    #[tokio::test]
712    async fn group_membership_requires_both_owner_claim_and_node_consent() {
713        let group_uri_key = group_record_key("3g");
714        let group_rec = GroupRecord::new(
715            "east-coast-gpus",
716            OWNER_DID,
717            None,
718            "2026-06-23T12:34:56.789Z",
719        )
720        .unwrap();
721        let group_uri = format!("at://{OWNER_DID}/{group_uri_key}");
722
723        // Case 1: owner claims the node, but the node's own record does NOT
724        // list the group (no node-side consent) -> not a member.
725        {
726            let owner_car = repo_car(
727                OWNER_DID,
728                &[
729                    (group_uri_key.clone(), group_rec.to_dag_cbor()),
730                    (
731                        group_item_record_key("3i"),
732                        GroupItemRecord::new(
733                            group_uri.clone(),
734                            NODE_DID,
735                            "2026-06-23T12:34:56.789Z",
736                        )
737                        .unwrap()
738                        .to_dag_cbor(),
739                    ),
740                ],
741            );
742            let node_rec = sample_node_record(vec![]); // no consent
743            let node_car = repo_car(NODE_DID, &[(node_record_key("3a"), node_rec.to_dag_cbor())]);
744            let resolver = FixedResolver {
745                repos: HashMap::from([
746                    (OWNER_DID.to_owned(), owner_car),
747                    (NODE_DID.to_owned(), node_car),
748                ]),
749            };
750            let index = PlacementIndex::new();
751            index.ingest_did(&resolver, OWNER_DID).await.unwrap();
752            index.ingest_did(&resolver, NODE_DID).await.unwrap();
753            assert!(
754                !index.is_member(NODE_DID, &group_uri),
755                "owner-claim without node consent must NOT be membership"
756            );
757            assert!(!index
758                .effective_labels(NODE_DID)
759                .iter()
760                .any(|(k, _)| k == &format!("group/{group_uri}")));
761        }
762
763        // Case 2: node consents (lists the group in its own record), but the
764        // owner never published a GroupItemRecord naming it -> not a member.
765        {
766            let owner_car = repo_car(
767                OWNER_DID,
768                &[(group_uri_key.clone(), group_rec.to_dag_cbor())],
769            );
770            let node_rec = sample_node_record(vec![group_uri.clone()]);
771            let node_car = repo_car(NODE_DID, &[(node_record_key("3a"), node_rec.to_dag_cbor())]);
772            let resolver = FixedResolver {
773                repos: HashMap::from([
774                    (OWNER_DID.to_owned(), owner_car),
775                    (NODE_DID.to_owned(), node_car),
776                ]),
777            };
778            let index = PlacementIndex::new();
779            index.ingest_did(&resolver, OWNER_DID).await.unwrap();
780            index.ingest_did(&resolver, NODE_DID).await.unwrap();
781            assert!(
782                !index.is_member(NODE_DID, &group_uri),
783                "node consent without an owner claim must NOT be membership"
784            );
785        }
786
787        // Case 3: both sides agree -> effective member, surfaced as a synthetic label.
788        {
789            let owner_car = repo_car(
790                OWNER_DID,
791                &[
792                    (group_uri_key.clone(), group_rec.to_dag_cbor()),
793                    (
794                        group_item_record_key("3i"),
795                        GroupItemRecord::new(
796                            group_uri.clone(),
797                            NODE_DID,
798                            "2026-06-23T12:34:56.789Z",
799                        )
800                        .unwrap()
801                        .to_dag_cbor(),
802                    ),
803                ],
804            );
805            let node_rec = sample_node_record(vec![group_uri.clone()]);
806            let node_car = repo_car(NODE_DID, &[(node_record_key("3a"), node_rec.to_dag_cbor())]);
807            let resolver = FixedResolver {
808                repos: HashMap::from([
809                    (OWNER_DID.to_owned(), owner_car),
810                    (NODE_DID.to_owned(), node_car),
811                ]),
812            };
813            let index = PlacementIndex::new();
814            index.ingest_did(&resolver, OWNER_DID).await.unwrap();
815            index.ingest_did(&resolver, NODE_DID).await.unwrap();
816            assert!(
817                index.is_member(NODE_DID, &group_uri),
818                "both claims present -> member"
819            );
820            assert!(index
821                .effective_labels(NODE_DID)
822                .iter()
823                .any(|(k, v)| k == &format!("group/{group_uri}") && v == "true"));
824        }
825    }
826
827    #[tokio::test]
828    async fn reingesting_a_did_replaces_its_prior_contribution() {
829        let rec_a = sample_node_record(vec![]);
830        let car_a = repo_car(NODE_DID, &[(node_record_key("3a"), rec_a.to_dag_cbor())]);
831        let resolver_a = FixedResolver {
832            repos: HashMap::from([(NODE_DID.to_owned(), car_a)]),
833        };
834        let index = PlacementIndex::new();
835        index.ingest_did(&resolver_a, NODE_DID).await.unwrap();
836        assert_eq!(index.declared_resources(NODE_DID).len(), 1);
837
838        // Re-poll with an empty repo (record deleted upstream) — must clear, not
839        // leave the stale entry around forever.
840        let resolver_b = FixedResolver {
841            repos: HashMap::new(),
842        };
843        index.ingest_did(&resolver_b, NODE_DID).await.unwrap();
844        assert!(
845            index.known_node_dids().is_empty(),
846            "stale contribution must be cleared on re-poll"
847        );
848    }
849
850    #[tokio::test]
851    async fn invalid_commit_signature_does_not_produce_membership() {
852        // #932 — verified-by-construction ingest: a repo CAR whose commit
853        // signature fails verification against the resolver-provided `#atproto`
854        // key must be REFUSED at ingest, so its records cannot produce
855        // membership (or any other derived fact). Mirror the "both sides agree
856        // -> member" setup, but have the resolver report a *wrong* key for the
857        // owner so the GroupItemRecord claiming NODE_DID never enters the index.
858        let group_uri_key = group_record_key("3g");
859        let group_rec = GroupRecord::new(
860            "east-coast-gpus",
861            OWNER_DID,
862            None,
863            "2026-06-23T12:34:56.789Z",
864        )
865        .unwrap();
866        let group_uri = format!("at://{OWNER_DID}/{group_uri_key}");
867
868        let (owner_car, _owner_vk) = repo_car(
869            OWNER_DID,
870            &[
871                (group_uri_key.clone(), group_rec.to_dag_cbor()),
872                (
873                    group_item_record_key("3i"),
874                    GroupItemRecord::new(group_uri.clone(), NODE_DID, "2026-06-23T12:34:56.789Z")
875                        .unwrap()
876                        .to_dag_cbor(),
877                ),
878            ],
879        );
880        // A key the owner's commit was NOT signed by -> verification must fail.
881        let wrong_vk = P256VerifyingKey::from(&P256SigningKey::random(&mut rand::rngs::OsRng));
882
883        // The node consents to the group (so membership would hold if the
884        // owner's claim were ingested); its own repo verifies normally.
885        let node_rec = sample_node_record(vec![group_uri.clone()]);
886        let (node_car, node_vk) =
887            repo_car(NODE_DID, &[(node_record_key("3a"), node_rec.to_dag_cbor())]);
888
889        let resolver = FixedResolver {
890            repos: HashMap::from([
891                (OWNER_DID.to_owned(), (owner_car, wrong_vk)),
892                (NODE_DID.to_owned(), (node_car, node_vk)),
893            ]),
894        };
895        let index = PlacementIndex::new();
896        // Owner ingest must fail closed — a commit that does not verify is
897        // refused (the caller logs and continues; liveness is unaffected).
898        assert!(
899            index.ingest_did(&resolver, OWNER_DID).await.is_err(),
900            "a repo whose commit signature fails verification must be refused at ingest"
901        );
902        index.ingest_did(&resolver, NODE_DID).await.unwrap();
903
904        assert!(
905            !index.is_member(NODE_DID, &group_uri),
906            "an unverified GroupItemRecord must not produce membership even with node consent"
907        );
908        assert!(!index
909            .effective_labels(NODE_DID)
910            .iter()
911            .any(|(k, _)| k == &format!("group/{group_uri}")));
912    }
913
914    #[tokio::test]
915    async fn substituted_block_under_genuine_signed_commit_does_not_produce_membership() {
916        // Security: the commit signature alone is not enough — `Commit::verify`
917        // only signs the commit's own bytes (which name the MST root CID), so
918        // an attacker who replays a genuine signed commit but SUBSTITUTES a
919        // record block's bytes under its declared CID can otherwise forge a
920        // GroupItemRecord claiming NODE_DID. The per-block CID content-binding
921        // check at ingest must catch this: the recomputed CID ≠ declared CID,
922        // so the whole ingest is refused (fail closed) and no membership is
923        // produced — even though the commit signature still verifies.
924        let group_uri_key = group_record_key("3g");
925        let group_rec = GroupRecord::new(
926            "east-coast-gpus",
927            OWNER_DID,
928            None,
929            "2026-06-23T12:34:56.789Z",
930        )
931        .unwrap();
932        let group_uri = format!("at://{OWNER_DID}/{group_uri_key}");
933
934        // The genuine GroupItemRecord the owner *signed* into their MST.
935        let genuine_item =
936            GroupItemRecord::new(group_uri.clone(), NODE_DID, "2026-06-23T12:34:56.789Z").unwrap();
937        let genuine_item_bytes = genuine_item.to_dag_cbor();
938        // A *different* valid GroupItemRecord (forged bytes) the attacker swaps
939        // in under the genuine one's CID. It still claims NODE_DID, so without
940        // the CID check it would decode and produce membership — proving the
941        // catch is the content-bind, not a decode failure.
942        let forged_item_bytes =
943            GroupItemRecord::new(group_uri.clone(), NODE_DID, "2026-07-09T00:00:00.000Z")
944                .unwrap()
945                .to_dag_cbor();
946        assert_ne!(
947            genuine_item_bytes, forged_item_bytes,
948            "forged block must differ from the genuine one"
949        );
950
951        let (owner_car, owner_vk) = repo_car(
952            OWNER_DID,
953            &[
954                (group_uri_key.clone(), group_rec.to_dag_cbor()),
955                (group_item_record_key("3i"), genuine_item_bytes.clone()),
956            ],
957        );
958        // The CID under which the genuine item lives in the signed MST.
959        let item_cid = Cid::from_dag_cbor(&genuine_item_bytes);
960
961        // Replay the owner's genuine signed commit, but swap the item block's
962        // bytes for the forged record while keeping the declared CID unchanged.
963        let (roots, blocks) = parse_car_v1(&owner_car).unwrap();
964        let tampered_blocks: Vec<(Cid, Vec<u8>)> = blocks
965            .into_iter()
966            .map(|(cid, bytes)| {
967                if cid == item_cid {
968                    (cid, forged_item_bytes.clone())
969                } else {
970                    (cid, bytes)
971                }
972            })
973            .collect();
974        let tampered_owner_car = build_car_v1(&roots, &tampered_blocks);
975
976        // Node consents (so membership WOULD hold if the forged claim ingested).
977        let node_rec = sample_node_record(vec![group_uri.clone()]);
978        let (node_car, node_vk) =
979            repo_car(NODE_DID, &[(node_record_key("3a"), node_rec.to_dag_cbor())]);
980
981        let resolver = FixedResolver {
982            repos: HashMap::from([
983                (OWNER_DID.to_owned(), (tampered_owner_car, owner_vk)),
984                (NODE_DID.to_owned(), (node_car, node_vk)),
985            ]),
986        };
987        let index = PlacementIndex::new();
988        // The owner ingest MUST fail closed — the commit signature verifies, but
989        // the substituted block's recomputed CID ≠ its declared CID.
990        assert!(
991            index.ingest_did(&resolver, OWNER_DID).await.is_err(),
992            "a repo whose block bytes don't hash to their declared CID must be refused, \
993             even with a valid commit signature"
994        );
995        index.ingest_did(&resolver, NODE_DID).await.unwrap();
996
997        assert!(
998            !index.is_member(NODE_DID, &group_uri),
999            "a block substituted under a genuine signed commit must not forge membership"
1000        );
1001        assert!(!index
1002            .effective_labels(NODE_DID)
1003            .iter()
1004            .any(|(k, _)| k == &format!("group/{group_uri}")));
1005    }
1006
1007    #[tokio::test]
1008    async fn missing_verifying_key_fails_closed() {
1009        // #918 r2: a resolver that cannot supply a #atproto key MUST cause
1010        // ingest to fail closed — no silent unverified ingest.
1011        let rec = sample_node_record(vec![]);
1012        let (car, _) = repo_car(NODE_DID, &[(node_record_key("3a"), rec.to_dag_cbor())]);
1013
1014        struct NoKeyResolver(HashMap<String, Vec<u8>>);
1015        #[async_trait(?Send)]
1016        impl RecordResolver for NoKeyResolver {
1017            async fn resolve_record(
1018                &self,
1019                _did: &str,
1020                _collection: &str,
1021                _rkey: &str,
1022            ) -> Result<Option<RecordCarData>> {
1023                Ok(None)
1024            }
1025            async fn resolve_repo(&self, did: &str) -> Result<Option<RecordCarData>> {
1026                Ok(self.0.get(did).map(|car| RecordCarData {
1027                    uri: format!("at://{did}"),
1028                    car: car.clone(),
1029                }))
1030            }
1031            // resolve_verifying_key defaults to Ok(None).
1032        }
1033
1034        let resolver = NoKeyResolver(HashMap::from([(NODE_DID.to_owned(), car)]));
1035        let index = PlacementIndex::new();
1036        assert!(
1037            index.ingest_did(&resolver, NODE_DID).await.is_err(),
1038            "a resolver with no #atproto key must fail closed, not silently ingest"
1039        );
1040        assert!(index.known_node_dids().is_empty());
1041    }
1042
1043    #[tokio::test]
1044    async fn did_confused_repo_is_rejected_and_clears_stale_state() {
1045        let rec = sample_node_record(vec![]);
1046        let valid = repo_car(NODE_DID, &[(node_record_key("3a"), rec.to_dag_cbor())]);
1047        let index = PlacementIndex::new();
1048        index
1049            .ingest_did(
1050                &FixedResolver {
1051                    repos: HashMap::from([(NODE_DID.to_owned(), valid)]),
1052                },
1053                NODE_DID,
1054            )
1055            .await
1056            .unwrap();
1057
1058        let owner_repo = repo_car(
1059            OWNER_DID,
1060            &[(
1061                node_record_key("3a"),
1062                sample_node_record(vec![]).to_dag_cbor(),
1063            )],
1064        );
1065        let confused = FixedResolver {
1066            repos: HashMap::from([(NODE_DID.to_owned(), owner_repo)]),
1067        };
1068        assert!(index.ingest_did(&confused, NODE_DID).await.is_err());
1069        assert!(index.known_node_dids().is_empty());
1070    }
1071
1072    #[tokio::test]
1073    async fn decode_failure_clears_stale_state() {
1074        // #918 r2: fail-closed means NoKeyResolver always fails; use
1075        // FixedResolver (provides a key) to first successfully ingest, then a
1076        // malformed repo to trigger a decode failure that clears the stale state.
1077        let (car, vk) = repo_car(
1078            NODE_DID,
1079            &[(
1080                node_record_key("3a"),
1081                sample_node_record(vec![]).to_dag_cbor(),
1082            )],
1083        );
1084        let index = PlacementIndex::new();
1085        index
1086            .ingest_did(
1087                &FixedResolver {
1088                    repos: HashMap::from([(NODE_DID.to_owned(), (car, vk))]),
1089                },
1090                NODE_DID,
1091            )
1092            .await
1093            .unwrap();
1094        assert!(!index.known_node_dids().is_empty());
1095
1096        // A malformed repo (garbage bytes) triggers decode failure → clears state.
1097        let malformed = FixedResolver {
1098            repos: HashMap::from([(NODE_DID.to_owned(), (vec![0xff], vk))]),
1099        };
1100        assert!(index.ingest_did(&malformed, NODE_DID).await.is_err());
1101        assert!(index.known_node_dids().is_empty());
1102    }
1103
1104    #[tokio::test]
1105    async fn third_party_group_claim_is_rejected() {
1106        let group_uri = format!("at://{OWNER_DID}/{}/3g", group::COLLECTION_NSID);
1107        let third_party_item =
1108            GroupItemRecord::new(group_uri, NODE_DID, "2026-06-23T12:34:56.789Z").unwrap();
1109        let third_party_repo = repo_car(
1110            NODE_DID,
1111            &[(group_item_record_key("3i"), third_party_item.to_dag_cbor())],
1112        );
1113        let resolver = FixedResolver {
1114            repos: HashMap::from([(NODE_DID.to_owned(), third_party_repo)]),
1115        };
1116        let index = PlacementIndex::new();
1117
1118        assert!(index.ingest_did(&resolver, NODE_DID).await.is_err());
1119        assert!(index.known_node_dids().is_empty());
1120    }
1121
1122    #[test]
1123    fn car_structure_bypasses_are_rejected() {
1124        let (car, vk) = repo_car(
1125            NODE_DID,
1126            &[(
1127                node_record_key("3a"),
1128                sample_node_record(vec![]).to_dag_cbor(),
1129            )],
1130        );
1131        let keys = hyprstream_pds::commit::PublishedAtprotoKeys::single(vk);
1132        let (roots, blocks) = parse_car_v1(&car).unwrap();
1133        // Structural checks fail before signature verification; single key suffices.
1134        let duplicate = build_car_v1(&roots, &[blocks.clone(), blocks.clone()].concat());
1135        assert!(PlacementIndex::decode_repo_car(NODE_DID, &duplicate, &keys).is_err());
1136        let multiple_roots = build_car_v1(&[roots[0], roots[0]], &blocks);
1137        assert!(PlacementIndex::decode_repo_car(NODE_DID, &multiple_roots, &keys).is_err());
1138        let missing_record = build_car_v1(&roots, &blocks[..blocks.len() - 1]);
1139        assert!(PlacementIndex::decode_repo_car(NODE_DID, &missing_record, &keys).is_err());
1140    }
1141
1142    // ── #918: re-sign-on-rotation + single-key verification ──────────────────
1143
1144    /// (a) Rotate K→K', re-sign head with K', verify against the current doc
1145    /// key (=K') → passes. The producer's re-sign is what makes verification
1146    /// succeed.
1147    #[tokio::test]
1148    async fn rotated_head_re_signed_verifies_against_current_key() {
1149        let old_key = P256SigningKey::random(&mut rand::rngs::OsRng);
1150        let new_key = P256SigningKey::random(&mut rand::rngs::OsRng);
1151        let new_vk = P256VerifyingKey::from(&new_key);
1152        // Head re-signed with the NEW key.
1153        let (car, _) = repo_car_with_key(
1154            NODE_DID,
1155            &[(
1156                node_record_key("r1"),
1157                sample_node_record(vec![]).to_dag_cbor(),
1158            )],
1159            new_key,
1160        );
1161        let resolver = FixedResolver {
1162            repos: HashMap::from([(NODE_DID.to_owned(), (car, new_vk))]),
1163        };
1164        let index = PlacementIndex::new();
1165        index
1166            .ingest_did(&resolver, NODE_DID)
1167            .await
1168            .expect("re-signed head verifies against current key");
1169        assert!(index.known_node_dids().contains(&NODE_DID.to_owned()));
1170        let _ = old_key;
1171    }
1172
1173    /// (b) A head NOT re-signed after rotation (still signed by K) does NOT
1174    /// verify against the current key (K') — the producer's re-sign is what
1175    /// makes verification succeed; without it, verification correctly fails.
1176    #[tokio::test]
1177    async fn not_re_signed_head_fails_against_rotated_key() {
1178        let old_key = P256SigningKey::random(&mut rand::rngs::OsRng);
1179        let new_key = P256SigningKey::random(&mut rand::rngs::OsRng);
1180        let new_vk = P256VerifyingKey::from(&new_key);
1181        // Head still signed by the OLD key.
1182        let (car, _) = repo_car_with_key(
1183            NODE_DID,
1184            &[(
1185                node_record_key("r1"),
1186                sample_node_record(vec![]).to_dag_cbor(),
1187            )],
1188            old_key,
1189        );
1190        // Resolver returns the NEW (current) key.
1191        let resolver = FixedResolver {
1192            repos: HashMap::from([(NODE_DID.to_owned(), (car, new_vk))]),
1193        };
1194        let index = PlacementIndex::new();
1195        assert!(
1196            index.ingest_did(&resolver, NODE_DID).await.is_err(),
1197            "a head not re-signed after rotation must fail against the rotated-in key"
1198        );
1199        assert!(index.known_node_dids().is_empty());
1200    }
1201
1202    /// (c) Forged signature → fails.
1203    #[tokio::test]
1204    async fn forged_signature_fails() {
1205        let signing = P256SigningKey::random(&mut rand::rngs::OsRng);
1206        let forged_vk = P256VerifyingKey::from(&P256SigningKey::random(&mut rand::rngs::OsRng));
1207        let (car, _) = repo_car_with_key(
1208            NODE_DID,
1209            &[(
1210                node_record_key("r1"),
1211                sample_node_record(vec![]).to_dag_cbor(),
1212            )],
1213            signing,
1214        );
1215        // Resolver returns a DIFFERENT key than the one that signed.
1216        let resolver = FixedResolver {
1217            repos: HashMap::from([(NODE_DID.to_owned(), (car, forged_vk))]),
1218        };
1219        let index = PlacementIndex::new();
1220        assert!(
1221            index.ingest_did(&resolver, NODE_DID).await.is_err(),
1222            "a commit signed by a different key than the resolver provides must fail"
1223        );
1224        assert!(index.known_node_dids().is_empty());
1225    }
1226
1227    #[test]
1228    fn shared_mst_node_is_rejected_traversal_wide() {
1229        use hyprstream_pds::mst::TreeEntry;
1230
1231        let leaf_bytes = NodeData { l: None, e: vec![] }.encode();
1232        let leaf_cid = Cid::from_dag_cbor(&leaf_bytes);
1233        let parent = NodeData {
1234            l: Some(leaf_cid),
1235            e: vec![TreeEntry {
1236                p: 0,
1237                k: b"x/y".to_vec(),
1238                v: Cid::from_dag_cbor(b"record"),
1239                t: Some(leaf_cid),
1240            }],
1241        };
1242        let parent_bytes = parent.encode();
1243        let parent_cid = Cid::from_dag_cbor(&parent_bytes);
1244        let blocks = HashMap::from([(leaf_cid, leaf_bytes), (parent_cid, parent_bytes)]);
1245        let mut out = Vec::new();
1246
1247        assert!(walk_mst(parent_cid, &blocks, &mut out, NODE_DID).is_err());
1248    }
1249}