Complexity asymmetry

Engineers choose a data structure by its cost in time and memory. On Solana, you also weigh the part of the work that runs on-chain, which can be far smaller than the total. An operation can cost O(n) in total and O(1) on-chain, because the O(n) part runs on the client.

On-chain programs add one more variable, the on-chain complexity. This is the work the program pays for. Compute costs compute units, with a limit per transaction, and memory costs rent for every account the program keeps. The rest runs on the client or on an indexer, a server that keeps a copy of chain data, and costs the program nothing. The gap between the total cost and the on-chain cost is called complexity asymmetry.

Remember from the constraints lecture that anyone can call any instruction. In most protocols anyone can also add data, by opening an order, creating a position or minting an item.

Now imagine an instruction that walks through all of that data. Every entry makes it more expensive, and an attacker can add entries cheaply. Once the walk needs more than the 1.4 million compute units a transaction allows, the instruction fails for every caller, and nobody can use that part of the program. This is a denial-of-service attack, or DoS.

So the work inside an instruction should not grow with data anyone can add, or should grow very slowly. O(log n) is fine, since a billion entries need only about 30 steps. A loop over a fixed-size list is safe too, because nobody can make it longer. Anything heavier belongs off-chain.

A sorted linked list is surprisingly common in Solana programs, though in general it is slow. Finding the position for a new element takes O(n), because you walk the list from the start. Linking it in is O(1) once you have the position.

On-chain, the search disappears. The client walks the list off-chain and sends the position with the instruction. The program only checks the two neighbors of the new element, which takes the same time however long the list is. The client spends O(n) to find the position, and the program spends O(1) to check it.

This holds only if the program reads just the elements it needs, as a zero-copy account allows. If it deserializes the whole account, it pays for every element on every call.

You met Monaco's order book in the role inversion lecture. Here is how it adds an order.

The book is one account with a fixed set of cells. Orders are sorted from the highest price to the lowest, and each points to its neighbors by cell number. A new order takes any free cell, so cell numbers do not follow the price.

The client works out where the new order goes and sends "after this order". The program checks three things. The order on the left is not cheaper than the new one. The order on the right is cheaper. Both cells hold open orders.

Because the right neighbor must be strictly cheaper, a new order always goes after older orders at the same price, so those fill first.

The cell numbers and prices in the diagram below are illustrative.

A fixed number of cells means the book never outgrows its account, so walking the whole book on-chain would also fit in the compute budget. But then every new order would pay for every cell. The neighbor check makes it pay for two.

The downside is a hard limit on open orders. An attacker could fill every free cell to block real traders, so each order locks some of its owner's funds to make that expensive.

Bubblegum from the divide and conquer lecture uses the same asymmetry for memory. One account keeps the root of a Merkle tree covering a million NFTs, and indexers keep the full tree off-chain.

To change one NFT, the client sends the leaf and the hashes on its path to the root, except the top levels the account already keeps in its canopy. The program rebuilds the root and compares it with the stored one.

Count the costs. The account's size is fixed and does not grow as NFTs are minted, so on-chain memory is O(1). The check walks one path from leaf to root, so on-chain compute is O(log n). The O(n) part, every leaf, lives with the indexer.

Why bother? A normal backend would never hash a million records into a Merkle tree. It puts them in a database and reads any one in a single step.

On Solana, the usual way to store a million records is a million PDAs, each a separate account with its own rent deposit. A Merkle tree replaces all of them with one account holding one root. That saving makes the Merkle tree one of the most popular structures on Solana.

When you choose a data structure, write down two complexities for every operation, the total and the on-chain part. Then ask how the on-chain part grows if someone adds a million entries on purpose. If it stays at O(1) or O(log n), the structure is safe. If it grows linearly, move the search to the client and leave the program only the check.

A textbook would not recommend a sorted linked list or a Merkle tree. On-chain, they are often the right choice once their expensive part runs off-chain.