How to use compressed NFTs on Solana, powered by state compression

Initialize the tree

The first thing you need to do is initialize the Merkle tree. There are three parameters to any Merkle tree: 1) Depth (capacity), 2) buffer size (concurrency / latency), and 3) canopy height (composability).

Depth is easy —t he capacity of a perfectly balanced concurrent Merkle tree is 2^{DEPTH}, and trees can be configured to hold anywhere from eight leaves all the way up to a billion (2^30). In this case, leaves can be NFTs.

Buffer size is an approximation of the number of concurrent updates that can happen in the same block. Merkle trees typically have an issue whereby any modification of the tree causes any previously computed proofs to go out-of-date, but with this novel concurrent Merkle tree implementation, stale proofs can be fast-forwarded and still be accepted by the smart contract. A buffer size of 64 means that any given proof will still remain valid for up to 64 updates of the tree, after which it must be recomputed. Buffer size can be anywhere from eight to 2048.

Canopy height specifies the portion of the tree that remains on-chain, reducing the amount of proofs that have to be submitted by clients for verification. Given the current transaction size limits on Solana, this is the only feasible way to pass enough proofs to be able to validate the existence of trees with a depth > 20. Canopy height maxes out at 17.

Rather than initialize one giant tree to hold everything, I recommend issuing numerous, smaller trees of varying sizes. This reduces write-lock contention on the tree account, as well as provides more opportunities for composability by reducing the number of proofs needed to be submitted for any given modification.

Choose a canopy height that maximizes composability — while it costs more in rent, a canopy height that is DEPTH-3 provides a similar interface to existing NFT-related smart contracts that already pass 3 accounts. For example, a tree of depth 20 could have a canopy of 17 so that clients only need to submit three proofs to make any modification to a tree.