State, Projection & the Root Hash

What projection is

You never query the DAG directly. You query state — the current value of every entity, who may write it, who belongs to the scope. Projection is the act of replaying the operation log to compute that state, plus a single hash that fingerprints it.

A bank balance is the projection of its transaction history. The balance isn’t a fact you trust on its own — it’s recomputed from the list of deposits and withdrawals, and anyone holding the same transactions arrives at the same balance. A Calimero scope works the same way: the DAG of operations is the ledger, the state is what you get by folding that ledger down, and the scope root is a 32-byte fingerprint of the result.

▶ Replay

Everything below unpacks three claims:

• the fold is order-independent — replay the same operations in any order and you land on the same state and the same root;
• the root is a total fingerprint — it covers data and authorization, so no change can move state without moving the root;
• comparing two roots is therefore enough to tell whether two nodes agree.

A worked example: three ops to one root

Start concrete. Take three data-plane operations in one scope. Each entity id is derived from its key, so it is identical on every node (hashes are abbreviated and illustrative):

op1:  Put    entity=0x9a…m1  value="hi"   hlc=1750.000100:#0
op2:  Put    entity=0xb3…m2  value="yo"   hlc=1750.000120:#0
op3:  Delete entity=0x9a…m1               hlc=1750.000150:#0

Step 1 — fold the ops into slots. The projection treats each entity as a slot and keeps, per slot, the stamp of the last operation to write it. op1 and op3 both touch slot 0x9a…m1; op3’s stamp (…150) outranks op1’s (…100), so the delete wins. A late-arriving op1 can’t resurrect the entity — its lower stamp loses.

Slot	Resolved value	Why
0x9a…m1	absent	op3 Delete stamp …150 > op1 Put stamp …100
0xb3…m2	"yo"	only one writer

Step 2 — hash the resolved state. Only m2 survives, so the data hash is taken over that one live entity, in ascending-id order. The two authorization planes are empty here, so each hashes to the empty-input digest:

entities_hash = SHA-256( 0xb3…m2 ‖ u64_le(2) ‖ "yo" )       = 0x1f44…ab
acl_hash      = SHA-256( <no objects> )                      = 0xe3b0…55   (empty plane)
groups_root   = SHA-256( <no governance> )                   = 0xe3b0…55   (empty plane)

scope_root = SHA-256( entities_hash ‖ acl_hash ‖ groups_root ) = 0x8d27…f0

Why two nodes get the same hash. A node that received op3, op1, op2 and a node that received op1, op2, op3 walk different paths, yet they resolve the same slots to the same bytes — because each slot keeps only its highest-stamped write, and a stamp doesn’t depend on arrival order. Same set of ops ⇒ same slots ⇒ same scope_root = 0x8d27…f0. The two nodes are converged, and neither ever had to agree on an order.

The fold, formally

The example’s “highest stamp wins” rule is the whole engine. Formally, the projection is last-writer-wins per slot: every addressable piece of state — an entity, an object’s writer set, a member’s role — is a slot, and applying an operation overwrites a slot only if it carries a higher stamp.

// applying one operation — pure, deterministic, order-independent
fn apply(op):
  for (slot, value) in op.writes():
    stamp = (op.hlc, generation(op), op.id)
    if stamp > clock[slot]:
      state[slot] = value
      clock[slot] = stamp

The stamp is a triple, compared left to right:

• hlc — the hybrid logical clock. It tracks wall-clock time but is nudged forward whenever a higher clock is observed, so it stays causally monotonic: an operation that causally follows another always carries a higher (or equal) hlc.
• generation — the operation’s causal depth in the DAG (1 + max(parent generation), 0 at a root). This breaks ties where hlc alone can’t. Governance operations are authored with hlc = 0, so generation is what orders them — a later structural change always sits deeper in the DAG than the state it supersedes.
• id — the content hash, a final deterministic tiebreaker so two genuinely concurrent writes still resolve the same way on every node.

A Delete records a stamp exactly like a write — which is why the stale re-add in the example above could never win.

This is also where order-independence comes from: because a slot only ever remembers the single highest stamp it has seen, the order operations arrive in can’t change the outcome. Replay the same set in any order — authored, gossiped, or backfilled — and every slot lands on the same value.

The one slot that is not a plain register: joins

A member’s role is a last-writer-wins slot for an add, a role change, a removal and a leave. An invitation join is different, because the node skips a join by an account that already holds a membership row. Folding it as one more write would let a retried join put the invitation’s role back over the role an admin set since.

So a join never overrides a standing membership. It takes effect only when the member is absent, or when the latest of those writes is a removal or a leave with a lower stamp than the join. Among several such joins, the one with the lowest stamp wins, since the later ones were skipped.

join(Member), set role Admin, join(Member)    → Admin
join(Member), join(Admin)                     → Member
join(Member), leave, join(ReadOnly)           → ReadOnly

