Nix Closure Structure and Transitive Dependency Graphs

A compiled binary in the Nix store, if any file inside its store path contains the hash substring of another store path, has that path recorded by Nix as a runtime reference. Take a built copy of the hello program and glibc 2.31, stored at a path like /nix/store/9df65igwjmf2wbw0gbrrgair6piqjgmi-glibc-2.31. If the hash substring 9df65igw… turns up anywhere inside the hello store path, Nix records glibc as a runtime reference of that binary. This is not a convention or a best practice; it is how the Nix reference manual describes the mechanism in plain terms, stating that Nix determines potential runtime dependencies between store paths by scanning for hash parts of store paths.

The scan works at the binary level, independent of what a developer wrote down. A dependency that leaks into a compiled artifact through a string literal, an rpath entry, or a pkg-config reference gets captured whether or not anyone declared it in the build instructions. And the process doesn't stop at one hop. Each store path discovered this way is itself scanned for further hash substrings, and the walk continues recursively until no new references turn up. The complete set of store paths reachable this way, that is the closure.

Compare this to how most package managers handle dependencies. A package.json, a requirements.txt: these are declarations, lists a maintainer wrote by hand and hopes are complete. If a maintainer forgets to list a transitive dependency, nothing catches the omission until a user runs the software somewhere that transitive piece happens to be missing. Nix inverts this relationship. Rather than trusting a human's account of what the software needs, it inspects the artifact itself and builds the dependency graph from physical evidence found inside it.

The structural guarantee the closure model provides

That scanning mechanism produces something stronger than a report; it produces an enforced rule. The Nix reference manual states the guarantee directly: Nix always maintains the existence of the transitive closure of a store path under the references relationship, and it is therefore not possible to install a store path without having all of its references present. Because the closure is maintained transitively and checked at install time, deploying a store path without one of its dependencies is structurally impossible, not merely unlikely or something a scanner might catch after the fact. That distinction, between "probably fine" and "cannot occur," is the entire basis for everything the closure model is later asked to support.

The guarantee holds because every build in Nix behaves as a pure function: the same source code, build scripts, compiler version, and every transitive dependency down to libc will always produce the same output. Inputs are identified by cryptographic hash, so a store path's name encodes the artifact's full provenance. When a dependency changes version, it doesn't overwrite what was there before; it occupies an entirely new store path with a new hash, leaving the old one untouched.

This same property means two upstream libraries can each require a different, conflicting version of some shared library without conflict. Instead of forcing a single global version and hoping neither caller notices the substitution, Nix lets each package specify the exact dependency identity it was built against, and multiple versions of the same library coexist peacefully because they occupy distinct store paths.

Set this against how a conventional Dockerfile builds an image: a line like apt-get install pulls whatever package version happens to be current on the day the build runs. A CI image built Monday and a hotfix image built Wednesday can differ in libssl behavior because Ubuntu pushed a security update in between, and the tests never catch it. No structural property in the Dockerfile model prevents that drift; only Nix's closure guarantee does.

Nix Flakes extend the closure guarantee to the project level

The per-package guarantee only matters if it scales to the actual unit of work most teams care about: a whole project with its own tree of external dependencies, not a single artifact in isolation. Nix Flakes extend the same hash-pinning logic from an individual package up to the complete input graph of a project, so the closure guarantee holds not just inside nixpkgs but across every external dependency a project declares.

The mechanism lives in the flake's lock file. Each pinned input carries a handful of fields, among them lastModified, narHash, owner, repo, rev, and type, enough information between them to reconstruct the exact source tree an input came from. The narHash field matters most for integrity: if an upstream repository changes its content without changing the commit reference it's pinned to, the narHash check fails and the build is refused. Tampering, in other words, is caught at the build boundary rather than discovered later at runtime by whoever happens to be running the software.

Any engineer who checks out a repository and runs nix develop gets the same tool versions, bit for bit, regardless of whatever happens to already be installed on their own machine. Because the lock file is a versioned artifact committed alongside the code, this reproducibility isn't limited to the current state of the repository. It extends to any historical commit, since the lock file at that commit describes the exact environment that existed then.

It helps to be precise about where this mechanism's authority begins and ends. Flakes pin the nixpkgs revision and other flake inputs; the underlying closure guarantee then applies within that pinned package set. The two mechanisms compose rather than compete: flakes answer the question of which package set and which external sources to use, and the closure guarantee answers the question of what's structurally required once that set is fixed.

How the closure behaves in practice

None of this is theoretical. But the same mechanism that makes closures trustworthy can also make them larger than anyone intended, because the scan has no way to distinguish a dependency the program actually needs from one that merely left a trace behind.

The reference manual's own canonical example involves a compiler. If a build accidentally embeds a reference to the compiler used to build a program, perhaps through a debug string or an uncleaned build artifact, the compiler and its entire closure appear in the program's runtime closure, even though the program itself never calls the compiler once it's running. A single stray reference can drag in a large, unrelated subtree of the dependency graph.

Diagnosing exactly where such a reference lives is the job of nix why-depends. The command traces a path, the shortest one by default or every path with the --all flag, through the references graph from one store path to another, and for each edge it names which file actually contains the embedded reference. A more elaborate case, nix why-depends --all nixpkgs#thunderbird nixpkgs#xorg.libX11, finds multiple references inside libxul.so, with further ones buried deeper inside libXdamage.so, each one embedding the libX11 store path. A --derivation flag shifts the same query to build-time dependencies, useful for understanding why some tool is required only during compilation and never afterward.

