Larry Engineer 🍡

@larry0x

I think I'm having a Eureka moment in performant blockchain design. Three main points:

1. Do not Merklize chain state. This removes a huuuuge overhead in both execution and disk usage!

2. Use an SQL DB instead of a raw KV store. Instead of the chain implementing a query server,

174

9:38 PM • Dec 26, 2023

... And to some extent, this is true. In the Sovereign SDK, for example, we find that our (mostly unoptimized) merkle tree update currently takes at least 50% of our total runtime. Although exact performance numbers vary, updating the state trie is also a significant bottleneck for Ethereum and Cosmos node implementations.

The commonly cited reason for this inefficiency is that maintaining a merkle tree incurs lots of random disk accesses. And indeed, if you look at existing merkle tree implementations, you'll find this to be exactly the case. But I think this state of affairs is more an artifact of history than a fundamental limitation of merklization. In this post, I'll outline a more efficient strategy for merklizing state data, which I hope will be useful to the broader community.

N.B. Although this post makes some original contributions, it also combines many existing optimizations into a single scheme. When ideas were not developed originally, I credit the original author in block like this one.

Background: Why is Merklization Expensive?

A Very Brief Introduction To Addressable Merkle Trees

N.B. If you're totally unfamiliar with merkle trees and want a better introduction, I recommend the Jellyfish Merkle Tree paper

Addressable merkle trees usually work by grouping intermediate hashes into sets of 16 (called a node) and storing them in a key-value store like LMDB or RocksDB, where the key is the node hash and the value is the node itself.

To traverse the trie, implementations do something like the following:

struct ChildInfo { 
  is_leaf: bool,
  hash: H256,
  // ... some metadata omitted here
}

struct Node { 
  children: [Option<ChildInfo>; 16]
} 

fn get(db: TrieDb, path: &[u4]) -> Option<Leaf> { 
  let mut current_node: Node = db.get_root_node();
  for nibble in path { 
    let child: ChildInfo = current_node[nibble]?;
    if child.is_leaf { 
      // Some checks omitted here
      return db.get_leaf(child.hash)
    }
    current_node = db.get_node(child.hash)
  } 
}

As you can clearly see, this algorithm requires one random disk access for each layer of the tree that needs to be traversed. A basic property of addressable merkle tries is that their expected depth is logarithmic in the number of items stored, and the base of the logarithm is the width of the intermediate nodes. So if your blockchain has five billion objects in state and uses intermediate nodes with a width of 16, each state update will need to traverse to an expected depth of  log_16(5,000,000,000) ~= 8. Putting all of this together, we can see that traversing a naive merkle trie will require roughly 8 sequential database queries per entry.

Compare that to the single query required to look up a value a "flat" (non-merklized) store like the one used in Solana, and you'll begin to see why merklization has such a big performance impact.

But Wait, there's More (Overhead)!

Unfortunately, this isn't the end of the story. In the previous discussion, we treated the underlying key-value store as if it could store and fetch values with no overhead. In the real world, though, lookups can be expensive. Almost all key-value stores use a tree structure of their own internally, which causes "read amplification" - multiplying the number of disk accesses for a random read by another factor of log(n).

So, for those of you keeping track at home, each read against a merkle tree incurs an overhead of log(n) ^ 2, where n is the number of items in global state. On Ethereum mainnet today, this log-squared factor is roughly 50 - meaning that each state update takes roughly 50 sequential disk accesses. When you observe that a typical Swap on Uniswap might write to 7 storage slots across 4 different contracts addresses and update the balances of 3 additional accounts, you can see how this becomes an issue.

This is the reason Ethereum doesn't just "raise the gas limit". Even though all the major full node implementations could easily a handle an order of magnitude increase in throughput today, the resulting state growth would eventually degrade node performance to an unacceptable degree.

Part 2: Let's make it better

But hang on... aren't merkle trees a theoretically optimal data structure? They should be fast! Can we make them live up to the hype?

I think so, yes. Here's how.

Step 1: Make the Trie Binary

The first thing to do is to decouple your data storage format from the logical structure of your merkle trie. While it's a good idea to store nodes into groups of 16 (or more!) on disk and in-memory, using a high-arity merkle tree wastes computation and bandwidth. The solution is simple. Store your nodes in power-of-two-minus-two sized groups where each cluster contains a rootless binary subtree of some constant depth. In plain english, store your nodes as arrays of size (say), 6, where the array represents a binary tree with depth (say) 2 - with the additional wrinkle that the root of each tree is stored at the layer above. (See diagram).

The reason we store data this way is to ensure that all of the siblings needed in order to make a proof for a particular leaf are stored in the same nodes as the hashes that will be modified. If we also included the root of the binary trie in the node, then we would have to do an extra disk access each time we wanted to do an update that touched the root hash of a node (since the sibling of the root would be stored is stored in a different node).

Using this binary layout, we can eliminate a significant amount of overhead. For example, when we want to prove an insertion at  q, we only need to perform four hash compressions: H(a || b), H(c || d), H(g || h), and H(q || r). This is significantly better than the number of compressions we would need to ingest a branch node in a 16-ary trie (roughly 9). Similarly, we only need to send four siblings in the merkle proof instead of the (minimum) 15 required by a 16-ary trie.

N.B. The idea of separating disk-format from tree arity is not new to Sovereign. It is already implemented in the Jellyfish Merkle Tree pioneered by Diem, and was suggested by Vitalik as least as early as 2018

Step 2: Improve the Disk Layout

