Verifying Provenance by Rebuilding

Every other verification in an image supply chain ultimately rests on someone’s assertion. A signature asserts that a key endorsed a digest. A provenance statement asserts that a builder ran particular inputs and produced particular output. A scan result asserts that a particular set of packages was present. Each assertion can be checked for internal consistency, and none can be checked for truth without either trusting the asserter or repeating the work. Rebuilding is repeating the work, and it is the only check that converts a claim into evidence.

What a rebuild establishes

An independent rebuild takes the inputs a provenance statement names (a source revision, a base image digest, a set of build parameters) and runs them through a build system to produce an artifact. If the resulting digest equals the published digest, then the published artifact is consistent with those inputs, given that build system’s determinism.

The qualifier matters. A match proves the inputs produce this output; it does not prove that the publisher used those inputs. A publisher could have built a malicious artifact from different inputs, published a provenance statement naming innocuous inputs, and the rebuild would produce the innocuous artifact and fail to match, which is the detection case. But a publisher could also have built the malicious artifact from the innocuous inputs, by exploiting a nondeterministic or compromised build step, in which case the rebuild reproduces the malicious artifact and matches. Rebuilding detects substitution of inputs. It does not detect a build that is compromised in a way that is itself deterministic.

A mismatch is therefore conclusive evidence of a problem, while a match is strong evidence of consistency. This asymmetry is why rebuild verification complements attestations rather than replacing them: the attestation says what happened, and the rebuild says whether that claim holds.

The comparison must be at the right granularity

Comparing image digests answers one question: are these the same bytes. When the answer is no, it says nothing about why, and the search space is every layer, every file, and every metadata field.

Comparing manifests narrows it to the set of layer digests. A diff at this level tells which layers differ, and the position of the first differing layer localizes the cause to the instruction that produced it, since layers correspond to build steps in order. This is the comparison worth starting with.

Comparing diff IDs rather than compressed digests removes compression settings from the comparison. Two builds with identical filesystem content but different compressors have different manifest digests and identical diff IDs. A rebuild that matches on diff IDs but not on blob digests has established that the content is the same and the packaging differs, which is a much cheaper problem to fix than a content difference.

Comparing unpacked trees removes tar serialization from the comparison. If diff IDs differ, unpack both layers and compare the file trees with metadata (mode, ownership, size, content hash) to distinguish “different files” from “same files, different metadata”. This is where the diagnosis becomes actionable, because the fix differs entirely depending on which side of that line the mismatch falls.

def compare_layers(a, b):
    # a and b are extracted directories for the same layer index.
    for rel in sorted(walk(a) | walk(b)):
        fa, fb = os.path.join(a, rel), os.path.join(b, rel)
        if not (os.path.exists(fa) and os.path.exists(fb)):
            yield ("missing", rel)
            continue
        sa, sb = os.lstat(fa), os.lstat(fb)
        if (sa.st_mode, sa.st_uid, sa.st_gid) != (sb.st_mode, sb.st_uid, sb.st_gid):
            yield ("metadata", rel)
        elif stat.S_ISREG(sa.st_mode) and filehash(fa) != filehash(fb):
            yield ("content", rel)

A comparison that reports content differences at many paths usually indicates a timestamp embedded in a compiled artifact or a generated file that records the build time. A comparison that reports metadata differences across every path indicates the build ran as a different user or with a different umask.

Tar is where rebuilds usually fail

The tar format records, per entry, the modification time, uid, gid, uname, gname, mode, and the entry name. None of these are determined by file content, and all of them are included in the diff ID. A rebuild that runs on a different day produces different mtimes unless the build normalizes them.

Normalization has to happen at the point the tar is written, not at the point the files are created, because any tool that writes a file during the build sets its own timestamp. A build that normalizes at the end must walk the whole tree and rewrite metadata, which is a pass over every file; a build that normalizes at the tar writer pays only for the entries it emits.

The standard normalizations are: mtime set to a fixed epoch, uid and gid set to zero, user and group names empty, and entries sorted by name with directories before their contents. Each has a cost. Fixed mtime destroys any legitimate timestamp semantics, which matters for images that ship files whose mtime is read by an application. Zeroed ownership breaks images where a service runs as a non-root user selected by file ownership, unless the build sets ownership explicitly. Sorting changes the order in which a filesystem image is laid out, which is irrelevant for correctness and can affect locality during unpacking.

