Circuit 1 — Build provenance

Status: v1 shipping. The foundation circuit — binds every other circuit in the bundle to a specific build of a specific artefact produced by an approved pipeline.

SSCoP principles: 2.1 (build-environment access control), 2.2 (build-environment change logging), 3.1 (secure distribution). CRA provisions: Article 13(1) conformity-assessment evidence retention. NIST SSDF practices: PS.1, PS.2, PW.6. DCC scope: Level 2 and Level 3 supply-chain controls.

The claim

This binary (identified by its SHA-256 hash) came out of an authorised build pipeline, signed by an identity that belongs to the buyer's approved-builder set, over a SLSA v1.0 in-toto provenance attestation that lists this binary as its subject.

The proof anchors every downstream claim. Circuits 2, 3, 4, and 5 each reason about release-specific evidence (commits, SBOMs, notification timestamps, policy commitments); Circuit 1 is what ties that evidence to this specific binary rather than some other one the vendor might have produced. A bundle without Circuit 1 cannot prove the other four are about the release the buyer is receiving.

What the proof does not claim

• It does not verify the Fulcio certificate chain inside the circuit. The off-circuit verifier (colofon-sdk) validates the chain, parses the SAN URI from the signing certificate, and feeds the public key and identity hash into the circuit as witness. In-circuit X.509 parsing is deferred to a later version on cost grounds.
• It does not verify Rekor inclusion inside the circuit. The SDK performs Rekor inclusion verification against the current signed tree head before admitting the attestation as witness.
• It does not prove which JSON field the subject digest sits in — only that the public binary digest appears at the offset the prover hinted, anchored by the substring "sha256":". A structural anchor (requiring the offset to follow "subject":[) is a planned hardening step; see §"Honest caveats" below.

Why existing mechanisms are not enough

• cosign verify-blob output emailed to the buyer. The buyer sees a text line saying the attestation verified. They have no way to tell whether the attestation was verified against their specific approved-builder set, against a current Rekor tree head, or against the binary they actually received.
• Published SLSA attestations. The buyer can verify them themselves — but now every detail the attestation exposes is public: the CI runner identifier, the workflow path, the release-manager identity in the Fulcio SAN, the toolchain version. These are the precise signals an adversary uses to craft targeted phishing, CI misconfiguration probes, and toolchain-version fingerprinting.
• Vendor-asserted "we built it on our approved pipeline." A signed text assertion without a proof of the signing relationship is a trust fall.

The proof is the bridge: cryptographic verification of an authorised build, without disclosing the identifying details of the build environment to the buyer or to anyone who obtains the bundle later.

Construction

Signed inputs

The SLSA attestation's subject[].digest.sha256 field names the binary; the runDetails.builder.id field names the workflow path; the Fulcio certificate's SAN URI names the builder identity. The circuit proves the binding between the binary digest (public) and the builder identity (private, Merkle-committed to an approved set).

Public inputs

The circuit exposes five public values:

• pae_digest_hash — Poseidon2 commitment of sha256(pae_bytes), where pae_bytes is the DSSE pre-authentication encoding of the SLSA envelope
• approved_builder_root — root of the Merkle tree committing to the buyer's approved-builder set
• signer_commitment — Poseidon2 hash binding the signing public key to the builder identity (prevents a prover from mixing one identity's key with another identity's Merkle opening)
• binary_digest_high, binary_digest_low — the 32-byte SHA-256 of the binary, split into two BN254-compatible halves

The private witness comprises the PAE bytes themselves, the ECDSA signature components, the signer's public key, the builder identity hash, the Merkle opening into the approved-builder set, and the byte offset of the subject-digest anchor inside the PAE.

What the circuit checks

