Solana Builders — ZK Compression

In the days following Helius and Light Protocol’s announcement of their Zero-Knowledge (ZK) Compression project on Solana, there has been much discussion about ZK Compression. A significant portion of the conversation has focused on nomenclature. Is it a ZK rollup? An L2? Or something else entirely?

Why is this important? Some people within the Solana ecosystem believe that the arguments around nomenclature are unnecessary. I partially agree that the name we use is not as important as what it does — but it’s still important because those names refer to constructs that have specific properties and group them together. Thus, calling it XYZ can tell us about its properties and trust assumptions — and those we should care about!

Properties

Let's list some properties that Solana has that we're interested in before we evaluate them in the context of ZK-Compression:

1. Synchronous Atomic Composability
2. Concurrency
3. Safety
4. Liveness
5. Censorship resistance

Initial Trust Assumptions

We'll use the term "trustless" to apply to the security assumptions of a full node. This definition is our baseline. Anything a full node can't do alone involves additional trust assumptions. (Sidenote: a full node is the only trustless way to interact with a protocol. If someone tries introducing additional trust assumptions — bridge, committee, multi-sig, ZK, fraud, or whatever and claims that it's trustless, they’re wrong).

Some Background

I'll try to briefly give the necessary background about Solana to understand ZK-Compression using quick bullet points. 

• Solana state is stored on the disks of full nodes in the “AccountsDB”
• The unit for storage is called an "Account"
• Accounts have addresses (32 bytes each)
• The amount of data an account can store varies - between 0 to 10 MB (max)
  • Storing 10 MB in Solana costs roughly 70 SOL paid by the creator of the account. This cost is tied to storage and not the number of accounts — it can be 1x 10MB or 1000x 10KB accounts.
  • The current size of all accounts on Solana is 76GB (compressed)
• Every Solana transaction needs to specify all the accounts it reads and writes to
• Solana transactions are currently capped at 1232 bytes (a proposal exists to increase this)
• Each Solana transaction needs to specifysome text
  • Signatures (64 bytes each)
  • Accounts (32 bytes each)
  • Instruction data (arbitrary length)
  • Recent blockhash (32 bytes)
  • Program addresses (32 bytes each) (CPI: cross-program invocations)
• Solana transactions include a 32-byte “recent blockhash”  that must land within the most recent 150 blocks ) or be considered invalid and need to be re-signed and re-submitted

Lifecycle of a Normal Transaction

When a transaction is typically executed, the lifecycle is as follows:

1. Age check (only recent transactions are valid), deduplication, structural verification, fees (gas), and signature checks are first performed on a transaction
2. The program bytecode is loaded based on the program address, and the Solana Virtual Machine (SVM) is instantiated
3. All the accounts referenced by the transaction are checked, loaded from storage into memory, and passed to the SVM
4. The program bytecode is executed
5. Any modified accounts are synced back into storage in their updated state

The primary motivations for ZK-Compression are:

• On-chain state is expensive. For example, one thousand accounts cost 70 SOL, so products like Drip Haus get expensive quickly
• Even without full state Merkelization, more accounts to store on disk means larger snapshots, larger indexes, etc.
• Not all accounts are accessed frequently, so incurring a continuing resource cost is unnecessary

So, What is the Simplest Way to Achieve Compression?

Instead of storing accounts on disk and reading them when needed (step 3 in the transaction execution lifecycle), a transaction can pass in the account data as part of the payload, saving on the costs associated with on-chain storage. But this opens up a new problem—how can you enforce the rule that users are not lying about the state?

For example, let's say the off-chain value of an account that stores a token balance is 1200, and its owner field has “BYixJwV32DjeuyRww72PwZMyKcaedN533GBrv7CDh4n9”. If you submit a transaction with that data to the chain, then how would the chain know that you didn’t lie about how many tokens the address “BYixJwV32DjeuyRww72PwZMyKcaedN533GBrv7CDh4n9” has? After all, the full node processing the transaction doesn’t have access to the off-chain data — it expects you to provide the data with the transaction.

