Preface

Dacite: distributed immutable data with content-addressed nodes.

Chapters (Four Layers)

1. Content Stores — immutable content-addressed map, backends, caching.
2. Hash Fusion — fuse primitive and content identity.
3. Values — scalar/seq/map + types.
4. Rooted Stores — mutable root ref, watches, durability, push/sync, GC.

Stop after 1 (persistence), 2 (hashing), 3 (structs), 4 (mutable state + sync).

Reading

Sequential; SPEC.md for precision.

For

Users, implementors, designers.

Jonathan & Gorm, 2026

Chapter 1: Content Stores

This chapter introduces the content store — the persistence layer at the bottom of Dacite. A content store is a single, simple thing:

An immutable, content-addressed dictionary: hash → value.

Each entry maps a 256-bit content hash to a stored value. The store knows nothing about the structure or meaning of what it holds — it maps hashes to opaque payloads and nothing more. It has no notion of a “current” value, no mutable state, and no root; it only ever grows as new entries are added.

That deliberate simplicity is what the rest of Dacite builds on. Chapter 2 explains how hashes are computed. Chapter 3 defines the value model — trees of nodes that live as entries in a content store. Chapter 4 adds a single mutable root on top of a content store, turning this immutable dictionary into something that can evolve and synchronize over time. Here we stay at the immutable persistence layer: the IStore protocol, its implementations, and content addressing.

1.1 Store Entries

Every entry in a content store has the same shape:

hash → value

• hash: A 256-bit content hash (4 × 64-bit integers). How it is derived from the content is Chapter 2’s subject.
• value: An opaque serialized payload. The store neither knows nor interprets its structure.

The store is a pure key/value mapping. All interpretation of a stored entry happens in higher layers (Chapter 3). Because the key is a hash of the value, entries are immutable: a given hash always maps to the same content, so writing the same content twice is idempotent and two callers that produce the same content share one entry.

Representation note. Conceptually an entry’s value is opaque bytes. The reference implementation currently stores serialized Dacite node values (EDN), and the LMDB backend keeps the bytes of that serialization. A true opaque byte-array representation is a later refinement tied to the serialization format (see the serialization appendix); it does not change the content-store contract described here.

1.2 The Store Protocol

Every content store implements IStore:

(defprotocol IStore
  (s-get [store hash]  "Return the stored value, or nil")
  (s-put [store hash value] "Store value at hash, return the store")
  (s-has? [store hash] "Check if hash exists")
  (s-snapshot [store] "Return a map of all {hash → value}")
  (s-merge [store m] "Merge {hash → value} into the store")
  (s-reset [store] "Clear all entries"))

Typical usage at this layer:

;; Store a value at its hash
(s-put store h node)

;; Fetch it back
(s-get store h)   ;; => node, or nil if absent
(s-has? store h)  ;; => true

Application code rarely calls s-get / s-put directly. Instead it uses the value constructors of Chapter 3, which persist nodes into a store on your behalf. The public value API always takes a store (implicitly via a current-store binding, or explicitly as the first argument) so that persistence stays visible rather than hidden.

1.3 Content Addressing

Because a store is addressed by content hash, it has two useful properties for free:

• Deduplication. Identical content produces an identical hash, which maps to a single entry. Storing the same node from two places costs one entry, not two.
• Idempotent writes. s-put of content that is already present is a no-op in effect — the hash and value are unchanged.

(s-put store h node)
(s-put store h node)   ;; same hash, same value — still one entry

This is the foundation that lets higher layers share structure aggressively: an edited collection reuses every unchanged node, because unchanged nodes hash the same and therefore are the same entry.

1.4 Implementations

All content stores implement IStore, so they are interchangeable. Each has its own constructor function — there is no single unified wrapper; you pick a backend by calling its constructor.

Memory Store

An atom-backed store. Fast, ephemeral, ideal for testing and for building values before they are persisted elsewhere.

(def s (store/mem-store))

File Store

Filesystem persistence, one file per entry, with two levels of directory sharding by hash prefix to keep directories small. Survives restarts.

(def s (store/file-store "path/to/dir"))

LMDB Store

Persistent store backed by LMDB. Content entries live in the primary database. (A small meta database is also created; rooted stores in Chapter 4 use it to persist a root hash — the content store itself never touches it.)

(def s (store/lmdb-store "path/to/db"))

Layered Store

Composes several stores into a stack, fastest first (e.g. memory in front of LMDB). It provides transparent caching without changing the IStore API.

(def s (store/layered-store (store/mem-store)
                            (store/lmdb-store "path/to/db")))

• Read (s-get): walk layers front to back until a layer has the entry. On a hit in a slower layer, the entry is read through — backfilled into the faster layers it was missing from — so repeat reads are fast.
• Write (s-put, s-merge): write to all layers. This keeps the durable back layer authoritative and the fast front layer warm.

A single write policy (write-to-all) is intentional at this layer; richer per-layer policies are out of scope for the content store.

1.5 What This Layer Provides

1. An immutable, content-addressed dictionary: hash → value.
2. A minimal protocol — s-get / s-put / s-has? / s-snapshot / s-merge / s-reset.
3. Content addressing, and with it free deduplication and idempotent writes.
4. Composable backends: memory, file, LMDB, and layered caching — all interchangeable.

There is deliberately no mutable state here: no current value, no root. That single moving part is added in Chapter 4.

Chapter 2 defines how the hashes that key this dictionary are formed. Chapter 3 builds the value model whose nodes live as entries in a content store. Chapter 4 wraps a content store with a mutable root to make it evolve and synchronize.

Chapter 2: Hash Fusion

Chapter 1 introduced content stores — an immutable map from content hashes to serialized values. Every node in that map is keyed by its hash. This chapter defines how those hashes are formed.

Everything in Dacite’s composite structures is built on a single operation: fuse. It combines two 256-bit hashes into a new 256-bit hash using nothing more than integer arithmetic. No SHA-256 at runtime, no hash function calls in the critical path — just six additions and a multiplication.

The idea originates from an HP Labs white paper on using upper triangular matrix multiplication to combine hashes associatively:

Haber, S. et al. (2017). Efficient and Secure Hash-Based Timestamps. HPE-2017-08. https://www.labs.hpe.com/techreports/2017/HPE-2017-08.pdf

The paper proposes representing hashes as upper triangular matrices and multiplying them. Matrix multiplication is associative but not commutative — exactly the properties needed for tree-shape-independent hashing. Dacite’s contribution is the specific 4×4 matrix over 64-bit cells, chosen based on empirical testing of degeneration behavior (see §2.8).

This chapter introduces fuse, its algebraic properties, and how it turns raw bytes into content addresses. Chapter 3 applies these ideas to the value model: scalars, plus the vectors, strings, blobs, maps, and sets built on them.

2.1 Hashes as Four Words

A Dacite hash is 256 bits, represented as four 64-bit unsigned integers in big-endian word order:

hash = [c0, c1, c2, c3]

Word c0 holds the most mixed bits (from fuse) and is used first for HAMT navigation. Word c3 holds the least mixed bits.

2.2 The Fuse Operation

Fuse takes two hashes and produces a third:

Input:  a = [a0, a1, a2, a3]
        b = [b0, b1, b2, b3]

Output: c = [c0, c1, c2, c3]

c0 = a0 + a3*b2 + b0    ← most bit mixing (single multiply)
c1 = a1 + b1
c2 = a2 + b2
c3 = a3 + b3             ← least bit mixing (simple addition)

All arithmetic wraps at 2^64. The total cost: 6 additions, 1 multiplication.

Properties

These properties are not incidental — the entire system depends on them:

• Associative — fuse(a, fuse(b, c)) = fuse(fuse(a, b), c). This means tree shape doesn’t affect the hash. A balanced tree and a left-degenerate tree over the same leaf sequence produce the same root hash.
• Non-commutative — fuse(a, b) ≠ fuse(b, a) (for a ≠ b). Order matters. [x, y] and [y, x] have different hashes.
• Identity — [0, 0, 0, 0] is a two-sided identity. fuse(a, 0) = fuse(0, a) = a. Empty sequences hash to the identity.
• Fast — no hash function calls, just integer arithmetic. This matters when every node in a tree computes a fuse on construction.

