Determinism Specification

Audience: engineers building or verifying any service that produces verdicts, evidence, or attestations. Status: Living document · Version: 1.0 · Created: 2025-12-26 Owners: Policy Guild, Platform Guild Related: Data flows · CONSOLIDATED – Deterministic Evidence and Verdict Architecture (archived advisory)

Overview

This specification defines the determinism guarantees for Stella Ops verdict computation, including digest algorithms, canonicalization rules, and migration strategies. Every service that produces or verifies verdicts MUST comply with this specification.

The contract is simple: identical inputs, pinned and content-addressed, always produce byte-identical canonical outputs and therefore identical digests — across machines, architectures, and runs. The sections below define how that is achieved (canonicalization, NFC normalization, version markers), how it is enforced (compile-time analyzer, runtime guard), and how it is verified (replay, golden, chaos, and cross-platform tests).

Reconciliation note (verify against src/): This document was reconciled against the implementation in src/Attestor/__Libraries/StellaOps.Attestor.ProofChain, src/Policy, src/__Libraries/StellaOps.Canonical.Json, src/__Analyzers/StellaOps.Determinism.Analyzers, and src/Replay. Several identifier generators that earlier drafts attributed to single “…IdGenerator” classes are in reality methods on a shared ContentAddressedIdGenerator (Attestor) or live in different modules; some named types do not exist at all. Where a type is not yet implemented it is flagged inline as NOT IMPLEMENTED or Draft/roadmap. When this doc and the code disagree, the code (src/) wins.

1. Digest Algorithms

1.1 VerdictId (delta verdicts)

Purpose: Uniquely identifies a delta-gate verdict computation result.

Algorithm:

VerdictId = "verdict:sha256:" + SHA256_hex(CanonicalJson(verdict_payload))

Input Structure (the payload actually serialized by the implementation):

{
  "_canonVersion": "stella:canon:v1",
  "appliedExceptions": ["..."],
  "blockingDrivers": [ { "type": "...", "severity": "...", "description": "...", "cveId": "...", "purl": "..." } ],
  "deltaId": "...",
  "gateLevel": "...",
  "warningDrivers": [ ... ]
}

Drivers are sorted by (Type, CveId, Purl, Severity) (Ordinal) and appliedExceptions is sorted Ordinal before hashing; serialization uses camelCase with the _canonVersion marker prepended.

Implementation: StellaOps.Policy.Deltas.VerdictIdGenerator (interface IVerdictIdGenerator) at src/Policy/__Libraries/StellaOps.Policy/Deltas/VerdictIdGenerator.cs.

Reconciliation: There is no VerdictIdGenerator under StellaOps.Attestor.ProofChain.Identifiers. The Attestor ProofChain layer instead exposes VexVerdictId (a content-addressed sha256:… record produced by ContentAddressedIdGenerator.ComputeVexVerdictId, hashing a versioned VexPredicate). The evidence_refs / explanations / risk_score / status / unknowns_count payload shape shown in earlier drafts is not what the current code hashes and has been replaced with the real delta-verdict payload above.

1.2 EvidenceId

Purpose: Uniquely identifies an evidence predicate (the structured evidence record, e.g. SBOM/VEX/reasoning attestation input).

Algorithm:

EvidenceId = SHA256(CanonicalizeWithVersion(EvidencePredicate { EvidenceId = null }, "stella:canon:v1"))

The generator nulls the self-referential EvidenceId field, then RFC 8785-canonicalizes the predicate with the _canonVersion marker before hashing. The result is wrapped in a sha256:-prefixed EvidenceId record.

Notes:

• For structured evidence predicates: hash the versioned canonical JSON as above (this is the implemented path).
• For raw SBOM JSON bytes: ContentAddressedIdGenerator.ComputeSbomDigest returns sha256: + SHA-256 of the un-versioned canonical JSON.
• For multi-leaf proof bundles: ComputeProofBundleId computes a Merkle root over (SbomEntryId, sorted EvidenceIds, ReasoningId, VexVerdictId).

Implementation: StellaOps.Attestor.ProofChain.Identifiers.ContentAddressedIdGenerator.ComputeEvidenceId (returns EvidenceId) at src/Attestor/__Libraries/StellaOps.Attestor.ProofChain/Identifiers/.

