Trusting trust - building Nix from a manually verified seed

Every build you run rests on a tower of software you did not write and have never read. Your package manager was built by a compiler. That compiler was built by an older one, and that one by an older one before it, with a chain stretching back decades into binaries nobody on your team has ever looked at. You trust the source code because you can read it. But you run the binaries, and a binary can do things its source never mentions.

For most software, that gap is an abstract worry. For software that has to run in high-assurance, it is the whole problem.

Information security frameworks for high-assurance environments (eg, Secure by Design in the UK or BSI Grundschutz in Germany) mandate principled software supply chain security practices; this means tracing back software packages and source code, and, in the limit, of course also compiler infrastructure.

This post is about closing that gap for Nix, the package manager we use to build, well, almost everything. We got there by peeling back one layer at a time:

• We wanted to build Nix itself from source, with every dependency pinned and accounted for.
• But building from source needs a compiler we can trust, so we bootstrapped the standard build environment from a 256-byte seed rather than inheriting a pre-existing one.
• And a seed is only worth trusting if someone has actually read it, so we audited that seed and its bootstrap chain byte by byte, answering one of the oldest known attacks in computing.

The whole journey, from left to right in time, splits cleanly around the moment we have a Nix we can stand on:

The problem: you cannot read a backdoor out of a binary

In 1984, Ken Thompson gave a Turing Award lecture called "Reflections on Trusting Trust". He described a compiler backdoor with a vicious property: it could hide itself. A compromised compiler can recognise when it is compiling int login() and silently insert a backdoor. Worse, it can recognise when it is compiling itself, and re-insert both the login attack and the self-replication logic into the new compiler binary.

Once that has happened, the backdoor lives only in the binary. You can read the compiler's source code top to bottom and find nothing. You can rebuild the compiler from clean source, but you rebuild it with the compromised compiler, which quietly puts the backdoor back. You can trust the source, but you cannot trust the binary that interprets or compiles it.

Thompson's conclusion was bleak: "You can't trust code that you did not totally create yourself." There is, though, a way out that he hinted at and that the bootstrappable builds community has since made real. If you can start from a binary small enough to verify by hand, and grow everything else from there in steps you can each check, you never have to trust a compiler you did not watch being born.

That is the mental model for everything below: build up from something a human and their agent companion can fully read, and never inherit a binary you cannot account for.

Step one: building Nix from source

Nix is the tool we use to make builds reproducible. So it would be wrong for us if Nix itself arrived as a mystery binary from the internet. The first job was to build the Nix daemon from source, in a way we could ship and defend.

The output is a single, fully statically linked nix binary, linked against musl libc rather than glibc, with zero runtime shared-library dependencies. It runs on any Linux host without pulling in a single .so. Fewer moving parts at runtime means fewer things to trust at runtime.

We rebuild what we cannot otherwise account for

A modern Nix needs recent libraries, and a fully static build needs every one of them available as a static archive built with a compatible compiler. The distribution could not give us that for everything, so a number of dependencies are built from source inside the build rather than installed as pre-compiled packages.

We build a dependency from source whenever the packaged version would force us to trust something we cannot account for: for example when the distribution's version is older than Nix requires, when no static variant is packaged at all, or when the packaged static archive was produced by a different compiler than the rest of our toolchain and cannot be safely linked into a single binary. In each case, the alternative is to accept a pre-compiled blob whose provenance we cannot establish. Building from source is more work, but it is the difference between a dependency we can account for and one we take on faith, and accounting for every byte is the entire point of the exercise.

Every input to the build is then pinned. The base image is pinned by digest rather than a moving tag, so the same package set resolves every time. Every source checkout verifies that what we fetched matches an expected revision, so a force-pushed or rewritten tag fails the build loudly instead of slipping through. Source tarballs are checked against a known cryptographic hash before they are used.

An SBOM that cannot quietly drift

Pinning inputs is only half of trust; the other half is being able to say what went in. Every build emits a software bill of materials (SBOM) as CSV with columns name, type, usage, url, checksum, covering both the packages in the build container and the source-built dependencies, with checksums for each.

The detail we are quietly proud of is the usage column, which records whether a dependency's code actually ends up in the binary or is only used during the build. We do not maintain that list by hand, because hand-maintained lists rot the moment someone adds a dependency and forgets to update them. Instead we derive it programmatically from the package database: a package that ships a static archive under a standard library path gets classified as link (its code is in the binary); one that ships only headers or tools gets build; one that ships both gets both. The one blind spot is header-only libraries: they read as build but compile straight into the binary, so they really belong with link. Beyond that, adding or removing a dependency re-derives the SBOM rather than waiting on someone's memory, and a bill of materials you have to remember to update is one that will eventually lie to you.

Step two: where does the first compiler come from?

Here is the uncomfortable question that step one does not answer. We built Nix from source, but we built it with a compiler. And we built the standard environment (stdenv) that Nix uses to build everything else, also with a compiler. Where did that compiler come from?

If the honest answer is "it came pre-built with the distro," then we have done a lot of careful pinning and still planted our entire tree of trust in a binary we never read. This is exactly the seam Thompson's attack lives in.

The answer the Nix ecosystem reaches for is stage0-posix, the project nixpkgs uses as the literal root of its bootstrap. Instead of starting from a full compiler, it starts from a seed binary of a couple of hundred bytes and grows a real toolchain from there:

Each stage is built by the one before it. The crucial property is that the thing at the very bottom is small enough for a person to read in full, and everything above it is built from human-readable source by a tool you have already checked.

hex0: a compiler you can read in an afternoon