Why Associativity Matters

Associativity is the foundation of structural sharing. Consider a sequence [a, b, c, d]. Its hash is:

fuse(fuse(fuse(a, b), c), d)

But because fuse is associative, any parenthesization gives the same result:

fuse(fuse(a, b), fuse(c, d))    — balanced tree
fuse(a, fuse(b, fuse(c, d)))    — right-degenerate tree

This means two stores can organize the same data differently (different tree shapes for performance) and still agree on the root hash.

graph TD
    subgraph "Left-degenerate tree"
        L1["fuse"] --> L2["fuse"]
        L1 --> Ld["d"]
        L2 --> L3["fuse"]
        L2 --> Lc["c"]
        L3 --> La["a"]
        L3 --> Lb["b"]
    end

    subgraph "Balanced tree"
        B1["fuse"] --> B2["fuse"]
        B1 --> B3["fuse"]
        B2 --> Ba["a"]
        B2 --> Bb["b"]
        B3 --> Bc["c"]
        B3 --> Bd["d"]
    end

    R["Same root hash"] -.-> L1
    R -.-> B1

    style R fill:#4a9,stroke:#333,color:#fff

Different tree shapes, same root hash. This is what makes finger trees possible — internal rebalancing never changes the identity of the sequence.

Why Non-Commutativity Matters

If fuse were commutative, [a, b] and [b, a] would hash the same. Sequences would be indistinguishable from sets. Order-sensitive data structures (vectors, strings) require that fuse(a, b) ≠ fuse(b, a).

graph LR
    subgraph "fuse(a, b)"
        AB["fuse"] --> A1["a"]
        AB --> B1["b"]
    end

    subgraph "fuse(b, a)"
        BA["fuse"] --> B2["b"]
        BA --> A2["a"]
    end

    AB -. "≠" .-> BA

    style AB fill:#4a9,stroke:#333,color:#fff
    style BA fill:#a44,stroke:#333,color:#fff

Order matters: [a, b] and [b, a] produce different hashes.

2.3 Group Structure

Fuse forms a group over (ℤ/2^64)^4. Every hash has a unique inverse:

inv([a0, a1, a2, a3]) = [a3*a2 - a0, -a1, -a2, -a3]

Such that fuse(inv(a), a) = fuse(a, inv(a)) = [0, 0, 0, 0].

Cost: 1 multiply + 4 negations.

Unfuse

Given fused = fuse(a, b), if you know b, you can recover a:

unfuse(fused, b) = fuse(fused, inv(b)) = a

Strip from the left: fuse(inv(a), fused) = b.

What the Group Enables

• Cross-type equality — strip a type hash to compare the underlying content (see Chapter 3, Cross-Type Equality).
• Hash recovery — recover one component of a fused pair when the other is known.
• Incremental re-hashing — update a fused chain without recomputing from scratch. Replace an element by unfusing the old and fusing the new.

2.4 The Byte Hash Table

Dacite doesn’t hash bytes directly with fuse. Instead, it uses a precomputed lookup table mapping each byte value (0–255) to a 256-bit hash:

byte_hash: byte → Hash    (256 entries)

The default table is seeded using SHA-256: byte_hash[i] = sha256(byte_array([i])). But any set of 256 distinct, high-quality 32-byte values works. This decouples Dacite from any specific hash function at runtime — SHA-256 is used once at build time to generate the table, never again.

Hashing Bytes and Strings

All data hashing reduces to table lookups and fuses:

fuse_bytes(bs) = reduce(unchecked_fuse, [0,0,0,0], map(byte_hash, bs))
fuse_str(s)    = fuse_bytes(utf8_bytes(s))

Because fuse is associative: fuse(fuse_str(a), fuse_str(b)) = fuse_str(a ++ b)

Composing fused results is equivalent to fusing the concatenation. This is both a feature (tree nodes can combine child hashes) and a constraint (a domain separator is needed between a value’s type and its data — see Chapter 3).

2.5 Protocol ID

The byte hash table is a build-time constant, not stored inside the content-addressed space. The table’s own hash serves as a protocol identifier:

protocol_id = fuse_bytes(concat(table[0], table[1], ..., table[255]))

The table hashes itself: each row is 32 bytes, concatenated into 8,192 bytes, and fuse_bytes (which uses the table) produces the ID.

Two stores are compatible if and only if they share the same protocol ID. Implementations check this on first contact.

2.6 Low-Entropy Rejection

Fuse must reject inputs and outputs where the lower 32 bits are zero in all four words:

low_entropy?(h) =
  (h[0] & 0xFFFFFFFF) == 0 AND
  (h[1] & 0xFFFFFFFF) == 0 AND
  (h[2] & 0xFFFFFFFF) == 0 AND
  (h[3] & 0xFFFFFFFF) == 0

The checked fuse:

fuse(a, b):
  REJECT if low_entropy?(a)
  REJECT if low_entropy?(b)
  result = unchecked_fuse(a, b)
  REJECT if low_entropy?(result)
  return result

An unchecked variant exists for internal use where inputs are known valid.

2.7 Why 4×4 with 64-bit Cells

The HP paper describes hash fusing using upper triangular matrices in general terms. The same 256-bit hash can be packed into matrices of different sizes depending on cell width:

The HP paper’s specific implementation used 8-bit cells in a 9×9 matrix. Larger cells mean fewer cells in the matrix, but each cell participates in more bit-mixing per multiply. This tradeoff matters for degeneration resistance — and as the experiments below show, the 8-bit choice degenerates surprisingly quickly.

The Folding Experiment

Empirical testing (published at Clojure Civitas) revealed a critical difference between cell sizes. The test: take a hash h, fuse it with itself (“fold”), then fold the result with itself, and repeat. Each fold squares the hash: fold 1 = h², fold 2 = h⁴, fold n = h^(2^n). This measures resistance to the worst case — long runs of identical values.

The exact fold count varies with the starting hash, but the relationship is statistical: folds to zero tracks the cell size in bits. Smaller samples showed values within a few folds of the cell size; a larger sample would pin down the distribution more precisely.

With 8-bit cells — the HP paper’s implementation choice — repeating the same hash roughly 256 times causes complete degeneration. With 64-bit cells, you’d need approximately 2^64 repetitions — far beyond any realistic data.

graph LR
    H["h"] -->|"fold 1"| H2["h² = fuse(h,h)"]
    H2 -->|"fold 2"| H4["h⁴ = fuse(h²,h²)"]
    H4 -->|"fold 3"| H8["h⁸ = fuse(h⁴,h⁴)"]
    H8 -->|"..."| HN["h^(2^n)"]
    HN -->|"fold n"| Z["zero (degenerated)"]
    style Z fill:#a44,stroke:#333,color:#fff

A separate experiment with random fuses (alternating between two random hashes) showed zero collisions across millions of fuses for all cell sizes. Degeneration is specific to low-entropy data — repeated fusing of the same value.

The Decision

The 4×4 matrix with 64-bit cells won on all axes:

• Degeneration resistance — ~2^64 repeated fuses vs ~2^8 for the HP paper’s 8-bit cells
• Performance — smallest matrix means fewest operations per fuse (6 additions + 1 multiplication vs. dozens for 9×9)
• Simplicity — 4 words map naturally to 256 bits; no packing tricks
• Hardware fit — 64-bit integers are native on modern CPUs

The low-entropy rejection check (§2.6) checks the lower 32 bits of each word. This means fuse rejects degenerate hashes after approximately 2^32 repeated fuses of the same value — well within the 64-bit cell’s ~2^64 capacity, providing a conservative safety margin that catches degeneration long before it reaches the theoretical limit.

2.8 API Surface

Primitives

The irreducible core — everything else derives from these:

Derived

Convenience functions that compose from the primitives:

Properties

• fuse(a, fuse(b, c)) = fuse(fuse(a, b), c) — associativity
• fuse(a, b) ≠ fuse(b, a) for a ≠ b — non-commutativity
• fuse(a, [0,0,0,0]) = a — right identity
• fuse([0,0,0,0], a) = a — left identity
• fuse(a, inv(a)) = [0,0,0,0] — right inverse
• fuse(inv(a), a) = [0,0,0,0] — left inverse
• fuse(a, inv(b)) = unfuse(a, b) — unfuse is derived
• fuse(inv(a), fuse(a, b)) = b — left recovery
• fuse-bytes(a ++ b) = fuse(fuse-bytes(a), fuse-bytes(b)) — composability
• fuse rejects when low-entropy? is true for input or output

This layer has zero dependencies — no I/O, no state, just integer arithmetic and a lookup table. It is the natural starting point for porting Dacite to a new language.

2.9 What This Layer Provides

Hash fusion gives the rest of Dacite three guarantees:

1. Content identity — any value, at any scale, reduces to a 256-bit hash. Same content → same hash, always.
2. Tree-shape independence — associativity means the hash captures what is stored, not how it’s organized.
3. Decomposability — the group structure means hashes can be taken apart, not just composed. This enables typed values, incremental updates, and cross-type comparisons.

The next chapter builds the value model — scalars, plus the vectors, strings, blobs, maps, and sets built on them — on this foundation.

Chapter 3: Values

Chapter 1 gave us the content store — an immutable content-addressed map from hashes to values. Chapter 2 gave us fuse and three guarantees: content identity, tree-shape independence, and decomposability. This chapter builds the value model on both foundations: a closed set of six user value kinds — scalars, vectors, strings, blobs, maps, and sets — together with the internal primitives that implement them.

3.1 Values Know Their Store, Hash, Type, and Content

Every Dacite value carries four pieces of data:

• store — the store that created and persists it
• hash — its content-addressed identity (via dacite-hash)
• type — a string identifying its kind (e.g. "i64", "vector")
• content — the value itself, exposed in the host language via an explicit call (realize in the reference implementation). A scalar yields its native value; a collection yields a lazy iterable of realized elements (a map yields realized [key value] pairs), so sub-collections become nested lazy iterables. Laziness keeps access compatible with partial availability — only the part you consume is fetched.

(def v (dacite/vector 1 2 3))

(dacite-hash v)
;; => [c0 c1 c2 c3]  ; the 4-long hash

(dacite-store v)
;; => #<DaciteStore ...>  ; the store that owns this value

(dacite-type v)
;; => "vector"  ; the value's type name

Most work happens in the context of a current store — a dynamic binding (*store* in the reference implementation) that defaults to an in-memory store for REPL use. Constructors such as (dacite/vector 1 2 3) persist into that store; the resulting value remembers which store created it. When you need a specific store — tests, migration, multiple stores — use the explicit -with-store variants:

(dacite/vector-with-store store 1 2 3)

Use with-store to bind an isolated store for a block of code (see §3.9).

The store reference enables transparent persistence: when you assoc a Dacite map or conj a Dacite vector, the new value is automatically stored in the same backing storage. You don’t thread the store through every operation — values know where they belong.

This also means values are tied to their store. A value created in store A cannot be directly inserted into store B; you must first migrate the underlying content (or use ref push — see Chapter 4).

3.2 A Closed Set of User Values

Dacite exposes a closed set of six user value kinds:

• scalar — an atomic, typed value: a number, character, boolean, or null
• vector — an ordered collection of values
• string — text: an ordered collection of characters
• blob — binary data: an ordered collection of bytes
• map — an associative collection of key/value pairs
• set — an unordered collection of distinct values

Scalars are atomic. The other five are collections, and they are not primitive all the way down — they are assembled from internal value primitives:

• Finger-tree nodes implement the sequence types: vector, string, and blob (§3.6).
• HAMT nodes implement the associative types: map and set (§3.7).

Internal nodes are real content-addressed values with their own type names and hashes, but they are never handed to users directly. They exist only to give the user types their shape and performance.

The set of user types is fixed, but it is not special-cased in the storage layer: a type is just a string of characters (§3.3). The vocabulary could grow in the future without changing any of the machinery below.

3.3 How Every Value Is Hashed

Every Dacite value — user-facing or internal — is hashed by the same rule:

value_hash = fuse(type_hash, data_hash)

The Type Hash

The type hash identifies the kind of value. It is the fuse of the type name’s characters followed by a terminating 0x00 byte:

type_hash = fuse_bytes(type_name ++ [0x00])

Type names are ordinary character strings — "i64", "vector", "ft/node". Because type names never contain a null byte, the trailing 0x00 cleanly separates the type from the data that follows. Without a boundary marker, type "i64" with data "2" could collide with type "i6" and data "42" (fuse composes over concatenation). The 0x00 makes the boundary unambiguous.

This is also what makes types self-describing: given any value, read its type name to discover its interpretation. No registry, no schema negotiation.

The Data Hash

The data hash captures the value’s content. How it is computed depends on the kind of value:

• Scalar — the fuse of its canonical bytes:

data_hash = fuse_bytes(canonical_bytes)

• Collection — the fuse of all leaf element hashes, in sequence order (vector, string, blob) or ascending key-hash order (map, set):

data_hash = fuse(fuse(fuse(e0, e1), e2), ..., en)

For collections, the data hash is built from the leaves only. The internal node type hashes (ft/node, hamt/bitmap, …) never enter it. This is deliberate — it is what makes the data hash shape-independent.

Shape Independence

Because internal type hashes are excluded, two collections with the same leaves but different internal tree shapes produce the same data hash, and therefore the same value hash. A balanced finger tree and a degenerate one holding the same elements in the same order are indistinguishable by hash. This is what lets a store reorganize a collection for performance without changing its identity.

(There is exactly one exception — HAMT bitmap nodes — explained in §3.7.)

Cross-Type Equality

Here is where Chapter 2’s group structure pays off. Since value_hash = fuse(type_hash, data_hash), the type hash can be stripped back off with the group inverse:

content_hash(v) = fuse(inv(type_hash), value_hash) = data_hash

Two values with different types but the same underlying data have the same content hash, computed in O(1). A "string" and a "vector" holding the same characters share a data hash — because their leaves are literally the same content-addressed values — even though their full hashes differ by the type tag.

3.4 The User Value Types

The six user value kinds divide into atomic scalars and collections.

Scalar types — an atomic value with a canonical byte encoding:

Collection types — a type hash over a tree of leaves:

Scalar types are atomic. Collection types are backed by internal finger-tree or HAMT primitives (§3.6, §3.7); the type hash is what distinguishes, say, a vector from a set even when their leaves coincide.

Strings, Blobs, and Vectors

Strings, blobs, and vectors are all sequences over a finger tree; they differ only in their type name and the kind of leaves they hold. A string is a sequence of char scalars, a blob a sequence of u8 scalars, a vector a sequence of arbitrary values.

The type hash keeps them distinct even when their bytes coincide: the string "A" (UTF-8 0x41) and a one-byte blob containing 0x41 have the same leaves but different type hashes, and therefore different value hashes. Internally they share the same finger-tree machinery; only the type hash differs.

3.5 Sets and Negative Sets

The Set Type

A "set" is a user value backed by a self-map — a HAMT in which every key maps to itself:

set({a, b, c})  →  type "set" over self-map {a: a, b: b, c: c}

Content addressing means the key and value point to the same hash — zero additional storage for the “duplicate” reference.

Membership test: get(self-map, x) != nil.

The Negative Sentinel

The built-in scalar type "negative" is a sentinel used to denote negative (cofinite) sets — sets that represent “everything except these elements”:

negative  →  scalar of type "negative" (empty data)

A negative set is a "set" whose self-map includes the negative sentinel as an element:

negative_set({a, b})  →  type "set" over self-map {negative, a, b}

