ADR-020: CGS Merkle Tree Implementation

Formerly docs/technical/adr/0042-cgs-merkle-tree-implementation.md (legacy ADR 0042).

FieldValue
StatusAccepted
Date2025-12-29
Decision makersBackend team, Security team, Attestation team (consulted)
Review date2026-06-29 (re-evaluate whether code duplication warrants a shared library)
RelatedADR-021 (Fulcio keyless signing)

For: engineers working on the Stella Ops verdict pipeline (CGS hashing, evidence packs, attestation). This ADR records why the Canonical Graph Signature (CGS) hash is computed by a small, purpose-built Merkle tree inside VerdictBuilderService rather than reusing the Attestor proof-chain builder.

Context

The CGS (Canonical Graph Signature) system requires deterministic hash computation for verdicts. The decision was whether to:

  1. Reuse the existing StellaOps.Attestor.ProofChain Merkle tree builder, or
  2. Build a custom Merkle tree implementation in VerdictBuilderService.

Requirements

Existing ProofChain Merkle Builder

Located at: src/Attestor/__Libraries/StellaOps.Attestor.ProofChain/

Pros:

Cons:

Decision

Build custom Merkle tree implementation in VerdictBuilderService.

Rationale

  1. Separation of Concerns: CGS hash computation has different requirements than attestation chain verification

  2. Full Control Over Determinism: Custom implementation allows:

    • Explicit leaf ordering: SBOM → VEX (sorted) → Reachability → PolicyLock
    • VEX document sorting by content hash (not insertion order)
    • Culture-invariant string comparison (StringComparer.Ordinal)

  3. Simplicity: ~50 lines of code vs modifying 500+ lines in ProofChain

  4. No Breaking Changes: Doesn’t affect existing attestation infrastructure

Implementation

// VerdictBuilderService.cs
private static string ComputeCgsHash(EvidencePack evidence, PolicyLock policyLock)
{
    // Build Merkle tree from evidence components (sorted for determinism)
    var leaves = new List<string>
    {
        ComputeHash(evidence.SbomCanonJson),
        ComputeHash(evidence.FeedSnapshotDigest)
    };

    // Add VEX digests in sorted order (ORDER-CRITICAL for determinism!)
    foreach (var vex in evidence.VexCanonJson.OrderBy(v => v, StringComparer.Ordinal))
    {
        leaves.Add(ComputeHash(vex));
    }

    // Add reachability if present
    if (!string.IsNullOrEmpty(evidence.ReachabilityGraphJson))
    {
        leaves.Add(ComputeHash(evidence.ReachabilityGraphJson));
    }

    // Add policy lock hash
    var policyLockJson = JsonSerializer.Serialize(policyLock, CanonicalJsonOptions);
    leaves.Add(ComputeHash(policyLockJson));

    // Build Merkle root
    var merkleRoot = BuildMerkleRoot(leaves);
    return $"cgs:sha256:{merkleRoot}";
}

private static string BuildMerkleRoot(List<string> leaves)
{
    if (leaves.Count == 0)
        return ComputeHash("");

    if (leaves.Count == 1)
        return leaves[0];

    var level = leaves.ToList();

    while (level.Count > 1)
    {
        var nextLevel = new List<string>();

        for (int i = 0; i < level.Count; i += 2)
        {
            if (i + 1 < level.Count)
            {
                // Combine two hashes
                var combined = level[i] + level[i + 1];
                nextLevel.Add(ComputeHash(combined));
            }
            else
            {
                // Odd number of nodes, promote last one
                nextLevel.Add(level[i]);
            }
        }

        level = nextLevel;
    }

    return level[0];
}

private static string ComputeHash(string input)
{
    var bytes = Encoding.UTF8.GetBytes(input);
    var hashBytes = SHA256.HashData(bytes);
    return Convert.ToHexString(hashBytes).ToLowerInvariant();
}

Consequences

Positive

Negative

Neutral

Alternatives Considered

Alternative 1: Modify ProofChain Builder

Rejected because:

Alternative 2: Use Third-Party Merkle Tree Library

Rejected because:

Alternative 3: Single-Level Hash (No Merkle Tree)

Rejected because:

Verification

Test Coverage

File: src/__Tests/Determinism/CgsDeterminismTests.cs

  1. Golden File Test: Known evidence produces expected hash
  2. 10-Iteration Stability: Same input produces identical hash 10 times
  3. VEX Order Independence: VEX document ordering doesn’t affect hash
  4. Reachability Inclusion: Reachability graph changes hash predictably
  5. Policy Lock Versioning: Different policy versions produce different hashes

Cross-Platform Verification

CI workflow: .gitea/workflows/cross-platform-determinism.yml

All platforms produce an identical CGS hash for the same input.

Migration

No migration required - this is a new feature.

References