Proof and Evidence Chain Technical Specification

Version: 1.0 Status: Implementation Ready Source: docs/product/advisories/14-Dec-2025 - Proof and Evidence Chain Technical Reference.md Last Updated: 2025-12-14

Executive Summary

This specification defines the implementation of a cryptographically verifiable proof chain that links SBOM components to VEX verdicts through signed evidence and reasoning statements. The system provides complete traceability from scan results to policy decisions with deterministic, auditable outputs.

Architecture Overview

┌─────────────────────────────────────────────────────────────────────────────────────┐
│                              PROOF CHAIN ARCHITECTURE                                │
├─────────────────────────────────────────────────────────────────────────────────────┤
│                                                                                     │
│  ┌─────────────┐   ┌─────────────┐   ┌─────────────┐   ┌─────────────┐             │
│  │   Scanner   │──►│   Evidence  │──►│  Reasoning  │──►│     VEX     │             │
│  │    SBOM     │   │  Statements │   │  Statements │   │   Verdicts  │             │
│  │ (CycloneDX) │   │             │   │             │   │             │             │
│  └─────────────┘   └─────────────┘   └─────────────┘   └─────────────┘             │
│         │                │                │                │                        │
│         │                │                │                │                        │
│         ▼                ▼                ▼                ▼                        │
│  ┌─────────────────────────────────────────────────────────────────────────────┐   │
│  │                          CONTENT-ADDRESSED IDs                               │   │
│  │  SBOMEntryID | EvidenceID | ReasoningID | VEXVerdictID | ProofBundleID      │   │
│  └─────────────────────────────────────────────────────────────────────────────┘   │
│                                        │                                            │
│                                        ▼                                            │
│  ┌─────────────────────────────────────────────────────────────────────────────┐   │
│  │                              PROOF SPINE                                     │   │
│  │  Merkle aggregation: merkle_root(SBOMEntryID, EvidenceID[], ReasoningID,    │   │
│  │                                  VEXVerdictID) = ProofBundleID              │   │
│  └─────────────────────────────────────────────────────────────────────────────┘   │
│                                        │                                            │
│                                        ▼                                            │
│  ┌─────────────────────────────────────────────────────────────────────────────┐   │
│  │                           DSSE ENVELOPES                                     │   │
│  │  - In-toto Statement/v1 format                                              │   │
│  │  - Signed by role-specific keys                                              │   │
│  │  - Predicate types: evidence.stella/v1, reasoning.stella/v1,                │   │
│  │                     cdx-vex.stella/v1, proofspine.stella/v1                 │   │
│  └─────────────────────────────────────────────────────────────────────────────┘   │
│                                        │                                            │
│                                        ▼                                            │
│  ┌─────────────────────────────────────────────────────────────────────────────┐   │
│  │                         TRUST ANCHORS                                        │   │
│  │  - Per-dependency anchor (PURL pattern matching)                            │   │
│  │  - Allowed key IDs for verification                                          │   │
│  │  - Key rotation with historical validity                                     │   │
│  └─────────────────────────────────────────────────────────────────────────────┘   │
│                                        │                                            │
│                                        ▼                                            │
│  ┌─────────────────────────────────────────────────────────────────────────────┐   │
│  │                      REKOR TRANSPARENCY LOG                                  │   │
│  │  - Inclusion proofs for all DSSE envelopes                                  │   │
│  │  - Checkpoint verification                                                   │   │
│  │  - Offline verification support                                              │   │
│  └─────────────────────────────────────────────────────────────────────────────┘   │
│                                                                                     │
└─────────────────────────────────────────────────────────────────────────────────────┘

Content-Addressed Identifier System

ID Formats

Canonicalization Rules

1. UTF-8 encoding for all strings
2. Sorted keys (lexicographic, case-sensitive)
3. No insignificant whitespace
4. No trailing commas
5. Numbers in shortest form
6. Deterministic array ordering (by semantic key: bom-ref, purl)

Canonicalization Versioning

Content-addressed identifiers embed a canonicalization version marker to prevent hash collisions when the canonicalization algorithm evolves. This ensures that:

• Forward compatibility: Future algorithm changes won’t invalidate existing hashes.
• Verifier clarity: Verifiers know exactly which algorithm to use.
• Auditability: Hash provenance is cryptographically bound to algorithm version.

Version Marker Format:

{
  "_canonVersion": "stella:canon:v1",
  "sbomEntryId": "...",
  "vulnerabilityId": "..."
}