The seed is a program called hex0, and it is about the simplest "compiler" imaginable. It reads a text file of hex digit pairs, things like 7f 45 4c 46, and writes out the raw bytes those digits spell. It is a hand-rolled xxd -r -p, ignoring whitespace and comments.

What makes it the root of trust is that hex0 is itself written in hex, and the binary is tiny: just 256 bytes. Inside those bytes there is a minimal ELF header so Linux will load it, and the rest is around a hundred instructions doing open, read, parse-a-nibble, and write. It is small enough that one person can sit down and account for every byte.

From there the chain climbs in steps you can each verify: hex0 assembles hex1, which adds labels; hex1 assembles hex2, which adds more; and on up through a macro assembler and a tiny C compiler to M2-Planet, a compiler for a subset of C, simple enough to be built by those primitive tools below it yet capable enough to compile the larger, more complete compilers above it. M2-Planet is where the chain crosses from hand-written assembly into real C, and from there it climbs to GCC and a full stdenv. No step inherits a binary from outside the chain.

Our tooling fetches the stage0 source, prepares it exactly the way nixpkgs does, and verifies the result hashes to the same value nixpkgs expects, so the source feeding our bootstrap is provably semantically equivalent to the upstream source.

Step three: auditing the seed, byte by byte

Maintaining the bootstrap source is necessary but not sufficient. The entire argument rests on the claim that the seed and the early stages do exactly what they say and nothing more. A claim like that is worth only as much as the audit behind it. So we reviewed the bootstrap chain at the byte level and wrote down what we found.

For the 256-byte seed, that meant 121 distinct checks with zero failures:

• The ELF header, field by field, all 20 of them, down to the entry point landing exactly where the header and program header end.
• Every instruction, each opcode checked against the CPU instruction set, with all 256 bytes accounted for: 52 of ELF header, 32 of program header, 172 of code, and no leftover padding that might conceal stray instructions.
• Every jump target, each relative offset computed by hand and confirmed to land on a real label rather than into the middle of another instruction.
• Every syscall. This is the heart of it. The seed makes exactly five int 0x80 calls: two open, one read, one write, one exit. That is the complete list. No network. No mmap. No ptrace. No fork. No exec. No known kernel/OS exploits To double-check our analysis, we then asked a bunch of LLMs to look at hex0; they came to the same conclusion: it's a file-to-file converter and nothing else.

We then reconstructed the seed from its hex source and recorded the SHA-256 of the result, so the exact binary we audited is pinned rather than described.

We applied the same exhaustive syscall audit up the chain to hex1, hex2, catm, M0, and the small C compiler cc. Each touched only the file and memory syscalls its job requires, with no network or process-spawning syscalls anywhere they should not be. And we cross-verified each early stage against independent representations of the same program: the .hex0 source, a GAS assembly version, and an M1 macro-assembly version. A discrepancy in any one would stand out against the other two.

Answering Ken Thompson

This is what actually defuses the Trusting Trust attack, so it is worth stating plainly.

Thompson's backdoor survives because the compiler that builds the compiler is itself an unread binary. The stage0 chain removes that unread binary. The only pre-built thing is the seed, and the seed is small enough that "read it yourself" stops being a figure of speech. hex0 is also self-hosting: the seed run against the hex0 source reproduces the seed, so the one binary you start from can be checked against the source you can read. Every stage above it is built from human-readable source by a tool you have already verified. There is simply nowhere for a self-replicating compiler backdoor to hide, because there is no inherited compiler to carry it.

Every file came back the same way: no backdoors, no hidden functionality, no unexpected syscalls.

The review was not purely a rubber stamp, either, which is how you know it was a real review. It flagged that these single-shot build tools map their memory read-write-execute, which is fine for a tool that runs once and exits, and recorded it explicitly rather than ignoring it. It noted that the early assemblers do not check whether open() succeeded, so a missing input fails the build silently rather than loudly, low-risk for trusted build files, but worth recording. And it caught a naming inaccuracy in one opcode macro, where a shift instruction carried a mnemonic that did not quite match its encoding. None of these are vulnerabilities. All of them are the kind of thing you only find when someone is genuinely reading every byte.

What this buys us, and what it does not

It is worth being precise about the boundaries of the claim, because over-claiming security is its own kind of insecurity.

What we have is a Nix toolchain whose every layer we can account for: a statically linked Nix built from pinned, SBOM'd sources, standing on a stdenv grown from a seed we have read byte for byte and audited for exactly what it does. We do not inherit a compiler we never looked at. That is a real and unusual property, and it is the foundation the rest of our supply-chain work builds on.

What it is not is the finish line. A trustworthy toolchain is link one in a chain that also has to cover the thousands of dependencies you build with it, the registries you pull them from, and everything that runs in production afterwards. It also rests on parts of the environment we have not bootstrapped away: the kernel and operating system the audit runs on, and the rest of the distribution's tooling. We shrink what we take on faith rather than remove it, and running the audit on independent systems and comparing the results is what makes a coordinated backdoor there impractical.

It is also worth being honest about one loop we have not yet closed. The bootstrap above runs inside the Nix we built in step one, and that Nix was compiled by a toolchain we inherited rather than grew. A sufficiently clever backdoor in it could, in principle, still lie about its own build. Rebuilding Nix inside the audited stdenv, and checking the result against the binary we started from, is what would finally close Nix's own loop.

The same principle extends to all of those: start from something you can verify, and never inherit what you cannot account for. That is where this work goes next.

For now, the part that felt almost philosophical when Thompson posed it in 1984 (can you ever really trust a tool you did not build yourself?) has a concrete, auditable answer sitting in our build pipeline. It starts with 256 bytes you can read by hand.

Author: Matteo B