The third history uses a leave because that is the one the node admits: a member who left comes back on a freshly issued invitation. A member an admin removed does not, since the node refuses its join until an admin adds it again, so no such join reaches the log.

This is still a function of the operation set and its stamps, so it is order-independent like every other slot. “Lowest stamp” means first in causal order only where the stamps carry causal depth, which is the fold at a cut (acl_view_at), the one authorization reads. The streaming fold behind the scope root stamps every operation at depth 0, and governance operations carry no clock, so there it means the lowest operation id: the same on every node and in every arrival order, but not always the join that came first. For two chained joins on different invitations the cut resolves the first one’s role, and the streaming state may hold the second’s. The fold keeps each join that beats the member’s latest such write, so a removal that arrives after the joins on either side of it resolves to the same member as one that arrived between them. It cannot keep them all, since a node publishes a join again on every retry, so per member and group it keeps three things, each a function of the operation set alone:

• the latest 65 joins above the member’s latest add, role change, removal or leave;
• the first join the member ever made, whatever has been written since;
• the least role any of the member’s joins ever carried, with ReadOnly below Member below Admin.

The first join and the least role count every join, including the ones a removal has already spent, and nothing clears them, not even an add with a higher stamp. “The first join above the latest removal” would be the natural thing to keep, but a removal that arrives before the joins and one that arrives after them would then keep different joins, and two nodes holding the same operations would disagree.

While no add stands, the member’s role is:

1. the first join’s, if no removal or leave has a stamp above it, so repeating a join any number of times changes nothing;
2. otherwise the earliest join’s above the latest removal or leave, if at most 64 joins are above it, and no role if none is;
3. otherwise the least role the member ever joined with.

Only the third case can differ from the exact answer, and it applies in exactly one situation, whatever order the operations arrive in: the latest of the member’s adds, role changes, removals and leaves in the group is a removal or a leave, its stamp is above the member’s first join of the group, and more than 64 of the member’s joins of the group have a stamp above it. The least role is never above the role of the join that actually came first after the removal, so this case can lower a member’s authority and never raise it, and the member is present either way. It is exact whenever all of the member’s joins of the group carried the same role, which is what a retried join does. What stays inexact is a member who left, came back on an invitation with a higher role than one it had joined with before, and then repeated that join more than 64 times with no admin write since: it resolves to the lower role. No bounded fold can be exact for every such history, because joins that fold before a leave that may land between any two of them would need every join’s role kept. A TEE attestation admission is not a join in this sense: it folds as a plain write. That is what the node does when the account holds no role or a TEE role, which re-attesting converts. It is not what the node does when the account holds a non-TEE role: the node leaves that role alone, and the projection replaces it with the TEE role.

A namespace leave reaches every subgroup

A member who leaves the namespace root loses its direct row in every subgroup too, because the node deletes those rows when it applies the leave. The projection folds a leave as its own operation, MemberLeft, so it can do the same: a leave of the root is a removal of the member from every group of the scope, at the leave’s stamp.

join root, added to S as Admin, leave root, join root                      → no role in S
join root, added to S as Admin, leave root, join root, join S (ReadOnly)   → ReadOnly in S
join root, join S (Member), leave root, join root, join S (Admin)          → Admin in S

Each (group, member) slot resolves over its own operations plus that one removal, so the result does not depend on the order the leave and the subgroup operations arrive in. An add or a join with a higher stamp than the leave stands, which is how a member comes back. A leave of a subgroup reaches no other group. An admin’s removal of a member from the root is not a leave: the node keeps that member’s subgroup rows, and so does the projection. The one case the projection does not follow is a TEE node removed from the root by an admin, which the node evicts from every subgroup and the projection removes from the root only. Like the join rule, this fold is part of SignedNamespaceOp version 23.

What the projection holds

The fold maintains one set of slots per plane. Together they are the complete materialized state of a scope:

Plane	Slots	Resolved value
Data	entities	the latest value written to each entity (or absent, if deleted)
Access control	acl	the writer set and capability mask for each object
Membership	groups	each group’s members and their roles
Admin	root_admin, policy	the scope’s admin identity and policy bytes
Structure	subgroups	the subgroup tree: parent links and visibility
Capability	default_caps, member_caps	default and per-member capability grants

The data plane is the application’s state; the other planes are the governance planes. They all fold the same way — that is the unification.

The scope root

The whole projection collapses to one 32-byte hash: the concatenation of three plane hashes, each taken over its slots in sorted, deterministic order.

scope_root = SHA-256( entities_root ‖ acl_hash ‖ groups_root )

// each component is a hash over its plane's slots in sorted key order
entities_root = the data-plane root (on the wire, the storage Merkle root — see below)
acl_hash      = H( for each object:  id ‖ writer ‖ capability_mask )
groups_root   = H( memberships ‖ admin ‖ policy ‖ subgroups ‖ caps )

Because every node sorts the same way and hashes the same bytes, equal operation sets give equal roots. The exact byte layout — and the subtlety behind entities_root — is in the specification below.

