Merkle state and proofs

What the state trie is

The state trie is the authenticated key-value store a UniNet chain keeps its state in. StateTree wraps one SparseMerkleTrie, and every typed accessor on it — balances, nonces, element records, file manifests, storage plans — is a read or write against that one trie under a prefixed key. The trie's root is a 32-byte BLAKE3 hash that changes whenever any of those values changes.

The problem it addresses is that a node answering a query is asking to be believed. A response saying "your file manifest is X" carries no information about whether the node is reporting state or inventing it. A Merkle proof converts the answer into something a third party can recompute: given the proof and a root obtained from somewhere else, the claim either reproduces that root or it does not.

Node types and key paths

A key is expanded to nibbles by key_to_nibbles before it is walked: each byte becomes two path elements, high half first. A file-manifest key is 33 bytes, so its nibble path is 66 elements long at a branching factor of 16. The trie does not materialise 66 levels for it — descent stops at the first leaf, which stores the unconsumed nibbles in key_remainder.

   key    f5 3a ...        33 bytes: 1 prefix + 32 hash
   path   f  5  3  a ...   66 nibbles; branches consume one each,
                           the terminal leaf holds whatever is left

| | Fields | What its hash commits to | Terminal | | --- | --- | --- | --- | | Branch | 16 optional child hashes, optional value | every child slot, present or empty, and the value | only when the key ends here, or the slot is empty | | Leaf | remaining key nibbles, value | the suffix it claims and the value verbatim | always | | Extension | shared prefix nibbles, one child hash | the prefix it collapses and the child it points at | never |

TrieNode::hash() is BLAKE3 over the Borsh serialization of the whole node. That is the property the rest of the design rests on: a parent committing to a child's hash is committing to the child's entire content, not to an opaque digest of a value. The empty trie's root is the hash of an empty branch.

Extension is handled everywhere — get, insert, delete, prove and verify all have an arm for it — but nothing in the crate ever introduces one. Every TrieNode::Extension constructor in sparse_trie.rs sits inside a match arm that has already found an extension, and a trie starts life as an empty branch. So a trie built by these operations is branches down to a leaf, and no proof this node generates contains an extension. The verifier's extension arm still has to be right, because a proof handed to verify is whatever the caller supplies.

Insertion is immutable. insert_recursive rebuilds the nodes along the path bottom-up and stores each one under its own content hash, so an old root and every node reachable from it remain in the store. When the trie is constructed with a backend, each node is written through at trie:node: followed by its raw 32-byte hash, and save_root writes the current root at trie:root. The node runs that backend as a DiskBackend under an EncryptedBackend in the state directory.

What a proof contains

MerkleProof has three fields: path, an ordered Vec<TrieNode> from the root node down to the terminal node; value, Some for inclusion and None for exclusion; and key_nibbles, which binds the proof to one key.

The path carries whole nodes, not sibling hashes. MerkleProof::verify(root, key) therefore does not combine hashes pairwise — it recomputes each node's own hash and checks it against what the previous step committed to, starting with root itself:

   root ──hash──▶ path[0]  Branch   child[nibble] ──▶ expected
                  path[1]  Branch   child[nibble] ──▶ expected
                  path[2]  Leaf     terminal: compare value

Verification rejects a proof whose key_nibbles do not equal the expansion of the key it was handed, and it requires the walk to reach a terminal decision. Five points decide, and each must fall on the last node in the path. Three prove absence outright: a branch whose slot for the next nibble is empty, a leaf whose stored remainder differs from the key's, and an extension whose prefix diverges — all three require the proof's value to be None. A leaf whose remainder matches decides by comparing its stored value to the proof's. A branch reached with the key exhausted compares its own optional value to the proof's, which is an inclusion check when both are present and an absence check when both are empty. A path that ends early while the key continues into a present child is rejected, and so is an empty path: a unit test asserts a fabricated zero-length exclusion proof does not verify against an arbitrary root.