V1 Algorithm Specification:

Version Detection:

// Detect if canonical JSON includes version marker
public static bool IsVersioned(ReadOnlySpan<byte> canonicalJson)
{
    return canonicalJson.Length > 20 &&
           canonicalJson.StartsWith("{\"_canonVersion\":"u8);
}

// Extract version from versioned canonical JSON
public static string? ExtractVersion(ReadOnlySpan<byte> canonicalJson)
{
    // Parse and return the _canonVersion value, or null if not versioned
}

Migration Strategy:

See also: Canonicalization Migration Guide

DSSE Predicate Types

1. Evidence Statement (evidence.stella/v1)

{
  "predicateType": "evidence.stella/v1",
  "predicate": {
    "source": "scanner/feed name",
    "sourceVersion": "tool version",
    "collectionTime": "2025-12-14T00:00:00Z",
    "sbomEntryId": "<SBOMEntryID>",
    "vulnerabilityId": "CVE-XXXX-YYYY",
    "rawFinding": "<pointer or data>",
    "evidenceId": "<EvidenceID>"
  }
}

Signer: Scanner/Ingestor key

2. Reasoning Statement (reasoning.stella/v1)

{
  "predicateType": "reasoning.stella/v1",
  "predicate": {
    "sbomEntryId": "<SBOMEntryID>",
    "evidenceIds": ["<EvidenceID>", ...],
    "policyVersion": "v2.3.1",
    "inputs": {
      "currentEvaluationTime": "2025-12-14T00:00:00Z",
      "severityThresholds": {...},
      "latticeRules": {...}
    },
    "intermediateFindings": {...},
    "reasoningId": "<ReasoningID>"
  }
}

Signer: Policy/Authority key

3. VEX Verdict Statement (cdx-vex.stella/v1)

{
  "predicateType": "cdx-vex.stella/v1",
  "predicate": {
    "sbomEntryId": "<SBOMEntryID>",
    "vulnerabilityId": "CVE-XXXX-YYYY",
    "status": "not_affected|affected|fixed|under_investigation",
    "justification": "vulnerable_code_not_in_execute_path",
    "policyVersion": "v2.3.1",
    "reasoningId": "<ReasoningID>",
    "vexVerdictId": "<VEXVerdictID>"
  }
}

Signer: VEXer/Vendor key

4. Proof Spine Statement (proofspine.stella/v1)

{
  "predicateType": "proofspine.stella/v1",
  "predicate": {
    "sbomEntryId": "<SBOMEntryID>",
    "evidenceIds": ["<ID1>", "<ID2>"],
    "reasoningId": "<ID>",
    "vexVerdictId": "<ID>",
    "policyVersion": "v2.3.1",
    "proofBundleId": "<ProofBundleID>"
  }
}

Signer: Authority key

5. Verdict Receipt Statement (verdict.stella/v1)

{
  "predicateType": "verdict.stella/v1",
  "predicate": {
    "graphRevisionId": "<GraphRevisionID>",
    "findingKey": {"sbomEntryId": "<ID>", "vulnerabilityId": "CVE-..."},
    "rule": {"id": "POLICY-RULE-123", "version": "v2.3.1"},
    "decision": {"status": "block|warn|pass", "reason": "..."},
    "inputs": {"sbomDigest": "sha256:...", "feedsDigest": "sha256:...", "policyDigest": "sha256:..."},
    "outputs": {"proofBundleId": "<ID>", "reasoningId": "<ID>", "vexVerdictId": "<ID>"},
    "createdAt": "2025-12-14T00:00:00Z"
  }
}

Signer: Authority key

6. SBOM Linkage Statement (sbom-linkage/v1)

{
  "predicateType": "https://stella-ops.org/predicates/sbom-linkage/v1",
  "predicate": {
    "sbom": {"id": "<sbomId>", "format": "CycloneDX", "specVersion": "1.6", ...},
    "generator": {"name": "StellaOps.Sbomer", "version": "x.y.z"},
    "generatedAt": "2025-12-14T00:00:00Z",
    "incompleteSubjects": [],
    "tags": {"tenantId": "...", "projectId": "...", "pipelineRunId": "..."}
  }
}

Signer: Generator key

7. Graph Root Statement (graph-root.stella/v1)

The Graph Root attestation provides tamper-evident commitment to graph analysis results (dependency graphs, call graphs, reachability graphs) by computing a Merkle root over canonicalized node and edge identifiers.

