Reproducible Builds and the Sources of Byte-Level Nondeterminism

Two builds of the same source tree with the same compiler are not, by default, the same bytes. The difference is not in the code: it is in timestamps, ordering, paths, and the incidental state of the machine that produced the artifact. Reproducibility is the property that those incidental inputs have been eliminated, so that the artifact is a function of the declared inputs alone. When that property holds, an independent party can rebuild and compare, which turns a binary artifact into something auditable.

The work is in enumerating the incidental inputs. They are more numerous than they appear, and each one has an independent fix.

Timestamps are the first and most obvious leak

A tar archive stores a modification time per entry in its header. A ZIP archive stores a modification time per entry, plus, in some variants, an extended timestamp field. A file’s mtime is the wall-clock time the file was written, so any archive created from freshly compiled objects carries the build time.

The convention that fixes this is SOURCE_DATE_EPOCH: a single integer, seconds since the Unix epoch, that a build may consult instead of the current time. Tools that honour it clamp all embedded timestamps to that value. The variable is specified by the reproducible-builds project rather than by POSIX or a language standard, and its adoption is what makes cross-tool comparisons possible at all: two different archive tools that both honour the same epoch produce the same timestamps.

Clamping has a second-order effect. A tar header stores the modification time as an octal digit string in a fixed-width field, so a timestamp too large for that field has to be written using the GNU base-256 extension, which not every archive reader accepts. ZIP has the opposite problem: its DOS timestamp cannot represent a date before 1980, so a very small epoch must be clamped upward to the earliest representable time. Both cases mean the chosen epoch also constrains the encoding, which is why the value is normally taken from the source rather than picked arbitrarily.

ZIP is worse than tar because the classic format stores a DOS timestamp with two-second resolution and a limited year range, and because its central directory duplicates metadata stored in local headers. A tool that clamps the local header time but not the central directory time produces an archive that differs between builds in a way that survives extraction. The extended timestamp extra field, if present, must be clamped as well.

Ordering and iteration

Directory listing order is not stable across filesystems and is not guaranteed by any POSIX interface. A build script that walks a directory and appends entries to an archive in traversal order produces an archive whose entry order depends on the filesystem’s internal hashing or on creation history. Two machines with the same files can produce differently ordered archives.

The fix is to sort. Sorting must be by a defined key, and the natural key is the entry’s path as stored in the archive, byte-compared. Sorting by locale-sensitive comparison introduces a dependency on the locale environment, which is exactly the kind of incidental input reproducibility tries to remove.

The same problem appears inside compiled artifacts. Hash tables keyed by pointer values iterate in an order that varies with address-space layout randomisation; a compiler that emits symbols, sections, or strings in hash-table iteration order produces different output across runs. Sorting before emission, or using an insertion-ordered structure with a deterministic insertion sequence, is the standard remedy. Debug information is a common carrier: type ordering and string tables can be large, and their order affects the artifact size and content.

Parallelism compounds it. A build that compiles translation units concurrently and links in completion order can produce different object ordering depending on scheduling. Determinism requires that the merge step be order-independent or that the ordering be imposed after the fact.

Paths, environment, and identity

An artifact that embeds absolute build paths leaks both the build machine’s layout and its user names, and produces different bytes when built in a different directory. The general remedy is to build in a fixed path, often by bind-mounting the source into a container at a constant location, or to pass a path-mapping flag so the compiler rewrites recorded paths.

Environment variables are a broader version of the same problem. A compiler that reads CFLAGS from the environment, or a build script that reads HOME, or a tool that consults the locale, produces output that depends on state not captured in the source. The discipline is to declare every input explicitly and to build in an environment where undeclared variables are absent or fixed.

Identity is the hardest. Build IDs, version strings derived from version control, and embedded user or host names all need a defined value. Version control metadata is especially awkward, because a build from a dirty working tree has no meaningful revision. Reproducible builds typically require a clean tree and derive the version from the commit identifier, which is then the same for every builder of that commit.

Randomness and time-derived identifiers are a related class. A build step that generates a UUID per artifact, or a temporary filename embedded in a debug string, breaks determinism outright. Where such a value is genuinely needed, it must be derived from declared inputs, for example by hashing the content it accompanies.

Why archive-level determinism is harder than object-level