1. PAE SHA-256. The SHA-256 of the active bytes of pae_bytes (up to pae_len) is computed. This is the message the ECDSA signature covers.
2. ECDSA P-256 signature verification. The ECDSA signature (r, s) validates under the provided public key against the PAE hash. Uses Noir's standard-library P-256 verifier.
3. PAE digest commitment. The SHA-256 of the PAE is split into two 16-byte halves (both fit inside BN254 Fr; ~81% of real SHA-256 values exceed the modulus as a single field), hashed with Poseidon2, and asserted to equal pae_digest_hash.
4. Approved-builder Merkle membership. The builder identity hash (private witness) has a valid Merkle opening in the tree rooted at approved_builder_root. Uses the same IMT-adjacent membership primitive as Circuits 2 and 3.
5. Signer commitment. The Poseidon2 hash of the signing pubkey coordinates plus the builder identity hash equals the public signer_commitment. This is the binding that prevents a prover from using identity A's Merkle opening with identity B's signing key.
6. Subject-digest extraction. The circuit checks the 10-byte anchor "sha256":" appears at the prover-hinted offset inside pae_bytes, parses the following 64 lowercase-hex bytes into 32 raw bytes, and binds those bytes to binary_digest_high / binary_digest_low. Uppercase hex is rejected (the SLSA spec and every real generator observed in the wild emit lowercase; rejecting uppercase keeps the anchor unambiguous).

Every PAE is processed at full MAX_PAE_LEN regardless of actual length. sha256_var parameterises on pae_len for padding correctness but not for constraint count. Proving cost is therefore flat across small and large attestations.

The trust boundary

The circuit verifies three things: a signature, a Merkle opening, and a digest extraction. It does not verify:

• The Fulcio certificate chain. Verification of the Sigstore PKI (Fulcio's issuing authority, the chain to the root, OCSP/CRL state) is off-circuit. The SDK does this before admitting the attestation as witness and derives the builder_identity_hash from the SAN URI. In-circuit X.509 parsing would add tens of thousands of constraints for a trust signal the SDK can compute faster off-circuit against Sigstore's well-known anchors.
• Rekor inclusion. The SDK queries Rekor for the attestation's log entry and verifies the inclusion proof against the current signed tree head. A bundle where Rekor inclusion cannot be established is rejected before Circuit 1 runs.
• The buyer's approved-builder set membership semantics. The Merkle root is buyer-committed — typically published by the buyer to Rekor as part of their policy issuance. The circuit proves membership against whatever root the public input specifies; the question of whether that root reflects a sensible approved-builder list is the buyer's.

The off-circuit / in-circuit split is deliberate. Verification that has a clean external trust anchor (Sigstore PKI, Rekor tree head) is cheap off-circuit and expensive in-circuit, and the trust anchor is not improved by re-proving it. Verification whose value comes from the proof itself (this binary was signed by this approved identity) goes in-circuit.

Cross-circuit binding

Circuit 1's public outputs are the commitments every other circuit in the bundle binds against:

• Circuit 2 (developer authorisation) binds against the commit hash named in Circuit 1's SLSA predicate. A Circuit 2 proof that names a different commit than the one Circuit 1 attests to fails the bundle verifier.
• Circuit 3 (SBOM non-membership) binds sbom_root into the SLSA predicate's subject fields. A vendor cannot ship Circuit 3 against a cherry-picked SBOM subset; the SBOM root Circuit 3 proves non-membership against is the one Circuit 1's signed payload references.
• Circuit 4 (notification SLA) binds the customer-set commitment to the release identified by Circuit 1's binary digest.
• Circuit 5 (policy composition) wraps all four and proves that each binds consistently against the same Circuit 1 anchor.

The effect: the bundle is internally consistent about which release it is describing. Cross-circuit inconsistencies (Circuit 2 for a different commit, Circuit 3 for a different SBOM) are caught at the bundle-verifier composition step, not hidden.

Approved-builder set semantics

The approved-builder set is a Merkle tree of builder-identity hashes. For GitHub Actions keyless signing, each leaf is a Poseidon2 hash of a canonicalised SAN URI — for example, https://github.com/colofonhq/colofon-circuits/.github/workflows/release.yml@refs/tags/v0.3.1. The SAN encodes the repository, the workflow path, and the ref the workflow ran against.

Buyer policies differ in how narrowly the set is specified:

• Narrow — a specific workflow path at a specific ref. Strong: excludes tag-prefix collisions and unauthorised workflow files added later.
• Medium — a specific repository's workflows at any tagged ref. Common in production deployments.
• Broad — any workflow in a specific GitHub org. Appropriate for large vendors with multiple release trains.

The set is buyer-committed: the buyer publishes their accepted set as a Rekor entry, and the vendor's bundle points at that root. Changing the set is a buyer-side action with its own audit trail.

Tree parameters (v1):

What the proof carries — and what it does not

The proof publishes:

• the binary digest (the claim's subject; intended to be public)
• the approved-builder Merkle root (a commitment — does not reveal the set's members)
• the signer commitment (a commitment — does not reveal the signing key or the identity)
• the PAE digest commitment (a commitment — does not reveal the PAE contents)

An adversary who obtains the proof cannot derive:

• which CI workflow path produced this release (attacker cannot probe misconfigurations in the specific workflow file)
• which release-manager identity signed (attacker cannot target that individual with phishing, OIDC session hijacking, or credential-theft campaigns)
• which toolchain version the binary was compiled with (attacker cannot fingerprint versions with known compiler-level vulnerabilities)
• the membership of the approved-builder set (attacker cannot enumerate the vendor's release trains)
• the correlation between this release and any prior release — the signer commitment and PAE digest are per-attestation; two releases by the same signer produce uncorrelated commitments unless the adversary already knows the signer's key

Honest caveats

• Subject-digest anchor is substring-based, not structural. The circuit asserts "sha256":"<target-hex>" appears at the prover-hinted offset inside the PAE. The same substring can legitimately appear under materials[].digest.sha256 or other nested digest fields inside a SLSA predicate. An honest prover's SDK locates the offset by searching for the unique subject digest; an adversarial prover who constructs an attestation where the target hash also appears in materials could claim the wrong provenance semantics. A structural anchor (requiring the offset to follow "subject":[) is a planned v1.5 hardening step.
• In-circuit X.509 deferred. The circuit trusts the SDK to derive builder_identity_hash from the Fulcio SAN correctly. An SDK-level bug here would be a soundness bug at the bundle level even though the circuit itself is sound. Independent cryptographic review of the SDK's SAN parser is part of the pre-launch audit scope.
• No non-equivocation across Rekor tree heads. Circuit 1 binds against a single attestation entry. It does not prove the attestation has not been superseded by a subsequent attestation for the same binary under a different identity. This is a non-issue under normal Sigstore semantics but is a theoretical attack surface in a scenario where a vendor loses control of an identity and a second attestation is logged by the attacker. Bundle-level policies that require "first signed attestation for this digest" close this; the circuit itself does not enforce it.
• MAX_PAE_LEN is hard. An attestation larger than 4096 bytes cannot be proved by the v1 circuit. This is unusual in practice but is not guarded against silently — the SDK errors before witness construction if the PAE is too large. Raising the bound is a straightforward recompilation.

Parameters and performance

Measured values ship with each release alongside the bundle.

Further reading

• Whitepaper §3 — Whitepaper
• Source circuit — colofonhq/colofon-circuits/build_provenance/src/main.nr
• SLSA v1.0 — https://slsa.dev/spec/v1.0/
• in-toto attestation framework — https://github.com/in-toto/attestation
• Sigstore Fulcio — https://docs.sigstore.dev/certificate_authority/overview/
• Sigstore Rekor v2 — https://docs.sigstore.dev/logging/overview/
• GitHub Artifact Attestations — https://docs.github.com/en/actions/security-guides/using-artifact-attestations-to-establish-provenance-for-builds