Now that we've decoupled our on-disk layout from the underlying logical structure of the merkle tree, lets design the best possible layout.

N.B. Both Monad and Avalanche are doing related work at the same time this blog post is being written. Monad's work is still closed source, so it's not possible to assess how much overlap there is between our construction and theirs. Avalanche has open-sourced their FirewoodDB, but has not released much documentation, so I haven't yet had time to assess it in detail.

First, we're going to increase the size of our on-disk nodes to be the size of a page on a standard SSD. SSDs can’t read or write data in units smaller than a page - so storing smaller chunks than that just wastes IOPS. While there's some variance in the page size across popular SSDs, 4096 bytes seems to be a popular one. Let's start there.

Using nodes of size 4096, we can fit a rootless binary trie of depth 6 into a single node and still have 64 bytes left over for metadata. Great.

Now, how can we use our disk most effectively? Well, SSDs accesses have pretty high latency, but modern drives have lots of internal parallelism. So, we want to make sure that our lookups can be pipelined. In other words, the on-disk storage location where we keep a node should not depend on the specific contents of the merkle tree! That way, we can fetch all of the data at once, instead of reading one node at a time.

How can we pull that off? Simple - we give each node in our tree a unique key. Since we're using nodes of size 2^6 to store a binary tree of (logical) size 2^256, we have 2^250 distinct logical nodes that might be stored on disk. We'll give the root node the ID 0, its leftmost child the ID 1, and so on. To convert between the path to a node and that node's ID, we can use a relatively simple formula. The ith child of a the node with ID k has ID k * 2^6 + i.

Cool, now each node in our tree has a unique key. Using those keys, we can build a simple hashmap backed by our SSD. First, we pick some fixed number of blocks on the SSD to use for storing merkle tree nodes. Then, we assign each of those blocks a logical index. To compute the expected location of a particular node on disk, we simply use the formula index = hash(node_id) % num_blocks. In other words, it works exactly like a standard hashmap, just on disk instead of in memory.

The beauty of this construction is that it lets us look up all of the data on the path to a given node concurrently. Say, I want to update the merkle leaf at path 0x0f73f0ff947861b4af10ff94e2bdecc060a185915e6839ba3ebb86b6b2644d2f. I can compute exactly which pages of the SSD are likely to contain relevant merkle nodes up front, and then have the SSD fetch all of those pages in parallel. In particular, I know that my tree is unlikely to store more than a few trillion items, so in general I shouldn't find any non-empty nodes beyond the first ~40 layers of the tree. So, I can just fetch the first 40/6 = 7 nodes along the path - well within the capability of the SSD to handle in parallel.

But wait... hash maps can have collisions. How can we handle those? In the current setup, we can't. We can't even detect them. Thankfully, there's a simple fix that's been used in hash maps since time immemorial. If you're worried about collisions, just store the key inside the hash bucket alongside the value. By a lucky coincidence, our keys are just node ids - which themselves are just 250-bit integers. And as we mentioned before, each of our on-disk nodes happens to have 64 bytes of extra space. So, we can just follow the standard practice of storing the key along with its value and call it a day. With that setup in place, we can now detect collisions - so all that's left to do is figure out how to handle them. Since we still have about 32 bytes of extra space for metadata (which we can use to record the fact that a collision has occurred and link to the colliding node), this should be straightforward. There are a plethora of strategies in the literature (linear probing, quadratic probing, double-hashing, etc.), and a full discussion is out of scope for this article.

Whew, that was a lot. Let's take a moment and survey what we've built so far.

