Divide and conquer

A Solana transaction is small, compute is limited, and one big account gets more expensive with every user. Divide and conquer splits a program's state into many small accounts and keeps the values every action needs in one central account. A transaction touches only the accounts its action needs, so its cost stays the same however big the program grows.

In algorithms, divide and conquer means splitting a task into independent parts, solving each on its own, and merging the results. Solana programs split their state the same way, because of the chain's limits. Each part is a separate account, and values that combine all the parts, like a total, live in one central account.

Remember from the constraints lecture that a transaction is small and bounded. Keep all of your program's state in one account, and you hit those limits as the program grows.

A transaction can use at most 1.4 million compute units, so work that grows with the data, like a loop over every user, eventually stops fitting. An account can never grow past 10 MiB.

With Anchor's Account type, the program deserializes the whole account when the instruction starts and, if the account is mutable, writes all of it back at the end. Change one byte in a 10,000-byte account, and the program still processes all 10,000. The data must also fit in the program's heap, which is 32 KiB by default and 256 KiB at most. So a regular Anchor account stops working long before 10 MiB. Zero-copy accounts skip deserialization and the heap, but a loop over their data still hits the compute limit.

Solana also runs transactions in parallel, except those that write the same account. If every user writes to one account, their transactions run one after another.

The pattern is to store the data in many small accounts, called partitions, plus one central account with the values every action needs, such as a total, the current price or a Merkle root. A transaction includes only the partitions its action needs and the central account.

Splitting has one cost. Every account a transaction uses adds its 32-byte address to the 1232-byte limit, however big the account is. One big account takes 32 bytes, and every partition adds 32 more, so a good split keeps each action to a few partitions.

Often the transaction that changes a partition also updates the central account, so the user who acts pays to keep it current. We call this Pay-As-You-Act. When that is not needed or costs too much, programs update the central account separately, for example with a job anyone can call, like those in the untrusted executor lecture.

Orca Whirlpools is a concentrated liquidity DEX. Liquidity providers pick a price range, and prices are split into small steps called ticks. Each tick records how much liquidity starts or ends at that price.

With the smallest price steps, a pool has about 887,000 possible ticks. At 113 bytes each, that is around 100 MB, ten times what one account can hold. Even in pools with fewer ticks, every swap would load and save all of them to use a few.

So Orca groups ticks into tick arrays, separate accounts of 88 ticks each. A tick array exists only once someone creates it, usually a liquidity provider opening a position in that range. A range where nobody has ever opened a position has no account at all. The pool account is the central state, holding the current price, the current tick and the active liquidity.

A swap passes the pool account and up to three tick arrays, the ones the price can move through. The client picks them, and every other tick array stays out of the transaction. So the program loads at most 264 ticks, three arrays of 88, however many the pool has. The same swap updates the price and liquidity in the pool account, which is Pay-As-You-Act at work.

The split has costs. A swap can only move the price as far as its tick arrays reach, so the client must pick them correctly. And every swap still writes its pool account, so swaps in one pool run one after another, while swaps in different pools run in parallel.

A regular NFT is several accounts, such as a mint, a metadata account and a token account, each with its own rent deposit. Bubblegum, Metaplex's compressed NFT program, keeps a million NFTs in one account.

It stores them as a Merkle tree. Each NFT is a leaf, a hash of its data, and leaves are hashed in pairs, level by level, up to a single root. Change one bit in any leaf and the root changes, so storing the root protects every NFT in the tree.

The partitions here are not accounts at all. Indexers keep the NFT data off-chain, reading it from the transactions that created and changed each NFT. When an action needs an NFT, the client brings its data, and the program checks it against the root.

To make that check possible, the client also sends the hashes along the leaf's path to the root, one per level. A million leaves means 20 levels, since 2^20 is 1,048,576, so the path is 20 hashes. The program recomputes the root and compares it with the stored one. If they match, the leaf is really in the tree, so its owner and data are correct.

The account also keeps a short history of recent changes. A client builds its proof against the root it last saw, and if another update lands first, the history lets the program still accept that proof.

Twenty 32-byte hashes take 640 bytes, more than half of a 1232-byte transaction. So the tree account also stores the top levels of the tree, called the canopy. With a 10-level canopy, the client sends only the bottom 10 hashes, 320 bytes. The canopy has a cost. Ten levels hold about 2,000 hashes, around 65 KB, and the tree creator pays rent for all of it up front. A deeper canopy means shorter proofs and a bigger account.

ZK Compression applies the same idea to any account. Each account's data is a leaf in a Merkle tree, and the transaction brings the data when an action needs it. Instead of a path of hashes per account, the transaction carries one zero-knowledge proof that all of its accounts are in their trees. The proof is always 128 bytes, whether it covers one account or several. The account data still has to fit in the transaction, and checking the proof costs about 100,000 compute units.

Look at every account your program writes. If one grows with the number of users, orders, positions or items, it will hit one of the limits above.

For each such account, ask what a single action needs to read and write. That part becomes a partition. What all actions must agree on stays in the central account.

Then decide how the central account stays current, with Pay-As-You-Act or separately. Also check whether one central account can take all the writes. If it can't, write it only in the actions that must change it, or split it too, for example into several Merkle trees for one NFT collection.

Once the split is right, a transaction pays only for its own action.