Reconciliation: There is no standalone EvidenceIdGenerator class under ProofChain; EvidenceId is a record and the computation is a method on ContentAddressedIdGenerator. (A separate, unrelated StellaOps.Scanner.PatchVerification.Services.EvidenceIdGenerator exists for patch-verification scan IDs and is out of scope here.) The earlier “SHA256(raw_bytes)” formula is incorrect for the predicate path — the implementation hashes versioned canonical JSON, not raw bytes.

1.3 GraphRevisionId

Purpose: Uniquely identifies a call graph or reachability graph snapshot.

Algorithm (Merkle root over sorted leaves, not a single CanonicalJson hash):

GraphRevisionId = "grv_sha256:" + hex(MerkleRoot(
  [ ...SortOrdinal(nodeIds),
    ...SortOrdinal(edgeIds),
    policyDigest, feedsDigest, toolchainDigest, paramsDigest ]
))

Sorting Rules:

• Node IDs: lexicographic, Ordinal.
• Edge IDs: lexicographic, Ordinal (edge IDs are pre-encoded strings, not (source, target, kind) tuples sorted at hash time).
• The four pin digests (policy, feeds, toolchain, params) are trimmed and appended after the node/edge leaves.

The result carries a grv_sha256: prefix (a GraphRevisionId struct), not a bare sha256: digest.

Implementation: StellaOps.Attestor.ProofChain.Identifiers.ContentAddressedIdGenerator.ComputeGraphRevisionId (returns GraphRevisionId) at src/Attestor/__Libraries/StellaOps.Attestor.ProofChain/Identifiers/ContentAddressedIdGenerator.Graph.cs.

Reconciliation: No StellaOps.Scanner.CallGraph.Identifiers.GraphRevisionIdGenerator exists. The generator is in Attestor ProofChain, the algorithm is a Merkle root (so node/edge ordering and the policy/feeds/toolchain/params pins are bound into the digest), and the ID is grv_sha256:-prefixed.

1.4 ManifestId (Draft / roadmap)

Purpose: Uniquely identifies a scan/replay manifest (all inputs for an evaluation).

Intended Algorithm:

ManifestId = SHA256(CanonicalJson(manifest_payload))

Intended Input Structure:

{
  "_canonVersion": "stella:canon:v1",
  "engine_version": "1.0.0",
  "feeds_snapshot_sha256": "sha256:...",
  "options_hash": "sha256:...",
  "policy_bundle_sha256": "sha256:...",
  "policy_semver": "2025.12",
  "reach_subgraph_sha256": "sha256:...",
  "sbom_sha256": "sha256:...",
  "vex_set_sha256": ["sha256:..."]
}

Reconciliation — NOT IMPLEMENTED as a named generator. There is no StellaOps.Replay.Core.ManifestIdGenerator (nor any ManifestIdGenerator) in src/. The Replay module models manifests via ReplayManifest, InputManifestResolver, and the replay.schema.json / replay-export.schema.json schemas under src/__Libraries/StellaOps.Replay.Core and src/Replay/__Libraries/StellaOps.Replay.Core, and content-addresses inputs through CAS references rather than a single canonical “ManifestId” formula. The pinned-input set above is consistent with the Replay Contract (§4.1) but the specific digest field and generator class remain a design target, not shipped code.

1.5 PolicyBundleId (Draft / roadmap)

Purpose: Uniquely identifies a compiled policy bundle.

Intended Algorithm:

PolicyBundleId = SHA256(CanonicalJson({
  rules: SortedBy(rules, r => r.id),
  version: semver,
  lattice_config: {...}
}))

Reconciliation — NOT IMPLEMENTED as a named generator. There is no StellaOps.Policy.Engine.PolicyBundleIdGenerator (nor any PolicyBundleIdGenerator) in src/. Policy bundles are content-addressed elsewhere (e.g. policy_bundle_sha256 is carried as a pinned input in the Replay Contract, §4.1, and policy bundle digests flow through CAS), but the specific generator class and the {rules, version, lattice_config} payload shape above are a design target, not shipped code. Verify the actual bundle-digest path under src/Policy/ before relying on this section.

2. Canonicalization Rules

2.1 JSON Canonicalization (JCS - RFC 8785)

All JSON artifacts MUST be canonicalized before hashing or signing.

Rules:

1. Object keys sorted lexicographically (Ordinal comparison)
2. No whitespace between tokens
3. No trailing commas
4. UTF-8 encoding without BOM
5. Numbers: IEEE 754 double-precision, no unnecessary trailing zeros, no exponent for integers ≤ 10^21