Why it matters: detecting divergence

Order-independence plus a total fingerprint is what turns “are these two nodes in sync?” into a single comparison.

The root covers authorization, not just data

Equal sets give equal roots — and unequal state gives unequal roots, including state with no data effect at all.

Key property

A change with no data effect still moves the scope root.

Rotate an object’s writers, or remove a member, and the data entities may be byte-for-byte identical — yet because acl_hash and groups_root are folded into the root, the scope root changes. Returning to the worked example: add a fourth op that only rotates a writer set, and the data slots stay identical while acl_hash (and so scope_root) moves. This closes the gap that would otherwise let a silent access-control or membership split-brain hide behind matching application data. Convergence is checked on the whole scope, not just its data.

Convergence is a hash comparison

With an order-independent fold and a single total root, checking whether two nodes agree is trivial: compare scope roots. No agreement on ordering, no quorum, no coordination — just two hashes.

▶ Replay

Equal roots mean the nodes hold the same state and are done. Unequal roots mean one is missing operations the other has — which is exactly the signal the sync engine acts on.

Reading the past: authorization at a cut

The fold above produces the current state. But authorization often needs the state as it was at a particular point in history — specifically, the membership and access-control state an operation’s author had observed when they wrote it.

The projection answers this by folding only the causal cut: the operation’s parents and everything those parents transitively descend from, and nothing later. This yields an access-control view “as of” that point.

Why it matters

Forward-only authorization.

A write authored before a member was revoked is judged against the access-control state that existed before the revocation — so it stays valid regardless of the order in which a peer happens to receive the write and the revocation. Authority is evaluated at the author’s cut, never at the receiver’s present. Governance builds the full membership and capability rules on top of this primitive.

One exception narrows a cut: an op of a signer whose removal is concurrent with it carries no authority, and the node’s projection leaves it out of every view. The set of such ops is a function of the op set, so the views and the scope root are the same in any arrival order.

Specification

The exact composition of the scope root. Every node must hash identical bytes in identical order, so the rules below are normative for interop. All integers are little-endian; every map is iterated in ascending key order (the determinism source).

scope_root = SHA-256( entities_root ‖ acl_hash ‖ groups_root )  // three 32-byte inputs

Important

Two entity roots — pick the right one for the wire.

The entities_root input has two sources. The projection can hash its own entity map (a self-contained root, used in tests and local checks). But the convergence signal exchanged on the wire folds the storage layer’s Merkle root as entities_root, with this projection’s acl_hash and governance_hash on top. The storage Merkle root is authoritative for the data plane; the projection never re-hashes entity state for the wire signal. A second implementation must fold its storage root here, not a re-hash of the entity map.

entities_hash (projection-local data plane)

// for each (id, value) in entities, ascending by id
h.update( id )       // 32 bytes
h.update( u64_le(len(value)) )
h.update( value )

acl_hash (access-control plane)

// for each (object_id, writers) ascending; writers ascending by key
h.update( object_id )  // 32 bytes
for (writer, mask) in writers:
  h.update( writer )  // 32 bytes
  h.update( [mask.bits()] )  // 1 byte bitflag

groups_root (membership + admin + policy + structure + caps)

The third component. The implementation names the function that computes it governance_hash, because it spans the scope’s admin, policy, and subgroups in addition to group memberships and capabilities — all of it folded in below.

// 1) groups — ascending; empty groups are skipped entirely
for (group, members) in groups, if members not empty:
  h.update( group )
  for (member, role) in members: h.update( member ‖ [role_byte] )
// 2) root admin
h.update( admin ? [1] ‖ admin : [0] )
// 3) policy
h.update( u64_le(len(policy)) ‖ policy )
// 4) live subgroups — ascending; only those whose latest exists=true
for (child, slot) in subgroups, if slot.live:
  h.update( child ‖ [parent if set] ‖ [restricted_byte] )
// 5) capability plane — each map ascending
for (group, caps) in default_caps: h.update( group ‖ u32_le(caps) )
for ((group,member), caps) in member_caps: h.update( group ‖ member ‖ u32_le(caps) )
for (group, admin) in group_admin: h.update( group ‖ admin )

Stable role encoding

Roles hash to an explicit byte — fixed independently of any in-memory enum order, so the root survives refactors:

Role	role_byte
Admin	0
Member	1
ReadOnly	2
ReadOnlyTee	3
RelayTee	4

Note the empty-group skip and the live-subgroup filter: materialized state must hash identically no matter how it was reached, so a phantom empty group or a deleted subgroup must never perturb the root.

Where this leads

A signed operation, a causally-ordered DAG, an order-independent fold to state, and a single scope root that makes convergence a hash comparison — that is the core of the protocol. Everything else applies this machinery to a purpose.

Next is Anatomy of State — a visual tour of how the DAG, the Merkle tree, and the on-disk column families actually lay this state out. After that, Execution shows where data operations come from (a running WASM application), and Governance shows how the authorization planes encode membership and authority.