Proof Spine Assembly Algorithm

Sprint: SPRINT_0501_0004_0001 Module: Attestor / ProofChain

Overview

The Proof Spine is the cryptographic backbone of StellaOps’ proof chain. It aggregates evidence, reasoning, and VEX statements into a single merkle-rooted bundle that can be verified independently.

Architecture

┌─────────────────────────────────────────────────────────────────────────────┐
│                         PROOF SPINE STRUCTURE                               │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  ┌──────────────┐  ┌──────────────┐  ┌──────────────┐  ┌──────────────┐    │
│  │ SBOMEntryID  │  │ EvidenceID[] │  │ ReasoningID  │  │ VEXVerdictID │    │
│  │ (leaf 0)     │  │ (leaves 1-N) │  │ (leaf N+1)   │  │ (leaf N+2)   │    │
│  └──────┬───────┘  └──────┬───────┘  └──────┬───────┘  └──────┬───────┘    │
│         │                 │                 │                 │            │
│         └─────────────────┴─────────────────┴─────────────────┘            │
│                                    │                                        │
│                                    ▼                                        │
│                    ┌───────────────────────────────┐                        │
│                    │     MERKLE TREE BUILDER       │                        │
│                    │  - SHA-256 hash function      │                        │
│                    │  - Lexicographic sorting      │                        │
│                    │  - Power-of-2 padding         │                        │
│                    └───────────────┬───────────────┘                        │
│                                    │                                        │
│                                    ▼                                        │
│                    ┌───────────────────────────────┐                        │
│                    │      ProofBundleID (Root)     │                        │
│                    │  sha256:<64-hex-chars>        │                        │
│                    └───────────────────────────────┘                        │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

Algorithm Specification

Input

Parameter	Type	Description
`sbomEntryId`	string	Content-addressed ID of the SBOM entry
`evidenceIds`	string[]	Array of evidence statement IDs
`reasoningId`	string	ID of the reasoning/policy match statement
`vexVerdictId`	string	ID of the VEX verdict statement

Output

Parameter	Type	Description
`proofBundleId`	string	Merkle root in format `sha256:<64-hex>`

Pseudocode

FUNCTION BuildProofBundleMerkle(sbomEntryId, evidenceIds[], reasoningId, vexVerdictId):
    
    // Step 1: Prepare leaves in deterministic order
    leaves = []
    leaves.append(SHA256(UTF8.GetBytes(sbomEntryId)))
    
    // Step 2: Sort evidence IDs lexicographically
    sortedEvidenceIds = evidenceIds.Sort(StringComparer.Ordinal)
    FOR EACH evidenceId IN sortedEvidenceIds:
        leaves.append(SHA256(UTF8.GetBytes(evidenceId)))
    
    leaves.append(SHA256(UTF8.GetBytes(reasoningId)))
    leaves.append(SHA256(UTF8.GetBytes(vexVerdictId)))
    
    // Step 3: Pad to power of 2 (duplicate last leaf)
    WHILE NOT IsPowerOfTwo(leaves.Length):
        leaves.append(leaves[leaves.Length - 1])
    
    // Step 4: Build tree bottom-up
    currentLevel = leaves
    WHILE currentLevel.Length > 1:
        nextLevel = []
        FOR i = 0 TO currentLevel.Length STEP 2:
            left = currentLevel[i]
            right = currentLevel[i + 1]
            parent = SHA256(left || right)  // Concatenate then hash
            nextLevel.append(parent)
        currentLevel = nextLevel
    
    // Step 5: Return root as formatted ID
    RETURN "sha256:" + HexEncode(currentLevel[0])

Determinism Invariants

Invariant	Rule	Rationale
Evidence Ordering	Lexicographic (byte comparison)	Reproducible across platforms
Hash Function	SHA-256 only	No algorithm negotiation
Padding	Duplicate last leaf	Not zeros, preserves tree structure
Concatenation	Left `\|\|` Right	Consistent ordering
String Encoding	UTF-8	Cross-platform compatibility
ID Format	`sha256:<lowercase-hex>`	Canonical representation

Example

Input

{
  "sbomEntryId": "sha256:abc123...",
  "evidenceIds": [
    "sha256:evidence-cve-2024-0001...",
    "sha256:evidence-reachability...",
    "sha256:evidence-sbom-component..."
  ],
  "reasoningId": "sha256:reasoning-policy...",
  "vexVerdictId": "sha256:vex-not-affected..."
}

Processing

Leaf 0: SHA256("sha256:abc123...") → SBOM
Leaf 1: SHA256("sha256:evidence-cve-2024-0001...") → Evidence (sorted first)
Leaf 2: SHA256("sha256:evidence-reachability...") → Evidence
Leaf 3: SHA256("sha256:evidence-sbom-component...") → Evidence
Leaf 4: SHA256("sha256:reasoning-policy...") → Reasoning
Leaf 5: SHA256("sha256:vex-not-affected...") → VEX
Padding: Duplicate leaf 5 to get 8 leaves (power of 2)

Tree Structure

                    ROOT
                   /    \
                  H1     H2
                 / \    / \
               H3   H4  H5  H6
              / \  / \ / \ / \
             L0 L1 L2 L3 L4 L5 L5 L5  (padded)

Output

sha256:7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069

Cross-Platform Verification

Test Vector

For cross-platform compatibility testing, use this known test vector:

Input:

{
  "sbomEntryId": "sha256:0000000000000000000000000000000000000000000000000000000000000001",
  "evidenceIds": [
    "sha256:0000000000000000000000000000000000000000000000000000000000000002",
    "sha256:0000000000000000000000000000000000000000000000000000000000000003"
  ],
  "reasoningId": "sha256:0000000000000000000000000000000000000000000000000000000000000004",
  "vexVerdictId": "sha256:0000000000000000000000000000000000000000000000000000000000000005"
}

All implementations (C#, Go, Rust, TypeScript) must produce the same root hash.

Verification

To verify a proof bundle:

Obtain all constituent statements (SBOM, Evidence, Reasoning, VEX)
Extract their content-addressed IDs
Re-compute the merkle root using the algorithm above
Compare with the claimed proofBundleId

If the roots match, the bundle is valid and all statements are bound to this proof.

API

C# Interface

public interface IProofSpineAssembler
{
    /// <summary>
    /// Assembles a proof spine from its constituent statements.
    /// </summary>
    ProofSpineResult Assemble(ProofSpineInput input);
}

public record ProofSpineInput
{
    public required string SbomEntryId { get; init; }
    public required IReadOnlyList<string> EvidenceIds { get; init; }
    public required string ReasoningId { get; init; }
    public required string VexVerdictId { get; init; }
}

public record ProofSpineResult
{
    public required string ProofBundleId { get; init; }
    public required byte[] MerkleRoot { get; init; }
    public required IReadOnlyList<byte[]> LeafHashes { get; init; }
}

Proof and Evidence Chain Technical Reference - §2.4, §4.2, §9
Content-Addressed IDs
DSSE Predicates