security+perf: SHA-256 memory provenance hash, O(1) knowledge-graph adjacency

INT-01: MemoryProvenance.content_hash was an unkeyed FNV-1a 64-bit hash,
which has no collision resistance -- an adversary could cheaply craft
different poisoned memory content matching an already-recorded hash,
undermining the "poisoning resistance" the provenance store exists to
provide. Switch to SHA-256 hex digests via the existing, default-on
clawhdf5-format::provenance::sha256_hex helper (already a dependency,
already used for on-disk dataset provenance) -- zero new deps.

INT-02: KnowledgeCache::bfs_neighbors and ::spreading_activation did a
full linear scan over all relations for every node visited/activated
(O(V*R) and O(steps*V*R) respectively), plus an O(n) get_entity scan per
discovered neighbour. Both now build a per-call adjacency index once
(O(V+R)) and use it for O(1) neighbour/entity lookups inside the
traversal loop. Built fresh per call rather than cached on the struct
since schema.rs's deserialization path pushes into the public
entities/relations vecs directly, which would make a cached index go
stale.

research/IMPLEMENTATION_BRIEF.md documents the audit (including bounds-
checking and BM25/HNSW areas found already hardened by prior tiers) and
what was deliberately deferred.

cargo test --workspace: 0 failures.

Co-Authored-By: Claude Sonnet 5 <[email protected]>

crates/clawhdf5-agent/src/knowledge.rs

@@ -329,6 +329,47 @@ impl KnowledgeCache {
         (id, true)
     }
 
+    // -----------------------------------------------------------------------
+    // Adjacency index (built fresh per traversal call — see doc comment)
+    // -----------------------------------------------------------------------
+
+    /// Build an O(V+R) adjacency index for one traversal call: an entity-id →
+    /// vec-index map for O(1) entity lookups, and an entity-id →
+    /// `(neighbour_id, relation_weight)` map (covering both outgoing and
+    /// incoming edges) for O(1) neighbour expansion. The weight is carried
+    /// alongside each neighbour so callers like `spreading_activation` that
+    /// need per-edge weight don't have to re-scan `relations`.
+    ///
+    /// This is rebuilt at the start of every `bfs_neighbors`/
+    /// `spreading_activation` call rather than cached on the struct: `entities`
+    /// and `relations` are public fields, and `schema.rs`'s deserialization
+    /// path pushes into them directly (bypassing `add_entity`/`add_relation`),
+    /// so a struct-cached index could go stale. Building it once per call
+    /// still turns an O(V·R) (or O(steps·V·R)) traversal into O(V+R) (or
+    /// O(steps·(V+E))), since the old code repeated the O(R) relation scan
+    /// once per visited node instead of once per call.
+    fn build_adjacency(&self) -> (HashMap<u64, usize>, HashMap<u64, Vec<(u64, f32)>>) {
+        let mut entity_index: HashMap<u64, usize> = HashMap::with_capacity(self.entities.len());
+        for (i, e) in self.entities.iter().enumerate() {
+            entity_index.insert(e.id, i);
+        }
+
+        // Note: a self-loop relation (src == tgt) contributes a single
+        // neighbour entry, not two, matching the if/else-if (not two
+        // independent ifs) structure this replaces — otherwise a self-loop
+        // would be double-counted by `spreading_activation`.
+        let mut adjacency: HashMap<u64, Vec<(u64, f32)>> =
+            HashMap::with_capacity(self.relations.len());
+        for r in &self.relations {
+            adjacency.entry(r.src).or_default().push((r.tgt, r.weight));
+            if r.tgt != r.src {
+                adjacency.entry(r.tgt).or_default().push((r.src, r.weight));
+            }
+        }
+
+        (entity_index, adjacency)
+    }
+
     // -----------------------------------------------------------------------
     // Graph traversal: BFS neighbors
     // -----------------------------------------------------------------------