The tar format itself has variants. The original format limits path names and file sizes; extensions in the POSIX pax format and the GNU format lift those limits with additional header records that are themselves part of the stream and therefore part of the hash. A build that switches tar implementations can change which extension records are emitted for the same files, producing a different stream with identical content.

# Compare two layer tarballs by content and metadata, ignoring nothing.
tar --full-time --numeric-owner -tvf layer-a.tar > a.txt
tar --full-time --numeric-owner -tvf layer-b.tar > b.txt
diff a.txt b.txt

Listing with numeric ownership and full timestamps makes the metadata visible. A plain listing hides the seconds on the timestamp and resolves ownership to names, which are exactly the fields that differ.

Compression is the last, cheapest difference

If diff IDs match and blob digests do not, the difference is the compressor. Gzip output depends on the deflate implementation, the level, the block size strategy, and the header. The header carries an mtime field that some implementations populate from the input, and a name field that some populate from the input filename.

Registries deduplicate by blob digest, so a rebuild that differs only in compression stores a second copy of the same content. This is a storage cost rather than a correctness problem, and it is invisible unless someone compares manifest digests. For rebuild verification it is a false negative: the rebuild succeeded in every meaningful sense and the digest comparison reports failure.

The remedy is to compare at the diff ID level when the goal is to establish content equivalence, and to compare blob digests only when the goal is to establish bit-for-bit identity of the published artifact. The two goals are different and the second is stricter than most supply-chain policies need.

Source-side nondeterminism

The build environment is not the only source of variance. The source tree itself can produce different outputs from the same revision, and no amount of tar normalization helps.

Generated files that embed a version control identifier, a build timestamp, or the hostname produce different content on every build. Dependency resolution that consults a mutable index produces different dependency sets when the index changes, which is why lockfiles with content hashes are the mechanism that makes a rebuild meaningful: the lockfile pins versions and, in the better formats, the artifact hashes of each dependency.

Language runtimes and compilers embed paths and versions in their output. A build that compiles in a different directory produces object files containing different debug paths, and a build with a different compiler patch version produces different code. Neither is fixable by packaging changes; both require the rebuild to use a matching toolchain, which means the provenance has to record the toolchain identity for the rebuild to be a fair comparison.

Base image drift is the same problem one level up. If the provenance records a base image tag rather than a digest, the rebuild pulls whatever the tag points to now, and the comparison fails for a reason that has nothing to do with the build. This is why Content Digests and Why an Image Tag Is Not an Identity treats tag resolution as the weak link in the chain: a provenance statement that names a tag has not named an input.

Making rebuilds practical

A rebuild is expensive: it repeats the entire build, including dependency resolution and compilation, for every artifact under verification. The cost is why rebuild verification is applied selectively (to release artifacts, to artifacts entering a high-trust environment, or to a sample of the total) rather than to every pull.

The practical structure is a separate builder, configured to match the attested builder’s toolchain and to normalize packaging identically, fed from the provenance statement’s inputs. The comparison runs from the manifest down. A match is recorded against the digest and can be cached with it, since the property being verified (that these inputs produce this digest) does not change unless the inputs or the builder change.

The cache is where rebuild verification meets the rest of the supply chain. A cached verification result is an assertion with a lifetime, and its lifetime should be bounded by the lifetime of the attestation it confirms, not by convenience. If the trust root that makes the builder’s attestation valid rotates, a cached rebuild result from before the rotation is a statement about a claim that is no longer being made.

The inputs to the rebuild are themselves artifacts with their own supply chains: the source revision is a signed commit or is not, the base image has its own provenance or does not, the toolchain image has a digest. Pull-Through Caches and Where the Trust Anchor Sits applies to each of them, and a rebuild whose inputs were fetched through a channel the publisher controls has verified nothing about the publisher. The recursion terminates at trust anchors that are configured rather than fetched, and the number of hops from an image to such an anchor is the measure of how much of the chain is actually verified.