Preface

Dacite lets you write programs over immutable values while stores persist and transmit them. Values are content-addressed: identity is the hash, updates return new values, unchanged parts are shared. A rooted store adds one mutable root hash so a running program has a current snapshot.

This book is for people writing applications. Implementors of a new host or store backend will want How it works as well.

Reading

1. The Dacite way — the stance on data.
2. Install — nbb (fastest) or JVM.
3. Anatomy of a Dacite app — Values / Store split, root-ref, public API.
4. One tutorial that matches what you are building (a document, history, a large sequence, two writers, blobs, a browser UI).
5. The cookbook for field reads, updates, and commit loops.
6. Values and Stores when you need a function.

How it works is the four-layer model (content stores, hash fusion, values, rooted stores) plus pack transport. Skip it until the application recipe is clear — or until you are changing the library.

For

Application authors first. Implementors and designers second.

Jonathan & Gorm, 2026

The Dacite way

Dacite is a way of writing programs over immutable values while stores hold and move the bytes. The application thinks in maps, vectors, strings, and scalars. Persistence, caching, and the network are a dictionary from content hash to node.

This page is a stance, not an API. Anatomy of an app is next. Skip to How it works only if you are implementing a store.

Values, not blobs you round-trip

A Dacite value is store-aware and content-addressed. It knows its type, its hash, and which store created it. You do not serialize a Clojure map to EDN, write a file, and parse it back later. You build a value; the constructor writes nodes into the store; the hash is the identity of that content.

The closed set of user kinds is small on purpose:

• scalar — a typed atom (i64, bool, char, null, …)
• string — text (a sequence of characters)
• blob — bytes
• vector — an ordered collection of values
• map — keys to values
• set — distinct values

Model the domain in those six. Do not keep a host map “until it is time to save.” There is no save step. An assoc or conj returns a new value whose unchanged parts are the same nodes — and the same hashes — as before.

Finger trees and HAMTs implement those collections. They are not the application model. Pack chunks are not the application model either. Domain code requires dacite.value and dacite.store.

Identity is the hash

Two values with the same type and content have the same hash on every host (JVM, babashka, nbb). If you edit a document’s title and leave the body alone, the body hash does not change. History is free: keep the old document value (or its hash) in a vector; restoring it is installing that value again, not replaying a diff.

This is the property a JSON file cannot match. Overwriting config.json destroys the previous snapshot unless you invent versioning beside the data. In Dacite the previous snapshot is still in the store, reachable from any root that still names it.

You almost never want the whole tree

A value may be larger than memory, or only partly on this machine. Reads should name what you need:

realize on a scalar yields a host atom. realize on a collection yields a lazy seq of realized elements — not into []. Consuming the whole seq is an explicit full traversal.

Do not convert a Dacite value into a host collection “so the rest of the program can use it.” That assumes the tree fits in RAM and is fully local. dac->clj exists on the JVM as an emergency hatch for tests. Application code that reaches for it has found a hole in dacite.value — fill the hole (a bounded field read, a page, a streaming encoder), do not dump the tree.

One mutable root

Underneath, nothing is updated in place. The only moving cell is a root hash on a rooted store. “Save” means: compute a new value, then compare-and-set the root to its hash.

Several writers coordinate on that one hash. The portable update is ref-swap! (retry on conflict). There is no distributed lock and no CRDT in the core. Two clients appending to a log interleave with compare-and-set; lost updates show up as retries, not silent clobbering.

Remote stores refuse unconditional ref-reset!. Seeding an empty remote root uses ref-cas! from nil.

Stores are wiring

Mem, file, LMDB, and HTTP all speak the same store protocol. Domain functions take and return values. They do not open files or build URLs.

A typical app splits in two, as todo.cljc does:

• Values — add-todo, toggle-at, seed data, root-ref swap. Only dacite.value.
• Store — path, --url, write-back policy, reset. No todo shape.

Point the same domain at a file store or at clojure -M:service. The HTTP client packs neighborhoods on GET and flushes packed literals on commit. That is transport. The domain does not import it.

Not git, not REST, not an atom

Git is a fine tool for source. REST is a fine way to expose a view. An atom plus a file is a fine way to sketch. Dacite is for programs whose data is the value: nested, versioned, partly remote, and large enough that you should not load all of it to change one field.

Next

• Anatomy of a Dacite app — the recipe.
• Install — nbb or JVM.
• First values — five minutes, no service.
• Cookbook — field reads, updates, commit loops.
• Values API when you need a function name.

If you are implementing a hash function or a new store backend, start at Content Stores.

Install

This page is the supported on-ramp for Dacite 0.1 alpha. Read The Dacite way for the stance on data, then come back here to run something.

The library lives in a monorepo under impl/clojure; for alpha we recommend a clone plus either nbb (fastest) or tools.deps with :local/root.

Alpha means: useful for experiments; APIs may still change. Pin a git tag or SHA.

Prerequisites

Clone

git clone https://github.com/jclaggett/dacite.git
cd dacite
# optional: check out a release tag when available
# git checkout v0.1.0-alpha

nbb (Node / SCI)

From the repo root:

npm install
npm run hello          # Hello World
npm run config         # config CLI (file store)
npm run notes          # versioned notes (file store)
npm run log            # event log (file store; seeds 2000 events)
npm run sync           # directory/blob sync
npm run todo:batch     # durable todo list (non-interactive)
npm run todo           # interactive todo UI

