Bit-Reproducible Builds and Nondeterministic Actions

A build is bit-reproducible when running it twice from identical inputs in different environments produces byte-identical outputs. That is a stronger property than “compiles successfully twice” and a weaker one than “correct”: two builds can produce the same corrupted binary. Its value is that it makes the build relation a function, which is what every cache, every distributed worker, and every attempt to verify a binary against its source depends on.

Where the variation enters

Nondeterminism is not usually in the algorithm being compiled. It is in the metadata the toolchain embeds and in the order in which it happens to process things.

Paths are the most common source. Debug information records the name of the source file as the compiler saw it, which is an absolute path when the build was driven from one, and includes the working directory and often the user name. Two checkouts in different directories produce object files that differ in those strings. Compilers provide flags to rewrite such prefixes, mapping a build-root prefix to a canonical value so that the recorded path is stable, and those flags are the standard remedy. Without them, the difference is not cosmetic: the strings appear in the binary, so the digests differ and nothing downstream can be shared.

Time is the second. The C preprocessor defines macros that expand to the date and time of compilation, and the standard specifies their format as fixed-width text; any source that uses them changes its output on every build. Build systems provide a means of supplying a fixed timestamp through the environment so that tools which consult it, such as archivers, documentation generators, and anything else that stamps a produced artefact, write a constant instead of the current instant. Archive formats carry their own timestamps per member, the gzip container carries a modification time field, and the deterministic mode of the archiver exists specifically to zero the member timestamps, owner and group identifiers, and to fix the member mode. Distributions that publish reproducible packages build from a declared epoch and pass it through to the compilers, the archivers, and the packagers.

Order is the third and the most subtle, because it comes from the compiler’s internal use of hash tables and from the build’s own parallelism. A compiler that iterates a hash table keyed on symbol names can emit functions, relocation entries, or debug records in an order that depends on the hash seed or on insertion history rather than on the source. The results are usually semantically identical and bytewise different. Compilers expose a way to fix the random seed used for such generated names, which removes the run-to-run variation in a single binary but does not by itself make two different compiler invocations agree, because the insertion history may itself differ. Linking in parallel, or producing an archive from a set of object files in filesystem order rather than sorted order, produces a different output for the same input set; sorting the inputs before the command is the fix, and it belongs in the build rule rather than in the tool.

A fourth group is environmental values that leak into output: the locale, which affects collation and message text; the host name, which appears in build metadata and sometimes in generated code; and the identity of the user, which appears in debug information and in archive ownership. Each is a channel from the environment into the artefact, and each is closed either by scrubbing the environment (the hermetic approach described in Hermetic Actions and Undeclared Inputs) or by declaring the value as an input so that it is constant by construction.

Detecting divergence

Since the sources of variation are numerous and the effect of each is local, the practical method is empirical: build the same inputs twice under deliberately different conditions and compare output digests.

Conditions that catch the most: different build directory names, different home directories, different user and host names, different wall-clock times, different locale settings, and different parallelism. A single build compared against itself under none of those variations proves nothing; the point of the exercise is to vary the environment while holding the inputs fixed.

# Build the same inputs under two different conditions and compare the
# artefacts byte for byte; identical digests mean the action is a function
# of those inputs, and a difference localises the nondeterminism.
sha256sum build-a/app build-b/app
cmp -s build-a/app build-b/app || echo "the two builds differ"

Comparing whole-artefact digests establishes that something differs; locating the difference requires reading the two artefacts side by side. For binary objects and libraries, a byte-level comparison of the two files localises the divergence to an offset, and the bytes at that offset usually name themselves: a path string, a timestamp, an ordering difference. For archives, comparing the sorted member lists and each member’s stored metadata separates ordering differences from content differences. For the build as a whole, recording the digests of every intermediate output and comparing the two runs’ records narrows the search to the first action whose output diverged, which is far cheaper than comparing the final artefact when the final artefact is large.

The limitation of this technique is that it only finds nondeterminism that is sensitive to the varied conditions. An action whose output depends on an input nobody varied (the contents of a file in a fixed location, the result of a network request) will agree across both builds and still be nondeterministic in the sense that matters, which is that it is not a function of the declared inputs. Catching that case requires the input declaration to be checked independently, by sandboxing or by tracing accesses, rather than by comparison.

Reproducibility is what makes cache sharing sound

The reason reproducibility appears in a build-systems discussion at all is the interaction with caching. A cache assigns an output to a key derived from declared inputs. If the action is deterministic, the mapping is well defined and a hit from any machine is valid. If it is not, the cache records whichever result arrived first and serves it to everyone else, and the resulting failures appear far from their cause: a symbol missing from a binary that compiled fine on the machine that populated the cache.

The failure is not hypothetical in a distributed fleet, where the first machine to run an action is chosen by load balancing rather than by intent. Two workers with different conditions produce different bytes for the same key, and the cache picks one arbitrarily. The mitigation is twofold: make the action deterministic, which requires the normalisations above, and include everything that varies in the key, which requires hermeticity. Neither alone is sufficient: a perfectly hermetic action that stamps the current time into its output still produces a different result per run, and a perfectly deterministic action that reads an undeclared file still produces different results on machines where that file differs.

The interaction also runs the other way. Early cutoff, described in Content-Hash Caching and Early Cutoff, depends on comparing an output’s digest before and after re-running an action. A nondeterministic action never matches, so the comparison always reports a change and the optimisation silently does nothing. A build system can detect this pattern: an action that is re-run and whose output changes despite unchanged inputs is either nondeterministic or under-declares its inputs, and both deserve attention.

Verifying a binary against its source

The property that reproducibility enables beyond caching is independent verification. Given the source tree, the recorded build recipe, and the toolchain, an independent party can rebuild and compare the result against the binary that was distributed. A match does not prove the binary is free of defects, but a mismatch proves that the binary was not produced by that recipe from that source, which localises the question of trust to a set of inputs that can be inspected.

For this to be meaningful the variable environment must be declared as part of the recipe. The build’s timestamp, its directory layout, the toolchain identities, and the ordering rules all have to be specified, so that “the same inputs” is an objective statement rather than an approximation. That requirement is the same one a content-addressed cache imposes, which is why the two problems converge on the same answers: fixed timestamps, canonical path mapping, sorted inputs, declared toolchains, and an action description complete enough that reproducing it does not require guessing.

What reproducibility cannot promise is that the compilation is idempotent with respect to things outside the declared input set. A compiler with a genuine bug that depends on address-space layout, a code generator that queries a service, or a build that reads a file whose absence is silently tolerated will all still produce a self-consistent result that another machine cannot reproduce. Closing those channels is exactly the job of hermetic execution, and the two properties together (deterministic given the declared inputs, and seeing only the declared inputs) are what turn a build into a function of its source rather than a description of what happened on one machine on one afternoon.