{
  "_type": "https://in-toto.io/Statement/v1",
  "subject": [
    {
      "name": "graph-root://<graphType>/<merkleRoot>",
      "digest": {
        "sha256": "<merkle-root-hex>"
      }
    }
  ],
  "predicateType": "https://stella-ops.org/predicates/graph-root/v1",
  "predicate": {
    "graphType": "DependencyGraph|CallGraph|ReachabilityGraph|...",
    "merkleRoot": "sha256:<hex>",
    "nodeCount": 1234,
    "edgeCount": 5678,
    "canonVersion": "stella:canon:v1",
    "inputs": {
      "sbomDigest": "sha256:<hex>",
      "analyzerDigest": "sha256:<hex>",
      "configDigest": "sha256:<hex>"
    },
    "createdAt": "2025-01-12T10:30:00Z"
  }
}

Signer: Graph Analyzer key

Supported Graph Types

Merkle Root Computation

The Merkle root is computed deterministically:

1. Canonicalize Node IDs: Sort all node identifiers lexicographically
2. Canonicalize Edge IDs: Sort all edge identifiers (format: {source}->{target})
3. Combine: Concatenate sorted nodes + sorted edges
4. Binary Tree: Build SHA-256 Merkle tree with odd-node duplication
5. Root: Extract 32-byte root as sha256:<hex>

Merkle Tree Structure:
        [root]
       /      \
    [h01]    [h23]
    /   \    /   \
  [n0] [n1] [n2] [n3]

Integration with Proof Spine

Graph root attestations can be referenced in proof spines:

{
  "predicateType": "proofspine.stella/v1",
  "predicate": {
    "sbomEntryId": "<SBOMEntryID>",
    "evidenceIds": ["<ID1>", "<ID2>"],
    "reasoningId": "<ID>",
    "vexVerdictId": "<ID>",
    "graphRootIds": ["<GraphRootID1>"],
    "policyVersion": "v2.3.1",
    "proofBundleId": "<ProofBundleID>"
  }
}

Verification Steps

1. Parse DSSE envelope and verify signature against allowed keys
2. Extract predicate and Merkle root
3. Re-canonicalize provided node/edge IDs using stella:canon:v1
4. Recompute Merkle root from canonicalized inputs
5. Compare computed root to claimed root
6. If Rekor entry exists, verify transparency log inclusion

Database Schema

Tables

API Endpoints

CLI Exit Codes

Verification Pipeline

The 13-step verification algorithm:

1. Resolve SBOMEntryID → TrustAnchorID
2. Fetch spine and trust anchor
3. Verify spine DSSE signature against TrustAnchor.allowedKeyids
4. Verify VEX DSSE signature
5. Verify reasoning DSSE signature
6. Verify evidence DSSE signatures
7. Recompute EvidenceIDs from stored canonical evidence
8. Recompute ReasoningID from reasoning
9. Recompute VEXVerdictID from VEX body
10. Recompute ProofBundleID (merkle root) from above
11. Compare all computed IDs to stored IDs
12. If using Rekor: verify log inclusion proof
13. Emit Receipt

Key Rotation

Process

1. Add new key to TrustAnchor.allowedKeyids
2. Transition period: both keys valid
3. Optionally revoke old key (moves to revokedKeys)
4. Publish key material via attestation feed

Invariants

• Never mutate old DSSE envelopes
• Revoked keys remain valid for proofs signed before revocation
• All key changes are audited

Implementation Sprints

Related Documents

• Master Sprint Plan
• Content-Addressed IDs Sprint
• DSSE Predicates Sprint
• Proof Spine Assembly Sprint
• API Surface Sprint
• Database Schema Sprint
• CLI Integration Sprint
• Key Rotation Sprint
• Graph Root Attestation
• Attestor Architecture
• Signer Architecture
• Database Specification

Cryptographic Profiles

Determinism Constraints

Non-Negotiable Invariants

1. Immutability: DSSE envelopes are append-only
2. Determinism: Same inputs → same outputs
3. Traceability: Every verdict traceable to evidence
4. Least Trust: Explicit trust via TrustAnchors only
5. Backward Compatibility: New code verifies old proofs

Temporal Handling

• UTC ISO-8601 only
• No local time
• Timestamps only when semantically required
• Derivation from content preferred over wall-clock time

Document Version: 1.0 Target Platform: .NET 10, PostgreSQL ≥16, Angular v17