One consequence follows directly from nodes being hashed over their full serialization: a proof cannot be redacted. The terminal leaf's value is in the path, and removing it makes the path stop hashing to the root.

The endpoint

POST /api/storage/proof, handled by merkle_proof in the node's storage API. It is registered on the inner router, so like every /api/* route it is reachable only by re-dispatch from the UNP tunnel at POST /unp — the public listener serves /unp/* and rejects everything else. It is authenticated, and it does not accept a trie key. The caller names what it wants proved; the key is derived server-side from the authenticated identity, so no key outside the caller's own namespace is reachable.

| Request field | Meaning | | --- | --- | | kind: "file" with file_id | proves the caller's own file manifest; key is f followed by BLAKE3(identity ‖ ":" ‖ file_id) | | kind: "storage_plan" | proves the caller's own storage plan; key is s followed by the 32-byte identity element id | | chain_id | optional; anything other than the primary chain id returns 501 rather than silently answering about the primary |

The identity is read from the x-unp-identity header, which the UNP gateway injects after verifying the session token and which it strips from inbound client headers.

| Response field | Contents | | --- | --- | | target | the label for what was proved, e.g. file:deadbeef | | key | hex of the derived trie key, so the verifier can expand the same nibble path | | exists | whether the proof is an inclusion or an exclusion proof | | value_hash | hex BLAKE3 of the value, present only on inclusion | | root_hash | hex of the trie root the proof was generated against | | proof_path | array of hex-encoded Borsh serializations of the path nodes, in root-to-terminal order — or null | | path_withheld | a reason string, present only when proof_path is null | | verified | the result of the node running verify on its own proof against its own root |

proof_path is withheld when any value carried in the path differs from the caller's own. That case is not exotic: the terminal node of an exclusion proof is usually a neighbouring key's leaf, which belongs to a different identity, and its value is in the serialization. Deriving the key from the session stops a caller naming someone else's key; it does not stop a walk from ending on one. The rule is mechanical — the handler compares every Leaf and Branch value on the path against the proof's own value — and the intended case, proving your own entry is present, normally leaves the terminal leaf as the only value on the path.

verified is the node checking its own arithmetic. It is useful as an internal consistency signal and it is worth nothing as evidence, for the reason set out next.

What verification actually requires

To check the proof yourself you need three things: proof_path, the key, and a root you already trust. The first two are in the response. The third cannot be, because a root supplied by the party being checked makes the check circular — it proves the node is internally consistent with a number it chose.

The root in the response is this node's current trie root, which is the post-execution root of the latest applied block. Block headers commit a state root, but deliberately not that one. BlockHeader::state_root is the root the block executes against — the state as of the parent — because a proposer cannot know the post-execution root before executing, and cannot execute before the block is committed without speculating on a round that may lose a view change. So the root a proof is served against is the root committed by the next block's header. Genesis is the exception: block 0's header carries the root of the state after genesis allocations are applied.

