Skip to content
Calimero Core Calimero Core

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

Section titled “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.

Operation DAG 🔐 op 7c4a sig op b1e9 op c2d8 op 95af append-only · signed · replicated the history & the authority fold / projection DAG → state Materialized state root_hash 3e9c 1f… e1 e2 e3 e4 derived · queryable · rebuildable a cache of the DAG Keep the DAG; recompute the state. The DAG proves how you got here; the state is just where you are now.
  • 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

Section titled “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.

1 · Logical 2 · Entities 3 · Storage — State CF #[app::state] struct App msgs: UnorderedMap< String, Message> stored as root entity App 'msgs' — collection entity id = SHA256(parent ‖ '__calimero_collection__' ‖ 'msgs') entry 'alice' Message value '__calimero_entry__' entry 'bob' Message value '__calimero_entry__' child id = SHA256(parent ‖ '__calimero_entry__' ‖ key) persist context_id ‖ alice_id → Borsh(Message) context_id ‖ bob_id → Borsh(Message) context_id ‖ msgs_coll_id → Borsh(collection meta) key = context_id(32) ‖ entity_id(32) Nested collections recurse the same way (collection-id separator). #[app::private] → PrivateState CF: node-local, never synced, outside the Merkle root. Entity-per-value; ids are content-derived, so every node computes the same id for the same key.
  • 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

Section titled “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 Merkle tree in memory — every entity carries its own_hash and full_hash Id::root() own e1d0…7a full a3f1…9c 4b2c…01 own 9f3a…22 full c810…d4 7e90…aa own 1c44…0e full b6f2…58 aa10…3f own 5d2e…77 full 8c01…b9 bb21…4c own 2f9d…10 full 74e3…6a cc32…5d own 0a8b…c3 full e520…1f dd43…6e own 61f4…88 full 90ab…2d full_hash = SHA256( own_hash ‖ sorted child full_hashes ) children sorted by (created_at, id) · leaf own_hash = SHA256(value) Editing one leaf re-hashes only its ancestor chain — O(depth), not O(tree).

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

Section titled “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.

Merging two divergent trees — one leaf written concurrently on two nodes Tree A root full a3f1…9c aa10…3f 8c01…b9 bb21…4c 33aa…91 write @ HLC T1 ⊕ Tree B root full c4d2…7e aa10…3f 8c01…b9 bb21…4c 7c4e…0d write @ HLC T2 (T2 > T1) = Merged root full f0e1…45 (new) aa10…3f 8c01…b9 bb21…4c 7c4e…0d LWW → T2 wins Merge resolution per-entity · Last-Writer-Wins by HLC (Hybrid Logical Clock), content-hash tiebreak when clocks tie children · add-wins union of child sets deletes · recorded as tombstones Merge is deterministic and order-independent ⇒ every node computes the same root.
  • 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

Section titled “5. How the state is produced”

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

Local execute Receive — peer ops WASM method emits Actions (Put/Delete) apply_action writes entities recompute Merkle hashes up ancestor chain peer delta fold ops apply_action writes entities same entities · same root_hash materialized state (entity tree) + root_hash then → commit → State CF append op → DAG broadcast delta State is a deterministic projection — produced identically by local execution or by folding a peer's ops.
  • 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

Section titled “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.

Replicated — synced across every member Meta ContextMeta · root_hash · dag_heads · application UnifiedOp / Delta the operation DAG — signed, content-addressed, append-only State application data app CRDT entity tree keyed by entity id merge: per-slot LWW Group governance records — prefix-partitioned GroupMeta 0x20 GroupMember 0x21 MemberCapability 0x26 GroupOpLog 0x30 separate column families · distinct keys & merge rules fold fold scope_root one hash over both Node-local — never synced, never leaves this node PrivateState per-node private values SortedIndex local ordered index Governance and state sit side by side but never mix: distinct column families, distinct merge rules, both folded into the scope root.
  • 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

Section titled “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.

IdDerived fromWhere
BlobIdSHA-256(chunk bytes)Blobs (crates/store/blobs/src/lib.rs)
Map-entry idSHA-256(parent_id ‖ "__calimero_entry__" ‖ key)compute_id(parent, key) (crates/storage/src/collections.rs)
Collection idSHA-256(parent_id ‖ "__calimero_collection__" ‖ field)compute_collection_id (same file)
Delta idSHA-256(parents ‖ actions) — HLC deliberately excludedCausalDelta::compute_id (crates/storage/src/delta.rs)
App / bundle idhash of the manifest’s package + signerIdApplications

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

Section titled “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)

Section titled “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)LayoutFor our orgValue
GroupMeta0x20 ‖ group_id0x20 ‖ acme 0xa0…namespace meta { admin_identity: Alice, … }
GroupMeta0x20 ‖ group_id0x20 ‖ eng 0xe9…group meta { target_application_id, … }
GroupMember0x21 ‖ group_id ‖ identity0x21 ‖ acme 0xa0… ‖ Alice{ role: Admin, … }
GroupMember0x21 ‖ group_id ‖ identity0x21 ‖ eng 0xe9… ‖ Bob{ role: Member, … }
MemberCapability0x26 ‖ group_id ‖ identity0x26 ‖ eng 0xe9… ‖ Bob{ capabilities: <bitfield> }
GroupOpLog0x30 ‖ group_id ‖ seq(8 BE)0x30 ‖ eng 0xe9… ‖ 0…07Borsh(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

Section titled “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:

Engineering group (governance) · eng 0xe9… members & keys come from the group — not stored per-context membership inherited Context scope: deploys-chat (ctx 0x7a…) scope_root 0x6e… — ids & hashes below are illustrative hex Meta CF ContextMeta @ ctx 0x7a… → { application: app 0x3c… root_hash: 0x6e… dag_heads: [op2 0x…] } root_hash = scope_root key = context_id(32) State CF · entity tree ctx 0x7a… ‖ root_id → Chat root entity ctx 0x7a… ‖ msgs_id → collection id via __calimero_collection__ ctx 0x7a… ‖ m1_id → Message{from:alice,"hi"} id via __calimero_entry__ ctx 0x7a… ‖ m2_id → Message{from:bob,"yo"} id via __calimero_entry__ key = context_id(32) ‖ state_key(32) UnifiedOp CF · op DAG ctx 0x7a… ‖ op1 → Borsh(Op) parents:[] parent ctx 0x7a… ‖ op2 → Borsh(Op) parents:[op1] op2 = current DAG head key = scope(32) ‖ op_id(32) scope = the context id A context scope = its ContextMeta + its State entities + its own op DAG. Its membership is inherited from the group above.

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

Section titled “Next steps”