RichGraph v1 — Reachability Graph Schema

Contract ID: CONTRACT-RICHGRAPH-V1-015 Status: Published  ·  Version: 1.0.0  ·  Published: 2025-12-05 Owners: Scanner Guild, Signals Guild, BE-Base Platform Guild

Overview

richgraph-v1 is the canonical schema Stella Ops uses for function-level reachability analysis: the call graph that lets the scanner prove whether a vulnerable symbol is actually reachable from an application’s entry points. This contract defines the data model, hash algorithms, determinism rules, content- addressable storage (CAS) layout, and DSSE attestation that together make a reachability claim reproducible and verifiable.

Audience: engineers building or consuming reachability output — the Scanner reachability analyzer, the Signals runtime, symbol servers, and any service that stores, attests, or replays a reachability graph.

Schema Definition

richgraph-v1 Document Structure

{
  "schema": "richgraph-v1",
  "analyzer": {
    "name": "scanner.reachability",
    "version": "0.1.0",
    "toolchain_digest": "sha256:..."
  },
  "nodes": [
    {
      "id": "sym:java:base64url...",
      "symbol_id": "sym:java:base64url...",
      "lang": "java",
      "kind": "method",
      "display": "com.example.Foo.bar(String)",
      "code_id": "code:java:base64url...",
      "code_block_hash": "sha256:deadbeef...",
      "symbol": { "mangled": "_Z15ssl3_read_bytes", "demangled": "ssl3_read_bytes", "source": "DWARF", "confidence": 0.98 },
      "purl": "pkg:maven/com.example/foo@1.0.0",
      "build_id": "gnu-build-id:...",
      "symbol_digest": "sha256:...",
      "evidence": ["import", "disasm"],
      "attributes": {"key": "value"}
    }
  ],
  "edges": [
    {
      "from": "sym:java:...",
      "to": "sym:java:...",
      "kind": "call",
      "purl": "pkg:maven/com.example/bar@2.0.0",
      "symbol_digest": "sha256:...",
      "confidence": 0.9,
      "evidence": ["reloc", "runtime"],
      "candidates": []
    }
  ],
  "roots": [
    {
      "id": "sym:java:...",
      "phase": "runtime",
      "source": "main"
    }
  ]
}

Node Schema

Edge Schema

Gate Schema (optional)

When gates is present, each element follows:

Root Schema

Hash Algorithms

Summary

Graph Hash (BLAKE3-256)

The graph hash provides content-addressable identification:

graph_hash = "blake3:" + hex(BLAKE3-256(canonical_json_bytes))

Rationale: BLAKE3 chosen for:

• Speed (3x+ faster than SHA-256 on modern CPUs)
• Parallelizable for large graphs
• Cryptographic security equivalent to SHA-256
• Consistent with internal content-addressing standard

Symbol Digest (SHA-256)

Symbol digests use SHA-256 for interoperability:

symbol_digest = "sha256:" + hex(SHA-256(utf8(symbol_id)))

SymbolID and CodeID Fragments

Internal fragments use SHA-256 with base64url encoding:

fragment = base64url_no_pad(SHA-256(utf8(canonical_tuple)))
symbol_id = "sym:{lang}:{fragment}"
code_id = "code:{lang}:{fragment}"

Determinism Rules

All outputs must be reproducible. The Trimmed() operation enforces canonical ordering:

Ordering Rules

1. Nodes: Sort by id (ordinal string comparison)
2. Edges: Sort by (from, to, kind) in that order (ordinal)
3. Roots: Sort by id (ordinal)
4. Evidence arrays: Sort alphabetically (ordinal)
5. Candidates arrays: Sort alphabetically (ordinal)
6. Attributes objects: Sort keys alphabetically (ordinal)

Normalization Rules

1. Trim whitespace: All string values trimmed
2. Empty to null: Empty strings become null/omitted
3. Confidence clamping: Values clamped to [0.0, 1.0]
4. Default values:
   • kind defaults to "call" for edges
   • phase defaults to "runtime" for roots
   • analyzer.name defaults to "scanner.reachability"
   • analyzer.version defaults to "0.1.0"

JSON Serialization

• No indentation (compact JSON)
• Keys sorted alphabetically at all levels
• No trailing whitespace
• UTF-8 encoding
• No BOM