| What you must already hold | Where it comes from | What the node's HTTP API actually hands you | | --- | --- | --- | | the state root as of block N | state_root in block N+1's header | GET /api/blocks/:height and /api/blocks/latest return it as hex. Neither handler reads an identity header, but like every /api/* route they are reachable only through the UNP tunnel, never from the external listener. | | the header that carries it | the same endpoints | A summary, not the header. The JSON carries height, hash, parent hash, state root, transaction count, timestamp, proposer and — on /api/blocks/:height — view and sequence. It omits transactions_root, receipts_root and chain_id, three of the ten fields BlockHeader::hash covers, so the hash it reports cannot be recomputed from the fields beside it. | | the commit signatures over that header | not over HTTP | No route returns header.signatures. /api/chains/:id/blocks returns a signature_count and nothing more. Full blocks, certificate included, move only on the peer-to-peer BlockResponse path, which the receiving node drops unless the message envelope carries a verifying signature. |

Block::verify_signatures is real and strict — it takes the whole block, rebuilds commit_payload from the signature-free encoding, counts distinct validators whose Ed25519 signature over it verifies, and requires 2f+1 where f = max_faulty(n) = (n-1)/3. A repeated node_id is counted once. Chain::apply_block runs it, via Block::verify, on every block above height 0 that it applies, whichever path delivered the block. It is not something a client holding only the JSON above can run, because the JSON contains neither the signatures nor the bytes they cover.

Every node also runs verify_state_root before executing a block, refusing one whose commitment differs from its own root, so a divergence stops the chain at the next block instead of compounding. Two limits on that are in the code and matter more than the mechanism. verify_state_root accepts a zero commitment as "unverifiable" and returns Ok. And the quorum arithmetic for a single-validator chain is 2·0+1 = 1: on the single-proposer path the node builds the block, signs it with its own key, and applies it. On that deployment the signature backing the header is the key of the party serving the proof, so the chain of custody closes on itself. The proof is still a real proof — it still binds a value to a root — but the root is not independently attested. What makes a root worth trusting is a validator set you did not get from the node you are questioning.

What this design does not address

• A root handed to you by the prover. Verifying proof_path against root_hash from the same response always succeeds and demonstrates nothing. The root has to arrive by a path the prover does not control.
• Confidentiality of the path. Node hashes cover values verbatim, so a path cannot omit a value and still verify. The endpoint's only available response is to withhold the entire path, which is why an exclusion proof for a key with a populated neighbour returns path_withheld.
• Arbitrary state. The endpoint proves two things: a file manifest and a storage plan, both the caller's own. Balances, nonces and element records live in the same trie and have no proof endpoint.
• Historical roots. prove answers against the trie's current root and the handler takes no root parameter, so there is no way to request a proof against the state as of an earlier block, even though the content-addressed store still holds those nodes.
• Getting the anchoring root over HTTP. The block endpoints return a state root but not the header fields or commit signatures that would let a client check who stood behind it. Anchoring a proof to an attested root is a peer-to-peer operation today, not an API call.
• Child chains. A chain_id other than the primary is refused with 501 rather than answered against the primary chain.
• What the value means. A verified inclusion proof establishes that these bytes sit at this key under this root. Whether the bytes are a well-formed manifest, and whether the writer was entitled to write them, are questions for execution and delegated authority.

Compared with the domain registry

The same workspace contains a second thing called a Merkle proof, and it is not one. DomainRegistry::lookup returns a DomainLookupResult whose proof field is built as a one-element vector holding the hash of the looked-up leaf, annotated in the source as simplified. Its registry_root is recomputed as BLAKE3 over the concatenated leaf hashes of every entry, sorted by domain name — a flat digest of the whole set, with no interior nodes and no sibling path. A leaf hash there is BLAKE3 of the domain name concatenated with its chain id, so the root does not commit to a registration's owner, registration time or expiry at all.

| | State trie | Domain registry | | --- | --- | --- | | Structure | 16-way trie of Branch and Leaf nodes | flat list, hashed in sorted order | | What the proof carries | every node from root to terminal | the leaf's own hash | | What a verifier needs | the proof, the key, a trusted root | every entry in the registry | | Proves absence | yes — an empty branch slot, or a leaf holding a different remainder | no | | Cost of a wrong answer | the recomputed root differs from the trusted root | nothing is detected |

Recomputing the registry root requires the full entry set, at which point you have the data and the proof adds nothing. Treat the state trie's proofs as verifiable and the registry's as a placeholder in the shape of one. The registry's other properties — registration, ownership, expiry, .unp derivation — are covered in domains.

How it composes

The proof target is derived from an identity: the file key hashes the identity id with the file id, and the storage plan key is the identity's element id with a one-byte prefix. An identity is therefore the unit of namespacing in the trie as well as of authentication.

The root a proof anchors to is produced by execution and committed by the block that follows it, so the value of a proof is bounded by how much you trust the validator set that signed that block. For a single-node deployment — see running a node — that bound is one key.

What the design does and does not defend against, across the network rather than inside the trie, is set out in the threat model.