Compiling the same source twice with the same compiler and flags can be made deterministic with the measures above. Producing the same distributed artifact requires more, because packaging adds a layer.

The packaging step chooses a compression implementation. RFC 1952 defines the gzip container but not the compressor’s choices: block boundaries, match lengths, and the lazy-match heuristic are implementation-defined, and different zlib versions or compression levels produce different compressed bytes for identical input. A reproducible build must therefore pin the compressor as well as the compiler, and a rebuild on a system with a different zlib produces a different artifact even though the uncompressed content is identical.

This is why some ecosystems compare the uncompressed archive rather than the compressed file. Verifying that two .tar.gz files decompress to byte-identical tar streams is a weaker claim than byte-identical compressed output, and it is often the only achievable one across heterogeneous rebuild environments.

File metadata inside the archive is a second packaging-layer input. Ownership fields default to the building user’s uid and gid; a reproducible build sets them to a fixed value, conventionally root. Permission bits must be normalised, since the source checkout’s umask affects the modes of generated files. Extended attributes and access control lists, if carried, must be either excluded or normalised, because they depend on the filesystem.

A third is the choice of what to include. File globs that match generated files, or that include editor backups, produce a set that depends on the build directory’s state. The inclusion set must be explicit.

Verification and its limits

Verification requires a party to rebuild independently and compare. Comparison can be at the artifact level, which is strongest and most fragile, or at a normalised level that tolerates compression differences.

The mechanics matter more than the principle. A verifier needs the exact source, the exact toolchain, and the exact build instructions. Toolchain pinning is usually the weakest link: a compiler patch release can change code generation, and a rebuild with a slightly different compiler produces different output for legitimate reasons. Builds that are reproducible across different toolchains are a much stronger property and correspondingly rarer; most projects claim reproducibility for a defined environment, which is the same scope an environment directory or container image records, as described in Prefix-Based Environments and Why Activation Is Only Path Surgery.

The payoff is that a matching rebuild is evidence about the artifact’s provenance. If a binary published by a project can be rebuilt from its public source by an unrelated party and the bytes match, then the binary corresponds to that source, at least for the parts of the build that were reproduced. This does not prove the source is safe, and it does not prove the publisher did not also have a modified source tree, but it removes the possibility of an artifact built from different code than the one published.

That gap is why reproducible builds are usually paired with a signature over the artifact and a published build recipe. The signature says who published it; the rebuild says the published bytes correspond to the published source; the recipe says how to reproduce the correspondence. Each is useless alone.

The verification loop in practice is a comparison over a manifest of digests:

import hashlib, json, pathlib

def manifest(root):
    out = {}
    for p in sorted(pathlib.Path(root).rglob("*")):
        if p.is_file():
            out[str(p.relative_to(root))] = hashlib.sha256(p.read_bytes()).hexdigest()
    return out

def diff(a, b):
    only_a = sorted(set(a) - set(b))
    only_b = sorted(set(b) - set(a))
    changed = sorted(k for k in set(a) & set(b) if a[k] != b[k])
    return {"only_first": only_a, "only_second": only_b, "changed": changed}

Reporting three categories rather than a boolean is what makes the output actionable: a file present in one build and absent in the other is an inclusion-set bug, while a file present in both with different bytes is usually a timestamp or ordering bug inside that file.

The residual: what cannot be made deterministic

Some nondeterminism is irreducible without changing the language or toolchain. Compilers that perform profile-guided optimisation depend on profile data; if the profile is part of the declared inputs, the build is reproducible with respect to those inputs, which is a weaker but still useful claim. Just-in-time compilation at runtime is outside the artifact entirely.

Floating-point code generation can vary with instruction-set dispatch decisions if the build probes the host CPU. Building for a fixed target baseline removes the variation and costs performance on newer hardware.

Debug information embedding build paths is fixable, but debug information embedding type ordering is only fixable if the compiler sorts, which some do and some do not. Projects that need reproducible debug artifacts sometimes strip them, trading debuggability for determinism.

The honest position is that reproducibility is a property of a defined build environment, and every claim of it should name the environment. The verification machinery in Content Addressing and What Artifact Hashes Actually Prove then does something stronger than it otherwise could: the hash identifies a byte sequence that another party can independently produce.