Provenance Information

The previous lesson separated the field the signature covers from the field the verifier can test: once the declaration expanded to nine fields, the signature covered all nine, but the verifier could recompute only one. The remaining eight fields passed through signed, and being signed did not make them correct.

This lesson builds the document that stands in for those eight fields: provenance, the information that describes where and how the build was produced. The measure is a single number — how many of the document’s fields are independently verifiable, and how many remain only attested. A field is a verifiable field if it can be recomputed from an object the verifier can obtain on its own; if it cannot, it is an attested field, and its correctness comes down to trusting whoever wrote it.

SC11. The provenance document is fourteen fields in four groups: which source, which process, which environment, which input. The document and its objects are modeled with node. SC12. The set of objects the verifier can independently obtain is four: the source tree, the build definition file, the dependency lockfile, and the build artifact’s bytes.

The Document’s Fourteen Fields

// measurement-network/provenance.mjs — the provenance document is built field by field: how many are independently verifiable
import { createHash } from "node:crypto";

const digest = (b) => createHash("sha256").update(b).digest("hex").slice(0, 12);

// Fictional independent objects: the verifier can obtain and rehash these on its own.
const SOURCE = Buffer.from(["main.js", "measurement.js", "config.json"]
  .map((f) => `${f}\n// fictional subscriber portal\n`).join(""));
const BUILD_DEFINITION = Buffer.from("steps: build, test, package, sign\n");
const LOCKFILE = Buffer.from(Array.from({ length: 73 }, (_, i) => `component-${i}@2.0`).join("\n"));
const OUTPUT = Buffer.concat([Buffer.from("subscriber-portal\n"), Buffer.alloc(16384, "u")]);
const ON_HAND = { source: SOURCE, "build-definition": BUILD_DEFINITION, lockfile: LOCKFILE, output: OUTPUT };

// Provenance document: four groups, fourteen fields. `written` is the value put in the document.
const DOCUMENT = [
  ["source", "repo", "subscriber-portal", false],
  ["source", "commit", digest(SOURCE), true],
  ["source", "branch", "main", false],
  ["process", "build-definition", digest(BUILD_DEFINITION), true],
  ["process", "step-list", "build, test, package, sign", false],
  ["process", "invocation-parameter", "target=production", false],
  ["environment", "runner-type", "isolated-container", false],
  ["environment", "base-image", "7ad3e1c95006", false],
  ["environment", "isolation-level", "new runner per job", false],
  ["environment", "network-access", "closed", false],
  ["input", "lockfile", digest(LOCKFILE), true],
  ["input", "environment-variable-names", "TARGET, VERSION", false],
  ["input", "cache-key", "b41c-2", false],
  ["output", "output", digest(OUTPUT), true],
];

// A field is verifiable only if it can be recomputed from an object that can be obtained.
const S = [12, 28, 29, 0];
const row = (s) => console.log(s.map((v, i) => String(v).padEnd(S[i])).join(""));
row(["group", "field", "verification path", "type"]);
let verifiable = 0;
for (const [group, field, written, computable] of DOCUMENT) {
  if (computable) verifiable++;
  row([group, field, computable ? "object is rehashed" : "no object to compare",
    computable ? "verifiable" : "attested"]);
}
console.log("");
console.log(`document ${DOCUMENT.length} fields: ${verifiable} verifiable, ${DOCUMENT.length - verifiable} attested`);

// Five fields are deliberately given a wrong value; the verifier tests them with objects it holds.
const WRONG = { commit: "0000deadbeef", "build-definition": "111122223333",
  "base-image": "999988887777", "isolation-level": "shared runner", output: "aaaabbbbcccc" };
const onHandKey = { commit: "source", "build-definition": "build-definition", lockfile: "lockfile", output: "output" };
let caught = 0;
for (const [, field, , computable] of DOCUMENT) {
  if (!(field in WRONG)) continue;
  if (computable && digest(ON_HAND[onHandKey[field]]) !== WRONG[field]) caught++;
}
console.log(`of ${Object.keys(WRONG).length} fields deliberately written wrong, ${caught} are ` +
  `caught, ${Object.keys(WRONG).length - caught} are not tested because they are attested`);