You can use Merkle proofs for this. Without going into detail about Merkle proofs, consider that they are a way to "commit" to some data in a verifiable way with a small on-chain storage footprint. All the full nodes synced with the chain store that small "commitment," and when someone provides the data in a transaction, they can also provide a "proof" in the same transaction that can be verified against the commitment. This proof is cryptographically secure.

Are there any issues with this? The issue is that Merkle proofs can be large. If a tree contains 100,000 accounts, the proof size for one of these accounts is 17 * 32 = 544 bytes. If you want to provide proofs for multiple accounts, in the worst case, it ends up multiplying by the proof size, so ten accounts in the worst case would be 10 * 544 = 5440 bytes. This space issue is specific to Solana because a Solana transaction is currently limited to 1232 bytes, whereas other chains tend to be less restrictive. Refer to the section above, where we list the size of each component — programs, signatures, recent blockhash, etc. So even in the best case, you use half the transaction size just for the Merkle proof. 

There are a few questions that arise here: 

1. If the transaction size is 1232 bytes, how are you sending the full data as part of the transaction?

This is an excellent question. ZK Compression is useful for a very large number of accounts if they consist of small amounts of data. Token balances (8 bytes per token), small amounts of metadata for NFTs, etc. — 100 bytes of data can easily fit into a transaction. 1000 bytes is hard, considering there's other stuff that goes into it. If you need your accounts to store larger amounts of data, this method (and ZK Compression) won't work.

One nuance to this claim is that the same logic used in ZK Compression can be used for parts of the account state. This means that while fitting the complete data of an account in a single transaction payload is not possible, there are still ways around it — specifically committing and providing proof for partial data.

2. Are Merkle proofs the only way to do this?

No. A Merkle proof is just one kind of a vector commitment. It has a commitment size of 32 bytes and a proof size of Log₂(N) * 32 bytes where N is the size of the vector that you're committing to. That's where we got the 17 from given that Log₂(100000) is 17. But there are constant proof size commitments as well (KZG, Pedersen); in fact, ZK-Compression uses one such method! 

3. You say the account data normally stored on a full node as part of the state must be provided along with the transaction. Where is that data stored?

Very good question, and one that affects our trust assumptions and properties. The answer is - anywhere! Specialized RPC servers can store this data; it can be part of Filecoin or IPFS, or the user can even store it on their own machine. The important thing is that as long as all the elements of the vector are stored somewhere, the proofs can be calculated on the fly. We'll cover the implications of where this is stored in the properties section. 

4. Can other chains do this?

ZK-Compression specifically requires zk-SNARK verification to be cheap. So this works out well on Solana since compute is cheaper than storage. The generalized concept of using vector commitments and proofs for data provided to each transaction is possible on other chains, but compute being expensive means that the trade-off is less prominent than it is on Solana. In fact, a persistent verification gas cost compared to a one-time SSTORE actually works out to be more expensive on  EVM-based chains.

What is ZK-Compression?

• If you don't know what ZK Compression is, this section covers that
• If you have a vague idea of what it is, I'd still suggest reading this section because there are some common misconceptions
• If you know exactly what it is, I'd kindly request you to read it so you can correct me if I got something wrong :) 

If you understood the above section, you understood 90% of what ZK Compression is. The primary issue was the Merkle proof size, so all ZK Compression is, is using a scheme to prove a computation.

If you don't know what ZK is, it doesn't matter all that much. All you need to know is that it’s a way to prove that you carried out a computation "correctly." A simple example is that you want to prove you multiply two numbers to get a 3rd number. i.e., 4*3 = 12

The “ZK way” to prove this is to have the following function:

f(x,y) = x*y

If you generate a circuit for the above code, the prover generates a proof of correct computation. The circuit itself is the commitment, so everyone knows what the "computation" you're running is. But the beautiful thing is that they don't need to know the inputs. once you run f(3,4), it returns 12 and the "proof." Now anyone can take 12, "proof," and verify that you multiplied SOME two numbers to get 12. They don't know if you did 4,3 or 6,2, or even 12,1. The fact that you hide those numbers and someone can still verify is where you get the “zero knowledge” part.

