Reflections on Trusting Trust

Thompson built the argument in stages in his 1984 Turing Award lecture, and it is worth following the structure because each step is individually unremarkable and the conclusion is not.

Step one: a program can print itself. A quine is a program whose output is its own source. This is a well-known curiosity and establishes only that self-reference is mechanically possible.

Step two: a compiler can recognise a pattern and behave specially. Thompson's example was the C compiler learning to compile the escape \n — a fact about the character set that has to be hard-coded once, because the compiler's own source cannot use an escape the compiler does not yet understand. Once you accept that a compiler contains knowledge not derivable from the program it is compiling, the door is open: a compiler could recognise, say, the login program and insert an extra accepted password.

Step three: the compiler can recognise itself. Now teach the compiler to recognise that it is compiling *the compiler*, and in that case to insert both the login backdoor and this self-recognition logic into the output. Compile the compiler once with this modified version. Then delete the modification from the source entirely. The next compiler, built from clean source by the infected binary, contains the backdoor. So does the one after it. The source is clean, every subsequent source is clean, and every binary is compromised.

The result is not a trick about compilers specifically. It is a general observation: a system that reproduces itself can carry behavior that exists in no source anywhere, and no amount of source review will find it, because there is nothing in any source to find.

The conclusion Thompson drew is the one worth carrying: "You can't trust code that you did not totally create yourself." Not "compilers are dangerous" — the compiler is an illustration of a general property that applies to every self-reproducing tool in a chain, and the chain includes the assembler, the linker, the libc, the kernel and the hardware.

It is easy to over-read this as fatalism, and it is more useful read as a statement about *where* trust lives. Source review establishes properties of source. Trusting a binary requires either building it yourself with a toolchain you trust — which regresses — or establishing the correspondence between source and binary by some means that does not rely on the artifact under examination.

It is equally easy to under-read it. "Nobody would go to that trouble" is not a rebuttal; it is a risk assessment, and it has been wrong before about other supply-chain attacks that were also considered too elaborate. The XZ backdoor of 2024 was a multi-year social engineering effort culminating in a payload hidden in test fixtures, which is a different technique with the same structural insight: put the attack where nobody is reading.

The practical relevance today is less about someone backdooring GCC and more about the reasoning pattern. Every time a build downloads a binary — a stage 0 compiler, a container base image, a language server, a pre-built dependency — the same gap opens between what was reviewed and what runs. [[toolchain-trust]] enumerates how wide that gap is in an ordinary build.

David A. Wheeler's 2005 work — later his doctoral dissertation — is the known countermeasure, and it is a genuinely clever piece of reasoning rather than a mitigation. It establishes, under stated assumptions, that a compiler binary corresponds to its source, using a *second, independent* compiler that is itself allowed to be untrusted.

The technique: let A be the compiler binary you want to check and S be its source. Let B be any other compiler for the same language, from an independent lineage — a different vendor, a different implementation, ideally a different heritage entirely. Compile S with B, producing X. X is probably a poor compiler — slow, badly optimized — but if B was honest it implements what S says. Now compile S with X, producing Y. And compile S with A, producing Z.

If A is faithful to S, then A and X implement the same source and should produce identical output from identical input, so Y and Z must be byte-identical. If A contains a self-reproducing modification not in S, it inserts that modification into Z and X does not insert it into Y, so they differ. The check succeeds unless *both* A and B contain the same attack — which, for genuinely independent compilers, is a much stronger assumption than either being compromised alone.

The catch is the prerequisite, and it is the reason this connects directly to the next lesson: the comparison requires that compilation be deterministic and that the compiler be reproducible, or "byte-identical" has no meaning. Wheeler's dissertation makes this precondition explicit, and it is why the reproducible-builds movement and the trusting-trust problem are the same engineering programme viewed from two directions.

For almost every engineer the answer is not to run diverse double-compiling. It is to understand what the argument implies about ordinary practice, and to prefer the practices that narrow the gap it identifies.

Reproducible builds are the most valuable one, and they are the direct descendant of this argument: if many independent parties build the same source and get byte-identical output, then a compromise of any one builder is detectable. That is a practical, deployed version of the same reasoning, and it is what Debian, Arch, F-Droid and the Reproducible Builds project have spent a decade on — see [[reproducible-compilation]].

Bootstrappability is the second, and reduces the size of what has to be trusted rather than verifying it. Shrinking the unauditable seed from "a compiler binary somebody built in 2019" to "a few hundred bytes of hex a human could read" is a real reduction in exposure even though it does not eliminate the problem.

And the third is simply to know how large the trusted base actually is, which is the subject of [[toolchain-trust]] and is usually much larger than people expect.