@@ -337,6 +378,8 @@ impl KnowledgeCache {
     /// together with their discovered depth.  The seed entity itself is NOT
     /// included.  Traversal follows both outgoing and incoming relation edges.
     pub fn bfs_neighbors(&self, entity_id: u64, max_depth: usize) -> Vec<(Entity, usize)> {
+        let (entity_index, adjacency) = self.build_adjacency();
+
         let mut visited: HashSet<u64> = HashSet::new();
         let mut queue: VecDeque<(u64, usize)> = VecDeque::new();
         let mut results: Vec<(Entity, usize)> = Vec::new();
@@ -349,25 +392,15 @@ impl KnowledgeCache {
                 continue;
             }
 
-            // Collect neighbour IDs from outgoing and incoming edges.
-            let neighbours: Vec<u64> = self
-                .relations
-                .iter()
-                .filter_map(|r| {
-                    if r.src == current_id {
-                        Some(r.tgt)
-                    } else if r.tgt == current_id {
-                        Some(r.src)
-                    } else {
-                        None
-                    }
-                })
-                .collect();
+            let Some(neighbours) = adjacency.get(&current_id) else {
+                continue;
+            };
 
-            for neighbour_id in neighbours {
+            for &(neighbour_id, _weight) in neighbours {
                 if visited.insert(neighbour_id)
-                    && let Some(entity) = self.get_entity(neighbour_id)
+                    && let Some(&idx) = entity_index.get(&neighbour_id)
                 {
+                    let entity = &self.entities[idx];
                     results.push((entity.clone(), depth + 1));
                     queue.push_back((neighbour_id, depth + 1));
                 }
@@ -439,6 +472,8 @@ impl KnowledgeCache {
         min_activation: f32,
         max_steps: usize,
     ) -> Vec<(u64, f32)> {
+        let (_entity_index, adjacency) = self.build_adjacency();
+
         let mut activation: HashMap<u64, f32> = HashMap::new();
 
         // Initialise seeds with activation 1.0.
@@ -462,16 +497,11 @@ impl KnowledgeCache {
 
             for (source_id, source_score) in current {
                 // Spread to all neighbours via outgoing and incoming edges.
-                for rel in &self.relations {
-                    let neighbour_id = if rel.src == source_id {
-                        rel.tgt
-                    } else if rel.tgt == source_id {
-                        rel.src
-                    } else {
-                        continue;
-                    };
-
-                    let delta = source_score * rel.weight * decay_factor;
+                let Some(neighbours) = adjacency.get(&source_id) else {
+                    continue;
+                };
+                for &(neighbour_id, weight) in neighbours {
+                    let delta = source_score * weight * decay_factor;
                     if delta >= min_activation {
                         *activation.entry(neighbour_id).or_insert(0.0) += delta;
                         any_spread = true;

crates/clawhdf5-agent/src/provenance.rs

@@ -1,31 +1,31 @@
 //! Memory provenance tracking and integrity verification.
 //!
 //! Records the origin, authorship, and a content hash of every memory chunk
-//! so the system can detect *accidental* corruption and trace data lineage.
-//! The hash is unkeyed (see [`fnv1a_64`]) — this is not a tamper-evidence or
-//! authenticity guarantee.
+//! so the system can detect content corruption and trace data lineage. The
+//! hash is a SHA-256 digest (see [`hash_content`]), computed via
+//! [`clawhdf5_format::provenance::sha256_hex`]. It is still **unkeyed** — an
+//! actor able to overwrite the stored chunk can also recompute and overwrite
+//! the stored hash alongside it, so this is not an authenticity guarantee
+//! against that threat. What SHA-256 does provide over a fast non-cryptographic
+//! hash (the previous FNV-1a implementation) is collision resistance: an
+//! adversary cannot cheaply craft *different* poisoned content that matches
+//! an already-recorded legitimate hash.
 
 use std::collections::HashMap;
 
 pub use crate::consolidation::MemorySource;
 
 // ---------------------------------------------------------------------------
-// Hash helper (std-only FNV-1a 64-bit)
+// Hash helper
 // ---------------------------------------------------------------------------
 
-/// Unkeyed, non-cryptographic FNV-1a hash for detecting accidental content
-/// corruption. It is trivially forgeable by anyone able to modify the stored
-/// data, since they can recompute and overwrite the stored hash alongside
-/// it — do not rely on this as a tamper-evidence or authenticity control.
-fn fnv1a_64(text: &str) -> u64 {
-    const OFFSET: u64 = 14_695_981_039_346_656_037;
-    const PRIME: u64 = 1_099_511_628_211;
-    let mut hash = OFFSET;
-    for byte in text.bytes() {
-        hash ^= byte as u64;
-        hash = hash.wrapping_mul(PRIME);
-    }
-    hash
+/// SHA-256 hex digest of `text`, used to detect content corruption/tampering.
+///
+/// Unkeyed: an actor able to modify the stored chunk can also recompute and
+/// overwrite the stored hash, so a match is not proof of authenticity — only
+/// that the stored chunk and stored hash are mutually consistent.
+fn hash_content(text: &str) -> String {
+    clawhdf5_format::provenance::sha256_hex(text.as_bytes())
 }
 
 // ---------------------------------------------------------------------------
@@ -57,8 +57,8 @@ pub struct MemoryProvenance {
     pub created_by: String,
     /// Unix timestamp (seconds) of creation.
     pub created_at: f64,
-    /// FNV-1a 64-bit hash of the chunk text for integrity checking.
-    pub content_hash: u64,
+    /// SHA-256 hex digest of the chunk text for integrity checking.
+    pub content_hash: String,
     pub session_id: String,
     pub verified: bool,
 }
@@ -78,7 +78,7 @@ impl MemoryProvenance {
             source,
             created_by: created_by.into(),
             created_at,
-            content_hash: fnv1a_64(chunk),
+            content_hash: hash_content(chunk),
             session_id: session_id.into(),
             verified: false,
         }
@@ -121,13 +121,16 @@ impl ProvenanceStore {
     /// Re-hash `current_chunk` and compare against the stored hash.
     /// Returns `true` if the content matches (integrity intact).
     ///
-    /// This only detects accidental corruption: the hash is unkeyed, so an
-    /// actor able to modify the stored chunk can also recompute and
-    /// overwrite the stored hash. Do not treat a `true` result as proof the
-    /// data hasn't been tampered with.
+    /// The hash is unkeyed, so an actor able to modify the stored chunk can
+    /// also recompute and overwrite the stored hash. Do not treat a `true`
+    /// result as proof of authenticity against that threat — but unlike a
+    /// non-cryptographic hash, a `false` result reliably indicates that the
+    /// content does not match what was recorded, since SHA-256 makes it
+    /// computationally infeasible to craft different content that collides
+    /// with a specific existing digest.
     pub fn verify_integrity(&self, record_id: u64, current_chunk: &str) -> bool {
         match self.records.get(&record_id) {
-            Some(p) => p.content_hash == fnv1a_64(current_chunk),
+            Some(p) => p.content_hash == hash_content(current_chunk),
             None => false,
         }
     }
@@ -241,22 +244,32 @@ mod tests {
         1_700_000_000.0
     }
 
-    // --- fnv1a_64 ---
+    // --- hash_content ---
 
     #[test]
     fn hash_deterministic() {
-        assert_eq!(fnv1a_64("hello"), fnv1a_64("hello"));
+        assert_eq!(hash_content("hello"), hash_content("hello"));
     }
 
     #[test]
     fn hash_different_inputs() {
-        assert_ne!(fnv1a_64("hello"), fnv1a_64("world"));
+        assert_ne!(hash_content("hello"), hash_content("world"));
     }
 
     #[test]
     fn hash_empty() {
-        // Should not panic
-        let _ = fnv1a_64("");
+        // Should not panic, and should match the well-known SHA-256 of the empty string.
+        assert_eq!(
+            hash_content(""),
+            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
+        );
+    }
+
+    #[test]
+    fn hash_is_sha256_hex() {
+        let h = hash_content("clawhdf5");
+        assert_eq!(h.len(), 64);
+        assert!(h.chars().all(|c| c.is_ascii_hexdigit()));
     }
 
     // --- MemorySource Display ---
@@ -275,7 +288,7 @@ mod tests {
     #[test]
     fn provenance_new_hashes_chunk() {
         let p = MemoryProvenance::new(1, MemorySource::User, "agent-1", ts(), "hello", "s1");
-        assert_eq!(p.content_hash, fnv1a_64("hello"));
+        assert_eq!(p.content_hash, hash_content("hello"));
         assert!(!p.verified);
     }
 

research/IMPLEMENTATION_BRIEF.md

@@ -0,0 +1,176 @@
+# ClawHDF5 — Performance / Security / Provenance Implementation Brief
+
+**Date:** 2026-08-16
+**Scope:** Follow-up hardening pass on top of the already-shipped Tier 1-4 work
+(see `ROADMAP.md` "What's Next" and `IMPROVEMENT_LOG.md`). This brief covers
+only items verified against the current repo state at commit `b2dce41` that
+were **not** already addressed by prior tiers.
+
+## Method
+
+Read `ROADMAP.md`, `IMPROVEMENT_LOG.md`, `IMPROVEMENT_SCAN.md`, and
+`CLAUDE.md` first to avoid re-proposing work already merged (WAL CRC32,
+bounds-check audit + fuzz target, HNSW `prune_connections` parallelism,
+Android JNI length validation, `workspace.dependencies` hoisting, etc. are
+all already done — see those files for the full list).
+
+Then manually audited:
+- `crates/clawhdf5-format/src/{chunked_read,data_read}.rs` — bounds-check
+  spot audit (sampled `ensure_len` call sites around every raw slice index).
+  **Result: no new gaps found.** Every raw `file_data[a..b]` site sampled is
+  preceded by an `ensure_len`/`read_offset` overflow-checked bound. The prior
+  Tier 4a pass already closed this out.
+- `crates/clawhdf5-agent/src/provenance.rs` — memory record integrity →
+  **gap found**, see INT-01.
+- `crates/clawhdf5-agent/src/knowledge.rs` — knowledge-graph traversal →
+  **gap found**, see INT-02.
+- `crates/clawhdf5-agent/src/bm25.rs` — already has cached IDF, sorted
+  postings, WAND early termination. No changes proposed.
+- `crates/clawhdf5-ann/src/hnsw.rs` — build-time parallelism already scoped
+  to `prune_connections` per Tier 4c; the outer insert loop is flagged in
+  ROADMAP as needing its own correctness-sensitive design pass, out of scope
+  here.
+
+## INT-01 — Harden agent memory provenance hash from FNV-1a to SHA-256
+
+**File:** `crates/clawhdf5-agent/src/provenance.rs`
+**Category:** Security / Provenance
+**Status:** Implemented this pass.
+
+### Problem
+
+`MemoryProvenance::content_hash` used an unkeyed 64-bit FNV-1a hash
+(`fnv1a_64`) to detect corruption of stored agent-memory chunks. FNV-1a is
+a fast non-cryptographic hash with no collision resistance: an adversary
+attempting to plant poisoned/tampered memory content that still matches a
+previously-recorded or expected hash value only needs to find *any* input
+producing the same 64-bit output, which is computationally cheap for
+FNV-1a (no preimage or collision resistance guarantees at all). Given
+Track 5 of `ROADMAP.md` explicitly claims "poisoning resistance" and
+`verify_integrity()` is the one function whose entire job is to catch
+tampered memory content, using a hash with no collision resistance
+undermines that guarantee in a way that is easy to miss (the doc comment
+already, correctly, disclaims *authenticity* — i.e. it never claimed to
+stop an attacker who can also rewrite the stored hash — but it did not
+protect against a weaker, still-relevant attack: crafting *different*
+poisoned content that collides with an already-recorded legitimate hash).
+
+Separately, `clawhdf5-format` already ships a mature, default-on
+`provenance` feature (`crates/clawhdf5-format/src/provenance.rs`) with a
+`sha256_hex()` helper built on the `sha2` crate, used for on-disk dataset
+provenance attributes. `clawhdf5-agent` already depends on
+`clawhdf5-format` with default features enabled, so `sha256_hex` was
+already reachable with **zero new dependencies**.
+
+### Fix implemented
+
+- `MemoryProvenance::content_hash` changed from `u64` to `String` (lowercase
+  hex SHA-256 digest), computed via `clawhdf5_format::provenance::sha256_hex`.
+- `ProvenanceStore::verify_integrity` now compares SHA-256 hex digests.
+- Removed the local `fnv1a_64` helper from `provenance.rs` (no longer used
+  there — `clawhdf5-agent/src/multimodal.rs` keeps its own independent
+  `fnv1a_64` for `MediaRef` checksums, which is a content-identity/dedup key,
+  not a security/integrity control, so it is intentionally left unchanged
+  and out of scope for this item).
+- Updated the module-level and per-item doc comments to keep the existing,
+  correct disclaimer: this is still an **unkeyed** hash, so it is still not
+  an authenticity/tamper-*evidence* guarantee against an attacker who can
+  rewrite the stored hash alongside the content. What changed is that it is
+  no longer trivially *collidable*, which was the concrete, fixable gap.
+- Updated all existing unit tests in `provenance.rs` for the new `String`
+  hash type; behavior (which records match/mismatch) is unchanged.
+
+`MemoryProvenance` and `ProvenanceStore` are only used within
+`clawhdf5-agent` itself (not serialized to the HDF5 format, not consumed by
+other crates), so this is a self-contained, non-breaking-to-other-crates
+change verified by `grep -r MemoryProvenance crates/`.
+
+## INT-02 — Knowledge-graph traversal: replace O(V·R) relation scans with a per-call adjacency index
+
+**File:** `crates/clawhdf5-agent/src/knowledge.rs`
+**Category:** Performance
+**Status:** Implemented this pass.
+
+### Problem
+
+`KnowledgeCache::bfs_neighbors` and `KnowledgeCache::spreading_activation`
+are the core traversal primitives behind Track 1 (BFS neighbors, subgraph
+extraction) and Track 3 (graph-aware re-ranking) of the agent memory
+system. Both did a **full linear scan over `self.relations`** for every
+node processed:
+
+- `bfs_neighbors`: for every entity dequeued from the BFS frontier, it
+  scanned the entire `relations: Vec<Relation>` looking for edges touching
+  that entity — O(V·R) instead of O(V+E). It also called
+  `self.get_entity(neighbour_id)`, itself an O(n) linear scan over
+  `entities: Vec<Entity>`, once per newly-discovered neighbour.
+- `spreading_activation`: for every activated node in every propagation
+  step, it likewise scanned all of `self.relations` — O(steps·V·R).
+- `get_subgraph` calls `bfs_neighbors` once per seed, compounding the cost.
+
+For a knowledge graph with thousands of entities/relations (the scale this
+project's own benchmarks target — see `BENCHMARKS.md`), this is
+quadratic-ish behavior in traversal-heavy paths (`get_entity_context`,
+hybrid retrieval re-ranking that pulls graph context) that only gets worse
+as agent memory accumulates over long sessions.
+
+### Fix implemented
+
+Added a private helper, `KnowledgeCache::build_adjacency`, that builds, in
+one O(V+R) pass:
+- `entity_index: HashMap<u64, usize>` — entity id → index into `entities`.
+- `adjacency: HashMap<u64, Vec<u64>>` — entity id → neighbour ids (both
+  outgoing and incoming edges).
+
+`bfs_neighbors` and `spreading_activation` now build this index **once at
+the top of the call** (not persisted as struct state — see rationale below)
+and use it for O(1) neighbour/entity lookups inside the traversal loop,
+changing the complexity to O(V+E) per call for BFS and O(steps·(V+E)) for
+spreading activation.
+
+**Why not a persistent index on the struct:** `entities`/`relations` are
+public fields, and `crates/clawhdf5-agent/src/schema.rs` (deserialization
+path, loading a persisted knowledge graph back from HDF5) pushes directly
+into `cache.entities`/`cache.relations` rather than going through
+`add_entity`/`add_relation`. A struct-level cached index would silently go
+stale on that path. Building the index fresh at the top of each traversal
+call is O(V+R) — the same asymptotic cost as the scan it replaces would be
+for a *single* node — so it turns what was an O(V·R)-or-worse *whole
+traversal* into an O(V+R) traversal, with no risk of a stale-index
+correctness bug and no change to the existing public API or struct layout.
+`get_entity`, `get_relations_from`, `get_relations_to` are left as-is
+(still O(n)/O(R)): they're public API used elsewhere as one-off lookups,
+not inside a per-node hot loop, so indexing them is lower value and was
+left out of scope to keep this change minimal and low-risk.
+
+Existing tests (`test_bfs_neighbors_*`, `test_get_subgraph_*`,
+`test_spreading_activation_*`) exercise correctness and were not modified —
+they pass unchanged, confirming the traversal results are identical to the
+pre-change O(V·R) implementation.
+
+## Deferred / not implemented this pass
+
+Listed for a future pass — investigated but out of scope for this brief's
+budget, or blocked on a larger design decision already flagged upstream:
+
+- **HNSW outer insert-loop parallelism** — `ROADMAP.md` already flags this
+  as needing "its own dedicated design pass" before parallelizing; not
+  attempted here to avoid a correctness-sensitive change without that design
+  work.
+- **WAL per-entry format redesign** (explicit length-prefix instead of
+  read-then-verify-CRC32) — `ROADMAP.md` already notes the current CRC32
+  trailer works and this would only be worth revisiting "if profiling shows
+  it matters"; no such profiling signal was found this pass.
+- **`get_entity`/`get_relations_from`/`get_relations_to` indexing** — would
+  further help `get_entity_context` and any other one-off caller, but is
+  lower value than the hot-loop fix in INT-02 and was left out to keep this
+  change minimal.
+
+## Verification performed
+
+- `cargo build --workspace --lib --bins` — clean before starting (baseline).
+- `cargo test --workspace` — run after implementing INT-01 and INT-02 (see
+  commit for pass/fail status).
+
+TASK: INT-01 — Harden agent memory provenance hash from FNV-1a to SHA-256
+TASK: INT-02 — Knowledge-graph traversal: per-call adjacency index instead of O(V·R) relation scans