State compression and concurrent Merkle trees

A Merkle tree is a binary tree in which each leaf is labelled with a hash of some data. Adjacent leaves are hashed together to produce the label of their parent, adjacent parents are hashed together to produce theirs, and the process continues until a single hash remains at the top. That final hash is the Merkle root, and it commits to every leaf beneath it: changing any leaf changes the root.

The root alone is not enough to prove that a particular record is in the tree. To do that, a verifier needs the record's leaf hash and the sibling hashes along the path from that leaf to the root. Those sibling hashes are the proof. Hashing the leaf with its proof reproduces the root, and if the reproduced root matches the one stored on-chain, the record is proven to be in the tree.

For compressed NFTs, the leaf is a hash of a schema that includes the leaf's identifier, its owner or delegate, a hash of its creators and a hash of its metadata. Everything needed to verify a single compressed NFT cryptographically is therefore inside the leaf, and the proof is what connects it to the on-chain root.

A plain Merkle tree has a problem when more than one write happens in the same block. Each write changes the root, and a proof that was valid against the old root is no longer valid against the new one. If several transactions try to mint or transfer against the same tree in the same slot, the first one to land invalidates the proofs the others were built against, and they fail.

The concurrent Merkle tree solves this by storing more than the current root. It keeps a changelog: a buffer of recent roots together with the paths of the leaves that were modified to produce them. When a transaction arrives with a proof that has been invalidated by an earlier write in the same block, the program can use the changelog to fast-forward the proof to the current root rather than rejecting the transaction.

The size of that buffer is a parameter chosen when the tree is created, and it sets how many concurrent changes can be absorbed within a single block. If more writes occur than the buffer can fast-forward, some transactions fail and have to be retried. The buffer is therefore a throughput parameter for the tree, and it is chosen based on how much concurrent activity the collection is expected to see.

The tree also stores the rightmost proof on-chain. Because new leaves are always appended at the rightmost position, having that proof available means an append does not need to send a proof at all. That is how a mint can be performed without the client having to fetch and supply proof data.

A concurrent Merkle tree is defined by three values, and each one trades account size against a different capability. Choosing them is the main design decision when creating a compressed collection.

The canopy deserves a note because its purpose is not obvious. A proof for a leaf at depth twenty consists of twenty sibling hashes, and each hash is thirty-two bytes. Sending all of them in a transaction would consume a large fraction of the transaction's size budget. Caching the upper portion of the proof path on-chain means the client only has to send the lower portion, which keeps the transaction within its size limit and makes the compressed record easier to compose with other programs.

The saving is real, but it is not free. The most significant cost is that the data is no longer directly readable from an account. A program that wants to inspect a compressed record cannot simply load an account and read a field; it has to be given the record and its proof, and it verifies them against the root. That makes compressed records harder to compose with than ordinary accounts, and it is why the canopy exists — to keep the proof small enough to pass around.

The second cost is the indexer. Because the data lives in the ledger rather than in account state, reading it requires something that has watched the ledger and recorded what it saw. The standard approach is an indexer that observes the program's logs and stores the metadata that was hashed into the tree, so that a client can look up a record by its identifier. Without an indexer, the data is still on-chain in the sense that it is in the ledger, but it is not conveniently queryable.

The third cost is the concurrency limit. The changelog buffer bounds how many writes can be absorbed in one block, and a collection that exceeds that bound will see some transactions fail and need retrying. That is a throughput ceiling on the tree, and it has to be sized against the expected activity. It is a different kind of limit from the account-level contention described on the local fee markets page, but it has a similar shape: a single shared structure that serialises writes against it.