Membership is inverted: x is a member if get(self-map, x) == nil (and x is not the negative sentinel itself).

For a thorough treatment of negative sets — including proofs that the sentinel flows correctly through all set operations using only map primitives — see Negative Sets as Data.

Set Operations

The negative sentinel flows through ordinary map operations. Because it’s just another element in the self-map, no special set machinery is needed — only the three map primitives:

Where:

• merge(A, B) — add B’s elements not already in A
• keep(A, B) — keep only A’s elements that are also in B
• remove(A, B) — remove A’s elements that are also in B

Complement is toggling the negative element: complement(A) = add negative if absent, remove if present.

The negative sentinel participates in these operations like any other element, which is what makes the pos/neg operation table work — the sentinel’s presence or absence propagates correctly through merge, keep, and remove without special cases.

3.6 Inside Seqs: Finger Trees

Seqs are implemented as finger trees — a persistent data structure that provides O(1) amortized access to both ends and O(log n) random access. The key insight for Dacite: finger trees are parameterized by a monoid, and fuse is a monoid (actually a group). The tree accumulates fused hashes as its measure.

Structure

graph TD
    D["Deep"] --> L["Left digit (1-32)"]
    D --> S["Spine (recursive)"]
    D --> R["Right digit (1-32)"]

    L --> L1["elem"]
    L --> L2["elem"]
    L --> L3["..."]

    S --> N1["node (2-32)"]
    S --> N2["node (2-32)"]

    R --> R1["elem"]
    R --> R2["elem"]

A deep finger tree has three parts:

• Left digit — 1 to 32 elements, directly accessible
• Spine — a recursive finger tree of internal nodes
• Right digit — 1 to 32 elements, directly accessible

The classic finger tree uses 1–4 elements per digit and 2–3 children per node. Dacite widens both to 1–32 and 2–32, trading the classic amortized O(1) push/pop proof for shallower trees. A tree of 1M elements is only ~4 levels deep. In a distributed setting, fewer levels means fewer network round trips — and that’s the dominant cost.

Node Types

Every node is stored in the content-addressed store as its own entry. Children are hash references — no node ever contains inline data. This means every node has bounded size regardless of collection size: at most 32 × 32 = 1024 bytes of child hashes, plus ~48 bytes of measure metadata.

The Measure Monoid

Every node caches a measure of its subtree:

Measure = {
  count:          u64,   // number of leaf elements
  size_bytes:     u64,   // total byte size of leaf scalars
  elements_fuse:  Hash   // running fuse of all element hashes
}

Measures combine as a monoid:

combine(m1, m2) = {
  count:         m1.count + m2.count,
  size_bytes:    m1.size_bytes + m2.size_bytes,
  elements_fuse: unchecked_fuse(m1.elements_fuse, m2.elements_fuse)
}

identity = { count: 0, size_bytes: 0, elements_fuse: [0, 0, 0, 0] }

The elements_fuse uses unchecked_fuse because the identity [0, 0, 0, 0] would fail the low-entropy check — this is safe since measures are internal bookkeeping, not user-facing hashes.

The root’s measure gives O(1) access to:

• count — how many elements
• size_bytes — total materialized size
• elements_fuse — the seq’s data hash

Node Hashing

Internal nodes are hashed using their type name and semantic content, the same type_hash rule as every other value (§3.3):

node_hash = fuse(fuse_str(node_type_name ++ "\0"), node.measure.elements_fuse)

The null byte terminates the type name. Nodes with the same type and the same logical elements produce the same hash — different tree shapes normalize to a single hash in the store. This is correct because nodes with the same elements are functionally interchangeable.

The elements_fuse a node caches is exactly the data hash a user sequence wraps. A "vector" value’s hash is fuse(type_hash("vector"), root.measure.elements_fuse) — its type hash fused with the leaf fuse of its root node. The internal node’s own type hash (ft/node, etc.) never reaches the vector’s hash, which is precisely why the vector hash is shape-independent (§3.3).

3.7 Inside Maps: HAMT

Maps are implemented as a Hash Array Mapped Trie — a persistent hash map that provides O(log₃₂ n) lookup, insert, and delete.

Hash Navigation

The key’s hash is consumed 5 bits at a time, from most significant to least:

Level 0: bits 255–251  (upper 5 bits of c0)
Level 1: bits 250–246
...
Level 51: bits 4–0     (lower 5 bits of c3)

Each 5-bit chunk selects one of 32 possible child positions.

Because c0 has the most mixed bits (from the fuse multiply), the first levels of the HAMT navigate using the highest-quality entropy.

Bitmap Indexing

Internal nodes use a 32-bit bitmap to mark occupied positions:

child_index = popcount(bitmap & ((1 << chunk) - 1))

The children array is compressed — only occupied positions have entries. A bitmap node with 5 children stores exactly 5 hashes, not 32.

Node Types

Traversal Order

HAMT traversal visits children in ascending bitmap order, which corresponds to ascending key hash order. This makes elements_fuse deterministic regardless of insertion order — two maps with the same entries always have the same data hash.

HAMT Bitmap Node Hashing

Bitmap nodes include the bitmap value in their hash:

hamt_bitmap_hash = fuse(node_hash, fuse_bytes(bitmap_as_8_bytes))

This is the only exception to the shape-independence rule of §3.3. It’s necessary because two bitmap nodes at different HAMT levels could have the same elements and element fuse but different bitmaps — meaning they route lookups differently and are not interchangeable. Without the bitmap in the hash, these nodes would collide, creating self-referential loops in the store. The exception is confined to internal bitmap nodes; a map’s own data hash — the fuse of its leaf entries — remains shape-independent.

3.8 Collision Resistance

Fuse-based hashes have ~2^96 birthday-bound collision resistance, from the additive structure of components c1–c3. This is weaker than SHA-256’s ~2^128 but far beyond practical attack.

Threat Model

Fuse hashes are designed for cooperative environments where participants are trusted to produce honest data. In adversarial contexts — where untrusted peers contribute data — fuse hashes alone should not be relied upon for integrity.

For trust boundaries, pair dacite hashes with a cryptographic hash:

verification_pair = { dacite_hash, sha256 }

Verify the cryptographic hash on ingest; use the dacite hash for internal navigation. The fuse hash gives you speed and algebraic structure; the cryptographic hash gives you adversarial resistance.

3.9 API Surface

Primitives

The irreducible core of the value layer — scalars plus the internal tree primitives the collection types are built from:

Scalar

Seq (Finger Tree)

Map (HAMT)

Measure

Derived

Convenience functions that compose from the primitives:

From seq primitives

From map primitives

User value constructors — implicit forms use the current store; explicit -with-store forms take a store as the first argument. Implicit constructors are the primary API; most application code never passes a store explicitly.

Examples:

;; implicit — uses *store* (default or bound)
(dacite/i64 42)
(dacite/vector 1 2 3)
(dacite/hash-map "a" 1 "b" 2)

;; explicit — when the store matters
(dacite/i64-with-store store 42)
(dacite/vector-with-store store 1 2 3)

;; isolated context (testing, transactions)
(store/with-store [s (store/mem-store)]
  (dacite/vector 1 2 3))

The -with-store suffix avoids the varargs ambiguity that would arise if store were an optional first argument to the same function — (vector 1) must mean a one-element vector, not an empty vector in store 1.

Value accessors

The store reference enables transparent persistence. When you assoc a map or conj a vector, the resulting value is automatically stored in the same backing storage — no store parameter needed for operations or for construction in the common case.

Set operations — derived from HAMT primitives + dac-negative:

Cross-type

Properties

• All values round-trip: construct → hash → reconstruct yields the same hash
• content-hash(string("abc")) = content-hash(vector(['a','b','c']))
• count(conj-right(t, x)) = count(t) + 1
• nth(conj-right(empty, x), 0) = x
• measure(concat(a, b)) = combine(measure(a), measure(b))
• get(assoc(m, k, v), k) = v
• get(dissoc(m, k), k) = nil
• Insertion order doesn’t affect map hash (deterministic traversal)
• union(complement(A), A) = universal set (negative empty)
• intersect(A, complement(A)) = empty set

