Circuit 3 — SBOM dependency non-membership

Status: v1 shipping. Headline circuit — the claim that was not answerable before zero-knowledge proofs matured.

SSCoP principles: 1.2 (third-party composition), 3.3 (vulnerability management). CRA provisions: Annex I §1(2)(b), §2(1). NIST SSDF practices: PW.4.5, RV.1. DCC scope: Level 2 and Level 3 supply-chain controls.

The claim

No component in this release has an unpatched CVE above the buyer's severity threshold, older than the buyer's age threshold, against a trusted CVE snapshot.

The proof is issued per release. It is verifiable in any browser against public Sigstore Rekor transparency logs. The buyer receives a cryptographic receipt; the vendor's SBOM — dependency names, versions, licence composition, upstream maintainer identities, transitive-dependency topology — never leaves the vendor's infrastructure.

What the proof does not claim

• It does not say the SBOM is complete. Completeness is inherited from Circuit 1: Circuit 1 binds a specific SBOM root into the SLSA provenance attestation, so a vendor cannot ship Circuit 3 against a cherry-picked subset of components without breaking Circuit 1's chain to the approved build pipeline.
• It does not say the vendor's build is vulnerability-free in general — only against the buyer's specific severity and age thresholds.
• It does not say newly-disclosed CVEs (published after the proof was issued) are absent. The proof is timestamped; the CVE snapshot it verified against has a signed timestamp. Re-proving is the vendor's responsibility and is cheap.

Why this problem was unsolved before

Three existing mechanisms partially address the problem and each fails in a way that matters to regulated buyers.

• SCA scanners (Snyk, Sonatype, Chainguard, Black Duck). The vendor runs the scan and emails the report. The buyer has no way to verify the scan ran against the actual released SBOM, against a current CVE database, with thresholds applied truthfully.
• Published SBOMs. The buyer can run their own scan. The vendor has given up their dependency tree as an attack-surface map, their upstream-maintainer roster, and their licence composition. For DCC Level 2+, closed-source ISVs under prime-contract NDAs, and FCA-regulated vendors, this disclosure is contractually or legally forbidden.
• Plain signed attestations ("we certify no critical vulnerabilities"). A signature over an assertion is not a proof of the assertion. Every major supply-chain compromise in recent years ran against vendors whose attestation said the boxes were ticked.

The problem is structural. The claim the buyer needs ("your release has no vulnerabilities above my threshold") requires reasoning over the SBOM. Every mechanism that exposes enough of the SBOM for the buyer to reason over it, exposes enough for an adversary to reason over it too. Circuit 3 is the construction that answers the claim without the exposure.

Construction

Inputs — signed

Public inputs

The circuit exposes three public values. A verifier reads these as the headline of the proof:

• sbom_root — Poseidon2 Merkle root of the PURL hashes of the SBOM's components.
• cve_tree_root — root of the vendor's policy-filtered CVE indexed Merkle tree. Commits implicitly to the buyer's severity and age thresholds (see §"Policy as commitment" below).
• component_count — number of real components in the SBOM (constrained to 1 ≤ n ≤ MAX_SBOM_COMPONENTS).

Every other value — the PURL hashes themselves, the Merkle openings, the low-leaf preimages for non-membership proofs, the sibling paths — is private witness.

What the circuit checks

For each active slot i < component_count, the circuit asserts four things:

1. CVE non-membership. The component's PURL hash is not present in the policy-filtered CVE indexed Merkle tree committed to by cve_tree_root. Non-membership is proved by exhibiting the path to two adjacent sorted leaves whose range excludes the component's hash.
2. SBOM membership. The component's PURL hash is present in the Merkle tree committed to by sbom_root. Without this, a prover could swap a non-vulnerable placeholder for a vulnerable component without changing the public SBOM commitment.
3. Sortedness. Component hashes are strictly ascending within active slots. Duplicates fail. The i = 0 iteration asserts component[0] > 0, which doubles as a guard against zero-valued PURL hashes in real components.
4. Padding. Slots beyond component_count are required to have zero hashes. Without this, a prover could fabricate extra components past the count and a naive verifier would silently accept them as part of the SBOM.

Active slots are iterated identically to padding slots; per-slot checks are gated by an is_active implication. This keeps the constraint count uniform across SBOM sizes (a 10-component SBOM has the same proving cost as a 50-component SBOM), which matters for proving-time predictability under batching.

The non-membership primitive — Indexed Merkle Trees

The circuit's core move is a non-membership proof: "this component's PURL hash does not appear in the vulnerability exclusion set." Two established constructions support this in zero-knowledge:

• Sparse Merkle Tree (SMT). Fixed-depth tree (~256) with a leaf for every possible hash value. Non-membership = proving a default value at the leaf's index. Well-studied but no production-grade Noir reference implementation exists today.
• Indexed Merkle Tree (IMT). Aztec's nullifier-tree construction: sorted leaves, each leaf pointing to its successor. Non-membership = proving the path to two adjacent leaves whose range brackets the target. Smaller trees, cheaper updates.

Colofon uses IMT. Rationale: it is battle-tested in production (Aztec L2), it is native to the Noir/Aztec cryptographic stack the rest of the system runs on, and the port from protocol-internal to a standalone library (colofon-imt) is the correct unit of generalisation for the problem. The generalisation is upstreamable — the same primitive is useful to any Noir project doing non-membership over a policy-filtered set.

Tree parameters (v1):

Policy as commitment