Example:

// Before
{ "b": 1, "a": 2, "c": { "z": true, "y": false } }

// After (canonical)
{"a":2,"b":1,"c":{"y":false,"z":true}}

Implementation:

• StellaOps.Attestor.ProofChain.Json.Rfc8785JsonCanonicalizer (interface IJsonCanonicalizer) — the RFC 8785 canonicalizer used by the content-addressed ID generators, at src/Attestor/__Libraries/StellaOps.Attestor.ProofChain/Json/. Exposes Canonicalize(utf8Json) and CanonicalizeWithVersion(utf8Json, version).
• StellaOps.Canonical.Json.CanonJson (static helper) at src/__Libraries/StellaOps.Canonical.Json/ — convenience canonicalize/hash APIs (Canonicalize, CanonicalizeVersioned, Hash, HashVersioned, Sha256Hex, …) and the CanonVersion constants.

Reconciliation: There is no Rfc8785JsonCanonicalizer type inside the StellaOps.Canonical.Json namespace — that namespace’s entrypoint is the static CanonJson. The Rfc8785JsonCanonicalizer class lives in StellaOps.Attestor.ProofChain.Json. (A third library, StellaOps.Canonicalization, provides CanonicalJsonSerializer and stable converters for other call sites.)

2.2 String Normalization (Unicode NFC)

All string values MUST be normalized to Unicode NFC before canonicalization.

Why: Different Unicode representations of the same visual character produce different hashes.

Example:

// Before: é as e + combining acute (U+0065 U+0301)
// After NFC: é as single codepoint (U+00E9)

Implementation: NFC normalization is performed inside the canonicalizer: StellaOps.Attestor.ProofChain.Json.Rfc8785JsonCanonicalizer (see Rfc8785JsonCanonicalizer.StringNormalization.cs). When NFC normalization is enabled, each string value that is not already in NormalizationForm.FormC is normalized to it before being written.

Reconciliation: StellaOps.Resolver.NfcStringNormalizer is not in the active source tree — the StellaOps.Resolver library has been archived (src/__Libraries/_archived/StellaOps.Resolver/NfcStringNormalizer.cs). Do not reference it as a live implementation; the canonicalizer’s own NormalizeString is the current NFC path.

2.3 Version Markers

All canonical JSON MUST include a version marker for migration safety:

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

Current Version: stella:canon:v1

Migration Path: When canonicalization rules change:

1. Introduce new version marker (e.g., stella:canon:v2)
2. Support both versions during transition period
3. Re-hash legacy artifacts once, store old_hash → new_hash mapping
4. Deprecate old version after migration window

3. Determinism Guards

3.1 Forbidden Operations

The following operations are FORBIDDEN during verdict evaluation. The first four rows are enforced repo-wide by the determinism analyzer (§3.3); the remainder are convention enforced by review and tests.

3.2 Runtime Enforcement

DeterminismGuardService provides runtime enforcement. It wraps evaluation in a scope that pins the evaluation timestamp (via an injected TimeProvider) and collects DeterminismViolations; when enforcement is enabled, a violation at or above the configured severity throws DeterminismViolationException.

using StellaOps.Policy.Engine.DeterminismGuard;

var guard = new DeterminismGuardService(); // or with DeterminismGuardOptions

// Async guarded execution (extension method on DeterminismGuardService):
var result = await guard.ExecuteGuardedAsync(
    scopeId: "verdict-eval",
    evaluationTimestamp: pinnedTimestamp,
    evaluation: async scope =>
    {
        // scope.GetTimestamp() returns the fixed evaluation timestamp.
        // scope.ReportViolation(...) throws DeterminismViolationException
        // when enforcement is enabled and severity >= FailOnSeverity.
        return await evaluator.EvaluateAsync(manifest);
    });

The service also exposes AnalyzeSource(...) (static prohibited-pattern analysis), ValidateContext(...), and GetTimeProvider(fixedTimestamp) (a DeterministicTimeProvider).

Implementation: StellaOps.Policy.Engine.DeterminismGuard.DeterminismGuardService (with EvaluationScope, DeterminismGuardExtensions.ExecuteGuarded/ExecuteGuardedAsync, DeterministicTimeProvider, DeterminismViolationException) at src/Policy/StellaOps.Policy.Engine/DeterminismGuard/DeterminismGuardService.cs.

