unfs: A Content-Addressed Filesystem Data Format

Version 0 — Working Draft

#Abstract

This document specifies unfs, a data format for storing filesystem trees — files, directories, symlinks, devices, and their unix metadata (the recorded field set of §7). A filesystem tree is stored as an immutable, content-addressed graph of blocks in any key–value store. Moving such a graph between stores uses a byte-stream interchange format called "packs" — a deterministic profile of the IPLD CARv1 archive format (§12).

The format uses a single codec: a strict subset profile of IPLD DAG-CBOR. Because of this, every block is readable and link-traversable, and every pack is readable and transportable, by generic IPLD tooling. The format also uses a single configurable hash function per store, and stores all recorded unix metadata inline in directory entries. It is fully deterministic: the same logical content produced with the same parameters yields byte-identical blocks and identical references, regardless of how input was sliced, buffered, or ordered.

This specification is self-contained. An implementation can be written from this document and validated against the test vectors in Appendix A without reference to any existing implementation.

#1. Introduction

#1.1 Data model at a glance

A store contains exactly two kinds of things:

• Blocks — immutable byte strings addressed by their hash. Blocks form a directed acyclic graph (DAG).
• Named refs — mutable pointers binding a human-readable name to a block reference. Names are the only roots of the graph.

The concrete key–value layout underlying both — how blocks and refs map onto store keys — is formalized in §10.

Edge labels: n = dag-cbor (node) CID link, r = raw CID link.

Three properties fall out of this shape and drive the rest of the specification:

• Metadata lives in the parent's entry, not the child's block (§7). Changing a file's mode rewrites the directory that names it; the content blocks are untouched. Two files with identical bytes but different modes/owners share one content block.
• Every edit rewrites only the spine from the root to the changed entry (§8, §11). Every untouched subtree carries over by reference. Old roots remain valid and readable — snapshots are free.
• A block is stored and deduplicated by its multihash alone, while traversal identity is the full CID — content codec + multihash (§4). This single asymmetry must be respected by every deduplication set in a conforming implementation.

#1.2 Design goals

In priority order: unix fidelity, small size, performance, simplicity.

#1.3 Roles and trust model

This specification distinguishes writers (produce blocks, refs, and packs) and readers (consume them). Writers within one store are assumed cooperative: they are trusted to emit only conforming blocks. Writers need not be exclusive — the concurrency properties of each operation are given in §15.3; only garbage collection requires exclusive access (§15.2). Readers MUST treat all input — blocks fetched from a store, pack bytes, ref values — as potentially foreign or hostile, and MUST enforce every validation rule in this document (§13.2).

#1.4 Scope and non-goals

In scope: block encodings, the entry/node data model, chunking algorithms, the key–value storage mapping, the pack interchange format (a CARv1 profile, §12), and conformance requirements for readers and writers.

Out of scope: transport protocols, access control, encryption, multi-writer coordination, and any particular host-language API.

#1.5 How to read this document

The chapters that follow group into:

• Foundations (§2–§5) — terminology, primitives, refs, and the canonical CBOR profile.
• Data model (§6–§9) — nodes, entries, directories, and file content.
• Store and paths (§10–§11) — the key–value layout and path semantics.
• Interchange (§12) — the pack format for moving graphs between stores.
• Conformance rules and parameters (§13–§16) — conformance, parameters, and operational and security considerations.
• Draft extensions, not part of the specification (§17–§18) — the sync protocol and layered stores.
• Appendices — Appendix A (test vectors) and Appendix B (design rationale).

Validate an implementation against Appendix A continuously, as each chapter is implemented — not only once the whole document has been read.