The buyer's severity threshold (e.g. HIGH) and age threshold (e.g. 30 days) are applied off-circuit when the CVE tree is constructed. The vendor's witness builder runs the OSV feed through a filter — "include every CVE whose CVSS ≥ buyer's severity AND disclosure-age ≥ buyer's age cutoff" — and the filtered set becomes the tree's leaves. The root of that tree is cve_tree_root, which is public input.

This means:

• The policy is a property of the CVE tree, not a separate circuit argument. Different policies produce different trees and different public roots.
• Policy auditing is an off-circuit step: the buyer (or the buyer's auditor) re-runs the same OSV filter with the same thresholds against the same signed OSV snapshot, reconstructs the tree, and checks the root matches the proof's public input.
• Circuit 5 (policy composition) lets one proving run target multiple buyers' policies simultaneously — the prover constructs one CVE tree per buyer and proves conformance against each root.

This is not the only tenable design. The alternative is to pass severity and age as explicit circuit arguments and evaluate the filter inside the circuit. That design produces a single CVE tree committing to the full feed and a circuit that re-derives the filter per component. It costs ~3× in constraints for no buyer-visible win in the usual case (policies change slowly; off-circuit filtering caches well). The design choice is revisitable if a v2 use case demands in-circuit policy evaluation.

Cross-circuit binding

Circuit 3's SBOM commitment is bound to Circuit 1's provenance attestation. Specifically, the sbom_root that Circuit 3 proves non-membership against is the same value that Circuit 1's SLSA in-toto predicate names as the release's SBOM subject.

A vendor who wanted to cheat by shipping Circuit 3 against a curated subset of components would have to either:

• ship Circuit 3 against an sbom_root that disagrees with Circuit 1's bound root (the bundle verifier catches this), or
• produce a Circuit 1 proof against a falsified SLSA predicate (GitHub Actions' OIDC keyless signing catches this upstream).

The binding is enforced at the bundle-verifier level, not inside Circuit 3 itself. Circuit 3's public inputs contain the commitments it needs to reason about; cross-checking commitments across circuits is the composition step, and keeping it there keeps each circuit reasoning about a single claim.

Coverage tiers

Binary pass/fail is the wrong abstraction for SBOM conformance in 2026. Sigstore adoption across package ecosystems is uneven: npm and PyPI sit in the 7–17% attested range as of early 2026, while crates.io, Go modules and Maven Central remain at or near zero. A release that depends on 250 components is overwhelmingly likely to include components that do not have full upstream attestation today.

Circuit 3 reports coverage as a ratio rather than binary. A bundle shows, for example:

183 / 247 components Sigstore-verified 64 anchored by registry-integrity hash (Tier 2) 0 anchored by vendor-signed hash only (Tier 3)

The buyer applies their own coverageFloor (e.g. 0.90) as a separate policy input. This makes the circuit useful today under real ecosystem conditions while leaving room for the ratio to climb naturally as upstream attestation rolls out.

What the proof carries — and what it does not

The proof publishes:

• the SBOM Merkle root (a commitment — does not reveal the SBOM)
• the CVE tree root (a commitment — does not reveal the CVE list, nor the severity/age thresholds)
• the component count
• the coverage-tier ratios

An adversary who obtains the proof cannot derive:

• the dependency tree as an attack-surface map
• upstream-maintainer identities to target with malicious-PR campaigns
• the vendor's licence composition (competitive intelligence)
• which CVEs are currently unpatched on the vendor's release cadence (exploit-window intelligence)
• whether the vendor's policy is tight or loose against industry norms
• the relationship between this vendor's SBOM and any other vendor's SBOM — different vendors produce different Merkle roots, even for overlapping dependencies

The witness is never transmitted off the proving machine. A hosted prover run (e.g. colofon-prover.fly.dev) sees the witness in memory during proof generation and scrubs it on completion; the hosted-prover architecture is engineered around this guarantee.

Parameters and performance

Limitations and honest caveats

• OSV trust anchor is v1-pragmatic. v1 treats OSV as a trust anchor via HTTPS + certificate pinning. v2 pursues upstream contribution to OSV.dev for Sigstore-signed snapshot releases, closing the residual trust gap. The limitation is in §4 of the whitepaper; it is not hidden.
• Coverage tiers are a real constraint. Until upstream attestation coverage climbs, a meaningful fraction of real SBOMs depend on Tier 2 / Tier 3 evidence. Colofon reports coverage honestly rather than hiding the gap — this makes the bundle useful today under real conditions.
• Policy commitment is off-circuit. Auditing the policy requires re-running the filter; the circuit alone does not prove the filter ran correctly. This is a sharp knife: buyers who care should re-run the filter. The off-circuit step is documented, reproducible, and takes seconds.
• Newly-disclosed CVEs. A proof issued on day T is valid against the CVE snapshot at day T. A vulnerability disclosed at day T+7 is not retroactively captured. Re-proving at each release (or at buyer-configurable intervals) closes this. The bundle's timestamp is public and auditable.

Further reading

• Whitepaper §3 (circuit summary) — Whitepaper
• Source circuit — colofonhq/colofon-circuits/sbom_non_membership/src/main.nr
• IMT library — colofonhq/colofon-circuits/imt (ported and generalised from AztecProtocol/aztec-packages)
• OSV.dev — https://osv.dev/
• CycloneDX 1.5 — https://cyclonedx.org/specification/overview/
• Aztec Indexed Merkle Tree — https://docs.aztec.network/
• Sigstore Rekor v2 — https://docs.sigstore.dev/logging/overview/