group       field                       verification path            type
source      repo                        no object to compare         attested
source      commit                      object is rehashed           verifiable
source      branch                      no object to compare         attested
process     build-definition            object is rehashed           verifiable
process     step-list                   no object to compare         attested
process     invocation-parameter        no object to compare         attested
environment runner-type                 no object to compare         attested
environment base-image                  no object to compare         attested
environment isolation-level             no object to compare         attested
environment network-access              no object to compare         attested
input       lockfile                    object is rehashed           verifiable
input       environment-variable-names  no object to compare         attested
input       cache-key                   no object to compare         attested
output      output                      object is rehashed           verifiable

document 14 fields: 4 verifiable, 10 attested
of 5 fields deliberately written wrong, 3 are caught, 2 are not tested because they are attested

The document carries fourteen fields and four of them are verifiable. All four share one property: each is the digest of an object, and that object is in the verifier’s hands. The commit digest is recomputed from the source tree, the build-definition digest from the file in the repository, the lockfile digest from the dependency lockfile, the output digest from the build artifact’s bytes. Even if the document is written wrong, a lie does not hold in these four fields.

The remaining ten fields are attested, and what is striking is that none of them is a minor field. Isolation level, network access, runner type, and base image — all four are the fields that say the most about the build’s trustworthiness. None of them can be tested, because none has a counterpart that is an object the verifier can obtain. The sentence “network access was closed” is a statement the party running the build makes about itself.

The last line turns this distinction into a number: when five fields are deliberately given a wrong value, three are caught, two are not tested. The two not caught are base image and isolation level. The document says “new runner per job,” a shared runner was actually used, and no verification sees it. A provenance document’s value is measured not by its number of fields, but by its number of verifiable fields.

What Reproducible Building Turns into Evidence

Part of the ten attested fields actually feeds into the output: if the step list, the invocation parameter, or the base image were different, the output would be different too. This offers a lever for testability — the build is rerun with the same declared inputs, and if the output comes out the same, the declaration is verified.

SC13. The build function is fictional and produces output from declared inputs. In three of twelve builds an undeclared input feeds into the output, and in one the output has been altered afterward; the seed 410277 is visible.

// measurement-network/reproducible-build.mjs — what reproducible building turns into evidence
import { createHash } from "node:crypto";

const digest = (b) => createHash("sha256").update(b).digest("hex").slice(0, 12);
// Fictional build function: produces output from declared inputs. A hidden input feeds into the output too, if present.
const build = (g) => Buffer.from([g.source, g.lockfile, g.steps, g.parameter, g.baseImage,
  g.hidden ?? ""].join("|"));

