# Proof Graph (Node/Edge Types for Evidence Lineage and Integrity)

## Module
Attestor

## Status
VERIFIED

## Description
In-memory proof graph service with typed nodes (Artifact, SbomDocument, DsseEnvelope, RekorEntry, VexStatement, Subject) and edges (DESCRIBED_BY, ATTESTED_BY, WRAPPED_BY, etc.) supporting mutation, queries, paths, and subgraph extraction.

## Implementation Details
- **In-Memory Proof Graph Service**: `src/Attestor/__Libraries/StellaOps.Attestor.ProofChain/Graph/InMemoryProofGraphService.cs` -- core graph service with partials:
  - `.Mutation` -- add/remove nodes and edges, update metadata.
  - `.Queries` -- query nodes by type, find paths, search by content hash.
  - `.Subgraph` -- extract subgraphs rooted at a specific node.
- **Node Types**: `Graph/ProofGraphNodeType.cs` -- Evidence, Verdict, Policy, Artifact (representing SbomDocument, DsseEnvelope, RekorEntry, VexStatement, etc.).
- **Edge Types**: `Graph/ProofGraphEdgeType.cs` -- relationship types (DependsOn, Produces, Validates, DescribedBy, AttestedBy, WrappedBy, etc.).
- **Graph Node**: `Graph/ProofGraphNode.cs` -- node with content-addressed ID, type, metadata, and content hash.
- **Graph Edge**: `Graph/ProofGraphEdge.cs` -- directed edge with source, target, type, and optional metadata.
- **Graph Path**: `Graph/ProofGraphPath.cs` -- ordered sequence of nodes representing a traversal path.
- **Subgraph**: `Graph/ProofGraphSubgraph.cs` -- extracted subgraph with nodes and edges for a specific evidence lineage.
- **Content-Addressed IDs**: `Identifiers/ContentAddressedIdGenerator.Graph.cs` -- generates graph-scoped content-addressed node/edge IDs.
- **Tests**: `__Tests/StellaOps.Attestor.ProofChain.Tests/ProofGraphTests.cs`

## E2E Test Plan
- [ ] Create a proof graph with Artifact, Evidence, Reasoning, and Verdict nodes and verify all node types are stored
- [ ] Add edges with different `ProofGraphEdgeType` values and verify edge traversal returns correct neighbors
- [ ] Query nodes by type via `.Queries` and verify filtering works (e.g., all Evidence nodes)
- [ ] Find the shortest path between a Verdict and an Evidence node and verify the `ProofGraphPath` is correct
- [ ] Extract a subgraph rooted at a Verdict via `.Subgraph` and verify it includes all Evidence and Reasoning descendants
- [ ] Add a node via `.Mutation`, then remove it, and verify cascading edge removal
- [ ] Verify content-addressed node IDs: same content produces the same node ID across insertions
- [ ] Build a complex graph with cycles (e.g., mutual dependencies) and verify query operations handle cycles correctly

## Verification

| Check | Result |
|-------|--------|
| Tier 0 - Source Verification | PASS |
| Tier 1 - Build + Code Review | PASS |
| Tier 2 - Behavioral Verification | PASS |
| Verified Date | 2026-02-13 |
| Run ID | run-001 |