Anatomy of state — DAG, tree & storage

This page answers, with diagrams, the six “what does it actually look like” questions: the DAG vs the state, how the CRDT data is stored, what the Merkle tree looks like, how it merges, how state is produced, and how governance is stored next to it.

We use one running example throughout — a tiny chat app:

#[app::state]
struct Chat {
    msgs: UnorderedMap<String, Message>, // message_id -> message
}

1. The DAG vs the state

Two structures hold everything, and keeping them straight is the whole mental model. The operation DAG is the signed, append-only history. The state is the materialized fold of that history — an entity tree with a root_hash.

▶ Replay

• The DAG is the source of truth and the authority: every change is a signed, content-addressed operation pointing at its causal parents. You keep it.
• The state is a cache of the DAG — derived, queryable, and rebuildable from scratch by replaying ops. Two nodes that have seen the same ops compute the same state and the same root_hash.

That is why divergence can be detected (compare root_hash) and healed (ship the missing ops) rather than prevented — the DAG is the ground truth, the state just follows from it. See Operations and Projection for the two halves in depth.

2. How the CRDT data is stored

There is no “map” object on disk. Every value is its own entity with a content-derived id, and a collection is just a parent entity whose children are those per-value entities.

▶ Replay

• A map entry id is SHA-256(parent_id ‖ "__calimero_entry__" ‖ key); a nested collection id is SHA-256(parent_id ‖ "__calimero_collection__" ‖ field_name). The two domain separators mean a key "X" and a sub-collection named "X" never collide.
• Because ids are derived from content, every node computes the same id for the same key — no coordination, no auto-increment.
• Entities persist in the RocksDB State column family, keyed context_id ‖ entity_id. Nested collections (a Vector inside a map value, say) recurse the exact same way.
• Private data (#[app::private]) lives in a separate PrivateState column — node-local, never synced, and outside the Merkle root entirely. See Access-controlled storage for the typed wrappers.

3. The Merkle tree in memory

Those entities form a tree, and each carries two hashes: its own_hash (over its own value) and its full_hash (its own hash rolled up with its children’s).

The roll-up is the one formula to remember:

full_hash(node) = SHA-256( own_hash ‖ each child.full_hash, sorted by (created_at, id) )

The tree’s root full_hash is the storage root_hash that goes on the wire. Because each node only references its direct children’s hashes, editing one leaf re-hashes only its ancestor chain — O(depth), not the whole tree. (See Storage performance for the cost in full, and CRDT internals for the value-level hashing.)

4. How the tree merges

When a peer’s version of an entity arrives, the trees are reconciled per entity, by id — never as opaque blobs.

• For a given entity, the winner is last-writer-wins by HLC, with the content hash as a deterministic tiebreak when timestamps are equal.
• Children are an add-wins union; removals are tombstones (so a delete and a concurrent re-add resolve deterministically rather than racing).
• Every step is commutative and order-independent, so the merge is a pure function of the set of entities seen — every node lands on the same tree and the same root hash, regardless of arrival order.

5. How the state is produced

The same materialized tree is produced two ways, and they must agree:

▶ Replay

• Local execution: a WASM method runs, emits storage actions (Put/Delete), apply_action writes the entities and walks the Merkle hashes up to a new root_hash, then the node commits to the State column, appends the op to the DAG, and broadcasts the delta. (See The write path.)
• Receiving: a peer’s delta folds through the same apply_action, producing the same entities and the same root_hash. (See The receive & apply path.)

“State in memory,” then, is exactly this entity tree materialized from the State column — there is no separate in-RAM representation to keep in sync.

6. Governance vs state in the store

Governance (who is a member, what they can do) and application state (the chat messages) live side by side but never mixed — different column families, different keys, different merge rules.

▶ Replay

• State holds the app’s CRDT entity tree (this whole page so far).
• Group holds governance as prefix-partitioned records (GroupMeta 0x20, GroupMember 0x21, MemberCapability 0x26, GroupOpLog 0x30, …) — its own signed op log, not a CRDT tree.
• Meta holds the per-context root_hash, dag_heads, and bound application; UnifiedOp/Delta hold the op DAG; PrivateState and SortedIndex are node-local and never sync.
• Both the state root and the governance state fold into the single scope_root a peer compares during sync — so a node detects “we disagree on the data” and “we disagree on membership” through the same hash check. See Governance and the Storage schema.

Content addressing: every id is derived, not assigned

The entity ids in section 2 are one instance of a principle that runs through the whole system: ids are computed from content, never handed out by a coordinator. There is no allocator, no auto-increment, no central registry — an id is a hash of the thing it names.

Id	Derived from	Where
BlobId	SHA-256(chunk bytes)	Blobs (crates/store/blobs/src/lib.rs)
Map-entry id	SHA-256(parent_id ‖ "__calimero_entry__" ‖ key)	compute_id(parent, key) (crates/storage/src/collections.rs)
Collection id	SHA-256(parent_id ‖ "__calimero_collection__" ‖ field)	compute_collection_id (same file)
Delta id	SHA-256(parents ‖ actions) — HLC deliberately excluded	CausalDelta::compute_id (crates/storage/src/delta.rs)
App / bundle id	hash of the manifest’s package + signerId	Applications

The delta id is the sharpest case: its compute_id takes the HLC but ignores it, hashing only parents and the content-addressable parts of each action. Two nodes that replay the same operations therefore mint the same delta id regardless of physical time, so the DAG has identical node ids everywhere.

That is the payoff of content addressing across the board: because the same bytes always hash to the same id, every node independently computes the same id for the same thing — the convergence in sections 4 and 5 needs no coordination, no agreement round, and no id assignment to fall back on.

Worked example: an org in memory

To make the whole layout concrete, picture one org. Acme owns the namespace acme (its root governance scope, acme 0xa0…). Under it sits a group Engineering (eng 0xe9…), and inside Engineering lives the chat context deploys-chat (ctx 0x7a…) — the same msgs: UnorderedMap<String, Message> app from the top of this page. Alice is an admin at acme; Bob is a member of eng. Each of these is a scope in the same tree, and each lays its records into these column families under its own id. (Hashes and ids below are short illustrative hex, not real digests.)

Governance scopes (namespace + group)

Membership and capabilities never live in the context — they live in the Group column family, keyed by the scope id (the namespace id or group id), each record distinguished by a one-byte prefix. Here is what acme and eng actually hold:

Key (Group CF)	Layout	For our org	Value
GroupMeta	0x20 ‖ group_id	0x20 ‖ acme 0xa0…	namespace meta { admin_identity: Alice, … }
GroupMeta	0x20 ‖ group_id	0x20 ‖ eng 0xe9…	group meta { target_application_id, … }
GroupMember	0x21 ‖ group_id ‖ identity	0x21 ‖ acme 0xa0… ‖ Alice	{ role: Admin, … }
GroupMember	0x21 ‖ group_id ‖ identity	0x21 ‖ eng 0xe9… ‖ Bob	{ role: Member, … }
MemberCapability	0x26 ‖ group_id ‖ identity	0x26 ‖ eng 0xe9… ‖ Bob	{ capabilities: <bitfield> }
GroupOpLog	0x30 ‖ group_id ‖ seq(8 BE)	0x30 ‖ eng 0xe9… ‖ 0…07	Borsh(SignedGroupOp)

A namespace is just a root group, so it carries the same 0x20/0x21/0x26/0x30 records — plus a couple it owns alone: its node-identity keypair under NamespaceIdentity (0x36 ‖ namespace_id) and its governance ops under NamespaceGovOp (0x38 ‖ namespace_id ‖ delta_id). The GroupOpLog sequence is a big-endian u64 so the log sorts in numeric order; every other component is a raw 32-byte id. The point: governance lives in the Group CF, keyed by scope id — read all of eng’s membership with one range scan over 0x21 ‖ eng….

The context scope

deploys-chat adds no governance rows of its own. Its footprint is purely State entities, one Meta record, and its own UnifiedOp DAG — every row keyed by the context id:

So the context’s data is just State / Meta / UnifiedOp rows under ctx 0x7a…, while who may write them — Alice, Bob, and their roles — comes entirely from the Engineering group above it. The context stores no member list.

Every scope has the same uniform shape: its own id + its own records (in these CFs) + its own scope_root. The namespace, the group, and the context differ only in which records they carry, not in how they are laid out — which is exactly why one sync engine reconciles governance and application data alike.

Next steps

• Concepts & Scopes — next we’ll see how this state is organized into scopes.
• CRDT internals — the per-value merge algorithms.
• Storage schema — the exact on-disk key/value layouts.