Concepts & vocabulary
The shared terms the deep-dives in this survey use. Each is defined once here and grounded in at least one surveyed system; the deep-dives link back rather than redefining.
File system object (FSO)
The abstract value a content-addressing scheme serializes. Nix states the minimal version most directly — a file system object is exactly one of a regular file ("a possibly empty sequence of bytes for contents" plus "a single boolean representing the executable permission"), a directory ("mapping of names to child file system objects"), or a symbolic link ("an arbitrary string, known as the target") (store/file-system-object.md). Nix then says what is deliberately absent:
Nix does not encode any other file system notions such as hard links, permissions, timestamps, or other metadata.
Every system in this survey makes a version of that exclusion, and the differences between their exclusions are the first axis of the comparison. git keeps a four-value mode; OSTree keeps uid, gid, mode and extended attributes but still discards timestamps; REAPI is alone in carrying an mtime, and carries it as an optional node property rather than as part of the node.
Level 1 and level 2
Two nested trees, which this survey keeps strictly apart because a scheme can be conventional at one level and exotic at the other:
- Level 1 — the directory tree. How named children compose into a directory, and directories into a root. NAR, git trees, REAPI
Directoryand OSTree dirtrees all live here. - Level 2 — the intra-file tree. How the bytes of one file become a digest. For most of the field this is trivial ("hash the whole blob"), but it is a real tree for Bao/BLAKE3, for IPFS's unixfs chunker, and — the finding that surprised this survey — for REAPI's
SHA256TREE.
Venti settles the question of whether the levels nest: they do not. Its directories are "a special file" of concatenated 40-byte VtEntry structures, so its level-1 tree is an instance of its level-2 pointer tree with a different block-type base — the same machine run twice, not one layer inside another.
A scheme is a pair. Nix is NAR × whole-blob; git is git-tree × whole-blob; iroh is no level 1 at all (a bare blob) × Bao. The levels are independent, not a hierarchy.
Serial serialization vs Merkle DAG
Nix names the distinction precisely (file-system-object/content-address.md):
The simplest method is to serialise the entire file system object tree into a single binary string, and then hash that binary string, yielding the content address.
against
Another technique is that of a Merkle graph, where previously computed hashes are included in subsequent byte strings to be hashed. […] we can first hash (serialised) child file system objects, and then hash parent objects using the hashes of their children.
The consequence is the practical one this survey cares about. A serial scheme (NAR) has no subtree value: nothing below the root can be hashed independently, cached across runs, verified in isolation, or computed in parallel. A Merkle scheme (git, REAPI, OSTree, Bao) gives every subtree its own name, so a changed file rewrites one blob plus its ancestor chain, and disjoint subtrees hash concurrently.
Canonical form
The rule set that makes "two equivalent trees hash to the same value" true. Every Merkle scheme in this survey states one; the requirements are strikingly similar and the orderings are not. REAPI calls the concept out by name (remote_execution.proto):
A
Directorythat obeys the restrictions is said to be in canonical form.
Nix's reason for having a bespoke archive format at all is the absence of such a form in the obvious alternatives — TAR and ZIP "do not have a canonical serialisation, meaning that given an FSO, there can be many different serialisations", and "this would be bad because we use serialisation to compute cryptographic hashes" (content-address.md).
Entry ordering
The part of canonical form that differs most, and the one that cannot be abstracted behind a single comparison function. Four distinct answers appear in five systems — see the ordering axis for the table and the worked a versus a.b case that separates the first two.
Digest, and whether size is part of it
A content address is "an opaque fixed-size digest" (Nix), but the schemes disagree about what accompanies it. REAPI's Digest is a hash and a size_bytes, and both travel everywhere a digest travels; iroh's Hash is 32 raw bytes with the size carried separately in the wire protocol and verified progressively; git and OSTree carry the hash alone. Encoding differs again: hex for git and REAPI, Nix's own base-32 for store paths, and multibase-tagged bytes in the IPFS family.
Partial verification
Whether a consumer holding a root digest can validate a fragment without possessing the whole tree. Level-1 Merkle schemes give this at directory granularity for free. Level-2 chunk trees extend it inside a file, which is what iroh is built on — a lying provider is "caught within one 16 KiB chunk group". A serial scheme gives none of it: NAR must be hashed end to end.
Identity versus provenance
Where the context of a digest lives. A Merkle DAG deduplicates, which means it deliberately erases the path and origin by which a subtree was reached — two identical directories anywhere in the world are one object. Software Heritage hit this head-on: a citation needs to say which repository and which path a file came from, and none of that is recoverable from the identifier. Its answer is SWHID qualifiers (origin, visit, anchor, path, lines), which sit outside the hash and are unverifiable by construction.
The rule generalizes: record context beside the digest, never inside it. Putting provenance in the hash would destroy the dedup that made the digest worth having.
Parameterized digests
Most digests in this survey are a hash of a defined serialization, so two implementations agree by construction. A growing minority are hashes of a descriptor that includes the parameters used, so the same bytes legitimately produce different digests under different settings:
| Subject | Parameter that changes the digest |
|---|---|
| fs-verity | hash algorithm, block_size, salt — all covered by the descriptor |
| dm-verity | on-disk version (salt prepended vs appended), block size |
| IPFS unixfs | chunker, chunk size, DAG layout, raw-leaves |
| eStargz | the prefetch order chosen by a profiling run |
A parameterized digest is not comparable with a plain content hash, and often not comparable with itself across settings. Treat "what parameters does this digest cover" as a question to answer explicitly, not a detail.
Who builds the tree
For a level-2 Merkle tree, when it is constructed decides who pays and who can verify. The field runs in one direction:
| Built by | Example | Consequence |
|---|---|---|
| An offline tool, before distribution | veritysetup format (dm-verity) | The verifier receives a root only |
| The kernel, on demand | FS_IOC_ENABLE_VERITY (fs-verity) | One full pass at enable time; O(1) digest afterwards |
| The packager, shipped with the artifact | APK v4 .apk.idsig (APK v4); iroh's outboard (Bao) | The verifier can check a range without ever hashing the artifact |
Only the last removes the computation from the verifier, which is why a seam should let a tree arrive out of band rather than assuming each consumer recomputes one.
Index versus tree
Two ways to make part of a blob verifiable, and they are not equivalent. A tree (Bao, SHA256TREE) lets a 16 KiB range be checked against a 32-byte root with nothing else transmitted, because the geometry follows from the length. An index (eStargz and SOCI) is a flat list of per-chunk digests in a document that must be fetched whole before any byte can be checked — and whose own integrity hangs off an annotation or a side artifact. The index gives depth-2 trust; the tree gives O(log n).
Terms this survey does not use
- Chunking strategy (fixed-size, or content-defined via a rolling hash such as FastCDC) is a policy for choosing level-2 boundaries, not an addressing scheme. It is named where a subject uses one, never treated as a peer.
- Merkleization of typed data (Ethereum SSZ's
hash_tree_rootand relatives) addresses consensus objects, not file system objects, and is out of scope — it shares only the word "Merkle".