Reconciliation: The type is DeterminismGuardService, not DeterminismGuard, and it is invoked via CreateScope / the ExecuteGuarded[Async] extension methods — there is no static DeterminismGuard.ExecuteAsync(...). The file lives at src/Policy/StellaOps.Policy.Engine/..., not under src/Policy/__Libraries/StellaOps.Policy.Engine/....

3.3 Compile-Time Enforcement (Implemented)

A Roslyn analyzer flags determinism violations at compile time. It is implemented in src/__Analyzers/StellaOps.Determinism.Analyzers (NonDeterministicApiAnalyzer, CanonicalizationBoundaryAnalyzer) and ships at Error severity by default (isEnabledByDefault: true).

// This produces a compiler error (STELLA0111):
public Verdict Evaluate(Manifest m)
{
    var now = DateTime.Now; // STELLA0111: reads the wall clock; inject TimeProvider
    ...
}

Diagnostic IDs:

Suppression (intentional non-determinism): either a trailing per-call-site comment // Determinism:Allowed reason=... on the offending line, or [StellaOps.Determinism.DeterminismAllowed("reason")] on the enclosing method/type/field/property/assembly (attribute defined in src/__Libraries/StellaOps.Determinism.Abstractions/DeterminismAllowedAttribute.cs). A repo-wide conformance test (src/__Tests/architecture/StellaOps.Architecture.Tests/DeterminismCallSiteConformanceTests.cs) pins the production offender counts at 0 for all five IDs and rejects empty suppression reasons.

Reconciliation: This was previously documented as “Planned for Q1 2026” using a fictional STELLA001 diagnostic. The analyzer is implemented, enabled, and enforced at Error severity, and the real diagnostic IDs are STELLA0110–STELLA0114 (Sprints SPRINT_20260501_040 / _055).

4. Replay Contract

4.1 Requirements

For deterministic replay, the following MUST be pinned and recorded:

4.2 Replay Verification

// Load original manifest
var manifest = await manifestStore.GetAsync(manifestId);

// Replay evaluation
var replayVerdict = await engine.ReplayAsync(manifest);

// Verify determinism
var originalHash = CanonJson.Hash(originalVerdict);
var replayHash = CanonJson.Hash(replayVerdict);

if (originalHash != replayHash)
{
    throw new DeterminismViolationException(
        $"Replay produced different verdict: {originalHash} vs {replayHash}");
}

4.3 Replay API

The verdict-replay surface is implemented in the Replay WebService (src/Replay/StellaOps.Replay.WebService/VerdictReplayEndpoints.cs). Deterministic execution, verification, comparison, status, and the Console by-subject adapter use policy replay.token.read and scope replay:read; explicit durable token/bundle/snapshot production uses replay.token.write and replay:write (see StellaOpsScopes.cs):

POST /v1/replay/verdict          # Execute a verdict replay from an audit bundle
POST /v1/replay/verdict/verify   # Check replay eligibility for a bundle
GET  /v1/replay/verdict/{manifestId}/status  # Replay status (501 unless durable history configured)
POST /v1/replay/verdict/compare  # Compare two replay executions for divergence

Example response (POST /v1/replay/verdict):

{
  "success": true,
  "status": "...",
  "verdictMatches": true,
  "decisionMatches": true,
  "originalVerdictDigest": "sha256:...",
  "replayedVerdictDigest": "sha256:...",
  "originalDecision": "...",
  "replayedDecision": "...",
  "drifts": [],
  "divergenceSummary": null,
  "durationMs": 0,
  "evaluatedAt": "...",
  "error": null
}

Reconciliation: There is no GET /replay?manifest_sha=... endpoint and no {verdict, replay_manifest_sha, verdict_sha, determinism_verified} response shape in the code. The implemented contract is the POST /v1/replay/verdict[...] family above. Determinism comparison is surfaced via verdictMatches/decisionMatches and the drift/divergence fields; the underlying digest comparison and scoring are provided by StellaOps.Replay.Core.DeterminismVerifier.

5. Testing Requirements

5.1 Golden Tests

Every service that produces verdicts MUST maintain golden test fixtures:

tests/fixtures/golden/
├── manifest-001.json
├── verdict-001.json (expected)
├── manifest-002.json
├── verdict-002.json (expected)
└── ...

Test Pattern:

[Theory]
[MemberData(nameof(GoldenTestCases))]
public async Task Verdict_MatchesGolden(string manifestPath, string expectedPath)
{
    var manifest = await LoadManifest(manifestPath);
    var actual = await engine.EvaluateAsync(manifest);
    var expected = await File.ReadAllBytesAsync(expectedPath);
    
    Assert.Equal(expected, CanonJson.Canonicalize(actual));
}

5.2 Chaos Tests

Chaos tests verify determinism under varying conditions:

[Fact]
public async Task Verdict_IsDeterministic_UnderChaos()
{
    var manifest = CreateTestManifest();
    var baseline = await engine.EvaluateAsync(manifest);
    
    // Vary conditions
    for (int i = 0; i < 100; i++)
    {
        Environment.SetEnvironmentVariable("RANDOM_SEED", i.ToString());
        ThreadPool.SetMinThreads(i % 16 + 1, i % 16 + 1);
        
        var verdict = await engine.EvaluateAsync(manifest);
        
        Assert.Equal(
            CanonJson.Hash(baseline),
            CanonJson.Hash(verdict));
    }
}

5.3 Cross-Platform Tests

Verdicts MUST be identical across:

• Windows / Linux / macOS
• x64 / ARM64
• .NET versions (within major version)

6. Troubleshooting Guide

6.1 “Why are my verdicts different?”

Symptom: Same inputs produce different verdict hashes.

Checklist:

1. ✅ Are all inputs content-addressed? Check manifest hashes.
2. ✅ Is canonicalization version the same? Check _canonVersion.
3. ✅ Is engine version the same? Check engine_version in manifest.
4. ✅ Are feeds from the same snapshot? Check feeds_snapshot_sha256.
5. ✅ Is policy bundle the same? Check policy_bundle_sha256.

Debug Logging: Enable pre-canonical hash logging to compare inputs:

{
  "Logging": {
    "DeterminismDebug": {
      "LogPreCanonicalHashes": true
    }
  }
}

6.2 Common Causes

6.3 Reporting Issues

When reporting determinism issues, include:

1. Both manifest JSONs (canonical form)
2. Both verdict JSONs (canonical form)
3. Engine versions
4. Platform details (OS, architecture, .NET version)
5. Pre-canonical hash logs (if available)

7. Migration History

v1 (2025-12-26)

• Initial specification
• RFC 8785 JCS + Unicode NFC
• Version marker: stella:canon:v1

Doc reconciliation (later pass): Identifier/implementation references in this spec were reconciled against src/. Corrected the canonicalizer location (StellaOps.Attestor.ProofChain.Json.Rfc8785JsonCanonicalizer), the runtime guard type (DeterminismGuardService), the EvidenceId/GraphRevisionId/VerdictId algorithms and owning modules, and the replay API surface (POST /v1/replay/verdict[...]). Promoted the compile-time analyzer from “Planned” to implemented (IDs STELLA0110–STELLA0114, enforced at Error). Flagged ManifestIdGenerator and PolicyBundleIdGenerator as NOT IMPLEMENTED (Draft/roadmap) and StellaOps.Resolver.NfcStringNormalizer as archived. The on-disk canonicalization version marker is unchanged (stella:canon:v1).

Appendix A: Reference Implementations

Reconciliation: Earlier rows pointed at src/__Libraries/StellaOps.Canonical.Json/ for the JCS canonicalizer (it holds CanonJson helpers, not the Rfc8785JsonCanonicalizer type), src/Policy/__Libraries/StellaOps.Policy.Engine/ (the engine is at src/Policy/StellaOps.Policy.Engine/), and a “Golden Test Base” at src/__Libraries/StellaOps.TestKit/Determinism/ — that folder does not exist; the determinism-related helpers live under StellaOps.TestKit/Deterministic/ and the assertion/template helpers noted above.

Appendix B: Compliance Checklist

Services producing verdicts MUST complete this checklist:

• [ ] All JSON outputs use JCS canonicalization
• [ ] All strings are NFC-normalized before hashing
• [ ] Version marker included in all canonical JSON
• [ ] Determinism guard enabled for evaluation code
• [ ] Golden tests cover all verdict paths
• [ ] Chaos tests verify multi-threaded determinism
• [ ] Cross-platform tests pass on CI
• [ ] Replay API returns identical verdicts
• [ ] Documentation references this specification