Content Addressing of File System Objects
A primary-source survey of how twenty-one systems turn a tree of files into a digest — from Plan 9's Venti in 2002 through Nix, git, OSTree and Bazel's REAPI to the intra-file Merkle trees of Bao and fs-verity — and of the two places the field's own experience says it goes wrong: tar's absent canonical form and cache keys mistaken for content addresses.
The evidence base for the content-addressing layer of sparkles:build-primitives, and the falsification gate for the scheme seam that layer is designed around.
This survey answers nine questions:
- Serial serialization or Merkle DAG? Overwhelmingly Merkle, and everything a build system wants — subtree caching,
O(depth)rehash, independent verification, parallel hashing — lives on that side of the line. See axis 3. - Is there one canonical entry order? No. Four canonical answers, two deliberately non-canonical ones, and one subject that never orders at all. Two of the four disagree on inputs as ordinary as a directory
abeside a filea.b. See axis 2 and the worked case. - What belongs inside an identity? Timestamps: almost unanimously not. Everything above that floor: no agreement whatsoever. See axis 1.
- Are intra-file chunk trees a peer-to-peer curiosity? No — REAPI put one in a build protocol in 2023, and Venti had one in 2002. See axis 4.
- Can canonical form be retrofitted onto a format that lacks it? Only partly, and the people who tried have a list of what provably cannot be fixed. OCI is the ecosystem-scale demonstration.
- What does a level-2 tree buy over an index of chunk digests?
O(log n)verification against a 32-byte root versus depth-2 trust requiring the whole index first. See index versus tree. - How does the field handle case and duplicate collisions? Five ways, only one of which detects at ingest without corrupting the identity. See the disagreements.
- Is a cache key a content address? No, and ccache's
sloppinesslist is a published taxonomy of exactly how they differ. - What should
sparkles:build-primitivesadopt? See the recommendations — including the two places this survey contradicted an earlier decision.
Last reviewed: September 21, 2026
NOTE
Scope. This tree is about turning a tree of files into a digest. It is not about selecting the files — that is Fileset & File-Selection Query Languages — nor about the store, signature and cache layers above the digest, which sparkles:nix reaches through libnixstore-c rather than reimplementing.
Deliberately excluded, and named so they are not re-derived: typed-data Merkleization (Ethereum SSZ) addresses consensus objects rather than file system objects. Content-defined chunking is not excluded but is treated as what it is — a level-2 boundary policy, surveyed where a subject uses one (casync, bup, unixfs, Snix). Deferred, noted not omitted: Perkeep, restic/borg, Go's checksum database (a Merkle log, a different shape), and git packfile delta encoding (storage beneath identity).
Master catalog
| Subject | Ecosystem | Level 1 (directory tree) | Level 2 (file bytes) | Entry ordering | Digest | Link |
|---|---|---|---|---|---|---|
| Venti | Plan 9 | pointer-block tree; directories are files | same pointer tree | n/a — no names | SHA-1 "score" | venti |
| Nix Archive (NAR) | Nix | serial serialization | whole blob, inline | byte-wise, one sequence | SHA-256 over the stream | nar |
| Git objects | Git | Merkle DAG | whole blob | byte-wise + implicit / | SHA-1 / SHA-256 | git |
Git cache-tree | Git | — (incremental maintenance of the above) | — | — | — | cachetree |
Nix git-hashing | Nix (experimental) | git trees over Nix's FSO model | git blobs | git's | SHA-1 / SHA-256 | nixgit |
Snix castore | Snix (Nix reimplementation) | Merkle DAG, protobuf Directory | plain BLAKE3; FastCDC below identity | byte-wise, three arrays | BLAKE3 | castore |
| Mercurial → Sapling | Mercurial, Sapling | flat whole-tree listing, then per-directory trees | per-file revlog | sorted rows | SHA-1 over parents + content | hg |
| Bazel REAPI | Bazel, Buck2, Pants | Merkle DAG of protobuf Directory | whole blob or SHA256TREE | byte-wise, three arrays | {hash, size_bytes}, 7 functions | reapi |
| OSTree | Linux OS images | Merkle DAG (dirtree + dirmeta) | whole blob + header | byte-wise, two arrays | SHA-256 | ostree |
| Software Heritage | Source-code archive | Merkle DAG above the tree (dir→rev→rel→snp) | sha1_git | git's, reimplemented | SHA-1, fixed by the grammar | swh |
| bup / git-annex | Backup | git trees, with fanout | content-defined chunks as git blobs | git's | SHA-1 | bup |
| casync / desync | systemd ecosystem | catar, a canonical serial format | CDC across file boundaries | canonical | SHA-512/256 per chunk | casync |
| IPFS unixfs / CID | IPFS, Filecoin | DAG-PB; huge directories HAMT-sharded | pluggable chunker | n/a (links, not sorted names) | self-describing CID | ipfs |
| Bao / BLAKE3 | iroh | none | Merkle chunk tree | n/a | BLAKE3, 32 raw bytes | bao |
| Tahoe-LAFS | Distributed storage | mutable dirnodes; no ordering at all | three-tier tree over erasure-coded ciphertext | none | capability, not a hash | tahoe |
| OCI image layers | Containers | an ordered chain of tar layers | whole tar archive | unspecified | sha256: ×3 identities | oci |
| eStargz / SOCI | Containers | tar, made seekable | per-chunk digests in an index | workload-derived | TOC digest / zTOC | estargz |
| composefs + fs-verity | Linux, OSTree | EROFS image over a shared store | kernel-built, kernel-enforced Merkle tree | image layout | parameterized descriptor digest | cfs |
| dm-verity / APK v4 | Linux, Android | none — numbered blocks | Merkle tree; shipped in .apk.idsig | n/a | parameterized, signed root | apk |
| Reproducible archives | Debian, wider ecosystem | — (a retrofit onto tar/zip/ar/cpio) | — | only two formats can be ordered at all | — | repro |
| ccache / sccache / LLVM CAS | Build caches | — (inputs, not trees) | — | — | BLAKE3 key, salted | caches |
Shared vocabulary — file system object, the level-1/level-2 split, canonical form, parameterized digests, identity versus provenance, index versus tree — is defined once in concepts.
By level-1 composition
| Composition | Systems | Consequence | | ----------------------- | ---------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------- | ---------- | ------------------------------------------------------- | | Serial serialization | NAR, casync | No subtree values; sharing must be recovered below the tree, at chunk level, or not at all | | Flat whole-tree listing | Mercurial | O( | repo files | ) to parse — the failure that forced the move to trees | | Merkle DAG | git, Nix git-hashing, Snix, REAPI, OSTree, SWH, bup, unixfs | Subtree identity, O(depth) rehash, object-granular verification | | Chain, not tree | OCI | O(n) invalidation in the layer count; order-dependent semantics | | None — level 2 only | Bao, dm-verity | Proof the two levels are independent | | Level 2 is level 1 | Venti | The sharpest proof of the same point: one machine run twice |
By entry ordering
| Answer | Systems | Mechanism |
|---|---|---|
| One sequence, raw bytes | NAR | std::string <; the parser rejects name <= prevName |
One sequence, / appended to directories | git, Nix git-hashing, SWH, bup | base_name_compare substitutes / for a directory name's terminating NUL — four independent implementations |
| Two arrays, raw bytes | OSTree | files and directories sorted separately by strcmp |
| Three arrays, raw bytes | REAPI, Snix | files, directories and symlinks each sorted by UTF-8 bytes |
| A privileged prefix | JAR, via strip-nondeterminism | a comparator forcing META-INF/ first |
| Workload-derived | eStargz | a prefetch plan from a profiling run; .prefetch.landmark marks the boundary |
| Versioned in the data | Venti's vac | a known-wrong comparator retired by minting a new block magic |
| None | Tahoe, unixfs | children are never sorted |
| Unspecified | OCI | whatever the producer's tar emitted |
By metadata floor
| Floor | Systems |
|---|---|
| None — bytes or blocks only | Bao, Venti, dm-verity |
| One executable bit | NAR, Nix git-hashing, Snix |
| Path + revision id + one flag | Mercurial |
| Five modes, incl. symlink and submodule | git, SWH |
Executable bit + open key/value properties (incl. optional mtime) | REAPI |
| uid, gid, mode, xattrs — inside the content hash | OSTree |
| Negotiable by feature flag | casync |
| Full POSIX, including timestamps | OCI, composefs |
By partial verification
| Granularity | Systems |
|---|---|
| None — all or nothing | NAR, Mercurial (flat), OCI |
| Per object / per directory | git, Nix git-hashing, OSTree, REAPI, SWH, bup |
| Per chunk, via an index (depth-2 trust) | eStargz / SOCI, casync |
Per chunk, via a tree (O(log n)) | Bao, REAPI SHA256TREE, fs-verity, dm-verity / APK v4, Tahoe |
| Reserved but unimplemented | Snix — StatBlobResponse.bao is // still todo |
Milestones
| Year | Event | | ---------- | --------------------------------------------------------------------------------------------------------------- | ---------- | ------ | ------------- | ----------- | | 1980 | Merkle publishes hash trees (IEEE S&P) — cited by Venti as its ancestor | | 1998 | Stanford Archival Vault: a write-once object log, with "no way to share data between objects" | | 2000 | SFSRO (OSDI): SHA-1 blocks "applied recursively" | | 2001-10 | LBFS (SOSP): content-defined chunking | | 2002-01 | Venti (FAST '02): a block-level content-addressed store; directories are files of VtEntry scores | | 2003 | NAR appears in the Nix tree — archive.cc's history begins 2003-11-18 | | 2005-04 | Git's object model ships (first commit 2005-04-07) | | 2011-10 | OSTree begins — git's model plus uid/gid/mode/xattrs, minus timestamps | | 2018–2019 | REAPI v2 stabilizes the Directory/Digest canonical form | | 2019-10 | Sapling's retrospective states the O( | repo files | )→O( | changed files | ) argument | | 2020 | BLAKE3 published — a tree hash by construction, making verified streaming practical | | 2021-04 | SWHID v1.6 — SHA-1 welded into the identifier grammar | | 2022-05 | Nix's git-hashing implementation lands — approximate | | 2023-03-14 | REAPI adds SHA256TREE, "a version of SHA-256 that supports chunking" (PR #235) | | 2024–2025 | iroh settles on 16 KiB chunk groups; Snix ships BLAKE3 identity with NAR at the boundary |
NOTE
Dates come from the repositories' own histories where a local clone or forge API was available, and from cited papers otherwise. Git-history dates record when an implementation appeared, which may postdate a design; entries marked approximate are exactly that.
Suggested reading paths
"I want the findings, not the survey." → Synthesis & recommendations — in particular axis 2 (no single canonical order), axis 4 (chunk trees are not exotic), and the two contradictions this survey produced against earlier decisions.
"I'm implementing the content-addressing layer." → concepts → NAR → git objects → Nix git-hashing → Snix castore (a production system that made the same architectural choice, and one different one) → recommendations.
"I'm designing the scheme seam." → the falsification gate, then REAPI and Bao, which stress opposite ends of it.
"I care about incremental rebuilds." → git cache-tree (the mechanism, and racy-git) → build input caches (the same shape with the opposite failure mode).
"I care about metadata fidelity." → OSTree → composefs + fs-verity → axis 1.
"I want to know why tar keeps failing." → OCI layers → reproducible archives → NAR's rationale.
Sources
Every GitHub citation pins a 40-character commit SHA; non-GitHub forges are pinned by commit where the forge supports it. Verified against local clones or forge APIs:
- Nix —
NixOS/nixat1d8bdc1ee63246b591a8d77d0d481485cd09d438 - Git —
git/gitatf78ce2f7b6df702f93d40b85d6bda92a3f65da79 - Linux —
torvalds/linuxate43ffb69e0438cddd72aaa30898b4dc446f664f8 - OSTree —
ostreedev/ostreeat1d5a312a3189b0fbd70fe6769aadb19a366fedb2 - Bazel REAPI —
bazelbuild/remote-apisat76ddd98e1f92c0e2e71d0d3aa6906eca31754c03 - iroh blobs —
n0-computer/iroh-blobsate82cbdcbdac9a78033174aad55e3199b2cf4c0dc - Sapling —
facebook/saplingat87b7db94b0a7fc5186b472f0ee8d01fd5a2036a2 - OCI image-spec —
opencontainers/image-specataf26a05fba5ee648512f4ea3c9fda1fcc1b6d6dc - casync —
systemd/casyncatb4b7e5606f785572b78a43626a27a45fe3df2fbd - Snix —
snix/snixat86a6e6ef8c1c43d015b09f10051de78b2cae548b(Forgejo,git.snix.dev) strip-nondeterminism— salsa.debian.org at904281367bd7fbc34a0831a28dd40457b6753c1c
Related in-repo trees: Fileset & File-Selection Query Languages (which files to name), iroh (the peer-to-peer side of Bao), and Monorepo Tooling (what consumes a build-input digest).