Why am I explaining this? This generalized concept is incredibly powerful in proving that you carried out a certain computation and got a certain result. Once someone has the result and the proof, they can verify whether you did it correctly without actually running the computation. And this is true of ANY arbitrary computation. I just multiplied two numbers, but you can even use it to say, "I verified these ten signatures, and they're all valid". This is the second benefit and one of the biggest reasons zero-knowledge proofs are used even when you don’t need to “hide” something. Because you’re turning a problem that requires running 1000 computation steps (or even a million) into a problem that requires just verifying one proof to know that the computation has been done correctly. The caveat is that proof generation takes some time.

ZK Compression uses the same technology to run the actual Merkle tree membership logic. So, it has a circuit that can take the account data, a proof (128 bytes), and verify that the data is indeed part of the "commitment" on the chain. (The actual proof is 256 bytes, but a convenient thing with elliptic curves and points is that if you know the curve, you only need one point to obtain the second point).

This is done primarily to reduce the proof size to a constant 128 bytes, which still leaves a lot of room (relatively speaking) for the data of small accounts. While a normal Merkle proof is Log₂(N), ZK Compression is always constant so that you can have a very large number of accounts under a single commitment. (For reference, a Merkle proof for 100,000 accounts would be around 550 bytes, which is half the transaction payload) 

Generating this proof can be done off-chain, but verifying this proof has to be done on-chain since a program needs to know that you provided the right data for an account before it can allow execution to proceed. The basic mechanism to verify ZK proofs must be there to do that. The specific prover system that ZK-Compression uses is called Groth16 and it, in turn, relies on the alt_bn128 syscall, which is currently feature-gated in mainnet and is under testing.

The cool thing is that the mechanism that ZK-Compression uses can be used to verify arbitrary computations (not just "does this leaf belong to a tree that has this root?").

One primary benefit of ZK Compression is that it provides all the plumbing for a developer to not have to deal with the "ZK” part at all. From a developer's perspective, they treat it as just any other account with the same fields, etc., so inside the program, it can be treated as a regular account. There is value in abstracting away most of the "ZK magic" and not having developers deal with it.

ZK Rollups

Without going into too much detail, ZK rollups mostly use the same concepts that ZK-Compression uses. The main similarity is that the entire rollup state is represented as a single root in the base layer (Ethereum), which is why there are a few claims that ZK-Compression is a rollup. There are crucial differences, however.

Let's consider 100 rollup transactions. The entire ZK rollup is treated as a circuit (like the multiplication program we used as an example). All 100 transactions are verified (signature, contract logic, deduplication check, etc.), and one single proof is generated for

"After applying 100 transactions, the state root changes from A to B". Once the proof is verified, the smart contract updates the state root from A to B.

In ZK-Compression, however, each of the 100 transactions contains one proof that simply tells you that the account data is correct, but the state transitions (generated by transactions) are actually executed on-chain as part of the SVM itself. Once the proof is validated, it's treated as a regular account. This is critical in terms of the composability property that we'll discuss next.

Properties Revisited

Now, we come to the interesting part. What are some properties of Solana that ZK-Compression retains?

1. Synchronous Atomic Composability

If I have a transaction that references 2 ZK-compressed accounts and 10 "normal" accounts, It doesn't break the composability feature. An instruction referencing a ZK compressed account can call another instruction/program referencing a "normal" uncompressed account. This feature is completely retained even if two accounts are compressed under different trees. If one instruction fails, the complete transaction is rolled back (atomic), and changes from an instruction called in line 1 are visible to line 2 (synchronous).

This is not true for rollups since ZK rollups cannot call each other either synchronously or atomically (unless they take global locks and allow cross rollup rollbacks)

2. Parallelism

This feature has some impact on parallelism and each case is worth considering:

1. Writes to multiple compressed accounts under the same tree: Each tree is concurrent on its own. This means that if users are reading/writing from two compressed accounts under the same state root, they can execute concurrently, and the state root can be updated concurrently. The logic here would be the same one Solana uses for concurrent Merkle tree updates in cNFTs
2. Writes to the same compressed account: Each compressed account is not concurrent. If two users try to write to the same compressed account, then one of the transactions will fail regardless of ordering. During normal execution, the writes to an account from the previous instruction are available to the next instruction, but with ZK compressed accounts, the proof of the account data would be invalid since it’s a proof of the previous state