Sources are on the nbb path via nbb.edn:

{:paths ["impl/clojure/src" "examples"]}

Ad-hoc scripts:

npx nbb -e "(require '[dacite.store :as store]
                     '[dacite.value :as v])
            (let [st (store/mem-store)
                  vec (v/vector-with-store st 1 2 3)]
              (println (v/count vec))
              (println (store/hash->hex (v/dacite-hash vec))))"

See First values for a guided walkthrough.

JVM (tools.deps)

Point a dependency at the library root impl/clojure after cloning:

;; deps.edn in your project
{:deps {dacite/dacite {:local/root "/absolute/path/to/dacite/impl/clojure"}}}

Then:

(require '[dacite.value :as v]
         '[dacite.store :as store])

(let [st (store/mem-store)
      vec (v/vector-with-store st 1 2 3)]
  [(v/count vec)
   (store/hash->hex (v/dacite-hash vec))])

Git dependency (optional)

If your tools.deps version supports monorepo :deps/root, you can try:

{io.github.jclaggett/dacite
 {:git/tag "v0.1.0-alpha"
  :git/sha "REPLACE_WITH_TAG_SHA"
  :deps/root "impl/clojure"}}

If that fails on your tools.deps version, use clone + :local/root above — that is the reliable alpha path.

From inside impl/clojure you can also run the test suite and service:

cd impl/clojure
clojure -M:dev:test
clojure -M:service --port 8080 --store mem   # API + browser todo static UI

Browser todo demo

cd impl/clojure
clojure -M:cljs-web                    # once / after source changes
clojure -M:service --port 8080 --store mem
# open http://127.0.0.1:8080/app/
clojure -M:cljs-explorer
# open http://127.0.0.1:8080/app/explorer/

Details: examples/web/README.md. Pack GET/POST use wire-v1 binary by default.

Next steps

• The Dacite way — how to think about data
• Anatomy of a Dacite app — Values / Store split
• First values
• Values API / Stores API
• CHANGELOG — alpha scope and known limits

Anatomy of a Dacite app

Every portable example in this repo splits Values from Store. Domain code builds and updates Dacite values. Wiring opens a store and commits a root. The two meet at a root-ref.

Copy this shape. Do not start from a single namespace that both assocs fields and chooses a file path.

Public API only

Application code may require:

(require '[dacite.value :as v]
         '[dacite.store :as store])

If a domain function needs dacite.value.collections, dacite.store.pack, or dac->clj, that is a library hole. Promote a function on dacite.value (or wrap the store) in the same change. See The Dacite way.

1. Domain functions take and return values

New nodes are allocated relative to a peer that already has a store — another value, a root-ref, or an IStore:

(defn add-todo [todos title]
  (v/conj todos (v/hash-map-via todos "title" title "done" false)))

hash-map-via / vector-via / string-via / i64-via persist into the peer’s store. You do not thread the store through every call.

Reads name a field, not the whole tree:

(v/as-str (v/get todo "title"))
(boolean (v/native (v/get todo "done")))

2. Bootstrap once

The first allocation needs an explicit store. After that, *-via is enough.

At a REPL (nbb or JVM):

(require '[dacite.store :as store]
         '[dacite.value :as v])

(def st (store/mem-store))
(def doc (v/hash-map-via st
                         "title" (v/string-via st "Hello")
                         "done" false))

(v/as-str (v/get doc "title"))
;; => "Hello"

(store/hash->hex (v/dacite-hash doc))

Bare constructors such as (v/vector 1 2 3) use the dynamic store/*store* (a mem store by default). Prefer *-via / *-with-store in real programs so the store is obvious.

3. One rooted store, one root-ref

The store keeps a mutable hash. Wrap it once for value-level ops:

(def rs (store/rooted-store st))
(def r (v/root-ref rs))

(v/ref-cas! r nil doc)          ; seed empty root (works locally and remote)
(v/ref-swap! r add-todo "milk") ; CAS-retry
(v/ref-deref r)                 ; current Dacite value, or nil

Local single-writer apps may ref-reset! after each edit. Anything that might race (HTTP, two processes) uses ref-swap! or ref-cas!.

4. Store section is a different concern

Open mem, file, LMDB, or HTTP without mentioning the domain type:

;; local durable
(store/rooted-store (store/file-store "target/my-app"))

;; HTTP (JVM); write-back is the usual client policy
(store/remote-rooted-store "http://127.0.0.1:8080")

The domain namespace should still compile if you swap file for HTTP. Config and notes already do this with a --url flag.

On write-back HTTP, s-put stays in local memory until commit. Flush packs literals and POST /nodes, then POST /root/cas. Domain code does not call flush-from! or import pack. remote-cas-root! / ref-swap! on a write-back store do that underneath.

5. The whole loop

(open-store …)           ; Store section
(def r (v/root-ref rs))  ; Value section
(load-or-seed! r)
(v/ref-swap! r domain-op …)

load-or-seed! is ref-deref or, if empty, build a value via the ref and ref-cas! from nil (remote) / ref-reset! (local).

That is the architecture in todo.cljc, config.cljc, and the other portable examples.

Next

• First values — constructors and hashes, no root.
• Persist and update a document — nested map, file or HTTP.
• Values API / Stores API.

First values

You want a small vector and a map, their sizes, and a stable identity — without a file or a server. Build them as Dacite values. Count, get, and the content hash are the whole API you need here.

Five minutes. nbb only; no JVM.

Prerequisites

• Node.js 18+
• A clone of the dacite repository

git clone https://github.com/jclaggett/dacite.git
cd dacite
npm install

Run the example

npm run hello

Expected shape of the output:

Dacite Hello World
  vector count : 3
  vector hash  : 58a4799b…
  map count    : 2
  map hash     : 5de2bb0c…
  (get m "hello") realized: 42
Done.

The exact hashes are stable across hosts (JVM, babashka, nbb) for the same value structure — that is part of the Dacite porting contract.

What the code does

Source: examples/dacite/examples/hello.cljs.

1. Create a mem store — an in-memory hash → node dictionary.

   (def st (store/mem-store))
   

2. Build values — bootstrap with an explicit store, then *-via for peers:

   (def v (v/vector-with-store st 1 2 3))
   (def m (v/hash-map-via v
                          "hello" (v/i64-via v 42)
                          "vec" v))
   

3. Read with dacite.value — collection ops take the value first:

   (v/count v)              ; => 3
   (v/get m "hello")        ; => Dacite scalar
   (v/realize …)            ; => 42
   

4. Content hash — identity is the hash, independent of store location:

   (store/hash->hex (v/dacite-hash v))
   

Try it in a one-liner

npx nbb -e "
(require '[dacite.store :as store]
         '[dacite.value :as v])
(let [st (store/mem-store)
      vec (v/vector-with-store st 1 2 3)]
  (println (v/count vec))
  (println (store/hash->hex (v/dacite-hash vec))))
"

Next steps

• Anatomy of a Dacite app — add a root and persist
• Persist and update a document — nested map, file or HTTP
• Values API — constructors, *-via, collection ops

Persist and update a document

You have a nested config map. You want to change one field, persist it, and run the same domain against a file or against HTTP. Dacite’s move: get-in / assoc-in / native on values, a root-ref for the snapshot, store wiring in a separate section.

This example is the first claim-proving app in the roadmap: the server publishes a root hash; clients pull only what they need.

You will:

1. Seed and edit config on disk.
2. Point the same commands at clojure -M:service.
3. Watch a second process pick up a new root.

Prerequisites

• A clone of this repo (see Install)
• JDK 17+ and the Clojure CLI for the service and --url client
• Optional: Node.js 18+ (npm run config) or babashka (bb config) for the file store

The shape

Config is a Dacite map:

{"theme" "dark", "timeout" 30, "features" ["a" "b"]}

Domain code lives in dacite.examples.config and uses only dacite.value — get-in / assoc-in / native / as-str / root-ref. It never calls dac->clj. Store wiring (file path vs HTTP URL) is a separate section of the same namespace.

Local file

From the repo root:

cd impl/clojure
clojure -M:config -- --reset show

Or from the repo root with nbb / babashka (file store only):

npm run config -- --reset show
bb config --reset show

Expected shape:

seeded new store at target/dacite-config
theme:    dark
timeout:  30
features: a, b
root:     <64 hex chars>

Edit without leaving the value API:

clojure -M:config -- set timeout 60
clojure -M:config -- set theme light
clojure -M:config -- add-feature telemetry
clojure -M:config -- get features.0

--path DIR selects the store directory (content shards + a ROOT file). A second invocation without --reset reopens the same root.

Same commands against the service

Terminal 1 — start the HTTP content store:

cd impl/clojure
clojure -M:service --port 8080 --store mem

Terminal 2 — the same CLI, --url instead of --path:

cd impl/clojure
clojure -M:config -- --url http://127.0.0.1:8080 show
clojure -M:config -- --url http://127.0.0.1:8080 set timeout 90

store/remote-rooted-store implements the same root protocol as a local rooted store, so v/root-ref, v/ref-swap!, and v/ref-cas! work unchanged. v/ref-reset! is local-only and throws on a remote store; the app seeds with compare-and-set from nil.

A second process sees the new root

Terminal 3:

cd impl/clojure
clojure -M:config -- --url http://127.0.0.1:8080 watch

Back in terminal 2:

clojure -M:config -- --url http://127.0.0.1:8080 set theme solarized

watch polls GET /root twice a second and reprints when the hash moves. (Push watches come later, when a two-client live app needs them.)

The two clients share one content-addressed tree. After an edit they print the same root hash. That is the claim this app is here to prove.

Open local vs open remote

(require '[dacite.store :as store]
         '[dacite.value :as v]
         '[dacite.examples.config :as cfg])

;; local
(def r (v/root-ref (cfg/open-file "target/dacite-config")))

;; remote (JVM)
(def r (v/root-ref (store/remote-rooted-store "http://127.0.0.1:8080")))

(cfg/load-or-seed! r)
(v/ref-swap! r cfg/set-path ["timeout"] 60)
(cfg/timeout (v/ref-deref r))
;; => 60

One domain namespace. Two store wirings.

What this pulled from the library

dac->clj is not on this path. Field access uses native / as-str. Debug printing uses v/pr-str or bounded print-method.

Next

History is free — keep the previous document value; restore by hash.

History is free

You want every edit to remain a complete snapshot, and a title-only change must not rewrite the body. Dacite’s move: keep the previous document value (same hash) in a history vector; restore by installing that value again. Unchanged fields keep their content hash — you do not invent git.

This is the second claim-proving app in the roadmap.

You will:

1. Seed a note with a long body.
2. Change only the title and see the body hash stay put.
3. Restore an older snapshot by installing the same value again.

Prerequisites

• A clone of this repo (see Install)
• JDK 17+ and the Clojure CLI, or Node.js 18+ / babashka for the file store

The shape

The root is a notebook, not a bare document:

{"doc"     {"title" "…" "body" "…" "tags" […] "edited-at" n}
 "history" [previous-doc …]}

history is newest-previous first. A restore reuses a historical doc value — same hash, no rewrite. The library does not invent git; the app shows the recipe.

Domain code lives in dacite.examples.notes and uses only dacite.value. Bodies print with v/pr-str so a long string is not dumped into RAM.

Local file

cd impl/clojure
clojure -M:notes -- --reset show

Or from the repo root:

npm run notes -- --reset show
bb notes --reset show

Expected shape:

seeded new store at target/dacite-notes
title:      Welcome
edited-at:  0
tags:       intro
body:       "Dacite notes keep every snapshot…" (n chars)
doc:        <12 hex chars>
history:    0 previous
root:       <64 hex chars>

Edit, list, diff, restore:

clojure -M:notes -- set title Hello
clojure -M:notes -- add-tag demo
clojure -M:notes -- list
clojure -M:notes -- diff 0 1
clojure -M:notes -- restore 1

Version 0 is current, 1 is the previous snapshot, and so on. diff compares field hashes — a title-only edit reports title and edited-at, not body.

--path DIR selects the store directory. The same --url recipe as Persist and update a document works if the HTTP service is running.

Sharing bench

clojure -M:notes -- bench

Typical output:

sharing bench
  title-only:   +N nodes
  body-rewrite: +M nodes
  body shared after title edit: true

M is larger than N because the seed body is a real paragraph. The title-only path allocates a new title string, a new doc map, and a history conj. The body node is the same hash.

What this pulled

No dac->clj. History is a vector of documents in the same store.

Next

Large sequences stay cheap — page with subvec; do not seq the whole log.

Large sequences stay cheap

You have thousands of events. You need a page of them and a derived balance, not the whole log in RAM. Dacite’s move: v/subvec and nth on a vector; append is conj. Do not seq the log to print page 0.

This is the third claim-proving app in the roadmap.

You will:

1. Seed 2000 events (not five).
2. Page the log with v/subvec — no seq of the whole vector.
3. Replay the view from a prefix via nth.
4. See that one more append adds a handful of nodes at n=100 and at n=2000.

Prerequisites

• A clone of this repo (see Install)
• JDK 17+ and the Clojure CLI, or Node.js 18+ / babashka for the file store

The shape

{"log"  [{"type" "credit"|"debit" "amount" n "note" s} …]
 "view" {"size" n "credits" n "debits" n "balance" n}}

Append updates the view incrementally. Replay rebuilds the view from log[0, end) without walking the tail.

Domain code lives in dacite.examples.event-log and uses only dacite.value. Pagination pulled v/subvec.

Local file

cd impl/clojure
clojure -M:log -- --reset show

Or from the repo root (file store; seeding 2000 events takes a few seconds):

npm run log -- --reset show
bb log --reset show

--n 200 seeds a smaller log. Expected shape:

seeded new store at target/dacite-log (2000 events)
size:     2000
credits:  …
debits:   …
balance:  …
log:      2000 events
root:     <64 hex chars>

Page, append, replay:

clojure -M:log -- page 0
clojure -M:log -- page 3 10
clojure -M:log -- append credit 5 coffee
clojure -M:log -- replay 100

page prints a window and its content hash. replay 100 replaces the view with a fold of the first 100 events.

The same --url recipe as Persist and update a document works against clojure -M:service.

Append bench

clojure -M:log -- bench

Typical output:

append bench (nodes added by the last conj at each size)
  n=100   +N nodes
  n=500   +N nodes
  n=1000  +N nodes
  n=2000  +N nodes

The deltas stay small. They must not grow linearly with n — that would mean each append rewrote the log.

A prefix slice has the same hash as a log built from those events alone (hash fusion is shape-independent).

What this pulled

dac->clj is not on this path. Missing-node errors stay on the shelf until a remote page actually needs a catchable “not local” signal.

Next

Two writers, one CAS — ref-swap! retries; SSE watches the root.

Two writers, one CAS

Two processes must append without silent clobbering. Dacite’s move: compare-and-set is the whole distributed update. ref-swap! retries on conflict; SSE (GET /events) tells a third process the root moved. There is no lock and no CRDT in the core.

Two writers append to the event log on one HTTP root. This is the fourth claim-proving app in the roadmap.

You will:

1. Start clojure -M:service.
2. Append from two terminals without lost events.
3. Watch the root change without polling GET /root yourself.

Prerequisites

• JDK 17+ and the Clojure CLI
• The event-log app from the previous tutorial

Terminal 1 — the service

cd impl/clojure
clojure -M:service --port 8080 --store mem

Terminal 2 and 3 — two writers

cd impl/clojure
clojure -M:log -- --url http://127.0.0.1:8080 --n 0 append credit 1 from-a

cd impl/clojure
clojure -M:log -- --url http://127.0.0.1:8080 append debit 1 from-b

Each append uses v/ref-swap-info!: read the current ledger, conj, CAS the new root. If the other writer landed first, CAS fails, the fn runs again on the new ledger, and both events stay in the log. When a retry happened the CLI prints cas retried N time(s).

To force collisions:

clojure -M:log -- --url http://127.0.0.1:8080 contend 10

Two remote clients each append 10 events. The final size is start+20. cas-retries is how many times a writer rebuilt on a newer root.

Terminal 4 — watch

clojure -M:log -- --url http://127.0.0.1:8080 watch

This is GET /events (SSE), not a sleep-and-poll loop. The first frame is the current root; later frames fire after a successful CAS. Append in another terminal and this one reprints.

What this pulled

Async browser networking stayed on the shelf. Two JVM remotes plus an SSE watch prove the claim; sync XHR is still the browser demo.

Next

Sync a tree of blobs — list metadata; fetch one file.

Sync a tree of blobs

You have a folder of files. Listing it must not load every body; fetching one file must not pull its siblings; a second copy should send nothing already present. Dacite’s move: a tree of maps + blobs; ls reads kind and size; cat is v/as-bytes on one blob; sync-reachable! copies missing nodes.

This is a claim-proving app in the roadmap.

You will:

1. Seed a sample tree (two files share a blob).
2. ls names and sizes without reading file bytes.
3. cat one file.
4. Push the tree to clojure -M:service and pull it elsewhere.

Prerequisites

• JDK 17+ and the Clojure CLI, or Node.js / babashka for the file store

The shape

{"kind" "dir"
 "entries" {"readme.txt" {"kind" "file" "size" 13 "blob" <blob>}
            "copy.txt"   {"kind" "file" "size" 13 "blob" <same blob>}
            "sub"        {"kind" "dir"  "entries" {…}}}}

ls reads kind and size only. cat calls v/as-bytes on one blob. Identical contents share one blob hash.

Local

cd impl/clojure
clojure -M:sync -- --reset seed
clojure -M:sync -- ls
clojure -M:sync -- ls sub
clojure -M:sync -- cat readme.txt
clojure -M:sync -- bench

Or npm run sync -- --reset seed / bb sync --reset seed.

put /path/to/dir ingests a real host folder. export DIR writes the tree back to disk.

Push and pull

# terminal 1
clojure -M:service --port 8080 --store mem

# terminal 2 — publish the local tree
clojure -M:sync -- --url http://127.0.0.1:8080 push

# terminal 3 — another store
clojure -M:sync -- --path /tmp/dacite-sync-b --url http://127.0.0.1:8080 pull
clojure -M:sync -- --path /tmp/dacite-sync-b ls

store/sync-reachable! copies the subgraph (packed flush to a remote, per-node copy otherwise). Then the dest root is CAS’d to the same hash. A second pull copies nothing already present.

What the bench shows

sync bench
  names:        data.bin, readme.txt, sub, copy.txt
  shared blob:  true
  store nodes:  1992
  readme:       13 B
  data.bin:     256 B

The sample root hash is the same on JVM, babashka, and nbb:

fe0532ab564af43a7fb7c94541eaf63d63fa70d24e1290e6899747a571f4f196

A remote test measures store-protocol bytes: GET of one blob transfers less than GET of that blob plus its siblings. A second local sync-reachable! copies 0 nodes.

What this pulled

Opaque-byte store entries stayed on the shelf — EDN file nodes are enough to prove the fetch claim. A later port can store raw bytes without changing the app.

Next

Browse without dumping — walk the root as typed values. A browser app — todo and explorer on HTTP.

Browse without dumping

You want to see the current root as typed values, expand a collection, and not download the whole tree. Dacite’s move: walk with value-type, count, nth, paged seq; never dac->clj. HTTP GET /node returns a packed neighborhood; the UI then walks values locally.

This is the sixth claim-proving app in the roadmap.

You will:

1. Open /app/explorer/ against clojure -M:service.
2. See every public Dacite type as type + value (not a JSON/EDN dump).
3. Expand vectors, maps, and sets; page long collections 32 at a time.
4. Measure that the first page of a 128-element vector costs less than seq of the whole vector.

Prerequisites

• JDK 17+ and the Clojure CLI
• A clone of this repo (see Install)

The shape

The explorer does not invent a domain. It displays whatever is at the server root. If the root is empty, it CAS-seeds a type gallery — a map that includes every public type, plus "page-me" (128 small maps) so paging is forced. An existing root (notes, event log, sync, todo) is left alone.

Domain code lives in dacite.examples.explorer and uses only dacite.value: value-type, count, nth, paged seq, lazy realize prefixes for strings/blobs. It never calls dac->clj.

The browser store is the same as the todo demo: write-back cache plus default pack-filled GET /node. One request returns data — realized literals for a neighborhood under the asked hash, inside the ~1k soft budget. apply-chunk! installs those as ordinary nodes in the tab’s mem cache. The explorer then walks values locally (dacite.value); a tree click is not a GET.

A 5-item todo list fits in a single literal, so load + expand of the first item is one node GET after GET /root. A title longer than 1k still takes several GETs, but each GET BFS-fills ~1k of neighborhood (last item may overshoot toward 2k). A refresh starts a new heap, so that cache is empty again.

String/blob rows still realize a short prefix of char/byte nodes; after a string literal those nodes are already local.

Strings and blobs are leaves: a truncated preview and the total count. A later “read more” can lengthen that prefix; this first pass does not.

Run

cd impl/clojure
clojure -M:cljs-explorer          # once / after cljs changes
clojure -M:service --port 8080 --store mem
# open http://127.0.0.1:8080/app/explorer/   (trailing slash)

Todo stays at http://127.0.0.1:8080/app/.

Reload re-fetches GET /root. It does not watch GET /events.

What to look at

• Each row is a type badge then a summary (i64 -64, vector 3, string "prefix…" (n chars), blob n bytes 0x…).
• Maps show typed keys as well as values (the gallery includes a vector key).
• "page-me" is 128 entries; the first expand shows 32, then show next 32.
• The bw line is store-protocol bodies only (GET /node, GET /root, CAS) — the same meter as the todo demo.

Existing data

Point the service at a store you already seeded:

cd impl/clojure
clojure -M:log -- --reset show          # 2000 events in target/dacite-log
clojure -M:service --port 8080 --store file:target/dacite-log
# open /app/explorer/ — the ledger, not the gallery

The explorer must not overwrite that root.

Measure

cd impl/clojure
clojure -M:dev:test -n dacite.examples.explorer-test

remote-expand-page-cheaper-than-full-seq seeds the gallery over HTTP, then compares a cold client’s first child-page of "page-me" with seq of all 128. Page bytes and requests stay strictly below the full walk.

Related

• A browser app — todo + explorer on one service
• Values API
• Anatomy of a Dacite app

A browser app

The Values / Store split still holds in the tab. Domain code is dacite.value. The store is HTTP plus a write-back cache. The UI is DOM (todo) or a typed tree (explorer). Neither app dumps the root to JSON.

Run

cd impl/clojure
clojure -M:cljs-web                  # todo bundle (first time / after cljs)
clojure -M:cljs-explorer             # explorer bundle
clojure -M:service --port 8080 --store mem

Use a trailing slash. Hard-refresh after rebuilding JS (main.js?v=… cache-busts when we bump it).

Durable service: --store file or --store lmdb. Details: examples/web/README.md.

What the browser is doing

1. GET /root — current hash, or none.
2. Domain ops (add-todo, expand a node) run on Dacite values in memory.
3. GET /node/{hex} — one pack-filled chunk (literals under the hash, ~1k soft budget). The client applies the chunk, then reads the value. A tree click is not a GET if that neighborhood is already local.
4. Commit: write-back flush POST /nodes (same Layer 1 literals as GET), then POST /root/cas.

Todo CLI uses v/root-ref on a file store. The browser todo still coordinates hashes at the CAS layer in places — a library hole, not a reason to invent a JS model. Explorer is read-only on whatever root the service already has (todo, notes, the type gallery).

Sync XHR keeps IStore blocking so value ops stay synchronous. That is demo-only; an async remote is deferred until an app pulls it.

Next

• Browse without dumping — paging and pack GET.
• Anatomy of a Dacite app — the same recipe as the CLI.
• The Dacite way

Read without dumping

Name the piece you need. Do not convert the value to a host map “so the rest of the program can use it.”

native and as-str take an optional char limit (or v/*string-char-limit*). They throw if a string is longer than the limit — that is the point: field-sized text, not a 3k title dumped into RAM. pr-str never throws; long strings print as "prefix…" (n chars).

realize on a scalar is a host atom. realize on a collection is a lazy seq of realized elements. (into [] (v/realize big-vector)) is an explicit full traversal. Prefer subvec / nth / seq.

Missing blobs from as-bytes throw ex-info with :dacite/missing. Other missing nodes still surface as store exceptions — a library hole until an app pulls a uniform error.

See config (as-str / native / get-in), event log (subvec / nth), sync (as-bytes).

Update and share identity

Updates return new values. The old value is still in the store. Unchanged children keep their hashes.

(def v2 (v/conj todos (v/hash-map-via todos "title" "milk" "done" false)))
(v/dacite-hash todos)   ; unchanged
(v/dacite-hash v2)      ; new root of the vector

Nested documents:

(v/assoc-in config ["features" 0] "c")
(v/update config "timeout" (fn [n] (v/i64-via config (inc (v/native n)))))

assoc-in creates intermediate maps as needed. Path ops were pulled by the config app; use them instead of a hand-rolled walk.

Print hashes when you need to see sharing:

(store/hash->hex (v/dacite-hash (v/get doc "body")))

A title-only edit in notes leaves that body hash put and adds fewer store nodes than rewriting the body. History is another vector of document values: restore means assoc the notebook’s "doc" back to a historical value (same hash), not replaying a diff.

New nodes go into the peer’s store via *-via / conj / assoc. You do not call s-put from domain code.

Commit loops

The store’s mutable cell is a hash. Wrap it once:

(def r (v/root-ref rs))

ref-reset! throws on a remote store. Seeding:

(or (v/ref-deref r)
    (let [seed (v/hash-map-via r "theme" "dark")]
      (v/ref-cas! r nil seed)
      seed))

ref-swap! is read → apply f → CAS. If another writer landed first, f runs again on the new current value. Domain functions must be retries-safe: compute the next value from the argument, do not close over a stale copy.

(v/ref-swap! r add-todo "milk")
;; add-todo is (fn [todos title] (v/conj todos …))

Two HTTP clients appending an event log use this loop; :retries is the UX when they collide. See Two writers, one CAS.

On write-back HTTP, ref-swap! / remote CAS flushes packed nodes, then CAS the root. Domain code does not call flush-from!.

Same domain, local or HTTP

Point one namespace at a file store or at the HTTP service. Domain functions do not change.

;; file
(store/rooted-store (store/file-store "target/dacite-config"))

;; HTTP (JVM default policy is write-back)
(store/remote-rooted-store "http://127.0.0.1:8080")

Config, notes, event log, and sync all take --url. Example:

cd impl/clojure
clojure -M:service --port 8080 --store mem     # terminal 1
clojure -M:config -- --url http://127.0.0.1:8080 --reset show
clojure -M:config -- --url http://127.0.0.1:8080 set timeout 60

A second process shows the same root hash. Clients pull nodes they lack; they do not download a serialized view of the whole map.

Write-back: s-put is local until commit. Flush is POST /nodes (Layer 1 literals, same as pack GET), then POST /root/cas. The domain still requires only dacite.value + dacite.store.

nbb and babashka use the file store (npm run config, bb config). HTTP clients in those examples are the JVM --url path today.

See Persist and update a document and Anatomy.

What not to do

These habits fight the Dacite way. If you need them, name the why and add a bounded utility on dacite.value instead.

Dump the tree

Do not call dac->clj / clj->dac in application code. Do not (into {} …) / (into [] (v/realize v)) to “get a Clojure value.” That assumes the tree fits in RAM and is fully local. dac->clj stays on the JVM as a test hatch.

Read a field (native / as-str), a page (subvec), or a blob (as-bytes).

Host collections as the domain

Do not keep a Clojure map of todos and convert it at the edges. Build Dacite maps and vectors from the start (hash-map-via, conj). Cards’ shuffle still dumps to a host vector — that is a hole, not a pattern.

Twenty-line field readers

Do not write title-str that walks nodes by hand. v/as-str / v/native exist because config needed them. If a new read is twenty lines, promote it in the same change.

Leak internals

Domain code must not require:

• dacite.value.collections / .finger-tree / .hamt
• dacite.store.pack
• dacite.wire / dacite.wire.binary

If you need them, the public API is missing a function.

Bare PUT /node in a write-back app

Write-back clients flush packed chunks on commit. Per-node PUT is the unwrapped-remote path. Mixing them in one app usually means the domain started threading hashes.

Unconditional remote reset

ref-reset! is local-only. On HTTP, seed with ref-cas! from nil and update with ref-swap!.

Query-string pack opt-outs

GET /node/{hex} is always a pack-filled chunk. There is no ?raw=, ?nodes=, or ?near=. For a single item in process, pack-under with budget 0 — that is not an application API.

Values API reference (0.1 alpha)

Practical API for Dacite values as implemented in the Clojure / SCI reference library. For how to use values, start at The Dacite way and the cookbook. Internals: Values.

Public namespace: dacite.value (pair with dacite.store for stores).

What is a Dacite value?

A value is store-aware and content-addressed:

Values are immutable. Updates return new values that share unchanged nodes with the old ones. Laziness is natural: you only need the nodes you access.

(require '[dacite.value :as v]
         '[dacite.store :as store])

Constructors

Relative (*-via) — preferred in domain code

Use an existing Dacite value, a root-ref, or an IStore as the peer:

(defn add-todo [todos title]
  (v/conj todos (v/hash-map-via todos "title" title "done" false)))

Bootstrap (*-with-store)

When there is no peer yet (first allocation):

(v/vector-with-store st 1 2 3)
(v/i64-with-store st 42)

REPL convenience

Bare constructors use the dynamic store/*store* (default mem store):

(v/vector 1 2 3)
(v/hash-map :a 1)
(store/with-store [_ (store/mem-store)]
  (v/vector 1 2 3))

Root reference (value-level)

The store layer keeps a mutable hash. Wrap it once for value-level ops:

(def rooted (store/rooted-store (store/mem-store)))
(def r (v/root-ref rooted))

(v/ref-reset! r (v/vector-via r))
(v/ref-swap! r v/conj (v/i64-via r 1))
(v/ref-deref r)   ; => current Dacite value or nil

On the JVM, RootRef also implements atom interfaces:

@r
(swap! r v/conj 2)
(reset! r (v/hash-map-via r "k" "v"))
(add-watch r :ui (fn [k ref old new] …))   ; old/new are values

Portable function API (nbb / babashka / all hosts):

Collection API

First argument is always a Dacite value:

Example:

(let [st (store/mem-store)
      vec (v/vector-with-store st 10 20 30)
      v2  (v/conj vec 40)]
  [(v/count vec) (v/count v2)
   (v/realize (v/nth v2 3))])
;; => [3 4 40]

Identity and hashing

• Two values with the same type and content have the same hash on every host (see bin/hash-parity.sh).
• Print / log hashes with (store/hash->hex h) and parse with (store/hex->hash s).

Not part of the public value API

Related

• Stores API
• The Dacite way
• Anatomy of a Dacite app
• Cookbook
• Install

Stores API reference (0.1 alpha)

Practical API for content stores and client composition in the reference implementation. App wiring: Anatomy and Same domain, local or HTTP. Internals: Content Stores, Rooted Stores.

IStore protocol

Namespace: dacite.store

Hashes are 4-word vectors ([w0 w1 w2 w3]). Helpers:

(store/hash->hex h)
(store/hex->hash "…64 hex chars…")

Dynamic binding:

store/*store*          ; current store
(store/with-store [st (store/mem-store)] …)
(store/set-store! st)
(store/reset-store!)

Built-in stores

Rooted stores

A content store holds immutable nodes. A root cell holds one mutable root hash for application state (compare-and-set, watches, GC). Hash-level ops are re-exported on dacite.store:

Application value code should wrap the rooted store once and work with values, not hashes:

;; local file
(def r (v/root-ref (store/rooted-store (store/file-store path)
                                       (store/file-root-cell path))))

;; same value API over HTTP (JVM)
(def r (v/root-ref (store/remote-rooted-store "http://127.0.0.1:8080")))

(v/ref-swap! r domain-update)

set-root! / ref-reset! throw on a remote rooted store. Seed with ref-cas! from nil; update with ref-swap!.

See Values — root reference and Rooted Stores chapter.

Host ctors on dacite.store (JVM): (store/file-store path), (store/lmdb-store path), (store/lmdb-root-cell lmdb). On nbb, use (dacite.store.nbb/file-store path) (SCI cannot re-export circular host backends cleanly). Optional nbb LMDB (same data.mdb layout as JVM, wire-v1 nodes): (dacite.store.nbb.lmdb/lmdb-store path) after LMDB_DATA_V1=true npm rebuild lmdb (prebuilt lmdb is format v2 and will not open a lmdbjava env).

Client composition (remote / sync)

Interactive clients usually stack:

application Values
    ↓
write-back cache     (dacite.store.client-cache/wrap … :write-back)
    ↓
pack / chunk transport   (IChunkTransport + pack/flush-from!)
    ↓
optional rate-limit      (dacite.store.rate-limit)
    ↓
remote HTTP store        (dacite.store.remote | dacite.store.browser)

pack/flush-from! finds the outermost IChunkTransport and sends budgeted chunks (default soft budget 1024 bytes).

Wire: EDN vs wire-v1

• Spec: wire-v1 (repo) / book Serialization appendix
• Codec: dacite.wire.binary (portable .cljc — JVM + CLJS/nbb)
• EDN helpers: dacite.wire (read-edn / write-edn)
• Opt out: {:binary false} on remote/browser store constructors

Service dual-stack: dacite.service honors Content-Type / Accept.

Alpha quality notes

• HTTP service and remotes are experimental but usable for demos and tests
• Browser remote is sync XHR (main-thread blocking) — not production networking
• APIs may change before 1.0; see CHANGELOG

Related

• Values API
• HTTP service
• Anatomy of a Dacite app
• Install

HTTP service

Production endpoints for a dedicated content store plus one root. Full design: service.md.

The demo server: clojure -M:service --port 8080 --store mem (or file / lmdb).

Pack GET/POST prefer application/vnd.dacite.chunk.v1 (wire-v1). Root CAS and novelty stay EDN.

Write-back clients: GET /node on miss, POST /nodes on flush, then POST /root/cas. They do not PUT every node.

No query opt-outs on GET (?raw=, ?nodes=, ?near= are gone).

Throttle: empty bucket is 429 (Retry-After); oversized body is 413. remote-store retries 429/503. See service.md inbound throttle.

Static demos: /app/ (todo), /app/explorer/ (trailing slash).

Chapter 1: Content Stores

Writing an application? Start at The Dacite way and Anatomy. This chapter is how a store is built.

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

Writing an application? Start at The Dacite way. This chapter is how content hashes are formed.

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

Writing an application? The public API is Values; the stance is The Dacite way. This chapter is the representation (finger trees, HAMTs, typing).

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

There is no ft/single adapter. A one-element sequence uses the leaf value hash as the tree root. Digit and node children are either bare leaf hashes (scalars or public collection nodes such as vector) or structural ft/node hashes on the spine. Discrimination: non-ft/* means implicit single; ft/* means structure. Nested collections must be wrapped in a public collection node — never a bare ft/deep as a user value.

Every structural 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 structural 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

Writing an application? Use root-ref / ref-swap! — see Commit loops. This chapter is the rooted-store contract (CAS, watches, GC).

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.

Pack transport

Packing is wire-only. Durable values stay finger trees and HAMTs. Domain code does not import dacite.store.pack.

A chunk is a budgeted list of items. Each item is either:

• :literal — complete realized content at that hash (the receiver materializes through normal constructors; hash must match)
• :node — the stored cell, children fetched later

Layer 1 (encode-item) prefers a literal when cached size-bytes is ≤ the budget (default 1024) and a dry-run hash matches. Sequence bodies collapse contiguous same-type leaves to nested run / repeat. Layer 2 seals on sent bytes (wire-v1 by default). The item that crosses 1024 is kept (~2× possible). Budget 0 is a single item (the asked hash).

Where it runs

There is no ?raw=, ?nodes=, or ?near= query opt-out. GET always returns a pack chunk.

Implementors: leaf-chunking.md, wire-v1.md. Application authors can stop here.

Appendix: Serialization

Status: LEGACY reference. Multi-language interop and new work use wire format v1 (chunk-only binary). dacite.value.serial remains directionally related but is not the port contract.

This appendix describes the historical binary layout used in early Clojure work. 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.