const rng = (seed) => () =>
  (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const r = rng(410277);                                     // seed is visible

// Twelve fictional builds. Three carry an undeclared input, one has its output altered afterward.
const HIDDEN = [3, 7, 11], ALTERED = 9;
const BUILDS = Array.from({ length: 12 }, (_, i) => {
  const no = i + 1;
  const inputs = { source: `source-${no}`, lockfile: `lockfile-${no}`, steps: "build,test,package",
    parameter: "target=production", baseImage: no % 2 ? "base-a" : "base-b" };
  const actual = build(HIDDEN.includes(no) ? { ...inputs, hidden: `run-${Math.floor(r() * 900)}` } : inputs);
  const declared = no === ALTERED ? digest(Buffer.from("altered")) : digest(actual);
  return { no, inputs, declared, hasHidden: HIDDEN.includes(no) };
});

const S = [7, 16, 18, 12, 0];
const row = (s) => console.log(s.map((v, i) => String(v).padEnd(S[i])).join(""));
row(["build", "declared", "rebuilt", "match", "reason"]);
let matching = 0, realFinding = 0, falseMark = 0;
for (const y of BUILDS) {
  const rebuilt = digest(build(y.inputs));                 // only with DECLARED inputs
  const matches = rebuilt === y.declared;
  if (matches) matching++;
  else if (y.hasHidden) falseMark++;
  else realFinding++;
  if (y.no <= 4 || !matches)
    row([y.no, y.declared, rebuilt, matches ? "yes" : "NO",
      matches ? "-" : (y.hasHidden ? "undeclared input" : "output altered")]);
}
console.log("");
console.log(`of twelve builds, ${matching} match on rebuild, ` +
  `${BUILDS.length - matching} do not: ${realFinding} real, ${falseMark} false marks`);

// Reproducible building makes every declared input that feeds into the output testable.
const FEEDS_OUTPUT = ["step-list", "invocation-parameter", "base-image"];
const BEFORE = 4, FIELDS = 14;
console.log(`verifiable fields ${BEFORE}/${FIELDS} -> ${BEFORE + FEEDS_OUTPUT.length}/${FIELDS}; ` +
  `became testable: ${FEEDS_OUTPUT.join(", ")}`);
console.log(`remain attested ${FIELDS - BEFORE - FEEDS_OUTPUT.length}: ` +
  `repo, branch, runner-type, isolation-level, network-access, environment-variable-names, cache-key`);

build  declared        rebuilt           match       reason
1      27bfc23f4747    27bfc23f4747      yes         -
2      8338c7f7c879    8338c7f7c879      yes         -
3      b9f17edcb4c4    c8ea375d0c8a      NO          undeclared input
4      c06adc8bcf95    c06adc8bcf95      yes         -
7      cb7d2cb3cdff    2c83885ff93b      NO          undeclared input
9      4aa009153649    68b7642a596c      NO          output altered
11     e315e903f434    baf00860c3d5      NO          undeclared input

of twelve builds, 8 match on rebuild, 4 do not: 1 real, 3 false marks
verifiable fields 4/14 -> 7/14; became testable: step-list, invocation-parameter, base-image
remain attested 7: repo, branch, runner-type, isolation-level, network-access, environment-variable-names, cache-key

Reproducible building raises the verifiable-field count from 4 to 7. All three gained fields are inputs that feed into the output: had the step list, the invocation parameter, or the base image been written wrong, the rebuilt output would not have matched. The remaining seven fields never become testable under any condition, because they never feed into the output at all. Branch name, runner type, isolation level, and cache key do not affect the produced bytes; a declaration that does not affect something cannot be read back from that thing either. Half the document remains attested, and this is not a deficiency, it is the method’s limit.

The two numbers in the middle are the lever’s price. Four of twelve builds do not match, and of those four only one is real; in three of them an undeclared input has mixed into the output — a value such as a run number, a build timestamp, or a runner name. In those three the build is correct, the document is correct, and the only thing that changed is an undeclared input leaking into the output. The false-mark rate is 75%, and this rate is the exact definition of a scan that does not work: if three of four alerts are inspected in vain, the fourth stays under the same mark.

The source of the false mark is the method itself. Reproducible building assumes the set of declared inputs is complete; if it is not, the difference shows up in the output, but the reason for the difference is not written in the document. Working out which class a non-matching build falls into means comparing output bytes and finding the leaked value by hand — a separate investigation per alert. All three false marks are fixable flaws; the fix is not adding a field to the document, it is removing that value from the output. For the lever to be usable, the build must first be cleared of undeclared input, and that work belongs to the build definition, not to provenance.

As the Threshold Rises

Three measurements raise one policy question: which threshold should be required before deployment?

SC14. There are forty fictional deployment requests; broken requests also carry a valid signature — the result of the previous lesson, a signature does not prove a claim. Provenance generation is given as 12 seconds, rebuilding as 214 seconds, as data, not measured; the seed 87344 is visible.

// measurement-network/provenance-threshold.mjs — pass, blocked, and pipeline time as the verification threshold rises
const rng = (seed) => () =>
  (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const r = rng(87344);                                      // seed is visible

// A broken request also carries a valid signature: the result of the previous lesson — a signature does not prove a claim.
const REQUESTS = Array.from({ length: 40 }, () => {
  const broken = r() < 0.12;
  return { broken, signed: true, hasProvenance: broken || r() < 0.85,
    evidenceMatches: !broken, hiddenInput: r() < 0.18 };    // hidden input: rebuild does not match
});

// Times are given as DATA, not measured: provenance generation 12 s, rebuilding 214 s.
const PROVENANCE_S = 12, REBUILD_S = 214;
const THRESHOLDS = [
  ["signature is enough", (i) => i.signed, 0],
  ["signature + provenance document", (i) => i.signed && i.hasProvenance, PROVENANCE_S],
  ["signature + four verifiable fields", (i) => i.signed && i.hasProvenance && i.evidenceMatches, PROVENANCE_S],
  ["signature + reproducible build", (i) => i.signed && i.hasProvenance && i.evidenceMatches && !i.hiddenInput,
    PROVENANCE_S + REBUILD_S],
];

const BROKEN = REQUESTS.filter((i) => i.broken).length;
const S = [36, 6, 9, 16, 0];
const row = (s) => console.log(s.map((v, i) => String(v).padEnd(S[i])).join(""));
row(["threshold", "pass", "blocked", "wrongly blocked", "broken slipped / pipeline time"]);
for (const [name, rule, time] of THRESHOLDS) {
  const passed = REQUESTS.filter(rule);
  const blocked = REQUESTS.filter((i) => !rule(i));
  row([name, passed.length, blocked.length, blocked.filter((i) => !i.broken).length,
    `${passed.filter((i) => i.broken).length} / ${time * REQUESTS.length} s`]);
}
console.log("");
console.log(`requests ${REQUESTS.length}, genuinely broken ${BROKEN}, ` +
  `carrying an undeclared input ${REQUESTS.filter((i) => i.hiddenInput).length}, ` +
  `without a provenance document ${REQUESTS.filter((i) => !i.hasProvenance).length}; seed 87344`);

threshold                           pass  blocked  wrongly blocked broken slipped / pipeline time
signature is enough                 40    0        0               4 / 0 s
signature + provenance document     35    5        5               4 / 480 s
signature + four verifiable fields  31    9        5               0 / 480 s
signature + reproducible build      26    14       10              0 / 9040 s

requests 40, genuinely broken 4, carrying an undeclared input 7, without a provenance document 5; seed 87344

The second row turns this course’s most common misconception into a number. Requiring only the presence of a provenance document lets all four broken requests through — the document exists in broken requests too, because it is the build itself that produces the document. In exchange, 480 seconds go out of the pipeline and five legitimate requests are wrongly blocked. This is a gate whose marginal value is zero: a stage that fills in a field and compares nothing.

The third row catches all four broken requests with the same 480 seconds. The difference is a single operation: the document’s four verifiable fields are compared against objects the verifier obtains on its own. The wrongly-blocked count does not change, and slipped-through broken requests drop from 4 to 0. A provenance document’s value is not in its generation, but in its comparison.

The fourth row shows the lever’s price. Reproducible building catches no new broken request — all four were already caught in the third row — but it raises pipeline time from 480 seconds to 9,040 seconds and raises the wrongly-blocked count from 5 to 10, that is, a quarter of forty requests. This is the price of raising the verifiable-field count to 7, and whether that price is worth paying is decided by looking at the number of slipped-through broken requests, not the number of fields. A threshold that stalls one request out of four is, eventually, a threshold that gets bypassed.

Summary

• The provenance document is fourteen fields in four groups; 4 fields are verifiable, 10 are attested. What the verifiable ones share is that each is the digest of an object in the verifier’s hands.
• None of the remaining ten attested fields is minor: isolation level, network access, runner type, and base image cannot be tested. Of five deliberately wrong fields, 3 are caught, 2 are not tested.
• Reproducible building raises the verifiable-field count from 4 to 7; the three gained fields are inputs that feed into the output. The remaining 7 fields can never be tested, because they do not affect the produced bytes.
• 4 of twelve builds do not match on rebuild and only 1 is real; the false-mark rate is 75%.
• Requiring only the presence of a provenance document lets all 4 of 4 broken requests through and costs 480 seconds; comparing the four verifiable fields in the same time drops slipped-through broken requests to 0. The reproducible-build threshold catches no new broken request, and raises pipeline time to 9,040 seconds and wrongly-blocked requests to 10.

Next Step

The provenance document is built, verifiable and attested fields are separated, and the price of raising the threshold is written down. What is left standing is seven attested fields, and four of them describe a single subject directly: which environment the build ran in. Runner type, isolation level, network access, and environment-variable names are written in the document, and none of them can be tested — and because they cannot be tested, their values depend only on that environment actually having been set up that way.

The next lesson counts that environment item by item. The measure is no longer the document’s field, but the build environment’s own permissions: how many secrets the pipeline can access, how many are actually needed, how many steps break when network access is closed, and how many secrets could be exposed when a change from an outside contribution runs?