This layer depends on Chapter 2 (hash fusion) and Chapter 1 (content stores). No I/O required for pure operations, though values carry a store reference for transparent persistence when mutated. All primitive functions are pure.

3.10 What This Layer Provides

The value layer gives the rest of Dacite:

1. A closed data model — six user value kinds — scalars, vectors, strings, blobs, maps, and sets — compose into arbitrarily complex structures, all content-addressed.
2. Self-describing types — every value names its own type, and a type is just a string of characters. The user set is closed, but the vocabulary can grow without new machinery.
3. O(1) metadata — count, size, and data hash are always available at the root, without traversal.
4. Bounded nodes — every node in every tree fits in ~1 KB. No node is ever “too big to fetch.”
5. Shape independence — two collections with the same leaves have the same hash, regardless of internal tree organization.
6. Store-aware — values know their store, enabling transparent persistence on mutation.

The next chapter adds a single mutable root on top of the content store, turning this immutable world of values into one that evolves over time and synchronizes between peers.

Chapter 4: Rooted Stores

The first three chapters describe an entirely immutable world. A content store (Chapter 1) is a dictionary that only grows; hash fusion (Chapter 2) gives every piece of content a permanent identity; values (Chapter 3) are trees of nodes stored under those hashes. Nothing there ever changes — a value, once stored, is stored forever.

But useful systems change over time. A configuration is edited, a document is revised, a peer learns that “the current state” is now something new. Dacite expresses all of that with one mutable cell layered on top of the immutable world:

A rooted store wraps a content store and adds a single mutable root — a reference to one hash in the store.

Everything underneath stays immutable. The root is the only thing that moves. “Changing” the data means computing a new value (a new tree of immutable nodes, sharing all the unchanged ones) and then moving the root to its hash.

A rooted store is also a content store: it answers all the content operations of Chapter 1 by delegating to the store it wraps. So it is a drop-in wherever a content store is expected, while additionally exposing the root.

Because a root may be shared — several writers, and often across a network — its update contract is the heart of this chapter. That contract is compare-and-set.

4.1 The Root and Its Operations

A rooted store adds one mutable cell holding a root hash (or none, before anything has been stored). Two operations form the required core — the entire portable contract, and all that even a remote store must implement:

root is the read; cas-root is the one update primitive. Everything else is an optional convenience — available on a local store, but constrained or absent for a remote one:

Note the deliberate minimalism: there is exactly one moving value — a hash — and only two operations you must implement to have a working rooted store, remote included.

The root holds a hash, not a materialized value. root(store) returns a hash; to see the value it names, hand that hash to the value layer (Chapter 3). Keeping the mutable surface to a single hash is precisely what makes remote roots and synchronization tractable — you coordinate on 32 bytes, not on a whole tree.

4.2 Compare-and-Set Is the Core Update

Why single out cas-root instead of a plain “set the root”? Because an unconditional set loses updates whenever the root is contended.

Consider two writers that both read root R, each build a successor, and each install it:

sequenceDiagram
  participant A as Writer A
  participant S as Root (= R)
  participant B as Writer B
  A->>S: root() → R
  B->>S: root() → R
  A->>S: set-root(R1)
  Note over S: root = R1
  B->>S: set-root(R2)
  Note over S: root = R2 — A's change is lost

Whoever writes last wins, and the other writer’s change vanishes silently. cas-root prevents this: each writer installs new only if the root is still the expected value it built upon. The loser’s CAS fails — the root has already moved — so it must rebuild on the new root and retry:

update-root(store, f):
    loop:
        old = root(store)
        new = f(old)                     # build a successor value; store its nodes
        if cas-root(store, old, new):
            return new                   # success
        # else: someone moved the root — loop, re-read, rebuild on the new old

This read-modify-write-retry loop touches only the two core operations — root and cas-root — so update-root is a client-side convenience, not a capability the store (or a server) must provide specially. It is also the only safe way to evolve a shared root. set-root is merely the degenerate case where you know there is no contention (a fresh store, a single writer, initialization); it is a local convenience and is not offered for remote stores. Everything else — concurrent local writers, and especially remote stores — goes through CAS.

For a remote store, root is a network read and cas-root is an operation the server performs atomically against its authoritative root: the client sends (expected, new), the server compares and swaps under its own lock, and reports success or a conflict. The correctness of the whole distributed picture rests on that single server-side compare-and-set. An unconditional remote “set root” cannot be made safe under concurrency; it is not offered as the primitive for that reason.

4.3 Building a Successor

“Changing” data means computing a new immutable value and moving the root to it. Expressed with update-root:

update-root(store, fn(old):
    m  = value-at(store, old)       # Chapter 3: rehydrate the value at the root
    m' = assoc(m, "count", 42)      # structural edit — new nodes stored, unchanged nodes shared
    return hash-of(m'))             # the successor root hash

Because the value layer stores every node it builds before returning the successor hash, by the time cas-root runs, all nodes the new root reaches are already present in the content store. Installing the root is the final, atomic step — the store never points at content that isn’t there.

Replacing the root does not delete the old tree; nodes unique to it become detached (§4.6). And if a concurrent writer moved the root first, the CAS fails and the whole function re-runs against the new root — automatically rebasing the edit onto the latest state.

4.4 Observing Changes

Because the root is a single observable cell, others can react to its transitions:

• Locally, register a callback that fires on each successful root change with (old, new).
• Remotely, subscribe to the server’s root stream — an optional capability whose exact shape depends on the transport (long polling, websockets, server-sent events).

watch-root(store, :sync, fn(old, new):
    log("root moved", old, "->", new))

Observation is what makes a rooted store reactive: a root move can drive a re-render, a log entry, or a push to a peer (§4.7). Both observation forms are optional — local callbacks come for free, while remote subscription is protocol-specific.

A store may also guard transitions with a validator — a predicate consulted before a new root is installed, rejecting ones that fail it. A validator runs wherever the commit is decided, so it is a local-only convenience for now; enforcing one on a remote store would mean evaluating the predicate server-side, a future code-as-data capability.

4.5 Durability: the Root Cell

The root must outlive the process. A rooted store persists it through a small abstraction, the root cell, which knows only how to load and store a single hash:

• memory root cell — holds the hash in memory; ephemeral, for tests and REPL use.
• LMDB root cell — persists the hash in the LMDB meta database, reusing the same environment as an LMDB content store.

rooted-store(content-store)                       # ephemeral root (default)
rooted-store(content-store, lmdb-root-cell(lmdb)) # durable root beside LMDB content

On construction the store seeds its in-memory root from the cell; on every successful update it flushes the new root back to the cell. Reopening the store recovers the last root.

Note the clean separation of responsibilities: the content store persists nodes; the root cell persists the one hash that says which node is current. They may share a backend (LMDB), but they are distinct concerns.

4.6 Detached Nodes and Garbage Collection

Any entry reachable from the current root is live. Entries that were reachable under a previous root but are not part of the current tree are detached. They remain in the content store until garbage collection removes them.

GC is fundamentally a value-aware traversal, and it needs both halves of this layering: the root (this chapter) as the starting point, and the value model (Chapter 3) to deserialize a node and discover its child references. Starting from root(store), mark every reachable node; anything unmarked is detached and may be reclaimed. The content store itself knows nothing about reachability — it only maps hashes to values — which is exactly why GC lives up here with roots and values rather than down in the content store.

4.7 Sync Between Stores

Synchronization copies one store’s root onto another. Framed in terms of §4.2, moving target to source’s root is a compare-and-set on the target:

push(source, target):
    cas-root(target, root(target), root(source))

Because the target may itself be changing, a push can lose the CAS and need to be reconciled just like any other update — there is no privileged “force set” for a shared target. Push deliberately transfers only a hash; the underlying content must already be present at the target or be synced separately. Deciding when to push, and how to move the content a new root depends on, are application concerns; the rooted store provides only the atomic root move.

This is the seam through which peers coordinate: a source installs a new root (via CAS), then pushes that hash; subscribers on the target observe the new root and fetch whatever content they lack.

4.8 What This Layer Provides

1. A single mutable root — one hash — over an immutable content store.
2. A two-operation portable core — root and cas-root — sufficient for any store, local or remote; cas-root is the one update primitive.
3. Optional conveniences over the core: update-root (a client-side retry loop), set-root (local, uncontended), observation via watch-root (local callbacks; remote is transport-specific), and validators (local for now).
4. Durable roots via a root cell, kept separate from content persistence.
5. Content-store delegation, so a rooted store is a drop-in content store that also has a root.
6. Push as an atomic, CAS-based sync primitive between stores.

With this, Dacite has both halves of its model: an immutable world of content-addressed values, and one mutable pointer — governed by compare-and-set — that lets that world evolve and be shared. Future work (see the roadmap) builds distribution and event flows on exactly this root-and-CAS foundation.

Reference Implementation (Clojure)

The abstract operations above are language-neutral; a port to any language need only provide the core two. The Clojure reference implementation surfaces the operations through Clojure’s standard reference protocols, so a local rooted store behaves like an idiomatic mutable reference:

A local rooted store implements the whole set (IDeref, IRef, IAtom2) for free — compare-and-set! is the core primitive of §4.2 and swap! is its retry loop. A remote rooted store need implement only the core two (deref and compare-and-set!); it does not offer reset! (set-root) or validators, realizes swap! (update-root) as a client-side loop over the core, and exposes watches only if its transport supports them. The value never escapes being a single root hash, so these interfaces stay a thin, faithful skin over the language-neutral contract — not a dependency of it.

Appendix: Serialization

This appendix defines the canonical binary format used for storage and network transfer in Dacite. It is intentionally low-level and reference-oriented.

Binary Format

Every serialized node begins with a 1-byte kind tag:

Scalar

scalar = 0x00 ++ u8(len) ++ bytes[len]

Max size: 255 bytes. Hash = fuse_bytes(raw bytes) (framing is not part of the hash).

Measure (common)

Appears in seq and map nodes:

measure = u64(count) ++ u64(size_bytes) ++ hash(elements_fuse)

(8 + 8 + 32 = 48 bytes)

Seq Nodes (kind 0x01)

seq_node = 0x01
        ++ u8(subtype)
        ++ measure
        ++ u8(n_children)
        ++ hash[n_children]

Subtypes:

• 0x00: empty
• 0x01: single
• 0x02: digit (1–32 children)
• 0x03: internal node (2–32 children)
• 0x04: deep (left, spine, right)

Map Nodes (kind 0x02)

map_node = 0x02
        ++ u8(subtype)
        ++ measure
        ++ ... (type specific)

Subtypes:

• 0x00: empty
• 0x01: entry (key_hash ++ key_ref ++ val_ref)
• 0x02: bitmap (u32(bitmap) ++ u8(n) ++ hash[n])

Collections (kind 0x03)

collection = 0x03
          ++ u8(collection_type)
          ++ hash(root)
          ++ u64(count)
          ++ u64(size_bytes)

Collection types:

• 0x00: vector
• 0x01: string
• 0x02: blob
• 0x03: map

The collection header is always exactly 50 bytes.

JSON Format (for debugging and interop)

Structural mode (hash references):

• Uses "kind", "hash", and child hashes.

Materialized mode (fully inlined):

• Produces familiar nested objects with "type" and "value".

Hybrid mode: Combines both using an inline_under threshold.

See the old SPEC.md for full JSON examples and schemas if needed.

Extracted and adapted from old SPEC.md (as of 2026-02-27). This is the new canonical reference for the binary wire/storage format.

Archived Chapters

These chapters document the authorization and sharing model that was designed for a shared multi-user store. They are archived because the architecture has shifted to dedicated stores per user, which removes the need for Proof of Possession and sharing mechanisms entirely.

Contents

• 04-authorization/ — Proof of Possession, GET/PUT, auth stores, garbage collection
• 05-sharing/ — Shares map, claim mechanism, conventions

Why Archived

New direction (2026-06-05): Each user has their own dedicated store.

Key implications:

• No shared store → No need for Proof of Possession (PoP)
• No PoP → No authorization layer to gate access
• No authorization → No sharing mechanisms (shares map, claim, etc.)
• Dedicated stores → User isolation by architecture, not by convention

This is a fundamental simplification: instead of building access control on top of a shared content-addressed store, we give each user their own store and let higher-level protocols handle cross-user interactions.

Salvageable Ideas

Some concepts may be useful in future designs:

• Content-addressed root management
• Store backend abstractions
• Delegation concepts (may map to cross-store protocols)

Archived 2026-06-05

Chapter 4: Authorized Stores

Chapter 1 gave us stores — persistence and distribution across machines. Every store has a root. But Chapter 1’s stores are unauthorized: anyone with access can fetch any hash. In a single-user system, that’s fine. In a multi-user system, it’s “knowing a hash is authorization.”

Dacite rejects this. This chapter introduces authorized stores — stores that require proof of possession before they will fetch or store a node. The mechanism is structural proofs over the DAG: data proofs and chain proofs. Together they give secure access control without ACLs or capabilities — just roots and the paths between them.

The authorized store protocol builds directly on the unauthorized store from Chapter 1. The difference is that fetch and store now require proof. All interaction still flows through get-root and set-root, but the store verifies that every accessed node is structurally reachable from an authorized root.

4.1 The Authorization Challenge

In a conventional operating system, memory protection is relatively straightforward. The kernel allocates regions of RAM to a process and uses hardware memory management units (MMUs) to prevent that process from reading or writing addresses outside its allocation. A memory address is only meaningful within a protected context.

graph TD
    subgraph OS [Traditional OS]
        Kernel[Kernel\nMemory Protection]
        ProcessA[Process A\nAllocated Range]
        ProcessB[Process B\nAllocated Range]
        Kernel --- ProcessA
        Kernel --- ProcessB
    end
    style Kernel fill:#4a9,stroke:#333,color:#fff

Dacite faces a fundamentally harder problem.

All data is content-addressed. A hash is not a private location granted by a central authority — it is a globally unique, publicly shareable pointer into an immutable DAG that may be referenced by many users simultaneously. Knowing a hash gives you an address, but there is no kernel standing behind it to enforce ownership.

graph TD
    subgraph Dacite [Dacite Content-Addressed DAG]
        RootA[User A Root #RA]
        RootB[User B Root #RB]
        Shared[Shared Subtree #S]
        RootA --> Shared
        RootB --> Shared
    end
    style Shared fill:#a84,stroke:#333,color:#fff

Sharing is intentional and valuable. The danger is that any party who merely learns a hash can fetch its value — there is no kernel or access control list standing behind a content address. We must prove legitimate structural possession — that a requester can demonstrate they are authorized to access a value from their own authorized root.

This chapter introduces the mechanisms Dacite uses to solve this problem: proof chains, authenticated stores, and the GET/PUT protocols built on structural proofs.

4.2 Core Principle

Knowing a hash does not authorize access to its value.

Hashes leak — in logs, URLs, errors. A hash is an address, not a key. Dacite’s authorization is structural: prove you possess the data.

4.3 Proof of Possession

Every access in Dacite requires a proof of legitimate possession. There are two fundamental forms of proof:

Data Proof

The client sends the raw bytes. The server hashes them and confirms the hash matches the requested address. This is the most direct form of proof — the client is demonstrating it physically holds the data.

Chain Proof (Structural Possession)

When the client does not want to send the full data (or the data is very large), it can send a chain proof — an ordered list of hashes from an authorized root down to the target value.

A chain proof has the form:

[#R, #h1, #h2, ..., #target]

For each consecutive pair in the chain, the server verifies that the parent node actually contains the child hash. This proves the target is reachable from the root through a valid path in the DAG.

Example Chain Proof

graph TD
    R["map (root) #R"] --> E1["entry #E1\n'name' → 'Alice'"]
    R --> E2["entry #E2\n'scores' → vector"]
    E2 --> V2["vector #V2"]
    V2 --> S1["10"]
    V2 --> S2["20"]
    V2 --> S3["30 #S3"]
    style R fill:#4a9,stroke:#333,color:#fff
    style S3 fill:#49a,stroke:#333,color:#fff

A client wanting value #S3 can send the chain [#R, #E2, #V2, #S3]. The server performs three lookups to confirm each link is valid.

Chain proofs allow efficient verification without sending large subtrees. Together with data proofs, they form the foundation of both reading and writing in Dacite.

4.4 Reading (GET)

Reading is the simpler case. A client authenticates and receives its current root hash. To read a value, it sends a proof chain from that root to the desired target.

sequenceDiagram
    participant C as Client
    participant S as Server

    C->>S: authenticate
    S-->>C: session token + current root hash #R

    C->>S: GET #S3 with proof chain [#R → #E2 → #V2 → #S3]
    Note over S: Verify each link in the chain
    S-->>C: Value at #S3

The server only needs to validate the chain — it does not need to trust the client beyond that. This gives strong, stateless authorization.

4.5 Writing (PUT / Root Update)

Writing is expressed as a root replacement. The client does not send a separate “new root” declaration. Instead, it begins a proof stream whose first proof is for the new root itself.

• If the first proof is a chain proof, the last hash in the chain becomes the new root.
• If the first proof is a data proof, the hash of that node becomes the new root.

The client then walks the new tree in deterministic DFS order (via child-hashes). For each node encountered, it sends either:

• A data proof for newly created or modified nodes, or
• A chain proof from the old authorized root for unchanged subtrees.

The server validates each proof as it arrives. When the DFS traversal completes (the stack is empty), the server atomically updates the user’s root to the new hash.

This approach eliminates a round-trip and removes special-case logic. Because every node in the new tree must be proven from either new data or a valid chain from the client’s current root, hash-capture attacks are prevented.

sequenceDiagram
    participant C as Client
    participant S as Server

    C->>S: Begin PUT proof stream (first proof = new root)

    Note over C,S: Client walks new tree in DFS order

    C->>S: Proof for new root (chain or data)
    Note over S: Validates. New root hash = resolved hash.
    S-->>C: OK

    C->>S: Next proof in DFS order...
    S-->>C: OK

    Note over S: DFS stack empty — transition complete
    S-->>C: Root updated

GET is a strict subset of this PUT protocol.

4.6 Client-Side Proof Caching

The GET and PUT protocols place the burden of proof on the client. The server is stateless: it validates proofs but does not track paths or sessions. This section describes how clients efficiently generate the chain proofs required by these protocols.

Chain Proofs as Cached Path Information

A chain proof is a Dacite Vector of hashes [#R, #h1, ..., #target] representing a path from an authorized root to a target node. During normal operation, clients build and cache these proofs naturally:

During GET: A client requests node #A with chain proof Ac = [#R, ..., #A]. The server returns the value. The client now knows that every child hash of A is reachable via (conj Ac child-hash). These extended proofs can be cached for future use.

During PUT: A client constructs new node #B that reuses child #c from a previous GET. Rather than rebuilding a path from scratch, the client looks up #c in its cache, finds its chain proof, and emits it directly.

The Cache Structure

The client maintains a map from hash to chain proof:

;; hash → [root-hash ... target-hash]
{hash-a [root-hash mid1 hash-a]
 hash-b [root-hash mid1 mid2 hash-b]}

• Population: Lazily, during GET responses. Each fetched node extends its proof with its children.
• Lookup: O(1) for any cached hash. A chain proof for a child is (conj parent-proof child-hash).
• Growth: Bounded by the set of nodes the client has fetched in its current session.

Root Changes and Invalidation

When the client’s primary root is successfully updated via PUT, chain proofs based on the old root become invalid for future GETs and PUTs. However:

1. The client just walked the new tree during the PUT protocol. It knows the new structure.
2. For unchanged subtrees, the client can re-derive chain proofs by following the same paths under the new root.
3. Chain proofs based on shared roots (read-only, see Chapter 5) remain valid across primary root updates.

The client must track which root each cached chain proof is based on (primary vs. shared) and invalidate accordingly.

The Inverted Client/Server Relationship

Because chain proofs are represented as Dacite Vectors, they are themselves storable values. During a PUT, the client provides the server with an unauthorized store containing just the chain proofs it wishes to use. The server fetches these proofs as ordinary Dacite values to verify them.

This is not a new mechanism — it is a natural consequence of the client’s existing cache. The same chain proofs the client builds for its own efficient operation are precisely what the server needs to verify. The client cache serves dual purpose: it enables fast chain proof generation for the client’s own use, and it provides the proofs the server needs during PUT verification.

Design Notes

• Deferred: Cache size bounds and eviction policies are left for future work. For now, the cache is session-scoped and unbounded.
• Required for PUT: The client’s chain proof cache is not merely an optimization — it is the mechanism by which the server verifies PUT requests. The client must provide chain proofs as Dacite Vectors for the server to fetch and validate.

4.7 Garbage Collection (Future)

Not yet implemented. This section describes the target design.

Liveness is defined as reachability from any authorized root.

We plan to use a semi-space collector with two equivalent strategies:

The collector runs online, cost is proportional to live data, and structural sharing is preserved.

4.8 API Surface

Implemented

The prover is a function (fn [hash] -> {:type :chain, :chain [...]} | {:type :data, :value ...}).

Supporting (Layer 2)

• child-hashes — returns ordered vector of child hash references for any node type.

Key Properties

• Proof chains verify structural reachability
• PUT requires full possession (data or chain from current root)
• Server maintains invariant: it holds all data reachable from authorized roots
• DFS order is deterministic based on child-hashes
• Garbage collection will be based on root reachability

Depends on Layers 1–3. All verification logic is built on top of the store abstraction.

4.9 What This Layer Provides

1. Secure stores — proof of possession prevents “hash-as-capability” attacks
2. Stateless authorization — roots + chains, no server-side session state required
3. Uniform proof model — GET, PUT, and future GC all derive from the same concept
4. Peer-ready — the same proof protocol works in both directions
5. Client-driven — the server validates; the client controls proof ordering and tree shape

Chapter 5 builds on this foundation by introducing sharing conventions (shares map, groups, and delegation) layered atop authorized stores.

Chapter 5: Sharing

Chapter 4 gave us authorized stores. Every user has their own root, and access to any node must be proven from that root. This works well for private data. But it creates a practical question: how does Alice give Bob read access to just one subtree without handing over her entire root?

The answer is surprisingly simple. We do not add new primitives to the store or the authorization protocol. Instead, we establish a convention inside every root and a small claim protocol that lets one user ask the server for access to a subtree that someone else has offered. Users share with users, and the server shares with users, all through the same mechanism.

5.1 Claim Protocol

Let us walk through a concrete example. Alice has a collection of photos stored under her root. She wants to share just that collection with Bob, but she does not want to give him access to anything else she owns.

First, Alice updates her root to record the offer. She adds an entry in a shares map that says, in effect, “I am offering the subtree at hash #T to Bob.” She does this with a normal PUT, the same operation she uses for any other change to her data.

Next, Alice tells Bob about the offer through some out-of-band channel. She might send him a message that says, “claim the photos share from me.” Bob does not yet have the hash #T. He only knows the name Alice gave the share.

Bob now contacts the server and says, “I would like to claim the share named photos from Alice.” The server looks up Alice’s current root, finds the shares entry for photos, checks whether Bob is in the authorized set, and if so, adds the target hash #T to Bob’s session-scoped set of claimed roots. From that moment on, Bob can issue GET requests against #T (and any subtree under it) using the normal proof chain mechanism. His access is strictly read-only: he may not replace the value at #T itself. He may, however, create new values under his own primary root that reference or incorporate content reachable from #T.

sequenceDiagram
    participant A as Alice
    participant B as Bob
    participant S as Server

    A->>S: PUT root (add shares["photos"] = {#T, #{bob}})
    S-->>A: OK (new root hash)

    A->>B: out-of-band: "claim 'photos' from me"
    B->>S: CLAIM "photos" from Alice
    Note over S: look up Alice's root<br/>find shares["photos"]<br/>check bob ∈ authorized ✓<br/>add #T to Bob's claimed roots
    S-->>B: OK

    B->>S: GET #T (with proof from claimed root)
    S-->>B: Value at #T

The sequence is straightforward once you see it in action. Alice offers. Bob claims. The server validates the claim against Alice’s current root and grants Bob an additional valid root for the duration of his session. No special server state is required beyond what is already stored in Alice’s root. The set of claimed roots lasts only for the current session. Bob must re-claim any shared roots in each new session. This keeps the server stateless with respect to long-lived claims.

A subtle but important point: Alice is sharing a specific value (the immutable content reachable from #T), not an ongoing pointer to a location that might change. Because Dacite values are content-addressed and immutable, once Bob receives #T he has permanent access to that exact value and everything it contains. If Alice later wants Bob to see an updated version of the photos, she must create a new value at a new hash and either update the target in her existing share or create a fresh share entry. There is no way for her to retroactively alter what Bob already received.

One alternative design would have been to record claimed roots persistently in a claims map inside Bob’s root, similar to how shares records offers. This would let Bob work with only a single root and would make shared access survive across sessions. However, it would require the server (or the client convention) to decide where received shares live in the user’s tree. An inbox? A Downloads-style directory? A special received subtree? Different applications would naturally want different organizations, and enforcing one canonical location would make the sharing layer more opinionated than necessary. By keeping claimed roots session-scoped, the mechanism stays lightweight and the client is free to incorporate shared data into its own tree however it chooses.

5.2 Root Structure Convention

The shares map lives inside the root alongside the user’s actual application data. A typical root looks like this:

root = {
  "value": <app data>,
  "shares": {name: {target: #H, authorized: Set}, ...},
  "groups": {name: Set, ...}
}

The value field holds whatever the application cares about. The shares field records offers the user has made to others. The groups field lets the user define named sets of identities so that a single share can be offered to an entire group without listing every member.

All of this is ordinary data. Alice modifies her shares map the same way she modifies any other part of her tree. The server never interprets the contents of value. It only looks at shares and groups when processing a claim request.

5.3 Server Uses Shares

The server participates in the same sharing model. When a user first authenticates, the server looks up that user’s entry in its own root’s shares map. That entry contains the user’s root hash and the set of identities authorized to claim it. The user is effectively claiming their own identity from the server.

This uniformity is deliberate. There is no special server-side session table or capability list. The server root is just another Dacite root, and the same claim protocol that lets Bob access Alice’s photos also lets Alice access her own data after authentication.

server-root.shares = {
  "alice": {#RA, #{alice}},
  "team": {#TP, #{alice,bob}}
}

In this example, Alice can claim #RA for herself, and both Alice and Bob can claim the team root #TP. The server does not need to maintain any additional state beyond its own root.

graph TD
    SR["Server Root"] --> SV["value: config"]
    SR --> SS["shares"]
    SS --> SA["'alice': {#RA, #{alice}}"]
    SS --> SB["'bob': {#RB, #{bob}}"]
    SS --> ST["'team': {#TP, #{alice,bob,carol}}"]
    SA --> RA["Alice's tree"]
    SB --> RB["Bob's tree"]
    ST --> TP["Team tree"]
    style SR fill:#4a9,stroke:#333,color:#fff

5.4 Read-Only Access and Write-Back

When Bob claims a share from Alice, he receives a read-only view. He can traverse the subtree at #T and he can incorporate any of its contents into his own tree, but he cannot modify Alice’s data directly. If he wants to propose changes, the natural pattern is for him to create his own version of the subtree and then share that version back to Alice. Alice can then review the changes and merge them if she chooses.

This keeps the protocol simple. There is no write-back delegation or complex merge negotiation at the store level. Users collaborate by sharing data, modifying it in their own trees, and sharing the results back.

5.5 Named Groups

The groups map inside a root lets a user define named sets of identities. Instead of listing every member in the authorized set of a share, Alice can write authorized: "team". The server resolves that name against Alice’s groups map at claim time.

Updating the group updates access everywhere the group name is used. This is ordinary data manipulation, not a special administrative operation.

Public sharing is also supported through a convention. The set #{neg} means “everyone except the listed members.” A share with authorized: #{neg} is effectively public. The cofinite set convention was introduced in Chapter 3 as part of the set type and is reused here without any new machinery.

5.6 Share Types

The same shares structure supports several common patterns:

• Private: #{me} — only the owner can claim it.
• Direct: #{me, bob} — the owner plus one other party.
• Shared: #{team} — any member of a named group.
• Public: #{neg} — anyone at all.

Because the authorized field is just a set, any of these patterns is expressed the same way. The server does not treat them differently.

5.7 Named Refs and Revocation

A share records a target hash. If Alice later updates the content behind that hash, Bob will still see the old version unless he re-claims the share. This gives Alice a natural way to publish updates: she changes the target in her shares entry, and anyone who re-claims receives the new hash.

Revocation is similarly straightforward. Alice can remove Bob from the authorized set, or she can remove the share entry entirely. The next time Bob attempts to claim, the server will refuse. There is no need for a separate revocation list or lifecycle protocol. The share simply ceases to exist or ceases to include Bob.

5.8 Common Patterns

Several usage patterns emerge naturally from this model.

For a photo album, Alice keeps the target hash up to date. When she adds new photos, she updates the subtree and changes the share target. Bob re-claims to see the latest version.

For collaborative editing, Bob reads Alice’s subtree, makes changes in his own tree, and shares the modified subtree back to Alice. Alice reviews the changes and can merge them into her version if she wishes.

For a team workspace, the team root is shared with a group. Any member can read and, if they have write permission on the share, can also update the shared content. The group membership is managed in one place, the owner’s groups map.

5.9 Cross-User Sharing and Deduplication

When multiple users share the same subtree, they all reference the same content hashes. Dacite’s content addressing means the underlying nodes are stored only once. The sharing mechanism does not create copies. It simply gives multiple roots permission to reach the same nodes.

graph TD
    AE["Alice's tree"] --> SM["Shared subtree #SM"]
    BE["Bob's tree"] --> SM
    SM --> N1["shared nodes"]
    SM --> N2["shared nodes"]
    style SM fill:#aa4,stroke:#333,color:#fff

This is the same structural sharing that Dacite provides within a single tree, extended across users.

5.10 Audit

Every access is accompanied by a proof chain. The server can record which root was used for each request, and the chain itself shows the path from that root to the accessed node. This provides a natural audit trail without any additional logging mechanism.

5.11 Eliminated Concepts

The sharing design removes several ideas that were considered earlier:

• Grants with explicit lifecycles are replaced by ordinary shares that live in the data.
• Gift queues and pending offers are replaced by the claim-time lookup against the current root.
• A special service root or capability table is replaced by the server’s own use of the shares map.

All of these simplifications follow from the same principle: keep the protocol uniform and let the data carry the policy.

5.12 API Surface

The new operations are minimal.

Primitives

Derived Operations

The functions share, unshare, and add-group are ordinary HAMT operations on the root map. They require no special protocol support.

Zero new primitives are added to the store or authorization layers. Sharing is a convention built on top of Chapter 4.

5.13 What This Provides

1. Subtree sharing — Access is scoped by construction to whatever the sharer puts under the target hash.
2. Uniform mechanism — The server and ordinary users participate in the same protocol.
3. Mutable references — The target of a share can be updated through normal PUT operations.
4. Composability — A user can re-share data they received from someone else, creating chains of delegation without any special support.

The top of the stack is now complete: stores, hash fusion, values, authorized stores, and sharing conventions. Each layer adds capability without introducing new primitives at the layers below.