CAS Layout

Graph Storage

cas://reachability/graphs/{blake3}          # Graph body (canonical JSON)
cas://reachability/graphs/{blake3}.dsse     # DSSE envelope

Edge Bundle Storage (Optional)

For runtime hits, init-array roots, and contested edges:

cas://reachability/edges/{graph_hash}/{bundle_id}       # Edge bundle body
cas://reachability/edges/{graph_hash}/{bundle_id}.dsse  # DSSE envelope

Metadata Storage

{output_root}/reachability_graphs/{analysis_id}/richgraph-v1.json  # Graph body
{output_root}/reachability_graphs/{analysis_id}/meta.json          # Metadata

meta.json structure:

{
  "schema": "richgraph-v1",
  "graph_hash": "blake3:...",
  "files": [
    {"path": "...", "hash": "blake3:..."}
  ]
}

DSSE Integration

Predicate Types

Graph DSSE (Mandatory)

Every richgraph-v1 document requires a DSSE envelope:

{
  "payloadType": "application/vnd.stellaops.graph+json",
  "payload": "<base64(canonical_graph_json)>",
  "signatures": [...]
}

Subject: cas://reachability/graphs/{blake3}

Rekor Integration

• Graph DSSE: Always publish to Rekor (or mirror when offline)
• Edge Bundle DSSE: Optional, capped at configurable limit per graph

SymbolID Construction

Format

sym:{lang}:{base64url_sha256_no_pad}

Per-Language Canonical Tuples

CodeID Construction

Format

code:{lang}:{base64url_sha256_no_pad}

Use Cases

CodeIDs provide stable identifiers when symbol names are unavailable:

• Stripped binaries: code:binary:{hash} from {format}\0{file_hash}\0{addr}\0{length}\0{section}\0{code_block_hash}
• .NET modules: code:dotnet:{hash} from {assembly}\0{module}\0{mvid}
• Node packages: code:node:{hash} from {package}\0{entry_path}

Implementation Status

Existing Implementation

Required Changes

Decision Checklist

This contract resolves the following decisions from the 2025-12-02 alignment meeting:

Validation Rules

Schema Validation

1. schema must equal "richgraph-v1"
2. nodes array must not be empty
3. All node id values must be unique
4. All edge from/to must reference existing nodes
5. All root id values must reference existing nodes
6. confidence must be in range [0.0, 1.0]

Hash Validation

1. graph_hash must match BLAKE3-256 of canonical JSON
2. symbol_digest must match SHA-256 of symbol_id
3. SymbolID fragments must match SHA-256 of canonical tuple

Migration Path

From Current Implementation

1. RichGraphWriter: Replace ComputeSha256 with ComputeBlake3 for graph hash
2. meta.json: Update hash format from sha256: to blake3:
3. Existing graphs: Recompute hashes on next scan (no migration needed)

Compatibility

• Symbol digests remain SHA-256 (no change)
• SymbolID format unchanged
• CodeID format unchanged

Reference Implementation

Canonical JSON Writer

// From RichGraph.cs - Trimmed() enforces canonical ordering
public RichGraph Trimmed()
{
    var nodes = Nodes.OrderBy(n => n.Id, StringComparer.Ordinal).ToList();
    var edges = Edges
        .OrderBy(e => e.From, StringComparer.Ordinal)
        .ThenBy(e => e.To, StringComparer.Ordinal)
        .ThenBy(e => e.Kind, StringComparer.Ordinal)
        .ToList();
    var roots = Roots.OrderBy(r => r.Id, StringComparer.Ordinal).ToList();
    return this with { Nodes = nodes, Edges = edges, Roots = roots };
}

BLAKE3 Graph Hash (Required Update)

// Replace in RichGraphWriter.cs
private static string ComputeBlake3(byte[] bytes)
{
    using var blake3 = Blake3.Hasher.New();
    blake3.Update(bytes);
    var hash = blake3.Finalize();
    return "blake3:" + Convert.ToHexString(hash.AsSpan()).ToLowerInvariant();
}

Related Contracts

• Sealed Mode - Air-gap operation with CAS
• Mirror Bundle - Offline transport format
• Verification Policy - DSSE verification rules
• Scanner Surface - Surface analysis framework

Changelog