Another point to note is that the large compute unit (CU) usage of compression lowers the max concurrency per tree since each account can only take up 12M compute units per block, given the account CU limit.

(Note: While synchronous atomic composability is an issue with most rollups, the Parallelism property is more so stated to highlight no additional components are required to enable ZK Compression, such as sequencers, etc. The lack of a sequencer means that the base chain is performing the ordering. Now we can discuss how the same property is true for a based rollup, but it’s not true for most rollups since they use centralized sequencers for ordering)

Trust Assumptions

While anyone can store all the raw data needed to generate the proofs and submit transactions, this is an additional trust assumption that impacts the liveness of the state that is compressed. If, for some reason, the data is "lost" or there's a delay, then you won't be able to submit a transaction unless you have the data stored yourself. Fortunately, this is what is known as an f+1 problem and not a 3f+1 problem, which requires Byzantine fault tolerance. An f+1 problem just requires one honest node to provide the data, and since proofs are "self-verifiable," there is no "safety" issue. There is primarily a "liveness" issue and a censorship vector.

Both regular rollups and ZK-Compression require a validity proof to be supplied. But while rollups encode the complete state transition function inside the validity proof, ZK-Compression only encodes "Is the account data correct?" So, the trust assumptions are slightly different here. In the compression case, the trust assumptions are primarily for state access (while state transition is done in full). In the rollup case, the trust assumptions are for the complete state transition function (from the view of the base layer). The security assumptions regarding the number of bits or the hardness/intractability of the underlying problem are the same (Bilinear Diffie-Hellman Assumption), but it’s *what* you’re trusting that security model for that’s different - state access vs execution. I only mention it because it’s important to know where additional trust assumptions are being added and where they are not.

Currently, the program that verifies the ZK-compressed accounts is upgradeable, but it can be made immutable or frozen in the future since it only performs a highly specific operation (opening Merkle proofs), which doesn't really require constant upgrades.

Additionally state compression can also be achieved in two more ways.

1. A proposal to increase transaction size (proj-3x-tx channel in Solana discord) is under development. Once it goes live, you can use regular Merkle proofs if the size is feasible
2. Once the alt_bn128 syscall is live, it can also be used for a regular vector commitment of constant proof size (KZG works with any pairing-friendly curve, including alt_bn128). This doesn't require a ZK-prover circuit

What Do We Call This?

Unfortunately, terms like rollup, L2, and Validium have been very loosely applied to the point where some rollups aren't even rollups. They don't inherit the base layer's liveness, safety, or censorship resistance. While Helius has been accused of using a "marketing term," the same people have used "rollup" very loosely to refer to projects they have invested in for that same reason — marketing. In fact, non-rollups are tagged with different stages just so they can continue calling themselves rollups.

Not everyone is guilty of this- some people have been brutally honest about using precise terminology and have spent man-months arguing with people who use imprecise terminology to mislead users (shout out to Toghrul, who has consistently called for precise terminology from *everyone*).

Given that it has some properties and trust assumptions that are different from a rollup, calling it a rollup could confuse users. Calling it a Validium is also too broad since it ignores the fact that synchronous atomic composability or parallelism aren't broken, the data availability (DA) is on-chain, and not to mention that the state transition function itself is trustless (since the full nodes are executing the actual programs in full, and not simply verifying a validity proof for the execution itself). Some people might argue that ZK-proofs are trustless, but that simply isn't true — while they are greatly trust minimized — mathematically, the security assumptions are not the same (they might be sufficient for 99% of the use cases, but it does impose an additional trust assumption over that of a full node — for example, the Bilinear Diffie Hellman Assumption in the case of a pairing curve based zk-SNARK). But of course, since ZK-Compression is using the snark to check the validity of the account itself, it is fair to say that ZK-Compression is not trustless — there are trust assumptions for ZK-compressed accounts that don't exist for "normal" accounts. So it’s somewhere between trustless and a full-fledged ZK rollup.

If we use names to infer properties, then I would make a claim that calling it a "rollup" doesn't convey the presence of those properties or trust assumptions. Come up with a new name, perhaps? ZK-Compression sounds just fine as long as the trust assumptions are clear.