• We have a binary merkle-patricia tree, which gives us optimal hashing load and bandwidth consumption. This gives us performance which should be roughly equivalent to the best known constructions in terms of CPU, bandwidth, and (if we're using zk) proving cost.

• We have an on-disk structure which is mostly data independent. This means that in most cases we can fetch all nodes on the path to a particular leaf node with a single roundtrip to our SSD - taking full advantage of the drive's internal parallelism. Compare this to the naive merkle-tree construction I outlined in the first section, which needs 7 or 8 sequential database lookups, and about 50 sequential disk accesses due to nested tree structure.

Step 3: Compress your Metadata

At this stage, astute readers will have noticed a problem. Up to this point, we've made two contradictory assumptions:

Assumption 1: Every item we want to store is only 32 bytes long

Assumption 2: Operations are logarithmic in the number of items actually storedin the tree, rather than in the logical size of the tree.

These two assumptions can't co-exist naturally. For Assumption 2 to hold, we need to use an optimized leaf-node construction which allows us to elide empty branches of the tree (see the JMT paper for details). To make that work, we need to give leaf nodes a completely different structure from internal nodes. So we need a domain separator to allow us to distinguish between internal and leaf nodes. (N.B. Domain separators are a good idea for security reasons as well. Type confusion is bad!) But, we've already stipulated that each of the items in the tree is a 32-byte hash. If we increase the size to 33 bytes, our on-disk nodes will get too large to fit on a single SSD page, killing our performance.

Thankfully, there's a simple solution here too. Since all we need is a single bit of discriminant, we just borrow the one bit from our hash. In other words, we mandate that all internal nodes must have the leading bit set to 1, and all leaf nodes must have their leading bit set to 0. (That leaves us with 255 bits of hash output, which still leaves plenty of security margin.)

Step 4: Halve your Compressions

Thanks to our trick from the previous section, we can now guarantee the invariant that every internal node is the hash of exactly two children, and that each child has a width of exactly 32 bytes. That means that at each layer of the tree, we need our hasher to ingest exactly 64 bytes of data. By a shocking coincidence, 64 bytes happens to be exactly the amount of data that can be ingested by many hash "compression functions" in a single invocation. (Most notably, SHA-256).

Unfortunately, such fixed-length compression functions are insecure on their own due to length extension attacks - so they aren't exposed by common cryptographic libraries. If you invoke the sha256() function in your favorite programming language, the library will be secretly padding your input with 64 bytes of metadata to prevent exactly this issue. Such padding is mandated by the NIST standard, and is absolutely necessary to ensure collision resistance in the presence of arbitrary-length messages.

But in our case, the messages don't have arbitrary length. Internal nodes are always constructed from 64 byte inputs. And thanks to our domain separators, we can easily distinguish internal nodes (which have fixed-size inputs) from leaf-nodes (which do not). By exposing the internals of our favorite hashing library, we can reduce the number of hashes required for tree traversal by a factor of 2 by using a padding-free hasher for internal nodes.

(Note: Messing with hash functions should only be done with good reason, and always under the supervision of a qualified cryptographer! This optimization is most useful in contexts where you're proving statements about the tree in zero-knowledge. If you're only using the tree in "native" contexts, you may want to skip this one!)

Step 5: Blake is cool. Be like Blake.

So far, we’ve focused exclusively on internal nodes of the tree. Now, lets turn our attention to leaf nodes.

The first thing to do is to recognize that, despite all of our hard work, state trees are expensive. While we've drastically reduced overheads, the cost for each access is still logarithmic in the number of values stored. "Normal" hashing, on the other hand, is relatively cheap. You can do a standard (linear) hash of about a kilobyte of data for the same compute cost as a single merkle tree lookup (assuming a tree depth of 32). So, if two values have even a relatively small chance off being accessed together, you want to store them in a single leaf.

But increasing leaf sizes hits an efficiency ceiling disappointingly quickly. Using a linear hasher like sha256, you pay roughly one compression for every 32 bytes of data - so the "breakeven" leaf size is about one kilobyte. (In other words, if you'd need to add more than a kilobyte of data to the leaf before you'd expect that two distinct values from that leaf would be acessed together, then the clustering would not be worthwhile.)

Thankfully, there's yet another trick we can use to reduce the overhead. @fd_ripatel recently pointed out to me that Blake3 uses an internal merkle tree instead of a linear hasher. This means that it's possible to do partial reads and incremental updates against a Blake3 hash with only logarithmic overhead. With this advancement, the breakeven size of a leaf increases from about a kilobyte to over a gigabyte. In other words, if you're using Blake3 as your leaf hasher then your leaves should be really, really big.

Note: It seems like it should be possible to combine the padding scheme from Blake3 with the compression function from just about any secure hasher to yield an optimized leaf hasher. But IANAC! If you are a cryptographer and have thoughts on this, please reach out!

Step 6: Cache Aggressively

Last but not least, if we're going to make a performant merkle tree we need to cache aggressively. We'll start simple - the (physical) root node of the tree should always live in memory. Why? Because any read or write against the tree is going to read and/or write that node. By keeping this node in memory, we can already reduce our expected SSD load from 7 pages per query to 6 pages per query.

But we can go further. If we keep the next level of the physical tree in memory, we can eliminate one more page from each query. This only costs us an extra 256k of memory (since there are 2^6 nodes of 4k each at this height), and we've already reduced our disk IOPS by 30%.

Step 7: Be Lazy

Last but not least, we can improve our efficiency even using pretty standard tricks.

First, we should avoid reading from the merkle tree wherever possible. We can do this by storing our leaf-data in a "flat" key-value store so that we don't need to traverse the tree just to read data. This reduces disk IOPS and reduces tail latencies (since each page we avoid querying is one less opportunity for a hash collision). If the data is modified, we'll still end up needing to read the merkle path eventually - but this optimization is still well worth the effort since reads are so common.

N.B. Almost all merkle tree implementations already supporting reading data from a flat store without traversing the trie.

Second, we should always defer updates to our trie for as long as possible. The obvious reason for this is that two sequential updates might both update the same key (meaning that we can skip one trie update altogether). The less obvious reason is that a properly implemented merkle tree is asymptotically more efficient when updates are done in large batches.

The reason for this is relatively easy to understand. Suppose we have a sequence of four writes against the pictured merkle tree. Since the tree has depth 4 (excluding the root), we incur a cost of 16 hashes if we perform the updates sequentially (4 hashes per update time 4 updates). But if we perform the updates in a batch, we only need 9 hashes to compute the new root. Intuitively, this is because the hashing work for the top layers of the tree is amortized across 4 inserts. Even though we made four modifications, we only recomputed the root hash once.

Conclusion

Using the techniques described in this post, it should be possible to reduce the disk-induced latency of merkle tree operations a factor of ten or more, the computational overhead by a factor of two or more, and the total disk IOPS by a factor of 25 or more. With those improvements, it’s my hope that the cost of generating state commitments should no longer be prohibitive even for high throughput chains.

Of course, this approach is not magic. In engineering, tradeoffs abound. In this case, we achieve much of our IO performance gains by sacrificing the ability to store a complete archive of the merkle tree at all points in time. Also, we require lower-level interfaces to the SSD than standard constructions - which translates to some engineering complexity. Still, we’re excited to see where this approach leads!

Acknowledgements

Thanks to…

• Cem Ozer and Patrick O'Grady for reviewing drafts of this post.

• Zhenhuan Gao, Yuxuan Hu, and Qinfan Wu for the Jellyfish Merkle Tree paper

• Peter Szilagyi for his excellent talk on the physical limits of Ethereum (and for his tireless work on Geth)

• Richard Patel and @dubbel06 for introducing me to Blake3’s secret merkle hasher

• Emmanuel Goossaert for his excellent series on SSDs.

Final Note

Since this post is now approaching Jon Charb levels of verbosity, I’ve made the editorial decision to omit a complete description of insertion, deletion, and proving algorithms compatible with the general construction described here. You can find suitable algorithms in the Jellyfish Merkle Tree repo that Sovereign co-maintains. To understand the batched algorithms, see the Aptos fork of the JMT. I’ve also omitted some details related to crash recovery, but the problem is not too difficult (hint: use a WAL). Finally, I’ve left aside the question of storage for the leaf nodes of the merkle tree. The best store for that data will depend on the application, but either a key-value store or a custom database might be appropriate.

What is the Sovereign SDK Alpha Release?

This is an MVP release focused on a few core features that will give you a feel for the developer experience of the Sovereign SDK. Concretely, we've built:

• A demo rollup and prover

• Data availability layer adapters for Celestia and Avail (Thanks to the Avail team for implementing their adapter!)*

• A ZKVM adapter for Risc0**

• A module system that enables you to compose off-the-shelf modules and custom logic to build your application as a ZK-rollup

• Ready-to-use banking, storage, account, and centralized sequencing modules

• A simple and extensible RPC interface for reading application state

• A database layer to persist application state to disk, and an authenticated state store using a Jellyfish Merkle Tree

• And lots of documentation to make it as easy as possible to build your own rollup

It is important to note that the Sovereign SDK has not yet been audited and should not be used in production under any circumstances. During alpha, we will maintain API stability and compliance with semantic versioning only on a best effort basis.

What's next?

Over the next few months, we will be heads down productionizing our client: fixing known bugs, optimizing, improving developer experience, adding missing features like bridging and decentralized sequencing, and thoroughly testing the codebase.

Our goal is to reach beta (with APIs stabilized) in a year.

Why Sovereign SDK?

Once ready, the SDK will enable applications with:

• Guaranteed and Scalable Throughput: The Sovereign SDK will ensure a scalable, verifiable, and censorship-resistant backend that keeps pace with your application's growth, sparing your users from exorbitant fees.

• No Need to Bootstrap Validators: Developing your application is challenging enough. The Sovereign SDK will eliminate the need to persuade validators or worry about liveness issues if they fail to show up.

• Fast, Cheap, and Trustless Bridging: Users shouldn't worry about funds getting stuck in an application or paying unnecessary transfer fees to liquidity providers. With the Sovereign SDK, you will bid farewell to week-long withdrawal periods while securely scaling your application.

• Full Customizability: Use your token as the gas token or add custom transaction processing logic. The Sovereign SDK will empower you to fully customize your stack, freeing you to build a limitless application.

• Reduced Platform Risk: It's difficult to pick winners in the DA and zk-proof systems. Thankfully, our agnostic design will let you deploy rollups with any compatible DA layer (including Ethereum!) and zk-proof system, mitigating risks.

Ready to explore?

Check out the Sovereign SDK and start building your zk-rollup demo app! And fill out our early partner interest form if you have an idea you'd like to brainstorm with us.

The Internet of Rollups

We imagine a future where verifiable and censorship-resistant blockchain applications run side-by-side, scaling and communicating seamlessly.

Our mission is to enable anyone to build zk-rollups, not just cryptography experts or protocol engineers.

*: Tutorials to help you get started with the Avail adapter are coming soon.

**: The Risc0 adapter is currently limited as Risc0 does not support recursion yet.

By solving this problem, we’ll motivate a design for sovereign zk-rollups. Then, we’ll briefly explore the other advantages offered by sovereign designs.

Finality Bottlenecks… and How to Solve Them

For most zk-rollups, one of the largest expenses is proof verification. Depending on the underlying proof system, a rollup on Ethereum might spend anywhere from 300k to 5m gas to validate a single proof. But since proof sizes grow very slowly (or not at all) with the number of transactions, rollups can reduce their per-transaction cost by waiting to accumulate a large batch of transactions before submitting a proof. And indeed, this is exactly what most zk-rollups do today; popular rollups like StarkEx typically post proofs to L1 only once every few hours.

But waiting several hours for your transaction to finalize is an unacceptably bad user-experience. Can we do better? If a rollup posts raw transaction data onto its DA layer (rather than state diffs), then power-users who want fast finality can run full nodes. But if the rollup uses state-diffs, then even running a full-node doesn’t help. This is why most zk-rollups today have their sequencers give out “soft confirmations”. But soft confirmations are only possible in systems with centralized sequencers. So the question remains - how do we make decentralized zk-rollup competitive on latency?

If we only care about lowering the latency for full-nodes, then posting raw transaction data on chain solves the problem. As long as the full transaction data is available, full nodes can finalize as quickly as transactions can be applied (assuming the DA layer has single-slot finality). This lets our zk-rollup be just as responsive as a traditional L1!

This is a very powerful result. It makes zk-rollups viable for highly latency-sensitive applications like on-chain order books. Nevertheless, it doesn’t completely solve the original problem. What we really want is to reduce latency for light clients. Can we do that without drastically increasing proof verification costs?

Surprisingly, the answer is still yes! Here’s how: instead of waiting to create a single batch proof, we can create proofs in real time and use recursion to aggregate them into a batch proof later. As long as we distribute incremental proofs right away via the p2p network, light clients will experience fast finality. And since we’re still just posting the slower batch proofs on chain, we don’t have to pay extra for on-chain verification. In other words, we still get a trust-minimized bridge with the L1 - but the bridge is no longer the source of truth for light clients. Congratulations, we’ve just built a sovereign rollup!

Proving the Fork Choice

Eagle-eyed readers will have noticed a problem with the system described in the previous paragraph. In today’s rollups, the L1 smart contract is responsible for enforcing the rollups fork-choice rule. In other words, the smart contract doesn’t just verify the zk-proof, it also checks that the proof builds on the previous proof (and not some other fork), and that it’s processed all of the relevant “forced transactions” which were sent on L1. So, if we don’t use a smart contract, how do we pick a canonical fork?

Once again, the answer is surprisingly simple - if we require proofs to be posted as calldata on the L1, then we can add a rule that a new proof is only valid if it builds on the previous valid proof. Although we could enforce this rule client-side, it would require users to scan through the chain’s history all the way back to genesis (or at least some widely known checkpoint) - which isn’t ideal.

Thankfully, it’s not too hard to add it directly into the zk-proof instead. By tying calldata back to the L1 block headers, we can add a statement saying “I have scanned the DA layer for proofs (starting at block X and ending at block Y), and this proof builds on the most recent valid proof”. This lets us prove the fork-choice rule directly, rather than enforcing it client side! And if we’re already scanning the DA layer for proofs, we can easily scan for forced transactions as well.

Portability and Interoperability

In the Smart Contract rollup paradigm, the L1 bridge is unique. Since the bridge is responsible for checking statements that aren’t included in the proof (statements like “this proof includes all of the forced transactions”), adding proof-based bridges to other destinations doesn’t usually make sense. But once we’ve moved all of our logic inside the proof, this is no longer an issue. We can add bridges anywhere we want!

And we can even go a step further. If our L1 smart contract is just a regular bridge, we can do away with it altogether. For the first time, it makes sense to think about building rollups on systems that don’t support smart contracts. Just take your existing rollup logic and remove the L1 bridge. Suddenly, you can deploy on any DA layer! In other words, your rollup logic becomes instantly portable across different L1s.

Conclusion

The future of rollups is sovereign. By proving their fork-choice rules directly, sovereign zk-rollups enable seamless interoperability, instant portability, and fast finality. Just like smart-contract rollups, they provide low gas costs and trust-minimized bridges - but they aren’t forced to trade-off between cost and latency. Sometimes, you can have your cake and eat it too 🙂

As always at Sovereign, we’re building in public. All of our code is free and open source, and contributions are welcome. Oh, and we’re hiring. If this sounds interesting, come build with us!

Why ZK-Rollups?

In this section, we’ll try to explain why we think zk-rollups are the “endgame” for blockchains, from first principles.

The Price of Atomic Composability

We start from the thesis that Ethereum’s killer feature isn’t the EVM itself, it’s atomic composability. Any smart-contract can interact with any other one, and the system guarantees that the caller won’t get stuck in some intermediate state - even if something goes wrong further up the call stack. This drastically simplifies the programming model, making Ethereum one of the friendliest environments for developers. But atomic composability comes at a price. In order to execute a call atomically, full nodes need to access the relevant state of all contracts in the call stack in real time. That means that they have to have all of the relevant state stored locally, and they need to be able to load it very rapidly. In other words, full nodes need to buy SSDs, and they need to buy enough of them to store the entire chain state.

To maximize scalability, systems like Near attempt to relax these requirements. Instead of atomic composability, Near only allows asynchronous cross-contract calls. This setup allows much more scalability, since each contract’s state can be stored only on a dedicated subset of full nodes. But it comes at great cost to the programmer - who has to reason through a combinatorial explosion of code paths.

Best of Both Worlds

Our vision is the synthesis of these two extremes. We believe that no fully atomic system can scale to the needs of the entire world. But at the same time, we recognize the central role that atomicity plays in developing simple and composable smart contracts. And so, we seek to achieve the best of both worlds: an ecosystem of optimized chains that each provide atomic composability, connected by fast (but asynchronous) cross-chain bridges across the ecosystem.

Within a single chain, developers retain atomic composability. Contract designs can be relatively simple, and users can know the outcomes of their transactions in near-real time. But at the same time, no set of full nodes is responsible to store and update the state of the entire world.

Build rollups, not Blockchains

We certainly aren’t the first people to think along these lines. As far as we know, the first attempt to create an integrated multi-chain system was Cosmos. Much like our vision, Cosmos is a bottom-up ecosystem of heterogeneous chains with fast and reliable bridging. Where Cosmos falls short is in the ability to create new chains. Before a chain becomes useable, it needs a “validator set” to throw meaningful economic weight behind its operation. Costs of capital being what they are, it’s extremely difficult to attract a validator set to a chain until the chain has enough usage to create significant revenues. But of course, no user wants to risk their money on an insecure chain. This leads to a chicken-and-egg scenario, and makes launching new chains a herculean undertaking.

In addition, Cosmos chains face fundamental difficulties in implementing bridges. Their light client bridges (IBC) are expensive to maintain because headers have to be processed on-chain. This results in a sparse bridge graph, which translates into a bad user experience. Even worse, funds can be lost if a chain suffers a long-distance reorg or its validator set executes an invalid state transition.

Our solution to these problems is simple: share a validator set with many other chains. In other words, don’t build blockchains; build rollups.

This, at last, leads us to our offering: the Sovereign SDK.

What is the Sovereign SDK?

The Sovereign SDK is a toolkit for building asynchronously-proven, sovereign zk-rollups. That’s quite a mouthful, so let’s go through it piece by piece.

First, what does it mean that transactions are proven asynchronously? In plain English, it simply means that raw transaction data is posted to the L1 by a sequencer in real-time, and proofs are generated later. This is in contrast to rollups like StarkNet, where proofs are generated off-chain before any data is posted on chain. The advantage of asynchronous proving is that it allows transactions to be finalized in real-time, giving the rollup responsiveness like that of an Optimistic Rollup.

Second, what does it mean for a rollup to be sovereign? This is easiest to understand by contrast with a “smart-contract” rollup. In a smart-contract rollup, the L2 state is only final (in the view of light clients) when it is accepted by a smart-contract on the L1. Because today’s L1 chains have such limited throughput, smart-contract rollups are forced to update their canonical on-chain state relatively infrequently. On the other hand, light clients of sovereign rollups are responsible to decide for themselves if a particular block should be accepted. This allows sovereign rollups to finalize much more quickly, since they don’t have to throttle their update frequency to accommodate congested L1s.

How Does it Work?

The Sovereign SDK works by abstracting the functionality of a zk-rollup into a hierarchy of interfaces. At each level of the hierarchy, developers are free to use one of the pre-packaged implementations provided by the SDK or build their own functionality from scratch. By encapsulating logic behind well-defined interfaces, we’re able to provide pluggable components that create a simple developer experience without sacrificing flexibility.

The Core APIs

At the highest level of abstraction, each Sovereign SDK chain combines three distinct elements:

1. An L1 blockchain, which provides DA and consensus

2. A state transition function (written in Rust), which implements the "business logic" of the chain

3. A zero-knowledge proof system capable of (1) recursion and (2) running a subset of Rust

interface DaLayer {
  // Gets all transactions from a particular da layer block that are relevant to the rollup
  // Used only by full-nodes of the rollup
  function get_relevant_txs(header: DaHeader) -> Array<DaTxWithSender>
  // Gets all transactions from a particular da layer block that are relevant to the rollup,
  // along with a merkle proof (or similar) showing that each transaction really was included in the da layer block.
  // Depending on the DA layer, may need to include auxiliary information to show that no 
  // relevant transactions were omitted.
  // Used by provers
  function get_relevant_txs_with_proof(header: DaHeader) -> (Array<DaTxWithSender>, DaMultiProof, CompletenessProof>
  // Verifies that a list of Da layer transactions provided by an untrusted prover is both 
  // complete and correct.
  // Used by the "verifier" circuit in the zkVM
  function verify_relevant_tx_list(txs: Array<DaTxWithSender>, header: DaHeader, witness: DaMultiProof, completenessproof: CompletenessProof)
}

// The interface to a state transition function, inspired by Tendermint's ABCI
interface StateTransitionFunction {
    // Called once at rollup Genesis to set up the chain
  function init_chain(config: Config) 
  // A slot is a DA layer block, and may contain 0 or more rollup blocks
  function begin_slot(slotnumber: u64) 
  // Applies a batch of transactions to the current rollup state, returning a list of the
  // events from each transaction, or slashing the sequencer if the batch was malformed
  function apply_batch(batch: Array<Transaction>, sequencer: Bytes): Array<Array<Event>> | ConsensusSetUpdate
  // Process a zero-knowledge proof, rewarding (or punishing) the prover
  function apply_proof(proof: RollupProof): Array<ConsensusSetUpdate>
  // Commit changes after processing all rollup messages
  function end_slot(): StateRoot
}

interface ZkVM { 
  // Runs some code, creating a proof of correct execution
  function run(f: Function): Proof
  // Verifies a proof, returning its public outputs on success
  function verify(p: Proof): (Result<Array<byte>>)
}

Generalized Full Node

Using the core interfaces we just described, the Sovereign SDK will provide a generalized full-node implementation capable of running almost any state-transition function over any data availability layer. In general terms, the full node works by encapsulating rollup functionality behind the core interfaces we just described, and treating rollup data as opaque byte strings that can be stored and transmitted. To give you a sense of how the full node will operate, here’s a rough illustration of what the core event loop will look like.

// A pseudocode illustration of block execution. Plays fast and loose
// with types for the sake of brevity.
function run_next_da_block(self, prev_proof: Proof, db: Database) {
  // Each proof commits to the previous state as a public output. Use that state 
  // to initialize the state transition processor
  let prev_state = deserialize(prev_proof.verify());
  let current_da_header = db.get_da_header(prev_state.slot_number + 1);
  let processor = stf::new(db, current_da_header, prev_state);
  
  // Fetch the relevant transactions from the DA layer
  let (da_txs, inclusion_proof, completeness_proof) = da::get_relevant_txs_with_proof(current_header);
  da::verify_relevant_tx_list(da_txs, inclusion_proof, completeness_proof)
  
  // Process the relevant DA transactions 
  processor.begin_slot(prev_state.slot_number + 1)
  for da_tx in da_txs { 
    let msg = parse_msg(da_tx);
    if msg.is_batch() { 
      processor.apply_batch(msg)
    } else {
      processor.apply_proof(msg)
    }
  }
  processor.end_slot();
}

Pluggable Components

Because the full node implementation is completely general, developers can easily swap out modules to change the characteristics of their chain. For example, a developer who was very concerned about the cost of calldata would probably use Jupiter, our integration with the Celestia blockchain. On the other hand, a developer who cared primarily about access to liquidity might build on top of Ethereum or EigenDA (we’ll have a pluggable module for this too, but it won’t be developed until after the prototype stage).

Similarly, developers are free to choose their own zkVM - as long as it supports no_std Rust and a few shim APIs. Developers who prefer to use a standard compiler toolchain and VM interface will likely pick Risc0, while those who value small proof sizes might pick another VM like that of the =nil; foundation.

Default Modules

Jumping down a layer of abstraction, the Sovereign SDK also aims to simplify the process of creating state transition functions. Toward this end, we’ll provide a composable module system loosely inspired by the Cosmos SDK. Although we’ll continue building out functionality over time, we plan to launch with at least the following modules: storage, bridging, (fungible) tokens, and proving/sequencing.

As of this writing, the design of the module system is still in its early stages - so everything you read in the section is subject to rapid change. But, we still think it’s useful to sketch out some of the designs we’ve been working on just to give you a taste of what’s to come.

The Bridging Module

First up, bridging. Unlike bridging between separate chains (which is known to be impossible without strong trust assumptions), bridging between rollups on a shared DA layer is not fundamentally difficult. In the Sovereign SDK, we plan to take full advantage of this fact to provide low-latency trust minimized bridges by default.

It works like this: assume you had 50 rollups running on a shared DA layer. To run trust-minimized bridges between each of them in the standard paradigm, you would need every rollup to run an on-chain light client of every other rollup. Doing the math, that’s 50 * 49 = 2450 on-chain light clients. Since this would be prohibitively expensive to actually execute, you’d fall back to using multi-hop bridges instead. You’d have each chain connects to (say) 3 other chains, and - assuming your networks had a reasonable topology - you’d be able to route messages between any pair of chains using 3 or 4 hops.

With the power of zk, we can do much better. Recall that any two zero-knowledge proofs (in the VM model) can be aggregated into a third proof, and that this new proof is no more expensive to verify than the originals were. Leveraging this insight, we can recursively aggregate all 50 rollup proofs off-chain, and then verify that aggregate proof on each of the rollups. So instead of maintaining 2450 light client connections, we can do one off-chain proof aggregation and 50 on-chain proof verifications. In other words, we’ve reduced the communication complexity of all-to-all bridging from O(n^2) to O(n).

The Storage Module

A key component of efficient zk-rollups is state management. When designing an authenticated data store, developers have to juggle several competing concerns. On the one hand, they want something that’s efficient to represent in-circuit, since every read and write to state has to be authenticated inside the zero-knowledge proof. On the other hand, they want something that’s fast and lightweight during native execution so that it doesn’t bottleneck full-nodes and sequencers.

In the Sovereign SDK, we plan to provide a default storage module which balances these two design goals. For efficiency outside of the zkVM, we’ll use the Jellyfish Merkle Tree (JMT) originally developed by Diem, to store authenticated state data. For rapid access, we’ll also maintain a flat on-disk data structure to hold raw state. For efficiency in-circuit, we’ll make our JMT generic over hash function so that developers can easily plug in a hash tailored to their choice of zkVM.

Putting it All Together: the Block Lifecycle

Adding a block to a Sovereign chain happens in three steps. First, a sequencer posts a new blob of transaction data onto the L1 chain. As soon as the blob is finalized on the L1, a new logical rollup state is finalized as well.

As each L1 block is finalized, full nodes of the rollup scan through it and identify the blobs that are relevant to the rollup’s state transition function. Then, they apply the rollup’s STF to each of these blobs in order, computing the new rollup state root. At this point, the block is subjectively finalized from the perspective of the full nodes.

Next, prover nodes (full nodes running inside of a zkVM) perform the same process as full nodes - scanning through the DA block and processing all of the data blobs in order. Unlike full nodes, however, provers race against one another to generate proofs and post them on chain. The first eligible node to create a valid proof is rewarded with tokens corresponding to (some portion of) the rollup’s gas fees. Once a proof for a given batch has been posted on-chain, the batch is subjectively final to light clients.

Finally, a relayer may choose to submit a recent rollup proof to a bridge smart-contract on another chain - either the underlying DA layer or another rollup. For efficiency, relayers will probably use proof aggregation to combine validity proofs of many rollups into a single proof before submitting updates.

Conclusion

If you’ve made it this far, you should now have a good high-level understanding of the Sovereign SDK. If you’re interested in learning even more, dive into our github (contributions welcome!), reach out on Twitter, or come hang on Discord! Also, we’re hiring!

The Problem: Blockchain Apps Don’t Scale

Monolithic L1s Don’t Scale

In the quest to scale blockchain apps, three dominant paradigms have emerged: application-specific layer 1s, optimistic rollups, and zk-rollups. App-specific layer 1s are the simplest to design and implement - but they come with a significant drawback. Every layer 1 has to recruit its own validators and convince them to stake enough capital to defend the chain against attacks. Costs of capital being what they are, this approach is only viable for a few well-funded apps.

Optimistic Rollups Break Composability

Rollups try to solve this problem by allowing developers to extend existing blockchains with new logic, rather than starting new ones. This drastically decreases the barrier to entry for app-chain development.

But optimistic rollups (the rollups that dominate the market today) are not a panacea. In order to minimize the burden on the shared validator set, optimistic rollups rely on fraud proofs to prevent misbehavior. During an attack, these fraud proofs might be censored - so optimistic rollups have long “finality delays” during which transactions could be rolled back by the appearance of a fraud proof. This makes bridging out of optimistic rollups slow and costly.

So, optimistic rollup developers have to make a tough choice: do they build narrow, special-purpose rollups and expect users to bridge frequently between chains? Or do they build general-purpose rollups that try to satisfy all of a user’s needs in one place? Neither choice is good. Bridging between optimistic chains is too slow, too expensive, and too risky to be an everyday operation. But general-purpose optimistic rollups suffer from many of the drawbacks of monolithic L1s: not only do they suffer from scalability issues of their own, but they also fail to support the full diversity of functionality that app-chains can create.

Zk-Rollups are the Future

For all of these reasons, we expect zk-rollups to emerge as the dominant scaling paradigm. They share the advantages of optimistic rollups, but without the long finality delay. Instead of waiting days to see if a fraud proof appears, users can be confident that their transaction is final as soon as a validity proof is created - a process which can take mere seconds.

But if zk-rollups are the superior scaling solution, why isn’t everyone using them? Because until now, actually building zk-rollups has been a huge undertaking - requiring years of effort from expert cryptography engineers.

Enter Sovereign: The Internet Of Rollups

What is the Sovereign SDK?

The Sovereign SDK aims to do for zk-rollups what the Cosmos SDK did for layer 1 chains.

It will provide all of the boilerplate that would usually go into a blockchain - a p2p network, a database, and an RPC node - letting builders focus on the business logic of their chain. In addition, it will provide a set of default modules that operate efficiently in a zero-knowledge environment: a token implementation, an authenticated data store, and a bridging module. Developers will be able to combine these primitives into app-chains, or build their own state-transition functions completely from scratch by implementing a standard set of APIs.

Even better, the Sovereign SDK will be the first rollup framework to abstract away the details of zero-knowledge. To take advantage of its power, developers won’t need to become experts in cryptography. Instead, developers will be able to write their apps in idiomatic Rust (or eventually C++), and the SDK will automatically compile it to an efficient zk virtual machine.

What properties will the Sovereign SDK provide?

1. Sovereign SDK rollups will be seamlessly interoperable. We use a novel bridging technique based on proof aggregation to allow Sovereign SDK rollups on a shared L1 to bridge back and forth without a trusted third party. Since zk-proofs can be aggregated, rollups will be able to maintain as many bridges as they want at minimal cost. Off-chain relayers can aggregate the proofs of all the peer rollups into a single proof, and just that single proof can be verified on chain. And since state transitions are proven to be valid, there will be no need to pay fees to a liquidity provider or wait a week for transactions to finalize. Bridge right away, with no drawbacks.

2. Sovereign SDK rollups will be securely scalable. By purpose-building every component especially for use in zk-rollups, the Sovereign SDK will provide excellent performance by default. Thanks to advances in parallelism, our proving will have latencies measured in seconds. And with the magic of zero-knowledge proofs, chains will be able to scale without sacrificing end-user verifiability.

3. Sovereign SDK Rollups can run on any blockchain. Sovereign SDK chains delegate the responsibility for checking proofs to the end user, not the underlying L1. This is what makes them “sovereign” rollups as opposed to smart-contract rollups. Since the data availability layer doesn’t need the capability to verify proofs, Sovereign SDK rollups are automatically portable across any L1. Write once, run anywhere.

Where are we now?

We’re currently hard at work developing the Sovereign SDK. Our current roadmap is split into three phases.

Phase 1: Research (In Progress)

The Sovereign SDK is currently undergoing R&D. We’re in the process of designing the default storage module, cryptoeconomics, and core APIs. (If you’re interested in working on these problems, check out our jobs board!). We’re also working on a research prototype. Although the SDK will support a wide range of data availability layers and proving systems, our current prototype integrates Celestia for data availability and Risc0 for proving. We expect this phase to be complete around Q2 2023.

Phase 2: Initial Implementation

The initial implementation of the Sovereign SDK will begin in parallel with the remaining research. During this time, we’ll implement a peer-to-peer network, an RPC node, the core APIs, and default storage and sequencing modules.

Phase 3: Hardening

Once the SDK is feature complete, we’ll need plenty of time for code cleanup, testing, fuzzing, and audits. We’ll also begin developing our first use cases of the SDK during this time (more details on these to be announced!). We expect to see mainnet chains using the SDK after about six months of hardening the initial implementation.

Make scaling simple

At Sovereign Labs, we want to see blockchains support billions of users. That will only happen if zero-knowledge technology is accessible to developers without a PhD in cryptography - and if building rollups is accessible to developers who aren’t expert protocol engineers.

But limitless scalability is worthless if it comes at the expense of the end-user verifiability. If building, running, or viewing the state of your blockchain requires the cooperation of some centralized entity, then we have failed. That’s why the Sovereign SDK will always be completely free and open source - and why we’re committed to engineering every component of the stack for maximum resilience. But don’t just take our word for it. We’re building in public - come see for yourself.

Scaling should be simple. With the Sovereign SDK, it finally will be.

Resources

• Join our team

• Follow us on Twitter

• Join our Discord

• Check out our Github

Acknowledgments

We really appreciate our supporters, especially Tim Beiko, James Prestwich, Mustafa Al-Bassam, Chris Ahn, and Ekram Ahmed, for reviewing drafts of this post, and their guidance along our journey.