For engineers who prefer a visual pass over the graph rather than a command-line trace, the interactive TUI tool [nix-graph](https://github.com/AlexAntonik/nix-graph) offers a sortable, filterable terminal viewer, comparable to the older nix-tree but with additional features including sort, filter, and a reverse view for dependents.

The gap between a package's declared, direct dependencies and its full resolved closure is not small. In one cross-validated case, a small library's declared dependencies numbered 21, while its full closure reached 53. A mid-sized client library went from 44 declared dependencies to 190 in the resolved set. For haskell-language-server, used as a corpus target, 165 declared dependencies expanded to 459 once the closure was fully walked. These figures were checked directly against Nix's own evaluation output and matched exactly, 167 components, the same names, the same versions, with nothing missing and nothing extra.

This has a direct consequence for what belongs in an audit or a deployment artifact. The runtime closure is the right scope for both, because it can be validated against an external oracle the way the case above was validated against Nix's own evaluation. Test and benchmark closures can't be checked the same way, and including them in an artifact only inflates its size without adding any signal that can actually be verified. Including test dependencies in that kind of resolution would substantially inflate the artifact again, with the exact multiplier varying depending on the project.

Why reproducibility at closure scale matters beyond developer convenience

Bit-for-bit reproducibility across a full transitive closure is the precondition every downstream security and reliability claim depends on, not a convenience for developers who want a faster laptop setup. Without it, "same version" is an approximation between two systems that happen to look alike.

The NixOS project treats this as something to measure continuously rather than assert. The Lila tracker, hosted at reproducibility.nixos.social, monitors closure-level reproducibility across architectures including aarch64, producing a public, verifiable signal rather than a marketing claim.

CI time drops substantially under that guarantee, visible in build infrastructure. One production account reports that CI time dropped substantially early in adoption, and as the codebase grew larger, builds that would otherwise have crept past thirty minutes stayed under fifteen. The reason aggressive caching works this well under Nix is structural rather than incidental: because identical inputs are guaranteed to produce identical outputs, a cache hit is safe to trust rather than merely probable.

The absence of this guarantee has an organizational cost with its own name: environment drift, the state in which two machines nominally running the same stack have quietly diverged in ways nobody tracked. Tweag's work on dependency graphs in large codebases identifies stale build metadata, along with related issues like implicit transitive dependencies introduced through re-exports, as the kind of silent failure modes that accumulate in large projects over time.

None of this comes free. Team-hosted substituters, binary caches shared across an organization, are a prerequisite for making the reproducibility guarantee practical at scale rather than an optional speed boost layered on top. That trade-off is the reason teams building on Nix tend to need some control plane around their environments, not raw Nix alone.

NixOS's own deployment model is the clearest operational expression of the same guarantee. Running nixos-rebuild switch builds the entire new system closure, validates it, switches to it atomically, and leaves the previous generation available for instant rollback if anything about the new one fails. The guarantee that made the closure trustworthy in the first place, that every reference is accounted for and nothing is missing, is what makes an atomic, reversible system switch possible.

The closure graph as the foundation for supply chain visibility and SBOMs

A Nix closure is a complete, hash-verified record of every runtime component in a piece of software, from the application code itself down to libc. That makes it, by construction, one of the most accurate sources of truth available for software supply chain attestation, richer than most language-ecosystem software bills of materials, though turning it into a format regulators and auditors already recognize takes dedicated tooling.

Nix does not natively emit SPDX or CycloneDX documents. The derivation graph is the actual source of truth, and a separate translation step is required to turn that graph into the regulatory-ready formats auditors expect to see. The sbomnix toolchain, hosted at github.com/tiiuae/sbomnix, fills that gap: it accepts Nix flake references, derivations, and store paths directly, determines their dependencies, and exports the result in standard SBOM formats. Around it sit companion tools built for the same workflow: nixgraph for visualizing the dependency graph, vulnxscan for SBOM-driven vulnerability scanning, and provenance, a command-line tool that generates SLSA v1.0-compliant provenance attestation files in JSON for any Nix flake or derivation. Where Nixpkgs metadata is available, sbomnix uses it to enrich the components it discovers with more than just names and relationships.

The resulting SBOM carries more than a typical language-ecosystem tool produces, because Nix's closure includes the full native layer, glibc, openssl, and other system libraries, not only the Rust, Go, or Python dependencies that most language-level scanners are built to see.

A FOSDEM 2026 session titled "Describing Nix closures using SBOMs" made the case that Nix and Nixpkgs are gaining broader adoption at the same moment SBOMs are becoming a standard format for demonstrating provenance, and argued that bridging the two is imperative. The NixOS project's standing Software Provenance Team exists as the organizational answer to that same pressure.

Multiple jurisdictions are now writing SBOMs, attestations, and provenance tracking into law, and by one estimate 90% of organizations worldwide will fall under at least one regulatory requirement to demonstrate software assurance.

Production evidence for this bridge already exists outside the research literature. The semwright Rust project merged supply-chain certification work in September 2026 that pins nixpkgs to an exact revision, builds its release executables through a Nix derivation, and generates reproducible, per-binary CycloneDX documents as part of that pipeline. The closure that Nix has been scanning for and enforcing since a build first embeds one hash substring inside another file is the same graph now being exported, attested, and checked against the law.